운영체제 정리 - 6장

1. 교착상태 원리

교착상태

• 영속적인 블록 상태

  • 영구적인 이유는 기다리던 사건이 결코 발생하지 않기 때문

• 공유자원을 기다리면서 실행대기를 서로 하는 것 (서로 놓지 않음)

• 2개 이상의 프로세스들의 자원을 기다리면서 자신도 블록된다.

결합 진행 다이어그램

• P와 Q라는 두 개의 프로세스가 A와 B라는 자원을 경쟁적으로 사용하며, 수행하는 과정을 보여준다.

  • 맞물리면 진행불가, 두 프로세스를 종료시킬 수 밖에 없다.

1)

• 프로세스 Q가 자원 B를 획득, 자원 A를 획득, 수행 완료 이후 두 자원 반납

• 이제 프로세스 P가 수행되면 두 자원 사용 가능

2)

• 프로세스 Q가 자원 B, A를 획득한 후, 프로세스 P가 수행을 시작하나, 자원 A를 획득하지 못하고 블록

• 프로세스 Q가 수행을 완료하고 자원들을 반납

• 이제 프로세스 P가 깨어나면 두 자원 사용 가능

3)

• 프로세스 Q가 자원 B 획득, 프로세스 P가 자원 A 획득,

• 프로세스 Q는 A 획득을 시도하다가 블록, 프로세스 P는 B 획득을 시도하다가 블록

  • 교착상태

4)

• 프로세스 P가 자원 A 획득, 프로세스 Q가 자원 B를 획득

• 프로세스 P는 B 시도하다 블록, 프로세스 Q는 A 시도하다 블록

  • 교착상태

결합 진행 다이어그램 대안

• 교착상태의 발생은 동적인 프로세스 수행 과정 뿐만아니라 응용의 세부사항(프로그램 작성 방법)에도 영향을 받는다.

교착상태의 다른 예들

• 재사용 가능한 자원

  :교착상태는 한 프로세스가 자원을 획득한 후에 다른 자원을 원하며, 다른 프로세스는 반대 순서로 자원을 획득한 후 다른 자원을 원하면 발생

  • ex) 처리기, I/O 입출력 채널, 주/보조 메모리, 장치, 파일이나 데이터베이스나 세마포어와 같은 자료구조

  • 메모리 할당

    • 가용 메모리 크기 = 200kbytes

    

  • 디스크와 테이프를 이용한 백업

    • 한 번에 하나만이라 가정 시

    

• 소모성 자원

  : 싱크가 맞지 않으면 교착상태가 발생

  • 인터럽트, 시그널, 메세지, I/O 버퍼에 존재하는 정보 등

  • 통신

  

자원 할당 그래프 (Resource Allocation Graph)

교착상태의 4가지 조건

1) 상호배제 (mutual exclusion)

• 한 순간에 한 프로세스만이 자원을 사용할 수 있다.

2) 점유대기(hold and wait)

• 이미 자원을 보유한 프로세스가 다른 자원을 요청하여 기다리고 있다.

3) 비선점 (no preemption)

• 프로세스에 의해 점유된 자원을 프로세스가 강제적으로 빼앗을 수 없다.

4) 환형대기(circular wait)

• 프로세스들 간에 닫힌 연결 (closed chain)이 존재한다.

  • 즉 자원 할당 그래프에서 환형이 만들어지는 것

  • 닫힌 연결에서 블록 된 프로세스가 자원을 점유하고 있는데, 이 자원을 체인 내부의 다른 프로세스가 원하여 대기하고 있다.

<교착상태 가능 vs 발생>

• 가능: 상호배제, 점유대기, 비선점

• 발생: 상호배제, 점유대기, 비선점, 환형대기

교착상태 해결을 위한 3가지 접근방법

예방 > 회피 > 발견

→ strict, 병행성 떨어짐

• 교착상태 예방(Prevention)

  • 4가지 조건 중 어떤 하나를 절대 발생하지 않도록한다.

• 교착상태 회피(Avoidance)

  • 교착상태가 일어나지 않을 듯한 요청을 운영체제가 허용

• 교착상태 발견(Detection)

  • 교착상태가 발생하면 그것을 발견하고 회복하는 것

• 운영체제를 설계할 때, 교착상태 해결을 위해 한가지 전략만을 사용하는 경우는 거의 없다.

• 상황에 따라, 그리고 시스템의 조건에 따라 다른 전략을 사용하는 것이 더 효율적이다.

