[운영체제] Ch6. 동기화 도구들

공룡책(운영체제)을 읽고 정리한 글입니다.

 

 

서론

지금까지 공부하면서 프로세스가 병행하게 또는 병렬로 실행될 수 있다는 것을 알 수 있었다.

CPU 스케줄러는 프로세스 사이에서 빠르게 오가며 각 프로세스를 병행 실행시킨다. 이는 현재 프로세스는 다른 프로세스가 스케줄링 되기 전까지만 CPU에서 실행됨을 의미한다.

 

프로세스의 실행중에 언제든지 인터럽트가 발생할 수 있으며, CPU코어는 언제든지 다른 프로세스의 명령어를 받아들일 수 있다. 

이러한 병행, 병렬성 때문에 데이터 무결성에 문제가 생기게 된다. 그래서 이 챕터에서는 어떤 문제가 발생하는지 알아볼 것이다.

 

간단한 예를 먼저 알아보자

프로세스 사이의 메모리 공유를 1차원 배열의 유한 버퍼를 이용해 구현했던 코드이다.

 

생산자 코드

생산자는 버퍼의 크기가 count와 같으면 버퍼가 가득 차 있음을 인지하고, 버퍼가 비워질 때까지 대기한다(while)

만약 count가 버퍼의 크기보다 작다면 count를 증가시키고 데이터를 버퍼에 입력한다.

 

소비자 코드

소비자는 count가 0이면 버퍼에 데이터가 없다고 인식하고 버퍼에 데이터가 들어올 때까지 대기한다(while)

만약 버퍼에 데이터가 있다면 데이터를 가져오고 count를 1 낮춘다.

 

 

위 코드들이 병행하게 실행되면 데이터 무결성에 문제가 생기게 된다.

버퍼의 크기가 10이고 count가 5라면 생산자와 소비자 모두 데이터를 쓰고, 읽을 수 있다.

count++의 동작은 레지스터상에서 다음과 같이 진행된다.

count--의 동작은 레지스터상에서 다음과 같이 진행된다.

 

count++와 count--가 병행하게 실행된다는 것은 위 문장들을 임의로 뒤섞어 각자의 순서에 맞게 실행하는 것과 동일하다.

 

따라서 위와 같은 순서로 실행된다면 생산자는 count==6이 될 것이고, 소비자는 count==4가 될 것이다.

 

 

이러한 부정확한 상태에 도달하는 것은 두 프로세스가 동시에 count변수를 조작하도록 허용했기 때문이다.

이처럼 동시에 여러개의 프로세스가 동일한 변수에 접근해서 조작하고, 그 실행 결과가 접근이 발생한 특정한 순서에 의존하는 현상을 경쟁 상황(race condition) 이라고 한다.

 

운영체제의 여러 부분에서 자원을 조작하기 때문에 위와 같은 상황은 빈번하게 일어날 수 있다.

따라서 다중 코어 시스템, 다중 스레드 시스템을 사용하게 되면 경쟁 상황이 일어나지 않도록 하는것은 매우 중요하다.

 

---

임계구역 문제 - Critical Section Problem

 

각 프로세스는 critical-section이라 불리는 코드 구역을 가지고 있다.

그 안에서는 적어도 하나 이상의 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다.

이 시스템의 중요한 특징은 한 프로세스가 자신의 임계구역의 코드를 실행하는 동안에는 다른 프로세스는 그들의 임계구역에 접근할 수 없게 한다는 것이다.

 

임계구역의 구성요소는 다음과 같다.

• 진입 구역(lock)
• critical-section
• 퇴출 구역(unlock)
• 나머지 구역

 

임계구역 문제에 대한 해결방안은 다음과 같은 요구를 충족해야 한다.

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

 

경쟁 상황이 발생할 수 있는 대표적인 예

P0와 P1프로세스는 fork()시스템 콜을 사용해서 자식 프로세스를 생성한다. 자식 프로세스에게 pid를 할당해주어야 하는데, next_available_pid에 경쟁 조건이 있다. 두 프로세스가 실행한 fork() 시스템 콜은 서로가 공유하는 변수인 next_available_pid에 접근할텐데 상호 배제(mutual exclusion)가 제공되지 않으면, 동일한 프로세스 식별자 번호가 두 개의 다른 프로세스에게 배정될 수 있다.

 

 

