Better Jeong

Better Jeong

Vision Software Engineer

Posted:      Updated:

운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.

동기화 도구들

프로세스가 공유하는 데이터 관련 문제

협력적인 순차적 프로세스 또는 스레드로 구성된 시스템에서 서로 비동기적으로 수행하면서 데이터를 공유할 수 있다.
유한 버퍼를 사용할 때, 생산자와 소비자의 실행이 분리되어 병행하게 실행되면 공유 데이터에 문제가 생길 수 있다.
동시에 여러 개의 프로세스가 동일한 자료를 접근해 조작하고, 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.
경쟁 상황으로부터 보호하기 위해 어떤 형태로든 프로세스들이 동기화되도록 해야 한다.

임계구역 문제

각 프로세스는 임계구역(critical section)이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다.
임계구역 문제란 프로세스들이 데이터 공유 시 자신들의 활동을 동기화할 때 사용하는 프로토콜을 설계하는 것이다.

프로세스들이 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 하며, 이 요청을 구현하는 코드 부분을 진입 구역(entry section)이라고 한다.
임계 구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있다.
나머지 코드 부분은 나머지 구역(remainder section)이라고 한다.

임계구역 문제 해결안

  1. 상호 배제(mutual exclusion): 프로세스 $P_i$가 자신의 임계구역 실행 시 다른 프로세스들은 자신의 임계구역에서 실행될 수 없다.
  2. 진행(progress): 자신의 임계구역에서 실행되는 프로세스가 없고, 자신의 임계구역으로 진입하려는 프로세스가 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 임계구역으로 진입할 수 있는지 결정하는 데 참여한다. (무한정 연기될 수 없음)
  3. 한정된 대기(bounded waiting): 프로세스가 자신의 임계구역에 진입하려는 요청을 한 후 허용될 때까지 다른 프로세스들이 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

임의의 한순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화된다면 커널 코드에서 경쟁 조건이 발생하기 쉽다.
시스템의 모든 열린 파일 리스트를 유지하는 커널 자료구조, pid를 배정하는 상황, 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 유지하는 자료구조, 인터럽트 처리를 위한 자료구조 등에서 발생할 수 있다.

단일 코어 환경에서는 공유 변수를 수정하는 동안 인터럽트 발생을 막음으로써 해결할 수 있지만, 다중 처리기 환경에서는 사용하기 어렵다.

운영체제 내 임계구역을 다루기 위해 선점형 커널과 비선점형 커널의 일반적인 접근법을 사용한다.

비선점형 커널은 커널 모드 프로세스의 선점을 허용하지 않고 커널을 빠져나가거나 봉쇄되거나 자발적으로 CPU 제어를 양보할 때까지 계속 수행된다.
비선점형에서는 한순간에 커널 안에서 실행되는 프로세스는 하나밖에 없으므로 경쟁 조건을 염려하지 않아도 된다.

선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점하는 것을 허용한다.
이때 공유되는 커널 자료구조에서 경쟁 조건이 발생하지 않는다는 것을 보장하도록 설계해야 한다.
선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 적당하다.

Peterson의 해결안

Peterson의 해결안은 임계구역에 대한 고전적인 소프트웨어 기반 해결책이다.

임계구역과 나머지 구역을 번갈아가며 실행하는 두 개의 프로세스로 한정했을 때, 두 개의 데이터 항목을 공유하도록 하여 해결한다.
변수 turn 에 임계구역으로 진입할 프로세스를 지정한다.
flag 배열에 각 프로세스가 임계구역으로 진입할 준비가 되었는지 나타낸다.

$P_i$ 가 임계구역에 진입할 준비가 되어 flag[i] 를 참으로 만들었을 때, turn 을 j 로 지정한다면 프로세스 j 가 임계구역 진입을 원할 때 임계구역에 진입할 수 있다.
두 프로세스가 동시에 진입을 원하더라도 turn 에는 오직 한 가지의 값만 배정된다.

현대 컴퓨터 구조에서는 올바르게 실행된다고 보장할 수 없다.
시스템 성능 향상을 위해 프로세서, 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문이다.
데이터를 공유하는 다중 스레드 응용 프로그램의 경우 명령 순서가 바뀌면 데이터의 일관성이 깨지거나 예기치 못한 결과를 낳을 수 있다.

동기화를 위한 하드웨어 지원

메모리 장벽(Memory Barriers)

메모리 모델은 컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식이다.
일반적으로 메모리 모델은 메모리 변경 결과가 다른 모든 프로세서에 즉시 보이는 강한 순서, 즉시 보이지 않는 약한 순서의 범주 중 하나에 속한다.

