- Queueing Theory is the mathematical study of waiting for lines or queues.
- Scheduling is the method by which work is assigned to resources that complete the work
- work - also tasks, jobs, or processes
Task Types
|
Preemptive Task |
In a preemptive scheduling policy, a low-priority process has to be suspended execution if high priority process is waiting in the same queue for its execution |
|---|---|
|
Non-Preemptive Task Cooperative Task |
In a non-preemptive scheduling policy, processes are executed on a first-come-first-serve basis, which means the next process is executed only when the currently running process finishes its execution |
Processor Scheduler Types
|
Preemptive Multi-Tasking |
a style of computer multi-tasking in which the operating system initiates a context switch (preemption) from a running process to another process |
|---|---|
|
Non-Preemptive Multi-Tasking Cooperative Multi-Tasking |
a style of computer multi-tasking in which the operating system NEVER initiates a context switch from a running process to another process. Instead, processes voluntarily yield control periodically or when idle or logically blocked in order to enable multiple applications to be run concurrently |
|
Cyclic Executive |
a form of cooperative multi-tasking, in which there is only one task. The sole task is typically realized as an infinite loop in main() |
Processor Scheduling Algorithm (Choosing Which Task of Many to Execute)
|
First Come First Serve (FCFS) First In First Out (FIFO) |
In this scheduling algorithm, the first process entered in the queue is processed first. |
|---|---|
|
Shortest Job First (SJF) Earliest Deadline First (EDF) |
In SJF the process which requires the shortest CPU time to execute is processed first In EDF the process with the earliest deadline in the queue is processed first |
|
Shortest Remaining Time First (SRTF) |
This scheduling Algorithm is the preemptive version of the SJF scheduling algorithm. In this, the process which is left with the least processing time is executed first. |
|
Longest Job First (LJF) |
In this type of scheduling algorithm, the process with the maximum time required to execute is scheduled first. This type of scheduling is not widely used because it is not a very effective way of scheduling, as the average turn-around time and the average waiting time are maximum in this case. |
|
Longest Remaining Time First (LRTF) |
As SRTF is to SJF, LRTF is the preemptive version of the LJF scheduling algorithm. |
|
Priority Scheduling |
In this scheduling algorithm, priority is assigned to all the processes, and the process with the highest priority is executed first. Priority assignment of processes is done on the basis of internal factors such as CPU and memory requirements or external factors such as user choice. The priority scheduling algorithm supports preemptive and non - preemptive scheduling policies. |
|
Round Robin (RR) |
In this algorithm, the process is allocated the CPU for the specific time period called time slice, which is normally 10 to 100 milliseconds. If the process completes its execution within this time slice, then it is removed from the queue otherwise it has to wait for another time slice. |