[혼공단/OS] 프로세스 동기화와 교착상태

12-1 동기화란

동기화의 의미

• 여러 프로세스들은 동시에 실행되고 있다.
• 프로세스 동기화 : 프로세스 간 수행 시기를 맞추는 것. (스레드도 동기화 대상)
  • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
  • 상호 배제 : 동시에 접근해서 안 되는 자원에 하나의 프로세스만 접근토록 하기

생산자와 소비자 문제

• 생산자 : 물건을 계속 생산함
• 소비자 : 물건을 계속 소비함
• 동기화를 하지 않으면, 생산자의 작업이 끝나기 전, 소비자가 작업하거나, 반대의 상황이 발생 -> 생산과 소비의 수가 같아도 결과가 0이 아니게 됨.

공유 자원과 임계 구역

• 공유 자원 : 여러 프로세스가 같이 사용해야하는 자원
  • 전역 변수, 파일, 입출력장치, 보조기억장치 ...
• 임계 구역 : 동시에 실행하면 문제 생기는 자원에 접근하려는 코드 영역
• 레이스 컨디션 : 잘못된 실행으로 인해 여러 프로세스가 임계 구역에 접근해서 문제가 발생
  • 데이터의 일관성이 깨짐 ex. 생산 10, 소비 10 -> 결과가 0이 아님
  • 고급 언어로는 1줄 이어도, 저급 언어로 여러 줄임. 저급 언어 여러 줄이 실행되는 중 다른 프로세스로 문맥 교환이 발생할 때 문제.
• 상호 배제를 위한 동기화
  • 상호 배제 : 한 프로세스가 임계 구역 접근 중, 다른 프로세스는 접근 불가
  • 진행 : 임계 구역에 접근 중인 프로세스가 없으면, 진입하고자하는 프로세스는 진입 가능
  • 유한 대기 : 임계 구역에 접근하려는 프로세스는 언젠가 꼭 접근해야 함. (무한정 대기는 안됨)

12-2 동기화 기법

뮤텍스 락

• 임계 구역에 접근하고 있는 프로세스가 있으면, 뮤텍스 락으로 임계구역에 자물쇠를 걸어둠
• 구현
  • 자물쇠 : 프로세스들이 공유하는 전역 변수 lock
  • 임계구역 잠금 : acquire 함수
  • 임계구역 잠금 해제 : release 함수
• acquire 함수
  • 프로세스가 임계구역 진입 전에 호출
  • 임계구역이 잠겨있으면, 열릴 때까지 확인
  • 임계구역이 열려있으면, 잠금
• release 함수
  • 프로세스가 임계구역에서 작업 끝나고 호출
• acquire 함수가 계속 lock 여부를 확인함 : 바쁜 대기
  • C/C++, Python : 뮤텍스 락을 지원

세마포어 (카운팅 세마포어)

• 이진 세마포어 : 뮤텍스 락과 비슷
• 카운팅 세마포어 : 임계구역에 접근하는 프로세스의 개수를 통해 관리
• 구현
  • 임계구역에 진입 가능한 프로세스 개수 ( 사용가능한 공유자원 개수 ) 전역 변수 S
  • 임계구역 접근 가능 여부. 임계구역 진입 전 : wait 함수
    • S가 0 이하면, 가능해질 때까지 확인
    • S가 1 이상이면, S-- & 임계구역 진입
  • 기다리는 프로세스에게 접근 가능하다고 알림. 임계구역 진출 : signal 함수
    • 임계구역 작업 후, S++
  • 바쁜 대기는 CPU 주기를 낭비하므로 좋지 않음
• 대기 큐 사용
  • wait 함수에서 S--, 사용할 수 있는 자원이 없으면, 대기 큐에 넣고, 해당 프로세스를 대기 상태로 만듦.
  • signal 함수에서 S++, 대기 큐에서 프로세스를 빼고, 그 프로세스를 대기 상태에서 준비 상태로 만듦.

모니터

• 공유자원과 공유자원에 접근하기위한 인터페이스(통로)를 무껑서 관리.
  • 프로세스는 인터페이스를 통해서만 공유자원에 접근 가능
• 모니터는 인터페이스에 접근하기 위한 큐를 만듦.
  • 모니터에 하나의 프로세스만 접근하도록 하여 상호 배제를 위한 동기화
  • 조건 변수를 사용해서 프로세스 실행, 중단 제어. 실행 순서 제어를 위한 동기화
• 큐는 두 종류 존재
• 모니터에 진입하기 위해 삽입되는 큐 (상호 배제를 위한 큐)
• wait가 호출되어 실행이 중단된 프로세스들이 삽입되는 큐 (조건 변수에 대한 큐)
• 구현
  • wait 함수 : 실행 중지
  • signal 함수 : 실행 재개