메모리 모델은 프로세서 유형에 따라 달라서 커널 개발자는 메모리 변경의 가시성에 대해 가정할 수 없다.
따라서 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공해서 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이도록 보장한다.
이러한 명령어를 메모리 장벽 또는 메모리 펜스(memory fences)라고 한다.

메모리 장벽 명령어가 실행될 때, 시스템은 후속 적재 또는 저장 연산이 수행되기 전에 모든 적재 및 저장이 완료되도록 한다.
따라서 명령이 재정렬되어도 향후 적재 또는 저장 작업이 수행되기 전에 메모리에서 저장 작업이 완료되어 다른 프로세스에 보이게 한다.

메모리 장벽은 매우 낮은 수준의 연산으로, 일반적으로 상호 배제를 보장하는 특수 코드 작성 시 커널 개발자만 사용한다.

하드웨어 명령어

인터럽트 되지 않는 하나의 단위로서의 특별한 하드웨어 명령어들이 있다.
한 워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환(swap)할 수 있다.
여기서 원자적(atomically)으로 실행된다는 점이 중요한데, 여러 곳(각각 다른 코어)에서 같은 명령어가 동시에 실행된다면 임의의 순서로 순차적으로 실행된다.

test_and_set() 명령에서, false 로 초기화되는 lock 변수를 사용해 상호배제를 구현할 수 있다.

compare_and_swap() 명령어(CAS)는 3개의 피연산자를 대상으로 연산하며, 언제나 value 의 원래 값을 반환하지만 (*value == expected) 수식이 참일 때만 new_value 로 지정된다.
두 개의 CAS 명령이 동시에 실행되면 임의의 순서로 순차적으로 실행된다.

상호 배제 조건은 만족시키지만 한정된 대기 조건을 만족시키지 못하는 방식을 먼저 소개한다.
CAS에서는 전역변수 lock 을 선언하여 0으로 초기화한 뒤, compare_and_swap() 을 호출한 첫 프로세스가 lock 을 1로 지정한다.
lock 의 원래 값이 expected 와 같으므로 임계구역으로 들어간다.
이후의 compare_and_swap() 호출 시 lock 의 값이 1이므로, 기댓값 0과 달라 성공하지 못한다.
프로세스가 임계구역을 나올 때 lock 을 0으로 변경해 다른 프로세스가 임계구역에 들어갈 수 있도록 한다.

임계구역 조건을 모두 만족시키는 알고리즘은 아래와 같다.

while (true) {
    waiting[i] = true;
    key = 1;
    
    while (waiting[i] && key == 1)
        key = compare_and_swap(&lock, 0, 1);

    waiting[i] = false;

    /* critical section */

    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;

    if (j == i)
        lock = 0;
    else
        waiting[j] = false;

    /* remainder section */
}

임계구역에 들어가고 싶다는 의사를 표현하는 waiting 배열을 false 로 초기화 시키고 임계구역 진입을 제어하는 lock 변수를 0으로 초기화한다.
waiting[i]=true 로 임계구역 진입 의사를 표시하여 key=1 로 lock 획득 시도를 한다.
lock 이 0일 경우 CAS 연산에 성공해 key=0 이 되고 루프를 탈출한다.
lock 이 0이 아니라면 루프에서 계속 대기하며, 누군가에 의해 waiting[i]=false 가 될 경우 포기하고 루프를 강제로 나온다.
lock 을 얻은 후에는 대기 중이 아니므로 waiting[i] 값을 false 로 바꾼다.
임계구역 실행이 끝나면 waiting 리스트를 선형 탐색해 true 인 첫 번째 프로세스를 찾는다.
아무도 기다리지 않으면 lock 을 직접 해제하고, 누군가 기다리고 있다면 waiting[j] 를 false 로 바꿔주어 루프를 탈출하고 critical section으로 진입할 수 있게 한다.

원자적 변수(atomic variable)

일반적으로 compare_and_swap() 명령어는 사용되지 않으며, 정수 및 부울 등 기본 데이터 유형에 대한 원자적 연산을 제공하는 원자적 변수를 사용한다.
원자적 변수는 카운터가 증가할 대와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는 데 사용할 수 있다.
원자적 변수를 지원하는 대부분의 시스템은 원자적 변수에 접근하고 조작하기 위한 기능뿐만아니라 특별한 원자적 데이터를 제공하는데, 종종 compare_and_swap() 연산을 사용해 구현된다.

원자적 변수는 원자적 갱신을 재공하지만 모든 상황에서 경쟁 조건을 완벽히 해결하지는 않는다.
운영체제 및 병행 응용 프로그램에서 일반적으로 사용되지만 카운터 및 시퀀스 생성기와 같은 공유 데이터 한 개의 갱신에만 제한되는 경우가 많다.

댓글남기기