[OS] Locks

락

: 임계 영역에 대한 상호 배제 기법

• 평가 방법
  • 상호배제
  • 데드락 X
  • 기아 X
  • 공정성: 쓰레드들의 락 획득에 대한 공정한 기회
  • 성능

 

Interrupt 제어

lock을 통해 interrupt를 키고 끄는 방법

단점

• interrupt를 제어하는 것은 특권 명령, user mode에서 사용 X
• 멀티프로세스에서 동작 X ← 가장 치명적
  • 멀티프로세스는 CPU가 2개 이상인데, 하나의 CPU에서 interrupt를 꺼도 다른 CPU에 영향을 주지 않음
• interrupt를 오래 꺼버리면 중요한 장치의 interrupt를 놓칠 가능성
• 속도가 느림

 

Store/Load만 사용

lock을 통해 flag를 설정

단점

• flag를 확인하고 설정하는 부분 사이에 interrupt가 걸리면 경쟁 조건 발생

 

Test-And-Set

• Spin O → 성능 저하
• LD, ST 합성 (flag 읽어옴과 동시에 세팅)
• flag 설정
• lock 함수
  • flag 읽어온 값 반환, 무조건 1로 세팅
• Store/Load만 사용하는 방법의 문제점을 해결
• 평가
  • 상호 배제
  • 데드락 X

 

Compare-And-Swap

• Spin O
• Test-And-Set과 비슷한 동작
• flag 설정
• lock 함수
  • flag 읽어온 값 비교 후 반환, 비교한 값과 일치하면 1로 세팅
• 평가
  • 상호 배제
  • 데드락 X

 

Load-Linked and Store-Conditional

• Spin O
• Test-And-Set과 비슷한 동작이라기 보다는 Set 하는 부분을 다르게 구현
• flag 설정
• lock 함수
  • flag 읽어온 후 처음 쓰면 1 반환, 아니면 0 반환
• 평가
  • 상호 배제
  • 데드락 X

 

Fetch-And-Add

• Spin O
• 번호표 받는 것과 비슷한 동작(다음 번호표 및 번호판은 1 증가)
• ticket, turn 초기값 0 설정
• lock 함수
  • ticket 읽어온 값 반환, ticket + 1 세팅
• unlock 함수
  • turn + 1 세팅
• 평가
  • 상호 배제
  • 데드락 X
  • 기아 X
  • 공정성

 

Yield

• Spin X → 효율적
• CPU 점유 포기
• Running → Ready
• 하지만 단일 CPU에서 쓰레드의 개수가 많으면 여전히 비효율적 (문맥 교환 비용 ↑)
• Spin은 모두 Yield로 바꿀 수 있음

 

Sleep

• park(): Running → Blocked
• unpark(): Blocked → Ready
• Waiting Queue 필요 (기다리는 곳이 필요)
• guard라는 작은 lock 사용, 여기서 Spin 사용하지만 대기 시간 짧음
• 공정성
• 경쟁 조건 발생하는 문제
  • 하나의 쓰레드가 waiting queue에 들어가있고 guard를 0으로 만든 상태에서 interrup가 걸려 다른 쓰레드가 unpark하는 상황이 오면 다시 원래 쓰레드로 돌아갔을 때 park되어 못 깨어나는 현상 발생
  • guard를 0으로 만드는 것과 park하는 것의 순서를 바꾸면 sleep 상태가 되어 guard를 0으로 만들어 줄 수 없음
  • setpark 시스템콜을 사용하면 문제 해결
    • setpark을 waiting queue와 guard를 0으로 만든 코드 사이에 넣어 setpark과 park 사이에서 unpark이 일어나면 그냥 return

 

우선순위 역전 문제 및 우선순위 상속

우선순위 역전(priority inversion)

• 낮은 우선순위 쓰레드가 lock을 얻고 이후 높은 우선순위 쓰레드가 lock을 얻으려고 하는 경우, 낮은 우선순위 쓰레드가 실행되지 못해(unlock하지 못해) 높은 우선순위 쓰레드가 계속 spin하게 되는 현상 발생
• 위의 경우에서 높은 우선순위 쓰레드가 lock을 얻으려고 할 때 sleep(blocked) 시키면 되지만, 3개 이상의 쓰레드가 있는 경우 중간 우선순위 쓰레드가 lock을 기다리는 높은 우선순위 쓰레드보다 먼저 실행되는 현상 발생

우선순위 상속(priority inheritance)

• lock을 기다리는 높은 우선순위 쓰레드가 일시적으로 낮은 우선순위 쓰레드에게 자신의 우선순위를 빌려주는 것

 

Spin vs Sleep

• 유니프로세스(CPU 1개): Sleep 유리
  • Spin보다 문맥 교환이 유리
• 멀티프로세스(CPU 2개 이상)
  • Critical Section 길이가 길 때: Sleep 유리
  • Critical Section 길이가 짧을 때: Spin 유리
    • 문맥 교환하는 시간이 더 spin하는 시간보다 길기 때문

 

2단계 락

• spin을 먼저 해서 기다리다가 lock을 얻지 못하면 sleep
• 문맥 교환되는 시간만큼 spin
• 2 X 문맥 교환 시간만큼 걸림

 

Futex Locks

mutex

• 최상위 비트: lock 유/무
• 나머지 비트: lock을 기다리는 쓰레드의 수

v

• mutex의 최상위 비트와 나머지 비트를 가짐

futex_wait

• 현재 mutex와 v가 같은 경우에 sleep

futex_wake

• wait Q에 있는 쓰레드를 깨워 Ready 상태로 바꿈

automic_bit_test_set

• mutex의 상위 비트를 1로 만들지만 반환 값은 현재 mutex 상위 비트 값

automic_add_zero

• mutex와 0x80000000을 더함
• mutex 상위 비트를 0으로 만들기 위함
• 0이 되면 return (기다리는 쓰레드가 없음)

 

락 기반 병향 자료 구조

병행 카운터

근사 카운터

• local count, global count, local lock, global lock
• s (update 할 일정 주기)
• local lock을 이용해 local count를 증가시키고 local count가 s 이상이 되면 global lock을 이용해 global count에 local count 값을 더한 후 local count는 다시 0으로 설정
• 고전 vs 근사 카운터 (s =1024)
  • 고전 카운터는 lock에 대한 병목 현상 때문에 thread의 개수가 많아지면 성능⬇
  • 근사 카운터는 성능⬆
• 근사 카운터의 s 설정
  • s 값이 높을 수록 성능은 좋지만 count 정확도 낮음
  • s 값이 낮을 수록 성능은 안좋지만 count 정확도 높음

병행 연결 리스트

hand-over-hand-locking

• 개별 노드마다 lock 설정 → 병목 현상 제거
• 리스트 순회 시, 다음 노드의 락을 먼저 획득하고 지금 노드의 락을 해제
• 병렬성 좋아짐
• 락을 하나만 사용하는 것보다 빨라지지 않을 수 있고 오버헤드가 커짐

병행 큐

• lock 1개
• dummy 노드를 넣어 노드를 추가하고 빼는 것이 경쟁 조건이 안 생기게 함

병행 해시 테이블

• 연결 리스트 여러 개 사용
• 해시 버켓(리스트로 구현)마다 lock 사용