1. lock

임계영역(Critical section)
공유자원에 접근할 수 있는 영역을 말한다. 임계 영역은 반드시 보호 되어야하는 구간으로 상호 배제(mutual exclusion)해야 합니다. 이런 상호배제를 구현하기 위해서는 아래의 조건을 만족 해야합니다.

• 임계 구역에서의 실행은 Atomic 해야 합니다.
• 오직 하나의 쓰레드만이 임계구역 내에서 실행 가능하게 해야합니다.
• 모든 다른 쓰레드는 기다리는 상태에 들어가게 됩니다.
• 쓰레드가 임계 구역을 빠져나오면 다른 쓰레드가 들어가게 됩니다.

1. lock 제작

임계 구역을 balance = balance + 1라고 가정한 후 구현하면 아래와 같이 만들 수 있습니다.

lock_t mutex;
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

여기서 lock_t mutex는 현재 락 상태를 보관하는 변수로 두 가지의 상태가 가능합니다.

• locked(acquired, held) - 유일한 쓰레드 하나가 임계 구역내에서 락을 가지고 있는 상태입니다.
• unlocked(available, free) - 어떠한 쓰레드도 락을 가질 수 있는 상태를 의미합니다.

다음으로 lock(&mutex) ... unlock(&mutex)는 무엇인지 각각을 알아보면 아래와 같습니다.

• lock()
  - 락을 acquired를 시도해봅니다.
  - 만약 락을 어떠한 쓰레드도 가지고 있지 않다면, 쓰레드는 락을 acquired 할 수 있습니다.
  - acquired가 수행된 이후에 임계 구역에 들어가게 되고, 이 쓰레드가 락의 소유자(owner)가 됩니다.
  - 이미 락이 다른 쓰레드로 acquired가 된 상태라면 임계 구역에 들어가는 것을 막습니다.
  
• unlock()
  - 락의 소유자가 unlock()을 부르는 경우, 락은 다시 available(free) 상태가 됩니다.
  - lock()을 기다리는 다른 쓰레드를 깨우도록 합니다.

이러한 락은 아래의 방법을 통해서 사용할 수 있습니다.

• 락을 처음 생성 시에는 free상태로 만들어 주도록 합니다.
• lock()을 임계 구역에 들어가기 전에 불러주고, unlock()을 임계 구역을 빠져나가면 불러주도록 합니다.
• lock()은 호출자(caller)가 락을 가지고 있는 동안은 반환이 이루어지지 않습니다.
• unlock() 상태에 도달하기 전까지, 쓰레드는 스핀(spinlock) 또는 블락(mutex) 상태입니다.
• 최대 하나의 쓰레드가 어느 일정 시간에 락을 가질 수 있습니다.

예제 코드로 구현을 하면 아래와 같이 됩니다.

int withdraw(account, ammount){
	lock(lock);
	// ----- CRITICAL SECTION ----- //
	balance = get_balance(account);
	balance = balance - amount;
	put_balance(account, balance);
	// ----- CRITICAL SECTION ----- //
	unlock(lock);
	return balance;
}

그리고 락은 필히 아래와 같은 요구 사항을 충족할 수 있을 때 좋은 락이라고 할 수 있습니다.

• Correctness
  - Mutual Exclusion : 어느 일정 시간에는 오직 하나의 쓰레드만이 임계 구역에 있을 수 있습니다.
  - Progress(deadlock-free) : 만약 여러 개의 쓰레드가 임계 구역을 들어가고자 하는 경우, 반드시 하나는 들어갈 수 있어야 합니다.
  - Bound Waiting(starvation-free) : 대기 중인 쓰레드가 반드시 임계 구역에 들어갈 수 있어야만 합니다.
• Fairness
  - 각각의 쓰레드는 락을 획득을 하는 데 있어서 공정해야 합니다.
• Performance
  - lock과 unlock을 하는 데 드는 데 시간 비용(time iverhead)는 어느 정도인가?
  - 다중 CPU를 지원을 하는가?
  

2. lock 제작 방법

락 제작 방법에는 총 3가지 방법이 존재합니다.

1. 인터럽트 제어 방법 (controlling interrupts)
2. 소프트웨어적 방법론으로만 제작하는 방법 (software-only algorithm)
3. 하드웨어를 활용하여 제작하는 방법 (Hardware atomic Instructions)

인터럽트	소프트웨어	하드웨어
	Dekker’s Algorithm	Test-and-Set
세부 분류 없음	Peterson’s Algorithm	Comapare-and-Swap
	Lamport’s Bakery algorithm	Load-Linked(LL) and Store-Conditional(SC)
		Fetch-and-Add

---

lock 블로그
Condition variables 블로그