운영체제 - Interprocess Communication

※ 이 글은 3학년 2학기 운영체제 수업내용+강의록+"각종 블로그"의 내용들로 쓰여졌습니다.

 

@Interprocess Communication

*3가지 이슈

1. 한 프로세스가 다른 프로세스에게 어떻게 정보를 전달하는지.

2. critical activity에 참여할 때 두 개 이상의 프로세스가 서로 방해가 되지 않도록 보장.

3. 종속성이 있을 때, 올바른 순서의 지정. ex) A가 data를 공급하고 B가 그것들을 출력하려하면, B는 A가 data를 공급하기 전까지 기다려야한다.

 

@Race Conditions

=>두 개 이상의 프로세스가 동시에 일부 공유 데이터를 읽거나 쓰고 있으며 최종 결과는 누가 언제 정확하게 실행하느냐에 따라 달라진다.

*Race Condition이란, 여러 개의 프로세스가 공유 자원에 동시 접근할 때 실행순서에 따라 결과값이 달라질 수 있는 현상. 경쟁상태는 컴퓨터 입장에서 아주 큰 문제다. 왜 그러냐? 똑같은 코드를 100번 돌리면 실행 결과가 항상 같아야 하는데, 경쟁 상태가 발생하면 결과가 달라질 수 있기 때문이다. 이러한 문제를 방지하기 위해 공유 메모리를 쓰는 프로세스끼리 '동기화' 를 해줘야 한다. 정리하면 공유 메모리를 쓰는 프로세스끼리는 경쟁상태가 발생할 수 있는데, 이에 대한 해결책이 동기화다.

 

 

@Critical Regions

-Mutual Exclusion★(상호배제)
=>한 프로세스가 공유변수 또는 파일을 사용하는 경우, 다른 프로세스는 동일한 작업에서 제외된다
-Critical Region★(임계구역)=Critical Section
=?공유 데이터를 access 하는 코드의 일부분.
-Four conditions of a good solution to critical-section problem
1) 동시에 두개의 프로세스가 critical region에 접근 불가
2) CPU의 속도나 개수에 가정하여 만들어지면 안된다
3) critical region 밖에서 실행되는 어떤 프로세스도 다른 프로세스를 block할 수 없다*
4) 어떤 프로세스도 critical region에 진입하기 위해 영원히 기다릴 수 없다

 

 

@Mutual Exclusion with "Busy Waiting"(1)

1) Disabling Interrupts

-변수나 목록을 업데이트하는 동안 커널이 인터럽트를 비활성화하는 것이 편리하다.

-process swtiching은 interrupt에 의해 일어나는데 이 때문에 clock interrupt 자체를 차단한다.

-위 과정이 지나면 다시 enable interrupt로...

-장단점이 존재...

*가장 간단한 방법이지만 그다지 유쾌한 방법은 아니다. 각 프로세스가 임계구역에 진입 하자마자 인터럽트를 끄고 임계구역에서 나가기 직전에 인터럽트를 켜도록 하는 방식이다. CPU는 오직 클록이나 다른 인터럽트의 결과로 프로세스간에 문맥을 교환하므로 인터럽트를 끄면 CPU는 다른 프로세스로 문맥을 교환하지 않는다. 따라서 프로세스가 인터럽트를 끄면 다른 프로세스가 끼어들 걱정 없이 공유 메모리를 검사하고 변경할 수 있다. 이 방법이 유쾌하지 않은 이유는 우선 사용자 프로세스에게 인터럽트를 끌 수 있는 권한을 주는 것은 현명하지 못하기 때문이다. 만약 프로세스 중 하나가 인터럽트를 끄고 다시 켜지 않는다면 어떻게 될지 생각해 보라. 또한 (둘 이상의 CPU를 가진) 다중처리기 시스템의 경우 인터럽트를 끄는 disable 명령은 이 명령을 수행한 CPU에게만 영향을 미친다. 다른 CPU들은 계속 실행하면서 공유 메모리에 접근할 것
이다. 최근 대부분의 PC가 멀티 이상의 코어를 가지고 있는 것을 생각했을 때 이 방법은 해결책이라고 보기 힘들다.

 

2)Lock variables -> mutual exclusion 보장 X!

