[OS] 6-1. Process Synchronization I

Chapter 6-1. Process Synchronization I

Process Synchronization : 프로세스 동기화

= Concurrency Control : 병행 제어

여러 주체(객체)가 하나의 데이터를 동시에 접근하려고 할 때를 Race Condition이라고 한다.

데이터의 촤종 연산 결과는 그 데이터를 마지막에 다룬 프로세스에 따라 달라진다.

동시에 접근했더라도 연산의 수행이 더 늦게 끝나는 프로세스의 결과값을 따르게 된다.

즉,

공유데이터(shared data)의 동시접근(consistency access)는 데이터의 불일치 문제를 발생시킬 수 있다는 이슈이다.

그리고 우리는 이것을 조율해줘야 하는 문제가 발생한다.

공유 메모리를 사용하는 프로세스 사이에서 발생할 수도 있고,

커널 내부 데이터를 접근하는 루틴들 사이에서도 발생할 수 있다.

조금 더 상황을 구체적으로 살펴본다면, 크게 세 가지 경우를 볼 수 있다.

Kernel 수행 중 인터럽트가 발생

이 경우에는 중요한 루틴을 처리하고 있을 때는 인터럽트가 들어와도 인터럽트 처리를 미룬 뒤 작업을 마친 뒤에 인터럽트를 처리한다.

Process가 system call을 하여 kernel mode일 때 condtext switch 발생

이 경우엔 프로세스가 커널 모드로 수행 중일 때는 CPU를 preempt하지 않게 한다.

그리고 커널모드에서 사용자 모드로 복귀할 때 preempt한다.

Multiprocessor 에서 shared memory 내의 kernel data에 접근할 경우

하나의 프로세서가 공유 메모리에 접근할 때 데이터에 대해 lock을 걸어주고 메모리에서의 작업이 끝나면 unlock을 해준다.

But,

무조건적으로 접근을 제한하다보면 효율에 문제가 생기게 된다.

그래서 Critical Section(공유 데이터에 접근하는 코드)에 어떠한 방법을 적용해야 하는 것이다.

그 어떠한 방법은 어떤 조건들을 만족해야 하는가?

Mutual Exclusion(상호배제)

Critical Section에 동시에 도달하면 안된다.

어렵게 생각할 필요없고 이 조건은 구현할 알고리즘의 목적 그 자체다.

Progress

아무도 공유 데이터에 접근하고 있지 않을 때 접근하고자 하는 프로세스가 있다면 접근을 허용해야 한다.

어떻게 생각하면 당연하게 느껴질 수도 있는 조건이지만,

만약 아무 프로세스도 접근을 하고 있지 않는 데이터에 어떤 프로세스가 접근하고 있다는 데이터가 남아있어서

아무 프로세스도 접근할 수 없는 상황이 발생한다면?

이 조건은 반드시 고려해야하는 요소 중 하나가 된다.

Bounded Waiting

프로세스가 접근하기 위해 요청한 후 부터 요청이 허용될 때까지의 waiting time이 유한해야 한다.

스케줄링과 비슷한 개념으로 다른 프로세스도 언젠가는 접근을 할 수 있도록 해야 한다는 것이다.

조금 다르게 표현한다면 다른 프로세스들이 공유 데이터에 접근하는 횟수에 한계를 줘야 한다는 조건이다.

위 세가지 조건들을 모두 충족시킬만한 lock과 unlock을 분배할 알고리즘이 필요하다.

알고리즘 1

이 알고리즘에서는 turn이란 변수(Synchronization variable)을 사용하여 문제를 해결한다.

Process A, Process B가 있다고 가정하고 코드를 살펴보자.

A,B의 차이는 turn값이다.

A의 입장에서 코드를 살펴보면, turn 값이 0이 아닐 때는 critical section으로 들어가지 않고 루프를 돌면서 기다린다.

현재의 turn값은 현재 critical section에 접근하여 연산을 수행하고 있는 B의 turn 값 1이다.

Process B가 critical section에서의 일을 모두 마치고 나서야 turn값을 0으로 바꿔준다.

이 때가 되서야 Process A가 무한루프에서 빠져나와 Critical Section에 접근하게 되는 것이다.

code>

Process A(turn 값 = 0)
do {
     while(turn != 0);
     critical section
     turn = 1;
     remainder section
} while(1);
 
Process B(turn 값 = 1)
do {
     while(turn != 1);
     critical section
     turn = 0;
     remainder section
} while(1);

