Concurrency, Synchronization, and Interprocess Communication

Introduction and Context

Modern operating systems support many activities at the same time: a browser may render a page while downloading data, a database may serve several clients, and an AI application may preprocess data while a model performs inference. These activities are described as concurrent when their executions overlap in time. On a single processor, concurrency is achieved by rapidly switching between tasks; on a multicore processor, tasks may also execute truly in parallel.

Concurrency improves responsiveness, throughput, and resource utilization, but it introduces risks. When multiple threads or processes access shared data, the result may depend on the precise timing of execution. Such timing-dependent failures are difficult to reproduce and diagnose. Operating systems therefore provide synchronization mechanisms and communication abstractions that allow programmers to coordinate execution safely and efficiently.

This chapter examines critical sections, mutual exclusion, mutexes, semaphores, monitors, condition variables, atomic operations, message passing, pipes, shared memory, sockets, and lock-free programming. The discussion applies to operating-system services, server software, databases, distributed applications, and AI/ML workloads.

Learning Objectives

After studying this chapter, students should be able to:

1. Distinguish concurrency from parallelism and identify common concurrency hazards.

2. Explain the critical-section problem and its correctness requirements.

3. Select and use mutexes, semaphores, monitors, condition variables, and atomic operations.

4. Compare shared-memory and message-passing models of interprocess communication.

5. Explain pipes, shared memory, and sockets and identify suitable applications for each.

6. Analyze deadlock, starvation, livelock, race conditions, and priority inversion.

7. Describe lock-free concepts and the role of atomic read-modify-write operations.

8. Apply synchronization principles to a realistic concurrent system.

1. Concurrency, Parallelism, and Execution Interleaving

A process is an executing program with its own address space and operating-system resources. A thread is an execution path within a process. Threads in the same process share code, data, and open files, but each thread has its own stack, registers, and program counter.

Concurrency means that multiple activities make progress during overlapping time intervals. Parallelism means that multiple activities execute simultaneously, usually on different processor cores. Parallel execution is a possible implementation of concurrency, but concurrency can exist without parallel hardware.

Consider two operations on a shared variable `counter`:

```text

register = counter

register = register + 1

counter = register

```

The operation appears indivisible at the source-code level but normally consists of several machine instructions. If two threads execute it concurrently, both may read the same original value. Each computes the same incremented value, and one write overwrites the other. This is a lost-update race condition.

An execution can be modeled as an interleaving of individual steps from different threads. Because the operating system may interrupt a thread between any such steps, correctness cannot depend on a particular interleaving unless that interleaving is enforced by synchronization.

Important terminology

• Race condition: Program behavior depends on the relative timing of concurrent activities.
• Data race: Conflicting accesses to the same memory location occur concurrently, with at least one access being a write, without suitable synchronization.
• Atomic operation: An operation that appears indivisible to other threads.
• Critical section: Code that accesses shared state and must not be executed concurrently by conflicting activities.
• Safety: Nothing bad happens, such as two threads corrupting a data structure.
• Liveness: Something good eventually happens, such as a waiting thread obtaining a lock.

2. The Critical-Section Problem

A program containing concurrent threads can be divided into an entry section, critical section, exit section, and remainder section. The entry section obtains permission to enter; the critical section accesses shared resources; the exit section releases permission.

A correct solution to the critical-section problem should satisfy three classic requirements:

1. Mutual exclusion: At most one process or thread is in a given critical section at a time.

2. Progress: If no thread is in the critical section and some threads wish to enter, the selection of the next entrant cannot be postponed indefinitely by threads that are not interested in entering.

3. Bounded waiting: After a thread requests entry, there is a limit on how many times other threads may enter before it is admitted.

These properties address different concerns. Mutual exclusion is a safety property. Progress and bounded waiting are liveness and fairness properties. A mechanism can provide mutual exclusion yet still cause starvation if one thread repeatedly acquires the resource before another.

Memory ordering and visibility