-소프트웨어적인 solution
-Use of shared(lock) variable
-lock=0(사용가능) lock=1(사용불가능)
-lock=0이면 1로바꾸고 들어가고, lock=1이면 0이될때까지 계속 대기한다
-옳은 solution X => mutual exclusion 보장 X!
*process A가 lock 0이어서 while문을 탈출했는데 탈출함과 동시 에 interrupt가 걸렸다 치자. 그럼 process B에서는 lock 값이 0이므로 while문을 빠져나와서 lock 값을 1로 만들고 critical section에 접근한다. 그러다가 B에서 switching이 일어나서 A로 다시 돌아가게 되면 A에서는 아까 interrupt이후의 상황인 lock을 1로 바꾸고 critical section으로 접근하게 된다. 이렇게 되면 동시에 두 프로세스가 critical section에 접근하는 상황이 발생하게 된다**

 

3)Strict Alternation solution to critical region problem
-Busy waiting★★ -> mutual exclusion 보장!
-지속적으로 변수 check
-하지만 피하는것이 좋다. => CPU time 낭비

-mutual exclusion 보장하지만 효율적 X...
-Spin lock★ :busy waiting을 이용하는 lock을 spin lock...
*3번째 조건을 위반한다*
=>process is blocked by the other not in its critical region
-프로세스 A가 임계구역에 들어갔다가 나오면, CPU가 임계구역을 사용중이지 않더라도, 프로세스 B가 실행되기전에는 A는 임계구역에 다시 들어갈 수 없다.

Busy Waiting 코드

 

@Mutual Exclusion with Busy Waiting(2) 피터슨 솔루션!

-Peterson's solution for achieving mutual exclusion => mutual exclusion 보장!!**
-turn은 공용변수이기때문에 거의 동시에 call이 되더라도 turn은 결국 둘 중 조금이라도 늦게 호출된 녀석의 값이 turn에 들어가게 된다. 그러면 먼저 들어온놈이 들어가게된다.(turn==process)
-turn과 process의 번호가 일치.

피터슨 솔루션 코드

 

@Mutual Exclusion with Busy Waiting(3)
#TSL instruction★★ : Test and Set Lock
*2가지 operation: 1. enter_region 2. leave_region
-lock값을 RX에 저장해두고 lock값을 1로
-**위 두 명령어는 쪼갤 수 없어서 그 사이에 스케줄링이 개입될 수 없다!!****
=>The operation is guaranteed to be indivisible
-critical region앞에는 enter region을, 뒤에는 leave region을

-REGISTER값이 0이 아니였으면 처음으로 돌아가고, 0이면 계속 진행...
-lock 값이 0이면 리턴. 0=열려있다. 그러면 이 프로세스는 critical region으로 들어감

-lock을 1에서 0으로
-critical region안에있을때 lock의 값은 1
-여기서 다른 프로세스가 또 실행되면 RX값이 1로,,,
-그러면 J명령어를 수행하게되면서 다시 처음으로,,,
=>busy waiting의 일종,,,
-TSL을 부르는 순간 lock의 값은 무조건 1로 세팅되어서 lock variable에서 발생했던 문제점이 안발생함!** <-이게 중요함!
    ㄴ중간에 스케줄링이 발생하여도 괜찮다.
    ㄴrace condition이 안 발생한다! TSL이 있기에 가능.
-TSL 명령을 수행하는 CPU는 수행이 끝날 때까지, 메모리 버스를 잠금->다른 어떤 CPU도 메모리에 접근 불가능(인터럽트를 끄는 것과는 다름, 한 CPU에서 인터럽트를 끄는 것은 다른 CPU의접근에 영향을 미치지 않는다.)

TSL instruction

 

 

@Sleep and Wakeup
Busy Waiting의 문제점들:
-Wasting of CPU time

 

-Priority inversion problem

-높은놈과 낮은놈 관계의 역설.
-process 스케쥴링의 하나인 process priority.
-우선순위가 높은거부터 수행함. 위에 녀석이 안 끝나면 밑에 있는 녀석들은 실행이 안됨. 그러면 이러한 경우에 낮은놈이 critical region에 들어갔을 때(running상태), 높은놈이 blocked->ready로 되면 이론상 높은놈으로되면서 높은놈도 critical region으로 갈라한다. 높은놈이 cpu를 뺏어서 들어가려한다. 하지만, 이 높은놈은 들어가지 못한다. 작은놈이 다 실행되어서 lock을 풀어야 들어갈 수 있다. 하지만 중요한것은 cpu를 차지하고있는놈은 높은놈이다. 근데 작은놈은 빨리 수행하고 나올 수가 없다... 왜냐하면 높은놈이 cpu를 가져갔기때문이다. 매우 역설적인 상황들인데, 결국엔 우선순위높은놈은 critical region에 들어가지 못한다!

