[운영체제] 02. ipc

InterProcess Communication (프로세스간 통신)

three issues

1. 어떻게 프로세스가 다른 프로세스에게 정보를 전달하는가
2. 둘 또는 그 이상의 프로세스가 서로 상대방을 방해하지 않도록 하는 것
3. 종속성(dependency)이 존재할 때 적절한 순서를 정하는 것

 

⭐️Race conditions (경쟁 조건)

example) Spooler directory

(out: 프린트할 다음 파일, in: 디렉토리에서 다음 번 빈 슬롯)

 

상황: 거의 동시에 프로세스 A와 B가 프린트하기 위해 이름을 등록하려고 함

1. 프로세스 A가 in을 읽고 next_free_slot에 7을 적음
2. interrupt 가 발생하여 프로세스 B 역시 in을 읽고 next_free_slot에 7을 저장함
3. 프로세스 B는 자신의 파일 이름을 슬롯 7에 저장하고 in을 8로 변경
4. 다시 프로세스 A의 차례가 되었을 때, 자신의 파일 이름을 7에 기록 → 프로세스 B가 기록했던 파일 이름이 지워지고 in에 8을 기록
5. 프로세스 B는 자신의 인쇄물을 받을 수 없게됨

 

mutual exclusion (상호배제)

둘 이상의 프로세스가 동시에 공유 데이터를 읽기와 쓰기를 수행하지 못하도록 금지하는 방법

=두 프로세스가 동시에 임계구역에 존재하지 않도록 조절

⭐️critical region(임계구역): 공유 메모리를 접근하는 프로그램 부분

 

4가지 조건

1. 두 개 프로세스가 동시에 자기의 임계구역 내에 존재하면 안된다.
2. CPU의 개수나 속도에 대해 어떤 가정도 하지 않는다.
3. 임계구역 외부에서 실행하고 있는 프로세스는 다른 프로세스들을 블록시켜서는 안된다.
4. 임계구역에 진입하기 위해 무한히 기다리는 프로세스는 없어야 한다.

 

---

[mutual exclusion 구현]

#Busy waiting

 

(0) Disabling Interrupts

각 프로세스가 임계구역에 진입하자마자 인터럽트를 끄고 임계구역에서 나가기 직전에 인터럽트를 켜도록 하는 것

 

→ 프로세스 중 하나가 인터럽트를 끄고 다시 켜지 않을수도, disable 명령을 수행한 CPU에게만 영향미침

(OS 내부에서 사용하기엔 유용하지만, 일반적으로 사용하기에는 부적절)

 

(0) Lock variables

(software solution)

0으로 초기화된 단일 공유 변수 사용 (락 변수)

1. 락 테스트
2. (if Lock==0) 프로세스는 1로 설정한 후에 임계구역에 진입
3. (if Lock==1) 프로세스는 이 변수가 0이 될 때까지 기다림

(Lock=0: 임계구역 내에 어떤 프로세스도 존재하지 않는 상태, Lock=1: 임계구역에 어떤 프로세스 존재함)

 

→ Spooler directory에서 발생한 문제와 같은 문제 발생할 수 있음

 

(1) Strict Alternation

두 프로세스가 번갈아가며 임계구역에 진입하도록 turn 변수를 사용

(turn: 초기값이 0인 정수 변수)

1. 프로세스 (a)가 turn 을 검사하여 이 값이 0임을 발견하면 임계구역에 진입
2. 프로세스 (b)는 이 값을 검사하여 0임을 발견하고 turn이 1이 되는지를 검사하면서 루프를 돌게 됨
3. 프로세스 (a)가 임계구역을 떠나면서 turn을 1로 설정하여 프로세스 (b)가 임계구역에 진입할 수 있도록 함
4. 프로세스 (b)가 임계구역 실행을 마치고, turn이 0으로 설정

//특정 값이 될 때까지 계속해서 루프를 돌며 검사하는것: busy waiting

 

→ 프로세스 (b)가 turn을 0으로 바꾸기 전까지 프로세스 (a)는 while문에 묶여있어야함. 조건 3 위반

 

cf) Strict Alternation에서 사용되는 turn 변수는 스핀 락에서의 lock 변수와 유사한 역할을 함

spin lock: a lock that uses busy waiting

 

(2) Peterson’s solution

두 개 이상의 프로세스의 동기화 문제를 해결하는 방법 

 

(2) TSL Instruction

TSL 명령어와 공유 변수 lock을 사용

연속 수행이므로 쪼갤 수 없고 연산이 완료될 때까지 어떤 처리기도 메모리 워드에 접근할 수 없음

 

