임계구역 해결 방법

초보개발·2022년 4월 8일

OS

목록 보기

36/38

1. 기본 코드 소개

extern bool lock = false;
extern int balance;

int main() {
	while(lock == true);
	lock = true;
	balance += 10; // 임계구역
	lock = false;
}

2. 임계구역 해결 조건을 고려한 코드 설계

2.1 상호 배제 문제

lock = true이면 잠금, lock = false이면 잠금 해제
while(lock == true); 프로세스 P1, P2는 임계구역에 진입하기 전 임계구역에 잠금이 걸려 있는지 확인합니다. 만약 잠겨있다면 잠금이 해제될 때까지 무한 루프를 돌며 기다립니다.
lock=false; 임계구역에 있던 프로세스가 작업을 마치고 잠금을 해제하면 무한 루프를 빠져나와 작업을 시작합니다.
lock=true; 다른 프로세스가 접근하지 못하도록 잠금을 걸고 작업을 하고, 완료되면 다른 프로세스가 자원을 사용할 수 있도록 잠금을 해제시킵니다. lock=false;

아래의 상황은 어떠한 상황에서 문제가 발생하지 않는지 나타냅니다.

P1은 while(lock == true);를 실행하고 임계구역에 아직 작업중인 프로세스가 없기 때문에 무한 루프를 빠져나옵니다. 하지만 다음 문장을 실행하려던 순간, 자신에게 주어진 CPU 시간이 다 소진되어 준비 상태로 변경되어 버립니다. 문맥 교환이 발생하여 P2가 실행 상태로 변경됩니다.
P2는 while(lock == true);를 실행하는데 P1이 잠금을 걸지 않았으므로 임계구역에 진입할 수 있습니다.
P1은 lock=true;문을 실행해 임계구역에 잠금을 걸고 진입하고 P2도 lock = true;를 실행해 임계구역에 잠금을 걸고 진입하여 두 프로세스 모두 임계구역에 진입하게 됩니다.

P1은 while(lock == true)를 실행하고 나서 바로 lock = true를 실행해야만 다른 프로세스가 임계구역에 들어오는 것을 막을 수 있습니다. 하지만 P1이 lock = true;를 실행하기 전에 P2가 while(lock = true)를 실행하게 되면 둘다 임계구역에 진입하게 되어 상호 배제 조건을 보장하지 못하게 됩니다.

2.2 한정 대기 문제

아래 그림은 상호 배제를 보장하지 못하는 코드를 보완하여 작성된 코드입니다. 전역 변수로 lock1, lock2를 사용합니다.

이 코드에서는 잠금을 두 변수로 나누어 사용하므로 상호 배제가 보장됩니다. 하지만 아래와 같은 경우 두 프로세스가 모두 임계구역에 진입하지 못하는 무한 대기 현상이 발생하게 됩니다.

P1은 lock1 = true를 실행하고 자신의 CPU 시간을 모두 다 써버려 문맥 교환이 발생하고 P2가 실행 상태로 전환됩니다.
P2는 lock2 = true를 실행하고 자신의 CPu 시간을 모두 다 써버려 문맥 교환이 발생하고 P1이 실행 상태로 전환됩니다.
lock2 = true이므로 P1은 while(lock2 == true)에서 무한 루프에 빠지게 됩니다.
lock1 = true이므로 P2도 마찬가지로 while(lock1 == true)에서 무한 루프에 빠지게 됩니다.

P1, P2 모두 무한 루프에 빠져 임계구역으로 진입할 수 없게 됩니다. 한정 대기 조건을 보장하지 못하게 되어 교착 상태(Deadlock)에 빠지게 됩니다. 또한 이 코드는 프로세스가 증가하면 lock 변수도 증가하기 때문에 검사해야할 lock의 개수가 늘어나게 되어 비효율적입니다.

2.3 진행의 융통성 문제

공유 변수 lock 값이 1이면 프로세스 P1이 사용하고 lock 값이 2이면 프로세스 P2가 임계구역을 사용하는 뜻입니다. 잠금을 확인하는 문장이 하나이므로 상호 배제와 한정 대기를 보장합니다. 하지만 서로 번갈아가며 실행된다면 문제가 발생하게 됩니다.

프로세스의 우선순위에 무관하게 번갈아가며 임계구역에 진입하므로 한 프로세스가 두 번 연달아 임계구역에 진입하고 싶어도 진입할 수가 없습니다. P1은 P2가 임계구역에 진입하고 나온 다음에야 다시 진입할 수 있어 진행을 방해하는 구조라고 볼 수 있습니다. 이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(lockstep synchronization)라고 합니다.

2.4 하드웨어적인 해결 방법

기존의 while(lock == true)와 lock = true를 하드웨어적으로 두 명령어를 동시에 실행하면 임계구역 문제를 해결할 수 있습니다.

