Week 5.b
CS3650
02/07 2024
https://naizhengtan.github.io/24spring/

1. OS scheduling
2. Threads
-----

Recap: True or False

  - each function invocation has a corresponding stack frame.
  - all local variables are located on the stack frames.
  - the first four function arguments are stored on registers.
  - the return value is stored on registers.
  - call-preserved registers are registers that need to be saved by callee
  - caller does not have to save call-clobbered registers if their values are not useful
  - %rax is a call-clobbered register
  - %rsp is a call-preserved register

  Answers:
    all True

 * context switch from last time:

        P1             OS            P2
         |
    [trap to kernel]
         +------------>+
                       |
               [save P1 context]
               [choose P2 to run]
              [restore P2 context]
                       |
                       +------------->+
                                      |
                                     ...
                                [trap to kernel]
                       +<-------------+
                       |
               [save P2 context]
               [choose P1 to run]
              [restore P1 context]
                       |
         +<------------+
         |
        ...

1. OS Scheduling

    High-level problem: operating system has to decide which process (or
    thread) to run.

    A. When scheduling decisions happen:

        [draw process transition diagram]


                                              exit (iv)
                                                +-------->[terminated]
                           (iii) interrupt      |
    [new] -->   [ready]   <--------------    [running]
                  ^       --------------->      |
   I/O completion  \      scheduler dispatch    |
   or signal (ii)   \                 __________|
                     \               /
                      [waiting] <---/ I/O or wait (i)


    scheduling decisions take place when a process:

      (i) Switches from running to waiting state 
      (ii) Switches from waiting to ready 
      (iii) Switches from running to ready state 
      (iv) Exits 

    preemptive scheduling: at all four points

    nonpreemptive scheduling: at points (i), (iv), only (this is the
    definition of nonpreemptive scheduling)

    B. what are the metrics and criteria?

    timeline ----v---------v------------v---->
              arrival  1st execution   completion

    --turnaround time
    time for each process to complete (completion - arrival)

    --waiting/response/output time. variations on this definition,
    but they all capture the time spent waiting for something to
    happen rather than the time from launch to exit.

        --time between when job enters system and starts executing;
        following the class's textbook, we will call this "response time"
        (1st execution - arrival)
        [some texts call this "waiting time"]

        --time from request to first response (e.g., key press to
        character echo)
        we will call this "output time" 
        [some texts call this "response time"]

    --fairness
        different possible definitions:
        --freedom from starvation
        --all users get equal time on CPU
        --having CPU proportional to resources needed
        --etc.

    C. an example scheduling algorithm: 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

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

  To summarize:
    we have learned processes:
     -- a running program
     -- an abstract machine with registers and memory
     -- registers: %rip, %rsp, ...
     -- memory layout: code, data, heap, stack segment
     -- a life cycle of a process: fork/exec/exit
     -- how a process runs (assembly)
     -- stack frame and calling convention


2. Threads

    [Q: ask how many students have used threads]

    Interface to threads:

        tid thread_create (void (*fn) (void *), void *); 
            Create a new thread, run fn with arg

        void thread_exit (); 

        void thread_join (tid thr); 

            Wait for thread with tid 'thr' to exit

      plus a lot of synchronization primitives, which we'll see 
      in the next lecture

    thread vs. process: a frequently asked question
      -- threads share memory, but they have their own "execution context"
      (registers and stack).

    [draw abstract picture of threads in a process:
      own registers, share memory]

    A toy example:

      void f() {...}
      void g() {...}

      int main() {
        thread_create(f, NULL)
        thread_create(g, NULL)
        ...
      }

    --similar to PCB, there is TCB (thread control block)
      --Thread Identifier: Unique id (tid) is assigned to every new thread
      --Stack pointer: Points to thread's stack in the process
      --Program counter: Points to the current program instruction of the thread
      --State of the thread (running, ready, waiting, start, done)
      --Thread's register values
      --Pointer to the Process control block (PCB) of the process that the thread lives on

    [Google uses user-level threads for performance.

        See talk "User-level threads....... with threads."
            by Paul Turner from Google
            https://www.youtube.com/watch?v=KXuZi9aeGTw
    ]

    Question: if you were OS designer, what are you going to do
    if a thread calls fork()?
      [answer: only one thread left in the child process]

    [start from here next time]