11. concurrency

Concurrency & Threads

Reading

• 이 단원은 운영체제의 큰 주제 중 하나인 concurrency, 즉 동시성을 다룬다.

• 앞 단원들에서는 주로 다음 내용을 봤다.

  • CPU virtualization

    • 하나의 CPU를 여러 process가 나누어 쓰는 것처럼 보이게 함.

  • Memory virtualization

    • 각 process가 자기만의 address space를 가진 것처럼 보이게 함.

  • Swapping / page replacement

    • physical memory가 부족할 때 page를 disk와 memory 사이에서 관리함.

• 이제부터는 하나의 process 안에서도 여러 실행 흐름이 동시에 존재할 수 있다는 점을 다룬다.

• 핵심 질문은 다음과 같다.

  • 여러 thread가 동시에 실행되면 어떤 문제가 생기는가?
  • shared data를 여러 thread가 동시에 접근하면 왜 결과가 이상해질 수 있는가?
  • race condition을 어떻게 막을 수 있는가?
  • lock, condition variable, semaphore는 각각 언제 쓰는가?
  • concurrency bug, 특히 deadlock은 왜 생기는가?

Big Picture

• concurrency의 핵심

  • 여러 작업이 동시에 실행되는 것처럼 보이거나 실제로 동시에 실행되는 상황.
  • single CPU에서는 scheduler가 thread를 빠르게 바꿔 실행해서 동시에 실행되는 것처럼 보이게 한다.
  • multicore CPU에서는 여러 thread가 실제로 동시에 실행될 수 있다.

• concurrency가 어려운 이유

  • 실행 순서가 항상 같지 않다.
  • 어떤 thread가 먼저 실행될지 알 수 없다.
  • context switch가 언제 일어날지 알 수 없다.
  • shared data를 누가 먼저 읽고 쓸지 알 수 없다.

• 이 단원의 핵심 문장

  • 실행 순서가 바뀌어도 프로그램 결과가 항상 올바르게 나오도록 만들어야 한다.

Thread

• thread는 하나의 process 안에서 실행되는 흐름이다.

• 기존 process 모델

  • 하나의 process 안에 하나의 program counter가 있음.
  • 하나의 실행 흐름만 존재한다고 생각함.

• multi-threaded process

  • 하나의 process 안에 여러 개의 execution point가 존재함.
  • 각각의 thread는 자기만의 PC를 가진다.
  • 각각의 thread는 자기만의 register state를 가진다.
  • thread context switch가 일어나면 한 thread의 register 상태를 저장하고 다른 thread의 register 상태를 복원한다.
  • process context switch와 다르게 address space는 그대로 유지된다.

• thread와 process의 차이

  • process끼리는 보통 서로 다른 address space를 가진다.
  • 같은 process 안의 thread들은 같은 address space를 공유한다.
  • 그래서 code, heap, global data를 함께 볼 수 있다.
  • 대신 각 thread는 독립적으로 실행되어야 하므로 자기 stack을 가진다.

• multi-threaded address space

  • single-threaded process에는 보통 stack이 하나 있다.
  • multi-threaded process에는 thread마다 stack이 생긴다.
  • stack에 저장되는 local variable, parameter, return value 등은 각 thread의 thread-local storage처럼 동작한다.

Why Use Threads?

• thread를 쓰는 이유는 크게 두 가지다.

• 첫 번째 이유: parallelism

  • 큰 작업을 여러 CPU core에 나눠서 처리할 수 있다.
  • 예를 들어 큰 배열을 여러 조각으로 나누고 각 thread가 한 조각씩 처리할 수 있다.
  • single-threaded program을 여러 CPU에서 동시에 일하게 바꾸는 것을 parallelization이라고 볼 수 있다.
  • modern hardware에서는 CPU core가 여러 개이므로 thread를 쓰면 성능 향상을 기대할 수 있다.

• 두 번째 이유: blocking 회피

  • 한 thread가 disk I/O, network I/O, page fault 등을 기다리는 동안 다른 thread가 계속 실행될 수 있다.
  • 하나의 thread가 blocked 상태여도, scheduler는 같은 process 안의 다른 runnable thread를 실행할 수 있다.
  • web server, database system 같은 server-based application에서 thread를 많이 쓰는 이유도 이 때문이다.

• thread를 쓰면 좋은 점

  • 같은 address space를 공유하므로 data sharing이 쉽다.
  • process 여러 개를 쓰는 것보다 shared data를 다루기 편하다.

• thread를 쓰면 위험한 점

  • 같은 data를 공유하기 때문에 동시에 접근하면 문제가 생긴다.
  • shared data에 대한 read/write 순서가 꼬이면 결과가 달라질 수 있다.

Thread API

• thread를 쓰려면 thread를 만들고, 기다리고, 동기화하는 API가 필요하다.

• POSIX thread, 즉 pthread API가 대표적이다.

