[OS / 운영체제] Mutual Exclusion using TestAndSet, Mutual Exclusion and Swap, Mutual Exclusion using CAS, Bounded Waiting Mutual Exclusion, Atomic Variable

 

Mutual Exclusion using TestAndSet

  critical section 앞에 entry section이 있다. Lock의 초깃값이 false이다. 첫 번째 프로세스가 critical section에 들어가려고 시도를 한다. TestAndSet은 이전의 lock의 값을 return 해주는 함수이다. while()문이 깨지게 된다. 들어가는 입장에서 while문이 깨지는 것, Critical section에 들어갈 수 있다는 의미이다. lock = 0이므로 들어갈 수 있게 해주고 TestAndSet은 해당 lock값을 무조건 1로 바꾸어 준다. 그 변수의 값을 true로 바꿔준다. 다음 프로세스가 들어오게 되는 경우 TestAndSet의 리턴값은 true이므로 while 문이 유지가 되어서 critical section에 들어가지 못한다. 이 상황에서는 while 문이 유지되는 것이 좋다. 누군가가 들어가 있는 상황이므로 while문이 유지되는 것이 좋은 상황이다.

  3번째 프로세스가 들어오는 상황을 생각해보자. 그 프로세스도 while문이 유지가 된다. 기다리는 상호아에서 TestAndSet의 상황은 다 1로 유지가 된다. 결과적으로 P1은 들어가지만 P2 P3는 걸려서 기다리게 된다. P1이 나가려고 할 때 lock = false로 바꾼다. 해당 값이 0으로 바뀌게 되고 P2, P3에게 영향을 미치게 된다. P2의 경우 while문이 0이 되어버려서 Critical section에 들어가서 lock의 값을 1로 바꾸게 된다. 그러면서 P3는 들어오지 못하도록 막게 된다. 실제로는 Scheduling을 통해서 먼저 들어갈 수 잇는 프로세스가 들어가게 된다.

 

 

Mutual Exclusion and Swap

  local variable을 사용한다. 초깃값을 1로 설정을 한다. P1의 key값은 1이 된다. while문이 그러면 true가 된다. 이 상태에서 swap Atomic Instruction을 사용한다. lock과 key를 바꾸게 되면 lock은 0에서 1로 되고 key는 1에서 0으로 바뀐다. 이렇게 되면 while문이 깨지게 된다. 첫 번째 프로세스 P1은 critical section에 들어갈 수 있게 된다. 그 동안 P2가 들어가게 되는 경우 P2도 local variable이 있다고 할 수 있다. 초깃값은 1로 되어있다. key가 true이므로 swap을 실행하게 되고 lock은 현재 값이 1이고 key도 1이므로 바꿔도 계속 1이 된다.(프로세스마다 고유 지역 변수 key를 가지고 있고 해당 값은 초기에 항상 ture로 초기화가 된다.)

  해당 While 문이 계속 반복된다. critical section에 들어가지 못하고 기다린다는 뜻이다. P2, P3는 while에서 기다리게 된다. P1이 exit section을 만날 때 lock을 false로 만들게 된다. 그러면서 remainder section으로 이동하게 되는데 그 때의 P2, P3의 상황을 살펴보자.

 

  lock이 0에서 다시 1로 되고 key는 0으로 바뀌게 된다. while 문이 깨지게 되고 critical section으로 P2가 들어갈 수 있게 된다. 그리고 나올  때 lock을 0으로 바꾸어서 다음 프로세스가 들어갈 수 있도록 만든다. TestAndSet과 거의 동일하게 Mutual exclusion을 보장할 수 있다. lock은 shared 변수이고 key는 local 변수이다.

 

 

Mutual Exclusion using CAS

  compare_and_swap을 해서 lock = 0 인 상태를 보내게 되면 0이 리턴이 되어서 해당 condition에 의해서 while문이 깨지게 된다. 첫 번째 프로세스는 Critical section으로 들어가게 된다. lock과 두 번째 0의 값을 비교해서 같으면 세 번째 값을 lock에 할당하게 된다. while문을 지나가게 되면서 lock에는 1이라는 값이 할당된다. 첫 번째 프로세스는 들어가고 lock의 값을 1로 바꾸는 것이 우리가 원하는 결과이다. 그 상태에서 P2가 들어오는 경우를 생각해보자. 그 경우 return 값은 1이 된다. (현재 lock의 값이 return 됨)

  while 문이 유지가 되고 해당 lock 값은 1로 유지가 된다. P2는 while 문에서 기다리는 상태가 된다. P1이 떠나면서 lock = 0으로 만들고 떠나게 된다. P2와 P3에 어떤 영향을 주는가 살펴봐야 한다. P2의 경우 while문을 실행하면 return 이 0이 되고 while문이 깨지게 되고 다시 lock 값을 1로 바꾸게 되면서 P3를 while문 안에 머물게 만들어준다. 

 

 

