avatar

풀스택 웹🌐 개발자 지망생 🧑🏽‍💻
➕ 인공지능 관심 🤖

Categories

Recent views

  • 1
  • 2
  • 3
  • 4
  • 5

OS 정리-Chap 4-병행 프로세스와 상호배제

4. 병행 프로세스와 상호배제

🗣️ 출처

IT COOK BOOK 운영체제 (개정 3판, 구현회 저, 한빛 아카데미) 를 정리한 내용입니다.

병행 프로세스

병행 프로세스란?

프로세스는 프로세서, 레지스터, 캐시, 입출력 장치 등 여러 자원을 사용하며, 이중, 메모리 같은 자원은 모든 프로세스가 동시에 병렬로 공유

프로세서 자원을 시분할을 통해 여러 프로세서가 동시에 작업하는 것처럼 보이게 하는 것을 병행 프로세스라고 하며, 다음 두 가지로 나뉜다.

독립 프로세스

단일 처리 시스템에서 다른 프로세스와 자원을 공유하지않고, 영향을 주고받지 않는 독립적인 병행프로세스. 따라서 초깃값에 따라 항상 동일한 결과를 보여주며, 중지 후, 변동사항 없이 다시 시작 가능하다.

단일 프로그래밍, 다중 프로그래밍, 다중 처리의 프로세스가 예시이다.

협력 프로세스

다른 프로세스에 영향과 상호작용을 주고 받으며 특정 기능을 수행하는 비동기적 프로세스.
자원 효율성, 계산 속도, 모듈적 구성, 사용자 동시처리성 향상에 기여한다.

예를 들어, 파일을 읽는 프로세스와 파일을 쓰는 프로세스는 파일을 쓰는 순간 파일 내용이 바뀌므로 파일을 읽는 프로세스가 영향을 받으며, 이 덕분에 사용자는 편리하고 빠르게 문서작업이 가능하다.

따라서 서로 충돌이 일어나지 않게 하기위해 다음과 같은 세가지 형태의 상호작용을 한다.

  • 경쟁 관계, 다중 프로그래밍 환경에서 디스크나 프린터를 접근할 때, 프로세스가 서로를 인식하지 못하며, 정보 교환이 없고 완전히 상호배제함.

  • 간접적으로 서로의 관계를 인식, 입출력 버스 등을 공유 시, 다른 프로세스의 정보나 타이밍에 영향을 받고 개체 공유를 위해 협력한다.

  • 프로세스끼리 함수를 통해 서로 인식하고 통신, 완전한 협력 관계 하에 병행하여 동작한다.

✍ 병행성과 병렬성

병행성 : 한 프로세서가 시분할로 공유하는 여러 프로세스를 나누어 처리
병렬성 : 여러 프로세서가 동시에 여러 프로세스를 처리

병행 프로세스의 해결 과제

병행성은 다중, 단일 처리 시스템 등에서 시스템의 신뢰도를 높이고 처리 속도를 높이는데 중요한데, 몇 가지 문제를 가지고 있다.

  • 공유 자원을 상호 배타적으로 사용해야 한다. 프린터, 통신망 등이 예시.

  • 병행 프로세스 간에는 협력이나 동기화 되야 한다. 상호배제는 동기화의 한 형태.

  • 두 프로세스 간에 데이터 교환 및 통신이 되어야 한다.

  • 프로세스는 동시에 수행하는 다른 프로세스의 실행 속도와 관계없이 항상 일정한 실행 결과를 보장하도록 결정성(determinancy)을 확보해야 한다.

  • 교착 상태를 해결하고 병행 프로세스들의 병렬 처리 능력을 극대화해야 함.

  • 실행 검증 문제를 해결해야 함.

  • 병행 프로세스를 수행하는 과정에서 발생하는 상호배제를 보장해야함. 즉, 어떤 작업을 한 프로세스가 수행 중이면 다른 프로세스는 접근 불가.

선행 그래프와 병행 프로그램

이때, 상호배제를 보장하기 위해 프로세스는 선행 그래프를 이용한다.

선행 그래프(precedence graph)

프로세스는 프로세스 집합과 이것의 선행 제약(precedence constraint)로 정의할 수 있다.
프로세스 집합은 프로세스들의 모임이고, 선행 제약은 프로세스 집합 내 원소를 순서대로 다른 상태로 옮기는 것이다.

예를 들어 프로세스 집합 $P_1, P_2, \cdots, P_n$이 있고, 선행 제약이 $P_i<P_j$이면, 프로세스 상태는 $P_i$이후 $P_j$로 옮겨간다. 선행제약이 없다면, 두 프로세스는 독립적이란 의미이며, 서로 영향을 주지 않으므로 병행 실행이 가능하다.

선행 그래프(precedence graph)는 선행 제약을 논리적으로 표현한 것으로, 순차적 활동을 표현하는 방향성 비순환 그래프이다. 즉, 연결선(Edge)로 연결된 노드 간에는 한쪽 방향으로만 이동할 수 있으며, 순환(Cycle)이 존재하지 않는다.

선행 그래프에서의 노드 혹은 활동은 소프트웨어 작업이나 동시 실행 가능한 프로그램을 의미한다.

그림 4-2 (b)의 선행 그래프를 예시로 들자면

  • $S_1$과 $S_2$는 서로 독립적이므로 동시 수행 가능

  • $S_3$은 a 값과 b 값을 할당받기 전에 수행하면 안된다.

  • $S_4$는 c 값을 계산하기 전에 수행 불가

