[OS] 07. 프로세스 간 동기화 및 통신

(1) 개요

Concurrent Processes (병행 프로세스)

• 두 개 이상의 프로세스들이 동시에 수행됨을 의미한다.
  • 독립적으로 작업이 수행되며, 다른 프로세스와 협력하여 기능 수행도 가능하다.
  • 협력 수행 시에 프로세스 간의 *동기화 또는 통신이 필요하다.
  • 공유 자원을 가지고 수행한다.
• 병행 프로세스 처리는 제한된 자원을 공유하기 위해 *상호작용이 필요하다.
• 상호 작용하는 프로세스들을 동기화하지 않으면 문제가 발생할 수 있다.
  • Deadlock 문제, Critical Section 문제, 결과를 예측할 수 없는 상황 등이 발생할 수 있다.

*동기화 : 협력하는 프로세스 간에 실행 순서가 필요하다. ex)입금이 끝나야 출금이 수행되어야 한다.
*상호작용 : 제한된 자원을 공유하기 위함이며, 상호작용하는 프로세스는 순서에 맞게 실행되도록 동기화가 되어야 한다.

 

(2) Concurrent Processes Promblem

✔  병행 프로세스 처리 과정에서 OS가 반드시 해결해야 할 것

• 다른 Process가 관여하지 못하도록 공유 자원의 상호 배타적인 사용(Mutual exclusion)을 보장해야 한다.
• 하나의 기능을 공동으로 사용하여 수행하는 두 프로세스 간의 동기화(Synchronization)문제를 해결해야 한다. -> 프로세스 간에 순서를 정해서 한 프로세스만 처리한다.
• 두 개 이상의 프로세스의 실행 순서와 무관하게 항상 같은 결과를 얻을 수 있어야 한다.(일관성)
• Deadlock 문제를 해결할 수 있어야 한다.
• 프로세스 간에 자료 교환을 위한 메시지 전달 방식과 같은 통신 문제(Communication)의 해결이 필요하다.

 

➤  Critical Section (임계 구역)

• 어떤 프로세스가 공유 자원을 접근하면, 그 프로세스는 임계구역에 있다고 한다.
• 임계구역에 접근한 프로세스는 *상호 배제를 보장받아야 한다.
• 임계구역은 가능한 한 빨리 수행되어야만 하며, 프로세스가 임계구역에 들어간 후 블록 상태가 되어서는 안 된다.

*상호배제(Mutual Exclusion) : 하나의 프로세스만 공유 자원에 대해 배타적으로 접근하고 나머지 프로세스들은 공유 데이터의 접근할 필요가 있더라도 기다려야 한다.

 

 

➤  Mutual Exclusion (상호 배제)

• 다수의 프로세스들이 하나의 공유 자원(임계 구역)을 상호 배타적으로 사용한다.(동시 사용 불가)
• 공유 변수에 접근 중인 하나의 프로세스를 제외한 다른 프로세스들이 공유 변수를 접근하지 못하게 제어하는 기법이다.

수행중인 프로세스에서 save가 되기 전에 다른 프로세스가 수행되면 옳은 답이 나오지 않는다.

 

✔  Mutual Exclusion Algorithm 요구 조건

• 공유자원에 대해서는 어느 한 순간에 반드시 하나의 프로세스만이 임계구역에 진입해야 한다.
• 임계구역에 접근하고자 하는 프로세스의 수행이 무한 대기하지 않아야 한다.
• Starvation이 발생하지 않도록 해야 한다.
• Deadlock이 발생하지 않도록 해야 한다.
• 임계구역이 사용 중이 아니면 임계구역에 진입하기를 원하는 프로세스에게 즉시 진입하도록 허용해야 한다.
• 임계구역에 진입한 프로세스는 일정한 시간 내에 임계구역을 빠져 나와야 한다.

 

(3) Mutual Exclusion Algorithm (상호 배제 알고리즘)

➤  1단계 Mutual Exclusion Primitive(1단계 알고리즘)

