[OS] - Semaphore / Mutex

Semaphore

---

MultiProgramming 환경에서 Shared Resource에 대한 접근을 제한

• Shared Resource에 여러 Process가 동시에 접근하면서, 문제가 발생 할 수 있다.
• Resource에는 그렇기에 하나의 Process만 접근이 가능하다.

 

Critical Section

• 여러 Process가 data를 Share하면 수행 할 때, 각 Process에서 Shared Data를 접근하는 코드 부분
• Shared Data를 여러 Process 가 접근하면 잘못된 결과가 발생 할 수 있다.

 

Semaphore P,V

• P : Critical Section에 들어가기 전에 수행
• V : Critical Section에서 나올 때 수행

#SemaPhore

P(S)

# Critical Section Code

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

• 이와 같은 방식을 통해 P,V를 통해 Resource에 대해 Mutual Exclusion 구현이 가능

 

Mutex

---

• Critical Section을 가진 Thread들의 실행 시간을 겹치지 않고 각각 실행 가능하게 해준다.
• Mutual Exclusion의 약자
• 접근을 위해 Lock , Unlock을 사용
• Lock = Critical Section에 들어갈 권한
• UnLock = Critical Section을 모두 사용했음을 알린다.
• Mutex는 0,1 상태인 binary Semaphore라고 부른다.

 

Mutex Algorithm

1. Dekker Algorithm

• 프로세스 두 개일때 상호 배제를 보장하는 최초의 알고리즘입니다.
• Flag, Turn 변수를 통해 Critical Section에 들어갈 Process,Thread를 결정
• Flag = Process 중 누가 Critical Section에 들어갈 것인지
• Turn = 누가 임계 구역에 들어갈 차례인지
• i = 자신의 Process
• j = 상대 Process

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이 끝나면 다시 진입 시도
        }
    }

// ------- Critical Section ---------

turn = j; // end Critical Section -> turn change
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

}

 

2. Peterson Algorithm

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

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

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

// critical section

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

}

 

3. 다익스트라 Algorithm

• 프로세스 n개의 상호배제 문제를 해결한 최초의 알고리즘입니다.
• CS에 진입하기 위해 단계를 2단계로 나누어 단계마다 진입할 수 있는 프로세스를 걸러내어 최종적으로 하나의 프로세스만 CS에 접근할 수 있게 구현되었습니다.
• flag [i] 변수 상태
  • idle : 프로세스가 임계 구역에 진입 시도를 하고 있지 않은 상태
  • want-in : 프로세스의 임계구역 진입 시도 1단계
  • in-CS : 프로세스의 임계구역 진입 시도 2 단계 및 임계구역 내에 있을 때

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

	do {
	// 임계구역 진입시도 1단계
	  flag[i] = want-in                     // 1단계 진입시도를 한다고 알림
	  while (turn != i ) {                  // 자신의 차례가 될 때까지 대기를 함.
	    if (flag[turn] == idle) {           // 임계구역에 프로세스가 없다면,
	      turn = i;                         // 자신의 차례로 변경함.
	    }
	  }
	
	// 임계구역 진입시도 2단계
	  flag[i] = in-CS                      // 임계구역에 진입하겠다고 알림.
	  j = 0;
	  while ((j < n) && (j == i|| flag[j] != in-CS ){ // 자신을 제외한 in-CS 상태의 프로세스가 있는지 검사 함.
	    j = j + 1;
	  }
	} while(j < n)   // 자신 외에 2단계 진입을 시도하는 프로세스가 있다면 다시 1단계로 돌아감.
	
	// critical section   // in-CS 상태의 프로세스가 자신밖에 없다면 임계영역에 진입함.
	
	flag[i] = idle;  // 임계구역 사용완료를 알림.
	
}

 

4. Bakery Algorithm

• 프로세스 n개의 상호 배제 문제를 해결한 알고리즘입니다.
• bakery 알고리즘은 프로세스에게 고유한 번호를 부여하고, 번호를 기준으로 우선순위를 정하여 우선순위가 높은 프로세스가 먼저 임계 구역에 진입하도록 구현되었습니다.
• 번호가 낮을수록 우선순위가 높음.

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

  choosing[i] = true;   // 번호표 받을 준비
  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;  // 임계구역 사용완료를 알림.
}