Intro to OS

Notes for EECS482.

Process, Thread

Process

• A process contains the state for a program to run.
• Process has its own virtual memory, CPU, open files.
• Process and Program: when a program runs, it becomes a process
• A process has memory (code, data, executing stack), Program Counter (PC),
  some registers, some OS resources (open files, network connections)

Thread

• Thread defines a sequence of execution stream.
• Thread has it own PC, SP, Registers

Relationship

• A thread is bound to a process.
• A process can have many threads.
  • Sometimes interact, sometimes work independently

Per-thread State

• Each thread has its own PC, SP,
• The Data Segment (Heap + Static variables) is shared

---

Synchronization

• Atomic actions are the unit of interleaving.
• Controlling how events from different threads can interleave is called synchronization.
• Mutual exclusion
• Critical section
  • Mutual exclusion: Safe
  • Progress: Liveness
  • Bounded waiting: Liveness
  • Performance
• Busy waiting: consumes CPU while waiting.
• Lock (Mutex)
  • Lock: acquire the lock atomically. Or blocked and consume no CPU.
  • Unlock: release the lock.

---

Mutex

• Safe State: respect the invariant.
  • For the list, each node appears once, and the last node points to null.
• Fine-grained Locking
  • One lock per node.
  • Hand-over-hand Locking.
• Ordering constraints.
  • Wait (atomic)
    • Release
    • add to the waiting list
    • go to sleep
  • Wake using signal (wake up one waiting thread), boardcast (wake up all).
  • Always wait in a while loop!

---

Monitor

• A monitor = a lock + CV
• Mesa / Hoare Monitor (less popular).
• Use one CV for each before-after condition.
• Better signal() before unlock().
• Producer and Consumer (bounded buffer).
  • Coke Machine with monitors
    • Shared state: numCokes <- cokeLock
    • Before-After CV: waitingConsumers waitingProducers
• Signal vs. Boardcast
  • Use signal when both are true:
    • Only one waiting thread makes progress.
    • Any waiting thread can be that thread.

Semaphores

• Main Functions
  • down(): wait for semaphore value to become positive, then decrement semaphore value by 1.
  • up() increment semaphore value by 1.
• Binary Semaphores
  • Semaphore value is 0 or 1.
  • up() atomically sets value to 1.
• Must not hold “lock” (semaphore) when calling down() for ordering.

---

Build a thread

so far is about the concurrency

• non-running thread
  • a paused execution
  • context switch
• Thread control Block
  • In memory
  • meaningful only when the thread is not running
• States about a thread
  • New, Running, Blocked, Terminated, Ready
  • State Queues
• Thread return control to CPU
  • Internal events,External events
• Interrupt Vector Table (IVT)
  • Hardware: how
  • OS: what

---

Switching Threads

• CPU perform the steps
• The OS is trusted to do correctly
• Create a new thread:
  • Allocate TCB
  • Allocate Stack
  • Init TCB
  • Add TCB to a ready queue

---

Implement Lock and Unlock

• Atomicity on uniprocessor
  • Unsafe to run user code with interrupts disabled
  • Thread must leave interrupts disabled when calling switch
• Switch invariant
  • All threads promise to have interrupts disabled when calling switch
  • All threads can assume that interrupts are “still” disabled when switch returns

Dead Lock

• Four conditions
  • Limited resources
  • Hold and Wait
  • No Preemption
  • Circular Wait

Address Space

MMU (Per CPU)

• Speed, Size, Flexibility
• Two mechanisms
  • Base and Limit
  • Segmentation