[Operating System] Synchronization Tools (2)

hina·2023년 7월 11일

Operating System

목록 보기

7/9

Mutex Lock and Semaphore

Mutex Lock

이전의 방법들은 application programmers가 접근하기 어렵고 복잡하다.
OS designer는 임계 영역 문제를 해결하기 위한 software tool들을 제공하는데, 그 중 가장 간단한 방법이 Mutex Lock이다.

acquire() {
	while (!available);
	avilable = false;
}

release() {
	avilable = true;
}

do {
	acquire();
		/* critical section */
	release();
		/* remainder section */
} while (true);

acquire()과 release()는 atomic 해야 한다.
-> hardware atomic instructions로 구현한다.
mutex lock은 busy waiting (spinlock) 이 발생한다.

busy waiting
- while문 내에서 무한정으로 조건을 확인하므로 CPU를 계속 소모함 -> 성능에 영향을 줄 수 있다.
- busy waiting 해결 방법: 조건을 만족하지 않으면 sleep() 하고 나중에 다시 깨우는 방법
- busy waiting 문제는 single core에서는 큰 문제이지만, multi core에서는 커버할 수 있다.

Semaphore

Semaphore는 Mutex Lock보다 정교한 방법을 제공한다.
Semaphore S는 integer value이다. (<-> mutex lock의 available은 boolean)

두 개의 atomic한 operation이 있다.

wait()과 signal() 또는 P()와 V()

wait(S) {
		while (S<=0); // busy wait
		S--;
}

signal(S) {
		S++;
}

binary semaphore

integer value가 0 또는 1인 경우
- S가 1이면 진입, 0이면 wait
- 어떤 케이스에서는 mutex lock과 동일하게 적용될 수 있다.
초기값: S1 = 1
- binary semaphore는 임게 영역 문제 상황이다.

Counting semaphore

integer value가 범위가 존재한다.
초기값: S1 > 1
- Counting semaphore는 자원이 여러 개인 상황이다.

Semaphore 의 다른 예시: 순서 동기화

Binary semaphore: 초기값 S1 = 0

Task 1 code();
V(S1);

P(S1);
Task 2 code();

Implementation

두 프로세스가 wait()과 signal()을 동시에 실행할 수 없다는 것을 보장한다.
- wait()과 signal() 코드 자체가 critical section에 놓인다.
- critical section 안에서 구현하기 위해서는 또 busy waiting이 발생하지만, 임계 영역 내의 코드는 정해져 있고 짧은 시간에 해결된다.
- 만약 critical section에서 많은 시간이 소요된다면 그것은 좋은 해결 방법이 아니다.

Implementation with no waiting

busy waiting이 없게 하기 위해서는 프로세스를 무한루프로 대기하게 하는 것이 아닌 waiting queue로 보내 대기하게 한다.
이후 다른 프로세스에서 signal()을 호출하면 대기 큐에 있던 프로세스를 깨우고 ready queue로 보내 CPU 자원 획득을 기다릴 수 있도록 한다.

typedef struct
{
	int value;
	struct process* list; // linked list
} semaphore;

wait(semaphore* S)
{
	S->value--;
	if (S->value < 0)
	{
		add this process to S->list;
		sleep(); // 대기 큐로 이동함.
	}
}

signal(semaphore* S)
{
	S->value++;
	if (S->value <= 0)
	{
		remove a process P0 from S->list.
		wakeup(P); // 준비 큐로 이동함.
	}
}

-> 위 방법은 무한루프를 돌지 않으므로 single core에서 효율적으로 사용할 수 있다.

disable_interrupt()와 enable__interrupt() 방법은 멀티코어보다 싱글코어에서 효율적이다.
멀티코어의 경우, busy waiting이 더 낫다.

Problems with Semaphores

세마포어는 일반 사용자가 사용하기에 어렵다.
대부분의 유저는 세마포어를 사용하지 않으며, 이를 잘못 사용해도 인지하기 힘들다. -> 컴파일러에서 잘못 사용한 것을 잡아주지 않기 때문
Deadlock과 starvation이 나중에 발생할 수 있다.

