티스토리 뷰

OS

OS - 동기화

perseverance 2024. 9. 5. 22:06

협력적 프로세스는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스이다. 협력적 프로세스는 논리 주소 공간(즉, 코드 및 데이터)을 직접 공유하거나 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유할 수있다.

그러나 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있다. 데이터의 일관성을 유지하는 다양한 메커니즘을 알아보자

1. 배경

우리는 이미 프로세스가 병행하게 또는 병렬로 실행될 수 있다는 것을 알고 있다. CPU 스케줄러가 프로세스 사이에서 빠르게 오가며 각 프로세스를 실행하여 모든 프로세스를 병행 실행시킨다는 것을 배웠다.

 

이는 한 프로세스는 다른 프로세스가 스케줄되기 전에 일부분만 진행할 수 있다는 것을 의미한다. 사실 프로세스는 명령어가 실행될 때 어느 지점에서나 인터럽트 되고, 처리 코어는 다른 프로세스의 명령어를 실행하도록 할당될 수 있다.

 

또한 병렬 실행, 즉 다른 프로세스에 속한 두 개의 명령어 흐름이 한순간에 다른 처리 코어에서 동시에 실행되는 방식이 존재한다.

 

본 장에서 프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성에 어떤 문제를 일으키는지에 관해 설명한다.

두 프로세스가 공유 메모리를 통해 count변수를 공유하고 있다고 가정하자.

 

A 프로세스는 다음과 같이 count를 1높인다.

count++;

B 프로세스는 count를 1내린다.

count--

위 코드는 개별적으로 봤을때 올바를지리도, 그들을 병행적으로 수행시키면 올바르게 동작하지 않는다. 예를 들어, count의 현재 값은 5이고 A프로세스와 B 프로세스는 count++와 count—를 병행하게 실행한다고 가정하자.

 

이 두 개의 명령이 수행되고 나면 count가 5일걸 예상하겠지만 4나 6이 나올수 있다.

 

그럼 왜 이런 일이 발생할까? 사실 기계어에서는 count++은 다음과 같이 구현될 수 있다. register1은 한 CPU만 접근할 수 있는 레지스터 중 하나이다.

register1 = count
register1 = register1 + 1
count = register1

이거와 마찬가지와 count—는 다음과 같이 구현될 수 있다. register2 역시 CPU만 접근할 수 있는 레지스터 중 하나이다.

register2 = count
register2 = register2 - 1
count = register2

count++와 count— 문장을 병행하게 실행하는 것은 앞에서 제시한 저수준의 문장들을 임의의 순서로 뒤섞어 순차적으로 실행하는 것과 동일하다. (각 고수준 문장 내에서의 순서는 유지된다) 그중 하나는 다음과 같은 순서를 가질 수 있다.

register1 = count.             [register1 = 5]
register1 = register1 + 1.     [register1 = 6]  
register2 = count              [register2 = 5]
register2 = register2 - 1      [register2 = 4]
count = register1              [count = 6]
count = register2              [count = 4]

이러한 부정확한 상태에 도달하는 것은 두 개의 프로세스가 동시에 변수 count를 조작하도록 허용했기 때문이다. 이처럼 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 race condition이라고 한다.

 

위와 같은 경쟁 상황으로부터 보호하기 위해, 우리는 한순간에 하나의 프로세스만이 변수 count를 조작하도록 보장해야 한다. 이러한 보장을 위해, 우리는 어떤 형태로든 프로세스들이 동기화 되도록 할 필요가 있다.

 

운영체제는 여러 부분에서 자원을 조작하기 때문에 위와 같은 상황은 빈번하게 발생한다. 게다가 다중 코어 시스템과 다중 스레드 응용의 개발에 관한 관심이 증가하고 있다. 이러한 다중 스레드 응용세서는 자원을 공유할 가능성이 매우 높은 여러 스레드가 서로 다른 처리 코어에서 병렬로 실행된다.

 

분명히 우리는 이러한 행동에서 발생하는 수정이 서로 간에 영향을 주지 않기를 원한다.

