IM Engineer Study Notes
← Back to list
Computing & Embedded
#프로세스동기화#세마포어#뮤텍스#임계구역#모니터
Last updated · 2026-10-27

Process Synchronization

1. Overview

Process Synchronization refers to control techniques that coordinate the execution order and timing of access when multiple processes (or threads) access shared resources or shared variables concurrently, thereby guaranteeing data consistency and correct results.

As multiprogramming and multicore have become ubiquitous, it has become routine for multiple execution flows to share a single memory, file, or device at the same time. The problem is that the CPU arbitrarily interleaves execution flows at the instruction level. Even count++, which looks like a single line, is split into three steps — "read from memory → increment by 1 in a register → write to memory" — so if two flows execute these three steps intermixed, a lost update occurs in which one side's update disappears. This abnormal state, where the result changes depending on execution order (timing), is precisely a [[race-condition]], and process synchronization encompasses every mechanism for fundamentally eliminating such race conditions.

The reason synchronization is difficult is that its defects manifest non-deterministically. Even with identical code, depending on scheduling, load, and the number of cores, it sometimes works correctly and sometimes produces a wrong value. It is a classic Heisenbug that is not reproduced in testing but erupts intermittently under the high concurrency of production, so the cost of post-hoc debugging is very high. From the professional-engineer perspective, therefore, one must be able to judge precisely at the design stage "when synchronization is needed (identifying critical sections)" and "with which tool and how it is guaranteed (semaphore, mutex, monitor)."

Process synchronization has two broad purposes. The first is mutual exclusion — guaranteeing that only one flow uses a shared resource at a time — and the second is execution-order control (ordering/condition synchronization) — aligning the precedence relationship between flows, as in "B consumes only after A produces data." The former protects data integrity, and the latter protects the logical coherence of cooperation. However, if synchronization is designed poorly, it leads to other incidents such as a [[deadlock]] in which each waits for the other indefinitely, or starvation in which only a particular flow keeps being pushed back; thus synchronization is a problem of balance — designing it to be "neither excessive nor insufficient."

These two purposes are also commonly called competition synchronization and cooperation synchronization. Competition synchronization arbitrates so that only one at a time may use the same resource when multiple flows contend for it, to which mutual exclusion corresponds; cooperation synchronization makes flows with different roles align the precedence of their work to achieve one goal together, of which the producer-consumer relationship is typical. The two types require different tools: contention suits a lock (mutex), while cooperation suits a signaling mechanism that waits for a condition and then wakes (condition variable, semaphore). In real systems the two types appear mixed within one piece of code, so identifying which point is contention and which is cooperation is the starting point of design.

2. The Critical Section Problem and Synchronization Requirements

A code region that accesses a shared resource and changes its value is called a Critical Section, and the core of the concurrency problem lies in "guaranteeing that at no moment is more than one flow inside the critical section." Each flow's code consists of an entry section for entering the critical section, the critical section, an exit section after leaving, and the remainder section.

graph TD
    A["Process Synchronization"] --> B["Mutual Exclusion"]
    A --> C["Condition Sync"]
    B --> D["Critical Section Problem"]
    D --> E["Entry → Critical Section → Exit"]
    D --> F["3 requirements for a solution"]
    F --> G["Mutual Exclusion"]
    F --> H["Progress"]
    F --> I["Bounded Waiting"]

What happens if the critical section is not protected becomes clear from a simple example where two flows each increment the shared variable count (initial value 10) by 1. If count++ were indivisible, the result must be 12, but if the instructions interleave, one side's update is lost and it becomes 11, as below.

Time Flow T1 Flow T2 count (memory)
t1 read → 10 10
t2 read → 10 10
t3 10+1 = 11 10
t4 10+1 = 11 10
t5 write 11 11
t6 write 11 11

