Page 100 - DCAP403_Operating System

Unit 5: Scheduling

5.11 Review Questions Notes

1. Suppose that a scheduling algorithm favors those processes that have used the least
processor time in the recent past. Why will this algorithm favor I/O-bound programs and
yet not permanently starve CPU-bound programs?

2. Assume you have the following jobs to execute with one processor, with the jobs arriving
in the order listed here:
i T(pi)
0 80
1 20
2 10
3 20
4 50

(a) Suppose a system uses FCFS scheduling. Create a Gantt chart illustrating the
execution of these processes?
(b) What is the turnaround time for process p ?
3
(c) What is the average wait time for the processes?
3. Suppose a new process in a system arrives at an average of six processes per minute and
each such process requires an average of 8 seconds of service time. Estimate the fraction of
time the CPU is busy in a system with a single processor.
4. A CPU scheduling algorithm determines an order for the execution of its scheduled
processes. Given n processes to be scheduled on one processor, how many possible different
schedules are there? Give a formula in terms of n.

5. Many CPU-scheduling algorithms are parameterized. For example, the RR algorithm
requires a parameter to indicate the time slice. Multilevel feedback queues require
parameters to define the number of queues, the scheduling algorithms for each queue, the

criteria used to move processes between queues, and so on.
These algorithms are thus really sets of algorithms (for example, the set of RR algorithms
for all time slices, and so on). One set of algorithms may include another (for example, the
FCFS algorithm is the RR algorithm with an infinite time quantum).What (if any) relation

holds between the following pairs of sets of algorithms?
(a) Priority and SJF
(b) Multilevel Feedback Queues and FCFS
(c) Priority and FCFS
(d) RR and SJF
6. Distinguish between long term and short term scheduling.
7. Consider the following set of processes, with the length of the CPU burst given in
milliseconds.
Process Burst Time Priority
P 10 3
1
P 1 1
2
P 3 2 3
P 1 4
4
P 5 2
5

LOVELY PROFESSIONAL UNIVERSITY 93