2. 임계구역 문제 (The Critical-Section Problem)

프로세스 동기화에 관한 논의는 소위 임계구역 문제라고 불리는 문제로부터 시작한다. n 개의 프로세스가 있는 시스템을 고려해 보자. 각 프로세스는 임계구영이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다.

 

이 시스템의 중요한 특징은 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 사실이다. 즉 동시에 두 프로세스는 그들의 임계구역 안에서 실행할 수 없다.

 

임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다.

 

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

while (true) {

  [entry section]

  // critical section

  [exit section]

  // remainder section

}

임계구역 문제에 대한 해결안은 다음의 세 가지 요구 조건을 충족해야 한다.

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

임의의 한순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화될 수 있다. 그 결과 운영체제를 구현하는 코드(커널 코드)는 경쟁 조건이 발생하기 쉽다.

 

예를들어, 시스템의 모든 열린 파일의 리스트를 유지하는 커널 자료구조를 고려해 보자. 이 리스트는 새 파일이 열리거나 닫히면 수정되어야 한다 (파일을 리스트에 추가하거나 리스트에서 삭제해야 한다).

 

만일 두 프로세스가 동시에 파일을 열려고 한다면, 리스트에 대한 개별적인 갱신은 경쟁 조건을 일으킬 수 있다.

 

다른 예시로는, P0 및 P1의 두 프로세스는 fork() 시스템 콜을 사용하여 자식 프로세스를 생성한다. fork() 는 새로 생성된 프로세스의 프로세스 식별자를 부모 프로세스로 반환한다는 점을 알고 있어야 한다.

 

이 예에서, 커널 변수 next_available_pid에 경쟁 조건이 있으며, 이 변수는 다음 사용 가능한 프로세스 식별자의 값을 나타낸다. 상호 배제가 제공되지 않으면 동일한 프로세스 식별자 번호가 두 개의 다른 프로세스에 배정될 수 있다.

 

경쟁 조건이 발생하기 쉬운 다른 커널 자료구조로는 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 유지하는 자료구조, 인터럽트 처리를 위한 자료구조 등이 있다.

 

운영체제에서 이러한 경쟁 조건이 발생하지 않도록 보장하는 것은 커널 개발자의 책임이다.

단일 코어 환경에서는 공유 변수를 수정하는 동안 인터럽트가 발생하는 것을 막을 수 있다면 임계구역 문제는 간단히 해결할 수 있다. 이렇게 하면 현재 실행 중인 명령어들을 선점 없이 순서대로 실행될 수 있다는 것을 확신할 수 있다.

 

불행히도 이 해결책은 다중 처리기 환경에서 실현할 수 있지 않다. 메시지가 모든 프로세서에 전달되므로 다중 처리기에서 인터럽트를 비활성하면 시간이 많이 걸릴 수 있다. 이 메시지 전달은 각 임계구역으로의 진입을 지연시키고 시스템 효율성을 떨어뜨린다. 또한 클록이 인터럽트로 업데이트되는 경우 시스템 클록에 미치는 영향도 고려해야한다.

 

운영체제 내에서 임계구역을 다루기 위해 선점형 커널과 비선점형 커널의 두 가지 일반적인 접근법이 시용된다.

 

[선점형 커널]

프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.

[비선점 커널]

커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행된다.

 

비선점 커널은 한순간에 커널 안에서 실행 중인 프로세스는 하나밖에 없으므로 커널 자료구조에 대한 경쟁 조건을 염려할 필요는 없다. 선점형 커널에 커널 안에서 실행 중인 프로세스가 여러개일 수 있다. 따라서 공유되는 커널 자료구조에서 경쟁 조건이 발생하지 않는다는 것을 보장하도록 신중하게 설계되어야 한다.

 

3. Peterson의 해결안

