[CS/OS] 동기화 도구(SpinLock/Mutex/Semaphore/Monitor)

다은·5일 전

OS concurrency

CS

목록 보기

5/7

OS에서 Critical section에 대한 상호 배제를 보장하고 Synchronization를 제어하는 방법에는 무엇이 있는가

1. 하드웨어적 해결 방법

소프트웨어만으로는 완벽한 상호배제가 어렵거나 느리기 때문에 하드웨어의 도움을 받음

1. 인터럽트 금지

1. 원리

Interrupt 자체를 Turn Off
OS가 Context Switch하지 못하도록 막음

2. 특징

OS가 Interrupt에 의해 주도권을 변경하는 것을 막을 수 있음
따라서 명령어가 Atomic하게 수행됨을 보장할 수 있음

3. 한계

단일 프로세서에서만 유효함
- 다른 CPU에서 실행되는 스레드는 막을 수 없음
유저 레벨에서는 사용 불가
- 커널에 준하는 권한을 유저 레벨에게 부여해야 함
- 이는 보안 측면에서 비권장
기능 상실
- Interrupt가 꺼지면, OS의 스케쥴링이 동작하지 않아 프로세스가 종료될 때까지 다른 프로세스는 대기해야 함
- I/O 이후 돌아오는 프로세스의 시그널을 놓칠 수도 있음

void lock() {
	disableInterrupts();
}

void unlock() {
	enableInterrupts();
}

2. Atomic Instructions

Test-And-Set

읽기와 쓰기를 원자적으로 수행함
single shared variable을 이용함
주로 Spinlock 구현에 사용

typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *lock) {
	lock->flag = 0;
}

int testAndSet(int *old_ptr, int new) {
	// old의 값을 new로 바꾼 후 old값 리턴
	int old = *old_ptr;
	*old_ptr = new;
	return old;
}

void lock(lock_t *lock) {
	// 결과 값이 0 : 반복문을 탈출하고 내가 lock을 획득
	// 결과 값이 1 : 다른 프로세스가 이미 lock을 획득한 상태. 반복문을 탈출하지 못하고 무한정 대기
	while (testAndSet(&lock->flag, 1) == 1);
}

void unlock(lock_t *lock) {
	lock->flag = 0;
}

Compare-And-Swap

값의 비교와 교체를 원자적으로 수행
TestAndSet보다 더 세밀한 제어가 가능함
Mutex, Semaphore 등에 이용됨
Lock-Free / Wait-Free 동기화 등에 사용

typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *lock) {
	lock->flag = 0;
}

int compareAndSwap(int *old_ptr, int expected, int new) {
	int old = *old_ptr;
	if (old == expected) {
		*old_ptr = new;
	}
	return old;
}

void lock(lock_t *lock) {
	// 결과 값이 0 : 반복문을 탈출하고 내가 lock을 획득 (0이랑 비교해서 true, 1로 swap)
	// 결과 값이 1 : 다른 프로세스가 이미 lock을 획득한 상태. 반복문 탈출하지 못하고 무한정 댁정 대기
	while (compareAndSwap(&lock->flag, 0, 1) == 1);
}

void unlock(lock_t *lock) {
	lock->flag = 0;
}

Lock-Free Algorithm

Lock 없이 멀티 프로그래밍의 동시성을 극대화하기 위한 Non-Blocking 알고리즘

CAS를 기반으로 동작함

우선 공유 변수의 값을 변경하고 값이 맞는지 확인함

맞지 않다면, 다시 시도함

ABA 문제
void lockFree(int *ptr) {
	while (1) {
		int old = *ptr; // 현재 값을 읽음
		int new = old + 1; // 우선 값을 변경
		// 업데이트 시도
		if (compareAndSwap(&ptr, old, new) == old) {
			// 업데이트 성공 -> 반복문 탈출
			break;
		}
		// 업데이트 실패 -> 다시 시도
	}
}

2. OS/시스템 레벨의 동기화 도구

1. Spinlock

상호 배제, 즉 Critical Section에 단 하나의 쓰레드만 들어올 수 있도록 하기 위해 lock이 사용됨

1. 원리

Busy-Waiting 방식
루프를 돌며 대기함

2. 특징

Context Switch 비용 없음
Critical Section에 오직 하나의 스레드만 진입하도록 하여 상호 배제 보장

3. 사용

Critical Section이 짧을 때 유리

4. 단점

대기 시간이 길어지면 CPU 자원을 낭비함
starvation이 발생할 수 있음

5. 해결책

yield()
- busy-waiting 대신 CPU 양보
- context switch 비용 + starvation 가능성
queue + sleep
- queue에 들어가 sleep하고 대기
  -> mutex

2. Mutex

1. 원리

Blocking/Sleep 방식
lock/unlock 단계에서 spin lock을 통해 우선 guard를 얻음
락을 못 얻으면 Sleeping Queue로 들어감 → Context Switch 발생
락을 해제할 때 queue가 비어있지 않으면 대기하는 쓰레드를 깨움

