[OS] Classical Synchronization Problems

 

 

 

 

 

 

전통적 동기화

 

1. Producer and Consumer Problem

 

생산자가 일단 데이터를 생산하면 buffer에 저장하고 소비자는 buffer에 저장되어 있는 것을 소비한다.

buffer가 꽉차면 buffer가 소비자에 의해 비워질 때까지 생산자는 버퍼에 데이터를 저장할 수 없다.

buffer가 완전히 비면 소비자는 데이터를 빼내올 수 없다.

buffer는 데이터를 모아둘 수 있는 메모리 혹은 디스크 공간이다. → 용량이 유한하다. →  Bounded Buffer

 

class Buffer
{
	int[] 	buf;
    int 	size;
    int 	count;
    int 	in;
    int 	out;
	
    Buffer(int size)
    {
    	buf = new int[size];
        this.size = size;
        count = in = out = 0;
    }


    void insert(int item)  //데이터 집어넣음
    {
        while (count == size)  // 버퍼가 꽉찻다면 루프 돌면서 기다림
                ;
        buf[in] = item;
        in = (in+1) % size;  // in에 넣음
        count++;
    }

    void remove(int item)  // 데이터 빼냄
    {
        while (count == 0) // 버퍼가 비어있다면 루프 돌면서 기다림
                ;
        int item = buf[out];
        out = (out+1) % size; // out위치에 있는 것 빼냄
        count--;
        return item;
    }
}

이대로 실행하게 되면, 공통변수 count, buf[]에 대한 동시 업데이트가 일어나게 된다.

따라서 실행이 불가능하거나 count변수가 0이 아닌 값이 나오게 된다. = 버퍼에 최종적으로 1개 이상의 항목이 남아있게 된다.

(생산자가 돌다가 context switching되어 소비자가 돌게 되면 버퍼를 바꾸는 와중에 스위칭 일어나게 되어 엉망진창인 상황에 빠지게 됨)

 

이에 대한 해결방법으로 mutual exclusion, 세마포를 사용한 mutual exclusion 방법이 있다.

 

※ mutual exclusion ※

 

• critical section에 동시 접근 방지

생산자가 임계구역에 들어가면 소비자는 들어가면 안된다. 마찬가지로 소비자가 임계구역에 들어가면 생산자는 들어가면 안된다.

 

 

• 1개의세마포를 이용한 mutual exclusion

mutex.value = 1 // number of permit

 

 

• 3개의 세마포를 이용한 mutual exclusion → Busy wait

mutex.value = 1

empty.value = size  // 맨 처음 아무것도 생산하지 x → busy wait 하지 않고 버퍼가 빌 때까지 블락시켜 성능 향상

full.value = 0  // 맨 처음 빼낼 것이 아무것도 없음 → busy wait 하지 않고 버퍼가 찰 때까지 블락시켜 성능 향상

 

empty.value = 0이 되면 생산자는 블락됨 → 이를 소비자가 깨움. empty.release()

full.value = 0이 되면 소비자는 블락됨 → 이를 생산자가 깨움. full.release()

 

<생산자>
empty.acquire();
PRODUCE;
full.release();

<소비자>
full.acquire();
CONSUME;
empty.release();

버퍼가 가득차면 생산자는 세마포 감옥에 블락됨 → 더이상 cpu 서비스 받지 않음 →소비자가 버퍼에서 빼내면 빈공간 생기므로 블락된 것 깨움

버퍼가 비면 소비자는 세마포 감옥에 블락됨 → 더이상 cpu 서비스 받지 않음  →  생산자가 버퍼 채우면 블락된 것 깨움

 

 

 

2. Readers - Writers Problem

mutual exclusion은 한번에 한 프로세서만 접근하므로 비효율적이었다.

공통 데이터베이스를 가지고 원격지에서 공통적으로 접근한다. 데이터베이스의 접근이 임계구역을 생성한다.

Readers : 데이터베이스를 읽음

Writers : 데이터베이스를 씀

 

효율성 제고

Reader1이 데이터베이스를 읽으려 임계구역에 들어옴. 이 때 Reader2는 데이터베이스를 읽기만 하는 프로세서이므로 임계구역에 들어와도 된다. → 내용이 바뀌지x

한 reader가 들어오면 writer는 들어오지 못하고 기다려야 한다. writer는 reader가 다 빠져나간 후 들어갈 수 있다.

 

First R/W problem : 한 reader가 들어오면 writer는 들어오지 못하고 기다려야 한다. writer는 reader가 다 빠져나간 후 들어갈 수 있다.

Second R/W problem : writer가 reader보다 우선

Third R/W problem : 우선권을 아무에게도 안줌

 

 

 

 

 

3. Dining Philosopher Problem

식사하는 철학자 문제

5명이 식사를 하기위해 모두 왼쪽 젓가락을 든다면 옆 사람이 젓가락 한쪽을 놔주지 않으므로 5명 모두 식사를 하지 못하는 상황이 발생하게 된다. → starvation현상. 데드락 발생

 

 

 

 

<요약>

os에서 가장 중요한 서비스 : process management

 

process management

1. cpu scheduling

2. processor synchronization

    1. mutual exclusion

    2. 효율성 제고 → busy wait 하지 않도록