Synchronization: The Critical Section Problem(2)

Working Solutions

What is Peterson's solution?

피터슨은 1981년에 2페이지의 매우 간단한 해결책을 발간했습니다. 공유 변수인 turn을 사용해 해결한 그의 알고리즘은 다음과 같습니다.

\\ Candidate #5
raise my flag
turn = your_id
wait while your flag is raised and turn is your_id
// Do Critical Section stuff
lower my flag

위와 같은 pseudo C는 아래와 같습니다. 

\\ Candidate #5
bool flag1, flag2  //both initially false
int flag = 1

thread1:                          thread2:
  flag1 = true                      flag2 = true
  turn = 2                          turn = 1
  while(flag2 && turn == 2) {}      while(flag1 && turn == 1) {}
  Critical Section                  Critical Section
  flag1 = false                     flag2 = false

이러한 해결책은 Mutual exclusion, Bounded Wait, Progress를 만족합니다. 만약 2번 스레드가 turn을 1로 설정하고 현재 CS에 진입했다면 스레드1이 도착했을 때 turn을 2로 되돌려 thread 2의 flag를 내린다

Was Peterson's solution the first solution?

아닙니다. Dekkers algorithm(1962년)이 더 먼저 발견되었습니다. 이 알고리즘은 아래와 같습니다.

raise my flag
while(your flag is raised) :
   if it's your turn to win :
     lower my flag
     wait while your turn
     raise my flag
// Do Critical Section stuff
set your turn to win
lower my flag

어떻게 loop가 0번, 1번, 그 이상 반복되는지에 관계 없이 CS동안 프로세스의 flag가 들려있는 것인지 잘 살펴보세요. flag는 CS에 즉시 진입하기 위한 의도로 해석될 수 있습니다. 오직 다른 프로세스가 flag를 들어올렸을 때 하나의 프로세스를 연기하고, 깃발을 내리고 기다립니다.

Can I just implement Peterson's(or Dekkers) algorithm in C ro assembler?

물론 가능합니다. 조금만 검색해보면 특정 단순한 모바일 프로세서를 위한 production에서 찾을수 있습니다. Peterson's algorithm은 Tegra mobile process의 리눅스 커널 lock의 low-level 구현에 사용됩니다.

하지만 일반적으로 CPU와 C compiler는 CPU instruction을 재정렬하거나 다른 코어가 shared variable을업데이트한다면 CPU core에 stale한 특정한 로컬 캐시 값을 사용할 수 있습니다. 그러므로 단순한 C로 수행되는 pseudo code는 대부분의 flatform에서 너무 naive합니다

여기서부터는 읽지 않아도 됩니다.

다음과 같은 코드를 생각해 봅시다.

while(flag2 ) { /* busy loop - go around again */

효율적인 컴파일러는 flag2가 loop안에서 변하지 않는다는 것을 알 수 있어 while(ture)로 최적화될지도 모릅니다. volatile을 사용하면 이러한 종류의 최적화를 막을 수있습니다.

독립적인 instruction들은 최적화 컴파일러 재정렬 하거나 CPU가 out-of-order 실행 최적화를 해줌으로써 런타임에 재정렬될 수 있습니다. 만약 코드가 변수를 수정하거나 체크하고 정확한 순서가 필요하다면 이러한 복잡한 최적화가 필요합니다.

 이와 관련된 문제는 CPU core가 최근 읽거나 수정된 메인 메모리 값을 저장하기 위해 data cache를 가지고 있다는 것입니다. 수정된 값이 main memory에 다시 써지지 않거나 메모리로부터 즉시 다시 읽어지지 않을 수도 있습니다. 그러므로 flag나 turn 변수의 상태가 두 개의 CPU code에서 공유되지 않을 수도 있습니다.

그러나 다행히도 최근의 하드웨어 주소는 이러한 문제를 memory fence(barrier) CPU instruction을 사용해 해결합니다. 이 방법을 통해 메인 메모리와 CPU cache가 합리적이고 일관된 상태로 유지할 수 있습니다.

고레벨의 synchronization primitive들, 즉 pthread_mutex_lock과 같은 경우 구현 중 이러한 CPU instruction을 호출합니다. 그러므로 사실 CS를 둘러싼 mutex lock과 unlock을 호출할 때는 이러한 lower level problem을 무시해도 됩니다.