Week 6.b
CS 5600
10/15 2021

On the board
------------
1. Last time
2. Scheduling disciplines
    FIFO
    SJF
    RR
    Prio
    MLFQ
    Lottery
3. Vote for your favorite scheduling algorithm

-----------------------------------------------

1. Last time

  - intro to scheduling
    -- OS + scheduling
    -- deciding when to schedule which processes/threads

  - process status
    -- new, ready, running, waiting, terminated
    -- preemptive and non-preemptive scheduling

  - scheduling algorithms metrics
    -- turnaround time
    -- response time
    -- fairness

  - scheduling (context switch) has a cost
    -- (but we will ignore it if scheduling is infrequent)


2. Scheduling disciplines

    - scheduling game:
      -- multiple processes: P1, P2, P3, ...
        -- each with arrival time and running time
      -- 1 CPU
      -- ignore context switch costs, unless happening too frequently
      -- assume no I/O
         (Completely unrealistic but lets us build intuition, as a warmup.)
      -- scheduling output:
         a sequence of scheduling decisions

    - let's do some intellectual exercises!


    A. FCFS/FIFO

    --run each job until it's done

    --a case:

        process    arrival       running
        P1          0              24
        P2          0+\epsilon     3
        P3          0+2\epsilon    3

    --[ P1         P2  P3 ]

    --throughput: 3 jobs / 30 seconds = .1 jobs/sec

    --average turnaround time?
        (24 + 27 + 30) / 3 = 27

    --average response time?
       (0 + 24 + 27) /3 = 17

    --observe: scheduling P2,P3,P1 would drastically reduce average
    turnaround time

    --advantages to FCFS:
        --simple
        --no starvation
        --few context switches

    --disadvantage:
        --short jobs get stuck behind long ones


    B. SJF and STCF

      --SJF: shortest job first
            Schedule the shortest job first

      --STCF: shortest time-to-completion first
         preemptive version of SJF: if job arrives that has a shorter
         time to completion than the remaining time on the current job,
         immediately preempt CPU to give to new job

      --idea:
        --get short jobs out of the system
        --big (positive) effect on short jobs, small
          (negative) effect on large jobs

    --example:

        process      arrival     running
        P1              0            7
        P2              2            4
        P3              4            1
        P4              5            4

        preemptive:
        0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
        P1 P1 P2 P2 P3 P2 P2 P4 P4 P4 P4 P1 P1 P1 P1 P1

    --Question: what is the average turnaround time?
      Answer: (16 + 5 + 1 + 6) / 4 = 7

    --Question: what is the average response time?
      Answer: (0 + 0 + 0 + 2) / 4 = 0.5

    --defer advantages and disadvantages to after we introduce
      relaxation of "no I/O" assumption

    let's decide we also care about response time (as defined by our
    book: duration between when a job arrives and when it is first
    scheduled.)

    C. Round-robin (RR)

    --add timer

    --preempt CPU from long-running jobs. per time slice (also called quantum)

    --after time slice, go to the back of the ready queue

    --most OSes do something of this flavor (see MLFQ below)

    -- notice that our office hours use RR!

    --example:
        (with slice of 1 unit of time)
        process      arrival     running
        P1              0            50
        P2              0            50

    --schedule:
       P1 P2 P1 P2 ...

    --average turnaround time:
      (99+100) /2 = 99.5

    --Question: average response time:
      (0+1) / 2 = 0.5

    --advantages:

        --fair allocation of CPU across jobs
        --low average response time when job lengths vary
        --good for output time if small number of jobs

    --disadvantages:

        --what if jobs are same length?
        --in the example: 2 jobs of 50 time units each, a slice of 1
        --average turnaround time: 100 (vs. 75 for FCFS)

    --how to choose the slice size?

        --want much larger than context switch cost

        --pick too small, and spend too much time context switching

        --pick too large, and response time suffers (extreme case:
        system reverts to FCFS)

        --typical time slice is between 10-100 milliseconds. context
        switches are usually microseconds or tens of microseconds
        (maybe hundreds)

    D. Priority

    --priority scheme: give every process a number (set by
    administrator), and give the CPU to the process with the highest
    priority (which might be the lowest or highest number, depending
    on the scheme)

    --can be done preemptively or non-preemptively

    --example:

        process      arrival     running
        P1 (high)       0            10
        P2 (low)        0            5

    --schedule:
       P1 then P2
    --turnaround time:
      (10 + 15) / 2 = 12.5
    --response time:
      (0+10) / 2 = 5

    --if we swap the priorities on P1 and P2 (P2 is high; P1 is low)
      --turnaround time: (5+15) / 2 = 10
      --response time: (0+5) / 2 = 2.5

    --generally a bad idea to use strict priority because of
    starvation of low priority tasks.

        (--note: SJF is priority scheduling where priority is the
        predicted next CPU running time )

    --solution to this starvation is to increase a process's
    priority as it waits

    E. Multi-level feedback queue (MLFQ)

      -- combine RR and Priority

        three ideas:

        --*multiple queues, each with different priority*. 32
        queues, for example.

        --round-robin within each queue (flush a priority level
        before moving onto the next one). 

        --feedback: process's priority changes, for example based on
        how little or much it's used the CPU
          --you can design different feedback mechanisms
          --one example: "downgrade" a process after 5 unit of time running

        example:
          (with slice of 1 unit of time; 
          5 units of time to change priority, i.e., "downgrade")

          process      arrival     running
          P1              0            10
          P2              0            10
          P3              10           10

        schedule:
          P1 P2 P1 P2 ... (P3 arrive; P1/2 to low) P3 P3 P3 P3 P3 (P3 to low) P1 P2 P3 ...

        advantages:
        --approximates STCF

        disadvantages:
        --can't donate priority
        --not very flexible
        --not good for real-time and multimedia
        --can be gameable: user puts in meaningless I/O to keep job's
        priority high

    see OSTEP (chap 8) for details

    F. Lottery and stride scheduling

    [citations:

    C. A. Waldsburger and W. E. Weihl. Lottery
    Scheduling: Flexible Proportional-Share Resource Management.
    Proc. Usenix Symposium on Operating Systems Design and
    Implementation, November, 1994.
    http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspurger.pdf

    C. A. Waldsburger and W. E. Weihl.  Stride Scheduling:
    Deterministic Proportional-Share Resource Management.
    Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for
    Computer Science, June 1995. 
    http://www.psg.lcs.mit.edu/papers/stride-tm528.ps

    Carl A. Waldspurger. Lottery and Stride Scheduling:
    Flexible Proportional-Share Resource Management, Ph.D.
    dissertation, Massachusetts Institute of Technology,
    September 1995. Also appears as Technical Report
    MIT/LCS/TR-667.
    http://waldspurger.org/carl/papers/phd-mit-tr667.pdf
    ]

    Issue lottery tickets to processes 
    -- Let p_i have t_i tickets 
    -- Let T be total # of tickets, T = \sum t_i
    -- Chance of winning next slice is t_i / T
    -- Note lottery tickets not used up, more like season tickets

    --example
        (with slice of 1 unit of time)
        process      arrival     running
        P1 (t_1=20)    0            20
        P2 (t_2=10)    0            10

    --schedule
      (many possibilities; for example, P2 P2 P2 P2 ... P1 P1 P1 ...)

    --Question: expected turnaround time for (P1, P2):
       A. (20, 30)
       B. (30, 20)
       C. (30, 30)

       Answer: C
       expected turnaround time = (running time) / (expected running time in each slice)
       P1: 20 / (20/30) = 30
       P1: 10 / (10/30) = 30


    controls long-term average proportion of CPU for each
    process

    can also group processes hierarchically for control
        --subdivide lottery tickets
        --can model as currency, so there can be an exchange
        rate between real currencies (money) and lottery tickets

    --lots of nice features

        --deals with starvation (have one ticket --> will make
        progress)

        --don't have to worry that adding one high priority job will
        starve all others

        --adding/deleting jobs affects all jobs proportionally (T
        gets bigger)

        --can transfer tickets between processes: highly useful if a
        client is waiting for a server. then client can donate
        tickets to server so it can run.

        --note difference between donating tix and donating
        priority. with donating tix, recipient amasses enough
        until it runs. with donating priority, no difference
        between one process donating and 1000 processes donating

    --many other details

        --ticket inflation for processes that don't use their whole
        slice

        --use fraction f of slice; inflate tix by 1/f until it
        next gets CPU

    --disadvantages

        --latency unpredictable

        --expected error somewhat high 

        --for those comfortable with probability: this winds up
        being a binomial distribution. variance n*p*(1-p) -->
        standard deviation \proportional \sqrt(n),
            --where:
            p is fraction of tickets owned
            n is number of quanta

    --in reaction to these disadvantages, Waldspurger and Weihl
    proposed *Stride Scheduling*

        --basically, a deterministic version of lottery scheduling.
        less randomness --> less expected error.

        --see OSTEP (chap 9) for details


3. Vote for your favorite scheduling algorithm

   Candidates: FIFO, STCF, RR, Prio, MLFQ, and Lottery

   Winners:
     (with vote counts)

     "Best Turnaround Time" winner: STCF (22)

     "Best Response Time" winner:   RR (24)

     "Best Fairness" winner:        RR (11) and MLFQ (11)

     "Most popular algorithm" winner: MLFQ (15)


   cheng's choices:

     "Best Turnaround Time" winner: STCF
     "Best Response Time" winner:   RR
     "Best Fairness" winner:        Lottery
     "Most popular algorithm" winner: Lottery