[OS] 5-3. 여러가지 동기화 문제들
2022. 4. 17. 14:38ㆍMajor`/운영체제
1) Bounded-Buffer Problem
크기가 N인 Buffer가 존재
Producer : Buffer(N)에 데이터 저장
Consumer : Buffer(N)으로부터 데이터 읽기
$ 공유 자원
- Buffer
$ Semaphore
- Semaphore mutex = 1 :: Binary Semaphore & buffer에 대한 lock
- Semaphore empty = N :: Counting Semaphore
- Semaphore full = 0 :: Counting Semaphore
- empty, full이 Counting Semaphore인 이유는 buffer내부에 empty buffer & full buffer가 여러개 존재하기 때문
- 만약에 Binary Semaphore로 구현한다면 Producer는 empty buffer가 있음에도 불구하고 block당하게 된다
Semaphore로 구현
int buffer[N]
Semaphore mutex = 1 // Binary Semaphore
Semaphore empty = N // Counting Semaphore
Semaphore full = 0 // Counting Semaphore
"Producer"
do{
// Produce an Item
wait(empty); // empty buffer에 데이터 생산
wait(mutex); // Buffer에 대한 lock 얻기
...
// Add item to empty buffer
...
signal(mutex);
signal(full);
} while(true)
"Consumer"
do{
wait(full); // full buffer로부터 아이템 얻기
wait(mutex); // Buffer에 대한 lock 얻기
...
// Get an item from full buffer
...
signal(mutex);
signal(empty);
} while(true)Producer
1. 일단 buffer에 집어넣을 아이템 생산
2. 그리고 "empty" & "mutex" 자원 획득 요구
- wait(empty) : empty buffer가 생길 때까지 기다리기
- wait(mutex) : buffer에 대한 lock을 얻을때까지 기다리기 (Binary Semaphore "mutex")
3. 생산한 아이템을 buffer에 넣기
4. "full" & "mutex" 자원 반납
- signal(mutex) : buffer에 대한 lock을 반납하고 wait(mutex)를 통해서 block된 프로세스 하나 깨워주기
- signal(full) : full에 대한 자원 반납
- empty 자원을 획득해서 item을 넣었기 때문에 해당 자원은 full이 되었다
Consumer
1. "full" & "mutex" 자원 획득 요구
- wait(full) : full buffer가 생길 때까지 기다리기
- wait(mutex) : buffer에 대한 lock을 얻을때까지 기다리기
2. 자원을 획득했다면 buffer로부터 아이템 가져오기
3. "empty" & "mutex" 자원 반납
- signal(mutex) : buffer에 대한 lock을 반납하고 wait(mutex)를 통해서 block된 프로세스 하나 깨워주기
- signal(empty) : buffer에 empty 존재한다고 알려주기
Monitor로 구현
monitor Bound_Buffer{
int buffer[BUFFER_SIZE];
int itemCount;
int in; // produce 전용
int out; // consume 전용
condition full;
condition empty;
void produce(int item){
if(itemCount == BUFFER_SIZE){
empty.wait();
}
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
itemCount++;
full.signal();
}
element consume(){
if(itemCount == 0){
full.wait();
}
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
itemCount--;
empty.signal();
return item;
}
initialization_code(){
itemCount = 0;
in = 0;
out = 0;
}
}
Producer(){
int item;
while(true){
Bound_Buffer.produce(item);
}
}
Consumer(){
while(true){
item = Bound_Buffer.consume();
}
}
Monitor :: condition variable → Semaphore
monitor bound_buffer{
int buffer[BUFFER_SIZE];
int itemCount;
int in; // produce 전용
int out; // consume 전용
semaphore empty = BUFFER_SIZE // Counting Semaphore
semaphore full = 0 // Counting Semaphore
void produce(int item){
wait(empty);
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
itemCount++;
signal(full);
}
element consume(){
wait(full);
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
itemCount--;
signal(empty);
return item;
}
initialization_code(){
itemCount = 0;
in = 0;
out = 0;
}
}
Producer(){
int item;
while(true){
Bound_Buffer.produce(item);
}
}
Consumer(){
while(true){
item = Bound_Buffer.consume();
}
}2) Readers-Writers Problem
Readers : DB에서 데이터를 읽기만 하는 프로세스
Writers : DB에 데이터를 쓰기만 하는 프로세스
- Reader는 여러명이 동시에 DB에 접근이 가능하다
- Writer는 반드시 혼자만 DB에 접근이 가능하다
- Writer가 DB에 접근중이라면 모든 Readers는 DB에 접근이 불가능하다
- Writer는 현재 DB에 Reader가 없는 경우에만 DB에 접근이 가능하다
$ 공유 자원
- DB
- readCount : 현재 DB에 접근중인 Reader의 수
$ Semaphore
- Semaphore mutex = 1 :: Binary Semaphore & readCount에 대한 lock (Readers 전용)
- Semaphore DB = 1 :: Binary Semaphore & DB에 대한 lock
Semaphore로 구현
Database DB;
int readCount = 0;
Semaphore mutex = 1 // Binary Semaphore :: readCount Access
Semaphore DB = 1 // Binary Semaphore :: DB Access
"Writer"
do{
wait(DB);
...
// Writing is performed
...
signal(DB);
} while(true)
"Reader"
do{
wait(mutex);
readCount++;
if(readCount == 1){
wait(DB);
}
signal(mutex);
...
// Reading is performed
...
wait(mutex);
readCount--;
if(readCount == 0){
signal(DB);
}
signal(mutex);
} while(true)Writer
Writer는 DB에 대한 lock만 획득한다면 DB에 접근해서 데이터를 변경할 수 있다
물론 Reader가 이미 DB에 대한 lock을 획득했다면 writer는 block 당할 것이다
마지막 Reader가 나올 때 signal(DB)를 통해서 writer의 block을 풀어준다
Reader
Reader는 DB에 접근하려고 할 때마다 "readCount"를 증가시켜줘야 하기 때문에 별도의 Semaphore mutex가 존재한다.
그리고 처음 들어가는 Reader가 DB에 대한 lock을 획득하게 되는데 이 때 writer가 이미 DB에 접근중이라면 해당 reader는 block 당하게 된다
이에 따라서 나중에 들어가는 Reader들은 처음 들어간 Reader가 signal(mutex)를 해주지 않았기 때문에 wait(mutex) 단계에서 block을 당하게 된다
Monitor로 구현
// Reader가 높은 우선순위
monitor Reader_Writer{
int readCount;
int waitingReaders
int writeCount
int waitingWriters
condition reader;
condition writer;
void startWrite(){
if(writeCount == 1 || readCount > 0){
/*
writer 입장에서는 현재 DB에 아무도 없어야 접근할 수 있다
-> writer는 혼자만 접근가능 & Reader는 여러명이 동시에 접근 가능
*/
waitingWriters += 1;
writer.wait();
waitingWriters -= 1;
}
writeCount = 1;
}
void endWrite(){
writeCount = 0;
if(waitingReaders > 0){
// Reader가 우선순위가 높기 때문에 존재한다면 먼저 깨워주기
reader.signal();
}
else{
writer.signal();
}
}
void startRead(){
if(writeCount != 0){
waitingReader += 1;
reader.wait();
waitingReader -= 1;
}
readCount += 1;
}
void endRead(){
readCount -= 1;
if(readCount == 0){
writer.signal();
}
}
initialization_code(){
readCount = 0;
waitingReaders = 0;
writeCount = 0;
waitingWriters = 0;
}
}
Reader(){
Reader_Writer.startRead();
...
"Reading is performed"
...
Reader_Writer.endRead();
}
Writer(){
Reader_Writer.startWrite();
...
"Writing is performed"
...
Reader_Writer.endWrite();
}
// Writer가 높은 우선순위
monitor Reader_Writer{
int readCount;
int waitingReaders
int writeCount
int waitingWriters
condition reader;
condition writer;
void startWrite(){
if(writeCount == 1 || readCount > 0){
waitingWriters += 1;
writer.wait();
waitingWriters -= 1;
}
writeCount = 1;
}
void endWrite(){
writeCount = 0;
if(waitingWriters > 0){
// Writer가 우선순위가 높기 때문에 먼저 깨워주기
writer.signal();
}
else{
reader.signal();
}
}
void startRead(){
if(writeCount != 0){
waitingReader += 1;
reader.wait();
waitingReader -= 1;
}
readCount += 1;
}
void endRead(){
readCount -= 1;
if(readCount == 0){
writer.signal();
}
}
initialization_code(){
readCount = 0;
waitingReaders = 0;
writeCount = 0;
waitingWriters = 0;
}
}
Reader(){
Reader_Writer.startRead();
...
"Reading is performed"
...
Reader_Writer.endRead();
}
Writer(){
Reader_Writer.startWrite();
...
"Writing is performed"
...
Reader_Writer.endWrite();
}
※ Starvation
위의 코드에서는 Reader와 Writer간의 우선순위를 정해주어서 우선순위에 따라서 signal()을 표현한 코드이다
만약 Reader - Writer 간의 우선순위가 존재하지 않는다면 어느 하나의 type은 다른 type의 연속적인 access에 의해서 Starvation문제가 발생할 것이다
횡단보도의 신호등도 이와 같이 우선순위를 선정해주어서 구현한 객체이다
만약 신호등에 정해진 Time Quantum이 없다면 자동차든 보행자든 어느 하나의 type만 지속적으로 횡단보도라는 공유 Data에 Access할 것이다
이러한 Starvation을 해결하기 위해서 신호등도 일정한 Time Quantum을 두어서 Time Quantum이 종료되면 상대방이 횡단보도를 Access할 수 있도록 구현해주었다
하지만 위의 코드처럼 단순히 우선순위만 부여한다고 Starvation이 완전히 해결되는 것은 아니다
왜냐하면 우선순위와 상관없이 높은 우선순위인 type이 계속해서 밀려들어온다면 낮은 우선순위는 아마 Access를 받지 못할 것이 예상되기 때문이다
따라서 우선순위를 부여하고 + Count에 제한을 두어서 하나의 type이 Access할 수 있는 upper bound를 정해주어야 한다
Monitor :: condition variable → Semaphore
monitor Reader_Writer{
int readCount;
semaphore DBAccess; // Reader & Writer의 DB 접근 관련 Mutual Exclusion 방지 Binary Semaphore
semaphore reader; // readCount에 접근하기 위한 Binary Semaphore
void startWrite(){
wait(DB);
}
void endWrite(){
signal(DB);
}
void startRead(){
wait(reader);
readCount++;
if(readCount == 1){
wait(DB);
}
signal(reader);
}
void endRead(){
wait(reader);
readCount--;
if(readCount == 0){
signal(DB);
}
signal(reader);
}
initialization_code(){
readCount = 0;
}
}
Reader(){
Reader_Writer.startRead();
...
"Reading is performed"
...
Reader_Writer.endRead();
}
Writer(){
Reader_Writer.startWrite();
...
"Writing is performed"
...
Reader_Writer.endWrite();
}3) Dining-Philosophers Problem
철학자 5명이 원형 식탁에 앉아서 밥을 먹으려고 한다
>> 이 때 철학자 개개인은 본인 앞에 존재하는 젓가락 2개를 모두 집어야지 밥을 먹을 수 있다
$ 공유 자원
- chostick
$ Semaphore
- semaphore chopstick[5]
Semaphore로 구현
Semaphore chopstick[5] = {1, 1, 1, 1, 1};
"Each Philosopher"
do{
wait(chopstick[i]); // 왼쪽 젓가락 잡기
wait(chopstick[(i + 1) % 5]); // 오른쪽 젓가락 잡기
...
// eating
...
signal(chopstick[i]); // 왼쪽 젓가락 반납
signal(chopstick[(i + 1) % 5]); // 오른쪽 젓가락 반납
...
// thinking
...
}while(true)하지만 이러한 solution은 Deadlock이 발생할 수 있다
만약 5명의 철학자가 모두 배고파서 왼쪽 젓가락을 잡게되면 이제 필요한 것은 "오른쪽 젓가락"이다
하지만 오른쪽 젓가락은 내 오른쪽의 철학자가 왼쪽 젓가락을 잡으면서 이미 소유가 되어졌다
따라서 각자 자신의 왼쪽 젓가락은 소유하고 있으면서 오른쪽 철학자의 왼쪽 젓가락을 요구하고 있는 Deadlock이 발생한다
해결 1) 최대 4명의 철학자만 테이블에 앉도록 하기
해결 2) 철학자는 젓가락을 2개 전부 잡을 수 있을 때만 젓가락을 잡도록 허용 >> 이러면 critical section 내에서 젓가락을 잡아야 한다
해결 3) 비대칭 :: 홀수 철학자는 왼쪽 젓가락부터 & 짝수 철학자는 오른쪽 젓가락부터
물론 이러한 해결방안이 Deadlock을 해결해줄 수는 있지만 Starvation을 해결해주지는 않는다
Monitor로 구현
monitor DiningPhilosophers{
enum {thinking, hungry, eating} state[5];
// 5명의 철학자 모두 3가지의 State중 하나의 State를 보유할 것이다
condition self[5];
// 5명의 철학자 각각 현재 젓가락을 2개 모두 집을 수 있는 상태인지
// 모두 집을 수 없다면 wait()
void pickup(int i){
state[i] = hungry;
test(i); // "i번째 철학자"가 현재 젓가락 2개를 모두 집을 수 있는 상황인지 test
if(state[i] != eating){
self[i].wait();
}
}
void putdown(int i){
state[i] = thinking; // 밥 다먹고 다시 생각
test((i + 1) % 5);
test((i + 4) % 5);
// 내가 젓가락 2개 내려놓음으로써 양쪽 사람들이 젓가락 잡을 수 있으므로 양쪽 사람들 test
}
void test(int i){
// 현재 i번째 철학자가 젓가락 2개 집을 수 있는 상태인가 :: 양쪽 철학자 & 본인 상태에 의해 결정
if(
state[(i + 1) % 5] != eaiting &&
state[i] == hungry &&
state[(i + 4) % 5] != eaiting
){
state[i] = eating;
self[i].signal();
}
}
initialization_code(){
for(int i=0; i<5; i++){
/*
초기 : 전부 생각중
밥 먹을 생각 : 일단 hungry로 변환
젓가락 2개 모두 집을 수 있는 상태 : eaiting으로 변환해서 밥 먹기
*/
state[i] = thinking;
}
}
}Deadlock은 없어졌지만 여전히 Starvation은 존재한다
내 왼쪽 사람이 putdown을 하지 않으면 나는 영원히 밥을 먹지 못한다
Monitor :: condition variable → Semaphore
monitor DiningPhilosophers{
enum {thinking, hungry, eating} state[5];
semaphore self[5] = {0, 0, 0, 0, 0};
// 5명의 철학자 각각 현재 젓가락을 2개 모두 집을 수 있는 상태인지
// 모두 현재 잡을 수 없다고 가정하고 "0으로 초기화" (Binary Semaphore)
void pickup(int i){
state[i] = hungry;
test(i);
wait(self[i]);
}
void putdown(int i){
state[i] = thinking;
test((i + 1) % 5);
test((i + 4) % 5);
}
void test(int i){
// 현재 i번쨰 철학자가 젓가락 2개 집을 수 있는 상태인가 :: 양쪽 철학자 & 본인 상태에 의해 결정
if(
state[(i + 1) % 5] != eating &&
state[i] == hungry &&
state[(i + 4) % 5] != eating
){
state[i] = eating;
signal(self[i]);
/*
2개 모두 잡을 수 있다면 signal(self[i])를 통해서 self[i]의 Semaphore lock 풀어주기
이러면 pickup()에서 wait(self[i])는 lock을 얻게 된다
따라서 "나"는 이제부터 밥 먹기 가능
*/
}
}
initialization_code(){
for(int i=0; i<5; i++){
/*
초기 : 전부 생각중
밥 먹을 생각 : 일단 hungry로 변환
젓가락 2개 모두 집을 수 있는 상태 : eaiting으로 변환해서 밥 먹기
*/
state[i] = thinking;
}
}
}
"Each Philosopher"
DiningPhilosophers.pickup(i);
...
// Eating
...
DiningPhilosophers.putdown(i);