day13 🌕

장미·2022년 6월 26일

오늘의 성과

목록 보기

13/129

세마포어 뮤텍스 마저 정리하기

뮤텍스와 세마포어는 임계구역(critical section) 문제를 해결하기 위해 등장한 알고리즘이다.

그렇다면 임계구역(== 임계영역)이 무엇이냐?
임계구역은 *공유 자원의 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 뜻한다.

공유 자원: 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다.
공동으로 이용되기 때문에 누가 언제 데이터를 쓰거나 읽느냐에 따라 결과가 달라질 수 있다.

즉, 프로세스 실행 상황에서는 공유할 수 없는 자원이 중요한 자원이자 임계구역이다.
따라서 임계구역에서는 프로세스들이 동시에 작업하면 안 된다.
어떤 프로세스가 임계구역에 들어가면, 다른 프로세스는 임계구역 밖에서 기다려야 한다.
먼저 들어간 프로세스가 나와야 들어갈 수 있는 구조다.

임계구역과 관련하여 어떤 문제가 있느냐 하면, 전통적인 문제로 생산자-소비자 문제가 있다.

producer()
{
	input(buf);
	sum = sum + 1;
}

생산자: 계속 물건을 생산하여 버퍼에 넣는다.

consumer()
{
	output(buf);
	sum = sum = 1;
}

소비자: 계속 버퍼에서 물건을 가져온다.

버퍼가 비었는지 가득 찼는지 확인하기 위해 sum이라는 전역 변수(공유 자원)를 사용한다.

위의 알고리즘은 큰 문제 없이 돌아가는 것처럼 보이지만, 생산자 코드와 소비자 코드가 동시에 실행되면 문제가 발생한다.

생산자가 물건 하나를 buf 4에 저장하고, sum을 4로 바꿔야 하는데 못 바꿨을 때!
소비자가 물건 하나를 소비하고 sum을 2로 바꿔야 하는데 못 바꿨을 때!
→ 이 상태에서 생산자와 소비자의 sum값 변경 부분이 거의 동시에 실행되면 문제가 발생한다.

미세한 시간 차를 두고 생산자의 sum = sum + 1이 먼저 실행, 뒤에 소비자의 sum = sum - 1이 실행되면 결과값은 4가 아니라 2가 나올 것이다.
반대의 순서로 실행된다면 결과값 sum은 4가 나올 것이다.

즉, 실행 순서에 따른 결과 차이가 일어난다는 것이다.

그래서 이 임계구역 문제를 해결하기 위해 뮤텍스와 세마포어가 등장했다.

뮤텍스(Mutex)

스레드들 간에서 공유가 배제되는 객체.
Lock을 사용하여 임계구역을 보호하고 *경쟁 조건(race condition)을 예방한다.

경쟁 조건: 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황.

쉽게 말하자면, 카페 화장실(임계구역)에 들어갈 때 열쇠(Lock)를 받아 들어가는 것과 마찬가지다.
그리고 볼 일을 다 보면(ㅋㅋ), 즉 사용을 마치면 열쇠(Lock)를 다시 반납하는 것과 같다.

while(true) {
	acquire lock
		critical section

	release lock
		remainder section
}

acquire() {
	while (!available) {
		; /* busy wait */
	}
	available = false;
}

release() {
	available = true;
}

이것저것 코드가 많지만, acquire 부분은 열쇠를 얻는 부분이고, release 부분은 열쇠를 반납하는 부분이라 생각하면 된다.

참고로 busy waiting(바쁜 대기)은 상태 변화를 살펴보기 위해 반복문을 무한 실행하며 기다리는 것으로, 쉽게 말하자면 열쇠 얻으려고 존버한단 얘기다.

근데 이 바쁜 대기는 자원을 너무 많이 낭비하기 때문에 문제가 된다.
→ 뮤텍스에선 바쁜 대기가 가장 큰 문제가 된다.

하지만 스핀락(Spinlock)이라고, busy waiting을 하는 Mutex Lock을 칭하는 단어가 있다.

어쨌든 똑같이 busy waiting을 하는 놈인데 왜 이렇게 따로 이름을 붙여줬냐면, 얘가 은근 도움이 될 때가 있기 때문이다.

그게 언제냐면 CPU 코어가 여러 개일 때다. 코어가 하나일 땐 공회전만 계속하느라 자원 낭비가 심한데, 여러 개일 경우엔 빈 코어에서 존버 타다가 Lock이 풀리면 바로 진입할 수 있기 때문이다.
→ 즉, context switch 시간을 아낄 수 있단 소리다.

