[OS] 5. 동기화(세마포, 뮤텍스)

※본 포스팅은 공부목적(https://develaniper-devpage.tistory.com/77)에 따라 해당 블로그와 깃허브를 참조하여 제작된 포스팅 입니다.

1. 동기화

1) 경쟁상황( race condition )

 여러개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 말한다.

 이런 경우에 동일한 자료에 대한 접근을 제한하여 접근 순서에 관계없이 항상 일관적인 결과를 도출 할 수 있도록 해야한다.

 이렇게 같은 자원에 대해서 한번에 한 프로세스 혹은 쓰레드만 작업을 허용하는 것을 동기화라고 한다.

 2) 임계구역(Critical Section)

  공유자원이 접근하는 코드를 말한다. 각 프로세스 또는 쓰레드가 공유자원에 값을 변경하는 코드의 영역으로 둘 이상의 프로세스 혹은 쓰레드가 동시에 접근하면 안되는 영역이다.

3) 임계구역 문제

 임계구역으로 지정되어야 할 코드 영역이 지정되지 않았을 때 발생할 수 있는 문제이다.

4) 임계구역 문제 해결조건

 임계구역 문제를 해결하기 위해서는 3가지 조건을 모두 충족해야한다.

1. 상호배제(Mutual Exclusion)
   • 임계구역 내에서 실행되는 프로세스(쓰레드)는 단 하나의 프로세스(쓰레드)이다.
2. 진행(Progress)
   • 임계구역에 들어가려는 프로세스(쓰레드)가 다수라면 어느것이 먼저 들어갈 지 결정한 후 들어가야한다.
3. 한정된 대기(Bounded wating)
   • 기아상태를 방지하기 위해서는 이미 임계구역을 사용한 프로세스(쓰레드)가 다시 임계구역에 접근하려면 제한이 있어야한다.(시간/순서)
   • 즉, 진입 가능한 횟수 제한이 있다는 것이다.
   • 진행과 다른점은 이미 임계구역에 접근한 적이 있는 적이 있는지의 여부이다.

 5) 피터슨 해결안

 두개의 프로세스에 대한 소프트웨어 기반의 바쁜대기(Busy wating)을 사용하는 임계구역 문제 해결책이다.

피터슨 해결안은 두 프로세스가 공유하는 자원이 필요하다.

int turn;
bool flag[2];

변수 turn은  임계 구역으로 진입할 순번을 나타낸다. 즉, 프로세스를 P0, P1로 설정하면 turn==0 일때 P0가 들어갈 수 있는 순번이고 turn==1이면 P1이 들어갈 수 있는 순번인 것이다.

flag배열은 각 인덱스(0, 1) 프로세스가 진입할 준비가 됐는지를 나타낸다. 즉, flag[0]==true일 경우 P0가 임계구역에 들어갈 준비가 된 상태를 말한다.

do{
	flag[i] = true;
	turn = j;
	while(flag[j] && turn==j);	// 무한 대기
	//=========================
	// 만일 j가 진행중이 아니면 flag[j]==false이기 때문에 바로 넘어 온다.
	// 혹은 turn==i일 경우 j가 i보다 늦게 들어왔거나 나간 상태이기 때문에 임계구역에 들어올 수 있다.
	// 임계구역
	//
	//=========================
	flag[i] = false;	// 임계구역에서 작업을 마치면 준비상태를 false로 바꿔준다.
}while(TRUE);

-증명

1. 상호 배제
   • while문을 빠져 나가려면 flag[j]==false 혹은 turn==i 여야 한다. turn은 0혹은 1 중 하나의 값만 가질 수 있기 때문에 동시에 진입했을 때 둘중 하나만 루프를 빠져 나갈 수 있다.