• pthread_create

  • 새 thread를 만든다.
  • thread가 실행할 function, 즉 start routine을 넘긴다.
  • argument는 보통 void * 형태로 넘긴다.
  • 그래서 구조체 포인터를 넘기면 여러 값을 한 번에 전달할 수 있다.
  • thread가 만들어지면 바로 실행될 수도 있고, ready 상태로 있다가 나중에 실행될 수도 있다.

• pthread_join

  • 특정 thread가 끝날 때까지 기다린다.
  • child thread가 return한 값을 parent thread가 받을 수도 있다.
  • fork/join 구조에서 “child가 끝난 뒤 parent가 이어서 실행"되게 만들 때 사용한다.

• mutex 관련 API

  • pthread_mutex_init
  • pthread_mutex_lock
  • pthread_mutex_unlock
  • critical section에 들어가기 전 lock을 잡고, 끝나면 unlock한다.

• condition variable 관련 API

  • pthread_cond_wait
  • pthread_cond_signal
  • pthread_cond_broadcast
  • 어떤 조건이 만족될 때까지 thread를 재우고, 조건이 만족되면 깨우는 데 사용한다.
  • pthread_cond_wait는 mutex와 함께 사용된다.

• API 사용 시 주의점

  • thread function에 넘기는 argument가 valid한 lifetime을 가져야 한다.
  • stack에 있는 local variable의 주소를 잘못 넘기거나 return하면 위험하다.
  • thread API 호출 결과를 확인하는 것이 좋다.
  • 간단한 프로그램에서는 wrapper를 만들어 실패 시 바로 종료하도록 할 수 있다.

Shared Data Problem

• concurrency에서 가장 먼저 문제가 되는 것은 shared data다.

• 예시

  • 두 thread가 하나의 global variable counter를 동시에 증가시킨다고 하자.
  • 코드로 보면 counter++는 단순해 보인다.
  • 하지만 실제로는 다음처럼 여러 단계로 나뉜다.

counter 값을 메모리에서 읽는다
1을 더한다
결과를 다시 메모리에 쓴다

• 문제가 생기는 경우

  • Thread 1이 counter 값을 읽는다.
  • Thread 2도 같은 counter 값을 읽는다.
  • 둘 다 1을 더한다.
  • 둘 다 같은 값을 다시 저장한다.
  • 결과적으로 counter가 2 증가해야 하는데 1만 증가할 수 있다.

• 이 문제는 thread가 서로 다른 순서로 실행될 수 있기 때문에 생긴다.

Key Terms

• Critical Section

  • shared resource에 접근하는 코드 영역.
  • shared variable, shared data structure, shared queue, shared list 등을 읽거나 수정하는 부분.
  • 여러 thread가 동시에 들어가면 안 되는 구간.

• Race Condition

  • 여러 thread가 critical section에 거의 동시에 들어가 shared data를 수정하면서 예상과 다른 결과가 나오는 상황.
  • 실행 순서에 따라 결과가 달라진다.

• Indeterminate Program

  • race condition이 있어서 실행할 때마다 결과가 달라질 수 있는 프로그램.
  • 같은 input이어도 scheduler timing에 따라 output이 달라질 수 있다.

• Mutual Exclusion

  • 한 번에 하나의 thread만 critical section에 들어가게 하는 성질.
  • race condition을 막기 위한 핵심 조건.

• Atomicity

  • 어떤 작업이 중간에 끊기지 않고 하나의 단위처럼 실행되는 성질.
  • counter++처럼 겉으로는 하나의 작업처럼 보이는 코드도 실제로는 여러 instruction으로 나뉠 수 있다.
  • 그래서 atomic하지 않으면 중간에 context switch가 끼어들 수 있다.

Locks

• lock은 mutual exclusion을 구현하는 가장 기본적인 도구다.

• lock의 기본 아이디어

  • critical section 앞에서 lock을 잡는다.
  • critical section을 실행한다.
  • 끝나면 unlock한다.

• 예시

lock(&mutex);
balance = balance + 1;
unlock(&mutex);

• lock의 의미

  • lock이 free 상태이면 thread가 lock을 acquire하고 critical section에 들어간다.
  • lock이 held 상태이면 다른 thread는 기다린다.
  • lock을 가진 thread가 unlock해야 다른 thread가 들어갈 수 있다.

Evaluating Locks

• 좋은 lock인지 평가하는 기준은 크게 세 가지다.

• Correctness

  • lock이 mutual exclusion을 제대로 제공하는가?
  • 여러 thread가 동시에 critical section에 들어가지 못하게 막는가?

• Fairness

  • 기다리는 thread가 언젠가는 lock을 얻을 수 있는가?
  • 특정 thread가 계속 밀려서 starvation에 빠지지 않는가?

• Performance

  • lock을 잡고 푸는 비용이 작은가?
  • lock contention이 없을 때 빠른가?
  • 여러 CPU에서 lock contention이 있을 때도 효율적인가?

