1. CPU Scheduling

Modern computer systems usually have many processes in memory at the same time. However, a CPU core can execute only one instruction stream at a time. When multiple processes are ready to execute, the operating system must decide which process should run next. This decision-making process is called CPU Scheduling.

2. Why CPU Scheduling Is Required

Consider the following situation. Five applications are open simultaneously:

• Web Browser
• Music Player
• Code Editor
• Terminal
• File Manager

All of these applications require CPU time. Since only one process can execute on a single CPU core at any instant, the operating system must continuously decide which process receives the CPU next. This decision is performed by the scheduler.

3. Real-World Example

The scheduler selects one process from the ready queue and dispatches it to the CPU for execution.

4. Goals of CPU Scheduling

An effective CPU scheduling algorithm attempts to achieve several goals.

5. Where CPU Scheduling Occurs

CPU scheduling occurs whenever the operating system must choose the next process to execute. Common situations include:

• A running process terminates.
• A running process blocks while waiting for I/O.
• A higher-priority runnable process becomes eligible to execute (for preemptive schedulers).
• A timer interrupt causes the scheduler to reconsider which process should run.

6. The Scheduler

The scheduler is a component of the operating system responsible for selecting the next process to execute according to the scheduling policy. After making its decision, the operating system performs a context switch so that the selected process begins running.

7. Process States Review

CPU scheduling primarily involves processes that are in the Ready state.

The scheduler chooses a process from the Ready state.

8. Key Points

• Only one process executes on a CPU core at a time.
• The scheduler selects the next process from the ready queue.
• CPU scheduling improves system efficiency and responsiveness.
• Scheduling decisions are made by the operating system kernel.
• Different scheduling algorithms optimize different performance goals.

9. Interview Questions

1. What is CPU scheduling?
2. Why is CPU scheduling necessary?
3. Which process state is primarily used by the scheduler?
4. What are the main goals of CPU scheduling?
5. What is the role of the scheduler?

10. Scheduling Terminology

Before studying scheduling algorithms, it is important to understand the basic terms used in CPU scheduling. These terms describe the life cycle of a process from the time it enters the system until it completes execution.

11. Arrival Time (AT)

Arrival Time is the time at which a process enters the ready queue and becomes eligible for CPU scheduling. The scheduler can only select a process after it has arrived.

12. Burst Time (BT)

Burst Time (also called CPU Burst Time) is the total amount of CPU execution time required by a process. It represents how long the process needs the CPU, excluding time spent waiting or performing I/O.

13. Completion Time (CT)

Completion Time is the time at which a process finishes execution.

14. Turnaround Time (TAT)

Turnaround Time is the total elapsed time from the arrival of a process until it completes.

15. Waiting Time (WT)

Waiting Time is the total time a process spends waiting in the ready queue for CPU execution. It does not include the time during which the process is actually executing on the CPU.

16. Response Time (RT)

Response Time is the time from a process's arrival until it first receives CPU time. Unlike turnaround time, response time measures how quickly the process starts executing, not when it finishes.

17. Relationship Between Scheduling Metrics

Each scheduling metric describes a different aspect of process execution. Together, they help evaluate the performance of a scheduling algorithm.

18. Summary Table

19. Interview Questions

1. What is Arrival Time?
2. What is the difference between Burst Time and Waiting Time?
3. How is Turnaround Time calculated?
4. How is Response Time different from Turnaround Time?
5. Why is Response Time important for interactive systems?

20. The Dispatcher

The Scheduler decides which process should run next, but it does not actually start the process. The responsibility of starting the selected process belongs to another kernel component called the Dispatcher. The dispatcher transfers CPU control from the currently running process to the process selected by the scheduler.

21. Scheduler vs Dispatcher

22. How the Dispatcher Works

23. Responsibilities of the Dispatcher

• Perform the context switch.
• Restore the CPU registers of the selected process.
• Restore the process execution context.
• Switch to the appropriate address space.
• Transfer execution to the selected process.

24. Dispatcher Latency

Dispatcher Latency is the time required for the dispatcher to stop one process and begin executing another. This includes the work needed to perform the context switch and resume the selected process.

25. Why Dispatcher Latency Matters

