동기화

• 공유 데이터 접근 순서를 정하는 방법 → Race condition으로 인한 Data inconsistency가 일어나지 않도록 방지
• 스레드 프로그래밍, 공유 메모리, 커널 스레드를 위한 동기화 필요

동기화의 정의

• 여러 개의 프로세스가 있을 때 각 프로세스는 critical section(공유 데이터를 변경하는 부분)를 가지고 있음
• critical section → 한 번에 하나의 프로세스만 진입 가능
  
• 각 프로세스는 critical section에 들어갈 때 "어떻게" 들어갈 수 있고 "어떻게" 나오는지 entry section + exit section을 통해 표시 → 이후 remainder section을 통해 표시

Producer and Consumer

• 생산자: Critical section 진입 시 버퍼 IN에 생성한 값 입력
• 소비자: 소비한 buffer[out]을 다음 소비할 next_consumed에 할당

한 번에 하나의 프로세스만 Critical Section에 들어가도록 하자! 하지만 몇 가지 조건이 더 있다.

Critical Section Solution

1. Mutual Exclusion

• 프로세스 A가 Critical Section에 있다면 다른 모든 프로세스는 진입 X

2. Progress

• Critical section에 진입하려는 프로세스가 여러 개 있다면 이들 중 하나는 결국 나중에 Critical section에 진입할 수 있어야 함

3. Bounded waiting

• 특정 프로세스가 ciritical section에 진입할 때까지 걸리는 시간에는 한계 시간이 존재해야 함(무한 wait를 방지하기 위함)

알고리즘: ME

• 공유 변수: 정수 turn이 0이면 프로세스 0이 진입 가능
• ME: 만족. 한 번에 하나의 프로세스만 ciritical section에 진입할 수 있음
• Progress: 만족 X - 두 프로세스 수행 순서가 반복(alternate)하지 않다면 수행 X. 프로세스 0 → 프로세스 0 → 프로세스 0 수행될 때 두 번째 프로세스 0부터 멈추게 됨
• Bounded waiting: 만족 X - 무한정 대기하게 되는 프로세스 존재

개선 알고리즘: ME

• 불리언 변수 flag 사용, 0 인덱스가 참이면 프로세스 0이, 1 인덱스가 참이면 프로세스 1이 진입 가능
• ME: 만족
• Progress: 두 프로세스가 동시에 flag를 참으로 변경할 수 있기 때문에 모두 진입하지 못하는 경우가 있음
• Bounded waiting: 무한정 대기하게 되는 경우는 고려 X

Progress가 만족된다고 해서 bounded waiting이 보장된다고 할 수는 없다. 하지만 progress가 만족되지 못한다면, bounded waiting은 당연히 보장되지 않는다!

Peterson solution: ME, P, BW

• 위 두 가지 알고리즘에서 적용한 turn, flag 공유 변수를 모두 사용한다면 동기화 문제를 해결 가능
• ME: 만족
• Progress: 모든 플래그 값이 참이더라도 turn에 의해 특정 프로세스가 진입 가능한지 결정되기 때문에 만족. 플래그 값과 turn 값 두 조건에 따라서 대기가 결정

3개 이상의 프로세스에서는 Peterson solution을 적용하기 힘듦. NP-hard 문제이기 때문!

동기화 해결책

• Critical section에 들어가면서 인터럽트를 불가능하도록 설정 → 프로세스의 원하지 않는 종료를 방지하기 위함
• 커널을 critical section으로 만들기: 프로세스 수가 늘어날 경우 인터럽트 대기 시간이 늘어날 수 있음, 커널 멀티 스레딩 현상
• 확장성 문제: 프로세스 숫자가 많아질 때 문제가 생길 수 있음. 커널 멀티 스레딩 도입
• HW 지원: 인터럽트가 아닌 다른 해결책 → HW 명령어를 통한 접근 필요. lock을 할당받고 해제하는 과정을 통해 쉽게 해결 가능 → 동기화를 위한 인스트럭션

동기화 명령어

• CPU에서 원자적(atomic)으로 수행되는 명령어 → 명령어가 수행되는 동안은 uninterruptible

Peterson Solution + Test and Set

• lock을 검사하고 설정하는 함수를 통해 critical section 진입 여부 결정 가능
• TestAndSet 프로세스는 원자적 명령어이기 때문에 uninterruptible. 한 번에 하나의 프로세스만 lock을 얻지 못함
• ME: 만족
• Progress: 만족
• Bounded waiting: 구체적 구현을 통해 해결 가능

Compare and Swap

• 처음에 전달받은 값을 상황에 따라 리턴: expected 조건 하에서만 변수 값 변경 가능
• lock을 얻고 critical section에서 빠져나오면 다시 lock 값을 0으로 설정해야 함
• 동기화 조건 만족

CPU 명령어를 통해 동기화 조건을 손쉽게 만족 가능!

HW 명령어의 한계

• Bounded waiting: 문제마다 차이가 있기 때문에 사용자 프로그램에서 처리하기 어려움. 동기화 primitive가 필요한 까닭

  세마포어와 같은 보다 복합적인 해결책이 필요하다!