[OS] 동기화 (Synchronization)

floatFirstTOC: right

🖥️ 시작하며

🔍 동기화

• 스레드는 자원을 공유하고 공용 데이터 구조에 접근할 수 있고, 서로의 실행을 조율해야 함

• 그러나 프로그래머는 실행 순서가 어떨지 예상 불가능
→ 스케줄링 컨트롤 불가능
→ 동기화 문제 발생 가능성

🔍 동기화 문제

• 이러한 상황은 경쟁 상태(race condition)를 초래함.

• 경쟁 상태는 여러 프로세스가 동시에 공유 데이터를 접근하고 조작할 때 발생.

• 그 결과는 비결정적이며, 실행 타이밍에 따라 달라짐.

📌 공유 자원

• 로컬 변수들은 공유되지 않음
• 각자의 스택 공간

• 전역 변수, 동적 객체는 공유됨
• 전역 변수 : Static Data Segment (정적 데이터 세그먼트)
• 동적 객체 : Heap
 

📌 Critical Sections (임계 구역)

• Critical Section에서의 동시 접근을 방지하기 위해 Mutual exclusoin(상호 배제)을 사용
상호 배제는 한 번에 하나의 스레드만 Critical Section을 실행하도록 보장

• Ctirical Section은 경쟁 상태를 유발

💡 Critical Section에서의 요구사항

• 상호 배제 (Mutual Exclusion)
• 동시에 하나의 스레드만 크리티컬 섹션에 있을 수 있어야 합니다.
• 다른 모든 스레드는 크리티컬 섹션에 진입하지 못하고 대기해야 합니다.

• 진행 (Progress)
• 스레드 T가 크리티컬 섹션 내에 있는 경우, T는 합리적인 시간 내에 크리티컬 섹션을 완료해야 합니다.
• 스레드 T가 크리티컬 섹션 밖에 있는 경우, T는 다른 스레드 S가 크리티컬 섹션에 진입하는 것을 방해할 수 없습니다.

• 유한 대기 (Bounded Waiting, No Starvation)
• 스레드 T가 크리티컬 섹션에 진입하기 위해 대기하고 있는 경우, T는 결국 크리티컬 섹션에 진입할 수 있어야 합니다.
• 즉, 대기 중인 스레드가 무한히 대기 상태에 머물지 않도록 보장해야 합니다.

• 성능 (Performance)
• 크리티컬 섹션에 진입하고 나오는 과정의 오버헤드가 크리티컬 섹션 내에서 수행되는 작업에 비해 작아야 합니다.
• 즉, 동기화 메커니즘 자체의 성능 오버헤드가 최소화되어야 합니다.

📌 Critical Sections의 메커니즘

1️⃣ Locks (락)

• 설명: 가장 기본적인 동기화 메커니즘으로, 크리티컬 섹션을 보호하기 위해 사용됩니다.

• 장점: 간단한 사용법, 최소한의 의미론.

• 단점: 직접적인 사용 시 복잡한 동기화 문제를 해결하기 어려움, 데드락 가능성.

• 사용 예시:

pthread_mutex_t lock;
pthread_mutex_lock(&lock);
// 크리티컬 섹션
pthread_mutex_unlock(&lock);

2️⃣ Semaphores (세마포어)

• 설명: 카운터를 기반으로 한 동기화 메커니즘. 주로 두 가지 유형이 있습니다: binary semaphore (뮤텍스와 유사)와 counting semaphore (다중 자원 관리).

• 장점: 기본적이고 이해하기 쉬움.

• 단점: 복잡한 프로그래밍에 어려움, 잘못 사용할 경우 데드락이나 라이브락 발생 가능성.

• 사용 예시:

sem_t semaphore;
sem_init(&semaphore, 0, 1); // 초기화

sem_wait(&semaphore); // 크리티컬 섹션 진입
// 크리티컬 섹션
sem_post(&semaphore); // 크리티컬 섹션 종료

3️⃣ Monitors (모니터)

• 설명: 고수준의 동기화 메커니즘으로, 언어 차원에서 지원됩니다. 크리티컬 섹션 진입 및 종료가 암묵적으로 이루어집니다.

• 장점: 프로그래밍이 용이함, 코드 가독성 높음.

• 단점: 언어 지원 필요, 유연성 부족.

