[OS]CH6. 프로세스 동기화(Synchronization) & 상호배제(Mutual Exclusion)

본 글은 HPC Lab의 youtube 강의를 듣고 요약한 것입니다. 모든 이미지 출처 역시 HPC Lab의 pdf 수업자료입니다.

 

다중 프로그래밍 시스템이란?

---

시스템 내에 여러 개의 프로세스들이 존재하는 것

• 공유 자원 또는 데이터가 있을 때, 동기화와 관련된 문제 발생 가능

 

프로세스 동기화란?

---

프로세스들이 서로 정보를 공유해 공유 데이터에 관한 동작을 맞추는 것

 

Critical section(임계영역)

---

공유 데이터에 접근하는 코드 영역

• Race condition : 둘 이상의 프로세스의 공유 데이터에 대한 접근 순서에 따라 결과가 달라지는 현상(경쟁한다는 의미에서 race)

Race condition

 

Mutual Exclusion(상호배제)

---

둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

Mutual exclusion을 보장하기 위해선 다음의 세 가지 조건이 충족되어야 한다.

• Mutual exclusion(상호배제) : CS에 작업 중인 프로세스가 있으면, 다른 프로세스의 진입 금지
• Progress(진행) : CS 안의 프로세스 외에는 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
• Bounded wait(한정대기) : 프로세스의 CS 진입은 유한시간 내에 허용되야 함

 

Mutual Exclusion Solutions

---

1. SW solutions
   • Peterson's algorithm(다른 것도 많지만 이정도만 알아도 충분...중요한 것은 3번!)
2. HW solutions
   
   • Test-and-Set(TAS) instruction
3. OS supported SW solution
   • Mutex(Spinlock)
   • Semaphore
4. Language-level solution
   • Monitor

 

Peterson's algorithm

---

• 두 프로세스는 turn, flag라는 두 변수 공유
• turn은 CS에 누가 들어갈 차례인지를, flag는 프로세스가 CS에 들어갈 준비가 되었는지를 나타냄(flag[i] == True면 Process i가 ready)
• ME의 세 조건 모두 만족

• 단점
  • Busy waiting : 기다리면서 계속 반복문 돌고 있다 -> inefficient
  • 구현이 복잡

 

HW solution - TAS instruction

---

• test와 set을 한 번에 수행하는 기계어(machine instruction)
• 기계어이므로 atomic하다 -> 실행 중 interrupt를 받지 않음(즉, preemption되지 않음)
• 역시 Busy waiting이라는 단점 존재
• 3개 이상의 프로세스의 경우, Bounded wait 조건 위배

TAS instuction

TAS 사용 예시

 

Mutex(뮤텍스)

---

• acquire() lock과 release() lock이라는 두 기본연산 사용(lock이라는 key를 가지고 공유자원 관리)
  • 두 연산은 atomic
• 뮤텍스는 정수변수
• Busy waiting

다음과 같이 P,V로 나타내기도 한다.

 

Semaphore(세마포)

---

• wait()(혹은 P())와 signal()(혹은 V())이라는 두 기본연산 사용
  • 두 연산은 atomic

• Busy waiting
• 세마포 S - 정수 변수
  • Binary semaphor : S가 0과 1 두 값만 가짐(Mutex와 유사)
  • Counting semaphore : S가 0 이상의 정수값 가짐
• Mutex는 locking mechanism(lock에 대한 소유권이 있는 프로세스만 진입 가능), Semaphore는 signaling mechanism이다.

 

Semaphore with no busy waiting

---

• 각 세마포마다 waiting queue가 존재(queue를 도입함으로 busy waiting 해결)
• wait(), signal()안에 block(), wakeup() 연산 사용
  • block() : 프로세스를 waiting queue에 넣음
  • wakeup() : 프로세스를 waiting queue에서 지우고 ready queue에 추가

 

Deadlock(교착상태)과 Starvation(기아상태)

---

• Deadlock : 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리면서 다음 단계로 진행하지 못하는 상황 -> 여러 프로세스가 부족한 동일 자원 점유를 요청할 때 발생
• Starvation : 특정 프로세스가 계속 자원을 할당받지 못하는 상태 Ex) Reader-Writer 문제에서 Reader가 여러 개의 reader가 계속 들어오면 writer가 자원을 쓸 수 없음

Semaphore 사용 시 Deadlock 예시

• Semaphore는 Deadlock, Starvation이 모두 발생 가능하다. -> 그래서 나온 해결책이 Monitor

 

고전적인 동기화 문제들

---

1. Bounded-buffer problem
2. Readers-Writer problem
3. Dining-Philosophers problem