[OS] 상호배제와 동기화

상호배제의 개념

상호배제(Mutual Exclusion)는 병행 프로세스에서 특정 공유 자원을 한 순간에 한 개의 프로세스만 사용할 수 있을 때, 프로세스 하나가 공유 데이터에 접근하는 동안 다른 프로세스가 해당 테이터에 접근할 수 없게 제어하는 기법이다.

프로세스 간 동기화

물론 읽기 연산은 공유 데이터에 동시에 접근해도 문제가 발생하지 않는다. 하지만 변수나 파일은 프로세스 별로 하나씩 차례로 읽거나 쓰도록 해야 한다.
이때 동기화는 공유자원을 동시에 사용하지 못하게 실행을 제어하는 기법이다.
두개 이상의 프로세스를 한 시점에서 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 것으로 상호배제의 한 형태이다.
동기화는 상호배제를 보장하지만, 교착 상태와 기아 상태가 발생할 수 있다.

예시

두 프로세스 P1 과 P2를 동일한 컴퓨터에서 실행한다고 하자.

임계 자원(critical resource) : 두 프로세스가 동시에 사용할 수 없는 공유 자원
임계 영역(critical section) : 임계 자원에 접근하고 실행하는 프로그램 코드 부분

프로세스가 공통 변수를 읽고, 테이블을 갱신하고, 파일을 수정하는 등 공유 데이터에 접근할 때 임계 영역에 있다고 한다.

1단계에서 예정된 P1이 공유 메모리(임계 영역)에 들어가고, 2단계에서 인터럽트가 발생하여 P1 작업을 완료하기 전에 P2 실행을 예정한다. P2 가 공유 메모리에 진입하려고 시도하지만, P1 을 공유 메모리에서 수행하므로 P1을 종료할 때까지 P2를 차단한다.

그러므로 상호배제는 프로세스가 수정할 수 있는 공유 데이터에 접근할 때만 적용하고, 단순 읽기 등을 할 때는 동시에 수행하도록 허용해야 한다.

상호배제의 조건

이런 상호배제는 프로세스가 수정할 수 있는 공유 데이터에 접근할 때만 적용한다. 프로세스가 다른 프로세스와 충돌하지 않는 연산을 할 때는 프로세스를 동시에 수행하도록 허용해야 하므로, 다음 네 가지 조건을 만족해야 한다.

두 프로세스는 동시에 공유 자원에 진입할 수 없다.
프로세스의 속도나 프로세스 수에 영향을 받지 않는다.
공유 자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있다.
프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안된다.

임계 영역(critical section)

위에서 둘 이상의 프로세스가 공유할 수 없는 자원을 임계 자원(critical resource)라고 했다. 그리고 임계 영역(critical section)은 프로그램에서 임계 자원을 이용하는 코드 부분이다.

임계 영역에는 다수의 프로세스가 접근할 수 있지만, 어느 한 순간에는 프로세스 하나만 사용할 수 있다. 그러므로 어떤 프로세스가 임계 영역에 들어가면 다른 프로세스는 임계 영역으로 진입할 수 없어야 한다.

예를 들어 아래 그림과 같이 입력과 출력 두 프로세스가 버퍼를 공통으로 사용한다면 버퍼가 임계 영역이 되므로 두 프로세스는 동시에 버퍼를 사용하면 안 된다. 특히 공유 데이터에 여러 프로세스가 동시에 접근하면 시간 차이로 예상치 못한 결과를 만들 수 있다. 그러므로 임계 영역에는 반드시 한번에 프로세스 하나만 진입할 수 있어야 한다.

임계 영역 내에서는 빠른 속도로 작업을 수행해야 하며, 한 프로세스가 오랫동안 머무르면 안됨.
(임계 영역은 특정 프로세스가 독점할 수 없음.)
프로세스가 무한 루프 등에 빠지지 않도록 관리해야 함.

진입 상호배제

프로세스 하나가 임계 영역에 있으면 다른 프로세스가 임계 영역에 들어가지 못하게 하는 것이다. 즉, 임계 영역에 다른 프로세스가 있으면 이 프로세스(임계 영역에 이미 있는 프로세스)는 다른 프로세스가 임계 영역에 들어가지 못하도록 진입 상호배제를 수행해야 한다.

