Blog-Shine

CS/OS (2022-1)

[OS] Process Synchronization - 3

샤아이인 2022. 11. 28.

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

 

이번 시간에는 Process 동기화와 관련된 고전적인 3가지 문제에 대하여 학습해보자!

 

3. Bounded-Buffer-Problem (Producer-Consumer Problem)

생상자, 소비자 문제에 대하여 알아보자.

공유 데이터

buffer 자체 및 buffer 조작 변수 (empty / full buffer의 시작 위치)

 

Producer (생산자)

생산자는 여러개가 있을 수 있다. 하는 역할은 공유 Buffer에 데이터를 삽입하는 역할을 한다.

 

Empty 버퍼가 있는지 확인한다. (없으면 기다림)

공유 데이터에 lock을 건다.

Empty 버퍼에 데이터를 입력하고 버퍼를 조작한다.

lock을 푼다.

Full 버퍼가 하나 증가한다.

 

Consumer (소비자)

소비자는 여러개가 있을 수 있다. 소비자는 공유 Buffer에서 데이터를 가져오는 역할을 한다.

 

Full 버퍼가 있는지 확인한다. (없으면 기다림)

공유 데이터에 lock을 건다.

Full 버퍼에서 데이터를 꺼내고 버퍼를 조작한다.

lock을 푼다.

Empty 버퍼가 하나 증가한다.

 

3 - 1) 발생 가능한 동기화 문제

3 - 1 - 1) 공유 버퍼 동시 접근 문제

공유 버퍼이기 때문에 생산자 여러 명이 동시에 한 버퍼에 데이터를 쓰거나 수정할 수 있다.

마찬가지로 생산자가 동시에 한 버퍼의 데이터를 읽어갈 수 있다.

따라서 Lock을 걸고 사용하도록 해야한다.

 

3 - 1 - 2) 공유 버퍼 사이즈 문제

또한 Buffer의 사이즈가 유한하기 때문에 발생할 수 있는 문제도 있다.

 

만약 버퍼가 가득 차 있는 상황에서 생산자가 또 도착하여 데이터를 삽입하려 하면 어떻게 될까?

=> 생산자 입장에서는 사용할 수 있는 자원이 없는 상태이다.

 

이런경우 소비자가 등장하여 데이터를 가져가 빈 버퍼의 공간이 생겨야만 해결할수 있다.

생산자는 이렇게 비어있는 버퍼의 공간이 생길때까지 기다려야 한다.

 

소비자도 마찬가지 이다.

버퍼에서 꺼내갈 데이터가 없다면 생산자가 내용을 만들어 버퍼에 추가해줄때까지 기다려야 한다.

 

3 - 1 - 3) 세마포어 변수

이 문제에서는 Semaphore 변수를 사용해야할 곳 이 총 2곳이다.

1. 동시 공유 버퍼 접근 문제를 막기 위한 공유 버퍼 Lock 변수 (synchronization variables)

2. 버퍼가 가득 차거나, 비어있는 경우 가용자원의 갯수를 세는 counting semaphore 변수 (shared data)

 

3 - 2) 예시 코드

full은 내용이 들어있는 버퍼의 수를 세기위한 용도이고, empty는 비어있는 버퍼의 수를 세기위한 용도이다.

 

▶ Producer

  • P 연산을 통해 empty변수를 사용하여 남은 버퍼 공간이 있는지 확인한다. 없으면 대기
  • P 연산을 통해 empty공간이 있다면 mutex를 0으로 만들고 임계 구역에 진입한다.
  • 버퍼에 데이터를 입력한다.
  • V 연산을 통해 mutex 값을 1로 만든다.
  • V 연산을 통해 full 세마포어 변수를 1 증가하고 임계 구역에서 나온다.

 

▶ Consumer

  • P 연산을 통해 full변수를 사용하여 내용이 들어있는 버퍼가 있는지 확인한다. 없으면 대기
  • P 연산을 통해 내용이 들어있는 버퍼 공간이 있다면 mutex를 0으로 만들고 임계 구역에 진입한다.
  • 버퍼에 데이터를 빼 간다.
  • V 연산을 통해 mutex 값을 1로 만든다.
  • V 연산을 통해 empty 변수의 값을 1 증가하고 임계 구역에서 나온다.

 

4. Readers-Writers Problem (독자-저자 문제)

