[운영체제] 동기화 문제의 해결책

hyyyynjn·2021년 10월 6일
0

면접대비

목록 보기
18/31
post-thumbnail

동기화의 기본적인 해결방법

  1. 임계 영역으로의 진입 가능성을 확인하고 진입을 원자적으로 처리해야 한다.
  2. 경쟁 조건이 발생하지 않도록 해야하고 진입하게 되면 임계 영역으로 잠궈야 한다.(Lock)

✅동기화를 위한 하드웨어적 해결방법

Lock (락)

하드웨어 기반 해결책으로써,
동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 에 진입하는 프로세스는 Lock 을 획득하고
Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다

프로그램의 흐름을 잠근다는 의미의 락 (Lock)은 동기화의 가장 근본적인 수단이다.
Lock을 위한 공유변수를 변경하는 과정에서 CPU Interrupt가 발생하게 되면 Lock을 통해 동기화 문제를 해결할 수 없다.
그렇기 때문에 운영체제는 진입 가능성 확인 기능과 진입 기능을 쪼갤 수 없는 원자적 방식으로 Lock을 위한 공유변수를 제공한다.

TestAndSet() 명령어

한 워드의 내용을 확인하고 수정하는 연산을 원자적으로 처리하는 명령어

// TestAndSet 명령어의 의사코드
// 이 과정이 원자적으로 수행된다.
boolean TestAndSet(boolean *target) {
  boolean rv = *target;
  *target = TRUE; // target 값을 TRUE로 설정
  return rv; // old target 값을 반환
}

TestAndSet() 명령어는 위와 같은 응용프로그램 언어로 동작하는게 아니라 CPU의 하드웨어로서 동작한다. 하나의 의사코드로 받아들면 된다.

TestAndSet() 명령어를 이용한 상호 배제

// lock이란 이름의 공유변수의 초기값은 FALSE이다.
do {
  while (TestAndSet(&lock))
    ; // do nothing
    
  // critical section
    
  lock = FALSE; // lock을 풀어준다.
  
  // remainder section
  
} while (TRUE);

TestAndSet(&lock) 은 lock 변수의 값을 TRUE로 새롭게 설정한 뒤, old lock 변수 값을 반환한다.

  • lock == FALSE인 경우 TestAndSet(&lock) 명령어는 lock을 TRUE로 설정하고 old lock 변수 값인 FALSE를 반환한다.
    그 후 while (TestAndSet(&lock)); 문을 빠져나와 critical section으로 진입하게 된다.
  • lock == TRUE인 경우 TestAndSet(&lock) 명령어는 lock을 TRUE로 설정하고 old lock 변수 값인 TRUE를 반환한다.
    하지만 while (TestAndSet(&lock)); 문을 빠져나가지 못한다.

위 코드는 TestAndSet() 명령어를 이용하여 상호 배제 조건만 만족시킨 경우이다. 임계 영역 문제 해결을 위한 한정된 대기 조건을 만족하지 않는다.

만약 하나의 프로세스가 lock을 걸어 임계 영역의 코드를 수행하고 lock = FALSE;으로 lock을 풀었다고 가정해보자.

정상적인 경우라면 다른 프로세스가 lock을 걸어 임계 영역에 접근하겠지만, lock을 푼 프로세스가 다른 프로세스보다 빠르게 스케쥴링 되면 다시 while (TestAndSet(&lock)); 문을 실행하여 lock을 걸게된다.

위와 같은 경우가 반복되면 다른 프로세스가 무한정 대기하는 문제가 발생한다.

TestAndSet() 명령어를 이용한 임계 영역 문제 해결

한정된 대기 , 상호 배제 조건을 만족시키는 코드이다.

// 공유 데이터
boolean waiting[n];
boolean lock;

do {
   waiting[i] = TRUE;
   key = TRUE;
   while(waiting[i] && key)
     key = TestAndSet(&lock);
    waiting[i] = FALSE;
    
    // critical section
    
    j = (i+1) % n;
    while ((j != i) && !waiting[j])
      j = (j+1) % n;
    if (j==i)
      lock = FALSE;
    else
      waiting[j] = FALSE;
      
    // remainder section
} while (TRUE);

lock 변수와 함께 특정 프로세스가 임계 영역 접근을 기다리는지에 대한 여부를 나타내는 waiting 변수를 추가적으로 활용한 코드이다.

