critical section
critical section해결
do {
entry section
critical section
exit section
remainder section
} while(1);
프로세스들의 일반적인 구조다.
critical section을 해결하기 위해서
-
mutual exclusion (상호 배제)
어떤 프로세스가 critical section을 진행중이면 다른 모든 프로세스가 critical section에 들어가는 것을 막는다. -
progress
critical section에 아무런 프로세스가 없는 상태에서 critical section에 들어가려는 프로세스가 있으면 들어가게 해야한다. -
bounded waiting (유한 대기)
스타베이션을 막기 위해 프로세스가 critical section에 들어가려고 요청한 후 부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계를 둬야한다.
알고리즘 1
int turn = 0;
//프로세스1
do {
while(turn != 0);
critical section
turn = 1;
remainder section
} while(1);
//프로세스0
do {
while(turn != 1);
critical section
turn = 0;
remainder section
} while(1);
처음에 턴이 0으로 시작하면 프로세스1은 critical section으로 들어갈 수 있고 프로세스0은 턴이 1이 아닌 동안에 계속 while문을 돌게되어 critical section으로 들어갈 수 없다.
프로세스1이 턴을 1로 바꾸고 나오게 되면 그 때는 프로세스0이 critical section으로 들어갈 수 있게 되고 프로세스1은 턴이 0이 아닌동안에 while문을 계속 돌며 critical section으로 들어갈 수 없게 된다.
이 방법은 critical section은 충족하지만 progress가 해결되지 않는다.
예를 들어 프로세스0이 한번만 들어가고 더 이상 들어가지 않는다면 턴이 돌아오지 않아 프로세스1은 영원히 들어갈 수 없다.
알고리즘 2
flag[i] = false
flag[j] = false
//프로세스i
do {
flag[i] = true;
while(flag[j]);
critical section
flag[i] = false;
remainder section
} while(1);
//프로세스j
do {
flag[j] = true;
while(flag[i]);
critical section
flag[j] = false;
remainder section
} while(1);
프로세스가 들어가고 싶을 때 플래그를 설정해 사실을 알린다.
플래그는 모두 false로 시작한다.
critical section에 들어가기 전에 다른 프로세스가 플래그를 세팅했는지 확인하고 세팅을 했을면 기다리고 아니면 들어간다. 나올 때 자신의 플래그를 false로 만들어 상대가 들어올 수 있게 한다.
이 방법은 프로세스i가 플래그를 true로 세팅만 한 채로 CPU가 프로세스j에게 넘어가면 둘다 플래그가 true가 되면서 들어갈 수 없는 상황이 생긴다.
알고리즘 3 (Peterson’s Algorithm)
//프로세스i
do {
flag[i] = true;
turn = j;
while(flag[j] && turn == j);
critical section
flag[i] = false;
remainder section
} while(1);
//프로세스j
do {
flag[j] = true;
turn = i;
while(flag[i] && turn == i);
critical section
flag[j] = false;
remainder section
} while(1);
1,2번 알고리즘을 섞은 방식이다.
critical section문제를 모두 해결했지만 CPU와 메모리를 계속 쓰면서 기다리는(busy waiting = spin lock)문제가 생기게 된다.
semaphores
세마포어 S는 정수값을 가지는 변수고, P와 V명령에 의해서만 접근 가능하다.
P연산은 S값이 0이하인 동안에 while문을 돌며 기다린다.
V연산은 다시 돌려준다.
방법 1
P(S) {
while S <= 0; // 아무것도 하지 않음 (반복문)
S--;
}
V(S) {
S++;
}
semaphore 5면 자원이 5개, P연산을 1번하면 자원을 하나가져가 4개가 된다.
V연산을 하면 다시 5개로 늘어난다.
P연산으로 자원을 가져와 사용하고 끝나면 V연산으로 돌려준다.
// semaphore mutex = 1
do {
P(mutex);
critical section
V(mutex);
remainder section
} while(1);
들어갈 때 P 나올 때 V
이 방식도 결국 spin lock이다.
방법 2
block&wakeup방식(=sleep lock)은 자원을 쓰지 않고 잠들어버리게 한다.
typedef struct
{
int value; // semaphore
struct process *L; // 잠들어있는 프로세스를 연결하는 큐
} semaphore;
P(S) {
S.value--;
if (S.value < 0)
{
add this process to S.L;
block();
}
}
세마포어가 음수라면 커널은 block을 호출한 프로세스를 suspend시키고 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣는다.
즉 세마포어가 음수면 잠든상태로 대기하게 된다.
V(S) {
S.value++;
if (S.value <= 0)
{
remove a process P from S.L;
wakeup(P);
}
}
세마포어가 0이하라는 것은 P에서 음수가 되어 기다리는 프로세스가 있다는 말이니 block된 프로세스P를 wakeup시키고 이 프로세스의 PCB를 ready queue로 옮긴다.
busy-wait vs block/wakeup
block/wakeup을 쓰는게 보통은 좋다.
크리티컬 섹션의 길이가 길 때는 block/wakeup이 좋지만 짧을 때는 오버헤드가 커진다.
counting semaphore
도메인이 0이상인 임의의 정수값 주로 resource counting에 사용
binary semaphore(=mutex)
0또는 1만 가질 수 있다
주로 mutual exclusion(lock/unlock)에 사용
semaphore문제점
//프로세스0
P(S);
P(Q);
...
V(S);
V(Q);
//프로세스1
P(Q);
P(S);
...
V(Q);
V(S);
이런 상황에서 deadlock이 생길 수 있다.
프로세스0에서 S를 얻은 상태로 CPU가 프로세스1로 넘어가고 Q를 얻게 되면 deadlock이 된다.
//프로세스0
P(S);
P(Q);
...
V(S);
V(Q);
//프로세스1
P(S);
P(Q);
...
V(Q);
V(S);
이렇게 S를 먼저 얻어야만 하게 만들면 해결할 수 있다.
동기화 문제
Bounded-Buffer Problem
/* 내용이 들어있는 버퍼의 개수를 세기 위함
처음에 내용이 들어있는 버퍼의 개수가 0개*/
semaphore full = 0;
/* 비어있는 버퍼의 개수를 세기 위함
처음에는 전부 비어있을 테니
비어있는 버퍼의 개수가 n개*/
semaphore empty = n;
// 락을 걸기위함
semaphore mutex = 1;
// Producer
do {
아이템을 생성
P(empty); // 빈 버퍼가 있는지 확인하고 획득
P(mutex); // 락을 건다
버퍼에 데이터를 집어넣는다
V(mutex); // 락을 푼다
V(full); // 내용이 들어있는 버퍼의 개수를 1증가 시킨다
} while(1);
// Consumer
do {
P(full); // 내용이 들어있는 버퍼가 있는지 확인하고 획득
P(mutex); // 락을 건다
버퍼에 데이터를 꺼낸다
V(mutex); // 락을 푼다
V(empty); // 비어있는 버퍼의 개수를 1증가 시킨다
} while(1);
생산자는 데이터를 만들어 공유버퍼에 삽입하고 소비자는 공유버퍼에서 데이터를 꺼내는 역할이다.
생산자가 동시에 같은 위치에 데이터를 넣게되면 문제가 생기게 되니 먼저 락을 걸고 데이터를 집어넣고 락을 풀게된다.
소비자도 마찬가지의 절차를 거친다.
버퍼의 크기가 유한한 환경에서 생기는 문제는
생산자가 한꺼번에 공유버퍼를 다 채우게 됐을 때 생산자가 또 버퍼를 채우려면 소비자가 데이터를 꺼내야 생산자가 데이터를 넣을 수 있다.
생산자 입장에서의 자원은 비어있는 버퍼의 개수가 세야될 자원개수이다.
반대로 소비자 입장에서는 채워져있는 버퍼의 개수가 자원의 개수이다.
생산자는 빈 버퍼를 확인하고 없으면 기다린다.
빈 버퍼가 생기면 공유버퍼에 락을 걸고 빈 버퍼에 데이터를 입력한 후 비어있는 버퍼의 포인터 위치를 하나 증가시킨다.
그 다음 락을 풀고 채워져있는 버퍼의 개수를 증가시킨다.
소비자는 반대의 절차를 거친다.
Readers-Writers Problem
한 프로세스가 DB에 write중일 때 다른 프로세스가 접근해선 안된다.
다만 read는 동시에 여럿이 해도 된다.
read는 락은 걸지만 read는 허용해서 같이 읽을 수 있게 하고 write는 막는다.
int readcount = 0;
semaphore mutex = 1;
semaphore db = 1;
// Writer
P(db); // 락을 건다
DB에 쓴다
V(db); // 락을 푼다
// Reader
P(mutex); // readcount를 바꾸기 위해 락을 건다
readcount++; // 몇명이 읽고 있는지
if (readcount == 1) P(db); // 만약 내가 최초의 리더라면 DB에 락을 건다
V(mutex); // readcount에 대한 락을 푼다
DB를 읽는다
P(mutex);
readcount--;
if (readcount == 0) V(db); // 만약 내가 마지막으로 읽고 나간다면 DB에 락을 푼다
V(mutex);
이 방법은 writer가 스타베이션이 발생 가능하다.
Dining-Philosophers Problem
do {
P(chopstick[i]);
P(chopstick[(i + 1) % 5]);
eat();
V(chopstick[i]);
V(chopstick[(i + 1) % 5]);
think();
} while(1);
모든 철학자가 동시에 왼쪽 젓가락을 집어버리면 데드락이 생기게 된다.
데드락을 해결하려면 4명의 철학자만 동시에 앉을 수 있게 하거나
젓가락을 두개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 하거나
짝수 철학자는 왼쪽 젓가락만 집도록 만들면 된다.
/*self[1] = 0이면 1번 철학자가 젓가락 두개를 잡을 수 있는 권한이 없다
self[2] = 1이면 2번 철학자가 젓가락 두개를 잡을 수 있는 권한이 있다
처음에 0으로 시작하고 권한을 주면 1이 된다.*/
semaphore self[5] = 0;
// 생각하고, 배고프고, 먹는 상태
enum {thinking, hungry, eating} state[5];
/* 옆의 철학자의 상태를 바꿀 수 있기 때문에 공유변수이고
공유변수에 동시접근을 막기위한 락을 나타냄*/
semaphore mutex = 1;
// Philosopher i
do {
pickup(i);
eat();
putdown(i);
think();
} while(1);
void putdown(int i) {
P(mutex);
state[i] = thinking;
test((i + 4) % 5); // 젓가락을 내려놓을 때 왼쪽 철학자가 잡기위해 대기하고 있으면 잡을 수 있게 챙겨준다
test((i + 1) % 5); // 오른쪽 철학자에대한 같은 코드
V(mutex);
}
void pickup(int i) {
P(mutex); // 상태를 건들기 때문에 락을 건다
state[i] = hungry; // 상태를 hungry로 바꾼다
test(i); // 젓가락 2개를 잡을 수 있는 상태인지 테스트
V(mutex); // 락을 푼다
P(self[i]); // 테스트를 통과하면 젓가락을 잡은 상태가 된다 테스트를 통과하지 못하면 0인 상태라 대기하게 되고 옆의 철학자가 챙겨주면 잡게 된다
}
void test(int i) {
// 왼쪽 철학자가 밥먹고 있지 않고 오른쪽 철학자도 밥먹고 있지 않고 내가 배고픈 상태
if (state[(i + 4) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
state[i] = eating; // 상태를 eating으로 바꾼다
V(self[i]); // 젓가락 잡을 권한을 준다(0에서 1로 바꾼다)
}
}
젓가락을 두개 모두 집을 수 있을 때만 집을 수 있게하는 코드다.
monitor
세마포어는 한번의 실수가 모든 시스템에 치명적이고 검증하기가 어려운 문제가 있다.
모니터는 공유데이터를 접근하기 위해선 모니터의 내부 절차에 의해서만 공유데이터에 접근할 수 있다. 모니터 내에서는 한번에 하나의 프로세스만이 활동이 가능하기 때문에 락을 걸 필요가 없다.
그리고 프로세스가 모니터 안에서 대기할 수 있도록 하기 위해 condition variable을 사용한다. condition x, y;
condition variable은 wait와 signal연산에 의해서만 접근 가능하고
x.wait();로 suspend되고 x.signal();로 suspend된 프로세스를 재개한다.
monitor를 사용한 bounded-buffer problem
bounded-buffer {
int buffer[N];
condition full, empty;
void produce(int x) {
if 비어있는 버퍼가 없다면
empty.wait();
버퍼에 데이터를 넣는다
full.signal();
}
void consumer(int *x) {
if 내용이 들어있는 버퍼가 없다면
full.wait();
버퍼에 데이터를 꺼낸다
empty.signal();
}
}
모니터를 사용하면 이렇게 바꿀 수 있다.
monitor를 사용한 Dinning-Philosophers Problem
monitor dining_philosopher {
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((i + 1) % 5);
}
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;
}
}
}
Each Philosopher {
pickup(i);
eat();
putdown(i);
think();
} while(1)
Leave a comment