CSC 325 Operating Systems with an Emphasis on UNIX
Teamwork 3

1. 1. A CPU Scheduling algorithm determines an order for the execution of it's scheduled processes. Given n processes, determine how many different possible schedules there are. Give a formula for this in terms of n.
   
2. Explain what advantage there is to having different time quantum sizes on different queues in a multi-level queuing system and on a multi-level feedback queuing system.
   
3. Consider the following preemptive priority scheduling algorithm based on dynamically changing priorities. (Larger priority number here means higher priority.) When a process is waiting for the CPU (in the ready queue, but not running), it's priority changes at a rate of A; when it's running its priority changes at a rate of B. All processes are given a priority of 0 when they enter the ready queue. The parameters A and B can be set to give many different scheduling algorithms.
   1. What is the algorithm that results when B > A > 0?
   2. What is the algorithm that results when A > B > 0?
   3. How does this compare to the traditional UNIX scheduler?
      
4. Suppose that a scheduling algorithm on a short-term scheduler favors those processes that have used the least processor time in the recent past. Explain why this algorithm will generally favor I/O bound processes, but not permanently starve CPU-bound processes. How does this relate to the traditional UNIX scheduler?
   
5. Consider the following set of processes with the length of the CPU-burst given in milliseconds:

   Process	Burst time	Priority
   P1	10	3
   P2	1	1
   P3	2	3
   P4	1	4
   P5	5	2

   Assume that the processes arrive in the order P1, P2, P3, P4, P5 all at time 0.
1. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreemptive priorty (where a smaller priority number implies a higher priority), and RR (with quantum =1) scheduling. Note that you need not try to draw the boxes, but be sure to make it clear which process is given the CPU and at what time each process is given the CPU. For example, the Gantt chart at the top of p162 can be expressed as:
   0: P2, 1: P5, 6: P1, 16: P3, 18: P4, 19: done.
2. Compute the turn-around time for each process for each of the scheduling algorthms in part a.
3. Compute thewaiting time for each process for each of the scheduling algortithms in part a.
4. Determine which of the schedules in part a will result in the minimal average waiting time overall (for all processes.)