운영체제 - 동시성 제어 문제

TopOfTheHead·2025년 8월 3일

운영체제

목록 보기
21/24

동시성 제어 문제 ( Concurrency - Control )의 대표적 예시

  • 한정 버퍼 문제 ( Bounded-Buffer Problem )
    。생산자 - 소비자 문제 ( Producer - Consumer Problem )

  • 독자 - 저자 문제( Readers - Writers Problem )
    。여러명의 독자와 저자들이 하나의 저장공간( 버퍼 )에 동시접근 시 발생하는 문제

  • 철학자들의 저녁식사 문제( Dining - Philosophers Problem )
    。OS 상 Deadlock 상태를 설명하기위한 문제

한정 버퍼 문제 ( Bounded - Buffer Problem )
。대표적 예시 : 생산자 - 소비자 문제 OS - IPC
。Buffer Pool이 각각 1개의 item을 포함하는 n개의 Buffer들로 구성
▶ 생산자 프로세스는 소비자 프로세스를 위해 full buffer 제공
▶ 소비자 프로세스는 생산자 프로세스를 위해 empty buffer를 제공

  • 한정버퍼문제 코드예시
    。생산자 M : 소비자 N 관계 에서의 단일 Buffer Pool로 접근 시
    ▶ Mutex 또는 Binary Semaphore로 임계영역 접근
    • 초기화
      。1개의 Binary Semaphore와 2개의 Counting Semaphore로 초기화

      。Binary Semaphore :
      mutex : Mutex 기능으로서 상호배제 보장을 위한 임계영역 동기화 역할 수행
      ▶ Buffer Pool에 동시접근을 방지하는 Lock 역할
      ▶ Counting Semaphore가 아니므로 오직 단일 프로세스만 Buffer Pool로 접근

      。Counting Semaphore :
      empty : Buffer Pool에 구성된 empty buffer수를 Counting

      full : full buffer의 수를 counting

      ex ) Empty Buffer로 구성된 Buffer Pool에 한개의 Empty Buffer에 item을 넣는 경우
      ▶ empty는 Buffer Pool의 최대 버퍼수 n--
      ▶ full은 0++
    int n;
semaphore mutex = 1; // // 임계영역 동기화 용도
semaphore empty = n; // Empty Buffer 카운트
semaphore full = 0; // Full Buffer 카운트
    • 생산자 프로세스 구조
    while (true){
  //
  // Buffer Pool의 Empty Buffer에 item을 포함시키는 코드
  //
  wait(empty); // Full Buffer로 꽉찬 경우 Wait Queue 대기
  wait(mutex); // 다른 프로세스가 임계영역 존재 시 Wait Queue 대기
  //
  // 임계영역
  // Buffer Pool에 Buffer Pool를 추가하는 코드란
  // Buffer Pool에 Empty Buffer가 있고 오직 한개의 프로세스만 접근 가능.
  //
  signal(mutex); // 프로세스 자원 반납
  signal(full); // Full Buffer가 추가되었으므로 full++
}

    。wait(empty) : Buffer Pool에 Empty Buffer가 존재하지 않는경우 Wait Queue에서 대기
    ▶ empty > 0을 만족할 경우 wait(mutex) 실행 및 empty--
    ▶ empty <= 0인 경우 Full Buffer로 꽉찬 상태로서 Wait Queue에서 대기

    。wait(mutex) : 단일 프로세스만 임계영역에 진입할 수 있도록 설정
    ▶ 다른 프로세스가 이미 임계영역에 진입하여 mutex == 0인 경우 Wait Queue에서 대기

    ▶ Buffer Pool에 Empty Buffer가 존재하고, 한개의 프로세스만 임계영역에 접근한 경우에만 Buffer Pool에 접근하여 Buffer를 작성

    。signal(mutex) : 프로세스가 자원 반납 시 선언
    ▶ mutex--

    。signal(full) : Buffer Pool에 1개의 Full Buffer가 생겼으므로 full++

    • 소비자 프로세스 구조
    while (true){
  wait(full); // Full Buffer가 없는경우 Wait Queue 대기
  wait(mutex); // 다른 프로세스가 임계영역 존재 시 Wait Queue 대기
  //
  // 임계영역
  // Buffer Pool의 한개의 Full Buffer에서 item 제거
  //
  signal(mutex); // 프로세스 자원 반납
  signal(full); // Empty Buffer 가 하나 생겼으므로 empty++
  //
  // 버퍼에서 추출한 item을 활용하는 코드란
  //
}

    。wait(full) : Buffer Pool에서 item을 추출할 Full Buffer가 없는 경우 Wait Queue에서 대기
    ▶ full > 0 을 만족할때까지 Wait Queue에서 대기 및 만족 시 full-- 후 wait(mutex) 실행

    。signal(empty) : Buffer Pool에 Empty Buffer가 하나 생겼으므로 empty++
    。다음 대칭을 만족해야 정상적으로 구동
    ▶ Timing Error의 위험 존재