2. 진행에 대한 요구 조건을 만족(어느것이든 들어가야한다.)
   • i입장에서 보면 flag[j]의 기본 값은 false이며 j가 임계구역에서 빠져나오면서 flag[j]=false로 바꾸고 나오기 때문에 j가 임계구역에 들어간 적이 없어도, 있어도 flag[j]==false조건을 만족시켜 진행이 될 수 있다.
3. 대기 시간이 한 없이 길어지지 않는다
   • turn==j이면서 flag[j]==true일 때 j가 임계구역을 사용중이므로 i는 while문에서 대기하게 된다. 이때 while문을 빠져 나오려면 j가 임계구역 사용 후 flag[j]를 false로 바꿔야 한다.
   • 혹시라도 j가 임계구역을 빠져나와 다시한번 while문을 실행한다 해도 j는 turn을 i로 바꾸고 while문을 실행하기 때문에 i가 flag[i]=true로 바꾸고 들어 왔기 때문에 j 입장에서는 turn이 j가 아니면 임계구역을 실행하지 못한다.
   • i 또한, while문을 돌면서 임계구역을 사용하기 전에 turn을 바꿀 수 없기 때문에 무한한 대기시간이 생기지 않는다.

2. 세마포(Semaphore)-counting semaphore

공유된 자원의 데이터 혹은 임계영역(Critical Section)에 여러 프로세스/쓰레드 가 접근하는 것을 막아주는 동기화 도구이다.

1) 사용법

 세마포 S는 정수형 변수로, 초기화를 제외하고는 오직 wait()와 signal()에 의해서만 접근이 가능하다.

wait(S){
	while(S<=0) ;
	S--;
}
signal(S){
	S++;
}

wait()은 임계구역에 들어가기 전에 S를 확인하며 대기하는 함수로 들어가자 마자 S--로 다른 프로세스/쓰레드의 접근을 막는 함수이다. 피터슨 해결안에서 while(flag[j] && turn==j); 와 같은 역할을 한다.(S가 0보다 클 때 임계구역에 들어갈 수 있다.)

signal은 임계구역을 나왔을 때 기다리고 있는 다른 프로세스/쓰레드가 임계구역에 들어갈 수 있도록 S++로 만든다.

do{
	wait(S);
	// 임계구역
	signal(s);
}while(true);
    

피터슨 해결안의 방법과 유사하게 위와같은 단계에 따라 세마포를 실행할 수 있다.

 

이 방법은 while문을 반복하며 CPU점유율을 차지하는 바쁜대기(Busy Wating)라고 부르며 스핀락(spinlock)이라고 부르기도 한다.(회전하면서 lock이 걸려 있으므로)

 

따라서 , 바쁜대기를 극복하기 위해 wait()와 signal()의 연산을 재정의 할 필요가 있다.

 

(* 여기서는 프로세스, 쓰레드 모두를 대표적으로 프로세스라고 칭하겠다)

다른 프로세스가 임계구역에 들어가고 나머지 프로세스들은 대기상태이다. 따라서 wating을 하는 프로세스들을 대기큐에 넣고, 프로세스의 상태를 대기상태로 만든다.

이후 임계구역에서의 작업이 끝나면 대기 큐에서 하나를 꺼내 wakeup()연산으로 대기상태->준비완료 상태로 변환하고 다시 CPU스케줄링에 따라 프로세스가 실행되면 임계구역에 진입할 수 있게 되는 것이다.

 

따라서 세마포(S)를 다음과 같은 구조체로 정의하며

typedef struct{
	int value;
	struct process *list;
}semaphore;

wait()과 signal()연산은 다음과 같은 형태로 변형시킨다. 이를 Block-wakeup형식이라 할 수 있다.

wait(semaphore *S){
    S->value--;
    if(S->value < 0){	// 0이라면 자신이 들어오기 전에 1이상 즉, 접근 가능 상황
    	block();		// 호출한 프로세스를 대기큐에 넣고 대기상태로 만든다.
    }
}
signal(semaphore *S){
    S->value++;
    if(S->value<=0){	// 자신이 나오면서 임계구역이 사용 가능하면
    	wakeup(P);		// 큐에서 하나 꺼내서 봉쇄된프로세스(P)를 준비->대기상태로 만들어 block()을 푼다.
    }
}