4 - 1) 문제가 되는 상황

한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 된다. 하지만 read는 동시에 여러 명이 해도 된다!

이를 어떻게 해결할 것 인가?

 

4 - 2) 해결책

  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근할 수 있게 해 준다.
  • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
  • Writer가 DB에서 빠져 나가야만 Reader의 접근이 허용된다.

 

4 - 3) 공유 데이터

  • DB 그 자체
  • readCount (현재 DB에 접근 중인 Reader의 수)

 

4 - 4) 동기화 변수

binary semaphore 변수 2개를 사용한다.

  • mutex (공유 변수 readCount를 접근하는 코드 (임계 구역)의 상호 배제를 보장하기 위해 사용)
  • db (Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할)

 

4 - 5) 예시 코드

 

4 - 5 - 1)세마포어 설계

상호 배제를 보장해야 하므로 각각의 세마 포어 mutex, db의 값은 1로 지정하며, 다수의 Reader들이 readCount에 동시 접근하면 데이터 불일치의 위험이 있으므로 mutex를 정의하였다.

db 변수는 Reader와 Writer가 공통 데이터베이스에서 서로 상호 배제를  보장해야하므로 정의하였다.

 

▶ Wrtier 프로세스

  • P(db) 연산을 통해 공통 데이터베이스에 lock이 걸려있는지 확인한다.
  • lock이 걸려 있지 않으면 공통 데이터베이스에 lock을 걸고 임계 구역에 진입한다.
  • 쓰기 작업이 끝나면 V(db) 연산을 통해 공통 데이터베이스에 lock을 해제하고 임계 구역에서 빠져 나온다.

 

▶ Reader 프로세스

내가 읽기위해 lock을 사용했다면, 다른 프로세스들도 읽을 수 있도록 readCount변수를 활용하였다.

readCount는 몇명의 reader가 읽고 있는지를 나타낸다.

  • P(mutex) 연산을 통해 readCount 상호 배제 처리한다.
  • 아무도 read 하고 있는 프로세스가 없고 read 하려는 프로세스가 나 하나라면 공통 데이터베이스에 lock을 건다. (공통 데이터베이스에 lock이 걸려 있어도 read는 여러 프로세스가 동시에 가능)
    • 이때 만약 readCount == 1, 즉 처음 읽어 들어온것 이라면 P(db)를 통해 db에 lock을 건다.
  • V(mutex) 연산을 통해 임계 구역에서 빠져 나온다.
  • DB를 원하는 만큼 읽는다.
  • P(mutex) 연산을 통해 readCount 상호 배제 처리한다.
    • 이때 만약 readCount == 0, 즉 마지막으로 read를 그만하고 나가려는 프로세스가 나 하나라면 V(db)를 통해 공통 데이터베이스에 걸려있던 read lock을 해제한다.
  • V(mutex) 연산을 통해 임계 구역에서 빠져나온다.

 

▶ 위 예제의 문제점 (기아 현상 발생)

Writer가 쓰기 작업을 하고 싶어도 무조건 Read 하고 있는 프로세스인 Reader가 없어야 한다.

만약 Reader가 무한히 read 작업을 실행한다면 Writer는 영영 임계 구역에 진입 하지 못하는 Startvation에 빠질 수도 있다.

다만 해당 단점을 보완하는 예제는 난이도의 이유로 생략한다.

 

5. Dining-Philosophers Problem (식사하는 철학자 문제)

5 - 1) 문제 설명

철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다.

 

1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다.

2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다.

3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.

4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.

5. 다시 생각하다가 배고프면 1번으로 돌아간다.

 

5 - 2) 쉽게 떠올릴 수 있는 예제 코드

모두가 배고파서 동시에 왼쪽 젓가락을 드는 순간 오른쪽 젓가락을 들 수 없으므로 서로가 필요로 하는 자원을 무한히 기다리게 되는 Deadlock이 발생한다는 문제가 있다.

 

5 - 3) 해결 방안

  • 4명의 철학자만 테이블에 동시에 앉을 수 있게 한다.
  • 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 방향을 정해준다.

 

5 - 4) 세마포어 예제

