______ Operating Systems (CS 273 (OS), Fall 2019)
Home
>>    




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

    Note that there are actually three levels of scheduling in a batch system
    • 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
    Also, scheduling of cluster jobs is a prominent research question, related to OS batch scheduling.

  • 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 undesirable

    • Behavior 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.




rab@stolaf.edu, December 1, 2019