OS - Deadlock

hoonding·2022년 5월 8일

Deadlock OS 운영체제

OS

목록 보기

1/1

병행성 : 교착상태와 기아상태

1. 교착상태 정의(Deadlock)

상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.
2개 이상의 프로세스들이 공유 자원에 대한 경쟁(compete)이나 통신(communicate) 중에 발생한다.
block 상태에 놓여 필요한 자원을 이용하기 위해 기다릴 때 발생한다.
Block된 녀석의 Event를 기다리며 Block되어 있는 경우.
영구적인(permanent) block 상태
제한된 자원의 이용률을 높이고 시스템 효율성을 증가시키기 위해 사용하는 병행 처리 기술과 자원 공유에 따른 부작용이다.

Example of Deadlock

1, 6 : 1은 Process Q가 쭉 실행되고 난 뒤 P가 실행된다는 것 → Deadlock 절대 안생김
2 : Process Q가 자원 A,B를 먼저 점유하고 P가 실행됨. P는 A,B를 점유하려고 하지만 이미 Q가 점유하고 있기 때문에 Block되고 Release되는걸 기다린다. 그리고 Release되면 P가 쭉 실행된다.
3 : Q는 B를, P는 A를 점유 → Q는 다음으로 A를 요구, P는 다음으로 B를 요구 → Deadlock!!

Example of No Deadlock

Deadlock을 피하기 위해 Process P의 순서를 바꿨다.
P : Get A → Release A → Get B → Release B
3번 : Q가 B를 점유 → P가 A를 점유 → Q가 A를 요청 → Q Block → P가 A를 Release → Q 가 A를 점유 ,,,

교착상태에 빠지는 Resource의 종류

Reusable Resource(재사용 가능한 자원)
- 한번에 단 하나의 Process만 사용하게끔 해야되고
- 이 자원은 고갈되지 않음.
- Ex) 프로세서, I/O channel, 메인메모리, Device, Data Structure(파일, database, 세마포어..)
Consumable Resource(소모성 자원)
- 한개가 생성(create, produce)되고 소비(destroy, consume)되는 자원.
- Ex) Interrupt, Signal, Message, Information
- Ex) I/O buffers

Deadlock Example 1 → 재사용 가능한 자원을 서로 요구.

Deadlock Example 2 → Memory 요구.(재사용가능한 자원)

200KB를 쓸수있다.
P1이 첫번째 요청으로 80KB, P2가 첫번째 요청으로 70KB를 요청 (남은 사용가능 메모리 50KB)
P1이 두번째 요청으로 60KB를 요청 → Blocked
P2가 두번째 요청으로 80KB를 요청 → Blocked.
두 Process가 Block → 요청될 메모리의 양을 미리 모른다면 교착상태를 해결하기 어려움. → 나중에 가상메모리로 해결한다!

Dedlock Example3 → Consumable Resource(메세지 주고받기...)

두개의 프로세스가 메세지를 서로 받은 다음 메시지를 보내주겠다 라고 코드를 짜면 Deadlock이 걸림.
코딩을 하면서 예방하기 솔직히 어렵다. 찾아내기 힘들다... 말을 너무 못하신다...

2. 교착상태가 발생하기 위한 필요충분조건

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

Resource Allocation Graph.

자원 안의 점 → 동시에 접근 할 수 있는 Process의 개수.

Deadlock이 발생하기 위한 필요충분조건 → 암기!!!!

상호배제 조건(mutual exclusion) : 한 순간에 한 프로세스만이 자원을 사용할 수 있어야 한다.
점유대기 조건(hold and wait) : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다려야 한다.
비선점 조건(no preemption) : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제로 빼앗을 수 없다.
환형 대기 조건(circular wait) : 프로세스들 간에 닫힌 연결이 존재한다. 자원 할당 그래프에서 환형이 만들어지는 것이다.

→ 1,2,3을 만족한다고 Deadlock이 걸리는게 아님.

1,2,3을 만족하고 Circular Wait가 발생하면 Deadlock 상태로 들어간다.

1,2,3 → 필요조건.

4 → 충분조건

Deadlock Approaches - 3가지.

Deadlock Prevention - 필요충분조건 4가지 중 하나를 못하게 하는것.
아예 예방을 하는거임.
Deadlock Avoidence -
자원할당을 하다가 이번 할당에 deadlock 걸릴거같아! → 할당 X
필요충분조건 모두 허용..
할당은 하되, 할당하기 전에 Check해주는 기법.
Deadlock Detection -
자원을 무조건 할당. But 주기적으로 계속 확인해준다.
그리고 deadlock이 걸렸으면 복구시킬 수 있는 기법을 적용해서 검출, 해결.

