[OS] Synchronization (2)

이 글은 포스텍 박찬익 교수님의 CSED312 운영체제 수업의 강의 내용과 자료를 기반으로 하고 있습니다.

확실히 나중에 글을 쓰니까 더 빨리 써지는 것 같긴 하다.

그래도 이걸 지금 몰아서 쓰려니까 다른 과제도 못하고 바쁘다..

다음부턴 매주 주말에, 지난 주 공부한 걸 쓰도록 노력해봐야겠다.

이번 포스트에서는 저번 시간에 배운 lock, cv, semaphore를 구현하는 방법에 대해서 배운다.

1. Lock & Condition Variable

Lock을 구현하기 위해서는 lock에 대한 접근이 mutual exclusive해야 한다.

1. Implementing in Uniprocessor

Uniprocessor는 interrupt를 제외하고는 비자발적으로 thread의 실행 흐름이 바뀌지 않는다.

따라서 interrupt disable을 통해 mutual exclusion을 구현할 수 있다.

이제 interrupt disable을 통해 lock- queueing lock -을 구현해보자.

Queueing lock이란 lock이 BUSY일 때, busy waiting을 하지 않고 waiting queue에 해당 thread를 등록시키고는 waiting 상태로 만들어버리는 lock을 의미한다.

신경써서 봐야할 부분은 다음과 같다.

• release시 깨워야 할 thread가 있다면 value를 FREE로 세팅하지 않는다. Thread가 일어나면서 별도의 동작 없이 BUSY를 가질 수 있게 하기 위함이다.

• Shared state에 접근하기 전 interrupt를 끄고, 완료하고 나면 interrupt를 켜라!

2. Implementing in Multiprocessor

하지만 Multiprocessor에서는 interrupt disable만으론 부족하다.

해당 processor의 interrupt를 막는다고 해도, 다른 processor에서 여전히 접근할 수 있기 때문이다.

따라서! 우리가 이전 포스트에서 언급한 atomic load and store을 이용한 lock이 등장할 차례이다.

Spin Lock

가장 간단한 구현법은 spin lock이다.

Spin lock은 test_and_set 이라는 atomic operation을 사용해서 구현한다.

참 단순무식한 구현인데, 그냥 될 때까지 계속 test_and_set을 통해 점유를 시도하는 것이다.

한 가지 헷갈리지 말아야 하는 점은 test_and_set은 세팅 이전 값을 반환한다는 것이다. 세팅한 값을 반환하는 게 아니다!

곧, while문을 탈출하는 경우는 lockValue가 FREE여서 test_and_set이 FREE에서 BUSY로 덮어씌우는데 성공하고, FREE를 반환하는 경우이다.

Lock

이 Spin lock을 사용해서 Queueing lock을 구현해보면 위와 같다.

Uniprocessor의 Queueing lock을 이해했다면 별 무리 없이 이해할 수 있을 것이다.

Scheduler

• suspend: 전달받은 lock을 release하고, thread switing을 한다.

• makeReady: 전달받은 thread를 ready 상태로 만든다.

이것도 Uniprocessor의 Queueing lock을 이해했다면 별 무리 없이 이해할 수 있다.

의문점

아직도 이해가 잘 가지 않는 부분이 있다.

왜 disable interrupt와 spinlock aquire을 둘 다 할까?

현재까지 이해한 바로는 interrupt handler의 deadlock을 막기 위함이 아닐까 싶다.

Interrupt handler가 shedular에 접근할 일이 있을수도 있는데, 만약 이미 spinlock이 aquire 되어있다면 handler가 deadlock에 빠져버릴 테니까.

근데 handler가 접근할 일이 있나??? 잘 모르겠다. ㅠㅠ

Condition Variable

한 가지만 알면 된다.

disable이나 spinlock을 하지 않는 이유는 이미 lock에 의해 mutual exclusion이 보장되어 있기 때문이다.

나머지는 그냥 당연한 코드들이다.

2. Semaphore

Implementation

내 생각엔 PPT의 코드에 오류가 있는 것 같다.

PPT의 코드대로라면 value가 변화하지 않는다.

