[혼공컴운] 5주차_끝이 보인다(Ch 12 ~ 13)

12-1) 동기화란

동시다발적으로 실행되는 많은 프로세스는 서로 데이터를 주고받으며 협력하며 실행된다.

⇒ 협력하여 실행되는 프로세스들은 실행 순서와 자원의 일관성을 보장해야 하기에 반드시 동기화가 필수

• 프로세스 동기화 : 프로세스들 사이의 수행 시기를 맞추는 것

  • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기

  • 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

    • 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

    • 생산자와 소비자 문제

• 공유 자원 : 여러 프로세스 혹은 스레드가 공유하는 자원

  • 전역 변수, 파일, 입출력장치, 보조기억장치가 될 수 있다.

• 임계 구역 : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역

• 레이스 컨디션 : 자원의 일관성이 깨지는 경우

  • 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생

---

상호 배제를 위한 동기화를 위해서는 아래 세 가지 원칙이 반드시 지켜져야 한다!

1. 상호 배제 : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.

2. 진행 : 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 들어가고자 하는 프로세스는 들어갈 수 있어야 한다.

3. 유한 대기 : 한 프로세스가 임계 구역에 진입하고 싶다면 언젠가는 임계 구역에 들어올 수 있어야 한다.( 무한정 대기해서는 안 된다.)

12-2) 동기화 기법

• 뮤텍스 락 : 상호 배제를 위한 동기화 도구

  • 동시에 접근해서는 안 되는 자원에 동시에 접근하지 않도록 만드는 도구

  • 자물쇠 기능

    acquire() {
        while (lock == true) /*만약 임계 구역이 잠겨 있다면 */
                ;                /* 임계 구역이 잠겨 있는지를 반복적으로 확인 */
        lock = true;         /* 만약 임계 구역이 잠겨 있지 안다면 임계 구역 잠금 */
    }
    /* 임계 구역에서의 작업 진행 */
    release() {
        lock = flase;       /* 임계 구역 작업이 끝났으니 잠금 해제 */
    }

• 바쁜 대기 : 임계 구역이 잠겨 있는지 반복적으로 확인하는 대기 방식

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

  • 상호 배제를 위한 동기화 기법

    wait() {   /* 기다려야 할지 알려주는 */
        while (S <= 0)
        ;
        S--;     /* 프로세스의 개수 */
    }

    // 임계 구역
    signal() {  /* 이제 가도 좋다고 신호 주는 */
        S++;
    }

• 공유 자원이 없는 경우 프로세스는 무작정 무한히 반복 → 바쁜대기(CPU 주기 낭비)

⇒ 그래서 프로세스 상태를 대기 상태로 만들고, PCB를 세마포를 위한 대기 큐에 넣는다.

    wait() {
        S--;
        if(S<0) {
             add this process to Queue;   /* 해당 프로세스 PCB를 대기 큐에 삽입 */
             sleep();                     /* 대기 상태 */
         }
     }
     signal() {
        S++;
        if(S<=0) {
             remove a process p from Queue;   /* 대기 큐에 있는 프로세스 p 제거 */
             wakeup(p);                       /* p를 대기상태에서 준비상태 */
         }
     }

• 프로세스의 순서를 제어하는 방법은 세마포의 변수 S를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait 함수 붙이기

• 모니터 : 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리

  • 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 한다.

  • 상호 배제

    • 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입

    • 큐에 삽입된 순서대로 하나씩 공유 자원을 이요

  • 실행 순서 제어

    • 특정 조건을 바탕으로 프로세스 실행

    • 일시 중단하기 위해 조건 변수 사용

  • 상호 배제를 위한 큐 ≠ 조건 변수에 대한 큐

13-1) 교착 상태란

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

  • 식사하는 철학자 문제

⇒ 교착 상태를 해결하기 위해서는

1. 교착 상태가 발생했을 때의 상황을 정확히 표현

2. 교착 상태가 일어나는 근본적인 이유 파악

---

• 자원 할당 그래프 : 교착 상태를 단순하게 표현 가능

  1. 프로세스는 원, 자원의 종류는 사각형

  2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현

  3. 프로세스가 어떤 자원 할당 → 자원에서 프로세스를 향해 화살표

  4. 프로세스가 어떤 자원 기다림 → 프로세스에서 자원으로 화살표

• 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태

---

• 교착 상태 발생 조건

  • 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생김

1. 상호 배제 : 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문

   1. 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 발생

2. 점유와 대기 : 자원을 보유한 채 다른 자원을 기다렸기 때문

   1. 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 발생

3. 비선점 : 프로세스가 자원을 강제로 빼앗지 못했기 때문

4. 원형 대기 : 자원 할당 그래프가 원의 형태로 그려지면 발생 가능성

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

• 교착 상태 예방 : 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당

  • 상호 배제 제거

    • 모든 자원 공유 가능하도록

    • 현실적 사용 X

  • 점유와 대기 제거

    • 자원을 모두 할당 or 아예 할당하지 않음

    • 자원의 활용률이 낮아짐.

    • 기아 현상 야기

  • 비선점 조건 제거

    • 자원을 이용 중인 프로세스로부터 해당 자원 빼앗기

    • 선점하여 사용할 수 있는 일부 자원에 대해서만 효과적

    • 모든 자원이 선점 가능하지 X

  • 원형 대기 조건 제거

    • 모든 자원에 번호 붙이기, 오름차순 자원 할당

    • 모든 컴퓨터 시스템 내 자원에 번호 붙이기 가능성 X

    • 각 자원에 어떤 번호 할당? → 특정 자원의 활용률 떨어짐

⇒ 교착 상태가 발생하지 않음을 보장. 그러나 여러 부작용

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

  • 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주

  • 참고하기 : 은행원 알고리즘

  • 안전 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태

  • 불안전 상태 : 교착 상태가 발생할 수도 있는 상황( 안전 순서열이 없는 상황)

  • 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

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

  • 자원을 요구할 때마다 그때그때 모두 할당

  • 교착 상태 발생 여부 주기적으로 검사

  • 교착 상태 검출 된다면

    • 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식

    • 프로세스 강제 종료를 통한 회복

      1. 모두 강제 종료 : 가장 확실한 방법 그러나 많은 작업 내역 잃게됨

      2. 한 프로세스씩 강제 종료 : 작업 내역 손실 줄이지만 교착 상태 여부 확인하는 과정에서 오버헤드 야기

• 교착 상태 무시로 대처

  • 타잔 알고리즘

숙제!

• P 363, 1번문제

  • 4번, 대기상태로도 가능