운영체제 스터디 7주차 - Mutex, Semaphore, Monitor, Liveness

저번 주차까지 프로세스(혹은 스레드) 동기화의 해결 방법으로 소프트웨어적으로는 피터슨 알고리즘, 하드웨어적으로는 test-and-set 등으로 atomic variable을 만드는 방법을 보았다. 

https://kyumcoding.tistory.com/102

운영체제 스터디 6주차 - 동기화

 

이번에 알아볼 방법은 조금 더 하이레벨적인 솔루션들에 대해서 알아볼 예정이다. Mutex는 가장 심플한 동기화 툴이고(2개), Semaphore는 3개 이상이고, Monitor는 mutex와 semaphore의 한계를 극복한 툴이고, Liveness는 이전 것들이 상호배제 정도만 해결했다면 이제 데드락까지 해결하는 툴. (Mutex와 Semaphore에 대해서는 이전 Go 관련 포스팅에서 정리한 적이 있다) https://kyumcoding.tistory.com/67

11. Go를 이용한 스크래퍼 리팩토링하기 (7) - Semaphore와 Mutex를 활용한 고루틴(Goroutine) 제어하기

 

 

Mutex Locks

가장 기본적인 구조를 통해 공유 자원에 대한 접근을 제한하는 방법. 크리티컬 섹션에 들어가기 위해 락(Lock)을 획득(acuire)하고, 작업이 끝난다면 회수(release)하는 방식. 이전에 피터슨 알고리즘에서는 복잡하던 방식이 그냥 단순히 열쇠를 획득하고 회수하는 방법으로 좀 더 단순하게 구현. 하지만 이 획득과 회수 과정을 원자적으로 만들어야지, 안 그러면 저 과정 중에 인터럽트(문맥 교환)가 일어나 데이터의 정합성 등이 깨질 수 있음. 이는 compare_and_swap 오퍼레이션 등을 활용하여 구현 가능.

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

release() {
	available = true;
}

 

하지만 위와 같이 뮤텍스를 구현하는 경우 락을 획득하기 전까지 (!available 동안) while문을 돌게 되는데 이는 곧 CPU 자원의 낭비로 이어질 수 있음. 기다리기는 하는데 CPU 자원을 점유하면서 바쁘게 기다리는 것(busy waiting). 다른 프로세스를 실행할 수 있는데 사용할 수 있는 CPU 자원을 크리티컬 섹션 진입을 위해 대기하는데 사용하는 비효율성이 있을 수 있음.

 

Spinlock 하지만 멀티프로그래밍 환경에서 이런 공회전하는 것(영어로는 spinlock이라고 부름). CPU 자원을 점유하고 while문을 도는 spinlock은 꼭 부정적인 것은 아님. 싱글 코어에서는 다른 프로세스의 진입을 막아 비효율성을 초래하지만, 코어가 널널한 상태에서는 오히려 바로바로 문맥교환을 가능하게 하여 문맥 교환 비용을 줄이는데 일조하기도 함. 왜냐하면 wait queue에서 대기하는 프로세스에게 CPU 점유를 넘겨주려면 다시 ready queue로 넘겨야 하고 그 다음에 CPU 점유가 가능해지지만, busy waiting을 하고 있는 spinlock의 경우 바로 문맥 교환이 가능함.

 

 

Semaphore

mutex가 2개에 대한 이야기라면, semaphore는 n개에 대한 이야기임. 열쇠를 n개 발행해서 열쇠를 획득해야지만 크리티컬 섹션에 들어갈 수 있고, 만약 열쇠가 모두 다 누군가 가져갔다면 작업을 마친 프로세스가 열쇠를 하나 반납할 때까지 기다려야 함.

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

signal(S) {
	S++;
}

// Integer값인 S를 통해서 작업 하나 실행될 때 s—, 열쇠 반환하면 s++
// s를 1로 초기화하면 뮤텍스랑 똑같아지는 것

 

사용방법은 1) 원하는 열쇠 갯수대로 리소스를 초기화하고 → 열쇠 획득하게 하려면 wait(), 리소스 반환할 때는 signal()을 호출하게 함 → 만약 획득 가능한 열쇠가 0이라면 다른 프로세스는 기다려야 함.

 

semaphore 또한 busy waiting 문제가 있을 수밖에 없음. 이는 열쇠가 모두 소진되어 대기하고 있는 프로세스에게 우선 wait queue로 스스로 가게끔 한 다음에, 열쇠가 회수 되어 다른 프로세스가 크리티컬 섹션에 진입할 수 있을 때 그 때 ready queue로 다시 돌아오게 만들면 됨.

 

