[WIL] PintOS 프로젝트와 함께 알아보는 병행성과 동기화 도구: Semaphore, Lock, Mutex, Condition Variable, Monitor
KAIST PintOS Project
00. 들어가며
-
이번 주차 학습을 하면서 개념적으로 조금 모호했던 부분이 바로 이 동기화 도구들에 관한 부분이었다.
-
'Lock이랑 Mutex는 사실상 같은 녀석 아닌가?', 'Condition Variable 이라는 녀석은 또 뭐지?', 'Mesa 스타일 Monitor라는건 또 뭐야?'
→ 각각의 동기화 도구에 대해 어느 정도 개념론적인 내용은 알겠지만, 관계론적인 부분이 정리가 되지 않았다. -
이러한 궁금증에 대해 어느 정도 정리가 된 지금, 이 내용을 WIL로 남기면 좋겠다는 생각이 들어 글을 작성하게 되었다.
동기화 도구란?
- 특정 동작에 대한 병행 처리 도중, 하나의 자원에 대해 여러 제어 흐름이 접근하게 되는 상황, 즉, 하나의 자원을 두고 여러 제어 흐름이 경쟁하는 상황을 경쟁 상황 (Race Condition) 이라고 한다.
- 이 때, 이 자원을 공유 자원 이라고 하고, 공유 자원에 접근하는 코드 영역을 임계 영역 이라고 한다.
- 그리고 이러한 경쟁 상황의 해결을 위해 사용되는 도구가 바로 오늘 살펴 볼 동기화 도구들이다.
01. 동기화 도구 ( Semaphore, Lock, Mutex, Condition Variable)
-
우선, 크게 그림으로 정리하면 관계도가 위와 같다.
'결국은 다Semaphore를 가지고 장난치는 녀석들' 이더라. -
Semaphore 中 0과 1 값만 가지고 상호배제를 구현하는 도구를 이진 Semaphore (Binary Semaphore) 라고 하며, 이는 Mutex와 같다.
또, PintOS에서 사용하는 lock도 사실 Mutex이다.
(1로 초기화 하고, 0일 때 기다리도록 해서 0과 1 값만 사용하고 있다.) -
Lock에는 이 Mutex 외에도 여러가지 종류가 더 포함되는데,
Spin Lock이나Read-Write Lock이 여기 해당한다. -
조건 변수는 사실 위의 다른 동기화 도구들과 그 목적이 다르다.
공유 자원의 상호 배제를 위해 사용되는 나머지 도구들과 달리, 조건 변수는 어떤 동작이 특정 조건을 만족하지 못했을 때 대기 상태로 변경했다가, 특정 조건을 만족하면 실행되도록 하는 도구이다.
그리고 PintOS 코드에서는 이를 Semaphore를 통해 구현한다. -
그리고, 이 조건 변수와 세마포어를 함께 이용해 모니터(Monitor)라는 고수준의 동기화 도구를 작성할 수 있다.
01-1. Semaphore
Semaphore는 하나의 정수값과 두 개의 연산 (P,V) 으로 구성된다.
pintOS 코드와 함께 살펴보자.
여담: Semaphore는 최단 경로 알고리즘으로 유명한 Dijkstra 선생님께서 고안하셨다고 한다.
/* A counting semaphore. */
struct semaphore {
unsigned value; /* Current value. */
struct list waiters; /* List of waiting threads. */
};
/* Down or "P" operation on a semaphore. Waits for SEMA's value
to become positive and then atomically decrements it.
This function may sleep, so it must not be called within an
interrupt handler. This function may be called with
interrupts disabled, but if it sleeps then the next scheduled
thread will probably turn interrupts back on. This is
sema_down function. */
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
ASSERT (!intr_context ());
old_level = intr_disable ();
while (sema->value == 0) {
list_push_back (&sema->waiters, &thread_current ()->elem);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}
/* Up or "V" operation on a semaphore. Increments SEMA's value
and wakes up one thread of those waiting for SEMA, if any.
This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
old_level = intr_disable ();
if (!list_empty (&sema->waiters))
thread_unblock (list_entry (list_pop_front (&sema->waiters),
struct thread, elem));
sema->value++;
intr_set_level (old_level);
}semaphore는 어떤 공유 자원을 대해 여러 스레드가 사용할 때, 임계 영역 앞에sema_down(), 임계 영역 뒤에sema_up()을 호출 해 사용하며, 이를 통해 상호 배제를 보장한다.
※예시 상황 시나리오
- 어떤 스레드 A, B가 공유 자원 x에 접근 한다고 해보자.
semaphore의value값은 1로 초기화 된 상태이다.
- 스레드 A가 임계영역에 들어갈 때
sema_down()을 호출한다.semaphore의value값은 0이 될 것이다.
- 스레드 A의 실행 도중, 스레드 B가 실행 되었다.
- 스레드 B는
sema_down()을 호출한다.semaphore의value가 0이므로 스레드 B는 대기 상태가 되고,semaphore의waiters리스트에 추가된다.
- 스레드 A의 실행이 끝났다.
sema_up()을 호출 해semaphore의value를 1로 증가시키고, 스레드 B를 깨운다.
- 스레드 B는 다시
sema_down()을 호출 해semaphore의value를 0으로 만들고, 작업을 수행한다.
-
위와 같이 0과 1이라는 이진 값 만으로도 병행 처리에서 공유 자원에 대한 상호 배제를 구현해주는 것을 확인할 수 있다.
-
위와 같이 사용되는 것이 이진 세마포어, Mutex에 해당한다.
-
PintOS의 Lock이 이렇게 작성되었다.
/* Lock. */ struct lock { struct thread *holder; /* Thread holding lock (for debugging). */ struct semaphore semaphore; /* Binary semaphore controlling access. */ }; void lock_init (struct lock *lock) { ASSERT (lock != NULL); lock->holder = NULL; // 항상 1로 초기화하는 것을 여기서 확인할 수 있다. sema_init (&lock->semaphore, 1); } void lock_acquire (struct lock *lock) { ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (!lock_held_by_current_thread (lock)); sema_down (&lock->semaphore); lock->holder = thread_current (); } void lock_release (struct lock *lock) { ASSERT (lock != NULL); ASSERT (lock_held_by_current_thread (lock)); lock->holder = NULL; sema_up (&lock->semaphore); }
-
-
세마포어는 0으로 초기화해서 먼저 실행되어야 하는 스레드가 있을 때 순서 보장의 용도로도 사용이 가능하다.
-
세마포어는 1이나 0말고도 더 큰 수로 초기화도 가능하다. → 공유 자원의 개수, 스레드의 개수에 따라 핸들링이 가능하고, 이를 Counting Semaphore라고 한다.
Tip.
- 카페 화장실을 쓰려는데, 열쇠를 챙기는 상황을 생각해보자. 세마포어의 초기화 값을 화장실 열쇠의 개수라고 생각하고, 화장실을 임계 영역이라고 비유하면 이해하기 편하다.
만약, 세마포어를 0에서 대기하게끔 구현하지 않고 음수가 가능하게 만들면, 이 음수값은 해당하는 대기자 수가 된다.
01-2. Condition Variable
- Condition Variable은 PintOS의 테스트 케이스 코드와 실행 결과를 함께 보면 이해하기 한결 편하다.
/* Tests that cond_signal() wakes up the highest-priority thread
waiting in cond_wait(). */
#include <stdio.h>
#include "tests/threads/tests.h"
#include "threads/init.h"
#include "threads/malloc.h"
#include "threads/synch.h"
#include "threads/thread.h"
#include "devices/timer.h"
static thread_func priority_condvar_thread;
static struct lock lock;
static struct condition condition;
void
test_priority_condvar (void)
{
int i;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
lock_init (&lock);
cond_init (&condition);
thread_set_priority (PRI_MIN);
for (i = 0; i < 10; i++)
{
int priority = PRI_DEFAULT - (i + 7) % 10 - 1;
char name[16];
snprintf (name, sizeof name, "priority %d", priority);
thread_create (name, priority, priority_condvar_thread, NULL);
}
for (i = 0; i < 10; i++)
{
lock_acquire (&lock);
msg ("Signaling...");
cond_signal (&condition, &lock);
lock_release (&lock);
}
}
static void
priority_condvar_thread (void *aux UNUSED)
{
msg ("Thread %s starting.", thread_name ());
lock_acquire (&lock);
cond_wait (&condition, &lock);
msg ("Thread %s woke up.", thread_name ());
lock_release (&lock);
}
-
위의 테스트 케이스를 보면, 위의 for문에서 10개의 스레드를 만들고, 각각의 스레드에서
priority_condvar_thread()를 실행한다. -
priority_condvar_thread()함수에서는 본인 스레드의 시작을 알리고,cond_wait()을 호출한다. -
다음 for문에서는 10개의 스레드에 각각
cond_signal()을 주고 있다.
실행 결과는 어떻게 될까?
-
우선 순위 정렬을 구현하고 났을 때 기준으로, 실행 결과는 위와 같다.
각각의 스레드는 본인 스레드의 시작을 알리고cond_wait()을 호출해 대기 상태가 된다. -
이후,
cond_signal()을 각각의 스레드에 전달해 대기중인 스레드를 깨워준다.
- 이런 식으로, 조건 변수는 어떠한 동작을 '특정 조건이 만족 되기까지' 대기 시켰다가 실행 되도록 할 수 있는 것이다.
위의 테스트 케이스에서는 굳이 말하자면 '스레드 10개가 다 만들어지고 나서' 본인 스레드가 깨어남을 알리도록 조건을 준 것이다.
