Ain Shams University
Faculty of Engineering
Computer and Systems Engineering Department
CSE335: Operating Systems
S H E E T 5
1. Consider the following set of processes:
Process Arrival time Burst Time
A 1 5
B 2 1
C 5 2
D 6 3
a) Draw a Gantt chart showing how First-Come First-Served (FCFS) would schedule
the processes. What is the average waiting time and turnaround time (TAT) in this
case?
b) Draw a Gantt chart showing non-preemptive Shortest Job First (SJF) would
schedule the processes. What is the average waiting time and turnaround time (TAT) in
this case?
c) Draw a Gantt chart showing how Preemptive Shortest Job First (SJF) / shortest-
remaining-time-first would schedule the processes. What is the average waiting time
and turnaround time (TAT) in this case?
2. Consider the following set of processes, with the arrival time and estimated CPU
burst given in milliseconds.
Process Arrival Time Burst Time
P1 0 6
P2 1 8
P3 2 7
P4 3 3
1- Draw two Gantt charts that illustrate the execution of these processes using
the following scheduling algorithms:
a. First-Come First-Served
b. Non-preemptive Shortest Job First
2- Calculate the average waiting time for each case.
3- Consider the following set of processes, with the arrival time and estimated
CPU burst given in milliseconds.
Process Arrival Time Burst Time
P1 0 6
P2 2 4
P3 3 5
P4 6 2
1- Draw two Gantt charts that illustrate the execution of these processes using
the following scheduling algorithms:
a. First-Come First-Served
b. Preemptive Shortest Job First
2- Calculate the average waiting time for each case.
4- Consider the following set of processes:
Process Arrival time Burst Time Priority
A 1 6 3
B 3 2 4
C 4 2 1 (highest)
D 6 4 2
a) Draw a Gantt chart showing how non-preemptive priority would
schedule the processes. What is the average waiting time in this case?
b) Draw a Gantt chart showing preemptive priority would schedule
the processes. What is the average waiting time in this case?
c) Draw a Gantt chart showing how Round Robin (RR) with time
quantum =3 would schedule the processes. What is the average
waiting time in this case?
5- Consider the following set of processes, with the arrival time and
estimated CPU burst given in milliseconds. For the given priority values, a
smaller value means a higher priority.
Process Arrival Time Burst Time Priority
P1 0 6 2
P2 0 4 2
P3 3 5 1
P4 4 2 3
Draw two Gantt charts that illustrate the execution of these processes using the following
scheduling algorithms:
a) Preemptive priority scheduling. What is the average waiting time
and turnaround time in this case?
b) Assuming a quantum of 2-time units, draw a Gantt chart showing how
RR would schedule the processes. What is the average waiting time and
turnaround time in this case?
6- Consider the following preemptive priority-scheduling algorithm based on
dynamically changing priorities. Larger priority numbers imply higher priority.
When a process is waiting for CPU (in the ready queue, but not running), its
priority changes at a rate of a (i.e., P(t) = P0 +a * (t - t0) where t0 is the time at
which the process joins the ready queue) . Similarly, when it is running, its
priority changes at a rate b. All processes are given a priority 0 when they enter
the ready queue. The parameters a and b can be set to obtain many different
scheduling algorithms.
a) What is the algorithm that results from b > a > 0?
b) What is the algorithm that results from a < b < 0?
