5. Scheduling

• Resources fall into two classes:
  • preemptible: can take resource away, use it for something else, then give it back later. Example: processor or I/O chanel.
  • Non-preemptible: once given, it can't be reused until thread gives it back. Example: file space.
• OS makes two related kinds of decisions about resources:
  • Allocation: who gets what. Given a set of requests for resources, which processes shoulc be given which resources to make most efficient use of the resources?
  • Scheduling: how long can they keep it. When more resources are requested than can be granted immediately, in which order should the requirests be serviced? Examples are processor scheduling (one processor, many threads), memory scheduling in virtual memory systems.

 

Simple Scheduling Algorithms

• First-come-first-served (FCFS) scheduling (also called FIFO or non-preemptive):
  • Keep all of the ready threads in a single list called the ready queue.
  • When a thread becomes ready, add it to the back of the ready queue.
  • Run the first thread on the queue until it exits or blocks.
• Solution: limit maximum amount of time that a thread can run without a context switch. This time is called a time slice.
• Round robin scheduling: run thread for one time slice, then return to back of ready queue. Each thread gets equal share of the cores.
  • Typical time slice value: 10 ms
• How do we decide whether a sheduling algorithm is good?
  • Minimize response time.
  • Use resources efficiently:
    • Full utilization: keep cores and disks busy
    • Low overhead: minimize context switches
  • Fairness (distribute CPU cycles equitably)
• Is round-robin better than FCFS?
• Optimal scheduling: SRPT (Shortest Remaining Processing Time)
  • Run the thread that will finish most quickly, run it without interruptions.
  • Another advantage of SRPT: improves overall resource utilization.
    • Suppose some jobs CPU-bound, some I/O-bound.
    • SRPT will give priority to I/o-bound jobs, which keeps the disks/network as busy as possible
• Key idea: can use past performance to predict future performance.
  • Behavior tends to be consistent
  • If a process has been executing for a long time without blocking, it's likely to continue executing.

 

Priority-Based Scheduling

• Priorities: most real schedulers support a priority for each thread:
  • Always run the thread with highest priority.
  • In case of tie, use round-robin among highest priority threads
  • Use priorities to implement various scheduling policies (e.g. approximate SRPT)
• Multi-Level Feedback Queues: attacks both efficiency and response time problems.
  • One ready queue for each priority level.
  • After blocking, thread starts in highest priority queue
  • If it reaches the end of its time slice without blocking it moves to the next lower queue.
  • Sometimes, lower-priority queues have larger time slices
  • Result: I/O-bound threads stay in the highest-priority queues, CPU-bound threads migrate to lower-priority queues
  • What are the problems with this approach?
• 4.4 BSD scheduler (for first project):
  • Keep information about recent CPU usage for each thread
  • Give highest priority to thread that has used the least CPU time recently.
  • Interactive and I/O-bound threads will use little CPU time and remain at high priority.
  • CPU-bound threads will eventually get lower priority as they accumulate CPU time.

 

Multiprocessor Scheduling

• Simple approach:
  • Share the scheduling data structures among all of the cores
  • one dispatcher per core
  • Separate timier interrupts for each core
  • Run the k highest-priority threads on the k cores.
  • When a thread becomes runnable, see if its priority is higher than the lowest-priority thread currently running. If so, preempt that thread.
• Problems/issues for multiprocessors:
  • Contention:
    • With lots of cores, system will bottleneck on the central ready queue.
    • Solution: separate ready queue per processor; balance queues over tiem (work stealing).
  • Core affinity:
    • Once a thread has been running on a particular core it is expensive to move it to a different core (hardware caches will have to be reloaded).
    • Multiprocessor schedulers typically try to keep a thread on the same core as much as possible.
  • Gang scheduling:
    
    • If the threads within a process are communicating frequently, it won't make sense to run one thread without the others: it will just block immediately on communication with another thread.
    • Solution: run all of the threads of a process simultaneously on different cores, so they can communicate more efficiently.
    • This is called gang scheduling.
    • Even if a thread blocks, it may make sense to leave it loaded on its core, on the assumption that it will unblock in the near future.

 

Summary

• 자원은 두 가지 state 중 하나를 가진다. (non-preemptible: 한 thread가 자원을 가지면 이를 반환할 때까지 다른 thread는 재사용할 수 없다, preemptible: 그 외)
• OS는 자원에 관해 두 가지 관련된 결정을 한다. (allocation, scheduling)
• FCFS, Round robin, SRPT (Shortest Remaining Processing Time), priority-based scheduling
• Multiprocessor scheduling (core간에 scheduling을 공유, 같은 priority queue에서 실행시킬 thread를 뽑음)
• Thread간 communication이 빈번하게 일어날 때 해당 thread들을 동시에 실행시키는 것을 gang scheduling 이라 한다.
• Scheduling algorithm은 process의 결과에 영향을 미치지는 않지만 system의 효율과 반응 시간에 영향을 준다.