Synchronization is not only about preventing simultaneous execution. Modern processors and compilers reorder operations for performance, and each core may temporarily observe cached values. A synchronization operation must therefore establish suitable memory-ordering and visibility guarantees. For example, releasing a lock generally makes earlier writes visible to a thread that later acquires the same lock. The exact guarantees depend on the programming language and platform memory model; portable programs should use documented synchronization primitives rather than assumptions about hardware behavior.

3. Mutexes and Locks

A mutex is a mutual-exclusion object with two logical states: available and owned. A thread calls `lock()` before entering a protected region and `unlock()` after leaving it.

```text

lock(mutex)

try:

update_shared_structure()

finally:

unlock(mutex)

```

The `finally` pattern is important because an exception, error, or early return must not leave the mutex permanently locked. A mutex normally has ownership semantics: the thread that locks it is expected to unlock it.

A mutex may be implemented using hardware atomic instructions and may use either spinning or blocking. A spinlock repeatedly checks the lock, consuming processor time. Spinning can be appropriate when the expected wait is extremely short and the system has multiple cores. A blocking mutex suspends the waiting thread, allowing the processor to run other work; this is generally preferable for longer waits.

Lock granularity

A coarse-grained lock protects a large amount of state and is simple to reason about, but it reduces concurrency. Fine-grained locking protects smaller objects and may improve throughput, but increases complexity and deadlock risk. Good designs identify invariants—the conditions that must always remain true—and choose lock boundaries that protect those invariants.

Deadlock

A deadlock occurs when a set of threads wait forever for events that only members of the same set can cause. The four Coffman conditions are:

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

Deadlock prevention breaks at least one condition. A common technique is to impose a global ordering on locks and require every thread to acquire them in that order. Deadlock avoidance instead examines whether granting a request leaves the system in a safe state. Detection allows deadlocks to occur and later searches for cycles or unreleased resources.

4. Semaphores

A semaphore is a synchronization object containing a counter manipulated only through atomic operations commonly called `wait` (or `P`) and `signal` (or `V`). A counting semaphore can represent a number of available resources. A binary semaphore has values commonly restricted to zero and one, although it need not have the ownership semantics of a mutex.

Conceptually:

```text

wait(S) // decrement; block if the value is unavailable

critical_work()

signal(S) // increment and possibly wake a waiter

```

For a counting semaphore initialized to `k`, at most `k` units of the represented resource can be allocated simultaneously, assuming every acquisition is matched by a release. Semaphores are useful for producer–consumer coordination, connection pools, and bounded resources.

Bounded-buffer example

Suppose a buffer has capacity `N`. A producer must wait for an empty slot, then acquire exclusive access to modify the buffer. A consumer must wait for an occupied slot, then acquire exclusive access to remove an item.

```text

empty = N

full = 0

mutex = unlocked

producer(item):

wait(empty)

lock(mutex)

insert(item)

unlock(mutex)

signal(full)

consumer():

wait(full)

lock(mutex)

item = remove()

unlock(mutex)

signal(empty)

return item

```

The ordering is significant. A producer reserves an empty slot before entering the buffer, and a consumer reserves an occupied slot before removing an item. The mutex protects the data structure itself, while the counting semaphores represent buffer capacity and occupancy.

Incorrect semaphore ordering can cause deadlock. For example, if a producer locks the mutex before waiting for an empty slot while the buffer is full, a consumer may be unable to acquire the mutex to remove an item.

5. Monitors and Condition Variables

A monitor is a high-level synchronization construct that combines shared data, procedures operating on that data, and implicit mutual exclusion. At most one thread executes monitor code at a time. Languages such as Java and C# provide monitor-like features, while libraries in other languages provide equivalent abstractions.

A condition variable allows a thread to sleep until a condition associated with protected state may have become true. It is normally used with a mutex:

```text

lock(mutex)

while not condition:

wait(condition_variable, mutex)

perform_operation()

unlock(mutex)

```

