[OS] 상호 배제 알고리즘 (데커, 세마포, 모니터)

데커의 알고리즘(Dekker's algorithm)

• 두 프로세스의 통신을 위해 공유 메모리를 사용하여 충돌 없이 단일 자원을 공유할 수 있도록 하는 알고리즘
• 다익스트라 알고리즘 사용
• 프로세스가 임계 영역에 진입하고 싶으면 플래그를 설정하고 대기
  

특징

• 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들의 임계 영역 진입을 막지 않는다.
• 임계 영역에 들어가고 싶은 프로세스를 무한정 기다리게 하지 않는다.

SW만으로 Solution을 구현할 때의 단점

• 속도가 느림
• 구현이 복잡함
• Busy waiting -> 기다리는 동안에도 while문을 계속 수행 중임

SW + OS를 통한 제어 (세마포 Semaphore)

• 다익스트라가 제안
• Busy waiting 문제를 해결

초기화 연산 P(), V()로만 접근

• P : probern (검사), waiting 동작
• V : Verhogen(증가), 대기중인 프로세스를 깨우려고 신호를 보내는 signal 동작

P(S) {
	// Busy Waiting 문제가 여전히 존재한다.
    // ready Queue를 통해 해결 가능
	while(S <= 0) do
    endwhile;
    S <- S-1;
}

V(S) {
	S <- S + 1;
}

ready Queue가 추가된 Semaphore

Busy waiting 문제 해결

struct semaphoe {
	int count;
    queueType queue;
};
semaphoe S;

// wait 연산 P
wait(S) {
	S -> count--;
    if(S -> count < 0) {
		add this process to S -> queue; // 프로세스를 준비 큐에 추가
        block(); // 프로세스 중단
    }
}

// signal 연산 V
signal(S) {
	S -> count++;
    if (S -> count <= 0) {
    	remove a process P from S -> queue; // 준비 큐에서 제거
        wakeup(P) // 신호를 보내 프로세스 실행
    }   
}

P, V가 짝을 이루어 실행되어야 하는데 코드가 많아지면 매우 복잡해진다.

해결 방법 : 모니터

모니터

• 상호배제가 가능한 데이터 구조를 제공, 프로그래머가 구현
• 상호배제 가능한 데이터 = Abstracted Data Type, 객체지향 컨셉과 유사하다.
• Class 형태로 제공해 사용자가 처리하기 간편하다.

구조

• Entry queue (진입 큐)
  - 모니터 내의 procedure 수만큼 존재
• Mutual exclusion
  - 모니터 내에는 항상 하나의 프로세스만 진입 가능
• Information hiding (정보 은폐)
  - 공유 데이터는 모니터 내의 프로세스만 접근 가능
• Condition queue (조건 큐)
  - 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기
• Signaler queue (신호 제공자 큐)
  - 모니터에 항상 하나의 신호제공자 큐 존재
  • signal() 명령을 실행한 프로세스가 임시 대기

Monitor monitor_name
{
	// 공유 데이터 변수 선언
	procedure P1( ... ) {
    	...
    }
    
    procedure P2( ... ) {
    	...
    }
    
    .
    .
    .
    
    procedure Pn( ... ) {
    	...
    }
    
    initialization_code( ...) { //초기화
    	...
    }
}

---

Reference

운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미