[운영체제] 6. 스레드 동기화(thread synchronization)

해당 내용은 공룡책(Operating System Concepts 10th Ed: Abraham Silberschatz, Peter Baer Galvin, Greg Gagne)과 대학 강의를 기반으로 재구성하여 정리한 공부 내용입니다.
+) 6장부터는 사자책(명품 운영체제: 황기태)에 더 중점을 두고 전개됩니다.

1. 스레드 동기화의 필요성

P: 여러 스레드가 공유 데이터에 동시에 쓰기를 수행하면 공유 데이터가 훼손될 수 있다.

S: 스레드 동기화로, 한 스레드가 공유 데이터에 대한 사용을 마칠 때까지 다른 스레드가 접근하지 못하도록 제어한다.

 

스레드 동기화: 다수의 스레드가 공유 데이터를 동시에 쓰는 충돌 상황에서 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 기법

→ 한 스레드가 공유 데이터에 대해 배타적이고 독점적으로 접근하도록 허용되도록 함

→ 공유 데이터를 사용하려고 다수의 스레드가 경쟁하는 경우, 먼저 접근한 스레드가 공유 데이터를 배타적으로 사용하도록 다른 스레드가 접근하지 못하게 상호 협력함

 

임계구역(critical section): 사용자가 작성한 프로그램 중 공유 데이터에 접근하는 코드 블록

상호배제(mutual exclusion): 임계구역에 먼저 진입한 스레드가 임계구역의 실행을 끝낼 때까지 다른 스레드가 접근하지 못하도록 보장

 

2. 상호배제

상호배제 위치

공유 데이터를 다루는 멀티스레드 프로그램의 구성

→ 임계구역 전후에 상호배제 코드 작성(각각 진입코드와 진출코드)

 

• 일반 코드(non-critical 코드): 멀티스레드 응용프로그램에서 공유 데이터를 액세스하지 않는 코드 부분
• 임계구역 진입코드(entry 코드): 현재 임계구역을 이미 실행 중인 스레드가 있는지 검사하고, 없는 경우 다른 스레드가 들어오지 못하도록 조치하며, 이미 진입한 스레드가 있는 경우 진입한 스레드가 임계구역 실행을 끝내고 exit 코드를 실행할 때까지 현재 스레드를 대기시킴
• 임계구역 진출코드(exit 코드): entry 코드에서 대기 중인 스레드가 임계구역에 진입할 수 있도록 진입코드에서 취한 조치를 해제함
• 임계구역 코드(critical 코드): 한 번에 한 스레드만 실행하도록 보장

임계구역은 짧을수록 좋기 때문에, 공유 데이터를 액세스하는 최소한의 코드를 임계구역으로 만드는 것이 바람직하다.

 

세 가지 요구 조건 충족이 필요

1. mutual exclusion: 프로세스 1이 임계구역에서 실행되면, 프로세스 2는 임계구역에서 실행될 수 없다.

2. progress: 임계구역에서 실행되는 프로세스가 없고, 임계구역으로 진입하려고 하는 프로세스들이 있다면 진입할 프로세스를 결정하여 실행해야 한다. (무한정 선택을 미룰 수 X)

3. bounded waiting: 프로세스가 임계구역에 진입하려고 요청한 후부터 요청이 허용될 때까지 다른 프로세스들이 임계구역에 진입하도록 허용하는 횟수에 한계가 있어야 한다. (무한정 대기할 수 X, 기아 방지)

 

상호배제 구현

임계구역의 entry 코드와 exit 코드를 어떻게 구현하느냐의 문제

 

상호배제 방법의 분류

1) 소프트웨어적 방법: Peterson's 알고리즘 등

2) 하드웨어적 방법: 인터럽트 서비스 금지, 원자명령 활용 → 원자명령 활용 방법을 현재 사용 중!

 

Peterson's Solution

두 개의 프로세스 동기화 목적으로만 사용

