ASSIGNMENT ON SCHEDULING
1. Consider a multilevel feedback scheduling policy with five priority queues levels. Each
of these priority queues uses the round robin scheduling policy with a time quantum of 3
units. And the maximum execution time at each priority level in the quantum (or 6 units).
All jobs needing the CPU begin at the highest priority level and then move down priority
levels as the time using the CPU grows. The CPU is always allocated to the highest
priority job.
a. Does the scheduling policy work well for CPU bound processes? Explain
b. Is this scheduling algorithm good for I/O bound processes? Explain
c. Is starvation possible? If yes, how might you modify the policy to avoid starvation?
2. Five batch jobs, A through E, arrive at a computer center at essentially the same time.
They have an estimated running time of 15,9,3,6 and 12 minutes, respectively. Their
(externally defined) priorities are 6,3,7,9, and 4 respectively, with a lower value on
responding to a higher priority. For each of the following scheduling algorithm be
termine the turnaround time for each process and the average turnaround for all jobs.
Ignore process switching overhead. Explain how you arrived at your answers in the last
three cases assume that only one job at a time runs until it finishes and that a jobs are
completely processor bound.
a. Round robin with a time quantum of 1 minute
b. Priority scheduling
c. FCFS (run in order 15,9,3,6, and 12)
d. Shortest job first
3. Characteristics on the needs of four processes are given in the table below. These
processes are to be executed in a uniprocessor system with a single I/O device. In this
system, the overhead to dispatch a process onto the CPU is 1 time unit, the overhead to
remove a process from the CPU is zero, no overhead exists in placing/removing a process
on/from the I/O device, and is a very small positive unit. Using the round give robin
scheduling policy for the CPU, with time quantum of 5 units, give
a. Two timing charts (one for the CPU and one for the I/O device) to illustrate the
execution sequence.
b. TR = the average process turnaround time.
c. CPU-UTIL = the I/O device utilization (the percent of time the I/O device is busy).
d. I/O-UTIL = the I/O device utilization (the percent of time the I/O device is busy).
Assume each I/O request (if I/O is needed) is the last statement is the previous CPU
burst. Also assume I/O is never preempted.
Process Arrival Time CPU Burst I/O Burst Time CPU Burst
Number Time 1 Time 2
P1 0 5 5 2
P2 3-ɛ 2 22 2
P3 7-ɛ 8 0 0
P4 25 - ɛ 9 2 1
4. Assume you have the following jobs to execute with one process.
i τ (Burst Time) Arrival Time
0 75 0
1 40 10
2 25 10
3 20 80
4 45 85
Suppose a system uses RR scheduling with a quantum of 15:
a. Create a Grant chart illustrating the execution of these processes
b. What is the turnaround time for process p3?
c. What is the average wait time for the processes?
5. Assume you have the following jobs to execute with one processor:
i τ (p¡) Priority
0 80 2
1 25 2
2 15 3
3 20 4
4 45 1
The jobs are assumed to arrive at the same time. Using priority scheduling do the following:
a. Create a Gantt chart illustrating the execution of these processes
b. What is the turnaround time for process p1?
c. What is the average wait time for the processes?
6. Suppose that a scheduling algorithm (at the level of short-term CPU scheduling) favors
those processes that have used the least processes time in the recent past. Why will this
algorithm favor I/O bound programs and yet not permanently starve CPU-bound
programs?
7. Consider the following set process, 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
a. Draw four Gantt that illustrate the execution of these processes using the following
scheduling algorithms: FCFS, SJF, nonpreemptive 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 these scheduling algorithms?
d. Which of the algorithms result in the minimum average waiting time (over all
processes)?
8. Consider a preemptive priority scheduling algorithm based on dynamically changing
priorities. Larger priority numbers imply higher priority. When a process is waiting for
the CPU (in the ready queue, but not running), its priority changes at a rate α; when it is
running, its priority changes at a rate β. All processes are given a priority of 0 when they
enter the ready queue. The parameters α and β can be set to give many different
scheduling algorithms.
a. What is the algorithm that results from β > α > 0?
b. What is the algorithm that results from α < β < 0?
9. Suppose that the following processes arrive for execution at the times indicated. Each
process will run for the amount of time listed. In answering the question, use
nonpreemptive scheduling, and base all decisions on the information you have at the time
the decision must be made:
Process Arrival Time Burst Time
P1 0.0 8
p2 0.4 4
p3 1.0 1
a. What is the average turnaround time for these processes with the PCFS scheduling
algorithm?
b. What is the average turnaround time for these processes with the SJF scheduling
algorithm?
c. The SJF algorithm is supposed to improve performance, but notice that we chose to
run process p1 at time o because we did not know that two shorter processes would
arrive soon. Compute what the average turnaround time will be if the CPU is left idle
for the first 1 unit and then SJF scheduling is used. Remember that process P 1 and P2
are waiting during this idle time, so their waiting time may increase. This algorithm
could be known as future – knowledge scheduling.
