[OS] Semaphore, Mutex

BaeRonui·2022년 2월 24일

OS

목록 보기

9/14

들어가기에 앞서, 용어를 간단히 정리해보자.

1. Critical Section

여러 process, thread가 같이 접근하면 안되는 공유 영역을 뜻한다. 두개 이상의 처리단위가 이 부분을 같이 접근하게 되면 Critical Section Problem이 발생한다고 한다. Critical Section이 아닌 부분은 Remainder Section이라고 한다.

Critical Section Problem 해결 조건

Mutual Exclusion

Progress

Bounded Waiting

2. Race Condition

여러 process, thread가 동시에 같은 data를 조작할 때, 결과를 예상할 수 없는 상태가 일어날 수 있다. 이러한 상황을 Race condition이라고 한다.

3. Atomic Operation

외부에서는 하나의 조작으로 보이는 조작을 뜻하며, atomic Operation의 결과는 실패, 성공 중 하나이다. 이것이 가능하려면 2가지 조건을 만족해야 한다.

Operation이 완료될 때까지 어떤 프로세스도 변경을 알지 못하도록 비가시적이어야 한다.

Operation 중 하나라도 실패하면, 전체가 실패하고 시스템의 상태를 operation 조작 이전의 상태로 복구해야 한다.

이러한 과정을 소프트웨어 적인 측면에서 전부 해결할 수 없고, 그렇다 하더라도 한계점이 명확하기에, 메모리 장벽, 하드웨어 명령, 원자적 변수와 같은 하드웨어의 지원을 통해 구현한다.

4. Synchronization

여러 process, thread를 동시에 실행해도 의도대로 시행되는 상황을 의미한다. Process, thread의 입장에서는, 서로가 알고 있는 정보가 일치하는 상황을 말한다. 우리는 이러한 상황을 만들기 위해 Mutex, Semaphores를 사용한다.

Mutex Lock

이러한 critical Section을 보호하고, race condition을 방지하기 위한 것이 바로 Mutex Lock이다. Mutex라는 용어는 우선, Mutual Exclusion의 축약어이다. Mutex Lock은 2가지 연산을 통해 구현이 된다.
1. Critical Section에 들어갈 권한을 얻어오는 acquire()
2. Critical Section을 사용한 후 다른 process, thread가 Critical Section에 진입할 수 있도록 해주는 release()


While (true) {
	acquire() // acquire lock
    * Critical Section *
    release() // release lock
    * Remainder Section *
}

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

void release() {
	avilable = true;
}

이 때, acquire(), release()는 atomic하게 작동해야 한다. release()는 하나의 명령만 있으므로 어느정도 이해가 되는데, acquire()은 대놓고 명령이 한개가 아니다. C/C++ 한줄도 대응하는 assembly 명령이 여러개인데, C/C++ 코드부터 여러줄인데 이게 가능한가 싶었다. 결론만 말하자면 하드웨어단에서 atomic 하게 보장하는 CAS(Compare_And_Swap)이라는 함수가 있는데, 이를 통해 구현이 가능하다.

volatile bool Key = false;

bool cas(volatile int* addr, int expected, int newValue) {
    return atomic_compare_exchange_strong(reinterpret_cast<volatile atomic_int*>(addr), &expected, new_value);
}

void cas_acquire() {
    while(CAS(&Key, false, true) == false);
}

void cas_release() {
    X = false;
}

이러한 락 구현은 spinlock이라고 한다.
위의 구현은 한 process가 Critical Section에 있는 동안, Critical Section으로의 접근을 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 한다. 즉,busy waiting을 해야 한다는 단점이 존재한다.
이러한 단점이 장점으로 작동하는 상황이 있다. Lock이 유지되는 기간이 context-switch 두 번 하는 시간보다 짧을 경우, Spinlock이 성능상의 우위를 갖고, 이러한 경우 spinlock이 사용된다.

소프트웨어적인 방법 : Peterson's Algorithm

CAS를 쓰지않고, 소프트웨어적으로 해결하는 방법으로는 'Peterson's Algorithm'이 있다. 이 알고리즘은 process가 2개인 경우만 적용이 가능하다는 단점이 존재한다. 즉, 최신 컴퓨터 아키텍처에서 제대로 작동하지 않는다.

bool flag[2] = {false, false}
int turn = 0

void p0() {
	flag[0] = true
    turn = 1
    while(flag[1] && turn == 1) {/* busy wait */}
	* critical Section *
    flag[0] = false
}