Building Locks

• lock을 구현하는 방법은 여러 가지가 있다.

1. Disable Interrupts

• 가장 초기 방식 중 하나.

• critical section에 들어가기 전에 interrupt를 끈다.

• interrupt가 없으면 context switch가 일어나지 않으므로 critical section이 atomic하게 실행되는 것처럼 된다.

• 장점

  • 단순하다.

• 단점

  • single processor에서는 어느 정도 가능하지만 multiprocessor에서는 잘 맞지 않는다.
  • interrupt를 끄는 것은 privileged operation이라 user program에 맡기기 위험하다.
  • critical section이 길어지면 시스템 반응성이 나빠진다.

2. Just Loads / Stores

• 단순히 flag 변수 하나로 lock을 만들려는 방식.

• 예시

  • flag가 0이면 lock이 free.
  • flag가 1이면 lock이 held.

• 문제

  • flag를 읽고 쓰는 과정 자체가 atomic하지 않다.
  • 두 thread가 동시에 flag를 0으로 보고 둘 다 critical section에 들어갈 수 있다.

• 결론

  • 일반 load/store만으로는 올바른 lock을 만들기 어렵다.
  • CPU의 atomic instruction이 필요하다.

3. Test-and-Set

• test-and-set은 atomic exchange 계열의 hardware primitive다.

• 한 번에 다음 일을 한다.

  • 기존 값을 읽는다.
  • 새 값을 쓴다.
  • 기존 값을 반환한다.

• lock 구현 방식

  • lock flag가 0이면 test-and-set으로 1로 바꾸고 lock 획득.
  • 이미 1이면 계속 반복하면서 기다림.

• 이 방식으로 만든 lock은 보통 spin lock이다.

• spin lock

  • lock이 풀릴 때까지 CPU를 사용하면서 계속 확인한다.
  • 구현은 단순하다.
  • 하지만 lock을 가진 thread가 오래 실행되지 않으면 다른 thread들이 CPU를 낭비하며 빙빙 돈다.

4. Spin Lock

• spin lock은 lock이 풀릴 때까지 계속 반복해서 확인하는 lock이다.

• 장점

  • 구현이 매우 간단하다.
  • critical section이 아주 짧고 multicore에서 lock이 곧 풀릴 것 같으면 괜찮을 수 있다.

• 단점

  • CPU cycle을 낭비한다.
  • single CPU에서는 lock holder가 preempted되면 기다리는 thread가 쓸데없이 돈다.
  • fairness 보장이 약하다.
  • starvation이 생길 수 있다.

5. Compare-and-Swap

• compare-and-swap은 atomic instruction의 또 다른 형태다.

• 기본 아이디어

  • memory 값이 expected와 같으면 new 값으로 바꾼다.
  • 같지 않으면 아무것도 하지 않는다.
  • 원래 값을 반환한다.

• lock 구현

  • flag가 0이면 1로 바꾸고 lock 획득.
  • flag가 이미 1이면 계속 시도.

• test-and-set보다 더 일반적이고 강력한 primitive다.

• lock-free data structure 구현에도 자주 쓰인다.

6. Load-Linked / Store-Conditional

• MIPS 같은 architecture에서 제공하는 atomic instruction pair.

• load-linked

  • 특정 주소의 값을 읽는다.

• store-conditional

  • 그 주소가 load-linked 이후 다른 thread에 의해 바뀌지 않았을 때만 store에 성공한다.

• 성공하면

  • 값을 update하고 1을 반환한다.

• 실패하면

  • update하지 않고 0을 반환한다.

• lock 구현

  • lock flag를 load-linked로 읽는다.
  • free이면 store-conditional로 1을 쓰려고 한다.
  • 둘 중 한 thread만 성공하고 나머지는 실패 후 재시도한다.

7. Fetch-and-Add / Ticket Lock

• fetch-and-add

  • 값을 atomic하게 증가시키고, 증가 전 값을 반환한다.

• ticket lock

  • 기다리는 thread마다 ticket number를 받는다.
  • 현재 turn 값과 자기 ticket이 같아지면 critical section에 들어간다.

• 장점

  • 순서대로 lock을 얻을 수 있다.
  • fairness가 좋아진다.
  • starvation 가능성을 줄인다.

8. Yield

• spin만 계속 하는 대신, lock이 잡혀 있으면 CPU를 양보하는 방식.

• yield()

  • running 상태의 thread가 voluntarily CPU를 포기하고 ready 상태로 돌아간다.

• 장점

  • 계속 spin하는 것보다는 CPU 낭비가 줄 수 있다.

• 단점

  • thread가 많으면 context switch 비용이 커진다.
  • starvation 문제를 근본적으로 해결하지 못한다.

9. Sleeping Instead of Spinning

• spin이나 yield만으로는 낭비가 생긴다.

