[공룡책] 챕터7 동기화 예시

목표

• bounded-buffer, readers-writers, dining-philosophers 동기화 문제를 설명한다.
• 리눅스/윈도우에서 프로세스 동기화 문제를 해결하기 위한 특정한 툴을 소개한다.
• POSIX와 Java가 프로세스 동기화 문제를 풀어내는지 설명한다.
• POSIX와 Java API를 사용하여 프로세스 동기화 문제에 대한 해결방법을 디자인하고 개발하는 솔루션에 대해 알아본다.

고전적인 동기화 문제

생산자와 소비자 프로세스는 위 데이터 구조를 공유한다.

 

n개의 버퍼로된 pool이 있고 각 버퍼는 하나의 항목을 저장할 수 있다고 가정하자. mutex 세마포어는 버퍼 pool에 상호 배제적으로 접근하기 위해 제공되며 1로 초기화 된다. empty와 full 세마포어는 빈 버퍼와 가득찬 버퍼의 수를 나타낸다. 

 

생산자 프로세스 코드는 7.1이고 소비자 프로세스 코드는 7.2이다.

 

생산자와 소비자 코드 간의 대칭성에 주목하자. 생산자가 소비자를 위해 full 버퍼를 생성하거나 소비자는 생산자를 위해 empty 버퍼를 생성하는 것으로 볼 수 있다.

 

Readers-Writers Problem

하나의 데이터베이스가 여러 프로세스 사이에서 공유된다고 가정하자. 일부 프로세스는 데이터베이스를 읽기만하고, 다른 프로세스는 데이터베이스를 업데이트 한다.

reader가 동시에 DB에 접근하는 것은 문제가 없다. writer가 동시에 DB에 접근하는 것은 문제가 있다. 이 문제를 해결하려면 writer가 데이터베이스에 쓰는 동안 데이터베이스를 독점할 수 있어야한다. 이 동기화 문제를 reader-writer problem이라고 한다.

 

reader-writer 문제를 변형한 문제가 있다. 우선순위와 관련이 있다.

1. writer가 공유 객체를 사용할 수 있는 권한을 이미 얻지 않는 한 reader보고 계속 기다리라고 할 필요가 없다.
2. writer가 준비가 되면, writer는 가능한 빨리 처리해야한다. 다른말로하면, 만약 writer가 object에 대한 접근을 기다리면, 새로운 reader는 읽기를 시작할 수 없다.

위 문제들에 대한 해결법이 기아상태를 낳을 수 있다. 첫번째 경우는, writer가 기아가 될 수 있으며, 두번째는 reader가 기아가 될 수 있다. 때문에 다른 변형이 제안되었다. 여기서는 첫번째에 경우만 다룬다.

첫번쨰 경우에서 reader 프로세스는 아래 데이터 구조를 갖는다.

 

위 코드는 writer process이며 아래 코드는 reader 프로세스다. rw_mutex를 이용해서 상호 배제적으로 데이터에 접근한다.

아래 코드는 프로세스가 공유 데이터에 접근할 때 read 모드나 write 모드 둘 중 하나로 접근하게 되고 다른 접근을 막아버린다.

reader-writer가 유용한 상황

• 한 프로세스는 공유 데이터를 읽기만하고 다른 프로세스는 공유 데이터를 쓰기만 하는 프로세스를 애플리케이션에서 쉽게 식별할 수 있다.
• 애플리케이션에서 reader가 writer보다 많을 때 유용하다. reader-writer lcok은 일반적으로 세마포어나 뮤텍스보다 더 많은 오버헤드를 요구한다. 이 오버헤드는 동시에 여러 reader를 접근하게 하여 동시성을 높임으로써 비용을 상쇄할 수 있다.

반응형

식사하는 철학자 문제

5명의 철학자가 원탁에서 생각하고 식사를 한다고 가정하자. 테이블 중앙에는 한 사발의 밥이 있고 다섯 개의 젓가락이 놓여 잇다. 철학자가 생각할 때는 다른 동료들과 상호작용하지 않는다. 철학자가 배고파지고 자신에게 가장 가까이 있는 두 개의 젓가락(자신의 좌우)을 잡으려고 시도한다. 철학자는 한 번에 한 개의 젓가락만 집을 수도 있다. 옆 사람이 집고 있는 젓가락은 잡지 않는다. 식사를 마치면 젓가락을 두고 다시 생각한다.

모든 철학자가 동시에 식사를 시작하여 왼쪽 젓가락을 들면 오른쪽 젓가락이 생길 때 까지 기다릴 것이다. 결국 영원히 교착 상태와 기아상태에 머물게 된다.

간단한 해결책은 각 젓가락을 하나의 세마포어로 표현한다.

철학자는 wait()를 통해 젓가락을 집으려 한다. chopstick[i]는 접근 불가능한 상태가 된다. 다 먹었으면 signal()를 통해 자신의 젓가락을 놓는다. chopstick[(i+1) % 5]는 다음 젓가락을 의미하고 % 5를 해주는 이유는 원순열의 성질에 의해 처음으로 돌아가기 위해서다.

이 방법은 인접한 두 철학자가 동시에 식사하지 않음을 보장하지만 교착상태를 야기할 수 있다.

식사하는 철학자 문제를 해결하기 위해서는

• 최대 4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
• 한 철학자가 젓가락 두 개를 한번에 집을 수 있을 때만 집는다.
• 비대칭 해결안을 사용. 홀수 번호의 철학자는 먼저 왼쪽을 집고 오른쪽을 집는다. 짝수 번호는 먼저 오른쪽 집고 왼쪽을 집는다.

철학자들이 굶어죽지 않도록 교착상태와 기아상태를 제거해야한다.

 

