OS | Chapter 7 Synchronization examples

Yunny.Log ·2022년 10월 18일
0

OS

목록 보기
7/8
post-thumbnail
post-custom-banner

Chapter 7 Synchronization examples

Classical Problems of Synchronization

① Bounded-Buffer Problem

//Producer
while(true){
    ...
    /* produce an item in next_produced(새로운 item 하나 생성) */
    ...
    wait(empty) 
    // empty 는 empty-1이 된다. empty가 1~n 값중에서 시작했다면 다음줄로 넘어감.
    //만약 empty가 0이었다면 -1이 되어 block됌
    wait(mutex) 
    ...
    /* add next produced to the buffer(버퍼에 새로 생성된 item을 추가) */
    ...
    signal(mutex); 
    //버퍼에 item을 추가했으면, 
    //binary semaphore의 signal 함수를 호출하여 critical section의 탈출을 알린다.
    signal(full); 
    //signal(full)을 호출해서 0의 초기값을 count++를 통해 1로 만들어준다.
}
//Consumer
while(true){
    wait(full); 
    // 데이터를 꺼내기 위해 full 자원을 얻는다. 
    //버퍼에 item이 한 번도 안들어갔다면 0은 -1이 되어 block에 걸린다.
    wait(mutex); //full 자원이 있다면 lock을 걸기 위해 mutex를 실행한다. 
    ...
    /* remove an item from buffer to next_consumed(해당 버퍼에서 item을 꺼냄) */
    ...
    signal(mutex); 
    
    //item을 빼온 이후 signal 함수를 호출하여 critical section 탈출을 알린다. 
    signal(empty); 
    
    //signal(empty)를 호출해 데이터가 채워져 있는 버퍼의 공간 개수 하나를 뺀다.
    ...
    /* consume the item in next consumed(item을 소비함) */
    ...
}

  • 두 종류의 프로세스가 있다. 하나는 Producer, 또 다른 하나는 Consumer이다. 이는 생산자-소비자 문제(Producer-Consumer Problem)이라고도 불린다.

  • 여기서 발생할 수 있는 문제점은 어느 producer가 버퍼 중 빈 곳에 데이터를 쓰려고 할 때, interrupt가 발생하여 다른 프로세스한테 공유자원이 넘어가서 다른 프로세스가 해당하는 빈 곳에 데이터를 쓸 때 나타날 수 있다. > 그렇게 되면 둘 중 한 프로세스의 데이터가 유실될 가능성이 있다는 것

  • 만약 buffer가 꽉 찼다면 producer는 consumer가 item을 삭제할 때까지 기다려야 한다.
    producer는 buffer 안에 empty space가 필요하다.

    • number of empty slot 은 semaphore empty에 의해 나타나진다.

  • 만약 buffer가 비었다면 consumer는 producer가 item을 넣을 때까지 기다려야 한다.
    consumer는 buffer 안에 item이 필요하다.

    • number of item은 semaphore full에 의해서 나타나진다.

  • Producer-consumer problem with bounded buffer

    • Semaphores: full = 0, empty = n, mutex = 1;
    • 버퍼의 개수 n, binary semaphore : mutex, counting semaphore: empty, full

② Readers and Writers Problem

  • Readers와 Writers는 하나의 공유하는 데이터베이스를 가지고 있다.
  • Readers는 동시에 데이터베이스에 접근할 수 있지만, 한 writer가 shared data에 접근할 때, 어떤 thread도 그것에 접근할 수 없다.
  • (+) 독자(Reader)는 데이터를 읽기만 하는 프로세스, 저자(Writer)는 읽고 수정하는 프로세스
  • (+) 다수의 독자와 다수의 저자가 하나의 공통 데이터베이스를 사용할 때 발생할 수 있는 문제를 뜻하며, 이는 프로세스 동기화로 해결할 수 있다
//Shared data
semaphore mutex = 1;
semaphore rw_mutex = 1;
int read_count = 0;
//Writer
while(true){
	//writer은 공유 자원에 접근하면 다른 모든 프로세스들의 접근을 차단함.
    //binary semaphore로 다른 프로세스들의 critical section 진입을 일체 차단함.
    wait(rw_mutex);
    ...
    /* writing is performed(writing 수행) */
    ...
    signal(rw_mutex);
}

//Reader
while(true){
	//Reader에서는 Writer의 접근만 막을 뿜, Reader가 몇 명이 접근하는지는 신경쓰지 않음.
	
    wait(mutex); 
    // read_count에 대한 mutual exclusion을 보장하기 위한 설정
    read_count++; 
    // read_count가 0이라면 1로 증가시킨다. 
    if(read_count == 1)
    // read_count가 1이라면 wait(rw_mutex)를 실행, 
    // 이를 통해 writer은 임계구역에 진입 못함.
    	wait(rw_mutex);
        //reader는 read_count를 증가시킬 뿐, 
        // wait(rw_mutex)를 호출하지 않으므로 임계구역에 그냥 진입.
    signal(mutex);
    ...
    /* reading is performed */
    ...
    wait(mutex);
    read_count--;
    if(read_count == 0)
    // 임계구역에 머물러 있는 Reader가 하나도 없을 경우 
    // signal(rw_mutex)를 호출
    	signal(rw_mutex);
        //그럼으로써 writer가 공유 자원에 접근 가능하다.
    signal(mutex);
}

③ Dining-Philosophers Problem

