동기화 문제의 해결

멀티프로그래밍 작업을 할 때 프로세스는 독립적으로 작업을 하거나, 공유된 자원을 활용하여 공동작업을 하기도 한다. 멀티 프로세싱은 IPC(프로세스 간 통신방법)를 통해 자원을 공유하고, 멀티스레딩의 스레드들은 프로세스의 메모리 영역(코드, 데이터, 힙)을 공유하며 공동 작업을 한다. 자원 공유를 통해 응답성과 경제성을 높일 수 있지만 이에 따른 문제도 발생할 수 있다. 공유 자원을 동시에 여러 스레드가 접근한다면 어떤 문제가 일어날까? 2개 이상의 스레드가 공유 자원에 접근할 경우 그곳의 데이터는 온전하지 않을 수 있다. 따라서 Critical Section을 설정하여 두 개 이상의 스레드가 동시 접근을 할 수 없도록 막아야 한다. 이와 같은 동기화 문제의 해결 방법에 대해 알아보자.

<쉽게 배우는 운영체제> 책을 참고하였습니다.

---

Critical Section

임계 구역이라고도 하며, 둘 이상의 스레드가 동일한 프로그램의 영역을 접근하는 경우를 가리킨다. Critical Section에는 데이터 변수의 일관성을 유지하기 위해 동기화해야 하는 공유 변수 또는 Resource가 포함된다.

☆Resource의 종류 : CPU cycles, files, I/O devices(printers, drives) 등

 

CSP(Critical Section Problem) 해결조건

• Mutual Exclusion : Critical Section 내에는 하나의 스레드만 존재해야 함
• Bounded Waiting : Critical Section 내에 무한정으로 대기할 수 없음
• Progress Flexibility : Shared Resource가 사용 중이 아니라면 언제든 사용할 수 있어야 함

 

CSP 해결하기

• Concurrency를 보장할 수 있는가 (Mutual Exclusion)
• 각각의 스레드가 적당한 시간에 Critical Section에 접근 가능하고, 기아(starvation)에 빠지지 않도록 할 수 있는가 (Fairness)
• Lock을 사용함으로써 큰 Overhead가 발생하지 않는가 (performance)

Lock이란?

Critical Section은 여러 스레드에서 동시에 실행되면 안 되는 부분이다. 따라서 하나의 스레드만 접근할 수 있도록 보호하여야 하는데, lock을 통해 보호할 수 있다. 하지만 너무 많은 lock을 걸 경우 lock(), unlock()하는 데 있어 많은 Overhead가 발생한다.

• Fine-grained Lock : Critical Section마다 lock을 걸어 제한
• Coarse-grained Lock : 여러 개의 Critical Section을 묶어서 lock을 걸어 제한

싱글 쓰레드 환경에서 Fine-grained Lock이 Coarse-grained Lock보다 좀 더 성능이 좋다.

0. Interrupt Masking

void lock() {
    DisableInterrupts();    //인터럽트 막기
}

void unlock() {
    EnableInterrupts();
}

• Critical Section에 접근할 때 인터럽트를 막는다.
• Single Processor에서만 가능, Multi Processor에서는 동작 안 함
• 자발적으로 CPU에 권한을 양보해야 하는데, 이것을 제공하지 않음

1. Mutex Locks

• 상호 배제 문제만 해결
• 동기화를 위한 가장 간단한 툴
• Critical Section을 보호하고 race condition을 예방한다.
  • race condition : 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 할 때를 가리킴
• Busy waiting Problem
  • lock이 해제되길 기다리면서 무한루프를 돔
  • Spin lock이라고도 한다.
  • Spin lock이 유용할 때 : waiting 하면서 CPU를 계속 점유하고 있기 때문에 Context Switching이 일어나지 않는다.
    - CPU를 점유하고 있지 않다면 Wait Queue에서 Ready Queue로 가면서 시간이 오래 걸린다.

2. Semaphore

• 상호 배제 문제만 해결
• Mutex보다 좀 더 견고하고, 편리하고, 효과적인 툴
• Binary Semaphore : mutex lock과 유사
• Counting Semaphore : 여러 개의 인스턴스를 가진 자원들에게 사용할 수 있다.
• mutex와 마찬가지로 Busy waiting Problem이 있음
  • wait() operation을 통해 Wait Queue에 들어가게 하고, signal() operation을 통해 Ready Queue에 들어가게 해서 Busy waiting Problem을 막을 수 있다.

3. Monitor

• 상호 배제 문제만 해결
• Mutex와 Semaphore의 단점을 해결한 툴
  • wait()와 signal() Operation을 내부적으로 처리하자 → 공유자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다.
• monitor-lock or intrinsic-lock
• wait() : 해당 객체의 모니터 락을 획득하기 위해 대기상태로 진입함
• notify() : signal()과 같음, 해당 객체 모니터에 대기 중인 스레드 하나를 깨움
• synchronized : 임계 영역에 해당하는 코드 블록을 선언할 때 사용하는 자바 키워드
• 해당 코드 블록(임계 영역)에는 모니터 락을 획득해야 진입 가능

4. Liveness

• 상호 배제 문제와 데드락 문제 해결