[OS] Many types of Locks

G·2023년 5월 7일

OS

목록 보기

10/20

많은 lock 기법에 대해 알아보자.

Spin Locks

busy waiting, spin waiting 모두 critical section에 들어가기 전에 쓰레드, 프로세스가 아무것도 안 하는 것을 의미한다.

이 기법을 이용한 것이 Spin lock이다.
스핀락의 특징은 다음과 같다.

구현과 검증이 간단하다.

하나의 쓰레드만 critical section에 접근할 수 있게 한다.

쓰레드 수가 몇이던, 싱글 또는 멀티 프로세서 환경이던 다 잘 동작한다.

Busy waiting 하기 때문에 성능저하가 예상된다.

싱글 프로세서 환경에서 성능 저하가 심할 수 있다.

멀티 프로세서 환경에선 성능저하가 심하지 않다.

starvation이 발생할 수 있다.

Semaphore

busy waiting 하지 않는 lock 기법이다. 다양한 상황에 사용된다.
lock 변수 하나가 필요하며, 이는 자원을 몇 개의 쓰레드가 접근가능한지 알려주는 수단이다.
이를 위한 API 이름을 알아보자.

P(S) == semWait(): critical section에 접근한다. lock

V(S) == semSignal(): critical section 접근을 끝낸다. unlock

세마포어는 sleep & awake 기법을 사용하며 이는 lock 변수 이외에, 쓰레드를 저장할queue가 필요하다.

Binary semaphore(mutex locks)

상호배제 lock이라고도 불리우는 mutex lock은 critical section에 하나의 쓰레드만 접근할 수 있는 기법이다.

동작 방식은 다음과 같다.

첫 쓰레드는 1을 0으로 변경 후 critical section에 접근한다.

이후 쓰레드 진입은 전부 queue에 들어가고 block된다.

첫 쓰레드가 진입에서 벗어나면 2.에서 block된 쓰레드를 ready 상태로 변경하고 critical section에 진입한다.

queue가 empty라면 1.을 수행하고, 아니라면 2.를 반복한다.

이는 FIFO와 같이 순서를 보장하기 때문에 Strong semaphore라고 부른다.

Counting semaphore(general semaphore)

좀 더 일반적인 세마포어로, critical section 접근 쓰레드 수에 제한이 걸려있지 않다.
1. 1일 때 $\rightarrow$ 0으로 만들고 critical section에 접근한다.
2. 이후 쓰레드는 sleep한다.
3. awake 시, critical section에 접근한다.
4. 이후 count가 0 이하일 경우, (2 $\rightarrow$ 3)를 반복하고 0 초과라면 1을 수행한다.

Implementation

위와 같이 wait, signal 접근 자체가 공유자원인 count와 queue에 접근할 수 있으니 CAS와 같은 spin lock을 이용해야한다.

Deadlocks

Deadlock이란 다음과 같은 상황에 Scheduling으로 인해 발생한다. 두 쓰레드 모두 sleep 하는 경우이다.

세마포어는 overhead가 더 크다. 프로세스 스위치가 필요하기 때문이다. 그러나 spin lock도 대기하는 시간이 길어질 수 있다. 이러한 이유로, critical section의 수행이 길면, 세마포어, 짧으면 spin lock을 선택하듯이 상황에 맞게 선택하면 된다.