운영체제론[10]: 스레드 동기화 (이론편)

공유데이터에 대한 동시 액세스는 데이터 불일치를 초래할 수 있기에 협력하는 프로세스의 순서대로 실행되도록 보장하는 스레드 동기화가 필요하다. => 임계구역을 설정해야한다!

 

각 프로세스는 임계구역에 접근하기 전에 권한을 요청하고, 임계구역이 끝나면 권한을 놓아준다.

임계구역 문제를 해결하기 위해 3가지 조건이 필요하다.

 

상호배제(mutual exclusion)

- 오류가 발생하지 않도록 한 스레드만 진입 가능

 

진행(progress)

- 임계구역에 들어간 프로세스가 없을 때 들어가려는 여러 프로세스가 있을 때 어떤 프로세스가 들어갈지 결정해야함

 

유한대기(bounded waiting)

- 한 번 임계구역에 들어간 프로세스는 그 다음에 다시 들어갈 때 제한을 둬야하고, 모든 스레드는 유한시간 내에 해당 임계구역에 들어갈 수 있어야 한다.

 

 



Critical-Section Handling in OS

커널에서 임계구역을 처리하는 방법에는 preemptive 또는 non-preemptive 방법이 있다.

preemptive - 커널모드에서 실행중인 프로세스의 선점을 허용한다

non-preemptive - 커널모드에서 실행이 종료될 때까지 실행되고, CPU를 자발적으로 양보할 수 있다.

 

일반적으로 응답속도와 실시간 프로그래밍에서 이점이 있는 preemptive 방식을 선호한다.

 

 

 

Peterson's Solution

- 현대 아키텍처에서는 보장 x

- 두 개의 프로세스 솔루션 (3개 이상에서는 불가능)

- load / store 명령어가 atomic임을 가정한다.

- 두 프로세스는 두 변수를 공유한다 - int turn, bool flag[2]

- turn 변수는 임계 구역에 진입할 차례가 누구인지를 나타냄

- flag 배열은 프로세스가 임계 구역에 진입할 준비가 되었는지를 나타냄, ex) flag[i]=true 는 프로세스 i가 준비됨

 

위 알고리즘은 세 가지 임계구역 조건이 충족된다.

 

하지만, 프로세서나 컴파일러가 성능을 개선하기 위해 작업을 재배치(reorder)할 수 있다.

스레드 간 데이터 의존성이 있을 때, 명령어를 재배치하면 멀티 스레드 환경에서는 문제가 발생할 수 있다.

 

 

Synchronization Hardware

많은 시스템에서 임계구역 코드를 구현하기 위한 하드웨어 자원을 제공한다.

단일 프로세서는 인터럽트를 비활성화 할 수 있다.

- 현재 실행중인 코드는 선점되지 않고 실행되지만 멀티 프로세서 시스템에서는 효율적이지 않다

  => 이 방법을 사용하는 OS는 일반적으로 넓은 확장이 불가능하다.

 

하드웨어에서 지원하는 세 가지 형태가 있다 (memory barriers, HW instructions, atomic variables)

 

Memory Barriers

메모리 모델은 컴퓨터 아키텍처가 애플리케이션에 제공하는 memory guarantees이다.

메모리 모델은 다음 중 하나일 수 있다.

- strongly ordered : 하나의 프로세서에서 발생한 메모리 수정을 즉시 모든 다른 프로세서에서 볼 수 있음

- weakly ordered : 하나의 프로세서에서 발생한 메모리 수정을 즉시 모든 다른 프로세서에서 볼 수 없을 수도 있음

 

메모리 배리어는 메모리의 변경 사항을 강제로 전파하는 명령어이다.

즉, 메모리 배리어가 실행되면 현재 진행중인 load/store가 종료된 후에 다른 load/store가 실행된다.

 

이 경우에, x=100이 flag=true보다 먼저 완료되는 것을 보장한다.

 

 

Hardware Instructions

특별한 하드웨어 명령어는 워드의 내용을 테스트하고 수정하거나, 두 개의 원드 대용을 원자적으로 교환할 수 있는 명령어이다.

boolean test_and_set(boolean *target)

 - target을 true로 설정, 변경 전 target 값 반환



int compare_and_swap(int *value, int expected, int new_value)

 - value와 expected 가 같으면 value를 new_value로 변경, 변경 전 value 반환

 

boolean compare_and_exchange(int *value, int *expected, int new_value)

- value와 expected가 같으면 value를 new로 바꾸고 true, 다르면 expected를 value로 바꾸고 false

 

 

Atomic Variables

원자 변수는 정수같은 기본 데이터 유형에 대한 원자적 업데이트를 제공해주는 도구이다.

increment(&sequence)라 하면, sequence를 1 증가시킨다.

 

 

 

Mutex Locks

하드웨어 기반 솔루션은 애플리케이션 프로그래머에게 접근하기 어렵다.

그래서 만들어진 소프트웨어 도구중 하나로 Mutex Locks이 있다.

 

lock을 먼저 획득(acquire())한 다음 lock을 해제(release())하여 임계 구역을 보호한다.

acquire()와 release()는 원자적이다.

 

busy waiting이 필요해서 spinlock이라고도 불리는데, CPU를 소모하지만 컨텍스트 스위칭이 필요 없어서 lock을 걸고 있는 시간이 두 개의 컨텍스트 스위칭을 하는 시간보다 적으면 spinlock이 유리하다.

 

 

 

Semaphore

mutex lock보다 더 복잡한 방법을 제공한다.

정수인 Semaphore S가 0보다 크면 임계구역에 들어갈 수 있다.

