CPU Scheduling

Chapter 5

Objectives

• Describe various CPU scheduling algorithms
• Assess CPU scheduling algorithms based on scheduling criteria (metrics)
• Explain the issues related to multiprocessor and multicore scheduling
• Describe various real-time scheduling algorithms
• Apply modeling and simulations to evaluate CPU scheduling algorithms

​

CPU Scheduling Introduction

• CPU Scheduling is an Operating System concept that decides which process gets the CPU and for how long when multiple processes are waiting to execute.
• The scheduler in the operating system makes this decision.
• The goal is to use the CPU efficiently and reduce waiting time.

Basic Concepts

• Maximum CPU utilization obtained with multiprogramming
• CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
• CPU burst followed by I/O burst
• CPU burst distribution is of main concern

​

CPU Scheduler

• The CPU scheduler selects from among the processes in ready queue, and allocates a CPU core to one of them
• Queue may be ordered in various ways
• CPU scheduling decisions may take place when a process:

1. Switches from running to waiting state

2. Switches from running to ready state

3. Switches from waiting to ready

• Terminates
4. For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution.
5. For situations 2 and 3, however, there is a choice.

Preemptive and Nonpreemptive Scheduling

• When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is nonpreemptive.
• Otherwise, it is preemptive.
• Under Nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.
• Virtually all modern operating systems including Windows, MacOS, Linux, and UNIX use preemptive scheduling algorithms.

Preemptive and Nonpreemptive Scheduling

• When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is nonpreemptive.
• Otherwise, it is preemptive.
• Under Nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.
• Virtually all modern operating systems including Windows, MacOS, Linux, and UNIX use preemptive scheduling algorithms.

​

Preemptive Scheduling and Race Conditions

• Preemptive scheduling can result in race conditions when data are shared among several processes.
• Consider the case of two processes that share data. While one process is updating the data, it is preempted so that the second process can run. The second process then tries to read the data, which are in an inconsistent state.
• This issue will be explored in detail in Chapter 6.

​

Dispatcher

• Dispatcher module gives control of the CPU to the process selected by the CPU scheduler; this involves:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program
• Dispatch latency – time it takes for the dispatcher to stop one process and start another running

​

Scheduling Criteria and Metrics

• CPU utilization – keep the CPU as busy as possible. This measures how much time the CPU is actually working.
• CPU Utilization = CPU Busy Time / Total Time * 100
• Throughput – # of processes that complete their execution per time unit.
• Throughput = number of completed processes / Total execution time
• Turnaround time – amount of time it takes to execute a particular process.
• Turnaround Time = Completion Time - Arrival Time
• Waiting time – the total mount of time a process spends waiting in the ready queue.
• Waiting Time = Turnaround Time – Burst Time
• Response time – amount of time it takes from when a request was submitted until the first response is produced.
• Response Time = Time when process first get the CPU – Arrival Time

Scheduling Algorithm Optimization Criteria

• Max CPU utilization
• Max throughput
• Min turnaround time
• Min waiting time
• Min response time
• Response time measures how quickly the system starts responding to a process. This is important for interactive systems (like terminals, GUIs).

​

​

First- Come, First-Served (FCFS) Scheduling

​

​

​

• Suppose that all the processes arrive at time 0 in the order: P₁ , P₂ , P_{3 �}The Gantt Chart for the schedule is:

​

​

​

• Waiting time for P₁ = 0; P₂ = 24; P₃ = 27
• Average waiting time: (0 + 24 + 27)/3 = 17

​

​

FCFS Scheduling (Cont.)

FCFS Scheduling (Cont.)

FCFS Scheduling (Cont.)

Suppose that the same processes arrived in the order:

P₂ , P₃ , P₁

• The Gantt chart for the schedule is:�

​

​

​