2. 특징

Binary Semaphore와 유사
제어권을 명확하게 관리함
- thread가 다음 thread를 unpark()로 깨우며 제어권을 전달함

3. 사용

Critical Section이 길 때 유리

🚨 lock()에서 park() 직전에 scheduling이 되면?

1. lock()에서 A 쓰레드가 guard를 해제함
2. park()하기 전에, 즉 sleep하지 않은 상태로 제어권이 B 쓰레드로 넘어감
3. B 쓰레드가 작업을 마친 뒤, unlock()에서 unpark(A)를 수행해 queue에 있는 A 쓰레드를 깨우려고 함
4. A 쓰레드는 sleep 상태가 아니라 요청이 무시될 수 있음
5. 다시 A 쓰레드로 제어권이 넘어옴
6. park()를 마저 실행함
7. A를 unpark해줄 쓰레드가 없기 때문에, A 쓰레드는 영원히 깨어나지 못할 수도 있음 → deadlock

→ OS 차원에서 원자적 SysCall을 제공해야 함

typedef struct __lock_t {
	int guard; // 보호장치
	int flag; // 실제 락
	queue_t *q; // sleep하는 프로세스들이 대기하는 queue
} lock_t;

void init(lock_t *lock) {
	lock->guard = 0;
	lock->flag = 0;
	queue_init(lock->q);
}

void lock(lock_t *lock) {
	// spin-lock 이용해 guard 획득
	while (testAndSet(&lock->guard, 1) == 1);
	
	if (lock->flag == 0) {
		// lock 획득
		lock->flag = 1;
		// guard 해제
		lock->guard = 0;
	} else {
		queue_add(lock->q, gettid());
		
		// sleep 이전에 quard 먼저 해제
		// deadlock 발생 가능!
		lock->guard = 0;
		park();
	}
}

void unlock(lock_t *lock) {
	// spin-lock 이용해 guard 획득
	while (testAndSet(&lock->guard, 1) == 1);
	
	if (queue_empty(lock->q)) {
		// lock 해제
		lock->flag = 0;
	} else {
		// queue에서 가장 오래 대기한 쓰레드 깨움
		unpark(queue_remove(lock->q));
	}
	lock->guard = 0;
}

3. Conditional Variable

1, 2번과 다르게, 각 쓰레드의 실행 순서를 보장하기 위해 CV가 이용됨

1. 원리

조건이 만족될 때까지 락을 풀고 대기하는 대기실
thread가 특정 조건을 만족하지 못하면, lock을 반납하고 Sleeping Queue로 들어감
다른 thread가 작업을 진행하고 signal을 보내면, 깨어나서 lock을 다시 잡고 작업을 수행함

2. 특징

CV는 상태를 저장하지 않고 그저 thread를 잠재우는 queue의 역할만 수행함
반드시 mutex와 함께 실행되어야 함 → deadlock 방지
while을 이용해 조건을 확인함

void child() {
    lock(&m); // mutex lock 획득   
    done = 1;
    signal(&c); // 대기하는 thread 깨움
    unlock(&m);
}

void parent() {
    lock(&m);
    while (done == 0) {
        wait(&c, &m); // m 반납 -> CV에 들어감 -> 다시 일어나면 m 획득
    }
    unlock(&m); 
}

Producer-Consumer Problem

Producer : 빵을 생산하는 쓰레드
- empty : producer가 대기하는 CV
Consumer : 빵을 소비하는 쓰레드
- fill : consumer가 대기하는 CV

void *producer(void *arg) {
	// 정해진 분량만큼 빵을 생산함 (loop개만큼)
	for (int i = 0; i < loops; i++) {
		lock(&m);
		// 빵을 최대치만큼 만들었을 경우 (남은 버퍼가 없을 경우)
		while (count == max) {
			// empty라는 CV에 producer을 넣고 대기함
			wait(&empty, &m);
		}
		// 빵 생산
		put(i);
		// fill이라는 consumer의 CV에서 한 쓰레드를 깨움
		signal(&fill);
		unlock(&m);
	}
}

void *consumer(void *arg) {
	// 버퍼에 데이터가 들어오면 처리
	while (1) {
		lock(&m);	
		// 빵이 더이상 없을 경우 (읽을 데이터가 없을 경우)
		while (count == 0) {
			// fill이라는 CV에 consumer 넣고 대기
			wait(&fill, &m);
		}
		// 빵 소비
		get();
		// empty라는 producer의 CV에서 한 쓰레드를 깨움
		signal(&empty);
		unlock(&m);
	}
}

4. Semaphores

CV에 더해서 상호 배제 + 실행 순서 보장을 위해 Semaphore가 이용됨

1. 원리

Integer Value로 State를 관리함
- wait() : 조건을 검사하고 sleep하거나 value를 1 감소시킴
- post() : value를 1 증가시키고 대기하는 쓰레드를 깨움

