[OS] Process Synchronization - 2

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

 

이번 시간에 배웠던 세마포어는 추상 자료형(ADT)이다, Java로 생각하면 interface 정도가 될것 같다.

즉, 구현 세부사항이 아닌, 인터페이스를 생각하면 된다.

 

1. 세마포어 (Semaphore)

우선 세마포어 변수 S에 대하여 알아보자!

Integer variable : S를 사용함.

 

쉽게 생각하면 사용 가능한 자원의 수 라고 생각하면 된다.

 

세마포어 연산은 아래의 두 가지 atomic 연산에 의해서만 접근이 가능

▶ P(S): 공유 데이터를 획득하는 과정 (lock)으로 S가 양수이어야 한다.

// P(S)
while (S <= 0) do no-op; // ex) wait.
S--;

 

▶ V(S): 공유 데이터를 사용하고 반납하는 과정 (unlock)

// V(S)
S++;

 

1 - 1) n개의 프로세스가 임계 구역에 들어가려는 경우

▶ Synchronization variable

semaphore mutex;

 

위 세마포어 변수 값만큼 여러 개의 프로세스가 임계 구역에 접근할 수 있다.

이번 예제에서는 semaphore 변수의 값이 1이라고 가정한다. (1개의 프로세스만 임계 구역 접근 가능)

즉, mutex lock과 유사하다.

 

▶ Process Pi

do {
    P(mutex); // mutex의 값이 양수면 임계 구역 접근하고 mutex값을 1 감소시키고, 아니면 기다린다.
    critical section
    V(mutex); // mutex의 값을 1 증가한다.
    remainder section
} while (1);

 

P(mutex) 연산 수행 시, mutex의 값이 양수가 아니면 계속 기다려야 하는데, 프로세스의 CPU 할당 시간이 끝날 때까지 무의미하게 CPU를 낭비하는데, 이러한 현상을 busy-wait 또는 spin lock 이라고 부른다.

 

이러한 단점을 보완하기 위해 Block & Wake-up 혹은 Sleep lock 이라고 부르는 기법이 생겨났다.

 

1 - 2) Block / Wake-up (Sleep Lock) 방식

▶ 세마포어는 다음과 같이 정의

typedef struct {
    int value; // 세마포어 변수
    struct process *L; // 프로세스 Wait Queue
} semaphore;

이를 그림으로 확인하면 다음과 같다.

값 하나와, 대기중인 PCB들은 연결리스트 형태로 가지고 있다.

 

▶ block과 wake-up을 다음과 같이 가정

• block
  • 커널은 block을 호출한 프로세스를 suspend하고, 이 프로세스의 PCB를 세마포어에 대한 Wait Queue에 넣음.
• wakeup(P)
  • block된 프로세스 P를 wake up하고, 이 프로세스의 PCB를 Ready Queue로 옮김.

 

▶ 세마포어 연산은 다음과 같이 정의

P(S):

세마포어 변수 S를 무조건 1 줄이고, 그 변수의 값이 음수면 해당 프로세스를 Wait Queue로 보낸 후 Block 상태로 만든다.

// P(S)
S.value--;
if (S.value < 0)
{
    add this process to S.L;
    block();
}

 

S.value < 0 이라는 의미는, 이미 자원을 누군가 다 가져가서 사용중이라는 뜻이다.

따라서 해당 Process를 S.L에 추가시켜 준다.

 

V(S):

세마포어 변수 S를 무조건 1 늘리고, 그 변수의 값이 0보다 작거나 같으면 이미 기다리고 있는 프로세스가 있다는 뜻이다.

즉, 위에서 준비된 자원 수 보다 더많이 value-- 연산이 수행되어, 대기중인 process들이 있다는 것 이다.

 

누 군가 깨워야 할 대상이 있는지? 를 확인 하기 위해서 사용하는 value이다.

 

따라서 프로세스 P를 Wait Queue에서 꺼내서 Ready Queue로 보낸다.

세마포어 변수 S 값이 양수면 아무나 임계 구역에 들어 갈 수 있으므로 별다른 추가 연산을 하지 않는다.

