Process

• Process is a container of the resources that a running program needs:
  • Stored registers
  • Virtual memory
  • File descriptors
  • Scheduler state
  • Potpourri: timer state, umask, etc.
• Process states:
  • Running: either user or kernel mode
  • Blocked: kernel mode
    • Waiting for IO events
    • Sleep for an amount of time
  • Runnable: kernel mode
• Memory layout:
  • stack >< heap, uninitialized data (bss, block starting symbol), initialized data, text
  • Why separate bss and init data?
    • init data needs to be stored in program binary file
    • while bss variables just need their sizes to be stored ⇒ doesn’t take up space in binary file

Thread

• Schedulable registers, unit of execution
• Why threads?
  • Shared access to data structures: imagine a game that contains many objects
  • Responsiveness: handle events, callbacks, etc.
  • Multiprocessor advantages
• Thread cancellation is difficult:
  • 2 kinds: immediate or deferred (only safe way)
  • Consider locks, garbage (memory) collect, data structure consistency, etc.
• Race condition:
  • outputs depend on execution sequence
  • Use synchronization mechanism to prevent
• In Linux:
  • thread memory…???

Synchronization

• Disclaimer: modern memory is weird
  • Attempt to coalesce potential redundant IO operations
  • Memory barrier instructions for multiprocessor support
  • “Textbook” mutex memory does not account these
• 2 approaches:
  • atomic sequence: For short instruction sequences with low collision probability
  • voluntary descheduling

Critical section requirements

• Mutex
• Bounded waiting: waiting time bounded by the number of entries by others
• Progress: choosing protocol must be bounded

Progress guarantees

Algorithms can be further put into a hierarchy based on how strong they guarantee about progress: