1. Scheduling Algorithms in Operating Systems
Scheduling algorithms are fundamental to the design of effective and efficient operating systems. They are strategies used by the operating system's scheduler to allocate processor time among various tasks. The choice of scheduling algorithm can significantly impact the performance and responsiveness of a system. This documentation delves into various scheduling algorithms, elucidating their mechanisms, benefits, and potential drawbacks.
2. Types of Schedulers
The operating system employs different types of schedulers to manage process scheduling: the long-term scheduler (or job scheduler), the short-term scheduler (or CPU scheduler), and the medium-term scheduler. The long-term scheduler regulates the admission of processes into the ready queue, essentially controlling the degree of multiprogramming. The short-term scheduler, on the other hand, decides which of the ready, in-memory processes are to be executed next by the CPU. The medium-term scheduler temporarily removes processes from the CPU to reduce the degree of multiprogramming, often used in swapping.
2.1 Criteria for Scheduling
Effective scheduling algorithms aim to optimize several criteria: CPU utilization, throughput, turnaround time, waiting time, and response time. CPU utilization seeks to keep the CPU as busy as possible, while throughput measures the number of processes that complete their execution per time unit. Turnaround time is the interval from the submission of a process to the completion of its execution. Waiting time is the sum of periods a process spends waiting in the ready queue, and response time is the time from the submission of a request until the first response is produced, not output (for time-sharing systems).
2.2 Scheduling Algorithms Explained
First-Come, First-Served (FCFS)
FCFS is the simplest type of CPU scheduling algorithm that schedules according to the order of arrival of the processes in the ready queue. It's non-preemptive, meaning once a process starts executing, it runs to completion. While FCFS is easy to implement and understand, it can lead to poor performance in terms of average waiting time, especially in the presence of processes with varying execution times (the convoy effect).
Shortest Job First (SJF)
SJF is a scheduling policy that selects the process with the smallest execution time to run next. It can significantly reduce the average waiting time compared to FCFS and is both available in preemptive and non-preemptive forms. The main challenge of SJF is predicting the next CPU burst length, which might not be feasible in all scenarios. Despite its efficiency in reducing waiting time, SJF can lead to starvation, where longer processes may never get scheduled if shorter processes keep arriving.
Priority Scheduling
Priority scheduling assigns each process a priority, and the CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority). Priorities can be determined by various factors such as memory requirements, time constraints, or user preference. Priority scheduling can be preemptive or non-preemptive. While effective in meeting specific system goals, it can suffer from starvation, which can be mitigated through aging techniques.
Round Robin (RR)
RR is a preemptive variant of CPU scheduling that assigns a fixed time unit called a time quantum or time slice for each process in the ready queue. The processes are scheduled in a circular order, and if a process's execution is not completed within the allocated time quantum, it's placed at the end of the ready queue. RR reduces response time but can increase the average waiting time. The performance of RR significantly depends on the length of the time quantum.
Multilevel Queue Scheduling
Multilevel queue scheduling partitions the ready queue into several separate queues, each with its own scheduling algorithm. Processes are permanently assigned to a queue based on their characteristics, such as process priority, type, or memory requirements. This method allows for flexibility in treating different categories of processes differently but requires complex scheduling logic and may lead to starvation in lower-priority queues.
Multilevel Feedback Queue Scheduling
This variant of multilevel queue scheduling allows processes to move between queues based on their behavior and requirements. It offers the flexibility to adjust the scheduling criteria over time, providing a balance between turnaround time and response time for various types of processes. The configuration of the queues (number, scheduling algorithms, time quantum) significantly influences the effectiveness of this approach.
Implementation Considerations
Implementing scheduling algorithms requires careful consideration of the system's goals and the characteristics of the processes it handles. While theoretical understanding is crucial, practical considerations such as the overhead of context switching, system load, and the predictability of process behavior play a significant role in the choice and customization of scheduling algorithms. Performance metrics and testing under various load conditions are essential to evaluate the effectiveness of a scheduling strategy.
It is imperative to understand that no single scheduling algorithm is universally optimal. The choice depends on the specific requirements and constraints of the operating system environment.
3. Key Terminologies
Understanding the following terms is crucial for grasping the concepts of scheduling algorithms:
- Burst Time: The time required by a process for its execution.
- Arrival Time: The time at which a process arrives in the scheduling queue.
- Waiting Time (WT): The total time a process has been waiting in the queue before its execution.
- Turnaround Time (TAT): The total time taken by a process from getting to the queue to its completion.
- Response Time: The time from the arrival of a process to the first time it is scheduled.
4. Formulas for Calculation
Key formulas used in scheduling algorithms include:
4.1 Waiting Time (WT)
Waiting Time for a process is the total time the process has been in the ready queue waiting to get CPU time. It's calculated as \(WT = TAT - BT\)
Where \(TAT\) is Turnaround Time and \(BT\) is Burst Time.
4.2 Turnaround Time (TAT)
Turnaround Time is the total time taken by the process from getting to the ready queue to its completion. It's calculated as \(TAT = CT - AT\)
Where \(CT\) is Completion Time and \(AT\) is Arrival Time.
4.3 Average Waiting Time (AWT or WTave)
Average Waiting Time is the average of waiting times of all processes. It's calculated as \(AWT = \frac{\sum{WT}}{N}\)
Where \(\sum{WT}\) is the sum of waiting times of all processes, and \(N\) is the number of processes.
4.4 Average Turnaround Time (ATAT or TATave)
Average Turnaround Time is the average of turnaround times of all processes. It's calculated as \(ATAT = \frac{\sum{TAT}}{N}\)
Where \(\sum{TAT}\) is the sum of turnaround times of all processes, and \(N\) is the number of processes.
5. Scheduling Algorithms and Their Execution Sequence
5.1 First-Come, First-Served (FCFS)
In FCFS, processes are executed in the order they arrive in the ready queue, strictly adhering to their arrival times. This method is simple and non-preemptive, meaning once a process starts execution, it runs to completion without interruption. While FCFS is easy to implement and understand, it can suffer from the "convoy effect," where short processes wait for long ones to execute, leading to potentially high average waiting times.
5.2 Shortest Job First (SJF)
SJF selects the process with the shortest execution time (burst time) for the next execution. This strategy significantly reduces the average waiting time, especially for short jobs, by ensuring they are executed first. SJF can be preemptive or non-preemptive. In its preemptive version, a new process with a shorter burst time than the remaining time of the current process can preempt the CPU. However, SJF's main drawback is its potential for process starvation, where longer processes might never get executed if shorter processes keep arriving.
5.3 Priority Scheduling
Priority Scheduling operates by assigning a priority level to every process, and processes with higher priorities are executed first. Like SJF, it can be either preemptive or non-preemptive. In the preemptive variant, a running process can be interrupted if a higher priority process enters the ready queue. This method introduces the challenge of priority inversion, where lower priority processes hold resources needed by higher priority ones. Solutions like priority inheritance or ceiling can mitigate such issues.
5.4 Round Robin (RR)
RR is particularly designed for time-sharing systems, assigning a fixed time slice or quantum to each process in the ready queue and executing them in a cyclic order. This ensures no process monopolizes CPU time, providing a fair allocation of CPU to all processes. The key to RR's effectiveness is the quantum size; too small leads to high context switching overhead, while too large makes RR behave like FCFS. Balancing quantum size is critical for achieving optimal system performance.
5.5 Multilevel Queue Scheduling
Multilevel Queue Scheduling categorizes processes into multiple queues based on specific criteria like process priority, memory size, or process type (system vs. user). Each queue has its own scheduling algorithm, and queues themselves are scheduled according to their priority. This hybrid approach allows for flexibility in handling different types of processes efficiently but requires careful setup of queues and selection of scheduling algorithms for each queue to prevent bottlenecks and ensure fairness across processes.
6. Scheduling Algorithms Examples
Let us create the Gantt Chart and calculate the CT, TAT, WT, TATave, WTave for each process using all the major scheduling algorithms.
Important Considerations
- Priority is only applicable for Priority Based Scheduling.
- We are taking 7 as highest priority.
- Time Quantum for Round Robin TQ = 5.
| Job / Process | AT | BT | Priority |
|---|---|---|---|
| A | 0 | 4 | 5 |
| B | 1 | 5 | 6 |
| C | 2 | 2 | 7 |
| D | 3 | 1 | 3 |
| E | 4 | 6 | 4 |
| F | 5 | 3 | 2 |
| G | 6 | 8 | 1 |
6.1 First-Come, First-Served (FCFS)
Gantt Chart Representation
A
B
C
D
E
F
G
0
4
9
11
12
18
21
29
Performance Metrics
| Job | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 4 | 4 | 0 |
| B | 1 | 5 | 9 | 8 | 3 |
| C | 2 | 2 | 11 | 9 | 7 |
| D | 3 | 1 | 12 | 9 | 8 |
| E | 4 | 6 | 18 | 14 | 8 |
| F | 5 | 3 | 21 | 16 | 13 |
| G | 6 | 8 | 29 | 23 | 15 |
| Average | 83 / 7 = 11.857 | 54 / 7 = 7.714 | |||
6.2 Shortest Job First - Non Preemptive(NSJF)
Gantt Chart Representation
A
D
C
F
B
E
G
0
4
5
7
10
15
21
29
Performance Metrics
| Job | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 4 | 4 | 0 |
| B | 1 | 5 | 15 | 14 | 9 |
| C | 2 | 2 | 7 | 5 | 3 |
| D | 3 | 1 | 5 | 2 | 1 |
| E | 4 | 6 | 21 | 17 | 11 |
| F | 5 | 3 | 10 | 5 | 2 |
| G | 6 | 8 | 29 | 23 | 15 |
| Average | 70 / 7 = 10 | 41 / 7 = 5.857 | |||
6.3 Shortest Job First - Preemptive(SRTF) - Shortest Remaining Time First
Gantt Chart Representation
A
D
C
F
B
E
G
0
4
5
7
10
15
21
29
Performance Metrics
| Job | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 4 | 4 | 0 |
| B | 1 | 5 | 15 | 14 | 9 |
| C | 2 | 2 | 7 | 5 | 3 |
| D | 3 | 1 | 5 | 2 | 1 |
| E | 4 | 6 | 21 | 17 | 11 |
| F | 5 | 3 | 10 | 5 | 2 |
| G | 6 | 8 | 29 | 23 | 15 |
| Average | 70 / 7 = 10 | 41 / 7 = 5.857 | |||
6.4 Round Robin (RR)
Gantt Chart Representation
A
B
C
D
E
F
G
E
G
0
4
9
11
12
17
20
25
26
29
Performance Metrics
| Job | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 4 | 4 | 0 |
| B | 1 | 5 | 9 | 8 | 3 |
| C | 2 | 2 | 11 | 9 | 7 |
| D | 3 | 1 | 12 | 9 | 8 |
| E | 4 | 6 | 26 | 22 | 16 |
| F | 5 | 3 | 20 | 15 | 12 |
| G | 6 | 8 | 29 | 23 | 15 |
| Average | 90 / 7 = 12.857 | 61 / 7 = 8.714 | |||
6.5 Priority - Non-Preemption (NPP)
Gantt Chart Representation
A
D
F
G
E
B
C
0
4
5
8
16
22
27
29
Performance Metrics
| Job | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 4 | 4 | 0 |
| B | 1 | 5 | 27 | 26 | 21 |
| C | 2 | 2 | 29 | 27 | 25 |
| D | 3 | 1 | 5 | 2 | 1 |
| E | 4 | 6 | 22 | 18 | 12 |
| F | 5 | 3 | 8 | 3 | 0 |
| G | 6 | 8 | 16 | 10 | 2 |
| Average | 90 / 7 = 12.857 | 61 / 7 = 8.714 | |||
6.6 Priority - Preemptive(PP)
Gantt Chart Representation
A
D
E
F
G
F
E
A
B
C
0
3
4
5
6
14
16
21
22
27
29
Performance Metrics
| Job | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 22 | 22 | 18 |
| B | 1 | 5 | 27 | 26 | 21 |
| C | 2 | 2 | 29 | 27 | 25 |
| D | 3 | 1 | 4 | 1 | 0 |
| E | 4 | 6 | 21 | 17 | 11 |
| F | 5 | 3 | 16 | 11 | 8 |
| G | 6 | 8 | 14 | 8 | 0 |
| Average | 112 / 7 = 16 | 83 / 7 = 11.857 | |||