Synchronization Tool

Synchronization Issue

MultiProcess & MultiThread

• 멀티프로세스나 멀티쓰레드에서 공유 자원이 있음
  (message queue or shared memory)
• 프로세스나 쓰레드가 이 자원을 잘 사용하다가 중간에 갑자기 context swtich가 되면 Synchronization Issue가 발생

Example

같은 계좌에서 한 명은 ATM기에서 출금하고, 다른 한 명은 어플로 출금할 때:돈을 빼고 뺀 값을 저장하는데 뺀 값을 저장하기 전에 context swtich가 일어나면 돈이 복사가 됨

Producer Consumer 구조에서 Bounded buffer Issue가 발생할 때:
버퍼에 저장하면 count++, 읽으면 count—하는데 후위연산자 자체를 어셈블리어로 보면, temp = count, temp = temp + 1, count = temp라서 그 사이에 context swtich가 일어나면 Issue 발생

결국 한 행동이 한 덩어리의 움직임이 아니라 여러 가지의 행동을 합친 행동이라서 행동하는 사이에 context swtich가 일어나 Synchronization Issue가 발생

Problem

• 두 개 이상의 프로세스나 쓰레드가 같은 공유 메모리를 사용할 때 발생

• Race Condition

  • Synchronization Issue가 일어나는 이 상황
  • non-deterministic(어쩌다 한번 일어남)

• Critical Section

  • 이 Race Condition이 일어날 수 있는 소스코드의 영역

• 한 덩어리의 움직임이 아니라서 일어나는 것이기 때문에
  이를 한 덩어리로 뭉치는 방법이 해결책

Synchronization Tools

Requirements for Synchronization Tools

1. Mutual Exclusion (Mutex)
   상호배타적! 공유 자원에 접근하는 것들은 무조건 하나여야 하는 조건

2. Progress
   Critical Section을 실행하는 자가 아무도 없으면 기다림 없이 바로 사용

3. Bounded Waiting
   Critical Section을 실행하기 위해 기다리는 시간이 유한적

• 1번을 지키면 2, 3번은 부수적으로 따라옴

Synchronization Tools

• Locks
  low level단에서 접근하지 못하도록 전역변수를 통해 조건문을 다룸

• Mutex lock(blocked lock)
  Locks에서 조금 추가한 것

• Semaphores
  Lock기능을 응용해 만든 것

• Monitors
  자바에서 만든 것처럼 high level, 컴파일러들이 Lock Unlock을 관리

• Messages
  distributed systems(분산 시스템)에서 쓰므로 일반적으로는 잘 안씀

Low Level

Locks

• lock(), unlock(): 아무도 못 쓰게 자물쇠를 잠구고, 다 사용했으면 푼다는 뜻

• spinlock: lock에서 while(l->held);를 통해 held가 1이라면 while문 안에서 갇혀 뱅글뱅글 돈다고 해서 spinlock, unlock은 l->held = 0으로 설정하면서 다른 프로세스가 while문을 빠져나오도록 함

• 하지만 held 또한 전역변수 공유자원이고 held = 1, held = 0같은 선언문조차도 어셈블리어로 보면 여러 단계로 나뉘어져있어서 중간에 context swtich가 일어날 경우 똑같은 문제 발생

Solution

앞에서 말했지만 여러단계의 행동을 최소단위 한 덩어리로 만들면 됨

• Software-only algorithms
  알고리즘 1, 2, 3이라는 소프트웨어로 구현된 알고리즘을 사용하지만 high level에다가 오버헤드가 크기 때문에 잘 쓰지 않는 방식

• Hardware atomic instructions
  instruction을 atomic하게 한 큐에 최소단위로 처리

• Test-and-set(대체로 많이씀)
  RISC인데도 CISC처럼 한 덩어리의 instruction으로 설계

• compare-and-swap(인텔기반에서 씀)
  Test and set이랑 비슷한데 변수 한 개 더 있는 차이

• Disable/re-enable interrupts
  그냥 interrupt 기능을 비활성화하면 context swtich가 일어나지 않음

Problem

• 다른 프로세스는 계속 busy-waiting(spinlock이 걸림)중이라 자원 낭비↑
  -lock으로 대기 시 busy-waiting이 아닌 일반 waiting이나 sleeping상태여야함

Disabling Intterupts – Blocking Lock

• cli(), sti(): 인터럽트를 비활성화, 활성화 함으로써 context swtich가 일어나지 않도록 미연에 방지
• 인터럽트 기능을 끈다는 것은 timer 인터럽트나, I/O 인터럽트등 커널이 관장하는 다양한 기능을 잠시 포기하는 것과도 말이 같아서, High Level에서 사용시 매우 주의해야함

High Level

Semaphore

• Semaphore라는 전역변수가 있는데 이안에 정수 count를 사용해 접근하는 쓰레드 수를 counting
• wait(): count가 1이라면 계속 기다리고(busy-waiting아닌 sleep상태) 0이라면 실행하며 1로 설정
• signal(): count를 1로 설정해섯 티켓을 반납

Binary Semaphore

count가 1또는 0이어서 Binary 라고 부름

Counting Semaphore

정수형이어서 여러개의 쓰레드가 동시사용가능해서 Mutex하지 않음

Mutex lock(Binary Semaphore)

• 기존의 low level의 lock(), unlock()와 유사한 wait(), signal()
• Binary Semaphore이라서 count를 1개만 최대로 사용가능
• 두 프로세스가 서로 상호배타적이라 Mutex lock이라 부름
• Semaphore 구조체는 count값에 해당하는 value와, 기다리는 process를 저장하는 list

Deadlock

여러 프로세스가 서로 wait()를 하다가 꼬여서 서로를 기다리는 상황

Monitors

자바에서만 쓰이는 컴파일러에서 자체적으로 lock, unlock의 기능을 제공

• procedure body P1~ Pn사이의 프로시저에서 동시에 단 하나만 사용 가능
• P1이 어떤 프로세스나 쓰레드가 사용하고 있으면 다른 프로세스나 쓰레드에서 P2~Pn을 사용하려고 할 때 자바가 자동으로 막음
• 하지만 Bounded Buffer상황에서 Producer가 이미 Buffer가 찼는데 한 번 더 호출되어 busy waiting에 갇히게 되고, 그 상황에서 Consumer이 호출되면 Consumer또한 무한 대기를 하게 되어 DeadLock

Condition Variable

• 새로운 x, y condition 변수를 추가해서 프로세스가 무언가의 조건에 걸려 waiting되면 x에 추가가 되고 다른 프로세스가 signal()을 주면 x에 걸린 프로세스를 재실행한다
• 기존의 semaphore은 아무도 waiting상태가 아닐 때, signal()을 하면, Semaphore의 값이 1 증가해서 history가 있고 stateful
• Condition Variable + Monitor은 아무도 waiting상태가 아닐 때, signal()을 하면 아무 동작을 하지 않아서 history가 없어서 stateless