CPU Scheduling Algorithms – Preemptive or Non-Preemptive:
Different processes are to be assigned to the CPU Scheduling Algorithms based on particular algorithms. There are six popular process scheduling algorithms that we are going to discuss as follows: First-Come, First-Served (FCFS) Scheduling, Shortest-Job-Next (SJN) Scheduling, Priority Scheduling, Shortest Remaining Time, Round Robin(RR) Scheduling, Multiple-Level Queues Scheduling. HRRN Scheduling.
The Purpose of CPU Scheduling Algorithms
- Maximum CPU utilization
- Fare allocation of CPU
- Maximum throughput
- Minimum turnaround time
- Minimum waiting time
- Minimum response time
Scheduling Criteria
| This is the interval of time between the submission of a process and its com- pletion. Includes actual execution time plus time spent waiting for resources, including the processor. This is an appropriate measure for a batch job. |
| For an interactive process, this is the time from the submission of a request until the response begins to be received. Often a process can begin producing some output to the user while continuing to process the request. Thus, this is a better measure than turnaround time from the user’s point of view |
| When process completion deadlines can be specified, the scheduling discipline should subordinate other goals to that of maximizing the percentage of deadlines met. |
| A given job should run in about the same amount of time and at about the same cost regardless of the load on the system. A wide variation in response time or turnaround time is distracting to users. It may signal a wide swing in system workloads or the need for system tuning to cure instabilities |
| The scheduling policy should attempt to maximize the number of processes completed per unit of time. This is a measure of how much work is being performed. This clearly depends on the average length of a process but is also influenced by the scheduling policy, which may affect utilization. |
| This is the percentage of time that the processor is busy. For an expensive shared system, this is a significant criterion. In single-user systems and in some other systems, such as real-time systems, this criterion is less important than some of the others. |
| In the absence of guidance from the user or other system-supplied guidance, processes should be treated the same, and no process should suffer starvation. |
| When processes are assigned priorities, the scheduling policy should favor higher-priority processes. |
| The scheduling policy should keep the resources of the system busy. Processes that will underutilize stressed resources should be favored. This criterion also involves medium-term and long-term scheduling. |
Decision Mode
The decision mode specifies the instances in time at which the selection function is exercised. There are two general categories:
- Non-preemptive: In this case, once a process is in the Running state, it continues to execute until
- it terminates.
- it blocks itself to wait for I/O or to request some operating system service.
- Preemptive: The currently running process may be interrupted and moved to the Ready state by the operating system. The decision to preempt may be performed when a new process arrives; when an interrupt occurs that places a blocked process in the Ready state; or periodically, based on a clock interrupt.
First-Come-First-Served (FCFS)
The simplest scheduling policy is first-come-first-served (FCFS), also known as first-in-first-out (FIFO) or CPU Scheduling Algorithms a strict queuing scheme. As each process becomes ready, it joins the ready queue. When the currently running process ceases to execute, the process that has been in the ready queue the longest is selected for running.
Advantages
- Simple
- Easy and useful and understand
- First come, first served
Disadvantages
- This scheduling method is non-preemptive, that is, the process will run until it finishes.
- Because of this non-preemptive scheduling, short processes that are at the back of the queue have to wait for the long process at the front to finish throughput is not efficient.
- It is used in a small system only where I/O efficiency is not very important
The Turnaround time and the waiting time are calculated by using the following formula.
- Turn Around Time = Completion Time – Arrival Time.
- Waiting Time = Turn Around Time – Burst Time.
Example:
| AT | BT | CT |
0 1 2 3 | 5 3 8 6 | 5 8 16 22 |
Solutions:
| Process | AT | BT | CT | TAT=CT-AT | WT=TAT-BT |
P0 P1 P2 P3 | 0 1 2 3 | 5 3 8 6 | 5 8 16 22 | 5 7 14 19 | 5 7 14 19 |
Gantt Chart shows the following:
Average Wait Time: (0+4+6+13) / 4 = 5.75
Average Turn Around Time: (5+7+14+19)/4 = 30.75
CPU Scheduling Algorithms
Shortest-Job-First (SJF) Scheduling
The SJF scheduler is exactly like FCFS except that instead of choosing the job at the front of the queue, it will always choose the shortest job (i.e. the job that takes the least time) available. We will use a sorted list to order the processes from longest to shortest.
- Associate with each process the length of its next CPU burst.
- Use these lengths to schedule the process in the shortest time.
There are two SJF scheduling algorithms:
- Non-Preemptive: Once the CPU is given to the process it cannot be preempted until completes its CPU burst. SJF is optimal – gives a minimum average waiting time for a given set of processes.
- Preemptive: If a new process arrives with a CPU burst length less than the remaining time of the current executing process, preempt. This scheme is known as the Shortest-Remaining-Time-First (SRTF)
Example:
Non-Preemptive SJF
| Process | AT | BT |
p1 p2 p3 p4 | 0 2 4 5 | 7 4 1 4 |
Solutions:
| Process | AT | BT | CT | TAT | WT |
p1 p2 p3 p4 | 0 2 4 5 | 7 4 1 4 | 7 8 12 16 | 7 6 8 11 | 0 2 7 7 |
Gantt Chart show in the following:
Average Wait Time: (0+2+7+7) / 4 = 4
Average Turn Around Time: (7+6+8+11)/4 = 8
SJF Preemptive Scheduling (Shortest Remaining Time)
Shortest remaining time (SRT) is the preemptive version of the SJF algorithm.
The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion.
It is often used in batch environments where short jobs need to give preference.
Example:
CT
p1=32
p2=6
p3=12
p4=5
Turn Around Time= CT-AT
p1= 32-0=32
p2=6-1=5
p3=12-2=10
p4=5-3=2
Wait Time
p1=32-21=11
p2=6-3=3
p3=12-6=6
p4=5-2=3
Average Wait Time: (11+3+6+3)/4=5.75
Average Turn Around Time: (32+5+10+2)/4 = 12.25
Round Robin Scheduling Algorithms (RR)
- The simplest such policy is round robin. A clock interrupt is generated at periodic intervals. When the interrupt occurs, the currently running process is placed in the ready queue, and the next ready job is selected on a FCFS basis.
- This technique is also known as time slicing, because each process is given a slice of time before being preempted.
- If the quantum is very short, then short processes will move through the system relatively quickly.
- There is processing overhead involved in handling the clock interrupt and performing the scheduling and dispatching function.
- Round robin is particularly effective in a general-purpose time-sharing system or transaction processing system. One drawback to round robin is its relative treatment of processor-bound and I/O-bound processes.
Diagram of Round Robin Scheduling
CPU Scheduling Algorithms
There are Advantages and Disadvantage of Round Robin are as follows:
Advantages
- Every Thread / Process gets a chance to run.
- CPU is shared between all processes.
- Threads with the same priority are handled perfectly with Round Robin.
Disadvantages
- Low Priority tasks may wait for more time if the many tasks are given high priority.
- High Priority tasks may not execute the full instruction given stipulated amount of time.
Example:
| Process | AT | BT |
p1 p2 p3 p4 p5 p6 | 0 1 2 3 4 5 | 5 6 3 1 5 4 |
Solutions:
| process | AT | BT | CT | TAT | WT |
p1 p2 p3 p4 p5 p6 | 0 1 2 3 4 5 | 5 6 3 1 5 4 | 17 23 11 12 24 21 | 17 22 9 9 20 15 | 12 16 6 8 15 11 |
Gantt Chart for Round Robin are as follows:
Average Wait Time: 92/6=15.33
Average Turn Around Time: 68/6 = 11.33
Priority Scheduling
- The SJF algorithm is a special case of the general priority scheduling algorithm.
- A priority is associated with each process, and the CPU is allocated to the process
with the highest priority. Equal-priority processes are scheduled in FCFS order. - Priority scheduling can be either preemptive or nonpreemptive.
- When a process arrives at the ready queue, its priority is compared with the priority
of the currently running process. - A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process.
- A nonpreemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.
Advantage and disadvantage of priority scheduling algorithms
Advantages
- Simplicity.
- Reasonable support for priority.
- Suitable for applications with varying time and resource requirements.
Disadvantages
- Indefinite blocking or starvation.
- A priority scheduling can leave some low priority waiting processes indefinitely for CPU.
- If the system eventually crashes then all unfinished low priority processes gets lost.
Example:
| Process | BT | AT | Priority |
p1 p2 p3 p4 | 21 3 6 2 | 1 0 3 2 | 2 1 4 3 |
Solutions:
| Process | AT | BT | Priority | CT | TAT | WT | RT |
p1 p2 p3 p4 | 1 0 3 2 | 21 3 6 2 | 2 1 4 3 | 24 3 32 26 | 23 3 29 24 | 2 0 23 22 | 1 0 26 24 |
Gantt Chart for Priority Scheduling are as follows:
Average waiting Time: (2+o+23+22)/4=11.75
Average Turn Around Time: (23+3+29+24)/4=19.75
CPU Scheduling Algorithms
Highest Response Ratio Next (HRRN)
- Conventional HRRN algorithm schedules the tasks based on the response ratio which
provides the solution for starvation problem of scheduling algorithms. - The response ratio for each task is based on the estimated burst time and waiting time. Due to the absence of an exact measure value of burst time, there may be chances of imprecise value.
- Some algorithms use fuzzy techniques to handle this impreciseness. These fuzzy heuristics dealt with impreciseness to some extent.
- Apart from this, these scheduling algorithms have also improved the performance of existing scheduling algorithms.
Consider the following ratio:
R=(w+s)/s
where
- R response ratio
- w time spent waiting for the processor
- s expected service time
If the process with this value is dispatched immediately, R is equal to the normalized
turnaround time. Note that the minimum value of R is 1.0, which occurs when a
process first enters the system.
Example:
| Process | AT | BT |
p0 p1 p2 p3 p4 | 0 2 4 6 8 | 3 5 4 1 2 |
Solutions:
| Process | AT | BT | CT | TAT | WT |
p0 p1 p2 p3 p4 | 0 2 4 6 8 | 3 5 4 1 2 | 3 8 13 9 15 | 3 6 9 3 7 | 0 1 5 2 5 |
Gantt Chart for HRRN are as follows:
- P1 is executed for 5 units. Meanwhile, all the processes get available. We have to calculate the Response Ratio for all the remaining jobs.
RR(P2)=((8-4)+4)/4=2
RR (P3)=(2+1)/1=3
RR (0+2)/2=1
Since, the Response ratio of P3 is higher hence P3 will be scheduled first.
- P3 is scheduled for 1 unit. The next available processes are P2 and P4. Let’s calculate their Response ratio.
RR (P2)=(5+2)/4=2.25
RR (P4)=(1+2)/2=1.5
The response ratio of P2 is higher hence P2 will be scheduled.
Average Wait Time: 13/5= 2.6
Average Turn Around Time: 28/5= 5.6
Reference
Hi, I’m Dev Kirtonia, Founder & CEO of Dev Library. A website that provides all SCERT, NCERT 3 to 12, and BA, B.com, B.Sc, and Computer Science with Post Graduate Notes & Suggestions, Novel, eBooks, Biography, Quotes, Study Materials, and more.