상호배제는 자물쇠와 키의 관계
프로세스가 진입하지 못하는 임계 영역은 잠금 상태
프로세스는 임계 영역에서 작업을 수행하려면, 먼저 열쇠를 얻어 자물쇠를 열어야 함.
임계 영역은 임계 영역에 있는 프로세스가 열쇠를 반환할 때까지 다른 프로세스에 대한 잠금 상태를 유지

탈출 상호배제

임계 영역을 떠나는 프로세스는 탈출 상호배제를 수행함으로써 다른 프로세스가 임계 영역에 들어갈 수 있도록 한다.

임계 영역을 이용한 상호배제는 두 동작으로 분류할 수 있다.

어떤 프로세스가 열쇠를 사용할 수 있는지 확인하려고 검사하는 동작
다른 프로세스의 사용을 금지하는 동작

물론 이 두 동작은 단일 머신 사이클에서 진행해야 한다. 첫 번째 프로세스가 열쇠를 사용할 때 다른 프로세스도 열쇠를 사용하면 임계 영역에 프로세스가 2개 있어 상호배제를 보장하지 않기 때문이다.

병행 프로세스의 코드 영역 구분

프로세스가 서로 협력하여 자원을 사용할 수 있도록 설계하면 임계 영역을 성공적으로 구현할 수 있다.

진입 영역(진입코드)
- 각 프로세스는 접근하려는 자원의 임계영역에 들어갈 수 있는지 여부를 미리 요청해야 하며, 이를 코드로 구현한 부분.
탈출 영역
- 임계 영역에서 수행을 마치고 나갈 프로세스를 선택.
나머지 영역
- 진입영역과 탈출영역을 제외한 나머지 영역으로, 임계 영역을 마치고 나와서 수행.

또한 임계 영역은 아래 세가지 조건을 만족해야 한다.

상호 배제 : 1개의 프로세스가 임계 영역에서 수행 중일 때, 다른 프로세스는 임계 영역에서 수행할 수 없어야 한다.
진행 : 임계영역에서 수행하는 프로세스가 없고 여러 개의 프로세스가 임계영역으로 들어가려고 하면 프로세스 선정 알고리즘에 따라 다음 임계영역에서 수행할 대상을 선정한다. 이때 다음 임계영역으로 들어갈 프로세스 선택은 무한정 미룰 수 없다.
한정 대기 : 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하려면 임계 영역에 한번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 제한을 둔다.

임계 영역은 어떻게 구현했느냐에 따라 상호배제의 성공 여부가 결정된다. 생산자-소비자 예로 상호배제를 해결하는 초기의 몇 가지 시도를 살펴보자.

생상자 - 소비자 문제와 상호배제를 해결하는 초기의 시도

생산자 - 소비자 문제는 OS에서 비동기적으로 수행하는 모델로, 생산자 프로세스가 생산한 정보를 소비자 프로세스가 소비하는 형태이다.

생산자는 소비자에게 데이터를 전송할 때, 데이터를 소비자가 받을 준비가 되면 데이터를 전송하고 소비자가 계속 처리하지 못하면 대기해야 한다. 이때 생산자와 소비자가 불필요하게 공회전하지 않도록 데이터를 전송하는 방법이 필요한데, 이는 임시 기억 장소인 버퍼를 도입하여 해결할 수 있다.

소비자가 데이터를 받을 준비를 마칠 때까지 생산자는 버퍼로 데이터를 전송하도록 하면 되는 것이다.

생산자와 소비자가 공유하는 버퍼는 아래 그림처럼 세가지 경우가 발생할 수 있다.

이때 생산자가 이미 가득 찬 버퍼에 더 채우려 하거나 소비자가 빈 버퍼에서 데이터를 꺼내려고 하면 문제가 발생한다.

버퍼가 다 차면 더 생산할 수 없고, 소비자는 빈 버퍼에서 데이터를 가져올 수 없음.

무한 버퍼 VS 유한 버퍼

버퍼의 크기가 무한하다면(무한 버퍼) 버퍼가 꽉 차게 되는 일이 없을 것이다. 하지만 버퍼의 크기가 유한하다면(유한 버퍼) 생산자는 버퍼가 가득 찰 때 데이터를 더 생산하지 않고 기다려야 하고, 소비자는 버퍼가 빌 때 소비하지 않고 기다려야 하므로 생산자와 소비자는 동기화(실행 순서를 제어)를 해야 한다.

