This week's lab consists of questions to look at on your own (not to be turned in) and a significant programming task. The program for this lab is considered a "team program" (groups of size 2 or 3 permitted) for honor code purposes. Collaboration within a group is, of course, unrestricted. You may discuss the program with members of other groups, but what you turn in must be your own group's work. Groups must be formed no later than 4:00 PM, Friday, February 18, 2005, and be confirmed by all group members by electronic mail to terescoj@cs.williams.edu. All group members will be assigned the same grade for the lab.
Warning: Significant design and programming effort will be necessary to complete this lab. You may use any programming language you wish. If you are not a C expert, you may choose to use this as an opportunity to become an expert or maybe you will think better of it and become a C expert when we write the Unix shell. The case studies and writeup are worth 25% of the lab grade, so keep that in mind as you plan your time.
You do not need to turn in answers to these questions. But they could certainly form the basis for potential exam questions.
Discrete event simulation is a method used to model real world systems that can be decomposed into a series of logical events that happen at specific times. The main restriction on the system is that an event cannot affect the outcome of a prior event. When an event is generated, it is assigned a timestamp, and is stored in an event queue (actually, a priority queue). A logical clock is maintained to represent the current simulation time. At any point in the simulation, the next event to take place is at the head of the event queue. Since nothing of interest can happen between the present simulation time and the timestamp of the event at the head of the event queue, removal of an event for processing allows the logical clock to be incremented to that event's timestamp.
Multiple events may have the same timestamp. This models events that happen concurrently. Even though the events are processed sequentially by the simulator, they occur at the same logical time.
We use this model to simulate a simple operating system. Processes arrive in the system and take turns on the CPU, possibly spending some time waiting for I/O service. Each process remains in the system until its predetermined computational needs are met. There are a small number of events that can occur that will affect the system, and it is these events that drive the simulation.
You are to design and implement a discrete event simulator to model a CPU scheduler. You will then use your simulator to conduct studies of the performance of round robin (RR) and related scheduling algorithms.
The basic version of your program should implement a queueing system, as shown here:
Processes enter the system and wait for their turn on the CPU. They run on the CPU, possibly being pre-empted by the scheduler or for I/O service, until they have spent their entire service time on the CPU, at which point they leave the system.
Context switch time is entered as a parameter by the user and should be accounted for.
Conduct two (three if you are in a group with three members) studies of your own choosing using the simulator. These should involve comparisons of statistics such as CPU utilization, turnaround times, and queue lengths, as system parameters are varied. You are encouraged to e-mail me with your ideas to make sure they are appropriate before you go too far.
The most meaningful statistics are collected after the system stabilizes, that is, after the system has been under "load" for a while. The first processes to arrive enter an unloaded system and their behavior may not be typical of long-term trends. Wait until hundreds of processes have entered the system before gathering statistics, or run your simulation long enough that the behavior of these early processes will not have a significant effect on the long-term trends you are studying. Choose parameters that will result in several thousand (or more) processes passing through the system before the simulation ends. Some combinations of parameters produce mostly meaningless results, such as when processes arrive much more quickly than the CPU can process them. Avoid these situations in your studies.
If your simulator is not finished in time to use it for this part of the lab, you may generate your results using mine.
You should submit a writeup that includes a description of each of your two (or three) studies. Your discussion of each study should include what you expected would happen and what actually happened, conclusions you can draw from what happened, a critique of the model, and how your studies might apply to a "real world" situation. Include graphs to show trends as the key parameter(s) change.
Include this writeup in your lab submission as a single postscript or PDF file lab2-studies.ps or lab2-studies.pdf.
Since real computer scientists don't use Office, you are encouraged but not required to generate your writeup using LaTeX. You might also want to consider using gnuplot to generate your graphs. Both packages are available on the CSLab FreeBSD systems. There is a sample LaTeX document in /home/faculty/terescoj/shared/latexexample.