Week 3

Published

April 29, 2025

VL 5 - 28.04.25

Threads

  • Threads are miniprocesses.
  • Main idea: we want concurrency but still retain the recourses of a single process like the data, files and code. (different processes are isolated from each other and don’t share these resources)
  • Multithreading is using multiple such threads in a single process \(\Rightarrow\) They all use the same PCB (they coexist within the same process)
  • Advantages of threads w.r.t processes:
    • simple comunication between threads, they share the same resources, and it’s faster to synhronize them.
      (no system calls, no switching to kernel mode) Shared resources:
      • code
      • data
      • files
    • This makes threads more responsive compared to processes. Different functions of the program can be executed in different threads.
    • Threads are more scalabe compared to processes. (There can be much more threads than processes)
  • two types of threads:
    • user threads: threads are managed within the process itself
    • kernel threads: threads are managed by os globally.
    • how do these two types compare:
      • switching between user threads is faster, but since it is not controlled by the os, a blocking thread can slow down the program, whereas in kernel threads the os would issue an interrupt and switch to the next thread. In user threads the os would switch to another process (and switching between processes is in general quite expensive)
      • Kernel threads: in Multi-Core CPU’s various threads can be distributed among the cores by the us. (not possible in user threads)
  • mixed models:
    • one-to-one
    • many-to-many
    • many-to-one
  • threads: threads share state, which enables faster communication, but introduces multitasking-related difficulties, like race conditions. (shared state is both an advantage and a disadvantage of threads)
  • processes: they are isolated from each other, but this makes the communication difficult
  • POSIX Pthreads: pthread_*. An API for creating, deleting and synchronizing threads. (implementation of APIs exist both as user and kernel threads):
  • race conditions: lost updates \(\Rightarrow\) process synchronization (how to solve such problems)

VL 6 - 30.04.25

Process synchronization:

  • how can data be communicated from one process to another?
  • taking dependencies into account: if B depends on A, i.e. if B receives data from A, than B should wait for A to be done, before executing.
  • Processes / threads shouldn’t disrupt or block each other.

Race Conditions (Continued)

race condition: when multiple threads / processes read or write the same variable an update can be lost if one of the threads is interrupted before completing the update.

  • The producer - consumer problem: (Slide 8)
    • producer: writes to a buffer.
    • consumer: reads from a buffer.
    • problem: count variable is global, therefore an update , either count-- or count++ can get lost, causing count having a wrong final value (Klausurrelevant, Slide 9)
  • Solution: processes or threads should have critical regions where the execution can not be interrupted - other processes or threads are blocked during this time. \(\Rightarrow\) Mutual Exclusion

Mutual Exclusion

  • No two processes / threads can be executing simulatanously in their critical regions. (critical regions exclude each other)
  • A process that is not in its critical region can not block other processes / threads.
  • how is it implemented
    • hardware: a hardware switch (a single bit) is set to 1 when a thread is in its critical region which disables Interrupts.
    • software:
      • primitive solution: a single boolean variable (this allows only two simultanous threads / processes, therefore very limiting) (Slid 17)
      • Peterson’s solution: (slide 19)

General solution:

  • Locks and Lock varaibles
  • Semaphores
Locks

idea: use a token. The ownership of the token means … (Slide 22)

  • hardware solutions:
    • test and set lock - TSL. (Slide 23)
    • instruction swap - XCHG

These solutions are categorizing under active waiting (or spinlocks) \(\Rightarrow\). Problems: * wasting of processor time. * priority inversoin (Prioritaetsumkehr).

Semaphores
  • introduced by Dijkstra in 1965
  • Generalization of locks.
  • two operations:
    • wait()
    • singal()
  • how to implement mutual exclusion with semaphores (slides 29, 30)
  • binary semaphores are also called mutexes.
  • locks can be simulated with semaphores.
  • locks und semaphores (Klausurrelevant, Overview Slide 34, 35)

A Common Situation - Waiting for a Condition / Event

  • Simple solution - Polling: periodically querry the state of a variable in an infinite loop \(\Rightarrow\) inefficient.
  • better solution - efficient waiting: the thread is switched to ‘waiting’ state.