12 > 동기화(4)

* 해당 게시물은 경북대학교 컴퓨터학부 강의초빙교수, 배준현 교수님의 강의를 보고 작성되었음을 미리 알려드립니다. ( 개인적인 공부를 정리한 글입니다. )

 

> 주니온 TV Youtube Channel.  https://www.youtube.com/channel/UCOcPzXDWSrnaKXse9XOPiog

주니온TV 아무거나연구소

 

> 주니온 TV Inflearn page.  https://www.inflearn.com/users/@joonion

주니온님의 소개 - 인프런 | 온라인 강의 플랫폼

---

[ 추가 Youtube 영상 ]

기본 개념 | 교착상태 | 운영체제

 

[  ] 교착 상태 Dead lock.

시스템 측면에서 자원의 요구가 뒤엉킨 상태.

한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서 발생될 수 있는 사건을 서로 무한히 기다리는 상황.

* 대부분의 OS에서 교착상태를 완전히 예방해 주지는 못한다. > 자주 일어나는 현상이 아니기에, 사용자가 직접 어느 한쪽을 없애서 해결한다.

* 보통은 정교하게 구성되지 못한 Multi thread application 에서 발생한다. -> app을 강제 종료하거나 재시작한다. ( windows OS에서 응답없음이 나온다)

 

> 전형적인 멀티 스레드 교착 상태 사례

 

> 세마포어와 교착 상태.

1로 초기화된 semaphore S와 Q가 있다고 할 때, P0에서 S를 0으로 변경 후 진입했다. 그리곤 P1 에서는 Q를 0으로 변경 후 진입하고 S에 대해 wait 호출을 했다.

이미 P0에서 S를 0으로 바뀐 상태에서 다시 돌려주지 않았으므로 P1은 계속 기다린다. P0는 실행 도중 Q에 대한 접근이 필요하여 Semaphore를 확인했는데 이 역시 이미 P1에서 0으로 바꾼 상태라 진입할 수 없게 된다.

서로 이러지도 저러지도 못하는 Deadlock 상황이 발생한다.

 

> 교착상태를 유발시킬 수 있는 잠재적 요인.

- 공유 자원 > software resource (Mutex, Spin lock, Semaphore, File lock …), Hardware resource(Memory, Printer, Processor)

- 한 스레드가 여러 자원을 동시에 필요할 때, 한 번에 하나씩 자원을 할당하는 OS의 정책에 의해 발생한다.

 

> 교착 상태 발생 조건.

- 네 조건이 동시 성립할 때 발생한다.

1) Mutual exclusion (상호 배제) - 하나 이상의 자원이 비공유 모드로 점유돼야 한다.

2) Hold-and-wait (점유 대기) - 최소한 자원 하나를 점유한 채, 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기한다.

3) No preemption (비선점) - 점유된 자원은 다른 프로세스에 의해 선점될 수 없음.

4) Circular wait (순환 대기) - 프로세스들이 체인을 구성하여 자원을 상호 요청한다.

 

> 자원 할당 그래프

교착 상태를 보다 정확히 기술하는 방법.

G = (V, E), Vertex의 집합 V와, Edge의 집합 E 로 구성.

간선은 Process에서 resource를 향할 때는 요청 간선(Request edge)이라 하며, resource에서 Process를 향할 때는 할당 간선(Assignment edge)이라 한다.

 

 

> 교착 상태 해결 기법.

- 교착 상태 예방 = 교착 상태 발생 요건 중 하나라도 발생하지 않게 함.

1) 점유와 대기 조건 방지

  스레드가 자원을 요청할 때에는 다른 자원들을 점유하지 않음을 보장해야 함. > 자원 이용률이 낮고 기아상태 발생 가능

  어떤 임의의 프로세스가 자원을 요청할 때에는, 다른 자원들을 점유하고 있지 않다.를 보장한다.

  1-1) 각 스레드는 자신이 필요한 자원 전부를 요청하여 할당 받는다.

    이 방법은 실행 도중 자원이 없어서 대기상태에 빠지지 않게 한다.

  1-2) 각 스레드는 실행을 위해 일부 자원들만을 요청 할 수 있되, 추가적인 자원 요청은 모든 자원을 방출한 뒤에 가능하다. 

    5개의 자원이 필요한 스레드가 자원을 3개를 먼저 확보하고 실행 뒤, 추가 적인 자원 요청은 3개의 처리가 끝난 후 가능하다.

2) 비선점 조건 방지 > 이미 실행한 작업의 상태를 잃을 수 있다.

  스레드가 실행 중 이미 선점 된 자원을 요청하게 된다면, 실행하면서 선점한 자신의 자원들 모두를 비선점 시킨다.

  이 방법은 작업 상태를 쉽게 복구/저장이 가능할 때나, 빈번하게 발생하지 않을 때 사용하면 좋다.

3) 순환 대기 조건 방지

  계층적 요구 기법으로 모든 자원에 순서를 보여하고 이 순서대로 각 스레드들은 자원을 요청할 수 있다.

  이 방법은 순환대기의 가능성을 제거하여 교착 상태를 예방하며, 자원에 대한 접근을 불필요하게 거부하기에 효율적이지 못하다.

할당 받은 뒤에 추가적인 자원 요청을 하더라도, T4 입장에서 T1의 자원할당이 아직 이루어지지 않았음으로 R4에 대한 자원을 요청하지 않는다.

 

