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

스레드 동기화의 필요성

1) 동기화의 필요성

• 다수의 스레드가 동시에 공유 데이터 접근 → 공유데이터의 훼손
• 스레드 동기화 (thread synchronization)
  • 공유데이터에 대한 다수의 스레드가 동시에 접근할 때 공유데이터가 훼손되는 문제의 해결책
  • 공유데이터를 집근하고자 하는 다수의 스레드가 충돌없이 공유데이터에 접근하기 위해 상호 협력하는 것

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

• 여러 스레드가 공유 변수에 접근할 때, 공유 데이터 훼손
• 스레드 동기화 → 한 스레드가 공유데이터의 접근을 마칠 때까지 → 다른 스레드가 공유데이터를 접근하지 못하도록 제어
• 멀티 스레드의 경쟁 상황이 자주 발생 → 커널 안의 공유 데이터가 많아 자주 발생, 다중 코어에 더욱 조심해야함

3) 임계 구역과 상호 배제

#1 임계구역

• 공유 데이터에 접근하는 코드 영역

#2 상호배제

• 임계구역이 오직 한 스레드만 배타적 독점적으로 사용되도록 하는 기술
• 임계구역에 먼저 진입한 스레드가 해당 구역의 실행을 끝낼 때까지 다른 스레드의 진입을 막는 것

상호 배제 (mutual exclusion)

1) 상호 배제를 포함하는 프로그램

#1 일반코드

• 공유 데이터를 엑세스하지 않는 코드

#2 임계구역 진입 코드

• 상호배제를 위해 필요
• 현재 임계구역을 실행하는 스레드가 있는 지 검사 → 없으면 다른 스레드가 못들어오도록 조치, 있으면 진입 가능까지 대기

#3 임계구역 코드

• 공유 데이터에 접근하는 코드 영역

#4 임계구역 진출 코드

• 상호배제를 위해 필요
• 진입 코드에서 취한 조치를 해제하여 다른 스레드가 임계구역 코드를 실행하도록 하는 코드

2) 상호배제 구현

• 목표 : 임계구역에 오직 1개의 스레드만 진입
• 소프트웨어적 구현 방법 : Peterson’s 알고리즘 등
• 하드웨어적 구현 방법 : 인터럽트 서비스 금지, 원자 명령 활용
• 인터럽트 서비스 금지
• 인터럽트가 발생해도 cpu가 인터럽트를 무시하도록 하는 cpu 명령 이용
• 원자 기계 명령
• 가장 많이 사용, 임계구역에 진입 시 임계구역을 잠그곡 들어가는 명령 하나로 다른 스레드가 못들어오도록 조치

3) 인터럽트 서비스 금지 구현

• 인터럽트 서비스 금지 방법
• 임계구역 진입 코드에서 인터럽트 서비스를 금지하는 명령 실행
• 문제점
• 모든 인터럽트가 무시됨
• 멀티 코어 cpu나 다중 코어 cpu에서 사용이 불가 (다른 cpu까지 영향)

4) 단순 lock 변수로 상호배제

• 임계구역 진입/진출 코드에 lock 변수를 통해 상호배제 구현
• 단순 lock 변수를 읽는 명령과 변수를 저장하는 코드 사이에 컨텍스트 스위칭 발생 → 상호배제 실패 원인

5) 원자 명령 사용

• lock 변수를 읽어 들이는 명령과 lock 변수에 값을 저장하는 2개의 명령을 1번에 처리하는 원자 명령 사용
• TSL (Test and Set Lock)의 명령을 통해 상호배제 구현

멀티스레드 동기화 기법

• 상호배제 기반 위에 자원을 사용하려는 여러 스레드들이 자원을 원할히 공유하도록 하는 기법
• 동기화 프리미티브 (synchronization primitives)
• lock 방식과 wait-signal 방식으로 이루어짐

1) 뮤텍스 - lock방식

• 잠김/열림 중 한 상태를 가지는 락 변수를 이용하여 한 스레드만 임계구역에 진입
• 다른 스레드는 큐에 대기 (sleep-waiting)

#1 구성요소

1. 락 변수 (true/false 중 한 값만 가짐) true : 락 소유, 락을 잠근다 false : 락을 해제하여 접근이 가능하도록 만듬
2. 대기 큐 락이 열리기를 기다리는 스레드 큐
3. 연산 lock 연산 - 진입 코드에서 락을 잠그는 것 unlock 연산 - 진출 코드에서 락을 해제하는 것

#2 뮤텍스의 특징

• 임계구역의 실행 시간이 짧은 시간이면 비효율적
• 컨텍스트 스위칭을 통해 대기 큐에 삽입되고 깨울 때에도 컨텍스트 스위칭됨 → 실행시간이 짧을 경우 lock시간보다 스레드가 잠자고 깨우는 시간이 더 걸림

