Process Scheduling

Process scheduling is a core function of operating system kernels. It determines which process runs on the CPU at any given time, managing CPU allocation fairly and efficiently among multiple competing processes.

Scheduling Metrics

Turnaround Time

Time from when a job is submitted until it completes.

• Formula: Turnaround Time = Completion Time - Arrival Time
• Measures total time a job spends in the system
• Includes both waiting and execution time
• Lower is better (less time job sits around)

Response Time

Time from when a job arrives until it first starts running.

• Formula: Response Time = First Run Time - Arrival Time
• Critical for interactive systems (user perceives responsiveness)
• Different from turnaround time (only measures wait before first run)
• Lower is better (immediate feedback to user)

Other Key Metrics

• Waiting Time: Time spent waiting in ready queue (not running)
• CPU Utilization: Percentage of time CPU is actively executing processes
• Throughput: Number of processes completed per unit time

Scheduling Algorithms

FIFO (First In, First Out)

Description: Processes are executed in the order they arrive. The first process to arrive runs to completion before the next process starts.

Characteristics:

• Non-preemptive (once a process starts, it runs until completion)
• Simple to implement
• No starvation (all processes eventually run)
• Fair in theory (processes run in order of arrival)

Pros:

• Very simple algorithm
• No context switching overhead
• Predictable behavior

Cons:

• Convoy Effect: One long process blocks all others
• Poor response time for interactive applications
• Doesn’t account for job length
• Not optimal for mixed workloads

Example:

Jobs: A(10ms), B(5ms), C(3ms) arrive at t=0

Timeline:
[----A (10ms)----][--B (5ms)--][C (3ms)]
0                 10          15       18

Turnaround Times:
- A: 10ms
- B: 15ms  
- C: 18ms
Average: 14.33ms

Response Times:
- A: 0ms (starts immediately)
- B: 10ms (waits for A)
- C: 15ms (waits for A, B)
Average: 8.33ms

SJF (Shortest Job First)

Description: Process with the shortest burst time (CPU time needed) runs first. Minimizes average waiting time.

Characteristics:

• Non-preemptive (process runs to completion)
• Optimal for minimizing average turnaround time
• Requires knowing job length in advance (not always available)
• Can cause starvation of long jobs

Pros:

• Minimizes average turnaround time (provably optimal)
• Better than FIFO for mixed workloads
• Good average waiting time

Cons:

• Long jobs can starve (convoy effect still exists)
• Requires prior knowledge of job length
• Poor response time (long job must complete before others run)
• Unpredictable (user doesn’t know when short job will run)

Example:

Jobs: A(10ms), B(5ms), C(3ms) arrive at t=0

Timeline (sorted by length):
[C (3ms)][--B (5ms)--][----A (10ms)----]
0       3           8                  18

Turnaround Times:
- C: 3ms
- B: 8ms
- A: 18ms
Average: 9.67ms (better than FIFO!)

Response Times:
- C: 0ms
- B: 3ms
- A: 8ms
Average: 3.67ms

STCF (Shortest Time to Completion First)

Description: Preemptive version of SJF. The process with the shortest remaining time is always run. When a new job arrives, if it has less remaining time than the current job, the current job is preempted.

Characteristics:

• Preemptive (can pause a running process)
• Optimal for minimizing average turnaround time
• Also called Preemptive Shortest Job First (PSJF)
• Requires knowing remaining job length

Pros:

• Optimal average turnaround time
• Better than SJF for varying arrival times
• Responsive to new short jobs
• Improves over SJF significantly with staggered arrivals

Cons:

• Long jobs can still starve
• Requires knowing/estimating job length
• Poor response time for long jobs
• Context switching overhead
• Not fair (long jobs get less CPU time)

Example:

Jobs: A(8ms), B(4ms), C(2ms)
- A arrives at t=0
- B arrives at t=1  
- C arrives at t=2

Timeline:
[A(1ms)][C(2ms)][B(3ms)][A(2ms)]
0      1       3      6       8

Detailed:
t=0: A starts (remaining: 8ms)
t=1: B arrives (remaining: 4ms < 8ms) → preempt A, run B
t=2: C arrives (remaining: 2ms < 4ms) → preempt B, run C
t=4: C completes, run B (remaining: 3ms)
t=6: B completes, run A (remaining: 7ms)
t=8: A completes

