Load-Linked 해서 flag가 0인걸 확인했어도, 그 사이에 flag가 바꼈을 수도 있음
if 문으로 한 번 더 검사하고, flag 값 바꿔줌
int LoadLinked(int* ptr) {
return *ptr;
}
int StoreConditional(int* ptr, int value) {
if (LoadLinked 명령 후, *ptr이 변경되지 않은 경우) {
*ptr = value;
return 1;
} else {
return 0;
}
}
문맥 교환 비용이 과도해질 수 있음 스레드가 100개 이상이면, 계속 Context Switch
특정 스레드의 기아를 막을 수 없음 → 공정성이 무너짐
2. 큐사용: Sleep Lock
Sleep에 들어가면 대기 큐로 가게 함 락 사용이 가능할 때, 대기중인 스레드를 깨움
필요한 시스템 API
park()
스스로 대기 상태로 전이
unpark(threadID)
threadID로 지정된 스레드를 깨움
TestAndSet으로 Sleep Lock 구현
lock 자료구조 초기화
typedef struct __lock_t {
int flag; // 임계영역 진입용
int guard; // flag와 큐 동작 보호용
queue_t* q; // 락 대기자 전용 큐
} lock_t;
void lock_init(lock_t* m) {
m->flag = 0;
m->guard = 0;
queue_init(m->q);
}
lock & unlcok 사용
처음에 flag와 guard가 0으로 세팅되어 있음
A 스레드가 lock 진입 TestAndSet에서 Guard 검사로 1로 바뀜 + 스핀락 안 걸림 if (m→flag == 0)에 의해 flag를 1로 설정하고 guard를 0으로 세팅함
이제 B 스레드가 Lock에 진입 while문에 안 걸림 = 스핀락 발생 X, 만약 A가 guard=0 안 했으면 스핀락 ㅇㅇ
A가 flag를 1로 해둬서 else문으로 들어가서 본인을 queue에 넣음 guard=0으로 세팅함 이제 park()을 해야 하는데, 이때 A가 unlock 과정에서 Unpark() 해버림 4. A가 unlock 과정에서 Queue가 비어있지 않으니까 else 문으로 들어가서 unpark()을 수행해버림 5. B 스레드가 park()을 하면 더이상 unpark() 해줄 수 있는 애가 없게 됨
void lock(lock_t* m) {
while(TestAndSet(&m->guard, 1) == 1) ;
if (m->flag == 0) {
m->flag = 1;
m->guard = 0;
} else {
queue_add(m->q, gettid());
m->guard = 0;
park(); // 이 때, 경쟁조건이 발생할 수 있음
}
}
void unlock(lock_t* m) {
while(TestAndSet(&m->guard, 1) == 1) ;
if (queue_empty(m->q))
m->flag = 0; // Lock 대기자 없을 때만 flag 해제
else
unpark(queue_remove(m->q));
// flag 해제 X, 다음 스레드를 깨움
m->guard = 0;
}
Wake Up/Waiting Race 문제점
A 스레드: park() 직전에 인터럽트 당함
B 스레드: 락 사용 종료 → 큐에 대기자가 없으므로 락을 해제함
A 스레드: 남은 park() 마저 수행 → 영원히 못 깨어남
해결
setpark() 사용 : 다른 스레드가 미리 unpark() 하면 park()은 수행 X