CPU Scheduling Algorithms and Deadlock Situations in Computer Organization and Architecture

COMPUTER ORGANIZATION AND ARCHITECTURE 1
Computer Organization and Architecture
Student Name
Course
Institution
Date

COMPUTER ORGANIZATION AND ARCHITECTURE 2
Introduction
This assignment is focused on CPU scheduling algorithms and deadlock situations.
CPU scheduling refers to events where only one job/process is allowed to utilize the CPU
while others are put on hold or in the queue because the resources are being utilized by the
current process be executed. The objective of CPU scheduling includes maximum
throughput, minimum wait time, minimum response time, maximum CPU utilization,
minimum turnaround time, and fair allocation of CPU runtime (Brucker and Knust, 2012).
The operating system is responsible for fetching the process that is in ready queue to be
processed when the CPU becomes available. CPU scheduler is responsible for carrying out
the selection process. A deadlock can be described as scenario where resources that is needed
by another process is being held by another process, that is, if process P1 has resource R1 and
requires resource R2 to finish and process P2 is holding resource R2 and requires resource R1
to complete which is being held by P1, the processes will just remain in a cycle and cannot
complete (Gupta, 2013). Such a situation is referred to as a deadlock. Questions 1 and 2 of
this paper will be describing the various concepts of scheduling algorithms while questions 3,
4, and 5 will be discussing various deadlock situations.
Question 1:
Given the following arrival times and CPU cycle times
Table 1: 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.
i) FCFS
FCFS is a first come first served scheduling algorithm whereby a process that is received
first is processed first (Stroebele-Benschop, Dieze and Hilzendegen, 2016). FCFS is similar

COMPUTER ORGANIZATION AND ARCHITECTURE 3
to first in first out (FIFO) queuing in data structure which describes that the data element
which gets into the queue first leaves the first. FCFS is mostly used in batched systems and is
easy to implement and understand programmatically. A good scenario of FCFS is when one
is paying for the items at a supermarket. From the above table, we are going to draw a
timeline for first come first served algorithm.
Job A B C D E
Arrival time 0 2 4 6 9
Finish Time 12 17 19 30 31
Table 2: Arrival and Finish Time for FCFS
0 12 17 19 30 31
Table 3: Timeline for FCFS from 0 to 31
However, FCFS is faced with some problem. The priority of the processes does not matter in
FCFS because it is a non-pre-emptive scheduling algorithm. A low priority processes which
takes a longer CPU time are processed first yet there are several high priority processes on
the queue. As such, the high priority processes will have to wait to avoid crashing the system.
Also, it has a poor resource utilization because of the convoy effect resulting from the
impossibility of parallel utilization of resources.
ii) SJN
Shortest job Next (SJN), popularly known as shortest job first (SJF) is a scheduling
algorithm aimed at reducing the waiting time. It is best used in environments where the CPU
time in known in advance and is easy to implement on batch systems (Pushpa and
Devasikamani, 2014). Nevertheless, it is not applicable in systems where CPU time in
unknown such as interactive systems. To calculate and draw the time line from the processes
in table 1, we first calculate the arrival and finish times.
Job A B C D E
Arrival Time 0 2 4 6 9
Finish time 12 20 15 31 13
Table 4: Arrival and Finish Time for SJN
A B C D E

COMPUTER ORGANIZATION AND ARCHITECTURE 4
0 12 13 15 20 31
Table 5: Timeline for SJN from 0 to 31
iii) SRT
SRT (Shortest remaining time) scheduling algorithm is useful in time sharing system
because it is a pre-emptive algorithm. In this algorithm, jobs with the least run time estimate
to be completed is executed next. Contrary to SJN, a user may pre-empt a running process
with a smaller run time estimate (Almakdi, Aleisa and Alshehri, 2015). In table 1, when a
process with less CPU cycle gets in, the current process being executed is suspended. From
table 1, process A requires 12 milliseconds to be processed, but when process B gets in it
requires it is compared. Since process B requires 5 milliseconds, A will be preempted and B
takes over. But as process B continues, process C gets in and since it has a smaller estimate
run time of 2 milliseconds, process B is preempted and C is processed first this cycle
continues until all the jobs have been processed.
The table below shows the arrival time and the finish time.
Job A B C D E
Arrival Time 0 2 4 6 9
Finish time 20 7 9 31 10
Table 6: Arrival and Finish Time for SRT
0 2 7 9 10 20 31
Table 7: Timeline for SRT from 0 to 31
iv) Round Robin (use time quantum of 3)
In Round Robin scheduling algorithm, every job is assigned a fixed time called quantum.
The job is processed for the allotted time then preempted for another process to be executed
for a specified time (Srivastava and Kumar, 2019). In order to save the current states of the
processes that have been preempted, context switching is employed. For this case, a quantum
of 3 has been allotted for the processes. Natural wait time and context switching will be
ignored.
A E C B D
A B C E A D