[운영체제] 6. Process Synchronization

📑 본 글은 반효경 교수님의 운영체제 강의를 듣고 정리한 글입니다.

프로세스 동기화 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 유발할 수 있다.
• 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해 주는 메커니즘이 필요하다.
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• race condition을 막기 위해서는 병행 (concurrent) process는 동기화되어야 한다.

임계 구역 문제

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 임계 구역 (critical section)이 존재한다.
• 하나의 프로세스가 임계 구역에 있을 때 다른 모든 프로세스는 임계 구역에 들어갈 수 없어야 한다.

해결을 위한 충족 조건

상호 배제 (Mutual Exclusion)

어떤 프로세스가 임계 구역 부분을 수행 중이면 다른 모든 프로세스는 그의 임계 구역에 들어가면 안 된다.

진행 (Progress)

아무도 임계 구역에 있지 않은 상태에서 임계 구역에 들어가고자 하는 프로세스가 있으면 임계 구역에 들어가게 해 주어야 한다.

유한 대기 (Bounded Waiting)

프로세스가 임계 구역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 구역에 들어가는 횟수에 한계가 있어야 한다.

해결

Peterson's Algorithm

상대방이 임계 구역에 들어가 있지 않고, 들어갈 준비도 하지 않는다면 내가 들어간다.
세 조건을 모두 만족하지만, 계속 CPU와 메모리를 쓰면서 기다리기 때문에 busy waiting (spin lock)이 발생한다.
쉽게 말해 임계 구역에 들어가려면 상대방이 CPU를 잡고 flag 변수를 false로 바꿔주어야 하는데, 내가 CPU를 잡고 있는 상황에서 의미 없이 while문을 돌며 CPU 할당 시간을 낭비해야 한다.

do {
    flag[i] = true;
    turn = j;
    while (flag[i] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while (1);

동기화 하드웨어

임계 구역 문제가 발생한 근본적인 이유는 데이터를 읽고 쓰는 동작을 하나의 명령어로 수행할 수 없기 때문이다.
따라서 명령어 하나만으로 데이터를 읽는 작업과 쓰는 작업을 atomic 하게 수행하도록 지원하면 앞선 임계 구역 문제를 간단하게 해결할 수 있다.

세마포어 (Semaphore)

세마포어 변수 값만큼 여러 개의 프로세스가 임계 구역에 접근할 수 있다.
아래 예제에서는 mutex의 값이 1이라고 가정한다.

P(mutex) 연산 수행 시, mutex의 값이 양수가 아니면 계속 기다려야 한다.
이때 프로세스의 CPU 할당 시간이 끝날 때까지 무의미하게 CPU를 낭비하는데, 이러한 현상을 busy-wait 또는 spin lock 이라고 부른다.
이러한 단점을 보완하기 위해 Block & Wake-up 혹은 Sleep lock 이라고 부르는 기법이 생겨났다.

do {
    P(mutex); // mutex의 값이 양수면 임계 구역 접근하고, 아니면 기다린다.
    critical section
    V(mutex); // mutex의 값을 1 증가한다.
    remainder section
} while (1);

세마포어의 종류

계수 세마포어 (Counting Semaphore)

• 도메인이 0 이상인 임의의 정수 값
• 여러 개의 공유 자원을 상호 배제함.
• 주로 resource counting에 사용됨.

이진 세마포어 (Binary Semaphore)

• 0 또는 1 값만 가질 수 있음.
• 한 개의 공유 자원을 상호 배제함.
• mutex와 유사함. (완전히 같지는 않음.)

Deadlock과 Starvation

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다.

Starvation

프로세스가 자원을 얻지 못하고 무한히 기다리는 현상이다.

Bounded-Buffer-Problem (Producer-Consumer Problem)

• 공유 버퍼이기 때문에 생산자 여러 명이 동시에 한 버퍼에 데이터를 쓰거나 수정할 수 있다.
• 마찬가지로 생산자가 동시에 한 버퍼의 데이터를 읽어갈 수 있다.

공유 데이터

buffer 자체 및 buffer 조작 변수

Producer (생산자)

• Empty 버퍼가 있는지 확인한다.
• 공유 데이터에 lock을 건다.
• Empty 버퍼에 데이터를 입력하고 버퍼를 조작한다.
• lock을 푼다.
• Full 버퍼가 하나 증가한다.

Consumer (소비자)

• Full 버퍼가 있는지 확인한다.
• 공유 데이터에 lock을 건다.
• Full 버퍼에서 데이터를 꺼내고 버퍼를 조작한다.
• lock을 푼다.
• Empty 버퍼가 하나 증가한다.

Readers-Writers Problem (독자-저자 문제)

• 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 된다.
• read는 동시에 여러 명이 해도 됨.

Solution

• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 - DB에 접근할 수 있게 해 준다.
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
• Writer가 DB에서 빠져 나가야만 Reader의 접근이 허용된다.

Dining-Philosophers Problem (식사하는 철학자 문제)

철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다.
그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다.

1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다.

2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다.

3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.

4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.

5. 다시 생각하다가 배고프면 1번으로 돌아간다.

Solution

• 4명의 철학자만 테이블에 동시에 앉을 수 있게 한다.
• 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
  -짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 방향을 정해준다.

세마포어의 문제점

• 코딩하기 힘들다.
• 정확성의 입증이 어렵다.
• 자발적 협력이 필요하다.
• 한 번의 실수가 모든 시스템에 치명적인 영향을 끼친다.

Monitor

세마포어의 문제점을 해결하고자 등장했다.
프로그래밍 언어 차원에서 동기화 문제를 해결할 수 있는 고수준 동기화 도구이다.
프로세스가 공유 데이터에 접근하기 위해서는 위와 같이 모니터 내부의 프로시저를 통해서만 공유 데이터를 접근할 수 있도록 설계한다.