CPU schduling

Chapter 5: CPU Scheduling

Basic Concepts

  • CPU Utilization: Maximum CPU utilization is achieved through multiprogramming.

  • CPU-I/O Burst Cycle: Process execution involves alternating cycles of CPU execution and I/O waiting.

  • CPU Burst Distribution: Distribution of bursts influences scheduling efficiency.

Key Sequence of CPU and I/O Bursts

  • Processes follow an alternating sequence of CPU execution and I/O operations, affecting overall performance.

Histogram of CPU-burst Times

  • A graphical representation showing the frequency of CPU bursts.

CPU Scheduler

  • Responsible for selecting processes ready to execute from memory.

  • Allocates CPU to processes based on specific scheduling decisions.

    1. Nonpreemptive Scheduling: Involves transitions from running to waiting or termination states.

    2. Preemptive Scheduling: Occurs when processes switch from running to ready when a higher-priority process arrives.

Dispatcher

  • Dispatcher Module: Transfers control of the CPU to the selected process by performing three key tasks:

    • Context Switching: Changing from one process's context to another's.

    • User Mode Transition: Switching CPU to user mode.

    • Jump to User Program: Resuming the user process at the appropriate location.

  • Dispatch Latency: The time needed to switch from one process to another.

Scheduling Criteria

  • CPU Utilization: Keep the CPU as busy as possible.

  • Throughput: Number of processes completed per time unit.

  • Turnaround Time: Total time taken to complete a particular process.

  • Waiting Time: Time a process spends waiting in the ready queue.

  • Response Time: Time taken from request submission to the first response.

Optimization Criteria

  • Aim to maximize CPU utilization and throughput while minimizing turnaround time, waiting time, and response time.

Scheduling Algorithms

First-Come, First-Served (FCFS)

  • Process Burst Times: Example with processes P1, P2, and P3.

  • Waiting times calculated based on order of arrival:

    • Average waiting time is calculated to be 17 units.

  • Convoy Effect: Short processes can be delayed by long processes.

Shortest-Job-First (SJF) Scheduling

  • Assigns processes based on the shortest next CPU burst size.

    • Nonpreemptive: Once a process has the CPU, it runs until completion.

    • Preemptive: If a new process arrives with a shorter burst time, it preempts the current running process.

  • Optimal: Provides minimum average waiting time for a set of processes.

Process Arrival and Burst Times Example**

  • Calculation of average waiting time in both non-preemptive and preemptive SJF scenarios.

Estimation of Next CPU Burst Length

  • Length estimation based on previous CPU bursts using exponential averaging techniques.

Priority Scheduling

  • Each process is assigned a priority number; CPU is allocated based on priority.

    • Issues of Starvation associated with low-priority processes.

    • Aging: Increases the priority of waiting processes over time.

Round Robin (RR)

  • Each process receives a limited amount of CPU time (time quantum).

    • Performance varies based on the size of the time quantum relative to the context switch time.

  • Average Turnaround Time: Tends to be higher than SJF but improves response times.

Multilevel Queue

  • Structure: Separate queues for different process types (foreground interactive, background batch).

  • Each queue uses its scheduling algorithm; Interleaving where foreground gets priority.

  • Fixed Priority Scheduling can lead to starvation for certain queues.

Multilevel Feedback Queue

  • A process can move among queues based on its behavior, enhancing the scheduling strategy.

  • Defined by multiple parameters: number of queues, scheduling algorithms, and methods for process upgrades/demotions.

Multiple-Processor Scheduling

  • More complex than single-processor scheduling due to possible load sharing among homogeneous processors.

  • Asymmetric Multiprocessing: One processor manages system data structures to reduce the need for data sharing.

Real-Time Scheduling

  • Distinction between Hard real-time systems (guaranteed completion of tasks) and Soft real-time systems (priority scheduling for critical tasks).

Thread Scheduling

  • Two primary types: Local Scheduling (threads library) and Global Scheduling (kernel decision-making).

Example of Java Thread Scheduling

  • JVM uses a preemptive, priority-based algorithm.

  • FIFO queues if multiple threads have identical priorities.

Algorithm Evaluation

  • Deterministic Modeling: Testing algorithms with predetermined workloads to ascertain performance based on various criteria.

Conclusion of Chapter 5

  • Review of significant aspects of CPU scheduling methodologies in modern operating systems including practical examples and theoretical frameworks.