⛳ 멀티 스레드, 멀티 프로세서 환경에서의 공유 자원은 여러 스레드(프로세스)가 동시에 접근하면 문제가 발생한다. 이를 어떻게 해결할 수 있을까??

이를 알기 위해 임계구역에 대해 먼저 알아봅시다!

임계구역(Critical Section)이란,

: 여러 프로세스 혹은 스레드가 작업을 수행하면서 공유된 자원을 건드리게 될 수 있을 때, 프로그램 코드 상에서 공유 자원에 접근하는 부분을 말함

임계구역을 여러 프로세스 및 스레드가 함부로 접근할 수 없도록 관리하는 방식으로 크게 2가지가 있습니다. 세마포어와 뮤텍스!

세마포어

• 👀 세마포어란,
  동시에 공유자원에 접근할 수 있는 '허용 가능한 Counter의 갯수'를 가지고 있는 Counter라고 볼 수 있다.
  예를 들어, 병실에 방문객용 의자가 5개가 있다고 차면, 간호사는 이 병실에 방문자가 5명만 들어갈 수 있도록 허용하고, 나무지 방문객은 밖에서 대기하도록 한다.
  즉, Counter갯수만큼 공유자원에 접근할 수 있다. Counter의 갯수에 따라 1개인 경우에는 Binary Semaphore, 2개 이상인 경우에는 Counting Semaphore라고 부른다.
  +) 개념적으로는 Binary Semaphore가 뮤텍스와 같다고 할 수 있다.

• ⚒️ 작동원리
  상호 배제 알고리즘에 기반한다. 즉, 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역에서 구현된다.

  일반적으로, 세마포의 값이 0이면 값에 접근할 수 없도록 블락(Block)하고 0보다 크면 접근함과 동시에 세마포어의 값을 1 감소시킨다. 반대로 종료하고 나갈 때는 세마포어의 값을 1 증가시켜 다른 프로세스가 접근할 수 있도록 한다.
  

• 📜 연산

  • P : 임계 구역에 들어가기 전에 수행하는 연산 (프로세스 진입 여부를 자원의 개수를 보고 결정)
  • V : 임계 구역에서 나올 대 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

// s는 자원의 개수

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

뮤텍스

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

• ⚒️ 작동원리
  상호 배제 알고리즘에 기반한다. 즉, 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역에서 구현된다. 접근을 조율하기 위해 lock, unlock을 사용한다.
  • lock : 현재 임계 구역에 들어갈 권한을 얻어옴 (만약 다른 프로세스/스레드가 임계 구역 수행 중이라면 종료할 때까지 대기)
  • unlock : 현재 임계 구역을 모두 사용했음을 알림.(이때 대기 중이던 다른 프로세스/스레드가 임계 구역에 진입이 가능해짐)
• 📜 뮤텍스 알고리즘

1. 데커 알고리즘

   • 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로 바꿔 임계 구역 사용 완료를 알림

2. 피터슨 알고리즘 : 상대방 프로세스/스레드에게 진입 기회를 양보

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

3. 제과점(Bakery) 알고리즘 : 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입.

   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; // 임계 구역 사용 종료

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

• 뮤텍스와 세마포어 모두 병행 처리를 위한 프로세스 동기화! 기법

• 세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스/스레드가 접근할 수 있음.

• 뮤텍스는 오직 1개만의 프로세스/스레드만 접근할 수 있음

• 세마포어에서는 현재 수행 중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제가능하다.

• 뮤텍스에서는 락을 획득한 프로세스가 반드시 그 락을 해제해야 한다.