Transcript Scheduling

Operating Systems: Scheduling
Scheduling
• Processes can be in one of several states
– 5 state model :
– ‘short-term’ scheduling
» organising transitions between states
- on page-fault, waiting for or getting semaphores, I/O transfer completions etc.
» deciding order in which ready processes should be run
- priorities etc. and queue handling
1
Operating Systems: Scheduling
– 7 state model with medium and long-term scheduling :
2
Operating Systems: Scheduling
• Medium-term scheduling
– when main memory is full, processes need to be swapped out to disc
– medium-term sched. decides which and when to swap out and back in
» level of multiprogramming to achieve desired performance
» to have processes ready and waiting to run when running process blocks
– separate swap area on disc commonly used
» local disc to be effective
» networked discs too slow
– possible to use file storage sites instead of swap area
» for files mapped into virtual space from disc storage site
- accessing VM equivalent to accessing file storage site on disc
- stacks and heaps etc. can also be mapped files
- all VM space can be mapped files
» often simpler than separate swap area
- each page only has one corresponding disc site instead of possibly two
- paging out a dirty page updates the file
- clean pages need not be written out (if disc file sites initially cleared to zero)
3
Operating Systems: Scheduling
» drawbacks :
- cannot page out across a network to a file serve
- potential file inconsistency on system crash
» EMAS system used mapped files
- first version used a swap area on a dedicated drum (fixed head disc)
- later versions just paged to and from disc file sites
- worked because it was for a stand-alone mainframe with local discs
– swap areas are usually fixed partitions on disc
» drawbacks :
- may not be large enough
- may waste disc space if large enough for any eventuality
– swap areas probably more efficient overall
» all page transfers can be initiated together
- probably to a contiguous disc area
» disc driver will be more effective in optimising transfers
- minimises head movement
4
Operating Systems: Scheduling
• Long-term scheduling
– whether to allow new processes to enter a system
– for a compute server or background job stream :
» when to start next job
- depends on job priority, CPU-time needs, memory needs etc.
- also depends on existing load
– for multiple user interactive system
» how many users to allow on
- each should get acceptable performance
- or is it better to let all requestors on and let performance degrade?
CPU
Utulisation
knee
No. of Users
5
Operating Systems: Scheduling
Short-term scheduling
• Define the objectives and criteria to be met; then invent a scheme
• Precise scheme will depend on type of system :
– Compute server or background job stream processor
» overall throughput most important
– Single-user workstation
» foreground interactive response most important
– Multiple-user system
» interactive time-sharing
» transaction processing
- travel agent enquiry and booking systems, banking terminals etc.
» interactive response with fairness between users
– Real-time systems
» meeting hard deadlines
- keeping up with processing data streams e.g. comms, audio and video etc.
- industrial process control
6
Operating Systems: Scheduling
• System Manager objectives :
– throughput - to maximise number of jobs completed per unit time
– turn-around time for jobs
– utilisation - to make best use of expensive resources
» CPU - proportion of time spent executing user programs
» memory usage
» usage of peripherals
» overall cost-effectiveness
- a mix of CPU-bound and I/O bound tasks might be desirable for balance
– to be fair
» no favouring or starvation of some processes
» ensuring priorities met
– performance to degrade gracefully under load
– to be reasonably predictable
» wide variations in performance can be distracting
– to be adaptable to varying circumstances without need for intervention
7
Operating Systems: Scheduling
• User objectives :
– turn-around time for submitted jobs
– adequate response time for interactive working
» < 0.1 sec for immediate feedback
- e.g. key depressions, menu highlighting etc.
- may need special fast path through kernel to achieve
- or peripheral processor - keyboard interface or video processor
» < 1 sec needed to maintain user attention and interest for long periods
» > 1 sec : response can be very distracting - concentration will falter
» > 10 secs : intolerable for interaction
- even ‘talk’ conversations impossible
- time to go for a coffee!
– observed phenomenon :
» thinking time drops as response time drops
» an effect of short-term memory and attention span
8
Operating Systems: Scheduling
Scheduling Criteria
• Priority of process
– basic priority usually decided outwith the scheduler - may be dynamic later
– e.g. interactive v. background
• CPU boundedness
– does process always use its CPU quantum allocation without blocking?
• I/O boundedness
– does process frequently block for I/O ?
• Page-fault frequency
– a small PFF usually means the process has all the memory it needs and can
make good progress
– a large PFF means the process will not use much CPU - always waiting for
the page to be brought in from disc
9
Operating Systems: Scheduling
• Urgency of required response
– important for user interaction
– may be vitally urgent for a real-time system
» nearness to a deadline
• CPU time already received
– may decide to give CPU to a process that has not had much yet
– or ‘to him that hath shall be given’ ?
• CPU time to completion
– average waiting time minimised if process with least time to completion run
– need to know how much time still needed - usually unknown
• Regularity of requirements
– CPU required at fixed time intervals - real-time systems
– fairly straightforward to schedule given adequate system performance
10
Operating Systems: Scheduling
• Schedulers aim to optimise future performance
– need to know future characteristics of processes
– easiest to assume processes will continue to behave as previously
– must be able to adapt when processes change characteristics
• Pre-emptive scheduling
– currently running process can be interrupted before finishing
» put back onto the Run queue to get another go on the CPU later
– typically the scheduler is re-entered on regular clock or timer interrupts
» may also get re-entered whenever kernel entered
- peripheral interrupts, semaphore operations etc.
• Non Pre-emptive scheduling
– running process continues until it has finished or blocks
» low kernel overheads
» scheduler usually needs more control than this
» other processes may be seriously adversely affected
11
Operating Systems: Scheduling
Priority Queues
• Pre-emptive priority
– processes in highest priority queue always get run first
– those in lower priority queues always wait
– starvation likely
12
Operating Systems: Scheduling
• Non-Pre-Emptive Priority
– higher priority processes still favoured but not exclusively
– every so often, take a process from a lower priority queue
» a priority ratio table (used in EMAS medium-term scheduling)
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
– make priorities dynamic
» lower a processes priority after each time it has been run for a quantum
» used in Windows NT
- process given an initial boost in priority, then gradual decay
- favours short interactions
» boost a processes priority if it has not had a go on the CPU lately
– priority purchase ?
» a user may wish to pay more to get better service
- whether funny money i.e. computing time allocations, or real money
• Higher and lower priority bands
– kernel processes v. background job stream
– real-time processes (NT)
13
Operating Systems: Scheduling
• First-Come-First-Served
– processes queued on run queue in order of arrival
– oldest process on queue always run next to completion - no pre-emption
– simple to implement
– primarily used for background and batch streams
– performs much better for long jobs than for short ones
» example: measure turnaround time normalised by service time : Tq/Ts
– favours CPU- bound processes over I/O bound processes
– unacceptable for interactive systems - might be OK if combined with priority
queue system for known long run-time processes having lower priority
14
Operating Systems: Scheduling
15
Operating Systems: Scheduling
16
Operating Systems: Scheduling
• Round-Robin
– each process gets a quantum of time (a time-slice) in turn
– good for processes of equal priority
– widely used for multi-user interactive systems
» and single-user systems with multiple activities in progress
– a pre-emptive policy
» processes pre-empted by regular clock interrupts to kernel scheduler
– main issue is length of time-slice
» to optimise interactive response, make quantum just slightly longer than a
typical interaction i.e. should complete within first time-slice :
17
Operating Systems: Scheduling
» if quantum not large enough :
» more than one quantum means additional round-robin delay
– short time-slices :
» all processes in round-robin queue get a go on the CPU quickly
» short processes complete in one go
» overheads will increase due to more frequent context changing
18
Operating Systems: Scheduling
– large time-slices :
» round-robin time longer
» some processes will always use their full time-slice
» overheads lower
– CPU-bound processes favoured over I/O bound or page-faulting processes
» CPU-bound processes take full time-slice
» I/O bound processes blocked before completing a time-slice
– put blocked processes in a special queue
» more equitable to give them higher priority when they unblock
» or put them on front of round-robin queue to get CPU next
19
Operating Systems: Scheduling
• Shortest Process Next
– process with shortest expected processing time run next - non-pre-emptive
– intended to reduce bias towards long processes
– achieves much better turnaround time than FCFS on average
– some risk of starvation for longer processes (if new processes admitted on fly)
– variability of turnaround time greater than FCFS
– need a good estimate of expected processing time (extra overhead)
» possible for batch and background streams, if user knows
» can be estimated from previous behaviour for interactive processes :
Keep a running average of what was used in previous bursts of CPU use:
Sn+1 = (  Ti ) / n
or
Sn+1 = Tn/n + Sn*(n-1)/n
Better to use an exponential average function:
Sn+1 = Tn + (1-)*Sn
20
Operating Systems: Scheduling
For 0 <  < 1, all previous observations carry decreasing weight:
Sn+1 = Tn + (1-)Tn-1 + ... + (1-)..(1-)Tn-i + (1-)..(1-)S0
For  = 0.8, virtually all weight given to previous four observations :
Sn+1 = 0.8Tn + 0.16Tn-1 + 0.032Tn-2 + 0.0064Tn-3 + . . .
For  = 0.5, all weight given to previous eight observations.
Higher values of  reflect changes more quickly - but jerkily
21
Operating Systems: Scheduling
• Shortest Time Remaining
– process with least expected run-time to completion dispatched next
– in effect a pre-emptive version of SPN
» a new process entering the queue may pre-empt the running process
– need estimate of remaining run-time for each process
» record previous elapsed times and use weighted average as in SPN
– can use regular clock interrupts to re-evaluate best next process
– better turn-around time than SPN
– no bias in favour of long processes
– risk of starvation for longer processes
– in the example, three shortest processes all receive immediate service
22
Operating Systems: Scheduling
• Highest Response Ratio Next
– aim to minimise Tq/Ts for each process
– can approximate an a priori measure :
» Response ratio = (w + s)/s
» where
w = waiting time
s = expected service time
» expected service time must be estimated again
» waiting time measured as time progresses
– process with highest RR dispatched next
» longer the wait, the higher the priority
» short processes favoured but long processes not starved
» good balance on the whole
– non-pre-emptive as defined but could be made pre-emptive as STR
– overheads in recomputing RR
23
Operating Systems: Scheduling
Threads and Scheduling
• Threads are each scheduled separately
• Threaded applications may wish to assign relative priorities to threads
– a background screen update thread - low priority
– foreground interactive thread - high priority
– check-point thread - low priority, but must not be starved
• In a multi-user environment, CPU must be allocated equitably
– spawning lots of threads must not gain the process unfair advantage
– need to add up CPU used in all threads belonging to a process when reevaluating priorities or otherwise control allocation fairly
• In a single-user environment
– equitable CPU allocation less important
• Windows NT introduced fibers to give users more precise control of
scheduling than threads
– important for database and transaction processing systems
24
Operating Systems: Scheduling
Scheduling Scheme Evaluation
• Analytic methods v. Simulation
• Queuing network models :
– arrival rates and service times
– multiple servers and queues
– expected performance can be analysed mathematically for simple systems
• Simulation :
– model of scheduling scheme programmed
– process characteristics, rate of interaction, service time needs, can be
modelled to match experience
– traces of real sessions can be kept and used in simulations
» On EMAS multi-access system, sessions were recorded on a PDP-11
» re-run in simulation later
» ERTE - Edinburgh Remote Terminal Emulator
» produced useful data for tailoring scheduling schemes
25
Operating Systems: Scheduling
Real-time System Scheduling
• Soft and Hard deadlines for tasks
– soft deadlines are desirable aims but not obligatory
– hard deadlines must be met
» may need to reserve resources ahead of time
– schedule hard deadlines first, then fit soft deadlines in later
• Continuous data streams or regular data packets a feature
– much easier if timing characteristics and processing needs known in advance
• Need to avoid Priority Inversion :
– where a low priority task has a resource that is blocking a high priority task
– possible solution : priority inheritance
» low priority task inherits high priority of task needing the resource it has
26
Operating Systems: Scheduling
• Cyclic Static scheduling :
– for processing data appearing continuously or at regular times
– pre-allocate a fixed amount of CPU at regular intervals
» use timer interrupts to regain scheduling control from other tasks
– can interlace multiple processing needs :
A
B
A
A
B
A
A
B
• Dynamic scheduling : Most Urgent First
– dispatch process with earliest deadline
• Maximum Lateness First
– lateness = processing time left for task - time left until deadline
– task with largest lateness selected next
• Rate Monotonic
– assigns a priority to each task a priori proportional to the frequency of
occurrence of its triggering event.
27
Operating Systems: Scheduling
– task A : period 3ms, processing time 1.5ms
– task B : period 2ms, processing time 0,2ms
– task C : period 1ms, processing time 0.2ms
• A Priori Analysis
– mathematical and simulation techniques for predicting whether scheduling
objectives can be met and a schedule to meet them
28
Operating Systems: Scheduling
• Round Robin and other schemes also used in real-time systems
• Hierarchical Scheduling :
– form groups of tasks and apply different scheduling schemes to each group
Priority
Cyclic Static
T1
T2
Round Robin
T3
T4
T5
T6
• Important that user able to select an appropriate scheduling scheme
29