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 은 굉장히 어려운 부분이 많은것 같다..
- 여러 책하고 사이트를 보면서 부족한 부분을 정리하고 고쳐나가야 할 것 같다.