[OS] 프로세스 동기화와 상호배제 (Process Synchronization and Mutual Exclusion) - ①

SW + HW Solutions

Process Synchronization(동기화)

여러 개의 프로세스들이 존재하는 다중 프로그래밍 시스템에서 프로세스들은 서로 독립적으로 동작합니다. 공유 자원 혹은 데이터가 있을 때, 각각의 독립된 프로세스가 그 자원에 동시에 접근한다면?

다시 말해서 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있습니다!

이를 막기 위해 동기화가 필요한데, 동기화는 다음과 같이 정리할 수 있습니다.

• 프로세스들이 서로 동작을 맞추는 것
• 프로세스들이 서로 정보를 공유하는 것

Mutual Exclusion(상호 배제)

Mutual Exclusion(상호 배제)

상호배제란 둘 이상의 프로세스가 동시에 임계 영역에 진입하는 것을 막는 것을 의미합니다.

이러한 상호배제를 위해서 고려해야 할 3가지 기초 요소가 존재합니다.

• Mutual Exclusion(상호 배제) : 임계 영역에 프로세스가 있으면, 다른 프로세스의 진입을 금지
• Progress(진행) : 임게 영역에 있는 프로세스 외에는 다른 프로세스가 임계 영역에 진입하는 것을 방해 하면 안됨
• Bounded Waiting(한정 대기) : 프로세스의 임계 영역 진입은 유한한 시간 내에 허용되어야 함

Mutual Exclusion Solutions

Two Process Mutual Exclusion

Two Process ME Version 1

최초의 turn이 0번이라고 하고, 0번 프로세스가 임계 영역에 접근하기 전에 죽었다고 가정해봅시다.

이때 임계 영역이 비어있음에도 불구하고 1번 프로세스는 while(turn = 0) do endwhile; 조건 때문에 임계 영역에 접근할 수 없습니다. 이는 Progress 조건을 위배합니다.

또한 다음과 같은 케이스도 생각할 수 있습니다.

0번 프로세스가 임계 영역에서 작업을 마무리하고 1번에게 turn을 넘깁니다. 이때 1번은 아직 임계 영역에 진입할 준비가 안되었고, 0번은 벌써 방금 작업을 마치고 돌아와 임계 영역에 들어갈 준비를 끝냈습니다. 그러나 while(turn = 1) do endwhile; 조건 때문에 두번 연속으로 임계 영역에 접근할 수 없습니다. 역시 Progress 조건을 위배합니다.

 

Two Process ME Version 2

이러한 version1의 문제점을 보완하기 위해서 flag를 도입합니다. 여기서 flag는 임계 영역에 들어가려면 깃발을 들고, 나왔으면 깃발을 내리겠다는 의미입니다. 그러나 이 전략도 문제점이 존재합니다.

0번이 임계 영역에 들어가기 전에, 해당 위치에 Preemption이 발생했다고 가정해봅시다. 1번이 0번의 깃발이 내려가있는 것을 확인하고, 자신의 깃발을 올린 후, 임계 영역으로 진입해 자신의 작업을 진행합니다.

작업 도중에, 다시 0번이 CPU를 할당받아 자신의 깃발을 오리고 임계 영역에 진입합니다. 이렇게 되면 임계 영역에 두 개의 프로세스가 접근했으므로 Mutual Exclusion 조건을 위배합니다.

 

Two Process ME Version 3

version2에서 좀 더 보완하여, 깃발을 맨 처음에 올리는 방법을 내새웁니다. 안타깝게도 역시나 문제점이 존재합니다.

0번이 들어가기 위해 깃발을 올린 후, Preemption이 발생했다고 가정합시다. 그 사이에 1번도 임계 영역에 들어가기 위해 깃발을 올리고 들어가려했더니, while(flag[0]) do endwhile; 이라는 조건 때문에 1번은 계속 대기 하게 됩니다.

0번이 다시 CPU를 할당받고 임계 영역에 진입하려고 해도 마찬가지로 while(flag[1]) do endwhile; 조건 때문에 계속 대기 하게 됩니다. 이는 Progress와 Bounded Waiting 조건을 위배합니다.

SW Solutions - Dekker's Algorithm(데커 알고리즘)

