CSE 451 - Winter 1999

Chapter 5, Silberschatz and Galvin, 5th edition

1. n! possible schedules, assuming each process is allowed to run to completion once it has started. That's because there are n choices for the first process, n-1 for the second, n-2 for the third, and so on, producing (n)(n-1)(n-2)...(1) = n! schedules.

2. In nonpreemptive scheduling, the running process only leaves the CPU by giving it up voluntarily, either by making a request via a system call, or by calling yield(). (Well, technically, yield() is a request too, but let's not get picky.)

   In preemptive scheduling, a timer goes off every so often, and the scheduler runs. The scheduler decides whether the currently running process gets to retain control of the CPU or not.

   Strict nonpreemptive scheduling is not good for use in a computer center because there is no incentive to give up the CPU other than altruism, so once a user gets onto the CPU no one else gets a turn until that user deigns to give up the CPU.

3. Here is the set of processes:

   Process   Burst Time   Priority
   -------------------------------
      1          10          3
      2           1          1
      3           2          3
      4           1          4
      5           5          2
   

   a. Here are the four Gantt charts:

   FCFS:   1111111111233455555
   SJF:    2433555551111111111
   NPP:    2555551111111111334
   RR:     1234513515151511111
   

   b. The turnaround times for each process by scheduling algorithm are:

   Process:  1   2   3   4   5
   Scheme: +-------------------
      FCFS |10  11  13  14  19
       SJF |19   1   4   2   9 
       NPP |16   1  18  19   6
        RR |19   2   7   4  14
   

   c. The waiting times for each process by scheduling algorithm are:

   Process:  1   2   3   4   5
   Time:   +-------------------
      FCFS | 0  10  11  13  14
       SJF | 9   0   2   1   4
       NPP | 6   0  16  18   1
        RR | 9   1   5   3   9
   

   d. The average waiting times by schedule are:

   Schedule | Time
   ---------+-----------------------
       FCFS | (0+10+11+13+14)/5 = 9.6
        SJF | (9+0+2+1+4)/5 = 3.2
        NPP | (6+0+16+18+1)/5 = 8.2
         RR | (9+1+5+3+9)/5 = 5.4
   

   Shortest job first yields the minimal average waiting time.

4. Here is the set of processes:

   Process   Arrival Time   Burst Time
   -----------------------------------
      1          0.0            8
      2          0.4            4
      3          1.0            1
   

   a. The average turnaround time with FCFS is: ((8 - 0.0) + (12 - 0.4) + (13 - 1.0))/3 = 10.533

   b. The average turnaround time with SJF is: ((8 - 0.0) + (9 - 1.0) + (13 - 0.4))/3 = 9.533

   c. The average turnaround time with one idle unit and then SJF is: ((2 - 1.0) + (6 - 0.4) + (14 - 0.0))/3 = 6.867

5. RR with entries in ready queue as pointers to PCBs.
   a. Two pointers to the same process make that process run twice as often as anyone else.

   b. Advantages: Hey, we've just created no-brainer prioritization! Disadvantages: There's still a context switch every time slice, even if the same process runs twice in a row. Data structure management may be a pain if a process dies (or is moved to the waiting queue).

   c. The basic RR could just read a new entry in the PCB indicating how many quanta it should run for.

6. Why might you want different quanta for different levels on the multi-level queueing system? Well, imagine a single queue. How do you set the quantum for that queue? You want it to be long enough that you can get some real work done without having to context switch all the time, but short enough that interactive processes can get quick response times. A very natural division for queues is to have one queue (with a short quantum) for interactive jobs which need quick response time but won't need the CPU for long and another queue (with a long quantum) for long-running jobs which don't need quick response time but will use their entire quantum each run. Then you have the best of both worlds.

7. Beta is the priority rate of change for the running process, alpha is the priority rate of change for waiting processes, and new processes start at priority 0.
   a. If beta > alpha > 0, then the running process keeps the processor until it finishes, at which point the process which has been waiting longest gets to run. New processes join the queue at the end. This is First-Come First-Served.

   b. If alpha < beta < 0, then the running process keeps the processor until either it finishes or a new process comes along. So the first priority goes to new processes. Among processes of the same age, the process which has run the most gets priority. This does not conform to any of the algorithms outlined in the book and frankly, it's pretty wacky. I think they're just trying to show that this alpha-beta business, though deceptively simple looking, can actually describe a wide variety of behavior.

8. What relation holds between these pairs of algorithms?
   a. Priority and SJF. SJF can be implemented using the priority algorithm if you assign each job a priority equal to its length, with low priorities being higher. (This assumes non-preemptive priority.)

   b. Multilevel feedback queues and FCFS. The whole idea behind the multilevel feedback queue is that you can do anything with it. It is very flexible and adaptible. One thing you can do with it is throw away most of its usefulness by only using one queue and defining that queue's behavior to be FCFS.

   c. Priority and FCFS. FCFS is just priority where the priority is assigned by order of arrival, with low priorities being higher.

   d. Round Robin and SJF. It doesn't seem very easy to implement either of these in terms of the other, but they do share the characteristic that in each, the smallest job finishes first.

9. Suppose a short-term CPU scheduling algorithm favors processes that have used the least CPU time in the recent past. Then take two jobs, an I/O bound job and a CPU bound job. The I/O bound job, when given a chance to run, will execute a few instructions and then immediately block on I/O, because that's what it means to be I/O bound. Then the CPU bound job will run, and it will run until it is preempted, churning away on the CPU the entire time, because that's what it means to be CPU bound. When the scheduler looks at the recent history and chooses who to run next, it will run the I/O bound job whenever possible. (Now, the I/O bound job will not always be available, since it will spend a lot of time on the waiting queue rather than on the ready queue, so the CPU bound job will get its time too.)

10. How much does each scheduling algorithm favor short processes?
    • FCFS does not care how long each job is, it just runs processes in the order in which they arrive. Long jobs have to wait their turn just like short jobs.

    • RR favors processes short enough to fit in one quantum, but just to the extent that they'll be able to finish without interruption. I don't think this counts as much discrimination. RR still just runs the next process in line, regardless of how long it is expected to run.

    • Multilevel feedback queues, especially when set up as described in the book, favor short processes a great deal. More than just taking the RR approach and giving a short process a chance to finish quickly, MLFQ's actually give short processes priority over long processes.