[Distributed System] lock

요즘 학교에서 배우고 있는 분산시스템 수업에서 과제가 나왔는데 내용도 정리할 겸해서 올려본다.

우리가 운영체제를 다룰때 앞장에서 Mutual Exclusion을 배운다. Mutual Exclusion을 사용하는 이유는 공유하는 Memory에 대해서 thread들이 접근할 때 각 thread가 사용하는 데이터에 대해서 확실하게 보장하기 위해서다. 이런 상황을 가정해보자

만약 A0가 Write를 해주는 thread고 B0가 Read를 해주는 thread라고 가정을 해보자. 지금 보면 A0와 B0가 overlap되고 있는 것을 확인할 수 있다. 참고로 미리 알고 있어야 할건 A0 thread가 실행된다고 해서 write가 바로 이뤄지는 것이 아니라는 점이다. 마찬가지로 B0도 수행 시점이 b0가 되는게 아니라는 것이다. thread란 일종의 sequence of event 로써 위 그림처럼 시작점과 종료점으로 표현되는 것이지 실제 write가 이뤄지는 시점과 read가 이뤄지는 시점은 저 interval 사이에 있다고 가정하는 것이다. 문제는 A0가 write event를 하기 직전에 B0가 read event를 실행하는 가정이다. 우리가 당연히 A0와 B0 순서로 thread를 실행시키는 것은  A0가 쓰는 데이터를 B0로 하여금 읽게 하는 것인데 위와 같은 가정에서는 A0가 데이터를 쓰기전에 B0를 읽는 상황이 발생해서 우리가 원치않는 데이터가 읽히게 된다는 것이다. 보통 이런 방법을 막기 위해서 운영체제 시간에도 배우지만 lock mechanism을 쓴다.

 아이디어 자체는 간단하다. 위와 같이 overlap이 되서 event들의 precedence가 엉키는 상황을 아예 막자는 것이다. 그래서 가장 쉽게 쓸 수 있는 방법이 thread마다 flag를 둬서 지금 수행하는 thread가 누구인지 thread끼리 알게끔 하자는 것이다. herlihy 책에는 이걸 애완동물로 표현하고 있다. 

그래서 자기 애완동물을 풀어놓기전에 flag를 세워놓고 풀어놓으면 상대방이 그걸 읽고, 자기 애완동물은 그냥 데리고 있는다는 것이다.

그런데 사실 여기에는 오류가 존재한다. 만약 A0와 B0가 동시에 flag를 세우고 애완동물을 풀어놓는다면 어떻게 될것인가?

문제가 생길것이다. 보통 이런식으로 야기되는 문제가 Deadlock이나 Starvation 등이 있다.

코드로 살짝 들어가보면 이렇게 구현되어 있다고 보자

void lock(int i)
{
  int j = 1 - i;

  flag[i] = 1;
  victim = i;
  while((victim == i) && (flag[j] == 1)){};

  return;
}

void unlock(int i)
{
  flag[i] = 0;

  return;
}

void* counter(void *arg)
{
  int i;
  THREADARGS *temp = (THREADARGS *)arg;

  for(i = 0; i < temp->num_of_repeat; i++){
    lock(temp->id);
    result++;
    unlock(temp->id);
  }

  return;
}

위의 예시는 가장 simple한 peterson`s lock 구현이다. 이런식으로 count해주는 task를 2개의 thread로 나눠서 처리하면 어떻게 될까? 만약 2000000번의 counter를 돌리게끔 thread마다 1000000번씩 loop를 수행하게 했다. 그러면 정상적인 처리라면 result가 2000000이 나와야 정상이 된다. 하지만 결과는 다음과 같다.

분명 이 이야기는 thread들을 실행하는 도중에 하나가 중복으로 수행되었다는 것을 의미하게 된다. 즉 A0가 result 에 1을 더하는 순간에 B0도 동시에 result + 1을 수행하게 되는 것이다. 그러면 다음 iteration에서 A0와 B0는 동시에 같은 result를 읽고 같은 작업을 하게 될것이다. 이같은 경우가 발생하는 것은 앞에서 말했던 것처럼 thread간에 precedence가 엉키면서 나타나는 것이다. 다시 말해서 앞에서 말한 overlap으로 인한 문제를 해결하기 위해서 만든 peterson lock도 완벽한 solution이 아니라는 것이다.

이런 문제를 해결하려면 low level로 내려가서 직접 thread내에 사용되는 연산의 순서를 강제로 정하게끔 해야 된다. 보통 이걸 memory barrier라고 한다. 간단히 말해서 memory에 접근하는데 있어서 두개가 동시에 접근하는 경우를 사전에 차단하게끔 하자는 것이다. 코드상에서는 asm코드로 딱 한줄만 추가하면 된다.

void lock(int i)
{
  int j = 1 - i;

  flag[i] = 1;
  victim = i;
  asm("mfence");
  while((victim == i) && (flag[j] == 1)){};

  return;
}

void unlock(int i)
{
  flag[i] = 0;

  return;
}

void* counter(void *arg)
{
  int i;
  THREADARGS *temp = (THREADARGS *)arg;

  for(i = 0; i < temp->num_of_repeat; i++){
    lock(temp->id);
    result++;
    unlock(temp->id);
  }

  return; 

}

저기 있는 mfence라는 instruction 자체가 x86에서 지원하는 memory barrier instruction이다. 저걸 삽입해주면 add해주는 연산 자체에 precedence가 생겨서 올바른 결과가 나오게 된다.

대충 이렇다.

reference : Maurice Herlihy & Nir Shavit :  "The Art of Multiprocessor Programming”