[운영체제 공룡책] 고전적인 동기화 문제와 동기화 예시
Posted: Updated:
운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.
고전적인 동기화 문제
유한 버퍼 문제
유한 버퍼 문제란 생산자와 소비자가 하나의 공유 버퍼를 사용하는 상황에서 발생할 수 있는 문제이다.
버퍼가 가득 차면 생산자는 데이터를 더 넣을 수 없고, 버퍼가 비어 있으면 소비자는 버퍼에서 데이터를 꺼낼 수 없다.
int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;
n개의 버퍼로 구성된 풀(pool)이 있고, 각 버퍼가 한 항목(item)을 저장할 수 있다고 가정한다.
mutex 이진 세마포가 버퍼 풀에 접근하기 위한 상호 배제를 제공한다.
empty와 full 세마포는 각각 비어 있는 버퍼 수 와 꽉 찬 버퍼 수를 기록한다.
while (true) {
wait(empty); // 비어있는 칸 확인
wait(mutex); // 버퍼 풀 접근
signal(mutex); // 버퍼 잠금 해제
signal(full); // 채워진 칸 수 증가
}
생산자가 empty와 mutex를 이용해 버퍼에 아이템을 넣고 full을 증가시킨다.
while (true) {
wait(full); // 채워져있는지 확인
wait(mutex); // 버퍼 풀 접근
signal(mutex); // 버퍼 잠금 해제
signal(empty); // 비워진 칸 수 증가
}
소비자가 full과 mutex를 이용해 버퍼에서 아이템을 꺼내고 empty를 증가시킨다.
이러한 방법으로 생산자와 소비자를 동기화하여 해결할 수 있다.
Readers-Writers(독자-저자) 문제
하나의 공유 버퍼에 writer가 접근하고 있을 때, 다른 reader나 writer가 동시에 접근하게 될 경우 발생할 수 있는 문제이다.
따라서 writer의 쓰기 작업 동안 배타적인 접근 권한을 가지게 해야 한다.
- writer 우선인 경우의 Readers-Writers 문제
writer가 접근을 기다린다면 새로운 reader는 접근할 수 없다.
기존에 읽기 작업을 수행 중이던 reader는 수행을 계속할 수 있지만, 새로운 reader는 writer의 작업이 끝날 때까지 기다려야 한다.
이 경우 reader 가 기아 상태가 될 수 있다.
- reader 우선인 경우의 Readers-Writers 문제
reader의 읽기 작업을 기다리는 writer가 있더라도 새로운 reader가 읽기 작업을 시작할 수 있다.
따라서 writer는 계속 들어오는 reader들의 읽기 작업을 기다리면서 기아 문제가 발생할 수 있다.
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;
rw_mutex: reader와 writer가 공유, 임계구역으로 진입하는 첫 번째 reader와 임계구역에서 나오는 마지막 reader에 의해 사용
mutex: read_count를 갱신할 때 상호 배제를 보장하기 위해 사용
read_count: 현재 객체를 읽고 있는 프로세스 수
while (true) {
wait(rw_mutex);
/* 쓰기 작업 */
signal(rw_mutex);
}
writer 프로세스에서 공유 자원에 접근할 때 rw_mutex 를 사용한다.
while (true) {
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
/* 읽기 작업 */
wait(mutex);
read_count++;
if (read_count == 0)
signal(rw_mutex)
signal(mutex);
}
reader 프로세스에서 첫 번째 reader만 rw_mutex 를 사용하여 여러 reader가 접근할 수 있게 한다.
마지막 reader만 rw_mutex를 반환한다.
공유 데이터를 읽는 프로세스가 많고, 쓰는 프로세스는 드물 때 사용할 수 있다.
또한, 읽기 작업이 동시에 수행되어도 문제가 없을 때, 쓰기 작업이 반드시 단독으로 이루어져야 할 때 사용한다.
식사하는 철학자들 문제
다섯 명의 철학자가 있고, 테이블 위에는 하나의 식사가 있으며 5개의 젓가락이 놓여 있다.
이때, 젓가락은 한 쌍이 아니며 철학자들은 식사하기 위해 자신과 가까운 두 개의 젓가락을 집으려 한다.
이 문제는 다양한 종류의 병행 제어 문제의 한 예시로, 고전적인 동기화 문제이다.
교착 상태와 기아를 발생시키지 않고 스레드에게 자원을 할당해야 하는 상황을 비유한 것이다.
세마포 해결안
각 젓가락을 세마포로 표현해 해결할 수 있다.
철학자들은 젓가락을 집을 때 세마포에 wait() 연산을 수행한다.
젓가락을 놓을 때 signal() 연산을 수행한다.
while (true) {
wait(chopstick[i]);
wait(chopstick[(i+1) % 5])
/* 식사하기 */
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
/* 식사 마치기 */
}
5명의 철학자 모두가 동시에 배가 고프게 되어 각각 자신의 왼쪽 젓가락을 잡는다면, 오른쪽 젓가락을 잡기 위해 영원히 기다려야 한다.
이를 해결하기 위해 1. 최대 4명의 철학자만 동시에 앉을 수 있게 하거나 2. 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집을 수 있도록 허용하거나 3. 홀수 번호 철학자는 왼쪽 젓가락을 먼저, 짝수 번호 철학자는 오른쪽 젓가락을 먼저 집도록 할 수 있다.
모니터 해결안
철학자가 양쪽 젓가락을 모두 얻을 수 있을 때만 젓가락을 집을 수 있다고 제한한다.
enum {THINKING, HUNGRY, EATING} state[5];
철학자들이 처할 수 있는 3가지 상태를 구분하여, 양쪽 두 이웃이 식사하지 않을 때만 식사하도록 한다.
condition self[5]
self 로 철학자 i가 배고프더라도 젓가락을 집을 수 없는 상황에 젓가락을 집지 않도록 한다.
철학자가 식사 전 pickup()연산을 호출해 젓가락을 집거나 기다린다.
식사를 마치면 pickdown()을 호출한다.
monitor DiningPhilosophers
{
enum {THINKING, HUNGRY, EATING} state[5];
condition self[5];
void pickup(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait();
}
void putdown(int i) {
state[i] = THINKING;
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();
}
}
initialization_code() {
for (int i = 0; i < 5; i++) {
state[i] = THINKING;
}
}
}
커널 안에서의 동기화
Windows의 동기화
Windows 운영체제에서는 다중 스레드 환경에서 동기화를 위해 dispatcher 객체를 사용한다.
mutex 락, 세마포, event, 타이머 등 다양한 기법으로 동기화할 수 있다.
Event는 기다리는 조건이 만족하면 기다리고 있는 스레드에게 알려주며, 타이머는 지정한 시간이 만료되면 스레드에게 알려줄 때 사용된다.
Dispatcher 객체
dispatcher 객체는 Signaled 상태, NonSignaled 상태에 있을 수 있다.
- Signaled: 객체가 사용 가능하고 객체를 얻을 때 스레드가 봉쇄되지 않음
- Nonsignaled: 객체가 사용할 수 없고 객체를 얻으려고 시도하면 스레드가 봉쇄됨
Critical-section 객체
커널 개입 없이 획득하거나 방출할 수 있는 사용자 모드 mutex이다.
처음에는 스핀락을 사용하여 다른 스레드가 객체를 방출하기를 기다린다.
회전이 길어지면 락을 획득하려는 프로세스는 커널 mutex를 할당하고 CPU를 양도한다.
객체에 대한 경쟁이 발생할 때만 커널 mutex가 할당되어 효율적이다.
실제로 경쟁이 거의 발생하지 않으므로 CPU 절약에 좋다.
Linux의 동기화
2.6 버전 이전 Linux는 비선점형으로, 선점이 불가능했지만 현재 Linux 커널은 완전한 선점을 지원한다.
원자적 정수
Linux 커널 안에서 가장 간단한 동기화 기법이다.
락 기법을 사용할 때의 오버헤드가 필요 없어서 정수형 변수가 갱신되어야 하는 상황에서 효율적이다.
경쟁 조건에 많은 변수가 존재하는 상황에서는 사용하기 어렵다.
mutex
커널 안의 임계구역을 보호하기 위해 사용된다.
태스크가 임계구역에 들어갈 때 mutex_lock() 함수를 호출해야 하고, 나오기 전에 mutex_unlock() 함수를 호출해야 한다.
mutex 락을 획득하지 못한 경우 수면 상태에 놓이고, 락 소유자가 mutex_unlock()을 호출할 때 깨어난다.
스핀락
짧은 시간 동안 락이 필요한 경우에 사용된다.
다중 처리기 환경에서는 스핀락을 획득하고 방출할 수 있지만, 단일 처리기 환경에서는 스핀락을 사용할 수 없으므로 커널 선점을 가능하게 하거나 불가능하게 하는 방식으로 사용한다.
시스템의 각 스레드에는 thread_info 구조체가 있으며, 이 구조체에는 preempt_count라는 태스크가 소유하고 있는 락의 수를 나타내는 카운터 필드가 있다.
preempt_disable()을 호출하면 선점 불가능 상태로 만들고, preempt_enable()을 호출하면 선점 가능 상태로 돌아온다.
preempt_count가 0보다 크면 태스크가 락을 소유하고 있으므로 선점하면 안전하지 않다.
스핀락, 선점 불능 및 가능은 락을 짧은 시간 동안만 유지해야 할 때 사용한다.
오랜 시간 락을 유지해야 한다면 세마포 또는 mutex 락을 사용해야 한다.
POSIX 동기화
POSIX API는 사용자 수준에서 프로그래머가 사용할 수 있다.
UNIX, Linux 및 macOS 시스템 개발자가 스레드 생성 혹은 동기화에 사용할 수 있다.
POSIX mutex 락
Phtreads에서 사용할 수 있는 기본적인 동기화 기법이다.
Mutex 락은 코드의 임계구역을 보호하기 위해 사용된다.
스레드는 임계구역에 진입하기 전에 락을 획득하고 임계구역에서 나갈 때 락을 방출한다.
POSIX 세마포
기명(named)과 무명(unnamed) 두 유형의 세마포가 있다.
POSIX 기명 세마포
문자열 이름을 가진 세마포이고, 여러 프로세스가 세마포 이름만 참조하여 동기화에 공통 세마포를 쉽게 사용할 수 있다.
POSIX 무기명 세마포
이름 없이 변수처럼 사용하는 세마포이다.
주로 동일 프로세스 내의 스레드 동기화에 사용되며, 프로세스 간 공유를 위해서는 공유 메모리 영역에 할당해야 한다.
POSIX 조건 변수
스레드 간 특정 조건이 만족될 때 까지 기다리게 해주는 동기화 도구이다.
일반적으로 조건 변수에 mutex 락을 연결하여 락킹을 제공한다.
Java에서의 동기화
Java 모니터
BoundedBuffer 클래스를 사용할 수 있다.
생산자와 소비자가 각각 insert(), remove() 메서드를 호출한다.
이러한 메서드를 정의할 때 synchronized 를 선언하여 synchronized 메서드로 만들 수 있다.
이를 호출하기 위해서는 BoundedBuffer 객체 인스턴스와 연결된 락을 소유해야 한다.
다른 스레드가 이미 락을 소유했다면, synchronized 메서드를 호출한 스레드는 진입 집합(entry set)에 추가된다.
락이 사용 가능해지면 호출 스레드가 락의 소유자가 되어 메서드에 진입한다.
JVM이 진입 집합에서 락 소유자가 될 스레드를 임의로 선택한다.
public class BoundedBuffer<E>
{
private static final int 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 (InterruptedException 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;
}
}
- 생산자가
insert()호출 - 버퍼가 가득 차 있다면
wait()호출 후 락을 놓고 대기 상태로 전환 - 소비자가 락을 얻고
remove()호출 - 버퍼에서 항목 제거 후
notify()로 대기 중이던 생산자를 깨워 실행 가능한 상태로 바꿈 - 소비자가
remove()를 종료하고 락을 해제 - 대기 중이던 생산자가 락을 획득하고
wait()이후의 코드 재개
재진입 락
ReentrantLock은 API에서 사용 가능한 가장 간단한 락 기법이다.
synchronized 와 유사하게 동작하지만, 공정성 매개변수 설정 등 몇 가지 추가 기능을 제공한다.
스레드가 lock() 메서드를 호출해 ReentrantLock 을 획득한다.
락을 획득할 수 있거나 lock()을 호출한 스레드가 이미 락을 소유하고 있다면 lock() 이 호출 스레드에 락 소유권을 주고 제어를 반환한다.
락을 사용할 수 없는 경우 소유자가 unlock()을 호출해 락을 배정하기 전까지 봉쇄된다.
Lock key = new ReentrantLock();
key.lock();
try {
/* critical section */
}
finally {
key.unlock();
}
세마포
Java API는 카운팅 세마포도 지원한다.
Semaphore sem = new Semaphore(1);
try {
sem.acquire();
/* critical section */
}
catch (InterruptedException ie) { }
finally {
sem.release();
}
생성자 매개변수로 세마포의 초기 값을 지정한다.
락을 획득하려는 스레드가 인터럽트 되면 acquire() 메서드가 InterruptedException 을 발생시킨다.
세마포가 해제될 수 있도록 release() 호출을 finally 절 안에 배치한다.
조건 변수
wait() 및 notify() 메서드와 유사한 기능을 제공하는 조건 변수가 있다.
상호 배제 제공을 위해서는 재진입 락과 연관시켜야 한다.
ReentrantLock 을 생성하고 newCondition() 메서드를 호출해 조건 변수를 생성한다.
이 메서드는 조건 변수를 나타내는 Condition 객체를 반환한다.
Lock lock = new ReentrantLock();
Condition[] condVars = new Condition[5];
for (int i = 0; i < 5; i++) {
condVars[i] = lock.newCondition();
}
5개의 스레드에 작업을 수행하도록 하고자 할 때, ReentrantLock 을 생성하고 스레드 별로 하나씩 총 5개의 조건 변수를 생성한다.
public void doWork(int threadNumber)
{
lock.lock();
try {
if (threadNumber != turn)
condVars[threadNumber].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();
}
}
스레드에서 doWork() 를 호출하면서 스레드 번호를 전달한다.
threadNumber 값이 turn과 일치하는 스레드만 진행하고, 다른 스레드는 기다린다.
차례가 맞는 스레드는 작업 수행 후 다음 스레드를 깨운다.
finally 를 통해 모든 락을 반드시 해제시킨다.
대체 방안
트랜잭션 메모리
트랜잭션 메모리는 데이터베이스 이론에서 유래된 개념으로, 병렬 프로그래밍에서 락 없이 프로세스 동기화를 지원해준다.
메모리 트랜잭션은 여러 연산을 트랜잭션으로 묶고 모든 연산이 성공적으로 끝나야 확정(commit)되는 기법으로, 실패시 롤백(roll-back)하여 이전 상태로 되돌린다.
void update() {
atomic {
/* modify shared data */
}
}
락을 획득하고 해제하는 전통적인 방식과 다르게, atomic 과 같이 내부적으로 연산이 트랜잭션으로 실행된다는 것을 보장하는 structure를 활용할 수 있다.
명시적으로 락을 사용하지 않아 교착 상태가 발생하지 않고, 시스템이 원자성을 보장하므로 병행성이 증가하며 유지보수가 용이하다.
소프트웨어 트랜잭션 메모리(STM)
특별한 하드웨어 없이 소프트웨어로만 구현하며, 트랜잭션 블록 안에 검사 코드를 삽입하여 동작한다.
이 검사 코드는 컴파일러에 의해 삽입되고, 명령문들이 동시에 실행될 수 있는 지점과 락킹이 필요한 지점을 검사하여 트랜잭션을 관리한다.
하드웨어 트랜잭션 메모리(HTM)
하드웨어 캐시 계층 구조와 캐시 일관성 프로토콜을 사용하여 CPU 하드웨어 차원에서 지원한다.
코드 수정 없이 사용 가능하며 STM보다 적은 오버헤드를 가진다.
OpenMP
OpenMP는 공유 메모리 환경에서 병렬 프로그래밍을 돕는 도구이다.
컴파일러 디렉티브 #pragma omp parallel 이후의 코드는 병렬로 실행된다.
이 영역 내부의 코드는 한 번에 한 스레드만 실행할 수 있다.
void update(int value) {
#pragma omp critical
{
counter += value;
}
}
내부적으로는 이진 세마포나 mutex처럼 동작한다.
여러 임계구역을 사용한다면 각 임계구역에 이름을 할당할 수 있으며, 두 개 이상의 스레드가 동일한 이름을 가진 임계구역에 동시에 활동할 수 없게 할 수 있다.
함수형 프로그래밍 언어
최근에는 다중 코어 시스템과 병렬 처리가 중요해지면서 함수형 언어가 관심을 받고 있다.
명령형 언어는 전통적인 프로그래밍 방식으로 상태가 바뀌는 방식으로 동작하지만, 함수형 언어는 상태를 유지하지 않는다.
따라서 Race Condition이나 동기화 문제가 상대적으로 적어 코드가 더 안정적이고 예측 가능하다.
대표적으로는 Erlang, Scala 가 있다.
댓글남기기