3. 교착상태 예방(Deadlock Prevention)

교착상태가 일어나는 상호배제, 점유대기, 비선점 조건들을 허용하지 않거나 직접적으로 환형대기가 생기지 않도록 하는 것이다. 필요조건 3가지 중 하나를 못하게 하는 것. or 충분조건인 Circular Wait을 못하게 하는것.

간단 정리

상호 배제 : 운영체제에서 반드시 보장해주어야 함

점유 대기 : 프로세스가 필요한 모든 자원을 한꺼번에 요청

비선점 : 프로세스가 새로운 자원 요청에 실패하면 기존의 자원들을 반납한 후 다시 요청 or 운영체제가 강제적으로 자원을 반납시킴

환형 대기 : 자원 할당 순서(자원 유형)를 미리 정해두면 없앨 수 있음

교착상태 예방(Prevention) 전략 두가지.

간접적(Indirect) - 필요 조건(세가지) 중 하나를 Prevent하는 것.(허용 X)
직접적(Direct) - 충분 조건인 Circular Wait가 발생하지 않도록 하는것.

1) 상호 배제 - Prevention 불가!!

시스템을 설계할 때 상호 배제 조건(Mutual Exclusion)을 없앨 수는 없으므로 운영체제가 이를 반드시 지원해주어야 한다. 따라서 상호 배제는 Prevention 할 수 없다.

2) 점유 대기 - 간접적인 방법으로 Prevention 가능!!

프로세스는 자신이 사용할 모든 자원을 한번에 요청하는데, 만일 모든 자원을 할당받을 수 있으면 계속 수행된다. 반면 하나의 자원이라도 할당 받지 못하면, 어떠한 자원도 할당받지 않은 채 대기(Block)하도록 하는 것이다.
이 방법을 사용하면 점유 대기는 없앨 수는 있으나 세 가지 문제점(비효율성)이 생긴다.
1. 프로세스가 자원을 할당 받을 때까지 계속 기다려야한다는 것(Starvation가능..)
2. 한꺼번에 받은 자원 중 일부는 잠깐만 사용하고 안쓰는데 계속 자원을 들고있으면 자원이 효율적으로 사용되지 않는다
3. 메모리가 동적으로 할당될수도 있기 때문에 이 프로세스가 얼마나 하드디스크를 사용할지 등등 알 수가 없음. 프로세스가 미래에 필요로 할 자원을 예측하기 어려움.

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

3) 비선점 - 간접적인 방법

비선점 조건은 두 가지의 방법으로 없앨 수 있다.

자원을 점유한 프로세스가 다른 자원을 요청했을 때 할당받을 수 없다면(거절을 당한다면), 일단 자신의 점유한 자원을 모두 반납(Release)하고 이후 프로세스가 원래 자원과 새로 원하는 자원을 함께 요청하는 것
한 프로세스에서 다른 프로세스가 점유한 자원을 원하면 운영체제가 우선순위(preemption)에 따라 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스(우선순위가 제일 높은 Process)에 할당할 수 있다
- 2번 방법을 쓰려면 모든 Process의 Priority가 다 달라야한다.(똑같은 Priority를 가지면 안된다.)

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

4) 환형대기(Circular Wait) - 직접적인 방법.

환형대기 조건들은 자원들의 할당 순서를 정하면 없앨 수 있다.
Ex) 프로세스가 자원 R을 할당받았다면, 이후 이 프로세스는 자원 R 다음 순서를 갖는 자원들을 요청할 수 있는 것이다. 즉 자원마다 할당순서를 정해 R1 → R2 인 할당 순서를 정했다고 하면 R1을 할당받으면 그 다음 R2가 할당될 수 있게 된다. 만약 P1, P2 프로세스 중 P1가 R1을 할당하고 R2를 요청했다. 여기서 교착상태가 되려면 P2가 R2를 할당하고 R1을 요청해야하는데 이는 운영체제에서 정한 할당 순서에 위배되기 때문에 나타날 수 없다.
문제점(효율성 ⬇️))
- 프로세스의 수행지연 : 이런식으로 진행한다면 만약 P2가 R1 자원보다 R2자원을 먼저 필요로한다면 쓸데없이 R1을 먼저 대기해야 하는 수행 지연이 발생하게 될 수 있다.
- 불필요한 자원 할당 거부 : 만약 Process가 아예 R1이 아예 필요없어도 R1을 먼저 할당 받아야해서 불필요한 자원에 대해 할당받는것을 거부받을 수 있다.

4. 교착상태 회피(avoidence)

