outline
Critical Section
Requirements for the Solution
Alogrithm
Synchronization Hardware
TestAndSet and Swap
Semaphores
Critical Section of n Processes
Block/ Wakeup Implementation
프로세스 동기화(Process Synchronization)
- 프로세스는 독립 프로세스(Independent Process)와 협력 프로세스(Cooperating Process)로 나눠진다. 협력 프로세스는 다른 프로세스에 의해 영향을 주고받을 수 있는 프로세스이다. 반대로 다른 프로세스에게 영향을 미치지 않고 독립적인 프로세스를 독립 프로세스라고 한다. 현대 컴퓨터 환경에서는 협력 프로세스가 많이 존재한다.
- 프로세스 간에 영향을 미치기 때문에 데이터나 흐름에 대한 동기화가 매우 중요하다. 서로 협력하는 프로세스 간에 문제가 발생하지 않도록 일관성을 유지시키는 것을 프로세스 동기화(Process Synchronization)이라 한다.
경쟁 상황(Race Condition)
- 경쟁 상황이란 두 개 이상의 프로세스가 공유된 자원을 병행적으로 읽거나 쓸 때 공유 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 달라지는 상황을 의미한다. 프로세스는 자신의 주소 공간에 접근하는 경우는 문제가 되지 않지만 시스템 콜로 운영체제가 커널 코드에 접근하는 경우는 문제가 발생한다.
- 멀티 프로세스 환경의 경우 프로세스의 메모리 공간을 공유하기 때문에 문제가 발생한다. 경쟁 상황이 발생하게 되면 모든 프로세스에 원하는 결과가 발생하는 것을 보장할 수 없으므로 최종적으로 마지막에 저장한 프로세스의 결과 값이 출력될 수 있는 상황이 오게 된다. 그러므로 이러한 상황은 반드시 피해야 한다.
위에 예시를 보면 두 개의 협력 프로세스에 대한 문제를 보여주는데, CPU1과 CPU2가 메모리에서 X=2라는 자원을 공유한다고 가정하자. 프로세스 P1에서는 X= X+1 코드를 실행하고 P2에서는 X= X-1을 실행한다. 해당 작업을 어셈블리어로 내려가면 여러 줄로 구현된다. 이 두 개의 프로세스를 교차로 실행하게 되면, 공통 변수 X에 대한 접근을 교차로 접근하기 때문에 해당 프로세스의 결과 값이 비정상적으로 나온다.
이러한 문제가 발생하는 원인은 공통 변수(common variable)에 대한 동시 업데이트(concurrent update)때문이다. 이를 해결하기 위해서는 공통 변수에 접근하는 프로세스는 하나만 존재하도록 관리해야 한다. 이러한 공통 변수 구역을 임계 구역(Critical section)이라 한다.
임계 구역 문제(Critical Section Problem)
임계 구역은 여러 개의 스레드가 수행되는 시스템에서 각 스레드들이 공유하는 데이터(변수, 테이블, 파일 등)를 변경하는 코드 영역을 말한다.
임계 구역을 해결하기 위한 3가지 조건(Requirements for the Solution)
- 상호 배제(Mutual Exclusion): 프로세스가 임계 구역에서 실행 중이라면, 다른 프로세스들은 그들이 가진 임계 구역에서 실행될 수 없다.
- 진행(Progress): 임계 구역에서 실행 중인 프로세스가 없고, 별도의 동작이 없는 프로세스들만 임계 구역 진입 후보로서 참여될 수 있다. 한 임계 구역에 접근하는 스레드를 결정하는 것은 유한 시간 이내에 이루어져야 한다.
- 유한 대기(Bounded Waiting): 프로세스가 임계 구역에 진입 신청 후부터 받아들여질 때까지, 다른 프로세스들이 임계 구역에 진입하는 횟수는 제한이 있어야 한다. 임계 구역으로 진입하기 위해 대기하는 모든 스레드는 유한 시간 이내에 해당 임계 구역으로 진입할 수 있어야 한다.
알고리즘(Alogrithm)
- 프로세스들은 프로세스 간의 상태들을 동기화를 위한 공통 변수를 공유를 해야 한다.
entry section : 임계 구역을 진행시키기 전에 조건 설정.
exit section : 종료 시 종료 알림을 전달.
<알고리즘 예시>
do{
entry section
critical section
exit section
remainder section
}while(1);위에 예시 코드처럼 스레드를 진행하기 전제 임계 구역을 진행 시 키 전에 어떠한 조건을 설정해줘야 한다. 그리고 조건이 충족 시 임계 구역을 진행시키고, 임계 구역을 마치면 임계 구역을 마쳤다는 상태를 다른 프로세스에게 전달하는 무언가가 필요하다. 보통 그 무언가를 공통 변수로 설정한다.
<알고리즘 1>
do{
while (turn !=0); /* My turn?*/
critical section
turn = 1; /*Now it’s your turn*/
remainder section
}while(1);- 알고리즘 설명 : 첫 번째 알고리즘에서는 turn이라는 공유 변수를 설정하였다. 초기 turn 값은 0으로 설정하고 프로세스가 임계 구역을 들어가기 위한 조건을 turn=1일 때로 설정한다. 만약 turn 값이 0이 아니면 무한루프를 돌게끔 설정한다. 해당 무한루프는 다른 프로세스가 turn 값을 0으로 줄 때까지 반복된다.(다른 프로세스는 turn 값이 1일 때 무한루프를 돌고 0일 때가 종료로 설정되어 있다.) 만약 다른 프로세스가 종료했다고 turn 값을 0을 주면 해당 프로세스가 드디어 임계 구역을 실행하게 된다. 똑같이 임계 구역을 마치면 해당 임계 구역이 종료되었다고 turn 값을 1로 설정하여 다른 프로세스에게 상태를 알려준다.
- 문제점 : 해당 알고리즘은 상호 배제적 조건을 만족시키지만, 진행 조건을 충족하지 않는다. 왜냐하면 어떠한 프로세스 P0이 진행되려면 다른 P1에서 프로세서가 돌고 공유 변수 값을 전달해야지 해당 P0 프로세스가 진행되는데 만약 P1 프로세스가 진행이 되지 않는다면 해당 P0 프로세스는 무한 대기 상태가 된다.
<알고리즘 2>
do {
flag[i] = true; /* Pretend I am in*/
while (flag[j]); /*Is he also in? then*/
critical section
flag [i]=false; /* I am out */
remainder section
}while(1);- 알고리즘 설명 : 2번째 알고리즘에서는 flag라는 배열을 이용해서 프로세스 간의 상태를 알려주는 공유 변수를 설정한다. 초기 값으로는 false를 진행하고 프로세스 P(i)가 실행되면 일단 해당 프로세스의 flag 상태를 true로 설정한다. 그다음 다른 프로세스의 상태를 확인한다 만약 다른 프로세서에서 true 상태를 확인되면 해당 프로세스는 무한루프를 돌아서 대기 상태로 남겨둔다. 만약 다른 프로세스들이 다 false 상태이면 임계 구역을 실행하고 임계 구역을 끝마치고 해당 프로세스 P(i) 상태를 false로 설정해 준다.
- 문제점 : 해당 알고리즘은 다른 프로세스 상태가 true이면 대기를 한다. 해당 알고리즘도 상호 배제적 조건을 충족시키지만, 여전히 진행 조건을 충족하지 않는다. 왜냐하면 알고리즘 1의 의도를 너무 중요시 여겨서 다른 프로세서의 상태가 true이면 무한 대기 상태가 된다. 만약 프로세스가 동시에 실행되면 모든 프로세스가 true 상태가 되고 모든 프로세스가 서로의 true 상태를 확인하여 무한 대기 상태가 되어 문제가 발생한다. 프로세스들 간에 양보하는 현상이 발생한다.
<알고리즘 3 - Peterson`s Algorithm>
do{
flag [i]= true; /* My intention is to enter …. */
turn = j; /* Set to his turn*/
while (flag [j] and turn == j); /* wait only if …*/
critical section
flag [i] = false;
remainder section
}while(1);- 알고리즘 설명 : 3번째 알고리즘은 알고리즘 1과 알고리즘 2의 공유 변수를 결합하여 만든 알고리즘이다. 당연히 다른 프로세스의 상태를 확인하는 flag 공유 변수와 프로세스의 차례를 알려주는 turn이라는 공유 변수가 존재한다. 만약 다른 프로세스의 상태가 false이고 turn도 해당 프로세스의 차례이면 임계 구역을 실행한다.
- 문제점 : 모든 임계 구역을 해결하기 위한 3가지 조건은 충족되었지만 entry section 부분이 너무 길다. 모든 프로세서가 너무 긴 entry section을 가지기 때문에 성능 부분에서 문제가 발생한다.
하드웨어 동기화(Synchronization Hardware)
임계 영역 문제 해결책은 임계 영역의 실행 여부를 알 수 있는 메커니즘이 제공되는지가 관건이다. 임계 영역 문제 해결책으로는 크게 하드웨어적 해결책과 소프트웨어적 해결책이 있다. 하드웨어적 해결책으로는 TestAndSet, Swap 등이 있다.
1) 임계 구역의 문제에 대한 해결책 - Lock
- 하드웨어 기반 해결책으로써, 동시에 공유 자원에 접근하는 것을 막기 위해 임계 구역에 진입하는 프로세스는 Lock을 획득하고 임계 구역을 빠져나올 때, Lock을 방출함으로써 동시에 접근이 되지 않도록 설정한다.
- 다중 처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.
acquire()
{
while(!available); /*바쁜 대기 상태(busy wait)*/
available = false;
}
release()
{
available = true;
}
do {
acquire lock
//critical section
release lock
//remainder section
}while(TRUE);- acquired(locked, held) : 유일한 스레드 하나가 임계 구역으로 추정되는 공간에서 락(Lock)을 가지고 있는 상태.
- release(unlocked, free) : 어떠한 스레드도 락(Lock)을 가지고 있는 상태.
- available : Lock의 가용 여부를 판단.
- 만약 Lock이 가용하다면 acquire() 함수를 호출해서 락을 획득하고, 다른 프로세스가 접근하지 못하도록 lock은 곧 사용불가가 된다. lock을 반환할 때는 release()를 호출한다.
- 문제점 : lock에서 임계 구역에 들어가기 위해서 계속해서 acquire() 함수를 호출하는 반복문을 실행한다. lock이 가용해지기를 기다리면서 프로세스가 계속 반복 회전하고 있기 때문에 busy waiting 상태가 되는데, 이는 CPU cycle을 낭비하게 된다.
2) TestAndSet
boolean TestAndSet(boolean &target)
{
boolean rv = traget;
traget = true;
return rv;
}
do{
while(TestAndSet(lock));
//critical section
lock = false;
//remainder section
}lock의 초기값은 false로 초기화되어 있다. 따라서, 처음으로 실행한 프로세스는 첫 반복문(while)을 통과한다. 그리고 'TestAndSet'에 의해서 lock은 TRUE가 되었으므로, 다른 프로세스가 임계 영역을 실행하려고 해도, 반복문(while) 문에서 걸려서 실행할 수 없다. 여기서 상호 배제 조건을 만족한다. 그리고 임계 영역을 다 끝낸 프로세스는 lock 값을 다시 FALSE로 설정하여 다른 프로세스도 임계 영역을 실행할 수 있도록 한다. 진행 조건도 만족하지만 한정 대기 조건을 만족할 수 없다.
3) Swap
void Swap(boolean &a, boolean &b)
{
boolean temp = a;
a = b;
b = temp;
}
do{
key = true;
while(key == true) Swap(lock, key);
//critical section
lock = false;
//remainder section
}lock값이 false로 초기화를 시킨다. lock과 key를 swap 하면 key 값이 false가 되어 바로 반복문(while)을 통과한다. 하지만 lock 값이 true가 되었으므로 다른 프로세스는 반복문을 빠져나가지 못한다. 즉 상호 배제 조건을 만족한다. 그리고 임계 영역을 다 진행한 프로세스는 lock값을 false로 되돌리면 다른 프로세스도 임계 영역을 실행할 수 있다. 따라서 진행 조건도 만족하게 된다. 하지만 여전히 한정 대기 조건을 만족하지 못한다.
세마포(Semaphores)
- 세마포는 소프트웨어적 프로세스 동기화 기법 중 하나이다. 세마포는 사용 가능한 자원의 수를 의미하며, 세마포어 변수 값에는 wait(), signal()라고 하는 원자적 명령(atomic 연산) 또는 함수에 의해서만 접근이 가능하다.
- 세마포는 두 가지 동작이 존재하는데, 초기에는 P, V로 불렸다. P는 wait 함수이고, V는 signal 함수로 사용된다.
임계 영역에서의 프로세스들..(Critical Section of n Processes)
wait(S)
{
while(S<=0); /*바쁜 대기 상태(busy wait)*/
S--;
}
signal(S)
{
S++;
}
do{
P(mutex);
//critical section
V(mutex);
//remainder section
}while(1);- wait(S)는 S <0 일 때는 작동을 하지 않는다. S가 1 이상이 될 때까지 wait 상태로 되고 작동 시에는 S를 1씩 감소시킨다. signal(S)에서는 작동 시 S를 1씩 증가시킨다.
- mutex는 공유 변수이고 초기에 mutex =1로 초기화된다. mutex =1일 때 한 프로세스만 작동시킬 수 있다. wait 연산을 먼저 시행한 프로세스가 처음으로 임계 영역을 실행한다. 해당 프로세스가 종료되어서 mutex 값이 1이 될 때까지 다른 프로세스는 대기를 해야 한다. 해당 프로세스가 임계 영역으로 빠져나오면 signal 함수에서 mutex 값이 증가되어 다른 프로세스의 대기 상태가 mutex가 1이 되는 순간 해당 임계 영역을 실행할 수 있게 된다. 즉 mutex =1이라는 의미는 임계 영역을 실행할 수 있는 권한을 하나의 프로세스에만 주어지게 된다.
- P, V 연산은 polling이 아니라, sleep을 해버리기 때문에 기다릴 때 CPU 낭비가 발생하지 않기 때문에 'TestAndSet' 보다 효율적이고 많이 사용된다.
Block/ Wakeup Implementation
block : 커널은 자신을 호출한 프로세스를 일시 중단한다. 이 프로세스의 PCB를 wait queue에 넣는다.
wakeup(P) : block 처리된 프로세서 P의 실행을 재개한다. (이 프로세서의 PCB를 ready queue에 넣는다.)
typedef struct{
int value;
struct process *L;
}semaphore;
P(S) :
S.value--;
if(S.value<0)
{
//add this process to S.L;
block();
}
V(S) :
S.value++;
if(S.value <= 0)
{
//remove a process P from S.L;
wakeup(P);
}
- P(S)에서 value 값을 감소시키고 만약 value값이 0보다 작으면 이미 해당 임계 구역에 어느 프로세스가 존재한다는 의미이므로 현재 프로세스는 접근하지 못하도록 막아야 한다. 이를 list라는 기다리는 줄에 추가한 뒤 block을 걸어준다.
- V(S)는 value 값을 증가시키고, 만약 value 값이 0보다 같거나 작으면 임계 구역에 진입하려고 대기하는 프로세스가 list에 남아있다는 의미이므로 그중에서 하나를 꺼내어 임계 구역을 수행할 수 있도록 해주어야 한다.