먼저 무한 버퍼일 때는 아래처럼 생산자와 소비자가 독립적으로 알고리즘을 수행하도록 하여 버퍼를 활용할 수 있다.

유한 버퍼에서는 논리적 포인터 in과 out 2개로 버퍼를 순환 배열로 구현하여 해결할 수 있다.

in과 out은 0으로 초기화
변수 in은 다음으로 빈 공간을 가리키는 포인터,
변수 out은 채워진 버퍼의 첫 번째 위치를 가리키는 포인터
소비자는 버퍼에서 데이터를 읽기 전에 생산자가 앞서 가고 있는지, in > out 으로 확인.

다음은 위 버퍼를 프로그램으로 구현해본 것이다.

1. 공유 데이터 선언

#define BUFFER_SIZE 10 // 버퍼 크기
typedef struct {
	DATA data;
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

in 과 out 을 0으로 초기화
버퍼는 buffer[BUFFER_SIZE] 정수 배열로 선언하며 이때 버퍼에 최대 N-1 개만 채울 수 있음.
counter 는 원소를 추가할 때마다 1씩 증가, 삭제할 때마다 1씩 감소

2-1.생산자 프로세스

item nextProduced;

while(true) {
	// 버퍼가 가득 차 있을 경우 계속 while문에 머뭄
	while (counter == BUFFER_SIZE);
    buffer[in] = newxtProduced;
    // 유한 버퍼
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

2-2. 소비자 프로세스

item nextConsumed;

while(true) {
	// 버퍼가 비어있을 경우 아무 일도 하지 않음
	while (counter == 0);
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

그런데 두 코드를 동시에 수행하면 의도했던 방향보다 다르게 동작할 수 있다. 예를 들어, counter = 5 일때, counter++ 와 counter-- 를 동시에 수행하여 counter 값이 4, 5, 6이 될 수 있는 것이다.

반면에 두 코드를 따로 정상적으로 수행하면 counter 값은 5가 된다. counter 값이 맞는지는 기계어로 작성하여 확인할 수 있다. 여기서 register1, register2는 지역 레지스터이다.

두 코드를 동시에 수행한다는 것은 이 기계어들을 임의의 순서로 겹쳐 실행하는 것과 같다. 아래 그림을 보면 여기선 counter는 실제로 5가 되어야 하는데, 4이다. 그리고 T5와 T6의 순서를 바꾸면 6이 되기도 한다.

이처럼 counter 값이 일관성 없는 이유는 두 프로세스가 counter 를 동시에 연산하기 때문이다.

경쟁 상태(race condition)

위 예제처럼 여러 프로세스가 동시에(병행적으로) 공유 데이터에 접근(읽기나 쓰기)할 때 접근 순서에 따라 실행 결과가 달라지는 상황에 놓인 프로세스들을 경쟁 상태(race condition)에 있다고 한다.

즉, 공유 데이터에 최종적으로 남는 데이터의 결과를 보장할 수 없는 상황을 의미한다.

장치나 시스템이 둘 이상의 연산을 동시에 수행하려 할 때, 어느 프로세스가 제일 마지막에 수행된 후 결과를 저장했느냐에 따라 발생하는 오류

그러므로 접근 순서화가 필요하다.

읽기와 쓰기 명령을 거의 동시에 실행해야 한다면, 기본적으로 읽기 명령을 먼저 수행하고 다음에 쓰기 명령을 수행

경쟁 상태 예방(동기화)

임게 영역을 이용한 상호 배제로 구현 가능.

임계 영역

공유 변수 counter를 어느 한 순간에 한 프로세스만 조작할 수 있도록 한다.
여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로스세만 자원 또는 데이터를 사용하도록 지정된 공유 자원(영역)을 의미
임계 구역에서는 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납한 후에만 다른 프로세스가 자원이나 데이터를 사용할 수 있음.

상호배제

공유 변수 counter를 연산하는 부분을 임계 영역으로 설정하여 상호 배제함.
공유 자원(영역)을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 공유 자원에 대하여 접근하지 못하게 제어하는 기법

참고

운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미