예방(Prevention)과 회피(Avoidence)의 차이점 : 교착상태 예방은 미리 교착상태를 생기게 하는 조건을 없애는 것이지만 이는 자원의 사용과 프로세스 수행에 비효율을 만든다.
교착상태 회피(Avoidence)는 상호배제, 점유대기, 비선점을 허용(3가지의 필요조건을 허용)하지만 그렇다고 자원 할당 순서를 미리 정하지도 않는다. 그 대신, 자원을 할당할 때 교착상태가 발생 가능한 상황으로 진행하지 않도록 고려해서 자원을 할당한다.
이처럼 Deadlock Avoidence는 자원 할당을 결정할때 Dynamic하게 결정되기 때문에 Concurrency(병행성)가 Prevention(예방)보다 더 허용된다. == 자원사용의 효율성이 높다.
할당 전에 이 할당이 Deadlock을 발생시킬 가능성이 있는지 동적으로(Dynamic)하게 조사한다. 만약 Deadlock의 가능성이 있다면 자원을 할당하지 않는다.
현재 자원의 가용개수와 프로세스의 자원 요구량을 미리 알고 있어야 Avoidence를 진행 시킬 수 있다.

Avoidence의 장점

Deadlock Prevention보다 제약조건(Restrictive)이 적다. (자원 할당이 훨씬 자유롭기 때문에 시스템에서 자원 효율이 높아진다.)
Deadlock Detection보다 Overhead가 적다.(Rollback Process를 안해도 되고 Preempt를 안해도된다.) ⇒ Rollback : 만약 오류가 생기면 Check Point(오류가 발생하지 않은지점)으로 돌아가 다시 실행시키는것.

Avoidence의 단점 및 제약 조건.(Restrictions)

현재 자원의 가용개수와 프로세스의 자원 요구량을 미리 알고 있어야 Avoidence를 할 수 있다.
프로세스들은 서로 독립적으로 존재해야한다. 수행 순서 같은 종속 관계가 없어야 한다.
각 프로세스들이 사용할 최대 자원 요구량을 운영체제에게 미리 알려줘야 한다
할당하는 자원의 개수가 고정적(Fix)이여야 한다
자원을 선점한 상태로 종료되는 프로세스가 없어야 한다. 반드시 Release하고 종료되어야함.

회피 방법 - 2가지.

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

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

2) 자원 할당 거부(Resource Allocation Denial)

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

자원을 할당할 때 교착상태가 발생할 가능성이 있는지 여부를 동적으로 판단
교착상태의 가능성이 없을 때 자원을 할당한다.즉, 안전한 상태를 계속 유지할 수 있을 때에만 자원을 할당한다.

자원 할당 거부 - 은행원 알고리즘(Banker’s Algorithm)

은행원 알고리즘에서의 시스템 상태 구분 - 가정 : 고정된 수의 프로세스와 자원이 존재.

State : 프로세스들이 자원을 요구하고 할당받은 관계.

안전 상태(Safe State): 교착상태가 발생하지 않도록 프로세스들에게 자원을 할당할 수 있는 할당 경로(진행 경로)가 존재

불안전 상태(Unsafe State) : 할당 경로(진행 경로)가 없을 때..
무조건 데드락에 빠진다는게 아니고 가능성이 있다!는 상태.

벡터 : 자원(R)벡터 , 가용(V)벡터

행렬 : 요구(C)행렬, 할당(A)행렬.

<Safe State의 예시>

P1~4가 각각 R1~3에 대한 자원 요구를 “요구 행렬 C”에서 볼 수 있다.
현재 P1~4 가 각각 할당받은 자원을 “할당 행렬A”에서 볼 수 있고,
아직 할당 받지 못해서 필요한 자원을 “C-A”에서 볼 수 있다.
R1~3에 대한 총 자원은 R표에서 볼 수 있다.
R1~3에서 사용가능한 벡터가 V표에 나와있다.

그럼 여기서 과연 이 상태가 안전한지 불안전한지 살펴보면,먼저 (a)에서 가용 가능한 자원으로 끝낼 수 있는 프로세스는 P2 이므로, P2에게 부족한 R3 자원을 1 주면 P2는 끝나고 자신이 가진 자원을 반납하고 (b) 상태로 넘어간다.

(b)에서는 P1을 완료하여 P1을 끝내고 (c)상태로 넘어간다. (c)에서는 P3을 끝낼 수 있으므로 P3을 끝내고 (d)상태로 넘어간다. (d)상태에서 P4를 끝내면 수행이 끝난다.
결론적으로 모든 프로세서를 모두 무사히 끝내게 되므로 안전한 상태(Safe State)이다.

<Unsafe State의 예시>

위의 경우에서 불안전 상태로 판별나려면?

P1에 저런식으로 줘버리면 Deadlock 발생의 가능성이 생긴다.