• 더 나은 방식

  • lock을 얻지 못하면 thread를 sleep 상태로 보낸다.
  • lock이 풀리면 기다리던 thread를 깨운다.

• 이를 위해 OS 지원이 필요하다.

  • park / unpark
  • futex 등

10. Futex

• Linux에서 사용하는 효율적인 lock 지원 방식.
• futex는 user-level fast path와 kernel-level sleep/wake를 결합한다.
• contention이 없으면 user space에서 빠르게 lock/unlock한다.
• contention이 있으면 kernel queue를 이용해 sleep/wake한다.

11. Two-Phase Lock

• spin과 sleep을 섞은 hybrid 방식.

• 1단계

  • lock이 곧 풀릴 수 있으니 잠깐 spin한다.

• 2단계

  • 그래도 lock을 못 얻으면 sleep한다.

• 장점

  • lock이 빨리 풀리는 경우에는 context switch를 피할 수 있다.
  • 오래 기다려야 하는 경우에는 CPU 낭비를 줄일 수 있다.

Lock-Based Concurrent Data Structures

• shared data structure를 thread-safe하게 만들려면 lock을 붙여야 한다.

• 가장 단순한 방법

  • data structure 전체에 하나의 big lock을 둔다.
  • 모든 operation이 lock을 잡고 실행된다.

• 장점

  • 구현이 쉽다.
  • correctness 확보가 쉽다.

• 단점

  • scalability가 떨어질 수 있다.
  • thread가 많아질수록 lock contention이 커진다.

Concurrent Counter

• 가장 단순한 shared data structure 예시.

• counter에 하나의 lock을 붙이면 correctness는 확보된다.

• 문제

  • 모든 increment/decrement가 하나의 lock을 공유하면 성능이 나빠진다.

• approximate counter

  • CPU/core별 local counter를 둔다.
  • local counter가 일정 threshold를 넘으면 global counter에 반영한다.
  • 정확도와 성능 사이의 trade-off가 생긴다.

• threshold가 작으면

  • 정확도는 높지만 성능은 낮다.

• threshold가 크면

  • 성능은 좋지만 global count가 실제 값보다 늦게 반영될 수 있다.

Concurrent Linked List

• linked list에 lock을 붙이는 방법

  • 전체 list에 하나의 lock을 둔다.
  • insert, lookup 같은 operation마다 lock을 잡는다.

• 단점

  • list traversal이 길면 lock holding time이 길어진다.
  • scalability가 나빠진다.

• hand-over-hand locking

  • node마다 lock을 둔다.
  • 현재 node lock을 잡고 다음 node lock을 잡은 뒤 현재 node lock을 푼다.
  • lock coupling이라고도 한다.

• 주의점

  • lock을 많이 쓰면 concurrency가 늘어날 것 같지만 항상 성능이 좋아지는 것은 아니다.
  • lock acquire/release 비용이 커질 수 있다.
  • control flow 중간에 return할 때 unlock을 빼먹지 않도록 조심해야 한다.

Concurrent Queue

• queue는 multi-threaded program에서 자주 쓰인다.

• 단순한 방식

  • queue 전체에 하나의 lock.

• 더 나은 방식

  • head lock과 tail lock을 분리한다.
  • enqueue와 dequeue가 서로 다른 부분을 만질 때 더 많은 concurrency를 허용한다.

• bounded queue

  • queue가 비어 있으면 consumer가 기다려야 한다.
  • queue가 가득 차면 producer가 기다려야 한다.
  • 이 문제는 condition variable과 연결된다.

Concurrent Hash Table

• hash table은 bucket별로 list를 둔다.

• 각 bucket마다 lock을 두면 더 많은 operation이 동시에 진행될 수 있다.

• 장점

  • 하나의 big lock보다 scalability가 좋다.
  • 서로 다른 bucket에 접근하는 thread들은 동시에 진행 가능하다.

Lock-Based Data Structure의 교훈

• 처음에는 단순한 big lock으로 시작하는 것이 좋다.
• 성능 문제가 실제로 생기면 lock granularity를 줄이거나 구조를 바꾼다.
• 너무 일찍 복잡한 최적화를 하면 bug 가능성이 커진다.
• correctness가 먼저이고, performance는 그다음이다.

Condition Variables

• lock은 mutual exclusion을 해결한다.
• 하지만 lock만으로는 “조건이 만족될 때까지 기다리는 문제"를 잘 해결하기 어렵다.
• condition variable은 thread가 어떤 조건을 기다리도록 만드는 synchronization primitive다.

왜 필요한가?

• 예시

  • parent thread가 child thread가 끝날 때까지 기다리고 싶다.
  • consumer가 buffer에 item이 생길 때까지 기다리고 싶다.
  • producer가 buffer에 빈 공간이 생길 때까지 기다리고 싶다.

• 단순히 while loop로 계속 확인하면 busy waiting이 된다.

• condition variable은 기다리는 thread를 sleep 상태로 보낸다.

