程序代写代做代考 flex algorithm cache 04-Scheduling

04-Scheduling

Peter R. Pietzuch
prp@doc.ic.ac.uk

Scheduling

Scheduler tasks and goals
Process states
Pre-emption
Scheduling strategies

• First come first served, Round robin (time sliced),
Shortest job first, Priority based,
Multi level feedback queues, Lottery

Thread scheduling

22

Scheduler Tasks

The scheduler
– Allocates processes to processors.
– Selects highest priority ready process (from head of Ready

Queue) and moves it to the running state, i.e., allows it to
start executing on the processor.

– Gets invoked after every entry to the kernel.
Current process continues unless:

– Kernel call moved it into waiting state (e.g. waiting on
I/O).

– Error trap occurred (e.g. memory protection violation).
– Time slice expired.
– A higher priority process is made ready.

33

Process States

Terminated

Ready

Running

Waiting

New

Exit

Enable

Picked by
scheduler

Preempted

Event arrived
(I/O complete,
semaphore signaled, etc.)

Blocking
operation
(initiate I/O, down
on semaphore, etc.)

• New: the process is being created
• Ready: runnable and waiting for

processor
• Running: executing on a processor
• Waiting/Blocked: waiting for an event
• Terminated: process is being deleted

If multiple processes are ready,
which one should be run?

Menti.com Q1 42 63 05

44

Goals of Scheduling Algorithms

Ensure fairness
– Comparable processes should get comparable services

Avoid indefinite postponement
– No process should starve

Enforce policy
– E.g., priorities

Maximize resource utilization
– CPU, I/O devices

Minimize overhead
– From context switches, scheduling decisions

55

Goals of Scheduling Algorithms

Batch systems:
– Throughput è maximize jobs per unit of time
– Turnaround time è minimize time between job

submission and termination
– Maximize CPU utilization

Interactive systems:
– Response time crucial è quick response to requests
– Meet users expectations è predictability

Real-time systems:
– Meeting deadlines

• Soft deadlines: e.g., leads to degraded video quality
• Hard deadline: e.g., leads to plane crash

– Predictability

66

Preemptive vs. Non-Preemptive Scheduling

Non-preemptive
– Let process run until it blocks or voluntarily releases

the CPU

Preemptive:
– Let process run for a maximum amount of fixed time

• Requires clock interrupt
– External event results in higher priority process

being run

77

CPU-bound vs. I/O-bound Processes

CPU-bound processes
– Spend most of their time using the CPU

I/O-bound processes
– Spend most of their time waiting for I/O
– Tend to only use CPU briefly before issuing I/O request

88

First-Come First-Served (FCFS) (non-preemptive)

Waiting (Blocked) processes

Running
process

Blocking operation

Ready queue

Event arrived

ScheduleTerminated

New
process

• Runnable process added to
the end of ready queue
• Non-preemptive

99

FCFS Advantages

No indefinite postponement
– All processes are eventually scheduled

Really easy to implement

1010

FCFS Disadvantages

What happens if a long job is followed by many short jobs?
– E.g., 1h, 1s, 1s, 1s, with jobs 2-4 submitted just after

job 1

3600s 1s 1s 1s
§ Throughput?
§ Average turnaround time?

3600s1s 1s 1s

§ Throughput?
§ Average turnaround time?

Menti.com Q2,3 42 63 05

1212

FCFS Disadvantages

What about I/O bound processes?
E.g., one CPU-bound process runs for 1s each time, before doing
I/O to release processor. Needs > 1000s CPU time
Many I/O-bound process needs to perform 1000 disk reads to
complete, with minimal processing between I/O
Compute process runs for 1 sec then starts read so I/O process
can then run and start their read, but only do 1 read per sec.

– I/O bound processes initiates 1 request at a time?
• 1000s to complete

– Preempting CPU-bound process every 10ms?
• 10s to complete

1313

Round-Robin Scheduling (RR)

Process runs until it blocks or
time quantum exceeded

Waiting processes
Blocking operation

Ready queue

Event
arrived

ScheduleTerminated

New
process

Running
process

Preempted

1414

Round-Robin

Fairness
– Ready jobs get equal share of the CPU

Response time
– Good for small number of jobs

Average turnaround time:
– Low when run-times differ
– Poor for similar run-times

A: 200ms, B: 10s
Turnaround time:
FCFS: A = 200ms, B = 10,200ms

Avg = 5200ms
RR: A ≈ 300ms, B ≈ 10,200ms

