🧐 Study/MultiThread

- SET : 아이템의 중복을 허용하지 않음 : 정렬되어 저장됨 (unordered_set이 아님) - 검색 효율 증가 : 삽입 삭제의 효율성을 위해 링크드리스트 구현 : 구현 ) add, remove, contains : 필드 ) 리스트에 저장되는 값  : 메서드 - add(x) : 집합에 x추가, 성공 시 true - remove(x) : 집합에서 x 제거, 성공 시 true - contains(x) : 집합에 x가 있다면 true  : 추가 구현 ) 보초 노드 - 검색 효율을 위해 항상 존재하는 Head(MAXINT)와 Tail노드(-MAXINT)를 갖도록 함   - 성긴 동기화 : 리스트는 하나의 잠금을 가짐 : 모든 매서드 호출은 이 잠금을 통해 Critical Section으로 진행됨 ( = ..

- Lock-free 자료구조 : 여러 개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘  : Non-blocking이 보장되어야 함 : 알고리즘 내에 Lock이 있으면 당연히 Lock-free X, Lock이 없다고 해도 무조건 Lock-free인 것은 아님 : Lock이 존재하는 경우 다른 쓰레드를 실행할 수 없어 싱글 쓰레드와 다를 바가 없음     → wait-free를 유지하며, 메모리로 Atomic Memory를 만들 수 있는 알고리즘 존재? : 존재, 이 강의에서 생략.  → wait-free를 유지하며, 기존 씽글 스레드 자료구조도 Atomic Memory를 사용해 멀티쓰레드 자료구조로 변환 가능? : 불가능하다..

- CPU 주의점 : 저번 시간 상호 배제에 이어 메모리 일관성 문제도 고려해야 함 : 지금까지 프로그램은 공유 메모리에 대한 접근(읽기/쓰기)을 atomic하다고 가정함 → 컴파일러가 제대로 기계어로 번역했다면 → atomic : 메모리의 접근이 순간적으로 행해지며, 서로 겹치지 않고 실행 결과 순서가 정해지면, 모든 쓰레드에서 같은 순서로 보임 → 그러나 PC에서의 메모리 접근은 atomic이 아님 (메모리에 쓴 순서대로 메모리의 내용이 관측되지 않음)   : 0번 쓰레드도 false를 읽고 1번도 false를 읽음  : 저번 시간에 했던 피터슨 알고리즘에서 std::atomic_thread_fence(std::memory_order_seq_cst)를 제외한 경우 아래의 결과처럼..

- Data Race로 인한 오동작 1) Data Race를 없애자 → Lock/Unlock → 성능 저하 → Data Race를 줄이자 → 알고리즘 재 작성 → 너무 어렵다 2) Data Race를 고려한 프로그래밍을 하자 → ???   - 컴파일러 주의점 : Data Race가 있는 줄 알고 있고, 실행 결과를 예측할 수 있으면 문제를 피할 수 있도록 프로그래밍 할 수 있지 않을까?  아래 코드를 돌려보도록 하자.bool g_ready = false;int g_data = 0;std::mutex srm;void Reciver(){ while (false == g_ready) std::cout    → 결과 값 : Ok(Debug모드), 엉터리(Release ..

- 멀티쓰레드 프로그래밍 주요 사항  : 올바른 결과가 나와야 함 ( 무한루프에 빠지거나, 프로그램이 오류로 종류되면 안됨 ) : 이를 사용한 성능향상이 커야함 ( 적으면 멀티쓰레드를 쓰는 이유가 없음 ) : 멀쓰 프로그래밍은 하나의 프로그램을 나눠서 작성하는 것   - 위에서 틀린 결과가 나온 이유 : Data Race -> sum += 2 : 공유 메모리를 여러 쓰레드에서 읽고 쓰고, 이 순서에 따라 실행 결과가 예상과는 달라진다 : Data Race  ⇒ 복수의 쓰레드가 하나의 메모리에 동시에 접근 & 적어도 한 개의 write  : 읽고 - 더하고 - 쓰는 이 사이에 context switching이 일어나서 문제  (동시 접근 -> read, write) ─ 앞의 프..

- 멀티쓰레드 사용 목적 => 병렬 컴퓨터에서의 프로그램 성능 향상 : 멀티 코어 CPU에서의 프로그램 성능 향상 : 멀티 CPU 컴퓨터에서의 프로그램 성능 향상 : 분산 컴퓨터, 싱글 코어 환경에서의 성능 향상 X, 모듈화해서 쉽게 알아보기 X   - 멀티코어 CPU : 한 개 이상의 코어로 구성된 CPU : 현재 싱글 코어 CPU는 없다고 봐도 무방 : 코어 = ALU + Register + CU + Cache    ⇒ 그냥 CPU와 같음 : 멀티코어 CPU ⇒ 하나의 칩에 여러 개의 프로세서를 포장해 넣음 ( 프로그래머 입장 : 멀티 프로세서와 같음) : 6 Core(Quad Core) 대세 : 앞으로 더욱 많은 Core 사용하게 될 것 -> 기존 프로그램을 Du..