[pintos] 1주차 - 키워드 정리 (1) : Semaphore/Mutex, Busy Waiting/Sleep Waiting

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) { //ticks는 sleep 상태에 돌입해야 할 시간을 의미한다.
	int64_t start = timer_ticks (); //현재 타이머의 ticks을 가져오고 start에 대입한다.

	ASSERT (intr_get_level () == INTR_ON); 
	while (timer_elapsed (start) < ticks) //현재 타이머의 tick-start와 인자로 받은 ticks를 비교한다.
		thread_yield (); //ticks의 값이 더 크면 실행한다.
}

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) {
	struct thread *curr = thread_current (); //현재 실행 중인 스레드 가져오기
	enum intr_level old_level;

	ASSERT (!intr_context ()); //인터럽트 핸들러 내부에서는 yield 호출 금지

	old_level = intr_disable (); //인터럽트를 비활성화
	if (curr != idle_thread) //idle 스레드는 레디 큐에 넣지 않음
		list_push_back (&ready_list, &curr->elem); //현재 스레드를 레디 큐의 마지막에 넣기
	do_schedule (THREAD_READY); //스케줄러를 호출하여 현재 스레드를 THREAD_READY 상태로 설정 후, 다음 스레드로 전환
	intr_set_level (old_level); //다시 인터럽트 활성화
}

 

일단 구현해야 할 부분의 일부를 해석해보았다.

아직 뭘 구현해야겠는지 잘 모르겠으니 그만 알아보고 키워드 공부를 하자 🤨

 

Busy waiting (spinning) / Sleep waiting 

서로 다른 프로세스나 스레드가 임계 영역에 동시에 접근하려고 할 때, 두 가지 동기화 처리 방법이 있다.

1. Busy waiting : 조건이 만족될 때까지 무한 대기하며 cpu를 낭비

2. Sleep waiting : 조건이 만족될 때까지 cpu를 양보하고 sleep상태로 있다가 조건이 다시 만족되면 wake

여기서 조건이란 공유 자원에 접근할 수 있는 권한이 만족되었는가이다.

 

예를 들어 p1이 임계 영역의 lock을 얻어서 사용하던 중 context switch가 발생하여 p2가 공유 자원에 대한 lock을 가질 수 없게 됨

-> 무한 대기 하며 계속해서 cpu 점유하면 Busy waiting, sleep 상태로 전환되었다가 lock이 풀릴 때 다시 wake하면 Sleep waiting

 

Busy waiting은 필요한 자원을 얻을 수 있는 상태가 될 때까지 계속해서 무한 루프를 돌며 cpu를 낭비하므로 비효율적이다.

Sleep waiting을 사용하면 이 문제점을 극복할 수 있다. -> Semaphore, Mutex로 임계 영역에 접근 제한을 걸어서 구현하면 됨!

주의할 점은 임계 영역 접근 제한 기능을 남용하면 context switching이 너무 잦아서 시스템 성능이 저하될 수 있다는 것이다.

 

Semaphore

세마포어는 지금 공유 자원을 사용할 수 있는지의 상태를 나타내는 정수형 변수이다. 

예를 들어 세마포어 변수가 5이면 동시에 5개의 프로세스 또는 스레드만 임계 영역에 접근 가능하다는 뜻이다.

이 변수는 오직 P, V라는 연산으로만 다룰 수 있다.

 

세마포어 변수 값으로 0, 1만 가지는 경우와 0 이상을 가지는 경우로 종류가 나뉜다.

나중에 설명하겠지만 Binary Semaphore는 Mutex와 비슷한 방법이지만 차이가 있다고 한다.

 

1. Binary Semaphore : 0, 1

2. Counting Semaphore : 0 이상

 

P 연산 

- 진입 시 자원이 있는지 확인

- 자원이 있으면 자원 점유 / 없으면 wait

P(S):
    while S == 0: //자원이 없으므로 기다림
        wait
    S = S - 1 //S>0이 되면 S-=1을 수행하고 자원을 점유

 

V 연산

- 자원 반납

- 다음 스레드에게 자원 사용 허가

V(S):
    S = S + 1 //프로세스가 작업을 마치고 S+=1
    wake up one waiting thread (if any) //기다리던 스레드가 있다면 깨워서 자원을 사용하도록 함

 

임계 구역에 세마포어의 P, V 연산을 적용하면 다음과 같다.

P(S); //임계 구역 들어가기 전에 자원 확보
임계 구역에서 작업 수행
V(S); //임계 구역 나와서 자원 반납

 

(실행 예시)

1. 초기 세마포어 값은 S = 1
2. p1이 시작됨
   • P 연산 : P(S) == 1 이므로 while문 실행되지 않고 패스, S-=1을 수행하고 p1이 자원을 점유
3. p2가 시작됨
   • P 연산 : P(S) == 0 이므로 while문 실행, p2는 대기 상태로 전환
