[운영체제] Synchronization (2) - Spin lock, Busy waiting, Test-And-Set, Compare-And-Swap

Spinlock

• 잡으려는 lock이 avaliable 해 질 때 까지 계속 루프를 돌며 진입을 재시도한다.

• 이른바 바쁘게 기다리는 busy waiting의 한 종류이다.

  Busy waiting

  lock을 잡기 위해 다른 작업을 수행하지 않고 계속해서 기다리는 경우

---

Sofrware-only Algorithm

Peterson's Algorithm

• 동기화 문제를 해결하기 위해 처음으로 고안된 방법
• 오직 두개의 context만이 존재하는 상황을 가정한다.
• 전역변수 flag, turn 선언
  flag: critical section에 들어갈 준비가 되었는지
  turn: 누가 critical section에 들어갈 차례인지

문제점

• 두개의 context만 존재하는 상황에서만 가능
• atomic하지 않은 아키텍쳐에서 사용 불가능

Hardware Approaches

Disabling Interrupts

• 인터럽트 끄고 키는 것은 instruction으로 되어 있는데, priviliged instruction이므로 커널 모드에서 실행해야 한다. 이를 위해서는 운영체제를 호출해야 한다.

문제점

• 싱글 프로세스에서만 가능
• 멀티 코어 환경에서 적용하기 힘듬
• 운영체제 호출에 대한 cost 비용 증가

---

하드웨어적인 해결방법 2가지

Test-And-Set

• Atomic instruction을 제공. 하나의 명령어로 수행.
• 한개의 인스트럭션으로 새로운 값을 쓰고 옛날 값 리턴되는 것이 한번에 일어난다.
• 완전히 동시에 들어와도 하드웨어 수준에서 먼저 들어온 것이 결정되고 걔는 무조건 lock을 잡는다.
• 값이 return되는 것을 test 결과라고 보기에 test and set인 것이다.
• 옛날 거를 test 하도록 가져오고 새로운 값으로 set해라.

Compare-And-Swap

• Atomic instruction을 제공. 하나의 명령어로 수행
• condition을 줘서 예상하는 값이면 새롭게 바꾸고, 그렇지 않으면 옛날 값 return해라.