- 교착 상태 회피 = 자원 할당 전에 미리 스레드의 수행 상태를 파악하여 자원이 할당될 경우를 가정하여 교착 상태가 발생하면 자원 할당을 중지한다. (예방 보다는 조금 더 완화된 정책이다.)

  자원이 어떻게 사용될 지에 대한 추가 정보를 제공하도록 요구한다.

  각 프로세스는 자신이 필요한 각 유형의 자원들의 최대 수를 선언하고, 이 값을 바탕으로 교착상태가 발생하지 않는 알고리즘이다.

  안정 상태(Safe state)와 불안정 상태(Unsafe sate)로 나눠진다. 여기서 불안정 상태는 교착 상태 발생 가능성이 있다는 뜻이다. 이 불안전 상태를 막아 시스템을 항상 불안정 상태에 들어가지 않게 하여 교착 상태를 회피한다.

- 교착 상태 탐지 & 복구 = 발생을 탐지하여 시스템에 문제가 발생하지 않도록 처리함.

- 교착 상태 무시 = OS의 일반적 선택

 

 

[  ] Safe State

A state is safe if the system cam allocate resources to each thread (up to its maximum) in some order and still avoid a deadlock.

safe sequence가 존재한다면 각 thread들은 safe state를 유지하면서 자원을 할당 받을 수 있다.

 

[  ] 은행가 알고리즘 (Banker's Algorithm)

각각의 자원 유형들이 다수의 인스턴스를 갖고 있는 경우에 활용될 수 있다.

프로세스 시작 시, 자신이 필요한 각 자원의 최대 개수를 미리 선언하고 프로세스의 자원요청에 대해 안전상태와 불안정 상태를 판단한다.

RAG is not applicable to a resource allocation system with multiple instances of each resource type.

한 임계 영역에 자원이 두개가 있고, T0는 자원 A를, T1은 자원 B를 할당한다. 이럴 경우에 RAG(Resource Allocation Graph)를 보면 Cycle이 발생하지만 실행에는 전혀 문제 없다. 즉, 이런 경우에 RAG를 대입할 수 없다.

 

[  ] Data structures.

- Let n be the number of threads in the system and let m be the number of resource types.

  Available: A vector indicates the number of available resource types.

  Max: A matrix defines the maximum demand of each thread.

  Allocation: A matrix defines the number of resources of each type currently allocated to each thread.

  Need: A matrix indicates the remaining resource need of each thread.

 

- Available[m]: if Available[j] == k, then k instances of Rj are available.

- Max[n × m]: if Max[i][j] == k, then Ti may request at most k instances of Rj

- Allocation[n × m]: if Allocation[i][j] == k, then Ti is currently allocated k instances of Rj.

- Need[n × m]: if Need[i][j] == k, then Ti may need k more instances of Rj

 

An illustrative example:

- a set of five threads: T = {T0, T1, T2, T3, T4}

- a set of three resource types : R = {A, B, C}

- the number of instances of each resource types : A = 10, B = 5, C = 7

- the snapshot representing the current state of the system.

	(Allocation) A B C	(MAX) A B C	(Available) A B C	(Need) A B C
T0	0 1 0	7 5 3	3 3 2	7 4 3
T1	2 0 0	3 2 2		1 2 2
T2	3 0 2	9 0 2		6 0 0
T3	2 1 1	2 2 2		0 1 1
T4	0 0 2	4 3 3		4 3 1

 

 

1) work vector는 available 로 초기화, Finish vector는 Thread 수 만큼 false

2) 조건(idx is specified thread number, finish[idx] 가 false 면서 Need[idx] Work 보다 작거나 같을 때 할당을 해준다.

3) Work = Work + Allocation[idx] 을 하고 finish[idx] = true; 2번 Step으로 보낸다.

 

초기화 work[] = {3, 3, 2}, finish[] = {f, f, ,f, f, f }

idx = 0, need[0] = {7, 4, 3} <= {3, 3, 2} > 조건을 만족하지 못함.

idx = 1, need[1] = {1, 2, 2} <= {3, 3, 2} > work[] + allocation[] = {3, 3, 2} + {2, 0, 0} > work[] = {5, 3, 2}, finish[1] = true로 값이 변한다.

idx = 2, need[2] = {6, 0, 0} <= {5, 3, 2} > 조건을 만족하지 못함.

idx = 3, need[3] = {0, 1, 1} <= {5, 3, 2} > work[] + allocation[] = {5, 3, 2} + {2, 1, 1} > work[] = {7, 4, 3}, finish[3] = true로 값이 변한다.

idx = 4, need[4] = {4, 3, 1} <= {7, 4, 3} > work[] + allocation[] = {7, 4, 3} + {0, 0, 2} > work[] = {7, 4, 5}, finish[4] = true로 값이 변한다.

 

Loop

 

finish[idx] 가 true는 생략. (조건에 의해)

idx = 0, need[0] = {7, 4, 3} <= {7, 4, 5} > work[] + allocation[] = {7, 4, 5} + {0, 1, 0} > work[] = {7, 5, 5}, Finish[0] = true로 값이 변한다.

idx = 2, need[2] = {6, 0, 0} <= {7, 5, 5} > work[] + allocation[] = {7, 5, 5} + {3, 0, 2} > work[] = {10, 5, 7}, finish[2] = true로 값이 변한다.

 

finish가 된 순서를 보면 (첫번째에 완료된 Threads) T1, T3, T4, (두번째에 완료된 Threads) T0, T2 순이다.

이 순서를 지킨다면 Safety criteria 를 만족한다.