단일 코어 환경에서는 공유 변수를 수정하는 동안 인터럽트가 발생하는 것을 막을 수 있다면 임계구역 문제는 간단히 해결될 수 있다.

이렇게 하면 현재 실행중인 명령어들을 선점 없이 순서대로 실행될 수 있다는 것을 확신할 수 있다.

다른 명령어는 실행될 수 없으므로 공유 변수는 예기치 않게 수정되지 않는다.

 

하지만 이 해결 방법은 다중 처리기 환경에서 실현할 수 없다.

메시지가 모든 프로세스에 전달되므로 다중 처리기에서 인터럽트를 비활성화하면 시간이 많이 걸릴 수 있다. 이 메시지 전달은 각 임계구역으로의 진입을 지연시키고 시스템 효율성을 떨어뜨린다.

운영체제 내에서 임계구역을 다루기 위해서 선점형 커널과 비선점형 커널이 사용될 수 있다.
비선점형 커널을 사용하면 한 순간에 커널 안에서 실행 중인 프로세스는 하나밖에 없으므로 경쟁 상황을 염려할 필요가 없다.

 

그렇다면 왜 굳이 선점형 커널을 사용해서 경쟁 상황 문제를 안고 가는 것일까?

커널 모드 프로세스가 대기 중인 프로세스에 코어를 양도하기 전에 오랫동안 실행하지 않는 편이기 때문에 선점형 커널은 응답이 민첩하다. 그리고 선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적합하다.

 

---

Peterson의 해결안

 

임계구역에 대한 고전적인 소프트웨어적인 해결 방안을 살펴보자.

Peterson의 해결안은 현대 컴퓨터의 load, store같은 기본적인 기계어를 수행하는 방식에서는 올바른 실행을 보장하지 못한다. 하지만 임계구역 문제를 해결하기 위한 좋은 알고리즘 방식을 설명하고, 상호 배제, 진행, 한정된 대기의 요구조건을 중점으로 다루는 소프트웨어를 설계하는데 필요한 복잡성을 잘 설명해 준다.

 

Pi 가 임계구역에 진입하기 위해서 flag[i]를 true로 만든다.

그리고 turn 에 j를 입력해서 Pj가 임계구역에 진입을 원한다면 즉시 진입할 수 있게 설정해준다.

만약 flag[j]가 true이고, turn == j이면 Pj가 임계구역에 진입했다는 뜻이므로 while문을 돌면서 자신의 차례가 올 때까지 기다린다. 이를 spin-wait라고 한다.

임계구역이 종료되고, flag[i]를 false로 설정함으로서 Pj가 임계구역에 진입할 수 있도록 해준다.

 

위 코드는 상호 배제가 제대로 지켜진다.

- Pi와 Pj가 동시에 임계구역에 들어가려면 flag[i]와 flag[j]가 동시에 true가 되어야 한다. 그리고 turn의 값이 i이면서 동시에 j여야 한다. turn값은 반드시 하나의 값을 가지기 때문에 하나의 프로세스만 임계구역에 진입할 수 있다. 따라서 상호 배제 원리가 성립한다.

 

Peterson 해결안의 핵심은 현재 프로세스가 임계구역에 진입하기 전에 다른 프로세스에게 양보를 해준다는 것이다.

flag를 통해서 자신이 임계구역에 입장을 원한다는 표시를 남겨두고, turn을 상대 프로세스로 바꿔준다. 만약 상대 프로세스도 flag에 임계구역 입장을 원한다는 표시를 했다면 상대 프로세스가 먼저 실행이 된 후에 자신이 실행되게 된다.

 

Peterson 해결안의 단점은 최신 컴퓨터 아키텍처에서 작동한다고 보장할 수 없다는 것이다.

최신 프로세서 또는 컴파일러에서는 최적화를 위해서 서로 종속성이 없는 변수들은 순서가 뒤죽박죽으로 실행될 수 있게 한다.(굳이 정렬을 하지 않고 실행한다.)

 

Ex

 

두 스레드 간에 공유되는 데이터이다.

 

스레드 1이 위 코드를 수행한다.

 

스레드 2가 위 코드를 수행한다.

 

스레드 1에서는 100을 출력할것으로 보인다.

하지만 현대 아키텍쳐에서는 x와 flag 변수에 서로 종속성이 없다고 판단하여 flag = true 코드를 x = 100보다 먼저 실행시켜서 스레드 1에서 x값으로 0을 출력할 수 있다.

