세마포어(Semaphore) & 뮤텍스(Mutex)

---

요약

• 공유된 자원의 데이터 혹은 임계구역이 있을 때

  • 세마포어는 여러 프로세스가 진입할 수 있음, 다른 프로세스도 lock 해제 가능

  • 뮤텍스는 하나의 프로세스만 진입할 수 있음, 해당 프로세스만 lock 해제 가능

임계 구역과 동기화

• 임계구역

  • 배타적으로 읽고 쓸 수 있도록 설정한 코드

  • 요구사항 3가지

    • 상호 배제 : 한 프로세스가 임계구역을 실행 중일 때, 다른 어떤 프로세스도 임계구역을 실행 불가능

    • 진행 : 임계구역을 실행하는 프로세스가 없고 여러 프로세스들이 임계구역에 들어오고자 할 때, 유한한 시간에 하나의 프로세스만을 선택하는 임계구역에 진입시키는 올바른 결정 기법이 존재

    • 제한된 대기 : 프로세스가 임계구역의 진입의 요청과 실제 요청하기 사이에 다른 프로세스가 임계구역을 실행할 수 있는 횟수에 제한이 있음

• 동기화

  • 코드 상에 임계 구역을 설정하여 코드 상으로는 독립적이지만 진입과 진출을 순서화해서 실행 상황에서 선행제약을 만드는 것

뮤텍스

• 두 프로세스가 임계구역에 동시에 접근하지 못하도록 막기 위해 사용하는 객체

• 구성 - lock, unlock

  • lock : 현재 임계구역에 들어갈 권한을 얻어옴, 다른 프로세스가 임계구역을 실행 중이라면 종료할 때까지 대기

  • unlock : 현재 임계구역을 모두 사용했음을 알려서 대기 중인 프로세스가 임계구역에 진입할 수 있게 함

세마포어

• 뮤텍스와 달리, 진입 불가능할 때 대기 상태로 전환되고 임계구역을 떠나는 프로세스가 대기 프로세스를 준비 상태로 깨워줌

• 구성 - 정수값 S, P연산과 V연산

  • 임계구역에 들어가기 전에 P연산(try)과 임계구역에서 나올 때 V연산(increment)

  • S > 1이면 자원이 여러 개 있을 경우 자원과 대기자를 동시에 관리 가능

    • 프린트를 공유하는 여러 프로세스들

  • S == 1이면 공유변수에 대한 뮤텍스와 동일

    • 공유변수

  • S == 0이면 이벤트에 의한 다중 쓰레드 간의 serialization에 사용

    • 실제 공유자원은 없음

문제점과 해결책

• Readers Writers Problem

  • 공유자원에 여러 프로세스가 읽고 쓸 경우, 한 프로세스가 읽거나 쓸 때 모든 프로세스가 대기하는 것은 비효율

  • Reader들은 lock을 공유, Writer들은 모두 배타적으로 실행하고 Reader 대기 큐와 Writer 대기 큐를 분리

• 우선순위 역전 문제

  • 높은 우선순위를 가진 프로세스가 낮은 우선순위를 가진 프로세스가 공유자원 사용을 마칠 때까지 기다려야 하는 상황

  • 우선순위 상속 프로토콜

    • 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스가 실행 중인 임계구역에서 대기 중일 때, 실행 프로세스에 높은 우선순위를 상속시킴

구현

• 뮤텍스

  • Peterson's solution : 상대방에게 한 번씩 양보해줌

  int turn = 0;
  boolean flag[] = [0,0};
  
  // P0						// P1
  enter_mutex {					enter_mutex {	
      flag[i] = TRUE;					    flag[j] = TRUE;
      turn = j;					    turn = i;
      while(flag[j] && turn == j);			    while(flag[j] && turn == j);
  }						}
  				    
  // 임계구역					// 임계구역
  				    
  exit_mutex {					exit_mutex {
      flag[i] = FALSE;					    flag[i] = FALSE;
  }						}

  • Bakery algorithm

  choosing[i] = true;
  number[i] = max(number[0],number[1],...number[n-1]) +1 ;		// 번호표 뽑기
  choosing[i] = false;
  for ( j = 0 , j < n-1, j++ ) {
      while ( choosing[j] );						// 번호표 뽑기 대기
      while ( number[j] != 0 && (number[j],j) < (number[i],i) ); 		// 먼저 번호를 뽑은 프로세스가 끝날 때 까지 대기
  }
  number[i] = 0;

• 세마포어

  P(S) {
       S--;
       if S < 0
           // 이 프로세스를 대기 큐에 추가 (잠 듦)
   }
  
   V(S) {
       S++;
       if S <= 0
           // 대기 큐로부터 프로세스를 제거 (깨어남)
   }