임계구역에 대한 고전적인 소프트웨어 기반 해결책으로 Peterson의 해결안이 알려져 있다. 현재 컴퓨터 구조가 load와 store 같은 기본적인 기계어를 수행하는 방식 때문에 Perterson의 해결안이 이러한 구조에서 올바르게 실행된다고 보장할 수는 없다. 그러나 임계구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공하고 상호 배제, 진행, 한정된 대기의 요구 조건을 중점으로 다루는 소프트웨어를 설계하는 데 필요한 복잡성을 잘 설명하기 때문에 이 해결책을 제시한다.

 

Peterson의 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다. 프로세스는 P0와 P1로 번호를 매긴다. 편의상 P_i라고 표현하면 P_j는 다른 프로세스를 가리키고 j는 1-i와 같다고 하자.

 

Peterson의 해결안은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

  • int turn;

임계구역으로 진입할 순번을 나타낸다.

만일 turn == i 이면 프로세스 P_i가 임계구역에서 실행될 수 있다.

  • boolean flag[2];

프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.

 

예를 들어, flag[i]가 참이라면 P_i가 임계구역으로 진입할 준비가 되었다는 것이다.

임계구역으로 진입하기 위해서 P_i는 먼저 flag[i]를 true로 만들고, turn을 j로 지정한다. 이렇게 함으로써 프로세스 j가 임계구역으로 진입하기 원한다면 진입 가능하다는 것을 보장한다.

 

만일 두 프로세스가 동시에 진입하기를 원한다면 turn은 거의 동시에 i와 j로 지정될 것이다. 그러나 둘 중 오직 한 배정만이 지속된다. 다른 배정은 발생하기는 하지만 곧바로 겹쳐 쓰이게 된다. turn의 궁극적인 값이 둘 중 누가 먼저 임계구역으로 진입할 것인가를 결정한다.

while(true) {
  flag[i] = true;
  turn = j;
  while(flag[j] && turn == j)
    ;
  /* critical section */
  flag[i] = false;
  /* remainder section */
}

이 해결책에서 우리는 다음과 같은 사실을 보여야 한다.

  1. 상호 배제가 제대로 지켜진다는 사실
  2. turn값은 i아니면 j이다 즉, 동시에 두가지 값을 가지지 못하니 상호 배제는 지켜진다.
  3. 진행에 대한 요구 조건을 만족한다는 사실
  4. 대기 시간이 한없이 길어지지 않는다는 사실

2,3 번은 while(flag[j] && turn == j)을 수행하는 동안 turn값을 바꾸지 않고 임계구역을 끝낸 후 flag값을 false로 재지정 하기 때문에 2,3은 보장된다.

 

하지만 앞에서 말했다 싶이 Peterson의 해결안은 최신 컴퓨터 아키텍처에서 작동한다고 보장되지 않는다. 주된 이유는 시스템 성능을 향상하기 위해 프로세스 또는 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문이다.

 

단일 스레드 응용 프로그램의 경우 최종 결과가 예상한 것과 일치하기 때문에 프로그램의 정확성 측면에서 재정렬은 중요하지 않다. 그러나 데이터를 공유하는 다중 스레드 응용 프로그램의 경우 명령 순서가 바뀌게 되면 데이터의 일관성이 깨지거나 예기치 못한 결과를 낳을 수 있다.

예를 들어, 두 스레드 간에 공유되는 다음 데이터를 고려하자

  • boolean flag = false
  • int x = 0

여기서 thread1은 다음 명령을 수행한다.

while(!flag)
  ;
print x;

그리고 thread2는 다음 명령문을 수핸한다.

x = 100;
flag = true;

예상되는 동작은 스레드 1이 변수 x에 100을 출력하는 것이다. 그러나 변수 flag와 x사이에 데어터 종속성이 없으므로 프로세서가 스레드 2의 명령어를 재정렬하여 x=100을 배정하기 전에 flag가 true로 지정될 수 있다. 이 상황에서 스레드1은 변수 x에 대해 0을 출력할 수 있다.

이러한 사실이 Peterson의 해결안에 어떤 영향을 미칠까? Peterson의 해결안의 진입 구역에 나타나는 첫 두 문장의 순서를 바꾸면 어떤 일이 발생하는지 고려해 보자. 두 스레드가 동시에 임계구역에서 활성화될 수 있다.

 

