운영체제 6 : Process Synchronization and Mutual Exclusion (2)

SW 방식, HW 방식으로 Process Mutual Exclusion을 해결해보자.

 

• Dekker's Algorithm
• Peterson's Algorithm
• Dijkstra's Algorithm

 

• TAS (TestAndSet) instruction

---

 

SW Solutions

1. Dekker's Algorithm

전략

위의 1번 3번 방법을 섞어서 turn과 flag를 모두 사용한다.

 

둘 다 flag를 들고 while문에 들어가면 turn을 살핀다.

 

자신의 turn이 아닌 쪽이 flag를 다시 내리고, turn을 가진 프로세스가 CS에 들어가서 수행한다.

 

프로세스의 수행이 끝나면 turn과 flag를 최신화 하고 기다리던 프로세스가 flag를 들고 CS로 들어간다.

 

 

2. Peterson's Algorithm

전략

Dekker's algorithm과 같은 방법이지만 더 간단하다.

 

flag를 최신화한 후 turn을 바로 최신화하면서 차례를 양보한다.

 

 

3. Dijkstra's Alogirithm

 

최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결하였다.

 

기존에는 true / false 의 flag 값을 가졌다면, 이 알고리즘은 3가지 값을 가진다.

 

flag 값	의미
idle	프로세스가 임계 지역 진입을 시도하고 있지 않을 때
want-in	프로세스가 CS 진입 시도 1단계일 때 (들어가고 싶다고 의사를 밝히는 단계)
in-CS	프로세스가 CS 진입 시도 2단계일 때 (들어가기 직전 혹은 들어가 있을 때)

 

 

전략 - 1단계

flag를 want-in으로 최신화하고, 자신의 턴이 아니라면 기다린다.

 

현재 turn을 가진 프로세스의 flag가 idle이 될 때, turn을 내 차례로 가져온다.

 

만약 다른 프로세스가 turn을 가져가면 다시 기다린다.

 

전략 - 2단계

turn을 가져오게 되면 flag를 in-CS로 최신화한다.

 

in-CS 인 상태가 자신만 있는 지 확인하고, 자신 뿐인 것을 확인하면 CS에 들어갈 수 있다.

 

그렇지 않으면 처음으로 돌아가서 want-in 상태가 된다.

 

운이 없으면 CS가 비어있을 때가 있지만, 언젠가 프로세스가 들어간다.

 

---

 

SW solution의 문제점

- 속도가 느리고 구현이 복잡하여 비효율적이다.

 

- ME primitive 실행 중 preemption 될 수 있

 

- Busy waiting : 기다리느라 바쁘다. 기다리면서 while 연산을 계속 수행한다.

 

---

 

HW Solution

1. TestAndSet (TAS) instruction

: Test와 Set을 한 번에 수행하는 기계어

 

Machine instruction

기계어는 실행 중 interrupt를 받지 않아서 preemption되지 않는다.

 

// target을 검사하고, target 값을 true로 설정
boolean TestAndSet (boolean *target)
{
    boolean temp = *target;     // 이전 값 기록
    *target = true;             // true로 설정
    return temp;                // 값 반환
}

TestAndSet이라는 명령어는 중간에 멈추지 않고 무조건 끝까지 실행된다.

 

target 인자를 받고 true로 바꿔주며, 기존의 target 값을 반환한다.

 

전략

false 값을 가진 lock을 TAS의 인자로 넣으면 TAS는 false를 반환하고, lock은 true 값을 갖게 된다.

 

먼저 온 프로세스가 CS에 들어가 있을 때 lock=True 이기 때문에, 다른 프로세스가 CS에 들어가지 못하고 대기한다.

 

CS 내의 프로세스가 작업을 마치면 lock=false 가 되고, 다음 프로세스가 CS로 들어간다.

 

 

lock이 false일 때 CS에 들어갈 수 있고, 어떤 프로세스가 CS에서 나와서 lock=false를 해야만 다른 프로세스가 들어갈 수 있다.

 

Bounded waiting 조건 위배

- TAS 과정을 통과하지 못해 while문을 돌고 있는 프로세스들은 무작위로 선택되어 CS로 들어간다.

 

- 3개 이상의 프로세스가 있을 때, 운이 좋지 않은 프로세스는 CS로 들어가지 못하고 계속 대기한다.

 

 

2. N-Process mutual exclusion

do                                  // 프로세스 Pi의 진입 영역
{
    waiting[i] = true;
    key = true;

    while (waiting[i] && key)
        key = TestAndSet(&lock);
    waiting[i] = false;
    
    ///////////////////
    //   임계 영역   //
    //   탈출 영역   //
    ///////////////////
    
    j = (i + 1) % n;

    while ((j!=i) && !waiting[j])
        j = (j + 1) % n;            // 대기 중인 프로세스를 찾는다.
    
    if (j = i)                      // 대기 중인 프로세스가 없으면
        lock = false;               // 다른 프로세스의 진입 허용
    else                            // 대기 프로세스가 있으면
        waiting[j] = false;         // 해당 프로세스 Pj가 CS에 진입하도록 허용
}

전략

기다리고 있는 여부를 저장하는 waiting 개념이 추가되었다.

 

CS 전 기다리는 while문을 통과하기 위해서는, 대기 상태 waiting 혹은 TAS 의 결과 key 가 true 가 되어야 한다.

 

CS 를 나온 프로세스는 자신 뒤의 프로세스들 중 대기 중인 프로세스를 찾는다.

 

대기 중이 프로세스가 없으면, lock을 false로 하여 TAS의 결과인 key가 true가 되도록 한다.

 

대기 중이 프로세스가 있으면, 가장 먼저 나오는 프로세스의 waiting을 false로 최신화시킨다.

 

장점

구현이 간단

 

단점

Busy waiting 문제가 해결되지 않아 여전히 비효율적이다.

 

 

 

 

다음 글에서 Busy waiting 문제를 해결하기 위한 OS가 개입하는 기법을 살펴볼 것이다.

---

본 글은 HPC Lab. KOREAHECH YOUTUBE 채널의 김덕수 교수님 강의를 보고 작성되었습니다.

[Course] Operating System (CPA310) - 운영체제 강의