[운영체제]임계영역 해결조건 & Peterson's solution(피터슨 알고리즘)

[운영체제(OS) 목차 &책 추천]

쭉 이어서 동기화 내용 포스팅 하는 중입니다~~

 

 

피터슨 알고리즘 또한 동기화문제에서 발생하는 상호배제를 위한 병렬 프로그래밍 알고리즘 중 하나입니다

지금은 사용되지 않는 소프트웨어적이면서도 고전적인 방법이지만 항상 운영체제의 흐름이 어떻게 변화되었고 역사를 아는 것은 매우 중요하니까요 ㅎㅎ

 

이러한 알고리즘의 배경을 알고싶다면 임계영역의 문제와 lock방법에 대해서..

 

 

Peterson's solution은 이름에서 알 수 있듯이 1981년에 수학자 개리 피터슨이라는 사람이 고안한 알고리즘이예요

처음에 피터슨이 이 알고리즘을 발표했을 때는 오직 두 개의 프로세스에 대해서만 적용이 가능했다고해요

하지만 지금은 일반화되어서 2개 이상의 프로세스들 사이에서도 이 방법이 통용된다 합니다.

 

두 개의 프로세스에서 피터슨 알고리즘의 구조

P0 프로세스와 P1프로세스가 있지만 좀 더 일반화를 위해서 Pi와 Pj프로세스로 표시했어요

이 알고리즘의 특징은 flag와 turn이라고 하는 두 개의 변수를 사용해요

flag는 말 그대로 깃발 즉 신호를 나타내요. 내가 이 공유자원을 쓰고 싶어! 라고 표현하기 위한 변수입니다.

turn도 마찬가지 차례를 의미하므로 누구 차례인지 명시해주는 변수라고 이해하면 됩니다.

변수 이름이 역할을 잘 나타내고 있어서 이 알고리즘은 이해하기 쉬워요~ 

// n개의 프로세스가 있을 때, i번째 프로세스의 피터슨 알고리즘 구조도 입니다
do {
  flag[i] = true;  
   // 자 먼저 내가 임계영역에 들어가고 싶으니까 나 쓰고 싶다고 신호를 알려야겠죠? 
   //i프로세스가 지금 사용하고 싶어! 라는 의미를 전달하기 위해 flag를 true로 바꿔줍니다.

  turn = j;
  //내가 들어가고 싶다고 선언해주고 j차례로 돌려줌으로써, 
  //혹시 쓰고 싶은 다른 프로세스가 있나 확인합니다.
  //만약 다른 프로세스(ex j)가 이 공유 자원을 쓰고 싶어서 
  //7번까지 실행한 상태(j입장에서는 flag[j]=true; turn = i; 까지 실행한 상태)라면 
  //i프로세스가 j프로세스로 차례를 넘겨주자마자 16라인 코드(while)를 수행하고 임계영역에 들어가겠죠! 
  //즉 내가 쓰기 전에 먼저 쓰고 싶어했던 애가 있는 지 
  //확인하고 수행시켜주는 코드가 7번 라인입니다.

  while (flag[j] && turn == j); //전에 배운거 복습~ --> 얘가 바로 busy waits이죠!
  //임계영역에 들어가기 위해서는 당연히 내 차례여야 해요 
  //즉 turn==j일 경우 내 차례가 아닌데 j가 자원까지 쓰고 싶어한다면 
  // 나는 spinlock에서 머물어야 합니다.
  //반면에 내 차례거나 j가 자원을 쓰고 싶지 않은 경우(flag[j]==false) 
  //이제 spinlock을 빠져나와 진입할 수 있어요
  //이렇게 turn과 flag변수를 이용해서 동시 접근을 막는 거예요. 
  
  --critical section  //드디어 내가 쓰고 싶었던 자원에 와서 쿵짝쿵짝 

  flag[i]=false;  // 다 쓰고 나면 나는 다썼으니까! flag신호를 false로 바꿔줘요 

  --remainder section

} while (true);

쓰다 보니 코드에서 설명이 길어졌네요. 나름 자세히 설명하려고 했는데 워낙 복잡하지 않은 알고리즘이라 이해하기 어렵지 않을 것이라 예측합니다.

 

