임계구역 문제
어제 했던 lock은 임계구역 문제중 하나를 해결한것이다.
어떤 문제들과 해결하는 방법을 살펴보자
- 상호 배제(Mutual Exclusion)
- 하나의 프로세스가 임계구역에 들어가 있다면 다른 프록세스는 들어갈 수 없다.
- 진행 (Progress)
- 임계구역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면, 어느 것이 들어갈지를 적절히 결정해줘야 한다.
- 한정 대기 (Bounded Waiting)
- 하나의 프로세스가 들어가서 오랫동안 나오지 않으면 다른 프로세스는 실행 시킬 수 없게 된다.
- 한 번 임계구역에 들어간 프로세스는 다음 번 들어갈 때 제한을 둬야 한다.
Bakery Algorithm
빵집 알고리즘이다.
이 전에 했던 데커 알고리즘과 피터슨 알고리즘에서는 세개 이상 넘어가면 관리하기 힘들지만, 이 빵집 알고리즘은 N개 이생의 프로세스의 상호베제가 되도록 구현하는 방법이다.
쉽게 설명하면,
- 스레드에 먼저 온 순서대로 번호표를 부여
- 그 번호표가 우선인 프로세스부터 작업을 시켜줌
- 만약 두 스레드가 동시에 접근을 하여 번호표가 같아진다면, 스레드 번호가 낮은 순서로 우선순위를정한다.
#include <thread>
#include <iostream>
#include <vector>
#include <mutex>
#define N 4
using namespace std;
using namespace std::chrono;
int choosing[N] = { 0 }, turn[N] = { 0 };
int num = 0;
int Max()
{
int max = 0;
for (int i = 0; i < N; i++)
{
if (max < choosing[i])
{
max = choosing[i];
}
}
return max;
}
bool Compare(int num, int id)
{
if (choosing[num] < choosing[id]) return false;
else if (choosing[num] < choosing[id]) return true;
else
{
if (num < id) return true;
else return false;
}
}
void Lock(int i)
{
choosing[i] = 1;
turn[i] = Max() + 1;
choosing[i] = 0;
for (int j = 0; j < N; j++)
{
if (j != i)
{
while (choosing[j]);
while (turn[j] != 0 && Compare(j, i));
}
}
}
void UnLock(int i)
{
turn[i] = 0;
}
void TreadFunc(int thread_id)
{
for (int i = 0; i < 20000000 / N; i++)
{
Lock(thread_id);
num += 2;
UnLock(thread_id);
}
}
int main()
{
vector<thread> threads;
steady_clock::time_point start_time = high_resolution_clock::now();
for (int i = 0; i < 4; i++)
{
threads.emplace_back(thread{ TreadFunc, i });
}
for (int i = 0; i < 4; i++)
{
threads[i].join();
}
steady_clock::time_point end_time = high_resolution_clock::now();
auto time = end_time - start_time;
int result_time = duration_cast<milliseconds>(time).count();
cout << num << endl;
cout << "Result : " << result_time << endl;
}
이번에 결과는!?
35659846
Result : 1110
4개를 돌렸는데 처참하다. 역시 예상대로 잘 안돌아간다….
역시 그냥 mutex 쓰자….
그래도 막는 방법은 알겠다.