// Variable
enum {thinking, hungry, earting} state[5]; // 철학자들이 가질 수 있는 상태
semaphore self[5] = 0; // 철학자들이 젓가락 2개를 모두 들 수 있는 지 판단 (1이면 가능)
semaphore mutex = 1; // state[i]를 동시에 접근하지 못하도록 상호 배제 기능, 옆의 철학자도 나의 상태를 바꿀 수 있기 때문

// Philosopher i
do {
    pickup(i); // 젓가락 2개를 잡고
    eat(); // 먹고
    putdown(i); // 젓가락 반납
    think();
} while (1);

void pickup(int i) {
    P(mutex); // state 상호 배제
    state[i] = hungry;
    test(i); // 내가 지금 젓가락 2개를 들 수 있는지 확인.
    V(mutex); // 임계 구역 탈출
    P(self[i]); // self[i] = 1로 변경, 젓가락 2개를 들 수 있는 상태로 변경
}

void putdown(int i) {
    P(mutex); // state 상호 배제
    state[i] = thinking;
    // 양 옆 철학자가 식사할 수 있는 상태인지 확인하고, 가능하면 식사하게 해 줌.
    test((i + 4) % 5);
    test((i + 1) % 5);
    V(mutex); // 임계 구역 탈출
}

void test(int i) {
    if (state[(i + 4) % 5] != eating // 왼쪽 철학자는 밥먹고 있지 않는
        && state[i] == hungry // 내가 지금 배고픈 상태 
        && state[(i + 1) % 5] != eating) // 오른쪽 철학자도 밥먹고 있지 않는
    {
        state[i] = eating;
        V(self[i]); // 젓가락 2개를 들 수 있는 상태로 변경
    }
}

 

기존 세마포어 코드와는 조금 다르게, self[i] 세마포어는 초기 값을 0으로 설정하는 것을 알 수 있다.

원래 보통 세마포어 변수의 값을 사용가능한 자원의 수로 설정하는 점을 생각하면 조금은 어색하다?

 

6. Monitor

6 - 1) 세마포어의 문제점

  • 코딩하기 힘들다.
  • 정확성의 입증이 어렵다.
  • 자발적 협력이 필요하다.
  • 한 번의 실수가 모든 시스템에 치명적인 영향을 끼친다.

위 사진에서 왼쪽과 같이 V, P연산의 순서를 잘못 정할수도 있고, 오른쪽 처럼 동일한 연산만 2번 사용하는 휴먼 에러가 발생할 수 있다.

 

6 - 2) 개념

모니터는 프로그래밍 언어 차원에서 동기화 문제를 해결할 수 있는 고수준 동기화 도구라고 할 수 있다.

 

프로세스가 공유 데이터에 접근하기 위해서는 위와 같이 모니터 내부의 프로시저(함수)를 통해서만 공유 데이터를 접근할 수 있도록 설계한다. 이는 객체지향 스럽다 할 수 있는것 같다?

 

예를 들어 공유 데이터들이 있으면 밖에서 직접적으로 접근할 수 있는 것이 아니라, 모니터 내부에 공유 데이터에 접근하는 프로시저(함수)를 정의해 놓고 이 프로시저를 통해서만 접근하게 제어한다.

 

모니터가 내부에 있는 프로시저는 동시에 여러 프로세스가 사용하지 않도록 통제하는 기능이 있다.

즉 모니터 내에서는 한 번에 하나의 프로세스만이 활동이 가능하도록 제어하므로, 프로그래머 입장에서 lock을 직접적으로 사용 할 필요가 없다는 장점이 생긴다.

 

모니터 안에 active한 프로세스가 없을 때, 외부 entry queue에서 기다리고 있는 프로세스가 들어와서 코드를 실행할 수 있게 된다.

 

▶ Condition Variable

세마포어에서 자원의 개수를 세는 로직이 필요하듯이, 모니터도 자원의 개수를 세는 로직은 필요하다. (다만 모니터는 lock을 프로그래머가 걸 필요는 없다는 점이 세마포어와의 큰 차이점)

 

모니터는 조건 변수를 사용하고, Condition Varialbe은 wait 또는 signal 연산에 의해서만 접근 가능하도록 제한한다.

 

Monitor에서의 Condition Varialbe은 기존의 Semaphore와 큰 차이점이 있는데,

바로 Condition Varialbe은 자원의 수를 카운트 하는 변수가 아니라는 점 이다!

