Assignment III; due to April 20-21, 2009:

1. Design a cpu scheduler of your own choice. The idea is to schedule the CPU for several simulated processes that alternately compute and request I/O.
   • You are to read a file describing n processes and then simulate the n processes until they all terminate. The way to do this is to keep track of the state of each process and advance time making any state transitions needed. The data file has the following format:
     
     

     Process Arrival Time	CPU burst	I/O Operation	...	CPU burst	Line End
     0	100	2	...	200	-1
     5	6	4	...	25	-1
     &vellip#vdots;	&vellip#vdots;	&vellip#vdots;	...	&vellip#vdots;	-1

   • Assume that there is only one CPU and one I/O device in the system. The I/O device serves only one process at a time.
   • Recall that in a real operating system, the scheduler only executes whenever an interrupt or trap occurs. Similarly, your simulation should be event based.
   • Each event should be emitted along with relevant process states. For example:

      ...
     Time : 13
     - process 4 io started (blocked until 15, remaining = 3, burst = 2)
     - process 5 running    (remaining = 12, burst = 10)
     
     Time : 15
      - process 4 i/o completed (now ready, remaining=3, burst=2)
      - process 5 preempted (remaining = 10, burst = 12)
      - process 4 running   (remaining = 3, burst = 2)
     ...
     

     (preemption depends on the chosen scheduling algorithm.)
   • Ignore the context switching overhead and i/o latency.
   • At the end of the run you should first print an identification of the run including the scheduling algorithm used, any parameters (e.g. the quantum for RR), and the number of processes simulated. You should then analyze the behavior of your scheduler and report the followings;
     • Finishing time (i.e., when all the processes have finished).
     • CPU Utilization (i.e., percentage of time some job is running).
     • I/O Utilization (i.e., percentage of time some job is blocked).
     • Throughput, expressed in processes completed per hundred time units.
     • Average turnaround time.
     • Average waiting time.
   An example process data file

   0 5 -1
   1 3 2 3 2 3 -1
   6 10 2 60 2 30 3 70 2 10 2 10 -1
   23 3 2 3 2 3 -1
   24 70 2 70 2 40 3 70 2 20 2 10 -1
   25 3 2 3 2 3 -1
   26 80 2 80 2 50 3 70 2 40 2 10 -1
   27 3 2 3 2 3 -1
   28 25 2 10 -1
   29 3 2 3 2 3 -1
   31 3 2 3 2 3 -1
   33 3 2 3 2 3 -1
   35 3 2 3 2 3 -1
   40 3 2 3 2 3 -1
   40 3 2 3 2 3 -1
   42 3 2 3 2 3 -1
   43 3 2 3 2 3 -1
   45 3 2 3 2 3 -1