공유 자원과 임계구역

한정된 자원을 가지고 프로세스가 공동으로 작업할 때 발생할 수 있는 문제가 있다.

1. 공유자원의 접근

공유 자원(shared resource)는 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다. 공유 자원은 공동으로 이용되기 때문에 누가 언제 어떻게 데이터를 읽거나 쓰거나에 따라 그 결과가 달라질 수 있다. 이 때문에 원치 않은 문제가 발생하기도 한다.

1.1 경쟁 조건(race condition)

경쟁 조건(race condition)은 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 말하며, 공유 자원 접근 순서에 따라 실행 결과가 달라지는 상황을 말한다. 즉, 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말하는 것이다. (동시성 문제라고도 한다.)

1.2 임계구역(Critical Section)

공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 코드 영역을 임계구역(critical section)이라고 한다. 즉, 임계 구역 안에서 race condition이 발생하는 것이다.

1.3 생산자-소비자 문제

critical section에 관련된 전통적은 문제로 생성자-소비자 문제(producer-consumer problem)이 있다. 생산자-소비자 문제에서 생선자 프로세스와 소비자 프로세스는 서로 독립적으로 작업을 한다.

생산자는 말 그대로 계속 물건을 생산해서 버퍼에 넣고, 소비자는 계속해서 버퍼에서 물건을 가져온다.

가운데에는 buf라는 원형 큐 자료구조가 존재하고, producer는 값을 넣어준다. sum은 큐의 원소 수에 해당한다. consumer은 큐의 원소를 빼낸다. producer는 원소를 맨 뒤부터 차근차근 넣지만 consumer는 맨 앞부터 차근차근 빼낸다.

겉으로보기에는 문제없어보이지만, producer, consumer 둘이 같이 동시에 실행되면 문제가 발생한다. 생산자와 소비자가 전역 변수 sum에 접근하는 타이밍을 서로 맞추지 않기 때문이다.

즉, sum이 바로 critical section이며 race codition이 발생하는 것이다. 다음의 경우를 확인해보자