다음 절에서 볼 수 있듯이 상호 베제를 유지하는 유일한 방법은 적절한 동기화 도구를 사용하는 것이다.

 

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

앞에서 본것 같이 소프트웨어 기반 해결책은 최신 컴퓨터 아키텍처에서 작동하지 않을 수 있다. 이 절에서는 임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어를 제시한다. 이러한 프리미티브 연산은 동기화 도구로 직접 사용될 수 있거나 더 추상적인 동기화 기법의 기초 형태로 사용될 수 있다.

4.1 메모리 장벽

앞에서 명령어의 순서를 재정렬 할 수 있다는 것과 이러한 정책이 신뢰할 수 없는 데이터 싱태로 이어질 수 있다는 것을 보았다. 컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 한다.

일반적으로 메모리 모델은 두 가지 범주 중 하나에 속한다.

  1. 강한 순서
  2. 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임
  3. 약한 순서
  4. 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음

메모리 모델은 프로세서 유형에 따라 다르므로 커널 개발자는 공유 메모리 다중 처리기에서 메모리 변경의 가시성에 대한 어떠한 가정도 할 수 없다. 이 문제를 해결하기 위해 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 것을 보장한다.

 

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

 

다음 코드에서 메모리 장벽을 사용해 flag에 배정하기 전에 x에 대한 배정이 먼저 실행되도록 한다.

x = 100;
memory_barrier();
flag = true;

위 메모리 장벽을 이용하여 Peterson의 해결안에서 명령어 재정렬 문제를 해결할 수 있다.

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

 

4.2 하드웨어 명령어

많은 현대 기계들은 한 워드의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.

그중 test_and_set()과 compare_and_swap()을 살펴보자

test_and_set() 명령어는 다음과 같이 정의할 수 있다.

boolean test_and_set(boolean *target) {
  boolean rv = *target;
  *target = true;

  return rv;
}

중요한 특징으로는 이 명령어가 원자적으로 실행된다는 점이다. 그러므로 만일 두 개의 test_and_set() 명령어가 동시에 실행된다면(각각 다른 코어에서), 이들은 어떤 임의의 순서로 순차적으로 실행될 것이다.

만일 test_and_set() 명령을 지원한다면, false로 초기화되는 lock이라는 boolean 변수를 선언하여 상호 배제를 구현할 수 있다.

do {
  while (test_and_set(&lock)) 
    ; // 다른 스레드가 락을 가지고 있다면 계속 대기
  // critical section
  lock = false;
  // remainder section
} while(true);

compare_and_swap() 명령어(CAS) 는 test_and_set() 명령어와 마찬가지로 두 개의 워드에 대해 원자적인 연산을 하지만 두 워드의 내용 교환에 기반을 둔 다른 기법을 사용한다. CAS는 3개의 피연산자를 대상으로 연산을 하며 다음과 같이 정의되어 있다.

int compare_and_swap(int *value, int expected, int new_value) {
  int temp = *value;

  if(*value == expected)
    *value = new_value;

  return temp;
}

이 명령 또한 원자적으로 실행된다.

CAS를 사용하는 상호 배제는 다음과 같이 이루어진다. 전역 변수 lock이 선언되고 0으로 초기화된다. compare_and_swap()을 호출한 첫 번째 프로세스는 lock을 1로 지정할 것이다. lock의 원래 값이 expected 값과 같으므로 프로세스는 임계구역으로 들어간다. 이후의 compare_and_swap() 호출은 현재 lock값이 기댓값 0과 같지 않기 때문에 성공하지 못한다.

while(true) {
  while (compare_and_swap(&lock, 0, 1) != 0) 
    ; // do nothing
  // critical section
  lock = 0;
  // remainder section 
}

 

위 알고리즘은 상호 배제 조건을 만족시키지만 한정된 대기 조건을 만족시키지 못한다.

