N

CPU Scheduling Review

Chapter 5: CPU Scheduling

Table of Contents

  • Process States

  • Scheduling Metrics/Criteria

  • CPU Scheduling Algorithms

    • First Come First Served (FCFS)

    • Shortest Job First (SJF)

    • Priority

    • Round Robin (RR)

    • Multi-Level Queue

    • Multi-Level Feedback Queue

Process States

Overview

  • The scheduler maintains the status of each process that has been created but not yet completed.

Process States

  1. New: The process has been created but not yet in memory.

  2. Ready: The process is in memory and waiting to be assigned a CPU by the scheduler.

  3. Running: The process is currently being executed by a CPU.

  4. Blocked: The process is waiting for some event to occur (e.g., I/O operation to complete, lock to be acquired, or timer to expire).

  5. Terminated: The process has completed its execution.

Process State Transitions

  1. New → Ready: The operating system has allocated resources to the process, including memory, so that it can be executed.

  2. Ready → Running: The process has been selected for execution by the scheduler.

  3. Running → Blocked: The process has invoked a blocking operation.

  4. Running → Ready: The scheduler has taken away the CPU from the process.

  5. Running → Terminated: The process finished its execution.

  6. Blocked → Ready: The event that the process was waiting for has occurred.

Process State Diagram

![Process State Diagram]

  • States: New, Ready, Running, Blocked, Terminated

  • Transitions: Admitted, Scheduler dispatch, Interrupt, Exit, I/O wait, I/O completion

Additional Process States

  • Some schedulers may maintain additional states:

  1. Suspended (Ready): The process is not in memory and not waiting for any event to occur.

  2. Suspended (Blocked): The process is not in memory and is waiting for some event to occur.

Additional Transitions

  1. Ready → Suspended (Ready): The scheduler has moved the process image (currently ready) from memory to secondary storage.

  2. Suspended (Ready) → Ready: The scheduler has moved the process image (currently ready) from secondary storage to memory.

  3. Blocked → Suspended (Blocked): The scheduler has moved the process image (currently blocked) from memory to secondary storage.

  4. Suspended (Blocked) → Blocked: The scheduler has moved the process image (currently blocked) from secondary storage to memory.

  5. Suspended (Blocked) → Suspended (Ready): The event that the process was waiting for has occurred.

Augmented Process State Diagram

  • Diagram includes additional states and transitions between processes.

Scheduler Components

  1. Long Term Scheduler: Decides which newly created processes should be admitted for execution.

  2. Medium Term Scheduler: Temporarily removes some processes from main memory and places them in secondary memory/storage (e.g., hard disk), or vice versa.

  3. Short Term Scheduler: Decides which process in memory should be assigned the CPU. Also known as CPU Scheduler.

  • Note: Long-term and medium-term schedulers control the degree of multiprogramming.

  • Dispatcher: The OS module that gives control of the CPU to the process selected by the short-term scheduler.

Context Switch

  • Context Switch: The process of changing the execution context on a CPU from one process to another, involving:

    • Saving the execution context of the process previously assigned the CPU.

    • Loading the execution context of the process next assigned the CPU.

  • Dispatch Latency: The amount of time it takes for the OS to stop (suspend) one process and start (resume) another.

Execution Context

  • Components include:

    • Special and general purpose CPU registers.

    • Logical address translation data (TLB, Page Tables).

    • Cache contents for hiding memory latency.

    • Contents of the registers are saved in the PCB (process control block).

    • May require flushing TLBs and caches depending on architecture.

Context Switch vs. Mode Switch

  • Mode Switch: Involves changing the execution mode of the CPU (user to kernel or vice versa), often saving only a subset of registers, and does not require flushing logical address translation or cache.

  • Context switch is generally more expensive than mode switch, typically preceded and succeeded by a mode switch.

Scheduler Components Variability

  • Not all operating systems have all three components of scheduling. Short-term schedulers and dispatchers should be fast and incur minimal overhead since they are invoked more frequently than the other two.

Scheduling Metrics/Criteria

Metrics for CPU Scheduling

  • Many different CPU scheduling algorithms have been proposed, suited for various scenarios, including batch computing, interactive computing, or real-time computing.

Commonly Used Metrics

  1. CPU Utilization: The percentage of time the CPU is busy.

  2. Turnaround Time: Amount of time elapsed between when a process arrives and when it completes its execution.

  3. System Throughput: Number of processes completed per unit time.

  4. Waiting Time: Sum of time spent in the ready queue during the life of the process (blocked time is not included).

  5. Response Time: Time between when a user submits a request and receives a response.

  6. Fairness: Each process (or user) should get an equitable share of the CPU.

Illustrations of CPU Scheduling

  • Interactive scenarios exploring turnaround and waiting times with Gantt charts.

  • Comparisons of different scenarios demonstrating performance differences.

CPU Scheduling Algorithms

CPU Scheduler Overview

  • Responsible for selecting which ready process to run with two types of schedulers:

  1. Non-Preemptive Scheduler: Selects the next process when the running one no longer requires the CPU.

    • Vulnerable to starvation if the running process never invokes a blocking operation.

  2. Preemptive Scheduler: Can interrupt a running process and assign the CPU to another process.

    • Can be triggered by events or time limits.

CPU Scheduling Algorithms Descriptions
First Come First Served (FCFS)

  • Processes are executed in the order they arrive (non-preemptive).

  • Pros and Cons analysis identifying its simplicity and starvation-free under certain conditions, but poor performance in turnaround time, response time, etc.

  • Illustrated with examples and calculated turnaround times.

Shortest Job First (SJF)

  • Processes executed in increasing order of CPU burst time (both non-preemptive and preemptive variants known as Shortest Remaining Time First (SRTF)).

  • Provides optimal mean waiting time but requires prior knowledge of CPU usage and is vulnerable to starvation in infinite arrival scenarios.

  • Illustrated with examples and optimality proofs using sorted schedules.

Priority Scheduling

  • Order of execution defined by process priority (higher values executed before lower).

  • Can be non-preemptive or preemptive, needing a mechanism for handling starvation via aging.

  • Illustrated with examples for both variants.

Round Robin (RR)

  • Processes have a time quantum during which they can run before being preempted and switched with another.

  • Analyzed for both time quantum impacts and performance in terms of response times.

Multi-Level Queue

  • Implements multiple queues for ready processes assigned based on type or priority.

  • Each queue uses its scheduling algorithm with rules for inter-queue scheduling.

Multi-Level Feedback Queue

  • Combines multiple queues with promotion and demotion capabilities for processes based on their behaviors (e.g., CPU usage and waiting times).

  • Widely used in modern operating systems.

Conclusion

  • Discussion emphasizes the importance of selecting appropriate scheduling algorithms based on the system type and process requirements to optimize performance and resource utilization.