상호배재 알고리즘 알아보기(Dekker, Lamport, Peterson, Semaphore)
상호배재기법이란?
컴퓨터 과학 분야에서 상호배재는 주로 공유 자원에 대한 동시 접근을 효과적으로 제어하기 위한 알고리즘과 개념을 말합니다. 따라서 Dekker Algorithm, Lamport Algorithm, Peterson Algorithm과 같은 알고리즘은 상호배재의 예시로 볼 수 있습니다. 이러한 알고리즘들은 병렬 처리 환경에서 공유 자원에 대한 경쟁 조건을 방지하고 상호 배제를 실현하는데 사용됩니다.
Semaphore
- 목적: 공유 자원에 대한 동시 접근을 제어하고 상호배재를 구현하기 위한 동기화 기법 중 하나입니다.
- 특징: 세마포어는 정수 변수로, 두 가지 주요 연산인 P(S)와 V(S)를 통해 조작됩니다.
- P(S) 연산 (Wait 또는 Down): 세마포어 값을 감소시킵니다. 만약 세마포어 값이 0보다 작거나 같으면, 해당 프로세스는 대기 상태로 들어가게 됩니다.
- V(S) 연산 (Signal 또는 Up): 세마포어 값을 증가시킵니다. 만약 대기 중인 프로세스가 있다면, 이 중 하나를 깨우고 진행하게 합니다.
Dekker Algorithm
목적: 두 개의 프로세스 간에 상호 배제를 구현하여 공유 자원에 안전하게 접근하도록 합니다.
특징: turn 변수를 사용하여 두 프로세스가 번갈아가면서 자원에 접근하도록 합니다.
Lamport Algorithm
목적: 분산 시스템에서 각 프로세스 간에 상태 동기화를 실현합니다.
특징: Lamport 시계(timestamp)를 사용하여 이벤트 순서에 따라 프로세스들 간의 통신을 동기화합니다.
Peterson Algorithm
목적: 두 개의 프로세스 간에 상호 배제를 구현하여 공유 자원에 안전하게 접근하도록 합니다.
특징: flag 배열과 turn 변수를 사용하여 각 프로세스가 자원에 접근할 수 있는지를 결정하며, busy-wait 방식을 사용합니다.
이러한 알고리즘들은 공유 자원에 대한 안전한 동시 접근을 보장하면서도 성능과 효율성을 고려하여 설계됩니다. 이들은 경쟁 조건과 같은 문제를 방지하고 병렬 처리 시스템에서 안정적인 동작을 보장하기 위해 사용됩니다.
대표적인 상호배재 기법
- Dekker Algorithm (덱커 알고리즘): 공유 자원에 대한 접근을 조율하기 위한 알고리즘 중 하나로, 상호 배제를 위해 동시 접근을 방지하는 방법입니다.
- Lamport Algorithm (램포트 알고리즘): 분산 시스템에서 상태 동기화를 달성하기 위한 알고리즘으로, 이벤트 기반의 알고리즘입니다.
- Peterson Algorithm (피터슨 알고리즘): 두 개의 프로세스 간의 상호 배제를 위한 알고리즘으로, busy-wait 방식을 사용합니다.
- Semaphore (세마포어): 여러 프로세스 또는 스레드 간에 공유 자원에 대한 접근을 동기화하기 위한 기법 중 하나입니다.
Semaphore Algorithm
Semaphore는 동기화를 위한 기법 중 하나로, 프로세스나 스레드 간에 상호 배타적인 접근을 보장하기 위해 사용됩니다. 주어진 코드에서 P(S)는 세마포어 값을 감소시키고, V(S)는 세마포어 값을 증가시키는 연산입니다.
Semaphore 값이 0보다 작거나 같을 때까지 기다리는 동안, 다른 프로세스나 스레드들은 해당 자원에 접근할 수 없게 됩니다.
P(S) : while S＜=0 do skip；
S :＝S－1；
V(S) : S :＝S＋1；
주어진 코드는 세마포어(Semaphore)를 조작하는 기본적인 동작을 나타내고 있습니다. 세마포어는 여러 프로세스 또는 스레드 간의 공유 자원에 대한 접근을 제어하기 위한 동기화 기법입니다. 주어진 코드는 세마포어를 P(V) 연산으로 감소시키고, V(S) 연산으로 증가시키는 기본적인 구조를 보여줍니다.
P(S) : while S＜=0 do skip；
S :＝S－1；
V(S) : S :＝S＋1；P(S): while S <= 0 do skip;: 세마포어 값(S)이 0 이하인 동안 루프를 반복하여 아무것도 수행하지 않습니다.
S := S – 1;: 루프를 빠져나오면 세마포어 값을 1 감소시킵니다.
V(S):S := S + 1;: 세마포어 값을 1 증가시킵니다.
이 코드의 주요 목적은 세마포어의 P(V) 연산과 V(S) 연산을 구현하는 것입니다. P(S)는 세마포어를 감소시키는 연산으로, 만약 세마포어 값이 0 이하라면 대기하고, 그렇지 않으면 값을 1 감소시킵니다. V(S)는 세마포어를 증가시키는 연산으로, 세마포어 값을 1 증가시킵니다.
Dekker Algorithm
// Process 0
while turn != 0 do skip;
// Critical Section
turn = 1;
// Process 1
while turn != 1 do skip;
// Critical Section
turn = 0;
Dekker 알고리즘은 두 개의 프로세스가 공유 자원에 대한 접근을 번갈아가며 할 수 있도록 하는 방식으로 상호 배제를 달성합니다. turn 변수를 사용하여 어떤 프로세스가 현재 자원을 사용할 수 있는지 결정합니다. 이는 세마포어를 직접 사용하는 것이 아니지만, 상호 배제를 달성하는 데 사용되는 알고리즘입니다.
Lamport Algorithm
// Process i
timestamp[i] = max(timestamp[0], timestamp[1], ..., timestamp[N]) + 1;
// Critical Section
timestamp[i] = 0;
Lamport 알고리즘은 분산 시스템에서 상태 동기화를 위한 알고리즘으로, 이벤트 기반의 알고리즘입니다. 각 프로세스는 자체적으로 타임스탬프를 관리하고, 이를 활용하여 상태를 동기화합니다.
Peterson Algorithm
// Process 0
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1) do skip;
// Critical Section
flag[0] = false;
// Process 1
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0) do skip;
// Critical Section
flag[1] = false;
Peterson 알고리즘은 두 개의 프로세스 간의 상호 배제를 위한 busy-wait 방식의 알고리즘입니다. flag 배열과 turn 변수를 사용하여 각 프로세스가 자원에 접근할 수 있는지를 결정합니다. 이 또한 세마포어를 직접 사용하지 않지만, 상호 배제를 달성하기 위한 알고리즘입니다.
마무리
세마포어는 덱커 알고리즘, 램포트 알고리즘, 피터슨 알고리즘과는 조금 다른 개념으로 공유 자원에 대한 동기화를 제어합니다. 여러 프로세스가 공유 자원에 동시에 접근하지 못하도록 제어하고자 할 때 세마포어를 사용합니다. 그러나 위에 언급된 알고리즘들은 세마포어를 직접 사용하지 않고, 상호 배제를 달성하기 위해 다른 방법을 사용합니다.
