Scheduling

Introduction

Scheduling: mechanism for allocating CPU and resources among competing processes. Goal: maximize utilization, throughput, minimize latency. Operating systems use scheduling to manage multitasking and parallelism. Essential for responsiveness, fairness, and efficiency in computing systems.

"The scheduler is the heart of any multitasking operating system, deciding which process runs next." -- Abraham Silberschatz

Basic Concepts

Process and Thread

Process: program in execution, owns resources. Thread: lightweight process, shares resources. Scheduling manages both entities for CPU access.

CPU Burst Cycle

Processes alternate CPU bursts and I/O waits. Scheduling decisions often occur at CPU burst completion or preemption points.

Context Switch

Switching CPU from one process/thread to another. Overhead: saving/restoring state, cache effects. High frequency impacts performance negatively.

Scheduling Criteria

CPU Utilization

Percentage of time CPU is busy. Aim: keep near 100% without overloading.

Throughput

Number of processes completed per unit time. Higher throughput means more work done.

Turnaround Time

Time from submission to completion. Lower is better for user experience.

Waiting Time

Total time a process spends in ready queue. Minimizing improves responsiveness.

Response Time

Time from submission to first response. Critical for interactive systems.

Types of Scheduling

Long-Term Scheduling

Controls admission of processes into system. Balances load, controls degree of multiprogramming.

Mid-Term Scheduling

Swaps processes in/out of memory to control memory load and manage multiprogramming.

Short-Term Scheduling

Decides which ready process/thread runs next on CPU. Most frequent and critical scheduling.

CPU Scheduling Algorithms

First-Come, First-Served (FCFS)

Non-preemptive, runs processes in arrival order. Simple but can cause long waiting times (convoy effect).

Shortest Job Next (SJN)

Non-preemptive, selects process with shortest CPU burst. Minimizes average waiting time, requires burst time knowledge.

Shortest Remaining Time First (SRTF)

Preemptive version of SJN. Preempts running process if new arrival has shorter remaining time.

Round Robin (RR)

Preemptive, time quantum assigned. Processes rotate in ready queue. Good for time-sharing, guarantees response time.

Priority Scheduling

Processes assigned priority. Highest priority runs first. Can be preemptive or non-preemptive. Risk: starvation.

Preemptive vs Non-Preemptive

Preemptive Scheduling

CPU can be taken from running process. Enables responsiveness, supports real-time constraints.

Non-Preemptive Scheduling

Process runs to completion or blocks voluntarily. Simpler but less flexible, can cause poor response times.

Trade-offs

Preemptive: overhead, complexity. Non-preemptive: simplicity, possible poor utilization. Choice depends on system goals.

Real-Time Scheduling

Hard Real-Time

Strict deadlines. Missing deadline causes system failure. Requires deterministic scheduling.

Soft Real-Time

Deadlines important but not critical. Occasional misses acceptable.

Algorithms

Rate Monotonic Scheduling (RMS): fixed priority based on period. Earliest Deadline First (EDF): dynamic priority based on deadlines.

Multilevel Queue Scheduling

Queue Structure

Processes partitioned into queues by type/priority (e.g., foreground, batch). Each queue has own scheduling.

Scheduling Among Queues

Fixed priority between queues. Higher priority queues served first, lower queues starve.

Use Cases

Separates interactive and batch processes, enforces priority policies.

Multilevel Feedback Queue

Dynamic Priority

Processes move between queues based on behavior and aging. Penalizes CPU-heavy, favors I/O-bound.

Aging Mechanism

Prevents starvation by gradually increasing priority of waiting processes.

Complexity

Adaptive, responsive but complex to implement and tune.

Thread Scheduling

User-Level Threads

Managed by user libraries, OS unaware. Fast context switch, but blocking system calls block all threads.

Kernel-Level Threads

Managed by OS scheduler. Supports true concurrency, higher overhead.

Hybrid Approaches

Combine user and kernel threads to balance performance and concurrency.

Performance Evaluation

Metrics

Throughput, turnaround time, waiting time, response time, CPU utilization.

Analytical Modeling

Queueing theory, Markov chains used for predicting scheduler behavior.

Simulation

Discrete-event simulations model complex workloads and scheduling impacts.

Scheduling Issues

Starvation

Low priority processes never scheduled. Mitigation: aging or priority adjustment.

Deadlock

Processes wait indefinitely for resources. Scheduling must consider resource allocation to avoid.

Load Balancing

Distributing workload evenly across CPUs/cores. Critical in multiprocessor systems.

Fairness

Ensuring equitable CPU time distribution. Balances throughput and response times.

Algorithm Aging:while(process in ready queue) { wait_time += 1; priority = base_priority + (aging_factor * wait_time); if(priority > max_priority) priority = max_priority;}

References

• Silberschatz, A., Galvin, P. B., & Gagne, G., Operating System Concepts, 9th Ed., Wiley, 2013, pp. 120-180.
• Tanenbaum, A. S., Modern Operating Systems, 4th Ed., Pearson, 2014, pp. 200-250.
• Stallings, W., Operating Systems: Internals and Design Principles, 9th Ed., Pearson, 2017, pp. 300-360.
• Buttazzo, G. C., Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Springer, 2011, pp. 50-110.
• Leung, J. Y.-T., "A Review of Scheduling Theory," European Journal of Operational Research, vol. 78, 1994, pp. 1-21.