지금까지 살펴본 Mutex를 통해 상호 배제를 보장할 수 있다는 걸 알게 됐다.

세마포어(Semaphore)

복수의 작업을 동시에 병행하여 수행하는 운영 체제(또는 프로그래밍)에서 공유 자원에 대한 접속을 제어하기 위하여 사용되는 신호.

뮤텍스가 2개의 프로세스에서만 사용 가능했다면, 세마포어는 여러 개, 즉 n개의 프로세스에서도 사용할 수 있다.

Semaphore(n); //n == 공유 가능한 자원 수

P(); //사용 중 표시 (== wait)

	/* 임계구역 */

V(); //비었어~ 표시 (== signal)

세마포어 코드

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

사용 가능한 자원이 있으면 1만큼 감소시키고 임계구역에 진입한다.

signal(n) {
	n++;
}

n값을 1 증가시키고, 기다리는 프로세스에게 진입해도 좋다는 신호를 보낸다.

임계구역에 진입하기 전에 스위치를 사용 중(P())으로 놓고 임계구역으로 들어간다.
이후 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다.
프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호(V())를 보낸다.

→ 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

세마포어에서 잠금이 해제되길 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 신호를 받으면 큐에서 나와 임계구역에 진입한다.
→ 즉, 바쁜 대기를 하는 프로세스가 없다.

여기서 잠깐, 이진 세마포어에 대해 얘기하자면

*이진 세마포어(Binary Semaphores)는 자원의 범위가 0과 1로만 나타나기 때문에 뮤텍스와 유사하다.

하지만 차이점은, 뮤텍스는 Lock을 가진 자만 Lock을 해결할 수 있는 반면, 세마포어는 그렇지 않다는 거다. (wait와 signal을 날리는 존재가 다를 수 있다. 즉, Lock을 걸지 않은 스레드도 signal을 보내 Lock을 해제할 수 있다는 소리다.)

세마포어의 내부 코드가 실행되는 도중에 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못한다.
→ 상호 배제가 안 이뤄지고, 무한 대기하게 된다는 뜻이다.

세마포어의 가장 큰 문제는 잘못된 사용으로 인해 임계구역이 보호받지 못한다는 것이다.

예1. 프로세스가 세마포어를 사용하지 않고 바로 임계구역에 들어간 경우
예2. P()를 두 번 사용하여 *wake_up 신호가 발생하지 않은 경우
*임계구역에 진입해도 좋다는 신호
예3. P()와 V()를 반대로 사용하여 상호 배제가 보장되지 않은 경우

그러므로 P()와 V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야 한다.

참고 자료

조성호, 쉽게 배우는 운영체제
주니온TV 아무거나연구소, “운영체제: 13. 뮤텍스와 세마포어”, https://youtu.be/nezpmbe6Tkg
쉬운코드, “스핀락(spinlock) 뮤텍스(mutex) 세마포(semaphore) 각각의 특징과 차이”, https://youtu.be/gTkvX2Awj6g
우아한Tech, “와일더의 Mutex vs Semaphore”, https://youtu.be/oazGbhBCOfU

동기 비동기 정리

+) 22. 06. 27. day14 🌕 에 추가 완료!

코테 문제 마저 풀어보기

1. 2016년

class Solution {
    public String solution(int a, int b) {
        String answer = "";

        LocalDate date = LocalDate.of(2016, a, b);
        DayOfWeek day = date.getDayOfWeek();

        answer = day.getDisplayName(TextStyle.SHORT, Locale.US).toUpperCase();

        return answer;
    }
}

➡️ 2016년 중 입력 받은 달(a)과 일(b)의 요일(day)을 "SUN", "MON"... 형식으로 출력한다.

나는 이렇게 변수에 값을 저장했는데 했는데, 나랑 같은 라이브러리를 쓴 사람들은 변수에 저장하지 않고 아예 return에 다 때려 박았더라.
코드가 한층 더 간결해졌긴 하지만 과연 이걸 본 사람들이 이 메서드가 무슨 역할을 하는지 한번에 알아볼 수 있을까? 하는 의문이 들었다.
물론 내 코드도 별반 다를 것 없긴 한데. 아무튼 애초에 코테에서 이런 라이브러리를 써도 되는지부터가 의문인데(이거에 대해서 검색해봤더니 의견이 좀 분분하다. 근데 그냥 기본적인 거 말고, 이렇게 이런... 이런 걸 쓰는 건 별로인 게 맞는 듯하다.) 일단 나는 그냥 문법 공부 겸 연습해보는 거니 어쩔티비다.

어쩔티콘 2