학습 범위

동시에 프로그램을 실행할 때 반드시 고려해야 할 동기화와
해결해야 하는 문제인 교착 상태에 대해 알아가는 시간이다.

• Chapter 12 | 프로세스 동기화
  • 12-1 | 동기화란
  • 12-2 | 동기화 기법
• Chapter 13 | 교착 상태
  • 13-1 | 교착 상태란
  • 13-2 | 교착 상태 해결 방법

프로세스 동기화

동기화란

프로세스는 서로 데이터를 주고 받으며 협력하며 실행될 수도 있다.
프로세스의 협력에는 반드시 동기화 synhronization 가 중요하다.
(물론 스레드 또한 동기화가 중요하다.)

• 실행 순서 제어
  프로세스를 올바른 순서대로 실행하기
  어떤 프로세스가 완료되고 나서야 그 이후에 실행 가능한 다른 프로세스가 실행되도록 한다
• 상호 배제
  동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기
  공유 불가능한 자원의 동시 사용을 피하는 것이 상호 배제 mutual exclusion.
  ex. 생산자와 소비자 문제 (상대의 작업 끝나기 전에 "총합" 데이터 수정하는 이슈.)

협력하는 프로세스가 공동으로 사용하는 자원을 공유 자원 shared resource 라고 하며
공유 자원에 대한 동시 접근이 동기화 문제를 야기할 수 있다.
이러한 공유 자원에 접근하는 구간은 동시 실행 시 문제가 되는 구역으로
임계 구역 critical section 이라고 한다.

둘 이상의 프로세스가 임계 구역에 접근하여 공유 자원을 조작하면 동기화 이슈가 발생하는데
이와 같은 공유 자원에 대한 경쟁을 레이스 컨디션 race condition 이라고 한다.
고급 언어로 보면 문제되지 않을 것 같은 공유 자원 접근도
저급 언어로 변환하여 실행하다보면 여러 줄의 코드로 실행되어
실행 도중 문맥 교환으로 인한 레이스 컨디션이 발생할 수 있는 임계 구역이 된다.

운영체제는 임계 구역 문제를 다음과 같은 세 가지 원칙 하에 해결한다.

• 상호 배제 mutual exclution
  한 프로세스가 임계 구역 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
• 진행 progress
  임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있다.
• 유한 대기 bounded waiting
  임계 구역에 진입하고자 하는 프로세스는 무한정 대기하지 않고 언젠가는 들어갈 수 있어야 한다.

더 알아보기

【↗[컴퓨터 공학 기초 강의] 33강. 프로세스 동기화란?】
【↗[저자 GitHub] producer consumer 문제】

동기화 기법

프로세스의 동기화를 위한 대표적인 도구로는 다음과 같은 것들이 있다.

뮤텍스 락

뮤텍스 락 MUTual EXclusion lock 은 상호 배제를 위한 동기화 도구로,
하나의 전역 변수와 두 개의 함수로 구현할 수 있다.

• 자물쇠 역할: 프로세스들이 공유하는 전역 변수 lock
• 임계 구역을 잠그는 역할: acquire 함수
  임계 구역에 진입하기 전에 호출하는 함수.
  임계 구역이 잠겨 있다면 lock==false가 될 때까지 반복적으로 확인.
  (이와 같이 기다리며 계속 확인하는 것을 바쁜 대기 busy wait 이라고 한다.)
  임계 구역이 열려 있다면 lock=true 하고 임계 구역 접근.

  acquire() {
      while (lock == true); // 잠겨 있는 동안 잠김 여부 계속 확인
      lock = true; // 열려 있으면 잠그고 함수를 빠져 나감
  }

• 임계 구역의 잠금을 해제하는 역할: release 함수
  임계 구역의 작업이 끝나고 호출하는 함수.
  임계 구역을 열어 lock=false 하고 임계 구역을 벗어남.

  release() {
      lock = false; // 잠금 해제
  }

세마포

세마포 semaphore 는 공유 자원이 여러 개 있는 상황에서도 적용 가능한 동기화 도구로,
하나의 전역 변수와 두 개의 함수로 구현할 수 있다.

• 임계 구역에 진입할 수 있는 프로세스 개수: 프로세스들이 공유하는 전역변수 S
  바꿔 말하면, 사용 가능한 공유 자원 개수.
  처음에는 전체 자원 개수이며, 프로세스의 접근에 따라 변동된다.