V 연산은 특정 프로세스가 공유 데이터를 반납한 후 임계 구역에서 나가는 연산임을 기억해야 한다.

// V(S)
S.value++;
if (S.value <= 0)
{
    remove a process P from S.L;
    wakeup(P);
}

 

1 - 3) Busy wait vs Block Wake-up

일반적으로 Block Wake-up 기법이 좋음.

임계 구역의 길이가 긴 경우 Block/Wake-up 기법이 적합함.

임계 구역의 길이가 매우 짧은 경우 Block/Wake-up 기법의 오버헤드가 Busy-wait 기법의 오버헤드보다 크므로 Busy Wait 기법이 적합할 수 있음. Block/Wake-up도 Ready에서 Blocked 상태로 바꾸려면 overhead가 있다.

 

1 - 4) 세마포어의 종류

계수 세마포어 (Counting Semaphore)

도메인이 0 이상인 임의의 정수 값

여러 개의 공유 자원을 상호 배제함.

주로 resource counting에 사용됨.

 

이진 세마포어 (Binary Semaphore)

0 또는 1 값만 가질 수 있음.

한 개의 공유 자원을 상호 배제함.

mutex와 유사함. (완전히 같지는 않음.)

 

2. Deadlock과 Starvation

2 - 1) Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

 

2 - 2) Deadlock 예시

S와 Q가 1로 초기화된 세마포어라 하자.

 

P0가 CPU를 얻어서 P(S) 연산까지 수행하여 S 자원을 얻었다고 가정해 보자.

 

그런데 여기서 P0의 CPU 할당 시간이 끝나 Context Switch가 발생하여 P1에게 CPU 제어권이 넘어갔다.

P1은 P(Q) 연산을 수행하여 Q 자원을 얻었으나 또 다시 CPU 할당 시간이 끝나 Context Switch가 발생하여 P0에게 CPU 제어권이 넘어갔다.

 

P0은 P(Q) 연산을 통해 Q 자원을 얻고 싶지만, 이미 Q 자원은 P1이 갖고 있는 상태이므로 Q 자원을 가져올 수가 없다.

마찬가지로 P1도 P(S) 연산을 통해 S 자원을 얻고 싶지만, 이미 S 자원은 P0이 갖고 있는 상태이므로 S 자원을 가져올 수 없다.

 

이렇게 P0와 P1은 영원히 서로의 자원을 가져올 수 없고, 이러한 상황을 Deadlock이라고 한다.

 

2 - 3) Deadlock 해결 방안

우선 위에서 설명한 예시 같은 경우, 둘다 P(S)연산을 먼저 수행하면 된다.

그럼 P0가 P(s)를 수행해 s를 얻은 상황에서 Context Switch가 발생하여 P1에게 CPU 제어권이 넘어갔다면, P1은 s를 획득할수 조차 없다.

 

자원의 획득 순서를 정해주어 해결하는 방법이다!

S를 획득해야만 Q를 획득할 수 있게끔 순서를 정해주면 프로세스 A가 S를 획득했을 때 프로세스 B가 Q를 획득할 일이 없다.

 

2 - 4) Starvation (기아)

indefinite blocking

프로세스가 자원을 얻지 못하고 무한히 기다리는 현상이다.

 

2 - 5) Deadlock vs Starvation

언뜻 보기에 둘 다 자원을 가져오지 못하고 무한히 기다리니까 같은 단어라고 혼동할 수 있다.

 

Deadlock은 P0 프로세스가 A 자원을 보유하고 있고, P1 프로세스가 B 자원을 보유하고 있을 때 서로의 자원을 요구하여 무한히 기다리는 현상이다.

 

반면 Starvation은 프로세스가 자원 자체를 얻지 못하고 무한히 기다리는 현상이다.

Starvation은 기아라는 단어에 맞게 어떤 프로세스가 자원이 없어서 굶어 죽는다(?)고 생각하면 이해하기 편하다.

 

출처

https://core.ewha.ac.kr/publicview/C0101020140404151340260748?vmode=f 

반효경 [운영체제] 13. Process Synchronization 2

https://steady-coding.tistory.com/538

[반효경 운영체제] Process Synchronization 2