test and set 코드를 이용하면 명령어 실행 도중에 타임아웃이 발생하여 임계구역을 보호하지 못하는 문제가 발생하지 않게 됩니다. 방법은 편리하지만 바쁜 대기를 사용하여 검사하므로 자원 낭비의 문제가 있습니다. (성능 좋은 하드웨어에서는 바쁜 대기 없이 동기화해주기도 함)

3. Peterson’s Algorithm

P1은 임계구역에 진입하기 전, 먼저 잠금하고 turn을 2로 설정합니다. 변수 turn은 두 프로세스가 동시에 lock을 설정해 임계구역에 못들어가는 상황에 대비하기 위한 변수로 쓰입니다. 즉, 두 프로세스가 동시에 lock를 설정했더라도 turn을 사용해 다른 프로세스에 양보할 수 있습니다.

while(lock2 == true and turn == 2)를 실행하고 P2가 잠금을 설정하지 않았거나 잠금을 설정했더라도 곧바로 trun = 1로 바꾸면 P1은 임계구역에 진입해 작업을 마친 후 잠금을 해제하고 임계구역을 빠져나옵니다. P2도 같은 방식으로 임계구역에 진입합니다.

피터슨 알고리즘은 임계구역 해결의 세 가지 조건을 모두 만족하지만 2개의 프로세스에 대해서만 가능하다는 한계가 있어 사용하지 않습니다.

4. Dekker’s Algorithm

P1은 먼저 잠금을 겁니다.
P2의 잠금이 걸렸는지 확인합니다.
P2의 잠금이 걸려있다면 누가 먼저인지 확인합니다.if(turn == 2) 만약 P1의 차례라면(turn == 1) 임계구역으로 진입하고 P2의 차례라면 4로 이동합니다.
P1은 잠금을 풀고 프로세스 P2가 작업을 마칠 때까지 기다립니다. P2가 작업을 마치면 잠금을 걸고 임계구역으로 진입합니다.

임계구역 해결의 세가지 조건을 모두 만족하지만 프로세스가 늘어나면 그만큼 관리해야할 변수가 늘어나므로 복잡해지는 단점이 있어 잘 사용되지 않습니다.

5. Semaphore

앞의 알고리즘들은 바쁜 대기를 사용하여 자원 낭비가 심하고 알고리즘도 복잡하다는 단점이 있습니다. 이를 해결하기 위해 Dijkstra는 세마포어라는 알고리즘을 제안하였습니다.

세마포어는 임계구역에 진입하기 전 스위치를 사용 중으로 놓고 임계구역으로 들어가고 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다립니다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보냅니다.

세마포어는 임계구역이 잠겼는지 직접 확인하거나 바쁜 대기를 하거나 다른 프로세스에게 동기화 메시지를 보낼 필요가 없어 간단한 알고리즘입니다.

세마포어는 사용 전 초기 설정 Semaphore(n)을 하는데, n은 공유 가능한 자원의 수를 나타냅니다. 초기화를 하고 나서 임계구역에 들어가기 전에 사용 중이라는 표시 P()를 하고 임께구역을 나올 때 비었다고 표시하는 V()로 간단한 방법으로 임계구역을 보호합니다.

Semaphore(n): 전역 변수 RS를 n으로 초기화하며 RS는 현재 사용 가능한 자원의 수가 저장되어 있습니다.
P(): 잠금을 수행하는 함수, RS가 0보다 크면 1 감소시키고 임계구역에 진입하고 0보다 작으면 0보다 커질 때까지 대기합니다.

P() {
	if(RS > 0)
		RS -= 1;
	else
		block(); // until Rs > 0
}

V(): 잠금 해제와 동기화를 같이 수행하는 함수, RS 값을 1 증가시키고 세마포어 큐에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake_up 신호를 보냅니다.

V() {
	RS += 1;
	wake_up();
}

세마포어의 P(), V() 내부 코드가 실행되는 도중에 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장할 수 없습니다. 그러므로 P(), V()의 내부 코드는 검사와 지정을 사용해 분리 실행되지 않고 완전히 실행되게 해야 합니다.

6. moniter

세마포어는 사용자가 고의로 세마포를 사용하지 않거나 사용 중 실수때문에 문제가 발생하면 임계구역이 보호받지 못한다는 문제가 있습니다.

프로세스가 세마포어를 사용하지않고 임계구역을 진입
P()를 두번 사용해 wake_up 신호가 발생하지 않은 경우 → 세마포어 큐에 대기하고 있는 프로세스들이 무한 대기에 빠짐
P()와 V()를 반대로 사용해 상호 배제가 보장되지 않는 경우

공유 자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P(), V() 사용하지 않고 자동으로 처리할 수 있도록 하면 되는데, 이를 구현한 것이 모니터입니다. 모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간 동기화를 시킬 수 있습니다.