• 임계 구역 진입 가능 여부를 알려주는 역할: wait 함수
  임계 구역에 진입하기 전에 호출하는 함수.
  진입 가능한 프로세스가 없다면 S > 0가 될 때까지 반복적으로 확인.
  진입 가능한 프로세스가 있다면 S--으로 진입 가능한 프로세스 수를 하나 줄이고 임계 구역 접근.

  wait() {
      while (S <= 0); // 진입 가능한 프로세스가 없는 동안 진입 가능 여부 계속 확인
      S--; // 진입 가능하다면 진입 가능 프로세스 수를 1 줄이고 함수를 빠져 나감
  }

  바쁜 대기로 인한 CPU 주기 낭비를 방지하기 위해 세마포를 위한 대기큐 사용 가능

  wait() {
      S--;
      if (S < 0) {
          enQueue(); // 해당 프로세스의 PCB를 대기 큐에 삽입하는 가상의 함수
          sleep(); // 대기 상태 진입
      }
  }

• 임계 구역 앞에서 기다리는 프로세스에게 진입 가능을 알려주는 역할: signal 함수
  임계 구역의 작업이 끝나고 호출하는 함수.
  S--으로 진입 가능한 프로세스 수를 늘리고 임계 구역을 벗어남.

  signal() {
      S++; // 진입 가능 프로세스 1 증가
  }

  바쁜 대기로 인한 CPU 주기 낭비를 방지하기 위해 세마포를 위한 대기큐 사용 가능

  signal() {
      S++;
      if (S <= 0) { // S > 0일 때는 대기 큐에서 기다리지 않고 다 잘 사용 중.
          p = deQueue(); // 대기 큐에서 프로세스 p를 제거하는 가상의 함수
          wakeup(p); // 프로세스 p를 대기 상태에서 준비 상태로 변경
      }
  }

세마포를 이용하면 변수 S를 0으로 두고
먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait 함수를 두어
실행 순서 제어를 위한 동기화도 수행할 수 있다는 건 여담.

모니터

모니터 monitor 는 함수를 잘못 사용하는 것을 방지하여 세마포에 비해 사용하기 편리한 도구로,
공유 자원과 이에 접근하기 위한 인터페이스를 묶어서 관리한다.

모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고
큐에 삽입된 순서대로 하나씩 공유 자원 이용.

프로세스의 실행 순서를 제어하기 위한 특별한 변수 조건 변수 condition valiable 이용 시
특정 조건을 바탕으로 프로세스를 실행 및 일시 중단하여 실행 순서 제어 가능.

모니터에 진입한 어떤 프로세스가 어떤 조건 변수에 대한 wait 함수 호출 시
해당 프로세스는 진행되지 않고 해당 조건 변수를 위한 대기 큐에 삽입되고
다른 프로세스가 모니터 접근 가능.
(나중에 실행해야 하는 프로세스에서 호출)

이보다 먼저 실행되어야 하는 프로세스가 작업을 마치고 해당 조건 변수에 대한 signal 함수 호출 시
해당 조건 변수를 위한 대기 큐에서 기다리고 있던 프로세스가 다시 모니터 접근 가능.
(먼저 실행해야 하는 프로세스에서 호출)

• 특정 조건이 충족되지 않았을 때 wait 함수를 통해 실행 중단
• 특정 조건이 충족되었을 때 signal 함수를 통해 실행 재개

더 알아보기

【↗[컴퓨터 공학 기초 강의] 34강. 프로세스 동기화 기법】
【↗[저자 GitHub] 코드로 보는 동기화】

교착 상태

교착 상태란

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 교착 상태 deadlock 는
둘 이상의 프로세스가 서로가 독점하고 있는 자원을 기다릴 때 발생하곤 한다.

교착 상태는 자원 할당 그래프 resource-allocation graph 를 통해 단순하게 표현할 수 있다.
이 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있으며 어떤 자원을 기다리고 있는지 나타낸다.

• 프로세스는 원으로, 자원은 사각형으로 표현
• 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현
• 프로세스가 사용 중인 자원은 자원→프로세스 방향의 화살표로 표현
• 프로세스가 기다리는 자원은 프로세스→자원 방향의 화살표로 표현

교착 상태가 발생하는 조건에는 네 가지가 있으며
그 중 하나라도 만족하지 않으면 발생하지 않는다.