While the dispatcher is performing a context switch, the CPU is not executing user instructions. Frequent context switches increase overhead and reduce the amount of CPU time available for useful application work. Therefore, operating systems attempt to keep dispatcher latency as low as possible.

26. Real-Life Analogy

Imagine a teacher conducting oral examinations.

• The teacher decides which student will answer next.
• The student walks to the front of the classroom.
• The previous student leaves.
• The next student begins answering.

The teacher's decision is similar to the scheduler. The time required to change from one student to another is similar to the dispatcher latency.

27. Dispatcher in Linux

In Linux, scheduling and dispatching are closely integrated within the kernel scheduler. After the scheduler selects the next runnable task, the kernel performs a context switch to transfer execution to that task. Although textbooks often describe the scheduler and dispatcher as separate conceptual components, Linux implements these activities as part of its scheduling subsystem.

28. Key Points

• The scheduler decides which process should run.
• The dispatcher transfers CPU control to that process.
• Dispatcher latency is scheduling overhead.
• Reducing dispatcher latency improves overall system performance.
• Every context switch involves the dispatcher.

29. Interview Questions

1. What is the difference between a scheduler and a dispatcher?
2. What is dispatcher latency?
3. Why should dispatcher latency be minimized?
4. Which component performs the context switch?
5. Why are the scheduler and dispatcher often described separately in textbooks?

30. Context Switching

A Context Switch is the process of stopping the execution of one process and resuming the execution of another. Before switching processes, the operating system saves the execution state (called the context) of the currently running process. Later, when that process is scheduled again, its saved context is restored so that execution continues exactly where it stopped.

31. What is Process Context?

The context of a process is the information required by the operating system to suspend and later resume that process correctly. This information includes the CPU execution state and other kernel-managed information associated with the process.

32. Why Context Switching is Necessary

Context switching allows multiple processes to share the CPU while each process behaves as though it has exclusive use of the processor. Without context switching, the operating system could execute only one process until it terminated or blocked.

33. When Does a Context Switch Occur?

A context switch may occur in several situations:

• The running process blocks while waiting for an I/O operation.
• The running process voluntarily yields the CPU.
• A timer interrupt causes the scheduler to select another runnable process.
• The running process terminates.
• A scheduling policy decides that another runnable process should execute.

34. Context Switch Execution Flow

35. Where is the Context Saved?

The operating system stores the saved execution context in the Process Control Block (PCB) or an equivalent kernel data structure associated with the process. When the scheduler later selects the process again, this saved information is used to restore execution.

36. Before and After Context Switch

37. Does the Process Restart?

No. When a process resumes after a context switch, execution continues from the instruction identified by its saved Program Counter. From the process's perspective, execution appears to continue normally, even though another process may have used the CPU in the meantime.

38. Key Points

• A context switch allows multiple processes to share the CPU.
• The kernel saves the execution state of the current process.
• The scheduler selects the next runnable process.
• The kernel restores the saved state of the selected process.
• The resumed process continues from its previous execution point.

39. Interview Questions

1. What is a context switch?
2. What information forms the context of a process?
3. Why is the Program Counter saved during a context switch?
4. Where is the execution context stored?
5. Does a process restart after a context switch? Explain.

51. Preemptive and Non-Preemptive Scheduling

CPU scheduling algorithms are broadly classified into two categories:

• Non-Preemptive Scheduling
• Preemptive Scheduling

The primary difference is whether the operating system can interrupt a running process before it completes its current CPU burst.

52. Non-Preemptive Scheduling

In Non-Preemptive Scheduling, once a process starts executing on the CPU, it continues until one of the following occurs:

• The process terminates.
• The process voluntarily blocks (for example, waiting for an I/O operation).

The operating system does not forcibly remove the process from the CPU.

53. Example of Non-Preemptive Scheduling

Suppose three processes arrive at time 0.

If P1 starts first under a non-preemptive algorithm, it continues executing until it completes, even if P2 or P3 could finish sooner.

54. Advantages of Non-Preemptive Scheduling

• Simple to implement.
• Lower context-switch overhead.
• Predictable execution once a process begins running.
• Suitable for batch-oriented workloads.

55. Limitations of Non-Preemptive Scheduling