load, store 같은 기본 명령어를 사용하기 때문에 올바른 실행 보장을 못함. 원자성이 있다고 가정하고 생각

변수 turn은 임계구역으로 진입할 순번. turn이 i이면 프로세스 Pi가 실행될 수 있다.

boolean flag 배열은 해당 프로세스가 임계구역으로 진입할 준비가 되었으면 true

 

만약 프로세스 i와 j가 동시에 진입하고자 하여도, turn은 마지막으로 수정된 하나의 값으로 결정된다.

두 프로세스 중 하나는 반드시 진입하며, Bound가 최대 1이다.

조건 1, 2, 3 만족

그러나 현대 컴퓨터에서는 읽고 쓰는 명령의 원자성을 보장하지 않으므로 실제로 잘 동작할 거라는 보장이 되지 않는다.

명령어 재배치, 메모리 버스 인터럽트, 하이퍼 스레딩이나 멀티 스레딩 등을 지원하기 때문

 

하드웨어적 방법 (1) 인터럽트 서비스 금지

임계구역으로 진입할 때 entry 코드에서 인터럽트 서비스를 금지하고, exit 코드에서 인터럽트 서비스를 허용하는 CPU 명령을 실행하는 방법

→ 임계구역을 실행하고 있는 동안 인터럽트 미발생 → 스레드가 선점(preemption)되지 않음

 

입출력 장치나 타이머가 인터럽트를 걸지 못하게 하는 것은 불가능

→ 인터럽트를 걸 수 있게 허용, 대신 임계구역 실행하는 동안에는 발생한 인터럽트를 CPU가 서비스하지 못하게 하고, 임계구역을 벗어난 다음에 서비스하도록 함

 

cli: entry 코드에서 인터럽트 서비스 금지 명령(clear interrupt flag)

- CPU 내부 인터럽트 플래그를 0으로 리셋 → 인터럽트를 무시하고 현재 작업을 계속 수행하게 함

 

sti: exit 코드에서 인터럽트 서비스 허용 명령(set interupt flag)

- CPU 내부 인터럽트 플래그를 1로 설정 → 인터럽트가 발생하면 CPU가 하던 일을 멈추고 인터럽트 서비스 루틴을 실행하게 함

 

이 방법에서 생기는 2가지 문제

1. 임계구역을 실행하는 동안 모든 인터럽트가 무시됨 → 임계구역의 실행시간이 길어지게 되면 중요한 인터럽트 서비스 루틴이 제때 실행되지 못할 수 있음

2. 인터럽트 서비스를 금지하는 방법은 멀티코어 등 다중 CPU 시스템에서는 활용할 수 없음. 다른 코어의 인터럽트 서비스까지 금지시키지는 못하기 때문.

 

하드웨어적 방법 (2) 메모리 장벽

메모리 모델: 메모리 접근 시 보장되는 사항을 결정한 방식

일반적으로 두 가지 모델 중 하나에 속함

1. Strongly Ordered: 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임

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

 

메모리 장벽: 컴퓨터 아키텍처에서 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 통해 다른 프로세서에서 실행중인 스레드에 메모리 변경 사항이 보이는 것을 보장하는 것. 일종의 동기화 메커니즘이다.

 

즉 메모리 장벽을 사용하면 메모리 장벽 이전의 메모리 연산이 이후 연산보다 먼저 완료되도록 보장하여 멀티스레드 환경에서 데이터 일관성과 순서를 유지하는 데 돕는다.

다중 스레드의 실행 순서를 보장하기 위해 메모리 장벽 사용

실행 순서의 불확실성을 방지

 

하드웨어적 방법 (3) 원자명령 사용

원자명령 없이 lock 변수를 이용한 상호배제 시도

실패 원인:

(lock 변수를 두고, 0과 1 값을 이용해 0이면 1로 바꾸고 진입 후, 진출 시 0으로 바꾸는 식으로 상호배제)

