[운영체제/OS] 4. 병행성: 상호 배제와 동기화 Concurrency: Mutual exclusion and Synchronization (1)

✍︎ 운영체제 내부구조 및 설계원리 제8판 (Operating Systems Internals and Design Principles) 을 정리하는 글입니다.

💪 이 장의 목적

• 경쟁 상태, 운영체제 고려 사항, 상호 배제 요구 조건 등과 같은 병행성 관련 개념들을 이해할 수 있다.
• 상호배제를 지원하기 위한 하드웨어 수준 접근 방법을 설명할 수 있다.
• 세마포어를 정의하고, 동작 방식을 설명할 수 있다.
• 모니터를 정의하고, 동작 방식을 설명할 수 있다.
• 판독자/기록자 문제를 설명할 수 있다.

인덱스

1. 병행성(Concurrency)이란?

   • 필요성
   • 관련 주요 용어 정리
   • 원리
   • 경쟁 상태
   • 운영체제가 병행성 때문에 고려해야할 사항들
   • 프로세스간 상호작용 방법

2. 상호 배제

   • 요구 조건
   • 요구 조건을 만족시키는 접근 방법들
   • 소프트웨어적 접근 방법
   • 하드웨어적 접근 방법
3. 결론

병행성(Concurrency)이란?

필요성

멀티프로그래밍, 멀티프로세싱, 분산처리 등의 설계의 핵심은 병행성이다.

* 멀티프로그래밍: 단일 처리기 시스템에서 다수 프로세스 관리
* 멀티프로세싱: 멀티 프로세서 시스템에서 다수 프로세스 관리
* 분산처리: 분산된 시스템에서 수행되는 다수의 프로세스 관리 예) Cluster System

{프로세스 사이의 통신, 프로세스 활동들의 동기화, 자원에 대한 공유와 경쟁, 프로세스에 대한 처리기 시간 할당 등의 이슈} ⊂ 병행성

📍병행성 VS 병렬 처리

• 병행성은 프로세스를 인터리빙(interleaving, 번갈아가며 수행되지만 사용자들은 동시에 실행되는 것처럼 느낌) 한다.
• 병렬 처리(parallel processing)는 실제로 여러개의 cpu가 동시에 프로세스를 처리하는 것을 의미한다.

관련 주요 용어 정리

원자적 연산 Atomic operation

• 하나 또는 여러 개의 명령어들로 구성된 함수 또는 액션으로 더 이상 분할할 수 없는 단위. 따라서 어떤 프로세스들도 중간 상태를 볼 수 없으며 연산 중단이 불가하다.
• 명령어들은 모두 수행되거나 모두 수행되지 않아야 한다.
• 원자성은 병행 프로세스들에게 고립(isolation)을 보장한다.

임계영역 Critical section

• 공유 자원에 접근하는 (프로세스 내부의) 코드 영역
• 프로세스 내부의 코드 영역이 공유 자원에 접근한다면 해당 코드 영역을 임계 영역이라고 칭한다. 만약 어떤 프로세스가 임계 영역에서 작업 중이라면, 즉 공유 자원을 이용하고 있다면 다른 프로세스는 임계 영역에 접근이 불가하다.

교착 상태 Deadlock

• 각 프로세스가 다른 프로세스의 진행을 기다리면서 대기하고 있을 때 발생
• 두 개 이상의 프로세스들이 더 이상 진행을 할 수 없는 상태

라이브락 Livelock

• 두 개 이상의 프로세스들이 다른 프로세스의 상태 변화에 따라 자신의 상태를 변화시키는 작업만 하고 있는 상태
• 수행은 하고 있지만 실제로 수행하는 작업은 유용한 작업이 아니다.

상호배제 Mutual exclusion

• 한 프로세스가 공유자원에 접근하는 임계영역 코드를 수행 중이면, 다른 프로세스들은 자신들의 임계 영역 코드 수행 불가