Dekker's Algorithm(데커 알고리즘)

위의 Two Process Mutual Exclusion 문제점을 최초로 해결한 방법입니다. turn과 flag를 따로 두었던 기존의 방법과 다르게 이를 같이 사용하여 version 1, 2, 3에서 발생했던 문제점들을 보완하는데 성공한 방법입니다.

 

Peterson's Algorithm(피터슨 알고리즘)

SW Solutions - Dijsktra's Algorithm(다익스트라 알고리즘)

프로세스 최초로 n개의 상호배제 문제를 소프트웨어적으로 해결한 방법입니다.

실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 세마포 방법이며, 가장 짧은 평균 대기시간을 제공합니다.

다익스트라 알고리즘에서도 flag를 사용하는데, 위에서는 다르게 flag 변수가 3개로 정의가 됩니다.

• idle : 프로세스가 임계 영역에 진입을 시도하고 있지 않을 때
• want-in : 프로세스가 임계 영역에 진입 시도 1단계일 때
• in-CS : 프로세스가 임계 영역 진입 시도 2단계 및 임계 영역 내에 있을 때

Dijsktra's Algorithm(다익스트라 알고리즘)

먼저 flag[i] ← want-in을 통해 임계 영역에 진입하고 싶다고 의사를 밝히며 깃발을 올립니다.

while(turn ≠ i) 현재 나의 turn이 아니라면 flag[turn] 현재 turn인 프로세스가 idle이 될때까지 기다리고, 작업이 끝나면 i(나)에게 turn을 넘깁니다. 이렇게 해서 진입 시도 1차가 끝납니다.

(이때 turn을 넘겨 받았는데, 2단계로 넘어가기 전에 다른 프로세스에게 turn을 뺏기면 다시 1단계를 돌면서 대기하게 됩니다.)

1단계를 통해 어느정도 프로세스가 걸러지고 난 후, 2단계에 진입하면 flag ← in-CS를 통해 현재 2단계에 진입했음을 알리기 위해 깃발을 올립니다. 그리고 반복문이 진행되는데, j < n(프로세스의 번호) 이면서 j = i(현재 자신의 번호)거나 flag[j] ≠ in-CS(in-CS 영역에 다른 프로세스가 존재하지 않음) 라면 j의 값을 계속 증가시킵니다.

이를 만족하지 않으면 j < n 이므로 repeat ~ until(j ≥ n); 조건에 의해 다시 처음으로 돌아갑니다. 만약 while문의 조건을 만족하여 루프가 끝나면, j는 n이 되어 임계 영역에 들어갈 수 있게 됩니다.

SW Solutions 문제점

• 속도가 느림
• 구현이 복잡함
• ME primitive 실행 중 preemption 될 수 있음
• Busy Waiting(Inefficient)

HW Solutions - TAS(Test And Set)

SW Solution의 문제점들을 HW적으로 도움을 주기 위해 탄생한 HW Solution으로 Test와 Set을 한 번에 수행하는 기계어 입니다.

 

bool TestAndSet(bool *target) {
    bool temp = *target; // 이전 값 기록
    *target = true; // true로 설정
    return temp; // 값 반환
}

// 한번에 수행된다. (Machine Instruction)

 

TAS(Test And Set)

그러나 3개 이상의 프로세스인 경우 Bounded Waiting 조건을 위배하게 됩니다.

 

do { // 프로세스 i 진입 영역
    waiting[i] = true;
    key[i] = true;
    while(waiting[i] && key[i]) 
            key[i] = TestAndSet(&lock); 
    waiting[i] = false;

    // 임계 영역
    j = (i + 1) % n;
    while(j != i && !waiting[j]) // i뒤에 대기중인 프로세스를 찾음 
            j = (j + 1) % n;
    if(j == i) // 대기중인 프로세스가 없으면 
            lock = false; // 다른 프로세스의 진입 허용 (lock은 공유 변수)
    else // 대기 프로세스가 있으면
            waiting[j] = false; // 프로세스 j가 임계 영역에 진입할 수 있도록 대기를 풀어줌
} while(true);

HW Solutions 문제점

• Busy Waiting(Inefficient) → 대부분의 OS들이 사용하는 기법인 Semaphore를 통해 이를 해결