entry 코드의 문제! → lock 변수 값을 CPU 레지스터에 읽어놓는 명령과 lock 변수를 1로 바꾸는 2개의 명령이 하나의 단위로 실행되지 않았기 때문이다.

 

솔루션:

원자명령(atomic instruction) = TSL(Test and Set Lock)명령: 두 명령 사이에 컨텍스트 스위칭이 일어나지 않도록 하나의 명령으로 만드는 것

 

소프트웨어적 방식으로 설명:

TAS 방식(Test And Set)

lock이 false였다면, false를 반환하고 lock을 true(잠김)로 설정

 

CAS 방식(Compare And Swap)

intel x86 아키텍처에서는 CMPXCHG(Compare and Exchange) 명령어를 사용

공유 변수의 내용을 예상값과 비교하여, 일치할 때에만 새 값으로 교체

읽기-비교-조건부쓰기 작업을 단일 연산으로 수행해 원자성 보장

 

TAS vs CAS

TAS는 단순한 게 장점

CAS는 복잡한 시나리오에 적용하기 좋음

 

3. 멀티스레드 동기화 기법

= 동기화 프리미티브(synchronization primitive)

스레드들이 문제없이 공유 자원을 활용하도록 도움

스레드 라이브러리나 시스템 호출에 의해 제공

상호배제를 위해 암시적으로 원자명령을 사용

대표 기법 3가지: 1) 락 방식의 뮤텍스 2) 락 방식의 스핀락 3) wait-signal 방식의 세마포

 

뮤텍스(mutex)

= blocking lock = sleep-waiting lock (락이 풀릴 때까지 스레드가 블록 상태로 대기 큐에서 잠을 자서)

locked/unlocked 중 한 상태를 가지는 락 변수를 이용해 한 스레드만 임계구역에 진입시키고 다른 스레드들을 큐에 대기시키는 기법

 

뮤텍스 기법의 구성

구성 요소: 락 변수, lock/unlock 연산, 대기 큐

• 락 변수

락 변수를 lock으로 만든 스레드만이 임계구역을 실행할 수 있다.

락 변수를 잠김으로 만드는 것 = 락을 잠근다, 락을 소유한다 / 열림으로 만드는 것 = 락을 연다, 락을 푼다

• lock/unlock 연산(원자명령 사용)
  • lock 연산: entry 코드. 락이 잠겨 있으면 현재 스레드를 블록 상태로 만들어 대기 큐에 삽입하고, 열린 상태이면 락을 잠그고 임계구역으로 진입하게 함.
  • unlock 연산: exit 코드. 락을 열림 상태로 바꾸고 대기 큐에 있는 스레드 하나를 깨워 준비 상태로 만든다.

 

뮤텍스를 활용한 스레드 동기화 과정

 

뮤텍스의 특징

임계구역의 실행 시간이 짧은 경우 비효율적. 락이 잠겨 있는 시간보다 스레드가 잠자고 깨는데 걸리는 시간 낭비가 더 크기 때문!(2번의 컨텍스트 스위칭 발생)

 

POSIX 표준 pthread 라이브러리의 뮤텍스

뮤텍스락 변수: pthread_mutex_t lock;

조작 함수들: pthread_mutex_init(), lock(), unlock(), destroy()

대기 큐는 라이브러리 내부에서 생성, 유지되어 사용자에게 보이지 않음

 

스핀락(spinlock)

= busy-waiting lock, aggressive mutex

뮤텍스와 같이 락 기반이지만, 대기 큐가 없는 방법

스핀락의 구성

구성 요소: 락 변수, lock/unlock 연산

• 락 변수

스핀락이라 부름. 스핀락을 소유한 한 개의 스레드만 임계구역에 진입

