6. Synchronization Tools

협력적 프로세스는 시스템 내 실행 중인 다른 프로세스에 영향을 미치거나 영향을 받을 수 있는 프로세스이다. 이는 논리적 주소 공간을 공유할 수도 있고 공유 메모리나 메시지 패싱을 통해 데이터를 공유할 수도 있다. 이런 공유는 데이터 비일관성을 낳을 수 있기 때문에 이 장에서는 이를 방지하는 법을 다룬다.

6.1. Background

프로세스는 동시에 또는 병렬로 실행될 수 있다. 이 장에서는 동시적 또는 병렬 실행이 여러 프로세스에 의해 공유되는 데이터의 통합성에 어떤 영향을 미치는지를 알아본다. 여러 프로세스가 동일한 데이터를 동시에 접근 및 수정할 때 실행의 결과가 접근의 순서에 따라 달라지는 것을 레이스 컨디션이라 한다. 이를 막기 위해서는 해당 데이터를 조작하는 프로세스가 한 번에 하나뿐임을 보장해야 한다. 이는 프로세스 동기화와 프로세스 조정을 통해 보장된다.

6.2. The Critical-Section Problem

시스템에 n개의 프로세스가 있고 각 프로세스는 다른 프로세스와 공유하는 데이터를 접근 및 업데이트하는 임계 영역을 갖고 있다 하자. 이 때 자신의 임계 영역을 실행하는 프로세스는 한 번에 하나 뿐이어야 한다. 그러므로 각 프로세스는 진입 영역을 통해 임계 영역 진입에 대한 허가를 받고 출구 영역을 통해 허가를 반납한다. 나머지는 잔여 영역이라 한다. 이는 다음의 조건을 만족해야 한다.

  1. 상호 배제. 자신의 임계 영역을 실행하는 프로세스는 한 번에 하나 뿐이어야 함.
  2. 진전. 임계 영역을 실행 중인 프로세스가 없고 다른 프로세스가 임계 영역에 진입하려고 할 때는 잔여 영역을 실행 중이지 않은 프로세스만이 다음 임계 영역에 진입할지에 대한 결정에 참가할 수 있음.
  3. 대기 제한. 임계 영역 진입 요청을 한 프로세스가 진입하기까지 무한정 대기하면 안 됨.

운영 체제의 커널 코드는 레이스 컨디션에 노출된다. 이러한 임계 영역 문제는 싱글 코어 환경에서는 공유 변수가 수정되고 있다면 인터럽트를 막음으로써 해결할 수 있다. 하지만 멀티 코어 환경에서는 이러한 접근법은 부적합하다. 이를 해결하기 위한 두 가지 접근법으로 선점성 커널비선점성 커널이 있다. 비선점성 커널은 레이스 컨디션으로부터 자유롭지만 성능 문제가 있다.

6.3. Peterson’s Solution

이제 임계 영역 문제에 대한 소프트웨어 기반의 피터슨 해법을 알아보자. 피터슨 해법은 int형 변수 turn과 bool형 변수 flag[2]를 필요로 한다. 임계 영역에 진입하기 위해선, 프로세스 P_i는 flag[i]를 true로 세팅하고 turn을 j로 세팅한다. 이는 위의 3가지 조건은 충족하지만 현대 컴퓨터 아키텍쳐에서는 잘 동작하지 않는다. 왜냐하면 프로세서나 컴파일러는 읽기와 쓰기 연산에서 의존성이 없는 경우 이를 재배열하기 때문이다. 그래서 적절한 동기화 방법만이 해결책이다.

6.4. Hardware Support for Synchronization

이 장에서는 임계 영역 문제 해결을 지원하는 3개의 하드웨어 명령어를 알아본다.

6.4.1. Memory Barriers

컴퓨터 아키텍쳐가 보장하는 메모리 순서를 메모리 모델이라 한다. 이는 둘 중 하나로 분류된다.

  1. 강순서. 한 프로세서의 메모리 수정이 다른 프로세서에도 즉시 보여짐.
  2. 약순서. 한 프로세서의 메모리 수정이 다른 프로세서에 즉시 보여진다는 보장이 없음.

이는 프로세서마다 다르기 때문에 컴퓨터 아키텍쳐는 메모리의 변경이 다른 프로세서에 보여짐을 강제하는 명령어를 제공한다. 이를 메모리 배리어메모리 펜스라 한다. 메모리 배리어 명령어가 수행되면 시스템은 다른 불러오기/저장 연산이 수행되기 전 모든 불러오기/저장 연산을 끝내야 한다.

