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.
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)
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.
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.
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.
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.
For Offline Study you can Download from below link
Download Operating Systems Processor Scheduling algorithms PDF File
