ICT201 Computer Organization and Architecture: Scheduling and Deadlock

This report analyzes CPU scheduling algorithms (FCFS, SJN, SRT, and Round Robin) and deadlock scenarios within an operating system context, based on the provided assignment details for ICT201 Computer Organization and Architecture. The solution includes timelines for each scheduling algorithm, detailing ready queue formation and calculating waiting time and turnaround time for each job. The report also addresses deadlock problems, proposing features to incorporate into an operating system for resolving deadlocks in a spooling system without data loss. The report further examines a banking system scenario to determine if it can deadlock and explores the implementation of a numbering request policy to prevent deadlock with dynamic accounts. Detailed calculations and explanations are provided for all aspects of the assignment.

Operating System
T1 2019: ICT201 Computer Organization and Architecture
Assessment 1
1

Operating System
Table of Contents
CPU Scheduling 1
Scheduling turn around and waiting time 2
Deadlock 3
Deadlock detection 4
Resource Allocation graph 5
References 6
2

Operating System
Assignment Details:
1- Given the following arrival times and CPU cycle times.
Draw a timeline for each of the following scheduling algorithms and also show the details of the
ready queue formation during the timeline. (5 marks each)
i FCFS
ii SJN
iii SRT
Iv Round Robin (use time quantum of 3)
1. FCFS (First come First Serve )
As the name suggests this scheduling algorithm works on the concept , that the process which
arrives first is served first. It can be stated that the process which requests the process first , gets
the allocated the CPU first.
It works on the concept of the First in First out (FIFO) , queue data structure the element which
enters in the queue first leaves the queue first.
Ready Queue Formation
T
i
m
e
0 1 2 3 4 5 6 7 8 9 1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
R
u
n
n
i
n
g
A
.
1
2
A
.
1
1
A
.
1
0
A
.
1
0
A
.
9
A
.
8
A
.
7
A
.
6
A
.
5
A
.
4
A
.
3
A
.
2
A
.
1
B
.
4
B
.
3
B
.
2
B
.
1
C
.
2
C
.
1
D
.
1
1
D
1
0
D
9
D
8
D
7
D
6
D
5
D
4
D
3
D
2
D
1
E
1
3
Job Arrival Time CPU cycles
required
A 0 12
B 2 5
C 4 2
D 6 11
E 9 1

Operating System
st
a
t
e
J
o
b
R
e
a
d
y
st
a
c
k
1
(
T
O
P
)
.
B
B
.
4
B
.
3
B
.
2
B
.
1
C
.
2
C
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
E
.
1
.
C
C
.
2
C
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
E
.
1
.
D
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
E
.
1
F
i
n
is
h
st
a
c
k
A B C D E
.
B
B
.
4
B
.
3
B
.
2
B
.
3
B
.
1
C
.
2
C
.
1
D
.
1
D
.
1
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
E
.
1
4

Operating System
1 0
.
C
C
.
2
C
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
E
.
1
.
D
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
E
.
1
.
E
E
.
1
2 SJN (Shortest Job Next ) scheduling algorithm
This algorithm is also known as shortest job first , in this algorithm the non-preemptive approach
is followed . Here the approach is applied to minimize the waiting time. It is implemented using
the batch system and where the required CPU time is known in advance. It is impossible to
implement the interactive system when CPU time is not given.
Job Arrival
Time
CPU cycles
required
A 0 12
B 2 5
C 4 2
D 6 11
E 9 1
T
i
m
e
0 1 2 3 4 5 6 7 8 9 1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
3
1
R
u
n
n
i
n
g
s
A
.
1
2
A
.
1
1
A
.
1
0
A
.
1
0
A
.
9
A
.
8
A
.
7
A
.
6
A
.
5
A
.
4
A
.
3
A
.
2
A
.
1
E
.
1
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
5

Operating System
t
a
t
e
J
o
b
R
e
a
d
y
s
t
a
c
k
1
(
T
O
P
)
.
E
E
.
1
C
.
2
C
.
1
B
.
1
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
.
C
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
.
D
.
3
D
.
2
D
.
1
B B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
D
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
F
i
n
i
s
h
s
A B C D E
6

