[OS]Process Synchronization(2)

Semaphore 기법에 대해 좀더 자세히 알아보고 Mutual exclusion 의 다른 기법인 Monitor에 대해 알아 보자

Overview

Semaphore

이전 글에서 세마포어의 기본 개념에 대해 알아 보았다.
세마 포어란 쉽게 말해 프로세스 Synchronization을 위한 int형 변수이다

Semaphore 단점

하지만 이 세마포어도 큰 단점이 존재 하는데 바로 Unstructured Programming Construct 이기 때문에 컴파일러 등의 도구를 사용한 디버깅이 어렵다는 단점이 있다.

structured Programming Construct : if 문을 사용할때 {} 와 같은 괄호를 써줘서 컴파일러가 디버깅 할 수 있는 것을 말한다.

위 소스코드가 세마포어 단점의 한 예 이다.
Producer 와 Consumer 라는 프로세스 두개가 존재 할때, P와 V로 만든 Crtical Section 을 구현한 코드라면 Argument가 같아야하는데 Consumenr 의 Argument가 다르기 이 S2 를 S1으로 고쳐야 하는지 .. 아니면 다른 의도로 만들었다면 Producer의 V(S1)을 V(S2)로 고쳐야 할지 안 방법이 없다.
다시 말해서 이 소스코드를 만든 제작자의 의도가 Critical Section 을 의도 한건지, 아니면 그냥 스케줄링 관점을 의도한 건지 세마포어는 Unstructured Programming Construct 이기 때문에 컴파일러 도구를 사용하여 디버깅을 할 수 없기 때문에 버그가 나기 쉽다.

Semaphore 단점 해결법

P(), V() 라는 API 이름 대신에 mutex_ 를 붙인 API 함수를 사용한다.

기존 Semaphore API는 위 표와 같은 기능을 했다.
기존 lock() , unlock()을 이용하요 Mutual exclusion 을 구현 하려고 할때 mutex_ 를 붙여서 사용한다.
mutex_lock() , mutex_unlock() 을 사용하면 이 함수는 반드시 같은 세마포어를 argument로 받아 Critical section 을 구현해야 한다.
즉 위 소스에서 mutex_ 를 사용 했으므로 Task2의 S2를 S1으로 바꾸면 된다 .

Mutext 가 가진 추가 기능

Mutual Exclusion을 구현하기 위해 사용하는 sleeping Lock
동일한 Mutex를 사용할 때 mutex_lock()을 호출한 프로세스와 mutex_unlock()을 호출한 프로세스가 일치하여야 한다.
동일한 프로세스인지 mutex_ 는 체크하는 기능을 가지고 있다.
즉 문을 닫고 들어간 사람이 문을 열고 나갈 수 있기 때문이다.

Semaphore 구현 방법

세마포어는 int형 정수(0,1 또는 열쇠의 수에 따라 0,1,2 등..)로 표현된다고 말했다.
하지만 열쇠가 없어서 들어가지 못한 프로세스들이 대기하는 waiting queue 가 존재 해야한다.
세마포어는 위 코드처럼 int 형 변수와 큐를 가진 구조체이다.

P() , V() 구현 방법(싱글 프로세서)

세마포어 자체도 글로벌 변수이기 떄문에 이런 세마포어도 가드를 하기 위해 인터럽트를 걸어 준다. 즉 disableInterrupts() , enableInterrupts() 를 사용한다.
disableInterrupts() , enableInterrupts()는 굉장히 강력하지만 짧은 시간동안만 사용하기때문에 큰 상관이 없다.
S.cnt 를 검사하여 열쇠가 몇개인지 판단하고 그 결과에 따라 큐를 대기시킬지, 깨울지 조건에 따라 결정 하고 열쇠의 수를 감소시키거나 증가 시킨다.
여기서 추가적으로 알아야 할 것이 있다. 바로 세마포어의 카운트 값이 음수일 경우 이 음수의 절대값이 큐에서 대기하고 있는 프로세스의 개수이고 또 양수일 경우 남아 있는 열쇠(자원)의 개수 이다.