0. 현재 sum은 3이다.
1. producer가 buf에 물건을 하나 추가한다. 그러나 sum을 아직 안바꾸었다. 현재 sum은 3이다.
2. consumber가 buf에서 물건을 하나 소비한다. sum을 2로 바꾸어야하는데 아직 바꾸지 않았다. 현재 sum은 3이다.
3. 이 상태에서 sum = sum + 1과 sum = sum - 1```이 동시에 실행되는 문제가 생긴다.
4. 만약 sum = sum + 1이 먼저 실행되면 4가 되고, sum = sum - 1을 하면 sum은 2가 된다. 왜냐하면 2번에서의 sum은 4가 아니라 3이기 때문이다.
5. 만약 sum = sum - 1이 먼저 실행되면 2가 되고, sum = sum + 1이 실행되면 4가 된다. 1번 에서의 sum은 3이기 때문이다.

이렇게 이 때의 실행 순서에 따라 값이 변하는 현상이 발생한다.

1.4 임계구역 해결 조건

critical section 문제를 해결할 수 있는 방법은 다음 3가지 조건을 만족해야 한다.

1. 상호 배제(mutual exclusion)
   한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.

2. 한정 대기(bounded waiting)
   상호 배제 때문에 기다리게 되는 프로세스가 무한 대기하지 않아야 한다. 즉, 틍정 프로세스가 임계구역에 진입하지 못하면 안된다.

3. 진행의 융통성(progress flexibility, progress)
   임계구역에 프로세스가 없다면 어떠한 프로세스라도 들어가서 자원을 활용할 수 있다. 즉, 두 프로세스가 자원을 번갈아 쓴다고 가정할 때 한 쪽에서 자원을 안쓰고 있다고해서 다른 한 쪽 프로세스가 자원을 쓰고싶어도 자신의 turn이 아니라고 기다리는 것은 효율적이지 못하다는 것이다.

2. 임계구역 해결 방법

critical section 문제를 해결하는 단순한 방법은 Lock을 사용하는 것이다. 즉, 한 프로세스가 critical section에 들어간다면 lock을 걸어놓아 다른 프로세스가 들어오지 못하게 하는 것이다.

그리고 프로세스가 critical section에서 빠져나오게 되면 lock을 해제하고 동시에 동기화 신호를 보내는 것이다. 동기화 신호는 다음 프로세스에게 critical section을 사용해도 좋다는 신호를 주는 것이다.

임계구역 문제를 해결하기 위한 3가지 조건인 상호 배제, 한정 대기, 진행의 융통성(progress)을 모두 만족하는 lock, unlock , 동기화 구현 방법을 알아보도록 하자

2.1 예제 코드

#include <stdio.h>
typedef enum { false , true} boolean;
extern boolean lock = false;
extern int balance;

int main(){
    while(lock == true);
    lock = true;
    balance = balance + 10;
    lock = false;
}

c언어에서는 boolean 변수가 없기 때문에 다음과 같이 typedef로 정의했다.

ciritical section에 문제가 되는 들어갈 변수는 balance이고, 잠금은 lock으로 걸어놓는다. false이면 프로세스가 들어가 balance를 쓸 수 있고, true이면 기다리도록 한다.

2.2 상호 배제 문제(mutual exclusion)

위의 예제는 IPC 방법으로 shared memory를 사용하는 것과 같다.

공유 변수 boolean lock은 shared memory에 있는 변수인 것이다.

프로세스 p1과 p2는 임계구역에 진입하기 전에 코드를 통해 임계구역에 잠금이 걸려 있는 지 확인한다( lock == true)

만약 lock이 true라서 잠겨져 있다면 다른 프로세스가 임계구역에서 작업을 하고 있다는 뜻이므로 잠금이 해제될 때까지 무한 루프를 통면서 기다리게 된다.

임계구역에 있는 프로세스가 작업을 마치고 잠금을 해제하면 lock = false로 만들어주기 때문에 기다리고 있던 프로세스는 무한루프에 빠져나와 작업을 한다.

즉, lock = false는 임계구역을 사용해도 좋다고 다른 프로세스에 보내는 동기화 신호이다. 잠금이 풀려서 새로 임계구역에 진입하는 프로세스는 다른 프로세스가 진입하지 못하도록 잠금을 걸고 (lock = true) 작업을 하며, 작업을 마치면 다른 프로세스가 사용할 수 있도록 잠금을 해제한다(lock = false)

그런데 이는 문제없이 작동할 것 같지만 일부 문제가 존재한다. 다음의 상황을 살펴보자

위 그림에서 임계구역에 진입한 프로세스가 없다고 하자, 이런 상황에서 아래 순서대로 실행된다고 하면

1. 프로세스 P1은 while(lock == true); 문을 실행한다. 임계구역에 프로세스가 없기 떄문에 무한 루프를 빠져나온다. 그런데 이어서 다음 문장을 실행하려는 순간 자신에게 주어진 CPU 시간을 다해(timeout) ready 상태로 옮겨진다. context switching이 발생하고 프로세스 p2가 running 상태로 바뀐다.

2. 프로세스 p2는 while(lock == true);문을 실행한다 아직 프로세스 p1이 잠금을 걸지 않았기 때문에 lock은 여전히 false이며 프로세스 p2는 임계구역에 진입할 수 있다.

3. 프로세스 p1은 lock= true;문을 실행하여 임계구역에 잠금을 걸고 진입한다.

4. 프로세스 p2는 lock = true;문을 실행하여 임계구역에 잠금을 걸고 진입한다. 결국 둘다 임계구역 안에 진입하게 된다.

프로세스 p1은 while(lock == true);문을 실행하고 나서 곧바로 lock = true문을 실행해야 다른 프로세스가 임계구역에 들어오는 것을 막을 수 있다. 그러나 프로세스 p1이 lock = true;문을 실행하기 전에 프로세스 p2가 while(lock == true);문을 실행하면 둘 다 임계구역에 진입하게 된다. 결국 위 그림과 같은 상황은 상호 배제 조건(Mutual Exclusion)을 보장하지 못한다.

또 다른 문제는 잠금이 해제되기 전까지 busy waiting이 발생한다는 것이다. 바로 while(lock == true);문 부분인데, 작업을 할 필요가 없는 시간에도 계속 무한 루프를 돌면서 시스템 자원을 낭비한다.

2.2 한정 대기 문제( bounded waiting )

그래서 mutual exclusion 문제를 해결하기 위해서 lock을 하나만 두지 말고 두 개를 두기로 하자.

이전에는 lock을 두 프로세스가 공유하였기 때문에 문제였던 것이었다. 그러면 각 프로세스가 자신들만의 lock을 가지고 있도록 하는 것이다.

이전에는 화장실에 들어가고나서 잠그는 것을 까먹고 있다가, 다른 사람도 화장실에 들어가고나서 둘이서 똑같이 문을 잠그고 같은 변기?를 사용하는 더러운 상황이 나온 것이다. 그래서 이번에는 두 사용자가 각자의 키를 갖도록 하고, 화장실은 두 키 모두로 문을 걸어잠글 수 있다.

먼저 내가 문을 잠가놓고 들어가버리면, 잠가놓는 걸 까먹는 일이 발생하지 않기 때문에 상호 배제 문제가 발생하지 않는다.

프로세스 P1은 임계구역에 진입하기 전에 먼저 잠금을 설정하고(lock1=true;) 프로세스 P2가 잠금을 설정했는 지 확인한다(while(lock2 == true);) 만약 잠금을 설정하지 않았다면 임계구역에 진입하여 작업을 마친 후 잠금을 해제한다(lock1 = false;) 프로세스 P2도 같은 방식으로 임계구역에 진입한다.

위 코드는 일단 잠금을 하고 다른 프로세스가 잠겼는 지 확인하므로 두 프로세스의 상호 배제가 보장된다.

그런데, 두 프로세스가 모두 임계구역에 진입하지 못하는 무한 대기 현상이 일어난다. 두 프로세스에 명시된 순서대로 실행된다고 가정해보자

1. 프로세스 P1은 lock1=true; 문을 실행한 후 주어진 CPU 시간을 다 써버려 ready 상태로 돌아간다. context switching이 발생하고 프로세스 P2가 running 상태로 바뀐다.

2. 프로세스 P2도 lock2=true;문을 실행한 후 자신의 CPU 시간을 다 써버려 ready 상태로 돌아간다. context switching이 발생하고 프로세스 P1이 running 상태로 바뀐다.

3. 프로세스 P2가 lock2=true;문을 실행했기 때문에 프로세스 P1은 while(lock2 == true); 문에서 무한 루프에 빠진다.

4. 프로세스 P1이 lock1=true;문을 실행했기 때문에 프로세스 P2도 whilc(lock1 == true); 문에서 무한 루프에 빠진다.

결국 P1, P2 둘 다 while 문을 빠져나오지 못하고 무한 루프에 빠져서 critical section에 진입하지 못한다. 이는 bounded waiting 조건을 보장하지 못하고 데드락(교착상태, deadlock)에 빠진다.

데드락은 프로세스가 살아 있으나 작업이 진행되지 못하는 상태를 말한다.

또한, 위의 코드는 확장성의 문제또한 있다. 만약 process p3가 추가된다면 또 lock3를 추가해주어야 하고 점점 더 코드가 복잡해진다.

2.3 진행의 융통성 문제(Progress)

critical section 문제를 해결하기 위해 lock 값이 1이면 P1이 critical section에 들어갈 수 있고, lock이 2이면 P2가 critical section에 사용한다.

주의: 그림이 잘못되었다. lock을 서로 반대값으로 해주어야한다.

공유 변수 lock의 값을 통해 다른 프로세스가 critical section에 있는 지 확인하고, 없으면 진입한다. 프로세스 P1은 while(lock == 2); 문을 실행하고 프로세스 P2가 잠금을 걸었으면 기다린다. lock = 1이면 프로세스 P1이 critical section에 진입하고, critical section에 빠져나올 때 lock을 2로 바꾼다.

잠금을 확인하는 문장은 하나이므로 mutual exclusion과 bounded waiting을 보장한다. 그러나 서로 번갈아가면서 실행된다는 것이 문제이다. 한 프로세스가 두 번 연달아 임계구역에 진입하고 싶어도 그럴 수 없다.

P1는 P2가 critical section에 진입하고 나서야 critical section에 진입할 수 있다. 이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(lockstep synchronization)라고 한다. 따라서 위 예시는 progress를 보장하지 못한다.

2.4 하드웨어적인 해결 방법

위와 같은 소프트웨어적 해결방법 뿐만 아니라 하드웨어적 해결방법 또한 존재한다.

위의 코드는 이전에 살펴본 코드로 lock=true가 작동하기 직전에 timeout이 걸려 ready 상태로 돌아가면 mutual exclusion에 위배되는 문제가 발생한다.

이를 해결하기위해서는 while과 lock 사이에서 timeout이 발생하지 않도록 해야한다. 이를 (원자성)atomicity를 가져야 한다고 한다. 원자성을 가지는 작업은 실행되어 진행되다가 종료하지 않고 중간에서 멈추는 경우는 있을 수 없다.

이를 해결하기위해 하드웨어의 도움을 받을 수 있는데, 하드웨어적으로 두 명령어를 동시에 실행하도록하면 critical section 문제를 쉽게 해결할 수 있다.

testandset(검사와 지정)이라는 코드로 하드웨어 지원을 받아 while(lock == true);문과 lock=true;문을 한꺼번에 실행한다. 검사와 지정 코드를 이용하면 명령어 실행 중간에 타임아웃이 걸려 critical section이 보호하지 못하는 문제가 발생하지 않는다. 즉, 원자성(atomicity)를 보장한다는 것이다.

그러나 이는 방법은 편리하지만, busy waiting를 사용하여 검사하기 때문에 자원 낭비가 있다. 일부 하드웨어에서는 busy waiting 없이 잠금을 동기화해주기도 하지만, 이는 성능 좋은 하드웨어에서나 가능한 일이다.

위의 4가지 해결 방법은 아직 임계구역 해결 조건을 완벽하게 충족하지 못했다. 다음의 피터슨 알고리즘과 데커 알고리즘은 이러한 문제를 해결하였으나 구조가 복잡하여 현재 잘 사용되지 않는다.