This lost update, where count ends up as 11 rather than 12, is exactly the classic error synchronization must prevent. Had T2 been excluded while T1 was in the critical section, the result would always be guaranteed to be 12. In this way, a solution to the critical section problem must satisfy all three requirements (Dijkstra's formulation); one must understand that the conditions below are not a mere list of rules but devices, each to prevent a specific failure mode.

A. Mutual Exclusion. If one flow is executing in the critical section, no other flow may enter its own critical section. If this condition breaks, two flows update the shared variable simultaneously, causing lost updates and data corruption. Mutual exclusion is the most basic and minimal requirement of synchronization, but by itself it is not sufficient, because applying mutual exclusion excessively can fall into a deadlock in which no one can enter.

B. Progress. If the critical section is empty and there are flows wishing to enter, the selection of which flow will enter the critical section must not be postponed indefinitely. That is, a flow that is not currently using the critical section (that is in its remainder section) must not block another flow's entry. This condition prevents the inefficiency and deadlock of "no one being able to enter even though the seat is vacant." The very point where early software solutions repeatedly failed was this progress condition.

C. Bounded Waiting. After a flow requests entry, there must be an upper bound on the number of times other flows can enter the critical section before that request is granted. Without this condition, a particular flow keeps being pushed back and starvation occurs in which it never obtains the resource forever. In other words, bounded waiting is the condition that guarantees the fairness of synchronization.

A classic attempt to satisfy all three conditions with software alone is Peterson's Algorithm. Two processes together use two shared variables, flag[] (intent to enter) and turn (yielding variable), so that each sets its flag and then yields its turn to the other, thereby satisfying all three conditions. The core logic lies in marking "I want to enter (flag[i]=true)," then writing the other party into turn to express the intent to yield, and waiting only when the other is trying to enter and it is simultaneously the other's turn. Even if the two flows attempt entry almost simultaneously, the turn variable lets only one side through so mutual exclusion is not broken; if the other is uninterested, one can enter immediately, satisfying progress; and since they yield in turn, bounded waiting is also satisfied.

However, Peterson's solution is limited to two processes and, more fundamentally, does not work as is without memory barriers because of modern CPUs' out-of-order execution and caches. It also has the inefficiency of busy waiting, in which the CPU is continuously consumed while waiting to enter. For this reason, practice uses hardware support and operating-system-level synchronization tools.

3. Hardware and Software Synchronization Techniques

It helps to understand synchronization tools as a layered structure in which the operating system and language runtime stack abstractions — semaphore, mutex, monitor — on top of the hardware foundation of atomic instructions provided by the CPU.

flowchart TD
    HW["Hardware atomic instructions<br/>TAS · CAS · Fetch-and-Add"] --> OS["OS/runtime synchronization tools"]
    OS --> SEM["Semaphore<br/>P/V operations, integer counter"]
    OS --> MTX["Mutex<br/>binary lock with ownership"]
    OS --> MON["Monitor<br/>language-level encapsulation + condition variable"]
    SEM --> USE["Producer-Consumer · Readers-Writers"]
    MTX --> USE
    MON --> USE
    MTX --> PI["Beware Priority Inversion"]

A. Hardware techniques (atomic instructions). The CPU provides atomic instructions that perform "read-modify-write" as a single indivisible instruction. Representative examples are TestAndSet (returns the value it read while simultaneously setting it to true), Compare-And-Swap(CAS) (replaces with a new value only when the memory value equals the expected value), and Fetch-and-Add. Since no other flow can intervene in the middle, these become the very foundation for implementing a lock. CAS in particular is the core operation of lock-free data structures that use no lock at all, achieving atomic update without mutual exclusion by retrying until it succeeds. However, using hardware techniques directly is difficult because the developer must handle busy waiting and the ABA problem (the phenomenon where a value returns A→B→A and CAS misjudges) directly.

The simplest lock built from atomic instructions is the spinlock. In a way that repeats TestAndSet and keeps the CPU spinning until the lock is acquired, it is advantageous when the critical section is extremely short and the wait time is less than the context-switch cost. Conversely, if the critical section is long, a spinlock wastes the CPU, so a blocking approach (semaphore, mutex) that puts the flow to sleep in a wait queue is better. That is, the choice of "busy waiting vs. blocking" is a classic trade-off governed by the length of the critical section and the number of cores, and the kernel optimizes with an adaptive mutex that mixes the two, spinning for short waits and blocking when they grow long.

B. Semaphore. An integer synchronization variable proposed by Dijkstra, accessed only by two atomic operations, P (wait, decrement) and V (signal, increment). P decrements by 1 and enters if the semaphore value is positive, and if it is 0 or below, it puts the flow into a wait queue and blocks it. V increments the value by 1 and, if there is a waiting flow, wakes one. If the maximum value is 1 it is used as a binary semaphore (for mutual exclusion), and if it is 2 or more as a counting semaphore (for managing a finite resource pool). The semaphore is powerful in that it can express both mutual exclusion and execution-order control, but it draws criticism as an "easy-to-misuse" tool, since the developer must manually match the P/V pairs throughout the code and missing one immediately causes a deadlock or mutual-exclusion violation.

The use of a counting semaphore is easily understood through a database connection pool. If the pool has 10 connections, the semaphore is initialized to 10, a flow wishing to borrow a connection decrements the value by one with P and uses it, and returns it to the original with V when returning it. When the value reaches 0, the eleventh requesting flow automatically sleeps in the wait queue, and the instant someone returns a connection, V wakes it. In this way a single semaphore implements resource counting that "limits concurrent usage exactly to N," and a thread pool, request rate limiting, and concurrent-connection-count control follow the same principle. On the other hand, if only mutual exclusion is needed, a mutex with the notion of ownership is safer than a semaphore.

C. Mutex. A lock whose sole purpose is Mutual Exclusion; it looks similar to a binary semaphore, but the decisive difference is ownership. A mutex can be unlocked only by the flow that locked it (the lock/unlock subject is identical), whereas a semaphore allows any flow to call V. Thanks to this notion of ownership, a mutex can track the owner, so it can mitigate [[priority-inversion]] through priority inheritance, which temporarily raises the priority of a low-priority flow holding the lock. There are also variants such as a recursive mutex that, if a flow already holding the lock locks again, permits re-entry rather than deadlock, and a spinlock that is advantageous for short waits.

Ownership is also the basis of safety. A mutex can treat an unlock attempt by a flow that is not the owner as an error, structurally preventing the common misuse of a semaphore (mutual exclusion collapsing from a mismatched V call). Conversely, because of ownership, the risk arises that "if the locking flow dies before finishing, the lock is never released forever," so an idiom that automatically couples lock release to block exit, such as C++'s RAII-based lock_guard or Java's try-finally, is essential. In this way, a single small design choice (ownership) cascades to govern safety, recoverability, and even usage idioms — this is the essential difference from the semaphore.

D. Monitor and condition variables. A high-level language-level synchronization abstraction proposed by Hoare and Brinch Hansen to reduce the risk of misusing semaphores. It encapsulates shared data and the procedures that handle that data into a single monitor, and inside the monitor the compiler and runtime automatically guarantee mutual exclusion so that only one flow is active at any moment. The developer need not write P/V directly. Order control is expressed by the condition variable's wait (yields and waits until the condition is met) and signal (wakes a waiting flow). Java's synchronized/wait/notify and C#'s lock are representative implementations of the monitor model. When using a condition variable, one must call wait inside a while loop so that the condition is re-checked after waking, in order to prevent a spurious wakeup (where the condition may be false again even after waking) and signal interception.

A monitor's signaling discipline has two semantics, and their difference governs practical coding rules. The Hoare discipline (signal-and-wait) yields the monitor immediately to the awakened flow when signal is called, so the awakened flow is guaranteed the condition is true, but the implementation is complex and context switches are frequent. By contrast, the Mesa discipline (signal-and-continue), adopted by most real languages, has the signaling flow continue executing and the awakened flow compete again from the queue, so the condition may change again in the interim. Precisely for this reason, Java and POSIX condition variables must re-check the condition with while rather than if, and violating this rule produces the bug of "entering the critical section when the condition is false." This is a representative case showing that even with a high abstraction, one must understand the internal semantics to use it correctly.

4. Classic Synchronization Problems and a Comparison of Techniques

There are three classic problems that show the essence of synchronization design. Each problem represents a different synchronization requirement.

A. The Producer-Consumer (Bounded Buffer) problem. The producer puts data into a finite buffer and the consumer takes it out. When the buffer is full the producer must wait, and when it is empty the consumer must wait. It is solved cleanly with three semaphores — the number of empty slots (empty), the number of full slots (full), and one for mutual exclusion (mutex). This problem is the archetype requiring both mutual exclusion and order control at once, and the backpressure design of message queues and stream-processing pipelines is essentially this structure. For example, when a collection thread (producer) in a log-collection system pours out tens of thousands of entries per second, adjusting the buffer size and the number of consumers to match throughput without memory explosion is the real application of this model.

B. The Readers-Writers problem. Multiple readers may read concurrently from shared data, but while a writer is writing, neither readers nor writers may access it. In that reading is shared and writing is exclusive, it is more elaborate than simple mutual exclusion. A reader-preference policy raises read throughput but may starve writers, and a writer-preference policy is the opposite. The practical products of this trade-off are the shared lock/exclusive lock of databases and the ReadWriteLock for read performance, which further evolved into multi-version concurrency control (MVCC) that keeps writers from blocking readers.

In real services, the readers-writers structure stands out in caches, configuration stores, and session stores where the proportion of reads is overwhelmingly high. For example, in a system that reads a configuration value hundreds of thousands of times per second but updates only a few times a day, using a simple mutex makes reads unnecessarily block one another and throughput plummets. Here, letting readers pass concurrently with a ReadWriteLock raises read throughput by tens of times. However, if writes become frequent, the management overhead of a reader-writer lock can exceed that of a simple mutex, so it is an important design judgment that one must choose based on measuring the read/write ratio.

The readers-writers problem also shows that the fairness policy is directly tied to performance. When read and write requests arrive mixed, the distribution of throughput and latency varies greatly depending on whom to let through first (reader-preference, writer-preference, fair queuing), so the policy must be set while considering together the service's read/write characteristics and its latency-bound requirements. This reveals that synchronization is not merely a matter of "correctness" but a task of designing quality attributes (performance, fairness) together.

C. The Dining Philosophers problem. Five philosophers each must pick up both forks on either side to eat, but if all hold the left fork and wait for the right, they fall into circular wait (deadlock). This problem compactly shows how, when synchronization is done wrong, it leads to a [[deadlock]]. Solutions that make the resource-acquisition order asymmetric (odd-numbered pick up the left first, even-numbered the right first), limit the number of simultaneous diners to N−1, or make them pick up both forks atomically, all break one of the four conditions of deadlock. Though it looks like a toy problem on the surface, its structure is completely the same as practical situations where "multiple logical resources must be acquired at once," such as connection-pool exhaustion or thread-pool mutual waiting, so the same solution principle (resource ordering, limiting simultaneous users) applies directly.

As the three problems show, the choice of synchronization tool varies depending on "what must be guaranteed." The table below organizes the characteristics of representative tools, but why each tool suits such a use stems from differences along three axes: ownership, abstraction level, and fairness.

Tool Ownership Abstraction level Primary use Representative implementation
Atomic instruction (CAS) None Hardware Lock-free data structures compareAndSet, atomic
Semaphore None OS low-level Order control, resource pool POSIX sem_t
Mutex Yes OS/runtime Mutual exclusion pthread_mutex, std::mutex
Monitor (managed by language) Language high-level Mutual exclusion + condition wait Java synchronized

The most important practical implication in this table is the presence or absence of ownership. Because a semaphore has no owner, it is natural for an order-control pattern like "one flow waits and another wakes it," but using it for mutual exclusion lets the releasing flow differ from the locking flow, so bugs can hide easily. By contrast, because a mutex has ownership, it is safe for mutual exclusion and enables advanced features like priority inheritance, but order control additionally requires a condition variable. That is why modern languages recommend a division of roles: "mutex/monitor for mutual exclusion, condition variable for order control, semaphore for resource counting."

The difference in abstraction level also divides practical choice. Atomic instructions are the fastest but carry high error potential because the developer must take direct responsibility down to ABA and memory visibility, while a monitor is the safest but, bound to language support, makes fine-grained control difficult. The semaphore and mutex sit in between, with the operating system managing blocking and wait queues. In general, a "safety first, selective optimization" strategy is recommended — starting at the highest abstraction (monitor, concurrent collections) and descending to low-level tools only at hotspots where performance profiling has confirmed a bottleneck — because premature low-level optimization pays the large cost of irreproducible concurrency bugs.

5. Deep Dive: Recent Trends and Practical Application

A. Lock-free/Wait-free concurrency. As multicore has expanded to tens of cores and lock contention has become the bottleneck for scalability, lock-free data structures that achieve concurrency without locks by applying CAS repeatedly are drawing attention. Java's ConcurrentHashMap/AtomicInteger and C++'s std::atomic are representative. Lock-free gives the strong progress guarantee that the whole does not halt even if one flow stops, but it remains a high-difficulty area because the ABA problem and memory reclamation (hazard pointers, RCU) design are tricky. Depending on the strength of the progress guarantee, it divides into lock-free, where "at least one flow definitely advances," and the stronger wait-free, where "every flow advances within a finite time"; the latter is used to guarantee latency bounds in real-time systems but has a very high implementation cost.

B. Memory models and memory barriers. Modern CPUs and compilers reorder memory accesses for performance. Therefore a synchronization tool must be defined together with a memory barrier that "guarantees memory visibility at the boundaries of the critical section." Java's volatile and the happens-before relationship, and C++11's memory_order, deal with this explicitly. Since a considerable number of synchronization bugs originate from "the lock was held correctly but memory visibility was overlooked," at the professional-engineer level one must be able to discuss not only mutual exclusion but also visibility.

A typical case of overlooking visibility is the malfunction of double-checked locking. This idiom, which checks the condition once before locking and once after for performance, was widely used for singleton initialization, but due to reordering of object creation and reference assignment it produced the fatal bug where a partially constructed object — "the reference is visible but the internal fields are not yet initialized" — is exposed to other flows. Java solves this with a volatile declaration (under the memory model strengthened since 1.5), and C++ with std::atomic and an appropriate memory_order. This case clearly shows that even if mutual exclusion is perfectly observed, synchronization collapses if memory visibility is missed.

C. Asynchronous/non-blocking and distributed synchronization. Large-scale I/O services express concurrency with async/await, futures, and channels instead of blocking threads, reducing context-switch cost. Under the philosophy "do not communicate by sharing memory; share memory by communicating," the Go language makes channel-based synchronization a first-class citizen, and Rust blocks data races at compile time with ownership and a borrow checker. Meanwhile, mutual exclusion spanning multiple nodes cannot be solved with a single machine's mutex, so distributed locks such as Redis Redlock, ZooKeeper, and etcd are used. A distributed lock must reinforce safety with a lease and a fencing token because of network delays and node failures.

D. Past-exam linkage and expected exam directions. In the professional-engineer exam, synchronization is consistently set in forms such as describing the three requirements of the critical section problem, comparing the difference between semaphore and mutex (especially ownership), explaining the operation of monitors and condition variables, and designing semaphore solutions to the producer-consumer and readers-writers problems. As an answer-composition strategy, a deep-level, differentiated answer results if one: ① presents the race condition → the need for synchronization with the lost-update example in the overview, ② explains the three critical-section conditions each bundled with its failure mode, ③ organizes semaphore, mutex, and monitor along the axes of ownership and abstraction level together with a comparison table, ④ picks one classic problem and develops its solution code in pseudocode, and ⑤ in the conclusion connects the transition into deadlock, starvation, and priority inversion with the extension to distributed and multicore environments. Studying [[deadlock]], [[race-condition]], and [[priority-inversion]] bundled together can broadly cover the exam's scope.

6. Considerations and Implications (Professional Engineer Perspective)

  1. Synchronization is a trade-off between correctness and performance. Taking the lock scope (critical section) wide is safe but kills parallelism, while taking it narrow raises performance but increases bug risk. One must design the lock granularity to match resource contention, the number of cores, and response-time requirements, and apply layered optimizations such as reviving read parallelism with a ReadWriteLock or MVCC when the read proportion is high.

  2. Synchronization defects transition into deadlock, starvation, and priority inversion. A lock held for mutual exclusion invites a [[deadlock]]; neglecting fairness causes starvation; and in real-time systems [[priority-inversion]] occurs. Therefore synchronization design must be approached not as a single technique but as an integrated design that considers lock ordering, timeouts, priority inheritance, and aging together.

  3. Prefer high-level abstractions but understand the principles. Using verified high-level tools such as monitors, ReadWriteLock, and concurrent collections reduces misuse better than handling a semaphore's P/V by hand. But one must understand that their interiors ultimately stand on atomic instructions and memory barriers, in order to diagnose performance bottlenecks and subtle visibility bugs. In particular, the rule that a condition variable must be re-checked with while because of the monitor's Mesa semantics shows that understanding internal behavior is essential even when using an abstraction.

  4. Observability and automated verification are the heart of operations. Because synchronization bugs are hard to reproduce, an approach that monitors lock wait time, contention counts, and thread dumps to catch them early, and proves the absence of latent race conditions and deadlock-freedom before operations with ThreadSanitizer, static analysis, concurrency testing, and formal verification (TLA+, model checking), is recommended in high-reliability systems.

  5. In distributed and cloud environments the boundary of synchronization widens. Beyond a single process's mutex, distributed locks, idempotency, and optimistic concurrency control become new means of synchronization. Presuming network partitions and partial failures, reducing shared mutable state itself where possible (immutability, event sourcing) and designing with communication-based coordination raises resilience.

  6. Treat the correlation between synchronization granularity and scalability as a design metric. As the number of cores grows, a coarse-grained lock rapidly loses the gains of parallelization according to Amdahl's law. Therefore one should transition to structures that reduce contention itself — lock striping, read-copy-update (RCU), optimistic locking, sharded counters — and take a data-driven approach that quantifies contention points through performance profiling and adjusts granularity incrementally.

  7. Synchronization design must secure reliability by proof, not by testing. Concurrency defects manifest only under particular timing and are seldom reproduced by ordinary unit tests. Therefore it is best practice for high-reliability systems to apply, incrementally, concurrency-testing frameworks that aid deterministic reproduction, ThreadSanitizer that catches data races at runtime, and model checking (TLA+, SPIN) that mathematically proves the deadlock-freedom, safety, and liveness of a concurrency protocol. The key is assurance at the level of "it has been shown that a race condition is impossible under these conditions," not "it passed the tests."

References

In one line: Process synchronization formalizes the critical section problem with the three conditions of mutual exclusion·progress·bounded waiting, and stacks semaphore·mutex·monitor on top of atomic instructions to guarantee the consistency and execution order of shared resources, while it must be designed holistically — covering the transition into deadlock·starvation·priority inversion as well as memory visibility and distributed locks — as the core technique of concurrency.