경쟁 상태 Race condition

• 두 개 이상의 프로세스가 동시에 공유 자원에 접근하려는 상태
• 최종 수행 결과는 프로세스들의 상대적인 수행 순서에 따라 달라질 수 있다.

기아 Starvation

• 특정 프로세스가 수행 가능 상태임에도 불구하고, 매우 오랜 시간동안 스케줄링 되지 못한 경우

원리

단일 처리기 멀티 프로그래밍 시스템에서 프로세스들은 인터리빙(interleaving)된다. 인터리빙은 실제로 병렬 처리를 하는 것도 아니고, 프로새스 교환시 문맥 교환 비용이 발생하지만 시스템 처리 효율과 구조적 프로그래밍에 큰 장점을 제공한다.

멀티 프로세서 시스템은 인터리빙과 함께 오버래핑(overlapping)도 지원한다. 인터리빙과 오버래핑, 두 기법 모두 병행 처리의 예이며 동일한 문제를 야기한다.

단일 처리기 시스템과 멀티 프로세서 시스템에서 발생하는 문제의 본질은 “프로세스들의 수행 상대 속도를 예측할 수 없다”는 특징으로부터 기인한다. 수행 속도는 OS의 스케줄링 정책, 다른 프로세스들의 활동, OS의 인터럽트 처리 방법에 의해 영향을 받아 동적으로 변한다. 이로 인해 프로그램 개발 시 다음과 같은 어려움들이 발생한다.

1. 전역 자원의 공유가 어려워짐

void echo(){
    chin = getchar();
    chout = chin;
    putchar(chout);
}

👉 단일 처리기 기반 멀티프로그래밍 시스템이라고 가정했을 때,

echo()함수를 전역 메모리 공간에 적재하는 경우, 한 개의 함수 이미지가 메모리에 존재하도록 하여 공간을 절약할 수 있다. 즉, 프로세스간 메모리 공유는 공간 절약 측면에서 효율성을 높이고 프로세스간 긴밀한 상호작용을 가능하게 한다는 장점이 있지만 이로 인해 몇 가지 문제가 야기될 수 있다.

• 문제 상황

  1. 프로세스 P1의 echo() 함수 호출로 인해 getchar()가 호출된다. 사용자가 ‘x’를 입력하고 이 값이 chin에 저장되는 동안 OS는 P1을 선점하고 P2를 수행하기로 결정했다.
  2. P2가 활성화되어 echo()함수를 호출했고 1번과 같은 절차로 chin에 ‘y’가 저장된 후 출력된다.
  3. 이후 P1 수행이 재개될 때 ‘x’가 유실되었기 때문에 ‘y’가 다시 한 번 출력된다.

이 문제는 전역변수 chin을 두 개 이상의 프로세스가 공유하기 때문에 발생한다.
∴ 한 시점에 오직 한 프로세스만이 그 함수 내부에 존재하도록 해야 한다.

• 해결 상황

  1. 프로세스 P1의 echo() 함수 호출로 인해 getchar()가 호출된다. 사용자가 ‘x’를 입력하고 이 값이 chin에 저장되는 동안 OS는 P1을 선점하고 P2를 수행하기로 결정했다.
  2. P2가 활성화되어 echo()를 호출하지만 아직 P1이 echo() 함수 내에 있기 때문에 P2는 echo()함수 내부로 진입할 수 없다. P2는 echo()함수 사용이 가능할 때까지 일시 중지된다.
  3. P1 수행이 재개되면 ‘x’가 출력된다.
  4. P2는 P1이 echo()함수 내부에서 나왔을 때 수행이 재개되고 사용자가 ‘y’를 입력하면 ‘y’가 출력된다.

👍 위의 예시 상황을 통해 전역 변수를 공유(또는 자원을 공유)할 때 문제가 발생할 수 있고, 이를 막기 위해서는 전역변수를 보호해야함을 알았다. 이때 전역변수를 보호하는 유일한 방법은 공유자원에 접근하는 프로그램의 코드 부분을 제어하는 것이다.