멀티 프로세서에서 세마 포어 구현

위 메커니즘은 싱글 프로세서 에서 작동하는 메커니즘이다.
기존 싱글 프로세서에서 세마 포어는는 disable 이라는 메커니즘을 기반으로 구현을 하혔다.
어떻게 하면 멀티 프로세서 에서도 작동하는 메커니즘을 만들까? -> Atomic Operation이 필요 하다. 다시 말해서 글로벌 변수(자원) 을 읽고, 수정 하고,쓰고 , 다시 되돌리는 과정중 에 다른 프로세서가 그 글로벌 변수에 침입하지 못하도록 막는 것이 필요하다.

위 그림을 보면 이해가 쉬울 것이다.
맨처음 버스 아비터에게 버스를 쓰겠다고 요청하고 허가를 받은후 글로벌 변수를 읽는다. 여기까지가 Read 이고 읽어온 글로벌 변수를 수정한다(modify), 그리고 수정된 변수를 다시 메모리에 올리고 아비터에게 사용이 끝남을 알린다.(write)
1,2,3 번이 한 사이클로 동작 되는 것을 Atomic Operation 이라 하고 이 동작이 되는 동안 다른 프로세서는 버스를 사용할 수 없다.

TAS(Test-and-Set)

멀티프로세서 에서 위와 같은 Atomic Operation 을 구현하는 대표적 방식중 하나인 TAS(Test-and-Set)은 하드웨어가 제공해주는 Instruction 으로 TAS 의 파라미터로 메모리 location(lock_var 변수)이 들어간다.
그럼 TAS 는 이 lock_var 변수를 읽어(read) 들여서 이 변수를 1인지 0인지 Test 한다.
그리고 이 값을 1이던 0이던 무조건 1로 만들어 버린후 사용 한다. 즉 하나의 TAS 명령에서 읽고, 수정하고, 쓰기를 한다. 추가적으로 버스를 완전히 장학한다.
정확히 정리하자면 메모리의 Boolean 변수를 읽어서 확인한 후 값을 1로 쓰는 작업을 Atomic하게 수행하는 명령어 이다.

TAS 사용의 예

 while(TAS(lock_var)!=0)
{
		.
		.
		.
}



// Critical Section    
// 공유 자원을 다 사용하면 lock_var = 0

if(use shared resource == FALSE)
	lock_var = 0;

TAS()는 lock_var 을 읽어서 그 값을 체크하고, 리턴 하는데 0 이 아니면 무한 루프를 돌고 0이면 루프를 빠져 나온다.
어떤 한 프로세서가 공유자원을 사용 하고 있다면 글로벌 변수 lock_var 은 1이기 때문에 다른 프로세서는 While 문을 계속 돌고 있을 것이다.
공유 자원을 다 사용하면 lock_var = 0 으로 만들어주고 다른 프로세서가 루프문을 빠져나와 공유자원을 사용할 수 있다.

TAS 정리

멀티프로세서 Synchronization 을 하기위해서는 하드웨어적 서포트가 필요하다.
그 하드웨어적 서포트는 바로 글로벌 변수(lock_var)를 읽고, 수정하고, 다시 되돌리는 과정중 다른 프로세서가 진입하지 못하도록하는 Atomic operation을 만드는 것이다.
그 중 멀티프로세서에서 사용되는 가장 일반적인 방법이 TAS 이다.
TAS 는 글로벌 변수의 값을 읽어와 이놈이 0이면 0을 리턴하고 1이면 1을 리턴 하는데, 1이든 0이든 무조건 1을 쓰게 하여 루프문을 돌게 한다. 그렇게 하여 다른 프로세서가 자원을 사용중일 때 자신은 루프문을 돌아 침범하지 않도록 한다.

TAS 의 문제점

기존 싱글프로세서 세마포어는 웨이팅 큐에 들어가기 때문에 CPU에 큰 영향을 끼치지 않지만
멀티 프로세서의 TAS 는 한 프로세서가 루프에 들어가서 계속 돌고 있다.
이것을 Busy Waiting (또는 Spin lock) 이라 한다.
이 Spin lock 은 여러가지 나쁜 문제들을 초래한다.

