1. 문제의식 · 2. 고수준 동기화 · 3. Semaphores · 4. Classical Problems · 5. Monitor

1. 문제의식

1. spinlock만으로는 부족하다

• 다른 스레드가 lock을 잡고 있으면 계속 기다려야 함
• busy waiting이라 CPU 낭비가 큼
• 아주 짧은 critical section에만 적합함

2. Interrupt disable/enable도 한계가 있다

• 너무 원시적인 방식(단순 mutual exclusion(critical section안에 못들어가게 하기)만 해줌)
• critical section에서 인터럽트 계속 꺼두기 어려움
• 고수준 동기화 문제를 직접 해결해주지 않음

3. 그래서 뭐가 필요하나?

• 기다리는 스레드 block시키기
• critical section 안에서도 인터럽트 켜두기
• 고수준 동기화 사용하기

2. 고수준 동기화

0. 목적

• 단순 mutual exclusion 이상을 제공
• 기다림을 효율적으로 처리
• 복잡한 동기화 패턴을 쉽게 표현

1. Semaphores

• 세마포어는 보통 스핀락을 이용해 구현되어있음

1. binary semaphores: lock, mutex처럼 사용됨, value가 1개 뿐, critical section에 하나만 들어오는걸 보장함

2. counting semaphores: 일반적으로 세마포어라고 부르는 것, value가 N(N>1)인 것, N개의 동일 자원을 관리

2. Monitors

언어차원에서 제공하는 동기화 구조

3. Semaphores

• lock보다 한단계 높은 동기화 도구
• 한번에 하나만 들어와에 더해서 자리가 있으면 들어와의 느낌
• busy waiting를 하지 않는다.(계속 CPU쓰면서 lock 열렸는지 확인하지 않는다)

1. Wait(S): 값을 감소

• 세마포어가 열려있으면 critical section안에 넣고 value -1
• 세마포어가 닫혀있으면 세마포어 waiting큐에 달아놓고 block 시킴

2. Signam(S): 값을 증가

• 세마포어 열기(value + 1)
• 세마포어 waiting queue에서 block되어있는거 unblock시키기

3. 구현 예시

typedef struct {
    int value; // 1 or 1보다 큰 값 N, value가 3이면 3개만큼 critical section에 들어갈 수 있음
    struct process *L;
} semaphore;

void wait (semaphore S) {
    S.value--;
    // 여기기 acquire(S.lock)
    if (S.value < 0) {
        add this process to S.L;
        block ();
    }
    // 여기 release(S.lock)로 막는다 왜냐. wait과 signal이 atomic하게 동작할 수 있기 때문에. 이때 spinlock이 사용된다. 이거를 위해 스핀하는건 굉장히 짧기 때문에 타당하다.
}
void signal (semaphore S) {
    // acquire(S.lock)
    S.value++;
    if (S.value <= 0) {
        remove a process P from S.L;
        wakeup (P);
    }
    // release(S.lock)
}
// 만약 require, release하는게 싫다. 그럼 인터럽트 꺼야함 아니면 하드웨어 원자적 지원을 받던가

4. binary semaphore 실행 흐름:

1. S.value = 1
2. T1이 들어가려 함
3. T1이 wait(S) 호출
4. S.value-- 1 → 0
5. S.value가 0 이상이므로 T1은 통과 → critical section 진입
6. T2가 들어가려 함
7. T2가 wait(S) 호출
8. S.value-- 0 → -1
9. S.value < 0 이므로 T2는 못 들어감 → semaphore waiting queue에 들어감 → blocked 상태가 됨
10. T1의 critical section 작업이 끝남
11. T1이 signal(S) 호출
12. S.value++ -1 → 0
13. S.value <= 0 이므로 기다리는 thread가 있다는 뜻 → semaphore waiting queue에서 T2를 꺼냄 → wakeup(T2)
14. T2는 blocked 상태에서 ready 상태가 됨 → ready queue로 이동
15. scheduler가 T2에게 CPU를 주면 T2는 wait(S)를 다시 처음부터 호출하는 게 아니라, block() 이후 지점부터 이어서 실행됨
16. T2가 critical section에 진입

5. 세마포어의 문제점

1. deadlock

• 서로가 서로를 기다려서 전체가 멈춤

예시
P0가 프린터 세마포어 S를 이미 wait으로 잡은 뒤, 스캐너 세마포어 Q에 wait을 걸다가 block된 상황
초기:
S = 1 // 프린터기
Q = 1 // 스캐너

P0: wait(S)
S = 0
P0가 프린터 잡음

P1: wait(Q)
Q = 0
P1이 스캐너 잡음

P0: wait(Q)
Q = -1
P0는 스캐너 기다림

P1: wait(S)
S = -1
P1은 프린터 기다림

해결법
초기
S = 1
Q = 1

