[운영체제] Chapter7. Synchronization Examples

CS/Operating System

[운영체제] Chapter7. Synchronization Examples

TERRY✨ 2022. 6. 1. 20:55

1. Classic Problems of Synchronization

The bounded-buffer problem
The readers-writers problem
The dining-philosophers problem

1) The Bounded-Buffer Problem

두 종류의 프로세스가 있다. 하나는 Producer, 또 다른 하나는 Consumer이다. 이는 생산자-소비자 문제(Producer-Consumer Problem)이라고도 불린다. 여기서 발생할 수 있는 문제점은 어느 producer가 버퍼 중 빈 곳에 데이터를 쓰려고 할 때, interrupt가 발생하여 다른 프로세스한테 공유자원이 넘어가서 다른 프로세스가 해당하는 빈 곳에 데이터를 쓸 때 나타날 수 있다. 그렇게 되면 둘 중 한 프로세스의 데이터가 유실될 가능성이 있다는 것이다.

만약 buffer가 꽉 찼다면 producer는 consumer가 item을 삭제할 때까지 기다려야 한다.
- producer는 buffer 안에 empty space가 필요하다.
- # of empty slot 은 semaphore empty에 의해 나타나진다.
만약 buffer가 비었다면 consumer는 producer가 item을 넣을 때까지 기다려야 한다.
- consumer는 buffer 안에 item이 필요하다.
- # 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

//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을 소비함) */
    ...
}

2) The Readers-Writers Problem

Readers와 Writers는 하나의 공유하는 데이터베이스를 가지고 있다. Readers는 동시에 데이터베이스에 접근할 수 있지만, 한 writer가 shared data에 접근할 때, 어떤 thread도 그것에 접근할 수 없다.

Behavior of a writer
- 만약 한 thread가 critical section에 있을때, 모든 writers은 무조건 기다려야 한다.
- writer은 오직 어떤 thread도 critical section에 있지 않을 때에만 진입할 수 있다.
  - 모든 thread들이 critical section에 진입하는 것으로부터 이를 예방해야 한다.
Behavior of a reader
- 만약 어떤 writer도 critical section에 있지 않으면, 그 reader는 critical section에 들어갈 수 있다.
- 만약 어떤 writer가 critical section에 있다면, reader는 그 writer가 critical section에 빠져 나올 때까지 기다려야 한다.
- reader가 critical section에 있을 때, 아무 reader나 critical section에 진입할 수 있다. 하지만 writer은 불가능하다.
  - 첫번째 reader의 condition은 뒤따라오는 reader들과 다르다.

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

3) The dining-philosophers problem(식사하는 철학자 문제)

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

해결책은 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이 발생하는 경우는 어떤 경우일까?

- 5명의 철학자가 다같이 배고파서 다같이 동시에 자신 왼쪽의 젓가락을 잡는다면 chopstick의 모든 원소는 0이 된다. 결국 철학자는 오른쪽 젓가락을 영원히 잡을 수 없다. -> 이렇게 Deadlock이 발생

Starvation의 경우는?

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

Deadlock을 해결할 수 있는 방법(아래 3가지 조건 중 하나만 추가하면 해결 가능하다. 하지만 이 방법은 starvation의 가능성을 업애는 것은 아니다.)
- 최대 4명의 철학자만이 테이블에 동시에 앉을 수 있게 한다.
- 한 철학자가 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 한다.
- 비대칭 해결안을 사용한다. ex)홀수번째 철학자는 왼쪽 젓가락부터 집어야 하고 짝수번째 철학자는 오른쪽 젓가락부터 집어야 한다.
Monitor solution

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은 일어날 수 있다.

2. Synchronization within the Kernel

이 부분에서는 linux에 의해 제공되는 동기화 메커니즘에 대해서 설명한다.

Synchronization in Linux

Linux : 2.6 버전 이전에는 비선점형 커널이었다. 이는 kernel mode에서 작동하는 한 프로세스가 선점될 수 없다는 것을 의미한다. 하지만 지금은 linux kernel은 완전히 선점형이다.
Linux는 Semaphores(kernel에서 locking을 위해), atomic integers(수학연산을 위한), spinlocks(kernel에서 locking을 위해), 그리고 reader-writer version of both을 제공한다.
Atomic variables
- 컴퓨터 아키텍쳐가 간단한 수학 연산을 위해 atomin versions에 대해 명령어를 제공하기 때문에, Linux kernel 내에서 가장 간단한 동기화 기법
- atomic_t는 atomic integer의 타입이다.
- 모든 math operation은 interruption없이 수행된다.
- ex) atomic_t counter; int value; // 아래의 코드는 atomic integer counter를 선언하고 다양한 atomic연산을 수행하는 것을 보여준다.