그림 4-2 (a)에서 알고리즘의 일부를 병행 수행, 예를 들어 값 a와 b를 동시에 구하려면 프로세서 하나에 기능 단위를 여러 개 두거나 프로세서를 여러 개 사용한다.

예를 들어 그림 4-3의 선행 관계는 비순환적이다. 아래 그림 4-4의 경우 $S_2$는 $S_3$가 끝나야만 수행가능하고, $S_3$는 $S_2$가 끝나야만 수행가능하다는 의미를 가진 순한 관계가 존재하므로, 모순이 존재하며, 수행 불가하다.

fork와 join 구조

실제 프로그램의 선행 관계를 표기하기에는 2차원 선행 그래프는 너무 단순하며 추가적으로 fork, join, 병행 문장 등의 구조가 필요하다.

  • fork 명령어

    fork L 문장을 통해 병행 프로세스를 2개로 나눌 수 있다. goto 문과 비슷하기 때문에 조금 복잡하게 보일 수 있다.
    아래 예시 그림 4-5에서는 fork 명령어를 통해 $S_2$와 $S_3$가 병행 수행된다.

  • join 명령어

    fork와는 반대로 병행 연산 2개를 하나로 결합하는 명령으로, 병합 대상이 되는 두 프로세스 중 먼저 끝나는 순서대로 join을 먼저 수행한다.

    세개 이상의 프로세스를 join해야할 경우, 먼저 끝나는 두 프로세스가 서로 join된 뒤, 그 결과값과 다음에 끝나는 프로세스가 join된다.

    그림 4-6에서 count 매개변수로 join할 프로세스 갯수를 집어넣고, join이 실행되면, 프로세스간 조인이 진행되면서 1씩 줄어들며 0이 되면 join이 종료된다.

그림 4-7은 fork와 join을 이용한 병행 수행과 병합을 표현한 알고리즘과 선행 그래프 예시다.

그림 4-8은 3개의 노드가 join되므로, 유입 정도(In degree)는 3이며 count의 초기값은 3이다.

병행 문장

병행 문장은 하나의 프로세스가 여러 병렬 프로세스로 퍼졌다가 다시 하나로 뭉쳐지는 것을 나타내는 고급 언어 구조이다.

parbegin S1; S2; .....; Sn; parend;

각 $S_i$는 단일 문장이고, parbegin과 parend 사이의 모든 문장은 병행 수행가능 하다. 그림 4-9 예시처럼 최초로 시작되는 프로세스인 $S_0$와 모든 프로세스가 끝난 후에 실행되는 $S_{n+1}$ 문장을 추가해 정의할 수 있다.

이때 BEGIN과 END는 순차 실행 문장으로, 이를 통해 그림 4-10와 같은 복잡한 구조를 표현할 수 있다.

아래 그림 4-11은 그림 4-2를 parbegin/parend 구조를 이용해 표현한 것이다.

병행 문장은 블록 구조의 고급 언어에 쉽게 추가할 수 있으며, 다른 구조적 제어 문장의 장점을 많이 보여준다.

상호 배제와 동기화

상호배제의 개념

상호배제는 병행 프로세스에서 프로세스 하나가 공유 자원을 사용 시 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법이다. 줄여서 mutex(MUTual EXclusion)이라고도 한다.

예를 들어 그림 4-13처럼 공유 메모리를 $P_1$ 프로세스가 사용하고 있으면, $P_2$는 해당 공유 메모리에 접근할 수 없도록 막아야(=상호배제) 한다.

읽기 연산처럼 동시에 읽어도 문제없는 연산을 제외하고, 쓰기 연산의 경우, 프로세스 별로 차레대로 공유 자원에 접근해야 하며, 이를 제어하는 방법을 동기화라고 한다. 동기화를 통해 상호배제를 구현할 수 있지만 교착 상태와 기아 상태가 발생할 수 있다.

그림 4-13의 공유 메모리 같이 두 프로세스가 동시에 사용할 수 없는 공유 자원을 임계 자원(critical resource), 이러한 임계 자원에 접근하고 실행하는 프로그램 코드 부분을 임계 영역(critical section)이라 한다.

성공적인 상호배제 연산은 다음과 같은 4개의 조건을 만족해야 한다.

  • 두 프로세스는 동시에 공유 자원에 진입할 수 없다.

  • 프로세스의 속도나 프로세서 수에 영향을 받지 않음.

  • 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단 가능.

  • 프로세스가 공유 자원을 사용하려고 너무 오래 기다리면 안됨.

임계 영역

임계 영역의 예시로는 입출력 장치 간의 버퍼가 존재하며, 임계 영역에서는 작업을 빠르게 수행하고, 특정 프로세스가 임계 영역에 오래 머물거나 무한 루프 등에 빠지지 않게 관리해야 한다.

임계 영역으로 상호배제를 구현할 수 있는데, 임계영역에 다른 프로세스가 있으면, 이 프로세스는 다른 프로세스가 임계 영역에 들어가지 못하게 진입 상호배제를 수행하며, 임계영역에서 나오는 프로세스는 탈출 상호배제를 수행하여 다른 프로세스가 임계 영역에 들어갈 수 있도록 해야한다. 물론, 이 동작은 단일 머신 사이클에서의 동작이며, 다중 처리 시스템에서는 이 행동만으로 상호배제가 되지 않는다.

임계 영역의 상호배제를 자물쇠와 열쇠로 비유하면, 그림 4-14처럼 어떤 프로세스가 자물쇠를 풀 열쇠를 가지고 있는지 확인하는 검사 동작과, 다른 프로세스가 사용 못하도록 자물쇠로 잠그는 동작으로 분류할 수 있다.

이를 코드로 표현하자면 다음과 같다.