while(waiting[i] && key)
 key = TestAndSet(&lock);

while(waiting[i] && key) 문에서 key = TestAndSet(&lock); 으로 lock을 풀지 못하는 경우에도 waiting[i] 값이 FALSE이면 임계 영역에 접근할 수 있다.

j = (i+1) % n;
while ((j != i) && !waiting[j])
  j = (j+1) % n;
if (j==i)
  lock = FALSE;
else
  waiting[j] = FALSE;

먼저 기다리고 있는 j번 프로세스가 있다면, lock을 획득하지 못하더라도 waiting[j] = FALSE 으로 while 조건을 빠져나가 임계 영역에 접근할 수 있도록 해준다.

Swap() 명령어

두 워드의 내용을 서로 교환하는 연산을 원자적으로 처리하는 명령어

// Swap() 명령어의 의사코드
// b 변수에 a 변수 값을 할당
void Swap(boolean *a, boolean *b) {
  boolean temp = *a;
  *a = *b;
  *b = temp;
}

Swap() 명령어를 이용한 상호 배제

// lock이란 이름의 공유변수의 초기값은 FALSE이다.
// 각 프로세스는 지역 변수 key를 가진다.
do {
  key = TRUE;
  while (key == TRUE)
    Swap(&lock, &key); 
    
  // critical section
    
  lock = FALSE; // lock을 풀어준다.
  
  // remainder section
  
} while (TRUE);

Swap(&lock, &key) 은 lock변수의 값을 key변수에 할당한다.

  • lock == FALSE인 경우 Swap(&lock, &key) 명령어는 key에 lock 변수값인 FALSE를 할당한다.
    그 후 while (key == TRUE) 문을 빠져나와 critical section으로 진입하게 된다.
  • lock == TRUE인 경우 Swap(&lock, &key) 명령어는 key에 lock 변수값인 TRUE를 할당한다.
    하지만 while (key == TRUE) 문을 빠져나가지 못한채 Swap(&lock, &key) 명령어을 반복 실행한다.

Lock의 한계

다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

또한 TestAndSet(), Swap() 는 CPU 명령어이므로 임계 영역 문제를 해결하기 위해 어셈블리 수준의 코딩이 필요하다.

✅동기화를 위한 소프트웨어적 해결방법

Semaphore (세마포어)

운영체제는 소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구로써 Semaphore을 제공하고 있다.

Semaphore의 구성

  1. Semaphore 변수 S
  2. 검사 연산 wait(S) : lock 획득
wait(S) {
  while (S <= 0)
    ;
  S--;
}
  1. 증가 연산 signal(S) : lock 해제
signal(S) {
  S++;
}

두 개의 프로세스가 같은 Semaphore 변수 S를 공유할 때, wait(S) 함수로 S 변수값을 통해 lock이 걸려 있는지를 확인하고 signal(S) 함수로 S 변수값을 변경하여 lock을 해제한다.

Semaphore를 이용한 상호 배제 조건

// Semaphore 변수 mutex의 초기 값은 1이다.

do {
  wait(mutex);
  
  // critical section
  
  signal(mutex);
  
  // remainder section
} while (TRUE);
  • wait(mutex); 함수로 lock이 걸려있는지 확인한다. lock이 걸려있지 않다면 (mutex > 0) mutex--; 을 통해 lock을 걸어준다.
  • signal(mutex); 함수로 mutex++; 을 통해 lock을 풀어준다.

mutex 의 초기값이 1이므로 오직 하나의 프로세스만 임계 영역에 접근할 수 있다.

// 프로세스 P1
S1;
signal(synch);

// 프로세스 P2
wait(synch);
S2;

Semaphore 변수 synch의 초기값을 0으로 설정하였을 때, 두 프로세스간의 실행 순서를 지정할 수 있다. (S1 ⇨ S2)

위 코드는 상호 배제 조건만 만족시킨 경우이다. 임계 영역 문제 해결을 위한 한정된 대기 조건을 만족하지 않는다.

Semaphore의 한계

Busy Waiting (바쁜 대기)
Spin lock이라고 불리는 Semaphore 초기 버전에서
Critical Section 에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU 시간을 낭비했었다
이를 Busy Waiting이라고 부르며 특수한 상황이 아니면 비효율적이다.

일반적으로는 Semaphore에서 Critical Section에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤,
Critical Section에 자리가 날 때 다시 깨우는 방식을 사용한다.
이 경우 Busy waiting으로 인한 시간낭비 문제가 해결된다.