void p1() { ... }

진행방식은 다음과 같다.

flag[0] = true를 통해 Critical Section 사용의사를 밝히고, 턴을 넘긴다.

상대에게 턴을 넘겼는데, 상대가 Critical Section 사용의사가 있다면 (flag[1] == true 라면) 대기한다.

그렇지 않다면, Critical Section에 접근한다.

사용 후, flag[0] = false로 세팅한다.

3 ~ 4의 과정에서 flag[1] == true 가 되었다면, 4번 과정이 끝나자마자 p1이 대기를 끝내고 Critical Section을 사용하게 된다.

Semaphores

1개의 공유자원을 컨트롤하였던 Mutex와는 달리, n개의 공유 자원에 대한 접근을 제한하는 방법이다. Semaphores는 정수 변수 Semaphore S를 통해 구현이 된다. 이러한 Semaphore은 초기화를 할 경우를 제외하면 2개의 표준 Atomic Operation인 wait(), signal()로만 접근이 가능하다.

// S가 1로 초기화 되어있으면, Mutex Lock과 동일하게 사용할 수 있다.
wait(S) {
	while (S <= 0)
    ;	// busy wait
    S--;
}

signal(S) {
	S++;
}

이렇게 구현을 할 경우, busy waiting를 해야된다. busy waiting을 피하기 위해, wait, signal을 아래와 같이 다시 정의할 수 있다.

typedef struct {
	int value;
    struct process *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 P from S->list;
        wakeup(P);
    }
}

value는 공유 자원의 개수이고, list는 프로세스 리스트이다. wait에 들어가서 사용할 수 있는 공유자원이 없다면, list에 process가 들어가고, context-switching이 일어난다. 다른 process가 critical Section 사용을 마치고, signal로 신호를 준다면, list에서 프로세스가 나오고, 다음에 Critical Section을 사용하는 process를 wakeup 하는 과정을 거치게 된다. list에서 어떤 process가 먼저 나오는지 설계하는 것을 통해, 전략적으로 process를 다룰 수도 있다.

Atomic?

싱글코어 환경에서는, 단순히 wait(), signal() 연산들이 실행되는 동안 인터럽트를 금지함으로써 간단하게 해결할 수 있다. 하지만, 멀티코어 환경에서 동일하게 적용을 하려면, 모든 처리 코어에서 인터럽트를 금지하여야만 한다. 모든 코어에서 인터럽트를 금지하는 것은 매우 어려울 수 있고, 또한 매우 큰 overhead가 발생한다. 따라서, SMP 시스템은 atomic operation을 위해 CAS, spinlock과 같은 기법을 사용해야 한다.

Liveness

Liveness는 Process가 시행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 요소를 말한다.
Critical Section을 다루는 Synchronization tools를 사용할 때, 최악의 경우 process가 무기한 대기할 수 있다.( progress, Bounded Waiting 위배) 이는 Liveness의 조건을 위배한 것이라고 볼 수 있다. 이러한 Liveness Failure의 예시 2가지를 알아보자.

Deadlock

Semaphore은 process, thread의 순서를 조정하는 데 사용될 수도 있다. Deadlock은 여러개의 process들이 wait 상태에 들어갔을 경우 생기게 된다.

P0 {
	wait(S);
    wait(Q); // *1
    
    signal(S);
    signal(Q);
}

p1 {
	wait(Q);
    wait(S); // *2
    
    signal(Q);
    signal(S);
}

S, Q의 value의 초기값은 둘다 1이고, P0, P1이 동시에 시작하였다고 가정해보자. 그러면, wait(S), wait(Q)를 동시에 실행하여 둘의 value는 0이 되고, 이후에 1, 2에서 Q, S의 list에 들어가서 대기하게 된다.

Priority Inversion

A < B < C 의 priority를 갖는 process들이 있다고 가정하고, A가 Semaphore S를 갖고있다고 가정하자. C가 S를 필요로 하게 되면, A가 이를 갖고있으므로 block 상태에 들어간다. B는 아직 S를 필요로 하지 않아 task를 진행하고 있는 상태이다. A가 S 사용이 끝났을 때, C가 block에서 풀리기 전에 B가 wait(S)를 실행할 경우, 우선순위가 비교적 낮은 B가 semaphore를 차지하는 일이 발생할 수 있다. 이러한 경우를 priority Inversion이라고 한다.