[OS 공룡책] 6. Synchronization Tools, 7. Examples
동시 접근이 일어나면 항상 발생하는 문제가
data inconsistency - 일관성 문제이다
JVM에서 공부했던 내용이라 간략하게만 언급하면
스레드는 메모리를 공유하기 때문에 - 정확하게는 힙 영역을 공유하기 때문에 발생한다
c언어 예시이긴 하지만
sum++이 결국 sum (현재 값을 읽고->증가된 값 쓰기) 로직이니까
동시에 접근하는 값이 최신 값이 아니게 되면서 정합성이 깨지기 시작한다
자바 고급1에서 너무 많이했으니 패스
Race Condition
한국어로 교착상태
여러개의 프로세스가 하나의 값 수정을 할때 발생하는 문제
교착상태가 발생하는 코드 구역을 ciritical section이라고 부르는데
세부적으로 코드 영역을 4가지로 구분한다
여기서는 아직 락을 배우지 않았지만 언급하겠다
- entry section
require permission - 락을 획득해야 진입할 수 있는 구간
- critical section
임계영역으로 race condition이 발생하는 구간
- exit section
ciritical section이 끝나는 구간으로 락을 반납해야할 것이다
- remainder section
나머지~
이때 critical section 문제를 해결하기 위한 3가지 요구사항이 있다
- mutual exclusion
상호 배제
하나의 프로세스가 critical section을 실행하고 있다면 다른 프로세스는 실행할 수 없어야 한다
- progress (avoid deadlock)
프로세스가 critical section을 실행하고 있지 않음에도
다른 프로세스가 진입하지 못하는 경우가 없어야 한다
- bounded waiting (avoid starvation)
락을 획득하기 위해 기다리는 프로세스들이 있을텐데
락 획득에 우선순위를 둔다면 cpu scheduling때와 마찬가지로 우선순위에 계속 밀려 락을 획득하지 못하는 경우가 없어야 한다
우선 mutual exclusion은 너무 필수적인거고
아래 두가지를 모두 발생하지 않도록 하는 것은 매우 어렵다
그래서 이게 발생했을 때 어떻게 할것인지가 중요한 포인트
single core에서는 문제를 해결하는 것이 간단하다
읽기 -> 더하기 -> 더한값 쓰기
수행될 동안 interrupt되지 않도록 하면 된다
즉 atomic하게 수행하면 된다
반면에 코어가 여러개라면 다른 코어에서 실행하는 경우도 문제가 되고
처리가 오래 걸린다면 코어가 놀게되는 즉 cpu utilization 문제가 발생한다
Peterson's Solution
soft ware based로
원시적인 락을 건거다
하지만 이 방법은
while 문을 도는 busy waiting 즉 spin lock이라는 문제점이 있다
Hardware based solutions
결국 하드웨어를 다뤄야 한다
- memory barriers or fences
- hardware instructions
- atomic variables
이 내용은 보너스 느낌으로 나온 것 같다
살짝 복기해보면
자바 고급편에서는 이런 자료형이나 CAS 연산은 살짝만 알아보고
이를 활용하는 concurrent 컬렉션을 알아봤었다
본격적으로 OS 레벨의 락은 이제 나온다
Mutex Locks
mutual exclusion을 줄여서 mutex
락을 획득하고, 반납하는 구조
아까 나온 peterson이랑 사실은 비슷하다
이것도 문제점이
- spinlock (context switch 비용을 아낄수는 있다)
- n개를 처리할 수 없다
- interrupt를 차단할 수 없다면 문제가 발생한다(멀티코어)
Semaphore
세마포어는 신호기라는 말이다
실제 구현에서는 그냥 integer 변수다
전에 나온 mutex와 차이점은
mutex에서는 락하나를 두고 받고, 반납하는 방식인데
여기서는 전역변수를 증가, 감소하는 방식을 사용하는 것이다
구현차이
- binary semaphore를 사용한다면 즉 0, 1만 사용하면 mutex와 같은 것이다
- counting semaphore
n개를 사용 가능
구체적으로
wait(), signal()을 사용하게 되는데
여기부터 락 획득을 대기하는 wait set 개념이 나오게 되는 것이다
이로 인해 waiting queue에 들어가게 되면 busy waiting 문제도 해결된다
이건 semaphore 구현 방식 중에서도 차이가 있는거라 지금 논점은 mutex -> semaphore -> monitor 발전이니까 생각하지 말자
뮤텍스 / 세마포어를 사용한다면
timing error가 발생할 수 있다
간단한 예시로
wait -> signal 순서만 헷갈려도 심각한 에러가 날 가능성이 존재한다
Monitor
이를 해결하기 위해 간단하게 사용 가능한 고 수준으로 동기화를 다룰 수 있는 모니터를 제공한다
특히 생산자, 소비자 문제에서
어떤 그룹을 깨울지에 대한 문제가 생기는걸 확인했었다
이를 위해 conditional variable이 필요하다
이런식으로
자바에서 제공하는 모니터락
객체마다 가지고 있었던 모니터락 기억나쥬?
대표적으로 두가지가 있다
- synchronized
객체 단위로 임계영역/메서드를 묶어주는 키워드였다
- wait(), notify()
Object 클래스에 선언되어서 모든 객체가 가지고 있다
wait() 메서드로 모니터락 획득하러 대기 (ready queue)
notify()는 락을 반납하면서 해당 wait set에 있는 스레드 깨움
좀 헷갈려서 비교해달라고 했더니 이렇다고 한다
Liveness
뮤텍스 / 세마포어 / 모니터 모두 mutual exclusion 문제를 해결하지
deadlock, starvation 문제를 고려하지 않는다
이를 고려한 것이 liveness
자세하게 알 필요는 없다고 하고
데드락/starvation은 뒤에서 자세히 나온다
동시성 제어 문제 실질적인 문제들을 다룬다
- bounded-buffer problem
전에 살펴봤던 생산자 소비자 문제
- readers-writers problem
여러개의 프로세스들이 shared data에 접근하는 것은 동일하지만 어떤 프로세스는 read만, 어떤 프로세스는 read+write 한다는 가정이 다르다
data inconsistency를 일으키는건 writer이기 때문에 writer에게 우선적으로 락을 점유할 기회를 줄것인지, reader writer 모두 공평하게 락을 획득할 기회를 줄것인지에 대한 고민이 존재한다 -> 현재는 Redaer Writer Locks라는 표준화된 해결 기법이 존재하기 때문에 개발자는 고민하지 않아도 된다고 한다
- dining-philosophers problem
대표적인 동기화 문제인데 철학자 5명 사이에 젓가락이 하나씩 5개가 있다는 가정하에 생기는 문제다
단순히 생각하면 젓가락을 동시에 집지 못하도록 락을 걸어 mutual exclusive하게 하면 되는거 아닌가? 이지만
동시에 모든 철학자가 자신 기준 왼쪽 젓가락을 잡는다면? - deadlock
1, 2, 3, 4, 5순으로 원형으로 앉아있다고 하면
1, 3이 밥을 번갈아 가면서 먹으면 철학자 2는 영원히 밥을 먹지 못할 것이다 - starvation
해결책으로
왼쪽 오른쪽 젓가락을 모두 집을 수 있을때만 집는 방법을 떠올릴 수 있다
-> 구체적으로 모니터를 사용해 이를 해결하는 법을 알아보자
젓가락을 드는 메커니즘이 원래는
thinking (젓가락 사용X) -> eating (젓가락 사용)
인데 hungry 상태를 추가해
thinking -> hungry -> eating 상태로 관리한다
hungry 상태는 락을 점유하기 위해 기다리는, wait set을 떠올리면 된다
이렇게 하면 mutex, deadlock은 방지할 수 있지만
starvation을 방지할 수는 없다
CAP이론처럼 여기서도 3가지(mutex, deadlock, starvation)를 모두 달성하기는 매우 어렵기 때문에