• 사용 예시 (Java):

public synchronized void criticalSection() {
    // 크리티컬 섹션
}

4️⃣ Messages (메시지)

• 설명: 채널을 통해 데이터의 원자적 전송을 기반으로 한 동기화 및 통신 모델. 분산 시스템에 직접적으로 적용 가능.

• 장점: 간단한 통신 및 동기화 모델, 분산 시스템에서 유용.

• 단점: 성능 오버헤드, 구현의 복잡성.

• 사용 예시:

// Pseudo code for message passing
send(channel, message);
receive(channel, &message);

🔍 Locks

• acquire() : 해제될 때까지 기다린 후, 락 획득

• release() : 락을 해제, acquire() 에서 대기 중인 다른 스레드를 깨움

• 초기 상태: 락은 초기에는 해제된 상태입니다.

• 크리티컬 섹션 전후: 크리티컬 섹션에 들어가기 전에 acquire()를 호출하고, 크리티컬 섹션을 벗어난 후 release()를 호출합니다.

• 락 보유: acquire()와 release() 사이에서 스레드는 락을 보유하고 있습니다.

• 단일 스레드: 한 번에 하나의 스레드만 락을 보유할 수 있습니다.

• acquire() 동작: acquire()는 호출한 스레드가 락을 보유할 때까지 반환하지 않습니다.

📌 Locks의 종류

⚙️ 스핀락 (Spinlock)

• 작동 방식: 스레드가 락을 획득할 때까지 루프를 돌면서 계속 시도합니다.

• 특징: 빠르게 락을 획득할 수 있는 경우 유리하지만, 긴 대기 시간 동안 CPU를 낭비할 수 있습니다.

⚙️ 뮤텍스 (Mutex)

• 작동 방식: 스레드가 락을 획득할 때까지 블록 상태로 대기합니다.

• 특징: 대기 중인 스레드는 CPU를 사용하지 않으며, 다른 스레드가 실행될 수 있습니다.

📌 Locks의 구현 방법

• Software-only algorithms
• Dekker’s algorithm
• Peterson’s algorithm
• Lamport’s Bakery algorithm

• Hardware atomic instructions
• Test-and-set, compare-and-swap

• Disable/reenable interrupts
• context switch를 방지하기 위함

📌 Software-only algorithms

⚙️ Peterson’s Algorithm

📌 Hardware atomic instructions

⚙️ Atomic Instructions

📌 Spinlocks의 문제점

• 아주, 매우 비효율적
• CPU 사이클 낭비가 굉장히 심함 (while문)
• 락을 보유한 스레드가 의도치 않은 context switch로 중단될 수 있음
→ 다른 스레드가 임계 구역에 들어가지 못하는 문제 발생

📌 Disabling Interrupts

• 문제점
• 오직 커널만 가능, 하지만 이런 방법을 쓰지 말라고 가이드되어 있음
• 멀티프로세서 환경일 시 문제 발생
• critical section이 길다면 아무런 인터럽트를 받지 못함

🔍 High-level 동기화

• 더욱 고수준의 동기화 기법 필요성이 대두됨
1. 대기 중인 스레드를 블로킹:
Lock을 획득하려는 스레드가 블로킹 상태로 대기할 수 있어야 함
2. 인터럽트 활성화 유지
Critical section 내에서 인터럽트를 활성화 상태로 유지해 시스템의 응답성을 보장

• 두 종류가 존재함
• Semaphores: binary(mutex) and counting
• Monitors

🔍 Semaphores

• 락보다 고수준: 세마포어는 락보다 더 복잡한 동기화 문제를 해결할 수 있음

• busy waiting 없음: 세마포어는 대기 중인 스레드를 블로킹 상태로 유지하여 CPU 사이클을 낭비하지 않음

• Atomic한 조작: 세마포어는 두 가지 원자적 연산을 통해 조작됨
1. Wait (S): 세마포어 값을 감소시키고, 세마포어가 열릴 때까지 블로킹
• P() 연산: 네덜란드어 "Proberen" (시험하다)에서 따온 이름으로, 세마포어를 테스트하고 값을 감소. 영어로는 down() 이라고도 함.
2. Signal (S): 세마포어 값을 증가시키고, 다른 스레드가 진입할 수 있도록 함.
• V() 연산: 네덜란드어 "Verhogen" (증가시키다)에서 따온 이름으로, 세마포어 값을 증가. 영어로는 up() 이라고도 함.

