운영체제(7), Synchronization Examples

운영체제(7), Synchronization Examples

2022. 12. 18. 04:12ㆍ강의 내용 정리/운영체제

728x90

Synchronization Examples

어플리케이션 프로세스나 쓰레드가 사용하는 모델로는 세마포, 모니터, 뮤텍스 럭이 있다. 세마포는 카운팅, 바이너리가 있다. 바이너리 세마포는 뮤텍스 락과 동일하다.

운영체제에서는 스핀락과 인터럽트 enable, disable 방법을 사용한다.

1. Classical problem of Synchronization

1) Bounded-Buffer Problem

프로듀서는 데이터를 큐에 삽입하고, 컨슈머는 큐에서 데이터를 뽑아 사용한다. 큐를 공용으로 사용하기에 동기화 문제가 발생할 수 있다. 이는 두 가지 문제점이 있다.

우선 count, data, out은 모두 shared data이다. 어셈블리어로 이를 살펴보면 세개의 인스트럭션으로 쪼개지고, 그 사이에 인터럽트가 발생하면 문제가 발생할 수 있다. 즉, critical section을 보호하지 않기에 동기화 문제가 발생할 수 있다.

두번째로는 큐에 데이터가 차면 루프를 돌면서 waiting을 하기에 busy waiting을 하고 있다. 따라서 cpu를 사용하지 않고 block해서 기다리도록 하는 형태가 되어야지 cpu의 낭비가 없게 된다. cpu가 소비될 때는 본인의 time quantum을 모두 소비할 때까지 진행한다. 이때 cpu의 낭비가 매우 심하게 된다.

Semaphores를 사용하면 문제를 해결할 수 있다.

Semaphore 타입의 변수를 적어서 문제를 해결한다. 세마포는 block을 하기 위해 만들어졌기에 busy waiting도 방지할 수 있다.

mutex는 인터럽트로 인해 발생하는 문제를 해결한다. 이는 critical section을 보호하는 세마포가 된다. 이는 바이너리 세마포이다.

empty와 full은 busy waiting을 해결할 수 있도록 돕는다. 데이터가 들어가있는 개수를 full, 비어있는 개수를 empty로 정의해서 이를 처리한다. 컨슈머에서는 full이 0이면 이를 기다리도록 설정한다. 프로듀서는 empty가 0이면 이를 기다린다. 이를 통해 block된 상태로 존재할 수 있도록 한다. 반대로 컨슈머는 작업을 처리한 뒤에는 empty에 signal을 하고, 프로듀서는 작업을 한 뒤에 full에 signal을 보내 이를 처리한다. 이는 카운팅 세마포이다.

각 full과 empty의 값에 따라 프로듀서와 컨슈머가 동작한다.

Mutex lock을 이용한 코드

들어갈 때 lock, 나올 때 unlock을 한다. critical section에서 기다릴 때 사용하는 Condition variable로는 not_empty, not_full를 사용한다. condition variable을 사용하면 busy wait을 방지한다. count == 0일 때 컨슈머는 not_empty wait을 하기에 waiting 상태가 된다. 이때 프로듀서가 동작을 하다가 not_empty에 signal을 보내주면 컨슈머는 이후의 동작을 처리할 수 있게 된다. 여기서의 not_empty, not_full은 카운트를 의미하던 세마포의 empty, full과는 다르게 큐가 꽉 찼는지, 아닌지에 대한 정보를 가지고 있는 condition variable이다. lock을 건다면 mutex lock을 사용하는 다른 쓰레드는 이를 사용할 수 없지만 condition variable을 lock 내부에서 사용하면 condition variable이 만족하지 않는다면 잠시 lock이 풀려서 다른 쓰레드에서 이를 사용할 수 있도록 한다. 이후에는 조건이 만족된 다음 wait 이후부터 동작하게 된다.또한 기다리는 mutex lock이 없다면 signal이 아무 동작도 안한다.