6.4.2. Hardware Instructions

많은 현대 컴퓨터 시스템은 워드의 내용을 시험 및 수정하거나 두 워드의 내용을 원자적으로 교환할 수 있는 하드웨어 명령어를 제공한다. 이는 test_and_set()과 compare_and_swap()이다.

6.4.3. Atomic variables

compare_and_swap() 연산은 상호 배제 제공에 직접적으로 쓰이지는 않는다. 그 대신 임계 영역 문제를 풀기 위한 다른 도구를 구성하기 위한 기본적인 구성 요소로 쓰인다. 그 도구들 중 하나로 원자적 변수가 있다. 이는 정수나 bool형 같은 기본적 자료형에 대한 원자적 연산을 할 수 있도록 하는 것이다. 그러나 원자적 변수가 레이스 컨디션을 전부 해결해주지는 않는다는 것을 유념할 필요가 있다. 또한, 그들의 사용은 카운터나 수열 생성기 등에 대한 단일 업데이트에 제한된다.

6.5. Mutex Locks

임계 영역 문제를 풀기 위한 가장 간단한 고수준 소프트웨어 도구로는 뮤텍스 락이 있다. 프로세스는 임계 영역 진입 전 락을 획득하고 (acquire()), 임계 영역에서 벗어날 때 락을 반납한다 (release()). 이 구현의 단점은 바쁜 대기를 필요로 한다는 것이다. 즉, 프로세스가 임계 영역에 진입한 동안 임계 영역에 진입하려 하는 다른 프로세스는 acquire()에 대한 루프를 계속 돌아야 한다. 이런 형태의 뮤텍스 락은 스핀 락이라고도 한다. 이는 프로세스가 락을 대기할 때 컨텍스트 스위치를 필요로 하지 않는다는 장점도 있다.

6.6. Semaphores

세마포어는 정수형 변수로 초기화 이외에는 wait(), signal()의 두 원자적 연산을 통해서만 접근된다.

6.6.1. Semaphore Usage

카운팅 세마포어는 범위 제한이 없다. 이진 세마포어는 0, 1 사이의 값만을 갖는다. 즉, 뮤텍스 락과 비슷하다. 카운팅 세마포어는 유한한 개수의 인스턴스로 이루어진 특정한 리소스에 대한 접근을 제어하는 데 쓰인다.

6.6.2. Semaphore implementation

전 장에서 다뤘던 뮤텍스 락의 구현은 바쁜 대기의 문제점이 있다. 세마포어도 비슷한 문제가 있는데, 이는 다음과 같이 고칠 수 있다. 프로세스가 wait() 동작을 수행하고 세마포어 값이 양수가 아니라면 대기한다. 하지만 바쁜 대기를 하는 대신에 프로세스 자신을 늦추고, 세마포어와 연관된 대기 큐에 프로세스를 위치시킨다. 이는 다른 프로세스가 signal() 동작을 수행할 때 재시작되어 준비 큐로 이동된다. 이는 각 프로세스 제어 블럭 내 연결 필드로 쉽게 구현될 수 있다. 세마포어 동작들은 반드시 원자적으로 수행되어야만 한다.

멀티코어 환경에서는 인터럽트는 모든 프로세싱 코어에서 비활성화되어야 한다. 이를 보장하기는 어렵기 때문에 동시성 멀티프로세싱 시스템에서는 compare_and_swap()이나 스핀락 등을 통해 wait()과 signal()이 원자적으로 일어남을 보장한다.

위의 wait()과 signal()의 정의만으로는 바쁜 대기를 완전히 없애지 못한다는 것을 유념할 필요가 있다. 우리는 단지 진입 영역에서 임계 영역으로 바쁜 대기를 옮겨놨을 뿐이다. 임계 영역의 수행 시간이 길어진다면 상황은 달라진다. 이 때 바쁜 대기는 매우 비효율적이다.

6.7. Monitors

세마포어는 프로세스 동기화를 위한 편리하고 효과적인 메커니즘을 제공하지만, 잘못 쓰면 감지하기 어려운 타이밍 에러를 낳는다. 이런 타이밍 에러는 뮤텍스 락이나 세마포어를 써도 잔존할 수 있다. 이러한 문제를 다루는 하나의 방법은 고수준 언어 구조체로서 동기화 도구를 이용하는 것이다. 그 중 하나로는 모니터가 있다.

