A라는 사람의 계좌에 100만원이 있다.
동일한 타이밍에 100만원 입금과, 150만원 출금 요청이 들어왔다.

입금과 출금의 순서의 따라 task가 실패하느냐 성공하느냐 결과가 달라진다.
process나 thread들 또한 interleaved(병렬적)이기에 공유되는 리소스에서 이러한 문제가 발생할 수 있다. 그렇기에 동기화(synchronization)이 필요하다.

Shared Resources

• 각 stack의 local 변수들은 공유되지 않는다.
  • stack에 할당된 각 thread들의 local 변수는 공유되지 않는다.
• Gloval 변수는 공유되지만 write될 수 없다.
• Dynamic object(heap에 위치)들은 공유될 수 있다
  • 제일 큰 골칫덩이

Critical region (임계 지역)

• 공유되는 리소스에 대한 read/write가 존재하여 위험성이 존재하는 code

동기화를 위해 상호배재적으로 코드를 실행하고 싶다. (Mutual Exclusion)

임계지역 수행을 위한 요구 사항

• 상호 배재적이어야 한다

• 특정 task가 임계지역 수행을 위해 계속해서 대기하면 안된다.
• 특정 task가 임계지역을 작업했다면, 특정 task의 임계지역 진입을 막을 수 없다

임계지역에는 위와 같은 요구사항들이 존재한다.

Critical region algorithm

lock변수를 사용하기

lock변수가 0이라면 해당 code를 수행할 수 있고, 1이라면 수행할 수 없다.

하지만, 큰 문제점이 존재한다. Thread A가 해당 CR(Critical Region)에 진입하였을때 lock변수가 0임을 확인하고 while문을 통과하여 lock을 1로 설정할려는 찰나에 Thread B가 스케쥴되어 동시에 진입한면 Mutex를 달성할 수 없다. 변수의 교체가 atomic한 action이 아니기 때문에 일어나는 문제이다.

Strict alternation

Thread A와B가 각자 turn변수에 따라 대기한다. 이를 BusyWaiting이라고 한다.
(a)를 실행하는 A는 turn이 1이라면 while문을 반복하며 turn이 0이될 때 까지 대기한다. B 또한 똑같은 원리로 (b)를 실행한다. 이러한 알고리즘을 spin lock이라고 한다.
각자 turn이 올때까지 while문을 의미없이 돌리며 대기하는건 CPU를 지독하게 낭비하는 꼴이다.

피터슨 알고리즘

두 Process가 CR에 들어가기 위한 race condition이다. interested[2]배열을 사용하여
어떠한 process가 임계 지역 진입을 위한 waiting을 하고 있는지 알린다 (boolean을 사용)
즉, process 0가 CR에 진입한다면 turn을 0으로, interested[0]=truefh 설정한다.
process 1은 interested[0]가 false가 될때까지 busywaiting을 한다.

TSL (Test and Set Lock)

이번에는 hardware의 도움을 받아 atomic한 lock변수를 사용해보자.
특정 CPU가 CR을 read나 write를 한다면 메모리 버스를 lock하여 다른 cpu의 접근을 막아준다.

Sleep and Wake up

OS의 도움을 받아 조금 성능을 향상 시켜 보자. 기존의 Busywaiting은 무의미한 while문을 통해
계속해서 cpu 리소스를 낭비하였다. sleep system call을 사용하여, 특정 쓰레드(이하 'A')가 다른 쓰레드(이하 'B')가 점유 중인 임계구역에 들어가고자 할때 재워준다. 말 그대로,다른 쓰레드의 작업이 끝날때까지 block시키는 것이다. 'B'가 작업을 다 끝낼경우, wakeup() call을 통해 block되어 있는 'A'를 깨워주고 'A'는 임계 지역에 접근할 수 있게 된다. 굉장히 합리적이고 좋아보이지만, 여전히 문제는 존재한다 .

생산자-소비자 문제

유한 버퍼를 가진 소비자-생산자가 존재한다고 할때. 병렬적으로 쓰레드가 실행 된다면, 각 쓰레드마다 버퍼의 개수가 차이가 존재 할 수 있다. 버퍼가 공유 자원이기 때문이다.
공유자원원인 버퍼를 상호배타적으로 접근할 수 있도록 설정해줘야 한다.

Conclusion

오늘은 몇 가지 mutex를 위한 알고리즘들을 알아 보았다.
2장에서는 몇 가지 더욱 중요한 알고리즘을 살펴보도록 하자!!