• 다른 thread가 조건을 만족시키면 signal로 깨운다.

기본 연산

• wait

  • 조건이 만족되지 않았으므로 thread를 sleep시킨다.

• signal

  • 기다리는 thread 하나를 깨운다.

• broadcast

  • 기다리는 thread 여러 개를 깨운다.

wait의 중요한 특징

• wait는 mutex와 함께 사용된다.

• wait가 하는 일

  • lock이 잡혀 있다고 가정한다.
  • lock을 release한다.
  • thread를 sleep 상태로 보낸다.
  • signal을 받아 깨어나면 lock을 다시 acquire한 뒤 return한다.

• 이 과정은 race condition을 막기 위해 atomic하게 처리되어야 한다.

State Variable

• condition variable을 쓸 때는 보통 state variable이 필요하다.

• 예시

  • done
  • count
  • ready

• signal 자체는 상태를 저장하지 않는다.

• 따라서 “조건이 만족되었는지"를 나타내는 변수를 따로 관리해야 한다.

• state variable이 없으면 signal이 먼저 발생하고 wait가 나중에 발생하는 경우 문제가 생길 수 있다.

Always Hold the Lock

• condition variable을 사용할 때는 lock을 잡고 wait/signal하는 것이 안전하다.
• 특히 wait는 lock을 잡은 상태에서 호출해야 한다.
• signal도 lock을 잡고 호출하는 것이 일반적으로 안전하다.

Mesa Semantics

• 대부분의 실제 system은 Mesa semantics를 사용한다.

• Mesa semantics의 의미

  • signal은 “조건이 바뀌었을 수도 있으니 다시 확인해 봐"에 가깝다.
  • signal을 받은 thread가 깨어났을 때 조건이 여전히 참이라는 보장이 없다.

• 따라서 condition check는 if가 아니라 while로 해야 한다.

Why While, Not If

• 잘못된 방식

if (count == 0)
    wait(&cond, &mutex);

• 올바른 방식

while (count == 0)
    wait(&cond, &mutex);

• 이유

  • signal을 받고 깨어났더라도 다른 thread가 먼저 실행되어 상태를 바꿀 수 있다.
  • spurious wakeup이 있을 수 있다.
  • 조건을 다시 확인하지 않으면 비어 있는 buffer에서 get을 시도하는 bug가 생길 수 있다.

Producer / Consumer Problem

• producer-consumer 문제는 condition variable의 대표 예시다.

• 상황

  • producer는 buffer에 item을 넣는다.
  • consumer는 buffer에서 item을 꺼낸다.

• 문제

  • buffer가 비어 있으면 consumer는 기다려야 한다.
  • buffer가 가득 차 있으면 producer는 기다려야 한다.

• single buffer 기준

  • count == 0

    • buffer empty.
    • consumer wait.

  • count == 1

    • buffer full.
    • producer wait.

• condition variable을 하나만 쓰면 문제가 생길 수 있다.

  • consumer가 consumer를 깨우는 식으로 잘못된 thread가 깨어날 수 있다.

• 해결

  • condition variable을 두 개 둔다.

    • empty

      • buffer에 빈 공간이 생겼음을 producer에게 알림.

    • fill

      • buffer에 item이 생겼음을 consumer에게 알림.

  • producer는 full이면 empty에서 기다리고, item을 넣은 뒤 fill을 signal한다.

  • consumer는 empty이면 fill에서 기다리고, item을 꺼낸 뒤 empty를 signal한다.

Covering Conditions

• covering condition은 어떤 thread를 정확히 깨워야 할지 알기 어려울 때 사용한다.

• 예시

  • memory allocation에서 여러 thread가 서로 다른 크기의 memory를 기다리고 있음.
  • 어떤 free가 발생했을 때 어느 thread의 조건이 만족되는지 정확히 알기 어려움.

• 해결

  • signal 대신 broadcast를 사용해 여러 thread를 깨운다.
  • 깨어난 thread들은 각자 condition을 다시 확인한다.
  • 조건이 안 맞으면 다시 sleep한다.

• 장점

  • correctness를 얻기 쉽다.

• 단점

  • 필요 없는 thread까지 깨울 수 있다.
  • 불필요한 wakeup 비용이 생긴다.

Semaphores

• semaphore는 정수 값을 가진 synchronization primitive다.

• POSIX에서는 대표적으로 다음 두 연산을 사용한다.

  • sem_wait()
  • sem_post()

• semaphore는 초기값이 중요하다.

  • 초기값에 따라 lock처럼 동작할 수도 있고, ordering 도구처럼 동작할 수도 있다.

sem_wait

• semaphore 값을 감소시키려고 한다.
• 값이 충분하면 감소시키고 진행한다.
• 값이 없으면 thread를 block시킨다.
• 기다리던 thread는 다른 thread가 sem_post()를 호출하면 깨어날 수 있다.

sem_post