13-1 교착 상태란

식사하는 철학자 문제

• 모든 철학자가 동시에 왼쪽 포크를 집어들면, 식사를 영원히 할 수 없다.
• 교착 상태 발생
  • 프로세스 A 동작 중, 프로세스 B가 사용 중인 자원을 기다리고 있고, 프로세스 B 동작 중, 프로세스 A가 사용 중인 자원을 기다림.
  • 서로 기다리느라 어느 프로세스도 동작하지 않음.

자원 할당 그래프

• 프로세스가 어떤 자원을 사용하고 있고, 기다리고 있는지 표현하는 그래프

규칙

• 프로세스는 원으로, 자원 종류는 사각형으로 표현
• 사용 가능한 자원의 수는 자원 사각형 내에 점으로 표시
  • ex. 하드디스크가 3개 있으면, 하드디스크 사각형 내에 점 3개
• 프로세스가 자원 사용 중이면, 자원(점)에서 프로세스를 향해 화살표
• 프로세스가 자원을 기다리고 있으면, 프로세스에서 자원(사각형)을 향해 화살표

교착 상태 발생 조건

상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없음

점유와 대기 : 자원을 할당 받은 상태에서 다른 자원 할당 받기를 기다리는 상태

비선점 : 다른 프로세스가 자원을 점유하록 있을 때, 강제로 자원을 빼앗지 못함

원형 대기 :순환 형태로 프로세스가 자원을 점유하고, 대기하는 모습이면 교착 발생 가능

=> 항상 발생은 아님.

13-2 교착 상태 해결 방법

교착 상태 예방

상호 배제 없애기 - 불가능

• 모든 자원을 모든 프로세스끼리 공유 가능하도록 하면, 동기화 문제 발생

점유와 대기 없애기 - 불가능

• 프로세스가 모든 자원을 할당 받도록 하거나, 아니면 아예 할당 못 받게 하기
• 자원 활용률이 낮아짐.
  • 당장 자원이 필요해도 기다려야 하는 프로세스, 당장 사용 안하면서 오랫동안 할당된 상태로 있는 자원이 발생
  • 프로세스는 동시에 자원을 사용할 타이밍 찾기가 힘듦.
  • 많은 자원 필요한 프로세스가 기아 상황이 될 수 있음.

비선점 없애기 - 일부 자원 (CPU) 에서 효과적

• 다른 프로세스가 사용하는 자원 뺏어오기
• 일부 자원에 대해 효과적
  • CPU - 선점 가능.
    • 한 프로세스가 CPU 사용하다가 사용 시간 다 되면, 다른 프로세스가 CPU 할당 받음.
• 한 번에 하나의 프로세스만 이용 가능한 자원은 빼앗으면 안됨.
  • 범용성 떨어짐

원형 대기 없애기 - 단점 존재

• 모든 자원에 번호를 붙이고 오름차순으로 자원 할당
• 수많은 자원에 번호 붙이는 작업은 복잡함. 자원의 번호에 따라 특정 자원의 활용률 떨어질 수 있음.

결론

• 교착 상태 발생 조건을 원천적으로 제거하는 방식은 부작용이 있음.

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로 자원 할당
  • 교착 상태는 자원을 무분별하게 할당해서 발생하는 것.
• 안전 상태 : 교착 상태 없이 모든 프로세스가 정상적으로 자원 할당 받고 종료할 수 있는 상태. 안전 순서열대로 프로세스들에게 자원 배분
• 불안전 상태 : 교착 상태가 발생할 수 있는 상황. 안전 순서열이 없음
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스에게 자원을 할당할 수 있는 순서

교착 상태 검출 후 회복

• 교착 상태를 인정하고, 사후에 조치
• 운영체제는 프로세스가 자원 요구할 때마다 자원 할당, 교착 상태 여부 주기적 검사, 다음의 방식으로 조치

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아 줌 - 다른 프로세스로부터 자원을 뺏어서

프로세스 강제 종료를 통한 회복 - 단순&확실

• 교착 상태의 프로세스를 모두 강제 종료 - 작업 내용 잃을 수 있음
• 교착 상태가 없어질 때까지 하나씩 프로세스 강제 종료 - 교착 상태 없어졌는지 확인하는 과정에서 오버헤드 발생
• 타조 알고리즘 : 교착 상태를 아예 무시하기

필수미션

p. 363의 확인 문제 1번 풀고 인증하기

뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것을 고르시오.

⇒ 4. 세마포를 이용하면 반드시 바쁜 대기를 해야한다.

선택미션

Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기

⇒ 본문에 기재!