한정버퍼문제 코드

  • pthread 예시
    。semaphore 활용활용
    • 초기화
    #include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define true 1
#define BUFFER_SIZE 5
// 공유자원 초기화
int buffer[BUFFER_SIZE];
pthread_mutex_t mutex;
sem_t empty, full;
int in = 0, out = 0;
    • 생산자 스레드 수행함수
    // 생산자 스레드
void *producer(void *param){
  int item;
  while (true){
    usleep((1 + rand() % 5) * 100000);
    item = 1000 + rand() % 1000;
    insert_item(item); // 임계영역
  }
}

    。usleep을 통해 0.1초 ~ 0.5초 사이를 sleep 후 item을 랜덤으로 생성 후 임계영역에서 버퍼에 삽입

    。임계영역

    void insert_item(int item){
  sem_wait(&empty);
  pthread_mutex_lock(&mutex);
  buffer[in] = item;
  in = (in + 1) % BUFFER_SIZE;
  printf("생산자 : 삽입 %d\n", item);
  pthread_mutex_unlock(&mutex);
  sem_post(&full);
}

    。buffer pool 내 empty buffer 존재 및 ( empty > 0 ) 임계영역의 공유자원을 점유한 스레드가 없는 경우 ( mutex == 1 ) 임계영역에 진입 및 empty-- 후 Empty Buffer에 item 추가
    ▶ 이후 자원 반납( mutex++ ) 및 full++

    • 소비자 스레드 수행함수
      // 소비자 스레드
void *consumer(void *param){
  int item;
  while (true) {
    usleep((1 + rand() % 5) * 100000);
    remove_item(&item); // 임계영역
  }
}

    。usleep을 통해 0.1초 ~ 0.5초 사이를 sleep 후 임계영역에서 버퍼의 item을 삭제

    。임계영역

    void remove_item(int *item){
  sem_wait(&full);
  pthread_mutex_lock(&mutex);
  *item = buffer[out];
  out = (out + 1) % BUFFER_SIZE;
  printf("소비자 : 삭제 %d\n:",*item);
  pthread_mutex_unlock(&mutex);
  sem_post(&empty);
}

    。buffer pool 내 full buffer 존재 및 ( full > 0 ) 임계영역의 공유자원을 점유한 스레드가 없는 경우 ( mutex == 1 ) 임계영역에 진입 및 full-- 후 Full Buffer에서 item 추출 및 해당 item의 pointer( = out ) 제거
    ▶ 이후 자원 반납( mutex++ ) 및 empty++

    • 메인 스레드
    // 메인스레드