5. 교착상태 발견(Deadlock Detection)

자원 할당이 요구될 때마다 매번 수행할 수 있음
주기적으로 OS가 Circular Wait Condition에 빠졌는지 안빠졌는지 검사하는 Algorithm을 주기적으로 실행.
여기서 Algorithm 실행은 자원요청 때마다 할 수도 있고 10분이라는 시간을 정해서 할 수도 있고... 자유임.

자원 할당이 요구 될 때마다 Deadlock Detection의 장점

매번 자원 할당이 요구될 때마다 수행하면 빠른 Detection이 가능하다.
Algorithm은 간단하다. - ~~그냥 Deadlock에 빠졌는지 안빠졌는지만 검사하면 돼서.~~..
시스템의 상태가 점진적으로 변하기 때문에 간단해진다.

Deadlock Detection의 단점

자주 Detection을 체크하게 되면 프로세서 타임을 소비하게 된다.

Prevention vs Detection

Prevention은 비관적. → Deadlock이 발생할 것 같으니 그냥 처음부터 막자.. Delay도 감수하자. 성능저하도 감수.
Detection은 낙관적 → 가끔 발생 했을때 그냥 찾아내자~ 낙관적임.

교착상태 발견 알고리즘

교착상태 발견 알고리즘의 순서

할당 행렬 A에서 행의 값이 모두 0인 프로세스를 우선 표시(mark)한다.
임시 벡터 W를 만든다. 그리고 현재 사용 가능한 자원의 개수(결국 가용 벡터 V의 값)를 벡터 W의 초기값으로 설정한다.
표시되지 않은 프로세스들 중에서 수행 완료 가능한 것이 있으면 (요청 행렬 Q에서 특정 행의 값이 모두 W보다 작은 행에 대응되는 프로세스)이 프로세스를 표시한다. 만일 완료 가능한 프로세스가 없으면 알고리즘을 종료한다. → 종료할 때 Unmark된 Process가 있다면 그 Process는 Deadlock에 빠진 것.
단계 3의 조건을 만족하는 행을 Q에서 찾으면, 할당 행렬 A에서 그 행에 대응되는 값을 임시 벡터 W에 더한다(Update). 그리고 3단계를 다시 수행한다.

쉽게 설명

P4는 할당 받은 자원이 없다. 따라서 P4에 마킹을 한다.
가용벡터 V는 (0 0 0 0 1)로 초기화 된다.
P3의 요청을 만족할 수 있으므로 P3에 마킹한다. 가용벡터 V가 (0 0 0 1 1)이 된다.
마킹이 되지 않은 프로세스들 중에서 가용벡터로 끝낼 수 있는 프로세스가 존재하지 않으므로 알고리즘이 종료된다.

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

6. 교착상태 회복 알고리즘(Deadlock Recovery)

교착상태가 발견되면 그것을 해결하기 위한 기법이 필요하다.

회복(Recovery) 알고리즘 종류

교착상태에 빠진 모든 프로세스들을 종료시키는 것→ 생각보다 많은 운영체제가 사용한다.
교착상태에 빠진 각 프로세스의 수행을 일정 체크포인트 시점으로 롤백(Rollback)한 후 다시 수행시키는 것→ 교착상태가 다시 발생할 가능성이 존재한다(똑같은 방식으로). 하지만 병행처리의 비결정 특성으로 인해 확률이 낮기는 하다.
교착상태가 없어질 때까지 교착상태에 포함된 프로세스들을 하나씩 종료시키는 것
→ 종료시키는 프로세스는 비용이 가장 적은 것부터 종료된다. 하나씩 종료시키면서 발견 알고리즘을 실행 시킨다.
교착상태가 없어질 때까지 교착상태에 포함된 자원을 하나씩 선점시키는 것
→ 자원은 비용이 가장 적은 것부터 선택한다. 자원을 선점시키고 발견 알고리즘을 통해 교착상태가 사라지면 그 프로세스를 자원을 할당 받기 전 시점으로 Rollback(되돌린다).

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

지금까지 사용한 프로세서 시간이 적은 프로세스부터
지금까지 생산한 출력량이 적은 프로세스부터
이후 남은 수행시간이 가장 긴 프로세스부터
할당 받은 자원이 가장 적은 프로세스부터
우선 순위가 낮은 프로세스부터

Deadlock 예방, 회피 , 발견 정리

~Ch06-22S-2

7. 통합적인 교착상태 전략

통합적인 Deadlock 상태 막기 전략 3가지

자원들을 유형에 따라 서로 다른 클래스로 구분
자원 클래스들 간에는 할당 순서를 두어 Circular Wait를 막자.
클래스 내부의 자원들 간에는 각 클래스에 적절한 Deadlock 해결 방법을 사용.

