Concurrency, Locks

December 5, 2025 7 분 소요

이번 포스트는 OS의 Concurrency와 Locks에 대해 다룬다.

Concurrency

Thread

정의 : 싱글 프로세스 안에서 실행되는 독립적인 실행 흐름

프로세스 하나를 여러 개의 실행 단위로 쪼갠 것이 Thread

Multi-threaded Program의 특징

여러 실행 지점 (Multiple PCs)이 존재한다.
- 프로세스 전체의 PC가 아니라, 각 스레드마다 자기만의 Program Counter가 존재함.
스레드마다 Register set도 각각 존재한다.
- 실행 흐름을 유지하기 위해 필수적이다.
모든 스레드가 같은 Address Space를 공유한다.
- Code
- Heap
- Global Variables
이 메모리 공간들은 스레드끼리 공유되기 때문에, 스레드가 협력하는 구조가 가능해진다.

Stack of the relevant Thread

스레드가 여러 개라면 Stack도 여러 개
OS는 스레드별로 독립된 스택을 하나씩 부여한다.
- 여기서의 스택은 로컬 변수, 함수 호출 정보, return address 등을 저장하는 공간

왜 스택만 따로 존재할까?

함수 호출, 지역 변수, 리턴 주소 등이 스레드별로 독립적이어야 실행 흐름이 충돌되지 않음.

스레드는 반드시 자기만의 Stack이 필요하다.

스레드 간 Context Switch

Thread 간 Context Switch가 할 때 OS는 다음을 수행한다:

1. T1 의 Register Set을 저장

PC, SP (Stack Pointer), 레지스터 값들 저장
Thread Control Back (TCB)에 기록

2. T2의 Register Set 복원

T2 의 PC와 레지스터를 복구
그 지점부터 실행을 재개한다.

3. Address Space는 그대로 유지

스레드끼리는 같은 주소 공간을 공유하므로
프로세스 간 Context Switch 처럼 Page Table 교체는 필요가 없다.

차이점 (Context Switch) : Process VS Thread

항목	Process	Thread
Address space	변경됨	변경 없음
비용	비쌈	가벼움 (빠름)
필요한 자료구조	PCB	TCB

Thread 전환이 빠른 이유 : 주소 공간이 동일하기 때문

왜 Thread를 사용할까?

1. Parallelism (병렬성)

가장 주요한 이유 : 프로그램을 더 빠르게 만들기 위해서다.
Single-threaded program
- 실행 경로가 하나뿐 -> CPU가 아무리 많아도 하나만 사용
- 순차적 실행이라 직관적이지만 느리다.
Multi-threaded program
- 실행 지점이 여러 개 -> 여러 CPU 코어를 동시에 사용할 수 있음
- 현대 하드웨어에서 성능을 높이는 가장 보편적 기술
Parallelization
- 원래 단일 스레드로 작성된 프로그램을 여러 CPU에서 병렬 실행하도록 바꾸는 과정
- 병렬화는 매우 어려운 문제 (동기화, shared data 등을 고려해야 한다.)

2. Avoid Blocking due to slow I/O

I/O 때문에 프로그램이 멈추지 않게 하기
Single-threaded Program : 디스크 읽기, 네트워크 요청 같은 느린 I/O 작업이 끝날 때까지 전체 프로그램이 멈춤
Multi-threaded Program : 하나의 스레드가 I/O 기다리는 동안 다른 스레드가 계속 작업함.

Race Condition & Critical Section

Race Condition : 경쟁상태

프로그램의 결과가 코드 실행 타이밍에 따라 달라지는 상태
실행할 때마다 결과가 예측 불가능 (indetermine)
발생 이유
- 여러 thread가 shared variable (공유 변수)을 동시에 접근하고 수정하기 때문
예시

Two threads 가 다음 연산 수행:

counter = counter + 1

이 연산은 사실 3 단계로 분리됨

메모리에서 counter를 로드 -> register(eax)에 저장
register 값에 1 증가
결과를 다시 메모리에 저장

-> 문제점:

중간에 OS 스케줄러가 인터럽트를 걸어 Thread1을 멈추고 Thread2를 실행시키면..
두 개의 스레드가 같은 초기 값을 읽어서 각각 +1을 한다.
결과는 52가 기대되지만, 51이 됨

Race Condition이 만들어내는 오류

Critical Section : 임계 구역

동시에 실행되면 안되는 코드 영역
조건
- 공유 변수 (Shared Variable) 를 읽거나 쓰는 코드
- 두 개 이상의 스레드가 동시에 실행되면 Race Condition이 발생
해결 방법
- Cirtical Section은 원자성 (Atomicity)가 보장되야 함.
- 한 스레드가 Critical Section을 실행 중이면 다른 스레드는 절대 들어오면 안 됨.
- 지원하는 기법 : Mutual Exclusion
  - 예 : Mutex, lock, semaphore

