Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

• 프로세스들은 수행의 동기화(synchronize) 를 위해 몇몇 변수를 공유할 수 있다. → synchronization variable

프로그램적 해결법의 충족 조건

• Mutual Exclusion(상호 배제) : 프로세스 Pi 가 ciritical section 부분을 수행 중이면 다른 프로세스들은 그들의 critical section 에 들어가면 안된다
• Progress(진행) : 아무도 critical section 에 있지 않은 상태에서 critical section 에 들어가고자 하는 프로세스가 있으면 critical section 에 들어가게 해주어야 한다
• Bounded Waiting(유한 대기) : 프로세스가 critical section 에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야 한다
• 가정
  • 모든 프로세스의 수행 속도는 0보다 크다
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다

Algorithm 1

• 과잉양보 : 반드시 한번씩 교대로 들어가야만 함(swap-turn). 그가 turn 을 내 값으로 바꿔줘야만 내가 들어갈 수 있음. 특정 프로세스가 더 빈번히 critical section 에 들어가야 한다면?

⇒ Mutual Exclusion 은 만족함, Progress 는 만족하지 못함

Algorithm 2

• 둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능

⇒ Mutual Exclusion 은 만족함, Progress 는 만족하지 못함

Algorithm 3(Peterson’s Algorithm)