Operating System
t
a
c
k
.
E
E
.
1
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
C
C
.
1
C
.
2
B
.
5
B
.
4
B
-
3
B
.
2
B
.
1
0
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
3
D
.
2
D
.
1
.
B
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
D
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
2. SRT (Shortest remaining Time next) scheduling algorithm
It is a preemptive scheduling algorithm , in this scheduling the processes that takes less time to
complete its process is selected next. In this algorithm the processes with shortest cycle time is
preemptive first.
T
i
m
e
0 1 2 3 4 5 6 7 8 9 1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
3
1
R
u
n
n
i
n
g
s
t
a
t
A
.
1
2
A
.
1
1
A
.
1
0
A
.
1
0
A
.
9
A
.
8
A
.
7
A
.
6
A
.
5
A
.
4
A
.
3
A
.
2
A
.
1
E
.
1
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
7

Operating System
e
J
o
b
R
e
a
d
y
s
t
a
c
k
1
(
T
O
P
)
.
E
E
.
1
C
.
2
C
.
1
B
.
1
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
.
C
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
.
D
.
3
D
.
2
D
.
1
B B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
D
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
F
i
n
i
s
h
s
t
a
c
A B C D E
8

Operating System
k
.
E
E
.
1
C
.
2
C
.
1
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
C
C
.
1
C
.
2
B
.
5
B
.
4
B
-
3
B
.
2
B
.
1
0
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
3
D
.
2
D
.
1
.
B
B
.
5
B
.
4
B
.
3
B
.
2
B
.
1
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
.
D
D
.
1
1
D
.
1
0
D
.
9
D
.
8
D
.
7
D
.
6
D
.
5
D
.
4
D
.
3
D
.
2
D
.
1
3. Round Robin Scheduling
Round Robin scheduling is a preemptive process scheduling algorithm , here each process is
given affixed time period to execute and this is called quantum. Once the time period is over the
next process is preempted in the queue .
QUANTUM-2
Ti
m
e
0 1 2 3 4 5 6 7 8 9 1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
3
1
R
un
ni
ng
st
at
e
Jo
b
A
.
B
.
C
.
D E
.
R
ea
dy
st
ac
k
1(
A B D
9

Operating System
T
O
P)
A B D
A D
Fi
ni
sh
st
ac
k
A D
.E
.C
.B
.D
2- Using either internet resources or books, understand the concept of waiting time and
turnaround time. Define those terms (waiting time and turnaround time) in your own
words. Then calculate waiting time and turnaround time for every job for all four
scheduling algorithms mentioned in Q1 (Details of the calculations is essential).
Now according to this concept the work will be done as follows-
FCFS
0 12 17 19 30 31
PNO AT BT CT Turn around
time (CT-
AT)
Waiting
Time(TAT-
BT)
A 0 12 12 12 0
B 2 5 17 15 10
C 4 2 19 15 13
D 6 11 30 24 13
E 9 1 31 22 20
10
A B C D E

Operating System
Average waiting time = 0+10+13+13+20 / 5
= 11.2
Average Turn around Time = 12+15+ 15+24+22/ 5
= 20.6
2.SJN
According to this algorithm-
0 12 13 15 20 31
PNO AT BT CT Turn around
time (CT-
AT)
Waiting
Time(TAT-
BT)
A 0 12 12 12 0
E 9 1 13 4 3
C 4 2 15 11 9
B 2 5 20 18 13
D 6 11 31 25 14
Average Turn around time = 12+|4+11+18+25 / 5
= 16
Average waiting Time = 0+3+9+13+14/5
= 7.8
4. SRT (Shortest remaining time )
11
A E C B D

Operating System
Job Arrival
Time
CPU cycles
required
A 0 12
B 2 5
C 4 2
D 6 11
E 9 1
5.
6.
7.
0 12 13 15 20 31
PNO AT BT CT Turn around
time (CT-
AT)
Waiting
Time(TAT-
BT)
A 0 12 12 12 0
E 9 1 13 4 3
C 4 2 15 11 9
B 2 5 30 28 23
D 6 11 31 25 14
Average Turn around time = 12+|4+11+18+25 / 5
= 16
Average waiting Time = 0+3+9+13+14/5
= 7.8
5. Round Robin
Job Arrival
Time
CPU cycles
required
A 0 12
B 2 5
C 4 2
D 6 11
E 9 1
12
A E C B D