• semaphore 값을 증가시킨다.
• 기다리는 thread가 있으면 하나를 깨운다.

Binary Semaphore

• semaphore를 1로 초기화하면 lock처럼 쓸 수 있다.

• 예시

  • 초기값 1
  • 첫 번째 thread가 sem_wait() 호출 → 값 0, critical section 진입.
  • 두 번째 thread가 sem_wait() 호출 → 기다림.
  • 첫 번째 thread가 sem_post() 호출 → 값 증가, 기다리던 thread 진행.

• 이렇게 lock처럼 쓰는 semaphore를 binary semaphore라고 한다.

Semaphores for Ordering

• semaphore를 0으로 초기화하면 ordering을 맞추는 데 쓸 수 있다.

• 예시

  • parent가 child가 끝날 때까지 기다리는 상황.
  • parent는 sem_wait()에서 기다린다.
  • child가 일을 끝내면 sem_post()를 호출한다.
  • parent가 깨어나서 계속 실행한다.

• 초기값 0의 의미

  • 처음에는 통과할 수 있는 resource가 없다.
  • 누군가 post해야 진행 가능하다.

Semaphore로 Producer / Consumer 풀기

• bounded buffer 문제도 semaphore로 풀 수 있다.

• 필요한 semaphore

  • empty

    • 비어 있는 slot 개수.
    • 초기값: buffer size.

  • full

    • 채워진 slot 개수.
    • 초기값: 0.

  • mutex

    • buffer 자체에 대한 mutual exclusion.
    • 초기값: 1.

• producer 동작

  • sem_wait(empty)

    • 빈 slot이 생길 때까지 기다림.

  • sem_wait(mutex)

    • buffer 접근권 획득.

  • item 삽입.

  • sem_post(mutex)

    • buffer 접근권 반환.

  • sem_post(full)

    • 채워진 slot 증가.

• consumer 동작

  • sem_wait(full)

    • item이 생길 때까지 기다림.

  • sem_wait(mutex)

    • buffer 접근권 획득.

  • item 제거.

  • sem_post(mutex)

    • buffer 접근권 반환.

  • sem_post(empty)

    • 빈 slot 증가.

• 핵심

  • empty와 full은 ordering/condition 역할.
  • mutex는 critical section 보호 역할.

Reader-Writer Locks

• reader-writer lock은 read와 write의 성격 차이를 이용한다.

• 일반 lock

  • reader든 writer든 한 번에 하나만 critical section에 들어간다.

• reader-writer lock

  • 여러 reader는 동시에 들어갈 수 있다.
  • writer는 혼자만 들어가야 한다.
  • writer가 쓰는 동안 reader도 들어가면 안 된다.

• 사용하는 상황

  • lookup은 많고 update는 적은 자료구조.
  • read-only operation이 많을 때.

• 주의점

  • 구현이 복잡하다.
  • overhead가 커질 수 있다.
  • reader가 계속 들어오면 writer starvation이 생길 수 있다.

Dining Philosophers

• dining philosophers는 유명한 concurrency 문제다.

• 상황

  • 철학자 5명이 원형 테이블에 앉아 있다.
  • fork가 5개 있다.
  • 철학자는 생각하다가 먹으려고 한다.
  • 먹으려면 왼쪽 fork와 오른쪽 fork 두 개가 필요하다.

• 문제

  • 모든 철학자가 동시에 왼쪽 fork를 잡으면, 각자 오른쪽 fork를 기다리게 된다.
  • 아무도 진행하지 못한다.
  • deadlock이 발생한다.

• 해결 방향

  • 모든 철학자가 같은 순서로 fork를 잡지 않게 한다.
  • 예를 들어 마지막 철학자만 오른쪽 fork를 먼저 잡게 한다.
  • circular wait를 깨면 deadlock을 막을 수 있다.

Thread Throttling

• throttling은 너무 많은 thread가 동시에 어떤 구간에 들어가지 못하게 제한하는 것이다.

• 예시

  • 수백 개의 thread가 동시에 memory-intensive region에 들어가면 physical memory를 초과할 수 있다.
  • 그러면 swapping이 과도하게 발생하고 thrashing이 생긴다.

• semaphore를 사용한 해결

  • semaphore 초기값을 “동시에 들어갈 수 있는 최대 thread 수"로 설정한다.
  • region 앞에 sem_wait().
  • region 뒤에 sem_post().

• 의미

  • admission control 역할.
  • 위험한 구간에 들어가는 thread 수를 제한한다.

Implementing Semaphores

• semaphore도 내부적으로 구현되어야 한다.

• 구현 재료

  • lock
  • condition variable
  • integer state variable

• 기본 구조

  • value

    • 현재 semaphore 값.

  • lock

    • semaphore 내부 state 보호.

  • cond

    • value가 증가할 때까지 기다리는 thread를 재우고 깨움.

• wait

  • lock 획득.
  • value가 0 이하이면 condition variable에서 sleep.
  • value가 양수이면 value 감소.
  • lock release.