do &#123;
    while (turn != i); /* 진입 영역 */
    /* 임계 영역 */
    turn = j;/* 탈출 영역 */
    /* 나머지 영역 */
&#125; while (TRUE)

진입 영역에서는 각 프로세스가 임계 영역에 들어갈 수 있도록 요청한다.
만약 turn 변수가 i, 즉 자기 자신의 순번 턴이 되면, 임계영역에 진입하고, 순번이 아니면 무한 루프로 대기한다.

이후 임계 영역에서 작업을 처리한 후, 탈출 영역에서 다음 순번의 turn으로 바꾸어 준 뒤 임계 영역에서 나가게 된다.

임계영역은 세 가지 조건을 만족해야 성공적인 상호배제가 이루어진다.

  • 상호배제 : 어떤 프로세스가 임계 영역에서 작업 중이면 다른 프로세스는 임계 영역으로 들어갈 수 없다.

  • 진행 : 임계 영역에서 프로세스가 없는 상태에서 여러 프로세스가 들어가려고 할 때는 어떤 프로세스가 들어갈지 적절히 결정해야 한다.

  • 한정 대기: 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하기 위해 한번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 페널티를 받는다.

생산자-소비자 문제와 상호배제를 해결하는 초기의 시도

생산자-소비자 문제는 운영체제에서 비동기적으로 수행하는 모델로, 생산자 프로세스가 생선한 정보를 소비자 프로세스가 소비하는 형태이다.

예를 들어 그림 4-17에서 라인 프린터 드라이버는 라인 프린터가 사용하는 문자 데이터를 생산한다.

생산자는 소비자에게 데이터를 전송할 때, 소비자가 받을 준비가 됬을 때만 보내게 만들기 위해 버퍼를 도입하여 해결한다. (그림 4-16)

소비자가 받지 못할 때는 생산자는 버퍼에 데이터를 보내어 쌓고, 소비자는 여유가 생기면 데이터를 버퍼에서 가져감으로써, 생산자가 소비자의 처리속도에 영향을 받지않고 작업을 할 수 있다.


만약, 버퍼의 최대 크기가 유한하다면,

  • 버퍼가 가득찼을 때는 생산자가 더 이상 데이터를 보내지 않고 소비자가 버퍼를 소모해줄 때까지 대기 하도록

  • 버퍼가 비어있다면 소비자가 더 이상 데이터를 소비하지 않고 생산자가 버퍼를 채워줄 때까지 대기 하도록

두 가지 경우에 동기화가 필요하다.

이러한 동기화에 대해 먼저 무한 버퍼일 경우 소비자와 생산자의 알고리즘은 아래의 그림 4-18과 같다.


유한한 크기의 버퍼에서는 그림 4-16처럼 원형으로 순환하는 배열을 구현한 뒤, 삽입 포인터와 삭제 포인터를 구현하여 해결할 수 있다.

삽입 포인터가 삭제 포인터보다 앞선 번호라면(modulo 연산의 원형 큐로 구현시 무조건 큰 번호가 앞서지 않으므로 주의), 버퍼에 값이 존재하는 것이다.

유한 버퍼를 코드로 구현하면 다음과 같다.

// 공유 데이터의 선언
#define BUFFER_SIZE 10 //버퍼 최대 크기
typedef struct &#123;
    DATA data;
&#125; item;
item buffer[BUFFER_SIZE];
int in = 0; // 삽입할 원소 자리 포인터
int out = 0; // 삭제할 원소 자리 포인터
int counter = 0; // 버퍼 내 원소의 갯수

생산자와 소비자 두 프로세스는 공통적으로 while 문으로 counter 변수를 계속 확인하며 검사한다.

//생산자 프로세스
item nextProduced; //생산하는 새로운 원소를 위한 변수
while (true) &#123;
    while (counter == BUFFER_SIZE); //버퍼가 가득 차 아무일도 하지 않음
    buffer[in] = nextProduced;
    in = (in+1) &#37; BUFFER_SIZE;
    counter++;
&#125;


//소비자 프로세스
item nextConsumed; //소비하기 위해 추출한 원소를 위한 변수
while (true)&#123;    
    while (counter == 0); //버퍼가 비어 아무 일도 하지 않음
    nextConsumed = buffer[out];
    out = (out+1) &#37; BUFFER_SIZE;
    counter--;
&#125;

하지만 이러한 생산자-소비자 방식은 동시에 실행될 시 프로세스의 접근 순서에 따라 공유 데이터이 달라지게될 위험이 있다. 예를 들어 생산자-소비자 방식의 소스코드의 마지막 줄의 코드를 레지스터의 관점에서 살펴본다면 다음과 같이 작동한다.

//counter++ 기계어

register_1 = counter;
register_1 = register_1 + 1;
counter = register_1;

//counter-- 기계어

register_2 = counter;
register_2 = register_2 -1;
counter = register_2;

만약 이 두 코드가 동시에 실행되어 아래 코드와 같이 섞여 버려 다음과 같은 결과를 낼 수 있다.

// 초기 counter값은 5로 초기화
register_1 = counter; // register_1 = 5
register_1 = register_1 + 1; // register_1 = 6
register_2 = counter; // register_1 = 5
register_2 = register_2 - 1; // register_2 = 4 
counter = register_1; // counter = 6
counter = register_2; // counter = 4

정상적으로 동시성을 적용하면 counter 값은 5가 되는게 정상이지만, 공유 데이터인 counter의 접근 순서에 따라 실행결과가 6 또는 4로 달라지게 된다.

