Operating Systems
CS 273 (OS), Fall 2019
Preliminaries
Compute-bound vs IO-bound processes
Batch, interactive, real time
Policy vs mechanism
- preemption
Goals for scheduling:
General
- Fairness
- Policy enforcement
- Balance
Batch
- Throughput
- Turnaround time
- CPU utilization
Interactive
- Response time
- Proportionality: agreement with user's perception of how long an operation should take
Real-time
- Meet deadlines
- Predictability
Some algorithms
Batch
FCFS
- Advantages: Simple
- Disadvantages: Without preemption, compute-bound processes will cause great delays in I/O-bound processes
SJF
- Advantages: Lowest possible mean turnaround time, assuming all jobs arrive at once
- Disadvantages: Jobs must predict running time
Shortest time remaining next
- Advantages: New short jobs get good service
- Disadvantages: Jobs must predict running time
- Admission scheduler: determine which jobs will be scheduled
- Memory scheduler: which jobs resident in memory vs. swapped
out
Determines degree of multiprogramming - CPU scheduler: running vs. runnable vs. blocked
Interactive
Round-robin
- Each process is assigned a quantum of time; processes take turns in a fixed order executing their quanta, then context switch to another process
- Tradeoff: length of quantum vs. overhead of context switches and scheduling
- Advantages: Simple
- Disadvantages: No way to give some processes preference over others
Priority
- Assign processes priorities according to criteria such as urgency, importance, strategic value.
- To prevent high-priority processes from hogging all the CPU time, use modifications such as temporarily reducing priority value after a time slice.
- Can implement each priority class as a queue, and use round robin within each queue
- Advantages: Supports policies such as meeting real-time deadlines. Can lead to better overall system performance, e.g., if I/O-bound processes receive higher priority, they can do their work quickly when I/O arrives rather than waiting for several compute-bound processes to complete their time slices.
- Disadvantages: May be tricky to implement mechanisms well (e.g., CTSS <CR>s). Priority values have indeterminate relative values.
- Priority scheduling frequently appears as part of a scheduler's policy
Shortest process next
- Adaptation of SJF to scheduling of interactive processes: estimate the next expected running time in terms of prior experience.
- (Aging) For example, if T0, T1, T2, ... are actual runtimes of a
particular process for its time slices 0, 1, 2, ..., then Tn
might be estimated by the sum
1 1 1 1 Tn ~ - Tn-1 + - Tn-2 + - Tn-3 + ... + --- T0 2 4 8 2^n
This running sum (truncated) is easily computed using binary shifts and adds. Recent values of Ti have high influence; an unusual value eventually becomes insignificant. - Advantages: Easy to implement; approximates SJF, which would offer optimal performance; responds dynamically to new trends in Ti.
- Disadvantages: Unpredictable scheduling order (e.g., consider realtime guarantees).
- The attractive aging idea is also used in other OS contexts. Appears in some OS's, e.g., Linux
Guaranteed scheduling
- Adopt a fairness policy, e.g., that each of n processes should receive about 1/n of the CPU time
- Advantages: Seems like a fair policy
- Disadvantages: Often difficult to implement well
- Could adopt other notions of fairness, e.g., divvy up CPU time equally among users (who may have multiple processes) instead of among processes
Lottery
- Provide processes with "lottery tickets" for resources, viz., CPU time. Scheduler chooses a lottery number at random to determine next process to be scheduled. In the long run, your share of CPU is proportional to number of lottery tickets you have.
- Advantages: Simple implementation of a fairness policy. Responsive (new processes with tickets have chance for immediate service). Tickets may be traded, e.g., sender giving tickets to receiver of a message, for better performance. Readily solves some otherwise difficult scheduling problems (e.g., I/O devices that operate at different rates).
- Disadvantages: Desired proportion of performance is left to chance -- e.g., there could be a bad run where a critical process doesn't get enough CPU to meet a requirement.
Realtime systems
Hard deadlines: must absolutely be met.
Soft deadlines: occasional missed deadline is tolerable, though undesirableBehavior of all processes must be predictable.
Periodic vs. aperiodic occurrences of events
A schedulable realtime system: possible to meet time deadlines.
Static (set at initialization) vs. dynamic (decided at runtime) scheduling algorithms.