출처 - https://github.com/jmxx219/CS-Study (opens in a new tab)

뮤텍스와 세마포어

뮤텍스와 세마포어는 Mutual Exclusion을 해결하기 위한 방법이다.

임계영역 참고 (opens in a new tab)

뮤텍스(Mutex)

• 개념

  • 한 스레드 및 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법

    • Key에 해당하는 어떤 객체(Object)가 있으며, 이 객체를 소유한 스레드/프로세스만이 공유자원에 접근 가능

  • Critical Section을 가진 스레드의 실행시간(Running time)이 서로 겹치지 않도록 각각 단독으로 실행하는 기술

  • 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 synchronized 또는 lock을 사용함

    • 즉, 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없음
    • 임계영역에 들어갈 때 Lock을 걸고(locking), 나올 때 Lock을 해제(unlocking)함

• 과정

  1. A 프로세스가 자원을 접근하기 위해 Key를 점유
  2. A 프로세스가 키를 점유했기 때문에 공유 자원을 사용함
  3. B 프로세스가 공유 자원을 사용하기를 원해서 Key를 점유하기 위해 대기함
  4. A 프로세스가 공유 자원을 다 사용하고 Key를 반환
  5. B 프로세스는 대기하고 있다가 반환된 Key를 점유하고 공유자원을 사용함

Mutex Locks

• 뮤텍스 락(Mutex Locks)은 상호 배제(Mutual Exclusion)를 보장하기 위해 사용되는 동기화 기법 중 하나

• 프로세스는 임계 구역에 들어가기 위해 lock을 얻어야 하고, 임계 구역에서 나올 때는 lock을 반납해야 함

  • lock은 임계 구역에 들어가기 위한 key와 같음

• 구현

  • 두 개의 함수와 하나의 변수 필요
    • acquire(): lock 획득 연산
    • release(): lock 반납 연산
    • available: lock이 이용 가능한지 아닌지 알려주는 boolean 변수
  
  

  acquire(){
      while(!available){
          // 열쇠가 현재 사용 중이므로 기다림(Busy waiting)
      }
      // 열쇠 획득 후 사용 중이라고 표시 
      available = false;
  }

  release(){
      avaiable = true;
  }

  do {
      acquire() lock
      // Critical section
      release() lock
      // Remainder section
  } while (true);

• Busy waiting 문제

  • acquire()에서 발생

  • 한 프로세스가 자신의 임계 구역에 있으면, 자신의 임계 구역에 진입하려는 다른 프로세스가 진입 코드를 계속 반복 수행(무한루프)하는 것을 의미

  • 프로세스가 lock을 기다리는 동안 회전하기 때문에 SpinLock 이라고도 함

  spinLock의 경우 lock이 획득되자마자 바로 실행된다는 장점이 있음

  (waiting queue에서 바로 실행되는 것이 아닌 ready queue로 갔다 실행되기에 오버헤드발생)

세마포어(Semaphore)

• 개념

  • 뮤텍스에서 나아가 설정된 값만큼 스레드/프로세스를 공유자원에 접근하도록 상호배제를 보장하는 기법
    • 공유 리소스에 접근할 수 있는 최대 허용치만큼 동시 사용자(스레드, 프로세스) 접근을 허용함
  • 리소스 상태를 나타내는 간단한 카운터로 생각할 수 있음
    • 운영체제 또는 커널의 한 지정된 저장장치 내의 값
    • 일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 이용함
  • 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있음
    • 사용 중이지 않는 자원의 경우 그 프로세스가 즉시 자원을 사용할 수 있음
    • 이미 다른 프로세스에 의해 사용 중이라면, 재시도하기 전에 일정 시간을 기다려야 함
    • 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에 그 값을 변경하여 다른 세마포어 사용자들이 기다리도록 해야 함
  • 세마포어는 이진수를 사용하거나, 추가적인 값을 가질 수 있음ㅂ

