본문 바로가기

전체 글

 (86)
[Lecture 14] 멀티쓰레딩 VIII - Atomic Variables and Operations #Introduction 적절한 락(lock)이 사용될 때, 여러 스레드는 공유 주소 공간에 접근할 수 있고 공유 메모리 멀티스레딩 프로그래밍 모델의 기본 직관에 해당하는 이러한 공유 변수의 동일한 값을 볼 수 있다. 데이터 레이스가 없는 프로그램만이 순차적 일관성을 제공한다(모든 스레드에 의해 "단계"의 관점에서 모든 메모리 동작의 순차적 순서가 관찰되며 프로그램의 순서와 일치한다) 이를 보장하는 전통적인 방법은 lock사용, 세마포어나 조건 변수를 사용하는 것이었다 lock: lock을 획득하고 중요 섹션에 진입하는 두 번째 스레드에는 lock을 획득한 첫 번째 스레드에서 수행한 모든 업데이트가 표시된다 세마포어/조건 변수: 대기 호출에서 반환되는 스레드는 대기에서 스레드를 반환하게 된 신호 작업 전..
[Lecture 13] 멀티쓰레딩 VII - Performance #Performance Considerations 멀티스레딩 프로그램에서는 정확성이 가장 중요하다. 정확성은 성능과 바꿀 수 없다. 데이터 레이스, 원자성 위반, 순서 위반 또는 교착 상태가 발생하기 쉬운 코드의 성능에 대해서는 아무도 신경 쓰지 않는다. 그렇긴 하지만 이번 포스트에서는 멀티스레딩 프로그램에서의 성능에 대해서 알아보자. 먼저 잠금 (lock)의 비용을 알아 보자. 간접 비용(잠금 사용으로 인한 성능 손실) 아래 나올 사진들은 다음의 실험을 거처 나온 성능 결과이다. 5개의 CPU 바인딩 프로세스를 시뮬레이션하여 Lock을 경합하고 D 기간 동안 각 잠금을 유지한 다음 U 기간 동안 잠금 없이 실행한다. 스레드가 임의로 잠금을 선택한다. 연한 녹색은 잠금 장치를 고정하지 않고 실행되는 쓰레..
[Lecture 12] 멀티쓰레딩 VI - Atomicity Violations #Atomicity Violations 원자성 위반(Atomicity Violations)은 적절한 잠금 규칙을 준수하는 경우에도 발생할 수 있는 동시성 (concurrency) 버그 유형이다(공유 데이터에 액세스하거나 업데이트하는 동안 잠금이 일관되게 유지되는 경우). 보통 Atomic이어야 하는 업데이트가 결합될 때 동일한 잠금의 보호 하에 수행되지 않는 경우 발생한다. 원자성 위반 발생 가능 패턴들: 보호용 잠금 장치 획득 (a) 공유 상태에서 정보를 추출 (b) 잠금 해제 보호 (c) 정보를 기반으로 한 행동에 대한 약속 (d) S'를 보호하는 잠금 장치 획득 (e) 저장된 정보를 기반으로 한 공유 상태 S'에 대한 조치 (f) S'를 보호하는 잠금 해제 (g) 공유 상태로 업데이트되어 b)에서 ..
[Lecture 11] 멀티쓰레딩 V - Deadlock #Deadlock 데드락, 즉 교착상태란 2개 이상의 배타적인 자원을 2개 이상의 프로세서 또는 태스크가 부분적으로 각각 점유하고자 함에 따라 일어나는 상태이며 그것 이상 어느 쪽도 진행되지 않는 상태를 말한다. 그림은 태스크 A가 파일 A를 점유하여 파일 B의 점유해제를 기다리거나 태스크 B가 파일 B를 점유하여 파일 A의 점유해제를 기다리게 되어 양 A, B 태스크가 모두 이것 이상 처리가 진행되지 않는 상태의 예를 나타낸다. 쉽게 말해 하나 이상의 관련 스레드가 차단된 스레드의 원인이 되므로 절대 발생하지 않을 이벤트를 기다리는 상태이다 (리소스 에서 데드락이란: 스레드는 현재 리소스를 요청하는 스레드에 의해 보유되므로 허용되지 않는 리소스를 기다리는 동안 차단된다.) Deadlock은 리소스 경합..
[Hard] 295. Find Median from Data Stream (Microsoft 기출 문제) #문제 설명 #문제 풀이 class MedianFinder { PriorityQueue minHeap = new PriorityQueue(); PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); public MedianFinder() { } public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll()); } public double findMedian() { if (maxHeap.size() > minHeap.size()) retu..
[Medium] 451. Sort Characters By Frequency #문제 설명 #문제 풀이 HashMap + Heap class Solution { public String frequencySort(String s) { Map map = new HashMap(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } PriorityQueue pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a)); for (char c : map.keySet()) { pq.offer(c); } StringBuilder sb = new StringBuilder(); while (!pq.isEmpty()) { char c = pq.poll(); for (int i ..
[Lecture 10] 멀티쓰레딩 IV - Condition Variables & Monitors #Condition Variables & Monitors / 조건 변수 & 모니터 조건 변수(mutex와 함께)는 모니터라고 하는 더 큰 추상화의 구성 요소이다. 동시성 프로그래밍에서 모니터(Monitor)는 스레드가 상호 배제와 특정 조건이 거짓이 될 때까지 기다리는(차단) 기능을 모두 가질 수 있도록 하는 동기화 구성체이다. 모니터는 또한 다른 스레드의 조건이 충족되었음을 알리는 메커니즘을 가지고 있다. 모니터는 뮤텍스(lock) 개체와 조건 변수로 구성된다. 조건 변수는 본질적으로 특정 조건을 기다리는 스레드의 컨테이너이다. 모니터는 스레드가 배타적 액세스 권한을 다시 얻고 작업을 재개하기 전에 특정 조건이 충족될 때까지 대기하기 위해 일시적으로 배타적 액세스를 포기하는 메커니즘을 제공한다. 쉽게 ..
[Lecture 8] 멀티쓰레딩 II - Basic Locking / Managing Shared State #Introduction 멀티스레드 프로그램은 가상 주소 공간을 공유하기 때문에 주소 공간에 할당된 모든 개체(글로벌 변수, 힙 개체 등)에 직접 액세스할 수 있다 Preemptive scheduling 체제에 의해 도입된 non-determinism 및/또는 여러 프로세서 또는 코어에 대한 동시 실행은 이러한 공유를 어렵게 만든다. (예: counter++) #Data Races 데이터 레이스란 멀티 쓰레드 환경에서 여러 쓰레드가 공유자원에 동시에 접근할 때 유발되는 문제이다. 두 개 이상의 스레드가 공유 변수에 액세스하고, 적어도 하나의 액세스는 쓰기 액세스이며, 최종 결과는 스레드의 실행 순서, 특히 메모리 액세스 순서에 따라 달라진다 이러한 데이터 레이스는 동시성(concurrency) 관련 버그..

티스토리툴바