[운영체제] 4. Concurrency: Thread and Lock

Concurrency

공유 자원의 존재로 경쟁 상태가 유발됨에 따라 기대와 다른 결과를 도출하게 된다. 이를 잘 약속된 동기화 방법으로 강제하는 것을 병행성이라 한다.

 

Thread & Process

Process는 스케쥴링의 객체로 자원을 독점적으로 사용하는 모델이다.

-장점과 단점

• 장점: 독립적인 모델로 결함 발생 시 상대적으로 안전하다.
• 단점: 자원 공유가 불가능하다. 생성이 느리다(많은 영역을 복제).

Thread 또한 스케쥴링의 객체로 프로세스와 다르게 많은 자원을 공유한다.(code, data, heap and files)

'-장점과 단점

• 장점: 병렬성, 자원공유, 빠른 생성, 대기와 처리의 오버랩
• 단점: 결함 발생 시 프로세스 모델에 비해 취약하다.

---

Concurrency Example

아래의 코드가 두개의 쓰레드로 인해 동시에 수행될 경우 생기는 문제점

 

두 쓰레드의 동작 시 +2를 기대했으나 실제 +1의 결과만 얻음.

Solution

1. Controlled scheduling: 병행성 문제는 결국 Uncontrolled scheduling의 문제로 원자성을 통해 해결한다.
2. 경쟁 상태가 가능한 영역: 임계 영역으로 설정한다.
3. 임계 영역에는 오직 한개의 쓰레드만 접근을 허용한다: 상호배제

Main Issues Related To Concurrency

1. 상호배제: 하나의 쓰레드만 임게 영역에 접근이 가능하다. → Lock
2. 동기화: 쓰레드 간의 순서를 적절히 정의해준다. → Condition variable

---

Locks

원자성을 보장하는 API로 임계영역 앞, 뒤에 lock, unlock을 배치하면 임계영역 외부에서는 쓰레드가 병렬적으로 수행하다가 임계영역 내부에서는 하나의 쓰레드만 수행되게 된다.

Lock의 사용 예시 코드와(좌측) 세개의 쓰레드 상황에서 임계영역의 접근(우측)

 

Lock size

• Coarse-grained Lock: 큰 임계영역을 취하는 lock으로 간단하지만 병렬성이 떨어진다.
• Fine-grained Lock: 작은 임계영역을 취하는 lock으로 병렬성은 좋지만 구현이 복잡하다.

Lock을 구현하는 방법

1. Disable Interrupt: 인터럽트를 불능상태로 만들면 문맥 교환이 일어나지 않기 때문에 임계 영역에서 하나의 쓰레드만 동작하는 것이 가능해진다. 간단하지만 많은 문제점이 있다.
2. SW-only approach: 거의 사용하지 않는 방법이다. 정확성이 보장되지 않고, busy waiting으로 성능이 나쁘다. 장점으로는 순수한 SW 해결책이라는 점이다.
3. HW atomic operations: CPU에서 원자적으로 수행되는 명령어를 이용하여 구현

 

Lock을 구현하는 방법 - HW atomic operations

1. TestAndSet: 상호배제를 보장하며 형평성은 좋지 않다. Spin lock의 형태이다.

2. CompareAndSwap: 값을 예상 값과 비교하여 맞을 경우 새로운 값으로 교체하고, 이전 값을 리턴한다.

3. Load-Linked and Store-Conditional: 값을 불러온 뒤 변화가 없었다면 새 값으로 업데이트 한다.

4. FetchAndAdd: 티켓 락으로 구현되어 형평성이 보장된다.

 

---

Spin Locks & Sleep Locks

• Spin lock: busy waiting 기법으로 간단하지만 비효율적이다.
• Sleep lock: 선점이 되어 wait 상태로 전이되며, unlock이 발생할 시 wakeup의 전이가 발생하여 ready 상태가 된다. 효율적인 메카니즘이지만 구현이 복잡하다. Sleep queue의 관리, 문맥교환을 위해 OS의 보조가 필요하다.

---

Sloppy counter

전통적 카운터의 lock contention이 높은 문제를 해결한 자료구조이다. 하나의 전역 카운터와 여러 로컬 카운터를 두어 전역 카운터는 전역 락으로 로컬 카운터는 각각의 로컬 락으로 보호하여 성능이 좋다.