1. P0: wait(S)
   S: 1 → 0
   P0가 S를 잡음

2. P1: wait(S)
   S: 0 → -1
   P1은 S waiting queue에서 block
   아직 Q는 잡지 못함

3. P0: wait(Q)
   Q: 1 → 0
   P0가 Q도 잡음

4. P0: 작업 실행
   S와 Q를 둘 다 가지고 있으므로 작업 가능

5. P0: signal(Q)
   Q: 0 → 1
   Q 반납

6. P0: signal(S)
   S: -1 → 0
   S waiting queue에 있던 P1 wakeup

7. P1: ready queue로 이동
   CPU를 받으면 wait(S) 이후부터 이어서 실행

8. P1: wait(Q)
   Q: 1 → 0
   P1이 Q도 잡음

9. P1: 작업 실행

10. P1: signal(Q)

11. P1: signal(S)

2. starvation

• 특정 스레드가 못일어나고 계속 block되어있는 것

예시
Semaphore S
waiting queue = [T1, T2, T3]

정상 흐름이라면 T1, T2, T3가 모두 깨어나야하는데 스케쥴링 정책이 이상하거나 우선순위 문제 때문에 특정 스레드가 깨어나지 못함

• 해결책: fairness: FIFO queue(먼저 온 큐 먼저 깨우기), aging(오래기다린거 우선순위 높이기)

3. Priority Inversion

• 우선순위가 높은 thread가, 우선순위가 낮은 thread 때문에 기다리게 되는 상황

예시
L: lock S 보유 중
H: lock S 필요함 → L 기다림
M: lock S 필요 없음 → CPU 차지

실제 지연 원인:
H가 M보다 우선순위가 높은데도
M 때문에 L이 실행되지 못하고
L이 실행되지 못하니 H도 못 깨어남

4. 너무 자유도가 높아서 사용자가 실수하기 쉽다

1. 전역변수처럼 사용된다 - 코드가 복잡해질수록 뭐가 뭔지 헷갈리기 쉬워진다
2. 용도가 섞인다
   • 세마포어는 두가지 용도로 사용가능하다
     1. Critical Section 보호
     2. 실행 순서나 조건 맞추기
3. 올바른 사용을 강제해주지 않는다.

4. Classical Problems of Synchronization(동기화의 고질병)

1. Bounded-Buffer Problem

• 생산자와 소비자가 같은 버퍼를 공유하는 상황
• producer: 버퍼에 데이터 넣기
• consumer: 버퍼에 데이터 사용하기
• buffer: 둘이 공유하는 공간(버퍼의 크기는 무한하지 않다) 생산량이 소비량보다 많으면? 소비량이 생산량 보다 많으면? 마구마구 생산해서 큐가 꽉차면 count라는 전역변수를 사용해서 더이상 안채우기, 반대도 마찬가지

2. Dining-Philosophers Problem

• 원형 식탁에서 모두가 오른쪽 젓가락을 잡으면 왼쪽 젓가락은 아무도 못잡아서 아무도 밥을 못먹는 상황이 만들어짐(deadlock상황이 발생)

3. Readers-Writers Problem

5. Monitor

• 모니터는 그냥 라이브러리 함수 하나가 아니라, 프로그래밍 언어가 제공하는 구조. Java synchronized, C# lock과 같은
• 동기화 코드를 사람이 매번 직접 쓰는 게 아니라, 컴파일러와 런타임이 도와준다

synchronized void add1() {
    x = x + 1;
}
// add1() 들어갈 때
// → lock acquire
// add1() 끝나고 나올 때
// → lock release

• 세마포어를 사람이 직접 관리하기 어려워서 나온 구조
• 공유데이터 + 데이터를 다루는 함수 + 동기화 규칙을 한 덩어리로 묶은 것
• 공유데이터에 직접 접근하지 못하게 감싼다
• 한 번에 하나의 thread만 모니터 안의 procedure를 실행할 수 있게 보장

구조
Monitor
├─ shared data structures
│  └─ 공유 변수, 공유 버퍼 같은 데이터
├─ procedures
│  └─ 그 공유 데이터를 조작하는 함수들
└─ synchronization
   └─ 동시에 여러 thread가 들어오지 못하게 하는 규칙

Semaphore
├─ wait/signal을 직접 호출해야 함
├─ 공유 데이터를 직접 건드릴 수 있음
├─ 사용 규칙을 프로그래머가 지켜야 함
└─ 실수하기 쉬움

Monitor
├─ 공유 데이터와 함수를 한 곳에 묶음
├─ 함수로만 공유 데이터 접근 가능
├─ 동기화가 구조 안에 포함됨
└─ 실수를 줄이기 쉬움

1. Encapsulation 공유 데이터를 procedure 안에 숨김
2. Mutual exclusion 한 번에 하나의 thread만 monitor 내부 실행