저자 github

방학이라서 그런가, 다른 업무가 더해져서 그런가,
평소보다는 느린 페이스를 가진 주간이었다.
그래도 한 주 미리 작성은 성공.
애는 쓰고 있지만 비축분 만드는 게 쉽지 않다.
현실 회피하고 싶을 때마다 타조를 생각했다.

5주차

• Chapter 12 ~ 13
• p. 363의 확인 문제 1번 풀고 인증하기
• Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기

12 프로세스 동기화

12-1 동기화란

동기화(synchronization)의 의미

• 특정 자원에 접근할 때 한 개의 프로세스만 접근하게 하거나, 프로세스를 올바른 순서대로 실행하게 하는 것

• 실행의 문맥을 갖는 모든 대상은 동기화의 대상이다.
  1) 실행 순서 제어를 위한 동기화: 동시에 실행되는 프로세스를 올바른 순서대로 실행하는 것

• 예) reader writer problem
  2) 상호 배제(mutual exclusion)를 위한 동기화: 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

• 예) bank account problem / 한 번에 한 번

• Producer & Consumer problem

예제 코드

공유 자원과 임계 구역

• 공유 자원: 공동으로 이용하는 변수(전역 변수), 파일, 장치 등의 자원
• 임계 구역: 동시에 실행하면 문제가 발생하는 공유 자원에 접근하는 코드 영역
  • 레이스 컨디션(race condition): 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우
  • 운영체제가 임계 구역 문제를 해결하는 원칙
    1) 상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
    2) 진행(progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
    3) 유한 대기(bounded waiting): 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다. = 언젠가는 들어갈 수 있어야 한다.

12-2 동기화 기법

동기화 도구: 뮤텍스 락, 세마포, 모니터

• pseudo code를 눈으로 익혀 놓기
• 여기서 언급하고 있는 함수들은 실제로 있는 함수가 아니라 추상적인 함수다. 아래 개념을 토대로 구현은 직접 해야 한다.
• 철학자 문제로 적용해보기.

뮤텍스 락(Mutex lock: MUTual EXclusion lock)

• 동시에 접근해서는 안 되는 자원에 동시에 접근하지 않도록 만드는 도구, 상호 배제를 위한 동기화
• 구현
  - 전역변수 lock: 프로세스들이 공유. 자물쇠 역할
  • acquire 함수: 임계 구역을 잠금
  • release 함수: 임계 구역의 잠금을 해제
• 사용할 수 있는 공유 자원이 없는 경우 바쁜 대기(busy waiting) 반복(CPU 주기 낭비)
• c++, python 등 언어 자체에서 지원한다.

세마포(semaphore)

• 공유 자원이 여러개 있는 상황에서도 적용이 가능한 동기화 도구

• 동시에 실행되는 프로세스 or 스레드 간의 상호 배제를 위한 동기화와 실행 순서 제어를 위한 동기화를 할 수 있다.

• 구현

  • 전역 변수 S: 임계 구역에 진입할 수 있는 프로세스 개수를 나타냄
  • wait 함수: 임계 구역에 들어가도 되는지, 기다려야 할지 알려줌
  • signal 함수: 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋아' 신호

• busy waiting 해결 방법

  • 사용할 수 있는 자원이 없는 경우 대기 상태로 만듦(해당 프로세스의 PCB를 대기 큐에 삽입)
  • 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦(해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)

• 세마포를 활용한 실행 순서 동기화

  • 세마포의 변수 S를 0으로 두고
  • 먼저 실행할 프로세스 뒤에 signal 함수
  • 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 된다.

모니터

• 사용자가 사용하기에 세마포보다 좋음
  - 세마포는 임계 구역 앞 뒤로 wait, signal 함수를 명시하므로 코드가 방대해 질 수 있는 단점. 디버깅도 어렵다.

• 상호 배제(mutual exclusion)를 위한 동기화

  • 인터페이스를 위한 큐
  • 공유 자원에 접근하고자 하는 프로세스를 인터페이스를 위한 큐에 삽입
  • 큐에 삽입된 순서대로 한 번에 하나의 프로세스만 공유 자원 이용

