Processor Scheduling algorithms

PropellerAds

Now, let’s discuss some processor scheduling algorithms again stating that the goal is to select the most appropriate process in the ready queue. For the sake of simplicity, we will assume that we have a single I/O server and a single device queue, and we will assume our device queue always implemented with FIFO method. We will also neglect the switching time between processors (context switching).

1 First-Come-First-Served (FCFS)
In this algorithm, the process to be selected is the process which requests the processor first. This is the process whose PCB is at the head of the ready queue. Contrary to its simplicity, its performance may often be poor compared to other algorithms. FCFS may cause processes with short processor bursts to wait for a long time. If one
process with a long processor burst gets the processor, all the others will wait for it to release it and the ready queue will be filled very much. This is called the convoy effect.

Example 1
Consider the following information and draw the timing (Gannt) chart for the processor and
the I/O server using FCFS algorithm for processor scheduling.

example-1

2 Shortest-Process-First (SPF)

In this method, the processor is assigned to the process with the smallest execution (processor burst) time. This requires the knowledge of execution time. In our examples, it is given as a table but actually these burst times are not known by the OS. So it makes  prediction. One approach for this prediction is using the previous processor burst times for  the processes in the ready queue and then the algorithm selects the shortest predicted next processor burst time.

Example 2 :
Consider the same process table in Example 2.1 and draw the timing charts of the processor
and I/O assuming SPF is used for processor scheduling. (Assume FCFS for I/0)

shortest-process-first

3 Shortest-Remaining-Time-First (SRTF)

The scheduling algorithms we discussed so far are all non-preemptive algorithms. That is,
once a process grabs the processor, it keeps the processor until it terminates or it requests  I/O.
To deal with this problem (if so), preemptive algorithms are developed.

In this type of algorithms, at some time instant, the process being executed may be preempted to execute
a new selected process. The preemption conditions are up to the algorithm design. SPF algorithm can be modified to be preemptive. Assume while one process is executing on the processor, another process arrives.

The new process may have a predicted next processor burst time shorter than what is left of the currently executing process. If the SPF algorithm is preemptive, the currently executing process will be preempted from the processor and the new process will start executing. The modified SPF algorithm is named as Shortest-Remaining-Time-First (SRTF) algorithm.

Example 3
Consider the same process table in Example 2.1 and draw the timing charts of the processor
and I/O assuming SRTF is used for processor scheduling.
example-2-3

4 Round-Robin Scheduling (RRS)
In RRS algorithm the ready queue is treated as a FIFO circular queue. The RRS traces the ready queue allocating the processor to each process for a time interval which is smaller than or equal to a predefined time called time quantum (slice).
The OS using RRS, takes the first process from the ready queue, sets a timer to interrupt after one time quantum and gives the processor to that process. If the process has a processor burst time smaller than the time quantum, then it releases the processor

voluntarily, either by terminating or by issuing an I/O request. The OS then proceed with the next process in the ready queue.
On the other hand, if the process has a processor burst time greater than the time quantum, then the timer will go off after one time quantum expires, and it interrupts (preempts) the  current process and puts its PCB to the end of the ready queue. The performance of RRS depends heavily on the selected time quantum.

round-robin-scheduling

For an optimum time quantum, it can be selected to be greater than 80 % of processor bursts and to be greater than the context switching time.

Example 4
Consider the following information and draw the timing chart for the processor and the I/O
server using RRS algorithm with time quantum of 3 for processor scheduling.
example-2-4

example-2-44

5 Priority Scheduling
In this type of algorithms a priority is associated with each process and the processor is
given to the process with the highest priority. Equal priority processes are scheduled with
FCFS method.
To illustrate, SPF is a special case of priority scheduling algorithm where
Priority(i) = 1 / next processor burst time of process i Priorities can be fixed externally or they may be calculated by the OS from time to time.
Externally, if all users have to code time limits and maximum memory for their programs,
priorities are known before execution. Internally, a next processor burst time prediction such
as that of SPF can be used to determine priorities dynamically.
A priority scheduling algorithm can leave some low-priority processes in the ready queue
indefinitely. If the system is heavily loaded, it is a great probability that there is a higherpriority
process to grab the processor. This is called the starvation problem. One solution for
the starvation problem might be to gradually increase the priority of processes that stay in
the system for a long time.

example-2-5

For Offline Study you can Download from below link

8085-microprocessor pdf fileprocessor-scheduling-algorithms-pdf

Try Now – Operating Systems MCQs
Practice Now – Operating System Online Test