OS Chapter 5

chapter5 CPU Scheduling

basic concept

CPU-I/O BurstCycle

CPU Scheduler

Queue may be ordered in various ways

Preemptive Scheduling

CPU scheduling decisions may take place when a process:

Switches from running to waiting state

Switches from running to ready state

Switches from waiting to ready

Terminates

Scheduling under 1 and 4 is nonpreemptive

All other scheduling is preemptive

Dispatcher:Dispatcher module gives control of the CPU to the process selected by the short-term scheduler

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

CPU utilization – keep the CPU as busy as possible

Throughput – # of processes that complete their execution per time unit

Turnaround time – amount of time to execute a particular process

Waiting time – amount of time a process has been waiting in the ready queue

Optimization Criteria

Max CPU utilization

Max throughput

Min turnaround time\u00A0

Min waiting time\u00A0

Min response time

Scheduling Algorithm\u00A0

Process\tBurst Time\t\t P1 \u00A0 \u00A0 \u00A0 \u00A0 24\t\t P2 \u00A0 \u00A0 \u00A0 \u00A0 3\t\t P3 \u00A0 \u00A0 \u00A0 \u00A0 3\u00A0

Waiting time for P1 \u00A0= 0; P2 \u00A0= 24; P3 = 27

Average waiting time: \u00A0(0 + 24 + 27)/3 = 17

Convoy effect - short process behind long processConsider one CPU-bound and many I/O-bound processes

Shortest-Job-First (SJF) Scheduling

Associate with each process the length of its next CPU burstUse these lengths to schedule the process with the shortest time

SJF is optimal – gives minimum average waiting time for a given set of processesThe difficulty is knowing the length of the next CPU requestCould ask the user

Example of Shortest job first

Process \u00A0Burst Time\t\t \t\tP1 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A06\t\t\t\tP2\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\t8\t\t \t\tP3\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\t7\t\t \t\tP4\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\t3

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

Determining Length of Next CPU Burst

Can only estimate the length – should be similar to the previous oneThen pick process with shortest predicted next CPU burst

tn+1 = a tn +(1-a)tn

Example of Sortest remaining time first

ProcessA \u00A0Arrival Time \u00A0Burst Time\t\t \tP1\t\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\u00A0 \u00A0 \u00A0 \u00A0 \u00A00\t \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A08\t\t\tP2 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\t1 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A04\t\t \tP3\t\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t2\t \u00A0 \u00A0 \u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 9\t\t \tP4\t\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t3\u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t \u00A0 \u00A0 \u00A0 5

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

Priority Scheduling

A priority number (integer) is associated with each process

The CPU is allocated to the process with the highest priority (smallest integer  highest priority)PreemptiveNonpreemptive

Problem  Starvation – low priority processes may never execute

Solution  Aging – as time progresses increase the priority of the process

Example of Priority Scheduling

Process\u00A0\u00A0Burst Time Priority\t\t \tP1 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 10 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A03\t\t \tP2\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \t\t1 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 1\t\t \tP3 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A02 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 4\t\t \tP4\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\t1 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 5\t\t\tP5\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0\t\t5 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 2

Average waiting time = [(6)+(0)+(16)+(18)+(1)]/5 = 8.2 msec

Round Robin (RR)

Timer interrupts every quantum to schedule next process

Example of RR with Time Quantum = 4

Process \u00A0Burst Time\u00A0 \u00A0P1 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A024\t\t \u00A0 \u00A0P2\t \u00A0\t \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 3\t\t \u00A0 \u00A0P3 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 3

Multilevel Queue

Each queue has its own scheduling algorithm:foreground – RRbackground – FCFS

Multilevel Feedback Queue

A process can move between the various queues; aging can be implemented this way

Multilevel-feedback-queue scheduler defined by the following parameters:number of queuesscheduling algorithms for each queuemethod used to determine when to upgrade a processmethod used to determine when to demote a processmethod used to determine which queue a process will enter when that process needs service

Example of Multilevel Feedback Queue

Three queues:\u00A0Q0 – RR with time quantum 8 millisecondsQ1 – RR time quantum 16 millisecondsQ2 – FCFS

Thread Scheduling

Distinction between user-level and kernel-level threads

contention scope

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

Processor affinity – process has affinity for processor on which it is currently running

soft affinity

hard affinity

Variations including processor sets

Operating System Examples

Solaris Scheduling\u00A0

Scheduler converts class-specific priorities into a per-thread global priority

Thread with highest priority runs next

Multiple threads at same priority selected via RR

Windows Scheduling

Windows uses priority-based preemptive scheduling

Highest-priority thread runs next

Dispatcher is scheduler

Real-time threads can preempt non-real-time

Algorithm Evaluation

How to select CPU-scheduling algorithm for an OS?

Queueing Models

Knowing arrival rates and service rates

Little’s Formula

Simulations

Simulations more accurate

Programmed model of computer systemClock is a variableGather statistics \u00A0indicating algorithm performanceData to drive simulation gathered viaRandom number generator according to probabilities

Implementation

Even simulations have limited accuracy

Most flexible schedulers can be modified per-site or per-system

APIs to modify priorities