• 실행 순서 제어를 위한 동기화
  

  • 조건 변수(condition variable): 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위해, 프로세스나 스레드의 실행 순서를 제어하기 위한 특별한 변수
    1) 특정 프로세스가 아직 실행될 조건이 되지 않았을 때에는 wait를 통해 실행을 중단한다.
    2) 특정 프로세스가 실행될 조건이 충족되었을 때에는 signal을 통해 실행을 재개한다.

13 교착 상태

13-1 교착 상태란

• 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

식사하는 철학자 문제

다섯 명의 철학자가 하나의 원탁에 앉아 식사를 한다. 각각의 철학자들 사이에는 포크가 하나씩 있고, 앞에는 접시가 있다. 접시 안에 든 요리는 포크를 두개 사용하여 먹어야만 하는 스파게티 이다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없으며, 번갈아가며 각자 식사하거나 생각하는 것만 가능하다. 따라서 식사를 하기 위해서는 왼쪽과 오른쪽의 인접한 철학자가 모두 식사를 하지 않고 생각하고 있어야만 한다. 또한 식사를 마치고 나면, 왼손과 오른손에 든 포크를 다른 철학자가 쓸 수 있도록 내려놓아야 한다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있도록 하는 방법은 무엇인가?

• 출처: 나무위키

자원 할당 그래프

교착 상태 발생 조건 파악 가능

• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

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

• 자원 할당 그래프가 원의 형태를 띄고 있다면 -> 교착 상태가 일어날 수 있다.

교착 상태 발생 조건

• 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait): 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
• 비선점(nonpreemptive): 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait): 프로세스들이 원의 형태로 자원을 대기하는 상태

13-2 교착 상태 해결 방법

교착 상태 예방

• 교착 상태 발생 조건 중 하나를 충족하지 않게 하는 법

1) 상호 배제를 충족하지 않게 하자

• 모든 자원을 공유 가능하게 한다 -> 현실적으로 불가능

2) 점유과 대기를 없애자.

• 식사하는 철학자 > 포크를 2개 동시에 들거나, 아예 들지 못하게 함.
• 이론적으로 교착 상태 해결
• 자원의 활용률이 낮아질 우려(이유: 자원을 몰아줘야 하는 상황)

3) 비선점 조건을 없애자

• 자원을 이용중인 프로세스로부터 자원(포크)을 뺏을 수 있게 됨
• 선점하여 사용할 수 있는 일부 자원(CPU)에 대해 효과적
• 하지만, 모든 자원이 선점 가능하지 않다.
• 범용성이 떨어짐

4) 원형 대기 조건을 없애자.

• 모든 자원에 번호를 붙이고, 오름차순으로 자원 할당
• 단점: 수많은 자원에 번호를 붙이는 일은 현실적으로 힘듦

교착 상태 회피

은행 알고리즘 알아보기

• 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식(조심 조심 할당)
• 안전 상태(safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태. 안전 순서열이 있음
• 불안전 상태(unsafe state): 교착 상태가 발생할 수도 있는 상황. 안전 순서열이 없음.
• 안전 순서열(safe sequence): 교착 상대 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식

1) 선점을 통한 회복: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
2) 프로세스 강제 종료를 통한 회복

• 가장 단순하고 확실한 방법
• 경우1) 교착 상태인 프로세스 모두 강제 종료 -> 많은 프로세스들이 작업 내역을 잃게 될 가능성
• 경우2) 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료 -> 작업 내역을 잃는 프로세스들을 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부 확인 과정에서 오버 헤드 발생

교착 상태 무시

타조 알고리즘 유머와 같이 드물게 발생하는 교착 상태라면, 그냥 무시...

숙제

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

4) 세마포를 이용하면 바쁜 대기 x(이건 뮤텍스 락의 문제), 해당 프로세스 상태를 대기 상태로 만든다.

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

• 임계 구역: 동시에 실행하면 문제가 발생하는 공유 자원에 접근하는 코드 영역
  • 레이스 컨디션(race condition): 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우
  • 운영체제가 임계 구역 문제를 해결하는 원칙 중에 상호 배제란?
    한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.