멀티코어컴퓨팅 - 6. Concurrent Programming

concurrency

parallel, 병렬처리란 하나의 작업을 여러 쓰레드가 작업을 나누어 동시에 일을 처리하는 것을 말한다.

concurreny, 동시성은 동시에 여러가지 작업이 이루어지는 것 처럼 보이도록 하는 것을 말한다. 여러 core에서 직접 동시에 여러가지 다른 작업이 수행될 수 있고 혹은 싱글 core라도 여러 프로세스들을 빠른 속도로 interleaving 하면서 처리하여 concurrency를 구현할 수 있다.

Parallel / concurrency

좌측 그림은 세개의 core가 동시에 A,B,C 작업을 처리하고 있다.

우측 그림에서는 싱글 core가 한번에 A,B,C를 빠른 속도로 돌아가면서 처리하여(time 축을 보면 한번에 한 녀석의 일 만 함) 동시에 A,B,C를 실행하는 것처럼 보이게 한다. 이런 개념이 concurreny, 동시성이다. 

 

즉 concurrent의 반대말은 sequential이다. 순서대로 일을 처리하는게 아니라 interleaving하면서 이거하고 저거하고 하는 것이다.

concurrency가 반드시 필요한 이유는 throughput, repsonsiveness 때문이다.

예를들어 지금 cpu를 점유한 프로세스/쓰레드가 메시지를 보내는 작업을 했고 응답이 와야 다음 진행이 가능하다고 하자. 그 시간 동안 계속 cpu를 점유하고 있으면 자원 낭비이며 동시성을 사용자에게 제공할 수 없다. 따라서 현재 프로세스/스레드가 block되거나 충분히 반응성을 보여줄만큼 cpu를 점유했으면 바로 다음 녀석에게 기회를 양보해야 한다.

이렇게 여러 프로그램이 동시에 작동하는 것 처럼 만드는 것이 동시성이다. 심지어 multicore 환경에서는 여러 프로세스/쓰레드의 작업들을 parallel하게 처리함으로써 더 나은 동시성을 제공할 수 있다.

 

운영체제 시간에서 살펴본 bank account 문제, producer, consumer 문제, dining philosopher문제가 concurrency를 구현하는 문제였다.

이때 synchronization이 중요했던 이유는 여러 쓰레드가 동시에 인출, 예금을 요청하는 경우 동시에 shared data인 account에 접근할 수 있다. 즉 공유하는 자원에 대해서 mutual exclutsion을 보장해야 했다.

혹은 싱글 코어라고 해도 지금 인출하려는데 좀 전에 처리하던 예금 작업이 아직 완료가 안되었다면? 예금 작업이 완료되기 전에 인출이 되어 올바른 결과를 기대할 수 없다.

 

즉 interleaving execution 때문에 발생하는 race condition을 피해서 shared variable의 안전을 보장하기 위함이다.

그래서 공유하는 자원에 대해 lock, synchronized, semaphore, atomic variable등을 사용하는 방법을 이전 장에서 공부했다.

이 도구들을 사용해 한번에 최대 한 쓰레드만 진입이 가능한 critical section을 보호하는 방법을 살펴보았다. (mutual exclusion 구현)

 

deadlock

A(from) 계좌에서 B(to) 계좌로 이체를 tranfer함수라고 한다. 모든 account는 shared data이다.

즉 누군가가 transfer를 호출한다면 A, B 계좌 두개의 자원을 확보해야 한다.

a는 A에서 B로 송금을 원한다. a는 A를 소유한 상태 B가 unlock되기를 기다리는 중이다.

b는 B에서 A로 송금을 원한다. b는 B를 소유한 상태 A가 unlock되기를 기다리는 중이다.

이 두 프로세스/쓰레드는 서로를 계속 기다리며 영원히 작업을 완료하지 못하게 된다. 이게 데드락이다. 따라서 위의 예시의 approach는 문제가 있다.

 

운영체제 시간에 어떻게 데드락을 해결할 수 있는지 다양한 방법을 공부했었다. 기억을 다시 떠올려보자.

