Lock 설계하기
방법1 - lock을 걸 때 아예 interrupt를 꺼 버리기
애초에 lock을 거는 이유가, 한 영역에는 하나의 스레드만 들어가도록 하는 것이니깐 lock을 걸 때 timer interrupt를 꺼버려서 다른 스레드가 스케줄링 되지 않도록 함
하지만 당연히 문제가 많아 보이쥬?
- 나쁜 스레드가 lock 잡아 놓고 무한루프 돌리면,,,,, 좆됨
- multiprocessor에선 돌아가지 않음
- timmer interrupt 키고 끄는 게 느림
방법2 - lock에 flag를 두고, flag 값에 따라 lock이 held인지 released인지 구분하자
void lock(lock_t *mutex){
while(mutex->flag == 1){
;
}
mutex->flag = 1;
}
void unlock(lock_t *mutex){
mutex->flag = 0;
}
위 코드를 보면 , unlock일 때는 flag가 0이고, lock일 때는 flag가 1임.
lock을 쥐고 있는 스레드가 있는 경우엔 flag가 0으로 바뀔 때까지 spinning하면서 기다렸다가, 자기가 쥔 다음에 flag를 1로 세팅함
근데 여기서 문제
test를 해서 lock을 얻으려 하기 직전에, interrupt가 걸려서 다른 스레드가 lock을 얻어버리고 다시 나로 돌아와서 나도 lock을 얻으면...??
이것 참 정말로 accident 아닙니까... 그니깐 여기서 문제는 test 한 다음 바로 lock 값을 세팅 안해서 그래. 그니깐
test와 set을 Atomic Operation으로 만들자
lock이 held 됐는 지 확인 후 lock 값을 세팅하는 방법에는 네 가지가 있음 : TestAndSet, CompareAndSwap, LoadLinked & StoreConditonal, FetchAndAdd & TicketLock
lock이 held인지 확인 후, 값 세팅하는 법
TestAndSet
int TestAndSet(int *ptr, int new)TestAndSet은 ptr에 new 값을 넣고, 이전 ptr 값을 리턴함
방법 3 - TestAndSet을 사용한 lock
void lock(lock_t *lock){
while(TestAndSet(&lock->flag, 1)==1){
;
}
}이렇게 lock을 걸어주게 되면, 위의 while문은 flag가 0이 될때까지 계속 돌아가면서, lock에 1을 넣어줌!
즉, TestAndSet을 계속 하던 중, 다른 스레드가 lock을 release하게 되면, TestAndSet은 현재 스레드가 lock을 잡았다는 뜻으로,flag에 1을 넣고, 이전 flag 값인 0을 리턴하게 되는 것 ㅎㅎ
Issues
correctness : lock이 empty인지 확인 후, get 하는 과정이 atomic하게 이루어지므로, 다른 스레드와 lock이 겹칠 일 X
Fairness : lock이 release됐을 때 스케줄링 된 스레드가 lock을 가져가게 되는 구조로, fairness에 대한 guarantee는 1도 X
Performance : 계속 spin하면서 lock이 있는 지 확인하므로, single CPU의 경우 계속 spin하는 게 부담이 됨
Compare And Swap
int CompareAndSwap(int *ptr, int expected, int new);CompareAndSwap은 ptr이 expected와 같다면, new로 세팅하고 이전 ptr값을 리턴한당
방법4 - Compare And Swap을 활용한 lock
void lock(lock_t *lock){
while(CompareAndSwap(&lock->flag, 0, 1)==1);
}완전 직관적인 코드인데, flag가 1일 때는 계속 spinning하고, 0일 때는 현재 스레드가 lock을 잡았다는 뜻으로 flag에 1을 넣은 후 CompareAndSwap이 0을 리턴하므로 while loop를 빠져나오게 된당.
Load-Linked and Store-Conditionals
int StoreConditional(int *ptr, int value);StoreConditional() 함수는 LoadLinked가 호출된 이후에 ptr에 누가 load한 적이 없으면, ptr에 value를 넣고 1을 리턴하고, 누가 ptr에 load한 적이 있으면 0을 리턴함.
그니깐 LoadLinked 실행 후 누가 ptr에 접근하지 않았을 때만 ptr에 value를 넣고 1을 리턴하는 것.
방법5 - StoreConditional을 사용한 lock
void lock(lock_t *lock){
while(1){
while(LoadLinked(&lock->flag)==1);
if(StoreConditional(&lock->flag, 1)==1){
return;
}
}
}그니깐 먼저 LoadLinked 함수로 lock의 flag가 1인지 계속 확인 후 0이 되면 while loop를 종료함. 그리고 StoreConditional 전에 lock->flag 값에 변화가 있다면(다른 스레드가 lock을 쥐게 되면), 다시 lock이 empty할때까지 spin함. 변화가 없다면, 내가 Lock을 쥐고 함수를 리턴함
void lock(lock_t *lock){
while(LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1))
}위에서 while loop의 종료 조건은 LoaLinked(&load->flag)==0이고, StoreConditional(&lock->flag, 1)==1이어야 함.
즉, flag값이 0이고, 내가 lock을 쥐는 것에 성공하여 flag를 1로 바꾼 경우에만 while loop를 빠져나오고 함수를 리턴하게 된다.
FetchAndAdd
int FetchAndAdd(int *ptr)ptr값을 1 증가시키고, 이전 ptr 값을 리턴해주는 함수이당
방법6 - FetchAndAdd를 사용한 ticket lock
void lock_init(lock_t *t){
lock->ticket = 0;
lock->turn = 0;
}
void lock(lock_t *lock){
int myturn = FetchAndAdd(&lock->ticket);
while(lock->turn != myturn)
;
}
void unlock(lock_t *lock){
FetchAndAdd(&lock->turn)
}먼저 lock 함수를 보면 myturn을 ticket에 1을 더하고, 그 이전 ticket 값으로 세팅함
그리고 unlock돼서 turn 값이 증가되고, 그 turn 값이 myturn과 일치하면 내가 lock을 잡게 됨!
이전 방법들은 lock이 release됐을 때 스케줄링 된 스레드가 lock을 가져갔다면, ticket lock은 lock을 가지려고 한 스레드의 순서대로 lock을 주게 되므로 fairness가 보장된다.
comment
위의 hardware supported atomic instruction들은 전부 spinning을 하면서 lock이 release 되기를 기다리기에 time slice를 spinning만 하면서 낭비하게 된다 ㅠㅠ
따라서 다른 스레드가 lock을 잡고 있다면 spinning하지 않고 쿨하게 cpu를 yield해서 다른 스레드가 일을 할 수 있도록 os까지 도와주는 방법이 있다.
하지만 context switching 비용ㅇ도 만만치 않기에... 뭐가 맞는 지는 상황에 따라 알아서 판단하도록
