운영체제 - 상호배제와 동기화(뮤텍스,TAS,세마포어,모니터)

2019/07/28 - [운영체제] - 운영체제 - 병행 프로세스란?

운영체제 - 병행 프로세스란?

 

이전 포스팅에서 병행 프로세스에 대해 간단히 개념을 다루어보았는데, 병행 프로세스에서 꼭 해결해야할 것 중 하나가 공유 자원에 대한 상호배제(동기화)였다. 오늘은 이런 상호배제에 대한 내용을 다루어볼 것이다.

 

상호배제의 개념

상호배제는 병행 프로세스에서 프로세스 하나가 공유 자원을 사용할 때 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법이다. 즉, 공유 자원에 있는 데이터에 접근하는 다른 프로세스를 이미 사용중인 프로세스 하나가 해당 데이터에 접근할 수 없게 하는 것을 상호배제(Mutual exclustion,Mutex)라고 한다. 물론 읽기 연산은 공유 데이터에 동시에 접근해도 문제가 발생하지 않지만, 변수나 파일은 프로세스 별로 하나씩 차례로 읽거나 쓰도록 해야한다. 예를 들면 하나의 프로세스가 순차적으로 파일을 읽는 작업을 하는 도중에 다른 프로세스가 파일의 내용을 변경해버리면 읽어오는 값이 예상과 다를 수 있기에 이러한 상황을 제어하는 동기화 작업이 필요한 것이다.

 

 

예를 들어 위의 그림에서 Thread A가 파일 쓰기 작업을 진행 중이다. 하지만 작업 도중에 Thread B가 파일을 읽기 위해 접근한다면 Thread B는 읽기 작업을 하지 못하고 대기하게 된다. 여기서 해당 파일(공유자원)을 가지고 주무르는 작업(코드)을 임계영역이라고 하고 먼저 해당 자원을 사용하는 임계코드를 실행중인 Thread A는 Lock(열쇠)을 손에 쥐게 된다. 그리고 그 이후에 Thread B가 접근하면 해당 스레드는 이미 Thread A가 Lock(열쇠)을 손에 쥐고 있기 때문에 임계영역에 접근할 수 없고 대기하게 되며 추후에 Thread A가 Lock(열쇠)를 반환하면 그때서야 Thread B가 임계영역에 진입할 수 있게 되는 것이다.

 

여기서 특징은 상호배제(Mutex)의 특징이 나온다. 바로 해당 자원에는 한순간 하나의 프로세스만 접근할 수 있기 때문에 Lock은 딱 한 프로세스에게만 쥐어주는 것이다. 또한 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단하는 것을 알 수 있다.

 

<상호배제의 조건>

1. 두 프로세스는 동시에 공유 자원에 진입할 수 없다.
2. 프로세스의 속도나 프로세서 수에 영향을 받지 않는다.
3. 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있다.
4. 프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안 된다.

 

여기서 임계영역은 어떤 전역 변수일 수도 있고 입출력을 위한 버퍼가 될 수도 있다. 이러한 임계영역을 이용하여 효과적으로 상호배제를 구현할 수 있는 것이다.

 

상호배제 방법들

상호배제를 해결하는 다양한 방법이 있다. 아래 표에는 상호배제를 구현하는 방법들을 정리해 놓은 것이다.

 

수준	방법	종류
고급	소프트웨어로 해결	데커 알고리즘 크누스 알고리즘 램포트의 베이커리 알고리즘 핸슨 알고리즘 다익스트라 알고리즘
	소프트웨어가 제공 : 프로그래밍 언어와 운영체제 수준에서 제공	세마포어 모니터
저급	하드웨어로 해결	TestAndSet(TAS)

 

모든 것을 다 다루어 보지는 않을 것이다. 몇 가지만 살펴보자.

 

<데커 알고리즘>

