운영체제 강의 18

1. Initial Attempts to Solve Problem

‣ 두 개의 프로세스가 있다고 가정

프로세스들의 일반적인 구조

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

 

---

 

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

✓ Mutual Exclusion (상호 배제)

       : 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다

 

✓ Progress (진행)

       : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다

 

✓ Bounded Waiting (유한대기)

       : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

 

◎ 가정

       • 모든 프로세스의 수행 속도는 0보다 크다

       • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다

 

---

 

📌 Algorithm 1

• Synchronization variable

         int turn;

Satisfies mutual exclusion, but not progress

즉, 과잉양보 : 반드시 한번씩 교대로 들어가야만 함

                      그가 turn을 내값으로 바꿔줘야만 내가 들어갈 수 있음

                      특정 프로세스가 더 빈번히 critical section을 들어가야 한다면?

 

📌 Algorithm 2

• Synchronization variables

         boolean flag[2];

Satisfies mutual exclusion, but not progress requirement

둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능 (CPU를 critical section 앞에서 뺏긴 경우)

 

📌 Algorithm 3 (Peterson's Algorithm)

• Combined synchronization variables of algorithms 1 and 2

Meets all three requirements;

Busy Waiting = spin lock (계속 CPU와 memory를 쓰면서 wait)