[OS] 락 없는(lock-free) 알고리즘, 동기화 도구 사용 전략 정리

• 동기화 도구들은 임계 구역 문제인 상호 배제를 보장하고 라이브니스 문제를 해결하는데 효과적

---

락 없는(lock-free) 알고리즘

 

---

락 없는 알고리즘의 구현

• 락 없는 알고리즘을 구현하는 이유? → 락 오버헤드 없이 경쟁 조건으로부터 보호하기 위해
• 락 없는 알고리즘을 구현하기 위해 CAS 명령을 사용하는데 중점을 둠
  • CAS → compare and swap의 약어
    
• 장점 : 락 없는 설루션은 오버헤드가 낮고 확장성이 있기 때문에 인기가 있음
• 단점 : 알고리즘 자체가 개발 및 테스트가 어려운 경우가 많음

 

 

---

CAS 기반 접근 방식

---

CAS 기반 접근 방식이 낙관적으로 접근하는 과정

1. 우선 낙관적으로 변수를 갱신
2. 충돌 감지를 사용하여 다른 스레드가 변수를 병행하게 갱신 중인지 확인
3. 갱신 중이라면, 충돌 없이 성공적으로 갱신될 때까지 연산을 반복 시도

• cf) 상호 배제 락킹은 비관적 전략으로 간주
  • 다른 스레드가 병행하게 변수를 갱신 중이라고 가정
    → 갱신하기 전에 비관적으로 락을 획득

 

---

다양한 경합 부하에서 기존 동기화와 CAS 기반 동기화의 성능 차이

• 경합 없음
  • 두 옵션 모두 빠르지만, CAS 보호는 기존 동기화보다 다소 빠를 수 있음
    
    
• 적당한 경합 : CAS 동기화가 기존 동기화보다 빠르고, 훨씬 빠르게 작동할 것
  • CAS 연산 경우
    • 대부분 성공하고, 실패해도 루프를 반복할 것
      
      
  • 상호 배제 락(기존 동기화)의 경우
    • 경합 중인 락을 획득하려는 시도는 복잡하고 시간이 많아 소요되는 코드 경로를 따름
    • 해당 경로에 따른 실행
      → 스레드를 일시 중지 및 대기큐에 넣고, 다른 스레드로 문맥 교환 필요
      
      
• 심한 경합
  • 경합이 치열한 상황에서는 기본 동기화가 CAS 기반 동기화보다 빠름

 

 

---

경쟁 조건 해결을 위한 기법의 선택

• 경쟁 조건 해결을 위한 기법의 선택은 시스템 성능에도 큰 영향을 줄 수 있음

 

---

락 기법들의 특징

• 원자적 정수
  • 기존 락보다 훨씬 가벼움
  • 일반적으로 카운터와 같은 공유 변수에 대한 단일 업데이트에서 적합
    • mutex 락 또는 세마포에 비해 더 적합
      
      
  • 사용 예시
    • 락이 짧은 기간 동안 유지될 때 다중 처리기 시스템에서 스핀락이 사용되는 운영체제 설계
      
      
• mutex 락
  • 세마포보다 간단하고 오버헤드가 적음
  • 임계구역에 대한 접근을 보호하는 용도로 이진 세마포보다 더 선호됨
    
    
• 카운터 세마포
  • 한정된 수의 자원에 대한 접근을 제어하는 용도로 사용될 때는 카운터 세마포 적합
    • mutex락보다 카운터 세마포가 더 적합
      
      
• reader-writer 락
  • 카운터 세마포와 비슷하게, 일부 경우에 mutex 락보다 reader-writer 락이 더 선호될 수 있음
    ← reader-writer락이 mutex 락보다 더 높은 병행성을 허용하기 때문
    • 즉, reader은 여러 개일 수도 있음

 

---

모니터와 조건 변수

• 장점
  • 고급 도구는 단순성과 사용 편의성이 높음
    
    
• 단점
  • 고급 도구는 상당한 오버헤드가 생길 수 있음
  • 구현에 따라 경합이 심한 상황에서는 확장성이 나쁠 수 있음