데커 알고리즘은 병행 프로그래밍의 상호배제 문제를 풀 수 있는 첫 번째 해결책으로 알려졌다. 두 프로세스가 동시에 임계영역에 진입하려고 시도하면 순서에 따라 오직 하나만 임계영역에 들어가도록 허용한다. 데커 알고리즘에서 각 프로세스는 플래그를 설정할 수 있고, 다른 프로세스를 확인한 후 플래그를 재설정할 수도 있다. 프로세스가 임계 영역에 진입하고 싶으면 플래그를 설정하고 차례를 기다린다. 즉, 임계 영역에 다른 프로세스가 이미 있으면 해당 프로세스를 종료할 때까지 while 문에서 순환한다. 여기서는 임계 영역 진입, 두 프로세스 간의 순서를 나타내는 turn 변수를 입력했다는 의미로 flag[0] 플래그와 flag[1] 플래그를 사용한다. 간단한 코드로 살펴보자.

 

======================데커 알고리즘 간단한 코드=========================
flag[0]=false;
flag[1]=false;
turn=0;

===================프로세스 P0 임계 영역 진입 코드=======================
//프로세스 P0의 임계 영역 진입 절차
flag[0]=true; //P0의 임계 영역 진입 표시
while(flag[1]==true){ //P1의 임계 영역 진입 여부 확인
	if(turn==1){ //P1이 임계영역에 진입할 차례가 되면
    	flag[0]=false; //플래그를 재설정하여 P1에 진입 순서 양보
        while(turn==1){ //P0이 임계영역에 진입할 차례가 될 때까지
        	//프로세스 P0의 바쁜 대기
        }
        flag[0]=true; //P1이 임계 영역에 진입할 차례가 되면 플래그 값 변경
    }
}

/*임계 영역 코드*/
turn=1; //임계 영역 코드 수행 이후 P1에게 진입 turn을 양보.
flag[0]=false;
/*나머지 코드 수행부분*/

===================프로세스 P1 임계 영역 진입 코드=======================
//프로세스 P1의 임계 영역 진입 절차
flag[1]=true;
while(flag[0]==true){
	if(turn==0){
    	flag[1]=false;
        while(turn==0){
        	//프로세스 P1의 바쁜 대기
        }
        flag[1]=true;
    }
}

/*임계 영역 코드*/
turn=0; //임계 영역 코드 수행 이후 P0에게 진입 turn을 양보.
flag[1]=false;
/*나머지 코드 수행부분*/
======================데커 알고리즘 간단한 코드=========================

 

상호배제 문제를 소프트웨어적으로 해결하는 데커 알고리즘의 특징

• 특별한 하드웨어 명령문이 필요 없다.
• 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계 영역에 들어가려는 것을 막지 않는다.
• 임계 영역에 들어가기를 원하는 프로세서를 무한정 기다리게 하지 않는다.

 

<TestAndSet(TAS) 명령어>

공유 변수를 수정하는 동안 인터럽트 발생을 억제하여 임계 영역 문제를 간단하게 해결할 수 있지만, 이 방법은 항상 적용할 수 없고 실행 효율이 현저히 떨어진다. 또 소프트웨어적인 해결책은 더 복잡하고 프로세스가 2개 이상일 때는 더 많이 대기할 수 있다. 메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있는 하드웨어 명령이 TAS를 이용하여 간단한 방법으로 임계 영역 문제를 해결할 수 있다.

 

//target을 검사하고 target 값을 true로 설정
boolean TestAndSet(boolean *target){
	boolean temp=*target;
    *target=true;
    return temp;
}

//전역변수 영역(프로세스들의 공유변수들)
boolean waiting[n]; //배열을 선언함으로써 프로세스가 2개 이상와서 대기할 수 있도록 한다.
boolean lock=false;
int j; //0..n-1
boolean key;

do{ //프로세스 Pi의 진입 영역
	waiting[i]=true
    key=true;
    while(waiting[i]&&key){
    	key=TestAndSet(&lock);
    }
    waiting[i]=false;
    /*임계영역*/
    /*탈출영역*/
    
    j=(i+1)%n;
    while((j!=i)&&!waiting[j]){ //대기 중인 프로세스를 찾음
    	j=(j+1)%n;
    }
    if(j==i){ //대기 중인 프로세스가 없다면
    	lock=false; //다른 프로세스의 진입 허용
    }else{ //대기 중인 프로세스가 있으면 다음 순서로 임계 영역에 진입
    	waiting[j]=false; //Pj가 임계 영역에 진입할 수 있도록
    }
    //나머지 영역
}while(true);

 

