[운영체제] Semaphore와 deadlock, starvation

+ 운영체제를 공부중이고, 오늘은 Semaphore와 deadlock, starvation에 대해서 공부하였는데...ㅠ 해당 내용에 대해서는 깊은 이해가 아직 부족합니다. 앞으로 계속 보충하여 해당 포스트를 수정해 나갈 것입니다.

 

[운영체제] Thread 여기서 thread의 동기화 이슈를 살펴보았다. 

다시 한번 정리해보면, 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다. 

 

이를 해결하기 위한 몇가지 충족 조건

1) Mutual Exclusion

이를 해결하기 위해서는 Mutual exclusion(상호 배제)기법이 필요하다. 스레드는 프로세스의 모든 데이터에 접근 할 수 있으므로 여러 스레드가 변경하는 공통으로 사용하는 변수에 대해서 Exclusive Access를 통해 어느 한 스레드가 해당 변수를 갱신하는 동안 다른 스레드가 동시 접근하지 못하도록 막는 것이 필요하다. 

 

이를 코드로 보면 

2) Progress

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다. 

3) Bounded Waiting

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용되리 때까지 다른 프로세스들이 critical setion에 들어가는 횟수에 제한이 있어야 한다. (즉, 무한히 기다려야하는게 아니라 기다림의 끝이 있어야 한다. )

 

Semaphore

- S: 세마포어 값으로, 초기 값만큼 여러 프로세스가 동시 critical section 접근 가능

- P(S) : critical section에 들어갈 때 검사. S값이 1이상이면, critical section 진입 후, S값에서 1빼기 (S값이 0이면 대기)

- V(S): critical section에서 나올 때 S값에서 1을 더하고 나온다. 

즉, 아래의 두가지 atomic 연산에 의해서만 접근 가능

P(S): wait(S) {
               while S <= 0 //대기
    		;
   		S--; //다른 프로세스 접근 제한
   	}

V(S): signal(S) {
			S++; //다른 프로세스 접근 허용
   	}

그런데 위의 코드를 보면 while S <= 0 이라는 loop가 CPU에서 실행되고 있다. 즉, 기다리는 동안에도 CPU가 계속 쓰이긴 해야하므로 CPU에 부하가 속 되고 있다. 이러한 busy-wait 방법은 효율적이지 않다. 

그래서 semaphore를 Block & Wakeup 방식으로 구현한다. 

 

Block과 wakeup은 다음과 같이 가정한다. 

- Block: 커널은 block을 호출한 프로세스를 suspend 시킨다. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다. (S가 음수일 경우 busy-wait 대신 대기큐에 넣는다.)

- wakeup(P):  block된 프로세스 P를 wakeup시킨다. 그리고 이 프로세스의 PCB를 ready queue로 옮긴다. 

P(S): wait(S) {
               S.value--;
               if(S.value < 0){
               	add this process to S -> queue
               	block()
               }
   	}

V(S): signal(S) {
            S.value++; //다른 프로세스 접근 허용
            if(S.value <=0){
            	//내가 자원을 내놓았음에도 불구하고 자원값이 음수라는건, 이 자원을 기다리ㅣ며 누군가가 잠들어있다는 의미이다. (양수라면 이미 쓰고있었을테니까)
                remove a process P from queue
                wakeup(P)
           }
   	}

 

Deadlock & Starvation

critical section을 설정하고, 이 영역에 하나 또는 특정 개수의 스레드, 프로세스만 접근 할 수 있기 때문에 나머지는 기다리고 있는데, 이 때 발생 할 수 있는 문제가 Deadlock 과 Starvation이다. 

Deadlock은 여러 프로세스가 동일 자원 점유를 요청할 때 발생하고, 

Starvation은 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때, 특정 프로세스는 영원히 자원 할당이 안되는 경우를 주로 의미한다.

1) Deadlock

무한 대기 상태. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에, 다음 단계로 진행하지 못하는 상태

 

다음 네 가지 조건이 모두 성립될 때 데드락이 발생할 가능성이 있다 

- Mutual exclusion(상호 배제): 매 순간 하나의 프로세스만이 독점적으로 자원을 사용할 수 있다. 

- No Preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다. 

- Hold and wait(점유 대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.

- Circular wait(순환 대기): 자원을 기다리는 프로세스간에 사이클이 형성되어야 한다. 예를 들어, 프로세스 P0, P1, ...Pn이 있을 때

P0은 P1이 가진 자원을 기다림

P1은 P2이 가진 자원을 기다림

...

Pn-1은 Pn이 가진 자원을 기다림

Pn은 P0이 가진 자원을 기다림

Deadlock 해결 방법

1. deadlock 예방 (deadlock prevention)

위의 4가지 조건 중 하나를 제거하는 방법

- Mutual exclusion(상호 배제) 조건의 제거: critical section 제거

- No Preemption(비선점) 조건의 제거: 선점 가능 기법을 만들어줌

- Hold and wait(점유 대기) 조건의 제거: 한 번에 모든 필요 자원 점유 및 해제

- Circular wait(순환 대기) 조건의 제거: 자원 유형에 따라 순서를 매김

2. deadlock 회피 (deadlock avoidance)

자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당하는 것

가장 단순하고 일반적인 모델은 프로세스들이 필요로하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다. 

safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence: 프로세스의 sequence P0, P1, ...Pn이 safeㅎ하려면 P0, P1, ...Pn의 자원 요청이 "가용 자원 + P0, P1, ...Pn의 보유자원"에 의해 충족이 되어야 하고,이때만 자원을 허용하는 것이다.

이러한 조건을 만족하면 다음의 방법으로 모든 프로세스 P의 수행을 보장한다. 

- Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (i < j)가 종료될 때까지 기다린다. 

- Pi-1이 종료되면 Pi의 자원요청을 만족시켜서 수행한다. 

 

2) Starvation

특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

Starvation 해결 방법

우선순위 변경

- 프로세스 우선순위를 수시로 변경해서, 각 프로세스가 높은 우선순위를 가질 기회주기

- 오래 기다린 프로세스의 우선순위를 높여주기

- 우선순위가 아닌, 요청 순서대로 처리하는 FIFO 기반의 요청큐 사용

 

 

 

 

 

 

 

reference

[운영체제 Atomic방법] test_and_set, Compare_and_Swap, Bounded-waiting

[운영체제] 세마포어(semaphore) 완전 쉬운 이해! wait(), signal(), 이진, 계수형