공유 자원의 접근과 임계 구역

공유 자원(shared resource)는 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말합니다. 그리고 다수의 프로세스가 이러한 한정된 공유 자원을 가지고 공동으로 작업할 때 문제가 발생할 수 있습니다. 이렇게 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 임계 구역이라고 합니다. 그렇다면 임계 구역에서 문제가 발생하지 않기 위해서는 어떠한 조건을 만족해야 할까요?

임계 구역 해결 조건

3가지 조건이 존재합니다. 상호 배제(mutual exclusion), 한정 대기(bounded waiting), 진행의 융통성(progress flexibility) 입니다.

• 상호배제(mutual exclusion)
  한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계 구역에 들어갈 수 없는 것
• 한정 대기(bounded waiting)
  어떤 프로세스도 무한 대기하지 않아야 함
• 진행의 융통성(progress flexibility)
  한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다는 것

위 3가지 조건을 만족하는 코드를 설계하기 위해 다양한 방식이 나왔습니다. 다음 방식은 임계 구역 문제의 하드웨어적인 해결 방법입니다. 검사와 지정(test-and-set) 코드로 하드웨어의 지원을 받아 while(lock==true); 문과 lock=true; 문을 한꺼번에 실행하며 실행 중간에 타임아웃이 걸려 임계 구역을 보호하지 못하는 문제가 발생하지 않습니다. 주로 방산과 같은 중요한 프로그램에 사용되는 기술입니다.

while(testandset(&lock) == true);
//
임계구역
//
lock = false;

피터슨 알고리즘

피터슨 알고리즘은 변수 turn을 이용하여 두 프로세스가 동시에 lock을 설정하여 임계 구역에 진입불가 상황을 대비하는 알고리즘입니다. 만약 프로세스 P2의 잠금을 설정하지 않았거나 잠금을 설정했어도 turn이 1로 바뀌면 프로세스 P1은 임계 구역에 진입하여 작업을 완료한 후 잠금을 해제하고 임계 구역에서 벗어날 수 있습니다. 따라서 프로세스 P1이 임계 구역에 진입하기 위해서는 lock2가 false이거나 turn이 1이어야 합니다. 피터슨 알고리즘은 임계 구역 해결의 3가지 조건을 만족하지만 2개의 프로세스만 사용 가능하다는 단점이 존재합니다.

데커 알고리즘

데커 알고리즘의 동작 방식은 피터슨 알고리즘에 비해서는 조금 복잡합니다.
우선 공유 변수에서 lock1과 lock2가 false이고 turn값이 1인 상태에서 시작하며 프로세스 P1의 입장에서 본다고 가정합니다. 프로세스 P1에 잠금을 겁니다. 그리고 프로세스 P2에 잠금이 걸렸는지 확인합니다. 현재 lock2의 값이 false이므로 임계 구역으로 넘어가 작업을 하고 turn의 값을 2로 lock1의 값을 false로 지정합니다. 만약 프로세스 P2도 잠금이 걸렸다면 즉 lock2의 값이 true라면 turn 변수의 값을 통해서 우선 순위가 높은 프로세스를 확인합니다. 만약 P1이 높으면 임계 구역으로 진입하고 P2가 높으면 lock1을 false로 만들고 프로세스 P2의 작업이 끝날 때까지 기다립니다.

데커 알고리즘은 하드웨어의 도움 없이 임계 구역의 문제 해결이 가능하다는 장점이 있습니다.

세마포어(semaphore)

또 다른 임계 구역 문제 해결 방식으로는 세마포어가 있습니다. 세마포어는 다익스트라가 제안한 이론으로 프로세스가 임계 구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계 구역으로 들어가는 것 입니다. 이후에 도착한 프로세스는 스위치의 상태를 확인하고 앞의 프로세스가 작업을 마칠 때까지 기다립니다. 프로세스가 작업을 마치면 다음 프로세스에게 임계 구역을 사용하라는 동기화 신호를 보냅니다. 세마포어는 사용 전에 Semaphore(n);을 이용하여 사용 가능한 자원의 개수 n개를 나타냅니다. 임계 구역 진입 전에 P();을 이용하여 사용 중이라고 표시합니다. 이는 마치 스위치를 눌러 사용 중인 상태를 나타내는 것과 같습니다. 임계 구역을 나오면 V();를 통해 스위치를 내리며 사용을 끝났음을 나타냅니다. P(); 과정에서 사용 가능한 자원의 개수 n이 n-1로 줄어들고 V();를 통해 사용이 끝났으므로 사용 가능한 자원이 n-1개에서 다시 n개로 되돌아 옵니다. 위의 그림에서 RS는 사용 가능한 자원의 수를 저장하는 변수입니다.

모니터(monitor)

하지만 세마포어를 위 그림과 같이 잘못 사용하는 경우 임계 구역을 보호하지 못하게 됩니다. 각각의 경우는 세마포어를 사용하지 않은 경우, P();를 2번 사용한 경우, V();와 P();의 순서를 바꾸어 사용한 경우에 해당합니다.

이러한 실수를 없애기 위해 생긴 방법이 모니터입니다.
모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만을 제공함으로서 자원을 보호하고 프로세스 간에 동기화를 시킵니다. 임계 구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업을 요청하면 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려줍니다.

교착상태(dead lock)

시스템 내에 임계 구역이 존재하면 프로세스 간 상호배제를 보장해야 합니다. 운영체제가 상호배제를 보장하기 위해 잠금을 사용하다 보면 2개 이상의 프로세스가 다른 프로세스의 작업 종료를 기다리며 작업이 더이상 진행되지 않는 교착상태에 빠지게 됩니다.

교착상태와 아사현상은 비슷해보이지만 다른 점이 있습니다. 아사현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스가 작업이 지연되는 문제를 말하고 교착상태는 여러 프로세스가 작업 중 자연적으로 발생하는 문제입니다. 따라서 운영체제는 감시를 하다가 교착상태를 감지하면 강제적으로 이를 해결해야 합니다.

위 그림의 경우 프로세스 P1은 프린터를 할당 받았지만 CD 레코더를 기다리고 있고 프로세스 P2는 CD 레코더를 할당 받았지만 프린터를 기다리고 있습니다. 이러한 무한 대기 상태를 교착상태라고 합니다. 데이터베이스 같은 응용프로그램에서도 일관성을 유지하기 위해 잠금을 사용하다가 교착 상태가 발생할 수 있으며 이러한 교착 상태로 인해 일관성이 깨지고 무결성 또한 깨질 수 있습니다.

위 그림에서 사용된 실선, 점선, 화살표가 자원할당 그래프(resource allocation graph)입니다. 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것입니다. 프로세스는 원으로, 자원은 사각형으로 표현하며 자원을 사용하고 있는 경우에는 자원으로부터 프로세스로 향하는 화살표 실선으로 표시하고 프로세스가 자원을 기다리는 경우는 프로세스로부터 자원으로 화살표 점선으로 표시합니다.