race condition
김씨가 ATM기에서 돈을 인출하려고 한다.
인출할 수 있는 ATM에 프로그래밍 되어 있는 코드는 다음과 같다.
int withdraw(account,amount)
{
balance = get_balance(account);
balance = balance - amount;
set_balance(account, balance);
return balance;
}김씨가 20만원이 있었는데 5만원을 뺐다.
위에 코드대로라면, 잔액을 조회하고, 잔액에서 인출할 금액을 빼서 잔액을 다시 업데이트 해준다.
문제는 ATM기가 하나만 있는게 아니라 여러개가 있다는 것이다.
만약에 2개의 ATM기에서 동시에 같은 통장에서 돈을 인출한다면 어떻게 될까??
위에 코드는 어떠한 상황이냐면, 잔고가 20만원인 상태에서 5만원을 A atm기에서 인출을 했는데 set_balance에서 업데이트 되기 직전에 B atm기에서도 5만원을 인출을 한 것이다. 아직 A에서 업데이트 하지 않았기 때문에 잔고는 줄어들지 않은 상태이고 B에서 5만월을 인출해 15만원이 업데이트 되었다. 문제는 A에서도 balance 값이 15만원이라 두 atm기에서 5만원씩 뺐는데도 최종적으로 15만원이 잔고로 남았다.
이러면 돈을 계속 복사할 수 있기 때문에 큰 문제가 될 것이다.
더 심각하게는, 만약 A atm기에서 1만원만 빼고, B에서 20만원을 뺐다. 그러면 결과적으로는 잔고가 19만원이 남게 된다. A atm기의 balance 변수가 overwrite 되버리기 때문이다.
이렇게 thread가 동시에 shared resource에 접근을 해서 조작했을때 문제가 발생한것을 race condition이 발생했다고 한다.
critical section
shared resource에 접근하고 수정하는 코드를 critical section이라고 한다.
critical section에 thread들이 동시에 접근하게 되면 race condition이 일어난다.
int withdraw(account,amount)
{
balance = get_balance(account);
balance = balance - amount;
set_balance(account, balance);
return balance;
}balance라는 global variable을 고치려고 동시에 접근할 수 있기 때문에, 이 파트가 critical section이 된다.
Synchronization
그렇다면 ATM a에서 돈을 다뽑고 프로그램이 끝날때까지 기다리고 ATM b가 뽑게하면 되지 않겠느냐 라는 생각을 할 수 있다. 그게 맞다. 이렇게 하면 critical section에서 race condition이 일어날 가능성을 차단할 수 있다.
이렇게 막는것을 Synchronization이라고 할 수 있다.
Locks
그러면 어떻게 synchronization할 수 있을까? 바로 Locks 자료구조를 이용하면 된다. resource를 한번에 한 process만 사용할 수 있게 하는 것이다.(mutual exclusion)
이 lock 자료구조는 두가지 함수를 제공한다.
- void acquire() :lock이 free될때까지 기다렸다가 잡는다.
- void release() :unlock하고, acquire()를 기다리고 있는 thread를 깨운다.
- lock은 처음에는 free하다.
- free 상태의 lock을 acquire하면 lock을 얻을 수 있고, lock이 할당되어 있는 상태에서 다른 process가 acquire() 하면 lock 잡고있는 process가 release 할때까지 기다려야 한다.
- critical section에 들어가기전에 acquire()를 호출하고, critical section을 지나고 나서 release()를 호출한다.
thread T1에서 lock을 잡고실행하고 있었는데, thread T2가 acquire()하려고 했다. 하지만 T1이 lock을 아직 release 하지 않았기 때문에 T2는 대기하게 된다.
그다음 T1도 마찬가지로 T2가 release 하기 전까지 대기하게 된다.
결국 정리하자면, mutual exclusion을 제공하는 lock을 사용해서 critical section을 보호해서 race condition이 일어나지 않게 했다.
Locks의 요구사항
Correctness
- mutual exclusion : critical section에 한번에 한 thread만 접근할 수 있다.
- progress: 아무도 resource를 쓰지 않고 있다면 아무나 쓸수 있게 해줘야 한다.
- bounded waiting: resource를 사용하고 싶을때 기다리다보면 언젠간 자기 차례가 온다.
Fairness
- 각 thread는 lock을 얻을때 공정한 기회를 얻는다.
performance
- 경쟁상대가 있을때와 없을때 lock에 대한 time overhead
- lock의 종류(spin lock, busy waiting)에 따라 달라진다.
- critical section이 크고 자주 실행될수록 lock의 사용빈도가 높아지고, lock의 overhead가 높아지게 된다.
lock의 알고리즘
Peterson's Alogorithm
turn을 두어서 어떤 thread가 쓸것인지 결정한다.
interested는 0과 1만 있기때문에
1-my_id를 하면 상대방의 인덱스번호가 된다.
들어오면서 자신을 true로 만들어서 resource를 사용할 의사를 내비친다.
그리고 turn은 other를 해주어서 상대방이 먼저 사용할 수 있게 양보한다.
while문으로 들어오면 상대방이 사용할 마음이 있고, turn도 상대방 턴이면 나는 while문을 계속 반복하면서 대기하고, 상대방이 둘중하나라도 아니게 된다면 내가 lock을 잡게 된다.
어쨌든 둘중 하나의 task만 들어올 수 있게 되고, 빈 리소스에 대해서 두 task가 대기하는 일은 없게 된다.
따라서 mutual exclusion(critical section에 한번에 하나의 thread만 들어옴),
progress(resource가 free라면 thread가 lock을 가짐), bounded watiting(resource를 사용하고 싶을때 기다리다보면 언젠간 자기 차례가 온다.)
lock을 구현하기 위해 hardware로 도와줌
Test-And-Set
하드웨어가 새로운 값으로 업데이트해주고, 원래있던 값을 가져오는것을 한번에 처리해준다.
기존 spinlock에다가 Test-And-Set을 적용시켰다.
만약 thread A,B가 있다고 한다면, 기존에 lock은 0이었고, thread A가 lock에 접근하면 lock을 1로바꾸는 동시에 원래있던 값인 0을 리턴한다. 리턴값이 0이므로 while문을 빠져나오게 된다. 이상태에서 thread B가 접근한다면 똑같이 lock의 값을 1로 바꾸는데 기존에 1이었기때문에 1을 리턴받아서 while문에 갇혀있게 된다.
threadA가 release를 통해 lock을 0으로 바꾸면 그제서야 thread B가 lock을 1로바꾸고 0을 리턴받으면서 빠져나가게 된다.
소프트웨어로 코드로 구성하면 안되나??라고 생각할 수 있는데
int TestAndSet(int *v,int new){
int old = *v;
*v = new;
return old;
}이렇게 짜볼수 있다. 하지만 결국에는 critical section이 되어 두 프로세스가 동시에 접근하게 되면 원하는 결과를 도출할 수 없게 된다. 하드웨어가 한번에 처리해줘야만 하는 부분이다.
이렇게 읽고-수정하고-쓰고를 한번에처리해주는 걸 Atomic instruction이라고 한다.
compare-and-swap
- x86, Sparc, 등등에서 지원된다. 당연히 하드웨어에서 일어난다.
- test-and-set 처럼 새로운 값을 쓰고 old 값을 리턴하는건 같지만, 여기에는 expected 값이 추가된다.
- expected는 내가 예상하는 값이다. 코드로 나타내보자면,
int CompareAndSwap(int *v, int expected, int new){
int old = *v;
if(old == expected)
*v = new;
return old;
}
void acquire(struct lock *1){
while(CompareAndSwap(&1->held, 0 ,1));
}old 값이 expected 값과 같다면 new값으로 바꿔주고 old값을 리턴한다.
old 값이 expected 값과 다르다면 old값만 리턴해준다.
한 예로, process가 lock을 acquire할때는 CAS(0,내PID)를 해서 lock이 0이라면 내PID로 바꿔주고 lock을 가져간다. 그러면 다른 process들은 0을 expected하고 있기 때문에 lock이 0이 될때까지 대기하게 된다.
mut(aul)ex(clusive) lock
busy-wait:resource를 할당받을때까지 계속 두드려본다.
blocked: 다른 thread가 lock을 잡고 있다면 lock을 release해서 깨워줄때까지 blocked 되어서 기다리고 있는다.
spinlock
- mutex lock중에서
busy-wait를 하는 lock 구현체를spinlock이라고 한다.
✍️장점
- 구현하기가 쉽다.
- critical section이 짧을때 유리하다. critical section이 길다면 계속 두들겨보는건 시간낭비가 된다.
- context switch가 필요없다.
✍️단점
- busy-waiting은 system resource(cpu,memory,etc..) 낭비가 심하다.
semaphore
- 숫자 값 S를 가진다.
- S개까지 동시에 semaphore를 잡을 수 있다.
- wait() : semaphore를 잡을때 사용, S가 1씩 줄어든다. 당연히 S가 0보다 커야한다.
- signal(): semaphore를 반환할때 사용, S가 1 늘어난다.
busy-waiting semaphore
struct semaphore{
int S;
};
void wait(struct semaphore *sem){
while(sem->S <= 0);
sem->S --;
}
void signal(Struct smaphore *sem){
sem->S++;
}semaphore가 2개인 상태에서
만약 6개의 thread가 동시에 wait에 접근한다면 -4가 되어 버린다. 이 구현으로는 우리가 원하는 대로 구현이 되지 않는다.
이렇게 단순히 카운팅하는 방식으로는 동시에 접근하는 thread들을 관리할수가 없다.
semaphore 자체가 synchronization을 위한 구조체인데 이 semaphore를 구현하기 위해서는 synchronization이 필요한 상황이다.
Mutex lock을 사용해보자.
Mutex M
struct semaphore{
int S;
};
void wait(){
retry: M.acquire()
if(sem->S <= 0){
M.release()
goto retry
}else{
sem->S --
M.release()
}
}위 코드에서 볼 수 있듯이
먼저 mutex lock을 acquire하고 semaphore가 남아있다면 seamphore를 하나 가지고 lock을 release해주고, semaphore가 없다면 lock을 release 해주고 다시 시도하게 한다.
Implementing Blocking Semaphore
busy-waiting semaphore는 cpu와 memory 낭비가 심하기 때문에 이를 대체할 수 있는 semaphore 방식이 필요하다.
struct semaphore{
int S;
struct task *Q;
};
void wait(struct semaphore *sem){
sem->S--;
if(sem->S < 0){
add_this_task_to(sem->Q);
block();
}
}
void signal(struct semaphore *sem){
sem->S++;
if(sem->S <= 0){
P = remove_a_task_from(sem->Q);
wakeup(p);
}
}blocking semaphore는 들어갈때 토큰(semaphore->S)을 무조건 하나 가져간다. 그리고 나갈때 토큰을 무조건 하나 반납한다. 토큰을 가져갔는데 남아있는게 0보다 크거나 같다면 기다리고 있는 task가 없으므로 그냥 가져가면 되고, 토큰수가 0보다 작다면, 내가 들어가면 안되기 때문에 task가 block되어서 waiting된다.
이 코드도 기본적으로는 돌지 않는다. 왜냐하면 sem->S--이러한 증감 코드는 thread가 동시에 여러개가 들어왔을때, 나올수 있는 경우에 수가 다양하다. 따라서 synchronization 처리를 해줘야한다.
semaphore type
✍️Binary semaphore(= mutex)
- semaphore 초기값이 1이다.
- resource에 대해서 mutant exclusive를 보장한다.(한번에 하나만 들어갈 수 있다.)
✍️Couting semaphore
- Semaphore값이 N이다.
- resource를 N개의 thread가 잡게 해준다.
- semaphore가 남아있다면 thread가 접근할 수 있다.
Monitors
언어 수준에서 synchronization을 제공. 자바에서 사용한다.
member나 method에 synchronized를 붙여주면 한번에 한thread만 접근 가능하다.
컴파일러가 알아서 랭귀지 수준에서 처리해줌
Pthreads Synchronization
여러 lock과 semaphore를 구현할 수 있는 함수를 제공한다.
Deadlock
Thread A,B가 있고 mutex m1,m2가 있다.
이러한 상황에서 thread A는 m2를 acquire()을 해야지만 m1을 release할 수 있다.
thread B는 m1을 acquire()해야지만 m2를 release할 수 있다.
thread A와 B가 모두 원하는 mutex를 acquire하지 못해 waiting에 빠지게 된다.
이러한 현상을 deadlock이라고 한다.
리소스가 한개이상 필요한 상황에서 잘 발생한다.
리소스를 잡고있는데 추가적으로 더 잡으려고 할때 잡지못했을때, 지금 리소스를 잡고 waiting이 되면 deadlock이 발생할 수 있다.
정리하자면, thread들이 원하는 리소스가 서로에게 dependency에 걸려버린 상황이다.
Bounded buffer problem
✍️producer/consumer problem
producer들과 consumer들이 리소스 buffer로 연결되어 있다.
producer에서 buffer로 resource를 넣고, consumer는 buffer에서 resource를 꺼내온다. 하지만 producer와 consumer의 처리 속도는 다르다. producer가 consumer보다 훨씬 빠르다면, buffer는 overflow될 것이고(무제한 버퍼가 될 수는 없다.), 반대상황이라면 consumer는 버퍼에서 꺼내올 resource가 없을 것이다.
circular buffer
- in:data를 넣을 포인터
- out:data를 빼올 포인터
- in에 data를 넣으면 다음 칸으로 in 포인터를 전진시킨다.
- out포인터의 값을 빼면 다음으로 out 포인터를 전진시킨다.
두가지 기능을 구현해야한다.
1. buffer가 꽉차있는데 data를 넣지 않도록하기
2. buffer가 비어있는데 data를 빼지 않도록하기
- option
data가 증가할때마다 count를 센다.
count가 buffersize와 같아질때 까지만 data를 넣고
count가 0이면 data를 뺄 수 없다.
코드로 구현해보면
하지만 count를 세는것은 여러 쓰레드가 동시에 들어오면 코드가 잘 돌아갈 수가 없다.
1.mutex를 사용해서 critical section을 보호
2.semaphore 이용해서 구현
full은 빈공간, empty는 data가 차있는 공간이라고 볼 수 있다.
producer의 wait(&full)와 consumer의 signal(&full)이 대칭되는데, producer에서는 data를 넣었으니까 full을 하나 줄여주고, consumer에서는 data를 빼주는거니까 full을 하나 늘려준다.
empty도 마찬가지로 producer에서는 data를 넣어주니까 signal(&empty)을통해 empty를 늘려주고 Consumer에서는 data를 빼주니까 wait(&empty)를 통해 empty를 빼준다.
이 코드도 잘 돌지 않는다. semaphore가 thread들이 리소스를 N개까지 가져가는건 조절해주지만 그 안에서 thread끼리 resource를 순서대로 잘 가져갈 것이냐는 별개의 문제이다. 즉, semaphore는 동시에 thread가 몇개까지 들어가는지는 보장해주지만, thread끼리 서로 어떻게 상호작용하는지는 관여하지 않는다.
위 코드에서는 in에 여러 thread가 동시에 접근하게 되면 값을 예상할 수가 없을 것이다. 그래서 이 critical section을 보호해줄 mutex를 사용해야 한다.
Readers-writers Problem
게시판을 만들었다고 해보자. 해당 게시판에 많은 사람들이 동시에 들어왔다가 나갈 수 있다. Reader들은 상관없지만 Reader들과 writer가 겹친다면?? 아니면 writer와 writer가 겹친다면 해당 게시판은 예상할 수 없는 값으로 바뀔 것이다.
따라서 synchronization을 해줘야 한다. reader나 writer나 상관없이 한 사람이 들어가면 lock을 걸어서 다른 사람이 못들어오게 한다면?? 너무 프로그램의 성능이 떨어질 것이다. 따라서 다른 방법을 생각해봐야 한다.
Reader의 개수를 세는 변수를 하나 만들어주고, Reader가 모두 나가면 writer가 접근하게 해준다. 또한 writer가 있을때는 다른 reader나 writer가 접근하지 못하게 lock을 건다.
위 그림에서 Reader()를 보자.
wait(&mutex): reader가 들어오면 일단 mutex의 semaphore를 가져와서 다른 사람이 들어오지 못하게 막는다.(nr_reader를 동시에 접근하지 못하게 하기위해)
nr_reader++ : reader count를 하나 올려준다.
if(nr_readers == 1): reader수가 1이면
wait(&rw) : rw semaphore를 가져가서 rw를 0으로 만들고 writer가 접근하지 못하게 한다.
signal(&mutex) : semaphore mutex를 1로바꿔준다.(release해줌)
do_read(): 게시판을 읽는다
wait(&mutex): semaphore mutex를 잡아서 다른 사람들이 접근하지 못하게한다.(nr_reader에 동시에 접근하지 못하게 하기 위해서)
nr_readers--: 다읽고 나갈때, reader카운트를 다시 줄여준다.
if (nr_readers == 0) signal(&rw) : 안에 reader가 없으면 write가 접근할 수 있게 다시 rw를 1로 바꿔준다.
signal(&mutex) : mutex를 1로 바꿔줘서 다른 사람들이 접근하게 해준다.
void writer()를 보자.
wait(&rw): writer가 들어가면 rw semaphore를 잡고 rw를 0으로 바꿔줘서 reader가 들어가지 못하게 막는다. reader가 들어오면 Reader()에서 wait(&rw)에 걸려서 기다리게 된다.
do_write(): 게시판을 작성한다.
signal(&rw): rw를 다시 1로바꿔줘서 reader가 접근하게 해준다.
하지만 이게 잘 동작을 할것인가를 생각해보자.
이런 경우는 성능이 잘 나오고 싶다면 writer가 가끔 들어올때 이득이 많이 있을 수 있는 구조다. writer가 많이 들어오는 경우는 single lock으로 해도 큰 문제가 없을 것이다. 위 그림과 같은 경우는 writer에게 많이 불리하다. 왜냐하면, reader가 먼저들어가면 다른 reader들도 계속 들어올 수 있기 때문에 reader가 0이 안되고 계속 들어오게 된다면 writer가 무제한으로 기다릴 수 있는 상황이 올 수도 있다. 즉, starvation이 발생한다.
어떻게 고칠 수 있을까??
FIFO를 생각해보자. 만약에 reader가 줄 서있는 상황에서 writer가 들어오고 싶어서 줄을 섰다. 그러면 writer가 들어왔을때부터는 reader들이 들어오지 않고 기다리다가 기존에 있던 reader가 다 나가고 writer가 끝내고 나면 그 뒤에 들어오려고 했던 reader들이 들어오게 하면 된다. 이렇게 되면 writer가 기다려야 되는 시간이 bound 돼서 starvation이 발생하지 않는다.
어떻게 구현할 수 있을까??
reader가 들어올때 count만 하는게 아니라 writer가 누가 기다리고 있는지 봐야되고, 만약 writer가 기다리고 있다면 waiting queue에 해당 reader의 PCB를 대기시킨다. 언제까지 기다리냐면, writer가 자기 일을하고 rw semaphore를 놓을때가지 기다린다.
Dining Philosophers Problem
위 그림을 젓가락 한 개씩 이라고 생각해보자. 한사람이 젓가락 하나로는 밥을 먹을 수없지만, 양쪽에 있는 젓가락을 하나씩 잡으면 두개가 되므로, 밥을 먹을 수 있게 된다.
이렇게 하면 모든 사람이 행복하게 밥을 먹을 수 있게 될줄 알았다. 하지만 현실은 모든 사람이 먹지 못하게 됐다. 왜 이렇게 됐을까?
모든 사람이 자신의 왼쪽 젓가락을 잡고 오른쪽 젓가락을 잡는 규칙이라고 해보자.
모든 사람이 왼쪽 젓가락을 잡았다. 그러고 나서 오른쪽을 잡으려고 했더니 옆 사람들에 의해 오른쪽 젓가락은 이미 다른 사람에게 잡힌 상태이다. 바로 deadlock이다.
프로그램을 대입해보면,
프로그램 5개가 리소스가 2개씩이 필요하다. 모든 프로세스가 첫번째 리소스를 잡았는데 두번째 리소스를 잡지 못해서 모두 deadlock이 되어버린 상태이다.
solution
이 사람들이 밥을 먹을 수 있게 하는 방법은 무엇이 있을까?
1. 모든 사람들은 양쪽 젓가락을 동시에 잡으려고 한다. 만약 잡았다면 밥을 먹을 것이고, 못잡았다면 밥을 먹지 못한다.
이 방식은 컴퓨터에서 적용하기는 힘들다. 동시에 리소스를 두개를 잡는다는건 매우 힘든 문제이다.
-
젓가락을 왼쪽 잡고 오른쪽 잡으려고 시도를 하는데 안되면 다시 모두 내려놓는다. 그러고 나서 다시 왼쪽 오른쪽 순서로 잡으려고 한다. 이렇게 해서 둘다 잡히면 밥을 먹고 안잡히면 반복한다.
이렇게 하면 어쨋든 거의 모든 사람이 먹을 수 있게 된다.(운이 정말 나쁘면 굶을 수도 있다...)
컴퓨터에서는
thread가 리소스를 하나를 잡고 두번째까지 잡으려고 하는데 잡지 못한다면 모든 리소스를 내려놓고 다시 시도한다. -
모든 사람들이 왼쪽을 잡고 오른쪽을 잡는다. 하지만 모든 사람이 옆사람의 젓가락을 기다리다가 결국 맨처음까지 돌아오게 되면 deadlock이 걸려버린다. 이걸 없애고자 첫번째 사람은 왼쪽이 아닌 오른쪽을 잡으려고 한다. 오른쪽은 이미 다른사람이 잡고 있기 때문에 기다리게 되고, 이 과정에서 첫번째 사람의 옆사람이 밥을 먹을 수 있게 된다. 그러면 모든 사람이 결국 밥을 먹을 수 있게 된다.
implementation
모든사람이 왼쪽잡고 오른쪽 잡고 먹고 내려놓고를 구현해 놓았다. 하지만 이런 방식은 deadlock에 걸린다. pickup에서 왼쪽을 잡으려고 할때 모두 deadlock에 걸릴것이다.
2.
모든 사람은 왼쪽잡고 오른쪽 잡지만, 마지막 사람만 오른쪽 잡고 왼쪽 잡는 식이다. 이렇게 하면 deadlock을 해결할 수 있다.
