Chapter 6: CPU Scheduling

Chapter 6: CPU Scheduling

Overview

  • Context: This chapter focuses on CPU scheduling, essential for multiprogrammed operating systems.

  • Content Areas:

    • Basic Concepts

    • Scheduling Criteria

    • Scheduling Algorithms

    • Thread Scheduling

    • Multiple-Processor Scheduling

    • Real-Time CPU Scheduling

    • Examples from Various Operating Systems

    • Algorithm Evaluation

Objectives

  • Introduce CPU scheduling and its importance in multiprogrammed operating systems.

  • Describe various CPU-scheduling algorithms and their functionalities.

  • Discuss evaluation criteria used for selecting appropriate CPU-scheduling algorithms for specific systems.

  • Examine the scheduling algorithms utilized by multiple operating systems.

Basic Concepts

  • CPU Utilization: Achieved through multiprogramming, maximizing the number of processes in execution.

  • CPU–I/O Burst Cycle: Refers to the alternating sequence of CPU execution (CPU burst) and waiting for I/O operations (I/O burst).

    • CPU bursts are followed by I/O bursts.

    • Distribution of CPU burst times is critical for scheduling decisions.

CPU Burst Distribution

  • Presents a histogram indicating distribution of CPU burst durations:

    • Frequencies across various burst durations measured in milliseconds (histogram data illustrated).

CPU Scheduler

  • Short-Term Scheduler: Selects a process from the ready queue to allocate CPU time.

    • Queue can be organized in different ways to optimize scheduling decisions.

    • Scheduling decisions may occur during the following events:

    1. When a process switches from running to waiting.

    2. When a process switches from running to ready.

    3. When a process switches from waiting to ready.

    4. When a process terminates.

    • Non-preemptive Scheduling: Occurs during switching in states 1 and 4.

    • Preemptive Scheduling: Involves other transitions (states 2 and 3).

    • Considerations:

    • Access to shared data during scheduling.

    • Effects of preemption while in kernel mode.

    • Interrupts during critical OS tasks.

Dispatcher

  • Dispatcher Module: Responsible for handing control of the CPU to the scheduled process, involving:

    • Context switching

    • Switching to user mode

    • Jumping to the appropriate location in the user program to resume execution.

  • Dispatch Latency: Time taken for the dispatcher to stop one process and start another.

Scheduling Criteria

  1. CPU Utilization: Aim to maximize CPU activity.

  2. Throughput: Number of processes completing execution per unit time.

  3. Turnaround Time: Total time taken to execute a specific process.

  4. Waiting Time: Total time a process waits in the ready queue before execution.

  5. Response Time: Time taken from submitting a request to receiving the first response (important in time-sharing environments).

Scheduling Algorithm Optimization Criteria

  • Goals include maximizing or minimizing various factors:

    • Maximize CPU utilization

    • Maximize throughput

    • Minimize turnaround time

    • Minimize waiting time

    • Minimize response time

First-Come, First-Served (FCFS) Scheduling

  • Example of FCFS (Process Burst Time):

    • P1: 24 ms, P2: 3 ms, P3: 3 ms.

    • Arrival Order: P1, P2, P3.

    • Gantt Chart Demonstration:

    • Waiting Time: P1 = 0 ms, P2 = 24 ms, P3 = 27 ms.

    • Average Waiting Time: rac{0 + 24 + 27}{3} = 17 ext{ ms} .

Convoy Effect

  • Convoy Effect: Short processes get delayed behind longer processes; often occurs in a mix of CPU-bound and I/O-bound processes.

Shortest-Job-First (SJF) Scheduling

  • Definition: Schedule processes based on the length of their next CPU burst, prioritizing the shortest.

  • Optimality: SJF provides the lowest average waiting time for a set of processes.

  • Challenge: Indicating the length of the next CPU request, which may involve user input.

SJF Example

  • Process Arrival Time & Burst Time:

    • P1: 0.0 s, 6 ms

    • P2: 2.0 s, 8 ms

    • P3: 4.0 s, 7 ms

    • P4: 5.0 s, 3 ms

  • Average Waiting Time Calculation: rac{3 + 16 + 9 + 0}{4} = 7 ext{ ms} .

Prediction of Length of Next CPU Burst

  • Length can be estimated from previous CPU bursts; exponential averaging is employed to refine prediction:

    • Commonly, eta (smoothing factor) is set to rac{1}{2} .

  • Preemptive Version: Termed Shortest-Remaining-Time-First (SRTF), allows interruptions from shorter next jobs.

Priority Scheduling

  • Concept: Each process has a priority (integer), and the CPU is allocated to the process with the highest priority (smallest integer).

    • Can be implemented in both preemptive and non-preemptive forms.

    • SJF can be seen as a priority scheduling where priority inversely correlates with CPU burst time.

  • Issues: Low-priority processes may face starvation and require mechanisms like aging to prevent this.

Priority Scheduling Example

  • Process Arrival Time & Burst Time with Priorities:

    • P1: 10 ms, Priority 3

    • P2: 1 ms, Priority 1

    • P3: 2 ms, Priority 4

    • P4: 1 ms, Priority 5

    • P5: 5 ms, Priority 2

  • Average Waiting Time: 8.2 ms.

