5주차 학습 정리

Chapter 12 : 프로세스 동기화

12-1 : 동기화란

동기화(synchoronization)의 의미

• 프로세스 동기화 : 프로세스들 사이의 수행 시기를 맞추는 것을 의미합니다.
• 프로세스 동기화의 사용
  1. 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하는 것입니다.
     ex) Reader 프로세스, Writer 프로세스가 있는 경우 Reader 프로세스는 내부의 정보가 존재한다는 조건이 필요하므로, Writer 프로세스가 Reader 프로세스 보다 먼저 실행 되는 것을 의미합니다.
  2. 상호 배제(mutual exclusion) : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하는 것입니다.
     ex) 공유가 불가능한 자원의 동시 사용을 피하기 위한 알고리즘으로, 은행 관련 프로세스에서 저축 프로세스 여러 개가 동시에 "잔액"에 접근하여 "잔액"의 값을 변경하면 옳지 않은 값을 내보내는 것을 막기 위해 동시에 "잔액"에 접근하지 못하게 하는 것을 의미합니다.

생산자와 소비자 문제

• 생산자와 소비자 문제 : 고전적이고 유명한 동기화 문제입니다.
  • 생산자 프로세스와 소비자 프로세스가 "총합"이라는 데이터를 공유합니다.
  • 생산자 프로세스 : 물건을 계속 생산하며, 버퍼에 물건을 넣은 후, "총합"을 1 증가 시킵니다.
  • 소비자 프로세스 : 물건을 계속 소비하며, 버퍼에서 물거을 빼고, "총합"을 1 감소 시킵니다.
  • "총합"이 10일 때 두 프로세스를 동시에 10000번 실행 시키면 계속 "총합"이 10을 유지해야하지만, 실제로는 10이 아닙니다.
  • 해당 문제는 프로세스가 동기화 되지 않고, "총합" 데이터를 동시에 사용해서, 소비자가 생산자의 작업 완료 전 총합을 수정하고, 생산자도 소비자가 작업 완료 전 총합을 수정하여 발생하는 문제입니다.
  • 동시에 접근하면 안되는 자원("총합")에 동시에 접근하여 발생하는 문제입니다.

공유 자원과 임계 구역

• 공유 자원(shared resource) : 전역 변수, 파일, 입출력장치, 보조기억장치 등으로 동시에 실행되는 프로세스들의 공동의 자원을 의미합니다.
• 임계 구역(critical section) : 공유 자원 중 두 개 이상의 프로세스를 동시에 실행하여 문제가 발생하는 자원을 의미합니다. 임계 구역에 접근하는 프로세스들 중 하나가 실행 중이면 나머지 프로세스들은 기다려야 합니다.
• 레이스 컨디션(race condition) : 잘못된 실행으로 인하여, 임계 구역의 코드를 여러 프로세스가 동시에 실행하느 경우입니다. 레이스 컨디션 발생 시 위의 예시처럼 데이터의 일관성이 깨지는 문제가 발생합니다.
• 레이스 컨디션의 발생 이유 : 고급 언어 한 줄이 여러 줄의 저급 언어로 실행되며, 저급 언어 여러 줄을 실행하는 도중 '문맥 교환'이 일어나는 경우 문제가 발생합니다.
• 상호 배제를 위한 동기화의 세 가지 원칙
  • 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역으로 들어올 수 없습니다.
  • 진행(progress) : 임계 구역에 어떤 프로세스도 집입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 합니다.
  • 유한 대기(bounded waiting) : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 합니다. (임계 구역에 들어오기 위해서 무한정 대기해서는 안됩니다.)

12-2 : 동기화 기법

뮤텍스 락

• 뮤텍스 락(Mutex lock : MUTual EXclusion lock) : 임계 영역에 대한 상호 배제를 위한 동기화 도구입니다.
  • 임계 구역에 진입하는 프로세스에서 뮤텍스 락을 이용해 임계 구역에 자물쇠를 걸어, 다른 프로세스가 임계 구역이 잠겨 있다면 기다는 방식으로 임계 구역 진입을 통제 할 수 있습니다.