특정 스레드가 임계 구역에 들어가려 할 때, 다른 스레드들이 계속해서 compare_and_swap을 성공시키고 임계 구역에 들어가 버리면, 처음 스레드는 영원히 들어가지 못할 가능성이 있습니다. 이 경우 한정된 대기 조건이 깨진다.

 

4.3 원자적 변수

일반적으로 compare_and_swap() 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않는다. 오히려 임계구역 문제를 해결하는 다른 도구를 구축하기 위한 기본 구성요소로 사용된다.

 

그러한 도구 중 하나는 원자적 변수로, 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다. 앞에서 정수 값을 증가시키거나 감소시키면 경쟁 조건이 발생할 수 있음을 알고 있다.

 

원자적 변수는 카운터가 증가할 때와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는 데 사용될 수 있다.

 

원자적 변수를 지원하는 대부분의 시스템은 원자적 변수에 접근하고 조작하기 위한 기능뿐만 아니라 특별한 원자적 데이터 유형을 제공한다. 이러한 함수는 종종 compare_and_wap() 연산을 사용하여 구현된다.

 

예를 들어 다음은 원자적 정수 sequence를 증가시킨다

void increment(atomic_int *v) {
  int temp;

  do {
    temp = *v;
  }
  while(temp != compare_and_swap(v, temp, temp+1));
}

원자적 변수는 운영체제 및 병행 응용 프로그램에서 일반적으로 사용되지만 카운터 및 시퀀스 생성기와 같은 공유 데이터 한 개의 갱신에만 제한되는 경우가 많다.

 

5. Mutex Locks

임계구역에 대한 하드웨어 기반 해결책은 복잡할 뿐 아니라 응용 프로그래머는 사용할 수가 없다. 대신 운영체제 설계자들은 임계구역 문제를 해결하기 위한상위 수준 소프트웨어 도구들을 개발한다.

 

가장 간단한 도구가 바로 mutex Lock이다. 우리는 임계구역을 보호하고, 따라서 경쟁 조건을 방지하기 위해 mutex락을 사용한다. 즉, 프로세스는 임계구역에 들어가기 전에 반드시 락을 휙득(acquire())해야 하고 임계구역을 빠져나올 때 락을 반환(release())해야 한다.

 

Mutex 락은 available이라는 불린 변수를 가지는데 이 변수 값이 락의 가용 여부를 표시한다. 락이 가용하면 acquire() 호출은 성공하고 락은 곧 사용 불가 상태가 된다. 사용 불가 상태의 락을 휙득하려고 프로세스는 락이 반환될 때까지 봉쇄된다.

acquire() {
  while(!available)
    ; /* busy wait */
  available = false;
}

release() {
  available = true;
}

acquire() 또는 release() 함수 호출은 원자적으로 수행되어야 한다. 따라서 mutex락은 CAS를 사용하여 구현될 수 있다.

 

mutex의 단점은 바쁜 대기(busy waiting)를 해야 한다는 것이다. 프로세스가 임계구역에 있는 동안 임계구역에 들어가기를 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 한다. 이러한 계속된 루프의 실행은 하나의 CPU 코어가 여러 프로세서에서 공유되는 실제 다중 프로그래밍 시스템에서 분명히 문제가 된다.바쁜 대기는 다른 프로세스가 생산적으로 사용할 수 있는 CPU 주기를 낭비한다.

 

위에서 설명한 mutext 락 유형을 스핀락(spinlock) 이라고도 한다. 락을 사용할 수 있을 때까지 프로세스가 회전하기 때문이다. 그러나 스핀락은 프로세서가 락을 기다려야하고 문맥 교환에 상당한 시간이 소요될 때 문맥 교환이 필요하지 않다는 장점이 있다.

스핀락이 진행되는 동안에도 타이머 인터럽트는 여전히 발생할 수 있습니다. 하지만 스핀락이 자원을 짧은 시간 내에 획득할 수 있을 때, 문맥 교환 없이 락을 바로 획득하고 작업을 진행할 수 있기 때문에 문맥 교환에 소요되는 오버헤드를 피할 수 있습니다. 만약 락을 획득하지 못하고 타이머 인터럽트가 발생하여 문맥 교환이 필요해진다면, 그 시점에서는 문맥 교환이 발생하게 됩니다. 따라서 스핀락의 장점은 "타이머 인터럽트가 발생하기 전에" 락을 획득할 가능성이 높다는 데 있습니다.

 