---

 

 

같은 의미로, 위에서 보았던 Peterson의 해결안의 임계경로 진입 지점의 코드의 순서가 바뀌는 경우를 나타내었다.

flag설정보다 turn 설정이 먼저 일어난다면, 두 프로세스가 동시에 임계 구역에 진입하게 될 수 있어서 상호 배제의 원리를 충족시키지 못함을 알 수 있다.

---

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

 

위에서 본 소프트웨어-기반 해결책은 최신 컴퓨터 아키텍처에서 작동하지 않을 수 있다.

그리고 소프트웨어-기반 해결책의 문제점들이 존재한다.

1. 상호 배제의 원리가 지켜지기 어렵다.
2. lock 변수의 확인을 위해서 spin-wait를 하는 방식은 CPU를 낭비하게 한다.

따라서 하드웨어가 지원하는 원자적인 구조를 가진 명령어가 필요하다.

 

1. 메모리 장벽

시스템은 명령어의 순서를 재정렬 할 수 있다는 것과 이러한 정책이 신뢰할 수 없는 데이터 상태로 이어질 수 있다는 것을 보았다.

컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 한다.

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

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

 

위에서 보았던 문제를 해결하기 위해서 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공할 수 있다. 이러한 명령어를 메모리 장벽 또는 메모리 펜스라고 한다. 

 

이전에 보았던 스레드 1에  메모리 장벽 연산을 추가하면 

flag값이 x보다 먼저 적재되도록 보장한다.

마찬가지로 스레드 2의 x와 flag 입력 사이에 메모리 장벽을 넣으면 flag 설정 이전에 x 설정이 먼저 실행되도록 할 수 있다.

 

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

 

2. 하드웨어 명령어

현대에는 두 워드(word)의 내용을 원자적으로 교환 할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.

 

 

먼저 가장 간단한 test_and_set 명령어이다.

이 함수는 가장 작은 실행 단위로 간주되어 실행 중간에 인터럽트가 발생하지 않는다.

 

target변수에 저장된 값을 가져와서 true로 설정하고, true로 설정하기 이전의 원래의 값을 반환하는 함수이다.

 

 

lock을 얻는 과정을 원자적으로 구현함으로써 상호 배제의 원리를 충족시켰다.

 

 

compare_and_swap 명령어(CAS)는 value의 값이 expected와 같으면 value를 new_value로 변경하고, 기존의 value 값을 반환하는 함수이다.

---

 

 

wating 배열의 원소는 false로 초기화되고 lock은 0으로 초기화 된다.

이 알고리즘이 상호 배제 조건을 만족시킨다는 것을 증명하기 위해서는 Pi가 임계구역에 진입하는 경우가 오직 waiting[i] == false 이든지 key == 0이라는 사실을 주의하여야 한다.

key값은 compare_and_swap() 명령어를 실행했을 경우에만 0이 된다. 그리고 인자로 넘겨진 lock의 값은 1이 될 것이다.

 

 

⌛️궁금한 점

처음으로 compare_and_swap()을 실행시키는 프로세스는 key == 0을 발견할 것이다.

만약 while문을 빠져나가기 전에 다른 스레드로 전환되면 바뀐 스레드에서는 compare_and_swap()을 실행하지만 lock의 값이 1이므로 key값은 1이 될 것이다. 따라서 다른 스레드에서는 while을 빠져나오지 못하게 되고, 다시 원래 스레드로 돌아와서도 key값이 1로 변했기 때문에 while문을 빠져나오지 못하게 될 것으로 생각된다.

위에서 주어진 예제 코드에 잘못이 있는 것인지 아니면 내가 잘못 생각한 건지 잘 모르겠다.

위 코드의 문제점은 무한 spin-wait상태가 지속될 수 있다는 점이라고 생각한다.

그래서 문제를 해결하기 위해서는 key 변수를 없애고 아래와 같은 코드로 바꿔야 atomic하게 while문을 올바르게 빠져나갈 수 있지 않을까 생각이 든다.

while(compare_and_swap(&lock, 0, 1) == 1);

위 코드에서는 compare_ans_swap()함수가 실행이 되면 lock을 처음 얻은 스레드만 즉시 while을 빠져나갈 수 있게 되므로 spin-wait문제가 발생하지 않을 것으로 보인다.

 

 

