운영체제 6장

• 핵심 내용 및 예상 질문

  뮤텍스, 세마포어가 뭔지, 차이점은?

  Race Condition이란?
  

---

6.1 배경

• 프로세스가 병렬로 실행될 수 있다는 것은(비동기) 데이터 일관성 유지에 문제가 생긴다는 것을 의미
  • 두 개 이상 프로세스가 동시에 데이터를 조작하는 예: 생산자 - 소비자 문제
• race condition

  두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓸 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황

  • 용어 그대로 경쟁하는 상태!

• 협력적 프로세스들의 질서 있는 실행을 보장하여 데이터 일관성을 유지하는 다양한 메커니즘 논의
  • race condition을 방지하기 위해 한 순간에 하나의 프로세스 만이 변수를 조작하도록 보장!
  • 프로세스 동기화 필요

6.2 Critical section: 임계구역

한 순간 반드시 프로세스 하나만 진입해야 하는데, 프로그램에서 임계 자원을 이용하는 부분으로 공유 자원의 독점을 보장하는 코드 영역을 의미

• 임계 구역은 지정된 시간이 지난 후 종료된다.
• 한 프로세스가 임계구역에 수행하는 동안 다른 프로세스들은 그들의 임계구역에 들어갈 수 없음
• 임계 구역 문제 해결안
  1. mutual exclusion: 상호 배제
     • 프로세스 a가 실행된다면 다른 프로세스들은 임계구역에서 실행될 수 없음
  2. progress: 진행
     • 현재 임계구역에 실행 중인 프로세스가 없고, 임계구역으로 진입하고자 하는 프로세스들 중에 하나가 임계 구역에 진입해야 함
  3. bounded waiting
     • 임계구역에 진입하고자 하는 프로세스의 무한한 대기가 없어야 함

• OS에서 임계구역을 다루기 위해 선점형, 비선점형 커널의 접근법이 있음
  • 선점형: 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용
  • 비선점형: 커널 모드에서 프로세스의 선점 허용 X, 커널을 빠져나거나 봉쇄될 때까지 계속 수행 → 일반적으로 선호되는 것은 선점형 커널: 프로세스가 오랫동안 실행할 위험이 적고, 실시간 프로세스에 적합
    

6.3 Peterson's Solution

mutual exclusion, progress, bounded waiting의 요구조건을 중점으로 다루는 해결책

• 임계구역과 나머지 구역을 번갈아 가며 실행하는 두개의 프로세스로 한정
• 두개의 process가 두개의 데이터 항목을 공유하도록 하여 해결

int turn; // 임계구역으로 진입할 순번
// turn == 1이면 P(1)이 임계구역에서 실행할 수 있음을 의미
boolean flag[2]; // 프로세스가 임계구역에 진입할 준비 유무 
// flag[1] == true이면 P(1)은 임계구역으로 진입할 준비가 됨을 의미

do {
  flag[i] = true;
  turn = j;
  while (flag[j] && turn == j);
  // Critical section
  flag[i] = false;
  // Remainder section
} while(true);

6.4 하드웨어를 위한 동기화 기법

• test_and_set, compared_and_swap

6.5 Mutex Locks

여러 스레드가 공통 리소스에 접근하는 것을 제어하는 기법 (Mutual Exclusion)

• 모든 프로세스는 critical section에 들어가기 위해 lock을 획득해야 함
• critical section에 빠져나올 때 반환

while(true){
	acquire lock
    critical section

    release lock
    remainder section
}

• 단점
  • Busy waiting lock을 얻지 못해 critical section에 들어가지 못하는 동안 acquire 함수 내에서 while 문을 계속 돌고 있어야 함
    

6.6 Semaphores

동일한 공통 리소스에 접근하는 것을 제어하는 기법 (lock : Boolean 값, Semaphore: Integer 값)

• wait() : 자원을 사용할 때, semaphores 감소
• signal() : 자원을 반납할 때 사용, semaphores 증가
• Semaphores가 0이면 모든 자원이 사용 중임을 나타냄
• 종류
  • Counting Semaphore: Integer 값을 모두 사용, 여러 프로세스에 제한된 양의 resource 할당할 때 유용
  • Binary Semaphore: 0과 1 값만 사용하여 Mutex Lock과 거의 동일

6.8 Deadlock and Starvation on semaphore

한 세트 내의 모든 프로세스들이 동일한 세트 내의 다른 프로세스들로 인해 발생할 수 있는 이벤트를 기다리고 있어 결국 어떤 프로세스도 실행되지 못하는 상태

• Deadlock 예: 생산자 - Dining-Philosophers Problem