Imprint | Privacy Policy

Mutual Exclusion

(Usage hints for this presentation)

IT Systems, Summer Term 2024
Dr. Jens Lechtenbörger (License Information)

1. Introduction

1.1. Core Questions

  • What can go wrong with concurrent computations as result of race conditions?
  • What mechanisms for Mutual Exclusion (MX) does the OS provide to help?

(Based on Chapter 4 of (Hailperin 2019))

1.2. Learning Objectives

  • Recognize and explain race conditions
  • Explain notions of critical section and mutual exclusion
    • Use mutexes (and monitors) to enforce mutual exclusion
    • Apply and explain MX and cooperation based on monitor concept in Java
  • Explain and apply deadlock prevention and detection
  • Explain starvation as MX challenge

1.3. Retrieval practice

1.3.1. Informatik 1

1.3.2. Recall: Datenmanagement

  • Give examples for dirty read and lost update anomalies.
  • What is a database transaction?
  • What does each of the four ACID guarantees mean?
  • Explain serializability as notion of consistency.

The above is covered in this introduction to transaction processing.


2. Race Condition

  • Race (condition): a technical term

    • Concurrent activities on shared resources

      • At least one activity writes
    • Overall outcome depends on subtle timing differences
      • Missing synchronization, “nondeterminism”, bug
  • Analogy

    Ferrari Kiss

    Ferrari Kiss” by Antoine Valentini under CC BY-SA 2.0; from flickr

    • Cars are activities
    • Street segments represent shared resources
    • Timing determines whether a crash occurs or not
    • Crash = misjudgment = missing synchronization

2.1. Examples for Races Conditions

  • DBMS
    • SQL commands are activities
    • Database objects are shared resources
    • Update anomalies indicate missing synchronization
      • Serializability requires synchronization and avoids anomalies
  • OS
    • Threads are activities
    • Variables, memory, files are shared resources
    • Missing synchronization is a bug, leading to anomalies just as in database systems

2.2. Self-Study Tasks

2.2.1. The Deadlock Empire, Part 1

  • Play “Tutorial 1,” “Tutorial 2,” and the three games for “Unsynchronized Code” at
    • The games make use of C#
      • (Which you do not need to know; the games include lots of explanations, also mouse-over helps)
  • General idea
    • The game is about mutual exclusion and critical sections, to be discussed next
      • At any point in time just one thread is allowed to execute under mutual exclusion inside a critical section
      • If you manage to lead two threads into a critical section simultaneously (or, in some levels, to execute Assert(false)), you demonstrate a race condition
    • You win a game if you demonstrate a race condition
  • Really, start playing now! (Nothing to submit here)

2.2.2. Transfer of Deadlock Empire

Consider the following piece of Java code (from Sec. 4.2 of (Hailperin 2019)) to sell tickets as long as seats are available. (That code is embedded in this sample program, which you can execute to see races yourself.)

if (seatsRemaining > 0) {
   seatsRemaining = seatsRemaining - 1;
} else displaySorrySoldOut();

Inspired by the Deadlock Empire, find and explain race conditions involving the counter seatsRemaining, which leads to “too many” tickets being sold.

2.3. Non-Atomic Executions

  • Races generally result from non-atomic executions

    • Even “single” instructions such as i += 1 are not atomic

      • Execution via sequences of machine instructions
        • Load variable’s value from RAM
        • Perform add in ALU
        • Write result to RAM
    • A context switch may happen after any of these machine instructions, i.e., “in the middle” of a high-level instruction

      • Intermediate results accessible elsewhere
      • Demo: Play a game as instructed previously

3. Critical Sections and Mutual Exclusion

3.1. Goal and Solutions (1/3)

  • Goal
    • Concurrent executions that access shared resources should be isolated from one another
  • Conceptual solution
    • Identify critical sections (CSs)
      • CS = Block of code with potential for race conditions on shared resources
        • Cf. transaction as sequence of operations on shared data
    • Enforce mutual exclusion (MX) on CSs
      • At most one thread inside CS at any point in time
        • This avoids race conditions
        • Cf. serializability for transactions

3.2. MX with CSs: Ticket example

Interleaved execution of threads with MX for code from Sec. 4.2 of book "Operating Systems and Middleware – Supporting Controlled Interaction" by Max Hailperin, CC BY-SA 3.0. image/svg+xml Interleaved execution of threads with MX for code from Sec. 4.2 of book "Operating Systems and Middleware – Supporting Controlled Interaction" by Max Hailperin, CC BY-SA 3.0. 2017, 2018 Jens Lechtenbörger Thread T1 Thread T2 time // T1 enters CS with MXif (seatsRemaining > 0)// T1 preempted// T2 dispatched // T2 tries to enter CS// As T1 in CS, T2 blocked by MX// OS dispatches other thread, say T1 dispenseTicket();seatsRemaining -= 1// T1 finishes, leaves CS// T2 can continue if (seatsRemaining > 0)// T2 finishes