• 한 순간에 단지 하나의 프로세스만이 임계 구역에 진입하도록 보장해야 한다.(상호배제 보장)
• 한 개의 공유 변수를 이용한다.(processnumber) -> 동기화를 위해 사용하는 공유 변수다.

Pseduo Code

program mutex1;
var processnumber;

p0(){ //프로세스 p0의 임계구역 procedure
    while(true){
        while(processnumber != 0) //p1의 진입여부 확인
        ;
        critical_section
        processnumber = 1; //p1에게 임계구역 진입순서 양보
    }
}
p1(){ //프로세스 p1의 임계구역 procedure
    while(true){
        while(processnumber != 1) //p0의 진입여부 확인
        ;
        critical_section
        processnumber = 1; //p0에게 임계구역 진입순서 양보
    }
}
//main
    processnumber = 1; //공유변수를 p1 진입 순서로 초기화
    parbegin
     p0(); //p0과 p1의 동시 수행 -> 어떤 것이 먼저 수행될지는 상황에 따라 변경
     p1();
    Parend

1단계 알고리즘은 상호배제를 만족시키지만 문제점이 있다.

• 임계구역 진입을 교대로 진입해야 하고, 빠른 프로세스는 느린 프로세스의 속도에 의존한다.
• 한 프로세스가 임계 구역 내에서 중지된다면 다른 프로세스도 수행을 할 수 없다.
• 공유 변수 설정에 따라 시작되는 순서가 결정된다.

 

➤  2단계 Mutual Exclusion Algorithm

• 두 개의 공유 변수(p0_inside, p1_inside)를 이용하여 상호배제를 해결하고자 한다.

Pseduo Code

program mutex2;
boolean p0_inside, p1_inside;

p0(){ 
    while(true){
        while(p1_inside == TRUE) 
        ;
        p0_inside = TRUE; //p0이 임계구역 진입시도
        critical_section
        p0_inside = FALSE; //p1에게 진입순서 양보
        remainder section 
    }
}
p1(){ 
    while(true){
        while(p0_inside == TRUE) 
        ;
        p0_inside = TRUE; //p1이 임계구역 진입시도
        critical_section
        p0_inside = FALSE; //p0에게 진입순서 양보
        remainder section 
    }
}
//main
    p0_inside = false, p1_inside = false;
    parbegin
     p0();
     p1();
    Parend

2개의 프로세스가 병행하면서 한 줄씩 수행했을 때 문제점이 생긴다.

• 동시에 임계구역 진입이 가능한 경우가 발생하여 상호배제가 보장되지 않는다.
• 1단계와 다르게 순서가 정해져 있지 않다. (p0이 먼저 들어와도 되고, p1이 먼저 들어와도 된다.)

 

➤  3단계 Mutual Exclusion Algorithm

• 2단계의 문제점 해결

Pseduo Code

program mutex3;
boolean p0_inside, p1_inside;

p0(){ 
    while(true){
        p0_inside = TRUE; 
        while(p1_inside == TRUE) 
        ;
        critical_section
        p0_inside = FALSE; 
        remainder section 
    }
}
p1(){ 
    while(true){
        p1_inside = TRUE; 
        while(p0_inside == TRUE) 
        ;
        critical_section
        p1_inside = FALSE; 
        remainder section 
    }
}
//main
    p0_inside = false, p1_inside = false;
    parbegin
     p0();
     p1();
    Parend

while문 수행 이전에 자신의 플래그(px_inside)를 true로 미리 변경한다.(상호배제는 보장) 하지만 교착상태가 발생(두 프로세스가 수행을 못하는 상태)할 위험이 있다.

• 두 프로세스가 while문 이전에 차례대로 px_inside를 각각 true로 변경하면, 내부의 while문에서 각각 무한 루프를 돌게 된다.
• while(p1_inside == TRUE)과 while(p0_inside == TRUE)

 

➤  4단계 Mutual Exclusion Algorithm

• 1단계와 3단계 알고리즘을 결합한 것이다.
• 3개의 공유 변수(p0_inside, p1_inside, processnumber)를 이용한다.