✅동기화로 인해 발생하는 문제

동기화는 서로 병행적으로 실행되는 프로세스들의 실행 시점을 인위적으로 일치시킬 때, Lock을 활용하여 한 쪽 프로세스의 실행을 막는다.

동기화 기법을 적용할 때, 문제가 발생할 수 있다.

1. Deadlock (교착상태)

두 개 이상의 프로세스가 어떤 사건을 기다리고 있는데,
같이 기다리는 프로세스 중 하나만이 그 사건을 발생시킬 수 있는 상황이다.


위와 같이 두 개의 lock 변수 S, Q를 체크하여 임계 영역에 접근할 수 있는 상황이 있다.

프로세스 P1은 S ⇨ Q 순서로 체크하고
프로세스 P2는 Q ⇨ S 순서로 체크하여 lock을 획득하려고 한다.

프로세스 P1이 S 변수에 대해 lock을 걸고 Q 변수에 대해 lock을 걸려는 찰나에
프로세스가 P2가 Q 변수에 대해 lock을 걸었다고 가정해보자.

프로세스 P1의 입장에서 Q 변수에 대해 lock을 걸고 싶지만 이미 프로세스 P2가 건 상태이므로 대기해야한다.
Q 변수에 대한 lock이 풀리기 위해선 프로세스 P2가 signal(Q)를 실행해야한다.
하지만 프로세스 P2는 프로세스 P1이 S 변수에 대해 걸어둔 lock으로 인해 signal(Q)를 실행할 수 없다.
그 반대의 경우도 마찬가지이다.

이러한 상황을 프로세스 P1, P2 가 교착상태에 빠져있다라고 한다.

2. Starvation (기아) - Infinite Blocking (무한 대기)

프로세스가 Sempahore Queue에서 무한히 대기하는 상황이다.

상호 배제 조건만 만족시킨 경우 발생할 수 있는 문제이다.

3. Priority Inversion (우선순위 역전)

공유 자원에 대한 허가를 기다리는 동안 낮은 우선순위의 프로세스와 스케쥴링 순서가 뒤바뀌는 상황이다.

우선순위 방식의 스케쥴링과 lock에 대한 개념을 같이 이해해야한다.

위 그림은 스케쥴링된 프로세스 P1,P2,P3가 실행되는 상황을 나타낸 것이다. 우선순위는 P2 > P3 > P1 이다.

프로세스 P1과 P2는 Semaphore 변수 S를 공유하고 있다.

프로세스 P1이 Semaphore 변수 S를 통해 lock을 걸었다. 그 이후 프로세스 P2가 도착하였다.

일반적인 경우라면 우선순위가 높은 P2가 실행되지만, P2는 S 변수를 통해 lock을 걸어야 하기 때문에 프로세스 P1이 끝나 S 변수에 대한 lock을 풀 때까지 blocked된다.

프로세스 P3는 P2보다 우선순위가 낮기 때문에 ready 상태에서 waiting한다.

위와 같은 경우는 크게 문제되지 않는다.

P1이 S변수에 lock을 걸고 임계 영역을 실행하고 있다.

그 중간에 P2가 도착하였지만 S변수에 대한 lock이 풀릴때까지 blocked 된다.

이후에 P3가 도착했다. 우선순위가 P2보다 낮지만 S변수에 대한 lock을 얻지 않아도 되므로 P3가 실행된다.
P2는 P1이 S변수를 통해 lock을 풀 때까지 대기해야하는데,
P3로 인해 대기시간이 길어진다.
⇨ P3가 우선순위가 더 높은 것처럼 보인다 (우선순위 역전)

우선순위 역전 문제 해결방법

우선순위 상속 프로토콜 (Priority Inheritance Protocol)
상위 우선순위 프로세스를 막고 있는 동안 우선순위를 상속한다.

P2는 P1보다 우선순위가 높지만 S 변수에 대한 lock을 획득하기 위해 blocked되었다.

이 때, 일시적으로 P1의 우선순위를 P2와 동일하게 설정하여 P3가 도착하더라도 P1이 preempted되지 않고 P3가 blocked된다.

profile
hyyyynjn
이전 포스트

[네트워크] HTTP 메서드, GET과 POST의 차이점

다음 포스트

[데이터베이스] SQL vs NoSQL

0개의 댓글