공유자원에 접근하는 프로세스 내부의 코드영역으로 어떤 한 프로세스가 이 영역을 수행중일 때, 다른 프로세스가 같은 영역을 수행한다면 문제가 발생할 수 있다.
* 공유자원 : 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일
이러한 문제가 발생하지 않도록 한번에 하나의 프로세스만 이용할 수 있도록 보장해야 하는 영역이다.
1. 상호배제
하나의 프로세스가 임계 영역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다.
2. 진행
임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러 개라면 어느 것이 들어갈지 결정해주어야 한다.
3. 한정 대기
다른 프로세스의 기아를 방지하기 위해, 한 번 임계 영역에 들어간 프로세스는 다음번 임계영역에 들어갈 때 제한을 두어야 한다.
임계영역의 동시접근을 해결하기 위한 방법으로 락(lock), 세마포어(semaphore), 모니터(monitor)등이 있다.
뮤텍스(Mutex)
멀티 프로그래밍 환경에서 자원에 대한 접근에 제한을 강제하기 위한 동기화 기법이다.
0 또는 1의 값을 가지는 이진 세마포어와 유사하다. *임계영역에 하나의 스레드만 접근 가능(Binary Semaphore)
공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는다.
임계영역을 가진 스레드들의 실행 시간을 서로 겹치지 않게 단독으로 실행하게 하는 기술
멀티 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 하용한다.
뮤텍스 알고리즘
데커(Dekker) 알고리즘 : flag와 turn 변수를 통해 임계영역에 들어갈 프로세스를 결정
flag : 프로세스 중 누가 임계영역에 진입할 것인지를 나타내는 변수
turn : 누가 임계영역에 들어갈 차례인지를 나타내는 변수
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; // 차례가 넘어왔다면 진입을 알림.
}
}
// 임계영역
turn = j; // 임계구역의 사용이 끝났다면 차례를 프로세스j에게 넘김.
flag[i] = false; // 진입을 취소하여 임계구역 사용완료를 알림.
}
피터슨(Peterson) 알고리즘 : 데커 알고리즘과 유사하지만 상대방(다른 프로세스 또는 다른 스레드)에게 진입기회를 양보
while(1) {
flag[i] = true; // 프로세스i가 임계영역에 진입을 시도
turn = j; // 다른 프로세스에 진입 기회를 양보
while(flag[i] && turn==j); // 다른 프로세스가 진입을 시도하면 대기 아니면 진입
/* 이곳은 임계영역이다. */
...
flag[i] = false; // 임계영역 사용 완료
...
}
램퍼드의 베이커리 알고리즘(Lamport's Bakery Algorithm) : 여러 개의 프로세스(혹은 스레드)에 대한 처리가 가능하다. 가장 작은 수의 번호표를 가지고 있는 프로세스가 입계영역에 진입한다.
while(1) {
...
isReady[i] = true; // 번호표를 받을 준비
number[i] = max(number[0~n-1]) +1 // 현재 실행 중인 프로세스 중 가장 큰 번호로 배정
isReady[i] = false; // 번호표 수령 완료
for( j =0; j < n; j++ ) { // 모든 프로세스에 대해 번호표를 비교한다.
while( isReady[j] ); // 비교할 프로세스가 번호표를 받을 때까지 대기
while(number[j] && number[j] < number[i] && j<i);
// 프로세스 j가 번호표를 가지고 있고,
// 프로세스 j의 번호표가 프로세스i의 번호표보다 작거나 같을 경우
// j가 i보다 작다면(프로세스 j가 i보다 먼저 온 프로세스이면)
// 프로세스 j의 종료(number[j]=0)까지 대기
}
/* 이곳은 임계영역이다. */
...
number[i] = 0; // 임계영역 사용 완료
...
}
세마포어 (Semaphore)
멀티 프로그래밍 환경에서 다수의 프로세스나 스레드가 n개의 공유 자원에 대한 접근을 제한하는 방법으로 사용되는 동기화 기법이다.
뮤텍스가 임계영역에 들어가는 스레드가 하나라면, 세마포어는 복수 개가 가능하다.
접근 가능한 공유 자원의 수가 1개일 때는 이진 세마포어로 뮤텍스와 유사하게 사용할 수 있다.
큐에 연결된 스레드를 깨우는 방식에 따라 강성 세마포어, 약성 세마포어로 구분된다.
* 강성 세마포어 : 큐에 연결된 스레드를 깨울 때 FIFO 정책.
* 약성 세마포어 : 큐에 연결된 스레드를 깨울 때 순서를 특별히 명시하지 않음.
Signaling 메커니즘으로 Lock을 걸지 않은 스레드도 Signal을 보내 Lock을 해제할 수 있다.
wait과 signal을 통해 구현한다.
* wait이 먼저 호출되어 임계영역에 들어갈 수 있는지 확인 / 먼저 실행되어야 하는 프로세스가 실행되는지 확인
* 조건에 만족하면 wait을 빠져나와 임계영역으로 들어간다.
* 이후 signal이 호출되어 임계영역에서 빠져나왔음을 알린다.
예시
counting semaphore 예시
서버에 프린터가 다섯 대 연결되어있고, 사용자는 프린터를 사용하기 위해 서버에 요청을 한다.
여기서 프린터 5대는 공유자원이다. 세마포어 5로 설정된다.
프린터를 사용자가 사용할 때마다 세마포어는 1씩 감소한다.
사용할 프린터가 없어지면 세마포어는 0이 되고, 누군가 프린터를 쓰고 반환하면 세마포어는 1증가하게 된다.
여기서 세마포어는 단순히 공유자원의 개수를 나타내는 변수이다.
semaphore 접근 함수 wait(), signal()
자원을 사용하고 반납하기 위해 제공되는 함수 *wait(), signal()
사용할 때, 세마포어를 감소해주고 반납할 때 세마포어를 증가시켜주는 함수
다만, 세마포어 자체가 공유자원이 되면 안되므로 쪼개지지 않는 함수로 구성된다.
공유자원을 보호하기 위해 세마포어를 사용핮는데 세마포어 자체가 공유자원이 되면 안되기 떄문이다.
공유 자원을 사용하려 했지만, 현재 사용할 수 있는 공유 자원이 없어 기다려야 한다. - wait()
비어있는 공유 자원이 있으면 기다리지 않고 사용한다.
현재 세마포어의 값이 0이라면, wait()이다.
공유자원을 사용하고 반납하면 세마포어 값을 증가시켜주어야 한다. 대기하고 있는 프로세스가 있다면 사용할 수 있다는 것을 알려줘야 하므로 신호를 보내준다. - signal()
세마포어와 뮤텍스의 차이점
세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
뮤텍스는 동기화 대상이 1개일 경우에 사용하고, 세마포어는 동기화 대상이 n 개일 때 사용한다.
세마포어는 소유할 수 없으며, 뮤텍스는 소유할 수 있고 소유주가 그에 대한 책임을 진다.
뮤텍스는 Lock을 건 스레드만 Lock을 해제할 수 있지만, 세마포어는 Lock을 걸지 않은 스레드도 Signal()을 보내 Lock을 해제할 수 있다.
모니터
뮤텍스, 세마포어를 사용할 때 타이밍 오류가 발생할 수 있다. 예를 들어, wait(), signal() 연산의 순서가 바뀌는 경우, 임계영역이 끝나고 signal()대신 wait()이 호출되는 경우 오류가 발생하게 된다. 이를 보완한 것이 모니터이다.
* 모니터는 세마포어와 달리 wait(), signal() 설정을 해주지 않고, synchronized 키워드를 사용하면 알아서 상호배제하여 함수 작업을 수행한다.
모니터는 하나의 프로세스 내에서 다른 스레드 간의 동기화에 사용된다.
모니터는 C언어네는 없고 Java에는 있다.
프로세스 또는 스레드를 동기화하는 방법 중 하나이다. 모니터는 하나의 데이터마다 결합함으로써 동시에 두 개 이상의 스레드에 의해 접근할 수 없도록 막는 잠금 기능을 제공함으로써 동기화를 수행한다.
모니터는 두 개의 queue를 가지고 있다.
상호베타 큐(Mutial Exclusion Queue) : 공유자원에 하나의 프로세스만 진입하도록 하기 위한 큐이다. 공유 자원을 사용하는 스레드가 존재하면 상호베타 큐에 존재한다.