다중 코어 시스템의 특정 상황에서는 실제로 락이 필요할 때 스핀락이 선호된다. 잠깐 동안 락을 유지해야 하는 경우 다른 스레드가 하나의 코어에서 임계구역을 실행하는 동안 스레드는 다른 처리 코어에서 스핀하고 있을 수 있다.

 

6. 세마포(Semaphores)

세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다. wait() 연산은 검사하다 라는 의미를 가지고 있고 signal()은 증가하다라는 의미를 가지고 있다.

wait(S) {
  while (S <= 0 )
    ; // busy wait
  S--;
}

signal(S) {
  S++;
}

wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. 즉, 한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다. 또한 wait(S) 의 경우, S의 정수 값을 검사하는 작업(S<=0)과 그에 따라 실행될 수 있는 변경 (S—)한느 작업 또한 인터럽트 되지 않고 실행되어야 한다.

 

6.1 세마포 사용법

운영체제는 종종 카운팅(counting)과 이진(binary) 세마포를 구분한다. 카운팅 세마포의 값은 제한 없는 영역(domain)을 갖는다. 이진 세마포의 값은 0과 1사이의 값만 가능하다. 따라서 이진 세마포는 mutex락과 유사하게 동작한다. 사실 몇몇 시스템에서는 mutex락을 제공하지 않고 상호 배제를 보장하기 위해서 이진 세마포가 대신 사용된다.

 

카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다. 세마포는 가용한 자원의 개수로 초기화 된다. 각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소한다. 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포는 증가하게 된다. 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다. 이후 자원을 사용하려는 프로세스는 세마

포 값이 0보다 커질 때까지 봉쇄된다.

 

또한 순서를 제어하기 위해서도 사용된다. 다음과 같이 개발하면 P1프로세스가 P2프로세스보다 더 먼저 실행된다.

P1은 S1 명령문을, P2는 S2명령문을 병행하게 수행하고 있고, 세마포 synch를 공유하고 있으며 synch의 초기값은 0이다.

S1;
signal(synch);
---
wait(synch)
S2;

synch 값은 0으로 초기화되어 있으므로, P2가 S2를 수행하는 것은 P1이 signal(synch)를 호출한 후에만 가능할 것이다. 그리고 이 호출은 S1을 실행한 이후에만 가능하다.

 

6.2 세마포 구현

앞에서 봤던 것처럼 mutex 락 구현은 바쁜 대기를 해야 했다. 방금 설명한 세마포 연산 wait()과 signal()의 정의 역시 같은 문제를 가지고 있다. 이 문제를 극복하기 위하여, wait()와 signal() 세마포 연산의 정의를 다음과 같이 변경할 수 있다.

 

프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면, 프로세스는 반드시 대기해야 한다. 그러나 바쁜 대기 대신에 프로세스는 자신을 일시 중지시킬 수 있다. 일시 중지 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다. 그 후에 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위하여 선택한다.

 

세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal()연산을 실행하면 재시작되어야 한다. 프로세스는 wakeup() 연산에 의하여 재시작되는데 이것은 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경한다. 그리고 프로세스는 준비 큐에 넣어진다(CPU는 CPU 스케줄링 알고리즘에 따라 실행 중인 프로세스로 부터 새로 준비 완료가 된 프로세스로 전환될 수도 있고 되지 않을 수도 있다).

 

이러한 정의를 따르는 세마포를 구현하기 위해, 세마포를 다음과 같이 정의한다.

typedef struct {
  int value;
  struct process *list;
} semaphore;

각 세마포는 한 개의 정수 value와 프로세스 리스트 list를 가진다. 프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가된다. signal()연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워준다.

 

wait()연산은 이제 다음과 같이 정의될 수 있다.