Interleaved execution of threads with MX for code from Sec. 4.2 of book by Max Hailperin, CC BY-SA 3.0.” by Jens Lechtenbörger under CC BY-SA 4.0; from GitLab

3.3. Goal and Solutions (2/3)

  • Refined goal
    • Implementations/mechanisms for MX on CS
  • Solutions, to be discussed in detail
    • Locks, also called mutexes
      • Cf. 2PL for database transactions
      • Acquire lock/mutex at start of CS, release it at end
        • Exclusive “ownership” by one thread at a time
    • Monitors
      • Abstract data type, think of Java class, methods as CS with MX
      • Keyword synchronized turns Java method into CS with MX!
    • (Semaphores, beyond class)
      • Abstract data type, generalization of locks, blocking, signaling

3.4. Challenges

  • Major synchronization challenges arise

    • Programming errors, e.g., races involving seatsRemaining
      • Difficult to locate and reproduce; time-dependent, “non-deterministic”
    • Above solutions restrict entry to CS

      • Thus, they restrict access to the resource CPU

      • Deadlock

        • Set of threads is stuck
        • Circular wait for additional locks/resources/messages
        • Definition, detection, prevention in later presentation
      • Starvation (related to (un-) fairness)

3.5. Goal and Solutions (3/3)

  • Avoid race conditions with MX
    • Recall above loose definition
      • MX = At most one thread inside CS at any point in time
  • Stricter definitions also address deadlocks, starvation, failures
    • Our definition: Solution ensures MX if
      • At most one thread inside CS at any point in time
      • Deadlocks are ruled out
    • (Not our focus: Starvation does not occur)
      • (E.g., requests granted under fairness guarantees such as first-come first-serve or with “luck” based on randomness)
    • ((Lamport 1986) provides detailed discussion, also addressing failures)

4. Locking

4.1. Mutexes



Figure © 2016 Julia Evans, all rights reserved; from julia's drawings. Displayed here with personal permission.

4.2. Locks and Mutexes

  • Lock = mutex
    • Object with atomic methods

      • lock() or acquire(): Lock/acquire/take the object
        • A lock can only be lock()’ed by one thread at a time
        • Further threads trying to lock() are blocked until unlock()
      • unlock() or release(): Unlock/release the object
        • Can be lock()’ed again afterwards

Figure 4.4 of cite:Hai17

Figure 4.4 of cite:Hai17” by Max Hailperin under CC BY-SA 3.0; converted from GitHub

4.3. Use of Locks/Mutexes

  • Programming discipline required to prevent races
    1. Create one (shared) lock for each shared data structure
    2. Take lock before operating on shared data structure
    3. Release lock afterwards
  • ((Hailperin 2019) has sample code following POSIX standard)
  • Ticket example modified (leading to MX behavior):
if (seatsRemaining > 0) {
   seatsRemaining = seatsRemaining - 1;
} else displaySorrySoldOut();

4.4. Quiz on MX Vocabulary

5. Pointers beyond class topics

5.1. GNU/Linux: Futex

  • Fast user space mutex
    • No system call for single user (fastpath)
    • System calls for blocking/waiting (slowpath)
  • Meant as building block for libraries
  • Integer with up() and down()
  • Documentation

5.2. Lock-free Data Structures

5.3. “Safer” Programming Languages

  • High-level programming languages may help with MX
  • See (Jung et al. 2021) for introduction to Rust
    • Strong type system for detection of common bugs at compile time
      • Thread safety (absence of race conditions) for shared data structures with compile-time checks
    • Ongoing research into safety proofs
  • (Besides, the OS Redox is implemented in Rust)

5.4. Massively Parallel Programming

  • For massively parallel (big data) processing in clusters or cloud environments, specialized frameworks exist


Hailperin, Max. 2019. Operating Systems and Middleware – Supporting Controlled Interaction. revised edition 1.3.1.
Jung, Ralf, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. 2021. “Safe Systems Programming in Rust.” Commun. Acm 64 (4): 144–52.
Lamport, Leslie. 1986. “The Mutual Exclusion Problem: Part II—Statement and Solutions.” J. Acm 33 (2): 327–48.
Larus, James, and Christos Kozyrakis. 2008. “Transactional Memory.” Cacm 51 (7): 80–88.
Levandoski, Justin, David Lomet, and Sudipta Sengupta. 2013. “The Bw-Tree: A B-Tree for New Hardware Platforms.” In Icde 2013. IEEE.

License Information

Source files are available on GitLab (check out embedded submodules) under free licenses. Icons of custom controls are by @fontawesome, released under CC BY 4.0.

Except where otherwise noted, the work “Mutual Exclusion”, © 2017-2024 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.