[운영체제] 상호 배제 ( Mutual Exclusive ) 및 세마포어

상호배제를 보장받기 위한 요구조건이 있다.

 

1) 단 하나의 프로세스만이 임계영역에 진입되어야 한다. 

2) 임계 영역이 아닌 곳에서 수행이 멈춘 프로세스는 다른 프로세스 수행을 간섭해서는 안된다.

3) 임계 영역에 접근하고자 하는 프로세스의 수행이 무한히 미루어져서는 안된다.

4) 임계 영역이 비어있으면 즉시 임계영역에 들어갈 수 있다.

5) 프로세서 개수나 상대적 프로세스 수행속도에 대한 가정은 없어야 한다. ( 독립적 )

6) 임계 영역에 들어간 프로세스는 일정시간 내에 나와야 한다.

 

 

상호배제 보장 요구조건 만족을 위한 하드웨어 지원

 

 

1) 인터럽트 금지

 

단일처리기에서의 병행처리는 오버래핑(Overlapping)이 아닌 인터리빙(Interleaving)이 일어난다. 그러므로 임계영역에 들어간 프로세스의 인터럽트만 금지해도 상호배제를 보장할 수 있다. 

 

그러나 처리기가 하나인 만큼 프로세스가 임계영역에 들어간 시간동안 커널 명령을 수행 할 수 없어 스케줄링 등 모든 기능이 중지된다. 또한 멀티프로세싱 환경에서는 인터럽트 하나 금지시킨다고 보장되는 것이 아니다. 

 

2) 특별한 기계 명령어

 

기계명령어란, 두 가지 기능을 하나의 명령어 인출 사이클 동안 처리하도록 설계한 명령 ( 읽기 - 쓰기, 읽기 - 테스트 )

 

Compare and Swap ( CAS Operation ) 명령어 

 

while(true){
  while( compare_and_swap ( bolt, 0, 1 ) == 1 ); // 바쁜 대기 ( busy wating )

  /* 임계 영역 */

  bolt = 0;

  /* 임계 영역 */
}

 

Exchange 명령어 

 

keyi = 1;
do exchange ( &keyi, &bolt )
while ( keyi != 0 ); // 바쁜대기 ( busy wating )

/* 임계영역 */
bolt = 0;
/* 임계영역 이후 코드 */

 

 

 

세마포어 ( Semaphore )

 

 

세마포어는 임계영역을 지키는 객체이다. 프로세스는 임계영역에 접근하려면 세마포어의 semWait 메소드를 호출하여 임계영역 상태를 점검해야한다. 세마포어 값은 현재 임계영역을 접근을 위해 대기중인 프로세스 개수를 나타낸다. 세마포어 큐는 실제 대기 중이 프로세스와 연결된 자료구조이다. 

 

semWait 메소드를 호출한 프로세스는 세마포어 값이 음수이면 현재 임계영역이 사용중으로 인식한다. 인식한 프로세스는 임계영역 접근 대기실인 세마포어 큐에 연결되어 블록상태로 전이된다. 

 

임계영역 작업을 마무리한 프로세스는 semSignal 메소드를 호출하여 세마포어 값을 +1 한다. 그리고 세마포어 큐에 대기중인 블록된 프로세스들 중 하나를 깨운다. 

 

이와 같이 세마포어는 3가지 원자적 연산을 지원한다. 

 

1. initialize : 세마 포어는 음이 아닌 값으로 초기화 한다.

2. decreament : semWait 연산으로 세마포어 값을 감소시킨다.  값이 음수이면 queue 자료구조에 저장되어 블록된다.

3. increament : semSignal 연산으로 세마포어 값을 증가시킨다. 값이 양수이면 queue 자료구조에 블록된 프로세스들을 깨운다.

 

struct semaphore {
	int count; // 세마포어 값
    queueType queue; // 블록된 프로세스와 연결된 큐
}

void semWait(semaphore s){
	s.count--; //decreament
    if(s.count < 0 ){
    	// 프로세스 queue에 연결 및 프로세스 블록상태로 전이
    }
}

void semSignal(semaphore s){
	s.count++; //increment
    if(s.count <= 0){ // 블록되어 있는 프로세스가 존재하는 경우
    	// s.queue에 연결된 프로세스를 큐에서 제거
        // 프로세스의 상태를 실행 가능으로 전이시키고 ready list에 연결
     }
}

 

 

세마포어 분류

 

1. 세마포어 값

 

이진 세마포어 (Binary Semaphore) : 세마포어값이 0 또는 1만 올 수 있는 세마포어이다. 임계영역을 차지한 프로세스가 존재하거나 블록된 프로세스가 존재하면 0이고 존재하지 않으면 1이다.

 

범용 세마포어 (General Semaphore) : 세마포어값으로 정수가 올 수 있으면 범용 세마포어이다. 

 

2. 큐 관리 정책

 

두 가지 세마포어 모두 블록된 프로세스 관리를 위한 큐를 갖고 있다.

 

강성세마포어 : 공정(Fair)하게 FIFO 식으로 블록된 프로세스를 깨우는 방식을 가진 세마포어를 의미한다.

약성세마포어 : 큐에서 반출되는 프로세스 순서를 특별히 정하지 않은 세마포어를 의미한다. 

 

 

세마포어 상호배제

 

세마포어는 세마포어 값에 따라 상호배제가 가능하다. 

 

세마포어가 N이면 N개의 공유 자원에 접근 제어를 할 수 있다. 1이면 1개의 공유 자원을 접근 제어를 할 수 있다. 공유 자원이 0이면 다른 프로세스가 임계영역에 접근할 수 없다. 

 

 

 

---

 

 

참고자료

운영체제