• lock/unlock 연산(원자명령 사용)
  • lock 연산: entry 코드. 락 변수가 열림 상태이면 잠김 상태로 만들고 스레드가 임계구역에 들어가게 함. 락이 잠겨 있으면 열릴 때까지 락 검사를 무한 반복하고, 락이 열리면 즉각 락을 잠그고 임계구역에 들어가게 함.
  • unlock 연산: 락을 열림으로 변경

lock 연산은 락이 잠겨 있으면 무한 루프를 돌면서 락이 풀릴 때까지 검사하다가 타임 슬라이스가 소진될 때 스레드가 컨텍스트 스위칭되고, 다시 스케줄되면 다시 락이 풀릴 때까지 검사를 반복한다.

 

스핀락의 동기화 과정

스핀락의 특징

1. 뮤텍스 기법의 busy-waiting 모형이다.

2. 단일 CPU를 가진 운영체제에서 매우 비효율적이다.

→ CPU가 하나라면 락을 가진 T1이 중단되고 T2를 스케줄 → 락을 소유한 T1이 실행되어야 락이 열리는데, 의미 없이 타임 슬라이스가 소진될 때까지 CPU를 락 검사에 사용하고, T1의 실행을 빼앗음

∴ 멀티 코어 CPU에 매우 효과적

3. 임계구역 코드가 짧아 락이 빨리 열리는 응용 프로그램에 매우 효과적. 뮤텍스와 달리 컨텍스트 스위칭이나 스케줄링이 필요없다.

4. 스레드들이 락을 얻기 위해 무한 경쟁하기 때문에, 어떤 스레드는 기아가 발생할 수 있다. 또, 락을 잠근 스레드가 락을 열지 않고 종료하거나 코드 오류로 무한 루프를 돌게 되면, 다른 스레드들은 무한 대기하며 CPU를 사용하게 된다.

 

pthread 라이브러리의 스핀락

스핀락 변수 pthread_spinlock_t lock;

조작 함수들: pthread_spin_init(), lock(), unlock(), destroy()

 

세마포(semaphore)

세마포: n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원 관리 기법

세마포의 구성 요소:

1) 자원 n개

2) 대기 큐(자원을 할당받지 못한 스레드가 잠자는 곳)

3) counter 변수: 사용가능한 자원의 개수를 나타내는 정수형 변수. 자원 개수 n으로 초기화되며, 음수이면 자원을 기다리는 스레드의 개수. Semaphore S

4) P/V 연산(= wait/signal 연산): P 연산은 자원 요청 시, V 연산은 자원 반환 시 실행

 

세마포의 구조

스레드 수 > 자원 개수일 때 유용!

 

P/V 연산

- P 연산: 스레드에게 자원 사용을 허가함(S--)

- V 연산: 스레드가 자원 사용이 끝났음을 세마포에 알림(S++)

 

자원을 할당받지 못하는 스레드를 다루는 방법에 따라 1) 수면 대기 세마포 2) 바쁜 대기 세마포로 분류

1) 수면 대기(sleep-wait) 세마포: 카운터 변수 Semaphore S가 값과 큐를 가리키는 포인터로 구성되어 P 연산 중 자원 사용을 허가받지 못한 스레드를 대기 큐에서 재우고, V 연산에서 가용한 자원이 생기면 스레드를 깨워 자원 사용을 허락함

2) 바쁜 대기(busy-wait) 세마포: P 연산에서 가용 자원이 생길 때까지 무한 루프로 검사하다가 V 연산에 의해 가용 자원이 생기면 P 연산을 통과해 자원을 획득함(대기 큐가 없음!)

 

pthread 라이브러리의 세마포

세마포 구조체: sem_t s;

조작 함수들: sem_init(), destory(), wait() = 수면 대기 세마포, trywait() = 바쁜 대기 세마포, post(), getvalue()

여기에서는 counter 변수가 음수가 되지 않고, 가용 자원이 없는 경우 0으로 유지된다.

 

이진 세마포

관리 자원의 개수에 따라

