[운영체제] Chapter 7. Synchronization Examples

경희대학교 허선영 교수님의 운영체제 수업을 기반으로 정리한 글입니다.

 

Chapter Objectives

• bounded-buffer, readers-writers, and dining-philosophers synchronization problems에 대해 설명
• Linux, Windows에서 process synchronization problems를 해결하는 특정 tools에 대해 설명
• synchronization problems를 해결하기 위해 POSIX, Java가 어떻게 사용되는지 설명
• POSIX, Java API를 사용하여 process synchronization problems를 해결하는 solutions를 디자인하고 발전

 

Classic Problems of Synchronization

1. The Bounded-Buffer Problem

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

• n 개의 buffers -> 각각 1개의 item 소유 가능
• mutex: buffer pool에 접근하기 위한 mutual exclusion
• empty & full: 비어있거나(empty buffer), item이 들어있는(full buffer) buffer의 개수를 나타냄
• 가장 처음 상태는 모두 비어있는 상태

-> Consumer에서 empty++하면, Producer는 wait(empty) line을 탈출

-> Producer에서 full++하면, Consumerㄴ느 wait(full) line을 탈출

 

2. Readers-Writers Problem

• concurrent processes에 의해 공유되는 database를 가정
• read 작업만 원하는 process -> reader
• update 작업을 원하는 process(read & write 모두 가능) -> writer
• writer가 database에 접근하는 동안, 다른 processes가 database에 simultaneous하게 접근하면 복잡한 문제가 발생 -> readers-writers problem
• 한 번에 하나의 wirter만 shared data에 접근 가능

- first readers-writers problem

• No reader is to be kept waiting unless a writer is writing
• writer가 write 작업을 진행하지 않는 한, reader는 기다리지 않는다.
• reader에게 우선순위를 부여, read 작업이 진행중이면 writer는 접근이 불가능
• starvation 문제 발생 가능 -> writers may starve

- second readers-writers problem

• Once a writer is ready to write, no "newly arrived reader" is allowed to read.
• writer가 준비 완료 -> newly reader 접근 불가
• writer에게 우선순위를 부여, write 작업이 진행중이면 reader는 접근이 불가능
• starvation 문제 발생 가능 -> readers may starve

 

- solution for first case

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

• read_count: 현재 reader의 개수
• mutex: read_count 보호 -> mutual exclusion
• rw_mutex: read/write 결정

-> reader가 없어야 writer 접근 가능

 

- solution for starvation

• reader-writer locks를 제공하는 kernel

 

3. The Dining-Philosophers Problem

• 상황
  • N 명의 philosophers, round table, bowel of rice in the middle
  • thinking & eating state
  • neighbors와 상호작용 X
• 한 번에 2개의 chopsticks를 가지려 시도 -> bowel of rice를 취하려면, 2개 모두 소유해야 함 & 완수했을 때 2개 모두 release
• in the case of 5 philosophers, shared data는 다음과 같음
  
  • bowel of rice(data set)
  • semaphore chopstick [5]: 1로 초기화된 상태
• The structure of Philosopher i: 

while (true) {
    wait (chopstick[i]);
    wait (chopstick[(i + 1) % 5]);
    
    /* eat for awhile */
    
    signal (chopstick[i]);
    signal (chopstick[(i + 1) % 5]);
    
    /* think for awhile */
}

• problem with this algorithm -> Deadlock

• 각 philosopher i는 operation pickup() & putdown()을 호출

DiningPhilosophers.pickup(i);

/** EAT **/

DiningPhilosophers.putdown(i);

-> No Deadlock, but Starvation is possible -> philosopher의 eating 보장 X

 

Synchronization within the Kernel

• Linux와 Windows에서 제공되는 synchronization mechanisms 중 Linux에 대해 설명

1. Synchronization in Linux

• 2.6 이전의 버전 kernel에서는 short critical sections를 구현하기 위해 interrupts를 비활성화
• 2.6과 이후의 버전 -> fully preemptive
• Linux가 제공하는 것
  • Semaphores
  • Atomic integers
  • Spinlocks
  • Reader-writer versions of both
• On single CPU system, spinlocks -> kernel preemption을 활성/비활서오하하는 것으로 대체됨
  • spinlocks -> lower overhead -> efficient context switching
• Atomic Variables
  • atomic_t -> 원자 단위로 update(update 통째로)

-> atomic variable 전용 연산

 

POSIX Synchronization

• kernel developers만 사용할 수 있는 kernel과 다르게, user level에서도 사용 가능한 API 형태로 synchronization tools 사용
  • mutex locks
  • semaphores
  • condition variable
• Unix, Linux, macOS에서 많이 씀

1. POSIX Mutex Locks

• Creating and Initializing the lock

#include <pthread.h>

pthread_mutext_t mutex;

/* create and initialize the mutex lock */
pthread_mutex_init(&mutex, NULL);

• Acquiring and Releasing the lock

/* acquire the mutex lock */
pthread_mutex_lock(&mutex);

/* critical section */

/* release the mutex lock */
pthread_mutex_unlock(&mutex)

 

2. POSIX Semaphores

• named or unnamed
• named semaphores -> 이름을 붙임으로써, other processes와 공유 가능

- POSIX Named Semaphores

• creating an initializing the semaphore

#include <semaphore.h>
sem_t *sem;

/* Create the semaphore and initialize it to 1 */
sem = sem_open("SEM", O_CREAT, 0666, 1);

- "SEM": 이름으로 semaphore 공유

- 1: 초기값에 따라 동작이 달라짐

• acquiring and releasing the semaphore

/* acquire the semaphore */
sem_wait(sem);

/* critical section */

/* release the semaphore */
sem_post(sem);

- POSIX Unnamed Semaphores

• creating an initializing the semaphore

#include <semaphore.h>
sem_t sem;

/* create the semaphore and initialize it to 1 */
sem_init(&sem, 0, 1);

• acquiring and releasing the semaphore

/* acquire the semaphore */
sem_wait(&sem);

/* critical section */

/* release the semaphore */
sem_post(&sem);

 

3. POSIX Condition Variables

• 6.7에서 소개한 condition variable과 동작이 비슷하지만, Pthreads에서는 monitor 제공 X
  • locking mechanism to ensure data integrity
  • C/C++에서는 monitor 제공 X
• POSIX condition variables are associated with a mutex lock to provide mutual exclusion
• Creating and Initializing the condition variable

pthreaed_mutex_t mutex;
pthread_cond_t cond_var;    //condition variable -> 단독 사용 X(mutex와 함께 사용)

pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond_var, NULL);

• Threaed waiting for the condition a == b to become true

pthread_mutex_lock(&mutex);
while(a != b) {
    pthread_cond_wait(&cond_var, &mutex);    // cond_var, mutex 함께 사용
}

pthread_mutex_unlock(&mutex);

• Thread signaling another thread waiting on the condition variable

pthread_mutex_lock(&mutex);
a = b;
pthread_cond_signal(&cond_var);
pthread_mutex_unlock(&mutex);