Turnaround Times:
- A: 8ms (arrives at 0, completes at 8)
- B: 5ms (arrives at 1, completes at 6)
- C: 2ms (arrives at 2, completes at 4)
Average: 5ms

Round Robin (RR)

Description: Each process is assigned a fixed time slice (quantum/time slice) to run. Processes are placed in a queue and run in order for their time slice. If a process doesn’t complete within its time slice, it’s preempted and moved to the back of the queue.

Characteristics:

• Preemptive (every process gets equal CPU time)
• Fair (all processes get equal opportunity)
• No starvation (all processes eventually complete)
• Time slice/quantum determines fairness vs. context switching trade-off
• Works well for interactive systems

Pros:

• Fair CPU allocation
• Good response time (every process runs regularly)
• No starvation
• Works well for time-sharing systems
• Responsive to user input
• Predictable (known max wait time)

Cons:

• Context switching overhead increases with more processes
• If quantum too small: many context switches (overhead)
• If quantum too large: becomes like FIFO (poor response time)
• Worse average turnaround time than SJF/STCF
• Longer jobs get interrupted (cache pollution)

Example (Quantum = 3ms):

Jobs: A(8ms), B(4ms), C(2ms) arrive at t=0

Timeline:
[A:3][B:3][C:2][A:3][B:1]
0   3   6   8   11   14

Detailed:
t=0-3: A runs (remaining: 5ms) → back to queue
t=3-6: B runs (remaining: 1ms) → back to queue
t=6-8: C runs (remaining: 0ms) → done
t=8-11: A runs (remaining: 2ms) → back to queue
t=11-14: B runs (remaining: -1ms, done at 13)
t=13-15: A runs (remaining: -1ms, done at 15)

Turnaround Times:
- A: 15ms
- B: 13ms
- C: 8ms
Average: 12ms (worse than SJF/STCF but fair)

Response Times:
- A: 0ms (starts immediately)
- B: 3ms (waits 1 quantum)
- C: 6ms (waits 2 quanta)
Average: 3ms (good responsiveness)

Lottery Scheduling

Description: A probabilistic scheduling algorithm where each process is allocated lottery tickets. The scheduler randomly draws a ticket and runs the process holding that ticket. Processes get CPU time proportionally to the number of tickets they hold.

Characteristics:

• Preemptive (process runs for a time slice then is preempted)
• Probabilistic fairness (not guaranteed, but statistically fair over time)
• No starvation (every process has at least one ticket)
• Simple implementation (just a random number generator)
• Highly flexible and extensible

Pros:

• Proportional resource allocation (tickets control CPU share)
• Responsive to priority changes (can adjust tickets dynamically)
• No starvation (everyone gets at least one ticket)
• Simple to understand and implement
• Excellent for multi-resource scheduling (extend with tickets for I/O, memory)
• Good for fairness without complex data structures
• Minimal overhead (O(1) selection with good RNG)
• Works well in distributed systems

Cons:

• Not perfectly fair (short term variation due to randomness)
• Can take time to converge to fair allocation (statistical fairness)
• Doesn’t minimize turnaround time like SJF/STCF
• Poor worst-case response time for low-ticket processes
• Random behavior may be undesirable for deterministic systems
• Ticket management can become complex in large systems

Example:

Three processes with tickets:
- Process A: 50 tickets
- Process B: 30 tickets
- Process C: 20 tickets
Total: 100 tickets

Probability each is selected:
- A: 50% chance (runs roughly half the time)
- B: 30% chance (runs roughly 30% of time)
- C: 20% chance (runs roughly 20% of time)

Quantum = 10ms, 1000ms total time:

Possible random draws (10 draws total):
Draw 1: Random 37 → A runs (10ms elapsed)
Draw 2: Random 15 → B runs (20ms elapsed)
Draw 3: Random 62 → A runs (30ms elapsed)
Draw 4: Random 88 → A runs (40ms elapsed)
Draw 5: Random 41 → A runs (50ms elapsed)
Draw 6: Random 12 → B runs (60ms elapsed)
Draw 7: Random 95 → A runs (70ms elapsed)
Draw 8: Random 73 → A runs (80ms elapsed)
Draw 9: Random 27 → B runs (90ms elapsed)
Draw 10: Random 18 → C runs (100ms elapsed)