6.7.1. Monitor Usage

추상 자료형(ADT)은 데이터와 그 데이터에 작용하는 함수들의 집합을 캡슐화한다. 모니터 타입은 모니터 내 뮤텍스가 제공된 추상 자료형이다.

모니터 타입에는 condition 변수가 제공되며 이는 .wait(), .signal() 연산이 제공된다. x.signal() 동작이 프로세스 P에 의해 발생하고 이와 연관된 프로세스 Q가 지연된다고 하자. Q가 재개될 때에는 P는 대기중이어야 하지만, 둘 다 실행되는 경우도 있다. 이는 다음의 경우이다.

  • 시그널 후 대기. P는 Q가 모니터를 떠날 때까지 대기하거나 다른 이유로 대기함.
  • 시그널 후 재개. Q는 P가 모니터를 떠날 때까지 대기하거나 다른 이유로 대기함.

두 가능성 모두 합당한 이유가 있다. 물론, P가 시그널을 수행했을 때 P가 즉시 모니터를 떠나서 Q가 즉시 재개될 수도 있다.

6.7.2. Implementing a Monitor Using Semaphores

세마포어를 통한 모니터의 구현도 가능하다. 각 모니터마다 이진 세마포어 mutex를 제공하고 wait(mutex), signal(mutex) 동작을 제공한다.

6.7.3. Resuming Processes within a Monitor

모니터 내의 프로세스 재개를 생각해 보자. x 조건에 묶인 프로세스가 여럿 있을 때 x.signal()이 발생한다면 그 다음에 재개될 프로세스는 어떻게 결정해야 할까? 간단한 하나의 해결책은 선도착 선처리 순서를 부여하는 것이다. 다른 방법은 우선도 수를 부여해 조건부 대기를 시키는 것이다. 하지만 여기에도 문제점이 있는데, 프로그래머에 의해 정의된 고수준 연산을 다른 프로그래머가 적절히 사용하는지를 보장해야 한다는 것이다. 이를 위해서는 다음의 2가지를 확인해야 한다. 첫째로 사용자 프로세스가 모니터에 대한 호출을 올바른 순서로 수행해야 한다. 둘째로 비협조적 프로세스가 뮤텍스를 무시하고 공유 자원에 직접 접근하는 일이 없도록 해야 한다. 이 두 가지가 보장되어야만이 시간 의존성 오류를 해결할 수 있다.

6.8. Liveness

동기화 도구를 이용할 경우 임계 영역에 진입하려 하는 프로세스가 무한정 대기에 빠질 수 있는 문제를 해결해야 한다. 생존성은 프로세스가 실행 생애 주기 동안 진척을 이룸을 보장하기 위해 시스템이 만족해야 하는 특성들을 말한다. 여기서는 두 가지 생존성 실패를 다룬다.

6.8.1. Deadlock

대기 큐를 이용한 세마포어 구현은 2개 이상의 프로세스가 대기 프로세스를 1개만 가질 수 있는 이벤트를 무한정 기다리는 데드락에 빠질 수 있다.

6.8.2. Priority Inversion

높은 우선도 프로세스가 현재 낮은 우선도 프로세스에 의해 접근되고 있는 커널 데이터를 읽거나 수정해야 할 때도 문제가 생긴다. 이는 그 낮은 우선도 프로세스가 다른 더 높은 우선도 프로세스에 의해 선점되어 버릴 때 문제가 생긴다. 이를 우선도 반전이라 한다. 이는 우선도 상속 프로토콜을 구현해 피할 수 있다. 이 프로토콜에서는 우선도가 높은 프로세스들로부터 필요한 자원을 접근하는 모든 프로세스는 자원에 대한 처리가 끝날 때까지 그 높은 우선도를 상속받는다. 자원에 대한 처리가 끝나면 우선도는 원래대로 돌아간다.

6.9. Evaluation

지금까지 임계 영역 문제를 푸는 데 쓰일 수 있는 여러 동기화 도구를 알아보았다. 그러면 어느 때 어떤 도구를 쓸 것인가? 6.4장에 언급된 하드웨어 해결책은 굉장히 저수준이다. 그 대신에 락이 필요 없이 레이스 컨디션이 일어나지 않음을 보장하는 락프리 알고리즘이 인기가 높다. 또한 비교 후 교환 기반 접근은 낙관적 접근이라 하고, 뮤텍스 락은 비관적 접근이라고도 한다. 아래는 여러 접근법에 대한 가이드라인을 여러 조건하에 나열한 것이다.

  • 경합이 없는 경우. 두 방법이 모두 빠르지만, CAS 보호가 더 빠를 것이다.
  • 경합이 적당히 있는 경우. CAS 보호가 훨씬 빠를 것이다.
  • 경합이 매우 많은 경우. 전통적 동기화가 더 빠를 것이다.

