동기화 문제
멀티프로세스, 멀티쓰레드 환경에서 공유되는 자원을 동시에 접근할 때 생기는 문제이다. 이런 상황을 race condition이라고 한다.
위 예제에서, 두명의 사람이 은행에서 돈을 뽑는다고 가정하자. 계좌(account)에 100이 들어있고, amount가 둘 다 10이라고 가정할 때, A가 파란색 첫번째 줄에서 100을 불러와 balance에 넣고, 10을 빼서 balance를 90으로 세팅하였다. 이때 context switch가 일어나 B에게 코드가 넘어갔다면, 아직 put_balance를 하지 않았기 때문에 B의 빨간색 첫번째 줄에 balance에 100이 들어가게 된다. 같은 동작이 일어나고 put_balance를 하면 90이라는 값이 전역변수 balance에 들어가고, 여기서 또 context switch가 일어나 코드가 A에게 넘어가서 put_balance를 해주면 여기서도 전역변수 balance에 90이 들어간다. 결국, 100에서 두명이 합쳐 20을 뺐는데 90이 남는 상황이 벌어진다.
이렇게 공유되는 자원에 대한 접근을 컨트롤하는 매커니즘이 synchronization이다.
쓰레드/프로세스의 Shared Resources
- thread 동기화 문제 : 한 프로세스 내에 쓰레드들은 code, global변수, static변수, 동적메모리 영역인 힙을 공유한다. 이 자원들을 접근할 때 동기화문제가 생긴다.
- process 동기화 문제 : 프로세스는 원칙적으로 CPU에서 동시에 돌아갈 수 없지만, 프로세스끼리의 협력을 위해 IPC(Inter Process Communication)을 할 수 있다. 이를 위해 프로세스들은 공유메모리(Shared-memory)라는 특정 영역을 동시에 접근할 수 있다.
Critical Section
프로그램에서 자원이 공유되는 section. critical section에서는 오직 하나의 thread만 코드를 실행할 수 있다.
Critical Section 규칙
- Mutual exclusion이 지켜져야 한다. -> 오직 하나의 쓰레드만 Critical Section에 접근.
- 만약 어떤 thread가 Critical Section에 있다면 그 thread는 반드시 합리적인 시간 안에 작업을 끝내고 나와야 한다. 또한, Critical Section 밖에 있는 thread는 Critical Section 안에 있는 thread를 방해하면 안된다.(progress)
- Bounded Waiting -> Critical Section에 진입하기 위해 기다리는 밖에 있는 thread는 언젠가는 Critical Section에 진입할 수 있어야 한다. -> 무한으로 기다리는 것 X
- Critical Section에 진입하는 것과, Critical Section이 존재하는 것으로 발생하는 overhead는 Critical Section 안에서 수행되는 작업보다 작아야 한다.(performance)
Critical Section을 보호하는 매커니즘
- Locks : 공유되는 자원을 사용하는 동안 다른 프로세스나 쓰레드가 접근하지 못하도록 lock 하는 방법이다. critical section에 들어가기 전에 acquire()을 호출하고, 나와서 release()를 호출한다.
- Semaphores(higher-level) : 깃발이라는 뜻으로, critical section으로 진입해도 되는지, 아닌지 판단해준다. binary semaphore(Mutex), counting semaphore가 있다.
- Monitors(higher-level) : 나중에
- Messages : 나중에
1. Locks
- Lock에 사용되는 함수
- acquire() : 다른 thread가 Lock을 잡고있지 않으면, 해당 쓰레드가 Lock을 잡고 Critical Section에 진입한다.
- release() : Lock을 풀고 acquire()을 호출한 다른 쓰레드를 wake up 한다.
위의 예제에서 T1에서 A줄을 실행하면 T1이 Lock을 잡는다. T1이 Lock을 잡고 있는 와중에 T2가 A줄을 실행하면 대기 상태에 들어간다.(spinlock) T1에서 R줄을 실행하여 Lock을 풀면 그때 T2가 Critical Section에 진입한다. *aquire()는 caller(thread)가 Lock을 잡고 있으면 다른 return을 하지 않는다.
Lock에 관한 Thinking
Thread T1이 먼저 실행되어 acquire()을 먼저 호출하고 화살표 방향에서 context switch가 일어난다면, 전역변수인 held는 0인 상태이고, T2가 실행된다. T2에서 while문은 held가 0이기 때문에 실행하지 않고 held를 1로 세팅한 후 critical section에 진입한다. 이때 context switch가 일어나면 T1에서 l->held=1;을 실행하고 T1도 critical section으로 들어간다. 결국, mutual exclusion이 지켜지지 않는다.
Solution for Atomic Operation
Software algorithm을 활용한 해결법 : 알고리즘을 이용해 해결한다.
- Dekker's algorithm
- Peterson's algorithm
Hardware instructions : CPU 설계에 atomic instruction을 넣는다.- Test-and-Set
- Compare-and-swap
Disable/reenable interrupts : 인터럽트를 불가능하게 해 context switch를 막는다.
Peterson's algorithm
Test-and-Set
Compare-and-Swap
Disable/reenable interrupts
커널 내부에서만 작동한다. 외부 이벤트를 막아서 context switch가 일어나지 않도록 한다. 멀티프로세서에서 여러개의 thread가 동시에 acquire을 동시에 수행하면 문제가 된다. 또한, critical section이 너무 길면 그동안 event를 받지 않기 때문에 어떤 중요한 event를 놓치거나 지연시킬 수 있다.
**spinlock과 disabling interrupts는 primitive synchronization이다. 이것들은 critical section이 짧고 단순할 때만 유용하다. 따라서 higher-level synchronization이 필요하다.
2. semaphores
semaphore에는 두 연산이 있는데, wait / signal이 있다. wait에서는 semaphore가 열려있을 때. 그러니까 critical section에 진입할 수 있을 때 -1을 해주어 semaphore을 닫아주고 critical section에 진입한다. signal에서는 critical section에서 나올 때, +1을 해주고 semaphore을 열어준다. semaphore가 닫혀있는 상태를 block이라고 한다.
Binary Semaphore(Mutex)
오직 하나의 쓰레드만 critical section에 들어간다. counter가 semaphore가 열려있으면 1, 닫혀있으면 0이다.
Counting Semaphore
여러개의 쓰레드가 한번에 critical section에 들어간다. counter는 N으로 세팅된다.
Deadlock
모든 쓰레드가 critical section에 들어가지 못하고 기다리고 있는 상태이다.
동기화 문제
Bounded buffer problem
버퍼가 producer에서 추가되고 consumer에서 삭제되는데, 이 둘이 서로 독립적으로 동작하는데, count++와 count--는 어셈블리어로 변환되면 3줄이 된다. 따라서 동기화 문제가 발생할 수 있다.
Dining Philosopher
그림에서 모두가 배고파서 동시에 오른쪽 젓가락을 들면 어느 누구도 식사를 할 수 없다.
Semaphore의 문제점
- 전역변수를 갖고 있기 때문에 어떤 다른 코드에서 이를 참조하여 값이 망가질 수 있다.
- critical section과 coordination가 동시에 구현되어 이등 사용에 제약이 없고, 프로그래머에 모든 것을 맡긴다.
- 프로그래머가 wait과 signal을 적절히 잘 사용해야 한다.
- deadlock, starvation이 있다.
해결 -> monitor
모니터는 컴파일할 때 자동으로 삽입되는 소프트웨어 모듈인데, 공유된 데이터에서 작동하며 동기화를 자동으로 제공한다. 모니터의 예로 아래의 예가 있다.
Ref. 충북대학교 조희승 교수 OS Course
