CS 3733 Operating Systems, Fall 2008 Assignment 3 Comments

• This assignment was graded on the basis of 20 points.
  • Part 1: 12 points
  • Part 2: 5 points
  • Part 3: 3 points
• Almost everyone did Part 1 correctly.
  A few people used the wrong I/O burst time for one of the processes.
  You should not check that it is correct if you did not compare the simulator output with the known values.
• In Part 2, I was looking for you to think about why PSJF usually has a smaller AWT than SJF.
• Some people ran many (a million) tests to convince themselves that SJF cannot have a smaller waiting time than PSJF in the situation.
• You can prove that it cannot happen based on the following facts:
  • If PSJF causes a preemption, then it locally reduces the AWT.
    This means that if you only consider what happens after the two CPU bursts in question, then the preemption will reduce the AWT.
  • If a preemption occurs, the preempting process will leave the system after its CPU burst is complete.
    This is true because only its second CPU burst can cause preemption and then it is done.
  • After the preemption there is only one process left, so the ready queue will remain empty after the preempted process gets into the CPU.
• For 3 processes, each with two CPU bursts and one I/O burst with all processes arriving at the same time, the first 2 statements above are still true, but the last one is not.
• It is possible for SJF to have a smaller AWT than PSJF in this case.
  Here is an example:
  

      P1: CPU 1, I/O  6, CPU 5
      P2: CPU 5, I/O 17, CPU 3
      P3: CPU 7, I/O  5, CPU 3
  
      SJF:
      P1: RWWWWWWrrrrrrRRRRR
      P2: rRRRRRWWWWWWWWWWWWWWWWWRRR
      P3: rrrrrrRRRRRRRWWWWWRRR
      Total waiting time is 13
  
      PSJF:
      P1: RWWWWWWRRRRR
      P2: rRRRRRWWWWWWWWWWWWWWWWWRRR
      P3: rrrrrrRrrrrrRRRRRRWWWWWrrrRRR
      Total waiting time is 15
  

• This problem did not mention context switch time. Some people came up with solutions in which the context switch time was large. In this case, a preempt by PSJF might require processes to stay in the ready queue for a long time.