CS/운영체제

[공룡책🦖] ch6 Synchronization Tools

설기똥꼬 2023. 7. 20. 14:57

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Background

CPU 스케줄러가 프로세스 사이를 오가며 모든 프로세스를 병행 실행시킨다.

이것은 한 프로세스가 다른 프로세스가 스케줄 되기 전에 일부분만 진행한다는 것을 의미하는데, 한 변수에 서로 의존하는 경우 값이 변경되면 무결성을 해치는 상황이 된다. 

 

협력 프로세스(Cooperating Process)

Cooperating process 간 비동기적 실행, 데이터 공유로 인한 무결성 문제를 해결해야 한다.

  • 서로에게 영향 주고 받음
  • 논리적 주소 공간을 공유하거나 데이터를 서로에게 공유 가능
  • 공유 데이터에 동시 접근하는 것은 데이터 불일치 야기
  • 협력 프로세스에서는 순서대로 실행할 수 있게끔 설정하는 것이 중요
  • 순서대로 실행한다면 논리적 주소 공간에서의 데이터 일관성을 유지 가능

 

Race Condition (경쟁 상황)

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

  • 실행의 결과는 어떤 순서에 따라 접근되는지에 따라 결정됨
  • 오로지 하나의 포르세스가 특정 시간에 공유 데이터를 다룰 수 있게끔 설정해야 함
    • 이를 보장하기 위해 프로세스가 어떤 식으로든 동기화되어 있어야 함

경쟁 상황이 생기지 않도록 하나의 프로세스만이 자료를 조작하도록 보장해야한다. 이런 보장을 위해 프로세스들을 동기화할 필요가 있다.

 

 

 

Critical Section Problem (임계 구역 문제)

프로세스 동기화에 관한 논의는 임계구역 문제로부터 시작한다.

각 프로세스는 임계구역이라는 코드 부분이 존재하고, 임계구역 코드 안에서는 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다. 

  • 시스템에 n개의 프로세스가 구성되어 있다고 가정했을 때 각각 프로세스의 코드 영역 → 크리티컬 섹션
  • 프로세스가 하나 이상의 다른 프로세스와 공유되는 데이터에 액세스하고 업데이트 가능
  • 하나의 프로세스가 크리티컬 섹션을 실행중일 때 다른 프로세스는 크리티컬 섹션에 진입할 수 없게 설정하는 것이 시스템의 중요한 특징 중 하나

 

Critical-Section Problem 해결 방안

1. 상호 배제 (mutual exclusion)

  • 임계구역 하나당 하나의 프로세스만 실행

 

2. 진행 (progress)

  • 현재 임계구역에서 실행 중인 프로세스가 없는데 임계구역에서 실행하려는 프로세스를 막아서는 안됨
  • 데드락 방지하기 위한 요구사항
  • 아무도 크리티컬 섹션에 진입하지 못하는 상황은 없어야 함

 

3. 한정된 대기 (bounded waiting)

  • 어떤 프로세스가 임계구역으로 들어가고자 하면 기다리는 시간에 대해 bound가 있어야 함
  • 기아 상황 방지하기 위한 요구사항
  • 동일 프로세스가 독점할 수 없게끔 함

 

 

Peterson's Solution

임계구역 문제를 해결하는 소프트웨어적 방법 중 하나이다.

임계구역과 나머지 구역을 번갈아가며 실행하는 두 개의 프로세스로 한정하고 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

  • 상호 배제, 진전, 한정 대기, 세 가지 요구 사항을 모두 충족하는 알고리즘
  • turn과 flag 변수로 크리티컬 섹션에 진입할 프로세스 혹은 스레드를 결정
    • turn : 누가 임계구역에 들어갈 차례인지 표시
    • flag : 임계구역에 들어갈 준비가 되었다는 의사 표시
int turn; // 임계구역으로 진입할 프로세스
boolean flag[2]; // 프로세스가 입계구역으로 진입할 준비가 됐으면 1

 

임계구역에 진입하기 위해서 P[i]는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다.

이렇게 하여 프로세스 j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.