wait() : 임계구역에 접근

signal() : 임계구역에서 탈출

 

카운팅 세마포어 : 정수 값은 제한되지 않는 도메인에서 범위를 가짐

이진 세마포어 : 정수 값은 0과 1 사이의 범위를 가짐 - mutex lock과 같다.

위와 같은 방법으로 스레드 간의 순서가 필요할 때 사용할 수 있다.

 

 

동일한 세마포어에서 두 개의 프로세스가 동시에 wait()와 signal()을 실행하지 않도록 보장해야한다.

따라서 구현은 wait 및 signal 코드가 임계 구역에 배치된 임계 구역 문제가 된다.

-> 임계 구역에서 busy waiting이 발생할 수 있다.

임계 구역이 드물게 점유되면 busy waiting이 거의 없기에, 프로세스가 임계구역에 오래 머물러있지 않을 때 유리하다.

 

 

각 세마포어에는 대기 큐(waiting queue)가 있다.

대기 큐의 각 항목에는 (int)value, (pointer list : 리스트에서 다음 레코드를 가리키는 포인터)가 있다.

block : 해당 작업을 호출하는 프로세스를 적절한 대기 큐에 놓음

wakeup : 대기 큐에서 하나의 프로세스를 제거하고 준비 큐에 놓음

 

 

 

Monitors

프로세스 동기화에 대한 편리하고 효과적인 메커니즘을 제공하는 고수준 추상화이다.

추상 데이터 유형으로 내부 변수는 프로시저 내 코드에서만 접근 가능하다.

한 번에 하나의 프로세스만 모니터 내에서 활성화될 수 있다.

 

실행중인 프로세스가 어떠한 이유로 더 진행할 수 없으면 condition variable을 사용해 스스로 suspend할 수 있다.

 

condition variable은 개념적으로는 대기열의 이름으로, 두 가지의 작업이 가능하다.

x.wait() : 해당 작업을 호출한 프로세스는 x.signal() 이 호출될 때까지 대기

x.signal() : x.wait()를 호출한 프로세스 중 하나를 재개

 

condition variable로써 모니터를 사용하는 동안 다른 프로세스가 작업을 방해하지 않도록 보장한다.

다른 프로세스의 병행실행을 허용하려면 condition variable에 wait()를 호출함으로 가능하다.

따라서 프로세스가 preemption 위치를 스스로 지정할 수 있다.

 

 

만약 프로세스 P가 x.signal()을 호출하고 Q가 x.wait()에서 대기중이라면, Q와 P는 병행으로 실행될 수 없기에 두 옵션중 하나를 택해야한다. 이는 장단점이 있고, 언어 구현자가 결정할 수 있다.

Signal and wait - P가 Q를 기다림 - signal이 blocking으로 실행됨

Signal and continue - Q가 P를 기다림 - signal이 non-blocking으로 실행됨

 

Concurrent Pascal에서는 Signal and wait, 즉 P가 신호를 실행하고 즉시 모니터를 떠나고 Q가 재개된다.

Mesa, C#, Java를 비롯한 다른 언어에서 구현된다.

 

여러 프로세스가 condition variable x에 대기 중이고, x.signal이 실행된 경우 어떤 프로세스가 재개될까?

- 우선순위 번호 c가 있는 조건 대기 구조, 번호가 가장 낮은(우선순위가 높은) 프로세스가 다음으로 예약됨

우선순위 번호를 사용해서 경쟁하는 프로세스 간에 단일 리소스를 할당하고, 각 프로세스가 리소스를 사용할 최대 시간을 지정한다.

ResourceAllocator 유형의 인스턴스 R이라는 변수가 사용된다.

 

 

 

Liveness

프로세스가 동기화 도구를 획득하려 할 때 무기한 대기해야 할 수 있다. 무한 대기는 활성성(liveness) 실패의 예시이다.

활성성(liveness)는 프로세스가 진행되도록 보장하기 위해 시스템이 충족해야하는 속성 집합을 나타낸다.

 

데드락은 두 개 이상의 프로세스가 각자 다른 프로세스가 점유한 자원을 기다리며 무한대기하는 상태이다.

- 기아(Starvation) : 무기한 차단, 프로세스가 일시 중단된 세마포어 대기열에서 제거되지 않을 수 있다.

- 우선순위 역전 : 낮은 우선순위 프로세스가 높은 우선순위 프로세스가 필요로 하는 잠금을 보유하고 있는 스케줄링 문제

=> 우선순위 상속 프로토콜을 통해 해결된다!

 

Priority Inheritance Protocol

앞에서부터 우선순위가 높은 세 개의 프로세스 P1, P2, P3가 있다.

어떤 자원 R이 P3에 할당돼있고, P1이 이 자원에 접근하려하지만 락이 걸려있어 대기해야한다.

그러나 P2가 runnable 상태가 되어 P3을 선점하려하면 우선순위가 더 높은 P1이 간접적으로 자원에 접근할 수 없게 된다.

 

이를 방지하기 위해서 우선순위 상속 프로토콜을 사용한다. 이는 공유 자원에 접근하려는 가장 높은 우선순위 스레드의 우선순위를 현재 자원을 사용중인 스레드에 할당하는 것을 뜻한다. 따라서 자원의 현재 소유자는 자원을 획득하고자 하는 가장 높은 우선순위 스레드의 우선순위를 할당받는다.

즉, P1이 빠르게 리소스를 할당받을 수 있도록 리소스를 현재 사용중인 프로세스에게 P1의 우선순위를 상속한다.