• 뮤텍스 락의 단순한 형태 : 임계 영역 진입 전 acquire 함수를 호출하고 임계 영역 벗어나며 release 함수를 호출합니다.
  • 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
  • 임계 구역을 잠그는 역할 : acquire 함수
    • 프로세스가 임계 구역 진입하기 전에 호출하는 함수
    • 임계 구역이 이미 잠겨 있다면 열릴 때까지 반복적으로 확인(lock이 false일 때까지 반복)하고, 열려 있다면 잠그는(lock을 true로 변경) 함수입니다.
  • 임계 구역의 잠금을 해제하는 역할 : release 함수
    • 임계 구역에서의 작업이 끝나고 호출하는 함수입니다.
    • 현재 잠김 임계 구역을 열어주는 함수(lock을 false로 변경)입니다.
• 바쁜 대기(busy wait) : 반복적으로 확인하며 대기하는 것을 뜻합니다.
  • ex) aquire 함수에서 임계 구역이 잠겨 있을 경우 프로세스가 반복적으로 lock을 확인하는 방식입니다.

세마포

• 세마포(semaphore)
  • 뮤텍스 락과 비슷하지만, 조금 더 일반화된 방식의 동기화 도구입니다.
  • 뮤덱스 락은 하나의 공유 자원에 접근하는 프로세스를 상정한 것이며, 세마포는 공유 자원이 여러 개 있을 경우 사용하는 동기화 도구입니다.
  • 세마포는 철도 신호기에서 유래한 단어로, 신호에 맞춰서 코드의 진행 여부를 결정합니다. 임계 구역 앞에서 진행 신호, 멈춤 신호에 따라서 대기와 임계 구역 진입이 결정됩니다.
• 세마포의 단순한 형태 : 임계 영역 진입 전 wait 함수를 호출하고 임계 영역 벗어나며 signal 함수를 호출합니다.
  • 임계 구역에 진입할 수 있는 프로세스의 개수 (사용 가능한 공유 자원의 개수)를 나타내는 전역 변수 S
  • 임계 구역에 진입 가능 여부를 확인하는 wait 함수
    • 임계 구역에 진입할 수 있는 프로세스 개수가 0 이면 자원이 존재하는지 반복적으로 확인합니다.
    • 임계 구역에 진입할 수 있는 프로세스 개수가 1 이상이면 S를 1 감소시키고 임계 구역 진입합니다.
  • 임계 구역 앞에서 기다리는 프로세스에 '진입 신호'를 주는 signal 함수
    • 임계 구역에서의 작업을 마친 뒤 S를 1 증가시킵니다.
• 바쁜 대기를 극복하기 위한 세마포의 구현 형태
  • wait 함수
    • 사용할 수 있는 자원이 없는 경우(S가 0) 해당 프로세스 상태를 대기 상태로 변경하고, 프로세스의 PCB를 세마포를 위한 대기 큐에 집어넣습니다.
  • signal 함수
    • 다른 프로세스가 임계 구역의 작업이 끝난 경우 signal 함수를 호출할 때, 대기 중인 프로세스를 대기 큐에서 제거하고, 프로세스 상태를 준비 상태로 변경한 뒤 준비 큐로 옮깁니다.
• 세마포의 프로세스 순서 제어하는 방법
  • 세마포의 변수 S를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수를 사용, 다음에 실행할 프로세스 앞에 wait 함수를 사용하면 됩니다.
  • 먼저 실행할 프로세스가 S를 signal을 통해서 올려주지 않으면 wait에 의해 나중에 실행할 프로세스가 대기하게 됩니다.

모니터

• 모니터(monitor)
  • 세마포의 불편한 점(임계 구역 앞뒤로 wait, signal을 명시하는 것)이나 사용자의 실수를 방지하기 위한 방안입니다.
  • 공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어서 관리하며, 프로세스는 반드시 해당 인터페이스를 통해서만 공유 자원에 접근하도록 합니다.
  • 모니터를 통해 공유 자원에 접근하려는 프로세스를 큐에 삽입하고, 삽입한 순서대로 공유 자원을 이용합니다.
  • 큐를 통해서 모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 위한 동기화를 제공합니다.
