임계구역 문제
어제 했던 lock은 임계구역 문제중 하나를 해결한것이다.
어떤 문제들과 해결하는 방법을 살펴보자
- 상호 배제(Mutual Exclusion)
- 하나의 프로세스가 임계구역에 들어가 있다면 다른 프록세스는 들어갈 수 없다.
- 진행 (Progress)
- 임계구역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면, 어느 것이 들어갈지를 적절히 결정해줘야 한다.
- 한정 대기 (Bounded Waiting)
- 하나의 프로세스가 들어가서 오랫동안 나오지 않으면 다른 프로세스는 실행 시킬 수 없게 된다.
- 한 번 임계구역에 들어간 프로세스는 다음 번 들어갈 때 제한을 둬야 한다.
Dekker’s Algorithm
데커 알고리즘이다.
최초로 상호베제를 해결한 알고리즘이다.
방식은
- 한쪽의 깃발이 올라가면, 자신의 턴인지 확인하고 자신의 턴이 아니면 깃발을 내리고 자신의 턴이 될때까지 기다린다.
- 자신의 턴이 오면 다시 깃발을 올리고 다른 스레드의 깃발이 내려갔는지 확인 한 뒤, 계산한다.
#include <thread>
#include <iostream>
#include <vector>
#include <mutex>
using namespace std;
using namespace std::chrono;
int num = 0;
mutex mt;
int turn = 99999999;
bool flag[2] = { false };
int A = 0, B = 1;
void TreadFuncA()
{
for (int i = 0; i < 10000000; i++)
{
flag[A] = true;
while (flag[B])
{
if (turn == B)
{
flag[A] = false;
while (turn == B);
flag[A] = true;
}
}
num += 2;
turn = B;
flag[A] = false;
}
}
void TreadFuncB()
{
for (int i = 0; i < 10000000; i++)
{
flag[B] = true;
while (flag[A])
{
if (turn == A)
{
flag[B] = false;
while (turn == A);
flag[B] = true;
}
}
num += 2;
turn = A;
flag[B] = false;
}
}
int main()
{
vector<thread> threads;
steady_clock::time_point start_time = high_resolution_clock::now();
threads.emplace_back(thread{ TreadFuncA });
threads.emplace_back(thread{ TreadFuncB });
for (int i = 0; i < 2; 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;
}
39664190
Result : 317
결과는… 정확도가 높아졌긴 했는데 아직 문제가 있다.
속도가 생각보다 안나오고 그래도 완벽한 답이 나온것이 아니다. 다른 사람들의 소스를 봐도 같은 문제가 발생한다.
이 해결방법 말고 다른 해결방법이 있다
Peterson’s Algorithm
데커 알고리즘보다 더 간단하지만 다른 알고리즘인 피터슨 알고리즘이다.
- 임계영역에 들어가려고 시도
- 상대방에게 진입 기회 양보
- 상대방이 집인하려한다면 대기
- 연산
- 임계영역 사용완료 지정
이런 방식이다.
#include <thread>
#include <iostream>
#include <vector>
#include <mutex>
using namespace std;
using namespace std::chrono;
int num = 0;
mutex mt;
int turn = 99999999;
bool flag[2] = { false };
int A = 0, B = 1;
void TreadFuncA()
{
for (int i = 0; i < 10000000; i++)
{
flag[A] = true;
turn = B;
while (flag[B] && turn == B);
num += 2;
flag[A] = false;
}
}
void TreadFuncB()
{
for (int i = 0; i < 10000000; i++)
{
flag[B] = true;
turn = A;
while (flag[A] && turn == A);
num += 2;
flag[B] = false;
}
}
int main()
{
vector<thread> threads;
steady_clock::time_point start_time = high_resolution_clock::now();
threads.emplace_back(thread{ TreadFuncA });
threads.emplace_back(thread{ TreadFuncB });
for (int i = 0; i < 2; 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;
}
결과는~~~
39999960
Result : 640
정확도는 진짜 엄청많이 올라갔다…
하지만 정확도를 얻고 시간을 버렸다…
위에 두 알고리즘은 이렇게 임계구역 문제를 해결했지만, 아쉽게도 스레드가 많아지면 그만큼 복잡해진다.