자원들의 클래스 - 프로세스가 할당돼서 수행되는 순서랑 비슷..

스왑공간(Swappable Space) : Prevention, Avoidence 사용 가능.
- 보조 기억장치(Secondary Space)상의 메모리 블록, 프로세스들을 스와핑하는데 사용.
- Deadlock Prevention을 사용 - 필요한 모든 자원을 한꺼번에 요청하게 하여 점유 대기(Hold and Wait)를 막는다. 만약 요청이 거절되면 그냥 Process가 안만들어짐.
- Prevention 사용 가능 이유 : 스왑 공간을 할당하려는 프로세스가 미리 필요한 공간의 크기를 알 수 있기 때문에 구현 가능.
프로세스 자원(Process Resources) : Prevention, Avoidence 사용 가능.
- 할당 가능한 장치(Device) 자원. - 테이프 드라이브, 파일...
- 데드락 Avoidence(회피)가 효과적으로 사용될 수 있음. 프로세스가 이 클래스에 속한 자원의 예상사용 시간을 미리 예측할 수 있으며, 이 시간을 OS에게 알릴 수 있으므로 구현 가능.
- 자원 할당 순서를 미리 결정하는 데드락 Prevention에서도 이용 가능.
주 메모리(Main Memory) : Prevention
- 프로세스들에게 할당되는 자원. - Page, Segment의 단위로..프로세스에게 할당됨.
- 선점을 허용하는 Prevention이 적절.
- 프로세스가 블록되면 그 프로세스의 수행 이미지는 보조 기억장치로 스왑되고, 프로세스가 사용하던 메모리 공간을 반납.
내부 자원(Internal Resource) : Prevention
- 입출력 채널 같은 자원 (I/O Channel)
- 자원 할당 순서를 미리 결정하는 Prevention 방법

8. 식사하는 철학자 문제 : 교착상태를 다루는 문제

이 문제는 병행 프로그래밍의 어려움을 다시금 느끼게 될 수 있는 공유 자원을 통한 협동의 대표적인 문제이다.

문제 정의

원탁 테이블 가운데에는 스파게티가 담긴 큰 그릇이 하나있다.
철학자가 개인적으로 사용하는 접시가 5개 있고, 접시 양쪽에는 포크가 있다. (결국 테이블 위에는 5개의 포크가 존재한다.)
철학자는 배가 고프면 자신의 정해진 위치로 가서 큰 그릇에 담긴 스파게티를 자신의 접시에 담아 먹는다.
철학자들은 스프게티를 먹기 위해 반드시 포크 2개를 사용해야 한다.
고려되어야 할 것
- 임계영역이 지켜져야 한다 : 여러 철학자가 동시에 같은 포크를 사용할 수 없다. (상호 배제)
- 교착상태(Deadlock)나 기아(Starvation)에 빠져서는 안된다 : 어떤 철학자도 굶어 죽어서는 안된다
- 즉, 교착상태도 없어야 하고, 굶어 죽지도 않아야 한다.

1) 세마포어를 이용한 해결 방법 - Deadlock 발생하는 잘못된 알고리즘.

1. wait(fork[i]) : 철학자는 우선 왼쪽에 있는 포크를 집는다.
2. wait(for[i+1]) : 이후 오른쪽에 있는 포크를 집는다.
3. eat() : 식사를 한다.
4. sigal(fork[i+1]), signal(fork[i]) : 식사 이후, 철학자는 두 개의 포크들을 식탁에 다시 내려놓는다.

이러한 방법은 교착상태를 유발한다는 문제점이 있다.즉, 모든 철학자들이 동시에 식탁에 앉고 동시에 왼쪽 포크를 집었다고 가정하면, 오른쪽 포크를 집으려 해도 거기에는 포크가 없게 된다. 결국 아무도 식사를 하지 못하게 되는 것이다.

그 외 방법

교착상태를 피하기 위해 포크를 5개 더 구입하는 방법

포크 하나로 스파게티 먹는 법을 가르치는 방법

한 번에 최대 4명까지만 식탁에 앉을 수 있게 제한하는 방법

2) 세마포어를 이용한 다른 해결 방법 - 교착상태 발생하지 않음

한 번에 최대 4명까지만 식탁에 앉을 수 있게 제한하는 방법

1. room이라는 semaphore를 사용.
2. 최대 4명까지만 식탁에 Wait할 수 있음.

3) 모니터를 이용한 해결 방법

