프로세스 동기화(1)

Process Synchronization

• 공유 데이터의 동시 접근(nonatomic)은 데이터의 불일치 문제를 발생 시킬 수 있다 -> Race Condition

• Race Condition을 막기 위해서는 concurrent process는 동기화 되어야 한다

Critical Section

• 공유 데이터에 접근하는 코드
• 프로세스 1의 ‘X=X+1’, 프로세스 2의 ‘X=X-1’

Critical Section Problem

• 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어가 수 없어야 한다

Critical Section Solution

1. Mutial Exclusion (상호 배제)
   • 프로세스 P(i)가 critical section을 수행 중이면 다른 모든 프로세스들은 critical section에 들어가서는 안된다
2. Progress (진행)
   • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다
3. Bounded Waiting (유한대기)
   • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

1. turn variable 을 사용한다

   • 상호배제조건은 만족하지만 진행조건은 만족하지 못한다

   • 과잉양보 - 반드시 한번씩 교대로 들어가야한다.

   • 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면?
     특정 프로세스는 critical section에 접근하지 않는다면?

1. interest(flag) variable을 사용한다

   • critical section에 들어가고 싶은 프로세스는 flag variable로 의사표현을 한다

   • 상호배제조건은 만족하지만 진행조건은 만족하지 못한다
   • 데드락 발생가능하다 ( 둘다 1행까지 수행 후 끊임 없이 양보한다 )

1. Peterson’s Algorithm을 사용한다

• turn variable, flag variable 알고리즘을 합친 것
• 모든 조건을 충족하지만 busy waiting이 발생할 수 있다

1. Test & Set Lock을 사용한다

• 하드웨어적으로 Test&Set을 Atomic하게 수행하도록 지원한다

• Test-and-Set(lock)이 호출되면 Atomic하게 lock의 값(0 또는 1)을 읽고 1로 set 해준다

• lock의 초기값은 0이므로 처음 호출한 프로세스가 진입하고 작업이 완료되면 lock=0으로 set 해줘서 다른 프로세스가 critical section에 접근할 수 있도록 만들어준다

  

ref. KOCW

ref. turn variable

ref. interest variable

ref. peterson’s algorithm