운영체제 정리 4. 병행성 : 교착상태와 기아상태

교착상태 조건

-상호 배제 조건 : 한 순간에 한 프로세스만이 자원을 사용할 수 있어야 한다.

-점유대기 조건 : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다려야 한다.

-비선점 조건 : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제로 빼앗을 수 없다.

-환형 대기 조건 : 프로세스들 간에 닫힌 연결이 존재한다. 자원 할당 그래프에서 환형이 만들어 지는 것이다.(예시 참고)

교착상태 예방

-감기와 같이 교착상태도 예방 할 수 있다 그 방법은 교착상태가 일어나는 상호배제, 점유대기, 비선점 조건들을 허용하지 않거나 직접적으로 환형대기가 생기지 않도록 하는 것이다.

-상호 배제

-시스템을 설계할 때 상호 배제 조건을 없앨 수는 없으므로 상호 배제가 필요시에 OS가 이를 지원해 주어야 한다.

-점유대기

-점유대기는 다음과 같은 방법으로 없앨 수 있다. 프로세스는 자신이 사용할 모든 자원을 한순간에 요청하는데, 만일 모든 자원을 할당받을 수 있으면 계속 수행된다. 반면 하나의 자원이라도 할당 받지 못하면, 어떠한 자원도 할당받지 않은 채 대기하도록하는 것이다. 이 방법을 사용하면 점유대기를 없앨 수는 있으나 세가지 비효율성이 생긴다. 첫째는 프로세스가 자원을 할당 받을 때까지 계속 기다려야한다는 것, 둘째는 한꺼번에 받은 자원 중 일부는 프로세스가 끝날 때 쯤에 사용되기 때문에 자원이 효율적으로 사용되지 않는 다는 것, 셋째는 프로세스가 미래에 필요로할 자원을 미리하는 것은 어렵다는 것이다.

-위 설명을 읽어보면 점유대기를 없애기 위해서는 모든 수준(모듈, 프로세서, 쓰레드 등등)이 요구하는 모든 자원을 미리 알아야 한다.

-비선점

-비선점 조건은 두 가지의 방법으로 없앨 수 있다. 첫째는 자원을 점유한 프로세스가 다른 자원을 요청했을 때 할당받을 수 없다면, 일단 자신의 점유한 자원을 반납하고 이후 프로세스가 원래 자원과 새로 원하는 자원을 함께 요청하는 것, 둘째는 한 프로세스에서 다른 프로세스가 점유한 자원을 원하면 OS가 우선순위에 따라서 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에게 할당할 수 있다.

-비선점을 없애는 것은 자원의 상태를 복구하고 저장하기 쉬운 자원에 사용할 수 있다. ex)프로세서

-환형대기

-환형대기 조건들은 자원들의 할당 순서를 정하면 없앨 수 있다. 예를 들어 프로세스가 자원 R을 할당받았다면, 이후 이 프로세스는 자원 R다음 순서를 갖는 자원들을 요청할 수 있는 것이다. 즉 자원마다 할당순서를 정해

R1<R2인 할당 순서를 정했다고 하면 R1을 할당받으면 그다음 R2가 할당될 수 있게된다. 만약 P1, P2 프로세스중 P1가 R1을 할당하고 R2를 요청했다. 여기서 교착상태가되려면 P2가 R2를 할당하고 R1을 요청해야하는데 이는 OS에서 정한 할당 순서에 위배되기 때문에 나타날 수 없다.

-환형대기를 없애는 일은 프로세스의 수행 지연과 불필요한 자원 할당 거부를 생기게 할 수 있다.

교착상태 회피

-예방은 미리 교착상태를 생기게 하는 조건을 없애는 것이지만 이는 프로세스 수행에 비효율을 만든다. 반면에 교착생태 회피는 상호배제, 점유대기, 비선점을 허용하지만 그렇다고 자원 할당 순서를 미리 정하지도 않는다 그 대신 자원을 할당할 때 교착상태가 발생 가능한 상황으로 진행하지 않도록 고려하는 방법이다.

