Professor I. Rudowsky                                                                                                                     CIS 25 EW6

Chapter 5 Exercises                                                                                                                  Due Mar 9, 2005

 

5.3 Consider the exponential average formula used to predict the length of the next CPU burst. What are the implications of assigning the following values to the parameters used by the algorithm?

a. α = 0 and τ0 = 100 milliseconds

b. α = 0.99 and τ0 = 10 milliseconds

5.4 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

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0.

a. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1).

b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

c. What is the waiting time of each process for each of the scheduling algorithms in part a?

d. Which of the algorithms in part a results in the minimum average waiting time   (over all processes)?

5.5 Which of the following scheduling algorithms could result in starvation?

a. First-come, first-served     b. Shortest job first

c. Round robin                       d. Priority

5.6 Consider a variant of the RR scheduling algorithm in which the entries in the ready queue are pointers to the PCBs.

a. What would be the effect of putting two pointers to the same process in the ready queue?

b. What would be two major advantages and two disadvantages of this scheme?

c. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

5.7 Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. What is the CPU utilization for a round-robin scheduler when:

a. The time quantum is 1 millisecond

b. The time quantum is 10 milliseconds

 

Additional question: Do the same as in 5.4 a,b,c, and d, but now include in your calculations the fact that the processes do not all arrive at time 0 but at the times indicated below in the Arrival Time column.

Process            Arrival Time   Burst Time                  Priority

   P1                              0                     10                        3

   P2                              3                       1                        1

   P3                              7                       2                        3

   P4                             12                      1                        4

   P5                             18                      5                        2