프로세스 Pi의 진입 영역에서 waiting[i]가 true이므로 Pi는 임계 영역에 들어가려고 시도한다. 처음에 lock을 false로 초기화했다. 그러므로 임계 영역에 들어가는 첫 번째 Pi 프로세스는 TestAndSet(&lock)으로 key가 false가 되어 while문을 벗어 나게 되어 임계 영역을 진행한다. lock은 TestAndSet(&lock)으로 true가 되므로 다른 프로세스의 임계 영역 진입 코드의 while 문에서는 key가 true이기에 계속 while문에서 대기하게 된다. Pi가 임계 영역에 들어가기 전에 waiting[i]는 false로 설정하고 임계 영역으로 진입한다. 여기서 중요한 것은 lock이 true가 되어 다른 프로세스의 임계 영역 진입 코드의 while문에서 key가 true로 계속 반환되어 while 문에 머물고 있는 것을 기억해야한다.

Pi가 임계 영역을 떠날 때는 대기 프로세스 중에서 다음으로 진입할 수 있는 프로세스를 선택해야 한다. j=(i+1)%n; 코드로 차례가 높은 프로세스를 선택한 후 다음 while 문에서 각 프로세스를 검사한다. waiting 배열을 i+1,i+2,...n-1,0 순서로 조사하여 waiting 값이 true인 첫 번째 프로세스가 임계 영역으로 진입할 다음 프로세스가 된다.(임계 영역에 진입하기 위해 대기하는 프로세스는 임계 영역 초반 waiting[i]가 true가 된 상태로 while 문에서 대기중) 만약 대기 중인 프로세스가 없다면 lock을 false로 해제하고, 다음 프로세스가 Pj이면 임계 영역에 진입할 수 있도록 Pi는 waiting[j]를 false로 변경한다.(waiting[j]를 false로 변경하면 임계 영역을 진입하기 위해 대기중인 Pj가 while(waiting[j]&&key)에서 벗어 나게 되고 임계영역으로 진입한다.)

 

TestAndSet 명령어의 장단점

 

장점	사용자 수준에서 가능하다. 메인 메모리를 공유하는 다중 프로세서나 단일 프로세서에서 프로세스 수에 관계없이 적용할 수 있다. lock 변수 수에 상관없이 구현할 수 있다. 구현이 단순하고 확인이 용이하다. 다중 임계 영역을 지원한다.
단점	-바쁜 대기 발생 프로세서 시산 소모가 크다. 대기 프로세스는 비생산적, 자원이 소모되는 대기 루프에 남는다. -기아 상태 발생 : 프로세스가 임계 영역을 떠날 때 프로세스 하나 이상을 대기하는 경우가 가능하다. -교착 상태 발생 : 플래그는 우선순위가 낮은 프로세스가 재설정할 수 있지만, 우선순위가 높은 프로세스가 선점한다. 따라서 우선순위가 낮은 프로세스는 lock을 가지고, 우선순위가 높은 프로세스가 이것을 얻으려 시도할 때 높은 우선순위 프로세스는 무한정 바쁜 대기가 될 것이다.

 

<세모포어,semaphore>

앞서 제시한 상호배제의 해결 방법들은 좀 더 복잡한 문제에서는 일반화하기 어렵다. 또 프로세스가 임계 영역에 진입할 수 없을 때는 진입 조건이 true가 될 때까지 반복적으로 조사하고 바쁜 대기를 하게 되어 프로세스를 낭비한다. 진입 조건을 반복 조사하지 않고 true일 때 프로세스 상태를 확인한다면 프로세서 사이클을 낭비하지 않을 것이다. 다익스트라가 제안한 세모포어라는 동기화 도구는 상호배제 이외에도 다양한 연산의 순서도 제공한다.

 