Mutex locks
- kernel 내의 critical section을 보호하기 위해서 mutex lock을 사용하는 것이 linux에서 가능하다.
- int mutex_init(struct mutex *lock); // initialize the mutex
- int mutex_lock(struct mutex *lock); // acquire the mutex, critical section에 들어가기 전에 꼭 호출해야만 한다. 만약 mutex lock이 이용가능하지 않다면 mutex_lock()을 호출한 task는 sleep state에 들어가고, lock의 주인이 mutex_unlock()을 부를 때 깨어난다.
- int mutex_unlock(struct mutex *lock); // Release the mutex, must be invoked after exiting the critical section, If the mutex lock is unavailable, a task calling mutex_lock() is put into sleep state and is awakened when the lock's owner invokes mutex_unlock()
Spinlocks(spinlock은 다른 스레드가 lock을 소유하고 있다면 그 lock이 반환될 때까지 계속 확인하며 기다리는 것이다)
- spin_lock(), spin_unlock(), etc.
- SMP machines에서, 기본 locking mechanism은 spinlock이고, 그 kernel은 spinlock이 짧은 시간동안만 보유되도록 설계된다.
- 오직 단일 프로세싱 코어를 가진 임베디드 시스템 같은 단일 프로세서 머신에선 spinlock을 사용하기엔 부적절하고, kernel 선점을 활성화/ 비활성화 하여 대체된다.
Enabling/disabling kernel preemption
- Linux는 kernel 선점을 비활성화하고, 활성화 하는데 흥미로운 접근법을 사용한다. 그것은 커널 선점을 비활성화 하고 활성화 하는데 간단한 system calls을 사용한다.
- preempt_disable(), preempt_enable()

Single Processor	Multiple Processors
Disable kernel preemption	Acquire spin lock
Enable kernel preemption	Release spin lock

3. POSIX Synchronization

POSIX API는 1) Mutex locks 2) Semaphores 3) Condition variable을 제공한다.

UNIX, Linux, macOS에서 널리 사용된다.

1) POSIX Mutex Locks

Creating and initializing the lock

#include <pthread.h>
pthread_mutex_t mutex; // global declaration

//create and initialize the mutex lock
pthread_mutex_init(&mutex, NULL); //call before first lock
or
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

Acquiring and releasing the lock

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

/* critical section */

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

2) POSIX Semaphores

Named semaphores

Multiple unrelated processes는 common semaphore를 쉽게 사용할 수 있다.
Creating and initializing the lock

#include <semaphore.h>
sem_t *sem; // global declaration

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

Acquiring and releasing the lock

sem_wait(sem); // acquire the semaphore

/* critical section */

sem_post(sem); // release the semaphore

Unnamed semaphores

Creating and initializing the lock

#include <semaphore.h>
sem_t sem; // global declaration

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

Acquiring and releasing the lock

sem_wait(&sem); // acquire the semaphore

/* critical section */

sem_post(&sem); // release the semaphore

3) POSIX Condition Variables

POSIX는 일반적으로 C/C++에서 사용되고 이러한 언어는 모니터를 제공하지 않는다.

POSIX condition variables은 POSIX mutex lock과 연관되어 mutual exclution을 보장한다.

Creating and initializing

pthread_mutex_t mutex;
pthread_cond_t cond_var;

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

Example

조건 a==b가 true가 되는 것을 기다리는 스레드

pthread_mutex_lock(&mutex);
while(a!=b)
	pthread_cond_wait(&cond_var, &mutex);
pthread_mutex_unlock(&mutex);

condition variable에 대기중인 다른 스레드에게 시그널을 보내는 스레드

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

4. Synchronization in Java

Java는 가장 많은 synchronization feature을 제공한다.

Java monitors
Reentrant locks
Semaphores
Condition variables

1) Java Monitors

Java의 모든 객체는 lock을 가지고 있다.

먼저 아래 코드를 보자

public class BoundedBuffer<E>
{
    private static final in BUFFER_SIZE = 5;
    private int count, in, out;
    private E[] buffer;

    public BoundedBuffer(){
        count = 0;
        in = 0;
        out = 0;
        buffer = (E[]) new Object[BUFFER_SIZE];
    }

    //Producers call this method
    public synchronized void insert(E item){
    	while(count == BUFFER_SIZE){
        	try{
            	wait();
            }catch{
            	InterruptedExceprion ie
            }
            buffer[in] = item;
            in = (in + 1) % BUFFER_SIZE;
            count++;
            notify();
        }
    }

