written 5.6 years ago by | • modified 5.6 years ago |
Preemptive scheduling :-
Preemptive scheduling ensures that every task will get CPU time for execution . The allotment of CPU time depends on the preemptive scheduling algorithm.
It allows a process to be interrupted in the middle of its execution, taking the CPU away and allocating it to another process. The scheduling algorithm has high overhead. System is costly and complex in design.
Shortest Job first:-
- Shortest Job first is the example of this preemptive scheduling. If a new process arrives with a CPU burst length less than the remaining time of the current executing process, pre-empt. This scheme is known as the Shortest-RemainingTime-First (SRTF).
Priority scheduling in pre-emptive :-
A preemptive approach will pre-empt the CPU if the priority of the newly-arrived process is higher than the priority of the currently running process. (diagram)
Round-robin scheduling:-
In the round robin algorithm, each process gets a small unit of CPU time (a time quantum), usually 10-100 milliseconds.
After this time has elapsed, the process is pre empted and added to the end of the ready queue. If there are ‘ n’ processes in the ready queue and the time quantum is ‘q’, then each process gets ‘1/n’ of the CPU time in chunks of at most ‘q’ time units at once.
No process waits more than ‘ (n-1)q’ time units.
Performance of the round robin algorithm
$\hspace{1.5cm}$ - q large then FCFS
$\hspace{1.5cm}$ - q small then q must be greater than the context switch time; otherwise, the overhead is too high
- One rule of thumb is that 80% of the CPU bursts should be shorter than the time quantum
$\hspace{4.5cm}$OR
In the round robin algorithm, the kernel allocates a certain amount of time for each task waiting in the queue .
The time slice allocated to each task is called quantum. As shown in fig. if three tasks 1,2, 3 are waiting in the queue the CPU first executes task1 then task2 then task 3 and the again task1 in round robin algorithm each task waiting in the queue is given a fixed time slice .
The kernel gives control to the next task if the current task has completed its work within the time slice or if the current task has completed it allocated time The kernel gives control to the next task if
$\hspace{1.5cm}$a) the current task has completed within the time slice
$\hspace{1.5cm}$b) the current task has no work to do
$\hspace{1.5cm}$c ) the current task has completed its allocated time slice
- This algorithm is very simple to implement but there is no priorities for any task. All tasks are considered of equal importance . If time critical operation are not involved then this algorithm will be sufficient . Digital millimeter , microwave oven has this algorithm.