1. ForkReady : 5개의 조건변수. 각 조건변수는 각 포크에 대응됨. 이 조건변수는 철학자들이 포크가 사용 가능할 때까지 대기할 때 이용.
2. fork : 포크가 사용가능한지 안한지.
3. get_forks() : 2개의 포크를 요청할때 사용. 만약 하나라도 이용불가면 그 조건변수에서 대기. 이렇게 대기함으로써 다른 Process들이 모니터로 진입할 수 있게끔한다.
4. release_forks() : 2개의 포크를 반납할때 사용. 대기하고 있는 프로세스가 있으면 깨워준다.
5. pid : 철학자의 id.

9. 각 OS별 병행성 기법

1) 유닉스 병행성 기법(Concurrency Mechanism) - IPC, 동기화 제공.

프로세스 간 통신 (IPC : Interprocessor Communication)
1. 파이프(Pipe) - Named Pipe, Unnamed Pipe
  - Circular Buffer를 사용.
  - 생산자-소비자 모델을 갖는 두개의 프로세스 간에 통신 기능을 제공.
  - 파이프는 크기가 고정된 선입선출(FIFO)큐를 사용
  - 한 프로세스는 데이터를 꺼내고(읽고) 다른 프로세스는 데이터를 넣게(쓰게)된다.
  - OS는 파이프에 대한 상호배제(Mutual Exclusion)와 Buffer Synchronization을 보장해줌.
    - Buffer Synchronization - 버퍼가 비어있으면 읽지 못하게 해야하고 버퍼가 꽉차있으면 쓰지 못하게 해야한다.
  - Named Pipe : 어떠한 프로세스들 간에도 공유가 가능
  - Unnamed Pipe : 서로 관련된 프로세스들 간에만 공유가 가능.(Ex 부모-자식 관계)
2. 메시지(Message)
  - 프로세스들이 서로 통신할 때 사용하는 객체.
  - 바이트들의 블록으로 이루어지고 type을 가진다. → 이 type으로 메시지의 유형을 결정.
  - Message Passing을 위해 msgsnd,msgrcv 라는 시스템 Call을 OS에서 제공.
  - 메시지를 사용하려는 프로세스들은 메시지 큐를 생성. - Mailbox와 비슷한 역할.
  - 메시지 Sender는 메시지 Type을 설정 → 메시지 Reciever는 Type에 따라 다른 서비스를 제공
3. 공유 메모리(Shared Memory)
  - IPC(프로세스 간 통신)에서 제일 빠른 방식.
  - 공유 메모리는 여러 프로세스들에 의해 공유되는 가상메모리(Virtual Mem)상에 공통 메모리 객체.
  - 공유 메모리는 Read-only, Read-Write 등 다양한 Permission(접근 제어)가 가능함.
  - Shared Memory상에서 Synchronization(동기화)는 그 공유메모리를 사용하는 Process들이 제공해줘야한다. (Reader & Writer)
Synchronizing(동기화)를 위한 기법
1. 세마포어(Semaphore)
  - 세마포어를 시스템 호출(System Call)로 지원.
  - 원래 우리가 알던 구조가 아닌 좀 더 일반적인 구조로 지원(semSignal, semWait 와 같은 구조가 아니다.)
  - 증감되는 값이 1보다 클 수도 있고 여러개의 연산이 동시에 진행도 가능.(원래 세마포어와의 차이점)
  - Kernel은 세마포어에 대한 요청이 원자적으로 수행됨을 보장.(모든 요청이 완료되기 전까지 다른 프로세스의 세마포어에 대한 접근은 허용 X)
  - 세마포어의 구성요소
    1. 세마포어의 현재 값
    2. 세마포어에 마지막 연산을 수행했던 Process ID
    3. 세마포어의 값이 현재 값보다 더 큰 값이 되기를 기다리며 대기하는 프로세스들의 개수
    4. 세마포어의 값이 0이 되기를 기다리며 대기하는 프로세스들 개수
2. 시그널(Signal)
  - 비동기적인 사건의 발생을 프로세스에게 알리는 소프트웨어적인 방법.
  - 하드웨어 인터럽트와 비슷 But 우선순위(Priority)는 제공되지 않는다.(하드웨어는 Priority존재.)
  - 모든 시그널은 동등하게 취급, 동시에 발생한 여러 시그널의 처리 순서는 프로세스에 따라 다르다.
  - 프로세스 테이블에 필드(Field)를 업데이트 하면서 전달된 Signal이 필드에 표시된다. 이걸 보면서 처리방법을 다르게 한다.
  - 시그널 처리 방법
    1. 기존의 Default로 정의된 행동(Action)을 하는 것.
    2. Signal-Handler Function에 따라 실행하는 것.
    3. Signal을 그냥 무시때리는 것.
  - 시그널의 종류
    - SIGHUP - 프로세스가 사용자와 단절되어 특별한 작업을 수행하지 않고 있는 상태로 파악되면 OS가 프로세스에게 이 시그널을 보낸다.
    - SIGINT - 인터럽트
    - SIGKILL - 프로세스를 종료시킴
    - SIGALARM - 프로세스가 일정 시간 이후에 시그널을 받으려고 할때 이용.
    - SIGPWR - Power Failure 가 났을 때