• 과정
  1. 공유 자원에 대한 최대 허용치 정의(허용치: 2)
  2. A 프로세스가 공유 자원에 접근, 허용치 1로 감소
  3. B 프로세스가 공유 자원에 접근, 허용치 0로 감소
  4. C 프로세스가 공유 자원에 접근, 허용치가 0이므로 대기
  5. B 프로세스가 공유 자원을 다 사용한 후, 허용치 1로 증가
  6. C 프로세스는 대기하다가 허용치가 1로 증가되어 공유 자원에 접근, 허용치는 다시 0으로 감소

• 종류
  • 카운팅 세마포어(Counting Semaphore)
    • 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포어는 그 가용한 자원의 개수로 초기화 됨
    • 자원을 사용하면 세마포어가 감소하고, 방출하면 세마포어가 증가함
  • 이진 세마포어(Binary Semaphore)
    • MUTEX 라고도 부르며, 상호배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어짐
    • 이름 그대로 0 과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용함

세마포어 구현

• 구현
  • 두 개의 함수와 하나의 변수 필요
    • wait(): 쓰레드가 임계구역에 들어가기 위해 호출하는 연산, 다른 쓰레드가 임계구역에 작업중이면 대기
    • signal(): 쓰레드가 임계구역에 작업을 마치고 세마포어를 해제하는 연산
    • S: 정수 변수, 현재 공유 데이터에 접근 가능한 허용치 개수

• busy-waiting 방식

  wait(S){
      while(S <= 0) { // 이용가능한 세마포어가 없는 경우
          // busy wait
      }
      S--; // 자원 획득
  }

  signal(S){
      S++; // 자원 반납
  }
  • 이진 세마포어: S = 1인 경우로, 이는 뮤텍스 락과 비슷하게 동작
  • 카운팅 세마포어: S = n (n > 1) 인 경우로, S가 무한대로 증가할 수 있음

    1. S를 사용 가능한 자원의 갯수로 초기화

    2. 프로세스가 자원을 사용할 경우

       • wait() 을 실행하여 현재 사용가능한 S의 갯수를 줄여준다.

    3. 프로세스가 자원을 반납할 경우

       • signal()을 실행하여 현재 사용가능한 S의 갯수를 늘려준다.

    4. S = 0 인 경우 (= 모든 리소스가 사용 중인 경우)

       • S가 0보다 커질 때 까지 Busy wait

• block-wakeup 방식

  typedef struct {
      int value;            /* semaphore */
      struct process *list; /* process wait queue */
  } semaphore;

  wait(semaphore *S) {
      S->value--;
      if (S->value < 0 ) {              // 자원이 없다면
          add this process to S->list;    // 프로세스를 waiting queue에 넣고
          block();                        // block 시킴
      }
  }

  signal(semaphore *S) {
      S->value++;
      if (S->value <= 0) {               // 자원이 0이하라면 block중인 프로세스가 있다는 의미
          remove a process P from S->list; // 대기하고 있는 프로세스를 가져옴
          wakeup(P);                       // 가져온 프로세스를 깨움
      }
  }
  • block(): block()을 호출한 프로세스를 중지시키고, 해당 프로세스는 대기큐(waiting queue)에 들어감
    • 해당 프로세스는 running 상태에서 waiting 상태로 바뀜
  • wakeup(P): block된 프로세스 P를 wakeup(재시작) 시키고, 이 프로세스를 ready queue로 옮김
    • Wait 상태에 있던 프로세스는 깨어나서 Ready 상태로 변함
    • 이후 스케쥴러에세 선택받기를 기다림

뮤텍스와 세마포어의 차이점

• 동기화 대상의 개수
  • 뮤텍스는 동기화 대상이 오직 하나이며, 세마포어는 동기화 대상이 하나 이상일 때 사용함
• 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없음
  • 뮤텍스는 상태가 0과 1만 존재하는 이진 세마포어의 일종으로 lock을 걸면서 동기화 문제를 해결함
