Scheduling Algorithms Overview

Scheduling Algorithm Optimization Criteria

• Maximize CPU utilization
• Maximize throughput
• Minimize turnaround time
• Minimize waiting time
• Minimize response time

First-Come, First-Served (FCFS) Scheduling

• The first process that enters the ready queue is the first process that gets scheduled
• Scheduling processes based on the order they arrive
• FCFS can lead to the convoy effect, where a short process gets stuck behind a long process

Shortest-Job-First (SJF) Scheduling

• Schedules the job with the shortest burst time first
• Can be preemptive, known as shortest-remaining-time-first
• The length of the next CPU burst is used to determine the priority

Round-Robin Scheduling

• Each process is allocated a time quantum, and the CPU cycles through the processes
• When a time quantum is exhausted, the process is put back in the queue and the next job is scheduled
• Time quantum should be significantly larger than the context switch time
• The time quantum can affect the average turnaround time and response time
• If time quantum is too small, the system will be bogged down by context switching

Priority Scheduling

• Each process is assigned a priority number
• The process with the highest priority gets scheduled (smaller number is higher priority)
• Can be preemptive or non-preemptive
• Problem: Starvation, a low-priority process may never get scheduled
• Solution: Aging - incrementally increase a process's priority over time

Multilevel Feedback Queue

• Multiple queues with different scheduling algorithms
• A process can move between queues based on its behavior
• Aging can be implemented using multilevel feedback queues

Thread Scheduling

• Distinction between user-level and kernel-level threads
• Threads are scheduled instead of processes
• There are numerous models for scheduling, such as many-to-one and many-to-many
• Process-contention scope (PCS) is when threads within one process compete for the CPU
• System-contention scope (SCS) is when threads across all processes compete for the CPU

Pthread Scheduling

• Pthreads allows specifying either PCS or SCS during thread creation
• PTHREAD_SCOPE_PROCESS schedules threads using PCS
• PTHREAD_SCOPE_SYSTEM schedules threads using SCS
• Some OSes may limit the scheduling scope

Multiple-Processor Scheduling

• More complex when multiple CPUs are available
• Must consider:
  • Multicore CPUs
  • Multithreaded cores
  • NUMA systems
  • Heterogeneous multiprocessing

Load Balancing

• The goal is to keep all CPUs equally loaded for efficiency
• Push migration - moves a task from an overloaded CPU to a less loaded CPU
• Pull migration - an idle CPU pulls a waiting task from a busy CPU

Processor Affinity

• When a thread runs on a specific CPU, it caches memory accesses
• Load balancing may disrupt this affinity
• Soft affinity - the OS tries to keep a thread on the same CPU, but no guarantees
• Hard affinity - the process defines a set of CPUs it can run on

NUMA and CPU Scheduling

• If the OS is NUMA-aware, it assigns memory to the CPU nearest to the running thread

Real-Time CPU Scheduling

• Scheduling can be very challenging
• Soft real-time systems - critical tasks get the highest priority, but execution is not guaranteed
• Hard real-time systems - tasks must meet their deadlines
• Event Latency - the time between an event occurring and when it is serviced

Deterministic Modeling

• Analytic evaluation
• Based on a predetermined workload, calculates the performance of each scheduling algorithm
• Simple and fast, but specific to the input parameters

Queuing Models

• Describe the arrival of processes and their bursts probabilistically
• Used to calculate average throughput, utilization, waiting time, etc.

Explore various scheduling algorithms used in operating systems, such as First-Come, First-Served, Shortest-Job-First, and Round-Robin. Understand the optimization criteria that enhance CPU utilization and minimize wait times. This quiz will test your knowledge of process scheduling methods and their implications.