3. 원자적 변수

일반적으로 compare_ans_swap() 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않는다. 오히려 임계구역 문제를 해결하는 다른 도구를 구축하기 위한 기본 구성요소로 사용된다. 그러한 도구 중 하나는 원자적 변수(atomic variable)로, 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다.

 

정수 값을 증가시키거나 감소시키면 경쟁 조건이 발생할 수 있다.

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

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

 

예를 들어

increment(&sequence);

위 코드는 sequence를 증가시킨다.

 

여기서 increment() 함수는 CAS 명령어를 사용하여 구현된다.

 

원자적 변수는 모든 상황에서 race condition을 완벽히 해결할 수는 없다.

만약 A, B 두 개의 스레드가 count > 0을 기다리는 while 루틴을 spin-wait하는 상황이 있다고 가정하자.

count는 원자적 변수로서 올바르게 증가할 수 있지만, count가 증가하면서 A스레드에서 while문을 탈출하고 동시에 B스레드에서도 while문을 탈출하게 되면서 데이터의 무결성을 해칠 수 있다.

 

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

 

---

Mutex Locks

 

임계구역 문제를 해결하기 위한 가장 기초적인 상위 수준 소프트웨어 도구이다.

mutex라는 용어는 mutual exclusion의 축약 형태이다.

최소한 상호 배제 규칙만 지켜보자는 의미에서 mutex 라고 이름이 붙여졌다.

 

mutex lock의 기본 개념은 임계구역에 진입하기 위해서는 반드시 락을 획득해야 하고 임계구역을 빠져나올 때 락을 반환해야한다는 것이다.

lock을 획득하는 과정을 acquire, lock을 반납하는 과정을 release 라고 한다.

따라서 acquire, release 함수만 구현을 하면 되는데 이들 함수 내부에서 lock의 역할을 하는 것이 available이라는 boolean 형태의 변수이다.

 

실제 구현은 다음과 같이 할 수 있다.

available이 없으면 계속 기다리게 되고, available을 획득하면 while을 탈출하고 available을 false로 다시 바꾼다.

available을 true로 바꿔 주면서 다른 스레드들이 lock을 획득할 수 있게 해준다.

 

당연히 acquire내부의 동작과 release내부의 동작은 atomic하게 수행되어야 한다.

acquire 내부에서 while과 available 사이에 context swiching이 일어나면 문제가 생길 수 있다.

 

이들을 원자적으로 수행시키기 위해서는 CAS 같은 하드웨어 도구를 사용할 수도 있고, 인터럽트를 불가능하게 하는 방식을 사용할 수 있다.

 

Mutex Lock의 문제점

• Busy waiting(바쁜 대기) :
  다른 프로세스가 임계구역에 있을 때는 다른 스레드는 무한 루프를 돌게 된다.
  CPU를 비효율적으로 사용하게 된다.

 

Busy waiting을 하는 Mutex Lock을 Spinlock이라고 부른다.

Busy waiting이 단일 코어 시스템에서는 해당 CPU의 사용을 비효율적으로 만들 수 있지만, 다중 코어 시스템에서는 다른 코어 내부에서 Busy waiting을 함으로서 매우 적은 비용으로 context switching을 할 수 있다.

만약 Busy waiting이 없다면 모든 프로세스는 ready queue에 들어가게 되므로 context swiching 비용이 크게 발생할 것이다.

 

---

Semaphore

신호장치, 신호기 라는 뜻이다.

세마포를 S라고 하.

세마포는 정수 변수라고 할 수 있다. 세마포의 초기화를 어떻게 해주느냐에 따라서 wait(), signal()로 값을 설정할 수 있다.

wait() == P()
signal() == V()

 

wait() 함수는 S의 값을 감소시키는 작업이다. S의 값이 0이상인 경우에만 감소시킬 수 있다.

 

signal() 함수는 S값을 증가시키는 작업이다.

 

즉, 세마포는 S의 값을 초기에 설정해 놓고, S가 0이 되면 더 이상 다른 프로세스의 진입을 막는 것이다.(열쇠의 개수를 설정할 수 있다는 특징이 있다고 볼 수 있다.)

초기에 n개의 인스턴스를 가진 자원의 공유를 관리할 때 사용할 수 있다. (counting semaphore)

