프로세스 동기화

1. 같은 데이터를 동시에 건드리면

컴퓨터에서 데이터를 고치는 일은 한 번에 끝나지 않습니다. 저장소에서 값을 읽어오고, 연산하고, 다시 써 넣는 세 단계입니다. count++ 한 줄도 기계 수준에서는 세 동작입니다.

문제는 이 세 단계 사이에 CPU를 빼앗길 수 있다는 점입니다.

작은 예제

공유 변수 count가 10입니다. 프로세스 P1은 count++를, P2는 count--를 수행합니다.

순서	수행 주체	동작	레지스터	count
1	P1	count를 읽음	R1 = 10	10
2	P1	1을 더함	R1 = 11	10
3	-	문맥 교환	-	10
4	P2	count를 읽음	R2 = 10	10
5	P2	1을 뺌	R2 = 9	10
6	P2	count에 씀	R2 = 9	9
7	-	문맥 교환	-	9
8	P1	count에 씀	R1 = 11	11

정답은 10인데 결과는 11이 됐습니다. 순서를 바꾸면 9가 나오기도 합니다. 이렇게 실행 순서에 따라 결과가 달라지는 상황을 경쟁 상태(race condition)라고 합니다.

공유 데이터의 동시 접근은 데이터 불일치를 낳습니다. 일관성을 지키려면 협력 프로세스 간의 실행 순서를 정해 주는 장치가 필요합니다.

2. 운영체제에서는 어디서 생기는가

커널 코드도 여러 프로세스가 공유하는 데이터를 다룹니다. 경쟁 상태가 생기는 자리는 셋입니다.

1. 커널 수행 중 인터럽트가 발생하는 경우: 커널이 공유 데이터를 고치는 중에 인터럽트 처리 루틴이 같은 데이터를 건드리면 위 예제와 같은 일이 벌어집니다
2. 프로세스가 시스템콜로 커널 모드에서 수행 중인데 문맥 교환이 일어나는 경우: 두 프로세스가 커널 데이터를 번갈아 고치게 됩니다
3. 멀티프로세서에서 공유 메모리의 커널 데이터를 다루는 경우: CPU가 여럿이면 문맥 교환 없이도 두 CPU가 같은 순간에 같은 데이터를 건드립니다

1번은 인터럽트를 잠시 막아서, 2번은 커널 모드 수행 중에는 뺏지 않도록 해서 막을 수 있습니다. 3번은 그런 방법이 통하지 않아 본격적인 동기화 장치가 필요합니다.

3. 임계구역과 충족 조건

공유 데이터를 건드리는 코드 구간을 임계구역(critical section)이라고 합니다. 목표는 "한 번에 한 프로세스만 임계구역에 들어가게 하는 것"입니다.

do {
    진입 구역 (entry section)
        임계구역 (critical section)
    퇴출 구역 (exit section)
        나머지 구역 (remainder section)
} while (1);

프로그램으로 이 문제를 풀려면 세 조건을 모두 만족해야 합니다.

조건	의미	어기면
상호 배제 (mutual exclusion)	한 프로세스가 임계구역에 있으면 다른 프로세스는 못 들어감	1절의 데이터 불일치
진행 (progress)	아무도 임계구역에 없으면, 들어가려는 프로세스 중 하나는 들어가야 함	빈 방을 두고 아무도 못 들어감
유한 대기 (bounded waiting)	기다리는 시간에 한계가 있어야 함	특정 프로세스가 영원히 대기 (기아)

4. 소프트웨어로 풀어 보기

프로세스가 둘인 상황에서 단계적으로 시도해 봅니다.

알고리즘 1은 turn 변수 하나로 차례를 정합니다. 자기 차례가 아니면 while 문에서 기다립니다. 상호 배제는 되지만, 반드시 교대로만 들어갈 수 있다는 것이 문제입니다. P0이 한 번 더 들어가고 싶어도 P1이 한 번 들어가 줘야 차례가 넘어옵니다. 진행 조건을 만족하지 못합니다.