• A long-running process can delay shorter processes.
• Interactive response may become slow.
• CPU responsiveness decreases when lengthy CPU-bound jobs are running.

56. Preemptive Scheduling

In Preemptive Scheduling, the operating system can interrupt a running process and assign the CPU to another runnable process. Preemption occurs according to the scheduling policy. Common reasons include:

• The running process exhausts its time slice.
• A higher-priority runnable process becomes eligible to execute.

57. Example of Preemptive Scheduling

Suppose Process P1 begins execution. After two milliseconds, a higher-priority process P2 becomes ready. Under a preemptive scheduling policy, the scheduler may suspend P1 and allow P2 to execute.

58. Advantages of Preemptive Scheduling

• Improves responsiveness for interactive systems.
• Allows higher-priority processes to execute promptly.
• Supports time-sharing systems.
• Provides better response time for user applications.

59. Limitations of Preemptive Scheduling

• Increases context-switch overhead.
• Scheduling decisions become more complex.
• Frequent preemption may reduce overall CPU efficiency.
• Requires careful synchronization in concurrent applications.

60. Comparison

61. Linux Scheduling

Modern Linux uses preemptive scheduling. The kernel scheduler can preempt a running task according to its scheduling policy, priorities, and time-slice management. The details of Linux's scheduling algorithms, including the Completely Fair Scheduler (CFS), are covered later in this chapter.

62. Key Points

• Non-preemptive scheduling allows a running process to continue until it blocks or terminates.
• Preemptive scheduling allows the operating system to interrupt a running process.
• Preemptive scheduling generally provides better responsiveness.
• Non-preemptive scheduling has lower scheduling overhead.
• Modern desktop and server operating systems primarily use preemptive scheduling.

63. Interview Questions

1. What is the difference between preemptive and non-preemptive scheduling?
2. Which scheduling type provides better response time?
3. Why does preemptive scheduling increase context-switch overhead?
4. Which scheduling type is commonly used by modern operating systems?
5. Can a non-preemptive scheduler interrupt a running process?

64. Scheduling Criteria

Different CPU scheduling algorithms have different strengths and weaknesses. To compare scheduling algorithms fairly, operating systems use several performance measurements called Scheduling Criteria. These criteria help evaluate how efficiently the CPU is used and how well the operating system serves different types of workloads.

65. CPU Utilization

CPU Utilization is the percentage of time that the CPU spends executing useful work rather than remaining idle.

Example

66. Throughput

Throughput is the number of processes completed during a given period of time.

Example

67. Turnaround Time

Turnaround Time is the total elapsed time from the arrival of a process until its completion.

Lower turnaround time generally indicates that processes are completing more quickly.

68. Waiting Time

Waiting Time is the total time that a process spends waiting in the ready queue before receiving CPU execution.

Scheduling algorithms often attempt to minimize the average waiting time across all processes.

69. Response Time

Response Time measures how quickly a process begins execution after it arrives.

Interactive applications such as terminal programs and graphical user interfaces benefit from low response times.

70. Fairness

A scheduling algorithm should provide a reasonable opportunity for every runnable process to obtain CPU time. Fair scheduling helps prevent situations where one process waits indefinitely while other processes continue executing.

71. Relationship Between Scheduling Criteria

Improving one scheduling criterion may negatively affect another. For example:

72. Numerical Example

Consider the following process:

Using the standard formulas:

*Response Time requires knowing when the process first started executing, not just when it completed.

73. Summary Table

74. Interview Questions

1. Why can't a single scheduling algorithm optimize every scheduling criterion?
2. What is the difference between waiting time and response time?
3. Why is CPU utilization alone not sufficient to evaluate a scheduler?
4. Which scheduling criterion is most important for interactive systems?
5. How is throughput measured?

75. First Come First Served (FCFS) Scheduling

First Come First Served (FCFS) is the simplest CPU scheduling algorithm. Processes are executed in the same order in which they arrive in the ready queue. The process that arrives first receives the CPU first.

76. Basic Principle of FCFS

FCFS follows a simple rule:

• The scheduler always selects the process at the front of the ready queue.
• Once a process starts executing, it continues until it terminates or blocks.
• No arriving process can interrupt the currently running process.

Therefore, FCFS is a non-preemptive scheduling algorithm.