• 모니터의 실행 순서 제어를 위한 동기화
  • 조건 변수(condition variable) : 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수로, 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위해 사용합니다.
  • wait 연산 : 호출한 프로세스의 상태를 대기 상태로 전환하며, 일시적으로 조건 변수에 대한 대기 큐에 삽입하는 연산
    • 모니터에 진입을 위한 큐와 wait가 호출되어 실행이 중단된 프로세스들이 삽입되는 큐는 다릅니다.
  • signal 연산 : 조건 변수에 대한 대기 큐에 삽입된 프로세스의 실행을 재개하는 연산입니다.
    • 모니터 안에는 하나의 프로세스만 있을 수 있기에,
      signal 호출 시 대기 큐에 삽입된 프로세스는 signal을 호출한 프로세스가 떠난 뒤 실행되거나,
      signal을 호출한 프로세스의 실행이 일시 중단되고 대기 큐의 프로세스가 실행된 뒤 다시 수행을 재개합니다.

Chapter 13 : 교착 상태

13-1 : 교착 상태란

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

• 동그란 우너탁에 다섯 명의 철학자가 있습니다.
• 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이에 필요한 포크(총 5개)가 있습니다.
• 철학자들은 앞의 식사를 하기 위해서는 두 개의 포크가 필요합니다.
• 철학자들의 식사 순서
  1. 게속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
  2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
  3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
  4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
  5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
  6. 다시 1번부터 반복한다.
• 문제점
  • 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고, 영원히 생각하는 상황이 될 수 있습니다.
  • 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다립니다.
• 교착 상태(deadlock) : 일어나지 않을 사건을 기다리며 진행이 멈춰버린 현상을 의미합니다.
  • ex) 위의 철학자들이 기다리는 상태입니다.
• 교착 상태 해결을 위한 방안
  1. 교착 상태가 발생했을 때의 상황을 정확히 표현
  2. 교착 상태가 일어나는 근본적인 이유

자원 할당 그래프

• 자원 할당 그래프(resource-allocation graph) : 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프입니다.
  • 교착 상태를 단순하게 표현할 수 있습니다.
• 자원 할당 그래프의 규칙
  1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현합니다.
  2. 사용할 수 있는 자원의 개수는 자원 사각형 내의 점으로 표현합니다.
  3. 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시합니다.
  4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시합니다.
• 자원 할당 그래프의 예시
  
• 철학자 문제의 자원 할당 그래프
  
• 교착 상태의 그래프의 특징 : 교착 상태가 발생한 경우 자원 할당 그래프가 원의 형태를 띄게됩니다.

교착 상태 발생 조건

• 교착 상태 발생 조건 4가지를 모두 만족하면 교착 상태가 발생할 가능성이 생깁니다.
• 교착 상태 발생 4가지 조건
  • 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때입니다.
  • 점유와 대기(hold and wait) : 자우너을 할당받은 상태에서 다른 자우너을 할당받기를 기다리는 상태입니다.
  • 비선점(nonpreemptive) : 자원을 이용하는 프로세스의 작업이 끝나야만 다른 프로세스가 사용할 수 있는 상태입니다.
  • 원형 대기(circular wait) : 프로세스들과 프로세스가 요청 및 할당 받은 자원이 원의 형태를 이뤄 자원을 대기하는 것을 뜻합니다.

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

교착 상태 예방