세모포어는 값이 음이 아닌 정수인 플래그 변수이다.(음수 값을 가질 수 있는 세마포어는 음수 값을 할당하여 대기 중인 프로세스 갯수를 알고 처리하는 방법이 있다고는 하는데..음수가 되는 순간 해당 프로세스는 대기큐에 넣은 후에 S가 0보다 커지는 순간 대기큐에서 가져와 임계영역 코드를 수행시키는 원리.) 또한 P와 V 연산과 관련되어 있고 세마포어를 의미하는 S라는 변수를 갖는다. 임계 영역에 진입하는 프로세스는 P연산(wait)을 수행하여 S>=0이라면 S값을 하나 감소시키고 임계영역에 들어가고 만약 S<=0이라면 S값을 하나 감소시키고(S값이 음수로 된다) 대기큐로 들어간다.(지속적으로 S>=0일때가지 반복문을 도는 것이 아니라 대기 큐에 들어가 멈춰있는 상태-sleep가 된다. 바쁜 대기 문제 해결) 그리고 임계영역의 코드를 모두 수행하면 V연산(signal)로 S값을 하나 증가시키고 S값이 0보다 커지면 대기큐에서 sleep 중인 프로세스를 깨우는 행동을 하게 된다.

 

<Info>

음수 값을 가질 수 없는 세마포어는 뮤텍스와 같이 바쁜대기가 발생한다. 하지만 음수를 가지는 세마포어는 대기큐에 프로세스를 중단시킨 상태로 넣어놓으니 바쁜 대기가 발생하지 않는다.

바쁜 대기 : 자원을 사용할 수 있는 상태인지 반복해서 체크

 

P,V 연산은 운영체제가 실행하고, 임의의 프로세스가 시스템 호출을 하는 것이다.

 

P(S) : wait(S){
		S -> count--;
	    if(S -> count < 0) {
        	add this process to S -> queue; //프로세스를 준비 큐에 추가
            block(); //프로세스 중단(일시정지)
		}
	   }
       
V(S) : signal(S){
       		S -> count++;
            if(S -> count > 0){
            	remove a process P from S -> queue; // 준비 큐에서 P 프로세스 제거
                wakeup(P); //신호를 보내 프로세스를 실행
            }
	   }

 

P와 V 연산에 있는 세마포어 S의 정수 값 변경은 개별적으로 실행하고, 누군가가 이 연산을 수행하고 있다면 다른 프로세스는 해당 연산을 수행할 수 없다. 즉, P,V 연산이 다른 프로세스들이 동시에 할 수 없도록 조정해야한다. 여기서 일반 상호배제(뮤텍스)와는 조금 다른 것이 S값을 1보다 큰 값으로 초기화하여 여러 프로세스가 동시에 임계 영역을 진입하게 할 수 있다는 것이다.(S값만큼 공유 영역을 만들어서 각각의 공유 영역에 서로 다른 프로세스를 통과시킬 수 있다.)

 

즉, S가 1로 초기화된다면 바이너리 세마포어, S가 1보다 크다면 계수형 세마포어가 된다. 밑의 그림은 계수형 세마포어가 된다.

 

그렇다면 세마포어와 뮤텍스의 차이점을 무엇일까? 기본적인 차이점을 세마포어는 시그널링 메커니즘이라는 것이다. 즉, 프로세스는 wait() 및 signal() 작업을 수행하여 자원 획득 또는 해제여부를 나타낸다. 뮤텍스는 잠금 메커니즘이며, 프로세는 Lock을 획득해야한다. 아래는 세마포어와 뮤텍스의 차이점을 정리해 놓은 표이다.

 

세마포어	뮤텍스
세마포어는 시그널링 메커니즘이다.	뮤텍스는 잠금 메커니즘이다.
세마포어는 정수 변수이다.	뮤텍스는 Object이다.
세마포어는 여러 프로세스가 여러 유한한 자원에 액세스할 수 있게 한다.	뮤텍스는 여러 프로세스가 단일 리소스에 액세스할 수 있지만 동시에 수행할 수 없게 한다.
세마포어 값은 자원을 얻거나 해제하는 프로세스에 의해 변경 될 수 있다.	뮤텍스 Lock은 반드시 획득한 프로세스에 의해서만 해제된다.
세마포어는 계수형(count) 세마포어와 바이너리 세마포어로 분류된다.	더 이상의 분류는 없다.
세마포어 값은 wait() 및 signal() 연산을 사용하여 수정된다.	리소스를 요청하거나 해제하는 프로세스에 의해 Lock&Unlock이 된다.
모든 리소스가 사용 중이면 리소스를 요청하는 프로세스는 wait() 작업을 수행하고 대기큐에 들어가 있으면서 세마포어 값이 1이상이 될때 다른 프로세스에 의해 wakeup한다.	Lock이 걸려있으면 Lock의 소유 프로세스가 잠금을 풀때까지 프로세스가 대기하고 있는다(바쁜 대기)

 

