[운영체제] 스레드 동기화

스레드 동기화의 필요성

- 다수의 스레드가 동시에 공유 데이터에 쓰기를 접근하면 공유데이터가 훼손되는 문제 발생 가능

- 두 스레드가 동시에 공유데이터에 쓰는 경우 → 공유데이터 훼손 가능

 

스레드 동기화란?

- 공유데이터에 대한 다수의 스레드가 동시에 접근할 때 공유데이터가 훼손되지 않게 하는 기법

공유데이터 접근 문제의 해결책

- 문제점 = 여러 스레드가 공유변수에 접근할 때, 공유 데이터 훼손

- 해결책 = 스레드 동기화 : 한 스레드가 공유데이터 사용을 마칠 때까지, 다른 스레드가 공유데이터에 접근하지 못하도록 제어

- 멀티스레드의 경쟁상황은 매우 자주 발생하며 다중 코어에서 더욱 조심해야한다.

 

스레드 동기화와 관련된 2가지 중요 개념

임계구역(critical section)

- 공유 데이터에 접근하는 프로그램 코드들

상호배제(mutual exclusion)

- 임계구역을 오직 한 스레드만 배타적 독점적으로 사용하도록 하는 기술

 

상호 배제를 포함하는 전형적인 프로그램 모습

1. 일반코드 (≒지역변수)

- 공유 데이터를 액세스하지 않는 코드

 

2. 임계구역 진입 코드

- 임계구역에 진입하기 전 필요한 코드 블록

- 현재 임계구역을 실행 중인 스레드가 있는지 검사

 

3. 임계구역 코드

 

4. 임계구역 진출 코드

- 임계구역을 마칠 때 필요한 코드

- 대기중인 스레드가 임계구역에 진입할 수 있도록, 진입 코드에서 취한 조치 해제

 

상호 배제 구현

구현 목표 - 임계구역에 오직 1개의 스레드만 진입

구현 방법

1. 소프트웨어적 방법 : Peterson's 알고리즘 등 (시험에 안나옴)

2. 하드웨어적 방법 : 하드웨어의 도움을 받는 방법

- 인터럽트 서비스 금지 : 인터럽트 서비스를 금지하거나 허용하는 CPU 명령 사용

• 문제점 : 모든 인터럽트가 무시되는 문제 발생
• 멀티 코어 CPU나 다중 CPU를 가진 시스템에서 활용 불가

- 원자 명령 사용 : 원자 명령은 CPU 명령임, 오늘날 상호배제 구현에 사용하는 방법

 

단순 lock 변수로 상호배제 시도

- locking/unlocking 방식으로 임계구역의 entry/exit 코드 작성하면 상호배제가 가능할까?

원자 명령 사용

lock 변수를 이용한 상호배제의 실패 원인은 entry코드에 있다.

(lock 변수값을 읽는 명령과 1을 저장하는 명령 사이에 컨텍스트 스위칭이 될 때 문제 발생)

해결책 - 원자 명령 도입 : lock 변수를 읽어 들이는 명령과 lock변수에 1을 저장하는 2개의 명령을 한 번에 처리하는 원자 명령 필요

원자명령 : TSL(Test and Set Lock)

 

멀티스레드 동기화

상호배제 기반위에, 자원을 사용하려는 여러 스레드들이 자원을 원활히 공유하도록 하는 기법

동기화 프리미티브(synchronization primitives)로 부름

 

대표적인 기법

locks 방식 : 뮤텍스, 스핀락

wait-signal 방식 : 세마포

 

뮤텍스 기법

잠김/열림 중 한 상태를 가지는 락 변수 이용

한 스레드만 임계구역에 진입시킴

다른 스레드는 큐에 대기

sleep-waiting lock 기법

 

구성요소

1. 락 변수 - boolean 형으로, 현재 상태를 나타냄

2. 대기 큐 - 락이 열리기를 기다리는 스레드 큐

3. 연산 - lock 연산, unlock 연산

 

뮤텍스를 이용한 동기화 특징

임계구역의 실행 시간이 짧은 경우, 비효율적

 - 락이 잠겨있으면 (컨텍스트 스위칭되어) 대기 큐에서 대기, 락이 풀리면 다시 (컨텍스트 스위칭되어) 실행

 - 락이 잠겨있는 시간보다 스레드가 잠자고 깨는 데 걸리는 시간이 상대적으로 크면 비효율적

 

스핀락 기법

busy-waiting lock 기법 - 스레드가 큐에서 대기하지 않고 락이 열릴 때까지 계속 락 변수 검사

뮤텍스와 거의 같고 busy-waiting이라는 점에서만 다름

 - 대기 큐 없음

 - busy-waiting으로 인해 CPU를 계속 소모, CPU가 다른 스레드를 실행할 수 없음

락을 소유한 스레드만 자원 배타적 사용, 동기화 기법

 