만약 두 프로세스가 동시에 진입하기 원해도 한 프로세스만 배정이 지속되기 때문에 turn의 값이 누가 먼저 임계구역으로 진입할 것인지 결정하게 된다.

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

 

이 해결책이 올바르게 동작하는지 증명하기 위해 아래와 같은 사실을 보이면 된다.

 

1. mutual exclution (상호 배제)가 제대로 지켜지는가?

→ 동시에 실행되지만 turn 값에 따라서 임계 구역에 한 process만 진입하고 있으므로 만족한다. 한 process가 CS에 있는 한, 조건이 변하지 않고 유지되므로 나머지 process는 무조건 대기해야 한다.

 

2. Progress에 대한 요구 조건을 만족하는가?

3. Bounded-waiting이 한없이 길어지지 않는가?

→ 프로세스 Pi는 while문에서 대기하면서 변수 값을 변경하지 않으므로, Pj가 CS를 나오면서 flag[j]를 false로 변경할 때 CS에 진입한다. (1회 대기 → bounded waiting)

→ Pj가 CS를 나오면 다음 CS 진입 process는 대기 중인 Pi가 된다. (Pj가 다시 진입 X → progress)

 

Peterson의 해결책은 최신 컴퓨터에서는 작동하지 않는다. 시스템 성능을 향상시키기 위해 종속성이 없는 읽기/쓰기 작업을 재정렬할 수 있기 때문이다.

또한 Instruction들의 재배치로 인해 제대로 실행함을 보장할 수 없다.

상호 배제를 유지하는 방법은 적절한 동기화 도구를 사용하는 것이다.

 

 

Hardware Support for Synchronization

하드웨어를 사용하여 Critical-Section problem을 해결할 수 있다.

 

1. Memory Barriers

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

다음 명령 실행 전 모든 load와 store이 완료됨을 보장하고, reorder되더라도 후속 명령의 실행 전에 저장을 완료하고 그 결과를 모두에게 보여준다.

즉, 메모리 간 변경 사항을 전파해 명령어들의 순서를 보장한다.

 

 

2. Hardware Instructions - TAS, CAS

특별한 하드웨어 명령으로 원자성을 가진 명령을 추가하는 방법이다.

한 워드의 내용을 검사하고 변경하거나 두 워드의 내용을 원자적으로 교환할 수 있게 한다.

즉, 인터럽트 할 수 없는 하나의 단위로 간단하게 크리티컬 섹션을 해결할 수 있다.

  • test_and_set() : 제일 처음 process만 CS에 진입하도록 함 
  • compare_and_swap() : swapping에 기반하여 two words에 atomic하게 동작하도록 함

 

example code test_and_set

boolean test_and_set(boolean *target) {
    	boolean rv = *target;
        *target = true;
        
        return tv;
    }
    
    do {
    	while (test_and_set(&lock)); /* do nothing, context switching X */
		// 본인의 lock 을 true 로 만들고 진입한다.
        
		/* critical section */
        
        lock = false; // 크리티컬 섹션을 빠져나온 후 false로 만들어 다른 프로세스 진입을 허용
        
        /* remainer section */
    	
    } while (true);

 

example code compare_and_swap