만약 프로듀서와 컨슈머가 각각 하나씩만 있다면 condition variable에 대한 동작은 if문을 사용해도 된다. 하지만 두개 이상의 쓰레드가 있다면 while문으로 작성해야지 더 안전한 코드가 될 수 있다. 만약 두개 이상의 컨슈머가 wiat(not_empty)를 하며 waiting하다가 프로듀서에서 not_empty signal을 보낼 때 두 개의 컨슈머의 wait이 풀리는 문제가 발생할 수 있기 때문이다.

cf) 전역변수는 초기에는 0의 값을 가진다.

Readers-Writers Problem

Read는 여러 쓰레드가 동시에 해도 된다. 하지만 누군가가 Read를 할 때 write는 하면 안된다. 또한 write를 한다면 read와 write도 안된다.

이는 다음과 같이 코드를 작성할 수 있다.

// writer
void writer() {
	lock(L);
	// writing
	unlock(L);
}

// reader
void reader() {
	lock(L);
	// reading
	unlock(L);
}

하지만 위의 코드를 살펴보면 reader가 하나 있는 경우에는 다른 reader가 데이터를 읽을 수 없도록 만들었다. 이에 따라 첫번째 reader만 lock을 걸도록 할 수 있다.

// reader
void reader() {

	if (count == 0) 
    	lock(L);
    
    count++;
	// reading
    count--;
    
    if (count == 0)
    	unlock(L);
}

하지만 위의 코드의 경우에는 count라는 변수가 shared data이기에 해당 부분이 critical section이 된다. 이를 보완하기 위해 lock을 걸어준다.

// reader
void reader() {

	if (count == 0) // count 변수를 읽을 때는 상관 x
    	lock(L);
    
    lock(L2);
    count++;
    unlock(L2);
    
	// reading
    lock(L2);
    count--;
    unlock(L2);
    
    if (count == 0)
    	unlock(L);
}

count 변수를 수정할 때에는 lock으로 감싸준다.

아래는 세마포로 코드를 작성한 것이다.

reader에서 mutex는 readcount에 대한 critical section을 보호하기 위한 세마포이다.

readcount가 하나일 때에만 wait을 해주고, readcount가 0일때에만 signal을 보낸다.

만약 writer가 들어간 이후 인터럽트가 발생하고, reader가 들어가면 해당 reader는 조건문 내에서 wait을 한다. 만약 한번 더 reader가 들어온다면 첫번째 줄인 wait(mutex)에 의해 waiting 상태가 된다. 이후 writer가 동작을 마치고 signal을 보내면 첫번째로 진입한 reader는 signal(mutex)를 보내 대기중인 reader가 들어올 수 있도록 한다.

mutex는 리더가 들어올 수 있도록 하는 것에 의의가 있다.

Dining Philosopher

밥을 먹을 때 양쪽의 젓가락을 사용하는 경우에는 다른 사람이 밥을 먹지 못한다. shared data는 젓가락으로 고려하면 동기화 문제가 있을 수 있다.

젓가락은 0과 1을 반복하고, 누군가가 젓가락을 쓰면 0, 안쓰면 1로 둔다. 따라서 바이너리 세마포로 이를 구현할 수 있다.

위의 예시로는 다섯개의 쓰레드가 생긴다. 이 예시는 critical section을 보호하는 예시가 아닌 shared data를 공유할 때 사용하는 동기화 문제로 볼 수 있다.

논리적으로는 맞게 보이지만 위의 코드는 deadlock이 발생할 수 있는 여지가 있다. 만약 하나의 젓가락에 대해서만 wait을 한 뒤 interrupt가 걸리고 다른 쓰레드들도 하나의 젓가락만 잡는 상황이 된다면 모두 wait 상태가 되어 deadlock이 된다. random하게 think를 하기에 흔하게 발생하는 상황은 아니지만 특정 타이밍에는 발생할 가능성이 있다.

cf) deadlock: 락이 걸려서 영원히 풀리지 않는 상태

위의 문제를 해결하기 위해 두 개의 chopstick을 모두 보고 값이 1이라면 동시에 잡는 방식으로 문제를 해결할 수 있다.

