상호배제 알고리즘와 세마포어

동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘.

상호 배제(mutual exclusion)와 임계 영역(critical section)

- 임계 영역:
멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역.
즉, 경쟁 조건이 발생 할 수 있는 프로그램 코드 부분으로 임계 구역 문제를 해결하기 위해 3가지가 필요하다.
(임계 영역만으로 경쟁 조건이 만들어지지 않을 경우 공유 메모리를 사용하는 병렬 프로세스가 올바르게 수행되려면 마지막 조건이 추가적으로 필요.)

• Mutual exclusion(상호배제): 두 개 이상의 프로세스들이 동시에 임계 영역에 있지 않도록 함.
• Progress(진행): 임계 구역 밖에 있는 프로세스가 다른 프로세스의 임계 구역 진입을 막지 않도록 함.
• Bounded Wating(한정 대기): 어떤 프로세스도 임계 구역으로 들어가는 것이 무한정 연기되지 않도록 함.
• 프로세스들의 상대적인 속도에 대해 어떤 가정도 하지 않을 것

- 상호 배제: 
한 프로세스가 공유 자원을 사용하고 있을 때 다른 프로세스들이 사용하지 못하게 빠꾸 시키는 제어 기법.

1. enter
- 임계 영역 진입 전 다른 프로세스가 있는지 검사

2. exit
- 임계 영역을 벗어날 때 시스템에게 알려 후처리

프로세스 기준 상호배제 알고리즘

1. 프로세스가 2개인 경우: 데커 알고리즘
turn, flag 두 가지를 사용해 구현함.
먼저, flag를 체크하고 확인한 다음 turn을 확인하는 방법

//A 프로세스
while(1) {
	flag[A] = true;
    while(flag[B]) {
    	if(turn == B) {
        	flag[A] = false;
            while(turn == B);
            flag[A] = true;
        }
    }
    V ++; // critical section
    flag[A] = false;
    turn = B;
}

 

- flag: 초기값은 flag[0] = flag[1] = false이고 임계 영역에 들어가겠다는 표시는 true로 함.
- turn: 0 또는 1. 0인 경우 A순서, 1인 경우 B의 순서

2. 프로세스가 n개인 경우: 디익스트라스 알고리즘- idle: 프로세스가 임계 구역 진입을 시도하고 있지 않을 때
- Want-in: 프로세스가 임계 구역 진입 시도 1단계일 때
- in-CS: 프로세스의 임계 구역 진입 시도 2단계 및 임계 구역 내에 있을 때

// 임계 지역 진입시도 1단계 
flag[i]
while (turn ≠ i) do
	if(flag[turn] = idle) then
    	turn
endwhile;
// 임계 지역 진입시도 2단계
flag[i] // in-CS;
j;
while ((j<n) and (j = i or flag[j] ≠ in-CS)) do
	j
endwhile;
until (j>=n); // j가 n보다 작거나 같으면 다시

// critical section

flag[i]; // idle;
...

- Step1: 현재 턴인 프로세스가 일을 끝날 때까지 기다렸다가 내 턴으로 뺏는다.
- Step2: 여러개의 프로세스가 들어갈 수 있다. 여기서 flag를 in-cs로 바꾼다. while문 조건을 만족하면 결국 in-cs에 나 혼자 있을 때 임계 영역에 들어간다. (다른 프로세스가 돌고 있을 경우 until에서 다시 repeat문을 실행) 이 경우 여러번 돌 수 있지만 한정 대기 조건은 위배되지 않음.

세마포어

- Busy waiting 문제 해결: 기다려야하는 프로세스는 block 상태가 된다.
- 세마포어는 음이 아닌 정수형 변수여야 한다.