Transcript Unit 5

Operating Systems
Operating Systems
Unit 5:
– Processor scheduling
– Java
– Linux
– Windows XP
Process Lifecycle
COP 5994 - Operating Systems
2
Processor scheduling policy
• Decides which process runs at given time
• scheduling goals
– Maximize processor utilization
– Minimize response-time to user
– Also:
• Maximize throughput
• Complete process by given deadline
COP 5994 - Operating Systems
3
Concept: CPU And I/O Bursts
COP 5994 - Operating Systems
4
Histogram of CPU-burst
Times
COP 5994 - Operating Systems
5
Concept: Preemption
• Preemptive scheduling
– Process can be removed from current
processor
• improved response times
• important for interactive environments
– (preempted process remains in memory)
• Non-preemptive scheduling
– Process runs to completion or yield
• unimportant processes can block important ones
indefinitely
COP 5994 - Operating Systems
6
Concept: Priority
• Static priorities
– Priority assigned to a process does not
change
• Easy to implement, low overhead
• Not responsive to changes in environment
• Dynamic priorities
– Responsive to change
– Promote smooth interactivity
– Incur more overhead than static priorities
• Justified by increased responsiveness
COP 5994 - Operating Systems
7
Scheduling Criteria
•
CPU utilization
– keep the CPU as busy as possible
• Throughput
– # of processes that complete per time unit
• Turnaround time
– amount of time to execute a process
• Waiting time
– time a process has been waiting in the ready queue
• Response time
– time from request until first response is produced
COP 5994 - Operating Systems
8
Scheduling Objectives
Summary
• Several goals common to most
schedulers
– Fairness
– Predictability
– Scalability
COP 5994 - Operating Systems
9
Scheduling Criteria
• Consider run-time behavior of process
– Compute vs. I/O wait
• Process categories:
– Processor-bound
– I/O-bound
– Batch processes
• no user interaction
– Interactive processes
• frequent user interaction
COP 5994 - Operating Systems
10
Scheduling Algorithms
• Decide when and for how long a process
runs
• Make choices about
– Preemptibility
– Priority
– Running time
– Run-time-to-completion
– Fairness
COP 5994 - Operating Systems
11
First-In-First-Out Scheduling
– Simplest scheme
– Processes dispatched according to arrival
time
– Non-preemptive
– Rarely used as primary scheduling algorithm
COP 5994 - Operating Systems
12
Round-Robin Scheduling
– Based on FIFO
– Processes run only for a limited time slice or
quantum
• Must be preemptible
• Context switch overhead must be minimized
– Often used as part of more complex algorithms
COP 5994 - Operating Systems
13
RR Factor: time quantum size
– Determines response time to interactive
requests
– Very large quantum size
• Processes run for long periods
• Degenerates to FIFO
– Very small quantum size
• System spends most time context switching
– Compromise:
• Long enough for normal processes to issue I/O
request
• Batch processes still get majority of processor
time
COP 5994 - Operating Systems
14
Shortest-Process-First Scheduling
• process with smallest time to finish goes
first
– Lower average wait time than FIFO
• Reduces the number of waiting processes
– Potentially large variance in wait times
– Non-preemptive
• Results in slow response times to new processes
– Relies on estimates of time-to-completion
• Can be inaccurate or falsified
– Unsuitable for use in modern interactive
systems
COP 5994 - Operating Systems
15
Highest-Response-Ratio-Next
Scheduling
• Improves upon SPF scheduling
• also considers priority
priority =
waiting-time + service-time
service-time
– Considers how long process has been
waiting
– Prevents indefinite postponement
– Still non-preemptive
COP 5994 - Operating Systems
16
Shortest-Remaining-Time Scheduling
• Preemptive version of SPF
– Shorter arriving process preempts running
process
– Problems:
• Very large variance of response times:
– long processes wait even longer than under SPF
• Context-switching overhead can become significant
– Short incoming process can preempt a running process
that is near completion
COP 5994 - Operating Systems
17
Scheduling Realities
• Different processes have different needs
– Short I/O-bound interactive processes
should generally run before processorbound batch processes
– Behavior patterns not immediately obvious
to the scheduler
COP 5994 - Operating Systems
18
Example: Selfish RR
Scheduling
• process has priority
• 2 queues:
– Holding vs. Active
• process enters into holding queue
– Increases priority as process ages
• moves to active queue when it reaches
priority of other processes in active
queue
• RR scheduling in active queue
COP 5994 - Operating Systems
19
Multilevel Feedback Queues
COP 5994 - Operating Systems
20
Multilevel Feedback Queues
• Arriving processes enter the highest-level
queue with higher priority
• Long processes descend into lower levels
– Gives short and I/O-bound processes higher priority
– Long processes will run when short and I/O-bound
processes terminate
• Process entering a higher-level queue preempt
running process
• Each queue has own scheduler
– Typical: FIFO or RR
COP 5994 - Operating Systems
21
Fair Share Scheduling
COP 5994 - Operating Systems
22
Deadline Scheduling
– Process must complete by specific time
– Used when results would be useless if not
delivered on-time
– Difficult to implement
• Must plan resource requirements in advance
• Incurs significant overhead
• Service provided to other processes can degrade
COP 5994 - Operating Systems
23
Real-time Scheduling
• Processes have timing constraints
• Soft real-time system
• Does not guarantee that timing constraints will be
met
• For example, multimedia playback
• Hard real-time system
• Timing constraints will always be met
• modes of operation:
– periodic execution of processes
– response to external event
• catastrophic result if constraint is not met
COP 5994 - Operating Systems
24
Static Real-Time Scheduling
– Does not adjust priorities over time
• Low overhead
• Suitable for systems where conditions rarely
change
– used for hard real-time systems
– Rate-monotonic (RM) scheduling
• priority-based RR scheduling
• Process priority increases monotonically with the
frequency with which it must execute
– Deadline RM scheduling
• priority can be adjusted for deadline
COP 5994 - Operating Systems
25
Dynamic Real-Time
Scheduling
– Adjusts priorities to changing conditions
– has overhead: must ensure no missed
deadlines
• Priorities are based on processes’
deadlines
– Earliest-deadline-first (EDF)
• Preemptive, always dispatch the process with the
earliest deadline
– Minimum-laxity-first
• Similar to EDF, but bases priority on laxity
scenario: L = 0
scenario: L negative ?
• L = Deadline – (currentTime + timeToComplete)
COP 5994 - Operating Systems
26
Java Thread Scheduling
• threads have priority
– set by programmer
• queue per priority level
– round-robin scheduling
• arriving thread of higher thread preempts
• implemented via
– time slice
– yield operation
COP 5994 - Operating Systems
27
Java Thread Scheduling
COP 5994 - Operating Systems
28
Linux Task Scheduling
• Linux 2.6:
– O(1) scheduler
– scheduling operations run in constant time
– improve scalability because execution time
independent of number of tasks in the
system
• system timer interrupt every 1ms (IA32)
– to update kernel data structure
COP 5994 - Operating Systems
29
Linux Task Priority
• task has static priority
– -20 to 19 (lower number is higher priority)
• scheduling is based on effective priority
– adjusted for execution behavior
• ratio of sleep vs. run time
– task that sleeps more is given higher priority
COP 5994 - Operating Systems
30
Preemptive Scheduler
• variable time slice between 10 and 200ms
– higher priority gets larger time slice
• each task runs until either:
– its time slice expires
– a higher priority process becomes runnable
– the process blocks
• tasks placed in run queue levels for each
priority
– priority array refers to each level sub-queue
– RR scheduling for priority level sub-queue
COP 5994 - Operating Systems
31
Scheduler priority array
COP 5994 - Operating Systems
32
Indefinite Postponement
• each task executes once per epoch
– epoch duration limited by starvation limit
• default: 10 * tasks-in-run-queue seconds
– when starvation limit is reached
• tasks run that have not executed in the epoch
• epoch ends, new epoch starts
– guarantees that low-priority tasks will run
eventually
COP 5994 - Operating Systems
33
Linux Multiprocessor scheduling
• one run queue per processor
– tasks tend to stay on a processor
– advantage: processor cache
• scheduler performs dynamic load
balancing
– attempts to migrate only cache-cold tasks
COP 5994 - Operating Systems
34
Linux Real-time Scheduling
• Soft real-time scheduler
• scheduling classes
– SCHED_FIFO
• FIFO real-time tasks
– SCHED_RR
• RR real-time tasks
– SCHED_OTHER
• as before, non real-time tasks
COP 5994 - Operating Systems
35
Windows XP Thread
Scheduling
• thread dispatcher is part of micro kernel
• 32 Priority levels
– 0 = lowest priority
– 31 = highest priority
– 16 to 31: real-time threads
– 0: zero-page thread for idle-time tasks
• 32 ready queues
• RR for highest-priority ready queue
COP 5994 - Operating Systems
36
Windows XP Priorities
level class
priority class + priority level = thread priority
COP 5994 - Operating Systems
37
Thread Priority changes
– Only for dynamic threads (1-15)
– Priority boosts:
• Exiting the wait state
• Window receives user input
• Has not executed for a long time
– Priority reduction
• Cannot go below base priority
• Reduced by one if thread executes for entire
quantum
• Priority returns to previous level after one quantum
if thread boosted because had not executed for a
long time
COP 5994 - Operating Systems
38
Windows XP Multiprocessor
Scheduling
• Dispatcher considers:
– affinity mask
• processors which may run thread
• less important for SMP
– last processor
• processor on which thread executed last time it
ran
• attempt to preserve processor cache
– ideal processor
• Maximize parallelism
– related threads, different ideal processors
COP 5994 - Operating Systems
39
Agenda for next week:
• Chapter 9
– Memory management
• Read ahead !
COP 5994 - Operating Systems
40