[운영체제] 프로세스 동기화

<프로세스 동기화 내용 목차>

1. Critical-Section Problem (임계 영역 문제)

2. Hardware Synchronization (하드웨어 동기화)

3. Semaphore (세마포어 - 소프트웨어 동기화)

4. Classic Problems of Synchronization (동기화의 고전문제들)

5. Monitors (모니터)

Q. 임계 영역이란 무엇인가? 임계 영역 문제란 무엇인가?

 임계 영역은 공유 데이터에 접근하는 코드이다. 공유 데이터에 동시 접근하게 되면 데이터의 무결성이 손상될 수 있다. 이러한 문제가 바로 임계 영역 문제이다. 임계 영역 문제은 생산자-소비자 문제라고도 한다. 생산자, 소비자 역할을 하는 프로세스 2개가 동시에 공유 자원에 접근함으로써 기대했던 값과는 다른 결과가 나오게 된다. (그리고 이러한 상황을 경쟁조건이라고도 한다.)

Q. 경쟁 조건이란 무엇인가?

 경쟁 조건(race condition)이란 임계영역의 부적절한 처리로 예상치 못한 결과를 발생시킬 수 있는 상황을 의미한다. 경쟁 조건 문제를 해소하려면 반드시 한 순간에 하나의 프로세스만 임계영역을 실행할 수 있도록 보장해야 한다.

Q. 임계 영역 문제의 해결책이 되기 위한 조건은 무엇이 있나? (특정 해결책(solution)이 임계 영역 문제를 해결한다고 말하려면 무슨 조건을 만족해야 하나?)

 임계 영역 문제의 해결책이 되려면 3가지 조건을 만족해야 한다. 상호 배제(Mutual Exclusion), 진행(Progress), 한정 대기(Bounded Waiting)이다.

1 .프로세스 Pi가 임계영역에 존재하는 경우, 다른 프로세스는 임계영역을 실행하지 못하도록 하면 상호 배제 조건을 만족한다고 할 수 있다. 

2. 임계 영역 안에서 실행하고 있는 프로세스가 없는 경우, 임계 영역을 실행하고자 하는 프로세스는 반드시 임계 영역을 실행할 수 있어야 한다. 이를 만족하면 진행 조건을 만족한다고 할 수 있다. 

3. 임계 영역을 요청한 프로세스는 무한히 대기하면 안된다. 즉, 제한된 대기 시간을 가져야 한다. 이를 만족하면 한정 대기 조건을 만족한다고 할 수 있다.

 3가지 조건을 모두 만족해야만 임계 영역 문제(critical section problem)을 해결할 수 있는 해결책(solution)이라고 할 수 있다.

Q. 임계 영역 문제 해결책에는 어떠한 것이 있는가?

 임계 영역 문제 해결책은 임계영역의 실행여부를 알 수 있는 메커니즘이 제공되는지가 관건이다. 임계 영역 문제 해결책으로는 크게 하드웨어적 해결책과 소프트웨어적 해결책이 있다. 하드웨어적 해결책으로는 TestAndSet, Swap 등이 있고, 소프트웨어적 해결책으로는 세마포어, 모니터, 조건 변수 등이 있다.

Q. TestAndSet의 작동방식을 설명하라.

boolean * TestAndSet (boolean * target) 

{

  boolean * rv = * target;

  *target = TRUE;

  return rv;

}

인자로 받은 값을 그대로 반환한다. 다만, 인자의 값자체를 TRUE로 변경한다.

while(true) 

{

  while(TestAndSet(&lock))

    ; // do nothing

  // critical section

  lock = FALSE;

  // remainder section

}

