11 posts tagged with concurrency
concurrency pattern과 분산 시스템 스터디
Concurrency Pattern부터 Distributed System까지! 근데 대충함 … Concurrency pattern 대충 정리해보자. Wiki: Active Object Active Object는 Actor Model 구현하면서 써봤다. asynchronous method invocation과 request scheduling이 관건이다. 지난 글에서는 함수 요청을 functor로 만들어서 요청을 queueing…
producer/consumer model 구현
먹깨비 과제를 풀어보자. 여러 가지 구현법이 있을 것인데, 나는 간단하게 바구니는 공유 자원이니 lock으로 보호하고, 제빵사와 먹깨비는 actor로 만들어서 매 tick마다 상황 판단 후 작업을 처리하도록 했다. 따라서 공유 자원을 보호하기 위한 spin_lock과 actor 기반 코드를 만들었고 그 기반으로 바구니, 제빵사, 먹깨비를 만들었다. 먼저 spin_lock…
concurrency 알고리즘과 memory model
오늘 스터디에서 공부한 내용을 간략히 정리해보자. 원래 의도는, peterson’s algorithm을 보고 여기서 비순차 실행이 일어날 때 발생하는 문제를 보고, memory consistency model의 memory order를 통해 문제를 어떻게 해결할 수 있는지 본 후에, lock free stack, lock free queue algorithm을 보고 문제를 파악한 후에 이를 해결하기 위해 hazard…
thread-safe한 counter 구현
먼저 간단한 counter example을 만들어보자. 문제를 확인하기 위해서 다음과 같은 코드를 작성해본다. c++ code 한 줄이 원자적(atomic)으로 실행된다는 보장은 없다. assembly의 한 줄도 원자적으로 실행된다는 보장은 없다(smp, micro-operation) 위 코드를 release로 빌드해보면 ++counter 부분에 대한 코드가 assembly로 한 줄이 나오는데, 어쨌든 expect…
concurrency 스터디
오늘 스터디에서 공부한 내용을 간략히 정리해보자. Wiki: ABA problem Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms context switching과 simultaneously 실행 환형큐의 thread unsafety 문제 volatile/interlocked operation/memory barrier…
환형큐의 thread unsafety 문제
어떤 자원에 대한 환형큐가 있다고 해보자. size는 2의 자승이다. 위 코드는 당연히 thread safety 하지 않다. 하지만 문제가 발생하지 않도록 나름 머리를 써서 다음과 같이 위 코드를 사용한다고 해보자. 예전 자원을 반환하고, 새로운 자원을 할당받아 그것으로 무슨 작업을 하는 것이다. 이렇게 되면 pop 을 부르는 시점의 thread 는 적어도 자신이 push 한 자원…
Concurrent Pool (Static Size)
정적인 크기의 Thread-safe한 (Concurrent) Object Pool을 만들어보자. 핵심은 배열을 사용한다는 것. 왜냐하면 여러 thread가 접근해도 자신만의 index 지점을 접근하면 한 지점에 동시에 thread가 접근하면서 발생하는 문제가 없기 때문. 이게 동적으로 크기가 확장되면 배열의 포인터가 무효화되면서 여러 문제가 생길 수 있어 복잡하다. 따라서 정적인 크기라고 고정짓고 이야기를 해보자. Object…
객체별 함수 수행 동기화
(주의, 아래 글은 Visual Studio 2010 을 쓴다는 가정하에 작성하였다. 아무튼 C++11 이 지원되어야 한다) 여러 Thread가 동시에 접근을 수행하는 객체를 보호하기 위해서는 어떤 방법이 있을까? lock을 건다 각 Thread들은 하나의 queue에 요청할 작업을 쌓아두고, 그 객체 전담 Thread가 그 작업들을 처리한다. Read / Write Phase를 나누어서 Read는 다같이, Write…
Interlocked Singly Linked Lists
August 03, 2011Concurrent Data Structure는 Lock을 최소화하여 동작해야 multi thread에서 해당 자료구조에 접근할 때 발생하는 부담이 최소화되어 효율적인 프로그래밍이 가능하다. 여러가지 방법이 있겠지만, 가장 간단한(?) Windows API로 제공되는 Interlocked Singly Linked Lists에 대해 보자. (이후 SLIST 라고 이야기하겠다) SLIST는 단방향(singly) Linked…
context switching과 simultaneously 실행
August 02, 2011multi thread (or process) programming에서 가장 기초적인 개념으로 ABA Problem과 연결(되나?) 되는 기본적인 개념을 설명하고자 한다. 한 개의 코어는 한 시점에 한 개의 명령을 수행한다! 라는 기본 전제를 깔고 이야기를 시작해보려 한다. context switching 태초 단일 코어(core) 시대에는 한 개의 프로그램만 실행하면 됬다. 그게 OS…
volatile과 interlocked operation
volatile 다음과 같은 코드가 있다. 세 번의 ++ 연산을 모두 a 라는 변수에 수행하므로, 컴파일러는 최적화를 통해 다음과 같은 코드를 만들어낼 수 있다. 만약 multi-thread 환경에서 저 코드가 여러 thread에 의해 수행된다고 하면, add eax를 수행하고 mov dword ptr [count], eax를 수행하기 전에 switching이 되면, 다른 코드에서는 아직 count…