• post

  • lock 획득.
  • value 증가.
  • condition variable signal.
  • lock release.

Concurrency Bugs

• concurrency bug는 일반 bug보다 찾기 어렵다.

• 이유

  • 항상 재현되지 않는다.
  • thread scheduling에 따라 결과가 달라진다.
  • 어떤 실행에서는 맞고, 어떤 실행에서는 틀릴 수 있다.
  • timing이 조금만 바뀌어도 bug가 사라지거나 나타난다.

Non-Deadlock Bugs

• deadlock은 아니지만 concurrency 때문에 생기는 bug.
• 대표적으로 두 종류가 있다.

1. Atomicity Violation

• 원래 atomic하게 실행되어야 하는 코드가 중간에 끊겨서 생기는 bug.

• 예시

  • Thread 1이 어떤 pointer를 check한 뒤 사용하려고 한다.
  • 그 사이 Thread 2가 pointer를 NULL로 바꾼다.
  • Thread 1이 잘못된 pointer를 사용하게 된다.

• 해결

  • 관련된 check와 use를 하나의 critical section으로 묶는다.
  • lock을 사용해 중간에 다른 thread가 끼어들지 못하게 한다.

2. Order Violation

• 반드시 A가 B보다 먼저 실행되어야 하는데 그 순서가 보장되지 않을 때 생기는 bug.

• 예시

  • Thread 1이 초기화해야 하는 data가 있다.
  • Thread 2가 초기화가 끝나기 전에 그 data를 사용한다.

• 해결

  • condition variable이나 semaphore로 ordering을 강제한다.
  • “초기화 완료” state variable을 두고 wait/signal을 사용한다.

Deadlock Bugs

• deadlock은 여러 thread가 서로가 가진 resource를 기다리며 아무도 진행하지 못하는 상태다.
• 예시

Thread 1: L1을 잡고 L2를 기다림
Thread 2: L2를 잡고 L1을 기다림

• 결과

  • Thread 1은 Thread 2가 L2를 풀기를 기다림.
  • Thread 2는 Thread 1이 L1을 풀기를 기다림.
  • 둘 다 영원히 멈춤.

Conditions for Deadlock

• deadlock이 발생하려면 보통 네 조건이 함께 성립해야 한다.

• Mutual Exclusion

  • resource를 한 번에 하나의 thread만 사용할 수 있다.
  • 예: lock.

• Hold-and-Wait

  • thread가 이미 가진 resource를 놓지 않은 채 추가 resource를 기다린다.

• No Preemption

  • resource를 강제로 빼앗을 수 없다.
  • lock을 가진 thread가 unlock하기 전까지 다른 thread가 가져갈 수 없다.

• Circular Wait

  • thread들이 원형으로 서로의 resource를 기다린다.
  • T1은 T2를 기다리고, T2는 T3를 기다리고, T3는 T1을 기다리는 식.

• 네 조건 중 하나라도 깨지면 deadlock은 발생하지 않는다.

Deadlock Prevention

• deadlock prevention은 deadlock 조건 중 하나를 아예 깨는 방식이다.

1. Circular Wait 깨기

• lock acquisition order를 정한다.

• 예시

  • 항상 L1을 먼저 잡고 L2를 잡는다.
  • 모든 thread가 같은 순서를 따르면 circular wait가 생기지 않는다.

• 여러 lock이 있을 때는 total ordering 또는 partial ordering을 사용할 수 있다.

2. Hold-and-Wait 깨기

• 필요한 lock을 한 번에 모두 잡게 한다.

• 중간에 일부 lock만 잡고 다른 lock을 기다리는 상태를 피한다.

• 단점

  • global lock이 필요할 수 있다.
  • concurrency가 낮아질 수 있다.
  • 어떤 lock이 필요한지 미리 알기 어려울 수 있다.

3. No Preemption 깨기

• lock을 못 얻으면 이미 잡은 lock을 풀고 다시 시도한다.

• trylock을 사용할 수 있다.

• 단점

  • rollback 처리가 복잡하다.
  • 이미 수행한 작업을 되돌려야 할 수 있다.

4. Mutual Exclusion 줄이기

• lock 자체를 덜 쓰는 방식.

• lock-free 또는 wait-free data structure를 사용할 수 있다.

• compare-and-swap 같은 atomic hardware primitive를 활용한다.

• 단점

  • 구현이 어렵다.
  • 일반적인 lock보다 이해하기 힘들 수 있다.
  • 모든 문제에 쉽게 적용되지 않는다.

Deadlock Avoidance

• prevention과 다르게 avoidance는 deadlock이 생길 수 있는 조합을 피하도록 scheduling한다.

• 필요한 정보

  • 어떤 thread가 어떤 lock을 잡을 수 있는지에 대한 global knowledge.

• 방식

  • 동시에 실행하면 deadlock이 날 수 있는 thread들을 함께 schedule하지 않는다.