제일 처음에는 lock은 FALSE값으로 초기화되어 있다. 따라서, 처음으로 실행한 프로세스는 첫 while문을 통과한다. 그리고, TestAndSet에 의해서 lock은 TRUE가 되었으므로, 다른 프로세스가 임계 영역을 실행하려고 해도, while문에서 걸려서 실행할 수 없다. 상호 배제 조건을 만족하는 셈이다. 그리고 임계 영역을 다 끝낸 프로세스는 lock값을 다시 FALSE로 되돌려서 다른 프로세스도 임계영역을 실행할 수 있도록 한다. 따라서, 진행 조건도 만족하는 셈이다.

다만, 한정 대기 조건을 만족한다고 볼 수는 없다.

Q. Swap 의 작동방식을 설명하라.

void Swap (boolean *a, boolean *b)

{

  boolean temp = *a;

  *a = *b;

  *b = temp;

}

인자로 받은 a,b의 값을 서로 바꾼다.

while(true)

{

  key = TRUE;

  while ( key == TRUE)

    Swap(&lock, &key);

  // critical section

  lock = FALSE;

  // remainder section

}

제일 처음에는 lock값이 FALSE로 초기화되어있다. 따라서, lock과 key를 swap하면 key 값이 FALSE가 되어 바로 while문을 통과한다. 하지만, lock값이 TRUE가 되었으므로 다른 프로세스는 while문을 빠져나가지 못한다. 즉, 상호 배제 조건을 만족하는 셈이다. 그리고 임계 영역을 다 진행한 프로세스는 lock값을 FALSE로 되돌리므로 다른 프로세스도 임계 영역을 실행할 수 있또록 한다. 따라서, 진행 조건도 만족하는 셈이다.

다만, 한정 대기 조건을 만족한다고 볼 수는 없다.

Q. 한정 대기 조건을 만족하도록 TestAndSet 을 사용하여 임계영역을 구현하라.

우선, boolean waiting[n]; boolean lock;을 공유 변수(전역 변수)로 선언한다. waiting 배열을 이용하여 한정 대기 조건을 만족하도록 구현할 것이다.

do

{

  waiting[i] = TRUE;

  key = TRUE;

  while(key && waiting[i])

    key = TestAndSet(&lock);

  waiting[i] = FALSE;

  // critical section

  j = (i+1)%n;

  while((j!=i) && !waiting[j]) // scanning in 'waiting'

    j = (j+1)%n;

  if(j==i)             // if no process is waiting

    lock = FALSE; // lock release

  else                          // if a waiting process exists

    waiting[j] = FALSE; // the process can enter the critical section in next order.

} while (TRUE);

처음에 lock값은 FALSE로 초기화되어 있다. 처음으로 임계영역에 들어가는 프로세스에서는 TestAndSet에 의해서 key가 FALSE가 된다. 따라서 바로 while문을 통과하여 임계 영역을 진행한다. 이때, lock은 TestAndSet에 의해서 TRUE가 되었으므로 key값은 계속해서 TRUE이고, 다른 프로세스는 while문을 통과하지 못한다. 따라서, 상호 배제 조건을 만족한다고 할 수 있다. 

그 다음, 임계 영역을 모두 진행한 프로세스는 waiting 배열을 i+1, i+2, ... , n-1, 0, ... i-1 순서대로 조사한다. 조사한 순서에서 가장 처음으로 waiting값이 TRUE인 프로세스를 찾으면, 그 프로세스가 다음 차례로 임계 영역을 실행하는 프로세스가 된다. 그리고 만약 모두 조사했음에도 waiting값이 TRUE인 프로세스가 없다면 완전히 lock을 FALSE로 돌려버린다. (즉, lock을 놓아버린다.) 즉, 임계영역에 들어가기를 원하는 모든 프로세스들이 최대한 n-1 번 안에는 임계영역에 들어갈 수 있게 된다. 한정 대기 조건을 만족하게 되었다. 또한, 기다리는 프로세스가 없는 경우는 당연히 lock이 FALSE값이 되므로 바로 프로세스가 임계영역에 들어갈 수 있다. 진행 조건도 만족한다.