2) 리눅스 병행성 기법

UNIX 시스템의 병행성 기법을 모두 제공.
Linux는 RT(real-time) Signal을 제공!(UNIX와 차이점)
1. UNIX Signal과 다르게 RT Signal은 우선순위에 따라 Signal이 전달됨
2. 여러개의 Signal을 Queue에 저장함으로 받을 수 있다.
3. UNIX Signal(Standard Signal, 표준 시그널)에서는 값이나 메시지 전달은 불가능했고 오직 통보(notification)만 했다면 RT Signal은 Value(값)을 Signal에 넣어서 전달 할 수 있다.
원자적 연산(Operation)을 제공
- 중단/간섭없이 실행되는 작업이다.(Interrupt, interferenc X)
- 원자적 Operation 종류 - 2가지
  1. Integer Operation
    - 정수형 변수에 대한 원자적 연산을 제공
  2. Bitmap Operation
    - 비트에 대한 원자적 연산을 제공.
스핀락(spinlock)
- 리눅스에서 Critical Section을 보호하기 위해 가장 일반적으로 사용하는 방법.
- 한 번에 하나의 스레드만 스핀락을 획득할 수 있다.
- 다른 쓰레드들은 lock을 획득할 수 있을 때까지 계속 시도(spinning)한다.
- 각 쓰레드들은 CS에 들어가기전에 lock을 무조건 확인하고 들어간다.
  - lock = 0 이면 lock 값을 1로 변경하고 CS로 진입
  - lock ≠ 0 이면 값이 0이 될때까지 계속 확인 한다. 0이되면 그때서야 진입!
- 스핀락은 대기시간이 상당히 짧은경우에 사용해야 효율적임.(ex. 두번의 Context Change시간보다 짧을때)
- 스핀락의 장점
  - 구현하기 간단하다.
- 스핀락의 단점
  - 쓰레드가 계속 처리기를 차지하면서 바쁜 대기(Busy Wating)을 하기 때문에 처리기를 비효율적으로 사용.
세마포어
- User-Level 세마포어
  - UNIX 세마포어와 같음.
- Kernel-Level 세마포어
  - 커널 내부에서만 사용하기 위해 만들어진 세마포어
  - User-Program에서 시스템 콜을 통해 접근 할 수 없음.
  - 커널 내부에서 Function으로 구현되어 있고 User-level 세마포어보다 효율적이다.
- 세마포어의 Type - 3가지
  1. Binary 세마포어
  2. Counting 세마포어
  3. Reader/Writer 세마포어
장벽(Barrier) - 명령어 실행 순서를 보장.
- 컴파일러나 Processor는 성능 최적화의 목적으로 프로그램 내의 메모리 접근 실행 순서를 바꾸는 경우가 있다.
- 실행 순서를 바꿀 때 수행결과가 달라지지 않는지 확인하고 바꿔야함 → Barrier가 제공.
- 만약 순서를 바꾸면 결과가 달라진다!! 못바꾸게끔 Barrier를 통해 실행 순서를 보장 시킨다.

3) Solaris의 병행성 기법 - 쓰레드에서의 동기화(Synchronization)

Mutual Exclusion Lock(=Mutex Lock)
- 뮤텍스로부터 보호된 자원은 한 시점에 한 쓰레드만 사용 가능.
- 뮤텍스 lock을 건 쓰레드가 반드시 뮤텍스 Unlock(뮤텍스 lock을 반납)을 해줘야한다!!
- 락을 획득할때 mutex_enter()를 사용.
- 락 획득을 실패하면 Block된다.
- 블록되는 방법 - 락의 유형에 따라 다름.
  1. Default Blocking: 스핀 락 - Busy Waiting
  2. Interrupt-based Blocking : 수면상태로...
세마포어
- Counting Semaphore를 지원.
- 프리미티브
  1. sema_p() : 감소. 만약 자원 사용이 불가능하면 Block됨.
  2. sema_v() : 증가
  3. sema_tryp() : 감소. 만약 자원 사용이 불가능하면 Block X. 블락되지 않고 다른 작업을 수행한다.