1) 카운터 세마포(자원이 여러 개인 경우), 2) 이진 세마포(자원이 1개인 경우)

 

이진 세마포의 구성 요소:
세마포 변수 S: 0과 1 중 하나를 가지는 변수. 1로 초기화 * 뮤텍스 락과 유사하게 동작한다!

대기 큐

P 연산: S를 1 감소시키고 0보다 작으면 대기 큐에서 재우고, 0보다 크거나 같으면 자원 사용 코드를 실행한다.

V 연산: S를 1 증가시키고 0보다 크면 그냥 리턴, 0보다 작거나 같으면 대기 큐의 스레드 하나를 깨운다.

 

모니터(Monitors)

세마포나 뮤텍스락의 경우 프로그래머가 잘못 사용하면 오류가 쉽게 발생

간단한 동기화 도구를 통합한 고급 언어 구조체로 모니터 도입

 

모니터: 상호 배제가 보장되는 ADT

모니터 타입의 변수를 사용

모니터 내에서는 항상 하나의 프로세스만이 활성화되도록 보장한다.

자동적으로 waiting and signaling을 수행하여 동기화 에러의 부담을 줄인다.

프로그래머가 wait이나 signal같은 저수준 동기화 연산을 직접 코딩하지 않아도 됨

 

그러나 동기화 기법에 대해서는 별도의 condition 타입을 정의해야 함

모니터가 상호 배제는 보장하지만, 특정 조건이 만족될 때까지 프로세스가 모니터 안에서 기다려야 하는 경우가 존재하기 때문

ex. 생산자는 버퍼가 가득 차면 기다려야 함

 

Condition 변수 x, y를 모니터 내부에 정의하고 wait()과 signal() 메소드를 사용

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

x.signal(): 하나의 일시 중지 프로세스를 재개

 

만약 P가 모니터 안에서 x.signal()을 호출하여 Q가 깨어나야 하는데 P도 아직 모니터에 있다면, 모니터 안에 하나의 프로세스만 있을 수 있으므로 둘 중 하나만 실행되고 하나는 기다려야 함

두 가지 처리 방식:

1. signal and wait: 신호를 보낸 P가 기다리면 Q는 즉시 수행 재개 → 시그널로 깨어난 Q가 모니터를 떠날 때까지 또는 다른 조건을 기다림

2. signal and continue: 깨어난 Q가 기다리면 P는 signal을 보내고 계속 실행 → Q는 P가 모니터를 떠날 때까지 또는 다른 조건을 기다림

 

세마포를 통해 조건 변수 기능 구현 가능

signal-and-wait 기법을 사용

 

동기화 이슈: 우선순위 역전

Liveness: 프로세스가 실행 수명 주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성

다양한 형태의 라이브니스 실패 존재 ex. 무한 루프

뮤텍스 락이나 세마포 같은 툴로 상호 배제를 구현하려 할 때 발생 가능

라이브니스 실패로 이어질 수 있는 상황 1. 교착상태 2. 우선순위 역전

 

우선순위 역전(priority inversion): 스레드 동기화에 의해 우선순위가 높은 스레드가 순위가 낮은 스레드보다 늦게 실행되는 문제

해결책

1. 우선순위 올림(priority ceiling): 스레드가 공유 자원을 소유하게 될 때 일시적으로 미리 정해진 우선순위로 높이는 방법

위 그림에서, T1이 T3보다 높게 되면 T2에 의해 선점되지 않고 빨리 실행된다.

공유 자원에 대한 액세스가 끝나면 원래 우선순위로 되돌린다.

 

2. 우선순위 상속(priority inheritance): 스레드가 공유 자원을 획득하고 실행하는 동안 높은 순위의 스레드가 공유 자원을 요청하면, 낮은 순위의 스레드 우선순위를 요청한 스레드보다 높게 변경하여 계속 실행시킨다.

공유 자원에 대한 사용이 끝나면 원래 우선순위로 되돌린다.