👆위의 문제는 멀티 프로세서 시스템에서도 동일하게 발생되어 공유 자원 보호의 필요성을 보여준다. 이 경우에도 동일한 방법을 이용하여 해결할 수 있다.

2. 최적의 자원 할당(by 운영체제)의 어려움 증가

ex) 프로세스 A가 특정 입출력 자원을 할당받은 채로 block 또는 일시 중지된다면 다른 프로세스들도 해당 입출력 자원 사용 불가. 즉, 가용 자원이 실행 순서에 따라 사용될 수 없는 상황 발생. -> 이 경우가 악화되면 교착 상태 발생 가능

3. 디버깅 어려움 증가

경쟁 상태

다수의 프로세스나 쓰레드가 공유자원을 동시에 읽거나 쓰려고 하는 상태를 경쟁 상태(race condition)라고 한다. 경쟁 상태가 발생하면 최종 수행 결과는 프로세스의 수행 순서에 따라 달라진다.

• 예시 1)
  전역변수 a를 프로세스 P1, P2가 공유한다. P1은 a=1, P2는 a=2로 수정하려 하는데 이는 경쟁 상태로 볼 수 있다. 경쟁에서 져서 마지막으로 a에 접근한 프로세스의 수정결과가 a에 최종적으로 저장된다.
• 예시 2) b=1, c=2로 초기화된 전역 변수를 공유하는 P3와 P4를 가정해보자. P3은 b = b+c연산을, P4는 c = c+b연산을 수행할 때, 이 연산들의 결과 또한 수행 순서에 따라 결정된다.

운영체제가 병행성 때문에 고려해야할 사항들

1. OS는 모든 프로세스들의 상태와 수행 위치를 추적할 수 있어야 한다. - 이는 PCB를 통해 구현된다.
2. OS는 활동 중인 각 프로세스에 다양한 자원들(처리기 시간, 메모리, 파일, I/O장치)을 할당하고 해제할 수 있어야 한다.
3. 운영체제는 각 프로세스에 할당된 자원과 데이터들을 다른 프로세스들의 예기치 못한 간섭으로부터 보호해야한다.
4. 프로세스의 기능과 수행결과는 프로세스의 수행 속도 및 동시에 수행되는 다른 프로세스들의 상대적인 수행 속도와 독립적이어야 한다.

프로세스간 상호작용 방법

분류 기준: 프로세스가 다른 프로세스들의 존재를 어떤 수준으로 인식하고 있는가

📕 유형 1 “서로를 인식하지 못하는 프로세스들”사이의 상호 작용

협동 작업을 하지 않는 서로 독립적인 프로세스들 ex) 멀티 프로그래밍 환경

🖇 경쟁(자원에 대한 프로세스 사이의 경쟁) Competition

• 프로세스가 동일한 자원에 동시에 접근하려는 경우 발생
• 프로세스는 다른 프로세스의 존재를 모른다.
• 각 프로세스는 사용한 자원(입출력장치, 메모리, 처리기 시간, 클록 등)의 상태를 변화시켜서는 안된다.

• 경쟁 관계에 있는 프로세스들이 존재할 경우 발생하는 제어 문제들

  • 상호 배제: 한 시점에 단 하나의 프로세스만 임계 영역에 들어갈 수 있다. 상호배제 보장은 교착상태와 기아라는 제어 문제를 발생시킨다. 프로그래머에 의해 아래와 같이 직접 작성된다.

    void P1{
        while (true){
            //임계영역 이전 코드
            entercritical(Ra);
            //임계영역
            exitcritical(Ra);
            //임계영역 이후코드
        }
    }
    void P2{
        while (true){
            //임계영역 이전 코드
            entercritical(Ra);
            //임계영역
            exitcritical(Ra);
            //임계영역 이후코드
        }
    }
    ...
    void Pn{
        while (true){
            //임계영역 이전 코드
            entercritical(Ra);
            //임계영역
            exitcritical(Ra);
            //임계영역 이후코드
        }
    }

  • 교착 상태: 각 프로세스들은 자신이 할당받은 자원 이외의 자원을 할당 받기 위해 기다리지만, 기다리기만 할 뿐 자신의 자원은 반납하지 않음 -> 대기, 수행 X == 교착 상태
    
  • 기아: 교착 상태는 아니지만 특정 프로세스가 오랜 기간 동안 자원 사용이 불가한 상태
    