4. p1이 수행 완료됨
   • V 연산 : S+=1을 수행하여 세마포어 값이 다시 S == 1로 회복됨, p2가 자원 점유할 수 있게 깨우기

 

Mutex

하나의 스레드만 임계 구역에 접근할 수 있게 lock을 주는 방법

스레드 간 Mutual Exclusioin(상호 배제)를 실현해줌

다른 스레드는 lock이 풀릴 때까지 block 상태로 기다림

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock); //lock: 다른 스레드 진입 금지
임계 구역
pthread_mutex_unlock(&lock); //lock 해제: 다른 스레드 진입 허용

 

counter++는 비원자적 연산이기 때문에 동시에 여러 스레드가 접근하면 race condition이 발생한다.

뮤텍스로 감싸면 스레드 하나씩 순차적으로 접근하기 때문에 안전하다.

 

🤔 뮤텍스와 세마포어는 각각 어떤 상황에 쓰일까?

세마포어는 파일 시스템 상의 파일 형태로 존재하므로 시스템 범위에 걸쳐서 사용 가능하다.

시스템콜을 기반으로 동작하며, 커널에서 추적하므로 다른 프로세스들 사이에서도 공유할 수 있다.

즉 IPC(Inter-Process Communication)상황에서 주로 쓰인다.

반면 뮤텍스는 프로세스 범위에서 동작하며 프로세스가 종료될 때 자동으로 clean up 된다.

따라서 특정 주소 공간을 함께 쓰는 스레드 간의 공유 자원을 보호할 때 쓰인다.

POSIX를 이용하면 프로세스 간 공유 뮤텍스를 만들 수 있지만 세마포어가 훨씬 직관적이고 범용적이라고 한다.

//뮤텍스로 프로세스 간 공유 자원 관리하기
int counter = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

 

Semaphore와 Mutex 비교

내가 차이점을 공부하면서 느낀 핵심을 정리하면 다음과 같다.

 

뮤텍스는 주로 스레드 간 동기화에 쓰이므로 여러 스레드들이 프로세스의 전역 변수에 연산하려고 접근할 때마다 atomic race condition이 발생하지 않게 하는 것이 목적일 것이다. 따라서 좀 더 엄격하게 공유 자원을 관리하는 느낌이다. 하나의 공유 자원을 임계 영역으로 감싸고 그 임계 영역에 하나의 스레드만 접근할 수 있게 lock이라는 권한을 준다. lock을 가지고 있는 스레드만이 lock을 해제할 수 있으므로 스레드 끼리는 해당 임계영역에 있어서 상호배제적이게 된다.

 

세마포어는 주로 프로세스 간 동기화에 쓰인다. 따라서 프로세스 간에 공유하는 OS 자원이 주로 임계 영역으로 감쌀 대상이 된다. 이미 OS가 관리하고 있는 곳이라서 조금 덜 엄격하게 공유 자원을 관리하는 게 아닐까 생각한다. (수정 - 덜 엄격하다기 보다 세마포어는 lock의 소유자가 없고 signal 기반으로 unlock이 동작하기 때문에 자원을 아예 점유하여 상호 배제를 기대하기보다는 자원 접근 가능 여부를 확인하는 것을 주 목적으로 두고 있다는 점에서 차이가 있다고 보면 될 듯 하다.) 뮤텍스와 다르게 lock을 소유한다든가 lock 소유자만이 unlock할 수 있게 하지 않고 해당 자원이 필요한 프로세스가 또 생기면 signal을 보내 lock을 해제할 수 있다. 또한 하나가 아니라 여러 개의 공유 자원을 임계 영역으로 감싸서 임계 영역에 여러 개의(지정된 세마포어 변수 개수 만큼의) 스레드가 접근할 수 있다.

Mutex	Semaphore
0 또는 1 (이진)	0 이상 (정수 카운터)
스레드가 락을 소유	소유 개념 없음
락 소유자만 해제 가능	락을 걸지 않은 스레드도 signal을 보내 락을 해제할 수 있음
1개의 자원을 임계 영역으로 지정하여 한 번에 1개의 스레드만 접근 가능하게 함	여러 개의 자원을 임계 영역으로 지정하여 동시에 여러 개의 스레드가 접근 가능하게 함
스레드 간 상호배제가 목적	자원 개수를 제한하여 동기화를 실현하는 것이 목적
공유 변수 보호 (ex. counter++)	리소스 풀 (ex. 5개의 DB 커넥션, 3대의 프린터)
lock() unlock()	wait() signal()

예전에 대학교 OS 강의를 듣다가 일부만 이해하고 넘어갔던 개념인데

뮤텍스와 세마포어 차이를 확실히 정리하고 가니까 굉장히 후련한 느낌이다..

다음 키워드도 얼른 정리하러 가보자앗