도움이 되셨나요?! 쉬어가는 광고타임. 당근은 토끼를 춤추게 합니다!! (찡긋)

 

 

solution의 증명과 임계영역 해결 조건

두 개의 프로세스가 동시에 임계영역에 들어가고 싶어해볼게요. 거의 비슷하게 turn 변수가 i와 j로 설정되겠죠? Pi가 조금 빨랐으면 turn 을 j로 바꿔버린다음에 Pj가 turn을 i로 즉 뒤덮어버리겠네요. 즉 동시에 시행되어도 빨리 덮어쓰여지기 때문에 문제가 발생하지 않습니다. 뭐가 먼저 더 빨리 수행될지는 알 수 없어요.

peterson's solution이란 결국 마지막에 결정된 turn의 값이 두 개의 프로세스 중에 어떤 게 공유된 자원을 먼저 사용할지 결정시키는 알고리즘이랍니다.

 

 

저번시간에 임계영역과 lock 수행시 문제점을 살펴봤어요

여러 사람들이 생각한 결과 3개의 조건을 충족시켜주면 문제가 해결된다는 것을 알았는데요.

당연한 과정을 풀어서 논리적으로 정리해뒀다 생각하면 됩니다.

 

 

1. 상호배제가 보존되어야 한다. Mutual exclusion is preserved

(mutual exclusion이라는 개념은 deadlock에서도 나왔었죠? 똑같은 말이에요 동시에 접근하지 않으려면 당연히 서로 배타적이여야겠죠 당연한 말! mutual exclusion 모르겠으면 링크 ㄱㄱ)

2. 진행 The progress requirement is satisfied.

임계영역에 어떤 스레드의 접근도 없을 때 항상 접근이 가능해야 한다는거예요

3. 무한정 대기가 없어야 한다는 말 = Bounded-waiting requirement is met.

무슨 말이냐~ 이 조건은 모든 프로세스가 cs(critical section)에 들어가기 위한 기회를 가질 수 있게 하기 위한거예요.

한 프로세스만 cs에 계속 들어가면 결국 다른 프로세스는 starvation현상을 겪을 테니까요.

즉 어떤 프로세스가 cs를 사용하고 싶어하는데 한 프로세스가 계속 그 cs를 점유하면 안되니 횟수나 이런 제한이 필요하다는 말입니다.

 

 

자 피터슨 알고리즘이 이 세 개의 조건을 만족하는지 확인해볼게요.

 

 

먼저, 각각의 프로세스는 공유된 자원에 접근하기 위해서는 나 외에 다른 프로세스가 가디라지 말아야 하거나 (flag[j]=false) 내 차례여야 하는거잖아요 즉 차례가 내 순서가 아니면 아무도 접근 못하는거예요(여기서 1번 상호배타적인거를 만족합니다)

 

내 순서가 아니더라도 남들이 아무도 안쓰면 쓸 수 있어요 (즉 2번의 진행을 만족합니다) 저 16번의 라인 코드가 1,2조건을 만족해줍니다.

 

이번에 무한정대기에 대해서 살펴볼게요 Pi는 while 코드에서 수행되고 있을 동안 변수 turn의 값을 변화시키지 않습니다. 오로지 j에 의해서 바뀌죠. Pi는 많아야 Pj가 하나라도 들어와야 turn을 i로 바꿔주기 때문에 critical section에 들어갈 수 있게 됩니다.

즉 내가 계속해서 사용할 수 없게 제한을 걸어둔게 되는거죠. 남에 의해서 cs에 들어갈 수 있으니까요.

 

 

그래서 3번의 무한정 대기가 일어나지 않는 조건도 피터슨 알고리즘은 만족한답니다.

이로서 피터슨 알고리즘을 사용하면 동기화문제를 막을 수 있다는 것을 알았어요.

 

 

비록 좋은 방법이 많이 나와서 현재는 사용되지 않지만 소프트웨어적으로 어떻게 동기화문제를 예방하는지, 조건을 어떻게 만족시키는지 깔끔하면서도 좋은 view를 제공해주기때문에 한 번 더 짚고 넘어가는게 의미있는 알고리즘이었습니다.