OS: Synchronization

Synchronization Terminology

• Synchronization(동기화): Use Atomic Operation, 실행순서를 세세하게 조정하여 두 스레드가 상호작용함에 있어서 공유자원에 대한 접근을 조절, 데이터의 일관성을 보장
• Mutual Exclusion(상호배제): Only one thread at a time, 동시에 공유자원에 접근하는것을 막기 위한 기법, 한번에 하나의 스레드만 공유자원에 접근하는것을 허용
• Critical Section(임계영역): Part of code that modifies shared data, 공유자원에 접근하는 코드의 영역으로 한번에 한 스레드만 실행
• Lock(락): Prevent other thread from doing something, 상호배제를 구현하는 메커니즘, 락 요청시 스레드는 대기하거난 블록상태.
  • Critical Section에 들어가기 전 lock
  • Critical Section에 나올때 unlock

Enforcing Mutual Exclusion

Mutual Exclusion 의 방법으로는 다음이 있다

• up to user: 사용자에게 권한이 주어져 시스템의 동작을 직접 제어.
• up to OS: 운영체제가 시스템의 동작을 제어, 사용자는 OS 가 제공하는 인터페이스를 사용하여 자원요청, 운영체제는 이를 관리 및 스케쥴링
• up to hardware: 하드웨어가 시스템의 동작을 제어.
• Mutual Exclution을 실행하는 해결책은 다음 사항을 지켜야 한다
  • Avoid Starvation: 스레드가 critical section에 접근하려고 할시, 종국에는 접근에 성공하여야 한다
  • Avoid Deadlock: 여러 스레드가 동시에 critical section 에 접근 시도시 최소 하나는 성공하여야 한다
• Mutual Exclusion Algorithm은 다음으로 평가된다 - progress, bounded waiting, mutual exclusion

Mutual Exclusion Algorithm 1

• 가정: 칠판이 있는 igloo, 한번에 한 사람(스레드)만 igloo 내에 있을 수 있다, igloo 내에 칠판은 하나의 숫자만 쓸 수 있다
• Critical Section 에 접근하고 싶은 스레드가 igloo에 들어가 칠판을 확인한다.
• 본인의 숫자가 칠판에 적혀있지 않으면 바깥으로 나간다.
  • 차후에 다시 돌아와 확인
  • 'busy waiting' --> 실행 될 때 까지
• 본인의 숫자가 칠판에 적혀있다면 igloo를 떠나 critical section 에 접근
• Critical section 에서 복귀 했을때, 다른 숫자를 칠판에 적는다
•  

Algorithm 1

Mutual Exclusion Algorithm 2a

• 가정: 각 사람(스레드)가 각자의 igloo를 보유하고 있다, 각 스레드가 각자의 칠판을 확인하고 변경할 수 있다. 스레드는 다른 스레드의 칠판을 확인할 수 있지만 변경은 불가, 칠판에 'true'가 적혀있을시 critical section 접근
• Critical Section 에 접근하고 싶은 스레드는 다른 스레드의 igloo에 들어가 칠판을 확인한다.
  • 'false'가 적혀있을시, 본인의 igloo로 돌아가서 칠판을 true 로 바꾼 뒤 critical section에 접근한다
• Critical Section 에서 복귀시 본인의 칠판을 'false'로 변경

Algorithm 2a

Algorithm 2b

Mutual Exclusion Algorithm 3(Peterson's Algorithm)

• 가정: 어떤 스레드의 순서인지를 기록하고있는 '심판' 존재
• 두 스레드가 critical section 에 접근하려고 할 시에, 심판에게 물어봄
• n 개의 프로세스에 대해서는 Lamport's Bakery Algorithm
  • Critical section 에 들어가려고 할 때에, 숫자를 받는데, 이 숫자는 critical section 에 들어가려는 프로세스중 가장 높은수
  • 가장 낮은 수를 가지고 있는 스레드가 들어가게된다
  • 두 스레드가 만약 같은 숫자를 부여받을 경우 PID가 낮은 순서로 들어간다

 

Semaphore

• Dijkstra가 1965년도에 만들어낸 locking 메커니즘이다.
• 가정: 하나의 igloo에 칠판과 엄청 큰 냉동고
  • wait - 스레드가 igloo에 들어가 칠판 확인후 value decrement
    • 칠판의 값이 0이면 스레드는 critical section 에 들어간다
    • 칠판의 값이 음수라면 스레드는 냉동고에 들어가 동면(다른 스레드가 igloo에 들어올 공간)
  • signal - 스레드가 igloo에 들어와 value increment
    • 칠판의 값이 0이나 음수라면 냉동고에 스레드가 있으니 꺼내서 critical section 으로
• 두가지의 atomic operation 을 진행한다 -> P/wait, V/signal
  
  • Semaphore 은 1로 초기화
  • Critical section 에 들어가기 전, 스레드는 P(semaphore) 나 wait(semaphore)를 호출한다
    • wait(s)
      • s = s-1
      • if(s<0): block the thread that called wait(s) on a queue associated with semaphore s
      • else: let the thread that called wait(s) continue into the critical section
  • Critical section에서 떠나기 전 스레드는 V(semaphore) 나 signal(semaphore)를 호출
    • signal(s)
      • s = s+1
      • if(s<=0): wake up one of the threads that called wait(s), and run it

Semaphore Algorithm

• Semaphore Values
  • Positive Semaphore: Critical Section에 들어올 수 있는 스레드의 수
  • Negative Semaphore: Blocked 되어있는 스레드의 수
  • Binary semaphore는 초기 값이 1
  • Counting semaphore은 초기 값이 1보다 큰 수

ex) t1, t2 동시 접근

1. t1 접근, s = 1 -> s= 0

2. t2가 접근 s = 0 -> s = -1 --> 리소스 x, 누군가 깨울때까지 waiting 벼뎓

3. t1이 코드 수행 후 queue 확인, sleep 중인 2 깨움

4. t1 이 코드 수행 후 리소스 반납(s= -1 --> s= 0), t2가 critical section 접근 

5. t2가 코드 수행 후 리소스 반납(s = 0 --> s = 1)