두찡의 일상

Coarse Grained Synchronization : Single mutex로 method call 마다 잠금 Fined Grained Synchronization : 작개 쪼개서 여러 개 lock으로 사용 hand over hand - my method 가 affect 하는 만큼 Optimistic Synchronization : 찾을 때는 lock없이 찾고, lock을 잡은 후 valid check Lazy : logical remove, physical remove (실제 노드를 제거하는 것과, flag만 check 한 뒤 나중에 physical remove를 기다리는 것) Lock-free Synchronization : lock 없이 구현 -- 마치며 이 뒤 내용 (List, Queue 등..

1. Shared Bus snooping 메모리 트래픽이 있는 걸 알아서 기다림 2. Distributed each processor has partial of memory, cache internal circuit. Not share big bus 만약 Lock이 없다면 어떻게 해야할까? "spin" or "busy-wait" Test-and-Set Consensus number 2 swap true with current value return priori value Tas Lock if ret == false -> get lock if ret == true -> not get lock space O(1) - 하나의 변수에 TAS를 계속 반복 TTas Lock (Test and Test and Set..

Consensus is universal (만능) n-thread consensus build (wait-free, linearizable, n-threaded implementation, any sequentially specified object) wait-free - stronger (system), lock-free (per thread) Lock-free : infinitely often some method call finishes (how to prevent starve) Wait-free : each method call takes a finite number of steps to finish lock 없이 execution order를 만들기 위해 도움을 받아야 함. 만약 실패한다면 새 ..

Mutual Exclusion 이 안 좋은 이유 - Lock을 잡고 sleep 할 수 있다 Falut tolerance - 장애가 발생해도 정상적, 부분적으로 기능을 수행할 수 있음 Wait-Free synchronization 은 좋지만 어렵다 (Wait-Free : 일정 step 내에 method를 처리할 수 있음) systematically 하게 구현 하고싶지만 non deterministic 함 (현재 상태에서 여러 선택을 할 수 있음 - 오토마타 개념) Queue에서 Dequeuer가 여러 명일 때, Lock을 사용하지 않고 어떻게 처리할 수 있을까? Consensus (합의) 문제를 해결 할 수가 없음 -> race condition Consensus : Thread 별 값을 각각 갖고 있던 ..

Modern Multiprocessors 에서 사용되는 shared memory 는 어디에서 부터 온 것일까? 에 대한 내용 Register : Holds a (binary value), Can be read & written Register 의 종류 Safe Register : valid 한 값을 읽으면 safe (some valid value) ㄴ ex) binary 1bit register read 0 or 1 (safe), read "hi" (unsafe) Regular Register : Old Vluae if no overlap, Old or one of new values if overlap ㄴ Regualr != Linearlizable Atomic Register : Linearizabl..

Concurrent Objects : 여러 쓰레드가 하나의 Object에 동시에 접근 Queue에서 하나의 enqueuer thread와 하나의 dequeuer thread만 있을 때라고 가정 Bounded Queue, Non Blocking 1. 가장 쉬운 방법 ㄴ 모든 method 에서 lock을 잡음 2. wait-free (wait-free 개념은 후에 나옴) ㄴ enqueue : non blocking 이므로, 꽉 차 있을 때 에러를 발생한다. tail을 1 증가시키고 element 추가 ㄴ dequeue : non blocking 이므로, 비어있을 때 에러를 발생한다. element 값을 저장 한 후 head를 1 증가 ㄴ lock을 잡을 필요도 없고, 일정 step 내에 끝남 Concurre..

Mutual Exclusion - algorithm for critical section 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘 Concurrent Programming 이 어려운 이유 : unpredictable 예측할 수 없다 #include #include int a; void foo() { for (int i = 0; i < 100000; i++) { a++; } } int main() { a = 0; std::thread thread1(foo); std::thread thread2(foo); thread1.join(); thread2.join(); std::cout

http://cs.brown.edu/courses/cs176/lectures.shtml CS1760 – Lectures Lectures Lectures will not be recorded this semester, but the videos from 2012 are available: 2012 CS1760 Lecture Videos. Date Topic September 6 Introduction (PDF) September 11 Mutual Exclusion (PDF) September 13 Concurrent Objects (PDF) September 18 Concu cs.brown.edu 자세한 정리보다, 공부했던 내용을 나중에 쉽게 찾아보기 위해 만들게 되었습니다