만약 S가 1이라면 mutex lock 처럼 사용할 수 있게 된다. (binary semaphore)

 

 

세마포의 사용법

병행하게 실행되는 P1과 P2 프로세스가 있다. P1이 실행할 명령문은 S1, P2가 실행할 명령문을 S2라고 하자. S2는 반드시 S1이 실행된 후에 실행되어야 한다.

P1과 P2는 0으로 초기화 된 synch라는 세마포를 공유한다. 

P1에 위와 같은 코드를 삽입한다.

S1이 실행된 이후에 signal 함수를 통해서 synch의 값을 1 증가시킨다.

P2에 위와 같은 코드를 삽입한다.

P1이후에 wait가 실행되면 synch의 값이 1 증가되었기 때문에 wait를 벗어날 수 있다.

 

따라서 S1이후에 S2가 실행됨을 보장할 수 있다.

 

 

지금까지 알아본 세마포는 여전히 Busy waiting이 발생하게 된다.

그래서 Busy waiting을 없애고 CPU의 스케줄링 기법을 활용하는 세마포를 알아보자.

 

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

 

세마포에서 가장 중요한 특성은 여러개의 프로세스나 스레드가 임계구역에 접근하는 것을 가능하게 해준다는 것이다.

그리고 세마포의 락이 사용가능해 진다면, 프로세스나 스레드에게 wakeup signal을 보내서 CPU 스케줄링에 의한 프로세스/스레드 활성화를 시킬 수 있다.

 

---

Monitor

 

Mutex Lock과 세마포어는 구현이 간단하지만, 발견하기 어려운 오류가 발생할 수 있다. 이는 개발자 입장에서 디버깅이 매우 힘들어진다는 단점이 된다. 예를 들어 프로그램의 크기가 커질 수록 signal()과 wait()의 순서가 잘못되는 경우와 같이 충분히 일어날 수 있지만 발견하지 못하면 심각해지는 오류가 발생할 가능성이 높아진다.

 

오류를 간단하게 처리하기 위한 한 가지 전략으로 모니터(Monitor)라는 동기화 도구를 사용할 수 있다.

 

모니터 형(monitor type) 이란?

• ADT(Abstract Data Type, 추상화된 데이터형)는 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어서 보호한다.
  쉽게 생각해서 Java의 class라고 생각할 수 있다. (OOP)
  
  
• 모니터 내부에서 프로그래머가 정의한 상호 배제가 보장되는, 일련의 연산자 집합을 포함하는 ADT이다.
  상태를 나타내는 여러 개의 변수를 가지고 있고, 그러한 변수들을 제어하는 연산자(메소드)를 가지고 있는 것이라고 볼 수 있다.
  
  

 

위 코드는 모니터에 대한 pseudo 코드이다.

monitor라는 자료형을 선언하고, 해당 블록 안에서 여러 메소드들을 선언해 주면, 이 함수들은 모니터 내부에서 동기화 된 함수로서 사용할 수 있음을 명시해 준다.

 

위 내용을 바탕으로 한 모니터의 구조를 그림으로 표현하면 아래와 같다.

공유데이터, 공유데이터를 초기화 해주는 코드, 공유데이터에 대해서 동기화 되어야 하는 명령어들을 OOP처럼 하나의 class로 선언해 준 것이다. 따라서 이러한 모니터 자료형을 사용한 스레드들이 entry queue 같은 곳에서 대기할 수 있게 된다.

 

하지만 이러한 구조체/class는 아직까지 동기화를 수행하기에 충분하지 않다. 따라서 자체적인 동기화를 제공하는 추가적인 condition 변수들이 필요하다.

condition형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()이다.

x.wait()를 호출한 프로세스는 다른 프로세스가 x.signal()을 호출할 때까지 일시중지 되어야 한다는 것을 의미한다.

 

x.signal() 연산이 프로세스 P에 의하여 호출될 때, 조건 x와 연관된 일시중지된 프로세스 Q가 있다고 가정해 보자.

만일 일시 중지된 프로세스 Q가 실행을 재개하도록 허용된다면, signal을 보낸 프로세스 P는 반드시 대기해야 한다.

 

 

signal와 wait에 관련된 두 가지 매커니즘

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

 

condition형 변수 x, y가 추가되었으므로 모니터를 사용하는 프로세스는 내부에서 다시 x와 관련된 프로세스가 될 지, y와 관련된 프로세스가 될 지를 선택할 수 있다. 그렇게 x와 y에 관련된 프로세스들은 서로의 영역을 침범하지 않고 동기화 될 수 있다.

 

