락
- 락도 하나의 변수
- 락의 상태
- 사용 가능(available)
- 해제(unlocked 또는 free) : 어느 스레드도 락을 가지지 않음
- 사용 중(acquired) : 임계 영역에서 정확히 하나의 스레드가 락을 획득한 상태
- 락을 보유한 스레드에 대한 정보나 락을 대기하는 스레드들에 대한 정보 저장 가능
- lock() 호출을 통해 락 획득 시도
- 어떤 스레드도 락이 없으면 락을 획득, 임계 영역 진입
- 진입한 스레드를 락 소유자(owner)라고 부름
- 다른 스레드가 lock()을 호출하면 사용 중인 동안 lock() 함수가 리턴하지 않음
- 이 방식으로 다른 스레드들이 임계 영역 안으로 진입 불가
- 락 소유자가 unlock()을 호출하면 락은 다시 사용 가능 상태
- 대기가 없으면 사용 가능 상태
- 대기가 있으면 락을 획득하여 임계 영역 진입
Pthread 락
- 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex라고 부름
- 서로 다른 데이터와 자료 구조를 보호하기 위해 여러 락을 한 번에 여러 스레드가 서로 다른 락으로 보호된 코드 내에 진입할 수 있도록 함(fine-grained 락 사용 전략)
락의 평가
1. 상호 배제 지원
- 가장 기본 역할
- 락이 동작하여 임계 영역 내로 다수의 스레드가 진입을 막을 수 있는지 검사
2. 공정성
- 락 획득에 대한 공정한 기회
- 즉, 락을 전혀 얻지 못해 굶주리는(starve) 발생하는지 검사
3. 성능
- 락 사용 시간적 오버헤드 평가
- 경쟁이 없는 경우 성능
- 스레드가 실행 중 락을 획득하고 해제하는 과정에서 발생하는 부하
- 여러 스레드가 단일 CPU 상에서 락을 획득하려고 경쟁할 때 성능
- 멀티 CPU 상황에서 락 경쟁 시 성능
Test-And-Set (Atomic Exchange)
- lock()을 호출하여 플래그 값 검사(test)
- 플래그를 1로 설정(set)하여 보유(hold)함을 표시
- unlock()을 호출하여 플래그 값을 초기화
- 문제점
- 정확성
- 동시에 임계 영역에 진입하는 경우 문제
- 상호 배제 보장 실패
- 성능
- spin-wait라는 방법을 사용해 플래그 값을 무한히 검사
- 다른 스레드가 락을 해제할 때까지 시간을 낭비
진짜 돌아가는 스핀 락
- 해당 동작이 원자적으로 수행
- 플래그가 0이면 획득
- 플래그가 1이면 while 반복
- 제대로 상호 배제가 동작
스핀 락
- 락을 획득할 때 까지 CPU 사이클을 소모하며 회전
- 선점형 스케줄러
스핀 락 평가
- 정확성 만족
- 공정성 보장X
- 성능
- 단일 CPU : 오버헤드 상당
- 나머지 스레드들이 락을 획득하기 위해 CPU 사이클을 낭비하며 대기
- 멀티 CPU : 꽤 합리적
- 임계 영역 구간이 짧으면 락을 금방 획득할 수 있고 다른 CPU에서 대기하면 된다고 함
- (찾아보니 문맥 교환을 안해도 되서 비용을 아낌)
Compare-And-Swap
- expected 변수와 일치하는지 검사
- 호출한 코드가 락 획득 성공 여부를 알 수 있도록 함
- TestAndSet 명령어보다 강력
- 대기없는 동기화(wait-free synchronization)을 다룰 때 능력 발휘
- 단순히 스핀 락과 같은 식으로 만들어 사용하면 똑같이 동작
Load-Linked 와 Store-Conditional
- load-linked는 메모리 값을 레지스터에 저장
- store-conditional은 동일한 주소에 갱신이 없었던 경우에만 저장 성공
- 저장을 성공하면 load-linked가 탑재했던 값을 갱신
- 성공한 경우, store-conditional은 1을 반환, ptr이 가리키는 value 값을 갱신
- 실패한 경우, ptr이 가리키는 value 값 갱신X, 0 반환
- 플래그가 0이 되면 락 획득 가능 상태
-> store-conditional
- 성공하면 플래그 1, 임계 영역 진입
- 실패하는 경우
- store-conditional 호출 직전 인터럽트
-> 다른 스레드가 lock() 호출
-> 두 스레드 모두 store-conditional 호출하려는 상황
- 갱신이 없는 경우 store-conditional를 성공하기 때문에 다른 스레드가 성공한 이후 store-conditional를 호출한 스레드는 실패하게 됨
Fetch-And-Add
티켓 락
- turn을 사용하여 어느 스레드의 차례인지 판단
- 이전 방법과의 차이는 순서에 따라 진행
스핀 문제
간단한 해결법(양보)
- 락이 해제되기를 기다리며 스핀해야하는 경우 자신에게 할당된 CPU를 양보
- 락이 적고 스레드가 많다면 문맥 교환 비용이 상당하며 낭비가 심하다
- 굶주림 문제는 해결 못함
큐 사용(스핀 대신 잠자기)
- park() : 호출하는 스레드를 재우는 함수
- unpark(threadID) : ID의 스레드를 깨우는 함수
- guard : 플래그와 큐의 삽입/삭제 동작을 스핀 락으로부터 보호하는데 사용
- 회전 대기 완전히 배제 불가
- 락 획득, 해제 과정에서 인터럽트 가능하지만 회전 대기 시간 짧음
- 큐 사용 방식
: lock() 호출
-> 다른 스레드가 이미 락을 보유
-> 큐에 자신의 ID를 추가
-> guard를 0으로 변경, park() 호출 -> CPU 양보
-> unlock() 호출로 스레드를 깨움
- 깨우기/대기 경쟁(wakeup/waiting race) 문제
- park()문 수행하기 직전 자기 차례가 됨
- setpark()를 추가해서 해결