위 그림에서, T1이 실행 중일 때 T3이 자원을 요청하므로 T1을 T3보다 높은 우선순위로 변경해 계속 실행시킨다.

 

But, 이 두 방법 모두 쉽지 않고 오버헤드도 존재한다.

 

4. 생산자 소비자 문제(유한 버퍼 문제)

멀티스레드 응용프로그램에서 발생하는 전형적인 동기화 문제

문제 3가지:

1. 생산자들과 소비자들의 공유버퍼 사용에 대한 상호배제 문제

2. 비어 있는 공유버퍼를 소비자가 읽는 문제

3. 꽉 찬 공유버퍼에 생산자가 쓰는 문제

 

해결책

상호배제 해결

생산자나 소비자가 여러 개 있는 경우 생산자들 사이 또는 소비자들 사이에 발생 가능

임계구역에 대한 상호배제를 뮤텍스나 세마포를 이용해 작성

 

비어있는 공유버퍼 문제 해결

여러 개의 저장 공간이 있는 공유 버퍼에서, 소비자 스레드는 공유 버퍼 내 공간에 하나라도 데이터가 기록될 때까지 대기하고, 생산자 스레드가 데이터를 기록하면 소비자 스레드를 깨워 읽게 만든다.

→ 소비자 스레드가 wait하고, 생산자 스레드가 signal을 보내는 방식이므로 스레드 동기화를 위해 세마포가 적절

counter 값은 읽기 가능한 버퍼의 개수. 소비자가 P 연산 실행, 생산자가 V 연산 실행

 

꽉 찬 공유버퍼 문제 해결

생산자 스레드는 공유버퍼에 기록하기 전에 반드시 버퍼가 꽉 차있는지 확인해야 하고, 버퍼가 꽉 차있다면 소비자 스레드가 하나의 버퍼라도 비울 때까지 기다리며, 소비자 스레드는 버퍼에서 데이터를 읽은 후 생산자 스레드를 깨워 데이터를 쓸 수 있게 해야 한다.

→ counter 값을 쓰기 가능한 버퍼의 개수로 갖는 세마포 사용

생산자가 P 연산 실행, 소비자가 V 연산 실행

 

Bounded-Buffer Problem의 해결:

1. semaphore mutex = 1; 이진 세마포. 버퍼 풀에 접근하기 위한 상호 배제 기능 제공

2. semaphore empty = n; 비어 있는 버퍼의 수 기록. 

3. semaphore full = 0; 꽉 찬 버퍼의 수 기록.

 

생산자와 소비자 코드가 대칭적으로 나타남

5. Readers-Writers 문제

Readers: 오직 데이터에 대해 읽기만 함

Writers: 읽고 쓰는 것을 모두 하여 데이터를 갱신함

 

다수의 reader가 동시에 하나의 공유 데이터를 읽는데, 하나의 writer가 동시에 데이터베이스에 접근하는 문제

writer가 쓰는 동안 공유 데이터에 대한 배타적 접근 권한이 있어야 함(쓰기 작업은 반드시 하나의 writer만 가능하게 해야 함)

즉 다수의 reader가 동시에 데이터를 읽을 수 있게 허용하면서, 단 하나의 writer만 배타적으로 접근해 수정을 지원해야 함

 

 

해결책

semaphore rw_mutex = 1; 한번에 하나의 writer만 데이터셋에 접근 보장

semaphore mutex = 1; 아래 read_count 변수 동기화를 위해 사용

int read_count = 0; 현재 데이터셋을 읽고 있는 리더의 수

wait(rw_mutex): writer의 접근 요청

signal(rw_mutex): 쓰기 작업 후 writer의 자원 해제

 

첫번째 해결안: reader에게 우선순위를 주는 것; writer의 기아 현상 발생 가능

두번째 해결안: writer에게 우선순위를 주는 것; reader의 기아 현상 발생 가능