위는 모니터의 구조를 간단히 나타낸 그림이다. 모니터는 공유 자원 + 공유 자원 접근함수로 이루어져 있고, 2개의 큐를 가지고 있다. 각각 mutual exclusion(상호배타) queue, conditional synchronization(조건동기) queue이다.

• 상호배타 큐는 말그대로 공유 자원에 하나의 프로세스만 진입하도록 하기 위한 큐이다.
• 조건동기 큐는 이미 공유자원을 사용하고 있는 프로세스가 특정한 호출 명령어인 wait()을 통해 조건동기 큐로 들어갈 수 있다.

조건동기 큐에 들어가 있는 프로세스는 공유자원을 사용하고 있는 다른 프로세스에 의해 깨워줄 수 있다. 이 역시 깨워주는 프로세스에서 특정한 호출 signal()을 해주며, 깨워주더라도 이미 공유자원을 사용하고 있는 프로세스가 해당 구역을 나가야 비로소 큐에 있던 프로세스가 실행된다.

 

모니터와 Java

모니터를 이해하기 위해서 Java의 동기화 도구를 이해한다면 모니터를 거의 이해했다고 볼 수 있다.

Java는 monitor-lock 또는 intrinsic-lock이라고 불리는 도구를 사용한다.

자바의 동기화 도구를 이해하기 위해서 synchronized와 wait, notify라는 키워드를 먼저 알아보자

 

 

synchronized

• 임계영역에 해당하는 코드 블록을 선언할 때 사용하는 자바 키워드이다.
• 해당 코드 블록(임계영역)에는 모니터락을 획득해야 진입이 가능하다.
• 모니터락을 가진 객체 인스턴스를 지정할 수 있다.
• 메소드에 선언하면 메소드 코드 블록 전체가 임계영역으로 지정된다.
  - 이때, 모니터락을 가진 객체 인스턴스는 this 객체 인스턴스이다.

synchronized를 사용하면 해당 구역은 임계구역이 되고, JVM이 lock의 acquire, release를 관리해준다.

 

 

wait() and notify()

java.lang.Object 클래스에 선언되어 있으므로 모든 자바 객체가 가진 메소드이다.

• 스레드가 어떤 객체의 wait() 메소드를 호출하면 해당 객체의 모니터락을 획득하기 위해 대기 상태로 진입한다.
• 스레드가 어떤 객체의 notify() 메소드를 호출하면 해당 객체 모니터에 대기중인 스레드 하나를 깨운다.
• notify()대신에 notifyAll()메소드를 호출하면 해당 객체 모니터에 대기중인 스레드 전부를 깨운다.

 

코드 예제

package problem;

public class Main {
    
    public static void main(String[] args) throws Exception{
        Thread[] threads = new Thread[5];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = new Thread(new MyRunnable());
            threads[i].start();
        }
        for (int i = 0; i < threads.length; i++) {
            threads[i].join();
        }
        System.out.println("Count : " + Counter.count);        
    }

    static class Counter{
        public static int count = 0;
        synchronized public static void increment() {
            count++;
        }
    }

    static class MyRunnable implements Runnable {
        @Override
        public void run() {
            for(int i = 0; i < 10000; i++){
                Counter.increment();
            }
        }
    }
}

 

synchronized라는 키워드를 사용해서 지정한 코드 블럭을 동기화 시켜준다는 개념이 모니터와 동일한 개념이다.

 

---

Liveness

앞서 살펴본 Mutex, Semaphore, Monitor 모두 상호 배제의 규칙만 지킬 뿐 Progress(deadlock)나 bounded-waiting같은 문제를 해결해 주지는 못한다.

라이브니스는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성을 말한다.

Deadlock 또는 Starvation같은 상황이 라이브니스 실패의 예가 된다.

 

 

Deadlock

교착 상태라고 부른다.

P0이 wait(S)를 실행하고, P1이 wati(Q)를 실행한다.

P0이 wait(Q)를 실행할 때, P0는 P1이 signal(Q)를 실행할 때까지 기다려야 한다.

마찬가지로, P1이 wait(S)를 실행할 때는 P0이 signal(S)를 실행할 때까지 기다려야 한다.

 