Busy waiting 을 하게 되면 CPU time을 낭비하고, priority inversion problem 발생 우려

 

 

#Sleep and Wakeup

sleep: 프로세스를 대기 상태로 (block)

wakeup: 깨워서 실행 재개

 

-sleep and wakeup을 이용한 생산자-소비자 문제

→ wakeup 시그널이 소실되면, 소비자는 잠들고 생산자도 버퍼를 모두 채우고 잠 들게되고, 두 프로세스 모두 영원히 잠들게 되는 상태가 됨

solution: semaphores

 

#Semaphores

 

down(P) operation: semaphore>0일때, semaphore 감소하고 down 계속 수행

semaphore=0일때, 멈추고 sleep(block)

up(V) operation: semaphore 증가, down연산을 완료하지 못하고 잠들어있는 프로세스 하나의 down 수행 완료시킴

 

이 operation들은 indivisible atomic action (중간에 process switch발생하거나 분할 불가능)

 

3개의 semaphore

1. full: 아이템으로 채워진 슬롯의 개수
2. empty: 빈 슬롯의 개수
3. mutex: 생산자와 소비자가 동시에 버퍼에 접근하지 못하도록 함 (1로 초기화)

둘 또는 그 이상의 프로세스가 사용하면서 이들 중 하나의 프로세스만 임계구역에 진입할 수 있도록 하는 용도로 사용되는 세마포어: binary semaphore

 

-semaphore를 이용해 생산자-소비자 문제 해결

 

#Mutexes

 

세마포어의 개수를 세는 능력이 필요 없는 경우, simplified version of the semaphore

unlocked: 0, locked: non-zero

 

mutex_lock: 임계 구역에 들어가기 전에 mutex가 잠금해제 되었는지 확인하고, 잠겨있으면 다른 스레드에게 양보하여 잠금이 풀릴때까지 반복적으로 시도

mutex_unlock: 임계구역에서 작업이 끝난 후 mutex를 해제 하는 함수

 

→ semaphore는 사용하기에 어려움

 

#Monitors

 

단 하나의 프로세스만 한 순간에 모니터에서 활동할 수 있다.

임계구역을 모두 모니터의 프로시듀어 형태로 만들면 동시에 두 개의 프로세스가 임계구역에서 실행할 수 없다. 상호배제를 어떻게 달성하는지에 대해 전혀 알 필요 없음

 

⭐️조건 변수(condition variables)

wait: 모니터 프로시듀어가 더 이상 진행할 수 없음을 인식하면(ex.버퍼가 가득 찬 상태) 수행, 호출한 프로세스를 대기하게 만듦

signal: 대기 중인 조건 변수에 대해 수행, 대기중인 파트너를 깨움 (마지막 문장에서만 사용되어야 함)

 

→ 모니터와 컴파일러 의존성, 분산 환경에서의 비적용성(단일 메모리 공간에서 작동하는 것을 전제로 함)

 

-monitor를 이용한 생산자-소비자 문제

(java에서 synchronized 메소드는 스레드 간의 동기화를 위해 사용되며 상호 배제를 제공)

 

#Message Passing

 

method of interprocess comunication (send, receive system calls)

send(destination, &message): 메세지를 명시된 목적지에 전송

receive(source, &message): 메세지를 수신, 전달될 메세지가 없으면 도착할때까지 대기 or 오류 코드와 함께 즉시 복귀

 

→ 네트워크에 의해 메세지 소실 우려 (solution: ack,seq num)

 

-message passing을 이용한 생산자-소비자 문제

 

---

Barriers

한 프로세스가 장벽에 도착하면 다른 모든 프로세스가 장벽에 도착할 때까지 이미 도착한 프로세스들은 대기한다. 마지막 프로세스가 장벽에 도착하면 모든 프로세스가 장벽을 통과한다.

 

Dining Philosphers Problem

deadlock(모든 철학자가 한 개의 포크만 들고 두 번째 포크를 기다리며 영원히 대기하는 상태) 방지

 

1. 잘못된 해결책

→ cause deadlock

 

2. 철학자가 왼쪽 포크를 든 후, 오른쪽 포크가 사용 가능한지 확인

만약 오른쪽 포크를 사용할 수 없으면 왼쪽 포크를 내려놓고 다시 시도

→ cause starvation (기아상태)

 

3. 철학자가 오른쪽 포크를 들지 못했을 때 랜덤한 시간을 기다린 후에 재시도, 여러 철학자가 동시에 포크를 드는 것을 방법

 

4. binary semaphore

→동시에 한 명의 철학자만 식사를 하게 되는 버그 발생

 

5. 교착 상태 방지, 최대 병렬성 보장