Result after 100ms:
- A: 70ms (expected: 50ms, got 40% more due to randomness)
- B: 30ms (expected: 30ms, perfect!)
- C: 10ms (expected: 20ms, got 50% less due to randomness)

Over longer period (1000ms), proportions converge to expected values.

Ticket Mechanisms

Transfer: Process can temporarily transfer tickets to another process

transfer(from_pid, to_pid, num_tickets);

Useful for client-server applications where client gives tickets to server.

Inflation: Process temporarily increases its own ticket count

inflate_tickets(pid, multiplier);  // 1.5x tickets temporarily

Risky: requires mutual trust, can break fairness if abused.

Compensation Tickets: Process receives bonus tickets based on I/O wait

If process blocks for I/O:
- Give back unused CPU time at end of quantum
- Or give bonus tickets for next scheduling opportunity
- Compensates for I/O latency

Comparison to Round Robin

Real-World Usage

• Not commonly used as primary OS scheduler (OSes prefer deterministic fairness)
• Used in specialized systems and research (Lottery scheduler papers)
• Useful for resource management in distributed systems
• Good model for proportional fair queueing (networking)
• Similar to weighted fair queueing (WFQ) in network schedulers

Stride Scheduling (Related Algorithm)

A deterministic variant of lottery scheduling:

• Each process has a stride (inverse of priority/tickets)
• Each process has a pass value (accumulated stride)
• Always pick process with smallest pass value (like CFS vruntime)
• Increment that process’s pass by its stride
• Result: Deterministic fairness without randomness
• Trade-off: More complex than lottery, simpler than CFS

Stride = LARGE_NUMBER / num_tickets

Process A (50 tickets): stride = 200
Process B (30 tickets): stride = 333
Process C (20 tickets): stride = 500

Initial: All pass = 0

1. Pick A (smallest pass=0), run, increment pass: 0+200=200
2. Pick B (pass=0), run, increment pass: 0+333=333
3. Pick C (pass=0), run, increment pass: 0+500=500
4. Pick A (pass=200), run, increment pass: 200+200=400
5. Pick B (pass=333), run, increment pass: 333+333=666
6. Pick A (pass=400), run, increment pass: 400+200=600

Result: A,B,C,A,B,A scheduling order
A runs 50%, B runs 33%, C runs 17% (exactly fair!)

Algorithm Comparison

Choosing a Scheduling Algorithm

For Batch Systems (long-running background jobs):

• Use STCF or SJF for optimal turnaround time
• Minimize response time requirement

For Interactive Systems (user-facing applications):

• Use Round Robin with appropriate quantum
• Prioritize response time over turnaround time
• Balance quantum size: too small = overhead, too large = lag

For Real-time Systems (strict deadlines):

• Need priority-based scheduling
• Often use Earliest Deadline First (EDF)
• Combined with Round Robin or priority queues

For Modern Systems (typical servers/desktops):

• Hybrid approach: priority-based Round Robin
• Different priority levels
• Different quantum sizes per priority
• Example: Linux Completely Fair Scheduler (CFS)

Real-World Considerations

Context Switching Cost

• Saving/restoring process state
• TLB flushes (if address space changes)
• Cache misses (warm cache lost)
• Can be significant with frequent preemption

Process Estimation

• SJF/STCF require knowing job length
• Can estimate from historical data
• Hard to predict for new workloads
• Can use adaptive techniques

Priority

• Most systems use priority-based scheduling
• High priority process runs before low priority
• Can starve low priority processes
• Solution: aging (increase priority over time)

Multi-CPU Scheduling

• Single queue: contention on lock
• Per-CPU queues: load balancing issues
• Affinity: keep process on same CPU (cache locality)
• Complex in modern systems

Linux Process Scheduling Implementation

Process/Thread States

Every process/thread in Linux goes through various states throughout its lifetime. The KSE (Kernel Scheduling Entity) on a Linux system is the thread. Each thread has its own state, represented by flags in the task_struct structure.

Thread States

