운영체제(OS)

동기화 문제 (Problems of Synchronization)

yoongrammer 2021. 3. 21. 17:33
728x90

목차

    동기화 문제 (Problems of Synchronization)

    동기화에는 다음과 같은 고전적인 문제들이 있습니다.

    • Bounded-buffer (Producer-Consumer) Problem
    • The Readers-Writers Problem
    • 식사하는 철학자 문제(The Dining-Philosophers Problem)

    이번에는 세마포어를 사용하여 고전적인 문제들을 해결방법에 대해서 알아보도록 하겠습니다.

    Bounded-buffer (producer-consumer) problem

    생산자 소비자 문제라고도 하는 경계 버퍼 문제는 동기화의 고전적인 문제 중 하나입니다.

     

    문제 설명

    n개의 슬롯의 버퍼가 있으며 각 슬롯은 하나의 데이터를 저장할 수 있습니다.

    실행 중인 두 개의 프로세스, 즉 생산자(in)와 소비자(out)가 버퍼에서 작동합니다.

    size 16인 버퍼

    생산자가 버퍼의 빈 슬롯에 데이터를 삽입하려고 합니다. 소비자는 채워진 슬롯에서 데이터를 제거하려고 합니다.

    이 두 프로세스는 동시에 실행되는 경우 예상치 못한 문제가 발생할 수 있습니다.

    해결방안

    이 문제를 해결하기 위해 세 가지 세마포어를 사용합니다.

    • mutex : 잠금을 획득하고 해제하는 데 사용되는 이진 세마포어입니다. (초기값 = 1)
    • empty : 빈 슬롯의 수를 나타내는 세마포어 (초기값 = n)
    • full : 버퍼에서 점유된 슬롯의 수를 나타내는 세마포어 (초기값 = 0)

    생산자 구현

    생산자는 다음과 같이 구현됩니다.

    Producer Process:
