1. 세마포어

• 세마포어: 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법
• 임계 구역(cirtical Section): 여러 프로세스가 데이터를 공유하여 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
  • 임계 구역을 수행할 때는 다른 프로세스가 공유데이터에 접근하지 못하도록 해야함

1.1. 세마포어 P, V연산

• P: 임계 구역에 들어가기 전 수행
  • 프로세스 진입 여부를 자원의 개수를 통해 결정
• V: 임계 구역에서 나올 ㄸ 수행
  • 자원 반납 알림및 대기 중인 프로세스를 깨움

2. 뮤텍스

• 뮤텍스: 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

  • 상태가 0,1이라 이진 세마포어로 부르기도 함

• lock: 현재 임계 구역에 들어갈 권한을 얻음

  • 만약 다른 프로세스/스레드가 임계구역을 수행중이라면 종료할 때 까지 대기

• unlock: 현재 임계 구역을 모두 사용했음을 알림

  • 대기 중인 다른 프로세스/스레드가 임계 구역에 진입 가능

  2.1. 뮤텍스 알고리즘

• 데커 알고리즘: flag와 turn변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

  • flag: 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
  • turn: 프로세스 중 누가 임계구역에 진입할 차례인지 나타내는 변수

  while(true)
  {
    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이 끝나면 다시 진입 시도
      }
    }
  }
  
  // --------- 임계 구역 -----------
  turn = j;			//임계 구역 사용이 끝나면 turn을 넘김
  flag[i] = false;		//flag값을 false로 바꿔 임계 구역 사용 완료를 알림

• 피터슨 알고리즘: 데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

    while(true) {
       flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
       turn = j; // 다른 프로세스에게 진입 기회 양보
       while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
       }
   }
  
   // ------- 임계 구역 ---------
  
   flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

• 제과점 알고리즘: 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘

  • 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입

  while(true) {
    
      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);
  
          // 프로세스 j가 번호표 가지고 있어야 함
          // 프로세스 j의 번호표 < 프로세스 i의 번호표
      }
  }
  
  // ------- 임계 구역 ---------
  
  number[i] = 0; // 임계 구역 사용 종료