스마트폰의 Lockup 문제

스마트폰의 Lockup 문제가 대표적인 Spin lock 문제이다.
ex) 유저 프로세스가 자원을 사용하고 싶은데 그 자원이 Spin Lock 에의해 가드가 되어있다.
즉 다른 프로세서에 의해서 자원(lock_var)이 잡혀 있을때 자신은 자원이 풀릴 때까지 계속 Spinning 을 하게 된다.
근데 어떠한 예기치않은 상황(인터럽트 등..) 때문에 자원(lock_var)을 가지고 있던 프로세서가 쫒겨나고 이상한놈이 그 자원을 쓰고 있다면… 자신은 아무이유도 모르고 Spinning 을 하고 있을 것이다.
이런 문제를 Lock Holder Preemption 이라 한다

Lock Holder Preemption Problem

내가 lock_var(자원) 을 잡기위해서 루프를 돌고 있는데 그 lock_var 을 풀어 줄수 있는 놈이 쫒겨난 경우..
요즘 같이 멀티프로세서 를 사용하는 경우 이 문제가 많이 발생 된다.

세마포어 총정리

-프로세스의 Synchronization 을 제공하기위해서 OS 의 차원의 메커니즘이 세마포어인데 세마포어를 구현하려면 하드웨어적인 지원이 필요하다 싱글 프로세서일 경우에는 disableinterrupt ,enableinterrupt 를 사용하면 되고 멀티 프로세서일 경우는 TAS 같은 atomic operation 을 사용 하면 된다.

멀티프로세서도 가능한 세마포어 구현 방법

위와 같은 기존 싱글 프로세서에서 돌아가는 세마포어 코드에서 아래와 같이 수정해 준다.


disableInterrupt();
->  disableInterrupt();
    while (TAS(lockMem) ! = 0) continue;

enableInterrupt();
->  lockMem = 0;
	enableInterrupt();

또 다른 Synchronization 메커니즘 Monitor

기본적으로 세마포어를 사용한다.
세마포어의 Unstructured Programming Construct 의 단점을 개선하기 위해 만들어진 메커니즘이 Monitor 이다
Monitor 는 Abstract Data Type(클래스)의 구조를 기반으로 출발한다. 즉 멤버 변수와, 멤버 함수를 가지고 있다.

Monitor의 개념

기존 세마포어는 어셈블리어 수준이었다면, Monitor는 C++ 이나 JAVA 와 같은 하이레벨 언어로 제작되었다.

// C 스타일의 모니터

monitor QueueHandler
{
	struct{...} queue;  // shared date
	
	addToQueue(val)
	{
	 " code to add shared queue "
	}	

	int removeFromQueue()
	{
	 " code to remove from queue "
	}

}

monitor 인 큐핸들러 이다.
공유 데이터가 큐인 인 멤버변수 공유데이터가 있고 공유 데이터에 값을 넣는 add 함수와 공유데이터에서 값을 가져오는 remove 함수가 있다.
공유 데이터가 있기 때문에 Synchronization 이 필요하다.

공유자원에 추가하고 제거하는 수행을 하다가 어떤 조건(Condition variables)이 발생하는 경우가 있다.
그럼 그 조건에 맞게 wait() 또는 signal() 을 해야한다.


// resource_manager 라는 모니터 

var busy: bollean ;     // 공유 자원
x : condition;          // condition 변수

procedure entry acquire()   
{
	if(busy) x.wait;
	busy = true;
}

procedure entry release()
{
	busy = false;
	x.signal;
}
 
initialization()
{
	busy = false;
}