Avg ≈ 5250m à 1.01x

A: 10s, B: 10s
Turnaround time:
FCFS: A = 10s, B = 20s

Avg = 15s
RR: A ≈ 20s, B ≈ 20s

Avg ≈ 20s à 1.33x

Quantum = 100ms,
Context switch time = negligible

1515

RR Quantum (Time Slice)

RR Overhead:
– 4ms quantum, 1ms context switch time:

20% of time à overhead high
– 1s quantum, 1ms context switch time:

only 0.1% of time à overhead low
Large quantum:

– Smaller overhead
– Worse response time

• Quantum = ∞ à FCFS
Small quantum:

– Larger overhead
– Better response time
– Ideal quantum ≈ ave. CPU time between I/O

1616

Time quantum vs I/O times

Process allocated
time quantum

Time

Response time
s

Quantum
q

q – s

Figure 9.6 Effect of Size of Preemption Time Quantum

Interaction
complete

(a) Time quantum greater than typical interaction

Process allocated
time quantum

s

q

Process allocated
time quantum

Process
preempted

Other processes run

(b) Time quantum less than typical interaction

Interaction
complete

If time quantum is too
small, most processes will
require > 1 quantum to
complete, which
increases response time.

1717

RR Quantum

Choosing a quantum value:
– Should be much larger than context switch cost
– But provide decent response time

Typical values: 10-200ms

Some example values for standard processes (values vary depending
on process type and behaviour, priority, etc.):

– Linux: 100ms
– Windows client: 20ms
– Windows server: 180ms

1818

Shortest Job First (SJF)

Non-preemptive scheduling with run-times known in advance
Pick the shortest job first

– Process with shortest CPU burst

A: 8s
B: 12s
C: 16s
D: 20s

Avg: 56/4 = 14s

B: 4s
C: 8s
D: 12s
A: 20s

Avg: 44/4 = 11s

• Provably optimal when all jobs are available simultaneously

Turnaround time: Turnaround time:

1919

Shortest Remaining Time (SRT)

Preemptive version of shortest job first
– Again, runtimes have to be known in advance

Choose process whose remaining time is shortest
– When new process arrives with execution time less

than the remaining time for the running process, run it
Allows new short jobs to get good service

Example: 3 jobs: J1 = 6s, J2 = 4s, J3 = 1s, & arrives after 2s

J2 J1
4s 1s 6s

J2 J3 J1
2s 1s

J2
2s 6s

SJF:

SRT:

J3

2020

Shortest Remaining Time (SRT)

What if a running process is almost complete and a
shorter job arrives?

– Might want to disallow preemption when remaining
run-time reaches a low threshold to avoid indefinite
postponement

– What if context switch overhead is greater than the
difference in remaining run-times for the two jobs?

2121

Knowing Run-times in Advance

Run-times are usually not available in advance

Compute CPU burst estimates based on various heuristics?
– E.g., based on previous history
– Not always applicable

User-supplied estimates?
– Need to counteract cheating to get higher priority
– E.g., terminate or penalize processes after they exceed

their estimated run-time

2222

Minimise Turnaround Time

Five jobs are waiting to be run. Their expected run times
are 9, 6, 3, 5, and X. In what order should they be run to
minimize average turnaround time? (Your answer will
depend on X.)

2424

Fair-Share Scheduling

Users are assigned some fraction of the CPU
– Scheduler takes into account who owns a process before

scheduling it
E.g., two users each with 50% CPU share

– User 1 has 4 processes: A, B, C, D
– User 2 has 2 processes: E, F

What does a fair-share RR scheduler do?
– A, E, B, F, C, E, D, F, A, E, B, F…

2525

Priority Scheduling

• Jobs are run based on their priority
§ Always run the job with the highest priority

• Priorities can be externally defined (e.g., by user)
or based on some process-specific metrics (e.g.,
their expected CPU burst)

• Priorities can be static (i.e. they don’t change) or
dynamic (they may change during execution)

• Example: consider three processes arriving at
essentially the same time with externally defined
static priorities
A = 4, B = 7, C = 1, where a higher value means
higher priority.
§ Processes are run to completion in the order B, A, C.

2626

General-Purpose Scheduling

Favor short and I/O-bound jobs
– Get good resource utilization
– And short response times

Quickly determine the nature of the job and adapt to
changes

– Processes have periods when they are I/O-bound and
periods when they are CPU-bound

2727

