Race Condition
여러 프로세스가 공유하는 데이터에 동시에 접근하면 Data Inconsistency가 일어날 수 있다.
공유된 변수 counter (= 5)가 있다고 하자.
// P1
{
...
counter++
}// P2
{
...
counter--
}이렇게 두 프로세스가 동시에 count++과 count--를 실행하면
P1은
reg1 = counter
reg1 = reg1 + 1
counter = reg1을 실행하고, P2는
reg1 = counter
reg1 = reg1 - 1
counter = reg1을 실행할 것이다.
이 경우 counter는 5가 아니라 두 결과 중 나중에 적용된 4나 6일 것이다.
이렇게 여러 프로세스가 공유된 데이터에 동시에 접근하고 수정하려 하는 상황을 Race Condition이라고 한다.
Race Condition을 막기 위해선 counter++과 counter--는 Atomic하게 진행되어야 한다.
Atomic Operation이란 명령어가 중간에 Interrupt 되지 않고 하나의 명령어가 처리되는 것처럼 실행되는 것을 뜻한다.
Critical Section
Shared Data를 사용하는 프로세스의 코드는 Shared Data에 접근하는 부분인 Critical Section이라는 코드가 포함되어 있다.
한 프로세스만 Shared Data에 접근하도록 하기 위해선 한 프로세스가 Critical Section을 실행 중이면 다른 프로세스는 Critical Section을 실행하지 못하게 막아 Shared Data에 접근하지 못하게 해야 한다.
이런 기능을 구현하기 위해
- Software Approach
- Hardware Instruction
- Semaphore
- Monitor
등의 툴을 사용할 수 있다.
Synchronization Tools
Critical Section의 접근을 통제해 Synchronization을 구현하기 위해선 다음의 조건을 충족해야 한다.
- Mutual Exclusion : 한 프로세스가 Critical Section을 실행 중이면 다른 프로세스는 실행할 수 없다.
- Progress : Critical Section을 실행 중인 프로세스가 없고, Critical Section 실행을 대기 중인 프로세스가 존재한다면, 다음 Critical Section을 고르는 작업이 무기한 연기되어서는 안 된다.
- Bounded Waiting : 한 프로세스가 Critical Section 진입 요청을 하고 실제로 진입할 때까지, 다른 프로세스가 Critical Section에 진입할 수 있는 횟수는 제한되어야 한다.
Software Based Approach
프로세스 Pi과 Pj가가 있다고 가정하자.
P0와 P1은 다음과 같은 구조이다.
do
{
(Entry Section)
(Critical Section)
(Exit Section)
(Remainder Section)
} while(1)1
프로세스의 구조를 다음과 같이 짜보자.
// Shared Variable : int turn = 0
// if turn == i
// Pi can enter Critical Section
// Pi
do
{
while (turn != i); // Entry Section : Wait for turn
(Critical Section)
turn = j; // Exit Section
(Remainder Section)
} while(1)
turn 변수로 CS가 끝날 때 차례를 넘겨준다. CS는 자기 차례일 때만 실행한다.
Mutual Exclusion이 구현되나 Progress는 구현되지 못한다.
다음 상황을 가정해 보자.
- P0이 CS를 다 실행하고 P1의 차례가 되어 CS를 실행한다.
- P0는 RS를 처리한다.
- P1이 CS를 다 끝내 다시 P0의 차례가 된다.
- 아직도 P0는 RS를 처리하고 있다.
- 그 사이 P1이 다시 CS를 실행하려 한다.
- 그러나 P0는 아직 RS를 처리 중이기 때문에 turn은 0이고, P1은 기다려야 한다.
2
1을 보완해 flag를 도입해 보자.
// Shared Variable : boolean flag[2];
// flag[0] = flag[1] = false;
// if flag[i] == true,
// Pi is read to enter CS
// Pi
do
{
flag[i] = true;
while (flag[j]); // Entry Section
(Critical Section)
flag[i] = false; // Exit Section
(Remainder Section)
} while(1)
flag를 통해 CS가 필요한 상태인지 공유한다. 다른 CS가 필요하다면 CS가 완료될 때까지 양보한다.
마찬가지로 Mutual Exclusion이 구현되나 Progress는 구현되지 못한다.
동시에 flag[0] = true, flag[1] = true가 실행되면 두 프로세스 모두 while(flag[1]);과 while(flag[0]);에 걸려 대기 상태가 된다.
Peterson's Algorithm
Peterson's Algorithm은 두 방법을 혼합한 방법이다.
// Pi
do
{
flag[i] = true;
turn = j;
while (flag[j] && turn == j ); // Entry Section
(Critical Section)
flag[i] = false; // Exit Section
(Remainder Section)
} while ( 1 );
상대 차례이고, 상대가 CS 요청을 처리 중일 때 기다린다.
그러나 이런 Software를 통한 접근은 현대 컴퓨터에서는 적합하지 않다. 프로세서나 컴파일러가 명령어의 순서를 재배치하는 경우도 있기 때문이다.
Hardware Support
하드웨어가 Synchronization Instruction을 제공해 Synchronization을 구현하기도 한다.
하드웨어가 Atomic Instruction을 제공해 이 기능을 사용할 수 있다.
Atomic Instruction인 TestAndSet은 값을 확인한 뒤 설정할 수 있고, Swap은 두 값을 바꿀 수 있다.
대략 TestAndSet은 다음과 같은 구조이다.
bool TestAndSet(boolean *target)
{
bool rv = *target;
*target = TRUE;
return rv;
}이 기능을 사용해 아래와 같이 Mutual Exclusion을 구현할 수 있다.
// Shared Data : bool lock = false
do
{
while (TestAndSet(&lock)); // Entry Section
(Critical Section)
lock = FALSE; // Exit Section
(Remainder Section)
} while (1);lock이 false면 true로 바꾸고 CS에 진입할 수 있다. 이 과정은 Atomic해 중간에 다른 프로세스와 섞이지 않는다.
Swap은 다음과 같은 구조이다.
void Swap(boolean *a, boolean *b)
{
boolean temp = *a;
*a = *b;
*b = temp;
}Swap을 사용해 아래와 같이 Mutual Exclusion을 구현할 수 있다.
// Shared Data : lock = false
do
{
key = TRUE;
while (key == TRUE) // Entry Section
{
Swap(&lock, &key);
}
(Critical Section)
lock = FALSE; // Exit Section
(Remainder Section)
} while (1);Semaphore
Semaphore는 Atomic하게 실행되는 두 명령어로만 접근할 수 있는 변수를 사용하는 방법이다.
// Semaphore S
wait(S)
{
while (S <= 0)
{
(do nothing)
}
S--;
}// Semaphore S
signal(S)
{
S++;
}변수 S가 0과 1만 가지는 Semaphore를 Mutex Lock이라고 하기도 한다.
변수가 더 큰 범위를 가지면 Counting Semaphore라고 한다.
Spinlock
CS에 lock이 걸려 진입이 불가능할 때 wait의 while문 안에서 계속 돌며 기다리는 상황이다. CPU가 의미 없는 while 연산을 계속하며, Context Switch도 일어나지 않는다.
CS에 짧은 시간에 진입할 수 있으면 효율적이지만, CS에 진입하는 데 오래 걸린다면 그사이에 Context Switch로 다른 프로세스를 실행하다 오는 것이 효율적이다.
Semaphore를 사용한 Mutual Exclusion은 아래와 같이 구현할 수 있다.
// Shared Variable : mutex = 1;
do
{
wait(mutex);
(Critical Section)
signal(mutex);
(Remainder Section)
} while(1);Semaphore는 Spinlock 대신 sleep(), wakeup()을 사용해 대기 상태에 CPU를 사용하지 않는 식으로 구현하기도 한다.
Deadlock과 Starvation
Synchronization에서는 Deadlock과 Starvation이라는 문제가 나타날 수 있다.
- Deadlock : 두 프로세스가
waiting상태인데 해제하기 위해선 서로signal을 해줘야 해 모두 무한히 대기 중인 상태
- Starvation : 다른 프로세스들이 계속 사용 중이어서 영원히 실행되지 못하고 있는 상태
Monitor
Semaphore는 개발자가 signal, wait으로 동기화를 구현하는 반면, Monitor는 Monitor ADT가 내부에서 동기화를 관리해 준다.
monitor monitor-name
{
(Shared Variable Declarations)
procedure body P1 (...) {...}
procedure body Pn (...) {...}
...
{
(Initialization Code)
}
};
프로세서가 Monitor를 호출하면 Monitor Queue에 프로세스가 추가된다.
Queue의 맨 앞 프로세스는 실행 권한을 얻고, CS에 접근하려 하면 Lock을 획득한다.
Lock을 획득하면 Shared Variable에 접근해 조작할 수 있다.
CS를 종료하면 Lock을 해제하고, Queue의 다음 프로세스가 실행 권한을 얻는다.
Condition Variable과 wait, signal 명령어를 사용해 프로세스가 특정 조건을 만족할 때까지 프로세스를 대기시킬 수도 있다.
프로세스는 Condition Variable X를 선언하고, X.wait(), X.signal()과 같이 함수를 실행할 수 있다.
wait: 다른 프로세스로부터signal을 받을 때까지 대기한다.wait을 실행한 프로세스는 Queue의 맨 뒤로 이동한다.signal: Condition Variable을 사용하는 프로세스를 하나씩 깨운다. Queue에서 기다리는 프로세스 중 하나가 실행 권한을 얻는다.
프로세스 P가 x.signal()을 실행하고, x와 관련된 잠긴 프로세스 Q가 있다고 하자.
이때 P와 Q의 실행 방식은 두 가지가 있다.
- Mesa Semantics :
x.signal()이 발생한 이후에 Q는 Waiting Queue에서 Ready Queue로 넘어가지만, CPU Scheduler가 다른 프로세스를 선택하고, 하필 그 프로세스가x를 변경할 수도 있다. 따라서 깨어나도 원하는 상태임이 보장되지 않는다. Q는 모니터를 벗어나지 않고x를 다시 확인한다. Hoare보다 적은 Context Switch가 일어난다. - Hoare Semantics :
x.signal()이 실행되면 CPU Scheduler는 바로 Waiting Queue의 프로세스 중 하나(Q)를 택해 실행한다. 이 명령은 Atomic해 중간에x가 변경되지 않는다. 프로세스의 동기화를 보장하기 쉽지만, Context Switch가 자주 일어난다.
Synchronization Problems
다음은 Synchronization과 관련하여 고려해야 하는 상황이다.
Bounded-Buffer Problem
Producer 프로세스와 Consumer 프로세스가 있다. Producer는 버퍼에 데이터를 넣고, Consumer는 버퍼에서 데이터를 뺀다.
Producer A가 버퍼의 빈 곳에 데이터를 쓰려고 할 때, Interrupt가 발생해 Producer B가 같은 위치에 데이터를 쓴다면 두 프로세스 중 하나의 데이터가 유실될 수 있다. 따라서 프로세스는 Lock을 건 다음 비어있는 공간에 데이터를 쓰고, 빈 위치를 다음 위치로 바꾸고 Lock을 해제해야 한다.
Consumer가 데이터를 꺼내려 하는데 Interrupt가 일어나 다른 Consumer가 같은 데이터를 꺼낼 때도 문제가 발생한다. 마찬가지로 Lock을 건 뒤 프로세스를 실행하고, 저장 위치를 다음 위치로 바꾼 다음 Lock을 해제해야 한다.
// Shared Data
semaphore full = 0, empty = n, mutex = 1;
// Producer
do
{
...
(produce an item in nextp)
...
wait(empty); // 비어 있는 버퍼 - 1
wait(mutex); // Entry Section
...
add nextp to buffer // CS
...
signal(mutex); // Exit Section
signal(full); // 차 있는 버퍼 + 1
} while (1);
// Consumer
do {
wait(full); // 차 있는 버퍼가 있는지 확인 후 - 1
wait(mutex); // Entry Section
...
(remove an item from buffer to nextc) // CS
...
signal(mutex); // Exit Section
signal(empty); // 비어 있는 버퍼 + 1
...
(consume the item in nextc)
...
} while (1);Readers and Writers Problem
Writer는 DB의 데이터를 수정하고, Reader는 데이터를 읽는다.
Writer가 데이터를 수정할 때는 Reader가 데이터를 읽어선 안 된다.
Reader는 데이터를 조작하지 않기 때문에 여러 Reader가 동시에 데이터를 읽는 것은 가능하다.
// Shared Data
semaphore mutex = 1, wrt = 1; int readcount = 0;
// Writer
do
{
wait(wrt); // Entry Section
...
(writing is performed) // CS
...
signal(wrt); // Exit Section
} while (1);
// Reader
do
{
wait(mutex); // readcount의 진입을 Lock
readcount++; // readcount 수정
if (readcount == 1)
{
wait(wrt); // Writer의 진입을 Lock : Entry Section
}
signal(mutex); // readcount Lock 해제
...
reading is performed // CS
...
wait(mutex); // readcount Lock
readcount--; // readcount 수정
if ( readcount == 0 ) // 읽고 있는 사람 없으면
{
signal(wrt); // Exit Entry
}
signal(mutex); // readcount Lock 해제
} while (1);Dining-Philosophers Problem
철학자 5명이 식사하려고 원형 테이블에 앉았다.
철학자 사이에는 젓가락이 한 짝씩 있고, 젓가락 두 짝을 지어야 식사가 가능하다.
식사가 끝나면 젓가락을 내려놓고 생각에 빠진다.
철학자가 모두 왼쪽의 젓가락 한 짝을 지으면 아무도 식사를 하지 못해 굶어 죽는다.
// Philosopher i
do
{
wait(chopstick[i]) // i 젓가락과
wait(chopstick[(i+1) % 5]) // 옆 젓가락을 집는다.
...
eat // CS
...
signal(chopstick[i]); // 두 젓가락을
signal(chopstick[(i+1) % 5]); // 내려놓는다.
...
think
...
} while (1);그러나 이 방법은 Deadlock을 일으킬 수 있다.
Deadlock을 막기 위해서는 조건을 추가해야 한다.
- 최대 4명의 철학자만 밥을 먹게 한다.
- 두 젓가락이 모두 있을 때만 집는다.
- 홀수 번째 철학자들이 먼저 젓가락을 집고, 짝수 번째 철학자들이 그다음에 집는다.
monitor dp
{
enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i)
{
state[i] = hungry;
test(i);
if ( state[i] != eating )
{
self[i].wait();
}
}
void putdown(int i)
{
state[i] = thinking;
test((i+4) % 5); // test left neighbor
test((i+1) % 5); // test right neighbor
}
void test(int i)
{
if ( ( state[(i+4) % 5] != eating ) &&
( state[i] == hungry ) &&
( state[(i+1) % 5] != eating ) )
{
state[i] = eating; self[i].signal();
}
}
void init()
{
for ( int i = 0 ; i < 5 ; i++ )
{
state[i] = thinking;
}
}
}Monitor를 사용하면 이렇게 구현할 수 있다. 이러면 Deadlock은 없지만 Starvation은 있을 수 있다.