Monitor Solution(모니터 해결법)

식사하는 철학자 문제에서 교착 상태없는 해결법을 통해 모니터 해결법에 대해 알아보자.

모니터는 말 그대로 상태를 관찰하면서 접근한다.

철학자는 젓가락을 둘 다 사용할 수 있을 때만 집을 수 있게 제한하고 코딩을 위해 아래 데이터 구조로 표현한다.

 

 

젓가락을 집는 제어는 DiningPhilosophers.pickup(i)를 통해 집고 다 먹은 후 Diningphilosophers.putdown(i)로 젓가락을 놓는다.

philosopher i는 배가고프지만 젓가락을 집을 수 없을때 스스로 늦게 집도록 할 수 있다.

philosopher i 는 양 옆사람이 먹지 않는 경우(state[(i+4] % 5] != EATING && state[(i+1) % 5] != EATING)에만 state[i] = EATING으로 설정한다.

 

philosopher i는 배가고프지만 젓가락을 집을 수 없을때 스스로 늦게 집도록 할 수 있다.

젓가락을 집는 제어는 DiningPhilosophers.pickup(i)를 통해 집고 다 먹은 후 Diningphilosophers.putdown(i)로 젓가락을 놓는다.

이 방법은 인접한 두 철학자가 동시에 젓가락을 집는 것을 방지할 수 있고 굶어 죽는 문제도 해결할 수 있다.

커널에서 동기화

윈도우와 리눅스에서 커널 동기화에 대해 알아보자.

윈도우

윈도우 운영체제는 멀티스레드 커널로 리얼타임 애플리케이션과 멀티 프로세서를 지원한다.

윈도우는 dispatcher object를 제공한다. dispatcher object로 스레드는 뮤텍스, 세마포어, 이벤트 및 타이머를 비롯한 여러 메커니즘에 따라 동기화된다.

dispatcher object는 signabled과 nonsignabled 상태 둘 중 하나다.

signaled 상태에서 lock을 획득하면 non-signled 상태로 된다. non-signled 상태에서 lock을 해제하면 signled 상태가 된다.

• signaled : 디스패처 객체가 사용 가능하고 스레드가 객체를 획득 할 때 block 하지 않는다.
• nonsignabled: 디스패처 객체를 사용 불가능하고 스레드가 객체를 획득(접근) 할 때 block 한다.

dispatcher object와 thread와 state에 관계가 있다. thread가 signaled dispatcher object를 block하면 해당 상태가 ready 에서 waiting으로 바뀌고 thread는 해당 객체에 대한 wait queue에 배치된다.

dispatcher가 signaled로 상태가 바뀌었을 때 커널은 스레드가 해당 객체를 기다리는지 확인한다. 만약 스레드가 기다리고 있으면 커널은 하나 이상의 스레드를 대기상태에서 실행할 수 있는 준비상태로 바꾼다.

 

critical-section object

커널 개입없이 스스로 뮤텍스를 얻고 릴리즈할 수 있는 유저모드다.

멀티프로세스 시스템에서는 릴리즈 할 때 까지 스레드가 스핀락한다. 스핀락이 너무 길어지면 critical-section object를 획득한 스레드는 커널 뮤텍스를 할당하고 CPU를 양보한다.

 

transactional memory

트랜젝셔널 메모리는 데이터베이스 이론에서 기원한 것으로 프로세스 동기화를 위한 전략을 제공한다.

memory transaction은 원자적으로 메모리 읽기-쓰기 작업의 sequence를 의미한다. 모든 연산이 완료되어야 memory transaction이 완료되는 것이고, 그렇지 않으면 모든 연산은 roll back 된다.

mutex lock과 세마포어와 같은 동기화 방법은 교착상태와 같은 잠재적인 문제를 일으킬 수 있으나, transaction memory system은 개발자가 잠재적인 문제를 책임질 필요가 없어지고 메모리 시스템이 원자성을 보장해준다. 이에 대한 예시로 아래 코드를 보자.

첫번째 update 코드는 개발자가 acquire나 release의 순서가 잘못된다거나 개발자가 atomic한 코드를 보장해야하지만, 두번째 update에서는 시스템에서 atomic을 보장해준다.

 

Software Trasactional Memory(STM) : sw만으로 구현된 것. 트랙잭션 블록 안에 검사 코드를 삽입하여 동작.

Hardware Trasactional Memory(HTM) : 개별처리기 캐시에 존재하는 공유 데이터의 충돌을 해결하고 관리하기 위해 하드웨어 캐시 계층 구조와 캐시 일관성 프로토콜을 사용. -> 코드 계측 필요없음 -> STM보다 적은 오버헤드

Summary

• 고전적인 프로세스 동기화 문제로 bounded-buffer, readers-writers, dining-philosopheres 문제가 있고 mutex lock, semaphore, monitor, condition variable로 해결할 수 있다.
• windows에서는 디스패처 오브젝트와 이벤트를 사용하여 프로세스 동기화 도구를 지원한다.
• 리눅스는 atomic variable, spinlock, mutex lock을 사용하여 race condition과 같은 문제에 대응한다.
• POSIX API는 mutex lock, semaphore, conditional variable을 지원한다.
  • semaphore는 named와 unnmaed가 있으며 관련되지 않은 여러 프로세스는 name을 통해 named semaphore에 쉽게 접근할 수 있다.(세마포어가 프로세스 단위인 것을 기억하자)
  • unnamed의 경우 쉽게 공유되어선 안되고 공유메모리에 배치해야한다.
• 크리티컬 섹션 문제를 해결하기 위한 대체 접근 방식에는 transactional memory, OpenMP 및 함수형 언어가 있다.