2. 특징

semaphore은 Lock + CV로 구현할 수 있음
value의 초기값 설정에 따라 다른 기능을 구현할 수 있음
- 1로 초기화 → binary semaphore → mutex와 같은 상호 배제 기능 수행
- n으로 초기화 → counting semaphore → 자원 개수 관리
소유권 제어가 없음
- 락을 건 사람이 아닌 다른 사람이 락을 해제할 수도 있음
- mutex와의 결정적인 차이점
- 이 특징 덕분에 ordering이 가능해짐

/**
	Semaphore을 LOCK + CV로 구성
**/
typedef struct __sem_t {
	int value;
	lock_t lock;
	cond_t cond; // CV
} sem_t;

void init(sem_t *sem, int value) {
	sem->value = value; // 허용할 자원 개수 초기화
	lock_init(&sem->lock);
	cond_init(&sem->cond);
}

void wait(sem_t *sem) {
	lock(sem->lock);
	
	while (sem->value <= 0)
		cond_wait(&sem->cond);
	
	sem->value--;
	unlock(sem->lock);
}

void post(sem_t *sem) {
	lock(sem->lock);
	sem->value++;
	cond_signal(&sem->cond);
	unlock(sem->lock);
}

/**
	Mutex(Lock)을 Binary Semaphore로 구성
	wait => lock (1 -> 0)
	post => unlock (0 -> 1)
**/
typedef struct __lock_t {
	sem_t sem;
} lock_t;

void init(lock_t *lock) {
	// 1로 초기화: 최대 하나의 쓰레드가 접근할 수 있어야 함
	sem_init(&lock->sem, 1);
}

void lock(lock_t *lock) {
	// sem의 value -1
	wait(&lock->sem);
}

void unlock(lock_t *lock) {
	// sem의 value +1
	post(&lock->sem);
}

3. 고수준 언어 차원의 도구

개발자가 쓰기 편하게 프로그래밍 언어 차원에서 도구를 제공함

1. Monitors

1. 특징

ADT : 공유 변수와 메서드를 하나의 클래스로 묶음
컴파일러/언어가 lock 관리를 자동으로 해줌
언어 차원에서 상호배제를 관리해줌
Ordering이 필요할 때는 CV를 이용함

2. 사용

Java : synchronized

public class SynchronizedCounter {
	private int c = 0;
	public synchronized void increment() {
		c++;
	}
	public synchronized void decrement() {
		c--;
	}
	public synchronized int value() {
		return c;
	}
}

Semantics

Ordering을 위해 CV를 이용하는 상황에서, signal()을 보낸 쓰레드와 깨어난 쓰레드 간의 제어권 이동 방식의 차이

1. Hoare Semantics

signal-and-wait
실행 중인 쓰레드는 block하고, 깨어난 쓰레드에게 바로 제어권이 넘어감
따라서, if절로 조건을 확인해도 무방함
오버헤드가 큼

if (conditions_not_met)
	wait();

2. Mesa Semantics

signal-and-continue
실행 중인 쓰레드는 이어서 실행되고, 깨어난 쓰레드는 대기 큐에 들어가 lock을 잡기 위해 경쟁 함
hoare보다 더 효율적이고 현대 OS에서 더 많이 사용되는 방식

while (conditions_not_met)
	wait();

4. 비교

Mutex vs Binary Semaphores

	Mutex	Binary Semaphore
핵심 개념	Locking	Signaling
소유권	있음	없음
해제 주체	락을 건 스레드 본인만 해제 가능	누구든지 해제 가능
목적	상호 배제	순서 제어 + 상호 배제
우선순위 역전 문제	해결 가능	해결 어려움

CV vs Semaphores

	Condition Variable	Semaphore
핵심 개념	조건 대기 큐	자원 카운터
상태	없음	있음
Lock 필요 여부	필수	불필요
동작 방식	`Wait` (Unlock+Sleep) / `Signal`	`P` (Dec & Wait) / `V` (Inc & Wake)
목적	순서 제어	자원 관리 + 상호 배제
비유	직원이 부를 때까지 대기실에서 쉼	식권 자판기 (식권 있으면 입장, 없으면 대기)

다은

CS 마스터를 향해 ..

이전 포스트

[CS/OS] File System

다음 포스트

[CS/OS] 동기화 도구(SpinLock/Mutex/Semaphore/Monitor)

CS

1. 하드웨어적 해결 방법

1. 인터럽트 금지

2. Atomic Instructions

Test-And-Set

Compare-And-Swap

Lock-Free Algorithm

2. OS/시스템 레벨의 동기화 도구

1. Spinlock

2. Mutex

3. Conditional Variable

Producer-Consumer Problem

4. Semaphores

3. 고수준 언어 차원의 도구

1. Monitors

Semantics

4. 비교

Mutex vs Binary Semaphores

CV vs Semaphores

[CS/OS] File System

[CS/Java] Garbage Collection의 동작 원리

0개의 댓글