[운영체제] 세마포어(Semaphore) & 뮤텍스(Mutex)

[운영체제] 세마포어(Semaphore) & 뮤텍스(Mutex)CS/운영체제2022. 4. 4. 21:23@TTOII

Table of Contents

728x90

✔︎ 임계 영역 (Critical Section)

여러 프로세스가 데이터를 공유하면서 수행될 때 각 프로세스에서 공유 자원에 접근하는 프로그램의 코드 부분을 의미한다.

프로세스 간에 공유자원을 접근하는데 있어 문제가 발생하지 않도록 공유 자원의 독점을 보장해줘야 하는 영역이다.

멀티 프로그래밍 시스템에서 여러 프로세스들이 공유하고 있는 자원을 한 시점에 하나의 프로세스만 접근할 수 있게 하는 영역이다.

✔︎ 임계 영역의 문제점

1. 경쟁 상태의 발생

공유 자원(임계 자원)에 여러 프로세스가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결괏값에 영향을 줄 수 있는 경쟁 상태가 발생할 수 있다.

2. 자원의 독점 문제

임계 영역 내에서는 작업을 반드시 빠른 속도로 수행해야 하며 프로세스 하나가 임계영역 내에 오랫동안 머물러서는 안된다.

P1 프로세스가 임계영역을 사용하고 있을 경우 P2 프로세스는 임계영역을 사용할 수 없기 때문에 최대한 빨리 작업을 한 후 P2에게 양보해줘야 한다.

✔︎ 임계 영역 문제 해결 조건

임계 영역 문제를 해결하기 위해서는 아래의 3가지 조건을 충족해야 한다.

1. Mutual Exclusion (상호 배제)

한 프로세스가 자신의 임계 영역에 있다면 다른 프로세스들은 임계 영역에 진입할 수 없다.

2. Progress (진행)

아무도 임계 영역에 있지 않다면, 진입하고자 하는 프로세스를 진입하게 해줘야 한다.

즉, 임계 영역에 아무도 진입하지 못하면 안되어 다음에 어떤 프로세스가 임계 영역에 진입해야 하는 유한한 시간에 결정되어야 한다.

3. Bounded Waiting (유한 대기)

프로세스가 임계 영역에 진입하기 위해 무한정으로 기다리는 기아 현상(starvation)이 발생해서는 안된다.

✔︎ 세마포어(Semaphore)란

공유된 자원에 여러 프로세스가 동시에 접근하면 문제가 발생할 수 있다.

이 때 공유된 자원의 데이터는 한번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

이를 위해 나온 개념이 '세마 포어'이다.

즉, 세마포어란 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법이다.

세마포어의 구성 요소는 크게 세마포어 변수, P 동작, V 동작이 있다.

S (세마포어의 변수)

정수 값을 가지는 정적 변수이며, 정수 값은 공유 자원에 접근 가능한 프로세스의 개수를 의미한다.

이때 세마포어 값이 0 또는 1의 값만 만들 수 있다면 (한번에 접근 가능한 프로세스가 1개일 경우) 이진 세마포어라고 하며

2 이상의 값도 가질 수 있는 경우 계수 세마포어라고 한다.

P(try를 의미, acquire())

프로세스가 임계 구역에 들어가기 전에 수행되고(try), 세마포어 값을 감소시킨다.

만일 감소 후 값이 음수가 되면 프로세스를 Ready Queue에 추가한 후 함수를 호출한 프로세스는 Lock이 된다.

즉, 세마포어 값이 0보다 크면 프로세스의 접근을 허용하되 1을 감소하고 난 뒤 값이 0이 되는 순간부터 프로세스 접근을 금지한다.

V(increment를 의미, release())

작업이 끝나고 프로세스나 쓰레드가 임계 구역에서 나갈 때는 세마포어 값을 증가(increase)시킨다.

만약 세마포어 값이 음수이면, Ready Queue에 있던 Lock 상태의 프로세스를 하나 꺼내서 임계 구역을 수행할 수 있게 한다.

이때 변수를 수정하는 두 연산(P, V)은 모두 원자성을 만족해야 한다. 한 프로세스나 쓰레드에서 S 값을 변경하는 동안 다른 프로세스나 쓰레드가 동시에 접근해서 변경할 수 없다.

class Semaphore {
  int value;      // number of permits
  Semaphore(int value) {
    // ...
  }
  void acquire() {
    value--;
    if (value < 0) {
      // add this process/thread to list
      // block
    }
  }
  void release() {
    value++;
    if (value <= 0) {
      // remove a process P from list
      // wakeup P
    }
  }
}

✔︎ 세마 포어 구현 방법

procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다.

P와 V를 사용해 임계 구역에 대한 상호배제 구현이 가능하게 되었다.

✔︎ 세마 포어 예시

최초 S값은 1이고 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자

1. 먼저 도착한 A가 P(S)를 실행해 S를 0으로 만들고 임계 구역에 들어간다.

2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태이다.

3. A가 임계 구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 된다.

4. B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행한다.

✔︎ 세마포어 동작 방식

Busy - Wait 방식 (최초의 방식)

공유 자원이 모두 사용 중이라면 프로세스 A가 계속 wait 하는 방식
자원의 여유가 생기면 자원을 획득하고 자원을 모두 사용했다면 자원을 반납한다.
임계 구역에 들어갈 수 있을 때까지 빈 반복문을 수행하기 때문에 다중 프로세스 환경에서 처리 효율이 떨어진다.
사용 중인 화장실에 들어가기 위해 다른 일을 하지 않고 오로지 들어갈 때까지 기다리는 상황과 비슷하다.