다중 읽기/ 단일 쓰기 Lock(Readers/Writer Lock)
- Read-only 쓰레드들의 동시 접근을 지원(Multiple Thread)
- Write 쓰레드는 독점적인 사용을 보장(Single Thread)
- 쓰레드가 락을 획득한 용도에 따라 락의 상태는 두가지
  1. read lock : 읽기 용도로 획득한 lock , write 쓰레드들은 lock 획득 불가, read 쓰레드들은 획득 가능.
  2. write lock : 쓰기 용도로 획득한 lock, 다른 모든 쓰레드들이 lock 획득 불가.
조건 변수(Condition Variable)
- 특정 조건이 만족될 때(True)까지 대기.
- 뮤텍스 lock과 함께 사용됨.

4) Window의 병행성 기법 - 5가지..

객체 아키텍처의 일부로 쓰레드 간 동기화 기법을 제공.
Wait Function(대기함수)
- 수행 중에 쓰레드의 블록을 허용하는 함수.
- 특정 조건이 만족될때까지 절대 리턴하지 않는다.
- 대기 기능 유형(Type)에 따라서 함수가 달라짐.
- Ex) WaitForSingleObject - 단일 객체에 대한 대기 함수.
  - 해당 객체가 Signal State or NonSignal State인지.
  - Signal State(시그널을 받은 상태)이면 Return함.
Critical Section 객체.
- Mutex객체와 비슷
- 스핀 락을 사용.
- Mutex는 다른 프로세스에서 수행중인 쓰레드들도 지원
- Critical Section 객체는 한 프로세스(Single Process)에서 수행중인 쓰레드 들만 지원.
- 멀티프로세서 시스템에서 스핀락으로 CS에 진입하려고 할거임. → CS를 짧은시간동안만 사용한다면 효과적임. 스핀락 효율 굳
- 하지만 오랜시간동안 스핀락을 획들 할 수 없다면 디스패처를 써서 스케쥴링해서 최적화한다.
Slim Read-Writer Lock
- Single Process안에 있는 쓰레드들끼리만 공유됨.
- CS Lock처럼 스핀락을 사용한다.
- 따라서 포인터 크기의 메모리 공간만을 할당하기 때문에 Slim이라고 불린다.
- 너무 Slim해서 Lock에 어떤 다른 정보를 담기엔 너무 작다
- 대신 구현이 쉽다.
Condition Variable
- 특정 조건이 달성될때까지 Block
- CS Lock, SRW Lock과 함께 사용된다. = Single Process에서만 사용가능.
1. CS lock이든 SRW lock이든 획득
2. False면 Sleep, True면 수행.
3. 보호된 Operation을 수행
4. 수행끝나면 lock을 Release

5) Android에서의 Interprocess Communication

기존 다른 OS에서 사용하던 무거운 기법들은 사용 불가
임베디드 시스템에서는 자원의 제약이 있어서 Lightweigth한 기법들을 사용해야함
Binder
- 경량 RPC(Remote Procedure Call) 능력을 제공
- 두개의 프로세스간 Interaction을 할 수 있도록 중재하는 역할을 한다.(Binder의 역할)
- Binder Operation
  - Client(컴포넌트) Binder Service(컴포넌트)
  - Client가 호출을 요청 → 바인더로 전달 → 바인더에서 서비스로 전달 → 서비스에서 처리 후 다시 바인더로 전달 → 바인더가 Client한테 전달
- Binder Operation 그림.
1. Client가 서비스를 호출
2. Proxy를 동작시킴.
  Mashalling(마샬링) - 바인더 드라이버를 위해 요청(서비스호출)을 Parcel(파슬)로 바꾸는 작업
  Parcel - 바인더 드라이버를 통해 전달될 수 있는 메시지의 컨테이너.
  마샬링을 수행해서 요청(서비스호출)을 파슬로 바꾼뒤 바인더 드라이버에게 전달한다.
3. 파슬을 Stub에 전달.
4. Stub은 Unmashalling(언마샬링)을 진행.
  Unmahalling - Pacel을 Service에서 읽을 수 있는 자료구조로 변환하는 작업.
5. Service에서 수행한 후 결과값을 Stub에게 전달.
6. Stub은 return값을 응답 파슬로 Mahalling후 바인더 드라이버로 보냄
7. 바인더는 Proxy에게 응답 데이터 트랙잭션을 보냄
8. Proxy는 Unmashalling을 수행해서 응답 Pacel을 Return값으로 변환 후 Client에게 전달.
  
  참고
  https://velog.io/@pu1etproof/%EB%82%98%EB%A7%8C%EC%9D%98-%EB%B0%B1%EA%B3%BC%EC%82%AC%EC%A0%84-%EB%B3%91%ED%96%89%EC%84%B1-%EC%83%81%ED%98%B8%EB%B0%B0%EC%A0%9C-%EB%8F%99%EA%B8%B0%ED%99%94-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%EA%B8%B0%EC%95%84

hoonding