2. 교착상태 예방

• 교착 상태가 발생하기 위한 4가지 필요충분 조건 중 하나를 설계단계에서 배제하는 기법

  • 간접적인(Indirect) 방법

    • 교착상태가 발생하는 3가지 필요조건을 예방

      • 상호배제, 점유대기, 비선점을 예방

  • 직접적인(Direct) 방법

    • 환형대기 상태가 되는 것을 예방

      • 환형대기 상태가 되는 것을 예방

• 상호배제

  • 적절치 x

  • 시스템 설계시, 상호배제 조건을 없앨 수 없다.

    • 운영체제가 지원해주어야 한다.

• 점유대기

  • 비효율적

  • 프로세스가 필요한 모든 자원을 한꺼번에 요청

    • 모든 자원을 할당 받을 수 있으면 계속 수행, 하나의 자원이라도 할당 받을 수 없다는 어떤 자원도 할당받지 않을 채 대기

• 비선점

  • 적절치 x

  • 프로세스가 새로운 자원 요청에 실패하면 기존의 자원을 반납한 수 다시 요청하거나, 운영체제가 강제적으로 자원을 반납시킨다.

• 환형대기

  • 자원들의 할당 순서를 정하면 없앨 수 있다.

    • 점유대기의 경우처럼, 환형대기 조건을 없애는 것은 프로세스의 수행지연과 불필요한 자원 할당 거부를 야기할 수 있다.

💨 교착상태 예방은 자원의 사용과 프로세스 수행에 비효율성을 야기할 수 있다.

3. 교착상태 회피

• 교착상태 회피 기법은 교착 상태 발생을 위한 4가지 조건 중 1, 2, 3을 허용하며, 또한 4처럼 자원 할당 순서를 미리 정하지 않는다.

• 자원을 할당할 때 교착 상태가 발생 가능한 상황으로 진행하지 않도록 고려한다.

  • 미래의 자원 요청 정보 필요

  • 현재 자원의 가용 개수와 프로세스의 자원 요구향을 미리 알고 있어야 가능하다.

자원 할당 거부 (Resource Allocation Denial)

• 자원을 할당할 때 교착상태가 발생할 가능성이 있는지 여부를 동적으로 판단.

• 교착 상태의 가능성이 없을 때 자원 할당

  • 안전한 상태를 계속 유지할 수 있으면 자원 할당

• But, 각 프로세스들이 필요한 자원들을 미리 운영체제에게 알려야 한다.

• 시스템 상태 구분

  • 안전한 상태(safe state)

    • 교착상태가 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 진행 경로가 존재

    • 지금 들어온 요청을 허용해도 다른 프로세스들의 요청을 전부 만족시키는 것

    • 예) banker’s algorithm

      

  • 안전하지 않은 상태(unsafe state)

    • 안전한 자원 할당 경로가 없는 상태

    • 이미 돌고 있는 프로세스들이 알아서 반납하지 않는 한, 지금 요청한 프로세스가 자원을 사용할 수 없는 경우

    

프로세스 시작 거부 (Process Initialization Denial)

• 교착상태가 발생할 가능성이 있으면 프로세스 시작 거부

• 모든 프로세스들이 요구한 자원의 개수가 전체 자원 개수보다 적으면, 교착상태가 발생하지 않는다. (C < R)

  • 새로운 프로세스와 기존의 프로세스들이 요구하는 자원의 개수가 그 자원의 전체 개수보다 적은 경우에 수행을 허용하는 것 (C - A < V)

교착 상태 회피 알고리즘

<안전한 상태 확인 알고리즘 (은행원 알고리즘)>

교착상태 회피 장단점

• 장점

  • 교착상태 발견에 비해 선점이나 롤백의 필요가 없다.

  • 교착 상태 예방에 비해 덜 제한적이다.

• 단점

  • 미리 전체 사용 자원을 운영체제에 알려야 한다.

  • 프로세스들은 각자 독립적이어야 한다.

    • 수행 순서 종속 관계가 없어야 한다.

  • 자원 개수가 고정되어 있어야 한다.

  • 자원을 선점한 채 종료하는 프로세스는 없어야 한다.

4. 교착상태 발견

교착상태 예방 전략은 상당히 보수적이다. 즉, 교착상태가 발생하지 않도록하기 위해 자원 접근에 대한 제한과 프로세스의 수행에 제한을 둔다.