'식사하는 철학자 문제'는 5명의 철학자가 식사를 하고 있는 상황을 가정한 문제이다. 5명의 철학자들이 원형의 테이블에 앉아 있는데 철학자들 사이에는 젓가락 한 짝만 놓여있고 철학자 앞에는 음식이 놓여있다. 철학자는 배가고프면 양 옆에 있는 젓가락을 사용해서 식사를 하고 다시 젓가락을 원위치에 두고 생각을 해야한다. 이때 생기는 문제는 한명이 음식을 먹고 있다면 양 옆에 앉은 철학자 두명은 배가 고파도 음식을 먹을 수 없는 상황이 온다. 따라서 젓가락에 대한 접근을 하는 것에 대한 문제 해결이 필요하다. 


while(true){
    wait(chopstick[i]);			//pick up left chopstick
    wait(chopstick[(i+1) % 5]);		//pick up right chopstick

    /* eat for a while */

    signal(chopstick[i]);		//release left chopstick
    signal(chopstick[(i+1) % 5]);	//release right chopstick

    /* think for a while */
}
  • This solution guarantees that no two neighbors are eating simultaneously.
    However, it has the possibility of a deadlock.
    Possible remedies to the deadlock problem.

해결책은 deadlock-free와 starcation-free가 되어야 한다. 즉, 교착과 기아가 생기지 않게 하는 방법을 생각해야 한다

  • Semaphore 해결방법
  • Shared data: Bowl of rice(dataset) / Semaphore chopstick[5] initialized to 1
  • 아래 코드는 해결가능성이 있는 방법을 나타낸다. 하지만 deadlock이 발생할 수 있다. 

while(true){
    wait(chopstick[i]);			//pick up left chopstick
    wait(chopstick[(i+1) % 5]);		//pick up right chopstick

    /* eat for a while */

    signal(chopstick[i]);		//release left chopstick
    signal(chopstick[(i+1) % 5]);	//release right chopstick

    /* think for a while */
}

< Deadlock이 발생하는 경우는 어떤 경우일까? >

  • This solution guarantees that no two neighbors are eating simultaneously.
  • However, it has the possibility of a deadlock.
  • 5명의 철학자가 다같이 배고파서 다같이 동시에 자신 왼쪽의 젓가락을 잡는다면 chopstick의 모든 원소는 0이 된다. 결국 철학자는 오른쪽 젓가락을 영원히 잡을 수 없다.
    -> 이렇게 Deadlock이 발생

< Possible remedies to the deadlock problem. >

  • Deadlock을 해결할 수 있는 방법(아래 3가지 조건 중 하나만 추가하면 해결 가능하다. 하지만 이 방법은 starvation의 가능성을 업애는 것은 아니다.)

    • (1) Allow at most 4 philosophers to be sitting simultaneously at the table.
      최대 4명의 철학자만이 테이블에 동시에 앉을 수 있게 한다.
    • (2) Allow a philosopher to pick up her chopsticks only if both chopsticks are available.
      한 철학자가 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 한다.
    • (3) Use an asymmetric solution; 비대칭 해결안을 사용
    • an odd philosopher picks up first her left chopsticks and then her right chopstick, whereas an even philosopher picks up her right chopstick and then her left chopstick.
      ex)홀수번째 철학자는 왼쪽 젓가락부터 집어야 하고 , 짝수번째 철학자는 오른쪽 젓가락부터 집어야 한다.

< Starvation의 경우는? >

  • A deadlock-free solution does not necessarily eliminates the
    possibility of starvation
  • 가운데 사람이 껴서 양쪽의 사람만 밥을 먹고 가운데 사람은 밥을 먹지 못하는 starvation이 생길 수 있다.

Starvation의 경우는?

  • 가운데 사람이 껴서 양쪽의 사람만 밥을 먹고 가운데 사람은 밥을 먹지 못하는 starvation이 생길 수 있다.

Allow at most 4 philosophers to be sitting simultaneously at the table.
Allow a philosopher to pick up her chopsticks only if both chopsticks are available.
Use an asymmetric solution; an odd philosopher picks up first her left chopsticks and then her right chopstick, whereas an even philosopher picks up her right chopstick and then her left chopstick.
A deadlock-free solution does not necessarily eliminates the possibility of starvation.

Dining Philosophers using Monitor

monitor DiningPhilosophers{
enum {THINKING; HUNGRY; EATING} state[5];
condition self[5]; // shared data의 영역에서 프로세스의 대기상태를 설정하기 위한 변수

    void pickup(int i){
        state[i] = HUNGRY; 
        // 젓가락을 들면 해당 철학자의 상태는 배고픈 상태로 설정
        test(i);
        if(state[i] != EATING)
            self[i].wait; 
            // 다른 철학자가 eating하고 있어서 해당 state의 상태를 wait로 설정
    }

    void putdown(int i){
        state[i] = THINKING; 
        // 해당 철학자는 다시 상태를 생각하는 것으로 설정
        //test left and right neightbors
        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(); 
            // 해당 코드는 putdown에서 사용 가능
        }
    }

    void initialization_code(){
        for(int i = 0; i<5; i++)
            state[i] = THINKING;
    }
}

  • monitor를 이용한 dining philosophers problem

  • 각각의 철학자 i는 아래와 같이 pickup()과 putdown() operation을 실행 

DiningPhilosopher.pickup(i)
...
/** EAT **/
...
DiningPhilosopher.putdown(i);

이 해결법은 Deadlock은 발생하지 않지만 starvation은 일어날 수 있다.

profile
Yunny.Log
이전 포스트

OS | Chapter 6 Synchronization Tools

다음 포스트

스레드 컨텍스트 스위칭 vs 프로세스 컨텍스트 스위칭 속도 차이와 멀티태스킹 과정

post-custom-banner

0개의 댓글