철학자별로 세마포를 두어 위의 문제를 해결한다. state[i]는 i번째 철학자의 상태를 의미한다. pickup에서는 배고픔으로 만들고, 밥을 먹을 수 있는지 test 메서드를 통해 확인한다. 이때 state가 전역변수이기에 이는 critical section이 된다. 이를 보호하기 위해 wait, signal을 보내는 식으로 동작해야한다.

mutex를 wait하고 signal하는 것은 state에 대한 critical section을 보호하기 위함이다. s[i]는 초기에는 0으로 되어있기 때문에 주위에서 젓가락을 들 수 없다면 signal을 기다려야한다.

putdown에서 왼쪽과 오른쪽에 대한 test를 보내서 기다리고 있는 철학자가 있다면 signal을 보내도록 해서 문제를 해결한다. 이러한 경우에는 deadlock을 방지할 수 있다. 하지만 양쪽이 계속 밥을 먹는다면 starvation이 발생할 수 있는 여지가 있다. 따라서 이를 방지하기 위해 밥을 못먹으면 age를 높이는 aging을 사용할 수 있다.

모니터를 사용한 풀이

shared data를 모니터 내부에서만 사용하고, 이를 엑세스하는 함수를 모니터 안에서 사용한다.

모니터 내부에서 condition variable이나 관련 메서드를 정의한다.

여기서는 condition variable을 사용해서 wait하도록 했다. 위에서 봤던 코드와 유사한 것을 확인할 수 있다.

2. Synchronization tools in Real World

1) POSIX synchronization

유닉스/리눅스의 시스템 콜의 표준으로 사용한다.

POSIX semaphores

sem_init: 세마포를 초기화해서 초기값을 지정한다.

sem_wait: 세마포의 값을 1 빼거나 이미 0이면 기다린다.

sem_trywait: -1이 가능하면 값을 빼고, 0이어서 뺄 수 없으면 fail 처리를한다.

sem_post: signal의 동작을 한다.

sem_getvalue: 현재 세마포의 값을 알려준다.

sem_destroy: 세마포를 없애는데에 사용된다.

POSIX mutex locks (mutexes)

binary semaphores와 동일하게 사용할 수 있다.

pthread_mutex_init: 기본적으로 unlock 상태로 lock을 만든다.

pthread_mutex_destroy: lock을 없앤다.

pthread_mutex_lock: lock을 건다.

pthread_mutex_unlock: lock을 해제한다.

pthread_mutex_trylock: lock을 시도하고, unlock 상태면 lock을 하고, lock 상태면 fail 처리를 한다.

POSIX condition variable: mutex lock에서 이를 처리할 때 사용할 수 있다.

pthread_cond_init: condition variable을 만든다.

pthread_cond_destroy: condition variable을 없앤다.

pthread_cond_wait: condition variable을 기다린다.

pthread_cond_signal: condition variable을 처리하고 waiting 중인 하나의 쓰레드에게 signal을 보낸다.

pthread_cond_broadcast: condition variable을 처리하고 waiting 중인 모든 쓰레드에게 signal을 보낸다.

이는 mutex lock과 함께 사용하기에 critical section 내부에서 사용한다. 이에 따라 wait에 mutex도 파라미터로 전달해서 이를 처리한다. condition variable이 wait이라면 mutex lock은 lcok을 일시적으로 해제한다.

Bounded Buffer with POSIX Semaphores

sem_init에서 가장 뒤에 들어가는 파라미터는 세마포의 개수를 의미한다. wait과 post가 위에서 동작했던 것과 동일하다.

Bounded Buffer with POSIX Mutexes & Cond. Vars

cond_wait을 할 때 뮤텍스 락을 전달하는 것을 확인할 수 있다.

2) Java synchronization

Monitor

자바는 컴파일에서 이를 삽입하거나 JVM이 있기에 런타임에 모니터라는 개념을 지원할 수 있다.

이때 클래스를 정의해서 Synchronization이 필요한 멤버 메서드 앞에서는 synchronized를 입력하면 알아서 이를 처리한다.

3) C/C++/Java

프로그래밍 언어에 따라 지원하는 라이브러리를 참고해서 이를 처리한다.