임계구역에 진입하기 위해서 S, Q처럼 두개의 세마포어를 획득해야 하는 경우에 대표적으로 이러한 문제가 발생할 수 있다.

프로그래머 한명이 모든 코드를 짠다면 발생하지 않을 수 있지만, P0와 P1프로세스를 서로 다른 프로그래머가 개발하는 경우는 매우 흔한 일이다. 따라서 세마포어를 획득하는 코드의 순서가 뒤바뀌게 되어 교착상태에 빠질 수 있는 것이다.

 

 

Priority Inversion

우선순위 역전이라고 부른다.

 

높은 우선순위를 가진 프로세스가 낮은 우선순위 프로세스의 작업이 끝날 때까지 공유 자원에 접근하지 못하는 현상이다.

높은 우선순위를 가진 프로세스가 커널 데이터를 읽거나 수정하기를 원할 때 발생할 수 있다. 

 

예를 들어서 알아보자.

 

프로세스 우선순위 (L < M < H)

프로세스 L이 프린터 작업을 하고있다. 이때 L보다 우선순위가 높은 H가 작업을 하기 위해 CPU를 선점하려고 한다.

일반적인 스케줄링에서는 H가 CPU를 선점하고 L는 wait큐에 들어가게 될 것이다.

그런데 만약 H가 프린터 작업에 대한 Lock을 획득해야만 Ready 큐에 들어갈 수 있는 경우라면 우선순위 역전이 발생하게 된다.

 

프로세스 M이 갑자기 ready 상태가 되어 L을 선점하려고 한다.

M에게는 lock을 획득해야 한다는 조건이 없어서 H보다 우선순위가 낮음에도 불구하고 CPU를 선점할 수 있게 된다. 

우선순위를 따른다면 H가 L을 선점할 수 있지만 L는 프린터Lock을 가지고 있는 상태이고, L과 M이 끝나기 전까지 Lock을 얻을 수 없으므로 H는 우선순위가 높아도 CPU를 선점할 수 없는 상황이 생기는 것이다.

 

 

우선순위 역전 문제를 해결하기 위해서 Priority-inheritance 프로토콜을 사용할 수 있다.

이 프로토콜에 따르면,

더 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 모든 프로세스는 문제가 된 자원의 사용이 끝날 때까지 더 높은 우선순위를 상속받는다. 자원의 사용이 끝나면 원래 우선순위로 되돌아 간다.

위의 예에서 프로세스 L은 임시로 프로세스 H의 우선순위를 상속받게 하고, 따라서 프로세스 M이 L의 실행을 선점하는 것을 방지한다.

프로세스 L이 자원의 사용을 마치면 상속받았던 우선순위를 방출하고 원래의 우선순위로 되돌아 간다.

L이 Lock을 반납했기 때문에 H가 M보다 먼저 실행될 수 있게 된다.

 

---

요약

• 경쟁 조건은 프로세스가 공유 데이터에 병행하게 접근할 때 발생하며 최종 결과는 병행 접근이 발생한 특정 순서에 따라 다르다. 경쟁 조건으로 인해 공유 데이터 값이 손상될 수 있다.
• 임계구역은 공유 데이터가 조작될 수 있으며, 경쟁 조건이 발생할 수 있는 코드 영역이다. 임계구역 문제는 데이터를 협력적으로 공유하기 위하여 자신의 활동을 동기화 하는 프로토콜을 설계하는 것이다.
  
  
• 임계구역 문제에 대한 해결책은 (1) 상호 배제, (2) 진행 및 (3) 한정된 대기의 세 가지 요구 사항을 충족해야 한다.
  상호 배제를 통해 한 번에 하나의 프로세스만 임계구역에서 활성화 된다.
  진행은 프로그램들이 다음에 어떤 프로세스가 임계구역에 들어갈 것인지 협력적으로 결정하리라는 것을 보장한다.
  한정된 대기는 프로그램이 자신의 임계구역에 들어가기 전에 대기하는 시간을 제한한다.
  
  