📗 유형 2 “서로를 간접적으로 인식하고 있는 프로세스들”사이의 상호 작용

다른 프로세스들의 이름(식별자, ID)을 알지는 않지만 자원을 공유하는 프로세스

🖇 공유를 이용한 프로세스간 협력 Cooperation

• 간접적인 협력

  • 프로세스들은 서로를 명시적으로 알지 못하지만 서로 상호작용을 한다. 예) 다수의 프로세스들이 공유 변수/파일/데이터베이스에 접근하는 것
  • 서로 상호작용을 하며 데이터가 읽히거나 갱신되는데, 이때 데이터가 적절하게 관리될 수 있도록 프로세스들이 협력한다.
• 즉, 협력을 위한 제어 기법을 통해 공유 데이터의 무결성(integrity) 보장 가능

• 이 관계에 있는 프로세스들이 존재하는 경우 발생하는 제어 문제

  • 상호 배제: 읽기/쓰기 연산 중 쓰기 연산인 경우에만 발생한다.
  • 경쟁 관계와 동일하게, 상호 배제 보장으로 인해 교착 상태와 기아 문제가 발생한다.

  • Data 일관성 유지

    P1은 a = a+1;//1 b = b+1;//2 이고
    P2는 b = 2*b;//3 a = 2*a;//4 일 때,

    프로세스들이 동시에 수행된다면, 상호배제 조건이 지켜지더라도 일관성이 깨질 수 있다.
    예) 실행 순서가 1-3-2-4일 때

    이 예시를 통해, 상호배제 보장 시에는 각 공유자원에 접근하는 코드(프로그램 부분)를 개별 임계 영역으로 정의하는 것이 아니라, 연관된 공유 자원에 접근하는 프로그램 부분 전체를 단일 임계영역으로 정의해야 한다는 것을 알 수 있다.

    경쟁 제어 시 사용하는 entercritical()/exitcritical() 사용 가능하다

📘 유형 3 “서로를 직접적으로 인식하고 있는 프로세스들”사이의 상호 작용

다른 프로세스들의 이름(식별자, ID)을 알고, 이를 이용해 직접 통신하는 프로세스들. 공통된 작업을 함께 수행하기 위해 설계되었음.

🖇 통신을 이용한 프로세스간 협력 Cooperation

• 모든 프로세스들이 공통의 목표를 위해 연결되어있고, 이때 통신은 프로세스간 동기화 & 협력 & 다양한 공통 행위를 수행할 때 사용된다.
• 통신은 특정 유형의 메세지로 구성되어 있다. ∴ 프로그래밍 언어/OS는 메세지 송수신 가능한 primitive를 제공한다
• 상호 배제 X ∵ 메세지 송수신 시, 프로세스들 사이에 실제로 공유되는 것은 없기 때문이다.

• 이 관계에 있는 프로세스들이 존재하는 경우 발생하는 제어 문제

  • 기아: 예) P1, P2, P3 중 두 개 프로세스만 통신하고 나머지는 장시간동안 수신 대기 상태일 수 있다.
  • 교착 상태: 예) 두 개의 프로세스가 서로의 메세지를 기다리며 블록됨

상호 배제

요구 조건

