Concurrency

하나의 프로세스는 여러 개의 실행 흐름(Thread)을 가질 수 있다.

Thread는 개별 stack, PC, registers를 담는 TCB를 가지고 있다.

 

 Race Condition

-> execution이 atomic하지 않으면 발생

-> critical section(mutual exclusion/상호 배제)으로 보호가 필요

 

Lock

-> spinning or sleep을 이용해 lock 구현

 

Conditioin Variables

-> 초창기에는 spinning으로 lock을 구현(cpu 소모적)

-> wait을 통해 sleep pool로 이동시켜서 cpu를 할당받지 않도록 함(그러나 wait를 거는 와중에 unlock이 되버리면 문제 발생)

 

---

Lock의 구현

-> OS와 HW로 구현

-> 싱클 코어의 Disable Interrupts는 SW만으로도 구현 가능

-> 멀티 코어는 위와 같은 방법으로 해결 불가능

-> lock을 얻고자 flag를 사용하는 과정에서도 atomic하지 않기 때문에, 이를 HW에서 atomic으로 구현해야함(test-and-set)

-> Compare-And-Swap도 HW에서 하나의 instruction으로 구현되어 있음 

 

Sleeping

-> spinning은 구현은 쉽지만, cpu가 소모적임

-> sleep을 통해 lock이 해제될 때까지 cpu를 할당받지 않음

-> 그러나 thread를 park(=sleep)하는 도중에 unlock이 수행되면, 해당 thread는 영원히 sleep에 갇힐 수 있음

-> 이때, setpark를 통해 특정 변수의 값을 변경하고 unpark(=wakeup)에서 setpark가 일어났었는지 체크

 

Lock-based Concurrent Data Structure

-> 데이터를 동시에 접근하며, 쓰기를 포함한 명령을 수행한다면 lock이 필요하다.

-> 그러나 lock을 사용하면 correctness는 보장될지언정, 특히 멀티 코어 환경에서 performance는 급격히 떨어진다.

-> 현재 수행되고 있는 많은 연구들이 lock을 사용하지 않는 동시 접근에 대한 문제를 풀고 있다.

 

1. Sloppy counter

-> global 변수에 lock을 걸면 성능이 저하되므로, local 변수에 잠시 저장했다가 일정 threshold를 넘으면 global 변수에 더하는 방식

 

2. Linked Lists

-> Insert시 lock을 걸 수도 있지만, TAS(test-and-set) + 1 instruction을 이용하면 lock을 걸지 않아도 된다.

 

3. Scaling Linked List

-> Hand-over-hand locking(= lock coupling)이라고도 불리며, 링크드 리스트에 노드마다 lock을 두어 접근할 때 최대 2개까지 lock을 잡도록 한다.

 

4. Queue

-> Enqueue는 마찬가지로 lock 또는 TAS로 해결이 가능하다.

-> Dequeue는 TAS로 해결이 불가능하다.

 

5. Hash Table

-> Bucket 마다 lock을 두어, key가 다르다면 동시에 접근이 가능하다.

-> Bucket에 lock을 두지않고, value를 동시에 접근할 수 있도록 구현도 가능하다.

---

Condition Variables

-> 필요한 변수들

1. condition variable

2. mutex variable

3. state variable(= variable) : 3번째 그림과 같이 semantic이 없으면 parent는 무한히 기다리는 경우가 발생

 

The Producer / Consumer (Bound Buffer) Problem

-> 현실적인 문제들을 해결하기 위해 자주 사용됨(ex. 카카오톡)

-> 1:1인 경우 문제가 없던 코드가 다:다 인 경우 문제가 발생할 수 있다.

-> 특정 cv로 인해 thread가 깨어났지만, 다른 thread가 이미 소비해버려서 state가 변경되었을 때 문제 발생(recheck으로 해결)

-> 즉, thread가 깨어났음에도 불구하고 state가 만족한다고 보장할 수 없을 경우를 Mesa semantics

-> thread가 깨어났다면 무조건 state가 만족한다고 보장할 수 있을 때 Hoare semantics라고 한다.

-> cond queue를 여러 개를 두어 해결하거나, wakeup all을 통해 해결이 가능하다.

 

Semaphore

-> 일반적으로 binary variable과 같음

-> thread가 semaphore를 가져갈 때마다 -1씩, 반납할 때마다 +1씩 적용하여, semaphore가 음수일 때는 wait를 수행한다.

 

Reader-Writer Locks

-> read의 경우, 데이터를 변경하지 않음. 즉, lock을 read thread 각각에 걸면 오버헤드가 됨

-> read만 하는 thread들끼리는 lock을 사용하지 않음

-> 다만, 하나의 writer thread가 lock을 잡는다면 write를 수행하고, 하나의 reader thread가 lock을 잡는다면 모든 reader thread가 끝날 때까지 read를 수행한다.

 

---

Common Concurrency Problems