2) 스핀락 - lock 방식

• busy-waiting 기법으로 대기하지 않고 락이 열릴 때까지 락 변수를 계속하여 검사
• 뮤텍스와 락 방식을 거의 같으며 busy-waiting만 다름
• 락을 소유한 스레드만 자원 배타적 사용하는 lock방식

#1 구성요소

1. 락 변수 (true/false 중 한 값만 가짐) true : 락 소유, 락을 잠근다 false : 락을 해제하여 접근이 가능하도록 만듬
2. 연산 lock 연산 - 락이 잠긴 상태면 락이 풀릴 때까지 무한 루프를 통해 lock 연산 시도 unlock 연산 - 락을 열린 상태로 변경

#2 스핀락 특징

• 뮤텍스의 non-blocking 모델
• 단일 cpu를 가진 운영체제에서 비효율적, 멀티 코어에 적합
• 임계구역의 실행 시간이 짧은 경우 효과적

3) 뮤텍스와 스핀락의 비교

뮤텍스 스핀락

대기 큐	있음	없음
블록 가능 여부	락이 잠겨있으면 블록	락이 잠겨있어도 블록되지않고 계속해서 락 검사
연산 비용	저비용	cpu를 계속 사용하여 고비용
하드웨어 관련	단일 cpu에 적합	멀티코어 cpu에 적합
주 사용처	사용자 응용 프로그램	커널 코드, 인터럽트 서비스 루틴

4) 세마포 - wait-signal 방식

• 멀티스레드 사이의 자원 관리 기법 ( n개의 자원 - 다수의 스레드 )

#1 구성요소

1. 자원 : n개
2. 대기 큐 : 자원을 할당받지 못한 스레드들이 대기
3. counter 변수

• 사용 가능한 자원의 개수를 나타내는 정수형 전역 변수
• n으로 초기화

1. P/V 연산

• P연산 (wait 연산) : 자원 요청시 실행 연산
• V연산 (signal 연산) : 자원 반환시 실행 연산

#2 P 연산과 V 연산

• P 연산 : 자원 사용을 허가하는 과정, 사용가능 자원 수 감소
• V 연산 : 자원 사용을 마치는 과정, 사용가능 자원 수 증가

#3 세마포의 종류

• sleep-wait 세마포 P 연산 : 대기 큐에서 잠자기 V 연산 : 사용가능 자원이 있으면 잠자는 스레드를 깨우기
• busy-wait 세마포 P 연산 : 사용 가능 자원이 생길 때까지 무한 루프 V 연산 : counter 감소

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

#1 카운터 세마포

• 자원의 인스턴스가 여러 개인 경우
• 앞서 이야기한 세마포의 경우 카운터 세마포

#2 이진 세마포

• 자원이 1개 있는 경우 멀티스레드 사이의 자원 관리
• 뮤텍스와 유사하게 1개의 자원에 대해 하나의 스레드만 액세스 가능하도록 보호

#3 이진 세마포의 구성 요소

1. 세마포 변수 S : 0과 1 중 하나를 가지는 전역 변수
2. 대기 큐 : 사용 가능한 자원이 생길 때까지 스레드들이 대기
3. 2개의 원자 연산 wait연산 (P연산) : 자원 사용 허가를 얻는 과정 signal연산 (V연산) : 자원 사용이 끝났음을 알리는 과정

6) 우선순위 역전

• 스레드의 동기화롤 인해 높은 순위의 스레드가 낮은 스레드보다 늦게 스케줄링되는 현상
• 우선 순위를 기반으로 스케줄링하는 실시간 시스템의 근본 붕괴

#1 우선순위 역전 해결책

• 우선순위 올림
• 스레드가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 일시적으로 올림
• 우선순위 상속
• 낮은 순위의 스레드가 공유 자원을 가지고 있는 동안 높은 순위의 스레드가 공유 자원을 요청 → 공유 자원을 가진 스레드의 우선순위를 요청한 스레드보다 높게 설정

생산자 소비자 문제

1) 생산자 소비자 문제

• 공유 버퍼를 사이에 두고 데이터를 공급하는 생산자들과 데이터를 읽고 소비하는 소비자들이 공유 버퍼를 사용할 때 해당 공유 버퍼를 문제없이 동기화시키는 문제
• 3가지 문제점
• 공유버퍼에 대한 상호배제
• 비어있는 공유 버퍼를 소비자가 읽을 때
• 꽉 차 있는 공유 버퍼를 생산자가 쓸 때

#1 비어있는 버퍼 문제 / 꽉 찬 공유 버퍼 문제

• 버퍼가 비어있는 지 살피는 세마포 P/V 연산으로 해결
• 버퍼가 꽉 차 있을 때 처리하는 P/V 연산으로 해결