CPU Scheduling

Created

2/5

Threads

Scheduling problem:

  • you have k jobs to run and n>=1 CPUs, which jobs should we assign to which CPU(s) and for how long?
  • schedulable entities are refered to as "jobs," and they can be processes, threads, or people.
  • uses mechanisms like context switch, process state queues.

Scheduling goals:

  • ...

Scheduling "non-goals":

Starvation is when a process is prevented from making process because some other process has the resource it requires.

  • Undesirable
  • Resource could be the CPU or lock (used by readers/writers)
  • Relies on the algorithm to make sure this doesn't happen.
    • e.g., round robin is not an issue in round robin because it's fair
  • What causes starvation?
    • Scheduling
      • high priority process prevents low priority process from running
      • one thread always beats another when acquiring a lock
    • Synchronization
      • e.g., constant supply of readers always blocks our writers
      • It's not necessarily the scheduler's fault

Metrics to measure scheduling by:

  • throughput: # of process that complete per unit of time (high = better). # of jobs / time
    • we care about this for batch scheduling
  • turnaround time: time for each process to complete (lower = better). Tfinish−TstartT_{finish} - T_{start}
  • response time: time from request to first response (lower = better). Tresponse−TrequestT_{response} - T_{request} i.e., the time between waiting to ready transition adn ready to running
    • e.g., key press to echo, not launch to exit
  • Secondary criterias that affect the above
    • CPU utilization: %CPU, fraction of time CPU doing productive work
    • Waiting time: Avg(Twait)Avg(T_{wait}): time that a process waits in the ready queue.

Which measures do systems care about?

  • bath systems: job throughput, turnaround time
    • give each job access to as much resources they need as possible so that they can complete their job
  • interactive systems: response time for interactive job (PC), okay to trade off utilization and throughput.
  • optimize average measure

When are scheduling decisions made?

  • scheduling decisions may take place when a process:
    1. running -> waiting state
    2. running -> ready state
    3. new/waiting -> ready
    4. exits
  • if preemptive: decision is made all four pointsn
  • if non preemptives: only at 1 -> 4

FCFS Scheduling ("First come first-served"): jobs run in the order they arrive

  • limitation:
    • does not optimize for turnaround time / waiting time well
    • non-preemptive in nature, meaning that once CPU time has been allocated to a process, other processes can get CPU time only after the current process has finished or get blocked
      • results in the Convoy effect: longer jobs block shorter job

Scheduling jobs with computation and I/O (waiting for I/O to complete)

  • a scheduling job can improve throughput if both jobs require both computation and I/O
    • scheduling your I/O early so that data that the process needs is ready when the CPU becomes avaiilable
  • CPU is one of the several devices needed by users' jobs. As CPU runs compute jobs, disk drive runs disk jobs.
    • with network, part of the job can run on a remote CPU
  • on a 1-CPU system with n I/O devices.
    • scheduling asymmetric (n+1)-CPU multiprocessor
    • Result: all I/O devies + CPU busy -> (n+1)-fold throughput gain
    • Example: disk-bound grep + CPU-bound matrix_multiply:
      • overlap them just right, and the throughput would be doubled.

Shortest Job First (SJF): choose the job with the smallest expected CPU burst

  • e.g., person with the smallest # of items in shopping cart checks out first
  • has the probably optimal minimal average waiting time (AWT)
  • Two schemes
    • non-preemptive: once CPu given to process, it cannot be preempted until completes its CPU burst
    • preemptive: if a new process arrives with CPU burst length less than remaining time of current executing process, preemptive current process.
      • known as shortest-remaining-time-first (SRTF)
      • say a long one is running, and then a shorter job comes, then you switch process
      • AWT can be shorter
  • Limitations:
    • can lead to unfairness / starvation
      • impossible to know size of CPU burst ahead of time. e.g., choosing person in line without looking in the cart. You could make a reasonable guess though
        • e.g., exponentially weighted average
        • the idea of using the past to predict the near future

Round Robin (RR): each job is given a time slice called "quantum." Preempt job after duration of quantum. When preempted, move to the back of the FIFO queue

  • solution to fairness and starvation
  • advantages:
    • fair allocation of CPU across jobs
    • low average waiting time when job length varies
    • not good for responsiveness if small number of jobs
  • disadvantages
    • context switch are frequent and need to be fast
    • good for varying sized job, but what if they were the same-sized?
      • even of context switches were free, consider the average turnaround time, it would be greater than FCFS.
  • time quantum are selected while factoring:
    • we want a context much larger than the context switch cost
    • majority of bursts should be less than quantum
      • in an I/O process, then you want it to be likely that it completes fully so that it can be done and let the next I/O start.
    • not so large that it reverts to FCFS
    • typically 1-100ms

Linked from Operating Systems