The wait operation atomically releases the mutex and blocks the thread. When awakened, it reacquires the mutex before returning. The condition must be tested in a `while` loop, not an `if` statement, because:

• another thread may change the state before the awakened thread reacquires the mutex;
• wakeups may be spurious on some systems;
• a notification indicates that a condition may hold, not that it definitely holds for every waiter.

For example, a queue consumer waits while the queue is empty. A producer inserts an item while holding the mutex and signals the condition variable. The consumer rechecks the queue after waking.

Condition variables express logical conditions more clearly than low-level semaphore code. However, they do not themselves protect data; the associated mutex and correct predicate design are essential.

6. Atomic Operations and Lock-Free Concepts

An atomic operation completes as one indivisible unit relative to other threads. Common atomic operations include atomic load, store, exchange, increment, decrement, and compare-and-swap (CAS). CAS has the conceptual form:

```text

if (*address == expected):

*address = desired

return success

else:

return failure

```

The comparison and conditional update occur atomically. A thread can use CAS to retry an update when another thread changes the value first.

A lock-free algorithm guarantees that, regardless of individual thread delays, some thread completes an operation within a finite number of steps. It does not guarantee that every thread makes progress; one thread may repeatedly lose CAS attempts. A wait-free algorithm guarantees completion for every thread within a bounded number of its own steps. Wait-free guarantees are stronger and often harder to achieve.

A lock-free stack, for example, may store a pointer to the top node. A pop operation reads the top pointer, identifies the next node, and uses CAS to replace the top with the next pointer. If another thread changes the top first, CAS fails and the operation retries.

Lock-free programming has serious challenges:

• the ABA problem, in which a value changes from A to B and back to A;
• safe memory reclamation, because another thread may still hold a pointer;
• memory-ordering errors;
• starvation and unbounded retries;
• difficult testing and formal verification.

Techniques such as tagged pointers, hazard pointers, epochs, and read-copy-update address some reclamation problems. Lock-free code should be used only when its performance or progress benefits justify the complexity.

7. Interprocess Communication Models

Processes normally have separate address spaces. Interprocess communication (IPC) provides controlled ways for processes to exchange data and coordinate execution. Two broad models are shared memory and message passing.

Shared memory

The operating system maps a physical-memory region into the address spaces of multiple processes. After setup, processes communicate by reading and writing that region. Shared memory can be very fast because large data need not be copied through the kernel for every transfer. However, the processes must synchronize access using mutexes, semaphores, condition variables, or atomic operations. Shared memory therefore offers high performance at the cost of greater responsibility for consistency and protection.

Shared-memory designs must specify ownership, layout, initialization, synchronization, and recovery after a process crashes. A robust design may include version fields, sequence counters, checksums, or a protocol for identifying partially written records.

Message passing

In message passing, processes communicate through operating-system-managed messages or communication endpoints. The sender transmits a message and the receiver obtains it. Message passing can be direct, between named processes, or indirect, through a mailbox, queue, or broker.

Message passing reduces direct sharing and can make isolation easier to reason about. It also supports communication between processes on different machines. Its costs may include copying, serialization, context switches, queue capacity limits, and network delays.

Communication may be:

• Synchronous: The sender or receiver waits until the other side participates.
• Asynchronous: A send can complete once the message is placed in a buffer.
• Buffered: Messages wait in a queue with finite or theoretically unbounded capacity.

The correct choice depends on data size, latency, failure behavior, security boundaries, and whether communication must cross a machine boundary.

8. Pipes, Shared Memory, and Sockets

A pipe is a byte stream with a read end and a write end. An anonymous pipe commonly connects related processes, such as a parent and child. A named pipe, or FIFO, can connect less closely related processes through a filesystem name. Pipes are simple and useful for producer–consumer streams, command pipelines, and logging. They are generally unidirectional or logically stream-oriented, and they do not preserve application-level message boundaries unless the application defines a protocol.

