Mutex, Semaphore에 관한 글은 전 블로그에 가장 첫글입니다.
다시 해당 자료를 보면서 부족한 부분이 있다면 추가해서 작성해였습니다.
Mutex, Semaphore?
프로세스들은 병렬 프로그래밍, 다중 프로그래밍에 의해 병렬적 또는 병행적으로 실행됩니다.
하지만 프로세스간 메시지 전송 또는 공유 메모리를 통해 공유된 자원에 여러개의 프로세스가 동시에 접근하면 임계영역(Critical Section)문제가 발생한다.
Mutex, Semaphore 모두 이러한 임계영역 문제를 해결하기 위한 동기화 기법이다.
여기서 생소한 개념을 알고가야할 단어가 병렬, 병행 그리고 임계영역(Critical Section)입니다.
먼저 병렬과 병행의 차이에 대해 정확히 알고계시나요? 애매하다면 다시 한번 보세요.
병렬과 병행
Parallelism (병렬)
병렬은 두 개 이상의 작업이 동시에 진행되며, 각 작업은 물리적으로 독립적으로 실행되는 상태를 가리킵니다.
예를 들어 최근에는 멀티 코어 CPU로 여러 작업에 각 코어로 분산시켜서 동시에 작업합니다. 이러한 물리적으로 여러작업이 동시에 실행되는 것을 의미합니다.
Concurrency (병행)
병행은 두 개 이상의 작업이 동시에 진행되지만, 실제로는 동시에 실행되지 않고 소프트웨어적으로 작업들이 번갈아가며 실행되는 상태를 가리킵니다.
이 또한 예로 CPU가 하나의 코어만을 가지고 있고 여러작업을 수행해야할때 한 프로세스만을 점유하고 있다면 다른 프로세스들은 작업을 수행할수 없기 때문에 소프트웨어적으로 작업을 번갈아가며 수행하게 함으로써 작업이 동시에 실행되는 것 처럼 보이게 여러 프로세스를 교차 수행하게 됩니다.
두번째로 임계영역(Critical Section)입니다.
임계영역이란 멀티스레드 또는 멀티프로세스 환경에서 여러 스레드 또는 프로세스가 동시에 접근해서는 안 되는 공유 자원(데이터 또는 자료구조)에 대한 코드 영역을 말합니다.
do{
entry section // 1.진입 구역
critical section // 2.임계 구역
exit section // 3. 출구 구역
remainder section // 4.잔류 구역
}while(true);각 프로세스는 임계구역에 진입하기전에 허가를 받아야합니다.
이러한 허가를 요청하는 코드를 진입구역 (entry section) 이라고 하며 허가를 받아 임계구역(critical section)을 실행한 다음에는 다른 프로세스들이 진입할수 있도록 해주여야하는데 이것이 출구 구역(exit section)이라고 합니다.
나머지 진입구역, 임계구역, 출구구역이 아닌 코드의 부분을 잔류 구역(remainder section)이라고 합니다.
이러한 임계 구역을 해결하기 위한 매커니즘은 다음과 같습니다.
- 한 프로세스가 임계 구역에서 실행하고 있다면 어떤 프로세스도 임계구역에 진입할수 없어야 함
- 임계구역을 실행하고 있는 프로세스가 없을때 프로세스가 임계구역으로 진입하고자 할때 이들의 진입 순서는 이들에 의해 결정되어야 하며 또한 이러한 선택이 무한정 연기되서는 안됨.
- 다른 스레드가 임계 영역내에 없을때는 바로 진입할수 있어야함
- No DeadLock , No Starvation
여기서 DeadLock과 Starvation에 대한 정리가 필요할것 같습니다.
DeadLock
데드락은 두 개 이상의 프로세스 또는 스레드가 서로가 가지고 있는 자원을 점유하고, 각각이 다른 프로세스가 가지고 있는 자원을 기다리는 상태에 빠져 더 이상 진행하지 못하는 상태를 말합니다. 이 상태에서는 각 프로세스가 다른 프로세스가 가진 자원을 해제 해야만 진행이 가능하지만, 모든 프로세스가 서로가 가진 자원을 계속 기다리기 때문에 무한히 기다리는 상태가 발생합니다.
Starvation
Starvation은 특정 프로세스나 스레드가 항상 다른 프로세스나 스레드에 비해 우선순위가 낮아서, 항상 처리가 뒤로 미뤄지거나 실행되지 않는 상태를 말합니다. Starvation은 특정 프로세스가 공정하게 자원을 얻지 못하거나, 계속해서 우선순위가 높은 다른 프로세스에게 밀려 실행이 뒤로 미뤄지는 상태입니다.
Mutex(뮤텍스)
동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 기법입니다.
한 쓰레드, 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제기법
예로 들수 있는것이 식당 화장실 키입니다. 이렇게 lock과 unlock를 사용하는 매커니즘을 사용하기 때문에 이진 세마포어(0,1)이라고 부르기도 합니다.
이러한 뮤텍스 기법의 알고리즘은 다음과 같습니다.
- Dekker(데커) Algorithm
- flag와 turn 변수를 통해 임계구역에 들어갈 프로세스/스레드를 결정하는 방식
- flag : 프로세스중 누가 임계구역에 진입할것인지를 나타내는 변수
- turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수
- flag와 turn 변수를 통해 임계구역에 들어갈 프로세스/스레드를 결정하는 방식
- Peterson(피터슨) Algorithm
- Dekker algorithm과 유사하지만 상대방 프로세스/스레드에게 진입 기화를 양보하는것의 차이
- Backer(베이커리) Algorithm
- 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘
- 가장 작은수의 번호표를 가지고 있는 프로세스가 임계구역에 진입합니다.
Semaphore(세마포어)
Semaphore는 다익스트라가 고안한 두개의 원자적 함수(wait(P), signal(V))로 조작되는 정수 값(공유 자원의 개수)과 wating queue을 가진 객체입니다.
임계영역 에 대한 접속을 제어하기 위하여 최대 허용치 만큼 접근 요청을 가능케하며 세마포어의 카운트가 0이 될시 락이 실행되는 기법입니다.
여기서 세마포어의 정수값에 대한 수정은 원자적으로 실행되어야 합니다. 즉, 한 프로세스가 세마포어의 정수값을 수정하면 다른 프로세스가 동일한 세마포어의 값을 동시에 수정할수 없습니다.
보통 카운팅 세마포어와 이진 세마포어로 구별하며 여기서 이진 세마포어는 뮤텍스와 비슷하게 동작합니다.
동작과정
리소스를 사용하려는 각 프로세스는 세마포어에서 wait 작업을 수행(카운트 값 감소) 프로세스가 리소스를 해제할시 signal 작업을 수행(카운트 값 증가) 여기서 카운트 값이 0이 된다면 모든 리소스가 사용되고 있다는것입니다.
- busy waiting이 있는 세마포어의 경우에는 세마포어의 값이 음수가 되지 않습니다. 그러나 busy wating이 없는 세마포어의 경우 세마포어의 값이 음수가 될수 있으며, 음수이면 이것은 세마포어를 기다리는 프로세스의 수를 나타냅니다.
void semWait(semaphore s){
s.count--;// count 감소
if(s.count < 0){ // count가 음수라면
/*
place this process in s.queue; (세마포어 대기 큐로 옮김)
block this process (현재 실행중인 스레드는 여기서 실행중단 나중에 다른
스레드가 semSignal을 호출하면 깨어남
*/
}
call.scheduler();
}
void semSignal(semaphore s){
s.count++;// count 증가시키고 대기 큐에서 기다리는 스레드가 있을경우 하나를 깨워줌
if(s.count <= 0){
/*
remove a process P from s.queue;(레디큐에서 기다리던 스레드중 맨 처음
place process P on ready list; 것을 레디큐로 옮김 -> 스레드 깨움)
*/
}
}
Mutex(뮤텍스)와 Semaphore(세마포어)의 차이
- 세마포어는 공유 자원에 세마포어의 count 값의 크기만큼 프로세스/스레드가 접근할수있습니다(1개 이상). 반면 뮤텍스는 오직 1개의 프로세스/스레드만 접근 할수 있습니다.
- 세마포어는 소유할수 없는 반면 뮤텍스는 소유가 가능함,
- 세마포어는 시스템 범위에 걸쳐있고 파일 시스템상 파일 형태로 존재 합니다. 반면 뮤텍스는 프로세스 범위를 가지며 프로세 스가 종료될때 자동으로 Clean up 된다.
- 뮤텍스는 락을 획득한 프로세스가 그락을 해제해야 하지만 세마포어는 이러한 세마포어를 소유하지 않은 프로세스가 세마포어를 해제 할수 있습니다.