• TASK_RUNNING: Thread is either running on CPU or ready to run. Thread is in a run queue (one per core).
• TASK_INTERRUPTIBLE: Thread is sleeping and can be woken up by signals. Threads waiting are put in wait queues.
• TASK_UNINTERRUPTIBLE: Thread is sleeping and cannot be woken up by signals (blocking I/O, futex operations).
• TASK_STOPPED: Thread has been stopped, usually by a signal (SIGSTOP, SIGTSTP).
• TASK_TRACED: Thread is being traced by another process (e.g., a debugger).
• EXIT_ZOMBIE: Thread has finished execution but still has entry in process table. Parent must call wait() to reap it.
• EXIT_DEAD: Thread has been completely removed from process table.

Linux Process State Machine

                    +--------------------+
                    |      CREATED       |
                    |  (new task_struct) |
                    +---------+----------+
                              |
                              v
                   +----------+----------+
                   |      READY          |
                   | (runnable, in runq) |
                   +----------+----------+
                              |
                              | scheduled by CPU
                              v
                   +----------+----------+
                   |      RUNNING        |
                   +----------+----------+
                              |
        +---------------------+-----+---------------------+
        |                           |                       |
        | voluntary sleep           | preemption            |
        v                           v                       |
+-------+--------+        +---------+---------+              |
| INTERRUPTIBLE  | <----- |     READY         | <-----------+
|   SLEEP (S)    |        | (runnable again)  |
+-------+--------+        +-------------------+
        |
        | syscall waits (I/O, futex, etc.)
        v
+-------+--------+
|UNINTERRUPTIBLE|
|   SLEEP (D)    |
+-------+--------+
        |
        | I/O completes / futex satisfied
        v
+-------+--------+
|      READY     |
+-------+--------+

(signals)
        |
        v
+-------+--------+
|     STOPPED    |
|  (T state)    |
+-------+--------+
        |
        | SIGCONT
        v
+-------+--------+
|      READY     |
+-------+--------+

When process calls exit():
        |
        v
+-------+--------+
|      ZOMBIE    |
|   (defunct)    |
+-------+--------+
        |
        | parent calls wait()
        v
+-------+--------+
|     REAPED     |
|  (freed)       |
+-------+--------+

Linux Scheduling Policies

Linux supports several scheduling policies that determine how threads are prioritized and scheduled:

SCHED_OTHER (Default, CFS)

• Time-sharing policy for regular threads
• Uses the Completely Fair Scheduler (CFS)
• Default for most user-space applications
• Threads can be preempted at any time
• Fairly allocates CPU time based on priority (nice value)

SCHED_FIFO (Real-time, FIFO)

• First-in, first-out real-time scheduling
• Higher priority than SCHED_OTHER
• Requires CAP_SYS_NICE capability
• Thread runs until it:
  • Blocks on I/O
  • Stops or dies
  • Higher priority real-time thread becomes runnable
• No time slice (runs indefinitely until one of above happens)
• Risk: Can starve system if high-priority thread loops infinitely

SCHED_RR (Real-time, Round-Robin)

• Round-robin real-time scheduling
• Similar to SCHED_FIFO but with time slice
• Typical time slice: 100ms
• Thread yields back CPU when:
  • Time slice expires
  • Blocks on I/O
  • Stops or dies
  • Higher priority real-time thread becomes runnable

SCHED_BATCH

• Suitable for low-priority, non-interactive batch jobs
• Less frequent preemption than SCHED_OTHER
• Reduces context switching for throughput-oriented workloads

SCHED_IDLE

• Lowest priority background tasks
• Only runs when system is idle
• Good for background maintenance tasks

Completely Fair Scheduler (CFS)

The CFS is the default scheduling algorithm for SCHED_OTHER threads in modern Linux kernels.

Design Goals

• Allocate CPU time fairly among all runnable threads
• Each thread gets proportional share of CPU based on its weight (priority)
• Provide good response time for interactive applications
• Maintain high CPU utilization for system throughput

Implementation Details

Virtual Runtime (vruntime)

• Each thread tracks a virtual runtime representing CPU time received
• Lower vruntime = less CPU time received = runs next
• Adjusted based on priority: higher priority threads’ vruntime advances slower

Red-Black Tree Data Structure

