Chapter 5: CPU Scheduling

CPU Scheduling

• CPU Scheduling is the method by which the operating system decides which process in the ready state will be allocated CPU time.

• The CPU Scheduler uses a ready queue containing Process Control Blocks (PCBs) of processes that are ready to execute.

• The ready queue does not necessarily follow a First-In-First-Out (FIFO) order.

CPU-I/O Burst Cycle

• The CPU-I/O Burst Cycle indicates that process execution consists of alternating cycles of CPU execution and I/O waiting.

• Maximum CPU utilization can be achieved through multiprogramming by overlapping CPU bursts with I/O bursts.

CPU Scheduling Decisions

The CPU scheduling decisions may occur under the following conditions:

1. Process switches from running to waiting state (e.g., I/O request).

2. Process switches from running to ready state (e.g., due to an interrupt).

3. Process switches from waiting to ready state (e.g., after I/O completion).

4. Process terminates.

• Nonpreemptive scheduling occurs in conditions 1 and 4. All other situations involve preemptive scheduling.

Preemptive Scheduling

• The CPU Scheduler can take CPU away from a running process to allocate it to another process.

• Preemptions may happen whenever interrupts occur, requiring the existing process to be temporarily suspended.

• Care must be taken when accessing shared data to avoid simultaneous access issues.

Nonpreemptive Scheduling

• Once a process is allocated the CPU, it retains it until it voluntarily releases it or terminates.

• This type of scheduling is simpler and does not require additional hardware like a timer.

• However, it has less flexibility in fulfilling timing constraints and may hinder responsiveness in some scenarios.

Dispatcher

• The dispatcher differentiates between CPU processes by managing context switching, switching to user mode, and executing processes as necessary.

• Dispatch latency refers to the time taken by the dispatcher to switch from one process to another.

Scheduling Criteria

• CPU Utilization: Aim to keep the CPU busy.

• Throughput: The number of processes completed per time unit.

• Turnaround Time: Total time from submission to completion (includes I/O wait).

• Waiting Time: Total time spent by a process in the ready queue.

• Response Time: Time from request submission to the first response, pertinent in interactive systems.

Comparison of Scheduling Algorithms

First-Come, First-Served (FCFS)

• Example: Processes P1, P2, P3 with respective burst times.

  • Waiting time for P1 = 0, P2 = 24, P3 = 27

  • Average waiting time = (0 + 24 + 27)/3 = 17

• Cons: Convoy effect can lead to poor responsiveness.

Shortest-Job-First (SJF)

• Prioritizes processes with the shortest next CPU burst.

• Two Variants: Nonpreemptive and preemptive (Shortest-Remaining-Time-First, SRTF).

• Considered optimal for minimizing average waiting time.

Round Robin (RR)

• Each process receives a small time quantum (e.g., 10-100 ms).

• If a process does not finish in its quantum, it is preempted and added back to the ready queue.

• Average waiting time calculation is based on the total waiting time accumulated across processes.

Multilevel Queue Scheduling

• The ready queue is partitioned into separate queues (e.g., foreground, background), each with its scheduling algorithm.

• Fixed priority scheduling works with starvation risk for lower-priority processes.

Real-Time CPU Scheduling

• Soft Real-Time: Critical tasks have highest priority but no guarantee of scheduling.

• Hard Real-Time: Tasks must be serviced by specific deadlines.

Evaluation of Scheduling Algorithms

• Performance of scheduling algorithms can be analyzed using deterministic modeling for predetermined workloads.

• Algorithms may be evaluated based on average waiting time calculations.

Conclusion

• CPU Scheduling is essential to efficient process management, impacting overall system performance. Various strategies have their implications on responsiveness, utilization, and service quality, necessitating a fit-for-purpose approach tailored to system requirements.