• 상호 배제 mutual exclusion
  한 프로세스가 사용 중인 자원을 다른 프로세스가 사용할 수 없는 상황
• 점유와 대기 hold and wait
  자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상황
• 비선점 nonpreemptive
  다른 프로세스의 자원을 강제로 빼앗지 못하고 작업이 끝나길 기다리는 상황
• 원형 대기 circular wait
  서로가 서로의 자원을 기다리며 원의 형태로 자원을 대기하는 상황

따라서 이 중 하나라도 피하면 교착 상태를 피할 수 있다.

더 알아보기

【↗[컴퓨터 공학 기초 강의] 35강. 교착 상태란?】

교착 상태 해결 기법

예방하기

교착 상태 발생 조건 중 하나를 충족하지 못하게 한다

• "상호 배제" 제거 | 모든 자원을 공유 가능하게 한다
  현실적인 이유로 사용에 무리가 있다
• "점유와 대기" 제거 | 필요한 자원을 한 번에 모두 할당하거나 아무것도 할당하지 않는다
  한 프로세스에 필요한 자원을 몰아주는 것의 반복으로 자원의 활용률이 낮아진다
  필요 이상으로 오래 할당되거나 당장 필요해 기다려야만 하는 상황 발생
  자원을 많이 사용하는 프로세스일수록 적절한 타이밍 확보하기 어려워 무한정 기다릴 위험
• "비선점" 제거 | 자원을 이용 중인 프로세스부 해당 자원을 뺏을 수 있다
  CPU 등 선점하여 사용할 수 있는 일부 자원에 대해서 효과적
  프린터와 같은 자원의 경우 비선점을 제거하 어려워 범용성이 떨어진다
• "원형 대기" 제거 | 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당한다
  모든 자원에 번호를 붙이는 작업은 간단한 일이 아니며 경우에 따라 특정 자원의 활용률이 떨어질 수 있다

어떠한 방법이든 완벽하지 않아 부작용 존재.

회피하기

교착 상태가 발생하지 않을 정도로만 조심히 할당한다
교착 상태를 한정된 자원에 대한 무분별한 할당으로 인한 문제로 간주

프로세스에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원 분배.

• 안전 상태 safe state
  교착 상태 발생 없이 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  안전 순서열이 존재하며 그 순서대로 프로세스들에 자원 배분
  • 안전 순서열 safe sequence
    교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 불안전 상태 unsafe state
  교착 상태가 발생할 수 있는 상태
  안전 순서열이 존재하지 않는다

시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원 할당 시
교착 상태를 회피할 수 있다

검출 시 회복하기

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

• 선점을 통한 회복
  교착 상태가 회복될 때까지 한 프로세스씩 자원 몰아주기
  다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스에 할당 (우선순위에 따라?)
• 프로세스 강제 종료를 통한 회복
  교착 상태에 놓인 프로세스를 모두 강제 종료하거나 (많은 프로세스의 작업 내역 상실)
  교착 상태가 없어질 때까지 한 프로세스씩 강제 종료 (교착 상태 제거 여부 확인의 오버헤드 발생)

더 알아보기

【↗[컴퓨터 공학 기초 강의] 36강. 교착 상태 해결 방법】

미션 수행하기

이번 주 미션

• 기본 미션 | p. 363의 확인 문제 1번 풀고 인증하기
• 선택 미션 | Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기

기본 미션

미션은 P.363의 1번 문제뿐이지만, 이왕 학습하고 확인 문제를 푸는 거 다 풀어보자.

P.349 [12-1 | 동기화란] 확인 문제

1. 동기화의 의미에 대한 옳은 설명을 다음 보기에서 찾아 쓰세요.
   [보기| 상호 배제, 실행 순서 제어, 임계 구역]

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

2. 임계 구역에 대한 설명으로 옳지 않은 것을 고르세요.
   ① 임계 구역에서 여러 개의 프로세스가 동시에 실행해도 무방합니다. → 동시 실행 시 레이스 컨디션 발생.
   ② 임계 구역에서 여러 프로세스가 동시에 실행할 경우 레이스 컨디션이 발생합니다.
   ③ 임계 구역에서 실행되는 프로세스가 있다면 다른 프로세스는 기다려야 합니다.
   ④ 운영체제는 임계 구역을 관리합니다.

P.363 [12-2 | 동기화 기법] 확인 문제

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

(요것이 이번주 기본 미션!!)