Sleep and Wakeup
-critical region에 못 들어가면 sleep을 call 해서 blocked 상태로 간다. 그러면 CPU를 차지할 일이 없다. 그러면 작은놈이 나오면서 wakeup system call을 하면서  blocked상태에 있다가 ready로 된다.

 

@Sleep and Wakeup
#Producer-consumer problem♠
-Also known as the bounded-buffer(유한버퍼) problem
-두개가 용량이 한정된 버퍼를 공유. producer는 버퍼에 넣는 역할만. consumer는 버퍼로부터 뽑아가는 역할만.
-넣으려 했는데 버퍼가 꽉 차있으면 producer는 sleep한다. blocked상태로 간다. consumer가 하나를 가져가서 producer를 깨우기 전까지. 이와 반대의 경우도 같다.

♠♠♠♠
Race condition occurs when a wakeup set to a process that is not sleeping is lost.
*문제점: 버퍼가 비어있고, 소비자가 count값을 읽어서 0임을 알았다. 이 순간 스케줄러는 소비자의 '수행을 중지' 시키고 생산자를 수행하기 시작한다. 생산자는 아이템을 버퍼에 추가하고 count를 증가시켜 1이 되었다. 이전에 count값이 0이었으므로 생산자는 소비자가 sleep 상태일것이라고 생각하여 wakeup(consumer)를 실행한다. 불행하게도 소비자는 아직 잠든 상태가 아니므로 wakeup(customer)실행 이후에 소비자의 sleep()이 실행되어 wakeup 시그널이 사라지고 소비자는 영원히 잠들게 된다. 소비자 프로세스의 수행이 없으므로 생산자에 의해 버퍼가 가득차게 되어 생산자도 잠들게 된다. 이 문제의 본질은 아직 잠들지 않은 프로세스에 wakeup 시그널을 전송하면 소실된다는 것이다.

Sleep and Wakeup

 

@Semaphore★★
Usage
-down(P) operation(wait 함수)
-critical region
-up(V) operation(signal 함수)
-세마포어는 단순히 변수이다. 공유자원의 개수를 나타내는 변수.

 

@Semaphores★★
down(P) operation(wait)
-세마포어가 0보다 크면, 세마포어 값을 하나 감소시키고 진행.
-세마포어가 0이면, sleep상태로 들어간다.

 

up(V) operation(signal)
-자고있는 녀석이 있을경우 이 녀석을 깨운다.
-그렇지 않으면 세마포어의 값을 증가시킨다.

Each operation above is indivisible atomic action
-일반적으로 모든 interrupt가 잠시 비활성화된 시스템 호출로 구현된다.

 

 

@Semaphores★★

Solving the Producer-Consumer Problem using Semaphores★★ 문제해결!
-Semaphores solve the lost-wakeup problem
=>그 잠들고 깨우는 걸 받아야 되는데 깨우는 걸 받고 잠들면 영원히 잠드는 문제!

 

For mutual exclusion:
-하나의 프로세스만 버퍼를 읽고 쓰는것을 보장한다.
-Mutex: 공급자와 생산자가 동시에 버퍼에 접근하는 것을 막는다.
-binary semaphore: 1로 초기화되어서, 여러 프로세스들중 한개만이 critical region에 들어갈 수 있게 보장한다.

 

For synchronization:
-buffer가 꽉 찼을때 공급자를 stop하게하고, buffer가 비었을 때 소비자를 stop하게 보장한다.
-full: 차있는 slot의 수를 카운트
-empty: 비어있는 slot의 수를 카운트

Semaphores

 

@Mutex
세마포어의 단순화 버전.

둘 중 하나의 상태에 있을 수 있다:
-Unlocked: 0(사용가능)
-Locked: non-zero(usually 1) (기다림 필요)

Usage
-mutex_lock
-critical_region
-mutex_unlock

Implementation of mutex_lock and mutex_unlock

 

@Sharing data between processes
-세마포어와 같은 공유 데이터 구조는 커널에 저장될 수 있으며 시스템 호출을 통해서만 액세스할 수 있다.
-유닉스 및 윈도우를 포함한 대부분의 현대 운영 체제들은 프로세스들이 주소 공간의 일부를 다른 프로세스들과 공유 할 수 있는 방법을 제공한다.
-다른 방법이 없으면 공유 파일을 사용할 수 있다.