예시의 생산자-소비자 프로세스처럼 이렇게 공유 데이터 접근 순서가 달라지면 동일한 결과값을 보장하지 못하는 프로세스들을 경쟁 상태(race condition)에 놓여져 있다고 한다.

경쟁 상태를 예방하려면 병행 프로세스들을 동기화해야 하며, 동기화는 임계영역을 이용한 상호배제로 구현할 수 있다. 즉 공유 변수 counter를 임계 영역으로 두고, 상호배제해야한다.

상호배제 방법들

✍ 상호배제의 다양한 방법들
수준 방법 종류
고급 소프트웨어 - 데커의 알고리즘
- 크누스의 알고리즘
- 램포트의 빵집 알고리즘
- 핸슨의 알고리즘
- 다익스트라의 알고리즘
  프로그래밍 언어, 운영체제 수준 소프트웨어 - 세마포
- 모니터
저급 하드웨어 수준 원자 연산 TestAndSet(TAS)

고급 방식들

데커 알고리즘

데커 알고리즘은 두 프로세스가 서로 통신하기 위해 공유 메모리를 사용하여 충돌 없이 단일 자원을 공유할 수 있도록 허용하는 알고리즘이다.

각 프로세스는 같은 수의 플래그를 설정한 후, 다른 프로세스의 플래그를 무한 루프로 확인한 뒤, 임계 영역 할당을 기다린다. 다만 이 또한, 우연하게 동시에 플래그를 설정 및 검사하면 교착 상태가 발생할 수 있다.

데커 알고리즘은 다음과 같은 장점을 가지고 있다.

  • 특별한 하드웨어 명령문 필요 없음

  • 임계 영역 바깥에서 수행중인 프로세스가 다른 프로세스들이 임계 영역에 들어가려는 것을 막지 않는다.

  • 임계 영역에 들어가기를 원하는 프로세서를 무한정 기다리게 하지 않는다.

데커 알고리즘을 코드로 구현하면 다음과 같다.

// 프로세스가 공유하는 데이터 flag[] : 부울(boolean) 배열, turn : 정수
flag[0] = false;
flag[1] = false;
turn = 0 ;                         // 공유 변수, 0 또는 1


// 프로세스 P0;                     // 프로세스 P0의 임계 영역 진입 절차
flag[0] = true;                    // P0의 임계 영역 진입 표시
while (flag[1] == true) &#123;          // P1의 임계 영역 집입 여부 확인
    if (turn == 1) &#123;               // P1이 진입할 차례가 되면
        flag[0] = false;           // 플래그를 재설정해 P1에 진입 순서 양보
        while (turn == 1) &#123;        // turn을 바꿀 때까지 대기
           // 바쁜 대기
        &#125;
        flag[0] = true;            // P1이 임계 영역에 재진입 시
    &#125;
&#125;

/* 임계 영역 */
turn = 1;                          // P1에 진입 순서 제공
flag[0] = false;                   // P0의 임계 영역 사용 완료 지정
/* 나머지 영역 */                    // P0의 나머지 영역 수행

// 프로세스 P1; // 프로세스 P1의 임계 영역 진입 절차
flag[1] = true;
while (flag[0] == true) &#123;
    if (turn == 0) &#123;
        flag[1] = false;
        while (turn == 0) &#123;
           // 바쁜 대기
        &#125;
        flag[1] = true;
    &#125;
&#125;
/* 임계 영역 */
turn = 0;
flag[1] = false;
/* 나머지 영역 */

  • $P_0$은 flag[0]을 true로 설정하여 임계 영역 사실을 고지한다.

  • 이후 while문으로 flag[1]을 검사하여 $P_1$의 임계 영역 진입 여부를 확인한 뒤,

    • false이면 $P_0$이 임계 영역으로 진입하고

    • true이면 $P_1$이 임계 영역에 진입할 차례라서 자신의 플래그 flag[0]를 false로 설정한 뒤, 아래의 while문으로 이동해 바쁜 대기한다.

  • 공유 변수 turn을 통해 두 프로세스가 동시에 임계 영역에 들어가는 것을 방지한다.

이외의 소프트웨어 상호배제 알고리즘

  • 다익스트라 상호배제 : 2개 이상의 프로세스 상호배제 문제 해결, 가장 짧은 평균 대기시간 제공, 실행 시간이 가장 짧은 프로세스에 할당하는 세마포 방법

  • 크누스 : 이전 알고리즘 관계를 분석 후, 일치 패턴을 찾아 패턴 반복을 줄이는 방법으로 무한정 연기를 해결, 단 프로세스들이 평균 대기시간이 김.

  • 램포트 빵집 : 준비 상태 큐에서 기다리는 프로세스마다 우선 순위를 부여해 그중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당하는 방법. 빵집 번호표에 비유

  • 핸슨 : 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것으로 대기 시간과 실행 시간을 이용하는 모니터 방법

TestAndSet(TAS) 명령어

TestAndSet(TAS) 명령어는 하드웨어 명령어로, 메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있다.

이를 이용하면 실행 효율이 좋고, 대기시간이 짧으면서 간단하게 구현할 수 있다.

원자적 연산(atomic operation)은 중단 없이 실행하고 중간에 다른 사람이 수정할 수 없는 컴퓨터의 최소 단위 연산이다. 메모리의 1비트에서 작동한다. 따라서 중간에 다른 명령어가 들어갈 수 없어 상기했던 경쟁 상태가 벌어지지 않는다.

총 2개의 명령어인 TestAndSet 명령어와, TestAndSet에 지역변수 lock을 설정하는 명령어로 이루어진다.