2. 조건 변수 x와 y가 있다고 가정해 보겠습니다. 스레드 A는 실행 과정에서 x.wait를 호출하였고, 스레드 B는 y.wait을 호출했습니다. 스레드 C가 y.signal을 호출했을 때 스레드 A와 Bㅈ 중 실행이 재개되는 스레드는 무엇일까요?
   스레드 B

3. 빈칸에 들어갈 알맞은 말을 보기에서 골라 써 보세요.
   [보기| 실행 순서 제어, 상호 배제, 입출력장치]
   "세마포를 이용하면 동시에 실행되는 프로세스 혹은 스레드 간에 [① 실행 순서 제어 ]를 위한 동기화와 [② 상호 배제 ]를 위한 동기화를 할 수 있습니다."

P.374~375 [13-1 | 교착 상태란] 확인 문제

1. 교착 상태에 대한 설명으로 옳지 않은 것을 고르세요.
   ① 교착 상태는 다양한 상황에서 발생할 수 있습니다.
   ② 교착 상태는 자원 할당 그래프로 표현할 수 있습니다.
   ③ 교착 상태는 일어나지 않을 사건을 기다리며 무한히 대기하는 현상을 의미합니다.
   ④ 식사하는 철학자 문제에서 단 한 명의 철학자가 식사를 해도 교착 상태가 발생합니다. → 모두가 동시에 식사하려 할 때 발생.

옳은 것을 고르라는데 아무리 봐도 옳은 것 세 개, 옳지 않은 것 한 개라서 제보.

2. 교착 상태가 발생할 수 있는 네 가지 조건을 모두 써 보세요.
   [ 상호 배제, 점유와 대기, 비선점, 원형 대기]

3. 다음 자원 할당 그래프 중 교착 상태가 발생할 위험이 있는 그래프는 ①과 ② 중 무엇인가요?

②

P.386~387 [13-2 | 교착 상태 해결 방법] 확인 문제

1. 교착 상태를 회복하는 방법에 대해 옳지 않은 것을 고르세요.
   ① 교착 상태가 발생하는 조건 중 하나를 충족하지 않게 하면 교착 상태를 예방할 수 있다.
   ② 교착 상태가 발생했다면 이를 회복할 수 없습니다. → 선점 또는 프로세스 강제 종료를 통해 회복 가능.
   ③ 안전 상태를 유지할 수 있는 경우에만 자원을 할당하면 교착 상태를 회피할 수 있습니다.
   ④ 교착 상태의 검출 및 회피 방식에서 운영체제는 주기적으로 교착 상태의 발생 여부를 검사합니다.

2. 아래와 같은 상황에서 프로세스 P2에 자원 두 개를 나누어 줬다고 가정해 보겠습니다. 프로세스 P2가 실행을 올바르게 종료한 뒤 자원을 반납하면 남은 자원은 몇 개가 될까요?

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2
P3	9	2

• 할당 가능 자원: 12
• 할당한 자원(P1, P2, P3 현재 사용량의 총합): 9
• 남은 자원(할당 가능 자원 - 할당한 자원): 3

남은 자원은 5개

3. 교착 상태에 대한 대처 방법 중 타조 알고리즘에 대한 설명으로 옳은 것을 고르세요.
   ① 교착 상태를 회피하는 방법입니다.
   ② 교착 상태를 무시하는 방법입니다.
   ③ 교착 상태를 검출하고 회복하는 방법입니다.
   ④ 교착 상태를 예방하는 방법입니다.

4. 교착 상태 예방에 대한 설명으로 옳지 않은 것을 고르세요.
   ① 상호 배제 조건을 없앰으로써 교착 상태를 예방할 수 있습니다.
   ② 점유와 대기 조건을 없앰으로써 교착 상태를 예방할 수 있습니다.
   ③ 비선점 조건을 없앰으로써 교착 상태를 예방할 수 있습니다.
   ④ 원형 대기 조건을 추가함으로써 교착 상태를 예방할 수 있습니다. → 없앰으로써.

선택 미션

동시 접근 시 동기화 문제를 일으킬 수 있는 자원을 공유 자원이라고 하는데,
이러한 공유 자원에 접근하는 구간을 동시 실행 시 문제가 되는 임계 구역이라고 한다.

동기화 문제 예방을 위해 임계 구역에 대한 동시 접근을 방지하고자
한 프로세스가 임계 구역 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없도록 할 수 있는데
이러한 기법을 상호 배제라고 한다.