Round Robin (RR) Scheduling

  • Definition: Each process receives a small unit of CPU time (time quantum q ), usually between 10-100 ms. Upon expiry, processes are placed at the end of the ready queue.

  • Performance Considerations:

    • For n processes, each gets rac{1}{n} of CPU time in chunks of maximum q time units.

    • No process waits more than (n-1) q time units.

    • Timer interrupts schedule the next process.

    • Larger q approaches FCFS behavior while smaller q requires consideration for context switch overhead.

RR Example

  • Process Burst Times Example with Time Quantum = 4 ms:

    • Processes:

    • P1: 24 ms

    • P2: 3 ms

    • P3: 3 ms

    • Provides better response than SJF on average, though typically has higher average turnaround.

    • Suggested that q be large in comparison to context switch time, ideally 10 ms to 100 ms.

Multilevel Queue Scheduling

  • Structure: Ready queue split into multiple queues (e.g., foreground (interactive) vs. background (batch)). Each queue uses its own scheduling algorithm.

  • Scheduling Methods:

    • Fixed priority: all processes from the higher priority queue are served before the lower one (risk of starvation).

    • Time slice allocations: separate CPU time divisions for different queues (e.g., 80% to foreground, 20% to background).

Multilevel Feedback Queue

  • Definition: Allows a process to move between queues, using aging mechanisms to manage priorities dynamically.

  • Implementation Factors:

    • Number of queues

    • Scheduling algorithms allocated to each queue

    • Methods defined for upgrade/demotion of process priorities

    • Queue assignment methods for servicing processes.

Thread Scheduling

  • Types of Threads: User-level vs. kernel-level threads.

    • Thread scheduling models: many-to-one and many-to-many, affecting competition among threads.

  • Pthread Scheduling:

    • API Features: Allows specification of scheduling scope (PCS or SCS) during thread creation.

    • Can impact OS behaviour with limitations in scope depending on OS implementations (like Linux and Mac OS X).

Multiple-Processor Scheduling

  • Complexity: Does increase when multiple CPUs are present.

  • Processor Configurations:

    • Homogeneous multiprocessors with shared data structures.

    • Asymmetric vs. symmetric multiprocessing.

  • Processor Affinity: Processes prefer to stay on the CPU they are on, categorized into soft and hard affinity.

  • Load Balancing:

    • Essential in SMP to ensure even workload distribution:

    • Push migration: Overloaded tasks are pushed to underloaded CPUs.

    • Pull migration: Idle CPUs pull jobs from busy CPUs.

Multicore Processors

  • Definition: Trend towards having multiple cores on the same chip to enhance speed and efficiency at reduced power consumption.

  • Multithreading: Involves progressing on different threads while managing memory stalls.

Real-Time CPU Scheduling

  • Challenges: Differentiated by soft and hard real-time systems, focusing on guaranteeing service by deadlines.

  • Latencies affecting performance include:

    • Interrupt latency: Time from interrupt arrival to servicing.

    • Dispatch latency: Time to switch processes in the scheduler.

Rate Monotonic Scheduling

  • Mechanism: Assign priorities inversely to process periods; shorter periods mean higher priority.

  • Missed Deadlines: Illustrated with potential scenarios in scheduling decisions.

Earliest Deadline First (EDF) Scheduling

  • Principle: Assigns priorities based on deadlines—earlier deadlines receive higher priorities.

Proportional Share Scheduling

  • Definition: Shares allocated among processes where each application receives a fraction proportional to its allocated shares.

POSIX Real-Time Scheduling

  • Standardization: Exists for real-time threads, including classes like SCHEDFIFO and SCHEDRR.

  • API Functions to manage scheduling policies and attain thread coherence across diverse systems.

Operating System Scheduling Examples

  • Linux Scheduling: Preemptive priority scheduling, with fixes and improvements over versions (notably 2.5 and later enhancements to the Completely Fair Scheduler (CFS)).

  • Windows Scheduling: Prioritized preemptive scheduling with optimal thread management.

  • Solaris Scheduling: Multilevel feedback queues and class prioritization allowing dynamic adjustment based on workload.

Algorithm Evaluation

  • Selection Criteria: Involves determining the criteria and applying it to evaluate CPU-scheduling algorithms.

  • Deterministic modeling: Characteristics of each algorithm assessed under controlled workloads.

Queueing Models

  • Develop a probabilistic description of process arrivals and CPU/I/O tasks; calculations offer throughput, utilization, waiting time estimates.

  • Little’s Formula: n = ext{average queue length}, W = ext{average waiting time}, ext{and } \ n = ar{λ} imes W for steady-state processes.

Simulations

  • Solve analytic limitations by programming simulation models representing a computer system to collect statistical data on algorithm performance.

  • Influenced by various probabilistic inputs and tracing real system events.

Implementation

  • Implementation of new schedulers in real environments entails significant costs and risks due to variable environments, necessitating flexible adaptations and priority management.

Conclusion

  • End of Chapter: Methods and effectively aligning CPU scheduling with operating system requirements contribute significantly to performance and resource optimization.