1 Scheduling

• 2 main focuses:
  • Mechanism
  • Policy

1.1 Mechanisms

The mechanism for scheduling is how we actually switch from process to process. This problem has several solutions:

1. We can use yield() for cooperative multitasking.
   • yield() has same side effects as nop from the thread’s perspective, except that it tells the kernel to schedule another thread.
   • in linux, any syscall with no side effect (getpid()) does this
   • to use yield(), we must change the busy wait code:
     while(!ready(d)){  
       continue;  
     }

     into the polling approach:

     while(!ready(d)){  
       yield();  
     }

   • Problems:
     • Uncooperative processes can take over the CPU.
     • We could write compilers that insert yield() into your code automatically, but they aren’t very good at it.
   • Solution:
     • linux approach: Make the virtual machine insert a syscall every 1 000 000 instructions or so.
2. Preemptive Scheduling (linux solution)
   • The motherboard sends signal via bus to CPU.
   • The CPU traps.
   • We enter the kernel as though we called int.
   • Pros:
     • no runaway processes
     • we don’t have to add yield() to our code.
   • Cons:
     • complicates the critical section, which we will approach later.
     • doesn’t entirely solve infinite loop problem as process continues to run(though not taking up all of CPU).

• what’s our mechanism if we have say, 8 cores and 100 processes?
• does mechanism change with hardware?
  • multiple timer interrupts (1 for each core)
  • need to make sure a process isn’t running on multiple cores
  • mechanisms fundamentally the same

1.2 Policy

Policy dictates which process we choose to run when the kernel is asked to schedule a new process, either by the cooperative or preemptive mechanism. To construct a well thought-out policy, we must address the following long, medium and short term issues:

• long term
  • which processes will be admitted in the first place?
  • if we let anybody run, we will eventually be swamped.
  • the question of whether or not we want to make a new process gets asked every time we fork.
• medium term
  • 100 processes, each requiring 1G of RAM
  • we only have 8G of RAM
  • which processes’ memories do we keep in RAM vs on disk?
• short term (dispatcher)
  • if # of runnable processes > # of CPUs, which processes get CPU time?
  • we will be focusing on this in the lecture

Generally, we can have two main policy approaches when dealing with realtime scheduling:

• hard realtime scheduling (i.e. braking system in a car)
  • hard deadlines. cannot miss.
  • if we can’t schedule in hard realtime, it is an error as grave as OS crashing.
  • predictability is everything (more important than performance)
  • generally avoid timer interrupts here. they lend to unpredictability.
  • no blocked processes. use polling/busy waiting instead.
  • turn off cache. cache misses are not predictable.
  • turn off virtual memory.
• soft realtime scheduling (i.e. video playback)
  • some deadlines can be missed (there is a cost, but it’s not that big of a deal)
  • our focus for today

• Soft Realtime Scheduling Algorithms
  • Benchmark techniques:
    
    Schedulers are generally bad. In order to choose the right one, we need to compare different scheduling algorithms. To do so, we need metrics. We will refer to the following diagram for terms as to which times we use for metrics:
    •  
         +---+ +------------------------------------+  
         +---+-+------------------------------------+--+  
         ^   ^ ^                  |                 ^  
         |   | |                  |                 |  
         |   | |                  |                 |  
         |   | +------+execute    +1st output       +  
         |   |                                  finish  
         |   |  
         |   |  
         |   +end of prev  
         |  
         +  
         arrival

    • wait time = execute - arrival
    • response time = 1st output - arrival
    • context switch time = execute - end of prev
    • turnaround time = finish - arrival

    Each of the detailed times (wait time, response time, etc.) is a time measured from the point of view of a job. We often look at aggregates of these individual statistics such as average wait time, or worst case turnaround time, when judging the quality of a scheduler.

    There is another set of metrics that we can use to look at the quality of a scheduler. These look from the point of view of the scheduler, or the entity scheduling the jobs:

    • utilization - percent time spent doing useful work
    • throughput - number of jobs per second going through the system
    • fairness - all jobs will eventually finish

    Many of our goals for making the scheduler better are at odds. Making one better can make others worse. For example, improving utilization can lead to an unfair scheduler; improving the worst case of a time metric may take a toll on the average case of said metric.

  • First Come First Serve
    • fair
    • large average turnaround time

    • Job	arrival time	runtime	wait time	turnaround
      A	0	5	0	5
      B	1	2	4 + δ	6 + δ
      C	2	9	5 + 2δ	14 + 2δ
      D	3	4	13 + 3δ	17 + 3δ
      average			5.5 + 1.5δ	10.5 + 1.5δ

    • δ is context switch time
  • Shortest Job First
    • not fair
    • long jobs can starve
    • run times need to be known in advance
    • average wait time is less
    • average turnaround time also goes down as many processes with shorter runtimes are executed quickly.
  • First Come, First Serve +preemptive scheduling
    • better match for interactive systems
    • every Δt, interrupt, put current process at end of queue and switch to first in line.
    • better wait times
    • reduced utilization (more context switching)
    • longer average run time + turnaround time
  • Priority Based Scheduling
    • real world os has combinations of many types of scheduling.
    • os has job classes with priority levels.
    • jobs w/ higher priority levels always win.
    • two kinds of priority:
      • external (set by user, niceness in linux)
      • internal (set by scheduler)
    • priority is a function of external and internal priority, which takes into account which process showed up first, which costs more to run and many other factors.
    • SJF, and FCFS are just priority based schedulers with specific functions.