Atomicity

Race Condition의 문제를 해결하기 위해 원자성 (Atomicity)는 필요하다.

이상적인 방법 : 하드웨어가 아래 같은 단일 명령을 제공하면 좋다.

memory-add 0x8049a1c, $0x1

CPU가 이런 단일 명령을 제공하지 않는다.

실제 해결 : Lock 사용
- Critical Section을 보호하기 위해 락(Lock)을 사용한다.
```
lock(&mutex);
balance = balance + 1;   // Critical section
unlock(&mutex);
```
Lock을 통해 이 명령어들이 반드시 전체적으로 원자적으로 실행되는 것처럼 보이게 만들어 Race Condition을 예방한다.

Building a Lock

소프트웨어만으로 Lock을 구현하면 생기는 문제

flag = 0 (Lock available)
flag = 1 (Lock held)

typedef struct __lock_t {
    int flag;
} lock_t;

void lock(lock_t *mutex) {
    while (mutex->flag == 1) ;   // Spin-wait
    mutex->flag = 1;             // Acquire (supposedly)
}

문제점 1 : 상호 배제(Mutual Exclusion)가 보장되지 않는다.

두 스레드가 동시에 while (flag == 1) 검사를 통과하면 두 스레드 모두 flag = 1을 실행할 수 있어 락이 무효화된다.

while (flag == 1);
flag = 1;

Thread 1, 2가 동시에 flag = 1 설정
- 둘 다 Lock을 얻었다고 착각함. (Mutual Exclusion) 실패

문제점 2 : Spin-wait 낭비

flag가 해제될 때까지 CPU가 무한 반복으로 기다리는 구조는 CPU 낭비가 심하다.
따라서 순수 소프트웨어만으로 구현하면 안전하지 않고, 비효율적이다.
- 결국 하드웨어 지원이 필요하다.
대표적인 하드웨어 명령어들
- Test-and-set (TAS) , Compare-and-swap (CAS) , Fetch-and-add
- 읽기+쓰기 연산을 하나의 Atomic 명령으로 수행할 수 있게 해준다.

Lock

Lock의 목적 : 어떤 Critical Section을 마치 1개의 Atomic 명령처럼 실행되게 보장하는 것

위의 예시 balance = balance + 1 과같은 실제 3개의 instuction은 Race Condition을 유발한다.
해결 방법 : critical section 앞뒤에 lock () / unlock()을 추가하여 하나의 thread만 그 구역을 실행하게 만든다.
Lock은 Mutual Exclusion을 달성하는 도구

Buliding a Lock

좋은 Lock : Low Cost + mutual Exclusion 제공
Lock을 구현하기 위해 Hardware + OS 자원이 필수적
하드웨어가 제공하는 atomic instruction
- Test-and-Set / Compare-and-Swap/ Fetch-and-Add
OS 는 thread blocking/wakeup을 위한 기능 제공
- park() , unpark()

Lock - Basic criteria

Mutual Exclusion (상호 배제)

여러 Thread가 동시에 critical section에 진입하지 못하게 하는 기능이 제대로 동작하는가?

Fairness (공정성)

Lock을 기다리는 thread들이 Starvation 없이 공평하게 Lock을 획득할 수 있는가?

Performance (성능)

Lock 사용으로 인한 overhead (context switching, spin-waiting, 메모리 contention)은 어느정도인가?

Controlling Interrupt

Disable Interrupt 방식 : 초기(single-processor) 시스템에서 사용되던 가장 단순한 방식

현재 CPU가 Interrupt에 의해 중단되지 않게 만들어, Critical Section을 원작적으로 보장하는 방식
single-processor 환경에서만 가능
- Interrupt Disable 시 CPU는 다른 일 처리 X -> 하나의 CPU에서는 mutual Exclusion 을 보장함
Unlock시 EnableInterrupts() 호출

Disable Interrupt 문제점

신뢰 문제 : 사용자 프로그램이 남용하면 CPU 독점이 가능
멀티 프로세서에서는 절대 불가능 : mutual exclusion이 깨짐
심각한 시스템 불안정성 : Interrupt를 꺼놓으면 I/O, timer interrupt 가 지연

Spin Lock

개념 : Flag 변수를 이용해 Lock을 구현하려는 naive한 방식

while (mutex->flag == 1) ;   // spin-wait
mutex->flag = 1;            // lock 획득

문제점

1. Mutual Exclusion 실패

두 스레드가 동시에 flag를 확인하려는 경우 race condition 발생

2. Spin-waiting

while문으로 CPU를 낭비함.

해결책 : Hardware atomic instruction

Spin Lock의 Evaluation