wait(semaphore *S) {
  S->value--;
  if (S->value < 0) {
    add this process to S->list;
    sleep();
  }
}

signal() 연산은 다음과 같이 정의될 수 있다.

signal(semaphore *S) {
  S->value++;
  if (S->value <= 0) {
    remove a process P from S->list;
    wakeup(P);
  }
}

sleep() 연산은 자기를 호출한 프로세스를 일시 중지시킨다. wakeup(P) 연산은 일시중지된 프로세스 P의 실행을 재개시킨다. 이들 두 연산은 운영체제의 기본적인 시스템 콜로 제공된다.

 

바쁜 대기를 하는 세마포의 고전적 정의에서는 세마포의 값은 음수를 가질 수 없으나, 이처럼 구현하면 음수 값을 가질 수 있다. 세마포 값이 음수일 때, 그 절대값은 세마포를 대기하고 있는 프로세스들의 수이다.

 

대기하는 프로세스들의 리스트는 각 프로세스 제어 블록(PCB)에 있는 연결 필드에의하여 쉽게 구현될 수 있다. 각 세마포는 정수 값과 프로세스 제어 블록의 리스트에 대한 포인터를 갖고 있다. 한정된 대기를 보장하도록 리스트에 프로세스를 추가하고 삭제하는 한가지 방법은 선입 선출 큐를 사용하는 것으로 세마포가 큐의 머리와 꼬리에 대한 포인터를 모두 가지게 된다.

 

그러나 일반적으로 리스트는 임의의 큐잉 전략을 사용할 수 있다.

 

우리는 같은 세마포에 대해 두 프로세스가 동시에 wait()와 signal() 연산들을 실행할 수 없도록 반드시 보장해야한다. 단일 처리기 환경에서는, 단순히 wait()와 signal() 연산들이 실행되는 동안 인터럽트를 금지함으로써 간단히 해결할 수 있다. 이 방법은 일단 인터럽트가 금지되면, 다른 프로세스들의 명령어들의 명령어들이 끼어들 수 없기 때문에 단일 처리기 환경에서는 올바르게 동작한다.

 

다중 코어 환경에서는 모든 처리 코어에서 인터럽트를 금지하여야만 한다. 그렇지 않으면 (다른 코어에서 실행되는) 상이한 프로세스들의 명령어들이 임의의 방법으로 서로 끼어들 수 있다. 모든 코어에서 인터럽트를 금지하는 것은 매우 어려운 작업일 수 있으며 성능을 심각하게 감소시킨다. 따라서 SMP 시스템은 wait()와 signal() 연산이 원자적으로 실행되는 것을 보장하기 위하여 compare_and_swap() 또는 스핀락과 같은 다른 기법을 제공해야 한다.

 

compare_and_swap()을 사용하므로 wait()와 signal() 연산의 현재 정의에서 바쁜 대기를 완전하게 제거하지 못했다. 우리는 바쁜 대기를 wait()와 signal() 연산의 임계구역에만 국한하였으며, 이 구역은 매우 짧다(코드가 적절하게 작성되었다면, 약 10개의 명령어를 넘지 않는다). 그러므로 임계구역은 거의 항상 비어 있으며, 바쁜 대기는 드물게 발생한다며 발생하더라도 그 시간이 아주 짧다.

 

임계구역이 매우 길거나 또는, 거의 항상 점유된 응용 프로그램들을 갖는 전혀 다른 환경도 존재한다. 이 경우에 바쁜 대기는 극도로 비효율적이다.

 

7. 모니터

세마포가 프로세스 간의 동기화를 위해서 편리하고 효과적으로 쓰일 수 있지만 세마포는 자칫 잘못 사용하면 발견하기 어려운 타이밍 오류를 야기할 수 있는데 이러한 타이밍 오류들은 특정 실행 순서로 진행되었을 때만 발생하고 이러한 순서가 항상 일어나는 것은 아니기 때문이다.

 

앞에서 count를 사용할때 발생하는 문제를 해결하기 위해 Mutex 락과 세마포를 도입했다고 설명했다. 불행하게도 mutex락 혹은 세마포를 사용할 때에도 그와 같은 타이밍 오류는 여전히 발생할 수 있다.

 