-프로세스 시작 거부

-프로세스가 시작하려 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면, 프로세스를 시작시키지 않는 것이다.

-자원 할당 거부

-수행 중인 프로세스가 요구하는 추가적인 자원 할당이 교착상태 발생의 가능성이 있으면, 자원을 할당하지 않는 것이다.

-자원할당을 거부하는 방법을 은행원 알고리즘이라고 한다. 은행원 알고리즘에서는 안전한 상태와 불안전한 상태가 있는데 교착상태가 발생하지 않도록 프로세스에게 자원을 할당할 수 있는 진행 경로가 존재하면 안전한 상태, 그러한 진행경로가 없으면 불안전한 상태이다.(자세한 것은

밑의 예시 그림에서)

 먼저 A상태를 보자 프로세서 1~4는 각각 R1~3에 대한 자원을 요구를 행렬C표에서 볼 수 있다. 그리고 현재 P1~4가 각각 할당받은 자원을 할당 행렬A에서 볼 수 있고, 아직 할당 받지 못해서 필요한 자원을 C-A표에서 볼 수 있다. R1~3에 대한 총 자원은 R표에서 볼 수 있다. 그리고 R1~3에서 사용가능한 벡터가 V표에 나와 있다. 그럼 여기서 과연 이 상태가 안전한지 불안전한지 살펴보면 먼저 A상태에서 가용가능한 자원으로 끝낼 수 있는 프로세서는P2 이므로 P2에게 1남은 R3자원을 주면 P2는 끝나고 자신이 가진 자원을 반납하고 B상태로 넘어간다. B에서는 P1을 완료하여 P1을 끝내고 C상태로 넘어간다 C에서는 P3를 끝낼 수 있으므로 P3를 끝내고 D상태로 넘어간다. D상태에서 P4를 끝내면 수행이 끝난다. 결론적으로 모든 프로세서를 모두 무사히 끝내게 되므로 안전한 상태이다.

만약 초기상태에서 P2가 아닌 P1에게 자원을 할당시켰다면 교착상태가 일어나게되어 불안전한상태가 되었을 것이다. 이 처럼 미리 어떠한 프로세서에 자원을 할당해야 안전한 상태를 유지할 수 있을지 볼 수 있다.

-교착상태 회피를 사용하면 교착상태 예방에 비해서 자원 할당이 휠씬 자유로우므로 시스템에서 자원 효율이 높아진다. 하지만 각 프로세스들이 사용할 최대 자원 요구량을 os에게 미리 알려주어야 한다는 점과 프로세스들은 서로 독립적으로 수행 순서 같은 종속 관계가 없어야 한다는 점, 자원 개수가 고정적이여야 한다는 점, 자원을 선점한 상태로 종료되는 프로세스가 없어야 한다는 점과 같은 단점이 있다.

교착상태 발견

-교착상태는 말그대로 교착상태를 발견 하는 알고리즘이다. 교착상태 발견은 자원 할당이 요구될 때마다 매번 수행 할 수도 있고, 주기적으로 가끔 수행될 수도 있다.

-교착생태를 발견 할 수 있는 알고리즘

알고리즘 순서는 이러하다

1. P4는 할당 받은 자원이 없다. 따라서 P4에 마킹을 한다.

2. 가용벡터는 (0 0 0 0 1)로 초기화 된다.

3. P3의 요청을 만족 할 수 있으므로 P3에 마킹을 한다. 가용벡터가 (0 0 0 1 1)이 된다.

4. 마킹이 되지 않은 프로세스들 중에서 가용벡터로 끝낼 수 있는 프로세스가 존재하지 않으므로 알고리즘이 종료된다.

알고리즘 종류 후에도 P1과 P2는 마킹되지 않은 상태로 남아 있으며 이는 P1과 P2가 교착상태임을 뜻한다.

교착상태 회복 알고리즘

-교착생태가 발견되면 그것을 해결하기 위한 기법이 필요하다. 다음과 같은 것들이 있다.

-교착상태에 포함된 모든 프로세스들을 중지시키는 것, 생각보다 많은 OS가 사용함