Condition Varialbe은 process를 대기시키는 일종의 대기줄 역할을 하게 된다!

 

  • wait
    • 자원이 없으면 프로세스가 줄을 서서 기다리게 한다.
    • x.wait() 을 호출한 프로세스는 다른 프로세스가 x.signal() 을 호출하기 전까지 suspend 된다.

 

  • signal
    • 모니터에 접근하고 빠져나갈 때 signal 연산을 호출해서 기다리는 프로세스가 모니터에 접근할 수 있도록 한다.
    • x.signal() 은 정확하게 하나의 suspend된 프로세스를 resume 한다.
    • suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

 

6 - 3) 생산자 - 소비자 문제 코드를 모니터로 구현

monitor bounded_buffer
{
    int buffer[N];
    
    // full, empty 조건 변수는 값을 가지지 않고, 자신의 큐에 프로세스를 매달아서
    // sleep 시키거나 큐에서 프로세스를 깨우는 역할만 수행함.
    condition full, empty;

    void produce(int x) {
        if (empty 버퍼가 없다면) {
            empty.wait();
        }
        empty 버퍼에 x를 추가한다
        full.signal();
    }

    void consume (int *x) {
        if (full 버퍼가 없다면) {
            full.wait();
        }
        full 버퍼에서 데이터를 꺼내 간 뒤 *x에 값을 저장한다
        empty.signal();
    }

 

생성하거나 소비하기 위해서는 반드시 모니터 내부 코드를 통하여 실행해야 한다.

장점으로는 사용자가 직접 lock을 걸거나 푸는 일이 없다.

 

생산자

  • empty 버퍼가 없으면 empty 버퍼를 기다리는 큐에서 대기한다. (wait 연산)
  • empty 버퍼가 있다면 empty 버퍼에 데이터를 집어넣는다.
  • 작업이 끝나면 full.signal() 를 통해 full 버퍼를 기다리는 큐에게 프로세스 하나를 깨우라고 알린다.

 

소비자

  • full 버퍼가 없으면 full 버퍼를 기다리는 큐에서 대기한다. (wait 연산)
  • full 버퍼가 있다면 full 버퍼의 데이터를 꺼내서 *x에 값을 저장한다.
  • 작업이 끝나면 empty.signal() 를 통해 empty 버퍼를 기다리는 큐에게 프로세스 하나를 깨우라고 알린다.

 

6 - 4) 식사하는 철학자 문제 코드를 모니터로 구현

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();
        }
    }
}

// 각 철학자의 동작
Each Philosopher:
{
    pickup(i);
    eat();
    putdown(i);
    think();
} while (1)

 

pickup

  • 자신의 상태를 배고픈 상태로 변경한다.
  • 자신이 왼쪽 젓가락과 오른쪽 젓가락을 모두 들 수 있는지 확인한다.
    • 모두 들 수 있다면 자신의 상태를 먹는 상태로 변경하고, wait 큐에서 자신을 깨운다.
    • 모두 들 수 없다면 wait 큐에 대기한다.

 

putdown

  • 식사를 마쳤으므로 자신의 상태를 thinking 상태로 변경한다.
  • 자신의 왼쪽과 오른쪽 철학자에게 식사할 수 있는 기회를 준다.
    • 여기서 기회라는 것은 무조건 식사할 수 있다는 의미는 아니고, test() 함수를 통해 식사가 가능한지 판단할 수 있다는 의미이다.

 

test

  • 자신이 왼쪽 젓가락과 오른쪽 젓가락을 모두 들 수 있는지 확인하고, 가능하면 자신의 상태를 먹는 상태로 변경하고, wait 큐에서 자신을 깨운다.

 

출처 

https://core.ewha.ac.kr/publicview/C0101020140408134626290222?vmode=f 

 

반효경 [운영체제] 14. Process Synchronization 3

설명이 없습니다.

core.ewha.ac.kr

https://steady-coding.tistory.com/541

저작자표시

'CS > OS (2022-1)' 카테고리의 다른 글

[OS] Memory Management - 1  (0) 2022.11.29
[OS] Deadlock  (1) 2022.11.29
[OS] Process Synchronization - 2  (0) 2022.11.25
[OS] Process Synchronization - 1  (0) 2022.11.25
[OS] CPU Scheduling - 2 & Process Synchronization 도입  (0) 2022.11.24

댓글

티스토리툴바