운영체제(OS)

process synchronization: 상호배제(mutual exclusion)

yoongrammer 2021. 2. 24. 18:55
728x90

목차

    상호 배제(mutual exclusion)


    상호 배제란 둘 이상의 프로세스가 동시에 임계 영역(CS : Critical Section)에 진입하는 것을 방지하기 위해 사용되는 알고리즘입니다.

     

    공유 자원의 동시 사용을 방지하여 race condition과 같은 문제를 피할 수 있습니다.

     

    상호 배제 기본 연산


    • enterCS() primitive (primitive: 기본 연산)
      • Critical section 진입 전 다른 프로세스가 critical section 안에 있는지 검사를 합니다.
      • Critical section에 다른 프로세스가 있다면 비어 있을 때까지 대기를 합니다.
    • exitCS() primitive
      • Critical section을 벗어날 때의 후처리 과정을 합니다.
      • Critical section을 벗어남을 표시하게 됩니다.

    상호 배제 기본 연산을 위한 요구사항


    상호 배제를 구현하기 위해선 아래 세 가지 조건을 만족해야 합니다.

    1. Mutual exclusion (상호 배제)

    • CS에 프로세스가 있으면, 다른 프로세스의 진입을 금지하게 합니다.

    2. Progress (진행)

    • CS안에 프로세스가 없다면 CS에 진입할 수 있어야 합니다.

    3. Bounded waiting (유한한 대기)

    • 프로세스의 CS 진입은 유한 시간 내에 허용되어야 합니다.
    • 계속 기다리는 상황을 만들지 말고 언젠간 들어갈 수 있게 하여 기아상태(starvation)를 방지합니다.
    728x90

    요구사항 위배


    상호 배제를 구현할 때 요구사항을 위배하는 경우를 알아보도록 하겠습니다.

    1. Progress 위배

    위 알고리즘은 turn 값에 따라 CS에 진입할 수 있는 Process가 결정됩니다.

    • turn : 0 = ProcessA 만 CS에 진입 가능
    • turn : 1 = ProcessB 만 CS에 진입 가능

    반드시 A 다음에 B 또는 B 다음에 A 순으로 CS에 진입하도록 설계되어 있습니다.

    한 Process가 두번 연속 CS에 진입할 수 없기 때문에 Progress 위배를 하게 됩니다.

    2. Mutual exclusion 위배

    위 알고리즘은 자신의 flag값을 ture로 변경하여 CS에 진입할 것을 알리고 false로 변경하여 CS에 나왔다는 것을 알림으로써 상호 배제를 구현했습니다.

    하지만 다음과 같은 상황에서 동시에 CS에 진입하게 되어 Mutual exclusion에 위배됩니다.

    1. ProcessA가 while문에서 선점을 당함.
    2. ProcessB가 CS에 진입함.
    3. ProcessA가 while문에서 빠져나와 CS에 진입함.

    3. Bounded waiting 위배

    위 알고리즘은 다음과 같은 상황에서 Bounded waiting을 위배하게 됩니다.

    1. ProcessA가 while문을 진입하기 전에 선점을 당함.
    2. ProcessB가 while문을 수행함.
    3. ProcessA가 while문을 수행함.

    위 상황은 두 프로세스가 무한히 CS에 진입하지 못하게 되어 Bounded waiting에 위배 될 뿐만 아니라

    CS에 진입한 프로세스가 없음에도 불구하고 진입을 하지 못하기 때문에 Progress에도 위배가 됩니다.

     

     

    상호 배제 구현시 선점이 발생하는 위치에 따라 요구조건을 위배하는 경우가 발생할 수 있습니다.

     

    이런 상호배제 요구사항을 만족하는 최초의 알고리즘은 데커(Dekker) 알고리즘이며 이밖에 여러 가지 방법들이 있습니다.

     

     

    참고: https://hpclab.tistory.com/1?category=887083

     

    728x90