int compare_and_swap(int *value, int expected, int new_value) {
    	int temp = *value;
        
        if (*value == expected)
        	*value = new_value;
          
        return tmp;
    }
    
    while (true) {
    	while (compare_and_swap(&lock, 0, 1) != 0);
        /* do nothing */
        
        /* critical section */
        
        lock = 0;
        
        /* remainer section */

 

 

3. Atomic Variables

원자적 변수는 기본 데이터 타입(integer, boolean)에 대해 원자적 연산을 제공한다.

경쟁 상황(race condition)이 일어나는 단일 변수에 대해 상호배제(mutual exclusion)를 보장해준다.

원자적 변수를 지원하는 시스템은 원자적 변수에 접근하고 조작하기 위한 기능뿐 아니라 특별한 원자적 데이터 유형을 제공한다.

 

 

 

Mutex Locks

임계구역 문제를 해결하기 위해 상위 수준의 소프트웨어 도구 중 가장 간단한 것이 Mutex Locks이다.

 

Mutex Locks는 Mutual exclusion으로, 임계구역을 보호하고 경쟁 조건을 방지하기 위해 사용한다.

즉 프로세스는 임계 구역에 들어가기 전에 반드시 lock을 획득해야 하고, 임계구역을 빠져나올 때 lock을 반환해야 한다. 여기서 lock을 획득하는 함수는 acquire()이고, lock을 반환하는 함수는 release()이다. 이 두 함수는 atomic하게 수행되어야 한다.

 

이 방식의 단점은 바쁜 대기(busy waiting)을 해야 한다.

한 프로세스가 임계 구역에 있는 동안 나머지 프로세스는 계속 조건을 확인하며 loop를 실행해야 한다. 이로 인해 CPU가 낭비된다.

 

여기에 나온 Mutex Locks은 스핀락(spinlock)이라고도 하는데, 락을 사용할 수 있을 떄까지 프로세스가 회전한다.

이때 스핀락은 context switch이 필요하지 않다.

 

 

 

Semaphore

임계구역 문제를 해결하기 위해 상위 수준의 소프트웨어 도구 중 가장 간단한 것이 Mutex Locks이다.

Semaphore는 Mutex와 유사하게 동작하지만 프로세스들이 자신의 행동을 더 정교하게 동기화할 수 있는 방법을 제공한다.

 

Semaphore는 wait()(STOP)과 signal()(GO)를 통해 process가 critical section에 진입하는 것을 관리한다.

이는 정수형 변수, 초기화를 제외하고 두 표준 atomic 연산으로만 접근된다. (wait, signal)

 

  • 공유 자원이 여러 개 있는 상황에서도 적용 가능한 synchronization tool
  • 여러 개의 process가 각각 공유 자원에 접근 가능
  • binary semaphore & counting semaphore
    • S : 임계 구역에 진입할 수 있는 process 개수 (사용 가능한 공유 자원의 개수)
    • signal() : 임계 구역 앞에서 기다리는 process에게 '이제 가도 좋다'고 신호를 주는 함수
    • wait() : 임계 구역에 들어가도 좋은지, 기다려야 할지 알려주는 함수

 

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

signal(S) {
	S++;
}

→ wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. 

 

 

Semaphore Usage

Counting semaphore

  • 값들은 제한 없는 영역을 가짐
  • 공유 자원이 N 개인 경우 (0이면 unavailable) 가용한 자원의 수로 초기화
    • wait() 연산 수행하여 세마포 값 줄임
    • signal() 연산 수행하여 프로세스가 자원 방출할 때 세마포 값 증가
    • count == 0이면 자원 모두 사용됨
    • count ≤ 0이면 프로세스는 block됨 

 

Binary semaphore

  • 0 또는 1의 값만 가능
  • 공유 자원이 1개인 경우 mutex lock 대신 사용 가능

 

Semaphore Implementation

Mutex Locks과 마찬가지로 Semaphore 연산 wait()과 signal() 역시 바쁜 대기 문제(busy waiting)를 가지고 있다.

따라서 wait()과 signal()을 아래와 같이 수정해야 한다. 또한 semaphore를 새롭게 정의한다.

 

  • wait() : semaphore 사용을 위해 기다리면 프로세스가 list에 추가됨
    • busy waiting 대신 프로세스가 스스로 suspend operation (sleep())을 통해 waiting queue로 이동하여 waiting state로 전환
    • 제어가 cpu 스케줄러로 이동 후 다음 프로세스 선택
  • signal() : 기다리던 process를 리스트에서 제거하고 wakeup시킴
    • S를 기다리던 suspend된 프로세스는 다른 프로세스의 signal()(wakeup())로 ready state로 전환되어 restart됨 

 

 

Monitors

Semaphore는 프로세스 간의 동기화를 위해 편리하고 효과적으로 쓸 수 있지만, 잘못 사용하면 특정 실행 순서에만 발생하는 오류라 발견하기 어려운 타이밍 오류를 야기할 수 있다.

그리고 두 프로세스가 동시에 임계구역 안에 있는 문제도 발생할 수 있다.

  • Timing errors in Semaphores : wait() → CS → signal() 순서로 진행되어야 하는데 프로세스 중 하나라도 순서를 지키지 않고 잘못 동작하는 경우 timing error가 발생
  • Semaphore나 mutex lock을 잘못 사용하면 error가 매우 쉽게 발생하는 구조

 

이를 비롯한 다양한 오류가 쉽게 생길 수 있기에 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이 바로 모니터다.

 

Monitor Usage

  • monitor : 공유 자원과 공유 자원에 접근하기 위한 interface(통로)를 묶어서 관리
  • monitor = 공유 자원 + 공유 자원 접근 함수 && 2개의 큐
    • mutual exclusion queue, conditional synchronization queue
    • 상호 배타 큐 : 공유 자원에 하나의 프로세스만 진입하도록 하기 위한 큐
    • 조건동기 큐 : 이미 공유 자원을 사용하고 있는 프로세스가 특정한 호출 wait()을 통해 조건동기 큐로 들어감 
  • abstract data type (ADT) : 특정 구현과 무관한 데이터 및 연산을 캡슐화함
  • "monitor는 ADT다" → instance의 state를 정의한 변수와 그 변수에 동작하는 함수 본체 선언
    • monitor type은 process가 직접 사용 금지 → interface 통해 접근 (캡슐화)
    • monitor 내에서 한번에 한 process만 active함을 보장
    • 동기화를 위해 직접 정의하여 condition 변수 사용 (process나 thread의 실행 순서 제어)

 

  • x.wait()
    • 특정 process가 아직 실행될 조건이 되지 않았을 때 해당 process를 suspend함
    • 다른 process가 x.signal()을 호출하기 전까지 suspend됨
  • x.signal()
    • 특정 process가 실행될 조건이 충족되었을 때 해당 process의 실행을 resume함

 

 

모니터 내 (P, Q)의 경쟁 해결방안

condition x와 관계되는 process P, Q가 있다고 할 때 P에서 x.signal()을 호출하면 condition x에 대해 기다리면서 Q는 suspend된다.

이때 Q가 resume된다면 P는 wait해야하고 만약 P가 wait하지 않으면 monitor 내 P, Q 두 개가 동시에 active된다.

 

해결방안

1. Signal and Wait (P가 대기)

P는 Q가 monitor를 떠날 때까지 wait한다. 혹은 다른 조건 y에 대해 wait한다.

2. Signal and Continue (Q가 대기)

Q는 P가 monitor를 떠날 때까지 wait한다. 혹은 다른 조건 y에 대해 wait한다.

3. 절충안

P가 signal()하고 즉시 monitor를 떠난 후 Q가 즉시 resume한다.

 

 

 

Liveness

synchronization tool의 사용 결과로 임계 구역에 들어가려는 process의 무한 대기가 발생할 가능성이 있다.

무한 대기는 progress와 bounded-waiting을 위반한다.

시스템은 progress를 보장해야한다.

 

  • Liveness : system이 process의 progress를 보장하기 위해서는 만족해야 하는 property set
  • Liveness failuere가 생기면 성능과 응답성이 안 좋아진다 

⇒ Deadlock, Priority Inversion

 

 

Deadlock

  • 둘 이상의 process가 대기 중인 process 중 하나에 의해 일어나는 event를 무한히 기다리는 상황
  • P0는 P1이 signal(S)하기를 기다리고, P1은 P0이 signal(Q)하기를 기다림

⇒ 둘 다 무한 대기

 

Deadlocked state (교착 상태) : set 내 모든 process가 다른 process에 의해 야기되는 이벤트를 기다림

 

Priority Inversion

  • 높은 순위의 process가 낮은 순위의 process가 사용 중인 kernel data에 접근하는 경우에 발생
  • kernel data는 lock으로 보호됨 → 높은 순위의 process가 대기해야 함

Priority-inheritance protocol

: 높은 순위 process가 필요로 하는 자원에 접근하는 모든 process는 자원의 사용이 끝날 때까지 높은 순위를 상속받고 종료 시 원래 우선 순위로 돌아감