[혼공컴운] 5주차 Chapter 12~13

기본 미션

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

1. 뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것을 고르세요.
① 뮤텍스 락은 임계 구역을 잠근 뒤 임계 구역에 진입함으로써 상호 배제를 위한 동기화를 이룹니다.
② 세마포는 공유 자원이 여러 개 있는 상황에서도 이용할 수 있습니다.
③ 세마포를 이용해 프로세스 실행 순서 제어를 위한 동기화도 이룰 수 있습니다.
④ 세마포를 이용하면 반드시 바쁜 대기를 해야 합니다.

정답: ④
반드시 바쁜 대기를 할 필요는 없고, 대기 상태로 접어들게 할 수 있음

선택 미션

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

임계 구역: 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역을 의미. 임계 구역에 진입한 프로세스가 있다면 다른 프로세스는 임계 구역 밖에서 기다려야 함

상호 배제: 한 프로세스가 임계 구역에서 작업 중이면 다른 프로세스가 임계 구역에 들어갈 수 없도록 제어하는 것

내용 정리

12-1. 동기화란

• 동기화: 특정 자원에 접근할 때 한 개의 프로세스만 접근하게 하거나 프로세스를 올바른 순서대로 실행하게 하는 것을 의미
• 공유 자원: 공동으로 사용하는 자원으로, 전역 변수가 될 수도 있고, 파일이 될 수도 있고, 입출력장치, 보조기억장치가 될 수도 있음
• 임계 구역: 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역을 의미. 임계 구역에 진입한 프로세스가 있다면 다른 프로세스는 임계 구역 밖에서 기다려야 함
• 상호 배제: 한 프로세스가 임계 구역에서 작업 중이면 다른 프로세스가 임계 구역에 들어갈 수 없도록 제어한는 것

프로세스 동기화

• 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
• 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기
  
  

공유 자원과 임계 구역
잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행할 때
-> 레이스 컨디션 (race condition) (데이터의 일관성이 깨지는 문제 발생
ex) 저급 언어를 실행하는 과정에서 문맥 교환이 일어날 경우

-> 상호 배제를 위한 동기화를 위해 지켜져야 하는 원칙 3가지

• 상호 배제 (mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없음
• 진행 (progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 함
• 유한 대기 (bounded waiting): 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 함 (임계 구역에 들어오기 위해 무한정 대기해서는 안 됨)
  
  

---

12-2. 동기화 기법

뮤테스 락: 임계 구역을 잠금으로써 프로세서 간의 상호 배제를 이룸
세마포: 공유 자원이 여러 개 있는 임계 구역 문제도 해결할 수 있는 동기화 도구
모니터: 세마포에 비해 사용자가 사용하기 편리한 동기화 도구로 조건 변수를 사용함

뮤테스 락 (Mutex lock: MUTual Exclusion lock)

• 자물쇠 역할: 프로세스들이 공유하는 전역 변수 lock
• 임계 구역을 잠그는 역할: acquire 함수
• 임계 구역의 잠금을 해제하는 역할: release 함수
  -> 바쁜 대기 (busy wait): 임계 구역이 잠겨 있는지를 반복적으로 확인하는 대기 방식

세마포 (semophore)
공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구

• 전역 변수 S: 임계 구역에 진입할 수 있는 프로세스의 개수 (사용 가능한 공유 자원의 개수)를 나타냄
• wait 함수: 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려줌
• signal 함수: 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋다'고 신호를 줌
• 대기 큐 사용: wait 함수는 사용할 수 있는 자원이 없으면 프로세스를 대기 상태로 만듦. signal 함수를 호출하면 대기 큐에서 제거하고, 준비 상태로 변경한 뒤 준비 큐로 옮겨줌
• 실행 순서 제어 가능: 세마포의 변수 S를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait 함수를 붙임

모니터 (monitor)

• 조건 변수 (condition variable): 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
• wait: 호출한 프로세스의 상태를 대기 상태로 전환하고 일시적으로 조건 변수에 대한 대기 큐에 삽입하는 연산 (상호 배제를 위한 큐와 조건 변수에 대한 큐는 따로 존재함)
  • 특정 프로세스가 아직 실행될 조건이 되지 않았을 때에는 wait를 통해 실행을 중단
• signal: wait를 호출하여 큐에 삽입된 프로세스의 실행을 재개하는 연산
  • 특정 프로세스가 실행될 조건이 충족되었을 때에는 signal을 통해 실행을 재개

13-1. 교착 상태란

• 교착 상태: 일어나지 않을 사건을 기다리며 무한히 대기하는 현상
• 식사하는 철학자 문제는 교착 상태의 발생을 보여주는 예시
• 자원 할당 그래프를 이용해 교착 상태를 표현할 수 있음
• 교착 상태 발생 조건: 상호 배제, 점유와 대기, 비선점, 원형 대기

식사하는 철학자 문제 (dining philosophers problem)

1) 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2) 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3) 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4) 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5) 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6) 다시 1번부터 반복한다.

