Mutual Exclusion with Busy Waiting

바쁜 대기를 이용한 상호배제

1. 인터럽트 끄기(Disabling interrupts)

가장 간단한 방법이지만 그다지 유쾌한 방법은 아니다.

 각 프로세스가 임계구역에 진입하자마자 인터럽트를 끄고 임계구역에서 나가기 직전에 인터럽트를 켜도록 하는 방식이다. CPU는 오직 클록이나 다른 인터럽트의 결과로 프로세스간에 문맥을 교환하므로 인터럽트를 끄면 CPU는 다른 프로세스로 문맥을 교환하지 않는다. 따라서 프로세스가 인터럽트를 끄면 다른 프로세스가 끼어들 걱정 없이 공유 메모리를 검사하고 변경할 수 있다.

 이 방법이 유쾌하지 않은 이유는 우선 사용자 프로세스에게 인터럽트를 끌 수 있는 권한을 주는 것은 현명하지 못하기 때문이다. 만약 프로세스 중 하나가 인터럽트를 끄고 다시 켜지 않는다면 어떻게 될지 생각해 보라.

또한 (둘 이상의 CPU를 가진) 다중처리기 시스테믜 경우 인터럽트를 끄는 disable 명령은 이 명령을 수행한 CPU에게만 영향을 미친다. 다른 CPU들은 계속 실행하면서 공유 메모리에 접근할 것이다.

최근 대부분의 PC가 멀티 이상의 코어를 가지고 있는 것을 생각했을 때 이 방법은 해결책이라고 보기 힘들다.

2. 락 변수(Lock variables)

0으로 초기화된 단일 공유 변수(락변수)가 있다고 하자. 임계구역에 진입하려는 프로세스는 먼저 락 변수 값을 검사한다. 만약 락이 0이면 프로세스는 이를 1로 설정하고 임계구역에 진입한다. 만약 락이 이미 1이면 프로세스는 이 변수가 0이 될 때까지 기다린다. 따라서 0 값은 임계구역 내에 어떤 프로세스도 없다는 것을 의미하며 1은 임계구역에 어떤 프로세스가 존재함을 의미한다.

 이 방법은 스풀러 디렉터리와 동일한 결함을 가지고 있다. 한 프로세스가 락을 읽고 이 값이 0임을 알았다고 하자. 프로세스가 락을 1로 설정하려는 순간 CPU가 문맥을 교환해 다른 프로세스에게 CPU를 할당한다. 이 프로세스는 락 값이 0이므로 값을 1로 설정한 후 임계구역에 들어갈 것이다. 여기서 다시 첫 번째 프로세스가 실행된다면 첫 번째 프로세스는 자연스럽게 락을 1로 설정하는 명령어를 넣고 임계구역에 들어갈 것이고 결국 두 개의 프로세스가 동시에 임계구역에 들어가게 된다.

3. 엄격한 교대(Strict Alternation)

 

두 프로세스가 공유변수 turn 값을 기준으로 임계구역에 들어갈지를 결정한다. (a)의 프로세스0은 turn값이 0이면 임계구역에 진입한다. (a)의  while(turn != 0) 문장은 turn이 0이 될 때까지 무한루프를 도는 동작이다. 만약 turn이 0이 되어 임계구역에 진입한다면 나올 때는 다른 프로세스가 사용할 수 있게 turn값을 1로 바꿔주고 나온다. 착하다.

(b)의 프로세스1도 위와 마찬가지다.

그런데 이 방법은 두 프로세스의 작업 속도가 차이가 많이 날 경우 비효율을 초래하게 된다. 만약 프로세스0의 작업이 프로세스 1의 작업에 비해 매우 간단한 경우 프로세스0은 자기 일을 신속하게 수행하더라도 프로세스1의 작업이 오래 걸리므로 매번 오랜 시간을 기다려야 한다.

또한 이 방법은 상호배제는 만족하지만 3번 조건인 Progress조건을 만족시킬 수 없다. 예를 들어 (a) 프로세스가 임계구역에 들어갔다가 나오면  CPU가 사용중이지 않더라도 (b)프로세스가 작업을 하기 전에 (a)프로세스는 임계구역에 다시 들어갈 수 없게 된다.(turn 값을 1로 설정하고 나왔기 때문)

결국 이 알고리즘은 조3을 위반하므로 진정한 해결책의 후보가 될 수 없다.

4.Peterson의 해법

5. TSL 명령

하드웨어의 도움을 약간 필요로 하는 해결책이다.

TSL(Time and Set Lock) 명령은 다음과 같이 작동한다. 이것은 메모리 워드 LOCK의 값을 읽어 레지스터 REGISTER에 저장하고 메모리 주소 LOCK에 0이 아닌 값을 기록한다. 워드를 읽고 어떤 값을 저장하는 연산은 분할이 불가능하여(atomic) 이 연산이 완료될 때까지 다른 어떤 처리기도 메모리 워드에 접근할 수 없다. TSL 명령을 수행하는 CPU는 수행이 끝날 때까지 메모리 버스를 잠금으로써 다른 어떤 CPU도 메모리에 접근할 수 없도록 한다.

 메모리 버스를 잠그는 것은 인터럽트를 끄는 것과 매우 다르다. 인터럽트를 끄고 메모리 워드를 읽고 쓰는 경우는 중간에 다른 처리기가 버스를 통해 해당 워드에 접근하는 것을 막을 수 없다. 처리기 1에서 인터럽트를 끄는 것은 처리기 2에 전혀 영향을 미치지 못한다. 처리기 1의 작업이 끝날 때까지 처리기 2가 메모리에 접근하지 못하도록 하는 유일한 방법은 버스를 잠그는 것이며 이는 특별한 하드웨어 기능(버스를 잠근 처리기를 제외하고 다른 처리기가 버스를 사용하지 못하도록 버스 잠금을 선언하는 버스 라인)을 필요로 한다.