acquire() 메소드는 busy의 값을 읽어서 True 이면 자신이 wait를 하고 누군가가 자신을 꺠워주면 busy를 True로 만들고 자신의 일을 한다.
release() 메소드는 busy 를 false로 만들고 자기 때문에 기다리고 있는 프로세스가 있으면 깨워준다.
모니터의 동기화를 좀더 완벽하게 하기 위해서 조건 변수라는(Condition 변수)것을 추가하였다.
Monitor의 Condition 변수(조건 변수)는 어떤 조건이 충족되기를 기다리고 있는 Process들의 Waiting Queue 이다. 즉 이 큐는 wait 와 signal 이라는 명령어를 가지고 있고 x.signal은 waiting 큐에서 대기중인 프로세스가 깨어나는것, x.wait 는 프로세스가 큐에 대기 한다는 동작 이다.
Monitor 는 한번에 하나의 Process만 내부의 함수를 수행 할 수 있도록 허용하기 때문에 Monitor 내부의 공유 자원(공유 변수)를 따로 보호할 필요가 없다.

Hoare Sytle Monitor

Wait 큐에서 깨어난 Process 가 바로 Monitor 내부로 진입하는 방식

Brinch-hansen Style Monitor

Wait 큐에서 Sinal을 보낸 Process가 수행을 계속하는 방식의 Monitor

Monitor 구현

Monitor는 OS의 메커니즘이라기 보다 프로그래밍 언어의 메커니즘이다.
즉 컴파일러가 Monitor 를 세마포어로 변환 시켜줘야 동작을 한다.

/*Hoare Sytle Monitor*/


P(monitor_lock);
	Body of the Function;
if(sig_lock_count > 0) 
{
	V(sig_lock);
}
else
{
	V(monitor_lock);
}

// x.wait
x_count++;

if(sig_lock_count > 0)
{
	V(sig_lock);
}
else
{
	V(monitor_lock);
}
 P(x_lock);
x_count--;



// x.signal
if(x_count > 0)
{
	sig_lock_count++;
	V(x_lock);
	P(sig_lock);
	sig_lock_count--;
}


//monitor_lock  : 모니터를 위한 큐를 가지고 있는 세마포어
//sig_lock      : 시그널을 위한 큐를 가지고 있는 세마포어
//x_lock        : condition 변수를 위한 큐를 가지고 있는 세마포어

우선적으로 공유자원이 몇개인지 파악 or 큐의 수를 파악 하여 총 세마포어 수를 파악한다.

condition 변수 수에 맞게 큐가 필요하다. -> x_lock
Hoare Sytle Monitor에서 Sinal을 보낸 Process 가 Monitor 밖에서 대기하기 위한 큐가 필요하다. -> sig_lock
monitor_lock 큐

이제 동작 을 보자

제일 먼저 모니터에 들어가려면 모니터 함수를 호출하기 전에 P(monitor_lock)으로 문을 따고 들어가야 한다.
모니터안의 함수를 수행하고 다 끝나면 V()를 해서 꺠워줘야 하는데 우선적으로 signaler 에잇는 큐를 깨워준다 -> V(sig_lock)
시그널 큐의 카운트를 판단하여 없다면 monitor_lock 에 있는 놈을 꺠워준다.

wait 를 보자

wait 가 불려 진 시점에서 아직 진행되던 프로세스는 모니터 안에 있으므로 x_count(wait 카운트)를 하나 증가시키고
모니터를 빠져나오니깐 나대신 다른 프로세스를 넣어주어야 하기때문에 우선적으로 signaler 를 확인하고 없으면 monitor_lock 에 있는 프로세스를 모니터에 넣어 준다.
자신은 x_lock(condition 큐)로 빠져나온다. -> P(x_lock)
만약 깨어나면 다시 x_count– 을하고 모니터 안에서 진행한다.

signal을 보자

x_count 의 값을 확인하여 0보다 클경우 waiting 큐에 기다리는 프로세스가 있으므로 자신은 signaler로 들어가야 하기때문에 sig_lock_count 를 1증가 시키고
V(x_lock)으로 condtion 변수에 wait 프로세스를 깨워주고
P(sig_lock)으로 자신은 sinaler 큐에 wait 한다.

정리

Process Synchronization 은 굉장히 어려운 부분이 많은것 같다..
여러 책하고 사이트를 보면서 부족한 부분을 정리하고 고쳐나가야 할 것 같다.

Hyokyun Yim