• 철학자: 프로세스 혹은 스레드
• 포크: 자원, 임계 구역
• 생각하는 행위: 자원을 기다리는 것
  -> 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다림
  -> 교착 상태 (deadlick)

자원 할당 그래프 (resource-allocation graph)
1) 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2) 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3) 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
4) 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

교착 상태 발생 조건

• 상호 배제 (mutual exclusion): 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
• 점유와 대기 (hold and wait): 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점 (nonpreemptive): 어떤 프로세스도 다른 프로세스의 자원을 강제로 뺴앗지 못함
• 원형 대기 (circular wait): 프로세스들이 원의 형태로 자원을 대기하는 것
  • 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있음

13-2. 교착 상태 해결 방법

• 교착 상태 예방: 교착 상태의 발생 조건 중 하나를 충족하지 못하게 하는 방법
• 교착 상태 회피: 안전 상태를 유지할 수 있는 경우에만 자원을 할당하는 방법
• 교착 상태 검출 후 회복: 교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 발생하면 그때그때 회복하는 방식

교착 상태 예방

• 상호 배제
  • 모든 자원을 공유가능하게 만듦
    -> 현실에서 사용하기엔 무리가 있음
• 점유와 대기
  • 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분
    -> 자원의 활용률이 낮아짐. 기아 현상 야기 가능성
• 비선점
  • 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있음
  • ex) CPU
    -> 범용성이 떨어짐
• 원형 대기
  • 모든 자원에 번호를 붙이고, 오름차순으로 자원 할당
    -> 자원에 번호를 붙이는 일은 간단X, 각 자원에 어떤 번호를 붙이느냐에 따라 특정 자원의 활용률 떨어질 수 있음

-> 교착 상태 예방은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 따름

교착 상태 회피

• 안전 순서열 (safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미
  • 안전 상태 (safe state): 안전 순서열이 존재하는 상태
  • 불안정 상태 (unsafe state): 안전 순서열이 없는 상태
• ex) 은행원 알고리즘 (Banker’s Algorithm)
  
  

교착 상태 검출 후 회복

• 선점을 통한 회복
  • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복
  • 교착 상태에 놓인 프로세스들을 모두 강제 종료
    -> 많은 프로세스들이 작업 내역을 잃게 될 가능성
  • 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
    -> 교착 상태가 없어졌는지 확인하는 과정에서 오버헤드 야기

타조 알고리즘(ostrich algorithm)

• 교착 상태를 아예 무시하는 방법
• 때때로 이 방식이 적합할 때도 많음
  
  

후기: 이번주에 여행을 갔다왔더니, 밀리고 밀려 벼락치기로 끝내버림..ㅠㅠ
이번 주차가 운영체제에서 꽤나 중요한 부분인데 제대로 공부를 못해서 슬프당.. 다음주에 다시 공부하기! (이렇게 적어놓고 안 하진 않겠지.......)
복습 완료!