4. Concurrency

1. Thread
2. Lock
3. Condition Variable
4. Semaphore
5. Common Concurrency Problems

1. Thread

- 개념

• 독립된 객체로 프로그램 내에서 독립적으로 생성, 실행되어 프로그램 대신 작업 수행
• 하나의 프로세스 안에 thread들은 주소공간을 공유하여 동일한 값에 접근 가능
• 각 thread는 자신의 상태를 나타내는 PC, 레지스터들을 가지고 있으며 문맥교환시 이를 TCB에 저장
• 프로세스와 달리 쓰레드 간의 문맥 교환시 주소 공간을 그대로 사용
• 쓰레드마다 스택이 할당된다

 

- 쓰레드 장점

1. parallelism : 여러 cpu에 각각 쓰레드를 동작하게 함으로써 프로그램의 성능 향상
2. 멀티 쓰레드를 통해 하나의 프로그램 안에서 I/O 작업과 다른 작업이 중첩되어 프로세스가 blocked 되는 것을 방지

 

- 멀티쓰레드 문제점

• 쓰레드는 호출자와 별개로 실행되므로 특정한 실행 순서를 가지고 있지 않아서 race condition에서 indeterminate result 발생

 

- 해결방안

• race condition이 존재하는 critical section에서 하드웨어와 OS의 지원을 통해 synchronization primitive를 구현하여 쓰레드간 mutual exclusion을 보장해야 한다
• 이를 위한 쓰레드 간 시그널 교환 메커니즘을 위해 condition variable를 사용
• lock 기법을 통해 mutual exclusion 구현 가능

 

2. Lock

- 개념

• 소스 코드의 critical section을 lock으로 설정하여 해당 critical section이 마치 single atomic instruction인 것처럼 실행되도록하는 기법
• lock을 통해 mutual exclusion이 구현되므로 lock을 mutex라고도 부른다
• mutual exclusion : 한 쓰레드가 critical section 내에 있으면 이 쓰레드가 lock을 release 할때까지 다른 쓰레드가 해당 critical section에 들어 올수 없도록 제한 하는 것

 

- lock 평가 기준

1. mutual exclusion
2. fairness : 모든 쓰레드들이 락 획득에 대해 공정한 기회가 주어지지 않으면 계속 lock을 획득하지 못하는 starvation 발생
3. performance

 

3. Conditional Variable

- 개념

• 쓰레드간 시그널 교환 메커니즘 구현을 위해 사용된는 일종의 큐 자료구조
• 쓰레드가 계속 진행하기 전에 어떤 조건이 참인지 검사 하는 경우 lock만으로는 병행 프로그램을 제대로 구현할 수 없으므로 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐를 생성
• 다른 쓰레드가 조건을 만족시키고 시그널을 보내면 대기중이던 쓰레드는 깨어나서 작업 진행

 

4. Semaphore

- 개념

• 정수 값을 갖는 객체
• 세마포어를 락과 컨디션 변수로 모두 사용함으로써 동기화 관련 문제를 한번에 해결
• 세마포어는 초기 값에 의해 락 또는 컨디션 변수로의 동작이 결정됨

 

5. Common Concurrency Problems

1. Atomicity-Violation Bugs
   • 해결방법 : 락을 추가
2. Order-Violation Bugs
   • 해결방법 : 컨디션  변수를 추가하여 쓰레드의 순서를 지정
3. DeadLock Bug
   • deadlock dependency graph에서 dependency cycle이 존재하는 deadlock 발생 가능성 존재
   • deadlock 발생 조건
     1. circular wait : 각 쓰레드가 다음 쓰레드가 요청한 락을 갖으면서 순환고리 형성
        • 해결방법 : 락 획득의 전체 순서를 정하여 순환대기가 발생하지 않도록 한다
     2. hold-and-wait
        • 해결방법 : 원자적으로 모든 락을 단번에 획득하도록 한다
     3. no preemption
        • 해결방법 : trylock을 이용하여 락 획득 실패시 다시 시도한다
     4. mutual exclusion
        • 상호배제를 없애고 하드웨어 명령어를 사용하여 wait-free 자료구조 구현