Correctness : Yes
- 스핀락은 한 번에 하나의 쓰레드만 Critical Section에 들어가기 가능
Fairness : No
- 공정성 보장은 없다.
- 어떤 스레드는 lock을 계속 못 얻고 영원히 Spin할 수도 있다. (Starvation)
Performance
- Single CPU에서는 성능이 매우 나쁠 수 있다.
- 멀티코어에서도 CPU 수 = 스레드 수 일때는 괜찮게 동작함.

Test-and-Set

하드웨어가 제공하는 Atomic 명령어
메모리의 값을 읽고 (Test), 새로운 값으로 바꾸면서 (Set), 원래 값을 리턴함.
- 이 전체가 Atomic 이기에 끼어들기 없이 한 번에 수행됨.

int TestAndSet(int *ptr, int new) {
    int old = *ptr;    // 현재 값 읽기
    *ptr = new;        // 새로운 값 저장
    return old;        // 원래 값 반환
}

*ptr에 저장된 기존 값을 return 함 (Test)
그 위치에 new 값을 저장함 (Set)
두 동작이 분리되지 않고 동시에 이루어짐으로써 Race Condition 발생 X

SpinLock에서 Test-and-Set 구현

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ;  // spin-wait
}

동작 원리

lock->flag가 0이면 (lock free)
- TestAndSet(flag,1) 은 old = 0을 리턴하고, flag = 1로 바꿈
- Lock 획득 성공
lock->flag가 1이면 (lock held)
- TestAndSet(flag, 1)은 old = 1을 리턴, while에서 계속 스핀
- Lock이 풀릴 때까지 busy-wait

단점

CPU 자원을 계속 소모하는 busy-wait
Single CPU 환경에서는 preemptive scheduler 필수
- 스레드가 lock 획득한 채로 무기한 실행되면 교착됨.

Compare-And-Swap

CAS는 다음 3단계를 Atomic으로 수행한다:

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;         // 현재 값 읽기
    if (actual == expected)    // 우리가 예상한 값과 동일하면
        *ptr = new;            // new로 업데이트
    return actual;             // 실제 메모리에 있던 값을 리턴
}

CAS는 “비교 후 교체”라는 점에서 Test-and-Set보다 유연함

CAS 기반 Spin Lock

void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ;   // spin
}

동작 방식

flag가 0, CAS(&flag, 0, 1) 성공 : Lock 획득
flag가 1, CAS는 1을 리턴 : spin 반복

장점 : 원자성 보장, Test / Set을 조건부로 수행 가능해서 유연하다.

단점 : busy-wait은 여전히 존재하고, 많은 스레드가 경쟁하면 CAS 실패가 반복, 스레드들 간 성능 저하

Fetch-And-Add

원자적으로 값을 증가시키고, 동시에 증가 이전의 값을 반환하는 Atomic instruction

int old = *ptr;
*ptr = old + 1;
return old;

Ticket Lock

Fetch-And-Add 기반
Ticket : 새로 Lock을 요청한 스레드가 뽑는 번호
turn : 현재 lock을 사용할 차례 번호

공정성 보장 : FIFO 방식

Lock()을 호출할 때, fetch-and-add로 나만의 ticket을 받는다.

turn 값과 내 번호가 같을때까지 spin을 하고, unlock 시 turn을 1 증가시킨다.

Spinning

하드웨어 기반 스핀락은 구조가 단순하고 잘 동작한다.
단점도 확실하다:
- thread가 lock을 얻기 위해 계속 반복 (spin) : CPU 시간 낭비
- 스핀 상태에 빠지면 전체 time slice를 의미 없이 소비한다.
busy waiting은 CPU를 효율적으로 쓰지 못한다.

Lock 경쟁이 심할수록 OS 도움이 필요하다.

Just Yield

Simple Approach

spin을 계속 돌지 말고, yield()를 통해 CPU를 양보하는 방식
OS system call : thread를 ready 상태로 보내고, 다른 스레드가 실행되도록 변경
단점
- context switching 비용이 증가
- starvation 문제 해결 X

Using Queues

thread가 계속 기다리지 않도록 thread를 sleep 시키는 방식으로 전환
OS 지원 함수 : park() / unpark()
- 대기 중인 threads 을 저장하기 위해 큐 사용

1. park()의 동작과정

guard를 Test-and-Set으로 획득 (큐 접근 보호용)
flag == 0 (락이 비어있음) 이면 락 획득 후 종료
flag == 1 (누가 쓰는 중)이면
- 현재 스레드를 큐에 push
- guard 해제
- park()로 sleep

2. Unpark()의 동작과정

guard 획득 (큐 접근 보호)
큐가 비었으면 :
- flag = 0 (아무도 기다리지 않으므로 lock 완전 해제)
큐가 비어있지 않으면:
- 큐에서 하나 pop
- unpark(next_thread)로 다음 스레드를 깨움

Twitter Facebook LinkedIn