int main(int argc, char *argv[]){
  int i , numOfProducers = 1, numOfConsumers = 1;
  pthread_t tid;
  pthread_mutex_init(&mutex, NULL);
  sem_init(&empty,0,BUFFER_SIZE);
  sem_init(&full, 0, 0);
  srand(time(0));
  // 생산자 스레드 생성
  for (i=0; i<numOfProducers ; i++)
    pthread_create(&tid,NULL,producer,NULL);
  // 소비자 스레드 생성
  for (i=0; i<numOfConsumers ; i++)
    pthread_create(&tid,NULL,consumer,NULL);
  sleep(10);
  return 0;
}

    。Counting Semaphore empty = 버퍼 총 갯수 , full = 5로 초기화

    。메인스레드에서 자식 생산자 / 소비자 스레드 생성 및 Concurrent하게 실행

    。sleep(10)을 통해 10초동안 스레드 작업 수행

    。 5개의 소비자 스레드와 5개의 생산자 스레드가 동기화를 유지하면서 Concurrent하게 10초동안 단일 Buffer pool에 접근하여 Buffer의 item을 삽입 및 삭제를 수행
    ▶ Buffer Pool의 Buffer수를 조정하거나, 소비자 또는 생산자 스레드 수를 조정하더라도 동기화는 유지



  • JAVA 예시
    JAVA - Monitor로 생산자소비자 문제 해결

독자 - 저자 문제( Readers - Writers Problem )
。여러명의 독자와 저자들이 하나의 공유자원( ex. DB )에 동시접근 시 발생하는 동기화 문제

。생산자 - 소비자 문제와 다른점은 독자 프로세스( = Reader )는 읽기만하고 ( Read ) , 작가 프로세스( = Writer )는 읽기 & 쓰기 ( Write )를 둘다 수행

ex ) DB에 Concurrent하게 접근하여 reader는 SELECT를 통한 데이터 조회만 수행 및 writer는 데이터의 UPDATE를 통한 데이터 조회 및 수정을 수행

。DB에 Reader - Reader가 Concurrent하게 Execute 시 동기화 문제는 발생하지 않는다.

。DB에 Writer - Writer와 Reader - Writer가 Concurrent하게 Execute 시 Race Condition 발생

。독자 - 저자 문제의 해결방법 : Reader - Writer Locks

  • Readers - Writers Problem의 유형
    。독자 / 작가 프로세스 간 우선순위로 인해 Starvation이 다음 두가지 유형에서 발생할 수 있음
    • First Readers-Writers Problem :
      。Reader가 임계영역에서 데이터를 읽는 과정에서 Writer가 진입대기중이더라도 다른 Reader가 진입대기할 필요는 없다
      ▶ Reader - Reader는 Race Condition이 발생하지 않으므로

      。 해당 문제에서 Writer가 수 많은 Reader에 의해 무한정 대기하는 Starvation 문제가 발생할 수 있음
      ▶ 마지막 Reader가 공유자원을 Release해야 Writer가 임계영역에 진입가능

      ▶ 임계영역에 대해 대기중인 Reader와 Writer에게 서로 공평하게 우선순위를 부여해야함.

    • Second Readers-Writers Problem :
      。Writer가 임계영역에 진입하려고 대기중일때, 새로운 Reader가 임계영역에 접근하지 못하는 문제

      。해당 문제에서 Reader가 Starvation이 발생할 수 있음


  • Readers-Writers Problem 코드예시
    。독자 M : 작가 N 프로세스 간 단일 공유자원( DB )에 접근하는 경우
    ▶ Binary Semaphore 사용

    。Reader와 Writer는 DB에 Concurrent하게 접근.

    。특정 Writer가 임계영역에서 Execute중이고, n개의 Reader가 Wait Queue에서 대기중일때,
    ▶ 1개의 Reader는 rw_mutex의 Wait Queue에서 대기하여 Reader와 Writer 간 동기화
    ▶ n - 1개의 Reader는 mutex의 Wait Queue에서 대기하여 Reader 간 동기화
    • 초기화
      。Binary Semaphore를 사용하므로 오직 단일 프로세스가 임계영역에 진입하여 단일자원에 접근가능.
    semaphore rw_mutex = 1; // reader 와 writer가 공유해서 사용