• 교착 상태 예방은 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게하면 됩니다.
• 각 조건의 예방 방법
  • 상호 배제 예방
    • 모든 자원을 공유 가능하게 만드는 것을 의미합니다.
    • 단점
      • 이론 상으로는 교착 상태가 없어지지만, 현실적으로 모든 자원을 공유하도록 하는 것은 어렵습니다.
  • 점유와 대기 예방
    • 운영체제가 특정 프로세스가 요청하는 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분합니다.
    • 단점
      • 자원 활용률이 낮아질 수 있습니다.
      • 많은 자원을 사용하는 프로세스가 불리해집니다. (자원을 사용할 타이밍 확보가 어렵습니다.) 따라서, 기아 현상을 야기할 수 있습니다.
  • 비선점 조건 예방
    • 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있게 합니다.
    • 단점
      • 선점이 가능한 일부 자원에 대해서는 효과적(ex. CPU)이지만, 모든 자원이 선점 가능하지 않습니다.
        • ex) 프린터 : 프린터를 사용하여 출력 중인 프로세스에게 프린터 자원을 뺏는 것은 불가능합니다.
  • 원형 대기 조건 예방
    • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면됩니다.
    • 낮은 자원을 할당 받으면, 높은 자원 같이 할당할 수 없게 합니다.
    • 단점
      • 시스템 내의 수많은 자원에 번호를 붙이는 것은 쉽지 않습니다.
      • 각 자원의 번호에 다라서 활용률이 달라집니다.
• 교착 상태 예방은 교착 상태의 발생 조건을 원칙적으로 제거하여 사전에 방지하여 교착 상태가 발생하지 않게 보장할 수 있지만 부작용이 있습니다.

교착 상태 회피

• 교착 상태 회피는 교착 상태가 발생하지 않을 정도로 조심히 자원을 할당하는 방식입니다.
• 교착 상태 회피는 자원이 충분한 상태라면 교착 상태가 발생하지 않지만, 자원이 한정된 상태에서 자원 요구가 많은 경우 교착 상태 발생 위험이 증가하는 것을 염두한 방식입니다.
• 따라서, 교착 상태 회피는 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼 자원을 배분하는 방법입니다.
• 교착 상태 회피 방안 용어
  • 안전 순서열(safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미합니다.
  • 안전 상태(safe state) : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자우너을 할당받고 종료될 수 있는 상태입니다.
    • 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태
  • 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상황입니다.
    • 안전 순서열이 없이, 시스템이 불안전 상태에 놓이면 교착 상태가 발생할 수 있는 위험이 있는 상태입니다.
• 교착 상태 회피를 위해서는 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하여, 항시 안전 상태를 유지하도록 자원을 할당하는 방식입니다.

교착 상태 검출 후 회복

• 교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식입니다.
• 교착 상태 검출 후 회복 방식의 운영체제는 프로세스들이 자원 요구 시 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사하여, 교착 상태가 검출되면 회복합니다.
• 교착 상태 회복 방식
  • 선점을 통한 회복 : 교착 상태가 해결될 때까지 다른 프로세스의 자원을 강제로 빼앗아 한 프로세스씩 자원을 몰아주는 방식입니다.
  • 프로세스 강제 종료를 통한 회복 : 운영체제는 교착 상태에 놓인 프로세스를 모두 강제 종료하거나, 교착 상태가 없어질 때까지 한 프로세스씩 강제로 종료합니다.
    • 모두 강제 종료 시 교착 상태가 확실히 해결되지만 많은 프로세스들의 작업 내역을 잃습니다.
    • 하나 씩 강제 종료하는 경우, 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기합니다.

교착 상태를 무시

• 타조 알고리즘(ostrich algorithm) : 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식입니다.
  • 문제 발생의 빈도나 심각성에 따라서 이 방식을 사용하기도 합니다.

---

5주차 미션

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

1.1. p. 363 : 확인 문제 1번 : 뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것을 고르세요.

보기

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

정답

4번 : 큐를 이용해 wait(), signal()을 구현하여 바쁜 대기 없이 세마포를 이용할 수 있습니다.

2. 선택 미션 : Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기

• 임계 구역(critical section)
  • 공유 자원 중 두 개 이상의 프로세스를 동시에 실행하여 문제가 발생하는 자원을 의미합니다.
  • 임계 구역에 접근하는 프로세스들 중 하나가 실행 중이면 나머지 프로세스들은 기다려야 합니다.
• 상호 배제(mutual exclusion)
  • 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역으로 들어올 수 없는 것을 의미합니다.

---

참조 자료

• 혼자 공부하는 컴퓨터 구조+운영체제 : Chapter 12 ~ 13