CS4520/CS7520 Operating Systems I FS2023 – Exam 1 (100 pts)
Page 1 of 8
Section 1: Process Scheduling (24 points; 8 each part)
1. Given the following table, how will these processes be scheduled using each of the belo
...
CS4520/CS7520 Operating Systems I FS2023 – Exam 1 (100 pts)
Page 1 of 8
Section 1: Process Scheduling (24 points; 8 each part)
1. Given the following table, how will these processes be scheduled using each of the below
algorithms? Create a Gantt chart showing when each process will be scheduled and calculate the
average waiting time and average turnaround time for the processes. For simplicity, ignore any
potential context switch time.
Process ArrivalTime ProcessingBurst Time
P1 0 9
P2 0 8
P3 3 6
P4 4 4
P5 5 2
a. Shortest-Job-First (SJF – non-preemptive)
0->P2->8->P5->10->P4->14->P3->20->P1->29
Avg. Wait = (20+0+11+6+3)/5 = 40/5 = 8.0
Avg. Turnaround = (29+8+17+10+5)/5 = 69/5 = 13 4/5 = 13.8
b. Shortest-Remaining-Time-First (SRTF - preemptive)
0->P2->5->P5->7->P2->10->P4->14->P3->20->P1->29
Avg. Wait = (20 + 2 + 11 + 6 + 0)/5 = 39/5 = 7 4/5 = 7.8
Avg. Turnaround = (29+10+17+10+2)/5 = 68/5 = 13 3/5 = 13.6
c. Round Robin (RR) (with time quantum = 5)
0->P1->5->P2->10->P3->15->P4->19->P5->21->P1->25->P2->28->P3->29
Avg. Wait = ([0+16]+[5+15]+[7+13]+[11]+[14])/5 = 81/5 = 16.2
Avg. Turnaround = (25+28+26+15+16)/5 = 110/5 = 22
CS4520/CS7520 Operating Systems I FS2023 – Exam 1 (100 pts)
Page 2 of 8
Section 2: Deadlocks (20 points; 4 each part)
2. (10 points) Consider the following snapshot of a system in which resource types A, B, and C have the
total instances of 9, 6, and 7 respectively. Unless otherwise stated, assume your OS implements
deadlock avoidance.
Allocation Max Need Available State 0
A B C A B C A B C A B C
P0 3 3 1 7 5 3 4 2 2 0 0 2
P1 0 1 2 4 1 3 4 0 1
P2 3 0 2 4 0 4 1 0 2
P3 2 2 0 4 3 2 2 1 2
P4 1 0 0 1 0 1 0 0 1
a. Fill in the blank Need matrix and Available vector.
b. Is the system in a safe state? If your answer is “yes”, show a safe execution sequence.
Yes.
c. Starting from State 0, if a new request from process P4 arrives for (0, 0, 2) can the request be
granted? If your answer is “yes”, show that the system will be in a safe state after the new request is
granted (find a safe execution sequence after the request is granted). If your answer is “no”, explain
why the request cannot be granted.
No. 002 > Need(P4)
d. Starting from State 0, If a new request from process P2 arrives for (1, 0, 0) can the request be
granted? If your answer is “yes”, show that the system will be in a safe state after the new request is
granted (find a safe execution sequence after the request is granted). If your answer is “no”, explain
why the request cannot be granted.
No. 100 > Available(002)
e. Starting from State 0, assume requests from P0 for (0, 0, 1), P1 for (1, 0, 1), P2 for (1, 0, 2), P3 for (1,
0, 0), and P4 for (0, 0, 1). This time, assume your OS does not implement deadlock avoidance,
but deadlock detection instead. Is the system in a deadlock state? If it is in a deadlock state, which
processes are involved in the deadlock?
No, the system is not deadlocked. Many safe schedules exist.