• Maintains runnable threads in a red-black tree (balanced binary search tree)
• Sorted by vruntime
• Leftmost node (smallest vruntime) is next thread to run
• O(log n) insertion, deletion, and selection
• Efficient for large numbers of threads

Selection Algorithm

1. Always pick leftmost node (smallest vruntime) to run
2. When thread runs, its vruntime increases by actual time spent
3. Thread is reinserted in tree with updated vruntime
4. High-priority threads’ vruntime increases slower (or more slowly)
5. Result: Low-priority threads advance in tree, eventually get selected

Priority/Weight

• Threads have a priority (nice value: -20 to +19)
• Nice value converted to weight
• Lower nice value (higher priority) → weight increases → vruntime advances slower
• Thread gets more CPU time with lower (higher priority) nice value

Time Slice (Scheduling Period) - sched_latency

• sched_latency: Target scheduling latency (target time to schedule all runnable tasks once)
• Default: 6ms (tunable via /proc/sys/kernel/sched_latency_ns)
• On single core: each of N threads gets ~6ms/N time slice
• Represents desired responsiveness of system
• Trade-off:
  • Larger latency = longer time slices = fewer context switches = less overhead
  • Smaller latency = shorter time slices = more responsive = more overhead

Minimum Granularity - min_granularity

• min_granularity: Minimum time slice a task should get
• Default: 0.75ms (tunable via /proc/sys/kernel/sched_min_granularity_ns)
• Ensures tasks always get at least this much time (even with many threads)
• Prevents excessive context switching overhead
• If N tasks × min_granularity > sched_latency, then:
  • Scheduling period becomes N × min_granularity
  • Each task gets min_granularity time
  • Latency target is exceeded (acceptable trade-off for efficiency)

vruntime Calculation

• Actual runtime = wall-clock time the task ran
• Weight = priority weight based on nice value
• vruntime_delta = (actual_time * NICE_0_LOAD) / task_weight
• Higher priority (lower nice) task has higher weight → vruntime advances slower
• Lower priority (higher nice) task has lower weight → vruntime advances faster

Preemption Decision

• After each task runs for its time slice, scheduler checks if preemption needed
• Preemption occurs when: se->vruntime > cfs_rq->min_vruntime + sched_latency
  • se->vruntime: current task’s virtual runtime
  • cfs_rq->min_vruntime: minimum vruntime in run queue
  • sched_latency: scheduling latency target
• If current task’s vruntime exceeds min_vruntime by more than sched_latency, it’s preempted
• Next task selected is leftmost in tree (minimum vruntime)

Example CFS Behavior with sched_latency

Three threads with equal priority (nice=0, weight=1024):
sched_latency = 6ms, min_granularity = 0.75ms
Expected time slice per thread: 6ms / 3 = 2ms

Timeline:
t=0ms:    min_vruntime=0
          Select A (vruntime=0, leftmost)
          
t=2ms:    A ran for 2ms, A->vruntime += 2
          A->vruntime = 2, min_vruntime = 0
          Check preemption: 2 > 0 + 6? No (2 ≤ 6), continue? 
          Actually: select next = B, but A can continue if time allows
          A inserted at vruntime=2
          min_vruntime still 0 (B,C at 0)
          B becomes leftmost
          Select B
          
t=4ms:    B ran for 2ms, B->vruntime = 2
          Min thread (C) has vruntime=0
          B inserted at vruntime=2
          Select C
          
t=6ms:    C ran for 2ms, C->vruntime = 2
          All threads now have vruntime=2
          min_vruntime = 2
          Select A (leftmost at vruntime=2)
          
t=8ms:    A runs 2ms more, A->vruntime = 4
          All at 2, A at 4
          Min is 2 (B,C)
          Select B

Result: Perfect round-robin, each gets 2ms per cycle
        sched_latency = 6ms = 3 tasks × 2ms (exactly met)

Example with Many Tasks (hitting min_granularity)

10 threads, same nice value
sched_latency = 6ms, min_granularity = 0.75ms
Ideal time slice: 6ms / 10 = 0.6ms
Problem: 0.6ms < min_granularity (0.75ms)
Solution: Use min_granularity instead
Actual time slice: 0.75ms per thread
Actual scheduling period: 10 × 0.75ms = 7.5ms (exceeds sched_latency)

