concurrency

multi threadting programming시 고질적인 문제점.

1. 공유 변수 파악하기.

2. lock의 효율적인 사용.

3. atomic operation으로 구현하기.

concurrency

multi-programming, multi-thread때문에 발생한다. 결국 process간에 발생하는 문제로 볼 수 있다.

프로세스간 통신문제, 자원(memory, file, IO)에 대한 공유와 경쟁, 프로세스 활동들의 동기화, 프로세스에 대한 cpu 시간 할당문제를 가진다.

발생하는 문제 : race condition 

두 개 이상의 프로세스가 공유 자원에 접근하려는 상태.

특정자원이 정해진 순서로 작동하는 경우에만 작업이 성공적으로 수행된다면, 그 프로그램은 race condition을 포함한다.

Producer/consumer problem.

mutual exclusion

mutual exclusion : 한 프로세스가 공유자원에 접근하는 critical-section코드를 수행하고 있으면 다른 thread는 그 코드를 수행할 수 없다는 조건.

critical section : 공유자원에 접근하는 thread 내부의 코드.

starvation : 

하나의 thread나 thread의 집합이 어떤 이유로 동기화 객체의 소유권을 획득하지 못하는 상황.

너무 많은 객체의 소유권을 획득하려는 thread가 있거나 높은 priority의 thread가 CPU를 독점할 경우 발생하게 된다.

결과적으로 수행가능한 낮은 priority를 가지는 thread는 스케쥴링되지 못한다.

deadlock : 

두개 이상의 thread가 서로 충돌되는 자원을 요구할때 발생하며 해당 thread들은 더 이상 진행되지 못하게 된다.

해결방법1 : lock

운영체제와 프로그래밍 언어수준에서 cocurrency를 위해 제공됨.

race condition을 막는 가장 일반적인 방법이다. 

공유하는 메모리에 다른 thread가 접근하지 못하도록 lock을 사용한다.

한 프로세스가 특정 signal을 수신할 때까지 정해진 위치에서 중지하도록 강제한다.

이 signal을 위해 semaphore라는 변수를 사용한다.

-semaphore초기화 : semaphore값은 음이 아닌 정수 값

-SemWait : semaphore값을 감소시킨다.

만약 값이 음수이면, SemWait호출한 thread는 block된다.

-SemSignal : Semphore 값을 증가시킨다.

만일 값이 양수가 아니면 semwait연산에 의해 block된 thread를 깨운다.

-Windows에서는 EnterCriticalSection(), LeaveCriticalSection()

-Linux에서는 pthread_mutex_lock(), pthread_mutex_un

-C++11에서는 std::mutex의 lock(), unlock()

해결방법2 : atomic operation

multi-threading programming에서 lock을 안쓸 수는 없다.

그저 얼마나 효율적으로 lcok을 사용한 programming을 하느냐의 문제이다.

참조 : 멀티쓰레드 프로그래밍이 왜이리 힘드나요, 정내훈, http://deview.kr/2013/detail.nhn?topicSeq=64

위의 url 에따르면 두개의 thread의 성능차이가 상당히 많이 난다...

해결방법3 : SW solution

나만의 lock을 만드는 방법이다.

hw, os, pl의 어떠한 지원도 없을 경우에 쓸 수 밖엔 없다. 

단점으로는 시간이 오래걸리는 busy waiting방식이다.

Dekker's algorithm

메모리 위치에 대해 한번에 하나의 접근만 허용된다는 제약이 있다. 

turn변수를 두었다.

Peterson's Algorithm

turn, flag변수를 두었다.

해결방법4 : HW support

-testset instruction

-compare_and_swap(CAS)

2개의 기능을 원자적으로 처리하는 다양한 기계어

word와 testval을 비교해서 같으면 word를 newval값으로 바꾼다.

compare_and_swap함수는 atomic하게 수행된다. 대부분의 processor에서 지원한다.

Wait-free, Lock-free

.Lock을 사용하지 않고

.다른 쓰레드가 어떠한 행동을 하기를 기다리는 것 없이

.자료구조의 접근을 Atomic하게 해주는 알고리즘의 등급

.멀티 쓰레드 프로그램에서 쓰레드 사이의 효율적인 자료 교환과 협업을 위해서는 Non-Blocking 자료 구조가 필요하다.

hw지원의 문제점 : 

busy waiting을 사용.

starvation가능성

deadlock가능성

lock의 효율적인 사용

어쨋든 lock을 사용해야 하는데, 얼마나 효율적으로 lock을 사용하느냐 역시도 문제이다.

이유1 : lock이 2개 이상이 되거나하면 복잡해진다. 

이유2 : lock은 보통 명령에 비해 수백배 시간이 오래걸린다.

- 공유변수를 정확하게 찾아서 lock걸기.

- lock으로 보호하는 각각의 영역이 overlap 되진 않는가 확인한다.

위를 제대로 하기 위해서는 모든 lcok을 사용하는 메모리 영역을 문서화 하는 작업이 귀찮더라도 필요하다.

참조 : 

What Every Dev Must Know About Multithreaded Apps : https://msdn.microsoft.com/en-us/magazine/cc163744.aspx

한글참조 : 

http://www.slideshare.net/jacking/multithread