77. FCFS Ready Queue

The scheduler always removes the process from the front of the queue. New processes are inserted at the rear.

78. FCFS Execution Flow

79. Example

Consider the following processes. All processes arrive at time 0.

80. Building the Schedule

Since all processes arrive at the same time, they execute in the order they entered the ready queue.

81. Gantt Chart

82. Completion Time Calculation

83. Key Observation

The execution order depends only on the arrival order. Burst time does not influence which process is selected next. A shorter process arriving after a longer process must wait until the longer process releases the CPU.

84. Interview Questions

1. Why is FCFS called a FIFO scheduling algorithm?
2. Is FCFS preemptive or non-preemptive?
3. What determines the execution order in FCFS?
4. Does burst time affect process selection in FCFS?
5. How is a new process inserted into an FCFS ready queue?

85. Waiting Time Calculation

Waiting Time is the total amount of time a process spends waiting in the ready queue before it begins executing.

For non-preemptive FCFS, a process executes only once. Therefore, the waiting time is simply the interval between its arrival and the start of its execution.

86. Waiting Time Example

Using the previous FCFS schedule:

87. Turnaround Time Calculation

Turnaround Time represents the total time from process arrival until completion.

88. Response Time Calculation

Response Time is the time from process arrival until it first receives the CPU.

Since FCFS is a non-preemptive scheduling algorithm, each process starts only once. Therefore, in FCFS:

89. Average Waiting Time

For this example:

90. Average Turnaround Time

91. Complete FCFS Calculation

92. Convoy Effect

One of the major disadvantages of FCFS is the Convoy Effect. A long CPU-bound process at the front of the ready queue can delay many shorter processes waiting behind it. As a result, short processes experience long waiting times even though they require very little CPU time.

93. Why Does the Convoy Effect Occur?

FCFS always schedules processes strictly according to arrival order. It does not consider burst time, priority, or the amount of work remaining. Therefore, if a long-running process arrives first, every subsequent process must wait until it finishes or blocks.

94. Advantages and Limitations of FCFS

95. Interview Questions

1. How is waiting time calculated in FCFS scheduling?
2. Why is response time equal to waiting time in FCFS?
3. What is the Convoy Effect?
4. Why does FCFS suffer from poor average waiting time?
5. Does FCFS guarantee fairness? Explain.

96. FCFS Algorithm

The FCFS scheduling algorithm always selects the process that has been waiting in the ready queue for the longest time. The scheduler removes the process at the front of the ready queue, assigns the CPU to it, and allows it to execute until it terminates or blocks.

97. FCFS Pseudocode

while (ready_queue is not empty)

{

    process = remove_front(ready_queue);

    execute(process);

}

The scheduler repeatedly removes the first process from the ready queue and executes it.

98. C Program to Simulate FCFS Scheduling

#include <stdio.h>

int main()
{
    int bt[] = {5, 3, 2};
    int wt[3];
    int tat[3];

    wt[0] = 0;

    for (int i = 1; i < 3; i++)
        wt[i] = wt[i - 1] + bt[i - 1];

    for (int i = 0; i < 3; i++)
        tat[i] = wt[i] + bt[i];

    printf("Process\tBT\tWT\tTAT\n");

    for (int i = 0; i < 3; i++)
        printf("P%d\t%d\t%d\t%d\n",
               i + 1,
               bt[i],
               wt[i],
               tat[i]);

    return 0;
}

99. Sample Output

Process    BT    WT    TAT

P1         5     0      5

P2         3     5      8

P3         2     8      10

100. Time Complexity

The scheduler simply accesses the front of the ready queue, making FCFS one of the simplest scheduling algorithms.

101. Applications of FCFS

Although modern general-purpose operating systems use more advanced CPU scheduling algorithms, the FCFS principle is still useful in many situations.

102. FCFS in Linux

Modern Linux does not use FCFS as its primary scheduling algorithm for normal user processes. General-purpose scheduling in Linux is designed to balance fairness, responsiveness, and overall system performance. However, the First-In, First-Out principle appears in other parts of the system, such as queue management and certain scheduling policies.

103. Practice Problem

Using FCFS scheduling, calculate the waiting time and turnaround time for the following processes.