• 교착상태 발견은 매우 낙관적인 방법으로, 자원 접근에 대한 제한이나 프로세스의 행위에 제한을 두지 않는다.

1) 자원 할당이 요구될 때마다 매번 수행

• 교착상태를 빠른 시점에 발견할 수 있으며, 시스템의 상태가 점진적으로 변하기 때문에 발견 알고리즘도 간단해진다.

  • 처리 비용이 커진다 (부하가 큼)

2) 주기적으로 가끔 수행

• 부하는 적지만 발견이 늦어지고 발견 기법도 복잡해진다.

교착상태 발견 알고리즘

1) 할당 행렬 A에서 행의 값이 모두 0인 프로세스를 우선 표시(mark)한다.

2) 임시 벡터 W 를 만든다. 그리고 현재 사용 가능한 자원의 개수(결국 가용 벡터V 의 값)를 벡터 W 의 초기값으로 설정한다.

3) 표시되지 않은 프로세스들 중에서 수행 완료 가능한 것이 있으면 (요청 행렬 Q에서 특정 행의 값이 모두 W보다 작은 행에 대응되는 프로세스) 이 프로세스를표시한다. 만일 완료 가능한 프로세스가 없으면 알고리즘을 종료한다.

4) 단계 3의 조건을 만족하는 행을 Q에서 찾으면, 할당 행렬 A에서 그 행에 대응되는 값을 임시 벡터 W에 더한다. 그리고 3 단계를 다시 수행한다.

• 종료 후에도 표시되지 않은 프로세스가 존재한다면, 교착상태가 발생한 것이다.

  • 교착상태의 존재여부만 알 수 있으며, 더 진행되면 교착상태가 생길지 여부는 파악하지 못한다.

교착상태 회복 알고리즘

• 교착 상태에 포함되어 있는 모든 프로세스를 중지시킨다.

• 교착상태에 포함되어있는 각 프로세스의 수행을 롤백시킨다.

  • 즉 미리 정의된 특정 체크 포인트 시점까지 되돌린 후 다시 수행시킨다.

  • 다시 수행시켰을 때, 다시 교착상태에 빠질 수 있다는 단점

• 교착상태가 없어질 때까지 교착상태에 포함되어 있는 프로세스들을 하나씩 종료시킴

  • 교착상태가 없어질 때까지 교착상태에 포함되어 있는 자원을 하나씩 선점시킨다.

    • 하나씩 선점한 수 교착상태 발견 알고리즘을 수행시켜 아직 교착상태가 존재하는지 파악한다.

    • 이때 자원을 선점당한 프로세스는 자월을 할당받기 전 시점으로 롤백하고, 그 시점부터 다시 수행한다.

종료 (또는 선점될) 프로세스 선택 기준

• 시스템 중심적인 비용 고려

  • 지금까지 사용한 처리기 시간이 적은 프로세스부터

  • 지금까지 생산한 출력량이 적은 프로세스부터

  • 이후 남은 수행시간이 가장 긴 프로세스부터

  • 할당받은 자원이 가장 적은 프로세스부터

  • 우선 순위가 낮은 프로세스부터

• 사용자 중심적인 기준

  • 우선순위가 낮은 프로세스부터

5. 식사하는 철학자 문제

• 전제

  • 철학자는 밥을 먹거나, 생각하거나

  • 접시, 포크는 총 5개

• 고려사항

  • 임계영역이 지켜져야한다.

    • 즉 두명의 철학자가 동시에 같은 포크를 사용할 수는 없다.

  • 교착상태나 기아에 빠져서는 안된다.

    • 교착상태와 기아문제에 대한 기본적인 원리를 내포하고 있다.

세마포어를 이용한 해결 방법

• 철학자는 우선 왼쪽에 있는 포크를 먼저 잡고, 그 이후에 오른쪽에 있는 포크를 잡는다.

• 식사를 마친 이후에 두개의 포크들을 식탁에 내려 놓는다.

• 문제점

  • 모든 철학자가 일제히 왼쪽을 잡고, 오른쪽을 잡으려고하면 포크가 없다.

    • 교착상태 발생

세마포어를 이용한 다른 해결 방법

• 해결방법

  • 5개의 포크를 더 구입

  • 한 번에 최대 4명까지의 철학자가 식탁에 앉을 수 있도록 제한

    • 최소 1명은 식사 가능

  • 오른쪽 먼저 잡는 철학자랑 왼쪽 먼저 잡는 철학자를 섞는다.