transfer함수 자체를 critical section으로 잡으면 문제는 해결될 수 있다. 하지만 {a->b 송금 작업, c->d 송금 작업} 처럼 서로 관련 없는 자원을 요구하는 transfer일지라도 동시에 처리될 수 없다는 문제가 있다.

이렇게 synchronized를 바로 겹쳐 써도 문제는 해결되지 않는다. 

이렇게 account마다 rank를 부여한다. 동시에 A(high), B(low) 계좌를 원하는 a, b는 rank가 높은 A를 먼저 얻으려고 노력하기 때문에 a,b 둘 사이의 deadlock은 해결된다. 

 

Race condition

동시에 A,B가 a에 대한 자원을 요청한다고 해보자 A->B 순으로 변수 a를 가졌을때 결과는 a = 10이 되고 B->A순으로 a를 가졌을때 결과가 7이 될 수 있다.

이렇게 실행 타이밍에 따라 결과가 달라지는 상황을 race condition이라고 한다.

execution interleaving, 혹은 병렬처리에서공유하는 자원을 가지고 작업이 수행되는 과정에서 실행 결과가 execution time에 dependent할 때 발생한다.

이렇게 프로그램을 실행할 때마다 (여러 쓰레드들 중 자원을 누가 먼저 사용하냐에 따라) 결과가 달라져 버리면 문제가 있는 것이다. (non deterministic)

제한된 자원에 동시에 접근하려고 경쟁하는 과정에서 실행 결과가 매번 달라지면 race condition이 있다고 한다. 메모리의 특정 영역(변수), cpu 등 다양한 자원이 있다.

 

lock등의 동기화 도구들을 잘 사용해서 shared data의 동기화를 잘 수행해야 한다.

 

Dining Philosopher problem

left, right 식기를 모두 소유해야만 밥을 먹을 수 있다. 5명이 다 식사를 할 수 있도록 하자.

모두가 left, right를 순서대로 얻으려고 하면 deadlock의 위험이 있다.

이렇게 하면 문제는 해결되지만 식탁까지 소유해버리기 때문에 한번에 한 철학자만 식사를 할 수 있다. (동시 식사 불가)

앉은 위치가 홀수, 짝수냐에 따라 젓가락 집는 순서를 다르게 하면 모두가 식사가 가능하다. 설명이 간결한데 직접 해보면 이해가 될 것이다. 

 

livelock

두개 이상의 쓰레드가 실행은 계속하는데 진전이 없는 상태

starvation

몇몇 쓰레드가 계속해서 자원을 점유하지 못하고 진행이 안되는 것을 말한다.

 

최종 정리

counting semaphore

세마포어는 p세마포어, v세마포어가 있다. 사용법은 lock과 비슷하다.

자원을 점유하려고 하면 sem_p(s)을 호출해서 s를 증가시킨다.

작업을 마치고 자원을 반환하려고하면 sem_v(s)를 호출해서 s를 감소시킨다.

s는 0보다 작아지지 않는다. s 가 0이면 sem_p(s)를 호출한 쓰레드는 block된다.

즉 자원의 수만큼 s의 수를 설정(2이상) 하고 프로세스/쓰레드에게 자원을 나누어준다.

즉 자원의 critical section 에는 최대 s개의 쓰레드가 들어갈 수 있는 것이다.

 

binary semaphore

s = 1 일때를 말한다. lock이랑 비슷하다. 

 

concurrent hash map

thread-safe (race condition이 발생하지 않는) 한 자료구조이다. 

여러 쓰레드에게 공유되는 hash map인데 Insert, delete 동작에 있어서 safe하다.

atomic variable이다.

 

copy on write arrays

마찬가지로 concurrent version의 thread-safe한 array이다.

 

barrier

또 다른 종류의 synchronization이다. 

barrier를 설정하면 모든 쓰레드/프로세스는 barrier 지점에 도달했을 때 stop한다.

마지막 쓰레드가 barrier에 도달할 때까지 모든 쓰레드/프로세스는 barrier 지점에서 기다린다.