Draw the Gantt chart and compute:

• Completion Time
• Waiting Time
• Turnaround Time
• Average Waiting Time
• Average Turnaround Time

104. Key Points

• FCFS is the simplest CPU scheduling algorithm.
• Processes execute in arrival order.
• The scheduler always selects the front of the ready queue.
• FCFS has low scheduling overhead.
• The Convoy Effect is its primary limitation.
• Modern operating systems generally use more sophisticated scheduling algorithms for general-purpose workloads.

105. Interview Questions

1. Why is FCFS considered the simplest scheduling algorithm?
2. What is the time complexity of selecting the next process in FCFS?
3. Why is FCFS rarely used as the primary scheduler in modern operating systems?
4. Where is the FIFO principle commonly used outside CPU scheduling?
5. What limitation of FCFS motivated the development of SJF scheduling?

106. Shortest Job First (SJF) Scheduling

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest CPU burst time from the ready queue. Instead of scheduling processes only according to their arrival order, SJF gives preference to the process that requires the least CPU execution time.

107. Why Was SJF Developed?

The FCFS scheduling algorithm suffers from the Convoy Effect, where a long-running process can delay many short processes. SJF addresses this problem by selecting the shortest available CPU burst first. As a result, many short processes finish earlier, reducing the average waiting time.

108. Basic Principle of SJF

• Select the process with the smallest CPU burst time.
• If multiple processes have the same burst time, use their arrival order to break the tie.
• Execute the selected process.
• Repeat until all processes complete.

This section discusses the non-preemptive version of SJF. The preemptive version, called Shortest Remaining Time First (SRTF), will be covered later.

109. Example Processes

110. Selecting the First Process

All four processes arrive at the same time. The scheduler compares their CPU burst times.

Since P2 has the smallest burst time, it executes first.

111. Scheduling Order

The scheduler continues selecting the process with the shortest burst time among the remaining ready processes.

112. Gantt Chart

113. Completion Time

114. Why SJF Improves Performance

By allowing shorter processes to complete first, SJF reduces the amount of time that many processes spend waiting in the ready queue. This generally produces a lower average waiting time than FCFS for the same set of processes. However, longer processes may experience increased waiting times.

115. Key Points

• SJF selects the process with the shortest CPU burst.
• This section covers the non-preemptive version.
• SJF usually reduces average waiting time compared with FCFS.
• Burst time determines process selection.
• Arrival time is used to break ties when burst times are equal.

116. Interview Questions

1. What is the basic idea behind SJF scheduling?
2. Why was SJF introduced after FCFS?
3. Which process executes first in SJF?
4. What happens if two processes have the same burst time?
5. Is the SJF algorithm covered here preemptive or non-preemptive?

117. Waiting Time Calculation

The waiting time of a process is the total time it spends waiting in the ready queue before it starts execution. For non-preemptive SJF, each process begins execution only once.

118. Waiting Time Example

Using the previous SJF schedule:

119. Turnaround Time Calculation

120. Response Time

Response Time is the interval between process arrival and the first time the CPU begins executing that process.

Since non-preemptive SJF starts each process only once:

121. Average Waiting Time

122. Average Turnaround Time

123. Comparison with FCFS

*Computed using the FCFS example with processes (P1=5, P2=3, P3=2).

**Computed using the SJF example with processes (P1=6, P2=2, P3=8, P4=3).

124. Why SJF Usually Performs Better

Short processes complete quickly instead of waiting behind long CPU-bound processes. This generally reduces the average waiting time compared with FCFS when both algorithms are evaluated using the same workload.

125. Starvation

One disadvantage of SJF is starvation. If short processes continue arriving, a long process may wait for a very long time before receiving the CPU.

126. Burst Time Prediction

SJF requires knowledge of CPU burst times. In practice, an operating system usually does not know the exact CPU burst that a process will require in the future. Some systems estimate future CPU bursts using information from previous CPU bursts.

127. Key Points

• Waiting Time = Start Time − Arrival Time.
• Turnaround Time = Completion Time − Arrival Time.
• Response Time equals Waiting Time in non-preemptive SJF.
• SJF generally reduces average waiting time for the same workload.
• Starvation is the primary limitation of SJF.
• Exact future CPU burst times are generally unavailable in real operating systems.