• Waiting time for P₁ = 6; P₂ = 0; P₃ = 3
• Average waiting time: (6 + 0 + 3)/3 = 3
• Much better than previous case
• Convoy effect - short process behind long process
• Consider one CPU-bound and many I/O-bound processes

FCFS Scheduling (Cont.)

FCFS Scheduling (Cont.)

Shortest-Job-First (SJF) Scheduling

• This is a CPU scheduling algorithm where the process with the smallest burst time executes first
• Associate with each process the length of its next CPU burst
• Use these lengths to schedule the process with the shortest time
• SJF is optimal – gives minimum average waiting time for a given set of processes
• The difficulty is knowing the length of the next CPU request
• Could ask the user

Types of Shortest-Job-First (SJF) Scheduling

1. Non-Preemptive SJF
2. Preemptive SJF (Also called shortest-remaining-time-first)
1. How do we determine the length of the next CPU burst?
• Could ask the user
• Estimate

​

Example of SJF

​

​

​

​

​

• SJF scheduling chart. Assume all processes arrived at time 0.

​

​

​

​

• Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

SJF Scheduling (Cont.)

SJF Scheduling (Cont.)

Example of Shortest-remaining-time-first

• Now we add the concepts of varying arrival times and preemption to the analysis

​

​

​

​

Preemptive SJF Gantt Chart

​

​

• Average waiting time = [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 26/4 = 6.5

​

Preemptive SJF Scheduling (Cont.)

Preemptive SJF Scheduling (Cont.)

Round Robin (RR)

• Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is q, 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.
• Timer interrupts every quantum to schedule next process
• Performance
• q large ⇒ FIFO
• q small ⇒ q must be large with respect to context switch, otherwise overhead is too high

​

Example of RR with Time Quantum = 4

​

​

​

• The processes arrive at time 0 in the order P1, P2 and P3
• The Gantt chart is:

​

​

• Typically, higher average turnaround than SJF, but better response
• q should be large compared to context switch time
• q usually 10 milliseconds to 100 milliseconds,
• Context switch < 10 microseconds

​

RR Scheduling (Cont.) – Waiting Time

• WT for P₁ = (0 – 0) + (10 – 4) = 0 + 6 = 6
• WT for P₂ = (4 – 0) = 4
• WT for P₃ = (7 – 0) = 7
• Average Waiting Time = 6 + 4 + 7 = 17 / 3 = 5.7

RR Scheduling (Cont.)

RR Scheduling (Cont.)

Time Quantum and Context Switch Time

Turnaround Time Varies With The Time Quantum

80% of CPU bursts should be shorter than q

Priority Scheduling

• Priority Scheduling is a CPU scheduling algorithm in which each process is assigned a priority. The CPU is allocated to the process with the highest priority (lowest numerical value usually means higher priority).
• A priority number (integer) is associated with each process. The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority)
• SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
• Problem ≡ low priority processes may never execute
• Solution ≡ Aging –Starvation – as time progresses increase the priority of the process

​

Priority Scheduling

1. Non-Preemptive Priority
• Once a process starts, it runs to completion.
• Simple but may cause long waiting time for low-priority processes.
2. Preemptive Priority
• If a higher-priority process arrives, the CPU preempts the running process.
• Also called “Priority with Preemption”.

​

Example of Priority Scheduling

​

​

​

​

​

• Priority scheduling Gantt Chart. Assume that all processes arrived at 0

​

​

​

​

• Average waiting time = 8.2

Waiting Time

• Waiting time for P₁ = 6 – 0 = 6;
• Waiting time for P₂ = 0 – 0 = 0;
• Waiting time for P₃ = 16 – 0 = 16;
• Waiting time for P₄ = 18 – 0 = 18;
• Waiting time for P₅ = 1 – 0 = 1;
• The average waiting time = (6 + 0 + 16 + 18 + 1) = 41/5 = 8.2

​

​

Priority Scheduling (Cont.)

Priority Scheduling (Cont.)

Priority Scheduling w/ Round-Robin