물론 세마포어를 쓰는게 쉽지 않음. 타이밍 에러(timing error)가 나타나는데, 어떤 특정 실행 시퀀스에서 일어나게 되면 언제나 일어나는 것도 아니고 잡기도 어려움. (wait() → signal() 순서대로 실행해야 하는데 프로그램이 복잡해지면 그 순서가 바뀌거나, wait() → wait() 하거나 signal() → signal()하는 경우가 있을 수 있음. (프로그래머가 직접 세마포어를 구현하는 것을 기본 전제로 하는 듯함?))

 

 

Monitors

위와 같은 타이밍 에러 상황은 결국 사람에 의해서 발생할 수 있는 것이므로, 가장 좋은 것은 애초에 그런 일이 벌어지지 않도록 도구 자체를 개선하는 방법이 있음. 그 도구가 바로 모니터(Monitor). 모니터는 abstact data type인데, 상호배제를 프로그래머가 구현해서 사용해야 하는 타입. 모니터를 선언하고 그 안에 있는 함수들은 mutual exclusive 한 것이라고 생각하고 구현하게 하는 것.

condition variable을 통해서 모니터 안에서 각각 변수에 대응되는 것들의 상태를 조절할 수 있음. 예를 들어 condition variable x, y가 있다면 각 x와 y에 대응되는 것들의 wait과 signal을 호출하여 별도로 관리 가능.

 

monitor monitorName
{
	/* shared variable declaration */
    function P1 (...) {
    }
    function P2 (...) {
    }
    
    function Pn (...) {
    }
    initialization_code (...) {
    }
}


// Using Condition varaibles

condition x, y;
x.wait();
x.signal();

 

 

 

 

 

Java에서의 Monitor 자바에서는 모니터 비슷한 자료 구조로 스레드 동기화를 해결하고 있음. 이를 모니터-락 혹은 본질적인-락이라고 부른다. 자바에서는 synchronized 키워드를 활용하여 임계영역을 설정하고, wait()과 notify() 메서드를 통해 락을 획득, 회수 한다. synchronized 키워드을 통해 임계영역을 설정할 수 있다. 해당 키워드로 클래스를 만들 수도 있고, 메서드만 만들 수도 있다. 이 키워드를 사용한 공간은 임계영역을 가진 객체 인스턴스가 된다. 메서드 코드 블럭을 이용하게 되면 모니터 락을 가진 객체 인스턴스는 this 객체 인스턴스이다. wait()과 notify()는 java.lang.Object 클래스에서 선언되기 때문에 모든 자바 객체가 가진 메서드이고, wait()를 호출하면 해당 객체의 모니터락을 획득하기 위해 대기상태가 되고 notify(), notifyAll()메서드를 호출하면 해당 객체 모니터에 대기 중인 쓰레드들을 깨울 수 있다. synchronized (object) { // critical section } public synchronized void add() { // critical section }​

 

 

Liveness

지금까지 배웠던 해결책들은 프로그레스와 bounded waiting을 해결해주지 못함. 하지만 liveness는 이를 해결 가능함. 하지만 두 가지 상황에서 liveness가 실패할 수 있는데 그것은 deadlock과 priority inversion. 

 

지금까지 배웠던 해결책들은 프로그레스와 bounded waiting(어떤 프로세스 하나가 임계영역에 진입하고 싶지만 다른 프로세스들이 계속 들어갔다 나오는 바람에 계속 대기하고 있는 상황 → starvation 문제가 발생할 수도 있음)을 해결해주지 못함. 하지만 liveness는 이를 해결 가능함. 하지만 두 가지 상황에서 liveness가 실패할 수 있는데 그것은 deadlock과 priority inversion.

 

데드락은 서로 다른 프로세스가 서로를 기다리느라 아무것도 하지 못하는 상태.

 

priority inversion은 높은 우선순위 프로세스가 읽거나 수정하고자 하는 커널 데이터를 낮은 우선순위를 지닌 프로세스가 점유하고 있어서 사용하지 못하는 경우에 발생. 특히 각자 다른 우선순위를 가진 3가지 프로세스가 있는 경우 발생할 수 있는데, 이때는 낮은 우선순위 프로세스에 잠시 높은 우선순위를 부여해주는 priority-inheritence 방법을 통해 해결할 수 있다.