A socket is an endpoint for communication. Local-domain sockets support communication on one host; Internet sockets use protocols such as TCP and UDP. TCP provides a reliable, ordered byte stream but does not preserve message boundaries. UDP provides datagrams with lower protocol overhead but does not guarantee delivery, ordering, or duplicate suppression. Applications using UDP must provide any required reliability and ordering.

A socket server commonly follows this pattern:

1. Create a socket.

2. Bind it to an address and port or local endpoint.

3. Listen for incoming connections if using a connection-oriented service.

4. Accept a connection.

5. Exchange data according to an explicit protocol.

6. Close the connection and release resources.

Concurrent servers may use one thread per connection, a thread pool, asynchronous I/O, or an event-driven loop. Each approach involves trade-offs in memory consumption, implementation complexity, latency, and scalability.

9. Choosing a Synchronization or IPC Mechanism

A mutex is appropriate when one process or group of threads needs exclusive access to an invariant-protected data structure. A semaphore is appropriate when counting resources or coordinating stages. A condition variable is appropriate when a thread must sleep until a predicate over shared state becomes true. Atomic operations are useful for small independent state transitions and carefully designed lock-free structures.

Use shared memory when high-throughput exchange of large data is important and participating components can share a synchronization protocol. Use message passing when isolation, modularity, or cross-machine communication is more important. Use pipes for simple streams between related programs. Use sockets for explicit client–server protocols, network communication, or communication between independent services.

The decision should consider:

• required latency and throughput;
• data volume and copying overhead;
• failure and restart behavior;
• security and privilege boundaries;
• ease of testing and maintenance;
• fairness and real-time requirements;
• portability and platform support.

10. Applied Case: Concurrent Inference Service

Background

The following is an illustrative case. A university deploys an image-classification service for a research portal. Clients upload images, and the service places requests in a queue. Several worker threads preprocess images and invoke a machine-learning model. Results are returned through a network API.

Problem

The first implementation uses a shared queue without synchronization. Under load, requests occasionally disappear, two workers process the same request, and the service sometimes crashes during shutdown. Increasing the number of workers makes the problem more frequent.

Analysis

The queue has multiple producers because network-handler threads insert requests, and multiple consumers because worker threads remove them. Queue insertion and removal modify shared pointers and counters, so they require mutual exclusion. Workers also need to wait when the queue is empty, while producers must wait when the queue reaches its capacity. Shutdown introduces another shared state: workers must stop after all accepted requests are handled.

Approach and solution

The queue is protected by a mutex. Two condition variables represent `not_empty` and `not_full`. A producer locks the mutex, waits while the queue is full and shutdown has not begun, inserts a request, signals `not_empty`, and unlocks. A consumer locks the mutex, waits while the queue is empty and shutdown has not begun, removes a request, signals `not_full`, and unlocks.

The model object is initially read-only after loading, so workers share it without a model lock. If the inference library uses mutable internal buffers, each worker receives a separate context or an additional lock protects those buffers. Network handlers communicate with workers through the in-process queue, while clients communicate with the service through TCP sockets.

During shutdown, the service stops accepting new requests, sets a shutdown flag while holding the queue mutex, broadcasts to both condition variables, and allows workers to drain or reject queued requests according to the service policy. Every thread is then joined before shared resources are destroyed.

Outcome

The revised design prevents queue corruption, avoids busy waiting, and provides a defined shutdown protocol. Performance testing measures queue latency, worker utilization, rejected requests, and model throughput. The design also makes backpressure explicit: when the queue is full, the service can reject requests or apply a bounded wait rather than consuming unlimited memory.

Learning points

1. A shared queue requires both mutual exclusion and condition synchronization.

2. Predicates must be checked in loops.

3. Shutdown is a synchronization problem, not merely a final function call.

4. Read-only model data can often be shared safely, but library thread safety must be verified.

5. Bounded queues protect availability and support backpressure.

11. Challenges, Safety, and Professional Practice

