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

sky·2022년 6월 1일
운영체제정리
0

정리

목록 보기
9/13
post-thumbnail

[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) 문제

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

[OS] 파일 시스템

다음 포스트

[OS] 교착상태

0개의 댓글