여러개의 thread, process가 있는데 공통 variable을 동시에 접근하고 고칠 수 있게 되면 문제가 발생한다. 그렇게 shared variable을 접근하는 것을 critical section이라고 한다. 그러고 처리 잘 못하면 race condition이라고 한다. 이를 막기 위해서 synchronization해야한다.
Synchronization
- 하나의 프로세스 안에서 thread들이 돌아가면서(address space공유 -> 따라서 보는 데이터가 동일) 이때 동시에 같은 데이터를 건드리면 어떻게 해야하나
- 어떤 프로그램이 존재한다. 이 프로그램은 값을 읽고 고쳐서 업데이트 하는 로직을 가지고 있다. 이 프로그램은 한군데에서 도는 것이 아니라 여러 곳(tread나 process), A와 B에서 돈다고 생각하면 중간에 값을 읽고 A, B라는 자신의 local memory에 읽은 값을 저장했다가 다시 global로 업데이트 하는 상황이 발생한다. 동시에 진행되는데 운이 나쁘면 두개가 꼬여서 정상적으로 돌지 않게 된다.
- shared resource에 접근한 것을 잘 처리해야하는데 이를 synchronization 혹은 coordination이라고 한다.
Synchronization Problem
- 여러개의 execution instance(thread, process)들이 shared resource에 대해서 값을 바꾸려고 할때 제대로 잘 안 해주면 concurrency때문에 프로그램의 행동이 non-deterministic하게 바뀔수 있다.
-> global variable에 대해서 thread나 process들이 동시에 바꾸려고 할때 운이 나쁘면 값이 correct하게 수정되지 않는다. - 이런 현상을 concurrency 때문에 두 개 이상의 thread들이 race condition을 만들었다. 라고 한다. race condition 때문에 non-deterministic한 값이 나오게 된다 라고 한다.
Critical Section
- 동시에 shared resource를 접근하거나 고치는 부분
- 여러 개가 동시에 들어가지 못하도록 mutual exclusion해야 한다.
Lock
어떤 데이터 영역이 있는데 mutual exclusion하게 접근할 수 있는 기능을 제공하는 데이터 object
- acquire() : 해당하는 lock을 잡으려고 한다. 처음에는 아무도 lock을 잡고 있지 않는 상태이다.(화장실 문이 열려있으면 들어가서 문을 잠근다.->그 화장실 칸은 acquire해서 가져가는 것이다.)
- release() : 잡으려고 하는 lock이 존재하거나 return을 하지 않으면 기다리고 있어야 한다.(화장실을 들어가려고 하는데 acquire되서 누군가가 쓰고 있다. 기다려야한다. 안에 있는 사람이 release하면 다음에 들어가서 쓴다.)
- Requirements for Locks
- Correctness
Mutual exclusion : 동시에 acquire 하면 안된다.
Progress : 아무도 resource를 안 잡고 있을때 누군가가 잡으려고 하면 acquire할 수 있어야 한다.
Bounded waiting : 내가 부르고 있는 애가 starvation하고 있지 않게 짜야한다. - Fairness
여러 thread들이 fair하게 chance를 가진다. - Performance
CPU 문제->time overhead가 없어야한다.
- Correctness
Implementing Locks
-
Software-only algorithms
- Peterson's Algorithm
내가 들어왔으면 TRUE바꿔주고 turn을 상대방에게 준다. 그리고 상대방이 turn인 동안(사용 중)은 기다리고 상대방이 돌아가려고 하면 기다린다.
- Peterson's Algorithm
-
Hardware approaches
- Disable interrupts
- interrupt를 꺼서 read, compare, update를 한번에 돌게 한다.
- preemption <- scheduler <- timer interrupt
- 문제 : 컴퓨터에서 interrupt를 끄면 알람시계가 울리지 않는다. 그렇게 되면 스케줄링을 하지 않는다. Kernel만 interrupt를 끄거나 킬 수 있다. 프로세서가 하나 이상일 경우
- Hardware atomic instructions
- Test-And-Set :
- Compare-And-Swap : cmpxchg
- Disable interrupts
Higher-level Synchronization
- Mutex Lock
- Mut(ual)ex(clusive) lock : acquire() to lock, release() to unlock
- busy wait : spinlock(lock이 acquire될때까지 spinning하면서 기다린다.)이라고 한다. spinlock ∊ mutex lock.
- 장점 : context switch가 일어나지 않는다. 구현이 쉽다.
- 단점 : lock holder가 잡고 있는 상황에서 preempted되면 나머지가 오랫동안 기다려야 한다.
- block : busy wait와 반대
- Semaphores
- critical section을 보호
- value S가 있어서 그것을 기준으로 행동을 결정한다.
- wait() : devrease S by one, and wait until S>=0
- Signal() : increase S by one
- Monitor
- Condition Variables
Bounded Buffer Problem
- producer/consumer problem이라고도 한다.
- producer : pipe(buffer)에 내용을 채워넣는 것
- consumer : buffer에 들어온 내용을 가져가서 사용하는 것
- producer와 consumer를 잘 구현해야 하는 문제
Readers-Writers Problem
성능을 최대화시키기 위해서 하나의 resource에 대하여 reader는 여러개가 들어와서 읽어도 된다. 대신 값을 바꾸려고 하는 writer는 reader랑 공존하면 안된다. 더불어 writer끼리도 공존하면 안된다.
- 어떤 shared resource에 대하여 multiple reader는 허용하고 writer는 하나여야 한다.
- Implementation with semaphores
- readcount : # of threads reading object
- mutex : control access to readcount
- rw : exclusive writing or reading
Dining Philosophers Problem
- 하나의 task가 여러개의 shared resource를 필요하게 되는 경우가 있는데 이때 이 resource를 잡는 순서를 잘 고려해야한다.
- deadlock 발생(circular wait가 있을 때 발생한다.)