여하튼, 역시 그냥 읽어보면 이해가 갈 것이다.

Semaphores considered Harmful

이전 포스트에서도 언급했듯이, semaphore은 lock & CV에 비해 그닥 유용하지 못하다.

Semaphore를 1으로 초기화해서 lock처럼 쓰고, 0으로 초기화해서 CV처럼 쓰고… 이렇게 복잡하게 할 바에 그냥 lock & CV를 쓰는게 낫다.

그리고 애초에 CV의 stateless condition을 semaphore로 구현하기 상당히 귀찮다.

Implementing CVs using Semahphores

semaphore로 CV를 구현하려면 대강 이정도 방법이 떠오를 것이다.

근데 이거 다 문제가 있다.

첫 번째 건 우선 stateless하지 않다. signal()을 먼저 호출하고 wait()을 하면 wait이 되지 않는다.

두 번째 건 나름 stateless하긴 한데, 문제는 race condition이 발생한다.

release와 P() 사이에 다른 thread가 끼어들어서 signal()를 호출하게 되면 waiter가 영원히 while문을 탈출할 수 없게 된다.

세 번째 것도 여전히 race condition이 존재한다.

FIFO bounded buffer를 사용해서 구현이 가능하긴 한데, 그럴바에 차라리 그냥 CV를 쓰는게 낫다.

3. Communicating Sequential Processes

위 처럼 복잡하게 locking을 하지 않고 synchronization을 구현할 수 있을까?

Communicating Sequential Processes은 아예 하나의 thread만 shared object를 접근할 수 있도록 제한해서 synchronization을 구현한다.

이 구현에 따르면, shared object에 접근하는 유일한 방법은 해당 thread에 메세지를 보내는 것으로 제한된다.

이때 이 메세지는 queueing 되어 하나하나 순차적으로 처리되고, 자연스럽게 race condition이 발생할 수 없게 된다.

Bounded Buffer를 CSP로 구현한 예제를 보자.

Shared object thread는 메세지를 받고, 이에 따른 동작을 수행하는 구조이므로 필연적으로 switch-case나 if문을 이용한 event driven 방식으로 동작하게 된다.

4. Reader Writer Problem

Synchronization과 관련된 아주 유명한 문제가 있다.

어떤 데이터베이스를 여러 개의 process가 공유한다고 해보자.

일부 process는 데이터베이스를 update할 것이고, 일부 process는 데이터베이스를 read할 것이다.

각각을 writer와 reader라고 하자.

여러 reader가 동시에 데이터베이스에 접근하는 것은 아무 문제가 없다.

따라서 reader간에는 별다른 exclusive access가 필요하지 않다.

하지만 만약 writer와 reader가 데이터베이스에 동시에 접근하게 된다면 정말 예측 불가능한 결과가 나올 것이다.

따라서 writer는 exclusive access를 가져야만 한다.

이 synchronization을 구현하라는 문제가 Reader Writer Problem이다.

굉장히 많은 해법이 존재하는데, 가장 간단한 두가지는 다음과 같다.

1. No reader kept waiting unless writer already has permission to use shared object

2. Once writer is ready, it performs write asap

첫 번째 해법은 reader를 우선시하는 것이다.

아무도 reading하고 있지 않아야 write할 수 있다.

반대로 두 번째 해법은 writer를 우선시하는 것이다.

아무도 writing하고 있지 않아야 read할 수 있다.

하지만 두 해법 모두 문제가 있다.

첫 번째의 경우 writer가 starvation을 겪을 수 있다.

반대로 두 번째의 경우 reader가 starvation을 겪을 수 있다.

아래는 첫 번째 해법에 대한 코드이다.

• semaphore rw_mutex initialized to 1
• semaphore mutex initialized to 1
• integer read_count initialized to 0

뭔가 어려워보이지만 간단하다.

1. Reader가 한 명이라도 있으면 rw mutex를 걸어서 writer를 막는다.

2. 아무도 reading하지 않을 때 rw mutex를 풀어서 writer를 진입시킨다.

3. read_count는 shared state이므로 mutex를 통해 mutual exclusive하게 접근한다.