Module 3 - CPU Scheduling

Scheduling Concepts

• A process moves between different scheduling queues during its lifetime.

• The OS selects processes from these queues via the appropriate scheduler.

Types of Schedulers

1. Long-Term Scheduler (Job Scheduler)

   • Selects processes from secondary storage and loads them into memory for execution.

   • Executes infrequently (minutes between new processes).

   • Controls the degree of multiprogramming (number of processes in memory).

   • Selects a good mix of I/O-bound and CPU-bound processes.

2. Short-Term Scheduler (CPU Scheduler)

   • Selects processes from the ready queue for execution.

   • Must be very fast, as process execution occurs in milliseconds.

3. Medium-Term Scheduler (Not always present in all OSes)

   • Swaps out processes from memory to reduce multiprogramming (especially to avoid thrashing).

   • Later, the process can be reintroduced and continue execution.

   • This process is called swapping.

Scheduling Concepts

• A process moves between different scheduling queues during its lifetime.

• The OS selects processes from these queues via the appropriate scheduler.

Types of Schedulers

1. Long-Term Scheduler (Job Scheduler)

   • Selects processes from secondary storage and loads them into memory for execution.

   • Executes infrequently (minutes between new processes).

   • Controls the degree of multiprogramming (number of processes in memory).

   • Selects a good mix of I/O-bound and CPU-bound processes.

2. Short-Term Scheduler (CPU Scheduler)

   • Selects processes from the ready queue for execution.

   • Must be very fast, as process execution occurs in milliseconds.

3. Medium-Term Scheduler (Not always present in all OSes)

   • Swaps out processes from memory to reduce multiprogramming (especially to avoid thrashing).

   • Later, the process can be reintroduced and continue execution.

   • This process is called swapping.

Context Switching

• Definition: Saving the state of one process and loading the saved state of another process.

• Overhead: The system does no useful work while switching processes, so it should be minimized.

• Time Factors:

  • Varies based on hardware (memory speed, number of registers to be copied, special instructions).

  • Some processors have multiple register sets, reducing context-switch time.

CPU Scheduler

• The CPU Scheduler selects processes from the ready queue for execution when the CPU becomes idle.

When CPU Scheduling Decisions Occur

Scheduling decisions happen under four conditions:

1. Process switches from running → waiting state (e.g., I/O request, waiting for a child process to terminate).

2. Process switches from running → ready state (e.g., due to an interrupt).

3. Process switches from waiting → ready state (e.g., I/O completion).

4. Process terminates.

Preemptive vs. Non-Preemptive Scheduling

• Non-Preemptive:

  • Once a process gains the CPU, it runs until it releases it (finishes or voluntarily yields).

  • Simpler but not ideal for time-sharing systems.

• Preemptive:

  • A process can be interrupted and moved back to the ready queue if a higher-priority process arrives.

  • Allows for more efficient multi-tasking but requires careful synchronization.

Scheduling Algorithms

Different algorithms determine how the CPU selects the next process to execute.

First-Come, First-Served (FCFS)

• Process executed in the order they arrive.

• Simplest but can lead to long waiting times for CPU-bound processes (Convoy Effect).

• Is nonpreemptive. Once the CPU

  has been allocated to a process, the process keeps the

  CPU until it wants to release the CPU, either by

  terminating or be requesting I/O.

Shortest Job First (SJF)

• This algorithm associates with each process the length

  of the latter’s next CPU burst. When the CPU is

  available, it is assigned to the process that has the

  smallest next CPU burst

• Although the SJF algorithm is optimal, it cannot be

  implemented at the level of short-term scheduling.

  There is no way to know the length of the next CPU

  burst. The only alternative is to predict the value of the

  next CPU burst

Shortest Remaining Job First (SRJF)

• The SJF algorithm may be either preemptive or

  nonpreemptive. A new process arriving may have a

  shorter next CPU burst than what is left of the currently

  executing process.

• A preemptive SJF algorithm will

  preempt the currently executing process.

• Preemptive SJF scheduling is sometimes called shortest-remaining-

  time-first scheduling.

Priority Scheduling

• Each process is assigned a priority.

• The CPU is allocated to the highest-priority process.

• Can lead to starvation (low-priority processes waiting indefinitely).

• Aging can be used to gradually increase priority over time.

• When a process arrives at the ready queue, its priority is compared with the priority at the currently running process. A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the currently running process.

Round Robin (RR)

• Each process gets a time quantum (time slice).

• If a process does not finish in its time slice, it is moved to the end of the ready queue.

• Ideal for time-sharing systems.

• The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum. The RR algorithm is therefore preemptive.

• If the time quantum is too large (infinite), the RR policy degenerates into the FCFS policy. If the time quantum is too small, then the effect of the context-switch time becomes a significant overhead.

Multilevel Queue Scheduling

• Different priority queues for processes.

• Queues can be scheduled separately (e.g., foreground and background processes).

• Scheduling can be:

  • Fixed priority (absolute preference for higher queues).

  • Time-sharing between queues.

• This algorithm is similar to the multilevel queue

  scheduling algorithm except that it allows processes to

  move between queues. The idea is to separate processes with different CPUburst characteristics. If a process uses too much CPU time, it will be moved to a lower-priority queue.

Multilevel Feedback Queue

• Processes move between queues based on execution behavior.

• Good for balancing I/O-bound vs. CPU-bound processes dynamically.

Performance Evaluation of Scheduling

Scheduling Criteria

• CPU Utilization – Keep the CPU as busy as possible.

• Throughput – Number of processes completed per unit time.

• Turnaround Time – Total time taken for a process to execute (submission → completion).

• Waiting Time – Total time spent in the ready queue.

• Response Time – Time from submission to the first response.

Performance Evaluation of Scheduling

Trade-offs in Scheduling

• Shortest job first minimizes waiting time but requires predicting burst times.

• Preemptive scheduling improves responsiveness but increases context-switch overhead.

• Round Robin provides fairness but may have higher turnaround time.