경합이 적당히 있는 경우는 흥미롭다. 이 때에는 CAS 동작은 대개 성공하고, 실패할 때에는 성공할 때까지 몇 번의 루프를 돈다. 그와 비교해 뮤텍스 락은 경합 중인 락을 획득하려는 시도는 더 복잡하고 시간 소모적인 코드를 낳는다. 이는 스레드를 대기 큐에 넣고 컨텍스트 스위치를 시도하는 것을 포함한다.

레이스 컨디션을 해결하기 위한 메커니즘의 선택은 역시 시스템 성능에 크게 영향을 미칠 수 있다. 예를 들어 원자적 정수는 일반적인 락보다 훨씬 가볍다. 또한 뮤텍스 락은 세마포어보다 오버헤드를 일반적으로 적게 먹는다. 하지만, 유한한 크기의 자원에 대한 접근을 제어하는 데에는 카운팅 세마포어는 뮤텍스 락보다 효율적이다. 마찬가지로, 읽기-쓰기 락이 뮤텍스 락보다 효율적일 때도 있다. 모니터나 조건 변수는 간단해서 좋지만, 이러한 도구들은 큰 오버헤드를 낳으며, 확장 가능하지 않을 수 있다. 다행스럽게도, 다음의 발전들 때문에 동시성 프로그래밍은 더 발전하고 있다:

  • 컴파일러의 발전.
  • 프로그래밍 언어의 발전.
  • 존재하는 라이브러리나 API의 개선.

6.10. Summary

  • 프로세스가 공유 데이터에 동시적인 접근을 하는데 최종 결과가 동시적인 접근의 순서에 의존할 경우 레이스 컨디션이 일어나며, 이는 공유 데이터의 값을 망칠 수 있다.
  • 임계 영역은 공유 데이터가 수정되고 레이스 컨디션이 일어날 수 있는 코드 영역이다. 임계 영역 문제는 프로세스가 그들의 작업을 동기화하여 데이터를 협업적으로 공유할 수 있도록 프로토콜을 연구하는 것이다.
  • 임계 영역 문제에 대한 해법은 다음의 3가지를 만족해야 한다: 1) 상호 배제. 2) 진척. 3) 제한된 대기. 상호 배제는 임계 영역에 진입한 프로세스가 한 번에 하나임을 보장한다. 진척은 프로그램이 어떤 프로세스가 그 임계 영역에 진입할지를 결정한다. 제한된 대기는 프로그램이 임계 영역 진입 전 대기하는 시간을 제한한다.
  • 피터슨 방법 같은 임계 영역 문제에 대한 소프트웨어 해법은 현대 컴퓨터 아키텍쳐에서 잘 작동하지 않는다.
  • 임계 영역 문제에 대한 하드웨어 지원으로는 메모리 배리어, 하드웨어 명령어 (비교-및-교환 명령어 등), 원자적 변수 등이 있다.
  • 뮤텍스 락은 상호 배제를 보장하는데, 프로세스가 임계 영역에 들어가기 전에 락을 획득하고 임계 영역을 떠날 때 락을 반납한다.
  • 세마포어는 뮤텍스 락과 같이 상호 배제를 제공한다. 뮤텍스 락은 이진 변수이지만 세마포어는 정수값으로서 여러 동기화 문제를 해결할 수 있다.
  • 모니터는 고수준 프로세스 동기화를 제공하는 추상 자료형이다. 이는 프로세스가 특정 조건이 참값이 될 때까지 대기하는 조건 변수를 사용하며 그 조건이 참값이 될 때 다른 모니터에 이를 알린다.
  • 임계 영역 문제에 대한 해법은 데드락을 포함한 생존성 문제를 낳을 수 있다.
  • 임계 영역 문제를 풀고 프로세스의 활동을 동기화하기 위한 여러 도구들은 여러 경합 정도에 따라 평가될 수 있다. 어떤 환경에서는 어떤 도구들이 다른 도구들보다 더 잘 동작한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중