    //Consumers call this method
    public synchronized E remove(){
    	E item;
        while(count == 0){ //버퍼가 비어있으면
        	try{
            	wait();
            }catch{
            	InterruptedException ie
            }
            item = buffer[out];
            out = (out + 1) % BUFFER_SIZE;
            count--;
            notify();
            return item;
        }
    }
}

만약 한 method가 synchronized로 선언되어있다면, 그 method를 호출한 스레드가 그 object에 대한 lock을 얻어야 한다.
만약 다른 스레드가 그 lock을 실행하고 있다면, 호출한 스레드는 그 스레드가 끝날때까지 대기해야 한다.
Locks are released when the owning thread exits the synchronized method

이용불가능한 lock을 얻길 시도하는 스레드는 객체의 entry set에 들어간다.
만약 lock을 가진 스레드가 계속할 수 없으면 wait()를 호출한다.
- 한 스레드가 wait()함수을 호출했을 때:
  - 그 스레드는 객체에 lock을 푼다.
  - 그 스레스의 상태가 '차단'으로 설정된다.
  - 그 스레드는 wait set으로 배치된다.
스레드는 대기하고 있는 스레드를 깨우기 위해 notify()를 호출 할 수 있다.
- 한 스레드가 notify()를 호출했을 때:
  - 임의의 스레드 T가 wait set으로 부터 선택된다.
  - T는 wait set에서 entry set으로 이동한다.
  - T의 상태는 차단됨에서 runnable상태로 바뀜
- 그러면 T는 이제 condition이 true인지 확인하는 lock들과 경쟁할 수 있다.

2) Java Reentrant Locks

Reentrant Lock은 mutex로 생각하면 된다.

Lock key = new ReentrantLock();

key.lock();
try{
	//critical section
}finally{
	key.unlock();
}

여기서 finally 부분은 예외가 try block에서 발생한 경우에 lock이 release 될 것이라는 것을 보장한다.

3) Java Semaphores

Constructor

Semaphore(int value);

Usage

Semaphore sem = new Semaphore(1);

try{
    sem.acquire();
    //critical section
}
catch(InterruptedException ie){ }
finally{
    sem.release();
}

4) Java Condition Variables

Condition variables은 ReentrantLock과 관련이 있다.
ReentrantLock의 'newCondition()' method를 이용하여 condition variable을 만들 수 있다.

Lock key = new ReentrantLock();
Condition condVar = key.newCondition();

한 스레드는 'await()'라는 메소드를 호출함으로써 대기하며, 'signal()' 메소드를 호출함으로써 신호를 보낸다.
Example
- 0~4까지의 5가지 스레드가 존재한다고 하자.
- Shared variable인 'turn'이 존재한다. 이는 어떤 스레드의 순서인지 가리킨다.
- 스레드는 어떤 작업을 하고 싶을 때, dowork()를 호출한다. (하지만 이것은 오직 그 스레드의 순서일때만 그 스레드가 작업을 할 수 있다. )
- 만일 그 스레드의 turn이 아니라면 대기한다.
- 만약 그 스레드의 turn이라면, 잠시 그 일을 수행한다.
- 그 일이 끝났다면, 그 턴의 다음인 스레드에게 notify한다.
- 필수적인 data structure들은 아래와 같다.

Lock key = new ReentrantLock();
Condition[] condVars = new Condition[5];
for(int i = 0; i < 5; i++)
	condVars[i] = lock.newCondition();

public void doWork(int threadNumber){
    lock.lock();

    try{
        //If it's not my turn, then wait until I'm signaled
        if(threadNumber != turn)
            condVars[threadNumbers].await();

        //Do some work for awhile...

        //Now signal to the next thread
        turn = (turn + 1) % 5;
        condVars[turn].signal();
    }
    catch(InterruptedException ie){ }
    finally{
        lock.unlock();
    }
    
}

5. Alternative Approaches(대안적 접근)

Memory transaction
- 불러오기와 저장하기 명령(a sequence of memory read-write operations)의 집합이 atomic하게 수행될 수 있게 함으로서 병행성 프로그래밍을 단순하게 하는 방식이다.
- tramsaction은 atomic{s}( S에 있는 statement가 atomic하게 실행되도록 보장해주는) 를 추가해줌으로써 실현될 수 있다.

//Tranditional implementation
void update(){
    acquire();
    /* modify shared data */
    release();
}

//Memory transaction-based implementation
void update(){
    atomic{
        /* modify shared data */
    }
}

OpenMP(Open Multi-Processing)
- 공유 메모리 다중 처리 프로그래밍 API로 "#pragma omp critical"을 포함된 코드는 critical section으로 다뤄지며 atomic하게 수행된다.

void update(int value){
    #pragma omp critical
    {
    	count += value;
    }
}