<모니터>

세마포어는 상호배제와 프로세스 사이를 조정하는 유연성 있고 강력한 도구이지만 wait&signal 연산 순서를 바꿔 실행하거나 둘 중 하나 이상을 생략하면 상호배제를 위반하거나 교착 상태가 발생한다. wait과 signal 연산이 프로그램 전체에 퍼져 있고 이들 연산이 각 세마포어에 주는 영향을 전체적으로 파악하기가 쉽지 않기에 세마포어를 잘못 사용하면 여러 가지 오류가 쉽게 발생하여 프로그램을 작성하기가 어렵다. (즉, 타이밍 문제가 발생할 수 있다.)모니터는 이러한 단점을 극복하려고 등장하였다.

 

모니터의 개념과 구조

모니터는 프로그래밍 언어 수준에서 제공해준다. 모니터를 사용하여 상호배제를 하는 예제로는 Java 언어가 있다.

 

 

프로세스들은 모니터의 프로시저를 호출하여 모니터 안에 진입한 후 지역(공유) 데이터에 접근할 수 있다. 무엇보다 언제나 한 번에 프로세스 하나만 모니터에 진입할 수 있도록 제한하여 상호배제를 실현한다는 것이 중요하다. 만약 다른 프로세스가 모니터를 점유하고 있으면 프로세스는 외부의 모니터 준비 큐에서 진입을 기다리게 되어 상호배제를 실현한다. 위에서 초기화 코드는 모니터를 생성할 때 한번 사용된다.

 

또한 중요한 개념중 하나가 조건 변수이다. 특정 조건이 부합하지 않아 모니터 실행 도중 cwait(c1)을 호출한 프로세스는 모니터 내부의 조건 c1 준비큐에 들어가 대기한다. 그리고 새로운 프로세스가 모니터 안에서 수행을 진행하고 해당 프로세스가 c1.signal을 호출하면 c1 대기 큐에 있던 프로세스가 중단되어 있다 다시 실행하러 들어온다. 즉, 단순히 세마포어처럼 signal 연산을 보내는 것이 아니라 특정 조건 대기큐에 대한 signal을 보내 작업을 시작시키는 것이다.

 

예를 들어 프로세스 하나가 모니터 내부에서 임계영역 코드를 수행하고 c1에 시그널을 보내면 모니터 내부에 있는 c1 준비큐에서 프로세스 하나가 나와 임계영역 코드에 진입하고, 만약 조건 signal을 보내지 않고 빠져 나온다면 외부에 있는 큐중에 한 프로세스를 꺼내어 임계영역에 진입시킨다. 물론 c1 시그널을 보냈는 데 c1에 대기하고 있는 프로세스가 없다면 아무런 효과가 없어 외부에 있는 대기 큐에서 프로세스를 꺼내온다.

 

Java의 wait(),notify(),notifyAll()이 모니터를 사용하기 위한 조건 변수라고 볼 수 있다. 모니터 내부에서 wait()을 호출하면 모니터 내부에 있는 WaitSet에 들어가 중단된 상태로 대기하고 있는 상태가 되는 것이고 누군가가 notify(),notifyAll()을 호출하면 모니터 내부에 있는 WaitSet에 있는 프로세스중 하나를 실행상태로 만들어주는 것이다. 물론 synchronized가 걸려 모니터 내부에 들어오지 못한 프로세스(스레드)들은 EntrySet이라는 외부 준비큐에 들어가 있는 상태가 되는 것이다.

 

 

 

-참조

Difference Between Semaphore and Mutex (with Comaprison Chart) - Tech Differences

 

Difference Between Semaphore and Monitor in OS (with Comparison Chart) - Tech Differences