[운영체제] Locks #1

 

Lock에 대해서 알아보자

 

 

Lock이 필요한 이유

• 2개 이상의 thread가 동시에 공유 자원에 접근할 경우 race condition(병행성 문제)이 발생해서 결과를 예측할 수 없다.

따라서 공유 자원에 대한 동기화 메커니즘이 필요한데 그중 가장 일반적인 메커니즘이 Lock이다.

 

 

Critical Section

• 공유자원에 접근하는 코드의 조각이다.

 

Mutual Exclusion(병행성 해결)

• Critical Section은 하나의 부분인 것처럼 실행되어야 한다.(Atomically)
• Critical Section은 한 번에 하나의 쓰레드만 실행 가능하다.
• 다른 모든 쓰레드들은 Critical Section에 진입하기 위해서 현재 사용 중인 쓰레드가 종료될 때까지 entry에서 기다려야 한다.

 

---

Lock의 기본 개념

critical section에 진입하기 전에 lock을 얻고, critical section이 끝나는 경우에 lock을 반납하고 나온다.

 

 

Lock이 제공해야 하는 기능

1. Correctness
   • mutual exclusion : 한 번에 하나의 쓰레드만 critical section에 진입할 수 있게 해야 한다.
   • Progress : Dead-lock 상태(모두가 lock을 얻지 못하고 critical section에 진입할 수 없는 상태)가 발생해서는 안된다.(deadlock-free)
   • Bounded : 일정 시간 이상 기다리면 lock을 얻을 수 있게 보장해야 한다. (starvation-free)
2. Fainess
   • 모든 쓰레드는 lock을 얻는데 공평한 기회를 가져야 한다.
3. Performance
   • lock을 얻으려는 쓰레드의 수에 따른 Time overhead에 관한 내용

 

 

Lock의 구현 - Software Algorithm

 

Basic Algorithm

 

critical section에 진입하려는 쓰레드가 lock을 호출하면 자신의 flag(쓰레드 사용 여부)를 1로 만들고, 다른 쓰레드의 flag가 1이 아니라면 critical section에 진입해서 작업을 마친 뒤 unlock을 호출하여 critical section을 마무리하는 코드이다.

 

하지만 코드에 적혀있듯이 lock 내부에서 context switching이 발생하면 deadlock상태에 걸리게 되므로 좋지 않은 알고리즘이다.

 

 

 

Peterson's Algorithm

 

쓰레드의 순서를 결정하는 turn이라는 변수를 추가한 알고리즘이다.

 

상대방의 flag가 1이라도 turn이 self의 turn이라면 lock을 빠져나올 수 있다.

따라서 두 쓰레드의 flag가 모두 1이 되어 교착상태에 빠지는 걸 막을 수 있다.

 

 

hardware support가 필요한 이유

 

현재 lock이 사용되는지에 대한 변수 flag가 있다.

void lock에서 현재 lock 변수가 사용 중(flag == 1)이면 flag가 0이 될 때까지 while문을 돌면서 기다린다.

만약 flag가 0이 되면 flag를 얻고 critical section에 진입한다.

 

여기서 lock에 사용되는 flag변수도 공유자원이므로 critical section이 된다.

 

 

Problem 1

 

첫 번째 쓰레드에서 while문을 빠져나와 flag를 1로 만들기 전에 context-switch가 발생하면 다른 쓰레드의 flag도 1이 된다.

다시 첫 번째 쓰레드로 이동해서 flag를 1로 만들게 되면 동시에 2개의 쓰레드가 lock을 얻게 되어 mutual exclusion 문제가 발생한다.

 

 

problem 2

다른 쓰레드에서 lock을 얻을 수 있는지 계속해서 확인하는 작업을 하기 때문에 CPU가 낭비되어 성능 문제가 발생한다.

 

---

 

따라서 하드웨어적으로 lock변수를 atomic 하게 변경할 수 있는 instruction이 필요하다.

lock변수를 읽어오고, 변화시키고, 저장하는 작업을 하나의 명령으로 만들어 주어야 한다.