따라서, 위 구현은 3가지 조건을 모두 만족하므로 임계 영역을 완벽하게 해결한다.

Q. 세마포어란 무엇인가? 어떻게 구현하나?

 세마포어는 소프트웨어적 프로세스 동기화 기법 중 하나다. 세마포어 변수값에는 wait, signal 라고 하는 원자적 명령에 의해서만 접근이 가능하다. (원자적 명령이라는 말은 그 명령 혹은 함수가 진행하는 동안 다른 방해가 들어오지 않음을 의미한다.)

wait (S) {

  while S<=0

    ; // no-op

  S --;

}

signal (S) {

  S ++;

}

이러한 구현을 한 세마포어(무한루프로 wait을 구현한 세마포어)를 spin lock(스핀 락)이라고도 한다. 스핀 락은 불필요한 CPU 싸이클을 낭비하므로 좋지 못한 구현이다. (물론 스핀 락도 유일한 장점을 가진다. 바로, 컨텍스트 스위치가 전혀 없다는 것이다.) 따라서, 대기 큐를 이용한 세마포어 wait, signal 구현도 가능하다. 다만, 그러한 구현은 새로운 문제인 데드락을 발생시킨다.

wait (S) {

  S --;

  if ( S < 0 )

  {

    add this process to Waiting Queue;

    block;

  }

}

signal (S) {

  S ++;

  if( S >= 0 )

  {

    remove the process 'P' from Waiting Queue;

    wakeup (P);

  }

}

Q. 데드락, 교착 상태란 무엇인가?

 교착 상태를 쉽게 표현하면 '모든 것이 모든 것을 막는다'라는 상황이다. 세마포어를 waiting queue 를 이용해서 구현하면 2개 이상의 프로세스가 영원히 기다리는 상황이 발생할 수도 있다. wait 함수를 호출해 기다리는 상태에서 그에 상응하는 signal 액션이 영원히 발생하지 않는 상황이 되면, 그러한 상황에 있는 프로세스을 교착상태에 빠졌다고 말한다. 예를 들어 다음과 같은 프로세스가 2개 있으면 P0, P1 이 교착상태에 빠지게 된다. 세마포어 Q,S가 있다고 하고, 이들은 초기값을 1로 한다.

P0                  P1

wait(S);           wait(Q);

wait(Q);          wait(S);

...                   ...

signal(S);        signal(Q);

signal(Q);       signal(S);

만약, P0, P1 이 동시에 첫 줄을 실행하면 S와 Q 모두 세마포어 변수값이 0이 된다. 그 후 두번째 줄을 실행하면, S와 Q 모두 값이 0이므로 block이 된다. P0의 wait(Q)를 깨우려면 P1의 signal(Q);가 작동해야 하는데, wait(S)로 막혀 있으므로 절대 도달하지 않는다. 또한, P1의 wait(S)를 깨우려면 P0의 signal(S)가 작동해야 하는데, wait(Q)로 막혀 있으므로 절대 도달하지 않는다. 이러한 상황에 있을 때, P0, P1은 교착상태에 빠졌다고 말한다.

Q. 한정된 버퍼 문제란 무엇인가? (Bounded-Buffer Problem)

Q. 저자-독자 문제란 무엇인가? (Readers-Writers Problem)

Q. 식사하는 철학자 문제란 무엇인가? (Dining-Philosophers Problem)

Q. 모니터가 보장하지 못하는 경우에는 무엇이 있나?

총 4가지 경우가 있다. 

1. 자원에 대한 접근 권한을 얻지 않았음에도 자원에 대해 접근을 할 수도 있다. 

2. 자원에 접근하는 것에 대한 승인을 받은 후에 절대로 자원을 놓지 않을 수도 있다.

3. 요청하지 않은 자원을 놓을 수도 있다. 

4. 똑같은 자원을 두 번 요청할 수도 있다. (자원을 놓는 일을 하지 않고서도)