Pseduo Code

program mutex3;
boolean p0_inside, p1_inside;
var processesnumber;

p0(){ 
    while(true){
        p0_inside = TRUE;
        processesnumber = 1;
        while(p1_inside == TRUE and processesnumber == 1) 
        ;
        //p0의 진입여부 확인
        critical_section
        p0_inside = FALSE; 
        remainder section 
    }
}
p1(){ 
    while(true){
        p1_inside = TRUE; 
        processesnumber = 0;
        while(p0_inside == TRUE and processesnumber == 0) 
        ;
        //p1의 진입여부 확인
        critical_section
        p1_inside = FALSE; 
        remainder section 
    }
}
//main
    p0_inside = false, p1_inside = false;
    parbegin
     p0();
     p1();
    Parend

3단계 상호 배제 알고리즘의 교착상태 발생 위험을 제거하고, 상호배제도 만족시킨다.

 

(4) Synchronization by Hardware (하드웨어에 의한 동기)

하드웨어적인 임계구역 문제 해결

• 단일 프로세서(CPU) 시스템에서 임계구역 문제를 해결하기 위해서는 공유변수가 변경되는 동안 다른 프로세스가 공유변수에 접근하지 못하도록 혹은 인터럽트 발생을 허용하지 않도록 설정하면 된다.
• 더 이상 분할이 불가능한 특별한 하드웨어 명령인 *TestAndSet(targer)을 이용하여 임계구역 문제를 해결하고자 한다. (하드웨어 칩 이용)

*TestAndSet : 일단 수행이 시작되면 인터럽트 없이 모두 끝마쳐야 하는 하드웨어적 명령문으로, 공유변수 부분을 하드웨어 칩으로 구현한다. 다시 말해서 TestAndSet이 수행되는 동안 다른 것이 수행되지 않는다.

 

Pseudo Code

boolean TestAndSet(boolean & target){
    boolean temp = target;
    target = true;
    return temp;
    //target이 false인 경우, temp = false로 설정, false 반환
}
testandsetexample(){
    boolean lock;
    
    p0(){
        while(true){
            while(TestAndSet(lock))
            ;
            critical section
            lock = false;
            remainder section
        }
    }
    p1(){
        while(true){
            while(TestAndSet(lock))
            ;
            critical section
            lock = false;
            remainder section
        }
    }
    lock = false;
    parbegin
    p0();
    p1();
    parend
}

 

(5) Semaphore(세마포어)

✔  세마포어(임계구역에서 프로세스들의 동기화 방법)정의

• 프로세스 동기화 문제 해결을 위한 두 가지 연산(P, V)이 필요하다.
  P : 네덜란드어로 검사(Proberen)를 나타내며, 프로세스를 대기시켜서 동작으로 임계구역에 진입하기 위한 연산(wait), S값을 감소시킨다. (공유자원을 가져간다)
  V : 네덜란드어로 증가(Verhogen)를 나타내며, 대기 중인 프로세스를 깨우기 위해 신호를 보내는 동작으로 임계구역에서 나오기 위한 연산(signal), S값을 증가시킨다. (공유자원을 반납한다)
  S : 세마포어를 나타내며 표준 단위 연산 P와 V에 의해서만 접근되는 정수 변수로, 이 S값을 이용하여 프로세스들의 임계구역 접근을 제어한다.

 

세마포어 사용법과 P연산 및 V연산 정의

while(true){
    P(S);
    임계구역
    while S <= 0 do no-operation; // S = 0 일 때 또 다른 프로세스가 공유자원을 요청하면 음수값을 방지
    S = S - 1;
    V(S);
    잔류구역
    S = S + 1;
}

 

 

✔  세마포어를 이용한 생산자/소비자(데이터의 생산자/소비자) 문제 해결

