프로세스들은 병렬 프로그래밍, 다중 프로그래밍에 의해 병렬적 또는 병행적으로 실행됩니다. 하지만 프로세스간 메시지 전송 또는 공유 메모리를 통해 공유된 자원에 여러개의 프로세스가 동시에 접근하면 임계영역(Critical Section)문제가 발생한다.

Critical Section(임계 영역), 공유 변수 영역

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 블록입니다. 즉 둘이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부

만약 어떤 스레드가 임계 영역에 들어가야 한다면

이를 위해서 Mutex(뮤텍스), Semaphore(세마포어) 방식을 사용하며 각자 서로 다른 방식으로 임계영역 문제를 해결합니다.

임계 구역이 포함된 프로세스의 일반 구조

do{
		entry section //1
		critical section //2
		exit section //3
		remainder section //4

}while(1);

각 프로세스는 임계 구역에 진입하기전에 허가를 받아야합니다. 이허가를 요청하는 코드를 1. 진입 구역(entry section) 이라고 하며 허가를 받아 2. 임계구역(critical section)을 실행한 다음에는 다른 프로세스들이 진입할수 있도록 해주어야하는데 이것이 3. 출구 구역(exit section)이라고 합니다.

나머지 진입구역, 임계구역, 출구 구역이 아닌 코드 부분을 4.잔류 구역(remainder section)이라고 합니다.

임계 구역 문제를 해결하는 매커니즘은 다음과 같은 요건을 충족해야합니다.

  1. 한 프로세스가 임계 구역에서 실행하고 있다면 어떤 프로세스도 임계구역에 진입할수 없어야함
  2. 임계구역을 실행하고 있는 프로세스가 없을때 프로세스가 임계구역으로 진입하고자 할때 이들의 진입 순서는 이들에 의해 결정되어야 하며 또한 이러한 선택이 무한정 연기되서는 안됩니다.
  3. 다른 스레드가 임계 영역내에 없을때는 바로 진입할수 있어야함
  4. No DeadLock , No starvation

Mutex(뮤텍스)

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

임계영역을 가진 스레드들의 실행시간이 서로 겹치지 않고 단독으로 실행 되도록 하는 기술입니다.(상호 배제, Mutual Exclution)

한 프로세스가 소유한 Key를 기반으로 한 상호 배제 기법으로써 Locking 매커니즘으로 오직 하나의 쓰레드만이 동일한 시점에 key에 해당하는 뮤텍스 객체를 얻어 그 객체를 소유한 스레드, 프로세스만이 임계영역(공유 자원)에 접근할수있습니다.(Lock) 공유 자원을 마치면 락을 반납(Unlock)

ex) 식당 화장실 키

이렇게 lock과 unlock을 사용하는 매커니즘을 사용하기 때문에 이진 세마포어(0, 1)라고 부르기도 합니다.

뮤텍스 알고리즘

  • Dekker(데커) Algorithm
    • flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식
      • flag : 프로세스중 누가 임계구역에 진입할것인지 나타내는 변수
      • turn : 누가 임계 구역에 들어갈 차례인지 나타내는 변수
  • Peterson(피터슨) Algorithm
    • 데커 알고리즘과 유사하지만 상대방 프로세스/ 스레드에게 진입 기회를 양보하는것에 차이
  • Bakery(베이커리) Algorithm
    • 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘
    • 가장 작은수의 번호표를 가지고 있는 프로세스가 임계구역에 진입합니다.

Semaphore(Signaling mechnism)

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,Semaphore1.png

ex) Producer/Customer (생산자 소비자 문제)

여러 스레드가 동시 접근 가능한 Queue를 구현하는 문제

Producer 스레드(서버의 TCP, UDP 수신 thread)가 네트워크에서 client의 request 메시지를 받아 큐에 넣게 되면 customer의 스레드들(request 처리)이 큐에서 데이터를 빼 요청한 request를 처리하고 client에게 결과를 전송합니다.

이를 위해 thread들이 큐에 데이터를 넣고 뺄수 있어야함

  • queue는 원형큐

한순간에 오직 하나의 스레드 만이 큐에 접근할수 있음

  • 동시에 여러 스레드가 큐에 접근하면 순서적으로 접근할수 있게 해야함

Producer 스레드들은 큐가 가득찬 경우 빈 공간이 생길때까지 대기해야하며 customer 스레드는 큐가 비어있는 경우에는 데이터가 들어올때까지 대기해야함

Mutex,Semaphore2.png ex) 철학자들의 식탁

뮤텍스와 세마포어의 차이

세마포어는 공유 자원에 세마포어의 count 값의 크기만큼 프로세스/스레드가 접근할수있습니다. 1개 이상

반면 뮤텍스는 오직 1개의 프로세스/스레드만 접근 할수 있습니다.

세마포어는 소유할수 없는 반면 뮤텍스는 소유가 가능함, 세마포어는 시스템 범위에 걸쳐있고 파일 시스템상 파일 형태로 존재합니다. 반면 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될때 자동으로 Clean up 된다.

또한 뮤텍스는 락을 획득한 프로세스가 그락을 해제해야 하지만 세마포어는 이러한 세마포어를 소유하지 않은 프로세스가 세마포어를 해제 할수 있습니다.