do {
  ...
  // produce an item in nextp
  ...
  wait(empty);    // empty > 0 까지 기다린 다음 'empty' 감소
  wait (mutex);   // 잠금 획득

  // add nextp to buffer

  signal(mutex);  // 잠금 해제
  signal(full);   // 'full' 증가

} while (TRUE);
    • 생산자에 대한 위의 코드를 보면 생산자가 빈 슬롯이 하나 이상 있을 때까지 먼저 대기하는 것을 볼 수 있습니다.
    • 그런 다음 생산자가 해당 슬롯 중 하나에 데이터를 삽입할 것이기 때문에 빈 세마포어를 감소시킵니다.
    • 그런 다음 버퍼에 대한 잠금을 획득하여 생산자가 작업을 완료할 때까지 소비자가 버퍼에 액세스 할 수 없도록 합니다.
    • 삽입 작업을 수행한 후 잠금이 해제되고 생산자가 버퍼의 슬롯을 방금 채웠기 때문에 full 값 이 증가합니다.

    소비자 구현

    소비자는 다음과 같이 구현됩니다.

    do { 
  wait(full);   // full > 0 까지 기다린 다음 'full' 감소
  wait(mutex);  // 잠금 획득
  ...
  // remove an item from buffer to nextc
  ... 
  signal(mutex); // 잠금 해제
  signal(empty); // 'empty' 증가
  ...
  // comsume the item in nextc
  ...
} while(TRUE);
    • 소비자는 버퍼에 가득 찬 슬롯이 하나 이상 있을 때까지 기다립니다.
    • 그런 다음 소비자가 작업을 완료한 후 점유된 슬롯 수가 1만큼 감소하므로 전체 세마포어를 감소시킵니다.
    • 그 후 소비자는 버퍼에 대한 잠금을 획득합니다.
    • 그 후 소비자는 전체 슬롯 중 하나의 데이터가 제거되도록 제거 작업을 완료합니다.
    • 그런 다음 소비자가 잠금을 해제합니다.
    • 마지막으로, 소비자가 점유된 슬롯에서 데이터를 제거하여 빈 상태로 만들기 때문에 빈 세마포어가 1씩 증가합니다.
    728x90

    The Readers-Writers Problem

    독자-저자 문제(Readers-Writers Problem)란 여러 명의 독자와 저자들이 하나의 저장 공간(버퍼)을 공유하며 이를 접근할 때 발생하는 문제입니다.

    문제 설명

    Readers-Writers 문제에서는 다음과 같이 두 가지 유형의 프로세스가 있습니다.

    • Reader : 공유 데이터만 읽고 변경하지 않는 프로세스
    • Writer : 공유 데이터를 추가 또는 변경할 수 있는 프로세스

    여러 reader가 공유 데이터를 동시에 읽을 수 있지만 한 명의 writer만 공유 데이터에 쓸 수 있습니다.

    writer가 공유 데이터를 쓸 때는 다른 프로세스는 접근할 수 없습니다.

    해결방안

    Reader 또는 Writer에게 우선권을 부여하여 해결합니다.

    • Reader에게 우선권 부여
      • reader가 데이터 접근에 대한 우선권을 가지고 있습니다. 계속해서 reader에 대한 접근 요청이 일어나면 writer에 기아 상태(starvation)가 발생할 수 있습니다.
    • Writer에게 우선권 부여
      • writer가 데이터 접근에 대한 우선권을 가지고 있습니다. 계속해서 writer에 대한 접근 요청이 일어나면 reader에 기아 상태(starvation)가 발생할 수 있습니다.

    누구에게 우선권을 부여하느냐에 따라 구현이 달라지게 됩니다.

     

    여기서는 reader에게 우선권을 부여하여 문제를 해결하는 경우를 보겠습니다.

     

    이 문제를 해결하기 다음과 같은 변수 및 세마포어를 사용합니다.

    • readcount : 현재 버퍼에 접근 중인 독자의 수를 나타냅니다. (초기값 = 0)
    • wrt : 저자를 차단하고 해제하기 위해 사용하는 세마포어입니다. (초기값 = 1)
    • mutex : 독자가 readcount와 wrt에 접근하는 것을 원자적으로 하기 위해 사용하는 뮤텍스(이진세마포어)입니다. (초기값 = 1)

    Writer 프로세스 구현

    do {
  wait(wrt);  // 읽고 있는 독자가 없을 때까지 기다림.
  ...
  // 쓰기 작업 수행
  ...
  signal(wrt);
} while (TRUE);
    • writer는 리소스에 reader가 없을 때까지 대기를 합니다.
    • 쓰기 작업을 수행한 후 signal 함수 호출로 wrt가 증가하며 다음 writer가 리소스에 액세스 할 수 있습니다.

    Reader 프로세스 구현

    do {
  wait(mutex);
    readcount ++;  // 독자 수 1 증가.
    if (readcount == 1)
      wait(wrt);  // 쓰고 있는 저자가 없을 때까지 기다림.
  signal(mutex);
  ...
  // 읽기 작업 수행
  ...
  wait(mutex);
    readcount --;      // 독자 수 1 감소
    if (redcount == 0)
      signal(wrt);     // 독자가 없다면 이를 저자에게 알림.
  signal(mutex);
} while (TRUE);
    • reader는 readcount를 업데이트할 때마다 잠금을 획득합니다.
    • reader가 임계 구역에 접근하려면 먼저 readcount를 증가시킨 다음 접근하고 이후 readcount를 감소시키고 나옵니다.
    • 세마포어 wrt는 임계 구역에 들어가는 첫 번째 reader와 임계 구역을 나가는 마지막 reader에서 사용됩니다.
    • 그 이유는 첫 번째 reader가 임계 구역에 들어가면 writer는 차단되기 때문입니다. 이제 새로운 reader만 임계 구역에 진입할 수 있습니다.
    • 마찬가지로 마지막 reader가 임계 구역을 나오면 현재 readcount가 0개이고 writer가 임계 구역에 접근할 수 있는 기회를 가질 수 있으므로 signal(wrt)를 사용하여 writer에게 신호를 보냅니다.

    The Dining-Philosophers Problem

    식사하는 철학자 문제(The Dining-Philosophers Problem)는 여러 프로세스에게 제한된 리소스를 할당하는 상황에서 발생할 수 있는 문제입니다.

    문제 설명

    아래 그림과 같이 다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 음식과 양옆에 포크가 하나씩 있습니다.

    • 이 철학자들은 먹고 생각하는 두 가지 활동을 번갈아 합니다.
    • 철학자는 먹고 싶을 때는 양 옆의 두 개의 젓가락을 사용해야 합니다.
    • 젓가락은 인접한 철학자만 사용할 수 있으며 동시에 두 명이 사용할 수 없습니다.
    • 철학자는 식사를 마치고  두 젓가락을 원래 위치에 내려놓은 뒤 생각에 잠깁니다.

    해결 방안

    간단한 해결 방안은 세마포어를 사용하여 젓가락을 나타내는 것입니다.

    wait() 함수를 호출하여 젓가락을 집어 들고 signal() 함수를 호출하여 젓가락을 내려놓습니다.

    구현

    젓가락 구조는 다음과 같습니다.

    semaphore chopstick[5];

    처음에는 젓가락을 사용하지 않기 때문에 젓가락들은 1로 초기화합니다.

     

    철학자 구조는 다음과 같습니다.

    do {
  wait( chopstick[i] );            // 왼쪽 젓가락을 집어듬.
  wait( chopstick[ (i+i) % 5] );   // 오른쪽 젓가락을 집어듬.
  ...
  // eat
  ...
  signal( chopstick[i] );          // 왼쪽 젓가락을 내려놓음.
  signal( chopstick[ (i+1) % 5] ); // 오른쪽 젓가락을 내려놓음.
  ...
  // think
  ...
} while(TURE);
    • 철학자는 왼쪽 젓가락 (chopsticks[i])과 오른쪽 젓가락 (chopsticks[i+1)%5) 순으로 집어 든 뒤 식사를 합니다.
    • 식사를 마치고 두 젓가락을 내려놓은 뒤 생각을 하게 합니다.

    위 해결책은 두 명의 이웃 철학자가 동시에 먹을 수 없도록 합니다.

    그러나 모든 철학자가 동시에 왼쪽 젓가락을 집는다면 누구도 먹을 수 없는 교착상태가 발생하게 됩니다.

     

    교착상태에 대한 해결책은 다음과 같은 방법들이 있습니다.

    1. 4명의 철학자만 테이블에 동시에 앉을 수 있도록 합니다.
    2. 왼쪽과 오른쪽 젓가락을 모두 사용할 수 있는 경우에만 젓가락을 집을 수 있게 합니다.
    3. 짝수 번째 철학자들은 자신의 왼쪽에 있는 젓가락부터, 홀수 번째 철학자들은 자신의 오른쪽에 있는 젓가락부터 집어 들도록 합니다.

     

    728x90
    저작자표시 비영리 변경금지