TestAndSet 명령어는 읽기와 쓰기 모두를 제공하며, 해당 주소의 값을 읽고 새 값으로 교체하면서 해당 메모리 위치의 이전 값을 돌려준다. 동작을 코드로 설명하자면 다음과 같다.

// TestAndSet 명령어의 코드 구현, 실제로는 원자적 연산이므로 기계어로 되어 있다.
// taget을 검사하고, target 값을 true로 설정
boolean TestAndSet (boolean *target)&#123;
    bloolean temp = *target; // 이전 값 기록
    *target = true;          // true로 설정
    return temp;             // 값 반환
&#125;

부울 변수 lock을 이용해 프로세스의 임계영역에 존재를 1 또는 0으로 설정할 수 있다.
기계가 TAS 명령어를 지원시, 부울 변수 lock을 false로 초기화하여 상호배제를 구현할 수 있다.

//lock을 사용한 상호 배제
do
&#123;
    while (TestAndSet(&#38;lock)); 
    // lock을 검사하여 true이면 대기, false이면 임계 영역 진입
    //임계 영역       
    lock = false;    // 다른 프로세스의 진입 허용의미로 lock을 false로
    //나머지 영역
&#125; while (true);

최초로 lock 변수를 검사하여 true로 초기화 되어있으면, 임계영역의 사용이 막혀있는 상태이며, false으로 초기화했으면, 임계 영역에 진입 가능하다.

진입하면, TAS 명령어로 lock의 값이 true가 되므로, 다른 프로세스는 임계영역에 접근하지 못하고 while문에서 무한 대기하게 된다.

이후 임계영역에서의 작업이 끝나면 lock을 false로 재설정하여 다른 프로세스가 접근가능하다.

하지만 프로세스가 3개 이상일 경우, 무한대기 상태로 빠질 수 있으며, 이를 막기 위해 아래와 같은 코드로 상호배제를 구현할 수 있다.

boolean waiting[n]; // flag들의 모임 배열
boolean lock = false;
int j; // 0...n-1
boolean key;

false로 초기화된 공유 배열인 waiting[0...n-1]로 선언한다. 공유 부울 변수 lock은 모든 프로세스에 전역변수로 선언하여 상호배제를 구현할 수 있다.

// TestAndSet 명령어를 이용한 상호배제
do                               // 프로세스 Pi의 진입 영역
&#123;
    waiting[i] = true;
    key = true;
    while (waiting[i] &#38;&#38; key) 
        key = TestAndSet(&#38;lock);
    waiting[i] = false;
        // 임계 영역
        // 탈출 영역
    j = (i+1)&#37;n;
    while ((j!=i)&#38;&#38; !waiting[j]) // 대기 중인 프로세스를 찾음
        j = (j+1)&#37;n;
    if (j == i)                  // 대기 중인 프로세를 없으면
        lock = false;            // 다른 프로세스의 진입 허용
    else                         // 대기 프로세스가 있으면 다음 순서로 임계영역 진입
        waiting[j] = false;      // Pj가 임계 영역에 진입할 수 있도록
&#125; while (true);

프로세스 i가 임계영역을 진입하기 위해서는 자신의 flag waiting[i]를 true로 놓은 뒤, TAS를 통해 key를 가져오려 시도한다.
초기에 key 변수를 false로 초기화했으므로, key 값은 false로 변하고 lock 값은 true가 되어 while문에서 탈출하게 되고, 임계 영역에 들어서게 된다.

  • 만약 다른 프로세서가 사용하고 있다면 key 변수는 true일 것이고, while문을 통과하지 못하고 바쁜 대기 상태에 빠질 것이다.

이후 임계 영역을을 지난뒤, 자신보다 우선순위가 낮은 프로세스 중 우선순위가 높은 순서대로 waiting[j] 플래그가 true인 프로세스를 찾는다.

  • 찾게 된다면, 해당 프로세스에게 넘겨주기 위해 waiting[j] 플래그를 false로 바꾼다. 그럴 경우 key값과 관계없이 해당 프로세스는 임계영역에 들어가게 될 것이다.

  • 만약 없다면, 한바퀴 돌아 자기 자신의 번호인 i를 가르키게 되며, 다른 프로세스의 진입을 허용하기 위해 lock 변수를 false로 설정한다.

장단 TestAndSet 명령어의 장단
장점 사용자 수준에서 가능
- 메인 메모리를 공유하는 다중, 단일 프로세서 환경에서 프로세스 수에 관계없음
- lock 변수 수에 상관없이 구현
- 구현이 단순하고 확인이 용이
- 다중 임계 영역을 지원한다.
단점 - 바쁜 대기 발생 (대기 시간 증가, 비생산적 자원 소모)
- 기아 상태 발생 : 프로세스가 임계 영역을 떠날 때 프로세스 하나 이상을 대기하는 경우 가능하다.
- 교착 상태 발생 : 우선순위가 낮은 프로세스가 lock을 풀 때, 우선 순위가 더 낮은 프로세스로 넘겨주므로, 우선순위가 높은 프로세스는 무한정 바쁜 대기상태가 될 수 있다.

세마포

앞선 상호배제 해결 방법들은 일반화가 어렵고 바쁜 대기로 인한 자원낭비가 생긴다. 이를 막기 위해 다익스트라가 세마포(semaphore)를 제안하여 해결하였다.

3.1 세마포 개념과 동작

세마포는 값이 음이 아닌 정수인 플래그 변수이다. 세마포는 흔히 열차 차단기에 비유되며,

  • 세마포값이 true면 (차단기가 내려가면), 임계 영역을 진입할 수 있고,(열차가 지나갈 수 있음)

  • 세마포값이 false면 (차단기가 올라가면), 임계 영역을 진입할 수 없다(열차가 지나갈 수 없음)

세마포는 P와 V라고 불리우는 연산과 세마포를 의미하는 정수 변수 S로 동작하며, 이를 이용해 임계 영역이나 스케줄링 제약 조건을 시행할 수 있다. 코드로 표현하자면 아래와 같다.

// 프로세스를 대기하게 하는 wait 동작, 임계 영역에 진입하는 연산
P(S) : wait(S) &#123; // 보통 S(세마포 = 1로 초기)   
    while S &#38;#60;= 0; // 바쁜 대기, S &#38;#62; 0 때까지 대기, 나중에 바쁜대기를 없앤 코드 나옴
    S--;
&#125;
// 대기 중인 프로세스를 깨우려고 신호를 보내는 signal 동작, 임계 영역에 나오는 연산
V(S) : signal(S) &#123;
    S++; // 다른 프로세스의 접근 허용
&#125;

S에 대한 P 연산은 S 값을 검사하여 양수이면 1을 감소시키는 과정이며, S에 대한 V 연산은 S를 1만큼 증가시킨다.

P와 V 연산을 종료할 때까지는 다른 프로세스가 두 연산을 수행하지 못하며, 중간에 인터럽트가 존재하면 안된다.

관례적으로 양의 값일 경우는 사용가능하다는 의미이다. 양수 n으로 초기화하면 최대 n개의 프로세스가 동시에 임계 영역을 사용할 수 있다. 즉, 세마포가 0일 때는 임계 영역이 사용을 금지 중이거나 사용 중이라는 의미이며, 음의 값은 존재하지 않는다.

세마포(아래 코드의 mutex 변수)를 공유함으로, 1개의 임계 영역에 대한 n개의 프로세스 문제도 해결할 수 있다.

do &#123;
    wait(mutex);
        // 임계 영역
    signal(mutex);
        // 나머지 영역
&#125; while(1);

세마포는 동기화하는 데 사용할 수 있으며, 예를 들어 두 프로세스가 각각 명령 $S_1, S_2$를 실행해야 하고, 반드시 명령 $S_1$ 뒤에 명령 $S_2$ 순서로 수행되어야 한다면 아래와 같은 코드를 사용하면 된다.

// 첫번째 프로세스 동작
// 세마포 synch는 0으로 초기화
S1();
signal(synch)


// 두번째 프로세스 동작
wait(synch);
S2();

위와 같은 코드를 이용한다면 두번째 프로세스가 먼저 동작하여도 wait(synch)에서 세마포어 synch값이 0으로 시작되므로 S2() 함수가 시작되지 않고 바쁜 대기 상태에 빠지며, 첫번째 프로세스의 signal(synch)이 실행된 뒤부터 진행할 수 있다.

3.2 세마포의 종류

세마포에는 계수(counting) 세마포와 이진(binary) 세마포가 있으며, 계수 세마포는 생산자-소비자 문제처럼 상호배제와 조건부 동기화를 해결하기 위해 설계 되었으며, 이진 세마포는 임계 영역처럼 특별히 상호배제를 해결하려고 설계했다.

이진 세마포

이진 세마포에서는 세마포 S를 상호배제에 사용하고, 1 또는 0으로 초기화하며, S를 검사해 양수이면 S를 0으로 재설정하거나 아니면 S를 준비큐로 되돌리는 P 연산과 S를 1로 초기화하며 준비 큐에 있는 프로세스를 시작하는 V 연산을 교대로 실행한다.

앞서 설명했던 세마포와 마찬가지로 S를 0으로 초기화했을 경우, signal() 혹은 P 연산을 먼저 시작하기 전에 사용하지 못하게 막을 수 있다.

계수 세마포

계수 세마포를 이용해 유한한 자원에 접근할 때, 여러번 자원을 획득하거나 해제할 수 있도록 count 변수를 이용한다. count는 초기의 세마포 수로 초기화한다.

즉, 이진 세마포와 달리 0과 1로 이루어져있지 않다.(그림 4-20)

각 프로세스가 자원을 사용하려면 S(count)를 감소시켜야 하며, 반대로 해제할 때는 증가시킨다. count가 0이면 사용할 수 없거나 금지된 상태이며, 공유 가능한 세마포의 수는 count의 값과 같다.

3.3 세마포의 구현

앞서 구현했었던 세마포의 단점 중 하나는 바쁜 대기이다. 이는 프로세서 시간을 낭비하며, 코드를 수정하면 극복할 수 있다.

while문 대신 프로세스를 중단하고, 준비 큐에 배치해 대기 상태로 바꾼 뒤, 재실행하는 코드를 이용하면 바쁜 대기 상태가 없는 세마포를 구현할 수 있다.

이때, 프로세스 중단 및 준비 큐 배치는 스스로 가능하지만, 프로세스 재개는 세마포를 반환하는 프로세스가 signal 연산을 실행해줘야한다. 이를 코드로 구현하면 다음과 같다.

struct semaphore &#123; 
    int count; // 사용 가능한 세마포어의 
    queueType queue; // 해당 세마포어를 기다리는 프로세스들의 준비 큐
&#125;;
semaphore S; 

//wait 연산(=P 연산) 구현
wait(S) &#123;
    S -&#38;#62; count--;
    if (S-&#38;#62; count &#38;#60;0)&#123;
        add this process to S -&#38;#62; queue;  // 프로세스를 준비 큐에 추가
        block();                         // 프로세스 중단(일시정지)
    &#125;
&#125;

//signal 연산(=V 연산) 구현
signal(S) &#123;
    S -&#38;#62; count++;
    if (S-&#38;#62; count &#38;#60;= 0) &#123;
        remove a process P from S -&#38;#62; queue;// 준비 큐에서 P 프로세스를 제거
        wakeup(P);                         // 신호를 보내 프로세스를 실행
    &#125;
&#125;

wait() 연산을 실행하게 되면, 세마포의 S 값이 줄어들며, 만약 사용 불가였으면 프로세스가 중단된다.

따라서 특이하게, 기존의 바쁜 대기 세마포와 달리 개선된 세마포의 S->count 값이 음수가 될 수 있으며, 음수의 값을 통해 세마포에서 기다리는 프로세스 수를 의미한다.

실제 프로세스 준비 큐는 프로세스 제어 블록(PCB)의 링크 필드 정보를 이용해 구현한다.

또한 세마포의 연산들은 중간에 끼어들 수 없도록 원자적으로 수행되어야 한다. 이를 해결하기 위해 두 가지 방법을 이용할 수 있다.

  • 단일 프로세서 환경에서는 wait와 signal 연산 수행 중에 인터럽트를 금지시킨다.

  • 다중 프로세서 환경에서 모든 프로세서의 인터럽트를 금지시키면 성능이 크게 떨어지므로, 바쁜 대기 현상을 완전히 제거할 수 없으며, 응용 프로그램 진입 영역에서 임계 영역까지 바쁜 대기를 제거한다. 만약 응용 프로그램의 임계 영역이 너무 길면 성능이 매우 떨어질 수 있다.

다만 이렇게 구현한 세마포는 프로세스 하나가 한 세마포의 준비 큐에만 대기할 수 있으므로, 두 프로세스가 자원을 하나씩 점유하고 상대방이 점유한 자원을 대기하는 교착상태를 유발할 수 있다.

모니터(monitor)

세마포는 강력한 상호배제 도구지만, wait 연산과 signal 연산의 순서를 엄격하게 제한해서 실행해야 교착상태가 발생하지 않는다.

하지만 이러한 연산은 프로그램 전체에 퍼져있고, 복잡하기 때문에 세마포를 잘못쓰면 오류가 많이 생겨나게 되므로, 이를 보완하기 위해 모니터가 등장했다.

모니터의 개념과 구조

모니터는 공유 자원과 이것의 임계 영역을 관리하는 소프트웨어 구성체로, 사용자 사이에서 통신하려고 동기화하고, 자원에 배타적으로 접근할 수 있도록 프로세스가 사용하는 병행 프로그래밍 구조이다.

모니터는 공유 데이터, 임계 영역이 코딩된 프로시저, 초기화 코드로 구성되어 있다. 데이터 정의와 프로시저의 독점적 제어가 모두 포함되어 있다.

  • 초기화 코드 : 모니터 생성시 이용하는 코드

  • 공유 데이터 변수 : 모니터 내부의 프로시저로 접근 가능한 임계 자원

  • 프로시저 : 동시에 한 프로세스만 접근 가능한 임계 영역이 코딩된 프로시저

프로시저를 점유 중일 때, 접근에 실패한 다른 프로세스들은 차단된 뒤, 준비 큐에서 진입을 기다리게 하여 상호배제를 실현한다. 덕분에 동기화 제약 조건을 명시적으로 작성할 필요가 없어, 상대적으로 제어하기 더욱 쉽다.

조건 변수가 있는 모니터의 구조

모니터의 동기화 방법은 프로세스 특성에 따라 직접 추가해줘야 한다. 예를 들어, 생산자-소비자 프로세스는 공유 버퍼가 비어 있거나 가득차 있으면 프로세스를 대기시켜야 한다.

이렇게 프로세스가 대기해야할 조건에 대한 변수를 조건변수라고 한다.

조건 변수는 보통 하나 이상이며 조건변수 x, y는 모니터 안에 공유 데이터 변수와 별개의 영역에 연관된 큐와 함께 놓인다.

  • 조건변수가 하나 이상이면 마찬가지로 하나 이상의 프로세스가 모니터 내부에 존재하게 할 수 있으며, 준비 큐도 하나 이상일 수 있다.

  • 보통 준비 큐는 선입 선출 큐를 이용하지만 이 또한 다양한 스케줄링 알고리즘으로 대체할 수 있다.

x.wait 연산은 특정 조건이 true이면 프로세스의 실행을 중단 혹은 차단한다.

특정 조건이 false 이고, 어떤 프로세스가 x.signal 연산을 호출하면 프로세스 준비 큐에 중단되어 있던 다른 프로세스의 실행을 재개한다.

✨ 왜 굳이 조건이 바뀌면 실행하지 않고 다른 프로세스의 x.signal 연산을 기다리는가?

준비 큐 내의 프로세스, 혹은 모니터가 특정 조건이 false가 되는 순간을 감시하게 만들면, 바쁜 대기가 일어날 것이다.

따라서, 점유하고 있던 프로세스가 준비 큐 내의 프로세스를 깨우는 x.signal 연산을 기다리게 하는 것이다.

점유 중인 프로세스 P가 대기 중인 프로세스 Q에 모니터를 넘긴 후, 즉 P가 signal() 연산을 한 후에 프로세스 P는 대기해야 하는데, 두 가지 동작의 방법이 존재한다.

✨ 왜 P는 Q를 대기해야 하는가?

프로세스의 작업이 끝나지 않았기 때문이다. P의 작업이 끝나지 않았음에도 Q에게 프로세스를 넘기는 이유는 시분할에 의한 할당량 종료, 입출력 대기, 사용자의 요청, 조건변수의 변화 등 다양하며, 이는 작업이 완전 끝나고 넘기는 경우(=대기할 필요가 없는 경우)보다 빈도가 잦다.

  • 점유 중인 프로세스 P가 대기 중인 프로세스 Q에게 모니터를 넘긴 후, Q가 모니터를 떠나거나(준비 큐로 돌아가거나) 다른 조건으로 변할 때까지(Q 또한 모니터를 넘기는(signal()) 대신 이전에 wait()을 부를 수 있다.) 대기한다. (즉, 프로세스 P가 즉시 멈추고 준비큐로 돌아가는 것?)

  • 대기 중이던 프로세스 Q가 점유 중이던 프로세스 P가 모니터를 떠나거나(준비 큐로 돌아가거나) 다른 조건으로 변할 때까지 대기한다. (즉, 프로세스 P가 signal() 이후 계속 모니터를 점유하는것?)

둘다 장단점이 있으며, 이 둘을 절충한, x.signal 연산을 보낸 점유가 끝난 프로세스 P는 모니터에 즉시 나가는 방법도 존재한다.

모니터와 세마포 비교

모니터의 조건 변수 x에 대해 x.wait와 x.signal 연산은 세마포의 P와 V 연산과 비슷하지만 차이점 두 가지를 가지고 있는데,

  • 세마포의 P 연산은 언제나 차단시키지 않고 세마포가 0보다 클 경우, 자원이 충분하므로 대기하지 않고 실행되지만, x.wait 연산은 반드시 차단시킨다.

  • 세마포의 V 연산은 무조건 세마포의 크기를 증가시키고, 대기 작업을 확인해 넘겨주지만 x.signal은 대기중인 작업이 없으면 아무런 효과가 없다, 즉 조건변수 x(보통은 호출 가능한 자원의 수)에 영향을 주지 않는다.

또한, 세마포는 세마포의 크기가 V 연산으로 인해 커지면 즉시 다음 프로세스가 실행되지만, 모니터는 조건 변수 x가 충족이 되어도 점유 중이던 프로세스가 x.signal을 명시적으로 실행해야 다음 프로세스가 실행되므로, 병렬 프로그래밍에서 오류가 적고 쉽게 작성 가능하다.

하지만 모니터는 프로그래밍 언어로 구현하는 부분이 필요하며, 컴파일러가 관여하므로, 컴파일러가 운영체제의 임계 영역에 접근할 수 있어야 하므로, 자바, C# 같은 일부 언어만 지원한다.

  모니터 세마포
모니터 x.wait VS 세마포 P 조건변수 x와 관계없이 무조건 프로세스 대기 P연산 중이여도, 세마포가 0보다 크면 프로세스 실행됨
모니터 x.signal VS 세마포 V 대기 중인 프로세스가 없으면 조건 변수 x에 변동 없음 대기중인 프로세스가 없어도 세마포의 수가 증가

세마포를 이용한 모니터의 구현

모니터마다 1로 초기화된 세마포 mutex를 사용하며, 포르세스는 진입하기전 P(mutex) 혹은 wait(mutex) 연산을 실행해야하며, 모니터를 떠나려면 V(mutex) 혹은 signal(mutex)로 양도해야한다.

signal을 보내는 프로세스는 재개된 프로세스가 떠나거나 대기(wait)할 때까지 기다려야 하므로 next라는 이진 세마포를 생성하고 0으로 초기화한다. (세마포가 0이면 사용불가 혹은 대기 상태임을 상기하자.)

semaphore mutex; // 1로 초기화
semaphore next; // 0으로 초기화
int next_count = 0;
// 프로세스 외부 프로시저
wait(mutex); // mutex 세마포어가 1이면 진입, 0이면 대기
    ...
    // 프로시저(F)의 작업영역
    ...
if (next_count &#38;#62; 0) // next_count == 중단된 프로세스 수
    signal(next); //이진 세마포의 값을 1로 만들어 다음 프로세스에게 넘김
else
    signal(mutex);

조건 변수 x에서 초기값이 0인 세마포 x_sem과 정수 변수 x_count를 사용하여 아래와 같이 x.wait와 x.signal 연산을 구현할 수 있다.

semaphore x_sem; // 0으로 초기화
int x_count = 0; // 조건 x의 준비 큐에서 기다리는 프로세스의 수

//x.wait 연산
x_count++;
if (next_count &#38;#62; 0)
    signal(next);
else
    signal(mutex);
wait(x_sem);
x_count--;


//x.signal 연산
if (x_count &#38;#62; 0) &#123;
    next_count++;
    signal(x_sem);
    wait(next);
    next_count--;
&#125;

중단된 프로세스 중에 고르는 것은 선입 선출로도 가능하지만, 조건 대기 구조나 우선순위 큐, 우선순위 번호를 명시해주는 방식으로도 가능하다.

x.wait(c); // 우선순위 번호 할당, 
// x.signal 연산 시 c 값이 가장 작은 우선순위를 가진 프로세스를 실행

아래는 단일 자원 할당 모니터의 예시이다.

monitor resource_allocator &#123;
    condition_is_free;
    int in_use = 0; // 0일 경우 자원이 사용가능한 상태

    get_resource() &#123;
        if (in_use) // 만약, 자원이 사용 중이면
            wait(is_free); // 프로세스 중단(일시정지)
        in_use=1; // 자원이 사용중임을 표시
    &#125;

    return_resource() &#123;
        in_use = 0; // 자원 사용 가능하게 변경
        signal(is_free);   // 대기 중인 프로세스에 할당 허용(신호)   
    &#125;
&#125;