동기화와 교착상태

1. 프로세스 동기화

• 운영체제가 제공하는 동기화의 의미
  1. 실행 순서 제어: 프로세스를 올바른 순서로 실행하기
  2. 상호 배제: 동시에 접근해서는 안되는 자원에 하나만 접근하기
• 동시에 실행되는 프로세스 예제 1
  1. Book.txt가 없다면 파일을 만들고 값을 쓰고 저장하는 프로세스
  2. Book.txt를 읽어들이는 프로세스
     > 2번은 Book.txt가 없을 경우 실행할 수 없다. 따라서 1 => 2번 순서로 넘어가는게 맞다.
• 동시에 실행되는 프로세스 예제 2
  1. 2만원 입금 프로세스
     • 잔액을 읽어들인다.
     • 잔액에 2만원을 더한다.
     • 더한 값을 저장한다.
  2. 5만원 입금 프로세스
     • 잔액을 읽어들인다.
     • 잔액에 5만원을 더한다.
     • 더한 값을 저장한다.
       > 중간에 잔액이란 자원에 접근하는 프로세스를 순차적으로 진행하지 않는다면 원하는 결과인 17만원을 얻지 못한다. 이때 필요한게 프로세스 동기화이다.
• 문제의 근본적인 발생 원인
  • 동시에 접근해서는 안되는 자원에 접근을 동시에 했다.
  • 상호 배제를 위한 동기화가 이루어지지 않았다.
• 공유 자원과 임계 구역
  • 공유 자원: 공동의 자원 (e.g. 파일, 전역 변수, 입출력장치, ...)
  • 임계 구역: 동시에 접근하면 문제가 발생할 수 있는 공유 자원에 접근하는 코드

• 레이스 컨디션(race condition)
  • 임계 구역을 동시에 실행하여 자원의 일관성이 깨지는 현상

2. 뮤텍스 락과 세마포

• 동기화 해결의 세 가지 원칙
  1. 상호 배제: 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 대기해야 함
  2. 진행: 어떤 프로세스도 임계 구역에 진입하지 않았다면 진입이 가능해야 함
  3. 유한 대기: 한 프로세스가 임계 구역 진입을 위해 대기하고 있다면 언젠간 진입이 가능해야 함
• 뮤텍스 락: 상호 배제를 위한 동기화 도구 (기본적으로 공유 자원이 하나일 경우 상정) 
  • 자물쇠 역할: 프로세스들이 공유하는 전역변수 lock
  • 자물쇠 잠그기: acquire 함수
  • 자물쇠 열기: release 함수
• 세마포: 상호 배제 & 실행 순서 제어를 위한 동기화 도구 (공유 자원이 여러 개 있을 경우도 동기화 가능)
  • 실행 순서 제어, 상호 배제 동기화
  • 가라는 신호 > (임계 구역) 진입 가능 ==> 먼저 실행할 프로세스 뒤에 signal
  • 멈추라는 신호 > (임계 구역) 진입 불가 ==> 나중에 실행할 프로세스 앞에 wait
    1. 변수 S: 임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수)
    2. wait 함수: 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수
    3. signal 함수: 임계 구역 앞에서 기다리는 프로세스에게 가라는 신호를 주는 함수
• 예시1

• 예시2

3. 조건 변수와 모니터

• 기존 동기화 도구 문제점
  • 세마포 누락
  • wait과 signal 순서를 헷갈린 경우
  • wait과 signal를 중복으로 사용
• 모니터: 문제점을 극복하기 위해 사용이 간편한 동기화 도구
  • 공유 자원에 접근하기 위한 인터페이스
  • 인터페이스를 통해서만 접근 (상호 배제)
  • 실행 순서 제어를 위한 동기화를 위해 조건 변수 사용
  • 프로세스 상태 전이가 가능한 특별한 변수
    • wait() : 호출한 프로세스를 대기 상태로 전환
    • signal() : 호출한 프로세스를 깨움
• 조건 변수를 활용한 실행 순서 제어
  1. 아직 실행될 조건이 되지 않았을 때에는 wait을 통해 실행 중단
  2. 실행될 조건이 충족되었을 때에는 signal을 통해 실행 재개

3. 교착 상태와 해결 방법

• 교착 상태
  • 일어나지 않을 사건(필요한 자원의 할당)을 기다리며 무한히 대기하는 현상
• 교착 상태 발생 조건
  1. 상호 배제: 동시에 자원 사용이 불가능한 경우
  2. 점유와 대기: 자원을 할당받은 채 다른 자원의 할당을 기다리는 경우
  3. 비선점: 강제로 자원을 빼앗을 수 없는 경우
  4. 원형 대기: 자원을 원형으로 대기할 경우
• 해결 방법
  1. 교착 상태 예방
     • 교착 상태 발생 조건 네 가지 중 하나를 없애는 것
       
       > 상호 배제 조건 없애기
       ==> 자원을 공유 가능하도록 변경
       ==> 모든 자원에 대해 적용할 수 없음
       
       > 점유와 대기 조건 없애기
       ==> 특정 프로세스에 자원을 모두 할당, 아예 할당하지 않기
       ==> 자원의 활용률 저하
       
       > 비선점 조건 없애기
       ==> 선점하여 사용 가능한 자원에 대해서는 효과적 (e.g. CPU)
       ==> 모든 자원에 대해 적용 가능한 것은 아님 (e.g. 프린터기)
       
       > 원형 대기 조건 없애기
       ==> 자원에 번호 매기기
       ==> 오름차순으로 자원 할당
       
       
     • 교착 상태가 발생 배경 원천 차단
     • 교착 상태가 발생하지 않음을 보장할 수 있지만, 여러 부작용이 따르는 방식
  2. 교착 상태 회피
     • 교착 상태가 발생하지 않을 정도로만 조금씩 자원을 할당하는 방법
  3. 교착 상태 검출 후 회복
     • 교착 상태가 발생하면 그때 회복하는 방식
       • 선점을 통한 회복
       • 프로세스 강제 종료를 통한 회복