This scheduling is a strategy which allows the processes which are logically executable to be suspended temporarily so that some other process can be executed. This type of scheduling is usually adopted in most of the Multi Programming Environments, so that when some program, which takes long time for execution, can be suspended temporarily so that another process can be run and the control again comes to suspended process and is resumed from where it was suspended.
Most of the Pre-emptive Scheduling Algorithmsare complex as the job itself is very complex. But there are some algorithms for this type of scheduling which are quite simple. The following are some of the Preemptive Scheduling Algorithms available and used widely:
a) Round-Robin Scheduling Algorithm
b) Response Ratio Scheduling Algorithm
c) Priority Scheduling Algorithm
d) Multiple Queues Algorithm
Round Robin Scheduling Algorithm
This algorithm of scheduling is one of the oldest, fairest, simple and most widely used algorithms for scheduling purposes. The basic philosophy of this algorithm is that all the programs get equal opportunity to be processed. This is ensured by implementing that not program gets a second opportunity for execution, until and unless all the other programs have had at least one chance for execution.
This is done by dividing the CPUs processing time into small slices known as “Quantum”. This quantum of the time is assigned to each and every process which is executable. Once quantum of time is assigned to each and every process, which is executable. Once the process starts executing, it is checked that it is in its quantum of time, if within the quantum it is not completed then, it is suspended temporarily and the next process gets CPU four quantum of time, and it is not completed within that time, it is also suspended temporarily, so that other program in line gets its quantum and this process continues till all the process get their quantum then the CPU is given to the first program was suspended.
It is resumed from it was suspended and it gets it quantum of time, then the next process is executed and his cycles continues. This ensures that every process gets a fair chance for execution. The scheduler has to maintain a list of the executable processes.
The basic issue here is length of the quantum, as it plays a major role. Let us consider four processes P1, P2, P3 and P4 which have their execution time as follows:
Process` | Execution |
P1 | 12 |
P2 | 8 |
P3 | 16 |
P4 | 20 |
Let us take the quantum as 4 digits. Let us assume that the process P1 gets the first chance to be executed, therefore it gets quantum of 4 digits. Therefore, after the 1st quantum it still requires 8 units i.e., 2 quantum’s for completion, then P2 gets ext quantum is still requires 1 more quantum to be executed completely and then P3 gets the quantum and then P4 and after 4 quantum’s the control comes back to P1 and it gets 1 quantum, then P2 gets quantum and this cycle continues till the processes are completed. The following would be the sequence using Round Robin Scheduling Algorithm:
P1 -> P2 -> P3 -> P4 -> P1 -> P2 -> P3 -> P4 -> P1 -> P3 -> P4 -> P4
This Process of Switching from one process to other requires certain amount to time for various operations like saving and loading registers and memory maps, updating lists and tables maintained. Let is assume that this process tubes about 4 m secs. If the quantum is set at 20 m secs, i.e., after doing useful work for 20 m secs the CPU has to spend 4 m secs on switching which is 20% of time being wasted on overhead, lets now assume that the quantum is increased and with this big quantum.
If 10 interactive users initiate a process at almost some instance of time, then the 2nd one has to wait for about ½ a second and next for about a second and soon and the last one has to wait for about 5 secs, which is quite high waiting time.
Therefore, of quantum is set short, CPU time is wasted a lot in switches and if the quantum is set too long the waiting time is very high. For this reason a quantum of reasonable size say 100 m sees is good compromise. But the problem is that processes which require quite less time should have to wait long completion, i.e., the processes which have short execution times are un-necessarily penalized.
Therefore another strategy is used to along with this Round Robin Scheduling Algorithm, which is known as Shortest-Time-To-Go (STG) is used, which makes is sure that in scheduling those jobs whose time requirements are shortest than waiting jobs, they are given the CPU time for the quantum and this process is repeated at every scheduling moment, if favors jobs near to completion. Thus the processes are scheduling.
Response Ratio Scheduling Algorithm
To overcome the drawbacks of STG scheduling, the Response Ratio Scheduling Algorithm is advocated. This algorithm is based upon the response ratio which can be calculated as follows:
Response Ratio = Total Time Elapsed/Total Execution Time Required
Based upon the above ratio which is calculated at every scheduling moment. The process with the highest response ratio is scheduled for execution at any scheduling moment. It is worthy to note that the processes which are very short have High response ratio, therefore it is executed first. A longer job has to pass through many cycles to get his response ratio. This will make possible for shorter jobs which arrive to get scheduled, as they have higher response ratio than the one ratio than the ongoing processes.
Thus the processes are scheduled using this scheduling algorithm so that any short job does not have to wait long and even the long jobs get their priorities once their response ratio increases.
Priority scheduling algorithm
The Round Robin Scheduling as well as the Response Ratio Scheduling Algorithms assume that all the processes are equally important, which is not so in the real world. For example, in an organization the CEO has highest priority, then board, then people down the hierarchy. These types of external priority also have to be taken into account, while executing, by scheduling algorithm.
The algorithm which deals with assignment of priorities while scheduling is Priority Scheduling Algorithm. The main idea of this algorithm is that the executable process which has the highest priority is allowed to run first. This will result in a problem where other processes to high priority processes will run indefinitely giving no chance for run.
Therefore, the scheduler decreases the priority of the current process, at every scheduling moment i.e., clock interval. Which may result in the priority of the ongoing process to fall below priority of some other process, which will result in the switching of the process, so that the process which has the highest priority at any given point of time, gets chance for execution.
The priorities for the processes can be assigned either statically or dynamically, so that the system can achieve certain goals. A better way is to group the processes into priority classes and use this priority scheduling among the classes and within each class use Round Robin Scheduling Algorithm. For Example let us consider five priority classes namely P1, P2, P3, P4 & P5, and each class with some processes. P5 has the highest priority and it decreases towards P1 which has lowest priority. The algorithm is as follows:
As long as the processes are executable in priority has P5, P5 runs each of its processes for quantum, using round robin algorithmand will never bother about other classes with low priority, which will never get chance to get executed, therefore the priorities of the classes have to be adjusted from time to time so that all classes get fair chance of execution.
Education of Multiple Queues Algorithms
The problem of priority schedulingis that each switching resulted in swapping the ongoing process to the disk from primary memory. As it is assumed that the primary memory is insufficient to hold process. Therefore, this algorithm aims at reducing swapping times, which it does by creating priority classes as in priority scheduling.
The class with highest priority class gets two quanta and next class gets four class gets three quanta and next class gets two quanta and next class gets four quanta and this goes on increasing with decreasing priorities, which reduces the swap as more number of quanta are given at a time for processing and the process which uses all quanta allocated, would move down one class. This would save CPU time for short and interactive processes.
If the processes need to run for long time before the interaction has started, will suffer. Therefore, another policy is adopted where, where never a key is pressed from a terminal the process which initiated from that terminal is shifted to the highest priority class, as it assumes interaction. This was also subjected to disadvantages of misuse.
0 Comments