Concurrency failures include deadlock, livelock, starvation, priority inversion, races, and inconsistent visibility. Livelock occurs when threads remain active but repeatedly respond to one another without making progress. Priority inversion occurs when a high-priority task waits for a resource held by a low-priority task, while medium-priority tasks prevent the low-priority task from running. Priority inheritance or priority-ceiling protocols may reduce this problem in real-time systems.

Best practices include:

• minimize shared mutable state;
• document which lock protects each variable or invariant;
• establish and enforce lock-order rules;
• keep critical sections short and avoid blocking I/O while holding locks;
• use structured lock management and cleanup;
• prefer tested high-level concurrency libraries;
• distinguish notification from proof that a condition holds;
• test under varied schedules, processor counts, and failure conditions;
• use race detectors, thread sanitizers, stress tests, and model checking where appropriate;
• define timeouts and cancellation behavior;
• measure contention rather than assuming that more threads improve performance.

Concurrency also has security implications. A race may bypass authorization checks, corrupt audit records, or expose inconsistent financial or medical data. Shared-memory regions and sockets must be protected with appropriate operating-system permissions, authentication, encryption, and input validation. Privacy regulations may require reliable isolation and auditability when concurrent services process personal data. In AI systems, inconsistent preprocessing or model-state updates can produce unreliable or non-reproducible predictions, so synchronization policies should be part of the system’s governance and testing documentation.

12. Contemporary Developments

Contemporary operating systems increasingly combine threads, asynchronous I/O, event loops, user-level task schedulers, and hardware atomic instructions. Cloud services often use message brokers and partitioned streams to scale across machines. GPUs and specialized accelerators introduce additional synchronization domains, including host-device queues and kernel barriers.

The growing use of multicore CPUs makes memory-model literacy increasingly important. Languages with strong concurrency libraries provide channels, futures, actors, structured concurrency, or ownership-based protection. Structured concurrency treats child activities as a managed scope, improving cancellation and error propagation. These abstractions do not eliminate the need to understand races and synchronization; they provide safer ways to express common patterns.

Chapter Summary

Concurrency allows multiple activities to overlap, while parallelism executes activities simultaneously on multiple processing units. Shared mutable state creates race conditions unless access is controlled. Critical-section solutions must provide mutual exclusion, progress, and bounded waiting. Mutexes protect exclusive access; semaphores represent counted resources or coordination events; monitors and condition variables provide structured waiting on predicates. Atomic operations support indivisible state transitions and form the basis of lock-free algorithms, although lock-free programming introduces memory-reclamation and fairness challenges.

IPC may use shared memory or message passing. Shared memory can provide high throughput but requires explicit synchronization. Pipes provide simple stream communication, while sockets support local and networked client–server protocols. Correct concurrent designs address deadlock, starvation, visibility, shutdown, failure recovery, security, and performance. Practical systems should minimize shared state, document synchronization rules, test under adverse schedules, and select abstractions that match their latency, throughput, isolation, and reliability requirements.

Key Terms

Concurrency: Overlapping progress of multiple activities.

Parallelism: Simultaneous execution of activities on multiple processing units.

Thread: An execution path within a process.

Critical section: Code that accesses shared state and requires controlled entry.

Mutual exclusion: Property that permits at most one conflicting activity at a time.

Race condition: Behavior dependent on execution timing.

Data race: Unsynchronized conflicting memory accesses involving a write.

Mutex: Ownership-based mutual-exclusion lock.

Semaphore: Counter-based synchronization primitive.

Monitor: Construct combining protected data, procedures, and mutual exclusion.

Condition variable: Mechanism for waiting until a predicate may become true.

Atomic operation: Indivisible operation relative to concurrent activities.

Compare-and-swap: Atomic conditional replacement operation.

Deadlock: Permanent waiting caused by circular resource dependencies.

Starvation: Indefinite failure of a thread to obtain needed service.

Lock-free: Progress guarantee that some operation completes despite individual delays.

Shared memory: Memory mapped into multiple process address spaces.