알고리즘 2는 flag 배열을 써서 "나 들어갈래"라고 깃발을 들고, 상대가 깃발을 들고 있으면 기다립니다. 그런데 둘이 동시에 깃발을 들면 서로 상대가 내리기를 기다립니다. 임계구역은 비어 있는데 아무도 못 들어갑니다. 역시 진행 조건을 만족하지 못합니다.

알고리즘 3(Peterson 알고리즘)은 둘을 합칩니다. 깃발을 들되, 동시에 들었을 때는 turn으로 양보 순서를 정합니다.

flag[i] = true;          // 나 들어가고 싶다
turn = j;                // 근데 너부터 해
while (flag[j] && turn == j)
    ;                    // 상대가 원하고 상대 차례면 기다린다
    // 임계구역
flag[i] = false;

세 조건을 모두 만족합니다. 다만 기다리는 방식이 while 문을 계속 도는 것입니다. CPU를 잡은 채로 아무 일도 하지 않고 검사만 반복하는 이 상태를 바쁜 대기(busy waiting) 또는 스핀 락(spin lock)이라고 합니다.

알고리즘	방식	상호 배제	진행	문제
1	turn 변수	만족	불만족	반드시 교대해야 함
2	flag 배열	만족	불만족	둘 다 깃발만 들고 멈춤
3 (Peterson)	flag + turn	만족	만족	busy waiting

5. 하드웨어가 도와주면

소프트웨어 해결이 복잡한 근본 원인은 "읽고 쓰는 사이에 끊긴다"는 것이었습니다. 그렇다면 읽기와 쓰기를 하나의 명령으로 묶어 중간에 끊기지 않게 하면 됩니다.

Test-and-set 명령이 그것입니다. 값을 읽어 오는 동시에 새 값을 써 넣는 일을 원자적으로(atomic) 수행합니다. 이 명령 하나만 있으면 4절의 복잡한 알고리즘이 단순한 형태로 줄어듭니다.

6. 세마포어

매번 이런 코드를 직접 짜는 것은 번거롭습니다. 그래서 앞의 방식들을 추상화한 것이 세마포어(semaphore)입니다. 정수 변수 하나와 두 연산으로 이뤄집니다.

• P(S): 자원을 얻는 연산. 값이 없으면 기다립니다
• V(S): 자원을 반납하는 연산

두 연산은 원자적으로 수행됩니다. 세마포어는 두 종류가 있습니다. 값이 0과 1만 가능한 binary semaphore는 상호 배제용이고, 임의의 정수를 갖는 counting semaphore는 자원이 여러 개일 때 남은 개수를 셉니다.

기다리는 방식은 둘로 나뉩니다.

방식	동작	유리한 상황
busy-wait (spin lock)	CPU를 잡은 채 검사 반복	임계구역이 아주 짧을 때
block & wakeup (sleep lock)	Blocked 상태로 전환, 반납 시 깨워 줌	임계구역이 길 때

block & wakeup은 상태 전환 비용이 들기 때문에, 대기 시간이 문맥 교환 비용보다 짧으면 오히려 손해입니다.

7. 세마포어로도 남는 문제

세마포어를 쓴다고 모든 것이 풀리지는 않습니다.

• 교착 상태(deadlock): 둘 이상이 서로가 가진 자원을 기다리며 영원히 멈춥니다. P 연산의 순서를 잘못 짜면 바로 발생합니다
• 기아(starvation): 특정 프로세스만 계속 자원을 얻지 못합니다

이 문제들을 보여 주는 고전 예가 식사하는 철학자(dining philosophers) 문제입니다. 철학자 다섯이 원탁에 앉고 젓가락은 사이사이에 다섯 개뿐이라, 각자 양옆 젓가락을 모두 들어야 식사할 수 있습니다. 다섯이 동시에 왼쪽 젓가락을 집으면 모두 오른쪽을 기다리며 멈춥니다.