• 공유변수 semaphore mutex = 1; -> 버퍼 접근에 대한 상호 배제를 위한 세마포어
• 공유변수 semaphore empty = n; -> 버퍼에 비어 있는 항목의 개수를 위한 세마포어
• 공유변수 semaphore full = 0; -> 버퍼에 채워져 있는 데이터의 개수를 위한 세마포어
• 생산자 : 버퍼에 데이터를 넣기 위해 버퍼의 비어 있는 항목의 수(empty)를 1감소시킨다.
  • empty값이 0이면 프로세스가 블록된다. 다시 말해 생산자가 버퍼에 접근하지 못한다.
• 소비자 : 버퍼에 채워진 데이터의 개수를 나타내는 full값을 1감소시킨다.
  • full값이 0이면 프로세스가 블록된다. 다시 말해 소비자가 버퍼에 접근하지 못한다.

 

 

✔  세마포어를 이용한 데이터 읽기/쓰기 문제 해결

• 공유변수 semaphore wrt = 1; -> 쓰기 프로세스 접근 시 배타적 사용을 위한 세마포어
• 공유변수 semaphore mutex = 1; -> readcount 변수의 상호 배제를 위한 세마포어
• int readcount = 0; -> 읽기 프로세스의 개수 (초기 값은 0이다)
• wrt 세마포어는 쓰기 프로세스가 임계구역에 있을 경우, 다른 쓰기나 읽기 프로세스가 임계구역에 접근하지 못하도록 한다.
• P(wrt) : 읽기 프로세스가 1개 이상인 경우 쓰기 프로세스가 실행되지 못하도록 하다.
• readcount-- : 읽기 프로세스가 읽기를 마치고 빠져 나오는 경우에 자신을 제외한 다른 읽기 프로세스가 존재하는 경우에는 그냥 빠져 나온다.
• V(wrt) : 자신이 마지막 읽기 프로세스인 경우에는 쓰기 프로세스의 임계구역 진입을 허용한다.

 

(6) Monitor

개요 및 정의

• 순차적으로만 사용할 수 있는 특정 공유자원이나 공유자원 그룹을 할당하는데 사용된다.
• 데이터 및 프로시듀어를 포함하는 병행성 구조이다.
• 공유자원에 접근하고자 하는 프로세스는 반드시 특정 모니터의 진입부(entry)를 호출해야 한다.
• 이미 사용 중인 모니터에 들어가려고 하는 다른 프로세는 반드시 대기해야 한다.

 

모니터

• 세마포어의 P, V연산이 프로그램 전체에 퍼져 있어 이들의 연산이 미치는 영향을 전체적으로 파악하기 쉽지 않아 프로그램 작성이 어려운 단점을 극복하기 위해 모니터 방법이 필요하다.
  • 세마포어와 비슷한 기능을 하지만 제어하기가 용이하다.
• 프로그래밍 언엥서 지원한다. 즉, 프로그램 라이브러리 형태로 지원한다.
• 데이터와 이들 데이터를 처리하는 프로시듀어의 집합이다. (객체지향 개념)
• 모니터 내의 데이터는 모니터 내부에 의해서만 접근이 가능하므로 모니터 외부의 프로세스는 접근할 수 없어 정보 은폐(Informaiton Hiding)라고도 한다. (객체지향 개념)

 

✔ 모니터 사용

모니터 구조

• 하나의 프로세스가 모니터 내부에 머물러 있으면, 다른 프로세스의 진입을 허용할 수 없으므로 다른 프로세스는 모니터 밖에서 signal()이 있기까지 대기해야 한다.
• 동기화 기법이 필요하다면 프로그래머는 조건 변수를 선언하여 해결한다.
• condition x에 대하여 x.wait()와 x.signal()이 이용된다.
• 조건 변수에서 호출될 수 있는 연산은 wait와 signal이다.

 

연산 : x.wait() or wait(x)

x.wait() or wait(x) 연산을 호출하는 프로세는 다른 프로세를 다음 연산이 호출될 때까지 중단시킨다. 세마포어의 P연산과 유사하고, x는 세마포어의 S와 유사하다.

연산 : x.signal() or signal(x)
x.signal() or signal(x)은 중단된 다른 프로세스를 재개시킨다. 세마포어의 V연산과 유사하다.

 