Multilevel Feedback Queues 1

A form of priority scheduling
– Shortest remaining time also a form of priority

scheduling!

Implemented by many OSs:
– Windows Vista, Windows 7
– Mac OS X
– Linux 2.6 – 2.6.23

2828

Multilevel Feedback Queues 2
One queue for each priority level

– Run job on highest non-empty priority queue
– Each queue can use different scheduling algorithm

• Usually round-robin
• Could be different quantum eg highest priority is I/O

bound with short quantum. Exceed quantum, then
move down level but get bigger quantum.

2929

Multilevel Feedback Queues 3

Need to determine current nature of job
– I/O-bound? CPU-bound?

Need to worry about starvation of lower-priority jobs

Feedback mechanism:
– Job priorities recomputed periodically, e.g., based

on how much CPU they have recently used
• Exponentially-weighted moving average

– Aging: increase job’s priority as it waits

3030

Multilevel Feedback Queues 4

Not very flexible
– Applications basically have no control
– Priorities make no guarantees

• What does priority 15 mean?
Does not react quickly to changes

– Often needs warm-up period
• Running system for a while to get better results

– Problem for real-time systems, multimedia apps
Cheating is a concern

– Add meaningless I/O to boost priority?
Cannot donate priority

Menti.com Q4 42 63 05

3131

Single vs Multithreaded File server

Assume single processer & takes 15 ms to get a request
for work, dispatch it, and do the rest of the necessary
processing, assuming that the data needed are in the block
cache.
If a disk operation is needed, as is the case one-third of
the time, an additional 75 ms is required, during which
time the thread sleeps.

How many requests/sec can the server handle if it is
single-threaded? If it is multithreaded?

(a) non-preemptive scheduler,
(b) a preemptive round robin scheduler with a small

quantum > 25ms.

3434

Lottery Scheduling [Waldspurger and Weihl
1994]

Jobs receive lottery tickets for various resources
– E.g., CPU time

At each scheduling decision, one ticket is chosen at
random and the job holding that ticket wins

Example: 100 lottery tickets for CPU time, P1 has 20 tickets
– Chance of P1 running during the next CPU quantum: 20%
– In the long run, P1 gets 20% of the CPU time

3535

Lottery Scheduling
Number of lottery tickets meaningful

– Job holding p% of tickets, gets p% of resource
– Unlike priorities

Highly responsive:
– New job given p% of tickets has the p% chance to get

the resource at the next scheduling decision
No starvation
Jobs can exchange tickets

– Allows for priority donation
– Allows cooperating jobs to achieve certain goals

Adding/removing jobs affect remaining jobs proportionally
Unpredictable response time

– What if interactive process is unlucky for a few
lotteries?

3636

Policy versus Mechanism

Separate what is allowed to be done from how it is done
– a process knows which of its children threads are

important and need priority

Scheduling algorithm parameterized
– mechanism in the kernel

Parameters filled in by user processes
– policy set by user process

3737

Scheduling Questions

Five batch jobs, A through E, arrive at a computer centre at
essentially the same time. Their estimated running time are as
follows: A=15min, B=9min, C=3min, D=6min and E=12min.
Their (externally defined) priorities are:

A = 6, B = 3, C = 7, D = 9 and E = 4, with a lower value
corresponding to a higher priority.
For each of the following scheduling algorithms, determine the
turnaround time for each job, and the average turnaround time for
all jobs.
Ignore process switching overhead and assume all jobs are
completely CPU bound.
a) a) Non-preemptive priority scheduling.
b) b) FCFS (run in order A,B,C,D)
c) c) Shortest job first (SJF)
d) d) Round robin with a time quantum of 1 minute

4242

User Thread Scheduling

Possible scheduling of user-level threads
50-msec process quantum
Threads run 5 msec/CPU burst

4343

Kernel Thread Scheduling

Possible scheduling of kernel-level threads
50-msec process quantum
Threads run 5 msec/CPU burst

4444

Summary

Scheduling algorithms often need to balance
conflicting goals

– E.g., ensure fairness, enforce policy, maximize
resource utilization

Different scheduling algorithms appropriate in
different contexts

– E.g., batch systems vs interactive systems vs real-
time systems

Well-studied scheduling algorithms include
– First-Come First-Served FCFS, Round Robin, Shortest

Job First (SJF), Shortest Remaining Time (SRT),
Multilevel Feedback Queues and Lottery Scheduling

Menti.com Q5 42 63 05