Monitor

Why Monitor?

세마포어는 구조적이지 않았다.
- race condition이 발생하며 low level 언어이다.
프로세스 동기화를 위해 높은 레벨의 추상화된 편리한 매커니즘의 필요성이 요구됨
- High level의 mutual exclusion: 함수는 프로세스 하나밖에 사용하지 못한다.
- Locks are hidden: 모니터가 알아서 Lock과 unlock을 한다.

Monitor

monitor는 하나의 프로세스만 프로시저를 수행할 수 있다. -> 상호배제 만족
다른 동기화 조건은 아직 만족하지 못한다.

monitor monitor-name {
	// shared variable declarations <- private 변수 선언
	...
	procedure P1 (...) {...}
	...
	procedure Pn (...) {...}
	Initialization code (...) {...}
};

구성: shared data, operations, initialization code, entry queue (waiting queue)
- 순서에 대한 동기화는 없음.

queues associated with x,y conditions: 순서 제어 (order synchronization)

entry queue: monitor로의 진입 관리, mutual exclusion 제어

condition x, y: 순서 동기화를 위한 변수
x.wait(): x.signal() 전까지 block
x.signal(): 만약 x.wait()이 없으면 아무런 일도 하지 않는다.

Monitor - Code Example

monitor ResourceAllocator {
	boolean busy; // 공유 변수
	condition x; // queue
	
	void acquire(int time) { // = wait()
		if (busy)
			x.wait(time); // 바쁘므로 대기
		busy = true;
	}

	void release() { // = signal()
		busy = false;
		x.signal();
	}
	
	initialization_code() {
		busy = false; // available = true
	}
};

모니터에 acquire()와 release() 구현

condition variable

만약 P가 x.signal()을 호출한 뒤에 추가적으로 해야 할 일이 있다면, 그 일을 먼저 하는 것과 다른 P가 wait 상태에서 깨어나 들어오는 것 중 어떤 게 먼저일까?

Signal and wait - 다른 P가 임계 영역으로 들어올 수 있도록 signal을 호출하고 wait 상태로 간다.
Signal and continue - 새로 깨어난 P는 임계 영역에 있던 P가 나머지 일을 끝낼 때까지 기다린다.
두 방법 모두 장단점이 존재하며, Signal 후 잠깐 물러난 프로세스가 기다리는 큐는 우선순위가 높다.

Monitor Implementation 1

변수
- semaphore monitor_lock // 초기값 = 1
- semaphore sig_lock // 초기값 = 0
- int sig_lock_count = 0

wait(monitor_lock); // 모니터 진입 가능여부 판단
	...
	body of F
	...
if (sig_lock_count) > 0) // signal 후 잠깐 wait 중인 프로세스가 있다면
	signal(sig_lock); // 먼저 들어올 수 있다
else // 없다면
	signal(monitor_lock); // 다음으로 모니터 밖에서 기다리는 프로세스가 들어온다

실제 구현 함수 F만 작성하면, 모니터 진입 코드와 퇴장 코드는 컴파일러가 추가한다.
-> monitor는 언어 레벨에서 구현된 API이기 때문이다.

Monitor Implementation 2

변수
- int x_count; // 초기값 0, x를 기다리고 있는 프로세스의 수
- semaphore x_sem; // 초기값 0

/* x.wait */
x_count++;
// wait 하기 전에 들여보낼 process를 찾는다.
if (sig_lock_count > 0) // sig_wait이 존재한다면
	signal(sig_lock); // 깨운다
else // 없으면
	signal(monitor_lock); // 밖에서 기다리는 프로세스를 깨운다.
wait(x_sem); // wait 상태
x_count--; // wait 완료

/* x.signal */
if (x_count > 0) { // x_wait 하고 있는 프로세스가 있으면
	sig_lock_count++; // 그 프로세스를 들여보내고 나는 sig_wait 할 것이다
	signal(x_sem); // 기다리고 있는 프로세스 들여보낸다
	wait(sig_lock); // sig_wait
	sig_lock_count--; // wait 완료
}