임계 구역 문제 솔루션: OS, Language supported SW solution

이전 시간에 동기화 문제 해결을 위한 피터슨 알고리즘에 대해서 알아보았다. 좋은 알고리즘이지만, 너무 복잡했다.

또한 Peterson's algorithm과 같은 software적인 해결책은 SMP (Symmetric Multiprocessor System) 환경과 같은 modern computer system에서는 제대로 작동할 수 있다는 보장이 없다. 그 해결책으로 하드웨어적인 instruction이나 mutex, semaphore와 같은 소프트웨어적인 API를 사용하여 프로세스 간 동기화를 보장하는 방법을 사용한다.

이번 시간에는 Critical Section Problem 해결을 위한 좀 더 higher-level의 software tool에 대해서 알아보겠다.

OS supported SW solution

• Mutex Locks: 동기화를 위한 가장 간단한 도구 
• Semaphore: 여러 프로세스, 자원일 경우에도 적용 가능한 강력한 도구 (n개)

Language-Level SW solution

• Monitor: 뮤텍스, 세마포어의 단점 극복

Liveness: Mutual exclusion 뿐 아니라 Progress, bounded waiting까지 보장

---

Mutex Lock

mutex: mutual exclusion

임계 구역을 보호하고 경쟁 상황을 피하기 위해, 진입 시 lock을 걸고 나올 때 lock 해제.

2개의 프로세스 사이의 1개의 공유 자원일 때 적용 가능. (확장도 가능하긴 하다)

acquire() and release() API 제공.

enter-section과 exit-section이 간단해졌다

compare_and_swap 등을 활용해서 atomically 실행됨을 보장해야 한다.

C의 mutex는 lock, unlock 메소드 제공

 

Busy waiting

acquire()을 보면 무한 루프를 돌며 잠금 해제를 기다리고 있다.

이러한 바쁜 대기는 CPU를 의미없이 사용하기 때문에 다른 프로세스가 생산적인 작업을 할 시간을 뺐는다.

 

Spinlock

그런데 이런 바쁜 대기를 하는 mutex lock을 spinlock(공회전)이라고도 한다.

이는 오히려, core가 여유 있는 상황에선 이점을 가지기도 한다.

임계영역에 진입가능하게 됐을 때, spinlock일 경우 바로 임계구역에 진입할 수 있다.

(spinlock이 아닐 경우 waiting queue에서 ready queue로 갔다가 다시 cpu로 context switching되어야 한다)

 

 

---

Semaphore

semaphore: 신호장치. 신호기.(access해도 된다/안 된다)

공유 자원과 프로세스가 여러개 일 때도 사용할 수 있는 동기화 도구

현재 access할 수 있는 자원의 갯수를 표시해 놓고 그만큼만 진입을 허용한다.

2가지 atomic operations을 제공: wait() and signal() //or P() and V()

 

wait() and signal() operations must be executed atomically

• Semaphore(n): 전역 변수 RS를 n으로 초기화. (RS = 현재 사용 가능한 자원의 수)
• wait(), P(): 잠금을 수행하는 코드. 가용 자원을 줄여 진입 or 대기
• signal(), V(): 잠금 해제

Binary and Counting Semaphores

Binary Semaphore: 자원이 1개일 때, 0,1로 표현됨 ▷ mutex lock과 비슷하게 동작.

Counting Semaphore: 자원이 n개일 때.

 

Semaphore를 활용한 동기화 문제 해결 예제

예1)

공유 데이터 sum 1개로 세마포어 변수 초기화, entry 시 wait exit 시 signal

 

예2)

잘못된 사용으로 상호 배제 위반. 공유 데이터 sum이 1개이므로 RS 초기화를 1로 했어야 했다.

예3)

- 프로세스 P1, P2가 concurrently 실행 중이고, P1의 statement S1 후에 P2의 statement S2가 실행되어야 하는 상황.

- 동기화를 위한 변수 synch를 0으로 두고 시작한다.

signal을 먼저 사용하고 wait

P2가 먼저 실행되더라도 wait(0)로 인해 대기하게 되고 P1의 S1이 실행된 후 signal을 호출해야 S2로 진입 가능.

 

 

Semaphore 구현

바쁜 대기를 하지 않도록 wait(), signal()을 구현할 수 있다.

waiting queue에 대기시키고, 공유 자원을 사용 가능하게 된다면 ready queue로 옮긴다.

busy waiting 대신, wait()시 waiting queue에 넣고 signal()시 ready queue로 보낸다

typedef struct{
	int RS;
	struct process *waiting_list;
}semaphore;

wait(semaphore *S){
	S->RS--;
	if (S->RS <0){
		add this process to S->waiting_list;
		sleep(); //wait 상태로
	}
}
    
signal(semaphore *S){
	S->RS++;
	if (S->RS <=0){
		remove a process P from S->waiting_list;
		wakeup(P); //ready 상태로
	}
}

 

---

Monitor

semaphore 사용 시, 공유 자원의 갯수를 잘못 설정한다거나, wait, signal 순서 변경 및 누락이 발생할 수 있다.

이러한 문제를 해결하기 위한 좀 더 추상화된, 고수준의 도구가 Monitor이다.

예를 들어 자바에서는 모니터락을 지원하므로 synchronized 키워드로 간단하게 임계구역을 지정할 수 있다.

condition variable을 이용하여 모니터 ADT를 직접 구현할 수도 있다.

 

Monitor는 모니터 내부에서는 항상 하나의 프로세스만이 활성화되도록 보장해 주므로, 프로그래머가 동기화 제약 조건을 명시적으로 프로그래밍해야 할 필요가 없다는 장점이 있다

 

모니터는 공유 데이터와 임계 영역의 집합

- 모니터 내에는 항상 하나의 프로세스만 진입 가능하다(상호 배제)

- 모니터 내부의 자원(변수)에 접근하고자 하는 프로세스는 반드시 모니터 내부의 함수를 호출해야 한다(정보 은폐)

  세마포어 같은 프로세스 자원 분배를 담당하는 변수가 모니터 내에 있고, 이 변수는 모니터 내에서만 접근 할 수 있다. 

- 프로세스는 직접 wait()나 signal()을 사용하지 않고 모니터에 작업을 요청한다

  모니터 내부의 함수를 사용하는 프로세스는 상호배제(mutual exclusion)가 보장된다.

  요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리한다.

  자원이 필요한 프로세스는 모니터에 접근하여 보류될지 작업을 수행할지 결정된다.

모니터에 선언된 메소드들은 모니터 안의 변수를 동기화

구조

• 세마포어 같은 프로세스 자원 분배를 담당하는 변수
• entry queue: 모니터 내의 procedure 수만큼 존재
• condition quque: 대기실
• signaler queue: signal() 명령을 실행한 프로세스가 임시 대기

조건 변수: 각각의 변수에 대해서 동기화되도록

x, y 전체를 모니터링 하는게 아니라 필요에 따라 x에만 lock을 걸고, y에만 lock이 필요한 영역이 있을 수 있다.

모니터는 내부에 프로세스의 상호 배제 조건을 가르키는 조건 변수를 제공한다.

모니터의 조건 변수는 wait(), signal() 연산을 제공한다.

condition x, y;
x.wait(); //x에만 lock을 건다
x.signal();

각각의 변수에 대해서만 초기화되고 동기화된다.

 

 

 

---

 

 

참고 자료 & 이미지 출처
운영체제 공룡책 강의 (주니온 님)
Operating System Concepts, 10th Ed (Silberschatz et al)
쉽게 배우는 운영체제 (조성호 님)
https://www.youtube.com/watch?v=AnYN-kbCbRI