운영체제 - Peterson's Solution, Bakery 알고리즘(상호배제 문제 해결)

임계구역에 대한 요구사항

01 상호 배제(mutal exclusion)

한 프로세스가 임계 구역을 실행 중일때, 다른 어떤 프로세스도 임계 구역을 실행할 수 없다.

02 진행(Process)

임계구역 안에 반드시 하나의 프로세스를 선택하여 진입시키는 올바른 결정 기법이 있어야 하고, 이러한 결정은 무한정 미루어 져서는 안된다.

03 제한된 대기(bounded waiting)

한 프로세스가 임계 구역에 대한 진입 요청 후부터 요청의 수락까지의 기간 내에, 다른 프로세스가 임계 구역을 실행할 수 있는 회수에는 제한이 있어야 한다.

---

Peterson's Solution

임계구역에 대한 요구사항중 상호 배제를 해결하기 위한 알고리즘이다. 두 개의 프로세스나 쓰레드가 동시에 공유 자원을 사용할 때 발생할 수 있는 문제인 상호 배제 문제를 해결하기 위해 사용된다.

private static bool[] flag = new bool[2];
private static int turn;

static void Thread_1()
{
    while (true)
    {
        flag[0] = true;
        turn = 1;
        while (flag[1] && turn == 1)
        {
             // busy wait
        }
        // Critical Section
        Console.WriteLine("Thread_1가 Critical Section안에 있음!");
        flag[0] = false;
    }
}
static void Thread_2()
{
    while (true)
    {
        flag[1] = true;
        turn = 0;
        while (flag[0] && turn == 0)
        {
             // busy wait
        }
        // Critical Section
        Console.WriteLine("Thread_2가 Critical Section안에 있음!");
        flag[1] = false;
    }
}

flag - 쓰레드의 자원 요청 여부

turn - 쓰레드가 Critical section에 들어갈 차례인지

---

과정

1. flag[0] = true를 통해서 thread_1이 자원을 요청한다.

2. turn = 1 : thread_1이 임계 구역에 진입하고자 하는 차례임을 나타낸다.

3. while (flag[1] && turn == 1) : 다른 쓰레드(thread_2)가 자원을 사용 중이거나 자신의 차례가 아닌 경우 대기 한다. 

4. flag[0] = false 임계 구역을 빠져나온 후 'flag[0]'를 false로 설정하여 thread_1이 임계 영역에 진입하여 자원을 사용한 후 자원의 사용이 끝났을음 나타낸다.

---

Bakery 알고리즘(Lamport)

여러개의 프로세스에 적용 가능한 소프트웨어에 의한 임계구역 해결책이다. 프로세스나 쓰레드가 임계구역에 진입하는 순서를 결정하는데 사용된다.

과정

1. 프로세스가 임계구역에 진입하고자 할때, Bakery알고리즘을 통해 번호표를 받는다.

(번호표(Ticket) : 각 프로세스 혹은 쓰레드는 번호표를 발급 받는다. 번호가 낮을 수록 우선순위가 높다.)

2. 다른 프로세스가 이미 번호표를 받은 상태라면, 번호표 비교를 통해서 대기 상태로 들어간다.

(대기상태(Waiting State) : 번호표를 받은 프로세스는 해당 번호가 올때까지 대기한다.)

(번호표 비교(Comparison) : 프로세스는 번호표를 비교하여 우선순위를 결정한다. 번호표가 동일 할 경우 프로세스 ID값 등을 비교하여 우선순위 결정)

3. 번호표를 받은 프로세스가 임계 구역에서 나온 후, 번호표를 갱신하여 다른 프로세스가 번호표를 받도록 한다.

(번호표 갱신(Ticket Update) : 프로세스가 임게 구역을 빠져나온 후, 다른 프로세스가 번호표를 받을 수 있도록 번호표를 갱신)

4. 다른 프로세스들도 번호표를 받아 임계 구역에 진입하는 과정을 반복한다.

---

Code예시

01 변수 및 초기화 설정

private bool[] choosing; // 입장
private int[] number; // 번호표의 번호

// 초기화 하기
public Bakery(int num)
{
    choosing = new bool[num];
    number = new int[num];

    for (int i = 0; i < num; i++)
    {
        choosing[i] = false; // 모든 Thread가 진입 시도 중이지 않게 만든다
        number[i] = 0; // 모든 Thread에게 번호표의 번호를 0으로 설정
    }
}

---

02 쓰레드가 진입하는 entry 함수

public void entry(int id)
{
    choosing[id] = true; // Thread 진입 시도 중
    number[id] = number.Max() + 1; // number 배열 중 최대값에 1을 더한 값으로 번호표를 받음
    choosing[id] = false; // Thread 진입 완료

    for (int i = 0; i < number.Length; i++)
    {
        if (i != id)
        {
            while (choosing[i]) ;
            while (number[i] != 0 && (number[i] < number[id] || (number[i] == number[id] && i < id))) ;
        }
    }
}

1) if( i  !=  id) : 현재 쓰레드와 동일한 id를 가진 쓰레드에 대해서는 번호표 확인할 필요가 없다.

2) number[i] != 0 : 이미 다른 쓰레드(i)가 번호를 할당 받은 상태이므로 대기해야 한다. 

3) number[i] != 0 && (number[i] < number[id]) :  이미 다른 쓰레드(i)가 번호표를 할당 받았고 그 번효표가 현재 쓰레드(id) 보다 값이 작아서 대기 해야한다. 값이 작을 수록 우선순위가 높다.

4)number[i] != 0 && (number[i] == number[id] && i < id) : 이미 다른 쓰레드(i)가 번호표를 할당 받았고 그 번호표가 현재의 쓰레드(id)의 번호표와 같은 경우 동일한 우선순위를 가지게 된다. 그렇기 때문에 더 세밀하비교하기 위해서 다른 쓰레드(i)의 ID와 현재 쓰레드(id)의 ID를 비교한다. ID가 작은 쓰레드가 우선순위가 더 높은 쓰레드이다.  

---

03 쓰레드가 작업을 완료 하고 나오는 exit함수

public void exit(int id)
{
    number[id] = 0;
}

쓰레드의 번호표를 0으로 설정해서 번호표를 초기화한다.

---

 

04 실행 함수 만들기

static Bakery bakery;
static void ExecuteProcess(int id)
{
    bakery.entry(id);
    Console.WriteLine($"{id} 입장 ");
    Thread.Sleep(100);
    bakery.exit(id);
    Console.WriteLine($"{id} 퇴장 ");
}

---

05 실행하기

static Bakery bakery;
static int n = 8;  
static void Main(string[] args)
{
    bakery = new Bakery(n);
    Thread[] threads = new Thread[n];
    for (int i = 0; i < n; i++)
    {
        int id = i;
        Thread thread = new Thread(()=>ExecuteProcess(id));
        thread.Start();
    }
    for(int i = 0; i<n;i++)
    {
        threads[i].Join();
    }
    Console.WriteLine("작업 완료!");
}

각 쓰레드가 번호표를 받으면서 입장하고 순서대로 퇴장하는 것을 확인할 수 있다.