128. Interview Questions

1. Why can SJF reduce average waiting time?
2. What is starvation in SJF scheduling?
3. Why is burst time prediction difficult?
4. Can SJF always be implemented exactly in a real operating system?
5. Why should two scheduling algorithms be compared using the same workload?

129. Shortest Remaining Time First (SRTF)

Shortest Remaining Time First (SRTF) is the preemptive version of the Shortest Job First (SJF) scheduling algorithm. Instead of selecting the process with the shortest total CPU burst, SRTF always executes the process with the shortest remaining CPU execution time.

130. Why SRTF Was Developed

Non-preemptive SJF cannot interrupt a long-running process after it has started executing. As a result, a newly arrived short process must wait until the running process completes. SRTF solves this limitation by allowing the operating system to preempt the currently running process whenever a shorter remaining job becomes available.

131. Basic Principle of SRTF

• Select the process with the shortest remaining CPU time.
• Continuously compare newly arrived processes with the running process.
• Preempt the running process if a shorter remaining job arrives.
• Resume interrupted processes later when selected again.

132. Example

133. Step-by-Step Scheduling

Time = 0

• P1 starts execution.

Time = 1

• P2 arrives.
• P1 has 7 ms remaining.
• P2 requires only 4 ms.
• P1 is preempted.
• P2 begins execution.

Time = 2

• P3 arrives.
• P2 has 3 ms remaining.
• P3 requires 2 ms.
• P2 is preempted.
• P3 begins execution.

Time = 3

• P4 arrives.
• P3 has 1 ms remaining.
• P4 requires 1 ms.
• Both have equal remaining time.
• The scheduler continues executing P3 because it reached the ready state earlier.

134. Execution Timeline

135. Completion Order

136. Why SRTF Improves Response Time

Short processes begin execution soon after they arrive because the scheduler can interrupt longer-running processes when appropriate. This generally improves response time for short jobs compared with non-preemptive scheduling algorithms.

137. Key Points

• SRTF is the preemptive version of SJF.
• The scheduler always considers the remaining CPU burst.
• A running process may be interrupted.
• Interrupted processes later resume execution.
• Short processes generally receive faster service.

138. Interview Questions

1. Why is SRTF considered the preemptive version of SJF?
2. What causes a running process to be preempted in SRTF?
3. What does "remaining time" mean?
4. How is SRTF different from FCFS?
5. How is SRTF different from non-preemptive SJF?

139. Waiting Time Calculation

The waiting time of a process is the total time it spends in the ready queue while not executing. Unlike non-preemptive scheduling, a process in SRTF may enter the ready queue multiple times because it can be preempted. Therefore, waiting time includes all waiting periods.

140. Completion Time

Using the previous execution timeline:

141. Turnaround Time Calculation

142. Waiting Time Calculation

143. Response Time Calculation

Response Time measures how long a process waits before it first receives the CPU. Unlike waiting time, response time ignores later preemptions.

144. Average Waiting Time

145. Average Turnaround Time

146. Complete Scheduling Table

147. Advantages of SRTF

• Generally produces lower average waiting time than non-preemptive SJF for the same workload.
• Improves responsiveness for short processes.
• Allows newly arrived short jobs to execute quickly.
• Reduces the waiting time of short CPU bursts.

148. Limitations of SRTF

• Requires frequent scheduling decisions.
• Increases context-switch overhead.
• Exact future CPU burst times are generally unknown.
• Long-running processes may experience starvation.

149. Interview Questions

1. Why can waiting time be larger than response time in SRTF?
2. Why is response time different from waiting time in preemptive scheduling?
3. Why does SRTF usually outperform SJF for interactive workloads?
4. Can SRTF cause starvation?
5. Why is SRTF difficult to implement perfectly in real operating systems?

150. Priority Scheduling

Priority Scheduling is a CPU scheduling algorithm in which each process is assigned a priority value. The scheduler selects the process with the highest scheduling priority from the ready queue. Unlike FCFS and SJF, process selection depends primarily on priority rather than arrival order or CPU burst time.

151. Why Priority Scheduling?

Not all processes are equally important. Some processes require immediate CPU access, while others can tolerate longer waiting times. Priority scheduling enables the operating system to favor more important processes.