Busy-wait vs Block-wakeup

• Busy-wait 가 유리
  • 임계구역이 짧을 경우 block-wakeup을 할경우 잦은 문맥교환으로 오버헤드가 커질 수 있어 busy-wait방식이 유리하다.
  • SMP시스템의 경우 wait()와 signal()연산이 원자적으로 실행되는 것을 보장해야하기 때문에 스핀락과같은 락킹방법이 필요하다.
  • 다중처리기에서 block-wakeup을 사용하면 모든 인터럽트를 금지해야 하므로 busy-wait가 필요하다.
• Block-wakeup이 유리 
  • 임계구역의 길이가 긴 경우 busy-wait기법은 매우 비효율적이다. 임계구역을 실행할 동안 대기하며 cpu의 점유율을 차지하고 있기 때문이다.

 

교착상태 & 기아

P0가 wait(S)를 통해 S에 대한 임계구역에 들어갔고 P1은 wait(Q)를 통해 Q에 대한 임계구역에 들어갔다. 이상태에서 서로 P0는 Q에대한 P1은 S에 대한 signal을 기다린다면 무한봉쇄 상태에 걸리고, 어떤 작업도 처리되지 못하는 기아상태에 빠질 수 있다.

 

 

3. 뮤텍스(Mutex) - binary semaphore

이진세마포는 상호배제를 제공하는 락이다. 이에따라 이진세마포를 뮤텍스 락이라고 부른다.

 

위 세마포에서 S를 mutex라고 하면 mutex는 초기값이 1이다.

따라서 mutex== 0 일때 프로세스는 무한하게 봉쇄되며, mutex==1이 됐을 때 그 봉쇄가 풀리게 된다.

 

(카운팅)세마포와의 차이는 임계영역에 들어갈 수 있는 수(초기 S값)에 있다.

세마포 vs 뮤텍스

- 뮤텍스

•  뮤텍스는 오직 하나의 프로세스만이 동일한 시점에 뮤텍스를 얻어 임계영역에 진입할 수 있고 오직 이 프로세스로만 뮤텍스를 해제할 수 있다.
• Locking 메커니즘으로 락을 걸고 푸는 장치가 존재한다.

 - 세마포어

• 세마포어는 Signaling메커니즘으로  락을 걸지 않은 프로세스도 signal을 통해 락을 걸 수 있다. 이는 임계영역에 들어갈 수 있는 수가 다수일 수 있기 때문인데 임계영역에서 작업중인 프로세스의 상한선만 지킨다면 누가 나가던 락을 해제할 수 있는 것이다.
• 이진 세마포 또한 locking보다는 signaling 메커니즘으로 생각하는 것이 맞고 카운트를 1로 설정하면 뮤텍스처럼 활용할 수 있다.

※ 세마포는 뮤텍스 처럼 사용할 수 있지만 뮤텍스는 세마포처럼 사용할 수 없다고 한다.

 

 

※ 분명 헷깔리는 부분이 맞다. 2진 세마포를 누군가는 뮤텍스와 같다고 하고 누군가는 역할은 같지만 엄연히 다른 것이라고 한다(필자도 같다고 했다가 아니라고했다가...) 공룡책에도 

이진 세마포가 상호배제를 제공하는 락이기 때문에 뮤텍스 락이라고 부른다.

라는 내용이 있다. 내가 내린 결론은 "I don't give a Fxxx" 이다.

결론적으로 사용법은 같고, 이걸 같다고 해도 다르다고 해도 뭐라할 사람은 없을 것 같다. 다만 내가 이해한 내용을 말하면서 내 생각을 밝히는게 중요한 것 같다.

 

참조

https://galid1.tistory.com/479
https://hibee.tistory.com/297