구성요소

1. 락 변수 - boolean 형으로, 현재 상태를 나타냄

2. 연산 - lock 연산, unlock 연산

 

스핀락를 이용한 동기화 특징

busy-waiting으로 인해 CPU를 계속 소모, CPU가 다른 스레드를 실행할 수 없음

단일 CPU(단일 코어)를 가진 운영체제에서 비효율적

 - 단일 코어 CPU에서 의미 없는 CPU 시간 낭비

 - 멀티 코어에 적합

임계구역의 실행 시간이 짧은 경우 효과적

 

뮤텍스와 스핀락은 어떤 경우에 적합한가? (시간나면 보기)

1. 락이 잠기는 시간이 긴(임계구역이 긴) 응용 : 뮤텍스

2. 단일 CPU를 가진 시스템 : 뮤텍스

3. 멀티 코어(멀티 CPU)를 가진 시스템 : 스핀락

4. 사용자 응용프로그램 : 뮤텍스, 커널 코드 : 스핀락

5. 스핀락을 사용하면 기아 발생 가능

중요함

여러 자원을 여러 명이 사용하는 경우

세마포 → 번호표

세마포

멀티스레드 사이의 자원 관리 기법

 - n개의 공유자원을 다수 스레드가 공유하여 사용하도록 돕는 자원 관리

 

구성요소

1. 자원 n개

2. 대기 큐 : 자원을 할당받지 못한 스레드들이 대기하는 큐

3. counter 변수

 - 사용가능한 자원의 개수를 나타내는 정수형 전역 변수

 - n으로 초기화

4. P/V 연산

 - P연산(wait 연산) : 자원 요청시 실행하는 연산

 - V연산(signal 연산) : 자원 반환시 실행하는 연산

 

P연산과 V연산

세마포 종류 2가지

 - sleep-wait 세마포

   - P연산 : counter--, 대기 큐에서 잠자기

   - V연산: counter++, 사용가능 자원이 있으면 잠자는 스레드 깨우기

 - busy-wait 세마포

   - P연산 : 사용 가능 자원이 생길 때까지 무한 루프 후 자원이 생기면 counter—

   - V연산: counter++;

 

카운터 세마포와 이진 세마포

카운터 세마포(counter semaphore) - 여러 개의 자원을 관리하는 세마포

이진 세마포(binary semaphore) - 한 개의 자원을 관리하는 세마포

 

이진 세마포 구성 요소

1. 세마포 변수 S - 0 과 1 중 하나를 가지는 전역 변수, S는 1로 초기화

2. 대기 큐 - 사용 가능한 자원이 생길 때까지 스레드들이 대기하는 큐, 스레드 스케줄링 알고리즘 필요

3. 2개의 원자 연산

 - wait 연산(P 연산) – 자원 사용 허가를 얻는 과정

 - signal 연산(V 연산) – 자원 사용이 끝났음을 알리는 과정

 

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

우선순위 역전(priority inversion)

 - 스레드의 동기화로 인해 높은 순위의 스레드가 낮은 스레드보다 늦게 스케줄링되는 현상

 - ex) 주차장에 늦게 들어온 차가 먼저 들어온 차가 들어갈 자리에 끼어 들어가는 것

 

문제점

 - 실시간 시스템의 근본 붕괴

    - 우선순위가 높다는 것은 중요한 일을 할 가능성이 높은데, 높은 순위 의 스레드(T3)가 늦게 실행되면 심각한 문제 발생 가능

    - 낮은 순위의 스레드(T2)가 길어지면 더욱 심각한 문제 발생

 

해결책

1. 우선순위 올림(priority ceiling)

 - 스레드(T1)가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 미 리 정해진 높은 우선순위로 일시적으로 올림

 - 선점되지 않고 빨리 실행되도록 유도

2. 우선순위 상속(priority inheritance)

 - 낮은 순위의 스레드(T1)가 공유 자원을 가지고 있는 동안, 높은 순위의 스레드(T3)가 공유 자원을 요청하면, 공유 자원을 가진 스레드(T1)의 우선순위를 요청한 스레드(T3)보다 높게 설정하여 빨리 실행시킴

 

생산자 소비자 문제의 정의

생산자 소비자 문제란?

 - 공유버퍼를 사이에 두고, 공유버퍼에 데이터를 공급하는 생산자들과, 공유버퍼에서 데이터 읽고 소비하는 소비자들이, 공유버퍼를 문제 없이 사용하도록 생산자와 소비자를 동기화시키는 문제

 

구체적인 3가지 문제

문제 1 - 상호 배제 해결

문제 2 - 비어 있는 공유 버퍼 문제(비어 있는 공유버퍼를 소비자가 읽을 때)

문제 3 - 꽉 찬 공유버퍼 문제(꽉 찬 공유버퍼에 생산자가 쓸 때)

 

생산자와 소비자 알고리즘