경쟁 상태 (Race Condition) , 세마포어(Semaphore) & 뮤텍스(Mutex)

경쟁상태 ? 

여러 개의 프로세스들이 공유 자원에 동시적으로 접근할 때, 접근 타이밍과 순서에 따라 그 결과가 달라져서

데이터 일관성을 해칠 수 있는 상태를 뜻함

100의 값을 가지고 있는 공유 자원 data가 있고, 이 자원에 동시 접근하는 프로세스 A와 B가 있다.

프로세스 A는 data++을 수행하고, 프로세스 B는 data--를 수행한다.

일반적으로 이런 상황에서 의도하는 결과는 100에 1을 더한 뒤 빼거나,

1을 뺀 다음 더하여 처음과 그대로 data가 100이 나오는 것이다.

 

하지만 경쟁 상태에 의해 data가 99나 101로 나올 수도 있다

 

 

---

 

세마포어 (Semaphore)

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

이를 위해 나온 것이 바로 '세마포어'

 

임계 구역(Critical Section)

 

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.

 

 

 

세마포어 & 뮤텍스 설명

https://worthpreading.tistory.com/90

 

뮤텍스(Mutex)와 세마포어(Semaphore)의 차이

 

세마포어 P, V 연산

P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )

 

 

P연산 

같이 들어갈 수 없는 임계영역에 들어가고자 하는 프로세스는 P를 거쳐야 한다.

procedure P(S)
while S=0 do wait
S := S-1
end P

1. 최초 S값은 1
2. S가 0이면 S가 1이 될때 까지 기다린다.
3. S가 1이면 0으로 만들고 진입한다.

 

 

V연산

P연산을 통과해 임계영역의 연산을 끝낸 프로세스가 V연산을 수행하게 된다.

procedure V(S)          // 현재상태는 S가 0
S := S+1                // S를 1로 원위치시켜 해제하는 과정
end V                   // 이제는 다른 프로세스가 들어 올수 있음

• 최초 S값을 1로 만든다.

 

작동 예시

P(S);
---------------------
위험지역(Critical Section) = 임계영역
--------------------
V(S);

 

 

 

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

• 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없음 
  • 뮤텍스는 상태가 0, 1 두개 뿐인 이진형 세마포어
• 세마포어는 소유할 수 없는 반면, 뮤텍스는 소유가 가능하며 소유주가 이에 대한 책임
• 세마포어는 파일 형태로 존재하며 전 시스템 범위, 뮤텍스는 프로세스의 범위이며 프로세스 종료시 초기화

 

---

뮤텍스 알고리즘

 

데커 알고리즘(Dekker algorithm)

프로세스 두 개일때 상호 배제를 보장하는 최초의 알고리즘입니다.

flag는 누가 CS(Critical Section)에 진입할 것인지 알리는 변수이고, turn은 누가 CS에 들어갈 차례인지 알리는 변수

while(1) {               // 프로세스i의 진입 영역

  flag[i] = ture;        // 프로세스i가 임계구역에 진입하기 위해 진입을 알림

  while(flag[j]) {       // 프로세스j가 임계구역에 진입하려고 하는지 확인
    if (turn == j) {     // 프로세스j가 임계구역에 있다면
      flag[i] = flase;   // 프로세스i가 진입을 취소하고
      
      while (turn == j); // 프로세스i의 차례가 올 때까지 대기 함.
      
      flag[i] =ture;     // 차례가 넘어왔다면 진입을 알림.
    }
  }

// Critical Section

  turn = j;              // 임계구역의 사용이 끝났다면 차례를 프로세스j에게 넘김.
  flag[i] = false;       // 진입을 취소하여 임계구역 사용완료를 알림.
}

 

피터슨 알고리즘(Peterson algorithm)

프로세스 두 개 일 때 상호 배제를 보장하는 알고리즘입니다.

데커의 알고리즘과 유사하지만 상대방에게 진입 기회를 양보한다는 차이가 있고 보다 더 간단하게 구현되었습니다.

while(1) {                        // 프로세스i의 진입 영역

  flag[i] = ture;                 // 프로세스i가 임계구역에 진입하기 위해 진입을 알림.
  turn = j;                       // 프로세스j에게 진입을 양보함.
                                  //  (두 프로세스중 먼저 양보한쪽이 먼저 임계구역에 들어가게 됨.)
  while (flag[j] && turn = j);    // 프로세스i의 차례가 될 때까지 대기를 함.

// critical section

  flag[i] = false                 // 임계구역 사용완료를 알림.

}

 

베이커리 알고리즘(Bakery algorithm)

 

프로세스 n개의 상호 배제 문제를 해결한 알고리즘입니다.

bakery 알고리즘은 프로세스에게 고유한 번호를 부여하고, 번호를 기준으로 우선순위를 정하여 우선순위가 높은 프로세스가 먼저 임계 구역에 진입하도록 구현되었습니다

 

쉽게 말하자면 

빵집이 돌아가는 모습이 비슷하기 때문에 빵집 알고리즘이라고 불리는데

요즘은 은행과 비슷하다고 생각하면 됨

 

번호표를 뽑고 내 번호표보다 낮은번호(먼저온) 스레드의 처리가 끝날 때 까지 기다림

같은 번호표를 뽑을 수 있기 때문에, 스레드끼리 구분할 수 있는 인자(thread_id)값을 주어서

이게 낮은 스레드가 먼저 처리됨

 

while(1) {              // 프로세스i의 진입 영역

  choosing[i] = ture;   // 번호표 받을 준비
  number[i] = max(number[0], number[1], ..., number[n-1]) + 1;  // 번호표 부여 
                                                                // (번호표 부여중 선점이 되어 같은 번호를 부여 받는 프로세스가 발생할 수 있음)
  chossing[i] = false;  // 번호표를 받음

  for (j = 0; j < n; j++) { // 모드 프로세스와 번호표를 비교함.
    while (choosing[j]);    // 프로세스j가 번호표를 받을 때까지 대기

    while ((number[j] != 0) &&    
            ((number[j] < number[i])               // 프로세스 j가 프로세스 i보다 번호표가 작거나(우선순위가 높고)
            || (number[j] == number[i] && j < i)); // 또는 번호표가 같을 경우 j 가 i 보다 작다면 
                                                   // 프로세스 j가 임계구역에서 나올 때까지 대기.     
  }


// Critical Section

  number[i] = 0;  // 임계구역 사용완료를 알림.
}