⚙️ wait() 호출

• 세마포어가 열려 있는 경우:
• 스레드는 계속 실행됩니다.
• 세마포어의 카운터 값을 감소시킵니다.

• 세마포어가 닫혀 있는 경우:
• 스레드는 blocking 상태가 되어 큐에서 대기합니다.
• 세마포어의 카운터 값이 0 이하로 떨어집니다.

⚙️ signal() 호출

• 세마포어 열기:
• 세마포어의 카운터 값을 증가시킵니다.
• 카운터 값이 0 이상이 되면, 대기 중인 스레드 중 하나를 언블록합니다.

📌 세마포어의 유형

1. 이진 세마포어 (Binary Semaphore) - 뮤텍스(Mutex)
• 역할: 공유 자원에 대한 상호 배제 접근을 보장합니다.
• 특징:
• 한 번에 하나의 스레드/프로세스만 진입을 허용합니다.
• 카운터는 1로 초기화됩니다.
• 사용 예:
• 한 번에 하나의 스레드만 파일에 접근할 수 있도록 할 때.
• 크리티컬 섹션 보호.

2. 카운팅 세마포어 (Counting Semaphore)
• 역할: 여러 단위의 자원을 나타내며, 사용 가능한 자원이 있는 한 스레드/프로세스가 진입할 수 있도록 허용합니다.
• 특징:
• 예: 5개의 프린터.
• 카운터는 N(사용 가능한 단위의 수)로 초기화됩니다.
• 사용 예:
• 한 번에 여러 스레드가 데이터베이스 연결을 사용할 수 있도록 할 때.
• 리소스 풀(예: 연결 풀, 쓰레드 풀) 관리.
 

🔍 Deadlock과 Starvation

• Deadlock:
서로의 데이터를 기다리는 형태, 코딩의 오류로 일어남.

• Starvation:
• 정의: 특정 프로세스가 세마포어 큐에서 무한히 대기하여 실행되지 못하는 현상.
• 원인: 낮은 우선순위의 프로세스가 계속해서 높은 우선순위의 프로세스에 의해 밀려나는 경우 발생할 수 있습니다.
• 해결 방법: 선점형 스케줄링 알고리즘을 사용하여 각 프로세스가 적절한 시간 안에 실행될 수 있도록 합니다.

• 우선순위 역전 (Priority Inversion)
• 정의: 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스가 필요한 락을 보유하고 있는 경우 발생하는 스케줄링 문제.
• 문제: 높은 우선순위의 프로세스는 낮은 우선순위의 프로세스가 락을 해제할 때까지 기다려야 하므로 실행이 지연됩니다.
• 해결 방법: 우선순위 상속 프로토콜(Priority Inheritance Protocol)을 사용합니다.

🔍 동기화의 고전적인 문제점들

📌 Bounded Buffer Problem

1. 버퍼: 생산자와 소비자가 공유하는 자원 버퍼가 있습니다. 이 버퍼는 한정된 크기를 가지고 있습니다.
• 생산자: 자원을 버퍼에 삽입합니다.
• 예: 출력, 디스크 블록, 메모리 페이지 등.
• 소비자: 버퍼에서 자원을 제거합니다.

2. 생산자와 소비자: 생산자와 소비자는 서로 다른 속도로 실행되며, 직렬화되지 않습니다. 각 작업은 독립적으로 수행됩니다.

📌 Dining Pilosopher

🔍 세마포어의 문제점

• 필연적으로 전역 공유 변수를 사용해야 함
• 코드의 어느 부분에서도 접근 가능 → 이는 좋지 않은 프로그래밍

• Critical section(상호 배제)와 동기화(스케줄링)을 위해 사용되므로 코드의 복잡성이 증가

• 개발자가 적절히 쓸 수 있다는 보장이 없음
• 교착 상태, 기아 문제 유발

• 디버깅이 힘듦

🔍 Monitors

• 동기화 코드가 컴파일러에 의해 추가되고, 런타임 때 실행

• 모니터는 소프트웨어 모듈로써 캡슐화를 수행
• 공유 데이터 구조
• 데이터를 조작하는 프로시저