semaphore mutex = 1; // 임계영역 동기화 용도
int read_count = 0; // reader 갯수

    。2개의 Binary Semaphore와 1개의 int 사용

    。Binary Semaphore
    rw_mutex : 임계영역 동기화 용도 Lock
    ▶ Reader 와 Writer 모두 참조하며 다른 Writer의 접근을 Block하여 상호배제 보장

    mutex : 임계영역 동기화 용도 Lock
    ▶ read_count를 update 시 다른 Reader의 접근을 Block하여 상호배제를 보장

    read_count : Reader의 갯수
    ▶ 공유자원을 읽고있는 Reader의 수를 측정
    ▶ read_count == 0 인 경우 Writer 진입가능

    • 독자 프로세스 ( Reader Process )
    while (true){
  wait(mutex);
  // Critical Section
  read_count++;
  if ( read_count == 1 ){
    // Reader가 임계영역에 있는 경우
    // Writer Block
    wait(rw_mutex);
  }
  signal(mutex);
  //
  // Reading 코드란
  //
  wait(mutex);
  // Critical Section
  // Reader를 임계영역에서 해제
  read_count--;
  if ( read_count == 0 ){
    // Reader가 임계영역에 없는 경우 
    // Writer 임계영역 진입
    signal(rw_mutex);
  }
  signal(mutex);
}

    。첫번째 wait(mutex)를 통해 단일 Reader 또는 Writer의 임계영역 진입 후 read_count++ 후 권한 반납후 Reading 작업 수행
    ▶ 첫번째 Reader가 Execute된 경우 read_count == 1이 되고, 이때 wait(rw_mutex);를 통해 다른 Writer의 임계영역 접근을 제한

    。Reading이 끝난 후 두번째 wait(mutex)를 통해 단일 Reader 또는 Writer는 임계영역 진입 후 read_count-- 수행 후 권한 반납

    。read_count == 0 인 경우
    ▶ Reader와 Writer가 임계영역에서 없는경우에만 Reader에서 signal(rw_mutex)를 통해 Writer가 임계영역에 진입

    。Writer가 signal(rw_mutex) 실행 시 대기중인 복수의 Reader 또는 단일 Writer 중 하나를 스케쥴러에 의해 선택하여 실행을 재개
    ▶ 스케쥴러가 Reader와 Writer에게 공평하게 기회를 주는 경우 First 해결
    ▶ 스케쥴러가 Writer에게 우선기회를 주는 경우 Second 해결

    • 작가 프로세스 ( Writer Process )
    while (true){
  wait(rw_mutex);
  //
  // Critical Section
  // Writing 코드란
  //
  signal(rw_mutex);
}

    。wait(rw_mutex); : 임계영역에 Reader와 Writer 둘 다 없는 경우 ( rw_mutex > 0 ) 임계영역으로 진입
    ▶ 임계영역 진입 시 rw_mutex--로 인한 rw_mutex == 0이므로 다른 프로세스 진입불가

    。signal(rw_mutex) : 임계영역 진입권한 반납
    ▶ rw_mutex++



  • Reader - Writer Locks
    。Read 또는 Write의 동작 중 하나만 동작하도록 하는 Locking 방법
    ▶ Readers - Writers Problem의 해결방법

    。현재 프로세스가 Reader 또는 Writer의 구분을 한 후 Reader Lock과 Writer Lock을 각각 구현 및 획득
    ▶ Reader Lock 획득 시 여러 프로세스들이 임계영역에 접근 가능
    ▶ Writer Lock 획득 시 단일 프로세스만 임계영역에 접근가능

    。JAVA 예시
    JAVA - Monitor로 Reader-Writer Lock을 통한 작가-독자 문제 해결

출처
。운영체제 공룡책 강의

profile
TopOfTheHead
공부기록 블로그
이전 포스트

운영체제 - 임계영역문제 해결방안 ( SW ) : 피터슨, 뮤텍스, 세마포어, 모니터

0개의 댓글