Lock의 개념과 구현 방법

Lock이란?

앞서 설명했듯 critical section이란 여러 thread에서 동시에 실행되면 안되는 부분을 말한다.

따라서 critical section을 하나의 thread에서만 접근할 수 있도록 보호해야할 필요가 있다.

이 때 lock을 사용하면 critical section을 보호할 수 있다.

 

lock은 기본적으로 lock을 획득한 thread만 critical section을 실행하며, 사용하고 난 뒤에 lock을 반환한다.

따라서 다른 thread가 lock을 갖고 있지 않을 때 lock을 획득하는 lock() 함수와

critical section을 모두 수행한 뒤에 lock을 반환하는 unlock() 함수가 사용된다.

 

그렇다면 lock은 어떻게 사용하고, 어떻게 구현하고 평가하는지 알아보자.

 

Locking 전략

1. Fine-grained Lock

- critical section마다 lock을 걸어서 제한한다.

 

2. Coarse-grained Lock

- 여러 개의 critical section을 묶어 lock을 걸어 제한한다.

 

기본적으로 single thread 환경에서 Coarse-grained Lock이 Fine-grained Lock보다 훨씬 빠르다.

lock을 많이 만들 경우 lock의 획득과 해제의 overhead가 커져 느려지게 되기 때문이다.

concurrent system에서 Fine-grained Lock이 전체적인 성능을 향상시킬 수는 있지만,

복잡성을 증가시켜 deadlock과 같은 문제들을 일으킬 수 있기 때문에 주의하여 사용해야 한다.

따라서 처음에는 Coarse-grained Lock으로 시작하고, 필요한 경우 Fine-grained Lock로 바꾸는 것이 좋다.

 

Lock 구현 방법

그렇다면 lock을 어떻게 구현할까? 그리고 lock이 효율적으로 구현되었는지 어떻게 확인할까?

먼저 lock이 효율적으로 구현되었는지 평가하기 위한 기준을 다음과 같이 세워보자.

 

① Mutual Exclusion : 정말 1개의 thread만 critical section에 접근 가능한지

② Fairness : 오랫동안 코드를 실행하지 못하는 thread가 없도록 공평하게 lock을 획득할 수 있는지

③ Performance : lock을 사용함으로써 추가되는 비용이 얼마인지

 

그렇다면 이제 lock을 구현하는 여러 가지 방법을 알아보자.

 

1. Interrupt 제한을 통한 lock

앞의 게시글에서 설명했던 상황을 보면 timer interrupt 때문에 순서가 바뀌는 것을 볼 수 있다.

그렇다면 critical section에서는 interrupt가 발생하지 않도록 하면 되지 않을까라는 생각을 할 수 있다.

 

하지만 이 방법에는 여러가지 문제점이 있다.

1) 개발자가 의도적으로 전체 코드를 critical section으로 만들어 CPU를 독점할 가능성이 있다.

2) I/O 작업이 끝나서 오는 interrupt 등의 필수적 interrupt를 수신할 수 없다.

3) 멀티프로세서 환경에서는 동작하지 않는다.

4) 비효율적이다.

 

2. Flag를 이용한 lock

flag 변수를 하나 두어 lock() 호출 시 flag를 1로 만들고 1일 때는 critical section에 접근하지 못하도록 하는 방법이다.

 

다음과 같이 lock을 구현했다고 가정해보자.

① 만약 flag가 0이라면

② flag를 1로 바꾸고

③ critical section을 실행한 뒤 flag를 0으로 바꾼다.

 

이렇게 구현할 경우 큰 문제점이 있다.

Thread 1이 ①조건문을 지나 ②flag를 바꾸기 전에 interrupt가 발생하면

Thread 2는 아직 flag가 0이기 때문에 critical section 안으로 접근 가능하게 된다.

따라서 lock의 가장 중요한 mutual exclusion이 성립되지 않는다.

 

3. Spin을 이용한 lock

Spin을 이용한 lock은 while 조건문 안에 flag를 넣어 flag가 1일 때는 spin하도록 하는 방법이다.

 

다음과 같이 Spin lock을 구현해보자.

① 만약 flag가 1이라면 spin

② spin이 끝나면 flag를 1로 만들고 critical section 진입

③ critical section을 실행한 뒤 flag를 0으로 변경

 

이 경우도 마찬가지로 ①spin이 끝나고 ②flag를 1로 바꾸기 전에 interrupt가 발생하면 critical section에 여러 개의 thread가 진입하게 되므로 mutual exclusion이 성립하지 않는다.

 

그렇다면 flag를 검사하는 부분과 flag를 1로 바꾸는 부분을 합쳐 atomicity를 보장해주면 되지 않을까?

이런 생각에서 나온 것이 test-and-set과 compare-and-swap이다.

이 두 기법은 하드웨어에서 flag 검사와 변경을 한번에 실행하도록 지원하여 interrupt 발생을 막을 수 있다.

그러나 이 또한 lock이 공평하게 분배되지 못하며, spin으로 인한 자원 낭비가 발생한다는 단점이 있다.

 

4. Load-Linked and Store-Conditional

앞에서 설명한 방법은 interrupt가 일어나지 않도록 하여 문제가 생기는 것을 방지하기 위한 방법이다.

그렇다면 생각을 바꿔 interrupt가 일어나지 않았을 때만 저장하도록 할 수도 있지 않을까?

이 방법은 그래서 변수를 통해 다른 thread의 접근을 기록하여 접근되지 않았을 때만 저장하게 한다.

 

5. Fetch-and-Add

이 방법은 숫자를 하나씩 증가시키며 해당하는 차례의 thread가 critical section에 진입하는 방법이다.

차례되로 thread를 진입시키면 무엇보다 공평하게 lock이 분배된다는 장점이 있다.