You may work individually or in groups of two or three on this project. Groups must be formed by our class meeting on Tuesday, September 17.

Discrete Event Simulation

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.

System Description

You are to design and implement a discrete event simulator to model a round-robin (RR) CPU scheduler. You will then use your simulator to conduct studies of the performance of RR scheduling.

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.

• Time: A logical clock is used to coordinate all events in the system; the "ticks" of the clock are measured in (arbitrary) "time units." The total simulation time is a parameter supplied by the user.
• Ready queue: The ready queue is FIFO (first-in, first-out). A process is selected from the front of the ready queue when the CPU becomes available. The CPU becomes available when a process leaves the CPU because it has been completed, because it has been pre-empted, or because it requires I/O service. If the ready queue is empty, a process entering the ready state will be assigned to the CPU immediately.
• New process entry: The time between the arrival of new processes entering the system's ready queue is a random number of ticks; these random numbers have an exponential distribution about a user-supplied mean value. Each time a process enters the system, an event is generated that will result in the creation of the next process to enter the system.
• Process CPU requirements: The amount of CPU service time (total number of ticks elapsed while the process is in the CPU) required by the process will be a random number of ticks selected at the time the process first enters the system. This random value has an exponential distribution whose average is a user-supplied parameter.
• Quantum: Each process can spend up to, but not more than, one quantum in the CPU before it is switched out. The quantum is a system wide constant value, entered as a parameter by the user.
• Removal of processes from the CPU: When a process is assigned to the CPU, an event should be generated that will remove it from the CPU at a later time.
  1. If the time remaining for the process to complete is less than the time to the next I/O fault or the quantum, an event is generated that will cause the process to leave the system. Performance statistics for the process should be collected when this event is processed.
  2. Else, if the time remaining for the process to I/O fault (see next item) is less than the quantum, an event is generated that will cause the process will leave for I/O service.
  3. Else the process' quantum will expire. An event is generated that will return the process to the ready queue.

  Context switch time is entered as a parameter by the user and should be accounted for.

• I/O faults: The process executes for a set number of clock cycles between each I/O fault. This number is constant on a per-process basis - it is determined for each process when it is created, and remains the same for the duration of the process. It will be a uniformly distributed random number whose average is (1)/(2) the time needed to run the process.
• I/O Service time: The time needed to service an I/O fault is constant throughout the system. This is a user-supplied parameter. Assume that the I/O subsystem can handle an infinite number of requests at the same time with no loss of turnaround time. When each process enters I/O service, an event is created to take place at the time of the service's completion.

User-supplied parameters

Statistics to Gather

Implementation Notes

• You may use any programming language, as long as it can be compiled and run on the Williams CS FreeBSD or Solaris systems.
• A graphical user interface is not required, but you are welcome to provide one. Remember to design your simulator to facilitate the gathering of statistics for the studies (scripts are good, copy and paste is bad). Thus, you may wish to include an option to run without a GUI.
• The directory /home/faculty/terescoj/shared/cs432/project1 contains some files you may find useful. These include a sample Makefile, C source code and header files for functions that generate uniform and random distributions and do screen management. Also, a working executable, compiled for the Williams CSLab FreeBSD systems, is available in the file sim in that directory.

Submission of simulator source code

• Submit documented source code, with a brief README file that describes how to build and run your simulator. All necessary files should be submitted using turnin as a single "tar" file, project1.tar. Include a Makefile to allow easy compilation.
• The software and documentation is worth 50 homework/project points. Correctness, design, documentation, style, and efficiency will be considered when assigning a grade.
• Submit by 12:01 AM, Tuesday, September 24, 2002.

Studies to be conducted using the simulator

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 project, you may generate your results using mine.

What to turn in:

1. A formal 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.
2. Also include a list of two (or more) possible enhancements that would allow your system to simulate a real operating system more accurately. Briefly describe what deficiency of the current simulator each enhancement would address, and how difficult you believe it would be to implement each enhancement in your system.

Submission of simulator studies

• Submit a single postscript or PDF file, project1.ps or project1.pdf, using the turnin utility.
• Since real computer scientists don't use word processors, 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.
• The writeup is work 25 homework/project points. Both content and writing style will be considered when assigning a grade.
• Submit by 12:01 AM, Thursday, September 26, 2002.

Honor Code Guidelines

Collaboration within a group is unrestricted. You may ask the instructor or teaching assistant for help. Outside help (classmates, friends, reference manuals) with the programming language (syntax) or computer systems is permissible, but help with the design of your program is restricted to your group members, the instructor, and the teaching assistant. Outside references such as language manuals are permitted. Any other collaboration or consultation is prohibited and will be considered a violation of the Honor Code. If you wish to use any software libraries or outside source code beyond the standard C, C++, or Java libraries, check with me first. If in doubt about anything related to Honor Code, ask now and avoid problems later!