This is acceptable because:
- Prevents excessive context switching overhead
- Latency still reasonable for typical workloads
- Context switch cost would dominate if time slices too small

CFS Tuning Parameters

/proc/sys/kernel/sched_latency_ns

# View current value (in nanoseconds)
cat /proc/sys/kernel/sched_latency_ns
# Output: 24000000 (24ms default on many systems)

# Increase for systems with many tasks / higher throughput focus
echo 48000000 > /proc/sys/kernel/sched_latency_ns  # 48ms

# Decrease for interactive systems / lower latency focus
echo 6000000 > /proc/sys/kernel/sched_latency_ns   # 6ms

# Effect of increasing:
# - Longer time slices per task
# - Fewer context switches
# - Less responsive to user input
# - Better throughput for batch jobs

/proc/sys/kernel/sched_min_granularity_ns

# View current value
cat /proc/sys/kernel/sched_min_granularity_ns
# Output: 3000000 (3ms default on many systems)

# Increase to reduce context switching
echo 5000000 > /proc/sys/kernel/sched_min_granularity_ns

# Decrease for more responsive systems (more context switches)
echo 1000000 > /proc/sys/kernel/sched_min_granularity_ns

# Effect of decreasing:
# - More context switches (more overhead)
# - Better fairness with many threads
# - More responsive (shorter time per task)

/proc/sys/kernel/sched_wakeup_granularity_ns

# How much vruntime advantage a waking task gets
# Default: ~0.5ms - 1.5ms

# Smaller value: newly woken tasks run sooner (better for client-server)
# Larger value: avoid waking up sleeping task unless necessary benefit

# Typical scenario: network packet arrives, wake application task
# Wakeup granularity determines if wake task displaces running task

vruntime Weight Mapping

Nice Value → Weight mapping (approximate)
nice -20:  88761   (1.25× previous level)
nice -10:  9548
nice   0:  1024    (reference point)
nice +10:  110
nice +20:  15

Example: Two threads, one at nice=-5 (weight≈3121), one at nice=+5 (weight≈335)

If both run for 1 second:
Thread 1 (higher priority): vruntime += 1000 × 1024 / 3121 ≈ 328
Thread 2 (lower priority):  vruntime += 1000 × 1024 / 335  ≈ 3055

Thread 2's vruntime advances ~9.3× faster
Thread 1 gets ~90% of CPU, Thread 2 gets ~10% (weight ratio: 3121/335 ≈ 9.3)

CFS Advantages

• Fairness: All threads get proportional CPU time
• Responsiveness: No fixed time slice, adapts to workload
• Scalability: O(log n) tree operations
• Starvation-free: All threads eventually get CPU time
• Good cache locality: Threads tend to run on same CPU

Setting Process Priority

Nice Value (for SCHED_OTHER)

# Set priority when starting process
nice -n 10 ./my_process    # Lower priority (higher nice value)
nice -n -10 ./my_process   # Higher priority (lower nice value, needs root)

# Change priority of running process
renice -n 5 -p PID         # Increase nice value (lower priority)
renice -n -5 -p PID        # Decrease nice value (higher priority)

Real-time Priority (for SCHED_FIFO/SCHED_RR)

# Set real-time policy and priority
chrt -f 50 ./my_process    # FIFO with priority 50 (1-99 range)
chrt -r 50 ./my_process    # Round-robin with priority 50

# Change running process
chrt -f -p 50 PID          # Change to FIFO priority 50

Process Creation and Scheduling

Once a thread is created via fork(), clone(), or pthread_create(), it informs the scheduler that it’s ready for execution:

1. New task_struct allocated and initialized
2. Thread state set to TASK_RUNNING
3. Added to run queue
4. CFS: inserted into red-black tree at appropriate vruntime position
5. Scheduler can select it on next scheduling opportunity
6. Thread runs until preempted or blocks

Load Balancing

On multi-core systems, Linux must distribute load across CPUs:

• Per-CPU Run Queues: Each core has its own red-black tree to reduce lock contention
• Load Balancing: Periodic migration of threads between queues to balance load
• CPU Affinity: Attempt to keep threads on same CPU for cache locality
• Domain Hierarchy: Balancing happens at multiple levels (core, cache domain, NUMA node)