• Peterson의 해결안과 같은 임계구역 문제에 대한 소프트웨어 해결책은 최신 컴퓨터 아키텍처에서 제대로 작동하지 않는다. -> 컴파일러가 최적화를 위해 서로 종속적이지 않은 코드의 순서를 마음대로 결정하기 때문이다.
  
  
• 임계구역 문제에 대한 하드웨어 지원에는 메모리 장벽, compare_and_swap(CAS) 명령과 같은 하드웨어 명령 및 원자적 변수가 포함된다.
  
  
• Mutex 락은 프로세스가 임계구역에 들어가기 전에 락을 획득하고 임계구역에서 나올 때 락을 해제할 것을 요구함으로써 상호 배제를 제공한다.
  
  
• Mutex 락과 같이 세마포를 사용하여 상호 배제를 제공할 수 있다. 그러나 mutex 락은 락의 사용 여부를 나타내는 이진 값을 가지지만, 세마포는 정수 값을 가지므로 다양한 동기화 문제를 해결하는 데 사용될 수 있다.
  
  
• 모니터를 프로세스 동기화의 높은 수준의 형태를 제공하는 추상 데이터 유형이다. 모니터는 프로세스가 특정 조건이 true가 될 때까지 대기할 수 있게 하고 조건이 true가 되면 서로에게 신호를 보낼 수 있게 허용하는 조건 변수를 사용한다.
  
  
• 임계구역 문제에 대한 해결책은 교착 상태를 포함한 라이브니스 문제를 겪을 수 있다.
  
  
• 임계구역 문제를 해결하고 프로세스 활동을 동기화 하는 데 사용될 수 있는 여러 도구는 다양한 경합 정도에 따라 평가할 수 있다. 일부 도구는 특정 경합 상황에서 다른 도구들보다 더 잘 작동한다.

---

연습문제

---

1. '동기화를 위한 하드웨어 지원' 에서 인터럽트를 자주 비활성화하면 시스템 클록에 영향을 줄 수 있다고 언급했다. 왜 이런 일이 발생할 수 있고 그러한 영향을 최소화할 수 있는 방법에 대해 설명하라.

시스템 클록은 클록 인터럽트마다 갱신되면서 올바른 값을 유지한다. 그래서 오랫동안 인터럽트를 비활성화 한다면 시스템의 시간이 잘못될 가능성이 생긴다. 예를 들어, 매 클록 인터럽트마다 프로세스 내부의 시간이 업데이트되어, 프로세스를 계속 유지할지, 말지가 결정된다. 만약 클록 인터럽트가 비활성화 되면, 스케줄러가 정확한 시간을 할당할 수 없어서 문제가 발생하게 된다.

---

2. 바쁜 대기(busy waiting)라는 용어의 의미는 무엇인가? 운영체제에는 어떤 다른 대기가 있는가? 바쁜 대기를 완전히 피할 수 있는가?

다른 프로세스가 임계구역에 있을 때는 다른 프로세스는 무한 루프를 돌게 되어 CPU를 비효율적으로 사용하게 되는 현상이다.

 

다른 프로세스가 시그널을 보낼 때까지 대기하는 방법을 사용할 수 있다.

 

바쁜 대기를 피할 수는 있다. 하지만 바쁜 대기를 하지 않으면, 프로세스는 wait queue -> ready queue -> run 으로 이동하게 되므로 Context switch에 따른 오버헤드가 더 심할 수 있다.

---

3. 스핀락이 단일 프로세서 시스템에 적합하지 않지만 다중 처리기 시스템에서는 종종 사용되는 이유를 설명하라.

단일 프로세서 시스템에서 스핀락이 걸린다면 그 자체로 시스템이 봉쇄되는 현상이 일어나게 될 수 있다.

왜냐하면 단일 프로세서 시스템에서는 스핀락을 가진 프로세스가 스스로 락을 포기해야 다른 프로세스의 실행이 가능하기 때문이다. 따라서 락을 포기하지 않는 경우가 발생할 수 있기 때문에 단일 프로세서 시스템에는 적합하지 않다.

---

4. wait() 및 signal() 세마포 연산이 원자적으로 실행되지 않으면 상호 배제가 위반될 수 있음을 보여라

 

만약 두 개의 프로세스에서 동시에 wait()명령이 실행되었을 때 원자적으로 연산되지 않는다면 두 프로세스 모두 정수 값을 감소시키고 임계구역에 진입할 수 있게 된다.

---

5. 이진 세마포를 사용하여 n개의 프로세스 간에 상호 배제를 구현하는 방법을 설명하라.

do{
    wait(mutex);
    
    /* critical section */
    
    signal(mutex);
    
    /* remainder section */
    
} while (true);