• 세마포어는 자원 소유가 불가능, 뮤텍스는 자원 소유가 가능하며 소유주가 이에 대한 책임을 가짐
  • 뮤텍스의 경우 상태가 두 개뿐인 Lock이므로 Lock을 가질 수 있음
• 해제
  • 뮤텍스의 경우, 뮤텍스를 소유하고 있는 사용자만이 임계 영역을 나갈 때 뮤텍스(Lock)를 해제해야 함
  • 세마포어는 세마포어를 소유하지 않는 사용자도 세마포어를 해제할 수 있음
• 범위
  • 세마포어는 시스템 범위에 걸쳐있고 파일 시스템 상의 파일 형태로 존재
  • 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 해제됨

Monitor

뮤텍스와 세마포어의 문제점

• 뮤텍스의 락 혹은 세마포어를 사용할 때 타이밍 오류가 발생할 수 있음
  • wait()과 signal() 연산의 순서가 뒤바뀌는 경우
    • wait : 쉽게 말해 락을 거는(count를 감소시키는) 작업
    • signal : 쉽게 락을 푸는(count를 증가시키는) 작업
  • Critical Section이 끝나고 signal()대신 wait()이 호출되는 경우

모니터

• 개념
  • 세마포어에서 발전된 형태로, 상호 배제와 조건 동기화를 제공하는 동기화 방법
  • 운영체제가 처리하는 것이 아닌 프로그래밍 언어에서 지원함
• 특징
  • 타이밍 문제 해결
    • 들어가기 전에 락을 걸고 나오면 락을 푸는 것을 monitor가 대신 처리해줌
    • 내부에 있는 프로시저를 활용해서만 공유 데이터에 접근이 가능하도록 구현된 것
  • 프로그래밍 언어 레벨에서 제공되는 추상 데이터 타입(ADT)
    • 추상화된 데이터 형(Abstract Data Type, ADT)
      • 모니터 타입은 상호배제를 제공해주는 ADT로, 추상 자료형임
      • 객체지향의 클래스와 같이 기능의 구현 부분을 나타내지 않고,데이터의 형태와 그 데이터의 연산들을 정의해놓은 자료형
  • 객체 지향 프로그래밍에서 사용되는 동기화 도구
  • 상호 배제와 조건 변수를 사용해 동기화를 자동 처리하기 때문에 프로그래머의 실수를 줄임
• 구성 요소
  • monitor lock
    • 임계영역에서 상호 배제를 보장하는 장치
    • Thread 단위로 락을 취득해야 임계영역에 진입할 수 있고, 취득하지 못한 스레드는 큐에 들어가 대기 상태로 전환됨
  • 조건 변수(condition variable)
    • 대기 큐(스레드가 특정 조건이 충족될 때까지 대기상태로 머무는 곳)를 가짐
  • 조건 변수의 주요 동작(operation)
    • wait: 쓰레드가 자기 자신을 대기열에 넣고 대기 상태로 전환
    • signal: 대기열에서 대기중인 쓰레드를 하나 깨움
    • broadcast: 대기열에서 대기중인 쓰레드를 모두 깨움
• 작동 방식
  1. 스레드가 모니터에 진입하려고 할 때, 락 획득
  2. 다른 스레드가 이미 모니터의 락을 획득한 상태라면, 현재 스레드는 대기
  3. 대기 중인 스레드는 모니터 내부의 레디 큐에 저장
  4. 레디 큐에서는 스레드를 일시 중지시키고, 대기 중인 스레드들의 목록을 유지
  5. 모니터 내의 조건 변수를 사용하여 특정 조건이 충족될 때까지 프로세스를 대기시킬 수 있음
     • 이 경우, 프로세스는 조건 대기 큐(condition wait queue)에서 대기함
  6. 스레드가 일시 중지된 상태에서 해당 조건이 충족되면, 모니터는 대기 중인 스레드를 깨우고 다시 실행될 수 있도록 함
  7. 스레드가 모니터를 빠져나갈 때, 락을 반납함. 이때 다른 스레드들이 모니터에 진입할 수 있음