1. processes

- an abstraction of a machine

- process manipulation
  -- create process: fork()
    -- why not createProcess()?
  -- fork/exec separation
  -- parent and child
    -- orphan process and zombie process

- process's view
  -- memory
    -- [draw the memory view of a process]
    -- code, data, stack, and heap
    -- in C, what variables are in which memory area?
  -- registers
    -- %rip
    -- %rbp, %rsp
    -- others
  -- file descriptors (defer to later)

- assembly code (x86)
  -- pushq %rax
  -- popq %rax
  -- call 0x12345
  -- ret

- calling convention
  -- where is the arguments and where is the return value
  -- call-preserved & call-clobbered

-- stack frame and how function call works
  -- [saved %rbp; local variables; call-preserved regs; %rip]
  -- how it works?


-- process-kernel interaction
  -- system calls
  -- exceptions
  -- interrupts


-- system calls
  -- an interface between processes and kernels
  -- how to know a systems call's function?
    -- man 2 <syscall>
  -- important system calls:
    -- fork, execve, wait, exit
    -- open, close, read, write
    -- pipe, dup2
  -- (briefly) how syscall is implemented


-- file descriptors
  -- an abstraction: a file, a device, or anything that follows open/read/write/close
  -- 0/1/2: stdin/stdout/stderr
  -- redirection and pipe


-- shell
  -- an interface between human and computer
  -- how it works; Lab2
    -- parse commands
    -- run commands (fork/exec)
    -- handle shell operators
      -- redirections
      -- pipe
      -- connecting ops (;, &&, ||)
      -- subshell

-- threads
  -- two threads in the same process share memory
     -- meaning: they share code segment, data segment (i.e., global
        variables), and heap (i.e., memory from malloc)
  -- threads have separate stack and registers


2. Concurrency

-- thread APIs
  -- thread_create(function pointer, args)
  -- thread_exit()
  -- thread_join(thread id)

[draw the dangerous concurrency world with a safe path]

-- safe path: how to write concurrency code
  -- a systematic way to address concurrency problem
    -- this is one way, but is a good way, probably the best way that we're aware of

  -- Monitor (mutex + condition variable)
  -- 6 rules from Mike Dahlin
    -- memorize them!
  -- four-step design approach


  -- Mutex: providing mutual exclusion
    -- APIs
      -- init(mutex)
      -- acquire(mutex)
      -- release(mutex)
    -- providing a critical section
      -- entering c.s.: "I can mess up with the invariant"
      -- leaving c.s.:  "I need to restore the invariant"


  -- Condition variable: providing synchronization scheduling
    -- APIs
      -- cond_init(cond)
      -- cond_wait(cond, mutex)
      -- cond_signal(cond)
      -- cond_broadcast(cond)
    -- an important interface, cond_wait(...)
      -- meaning: 2 steps,
         (1) unlock mutex and sleep (until cond signaled)
         (2) acquire mutex and resume executing


  -- other synchronization primitives
    -- semaphore
    -- barrier
    -- spinlocks
    -- reader-writer locks
    -- read-copy-update (RCU)
    -- deterministic multithreading


-- dangerous concurrency world: concurrency problems

  -- if not sequential consistency
    -- hard for human beings to understand
    -- cases in handout week3.b panel 4

  -- concurrency problems under sequential consistency

    -- no synchronization:
      -- multiple threads working on some shared state
      -- atomicity-violation (race conditions) 
         [examples: linked list and producer/consumer in handout week3.a]
      -- order-violation

    -- with incorrect synchronization
      -- deadlock
        -- well-studied problem (and intellectually challenging!)
        -- four conditions
        -- solutions
      -- livelock
      -- starvation
      -- priority inversion


3. Scheduling


-- OS scheduling problem
  -- kernel needs to decide which process to run
  -- when does kernel need to make this decision?
    -- process state transition graph
       (ready, running, waiting, terminated)
    -- non-preemptive scheduler: running->terminated or running->waiting
    -- preemptive scheduler: all four transitions
  -- scheduling another process
    -- context switch
    -- it has a cost

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

-- CS5600 scheduling game
   -- multiple processes: P1, P2, P3, ...
     -- each with arrival time and running time
   -- 1 CPU
   -- ignore context switch costs
   -- assume no I/O
   -- note: processes arrive at the beginning of each time slot

-- six classic scheduling algorithms
  -- FIFO/FCFS
  -- SJF/STCF
  -- RR
  -- Priority
  -- MLFQ
  -- Lottery

-- beyond our scheduling game
  -- incorporating I/O into scheduling
  -- predicting future (simulating SJF/STCF)
  -- complicated scheduling in practice (Reconfigurable Machine Scheduling Problem)
  -- scheduling has a lot to do with others factors, for example, mutex


notes about exam
---

- NOTE: bring your id
  --because you need to write down your NUID

- a lot to read, not much to write

- a lot of code
  -- don't panic
  -- most lines are not important. They are there for completeness reasons.
  -- only several lines matter.

- 12 pages; A4; one-sided
  -- stapled
  -- feel free to disassemble (easier to read code and answer questions)
  -- if you do so, remember to fill in your name and NUID in the bottom of each page


- you will need to write code on paper
  -- we tolerate minor syntax errors
  -- you can always write down your assumptions

- you don't have to remember the "jargons"
  -- but you do need to remember "common terms"
  -- how to distinguish the two?
    -- Imagine you're a programmer. When you talk to your peers, are you
       comfortable to say the words without explanation?
    -- "connecting input and output of two commands? Use pipe."
       (most people are okay with this.)
    -- "try to predict the future? Use EWMA."
       (most people are not okay with this; EWMA means exponentially weighted
       moving average btw.)


[broadcast the first page of the midterm
 leak some information, but that's fine.]

Q&A
---

Exam related:
  Both material and Labs

Content related:
  Only material; no Labs