Processor Scheduling

Processor Scheduling

Basic Concepts

What Gets Scheduled

Process scheduling: in a multiprogramming system, pick one process from the ready queue and give it the CPU.

Thread scheduling: in a multithreaded system, pick one thread from the ready threads and give it the CPU.

When Scheduling Happens

1. A process finishes: the running process completes its execution
2. The time slice expires: the quantum runs out in a time-sharing system
3. A process blocks: the process waits for I/O or another resource
4. A higher-priority process becomes ready: a higher-priority process arrives under preemptive scheduling
5. A process gives up the CPU voluntarily: the process calls something like yield()

Switching Between Schedules

Context switch: when moving from one process to another, the state of the current process must be saved and the state of the new process must be restored.

Cost of the switch:

• Saving and restoring registers
• Updating the memory management unit (MMU)
• Flushing the cache
• Updating kernel data structures

Scheduling Criteria

User-Oriented Criteria

1. Turnaround time: the time from submission of a process to its completion

   • Turnaround time = Completion time - Submission time
   • Average turnaround time = Sum of turnaround times / Number of processes

2. Response time: the time from a user request until the system responds

   • Response time = Time of first CPU service - Submission time

3. Waiting time: the total time a process spends waiting in the ready queue

   • Waiting time = Turnaround time - Burst time

4. Deadline: the time by which a process must be completed in a real-time system

System-Oriented Criteria

1. CPU utilization: the percentage of time the CPU is busy

   • CPU utilization = CPU busy time / Total time

2. Throughput: the number of processes completed per unit of time

   • Throughput = Number of completed processes / Total time

3. Fairness: every process should get a fair chance at the CPU

4. Predictability: the behavior of the scheduling algorithm should be predictable

Scheduling Approaches

Non-Preemptive Scheduling

Characteristics:

• Once a process has the CPU, it runs until it finishes or blocks
• The scheduling decision is simple
• Response time is unpredictable

Suitable for:

• Batch systems
• Systems with modest real-time requirements

Preemptive Scheduling

Characteristics:

• A running process may be preempted by another process
• Response time is short
• The scheduling decision is complex

Suitable for:

• Time-sharing systems
• Real-time systems
• Interactive systems

Typical Scheduling Algorithms

1. First Come, First Served (FCFS)

Algorithm:

• Schedule processes in the order in which they arrive in the ready queue
• A non-preemptive scheduling algorithm

Characteristics:

• Simple to implement
• Fair in appearance
• Long average waiting time
• Unfavourable to short processes

Example:

2. Shortest Job First (SJF)

Algorithm:

• Always run the process with the shortest burst time
• Non-preemptive version: SJF
• Preemptive version: Shortest Remaining Time First (SRTF)

Characteristics:

• Shortest average turnaround time
• Unfair to long processes
• Requires the burst times of processes to be known in advance

Example:

3. Round Robin (RR)

Algorithm:

• Give every process a fixed time slice
• When a process uses up its slice, the CPU moves on to the next process
• A preemptive scheduling algorithm

Characteristics:

• Fair
• Short response time
• Performance depends heavily on the size of the time slice

Choosing a time slice:

• Too small: the context-switch overhead becomes large
• Too large: the algorithm degenerates into FCFS
• A common choice is 10-100ms

Example (time slice = 2):

4. Priority Scheduling

Algorithm:

• Assign a priority to every process
• Run the process with the highest priority
• It can be preemptive or non-preemptive

How priorities are determined:

• Static priority: fixed when the process is created and unchanged while it runs
• Dynamic priority: adjusted as the behavior of the process changes

Priority adjustment strategies:

• The longer a process waits, the higher its priority becomes
• The more CPU time a process has used, the lower its priority becomes
• I/O-bound processes get a higher priority than CPU-bound processes

5. Multilevel Feedback Queue

Algorithm:

• Set up several priority queues
• A new process enters the highest-priority queue
• When it exhausts its time slice it is demoted to the next queue down
• Lower-priority queues get longer time slices

Characteristics:

• Combines the strengths of several algorithms
• Favours short processes
• Long processes still get to run eventually

Example of queue setup:

Real-Time Scheduling

Characteristics of Real-Time Systems

1. Time constraints: a task must finish within the time it is given
2. Predictability: the behavior of the system must be predictable
3. Reliability: the system must be stable and dependable

Real-Time Scheduling Algorithms

1. Earliest Deadline First (EDF):

• Run the process whose deadline is the nearest
• A dynamic priority scheduling algorithm
• Theoretically optimal among real-time scheduling algorithms

2. Rate Monotonic Scheduling (RMS):

• The priority of a periodic task is inversely proportional to its period
• The shorter the period, the higher the priority
• A static priority scheduling algorithm

3. Least Laxity First (LLF):

• Run the process with the smallest laxity
• Laxity = Deadline - Current time - Remaining execution time

Multiprocessor Scheduling

Scheduling Policies

1. Global scheduling:

• All CPUs share a single ready queue
• The scheduler picks processes for every CPU
• Load balancing works well

2. Local scheduling:

• Each CPU has its own ready queue
• Processes are bound to a particular CPU
• Reduces the cost of migrating processes

Load Balancing

Goal: keep the load on all CPUs as even as possible.

Strategies:

• Work stealing: an idle CPU steals processes from a busy CPU
• Load migration: processes move from a busy CPU to an idle CPU
• Dynamic load balancing: the assignment is adjusted as the load changes

Evaluating Scheduling Performance

Metrics

1. CPU utilization: the percentage of time the CPU is busy
2. Throughput: the number of processes completed per unit of time
3. Turnaround time: the time from submission of a process to its completion
4. Waiting time: the time a process spends in the ready queue
5. Response time: the time from a request until the response

Performance Comparison

---

Glossary