1. 상호 배제 강제 - 반드시 단 하나의 프로세스만 임계 영역에 접근 가능
2. 임계 영역이 아닌 곳에서 수행 중지된 프로세스는 다른 프로세스 수행 간섭 불가
3. 임계 영역에 접근하려고 하는 프로세스에게 교착 상태 및 기아 문제가 발생하면 안됨
4. 임계 영역에 접근 중인 프로세스가 하나도 없을 때 영역에 진입하려하는 프로세스는 즉시 진입 가능
5. 프로세서 개수, 상대적인 프로세스 수행 속도를 예측할 수 없음
6. 임계 영역에 들어간 프로세스는 일정 시간 후에 임계 영역 밖으로 나와야 함

요구 조건을 만족시키는 접근 방법들

• 소프트웨어적 방법 병행 수행하는 프로세스들이 모든 책임 및 권한을 갖는 방법
  여기에서 더 알아보기
• 하드웨어적 방법 특별 용도로 설계된 기계어 이용
  여기에서 더 알아보기
• OS나 프로그래밍 언어 수준에서 보장하는 방법
  여기에서 더 알아보기

상호 배제를 보장하기 위한 소프트웨어적 접근 방법

운영체제나 프로그래밍 언어 차원의 지원 없이 프로세스간 협력을 통해 직접 상호 배제를 보장한다.
수행 부하가 크고, 잘 설계 되지 않았을 경우 오동작 가능성이 높다. 하지만 이 방법을 앎으로써 병행 처리의 복잡도와 상호 배제 윤리를 잘 이해할 수 있다.

상호 배제를 보장하기 위한 하드웨어적 접근 방법

🗝 인터럽트 금지 Interrupt Disable

상호 배제를 보장할 수 있는 가장 간단한 방법은 프로세스가 인터럽트 되지 않도록 하는 것이다.
∵ 단일 처리기에서 병행 처리(concurrent processing)되는 프로세스들은 인터리빙(interleaving)되기 때문이다. 또한 프로세스는 운영체제 서비스를 호출하거나 인터럽트가 될 때까지 계속 실행하기 때문에 인터럽트가 발생하지 않으면 한 프로세스의 지속적인 실행을 보장 가능

이를 위해 시스템 커널에서 인터럽트를 허용하거나 비허용할 수 있는 기본 인터페이스를 제공한다.

while(true){
    // 인터럽트 금지
    // 임계 영역
    // 인터럽트 허용
    // 임계 영역 이후 코드
}

단점

• 부하가 크다
  ∵ 인터럽트 비허용 시, 그 사이 외부에서 발생하는 이벤트에 대한 처리와 다른 프로세스에 대한 스케줄링 등 모든 기능이 중지되어 시스템 수행 효율이 확연하게 감소할 가능성 높음
• 멀티프로세서 시스템에서는 올바른 접근 방법이 아니다
  두 개 이상의 프로세스를 가지는 시스템에서는 인터럽트가 금지되어도 서로 다른 프로세스가 공유 자원을 동시에 접근할 수 있음. 즉, 보장 못함.

🗝 특별한 기계 명령어

멀티 프로세서 환경에서 여러 처리기들은 공통의 주기억 장치를 공유하며, 이때 모든 처리기는 동등한 관계에서 독립적으로 동작한다.
∴ 인터럽트 기법으로 상호 배제 보장 불가

하드웨어 수준에서 특정 메모리 주소가 접근되고 있을 때, 같은 위치에 대한 접근 요청은 차단된다는 것에 기반해 상호 배제를 보장하기 위한 두 가지 명령어가 구현된다. 이때 기계 명령어는 두 개의 기능을 원자적으로 처리한다.

원자적: 명령어 수행 도중 인터럽트 되지 않고 마치 하나의 단위인 것처럼 처리될 수 있다.