Bounded Waiting Mutual Exclusion

  남이 들어가면 내가 기다리는 데 최대한 몇 번까지 기다린다는 Bounded Waiting이라고 한다. N개의 프로세스가 있으면 최대한 N-1번까지 기다리게 하는 것이 상식적인 것이다. 프로세스가 0부터 N-1번 까지 존재하고 Shared Process에 접근하려고 한다. 모든 프로세스는 모든 순간에 Shared Process에 접근하려고 한다. (X) 이 경우 critical section으로만 이루어졌다는 말이므로 틀린 말이다. 진한 화살표는 Shared resource에 접근하고 싶은 프로세스이다. 얇은 화살표는 Critical section에 들어갈 생각이 현재는 없는 상태인 것이다. 빨간색 화살표는 현재 Critical section에 들어가 있는 프로세스를 의미한다. 검은색 굵은 화살표는 Entry section에 들어가 있는 상황으로 볼 수 있다. 들어가 있다는 것은 현재 Lock이 1 이라는 것이다. P1이 들어갔다가 나오려고 한다고 해보자. lock = 0으로 만들어서는 Bounded waiting을 보장하기 힘들다. 왜냐하면 불특정한 프로세스가 들어가기 때문이다. 누가 들어갈 지는 알 수 없다. 아마 Scheduling을 통해서 다음에 들어갈 프로세스가 들어갈 확률이 높고 내가 원하는 프로세스가 들어갈 보장을 할 수 없다. N개의 Process가 있으면 최대 N-1번 최대 기다릴 수 있다고 할 수 있다. 

 들어가다 나올 때 특정 프로세스에게 알려줘야만 원하는 순서를 부여할 수 있게 된다. P1이 들어갔다 나오려고 할 때 어느 프로세스에게 터치를 해야 하는가. P3에게 터치를 해야 하고 P3는 P5에게 살짝 터치를 해야 한다. P0가 마지막으로 나올 때는 어떻게 해야 하는가? 이 경우는 lock을 false로 만들기만 하면 된다. lock을 풀어줘야 하는 것이다. 

 

 

Bounded Waiting Mutual Exclusion

critical section에 아무도 없을 때는 lock = 0이고 누군가 있을 때는 lock = 1이 된다. 굵은 화살표가 Critical section에 들어가고 싶지만 Waiting 하는 것이 되고 빨간색 프로세스는 제외되어야 한다. 이를 waiting 배열로 지정을 한다. P1, P3, P5 모두 1이 되고 나머지 그냥 화살표들은 0이 된다. waiting 값은 0이 된다. waiting은 Bounded Waiting할 때 사용된다. 오른쪽으로 값을 따라가다가 값이 1인 프로세스를 들어오게 하면 된다. entry section과 exit section으로 되어 있다. Bounded Waiting을 보장하기 위해 코드 줄이 늘어났다. waiting[i] = 1인 친구들은 Entry section에 있는 친구들이다. Mutual Exclusioin을 보장하기 위한 코드가 Entry section에 존재한다. key = true이면 while test를 실행하게 된다. 두 개가 다 True여야 While문이 True가 된다. waiting 도 true이고 key도 true여서 TestAndSet을 호출하게 된다. lock의 초깃값은 0(false)이고 리턴 값은 0이 되고 key값이 0이 된다. 그리고 다시 while을 만나게 되면 while문이 false가 된다. 그래서 while문이 깨지게 된다. 그렇게 critical section에 들어가게 된다. 들어갈 때 TestAndSet을 실시했기 때문에 lock의 값이 1로 바뀌게 되고 waiting[i] 도 false(0)으로 바뀌게 된다. 

 2번 프로세스가 들어오는 경우 waiting[i] = True로 하고 key = true로 하면 while문이 실행된다. TestAndSet이 리턴하는 것은 lock의 값이다. 즉 리턴값은 1이 되고 key도 1로 유지가 된다. 그래서 while문이 계속 반복되서 Critical section에 못들어가게 된다. 

 J != I는 더 이상 돌리지 않고 한 바퀴만 돌고 끝내라는 조건이 된다. j == i 일때만 lock을 풀어주게 된다. 

 

 

Atomic Variable

임의로 증가할 수 있는 것이 아니라 특정한 Function을 이용해야만 변경이 가능하다. Atomic Variable의 뜻은 한 번의 operation이 분리될 수 없다는 것이다. 어떠한 변수의 값을 증가할 때 race condition을 발생시키지 않기 위한 작업이다. increment function을 이용해야만 바꿀 수 있다. 일반 Integer 변수는 이 함수가 아니더라도 변경할 수 있는 것이 차이점이다. Atomic variable은 OS가 제공하는 Tool이다. 일반 그냥 Function이다. 어떻게 Race condition을 막아주는가? 현재 atomic 변수가 하나 있는 데 (v == 5) 우리가 원하는 것은 v의 값을 6으로 만들어주는 것이다. temp라는 지역 변수가 존재한다. compare_and_swap의 리턴 value는 이전에 있었던 v의 값이 된다. 그러면 리턴값이 5가 되고 temp가 5이므로 해당 조건이 만족되지 않으므로 while문이 깨지게 된다. (temp = 5) 깨지고 나서는 v는 6이 된다. increment function이 끝나게 되고 이것이 우리가 원하는 동작이 된다. v의 값을 1 증가시켰고 정상적으로 끝나게 됐다.

 중요한 점은 누군가가 v에 접근하려고 할 때를 생각해보자. temp에다가 v를 할당한 경우, 다른 프로세스가 들어와서 먼저 increment 함수를 실행시킨 경우 v가 6으로 증가하게 된다. v == 6, temp == 5가 된다. compare_and_swap은 이때 6을 리턴하게 되고 temp == 5이므로 while문이 유지가 된다. v == 6 temp == 5이므로 temp+1을 v에 넣지 않게 되므로 v는 그대로 6이 된다. 다시 실행하게 되면 v = 6으로 할당이 되고 v == 6, temp == 6이되므로 v에 temp+1인 7을 할당하게 된다. 리턴값과 temp == 6은 동일하므로 while문이 깨지게 된다. 누군가가 끼어들어도 정확하게 하나 증가하는 작업이 이루어지게 된다.