모든 프로세스는 mutex라는 이진 세마포 변수를 공유하며 그 초기 값은 1이다. 각 프로세스는 임계구역에 진입하기 전에 wait(mutex)를 실행해야 하며 임계구역을 나올 때 signal(mutex)를 실행해야 한다. 만일 이 순서가 제대로 지켜지지 않으면 두 프로세스가 동시게 임계구역 안에 있을 수 있다.

  • 세마포에 대한 wait()와 signal()연산의 순서가 뒤바뀌어 아래와 같은 코드가 되었다고 해보자
signal(mutex);
//critical section
wait(mutex);

이 경우에는 여러 프로세스가 동시에 임계구역 안에서 실행될 수 있어 상호 배제 요구 조건을 위반하게 된다. 이러한 오류는 여러 프로세스가 동시에 자신의 임계구역안에서 실행되었을 때에만 발견될 수 있다.

  • 프로그램이 signal(mutex)를 써야 할 곳에 잘못해서 wait(mutex)를 써다고 가정해 보자
wait(mutex);
//critical section
wait(mutex);

이 경우에는 세마포를 사용할 수 없으므로 프로세스는 두 번째 wiat() 호출에서 영구적으로 봉쇄된다.

이 예들에서 볼 수 있듯이 세마포 또는 mutex락을 이용하여 임계구역 문제를 해결할 때 프로그래머가 세마포를 잘못 사용하면 다양한 유형의 오류가 너무나도 쉽게 발생할 수 있음을 알 수 있다.

 

7.1 모니터 사용법

추상화된 데이터 형(abstact data type, ADT)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다. 이때 함수의 구현은 ADT의 특정한 구현과는 독립적이다. 모니터 형은 모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT이다.

 

모니터 형의 표현은 다른 프로세스들이 직접 사용할 수 없다. 따라서 모니터 내에 정의된 함수만이 오직 모니터 내에 지역적으로 선언된 변수들과 형식 매개변수들에만 접근할 수 있다. 마찬가지로 모니터 내에 지역 변수는 오직 지역 함수만이 접근할 수 있다.

 

모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장해 준다. 그러므로 프로그래머들은 이와 같은 동기화 제약 조건을 명시적으로 코딩해야할 필요가 없다.

 

그러나 지금까지 정의한 모니터 구조물은 어떤 동기화 기법을 모델링하는 데에는 충분한 능력을 제공하지 않는다. 이를 위해 우리는 부가적인 동기화 기법을 정의해야 할 필요가 있다. 이 동기화 기법들은 condition이라는 구조물로 제공될 수 있다. 자신의 주문형 동기화 기법을 작성할 필요가 있는 프로그래머는 하나 이상의 condition형의 변수를 정의할 수 있다.

 

condition x, y;

 

이 condition 형 변수에 호출될 수 있는 연산은 오직 wait() 와 signal()이다. wait()는 이 연산을 호출한 프로세스는 다른 프로세스가 signal()을 호출할 때까지 일시 중지 되어야 한다는 것을 의미한다.

 

이제 x.signal() 연산이 프로세스 P에 의하여 호출될 때, 조건 x와 연관된 일시중지된 프로세스 Q가 있다고 가정해 보자. 만일 일시 중지된 스레드 Q가 실행을 재개하도록 허용된다면, signal을 보낸 스레드 P는 반드시 대기해야 한다. 그렇지 않으면 P와 Q는 모니터 안에서 동시에 활성화된다. 여기에 두 가지 가능성이 존재한다.

  1. Signal and wait: P는 Q가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.
  2. Signal and continue: Q는 P가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.

'OS' 카테고리의 다른 글

OS - 메인 메모리  (0) 2024.09.12
OS - 동기화 예제  (0) 2024.09.05
OS - CPU 스케줄링  (1) 2024.08.28
프로세스  (1) 2024.08.22
Process와 Thread의 차이  (0) 2024.08.22
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함