P(s){
    while(s <= 0) do wait
    s--;
}

///임계영역///

V(s){
    s++;
}

Block - Wakeup 방식

임계 영역에 진입할 때 S를 감소하는 것이 아니라 먼저 자원의 값을 감소한 뒤, 만약 자원의 개수가 부족해 사용할 수 없다면 프로세스를 Wait Queue에 추가하는 방법이다.
자원이 생기면 Wait Queue에서 프로세스를 꺼내와 wakeup()을 통해 프로세스를 수행한다.
사용 중인 화장실에 들어가기 위해 대기 리스트에 자기 이름을 적고, 다른 일을 하다가 차례가 오면 화장실에 들어가는 상황과 비슷하다.

P(S){
  S.value--;
  if(S.value < 0){
    // add this precess to S.queue;
    block();
  }
}

V(S){
  S.value++;
  if(S.value <= 0){
    // remove a process P from S.queue;
    wakeup(P);
  }
}

✔︎ 뮤텍스 (Mutex)

Mutual Exclusion으로 상호 배제라고도 한다.

다중 프로세스들의 공유 리소스에 접근하는 것을 조율하기 위해 locking과 unlocking을 사용한다.

뮤텍스는 이진 세마포어와 같이 초기값을 0과 1로 갖는다.

임계 영역에 들어갈 때 lock을 걸어 다른 프로세스나 쓰레드가 접근하지 못하도록 하고 임계영역에서 나올 때 lock을 해제한다.

mutex = 1;

void lock () {
  while (mutex != 1) 
  {
    // mutex 값이 1이 될 때까지 대기
  }
    // 이 구역에 도착했다는 것은 mutex 값이 1이라는 뜻. 이제 뮤텍스 값을 0으로 만들어 다른 프로세스(혹은 쓰레드)의 접근을 제한
   mutex = 0;
}

void unlock() {
    // 임계 구역에서 수행을 완료한 프로세스는 다른 프로세스가 접근할 개수 있도록 뮤텍스 값을 1으로 만들어 락을 해제.
    mutex = 1;
}

✔︎ 뮤텍스 (Mutex) 알고리즘

Dekker's Algorithm

flag와 turn이라는 변수로 임계 영역에 들어갈 프로세스나 쓰레드를 결정하는 방식

flag - 프로세스 중 누가 임게 영역에 진입할 것인지 나타내는 변수
turn - 누가 임계 영역에 들어갈 차례인지 나타내는 변수

While(1) {
  flag[i] = true;     // 프로세스 i가 임계영역 진입을 시도.
  while(flag[j]) {    // 프로세스 j가 현재 임계영역에 있는지 확인
    if(turn == j) {     // 프로세스 j가 임계영역을 사용 중이라면
      flag[i] = false;    // 프로세스 i의 진입을 취소하고,  
      while (turn == j);  // turn이 j에서 바뀔 때 까지 기다림
      flag[i] = true;     // j의 turn이 아니면, 즉 임계영역에서 j가 나오면 재진입을 시도
    }
  }
}
/* 임계영역*/
...
turn = j;           // 임계영역의 사용이 끝나면, turn을 넘김
flag[i] = false;    // 진입 flag값을 false로 바꾸어 임계영역 사용 완료

Peterson's Algorithm

데커 알고리즘과 유사하지만 상대방(다른 프로세스 혹은 쓰레드)에게 진입 기회를 양보한다는 차이가 있다.

do {
  flag[i] = true; //프로세스 i가 임계영역에 진입시도
  turn = j; // 다른 프로세스에게 진입 양보

  while (flag[j] && turn == j); // 다른 프로세스가 진입시도하면 대기

  // Critical section
  flag[i] = false; //
  // Remainder section
} while(true);

Bakery Algorithm

여러개의 프로세스 혹은 쓰레드에 대한 처리가 가능하며 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 영역에 진입한다.

while(1) {
...
  isReady[i] = true;                 // 번호표를 받을 준비
  number[i] = max(number[0~n-1]) +1  // 현재 실행 중인 프로세스 중 가장 큰 번호로 배정
  isReady[i] = false;                // 번호표 수령 완료

  for( j =0; j < n; j++ ) {          // 모든 프로세스에 대해 번호표를 비교.
    while( isReady[j] );               // 비교할 프로세스가 번호표를 받을 때까지 대기
    while(number[j] && number[j] < number[i] && j<i);
   }
/*  임계영역 */
...
number[i] = 0;                     // 임계영역 사용 완료
...
}

Semaphore vs Mutex

Mutex는 이진 세마포어로 세마포어의 일종이다.
가장 큰 차이점은 뮤텍스는 오직 1개의 프로세스 혹은 쓰레드만이 공유 자원에 접근할 수 있고, 세마포어는 하나 이상의 지정된 변수의 값만큼 접근할 수 있다.
세마포어는 운영체제 혹은 커널 단위에서 해당 리소스 변수가 관리되어 현재 공유 자원을 사용 중인 대상 뿐 아니라 다른 프로세스 및 쓰레드도 잠금 상태를 해제할 수 있지만 뮤텍스는 프로세스 단에서 관리되고 해당 변수(Lock)을 가지고 있기 때문에 Lock을 가지고 있는 변수만이 Unlock을 할 수 있다.
세마포어는 시스템 범위에 걸쳐 있고 파일 시스템 상의 파일 형태로 존재하지만, 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 해제된다.

참고

https://m.blog.naver.com/dong5053/220717508763

https://steady-coding.tistory.com/517
https://gyoogle.dev/blog/computer-science/operating-system/Semaphore%20&%20Mutex.html