Message passing: IPC based on sending and receiving discrete data.

Pipe: Stream-oriented IPC channel with read and write ends.

Socket: Communication endpoint for local or network communication.

Review Questions

Short Answer Questions

1. Distinguish concurrency from parallelism.

2. State the three requirements of a correct critical-section solution.

3. Why should a condition variable normally be used inside a `while` loop?

4. What is the principal difference between shared-memory and message-passing IPC?

5. What does compare-and-swap accomplish?

Long Answer Questions

1. Explain mutexes, semaphores, monitors, and condition variables, including a suitable use case for each.

2. Describe the four Coffman conditions for deadlock and explain two prevention techniques.

3. Explain the bounded-buffer problem and show how mutexes and counting semaphores coordinate producers and consumers.

4. Compare pipes, shared memory, and sockets in terms of communication model, performance, and application suitability.

5. Discuss the benefits and limitations of lock-free algorithms, including the ABA problem and memory reclamation.

Analytical / Application Questions

1. A server has a bounded request queue and multiple producers and consumers. Design a synchronization protocol that handles insertion, removal, full and empty states, and orderly shutdown.

2. Two threads acquire locks A and B in opposite orders. Analyze how deadlock can occur and propose a corrected lock-order policy.

3. An AI inference service shares a mutable model cache among workers. Determine which data should be protected, select suitable synchronization mechanisms, and explain how you would test the design for races and performance bottlenecks.

Multiple Choice Questions with Answers

Question 1

Which property ensures that no two conflicting threads enter a critical section simultaneously?

A. Progress

B. Mutual exclusion

C. Bounded waiting

D. Asynchronous execution

Correct Answer: B. Mutual exclusion

Question 2

Why is a condition-variable predicate normally tested in a while loop?

A. A wait operation permanently releases the mutex

B. Notifications guarantee that the predicate is true

C. The predicate may be false again when the thread reacquires the mutex

D. While loops make the condition variable atomic

Correct Answer: C. The predicate may be false again when the thread reacquires the mutex

Question 3

Which primitive is most directly suited to representing five identical available resources?

A. Counting semaphore initialized to five

B. Binary mutex initialized to zero

C. Condition variable without a mutex

D. TCP socket

Correct Answer: A. Counting semaphore initialized to five

Question 4

What is a principal characteristic of a mutex?

A. It preserves network message boundaries

B. It normally has ownership semantics

C. It guarantees every waiter will eventually proceed

D. It is used only between machines

Correct Answer: B. It normally has ownership semantics

Question 5

Which IPC mechanism generally provides a reliable, ordered byte stream over a network?

A. UDP

B. TCP

C. Anonymous signal

D. Counting semaphore

Correct Answer: B. TCP

Question 6

Which Coffman condition is directly addressed by requiring locks to be acquired in a global order?

A. Circular wait

B. Mutual exclusion

C. No preemption

D. Memory visibility

Correct Answer: A. Circular wait

Question 7

What does compare-and-swap do atomically?

A. Copies an entire process address space

B. Replaces a value only if it equals an expected value

C. Blocks all processors permanently

D. Converts a byte stream into messages

Correct Answer: B. Replaces a value only if it equals an expected value

Question 8

A lock-free algorithm guarantees that:

A. Every thread completes within a fixed number of steps

B. No thread can ever be delayed

C. Some thread completes within a finite number of steps despite individual delays

D. It never uses atomic instructions

Correct Answer: C. Some thread completes within a finite number of steps despite individual delays

Question 9

Which mechanism is most appropriate for a simple stream connecting a parent process to a child process?

A. Anonymous pipe

B. Model cache

C. Condition variable alone

D. Lock-free stack only

Correct Answer: A. Anonymous pipe

Question 10

In a bounded-buffer design, what does the `empty` counting semaphore usually represent?

A. The number of available empty slots

B. The number of occupied processors

C. The number of active sockets

D. The number of waiting mutex owners

Correct Answer: A. The number of available empty slots