• 한계

  • 모든 thread의 lock 사용 정보를 미리 알아야 한다.
  • general-purpose system에서는 어렵다.
  • concurrency를 제한할 수 있다.

Detect and Recover

• deadlock을 완전히 막기 어렵다면 가끔 발생하도록 두고, 발생 후 복구할 수도 있다.

• 방식

  • resource graph를 만든다.
  • cycle이 있으면 deadlock 가능성이 있다.
  • deadlock을 감지하면 process/thread를 종료하거나 resource를 회수한다.

• 사용 예

  • database system에서 deadlock detection/recovery를 사용하는 경우가 있다.

• 한계

  • deadlock이 드물게 발생한다는 전제가 필요하다.
  • 복구 비용이 클 수 있다.

Summary

• 11단원은 concurrency의 기본 개념부터 synchronization primitive까지 이어지는 단원이다.
• thread는 하나의 process 안에서 실행되는 여러 흐름이다.
• thread들은 같은 address space를 공유하므로 data sharing이 쉽다.
• 하지만 shared data를 동시에 읽고 쓰면 race condition이 생긴다.
• race condition을 막으려면 critical section을 보호해야 한다.
• critical section 보호의 핵심 성질은 mutual exclusion이다.
• lock은 mutual exclusion을 구현하는 기본 도구다.
• 좋은 lock은 correctness, fairness, performance를 고려해야 한다.
• lock은 단순한 flag만으로는 안전하게 만들 수 없고, test-and-set, compare-and-swap, load-linked/store-conditional 같은 hardware primitive가 필요하다.
• spin lock은 단순하지만 CPU를 낭비하고 starvation 가능성이 있다.
• 더 실용적인 lock은 OS 지원을 받아 sleep/wake를 사용한다.
• Linux futex는 user-space fast path와 kernel sleep/wake를 결합한 방식이다.
• lock-based concurrent data structure는 big lock으로 시작할 수 있지만, 성능 문제가 생기면 finer-grained locking이나 approximate counter 같은 기법을 쓴다.
• condition variable은 “조건이 만족될 때까지 기다리는 문제"를 해결한다.
• condition variable을 사용할 때는 state variable, lock, while loop가 중요하다.
• producer-consumer 문제에서는 empty와 fill 같은 조건을 구분해야 한다.
• semaphore는 정수 값을 가진 synchronization primitive다.
• semaphore는 lock처럼도 쓸 수 있고, ordering 도구처럼도 쓸 수 있다.
• reader-writer lock, dining philosophers, thread throttling 같은 문제도 semaphore로 다룰 수 있다.
• concurrency bug는 크게 non-deadlock bug와 deadlock bug로 볼 수 있다.
• non-deadlock bug에는 atomicity violation과 order violation이 있다.
• deadlock은 mutual exclusion, hold-and-wait, no preemption, circular wait 네 조건이 함께 성립할 때 발생할 수 있다.
• deadlock은 prevention, avoidance, detect-and-recover 방식으로 다룰 수 있다.

시험/복습 포인트

• thread는 같은 process 안에서 실행되는 여러 execution flow다.
• thread는 PC와 register state를 따로 가지지만 address space는 공유한다.
• thread를 쓰는 이유는 parallelism과 blocking 회피다.
• shared data 때문에 race condition이 생긴다.
• critical section은 shared resource에 접근하는 코드 영역이다.
• mutual exclusion은 한 번에 하나의 thread만 critical section에 들어가게 하는 성질이다.
• lock은 critical section을 보호하는 기본 도구다.
• 좋은 lock의 기준은 correctness, fairness, performance다.
• test-and-set, compare-and-swap, LL/SC, fetch-and-add는 lock 구현에 쓰이는 hardware primitive다.
• spin lock은 간단하지만 CPU 낭비와 starvation 문제가 있다.
• futex는 Linux에서 효율적인 mutex 구현에 쓰이는 sleep/wake 기반 primitive다.
• condition variable은 조건이 만족될 때까지 thread를 재우고 signal로 깨운다.
• condition variable은 lock과 state variable과 함께 써야 한다.
• condition check는 if가 아니라 while을 써야 한다.
• producer-consumer 문제는 empty, fill, mutex로 이해하면 좋다.
• semaphore 초기값 1은 lock처럼, 초기값 0은 ordering처럼 쓰인다.
• reader-writer lock은 여러 reader를 허용하지만 writer는 exclusive하게 처리한다.
• dining philosophers는 circular wait와 deadlock을 설명하는 대표 문제다.
• deadlock 조건 네 가지는 mutual exclusion, hold-and-wait, no preemption, circular wait다.
• deadlock prevention은 이 네 조건 중 하나를 깨는 방식이다.
• concurrency의 최종 핵심은 “빠르게 동시에 실행하되, 실행 순서가 바뀌어도 결과가 항상 맞게 만들기"다.