ProcessA arri Burst TimeT Priority

P₁ 4 3

P₂ 5 2

P₃ 8 2

P₄ 7 1

P₅ 3 3

• Run the process with the highest priority. Processes with the same priority run round-robin
• Gantt Chart with time quantum = 2

​

​

​

FCFS Scheduling (Cont.)

FCFS Scheduling (Cont.)

Multilevel Queue

• With priority scheduling, have separate queues for each priority.
• Schedule the process in the highest-priority queue!

​

Multilevel Queue

• Prioritization based upon process type

​

Multilevel Feedback Queue

• A process can move between the various queues.
• Multilevel-feedback-queue scheduler defined by the following parameters:
• Number of queues
• Scheduling algorithms for each queue
• Method used to determine when to upgrade a process
• Method used to determine when to demote a process
• Method used to determine which queue a process will enter when that process needs service
• Aging can be implemented using multilevel feedback queue

​

Example of Multilevel Feedback Queue

• Three queues:
• Q₀ – RR with time quantum 8 milliseconds
• Q₁ – RR time quantum 16 milliseconds
• Q₂ – FCFS
• Scheduling
• A new process enters queue Q₀ which is served in RR
• When it gains CPU, the process receives 8 milliseconds
• If it does not finish in 8 milliseconds, the process is moved to queue Q₁
• At Q₁ job is again served in RR and receives 16 additional milliseconds
• If it still does not complete, it is preempted and moved to queue Q₂

​

Thread Scheduling

• Distinction between user-level and kernel-level threads
• When threads supported, threads scheduled, not processes
• Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP
• Known as process-contention scope (PCS) since scheduling competition is within the process
• Typically done via priority set by programmer
• Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system

​

Multiple-Processor Scheduling

• CPU scheduling more complex when multiple CPUs are available
• Multiprocess may be any one of the following architectures:
• Multicore CPUs
• Multithreaded cores
• NUMA systems
• Heterogeneous multiprocessing

​

Multiple-Processor Scheduling

• Symmetric multiprocessing (SMP) is where each processor is self scheduling.
• All threads may be in a common ready queue (a)
• Each processor may have its own private queue of threads (b)

​

Multicore Processors

• Recent trend to place multiple processor cores on same physical chip
• Faster and consumes less power
• Multiple threads per core also growing
• Takes advantage of memory stall to make progress on another thread while memory retrieve happens
• Figure

​

Multithreaded Multicore System

• Each core has > 1 hardware threads.
• If one thread has a memory stall, switch to another thread!
• Figure

​

Multithreaded Multicore System

• Chip-multithreading (CMT) assigns each core multiple hardware threads. (Intel refers to this as hyperthreading.)����
• On a quad-core system with 2 hardware threads per core, the operating system sees 8 logical processors.

​

Multithreaded Multicore System

• Two levels of scheduling:�
1. The operating system deciding which software thread to run on a logical CPU��
2. How each core decides which hardware thread to run on the physical core.

Multiple-Processor Scheduling – Load Balancing

• If SMP, need to keep all CPUs loaded for efficiency
• Load balancing attempts to keep workload evenly distributed
• Push migration – periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs
• Pull migration – idle processors pulls waiting task from busy processor

​

Multiple-Processor Scheduling – Processor Affinity

• When a thread has been running on one processor, the cache contents of that processor stores the memory accesses by that thread.
• We refer to this as a thread having affinity for a processor (i.e., “processor affinity”)
• Load balancing may affect processor affinity as a thread may be moved from one processor to another to balance loads, yet that thread loses the contents of what it had in the cache of the processor it was moved off of.
• Soft affinity – the operating system attempts to keep a thread running on the same processor, but no guarantees.
• Hard affinity – allows a process to specify a set of processors it may run on.

​

​

NUMA and CPU Scheduling

• If the operating system is NUMA-aware, it will assign memory closes to the CPU the thread is running on.

​