Examples include:

• Emergency system tasks.
• Real-time control applications.
• Critical operating system services.
• Background maintenance tasks.

152. Basic Principle

• Assign a priority to every process.
• Select the highest-priority ready process.
• If priorities are equal, use another rule such as FCFS.
• Repeat until every process completes.

153. Example

Assumption: Lower numerical value indicates higher priority.

154. Selecting the Next Process

The scheduler compares the priorities of all ready processes.

Execution Order:

155. Gantt Chart

156. Completion Time

157. Non-Preemptive Priority Scheduling

In non-preemptive priority scheduling, once a process begins execution, it continues until it terminates or blocks. Even if a higher-priority process arrives later, the currently running process is not interrupted.

158. Preemptive Priority Scheduling

In preemptive priority scheduling, the operating system compares the priority of the running process with that of newly arrived processes. If a newly arrived process has a higher priority, the currently running process is preempted.

159. Key Points

• Priority scheduling selects the highest-priority ready process.
• This section assumes lower numerical values indicate higher priority.
• Equal priorities are commonly resolved using FCFS.
• Priority scheduling has both preemptive and non-preemptive forms.
• Process selection depends primarily on priority.

160. Interview Questions

1. How does Priority Scheduling differ from SJF?
2. What assumption about priority values is used in this chapter?
3. How are equal-priority processes commonly handled?
4. What is the difference between preemptive and non-preemptive Priority Scheduling?
5. Can Priority Scheduling interrupt a running process?

161. Waiting Time Calculation

Using the scheduling order from the previous example:

162. Turnaround Time Calculation

163. Response Time

In this non-preemptive example, each process starts execution only once. Therefore,

164. Average Waiting Time

165. Average Turnaround Time

166. Starvation in Priority Scheduling

A low-priority process may wait indefinitely if higher-priority processes continue arriving. This situation is called starvation (also known as indefinite postponement).

The waiting time of the low-priority process can become extremely large, and in some cases it may never receive the CPU.

167. Aging

Aging is a scheduling technique used to prevent starvation. The operating system gradually increases the scheduling priority of processes that have been waiting for a long time. Eventually, the waiting process becomes important enough to receive CPU time.

168. Priority Inversion

Priority inversion occurs when a high-priority process is forced to wait because a lower-priority process holds a resource that the higher-priority process needs. If one or more medium-priority processes continue executing while the low-priority process cannot run and release the resource, the high-priority process may experience unexpected delays.

169. Priority Inheritance

One common solution is the Priority Inheritance Protocol. When a low-priority process holds a resource required by a higher-priority process, the operating system temporarily raises the priority of the resource holder. After the resource is released, the process returns to its original priority.

170. Advantages of Priority Scheduling

• Important processes receive CPU time earlier.
• Suitable for systems with different task importance.
• Supports real-time and embedded applications.
• Can improve responsiveness for critical tasks.

171. Limitations of Priority Scheduling

• Starvation may occur.
• Choosing appropriate priorities can be difficult.
• Frequent preemption increases context-switch overhead.
• Priority inversion can reduce responsiveness if not managed.

172. Interview Questions

1. What is starvation in Priority Scheduling?
2. How does aging prevent starvation?
3. What is priority inversion?
4. Why is priority inheritance used?
5. What is the difference between aging and priority inheritance?

173. Round Robin (RR) Scheduling

Round Robin (RR) is a preemptive CPU scheduling algorithm in which every ready process receives a fixed amount of CPU execution time called the Time Quantum (also known as the Time Slice). If a process does not finish within its allocated time quantum, the operating system preempts it and places it at the end of the ready queue. The next ready process then receives the CPU.

174. Why Round Robin Was Developed

Algorithms such as FCFS and SJF may cause some processes to wait for a long time before receiving CPU time. Round Robin improves fairness by allowing every ready process to execute for a short interval before giving another process an opportunity to run. This approach is particularly suitable for time-sharing systems, where multiple users or applications share the CPU.

175. Time Quantum (Time Slice)

The Time Quantum is the maximum continuous amount of CPU time that a process may use before the scheduler checks whether another ready process should execute.

