Software-based Solutions for Critical section problem
Dekker’s Algorithm2개의 프로세스가 공유 자원을 문제 없이 사용할 수 있는 알고리즘
Eisenberg & McGuire’s Algorithm: n개의 프로세스를 사용하여 n - 1 이하의 대기 시간을 보장하는 알고리즘
Peterson’s AlgorithmCritical Section Problem 가장 완전하게 해결한 알고리즘. But,load&store와 같은 기계어 명령이 현대 컴퓨터에서 제대로 작동할 것이라는 보장이 안된다.
Peterson’s Algorithm
- 기본적으로 2개의 프로세스를 이용하며, 필요한 경우 확장할 수 있음.
while (true)
{
flag[i] = true;
turn = j;
while (flag[j] && turn == j) // entry section
;
/* critical section */
flag[i] = false; // exit section
/* remainder section */
}i, j 두 개의 프로세스 존재
i프로세스는j프로세스가 exit section에 도달해 flag[j] = false; 가 되면 Critical section 진입j프로세스가 remainder section 종료 후 다시 entry section으로 돌아와서 turn = i; 가 되면 Critical section 진입
→ i, j 두 개의 프로세스가 동시에 Critical section에 진입 불가능
간단하게 구현해보자
#include <stdio.h>
#include <pthread.h>
#define true 1
#define false 0
int sum = 0;
int turn;
int flag[2];
int main()
{
pthread_t tid1, tid2;
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n", sum);
}
//<생산자 코드>
void* producer(void* param)
{
for (int k = 0; k < 10000; ++k)
{
/* entry section */
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
;
/* critical section */
sum++;
/* exit section */
flag[0] = false;
/* remainder section */
}
pthread_exit(0);
}
//<소비자 코드>
void* consumer(void* param)
{
for (int k = 0; k < 10000; ++k)
{
/* entry section */
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
;
/* critical section */
sum--;
/* exit section */
flag[1] = false;
/* remainder section */
}
pthread_exit(0);
}코드를 실행해보면 기대값 (0)이 아닌 다른 값들이 종종 나온다.
피터슨 솔루션은 기계어 명령의 생성 방식에 따라 제대로 동작하지 않을 수 있다.
→ entry section에서 Context Switch가 발생하기 때문
Note:
i프로세스가 Critical section 실행 중일 때j프로세스는 대기
→ Mutual Exclusion (상호배제) 증명
- 프로세스가 Critical section으로 진입이 무기한 연기되지 않는다.
→ Progress Flexibility 증명
i프로세스가 Critical section 완료 시j프로세스가 진입한다.
즉, 어떤 프로세스가 진입을 계속 못하는 상황이 발생하지 않는다.
→ Bounded Waiting이 가능하므로 starvation(기아)가 발생하지 않는다.
Hardware-based Solutions for Critical section problem
- 소프트웨어 측면으로만 CSP를 해결하기에는 기계어 수준에서의 예상치 못한 Context Switch 발생 등으로 어려움이 있음. → 완벽한 문제 해결을 위해 하드웨어의 지원이 필요함.
- 3가지 처리 기법
- 메모리 배리어 (memory barrier) 혹은 메모리 펜스 (memory fence)
- 하드웨어 명령 (hardware instructions)을 이용하는 방법
- 원자적 변수 (atomic variable)
- 원자성 (atomicity) 더 이상 쪼갤 수 없는, 즉 인터럽트가 발생할 수 없는 동작을 원자적 동작 (atomic operation) 이라고 한다. 한 클럭 에 해결할 수 있는 기능을 만들기 위해 하드웨어 측면에서 특수 명령으로 만들 수 있다.
-
Test and modify
a++ 동작을 Load, Add, Store의 3 클럭으로 나누는 대신 한번에 동작하도록 한다. -
Test and swap
두 개의 변수를 swap 할 때 tmp = i, i = j, j = tmp의 3 클럭으로 나누는 대신 한번에 동작하도록 한다.-> 운영체제에서는
test_and_set(),compare_and_swap()의 형태로 제공한다. 해당 명령 수행 중에는 절대로 Context Switch가 일어나지 않는다.
-
- 원자적 변수 (atomic variable)
compare_and_swap()하드웨어 명령을 사용하여 구현 가능 원자적 변수의 사용을 통해 하나의 변수(single variable)에서 발생하는 경쟁 상태(race condition)를 막고 상호 배제(mutual exclution)를 보장할 수 있음
- Java에서 구현
import java.util.concurrent.atomic.AtomicBoolean;
public class Peterson2
{
static int count = 0;
static int turn = 0;
static AtomicBoolean[] flag;
//flag를 원자적 변수로 설정
static
{
flag = new AtomicBoolean[2];
for (int i = 0; i < flag.length; i++)
flag[i] = new AtomicBoolean();
}
static class Producer implements Runnable
{
@Override
public void run()
{
for (int k = 0; k < 10000; k++)
{
/* entry section */
flag[0].set(true); // 값을 직접 대입하는 대신 메소드를 사용함.
turn = 1;
while (flag[1].get() && turn == 1)
;
/* critical section */
count++;
/* exit section */
flag[0].set(false);
/* remainder section */
}
}
}
static class Consumer implements Runnable
{
@Override
public void run()
{
for (int k = 0; k < 10000; k++)
{
/* entry section */
flag[1].set(true);
turn = 0;
while (flag[0].get() && turn == 0)
;
/* critical section */
count--;
/* exit section */
flag[1].set(false);
/* remainder section */
}
}
}
public static void main(String[] args) throws Exception
{
Thread t1 = new Thread(new Producer());
Thread t2 = new Thread(new Consumer());
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(Peterson1.count);
}
}참고 :
Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.
꾸준하게