1. Compare & Swap 명령어
   compare_and_swap(): 테스트 하려는 값과 저장된 값을 비교한다.

   int compare_and_swap(int *word, int testval, int newval){
       int oldval;
       oldval = *word;
       if(oldval == testval) *word = newval;
       return oldval;
   }

   이 함수는 원자적으로 수행되기 때문에 중간에 중단되는 경우는 없다.
   대부분 모든 처리기에서 지원하며, 대부분의 OS에서 병행성을 위해 이 명령어를 사용한다.

   • Compare & Swap 명령어를 이용한 상호 배제 보장

     const int n = /*프로세스 개수*/;
     int bolt;
     void P(int i){
         while(true){
             while(compare_and_swap(bolt, 0, 1) == 1){ // 제일 처음 진입한 프로세스가 bolt를 1로 변경한 뒤
                 /*대기*/;
             }
             /*임계영역*/; // 임계영역에서 수행, 이때 진입을 하려는 프로세스들은 bolt가 1이기 때문에 위의 while문에서 대기해야한다.
             bolt = 0; // 수행이 끝나면 bolt를 0으로 바꾸고 임계영역을 나간다.
             /*임계영역 이후의 코드*/;
         }
     }
     void main(){
         bolt = 0;
         parbegin(P(1), P(2), ... , P(n));
     }

2. Exchange 명령어 exchange(): 레지스터 값과 메모리에 들어있던 값을 서로 교체하는 기능 수행

   void exchange(int *register, int *memory){
       int temp;
       temp = *memory;
       *memory = *register;
       *register = temp;
   }

   • Exchange 명령어를 이용한 상호 배제 보장

     int const n = /*프로세스 개수*/;
     int bolt;
     void P(int i){
         while(true){
             int keyi = 1;
             do exchange(&keyi, &bolt)
             while(keyi != 0);
             /*임계영역*/;
             bolt = 0;
             /*임계영역 이후의 코드*/;
         }
     }
     void main(){
         bolt = 0;
         parbegin(P(1), P(2), ... , P(n));
     }

   key는 1, bolt는 0일 때 exchange를 수행하면 key는 0, bolt는 1로 바뀐다. 임계영역에 진입해 있는 프로세스가 있는 경우, 새로 진입하려는 프로세스가 exchange(&keyi, &bolt)를 수행하고자 하면 수행 결과 key는 1, bolt는 0이 되어 계속 do while문을 돌게 된다. 진입했던 프로세스가 임계영역에서 빠져나올 때 bolt를 0으로 바꾸고 나서야 새로운 프로세스가 다시 임계영역에 진입가능하다.

기계 명령어 접근 방법의 특성

• 장점

  • 단일처리기 시스템 뿐만 아니라 공유 메모리를 사용하는 멀티 프로세서 시스템에서도 적용/사용 가능
  • 간단하고 검증이 쉽다.
  • 서로 다른 변수를 사용할 시, 여러 개의 임계영역 지원 가능

• 단점

  • 바쁜 대기 사용 ⇢ 임계영역에 진입하고자 하는 프로세스가 처리기를 계속 사용해야 함.
  • 기아 발생 가능 ⇢ 한 프로세스가 임계영역에서 빠져나올 때, 대기하고 있던 다수의 프로세스 중 하나만 다시 임계영역에 진입가능한데, 이 때 각 프로세스의 특성이나 대기시간을 고려하지 않기 때문에 기아 발생의 위험성이 있다.

  • 교착 상태 빠질 수 있음 ⇢ 가능한 시나리오

    1. P1이 임계영역 진입
    2. P1보다 우선순위가 높은 P2가 생성된 후 스케줄링되어 P2가 P1과 같은 자원에 접근을 시도하지만 상호 배제 때문에 실패하여 바쁜 대기 수행
    3. 이후 P1은 다시 스케줄링 될 수 없다. ∵ P2가 실행상태에 있기 때문이다.

결론

소프트웨어적 방법과 하드웨어적 방법은 모두 단점을 갖고 있기 때문에 새로운 해결책(운영체제, 프로그래밍 언어 수준에서 상호 배제를 보장하는 방법)이 필요하다.