If the process finishes before the time quantum expires, it leaves the CPU immediately.

176. Circular Ready Queue

Round Robin maintains the ready processes in a logical circular queue. After a process uses its time quantum without finishing, it moves to the end of the queue.

177. Example

Assume the following processes arrive at time 0. Time Quantum = 2 ms

178. First Round

179. Second Round

180. Gantt Chart

181. Completion Time

182. Key Points

• Round Robin is a preemptive scheduling algorithm.
• Every process receives a fixed time quantum.
• Processes that do not finish return to the end of the ready queue.
• The scheduler repeatedly cycles through the ready queue.
• Round Robin emphasizes fairness among ready processes.

183. Interview Questions

1. What is the purpose of the time quantum?
2. Why is Round Robin considered fair?
3. What happens when a process does not finish within one time quantum?
4. Why is Round Robin called a preemptive scheduling algorithm?
5. Which types of systems commonly use Round Robin scheduling?

184. Waiting Time Calculation

In Round Robin scheduling, a process may wait multiple times because it can be preempted after every time quantum. Therefore, the easiest method is:

185. Turnaround Time Calculation

186. Waiting Time Calculation

187. Response Time

Response Time is the time between process arrival and the first time the CPU begins executing the process. Later preemptions do not affect response time.

188. Average Waiting Time

189. Average Turnaround Time

190. Choosing an Appropriate Time Quantum

The value of the time quantum has a significant impact on the performance of Round Robin scheduling.

191. Advantages of Round Robin

• Provides fair CPU allocation.
• Good response time for interactive users.
• No process can monopolize the CPU indefinitely.
• Suitable for time-sharing systems.
• Simple to implement.

192. Limitations of Round Robin

• Performance depends heavily on the chosen time quantum.
• Frequent context switches increase CPU overhead.
• Average waiting time may be higher than SJF for the same workload.
• Not ideal for hard real-time scheduling requirements.

193. Practical Applications

Round Robin scheduling is widely used in systems that require fair CPU sharing among multiple runnable processes. Common applications include:

• Time-sharing operating systems.
• Interactive desktop environments.
• Multi-user computer systems.
• Educational operating systems and scheduling simulators.

194. Interview Questions

1. Why does Round Robin require a time quantum?
2. What happens if the time quantum is too small?
3. What happens if the time quantum is too large?
4. Why is Round Robin considered fair?
5. How is Round Robin different from FCFS?
6. Can Round Robin cause starvation?
7. Why is response time different from waiting time in Round Robin?

195. Multilevel Queue (MLQ) Scheduling

In Multilevel Queue (MLQ) scheduling, the ready queue is permanently divided into multiple queues based on process type. Each queue contains a specific category of processes. A process remains in its assigned queue throughout its lifetime.

196. Characteristics of MLQ

• Processes are permanently assigned to a queue.
• Each queue may use its own scheduling algorithm.
• Queues may have different priorities.
• Processes normally do not move between queues.

197. Multilevel Feedback Queue (MLFQ)

The Multilevel Feedback Queue (MLFQ) extends MLQ by allowing processes to move between queues. The scheduler adjusts process priority based on observed execution behavior.

198. Characteristics of MLFQ

• Processes may move between queues.
• CPU-intensive processes gradually move to lower-priority queues.
• Interactive processes can remain in higher-priority queues.
• Designed to improve responsiveness while maintaining fairness.

199. Linux Completely Fair Scheduler (CFS)

Modern Linux systems use the Completely Fair Scheduler (CFS) for normal processes. Instead of fixed time slices or static priorities, CFS attempts to distribute CPU time fairly among runnable processes.

200. Scheduling Algorithm Comparison

201. Choosing the Right Scheduling Algorithm

203. Final Interview Questions

1. Which scheduling algorithm minimizes average waiting time under the assumption that CPU burst times are known?
2. Why is Round Robin preferred for interactive systems?
3. What is the difference between MLQ and MLFQ?
4. What is starvation and which algorithms can experience it?
5. How does aging prevent starvation?
6. What is priority inversion?
7. What is the role of the dispatcher?
8. Why does context switching introduce overhead?
9. What scheduling algorithm is commonly used for normal processes in modern Linux?
10. When should SRTF be preferred over SJF?