하지만 이 알고리즘은 두번째 조건 Progress를 만족시키지 못한다.

반드시 A 다음에 B  or  B 다음에 A가 수행되도록 설계되어 있다.

A or B가 둘 중 하나의 프로세스가 다른 프로세스에 비해 critical section을 빈번하게 수행해야하는 프로세스라면,

이 알고리즘만 갖고는 해결이 되지 않는다.

알고리즘 2

이 알고리즘에서는 flag란 변수를 사용하고 각각의 프로세스가 고유의 값을 갖는다.

flag는 critical section에 들어가고자 하는 상태를 나타내는 변수이다.

flag값이

true 이면 깃발을 들다의 의미로 critical section에 접근하겠다라는 의미이고

false 이면 깃발을 내리다의 의미로 critical section에 접근하지 않는다라는 의미이다.

code>

do {
     flag[i] = true; // critical section에 들어가기 위해 true 값으로 바꾼다.
     while(flag[j]); // 다른 프로세스를 확인한다.
     critical section;
     flag[i] = false; // critical section에서의 수행을 마치고 다시 false로 바꿔준다.
     remainder section
} while(1);

하지만 이 알고리즘도 두번째 조건을 만족시키지 못한다.

깃발을 내려놓는 행위를 미처 하지 못하고 깃발을 들고 있는 도중에 CPU를 preempt 당하게 되면

다른 프로세스가 그 다음에 깃발을 들게 된다.

이렇게 되면 깃발을 들고 있는 프로세스는 두 개가 되고 아무도 critical section에 접근하고 있지 않음에도

어떤 프로세스도 접근할 수 없는 상황이 연출된다.

알고리즘 3

Peterson's Algorithm 이라고 불리는 알고리즘으로 위의 1, 2의 두 가지 알고리즘을 합쳐 놓은 알고리즘이다.

code>

do {
     flag [i] = true;
     turn = j; // 상대방 턴으로 바꿔둔다.
     while(flag[j] && turn == j); //
     critical section
     flag[i] = false;
     remainder section
} while(1);

둘다 접근하려고 하는 경우에는 turn 의 값으로 접근할 프로세스가 결정된다.

그렇지 않은 경우에는 flag값을 통해서 접근할 수 있다.

하지만 이 알고리즘에 문제가 없는 것은 아니다.

Busy Waiting (=spin lock) 의 문제가 발생한다.

계속 CPU와 memory를 사용하면서 대기하는 상황인 것이다.

쓸데없이 while 속에서 무한 루프를 반복하며 대기하고 있는 것은 비효율적인 방법이다. 

Semaphores

일종의 추상자료형으로 위의 알고리즘을 추상화시킨 것이다.

두 가지 타입으로 나눌 수 있다.

rescue counting에 사용하는 counting semaphore가 존재하고

0 또는 1의 값을 갖는  binary semaphore가 존재한다.

그리고 두 가지의 atomic 연산에 의해서만 접근이 가능하도록 하였다.

P(S)

whlie(S<=0) do no-op;

S--;

자원을 할당받지 못한 경우엔 while문에서 무한루프를 돌며 기다리다가 자원을 획득하는 과정이다. lock을 거는 과정이다.

V(S)

S++;

자원을 반납하는 과정이고, unlock과정이다.

물론 이 방법을 사용해도 busy waiting이 발생한다.

그래서 Block & Wakeup 방식을 도입한다. (=sleep lock)

프로세스가 sleep 되는 원리와 비슷하다.

쓸데없이 whlie문을 돌면서 기다리는 것이 아니라

자원이 없으면 blocked 상태에서 자원을 기다린다. 그리고 자원을 할당받으면 바로 접근할 수 있게 한다.

P(S) :
S.value --;
if(S <= 0){
     add this process S.L;
     block();
}
 
V(S) :
S.value++;
if(S.value <= 0) {
     remove a process P from S.L;
     wakeup(P);
}

block/wakeup 방식은 overhead가 발생한다.

ready 상태인 프로세스를 blocked로 해줘야 하고 또 blocked 상태인 프로세스를 ready로 변경해줘야 한다.

그래서 critical section의 길이가 짧은 경우에는 spin lock 방법(busy waiting) 방법을 사용해도 큰 문제는 없지만

긴 경우에는 block/wakeup방식이 적당하다.

Chapter 6-1. 끝

이 포스팅은 이화여대 반효경 교수님 강의를 듣고 요약한 내용을 담고 있습니다.