환형 버퍼에서 생산자/소비자 문제에 대한 모니터 사용 예시

 

(7) Message

• 프로세스 간의 통신 및 동기화에 적합한 비교적 단순한 메커니즘이다.
• 공유변수를 이용한 방법은 공유변수에서 병목현상 문제가 발생할 수 있고, 공유변수 파괴 시 시스템 성능의 현저한 저하 문제가 발생하여 이에 프로세스 간 직접 통신을 통하여 상호 간에 순서를 정하여 동기화를 해결하고자 한다.
• 메시지의 정의는 송신측 프로세스와 수신측 프로세스 간에 교환될 수 있는 정보의 집합이다.
• 분산 OS에서 메시지 메커니즘의 사용이 보편화 되어 있다.

 

메시지 형식
송신측 및 수신측 식별자(identifier)길이, 형식(type), data로 구성된다.

메시지 발생 시 고려사항
naming 문제 : 메시지 교환에 관계되는 해당 프로세스들이 상대 프로세스를 설정하는 방법을 결정한다.
직접 네이밍과 간접 네이밍 방식의 두 가지 형태가 존재한다.

 

➤  직접 Naming Method

• 송신측(sender)이 특정 수신측(recipient)을 설정해야 하고, 반대로 메시지 수신을 희망하는 수신측은 송신측을 설정한다.
• 일대일 통신 관계로 인하여 보다 안전하고 확실한 메시지 통신이 가능하다.

process A;
..
send(B, message); //A가 B에게 메시지를 보내겠다.
..
process B;
..
receive(A, message); //B가 A로부터 메시지를 받겠다.
..

 

 

➤  간접 Naming Method

• 메시지가 특정 목적만을 위하여 사용되는 영역에 송신되고, 그 영역에서 다른 메시지도 수신하는 방식으로 특정 영역을 우편함(mailbox)이라고 부른다.
• 모든 프로세스 간의 메시지 교환은 이 우편함을 통하여 수행된다.
• 송신측과 수신측 간에 일대일, 일 대 다수, 다수 대 일, 다수 대 다수의 통신 관계가 가능하다는 점에서 매우 유용하다.

process A;
..
send(mailbox1, message); 
..
process B;
..
receive(mailbox1, message);
..

 

 

✔  메시지 방식에서의 고려해야 할 사항

복사(Copying) 문제

• 전체 메시지를 수신측의 주소 공간에 복사하여 두거나, 또는 두 프로세스 간의 메시지에 대한 포인터를 단순히 전달함으로써 해결한다.
• 한 프로세스에서 오류가 발생하더라도 이로 인하여 메시지의 지역 복사본만이 손상된다.
• 송신측 프로세스의 버퍼에 메시지 복사, 수신측 프로세스의 버퍼에 메시지 다시 복사한다.
• 단점은 메시지 복사가 기억장치와 CPU의 사이클을 낭비한다.

 

버퍼링(Buffering) 문제

• 수신을 위한 준비가 되어 있지 않을 경우 송신측은 메시지를 일단 버퍼에 송신(저장)하고 나중에 수신측이 준비되면 그 때 전송된다.
• 비동기적 통신을 가능하게 하기 위해서는 버퍼링 방식이 필요하다.
• 수신측 상황에 관계없이 자신의 실행을 계속할 수 있는 과정을 “set and forget” 운영이라 하며, 이는 시스템 병행성의 정도를 향상시킨다.

 

길이(Length) 문제

• 메시지의 길이를 고정적으로 할 것인지 또는 가변적으로 할 것인지를 결정한다.
• 고정길이 메시지: 구현이 용이하나, 버퍼의 크기에 비하여 메시지가 작을 경우 버퍼의 낭비를 초래하며, 반대로 메시지가 클 경우에는 메시지를 분할하여 전송해야 하는 문제점이 있다.
• 가변길이 메시지: 동적으로 버퍼를 생성하는 것으로 구현이 복잡하기는 하나 높은 적응력을 가진다.