여러 곳에서 같은 자원을 사용할 때는 항상 조심해야 한다.
자원의 일관성이 깨질 수 있기 때문이다.
여러 곳에서 같은 자원에 접근하여 모순이 발생하는 상황을 Race Condition이라 한다.
그리고 공유 자원을 사용하는 코드영역을 Critical Section이라고 한다.
운영체제에서도 Race Condition이 발생한다.
프로세스들이 같은 커널영역을 사용하기 때문이다.
따라서 운영체제는 Critical Section에 진입하는 프로세스들을 동기화 시켜야 한다.
동기화는 앞에 일어나고 있는 작업의 결과를 반영한다는 뜻 이다.
예를 들어 점심 메뉴를 고르는 경우를 생각해보자.
친구 A가 떡볶이를 고르고, 친구 B는 튀김을 골랐다.
나는 친구 A와 친구 B의 메뉴를 고려하여 순대를 골랐다.
이러한 경우 내가 메뉴 고르는 작업을 친구들과 동기화 시킨 경우다.
반면 친구들이 떡볶이를 고르든 순대를 고르든 신경쓰지 않고,
그냥 돈까스를 고른 경우는 비동기적으로 메뉴를 고른 경우다.
동기화를 위한 조건
Race Condition이 발생하지 않도록 프로세스를 동기화 시키기 위해서,
아래와 같은 조건을 만족시켜야 한다.
Mutual Exclusion
한 프로세스가 Critical Section에 있다면,
다른 프로세스는 Critical Section에 진입하면 안된다.
Progress
현재 Critical Section에 프로세스가 없다면,
Critical Section에 진입하길 원하는 프로세스는 진입할 수 있어야 한다.
Bounded Waiting
Critical Section 앞에서 무한정 대기하는 프로세스는 없어야 한다.
해결방법
이제 프로세스를 동기화 시키는 방법을 알아보자.
Interrupt on / off
프로세스가 Critical Section에 진입할 때 Interrupt를 off 하고,
Critical Section에서 나올 때 Interrupt를 on하는 방식이다.
이 방식은 동기화 조건을 모두 만족시킨다.
그러나 운영체제에서 사용하는 CPU가 1개인 경우에만 가능한 방식이다.
하나의 CPU에서 Interrupt를 off 한다고 다른 CPU의 Interrupt가 off 되지 않는다.
Peterson's Algorithm
직접 코드로 동기화를 구현 하는 방식이다.
피터슨 알고리즘은 boolean타입의 flag와 int타입의 turn변수를 사용하여,
두개의 프로세스를 동기화 하는 알고리즘이다.
어떤 과정을 거쳐서 flag와 turn변수를 사용하게 되었는지 살펴보자.
첫번째는 turn변수만 사용한 경우다.
do{
while(turn != my_process_num);
// critical section
turn = another_process_num;
// 나머지...
}while(1);turn 변수를 사용하여 Mutual Exclusion을 구현했다.
나의 프로세스 번호가 아니면 while 문에서 대기한다.
나의 프로세스 번호면 critical section에 진입이 가능하고,
이후에 turn을 상대 프로세스 번호로 바꾼다.
이 방식의 문제점은 critical section에 교대로 진입해야 한다는 점이다.
내가 100번 도착해도 상대방이 도착하지 않아 turn을 바꿔주지 않는다면,
critical section에 진입하지 못한다.
두번째는 flag변수만 사용한 경우다.
do{
flag[i] = true; // 여기서 두 프로세스가 인터럽트를 당하면 무한 대기 해야한다.
while(flag[j]);
// critical section
flag[i] = false;
// 나머지...
}while(1);이 방식은 critical section에 교대로 진입하는 문제를 해결했다.
그러나 두 프로세스가 flag를 true로 바꾸자마자 인터럽트를 당했다면,
두 프로세스는 critical section 앞에서 무한정 대기해야 한다.
flag와 turn변수를 사용한 피터슨 알고리즘이다.
do{
flag[i] = true;
turn = j;
while(flag[j] && turn == j);
// critical section
flag[i] = false;
// 나머지...
}while(1); critical section에 교대로 진입하는 문제와,
critical section 앞에서 무한정 대기하는 문제를 해결했다.
하지만 이 방식은 2가지 문제점이 존재한다.
첫 번째는 busy waiting(=spin lock)이다.
자기의 차례가 아닌 경우 critical section 앞에서 cpu를 소모하며 대기한다.
cpu를 이용하여 의미 없는 반복문만 연산하고 있는 것이다.
두 번째는 개발자가 코딩하기 너무 어렵다는 것이다.
보기에는 간단해 보여도 굉장히 많은 경우를 포함하는 함축적인 코드다.
그리고 프로세스 개수가 2개가 아니라 더 늘어난다면 상황은 복잡해진다.
Test_and_Set
하드웨어를 사용하여 동기화를 구현하는 방식이다.
하드웨어로부터 읽고 쓰는 것을 한 번에 하는 atomic연산을 지원받는다면,
두 번째 문제를 해결할 수 있다.
boolean lock = false;
do{
while(Test_And_Set(lock));
// critical section
lock = false;
// 나머지 작업...
}while(1);Test_And_Set(lock)은 현재 lock를 리턴하고, lock에 true를 대입한다.
lock가 false인 경우 lock에 true를 대입하고 while문을 나올 수 있다.
lock가 true인 경우 lock에 true를 대입하고 while문을 나올 수 없다.
하지만 여전히 busy waiting(=spin lock)이 존재한다.
Semaphore
세마포어는 프로세스 동기화를 위해 운영체제에서 지원하는 자료형이다.
다음과 같이 정의할 수 있다.
struct Semaphore{
int value;
struct Queue *blocked;
};세마포어는 int형 변수 1개와 block된 프로세스 큐 1개를 가지고 있다.
int형 변수는 critical section에 현재 진입가능한 프로세스 수를 나타낸다.
큐는 현재 프로세스가 critical section에 진입하지 못하여 대기하는 경우를 나타낸다.
세마포어는 직접 변수를 조정할 수 없고, P 연산과 V 연산을 통해서만 조정할 수 있다.
그리고 P 연산과 V 연산은 atomic 이어야 한다.
function P(S) {
S.value--;
if(S.value < 0){
S.blocked에 현재 프로세스 push;
현재 프로세스 block;
}
}
function V(S) {
S.value++;
if(S.value <= 0){
S.blocked에서 pop한 프로세스를 CPU 대기 큐로 옮긴다;
}
}P 연산은 critical section에 들어갈 때 하는 연산이며, value를 1 감소시킨다.
value가 0 미만이 되면 critical section이 꽉 차있는 상태다.
따라서 blocked로 이동하고, CPU를 반납한다.
V 연산은 critical section에서 나올 때 하는 연산이며, value를 1 증가시킨다.
value가 0 이하인 경우는 blocked에 프로세스가 존재한다는 뜻이다.
따라서 blocked에서 프로세스를 꺼내와 CPU 대기 큐로 옮긴다.
struct Semaphore S;
do{
P(S);
// critical section
V(S);
// 나머지 작업...
}while(1);세마포어를 이용하여 프로세스 동기화를 구현하였다.
이렇게 하게 되면 코드도 간결해지고, busy waiting(=spin lock) 문제도 발생하지 않는다.
Monitor
세마포어로 인해 코드가 간결해졌다.
그러나 공유 자원이 많아질수록 프로그래머가 신경 써야 할 부분이 많아지고,
많이 어려워진다.
그리고 한 번 오류가 나면, 찾기 어렵다.
그래서 프로그래밍 언어 차원에서 Monitor라는 객체를 지원해 준다.
Monitor는 공유 데이터와 critical section을 처리하는 메소드로 이루어져 있다.
Monitor의 메소드에는 오직 하나의 프로세스만 접근할 수 있다.
프로세스 및 스레드의 동기화를 프로그래밍 언어 차원에서 지원해주며,
프로그래머는 모니터를 사용하면, 공유 자원에 대한 잠금과 해제를 신경쓰지 않아도 된다.
참고자료
http://www.kocw.net/home/cview.do?cid=3646706b4347ef09
https://www.youtube.com/watch?v=AnYN-kbCbRI&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=18