-교착상태에 포함된 각 프로세스의 수행을 일정 체크포인트부터 다시 수행시키는 것, 다시 교착상태에 빠질 수 있다. 병행 처리의 비결정 특성으로 인해 확률이 낮기는 함

-교착상태가 없어질 때까지 교착상태에 포함된 프로세스들을 하나씩 종료시킴, 종료시키는 프로세스는 비용이 가장 적은 것부터 종료됨, 하나씩 종료시키면서 발견알고리즘을 실행 시킴

-교착상태가 없어질 때까지 교착상태에 포함된 자원을 하나씩 선점시킴, 자원은 비용이 가장 적은 것부터 선택함 자원을 선점시키고 발견 알고리즘을 통해 교착상태가 사라지면 그 프로세스를 자원을 할당 받기 전으로 되돌림

식사하는 철학자 문제

-식사하는 철학자 문제는 유명한 교착상태를 다루는 문제로 5명의 철학자가 원탁 테이블에 앉아 식사하는 것으로 같은 집에서 살고 있는 철학자들의 삶은 사색과 식사로 구성된 단순한 삶이다. 또한 철학자들은 오랜 사색을 통해 스파게티가 자신들의 사색에 도움이 되는 유일한 음식이라는 결론에 도달하였다. 철학자들은 스파게티를 먹기 위해 2개의 포크를 사용한다. 식탁의 배치는 밑의 그림과 같다 원탁 테이블 가운데에는 스파게티가 담긴 큰 그릇이 하나 있다. 그리고 철학자가 개인적으로 사용하는 접시가 5개 있으며, 접시 양쪽에는 포크가 있다(결국 테이블 위에는 5개의 포크가 존재한다). 철학자는 배가 고프면 자신의 정해진 위치로 가서 큰 그릇에 담긴 스파게티를 자신의 접시에 담아 먹는다. 이때 문제에서 철학자는 식사를 위해 두개의 포크를 사용해야 한다는 것이다. 철학자는 자신의 접시 양 옆에 놓인 포크를 사용하려 한다. 이때 다음 두 가지가 고려되어야 한다. 첫째, 임계영역이 지켜져야 한다. 즉 두 명의 철학자가 동시에 같은 포크를 사용할 수는 없다. 둘째, 교착상태나 기아에 빠져서는 안 된다. 문제가 사실 왜 이런 의미없는 것을 해결해야되나 하는 의문을 들게하는게 사실이지만 이 문제는 명행 프로그래밍의 어려움을 다시금 느끼게 해줄 수 있는 공유 자원을 통한 협동의 대표적인 문제 입니다.

세마포어를 이용한 식사하는 철학자 문제 해결 방법이다. 철학자는 우선 왼쪽에 있는 포크를 집고(wait(fork[i])), 그 이후에 오른쪽에 있는 포크를 집는다(wait(fork[i+1])). 식사를 마친 이후에 철학자는 두 개의 포크들을 식탁에 다시 내려놓는다. (signal(fork[i+1])),signal(fork[i]) 이러한 방법은 교착상태를 유발한다는 문제점이 있다. 즉 모든 철학자들이 동시에 식탁에 앉고 동시에 왼쪽 포크를 집었다고 가정하면, 오른쪽 포크를 집으려 해도 거기에는 포크가 없게 된다. 결국 아무도 식사를 하지 못하게 되는 것이다.

교착상태를 피하기 위해서 포크를 5개 더 구입하는 것도 하나의 방법이다. 아니면 철학자들에게 포크 하나로 스파게티를 먹는 법을 가르치거나 혹은 최대 4명까지만 식탁에 앉도록 하는 방법도 있다. 이 제한은 최소한 한명의 철학자는 두 개의 포크를 집을 수 있으며 결국 식사할 수 있도록 하여 교착상태가 생기지 않도록 할 수 있다. 바로 위에 나오는 방법이다. room을 즉 방에 들어가는 최소 인원을 제한 함으로써 밥을 원활히 먹을 수 있는 것이다.