CPU Scheduling Concepts

• Chapter 5 focuses on CPU Scheduling

Basic Concepts

• Multiprogramming aims to maximize CPU utilization
• Process execution includes alternating cycles of CPU execution and I/O wait
• In a CPU-I/O Burst Cycle, a process alternates between CPU bursts and I/O bursts
• I/O-bound programs feature frequent, short CPU bursts
• CPU-bound programs have fewer, longer CPU bursts

CPU Scheduler

• The CPU scheduler (short-term scheduler) selects a process from memory that is ready to execute and allocates the CPU to it
• A ready queue can be structured as a FIFO queue, priority queue, tree, or unordered linked list
• CPU scheduling decisions occur during these four conditions:
  • When a process transitions from running to waiting (e.g., I/O request)
  • When a process transitions from running to ready (e.g., interrupt)
  • When a process transitions from waiting to ready (e.g., I/O completion)
  • When a process terminates
• Scheduling that occurs only under conditions 1 and 4 is "nonpreemptive", otherwise it is called "preemptive."
• With nonpreemptive scheduling, a process retains the CPU until it either terminates or enters a waiting state

Dispatcher

• The dispatcher module gives control of the CPU to the process selected by the short-term scheduler
• This process involves:
  • Switching context
  • Switching to user mode
  • Jumping to the proper location in the user program
• Dispatch latency is the time required for the dispatcher to stop one process and start another

Scheduling Criteria

• CPU utilization should be kept as high as possible
• Throughput is the number of processes completed per time unit
• Turnaround time is the time to execute a process, including waiting to get into memory, time in the ready queue, CPU execution, and I/O
• Waiting time is the sum of time periods spent in the ready queue
• Response time is the time from submission of a request until the first response is produced

Optimization Criteria

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

Scheduling Algorithms

• CPU scheduling focuses on selecting a process from the ready queue for CPU execution
• Common algorithms:
  • First-Come, First-Served (FCFS)
  • Shortest-Job-First (SJF)
  • Priority
  • Round-Robin (RR)
  • Multilevel Queue
  • Multilevel Feedback Queue

First-Come, First-Served (FCFS) Scheduling

• It is the simplest CPU scheduling algorithm
• The CPU is allocated to the process that requests it first
• FCFS can result in long average wait times
• The example given in the notes, the average waiting time is 17 milliseconds given the three process details
• If the process order is arranged differently in First-Come, First-Served (FCFS), it greatly reduces the average waiting time
• In FCFS, I/O devices can be idle, and all I/O-bound processes have short CPU bursts
• The FCFS algorithm is nonpreemptive, where the CPU is held until the process terminates or requests I/O.

Shortest-Job-First (SJF) Scheduling

• The process with the shortest next CPU burst is scheduled
• In nonpreemptive scheduling, the CPU is given to the process and cannot be preempted until the CPU burst is complete
• Preemptive scheduling occurs when a new process arrives with a CPU burst shorter than the remaining time of the current process, and this is known as Shortest-Remaining-Time-First (SRTF)
• If two processes have the same next CPU burst length, FCFS scheduling is used
• SJF is optimal due to providing the minimum average waiting time for a given set of processes

Example of Non-Preemptive SJF

• Non-preemptive SJF is not useful in timesharing environments
• Both FCFS and SJF are not useful for timesharing environments because they are nonpreemptive
• The average waiting time using FCFS is 4.75, while it is 4 with SJF scheduling

Example of Preemptive SJF

• Average waiting time is 3

Priority Scheduling

• A priority number (integer) is associated with each process
• The CPU is allocated to the process with the highest priority level (smallest integer typically signifies highest priority)
• Equal-priority processes are scheduled using FCFS
• SJF is a special case of priority scheduling where priority is the predicted next CPU burst time
• Priorities can be defined either internally or externally:
  • Internal priorities are based on measurable quantities
  • External priorities are set by outside criteria
• Priority can be preemptive or nonpreemptive

Priority Scheduling (Cont.)

• A preemptive priority scheduling algorithm will preempt the CPU if the newly arrived process has a higher priority than the currently running process
• A nonpreemptive priority scheduling algorithm will add the new higher-priority process to the head of the ready queue
• Starvation occurs, where low-priority processes may never execute
• Aging is the solution to starvation, with time the process priority will increase
• In the example of a nonpreemptive priority scheduling, calculate the average waiting time

Round Robin (RR)

• It is designed for time-sharing systems
• RR is similar to FCFS with added preemption for time slice
• Each process gets a small amount of CPU time, then is preempted and added to the end of the ready queue
• The time quantum or time slice is typically 10 to 100 milliseconds
• After the time slice expires, an interrupt occurs and a context switch happens
• If the n number of processes are in the queue and the time quantum is q time, then each process gets 1/n of the CPU time in chunks of at most q time units at once
• No process waits more than (n-1)q time units
• RR performance depends on the time slice size q
• If q is very large it will be FIFO
• If very small, then RR is called processor sharing, and context switch increases, so q must be large otherwise overhead is too high

Example: RR with Time Quantum

• In the example where Time Quantum is 20 calculate the waiting Time of each Process

How a Smaller Time Quantum Increases Context Switches

• A smaller time quantum will greatly increase context switches

Multilevel Queue

• The ready queue is partitioned into separate queues
• The separate queues are: foreground (interactive) and background (batch)
• Each queue has its own scheduling algorithm
• Foreground is Round Robin
• Background is FCFS
• Scheduling must be done between the queues
• The two method are:
  • Fixed priority scheduling
  • Time Slice where each queue gets certain amount of CPU

Multilevel Feedback Queue

• A process can move between queues to implement aging
• A process waiting too long in a lower-priority queue can be moved to a higher-priority queue to prevent starvation
• A process using too much CPU time is moved to a lower-priority queue
• The multilevel feedback queue scheduling algorithm is complex

Example of Multilevel Feedback Queue

• There are three queues:
  • Q0 - time quantum 8 milliseconds
  • Q1 - time quantum 16 milliseconds
  • Q2 - FCFS
• Scheduling involves a new job entering queue Qo and being served FCFS, receiving 8 milliseconds of CPU time. If it doesn't finish, it moves to queue Q1. At Q1, the job is again served FCFS and receives 16 additional milliseconds. If it still doesn't complete, it is preempted and moved to queue Q2.
• Multilvel feedback Queue Scheduling is preemptive