Concurrency Control: Race Conditions, Mutual Exclusion, and Semaphores
1️⃣ Concept of Concurrent Processes and Race Conditions
2️⃣Principles of Mutual Exclusion Techniques and Semaphores
3️⃣ Practice on Implementing Critical Sections Using Mutual Exclusion
Concurrent Processes and Mutual Exclusion
In this session, we explore concurrent processes and mutual exclusion.
In the previous session, we examined CPU scheduling; the problem of how the operating system decides the order in which multiple processes are allocated the CPU. However, in a computer system, the question of who uses the CPU first is not the only concern. As multiple processes and threads run simultaneously, situations naturally arise where they attempt to use the same resource at the same time. This session examines how processes can safely use resources in such situations.
이번 시간에는 병행 프로세스와 상호배제에 대해 살펴본다.
지난 시간에는 CPU 스케줄링을 다루면서, 여러 프로세스가 CPU를 사용하려 할 때 운영체제가 어떤 순서로 CPU를 할당할지 결정하는 문제를 살펴보았다. 그런데 컴퓨터 시스템에서는 단순히 CPU를 누가 먼저 쓰느냐의 문제만 있는 것이 아니다. 여러 프로세스와 스레드가 동시에 실행되다 보면, 같은 자원을 함께 사용하려는 상황이 자연스럽게 발생한다. 이번 시간에는 이러한 상황에서 프로세스들이 자원을 어떻게 안전하게 사용할 수 있는지를 살펴본다.
Shared Resource Problem; Online Banking Example
Let's look at a concrete example. Suppose a bank account has a balance of $100 in an online banking system. If two users simultaneously request to withdraw $80 each, what will the final balance be?
The expected outcome is straightforward: the first user withdraws $80, leaving $20, and the second user's withdrawal is denied due to insufficient funds. However, when both requests are processed simultaneously, a completely different result can occur. If both requests read the balance as \(100 before either withdrawal is recorded, both withdrawals may be approved, leaving the account at -\)60. This illustrates how simultaneous access to shared resources can produce unexpected results.
Shared Resource Problem; Global Variable Counter Example
Now let's look at a situation that can occur inside a program. Suppose there is a global variable counter initialized to 0. If two threads each perform the count++ increment operation 100,000 times, will the final result always be 200,000?
Intuitively, since each thread increments by 100,000, the result seems like it should be 200,000. However, in practice, this is not always the case. The count++ operation is not a single step — internally, it consists of three stages: reading the variable, adding 1, and storing the result. Without synchronization, if one thread reads the value before another thread has stored its result, both threads may operate on the same value, causing one increment to be lost. This is why the final result can be less than 200,000.
공유 자원 문제; 온라인 뱅킹 예시
이를 구체적인 예시로 살펴보자. 온라인 뱅킹 시스템에서 어떤 계좌의 잔액이 100달러라고 가정한다. 이때 두 사용자가 거의 동시에 각각 80달러씩 출금을 요청한다면 최종 잔액은 어떻게 될까?
공유 자원 문제; 전역 변수 카운터 예시
이번에는 프로그램 내부에서 발생할 수 있는 상황을 살펴보자. 전역변수 카운터가 하나 있고, 이 변수는 0으로 초기화되어 있다. 여기서 두 개의 스레드가 각각 10만 번씩 count++ 증가 연산을 수행한다고 할 때, 최종 결과는 항상 20만이 될까?
1️⃣ Concept of Concurrent Processes and Race Conditions
The Concept of Concurrent Execution
We have seen through the banking and counter examples how problems arise when simultaneous requests come in. To understand why this happens, let's first look at the concept of concurrent execution.
We have learned that the operating system does not allow a single process to monopolize the CPU. Instead, it switches CPU allocation between multiple processes so rapidly that it appears as though multiple execution flows are running simultaneously. This is called time-sharing. In reality, however, only one process executes on the CPU at any given moment.
In other words, while it may appear that multiple execution flows are running simultaneously, they are actually taking turns in an alternating structure. This form of execution, where flows cross and alternate with one another, is called interleaving, and this overall mechanism is referred to as concurrent execution.
병행 실행의 개념
앞서 계좌 출금 문제와 카운터 문제를 통해 동시 요청이 들어오는 상황을 살펴보았다. 이제 이런 상황이 왜 발생하는지 이해하기 위해 병행 실행의 개념을 먼저 살펴본다.
우리는 그동안 운영체제가 하나의 프로세스가 CPU를 계속 독점하도록 두지 않고, 여러 프로세스가 CPU를 번갈아 사용할 수 있도록 CPU 점유를 매우 빠르게 전환하며 실행한다는 것을 배웠다. 이처럼 CPU 사용이 빠르게 전환되기 때문에 겉으로 보기엔 여러 실행 흐름이 동시에 이루어지는 것처럼 보이는데, 이를 시 분할 방식(Time-sharing)이라고 부른다. 그러나 실제로는 한 순간에 하나의 프로세스만이 CPU에서 실행된다.
즉, 여러 실행 흐름이 동시에 수행되는 것처럼 보이지만 실제로는 실행 흐름이 번갈아 수행되는 구조인 것이다. 이처럼 실행 흐름이 서로 교차하면서 수행되는 형식을 교차(interleaving) 형태라고 하며, 이러한 방식을 병행 실행이라고 한다.
Concurrency vs. Parallelism
There is an important distinction to be made in relation to concurrent execution: the difference between concurrency and parallelism.
Concurrency refers to multiple execution flows taking turns on a single CPU. They are not actually running at the same time, but because they alternate in an interleaving fashion, they appear to run simultaneously in a logical sense. Parallelism, on the other hand, means that multiple execution flows are actually running at the same time across multiple CPUs.
Therefore, in a single-core environment, only concurrency is possible, while in a multi-core environment, parallel execution becomes possible. Although these two concepts may look similar, their execution structures are different and should be understood as distinct.
동시성과 병렬성
병행 실행과 관련하여 한 가지 개념을 구분할 필요가 있다. 바로 동시성과 병렬성이다.
먼저 동시성은 하나의 CPU에서 여러 실행 흐름이 번갈아 수행되는 방식이다. 실제로 동시에 실행되는 것은 아니지만, 앞서 살펴본 interleaving 형식으로 교차 실행되기 때문에 논리적으로는 동시에 실행되는 것처럼 보인다. 반면 병렬성은 여러 CPU에서 실행 흐름이 실제로 동시에 실행되는 것을 의미한다.
따라서 단일 코어 환경에서는 동시성만 가능하고, 멀티코어 환경에서는 병렬 실행이 가능하다. 이 두 개념은 겉으로 보기엔 비슷해 보이지만 실행 구조가 다르기 때문에 구분해서 이해할 필요가 있다.
2) Shared Resources and Types of Concurrent Processes
Shared Resources
A shared resource refers to a resource that two or more execution flows access simultaneously. Global variables, memory regions, and buffers are representative examples. When multiple execution flows use a single resource together, that shared resource can directly affect the outcome of execution. Therefore, in a concurrent execution environment, how shared resources are accessed and managed becomes a critical issue.
Consider a diagram showing two processes sharing a portion of memory. The region where both processes access the same memory area is called the shared region. In other words, when multiple processes use a single resource together, a shared region is created.
2. 공유 자원과 병행 프로세스 유형
공유 자원
공유 자원이란 둘 이상의 실행 흐름이 동일한 자원에 접근하는 상황을 의미한다. 전역 변수, 메모리 영역, 버퍼 등이 이에 해당하는 대표적인 예시이다. 이처럼 하나의 자원을 여러 실행 흐름이 함께 사용하게 되면, 공유 자원이 실행 결과에 직접적인 영향을 줄 수 있다. 따라서 병행 실행 환경에서는 이러한 공유 자원에 어떻게 접근하고 관리하느냐가 중요한 문제가 된다.
프로세스 1과 프로세스 2가 일부 메모리 영역을 함께 사용하고 있는 그림을 살펴보자. 이처럼 두 프로세스가 같은 메모리 영역에 접근하는 부분을 공유 영역이라고 한다. 즉, 여러 프로세스가 하나의 자원을 함께 사용하게 되면 이처럼 공유 영역이 발생하게 된다.
Types of Concurrent Processes Based on Shared Resources
Concurrent processes can be classified into two types based on whether they share resources.
An independent process does not share resources with other processes. As a result, it does not affect the execution of other processes, and it always produces the same result regardless of execution order. A cooperative process, on the other hand, shares one or more resources with other processes, meaning the result can vary depending on the order of execution. In other words, whether or not resources are shared is the starting point of concurrency problems.
공유 자원에 따른 병행 프로세스 구분
공유 자원의 여부에 따라 병행 프로세스를 두 가지로 구분할 수 있다.
먼저 독립 프로세스는 다른 프로세스와 자원을 공유하지 않는 프로세스이다. 따라서 다른 프로세스의 실행에 서로 영향을 주지 않으며, 실행 순서가 어떻든 항상 동일한 결과가 나온다. 반면 협력 프로세스는 하나 이상의 자원을 서로 공유하는 프로세스로, 실행 순서에 따라 결과가 달라질 수 있다. 즉, 자원을 공유하는지의 여부가 병행 문제의 출발점이 된다고 볼 수 있다.
Shared Resource Access Example
Let's examine a concrete example of how shared resources are accessed. Suppose two processes access the same global variable count. The initial value is int count = 0, and Process A and Process B each perform a count++ increment operation.
If these two processes run nearly simultaneously, will the final result always be 2? Intuitively, since each process increments by 1, the result seems like it should be 2. However, in practice, this is not always the case. The reason will be examined step by step through the execution process.
공유 자원 접근 예시
공유 자원에 대한 접근 상황을 구체적인 예시로 살펴보자. 두 개의 프로세스가 동일한 전역변수 count에 접근한다고 가정한다. 초기값은 int count = 0이고, Process A와 Process B가 각각 count++ 증가 연산을 수행한다.
만약 이 두 프로세스가 거의 동시에 실행된다면 최종 결과는 항상 2가 될까? 직관적으로 보면 각 프로세스가 1씩 증가시키기 때문에 결과는 2가 될 것처럼 보인다. 하지만 실제 실행에서는 항상 그런 결과가 나오지 않을 수도 있다. 왜 그런지는 실행 과정을 통해 차차 살펴본다.
How count++ Is Executed
The count++ increment operation may look like a single step, but it is actually carried out in multiple stages. First, in the Load stage, the current value of count is read from memory. Next, in the Add stage, 1 is added to the value that was read. Finally, in the Store stage, the calculated result is written back to memory. In other words, the count++ operation consists of three stages: Load, Add, and Store.
The critical point here is that these three stages do not constitute a single atomic operation. An atomic operation is one that executes as a single indivisible unit without being interrupted — meaning no other execution flow can intervene once the operation has begun. Since count++ is broken down into three separate stages, another thread or process can intervene in between, which can cause the execution stages of different processes to become mixed together.
count++의 실행 과정
count++ 증가 연산은 하나의 연산처럼 보이지만 실제로는 여러 단계로 나누어 수행된다. 먼저 Load 단계에서 메모리에 있는 count 값을 읽어오고, Add 단계에서 읽어온 값에 1을 더한 다음, 마지막 Store 단계에서 계산 결과를 다시 메모리에 저장한다. 즉 count++ 연산은 Load, Add, Store의 세 단계로 이루어진다.
여기서 중요한 점은 이 세 단계가 하나의 원자적 연산이 아니라는 것이다. 원자적 연산이란 연산이 중간에 끊기지 않고 하나의 단위로 실행되는 연산, 즉 다른 실행 흐름의 중간 개입 없이 한 번에 실행되는 연산을 의미한다. 그러나 count++ 연산은 세 단계로 나누어 실행되기 때문에 그 중간에 다른 스레드나 프로세스가 개입할 수 있고, 그로 인해 실행 단계가 서로 섞이는 문제가 발생할 수 있다.
In Sequence 1, if process A completes all three stages — Load, Add, Store — before process B begins, the result is the expected value of 2. However, in a concurrent execution environment, these stages are not guaranteed to run in order.
In Sequence 2, the stages can become interleaved. Process A first reads the value of count (Load) and adds 1 (Add), but before storing the result, process B also reads count. Since the value is still 0 at this point, process B also adds 1 to 0. Process A then stores its result, setting count to 1, and process B stores its result, overwriting count with 1 as well. Because both processes based their calculations on the same value of 0, the final result is 1, not 2.
This crossing of execution stages is called interleaving. The core of this problem is that both processes calculate based on the same value and overwrite each other's results, causing one increment operation to go unrecorded. This is precisely why problems occur when shared resources are accessed simultaneously.
실행 단계의 교차로 인한 문제
실행 단계가 어떻게 섞일 수 있는지 자세히 살펴보자. 프로세스 A와 B가 동시에 count++를 수행한다고 가정한다.
먼저 순서 1처럼 프로세스 A가 Load, Add, Store를 모두 수행한 뒤에 프로세스 B가 순서대로 수행한다면 결과값은 우리가 원하는 2가 된다. 그러나 병행 실행 환경에서는 이 실행 단계가 반드시 순서대로 수행되는 것은 아니다.
예를 들어 순서 2처럼 실행 단계가 교차될 수 있다. 프로세스 A가 먼저 count 값을 읽어오고(Load), 이어서 1을 더하는 연산(Add)까지 수행한다. 그런데 아직 그 결과를 저장하기 전에 프로세스 B가 실행되면서 마찬가지로 count 값을 읽어오게 된다. 이때 count 값은 아직 0이기 때문에 프로세스 B도 동일하게 1을 더하는 연산을 수행하게 된다. 이후 프로세스 A가 먼저 결과를 저장하여 count 값이 1이 되고, 프로세스 B도 자신의 계산 결과를 저장하면서 count 값을 1로 덮어쓰게 된다. 즉 두 프로세스가 모두 0을 기준으로 계산을 수행했기 때문에 최종 결과는 2가 아니라 1이 된다.
이처럼 실행 단계가 서로 교차하면서 수행되는 형태를 interleaving, 즉 실행 단계의 교차라고 할 수 있다. 이 문제의 핵심은 두 프로세스가 같은 값을 기준으로 계산하고 그 결과를 덮어쓰면서 증가 연산이 한 번만 반영되는 상황이 발생한다는 점이다. 바로 이러한 이유 때문에 공유 자원에 동시에 접근할 때 문제가 발생하는 것이다.
Race Condition
When multiple execution flows simultaneously access shared resources in a concurrent execution environment, the result can vary depending on the order of execution. This situation is called a race condition. It refers to the phenomenon where non-atomic operations on shared resources become interleaved, causing execution results to differ.
The key characteristic of a race condition is that even the same program can produce different results each time it runs, making it difficult to predict outcomes based on execution order.
There are two causes of race conditions. The first is that multiple execution flows use the same shared resource. The second is that operations are not performed atomically — that is, they are non-atomic operations. When both conditions exist simultaneously, the possibility of a race condition arising in a concurrent execution environment emerges.
Consider a diagram where a single variable count is shared by two processes — one incrementing and the other decrementing it. When these two operations are interleaved, the result may differ from what we expect. Depending on which operation executes first, the result changes. This is how race conditions arise when multiple execution flows access shared resources simultaneously.
경쟁 상태 (Race Condition)
병행 실행 환경에서 공유 자원에 여러 실행 흐름이 동시에 접근하게 되면 실행 순서에 따라 결과가 달라질 수 있다는 것을 앞서 살펴보았다. 이런 상태를 경쟁 상태(Race Condition)라고 한다. 이는 공유 자원에 대한 비원자적 연산이 서로 교차되면서 실행 결과가 달라지는 현상을 의미한다.
경쟁 상태의 특징은 프로그램이 동일하더라도 실행할 때마다 결과가 달라질 수 있다는 점이다. 즉 실행 순서에 따라 결과를 예측하기 어려운 상황이 발생한다.
경쟁 상태가 발생하는 원인에는 두 가지가 있다. 첫 번째는 여러 실행 흐름이 동일한 공유 자원을 사용한다는 점이고, 두 번째는 연산이 원자적으로 수행되지 않는다는 점, 즉 비원자적 연산이라는 점이다. 이 두 가지 조건이 동시에 존재할 때 병행 실행 환경에서 경쟁 상태가 발생할 가능성이 생기게 된다.
그림을 보면 하나의 변수 count가 두 프로세스에 의해 공유되고 있는 상황을 확인할 수 있다. 프로세스 1은 카운터를 증가시키고, 프로세스 2는 카운터를 감소시키는 역할을 한다. 이 두 연산이 교차되면서 실행되면 우리가 예상한 결과값과 다르게 나타날 수 있다. 어떤 실행을 먼저 하느냐에 따라 결과값이 달라지는 것이다. 이처럼 공유 자원에 여러 실행 흐름이 동시에 접근하게 되면 실행 순서에 따라 결과가 달라지는 경쟁 상태가 발생할 수 있다.
Problems Caused by Race Conditions
Race conditions can lead to several serious problems.
First, data integrity can be compromised. Multiple execution flows modifying data simultaneously can cause shared data to be changed to unintended values, leading to calculation errors. What makes this particularly problematic is that these errors do not occur every time — they only appear under specific execution orders. The same program may behave correctly in some runs and produce unexpected results in others. Because errors are difficult to reproduce, debugging becomes extremely challenging. Ultimately, these issues undermine the overall reliability of the system.
Therefore, in a concurrent execution environment, it is essential to protect the critical code regions that access shared resources. From this perspective, the next step is to examine which resources need to be protected and where in the code those resources are accessed.
경쟁 상태로 인한 문제
경쟁 상태가 발생하면 어떤 문제가 생기는지 살펴보자.
먼저 데이터의 무결성(integrity)이 훼손될 수 있다. 여러 실행 흐름이 동시에 데이터를 수정하면서 공유 데이터가 의도하지 않은 값으로 변경될 수 있고, 이로 인해 계산 결과의 오류가 발생할 수도 있다. 이러한 오류는 항상 발생하는 것이 아니라 특정 실행 순서에서만 나타난다는 점이 더 큰 문제이다. 같은 프로그램을 실행하더라도 어떤 경우에는 정상적으로 동작하지만, 어떤 경우에는 예상과 다른 결과가 나타날 수 있다. 이처럼 오류의 재현이 어렵기 때문에 디버깅도 매우 어려워진다. 결국 이런 문제들은 전체적으로 시스템 신뢰성을 떨어뜨리는 원인이 된다.
따라서 병행 실행 환경에서는 공유 자원에 접근하는 중요한 코드 영역을 반드시 보호할 필요가 있다. 이런 관점에서 보호해야 할 대상이 어떤 자원인지, 그리고 그 자원에 접근하는 코드 영역이 어디인지를 다음으로 살펴본다.
Critical Resources and Critical Sections
To distinguish between resources and code regions, the terms critical resource and critical section are used.
A critical resource is a resource shared by multiple processes where simultaneous access can cause problems. Shared variables, memory, files, and buffers are typical examples. Because simultaneous access to critical resources can cause race conditions, the code regions that access these resources are separately identified and managed — these regions are called critical sections. Multiple processes must not enter a critical section simultaneously; it must be guaranteed that only one process can be inside the critical section at any given time.
임계 자원과 임계 영역
자원과 코드 영역을 구분하기 위해 임계 자원과 임계 영역이라는 용어를 사용한다.
먼저 임계 자원은 여러 프로세스가 공유하는 자원 중에서 동시에 접근하면 문제가 발생할 수 있는 자원을 의미한다. 공유 변수, 메모리, 파일, 버퍼 등이 임계 자원의 대표적인 예시이다. 이러한 임계 자원에 여러 프로세스가 동시에 접근하면 경쟁 상태가 발생할 수 있기 때문에, 임계 자원에 접근하는 코드 영역을 따로 구분하여 관리하는데 이 영역을 임계 영역이라고 한다. 이 영역에는 여러 프로세스가 동시에 들어가면 안 되며, 한 번에 하나의 프로세스만 임계 영역에 들어갈 수 있도록 보장해야 한다.
The diagram shows a situation where an input process and an output process share a single buffer. The input process stores data into the buffer, while the output process retrieves data from the buffer and outputs it. If both processes access the buffer simultaneously, the data may not be processed correctly. Therefore, the code region that accesses this buffer is referred to as a critical section, and access to this region must be controlled so that only one process can enter at a time.
그림을 보면 입력 프로세스와 출력 프로세스가 하나의 버퍼를 공유하는 상황을 확인할 수 있다. 입력 프로세스는 데이터를 버퍼에 저장하고, 출력 프로세스는 버퍼에서 데이터를 꺼내 출력하는 역할을 한다. 이때 두 프로세스가 버퍼에 동시에 접근하게 되면 데이터가 정상적으로 처리되지 않을 수 있다. 따라서 이 버퍼에 접근하는 코드 부분을 임계 영역이라고 하며, 이러한 영역에서는 한 번에 하나의 프로세스만 접근할 수 있도록 제어해야 한다.
Structure of a Critical Section
A critical section follows a specific structure within a program.
The first part is the Entry Section. This is where a process acquires a lock before entering the critical section. A lock is conceptually similar to locking a door to prevent other processes from entering.
The second part is the Critical Section itself. This is the code region where the process actually accesses the shared resource — the area where the core work takes place.
The third part is the Exit Section. Once work in the critical section is complete, the process moves here and performs an unlock, releasing the lock so that other processes can enter the critical section.
The final part is the Remainder Section. This is the general code region unrelated to shared resources.
A process repeatedly cycles through this structure during execution.
임계 영역의 구조
임계 영역은 프로그램 안에서 다음과 같은 구조로 사용된다.
첫 번째는 진입 영역(Entry Section)이다. 임계 영역에 들어가기 전에 lock을 획득하는 과정이 이루어진다. lock은 임계 영역에 다른 프로세스가 들어오지 못하도록 문을 잠그는 것과 비슷한 개념이다.
두 번째는 임계 영역(Critical Section)이다. 공유 자원에 실제로 접근하는 코드 영역으로, 핵심 작업이 이루어지는 부분이다.
세 번째는 탈출 영역(Exit Section)이다. 임계 영역에서의 작업이 끝나면 이 영역으로 이동하여 unlock을 수행한다. 문을 여는 것처럼 lock을 해제하여 다른 프로세스가 임계 영역에 들어올 수 있도록 한다.
마지막으로 나머지 영역(Remainder Section)이다. 공유 자원과 관련 없는 일반적인 코드 영역이다.
프로세스는 이러한 구조를 반복적으로 수행하면서 실행된다.
Conditions for Solving the Critical Section Problem
Three conditions must be satisfied to solve the critical section problem.
The first is Mutual Exclusion. Only one process may be inside the critical section at a time; two or more processes must not enter the critical section simultaneously.
The second is Progress. If the critical section is empty and a process wishes to enter, that process must be allowed to do so. A situation where a process is forced to wait even though the critical section is available must not occur.
The third is Bounded Waiting. If a process has requested entry into the critical section, it must not be made to wait indefinitely. After a finite amount of time, it must be guaranteed entry.
To solve the critical section problem, all three conditions — mutual exclusion, progress, and bounded waiting — must be satisfied. The operating system uses mutual exclusion techniques that meet these three conditions to protect critical sections. The next section will examine the mutual exclusion techniques designed to satisfy these requirements.
임계 영역 문제를 해결하기 위한 조건
임계 영역 문제를 해결하기 위해서는 다음 세 가지 조건을 만족해야 한다.
첫 번째는 상호 배제(Mutual Exclusion)이다. 임계 영역에 한 번에 하나의 프로세스만 들어갈 수 있어야 하며, 두 개 이상의 프로세스가 동시에 임계 영역에 들어가면 안 된다.
두 번째는 진행(Progress)이다. 임계 영역이 비어 있고 어떤 프로세스가 그 임계 영역에 들어가려 한다면, 해당 프로세스는 반드시 들어갈 수 있어야 한다. 즉 임계 영역을 사용할 수 있는 상황임에도 불구하고 계속 기다려야 하는 상황이 발생해서는 안 된다.
세 번째는 한정 대기(Bounded Waiting)이다. 어떤 프로세스가 임계 영역에 들어가길 요청했다면 무한히 기다리는 상황이 발생해서는 안 되며, 일정 시간이 지나면 반드시 임계 영역에 들어갈 수 있어야 한다.
이처럼 임계 영역 문제를 해결하기 위해서는 상호 배제, 진행, 한정 대기 세 가지 조건을 모두 만족해야 한다. 따라서 운영체제는 이 세 가지를 만족하는 상호 배제 기법을 이용하여 임계 영역을 보호하며, 다음에서는 이 조건을 만족하기 위한 상호 배제 기법에 대해 살펴볼 예정이다.
2️⃣Principles of Mutual Exclusion Techniques and Semaphores
Types of Mutual Exclusion Techniques
In this section, we study the mutual exclusion techniques used to protect critical sections, as well as the principles behind semaphores. The focus is on the problems that arise when multiple processes simultaneously access a critical section, and the methods used to resolve them.
Mutual exclusion techniques for solving the critical section problem can be divided into three categories based on their implementation approach.
The first is software-based mutual exclusion. This approach controls the critical section using only shared variables, without any hardware support. However, it is characterized by the occurrence of busy waiting; a process continuously checks the state by repeating a while loop until a condition changes, occupying the CPU without doing any useful work, making it an inefficient waiting method.
The second is hardware-based mutual exclusion. This approach controls access to the critical section using atomic operations such as Test-and-Set. An atomic operation is one that executes as a single indivisible unit, meaning no other process can intervene once it has started — it completes in one step without interruption. Using such atomic operations allows safe control of shared resource access even when multiple processes run simultaneously. However, this approach also suffers from busy waiting.
The third is the semaphore. This is a synchronization technique that controls process execution using wait and signal operations, and operates on a block and wake-up basis.
The principles behind each of these techniques will be examined one by one, and related terminology will be reviewed again later.
상호 배제 기법의 종류
이번에는 임계 영역을 보호하기 위한 상호 배제 기법과 세마포어의 원리에 대해 공부한다. 임계 영역에서 여러 프로세스가 동시에 접근할 때 발생하는 문제와 이를 해결하는 방법을 중심으로 알아본다.
임계 영역 문제를 해결하기 위한 상호 배제 기법은 구현 방식에 따라 세 가지로 나뉜다.
첫 번째는 소프트웨어 기반의 상호 배제이다. 이 방식은 별도의 하드웨어 지원 없이 공유 변수만을 사용하여 임계 영역을 제어한다. 그러나 계속해서 상태를 확인하며 기다리는 busy waiting이 발생한다는 특징이 있다. 이는 조건이 바뀔 때까지 while문을 반복하며 상태를 계속 확인하는 방식으로, 아무 작업도 하지 않으면서 CPU를 계속 점유한 채 기다리기 때문에 비효율적인 대기 방식이다.
두 번째는 하드웨어 기반의 상호 배제이다. Test-and-Set과 같은 원자적 연산을 사용하여 임계 영역에 대한 접근을 제어한다. 원자적 연산이란 연산이 하나의 단위로 실행되어 중간에 다른 프로세스가 개입할 수 없는 연산, 즉 시작되면 중간에 끊기지 않고 한 번에 완료되는 연산을 의미한다. 이러한 원자적 연산을 사용하면 여러 프로세스가 동시에 실행되더라도 공유 자원에 대한 접근을 안전하게 제어할 수 있다. 그러나 이 방식 역시 busy waiting이 발생한다는 특징이 있다.
세 번째는 세마포어이다. wait, signal 연산을 사용하여 프로세스의 실행을 제어하는 방식으로, block과 wake-up 방식으로 동작하는 동기화 기법이다.
이 기법들이 어떤 원리로 동작하는지는 하나씩 살펴보고, 관련 용어들도 이후에 다시 한번 정리해볼 것이다.
Software-Based Mutual Exclusion
Software-based mutual exclusion is an approach that resolves the critical section problem using only code, without any hardware assistance. The fundamental problem to solve is preventing two processes from entering the critical section simultaneously — that is, mutual exclusion must be strictly guaranteed. The key question is whether this can be achieved without special hardware instructions.
The basic strategy involves two shared variables. The first is a variable that indicates a process's intention to enter the critical section, called the flag. The second is a variable that determines which process has priority when both attempt to enter simultaneously, called turn. In summary, software-based mutual exclusion controls critical section entry using the shared variables flag and turn.
소프트웨어 기반 상호 배제(Mutual Exclusion)
소프트웨어 기반 상호 배제는 하드웨어의 도움 없이 코드만으로 임계 영역 문제를 해결하려는 방법이다. 이때 해결해야 할 기본 문제는 두 프로세스가 동시에 임계 영역에 들어가지 못하도록 하는 것, 즉 상호 배제를 반드시 보장하는 것이다. 그리고 이러한 문제를 하드웨어의 특별한 명령 없이 해결할 수 있는지가 핵심이다.
이를 위해 사용되는 기본 전략은 두 가지 공유 변수를 활용하는 것이다. 첫 번째는 프로세스가 임계 영역에 들어가려는 의사를 표시하는 변수로, 이를 flag라고 부른다. 두 번째는 두 프로세스가 동시에 들어가려 할 때 어느 프로세스가 먼저 들어갈 것인지 우선순위를 결정하는 변수로, 이를 turn이라고 한다. 즉 소프트웨어 기반 상호 배제는 flag와 turn이라는 공유 변수를 사용하여 임계 영역 진입을 제어하는 방식이다.
Prerequisites of Software-Based Mutual Exclusion
Software-based mutual exclusion has several prerequisites. First, the problem is solved using only shared variables such as flag to check each other's state. Second, no atomic hardware instructions such as Test-and-Set are used; the solution is purely software-based. Third, this approach assumes that only two processes exist.
The representative algorithms that implement this approach are the Dekker algorithm and the Peterson algorithm. The following sections focus on the Dekker algorithm to examine how it works.
소프트웨어 기반 상호 배제의 전제 조건
소프트웨어 기반 상호 배제에는 몇 가지 전제 조건이 있다. 먼저 flag와 같은 공유 변수만을 사용하여 서로의 상태를 확인하는 방식으로 문제를 해결한다. 또한 Test-and-Set과 같은 원자적 하드웨어 명령은 사용하지 않고 순수하게 소프트웨어적인 방법으로 해결한다. 그리고 이 방법은 두 개의 프로세스만 존재한다고 가정한다.
이 방법을 구현하는 대표적인 알고리즘으로는 Dekker 알고리즘과 Peterson 알고리즘이 있으며, 이후에는 Dekker 알고리즘을 중심으로 동작 원리를 살펴볼 것이다.
Dekker Algorithm; Variable Structure
The Dekker algorithm uses two shared variables.
The first is the flag array, declared as boolean flag[2], which holds two elements. flag[0] represents process 0's intention to enter the critical section, and flag[1] represents process 1's. When a value is true, it means that process is attempting to enter the critical section. In the initial state, since neither process is inside the critical section, both are initialized as flag[0] = flag[1] = false.
The second is the turn variable, declared as int turn. It determines which process has priority when both attempt to enter the critical section simultaneously. turn is set to either 0 or 1, with its initial value indicating which process has the first priority.
Together, the flag and turn variables are used to prevent both processes from entering the critical section at the same time.
Dekker 알고리즘; 변수 구성
Dekker 알고리즘은 두 가지 공유 변수를 사용한다.
첫 번째는 flag 배열이다. boolean flag[2]로 선언되며 두 개의 원소를 가진다. flag[0]은 프로세스 0, flag[1]은 프로세스 1이 임계 영역에 들어가려는 의사를 나타낸다. 해당 값이 true이면 그 프로세스가 임계 영역 진입을 시도하는 상태임을 의미한다. 초기 상태에서는 두 프로세스 모두 임계 영역에 들어가지 않은 상태이므로 flag[0] = flag[1] = false로 초기화한다.
두 번째는 turn 변수이다. int turn으로 선언되며, 두 프로세스가 동시에 임계 영역에 들어가려 할 때 어느 프로세스에게 우선권을 줄 것인지를 결정하는 변수이다. turn은 0 또는 1로 설정되며, 초기값을 통해 처음 우선순위를 어느 프로세스에게 줄 것인지를 나타낸다.
이처럼 flag와 turn 변수를 함께 사용하여 두 프로세스가 동시에 임계 영역에 들어가지 못하도록 제어한다.
Overall Structure of the Dekker Algorithm
The Dekker algorithm's code is divided into three main parts. An important point is that this is a single shared piece of code used by both processes. Within the code, the currently executing process is referred to as i, and the other process as j.
The first part is the Entry Section. flag[i] = TRUE signals the current process's intention to enter the critical section. while(flag[j]) then checks whether the other process is also attempting to enter. If flag[j] is true, both processes are trying to enter simultaneously. Rather than entering immediately, the condition if(turn == j) checks whether the other process currently holds priority. If it does, flag[i] = FALSE is executed, temporarily abandoning the attempt to enter. while(turn == j) then waits until the priority changes. Once priority shifts, flag[i] = TRUE is set again and entry is reattempted. Through this process, when both processes attempt to enter simultaneously, one is made to yield, preventing any collision.
The second part is the Critical Section, the region where the shared resource is actually accessed.
The third part is the Exit Section. Once work in the critical section is complete, turn = j transfers priority to the other process, and flag[i] = FALSE indicates that the current process has exited the critical section, allowing the other process to enter.
Dekker 알고리즘의 전체 구조
Dekker 알고리즘의 코드는 크게 세 부분으로 나뉜다. 여기서 중요한 점은 이 코드가 두 프로세스가 함께 사용하는 하나의 코드라는 것이다. 따라서 코드 내에서 현재 실행 중인 프로세스를 i, 나머지 프로세스를 j로 표현한다.
첫 번째는 진입 영역(Entry Section)이다. flag[i] = TRUE를 통해 현재 프로세스가 임계 영역에 들어가겠다는 의사를 표시한다. 이후 while(flag[j])를 통해 다른 프로세스도 임계 영역에 들어가려는지 확인한다. 만약 flag[j]가 true라면 두 프로세스가 동시에 임계 영역에 들어가려는 상황이 발생한 것이다. 이때 바로 진입하는 것이 아니라 if(turn == j) 조건을 통해 현재 우선권이 다른 프로세스에 있는지 확인한다. 만약 우선권이 다른 프로세스에 있다면 flag[i] = FALSE를 실행하여 현재 프로세스는 잠시 임계 영역 진입을 포기한다. 그리고 while(turn == j)를 통해 우선권이 다시 바뀔 때까지 기다린다. 우선권이 바뀌게 되면 flag[i] = TRUE로 다시 설정하고 임계 영역 진입을 재시도한다. 이 과정을 통해 두 프로세스가 동시에 임계 영역에 들어가려 하더라도 한쪽이 양보하도록 만들어 충돌이 발생하지 않도록 제어한다.
두 번째는 임계 영역(Critical Section)이다. 실제로 공유 자원에 접근하는 영역이다.
세 번째는 탈출 영역(Exit Section)이다. 임계 영역 사용이 끝나면 turn = j로 변경하여 다른 프로세스에게 우선권을 넘겨주고, flag[i] = FALSE로 설정하여 현재 프로세스가 임계 영역을 벗어났음을 나타낸다. 이로써 다른 프로세스가 임계 영역에 진입할 수 있게 된다.
Dekker Algorithm Code Summary
Let's summarize the meaning of the code examined above.
In the Entry Section, flag[i] = TRUE signals the current process's intention to enter the critical section. while(flag[j]) checks whether the other process is also attempting to enter. The turn variable determines which process enters first when both attempt to do so simultaneously, when a conflict occurs, one process is made to yield and wait, preventing simultaneous entry.
The Critical Section is the region where the shared resource is actually accessed.
Once the critical section execution is complete, the Exit Section runs. turn = j passes priority to the other process, meaning that if both processes attempt to enter simultaneously next time, j will enter first. flag[i] = FALSE then indicates that the current process is no longer attempting to enter the critical section, allowing the other process to proceed.
Dekker 알고리즘 코드 정리
앞서 살펴본 코드의 의미를 다시 한번 정리해보자.
진입 영역(Entry Section)에서 flag[i] = TRUE는 현재 실행 중인 프로세스가 임계 영역에 들어가겠다는 의사 표시이다. while(flag[j])는 다른 프로세스도 임계 영역 진입을 시도하고 있는지 확인하는 부분이다. turn 변수는 두 프로세스가 동시에 진입하려 할 때 어느 쪽이 먼저 들어갈지 조정하는 역할을 한다. 즉 충돌이 발생하면 한 프로세스가 잠시 양보하고 기다리도록 만들어 동시에 진입하지 못하도록 제어하는 것이다.
임계 영역(Critical Section)은 공유 자원에 실제로 접근하는 구간이다.
임계 영역 실행이 끝나면 탈출 영역(Exit Section)이 실행된다. turn = j를 통해 다른 프로세스에게 우선권을 넘겨준다. 그렇게 되면 다음에 두 프로세스가 동시에 진입을 시도할 경우 j가 먼저 임계 영역에 들어갈 수 있게 된다. 그리고 flag[i] = FALSE로 설정하여 현재 프로세스가 더 이상 임계 영역 진입을 시도하지 않음을 나타낸다. 이 과정을 통해 다른 프로세스가 임계 영역에 진입할 수 있는 상태가 된다.
Dekker Algorithm; Simultaneous Entry Analysis
Based on the code examined above, let's walk through a scenario where two processes attempt to enter the critical section simultaneously. Assume P0 and P1 both set their flag to true at the same time, meaning both are trying to enter the critical section, and turn is initially 0.
In Step 1, flag[0] = TRUE and flag[1] = TRUE are set, indicating both processes intend to enter, and turn is 0.
In Step 2, P0 enters a waiting state because while(flag[1]) is true. P1 also waits because while(flag[0]) is true.
In Step 3, since turn is 0, priority belongs to P0. Therefore, P1 sets flag[1] = FALSE and temporarily gives up its attempt to enter.
In Step 4, P0's while(flag[1]) condition becomes false, allowing P0 to enter the critical section. P1 remains in a waiting state.
In summary, even when both processes attempt to enter simultaneously, only one process enters the critical section through the control of flag and turn. In particular, the turn variable determines which process enters first when a conflict occurs, ensuring that simultaneous entry into the critical section never happens.
Dekker 알고리즘; 동시 진입 상황 분석
앞서 살펴본 코드를 바탕으로 두 프로세스가 동시에 진입을 시도하는 상황을 단계별로 살펴보자. P0와 P1이 동시에 flag를 true로 설정한다고 가정한다. 즉 두 프로세스 모두 임계 영역에 들어가려는 상태이며, 이때 turn 값은 0이라고 가정한다.
1단계에서는 flag[0] = TRUE, flag[1] = TRUE로 설정되어 두 프로세스 모두 임계 영역 진입 의사를 표시하고, turn은 0인 상태이다.
2단계에서는 P0가 while(flag[1])이 true이므로 대기 상태에 들어가고, P1도 while(flag[0])이 true이므로 대기하게 된다.
3단계에서는 turn이 0이므로 우선권은 P0에 있다. 따라서 P1은 flag[1] = FALSE로 설정하고 임계 영역 진입을 잠시 포기한다.
4단계에서는 P0의 while(flag[1]) 조건이 false가 되어 임계 영역에 진입하게 되고, P1은 계속 대기 상태를 유지한다.
이를 정리하면, 두 프로세스가 동시에 진입을 시도하더라도 flag와 turn을 통해 하나의 프로세스만 임계 영역에 들어갈 수 있음을 확인할 수 있다. 특히 turn 변수는 충돌이 발생했을 때 어느 프로세스가 먼저 진입할지 결정하는 역할을 하며, 이로 인해 동시에 임계 영역에 진입하는 상황은 발생하지 않는다.
Dekker Algorithm; Satisfying the Three Conditions
The Dekker algorithm satisfies all three conditions required to solve the critical section problem.
The first is mutual exclusion. The flag and turn variables ensure that both processes cannot enter the critical section simultaneously.
The second is progress. If the critical section is empty and a process attempts to enter, that process is guaranteed to be able to do so.
The third is bounded waiting. The turn variable prevents any single process from continuously monopolizing the critical section.
Dekker 알고리즘; 3가지 조건 만족
Dekker 알고리즘은 임계 영역 문제에서 요구하는 세 가지 조건을 모두 만족해야 한다.
첫 번째는 상호 배제이다. flag와 turn 변수를 이용하여 두 프로세스가 동시에 임계 영역에 들어가지 못하도록 보장한다.
두 번째는 진행이다. 임계 영역이 비어 있고 어떤 프로세스가 진입을 시도한다면 반드시 한 프로세스는 들어갈 수 있다.
세 번째는 한정 대기이다. turn 변수를 통해 한 프로세스가 계속 임계 영역을 독점하는 상황을 방지한다.
Limitations of the Dekker Algorithm
Although the Dekker algorithm solves the critical section problem through a software approach, it has several limitations.
First, it can only be used with two processes. It is difficult to apply in environments with three or more processes.
Second, busy waiting occurs. The process continuously loops through a while statement while holding the CPU, making it inefficient.
Third, the algorithm's structure is relatively complex, making it difficult to use efficiently in real operating systems.
Due to these limitations, real systems tend to use hardware instructions or semaphores instead of the Dekker algorithm.
Dekker 알고리즘의 한계
Dekker 알고리즘은 임계 영역(Critical Section) 문제를 소프트웨어적으로 해결하지만 몇 가지 한계가 존재한다.
첫째, 두 개의 프로세스에서만 사용할 수 있다는 점이다. 셋 이상의 프로세스 환경에서는 적용하기 어렵다.
둘째, busy waiting이 발생한다. while문을 계속 반복하면서 CPU를 점유한 채로 기다리기 때문에 비효율적이다.
셋째, 알고리즘 구조가 비교적 복잡하기 때문에 실제 운영체제에서는 효율적으로 사용하기 어렵다.
이러한 한계로 인해 실제 시스템에서는 Dekker 알고리즘보다 하드웨어 명령어나 세마포어 같은 방법을 사용하게 된다.
Hardware-Based Mutual Exclusion
The software-based approach used shared variables to control the critical section, but it had limitations: complex implementation and busy waiting. To address this, operating systems can implement mutual exclusion using special instructions provided by hardware.
The key concept here is the atomic operation. An atomic operation is one that executes from start to finish without interruption. While a general operation involves multiple stages — reading memory, computing, and storing — an atomic operation performs the read and write as a single indivisible unit. Once started, no other process can intervene. By using atomic operations, it is possible to safely control critical section access even when multiple processes attempt simultaneous entry.
The most representative atomic operation instructions are Test-and-Set and Compare-and-Swap. The following sections examine Test-and-Set in greater detail.
하드웨어 기반의 상호 배제
앞서 소프트웨어 방식은 공유 변수를 이용하여 임계 영역(Critical Section) 제어했지만 구현이 복잡하고 busy waiting이 발생한다는 한계가 있었다. 이에 운영체제는 하드웨어가 제공하는 특별한 명령어를 이용하여 상호 배제를 구현하기도 한다.
이때 중요한 개념이 원자적 연산(Atomic Operation)이다. 원자적 연산은 중간에 끊기지 않고 한 번에 수행되는 연산이다. 일반적인 연산은 메모리를 읽고 계산하고 저장하는 여러 단계로 이루어지는 반면, 원자적 연산은 읽기와 쓰기 과정이 분리되지 않고 하나의 단위로 수행된다. 즉 연산이 시작되면 중간에 다른 프로세스가 끼어들 수 없고 한 번에 수행되는 구조이다. 따라서 이러한 원자적 연산을 이용하면 여러 프로세스가 동시에 접근하는 상황에서도 안전하게 임계 영역을 제어할 수 있다.
대표적인 원자적 연산 명령어로는 Test-and-Set과 Compare-and-Swap이 있으며, 이후에는 Test-and-Set 명령어를 더 자세히 살펴본다.
Hardware-Based Mutual Exclusion; Test-and-Set Operation
The Test-and-Set operation reads a memory value while simultaneously changing it. It first reads the value from memory, then sets it to true. Crucially, these two steps are not performed separately — they execute as a single unit. As a result, no other process can intervene while the operation is being performed.
The operation in code form is as follows:
boolean TestAndSet(boolean *lock) {
boolean old = *lock;
*lock = TRUE;
return old;
}
The current value of lock in memory is read and stored in old. Then lock is set to true, and the previous value old is returned. In other words, it returns the previous lock state while simultaneously setting the lock to true, and all of this happens atomically; no other process can intervene.
하드웨어 기반 상호 배제;Test-and-Set 연산
Test-and-Set 연산은 메모리 값을 확인하면서 동시에 값을 변경하는 연산이다. 먼저 메모리 값을 읽어오고, 그 값을 true로 설정한다. 여기서 중요한 점은 이 두 과정이 나누어서 실행되는 것이 아니라 한 번에 수행된다는 것이다. 따라서 연산이 수행되는 동안 다른 프로세스가 중간에 개입할 수 없다.
이 연산을 코드로 살펴보면 다음과 같다.
boolean TestAndSet(boolean *lock) {
boolean old = *lock;
*lock = TRUE;
return old;
}
먼저 메모리에 있는 lock 값을 읽어서 old 변수에 저장한다. 그리고 lock을 true로 설정한 뒤 이전 값인 old를 반환한다. 즉 이전 lock 상태를 반환하면서 동시에 lock을 true로 설정하는 연산이며, 이 모든 과정이 한 번에 수행되어 중간에 다른 프로세스가 개입할 수 없다.
Return Value of the Test-and-Set Operation
The core of the Test-and-Set operation lies in using its return value to determine whether a lock has been acquired.
If the return value is false, it means the lock was previously unoccupied, and the current process has successfully acquired it. Conversely, if the return value is true, it means another process already holds the lock, and the current process has failed to acquire it.
Test-and-Set 연산의 반환값
Test-and-Set 연산의 핵심은 반환값을 통해 잠금 획득 여부를 판단한다는 점이다.
반환값이 false라면 이전에 lock이 비어 있었다는 의미로, 현재 프로세스가 잠금을 획득한 상태이다. 반대로 반환값이 true라면 다른 프로세스가 이미 lock을 가지고 있다는 의미로, 현재 프로세스는 잠금을 획득하지 못한 상태이다.
Lock Structure Based on Test-and-Set
The basic idea of the Test-and-Set operation is to use a single lock variable and acquire the lock through the Test-and-Set operation.
Looking at the code, while(TestAndSet(&lock)) repeats until the lock is acquired. If the return value is true, another process already holds the lock, so the while loop continues waiting. If false is returned, the lock has been successfully acquired and the process enters the critical section. Once the critical section execution is complete, lock = FALSE is set to allow other processes to acquire the lock.
This structure has an important characteristic: the process repeatedly loops through the while statement until the lock is acquired. During this time, the process occupies the CPU while waiting; this is called busy waiting, meaning the CPU is continuously consumed while waiting for the lock to be released.
Test-and-Set 기반의 Lock 구조
Test-and-Set 연산의 기본 아이디어는 하나의 lock 변수를 두고 Test-and-Set 연산으로 잠금을 획득하는 방식이다.
코드를 살펴보면 while(TestAndSet(&lock))을 통해 lock을 획득할 때까지 반복한다. Test-and-Set의 반환값이 true라면 이미 다른 프로세스가 lock을 가지고 있는 상태이기 때문에 while문을 계속 반복하며 기다린다. 반대로 false가 반환되면 lock 획득에 성공한 것으로 임계 영역에 진입하게 된다. 임계 영역 실행이 끝나면 lock = FALSE로 설정하여 다른 프로세스가 lock을 획득할 수 있도록 한다.
이 구조에는 중요한 특징이 있다. while문을 반복하며 lock을 획득할 때까지 기다린다는 점이다. 이 과정에서 프로세스는 CPU를 사용한 채로 반복 대기하는데, 이를 busy waiting이라고 한다. 즉 CPU를 계속 사용하며 잠금이 해제되기를 기다리는 방식이다.
Limitations of the Simple Lock Approach
The simple lock approach has several limitations.
The first is CPU resource waste. The process continuously loops waiting for the lock to be released, occupying the CPU throughout, which is inefficient.
The second is a fairness problem. It is difficult to predict which process will acquire the lock first, so if a particular process repeatedly acquires the lock, other processes may be left waiting indefinitely.
The third is a scalability problem. As the number of processes increases, competition to acquire the lock intensifies, and the simple lock approach cannot easily account for priority among processes.
These limitations made it necessary to develop another synchronization technique to address them.
단순 Lock 방식의 한계
단순한 lock 방식에는 몇 가지 한계가 존재한다.
첫 번째는 CPU 자원 낭비 문제이다. 프로세스가 while문을 반복하면서 lock이 해제되기를 계속 기다리는 과정에서 CPU를 계속 사용하기 때문에 비효율적이다.
두 번째는 공정성 문제이다. 어떤 프로세스가 먼저 lock을 획득할지 예측하기 어렵기 때문에 특정 프로세스가 반복적으로 lock을 획득하게 되면 다른 프로세스는 계속 기다리는 상황이 발생할 수 있다.
세 번째는 확장성 문제이다. 프로세스 수가 늘어날수록 lock을 얻으려는 경쟁이 심해지며, 단순 lock 방식에서는 우선순위 고려가 어렵다.
이러한 한계로 인해 이를 해결하기 위한 또 다른 동기화 기법이 필요하게 되었다.
The Emergence of Semaphores
Semaphores emerged to overcome these limitations. The key idea is to not keep a waiting process running. If the critical section is unavailable, the process is transitioned to a waiting (blocked) state, and when the resource becomes available, it is woken up and resumed.
The spin approach — repeatedly looping through a while statement — is called spinning. Semaphores move away from this repeated waiting approach and instead put processes to sleep in a waiting queue, operating on a block basis. This synchronization technique that operates through block and wake-up is the semaphore.
세마포어의 등장
이러한 한계를 해결하기 위해 세마포어가 등장하였다. 핵심은 대기 중인 프로세스를 계속 실행시키지 않는 것이다. 즉 임계 영역을 사용할 수 없다면 해당 프로세스를 대기 상태로 전환하여 블락(block)시키고, 자원을 사용할 수 있게 되면 다시 깨워서 실행시키는 방식이다.
앞서 살펴본 while문을 반복하며 기다리는 방식을 스핀(spin)이라고 하는데, 세마포어는 이러한 반복 대기 방식에서 벗어나 프로세스를 대기 큐에서 잠들게 하는 block 방식으로 동작한다. 이처럼 block과 wake-up 방식으로 동작하는 동기화 기법이 세마포어이다.
Definition of a Semaphore
A semaphore is a synchronization technique that manages resource availability using an integer variable. This variable is not accessed directly, it is manipulated only through two operations: wait and signal.
wait is called when a process wishes to use a resource, and signal is called when a process has finished using a resource. Both operations are performed atomically to ensure no problems arise even when multiple processes access them simultaneously.
세마포어의 정의
세마포어는 정수형 변수를 이용하여 자원의 사용 여부를 관리하는 동기화 기법이다. 이 변수는 직접 접근하는 것이 아니라 wait와 signal이라는 두 연산을 통해서만 조작된다.
wait는 자원을 사용하려 할 때 호출되고, signal은 자원 사용이 끝날 때 호출된다. 이 두 연산은 여러 프로세스가 동시에 접근하더라도 문제가 발생하지 않도록 원자적으로 수행된다.
Basic Operation of a Semaphore
The basic operation of a semaphore in code form is as follows:
wait(S) {
S--;
if (S < 0)
block();
}
signal(S) {
S++;
if (S <= 0)
wakeup();
}
The wait operation decrements the semaphore value S by 1 (S--). If S becomes less than 0 (if (S < 0)), it means no resources are available, and the process is transitioned to a blocked state (block()).
The signal operation increments S by 1 (S++). If S is still 0 or less (if (S <= 0)), it means there are processes waiting, so one of them is woken up (wakeup()) and allowed to run.
세마포어의 기본 동작
세마포어의 기본 동작을 코드 형태로 살펴보자.
wait(S) {
S--;
if (S < 0)
block();
}
signal(S) {
S++;
if (S <= 0)
wakeup();
}
먼저 wait 연산은 세마포어 값 S를 1 감소시킨다(S--). 이후 S가 0보다 작다면(if (S < 0)) 사용 가능한 자원이 없다는 의미이므로 해당 프로세스를 block 상태로 전환한다(block()).
signal 연산은 세마포어 값 S를 1 증가시킨다(S++). 이후 S가 0 이하라면(if (S <= 0)) 대기 중인 프로세스가 있다는 의미이므로 그 중 하나를 깨워서(wakeup()) 실행하게 한다.
Structure of a Semaphore
A semaphore is not simply a single variable, it is a structure that includes a waiting queue for managing blocked processes.
struct semaphore {
int count;
queueType queue;
};
semaphore S;
A semaphore consists of a counter value and a waiting queue. The counter value represents the number of currently available resources. If S is greater than 0, a process can immediately enter the critical section. If S equals 0, no resources are available. If S is less than 0, there are processes waiting for the resource.
When wait is called, the process enters the waiting queue and is blocked. When signal is called, one process is removed from the waiting queue and woken up to resume execution.
세마포어의 구조
세마포어는 단순한 변수 하나가 아니라 대기 중인 프로세스를 관리하기 위한 대기 큐를 함께 사용하는 구조이다.
struct semaphore {
int count;
queueType queue;
};
semaphore S;
세마포어는 카운터 값과 대기 큐로 이루어져 있다. 카운터 값은 현재 사용 가능한 자원의 개수를 의미한다. S가 0보다 크면 즉시 임계 영역에 들어갈 수 있고, S가 0이면 사용 가능한 자원이 없는 상태이며, S가 0보다 작으면 자원을 기다리고 있는 프로세스가 있다는 의미이다.
이때 wait 연산이 호출되면 프로세스는 대기 큐에 들어가 block 상태가 되고, signal 연산이 호출되면 대기 큐에서 하나의 프로세스를 꺼내 wake-up시켜 실행하게 된다.
Semaphore vs. Test-and-Set: A Comparison
The most significant difference between the two approaches lies in how they handle waiting.
The Test-and-Set approach uses spin-waiting, repeatedly looping through a while statement. It continuously occupies the CPU until the lock is released, making it inefficient. The semaphore, on the other hand, transitions a process to a blocked state when the resource is unavailable, placing it in a waiting queue without consuming the CPU.
Additionally, Test-and-Set operates based on hardware instructions, while semaphores are a synchronization technique managed by the operating system. As a result, semaphores are generally the more efficient choice in typical operating system environments.
세마포어 vs Test-and-Set 비교
두 방식의 가장 큰 차이는 대기 방식이다.
Test-and-Set 방식은 while문을 반복하며 기다리는 스핀(spin) 방식의 대기를 사용한다. lock이 풀릴 때까지 CPU를 계속 사용한다는 점에서 비효율적이다. 반면 세마포어는 자원을 사용할 수 없으면 해당 프로세스를 block 상태로 전환하여 CPU를 사용하지 않고 대기 큐에서 기다리게 한다.
또한 Test-and-Set은 하드웨어 명령어 기반으로 동작하는 반면, 세마포어는 운영체제가 관리하는 동기화 기법이다. 따라서 일반적인 운영체제 환경에서는 세마포어 방식이 더 효율적으로 사용된다.
Roles of a Semaphore
A semaphore goes beyond simple lock implementation — it is a synchronization technique that controls the execution of processes. Its specific roles are as follows.
The first is implementing mutual exclusion. It prevents multiple processes from entering the critical section simultaneously.
The second is process synchronization. It regulates the order of task execution, ensuring that a subsequent task only begins after a preceding one has completed.
The third is managing multiple resources. Semaphores can be used to manage not just a single resource, but multiple resources simultaneously.
In this way, semaphores can be understood as a general-purpose control mechanism for process synchronization that goes well beyond simple locking. A key characteristic is that they use block-based waiting rather than spin-based waiting.
세마포어의 역할
세마포어는 단순히 lock 구현을 넘어서 프로세스의 실행을 제어하는 동기화 기법이다. 세마포어가 구체적으로 수행하는 역할을 살펴보자.
첫 번째는 상호 배제 구현이다. 여러 프로세스가 동시에 임계 영역에 들어가지 못하도록 제어한다.
두 번째는 프로세스 동기화이다. 작업 실행 순서를 조절하여 특정 작업이 끝난 뒤에 다음 작업이 실행되도록 한다.
세 번째는 다중 자원 관리이다. 세마포어는 단일 자원뿐 아니라 여러 개의 자원을 관리하는 데도 사용할 수 있다.
이처럼 세마포어는 단순한 lock을 넘어 프로세스 동기화를 위한 일반적인 제어 기법이라고 볼 수 있다. 또한 spin 방식이 아닌 block 기반 대기를 사용한다는 점이 중요한 특징이다.
3️⃣ Practice on Implementing Critical Sections Using Mutual Exclusion
Practice ① No Mutual Exclusion Applied; Reproducing a Race Condition
We implement mutual exclusion techniques in actual code and compare the cases where it is applied versus where it is not. We begin with the case where mutual exclusion is not applied.
Suppose two threads simultaneously increment the shared variable count. Since there is no code protecting the critical section, both threads can access count at the same time, producing a race condition where the result varies depending on execution order.
Looking at the code, two threads execute the same work function simultaneously via pthread_create. The problem arises in the following loop:
for(int i = 0; i < N; i++) {
count++; // no protection
}
Although this section is a critical section, there is no protective code whatsoever. As discussed earlier, count++ is carried out in multiple stages: reading the value, incrementing it, and storing it back. Therefore, if one thread reads the value of count at the same moment another thread reads the same value, both threads may each perform an increment operation, yet the result reflects only a single increment. This causes the Expected value and the Actual value to diverge, and a race condition occurs where the result changes with every execution.
As seen in the output, the Expected value is 6,000,000, but the Actual value is 5,874,213 — a clear discrepancy.
실습 ① 상호 배제 미적용 — 경쟁 상태 재현
상호 배제 기법을 실제 코드로 구현하여 적용한 경우와 적용하지 않은 경우를 비교해본다. 먼저 상호 배제를 적용하지 않은 경우이다.
두 개의 스레드가 공유 변수 count를 동시에 증가시키는 상황을 가정한다. 임계 영역을 보호하는 코드가 없기 때문에 두 스레드가 동시에 count에 접근하게 되고, 실행 순서에 따라 결과값이 달라지는 경쟁 상태가 발생한다.
코드를 살펴보면 두 개의 스레드는 pthread_create에 의해 동일한 work 함수를 동시에 실행한다. 문제는 아래 반복문에서 발생한다.
for(int i = 0; i < N; i++) {
count++; // 보호 없음
}
이 부분이 임계 영역임에도 불구하고 보호하는 코드가 전혀 없다. 앞서 살펴보았듯 count++는 값을 읽고, 증가시키고, 다시 저장하는 여러 단계로 나누어 수행된다. 따라서 한 스레드가 count 값을 읽는 순간 다른 스레드도 같은 값을 읽게 되면, 두 스레드가 각각 증가 연산을 수행하더라도 결과는 한 번만 증가한 것처럼 반영될 수 있다. 이로 인해 Expected 값과 Actual 값이 일치하지 않게 되고, 실행할 때마다 결과가 달라지는 경쟁 상태가 발생한다. 실행 결과를 보면 Expected 값은 6,000,000이지만 Actual 값은 5,874,213으로 차이가 발생한 것을 확인할 수 있다.
No Mutual Exclusion; The Occurrence of a Race Condition
This code is structured so that two threads both increment the same shared variable count, but there is no code in place to protect access to it.
When this code is run on Ubuntu, the Actual value printed is smaller than the Expected value. This occurs because, as the two threads simultaneously perform the count++ operation, they end up reading and overwriting the same value.
Although count++ appears simple on the surface, it internally consists of three steps: reading the current value, adding 1, and storing the result. When two threads execute this process simultaneously, one thread's result can be overwritten by the other, causing some increment operations to be lost.
This example directly demonstrates that failing to protect access to a shared variable can lead to a race condition.
상호배제 미적용 코드; 경쟁 상태(Race Condition)의 발생
이 코드에서는 두 개의 스레드가 동일한 공유 변수인 count를 함께 증가시키도록 구성되어 있지만, 접근을 보호하는 코드는 존재하지 않는다.
이 코드를 우분투에서 실행하면 actual 값이 expected보다 작은 수가 출력되는 현상이 발생한다. 이는 두 스레드가 count++ 연산을 동시에 수행하는 과정에서 같은 값을 읽고 덮어쓰는 상황이 발생했기 때문이다.
count++은 겉으로는 단순해 보이지만 내부적으로는 세 단계로 이루어진다. 현재 값을 읽고, 1을 더하고, 결과를 저장하는 과정이다. 두 스레드가 이 과정을 동시에 진행하면 한 스레드의 연산 결과가 다른 스레드에 의해 덮어씌워질 수 있고, 그 결과 증가 연산 일부가 사라지게 된다.
이 예제를 통해 공유 변수에 대한 접근을 보호하지 않으면 경쟁 상태(Race Condition)가 발생할 수 있다는 점을 직접 확인할 수 있다.
Practice ② Mutual Exclusion Applied — Spin Method
Next, we examine the spin method with mutual exclusion applied. This approach uses a Test-and-Set-based lock variable to protect the critical section. Since each thread must acquire the lock before entering the critical section, only one thread at a time can access the count variable.
However, a thread that fails to acquire the lock continuously checks the lock's state through a while loop. During this waiting period, the thread keeps consuming the CPU; this is known as busy waiting.
실습 ② 상호 배제 적용 — Spin 방식
상호 배제를 적용한 spin 방식을 살펴본다. 이 방식에서는 Test-and-Set 기반의 lock 변수를 사용하여 임계 영역을 보호한다. 각 스레드는 먼저 lock을 획득해야만 임계 영역에 들어갈 수 있으므로, 한 번에 하나의 스레드만 count 변수에 접근할 수 있다.
그러나 lock을 획득하지 못한 스레드는 while 반복문을 통해 계속 lock 상태를 확인하게 된다. 이 과정에서 대기하는 동안에도 CPU를 계속 사용하게 되는데, 이를 busy waiting이라고 한다.
Practice ② Mutual Exclusion Applied; Spin Method Code Analysis
Looking at the code, the critical section is protected using a lock variable initialized to 0.
In the acquire function, Test-and-Set is used to attempt to acquire the lock. If lock is already 1, the while loop continues spinning until the lock is released — meaning the thread keeps waiting while another thread is using the critical section. Once the lock is acquired, the critical section operation count++ is performed. Since this section is protected by the lock, two threads cannot execute it simultaneously. Afterward, release() resets the lock to 0, releasing it.
As a result, the Expected and Actual values always match in the output. However, since the while loop continues running while waiting for the lock, the CPU is constantly consumed — this is the busy waiting characteristic of this approach.
실습 ② 상호 배제 적용 — Spin 방식 코드 분석
코드를 살펴보면 초기값이 0으로 설정된 lock 변수를 이용하여 임계 영역을 보호하고 있다.
acquire 함수에서는 Test-and-Set을 이용하여 lock 획득을 시도한다. lock이 이미 1이라면 while 반복문을 계속 돌면서 lock이 해제되기를 기다린다. 즉 다른 스레드가 임계 영역을 사용 중이면 계속 대기하게 된다. lock을 획득하게 되면 임계 영역인 count++ 연산을 수행한다. 이 구간은 lock으로 보호되기 때문에 두 스레드가 동시에 실행될 수 없다. 이후 release()를 통해 lock을 다시 0으로 변경하여 해제한다.
따라서 실행 결과를 보면 Expected와 Actual 값이 항상 일치하게 된다. 그러나 lock을 기다리는 동안 while문이 계속 실행되기 때문에 CPU를 계속 사용하게 되는 busy waiting이 발생하는 구조이다.
Test-and-Set-Based Spin Lock — Mutual Exclusion Guaranteed, but Busy Waiting Occurs
The second example demonstrates a spin-based approach using a Test-and-Set lock. The difference from the previous example is that rather than protecting the shared variable count directly, this code requires a lock to be acquired before entering the critical section where count++ resides. The acquire() function serves exactly that purpose.
Running this code shows that the Expected and Actual values always match. Since only one thread can enter the critical section at a time, the race condition seen in the earlier example no longer occurs.
However, there is a drawback. A thread that cannot acquire the lock keeps looping inside the while statement. During this time, it continuously occupies the CPU without performing any useful work — this is busy waiting.
In summary, the spin method guarantees mutual exclusion but introduces busy waiting as its core limitation. This example directly illustrates that trade-off.
Test-and-Set 기반 Spin Lock — 상호배제는 보장하지만 Busy Waiting 발생
두 번째 예제는 Test-and-Set을 기반으로 Lock을 사용하는 Spin 방식의 코드다. 앞선 예제와의 차이는 공유 변수 count 자체를 보호하는 것이 아니라, count++이 있는 임계 영역(Critical Section)에 진입하기 전에 Lock을 먼저 획득하도록 구성되어 있다는 점이다. acquire() 함수가 바로 그 역할을 담당한다.
이 코드를 실행하면 expected 값과 actual 값이 항상 일치하는 것을 확인할 수 있다. 한 번에 하나의 스레드만 임계 영역에 진입할 수 있기 때문에, 앞서 발생했던 경쟁 상태가 나타나지 않는 것이다.
그러나 단점도 존재한다. Lock을 획득하지 못한 스레드는 while문 안에서 계속 반복하며 대기하게 된다. 이 과정에서 아무런 유용한 작업도 하지 않으면서 CPU를 계속 점유하게 되는데, 이를 Busy Waiting이라고 한다.
정리하면, Spin 방식은 상호배제는 보장하지만 Busy Waiting이 발생한다는 점이 핵심 한계다. 이 예제는 바로 그 트레이드오프를 직접 확인할 수 있는 코드다.
Practice ③ Mutual Exclusion Applied — Semaphore Method
This time, we examine the semaphore method with mutual exclusion applied. This approach uses sem_wait and sem_post to control access to the critical section. The shared variable is count, and the count++ operation is the critical section. Before entering the critical section, each thread calls sem_wait. If the resource is available, the thread immediately enters; if another thread is already using it, the thread is transitioned to a blocked state. Inside the critical section, the count++ operation is performed, and only one thread can access it at a time. Once the work is done, sem_post() releases the resource and wakes up any waiting thread to resume execution. Unlike the spin method, which continuously checks a while loop, this approach transitions threads to a blocked state, allowing the CPU to be used efficiently without waste.
실습 ③ 상호 배제 적용 - 세마포어 방식
이번에는 상호 배제를 적용한 세마포어 방식을 살펴본다. 이 방식에서는 sem_wait와 sem_post를 이용하여 임계 영역을 제어한다. 공유 변수는 count이며, count++ 연산이 임계 영역이 된다. 스레드는 임계 영역에 들어가기 전에 sem_wait를 호출한다. 이때 자원이 사용 가능하면 즉시 임계 영역에 진입하고, 이미 다른 스레드가 사용 중이면 해당 스레드는 block 상태로 전환된다. 임계 영역에서는 count++ 연산이 수행되며 한 번에 하나의 스레드만 접근할 수 있다. 작업이 끝나면 sem_post()로 자원을 반환하고 대기 중인 스레드를 깨워서 실행하게 된다. 이 방식은 while문을 계속 확인하는 것이 아니라 스레드를 block 상태로 전환하기 때문에 CPU를 낭비하지 않고 효율적으로 동작한다.
Practice ③ Mutual Exclusion Applied ; Semaphore Method Code Analysis
Looking at the code, access to the critical section is controlled using the semaphore variable mutex.
long long count = 0;
sem_t mutex;
The shared variable is count, and the count++ operation constitutes the critical section. Within the loop, each thread calls sem_wait(&mutex) before entering the critical section. If the semaphore value is 1, the thread enters immediately; if another thread is already using it, the thread is transitioned to a blocked state. Inside the critical section, count++ is performed, and because this region is controlled by the semaphore, only one thread can access it at a time. Once the work is complete, sem_post(&mutex) is called to release the resource and wake up any waiting thread.
As a result, the Expected and Actual values always match in the output. Since threads are transitioned to a blocked state rather than repeatedly looping through a while statement, busy waiting does not occur and the CPU is used efficiently.
실습 ③ 상호 배제 적용 — 세마포어 방식
코드 분석 코드를 살펴보면 세마포어 변수 mutex를 이용하여 임계 영역에 대한 접근을 제어한다. clong long count = 0; sem_t mutex;
공유 변수는 count이며 count++ 연산이 임계 영역이 된다. 각 스레드는 반복문 안에서 임계 영역에 들어가기 전에 sem_wait(&mutex)를 호출한다. 이때 세마포어 값이 1이면 즉시 임계 영역에 진입하고, 이미 다른 스레드가 사용 중이면 해당 스레드는 block 상태로 전환된다. 임계 영역에서 count++ 연산을 수행하며, 이 구간은 세마포어에 의해 제어되기 때문에 한 번에 하나의 스레드만 접근할 수 있다. 작업이 끝나면 sem_post(&mutex)를 호출하여 자원을 반환하고 대기 중인 스레드를 깨워서 실행하게 된다.
따라서 실행 결과를 보면 Expected와 Actual 값이 항상 일치하게 된다. 이 방식은 while문으로 반복 대기하는 것이 아니라 스레드를 block 상태로 전환하기 때문에 busy waiting이 발생하지 않고 CPU를 효율적으로 사용할 수 있다.
Semaphore — Mutual Exclusion with No Busy Waiting
The third example uses a semaphore. In this code, sem_wait() controls entry into the critical section and sem_post() releases the resource.
Running this code shows that the Expected and Actual values always match; confirming that semaphores can fully protect the critical section without any race condition.
The critical difference from the spin method lies in how waiting is handled. In the spin method, a thread that cannot enter the critical section repeatedly loops through a while statement, continuously occupying the CPU. In the semaphore method, a thread that cannot enter is instead transitioned to a waiting state, avoiding unnecessary CPU consumption.
In summary, the semaphore method's key advantage is that it guarantees mutual exclusion while enabling efficient waiting without busy waiting. Comparing the three examples examined above, one can clearly see the progression of approaches to protecting shared resources.
세마포어(Semaphore); 상호배제와 Busy Waiting 없는 대기
세 번째 예제는 세마포어(Semaphore) 를 사용하는 방식이다. 이 코드에서는 sem_wait()으로 임계 영역 진입을 제어하고, sem_post()로 자원을 반환하도록 구성되어 있다.
이 코드를 실행해보면 expected 값과 actual 값이 항상 일치하는 것을 확인할 수 있다. 즉 세마포어를 사용해도 경쟁 상태 없이 임계 영역을 완전하게 보호할 수 있다는 것이다.
Spin 방식과의 결정적인 차이는 대기 방식에 있다. Spin 방식에서는 임계 영역에 진입하지 못한 스레드가 while문을 반복하며 CPU를 계속 점유했다. 반면 세마포어 방식에서는 진입하지 못한 스레드가 대기 상태로 전환되어 CPU를 불필요하게 사용하지 않는다.
정리하면, 세마포어 방식은 상호배제를 보장하면서도 Busy Waiting 없이 효율적으로 대기할 수 있다는 점이 핵심 장점이다. 앞서 살펴본 세 가지 예제를 비교하면 공유 자원 보호 방식의 발전 과정을 한눈에 확인할 수 있다.
