여행다니는 펭귄

1. Multiprocessor 2. Multiprocessor: Background 3. Multiprocessor: Algorithms 1. Multiprocessor Multicore Processors CPU, Processor, Core, Thread Concurrency vs Parallelism Amdahl's Law Multicore Processors Single Core Processor의 성능 ( Clock Hz )의 증가가 Power Density 때문에 한계에 다다릅니다. 결국 number of threads per core 를 높이기로 결정하게 되었습니다. CPU, Processor, Core, Thread 멀티프로세스 시스템에서 프로그램을 짜는 것은 매우 어렵습니다. Concu..

1. Mutal Exclusion 2. Lock 1. Mutal Exclusion 우리는 Thread의 실행을 synchronize 해야 합니다. 이것은 한 Thread 가 Critical Section에 진입하면 나오기 전까지 모든 operation 을 atomically 수행하게끔 할 수 있죠. 이에 보편적으로 사용되는 Solution들은 1. Mutex (lock) and Semaphore 2. Condition variables (Pthreads) 3. Monitors (Java) 입니다. 오늘은 여기서 Lock과 다음 글에선 Semaphore에 대해서 다뤄보도록 하겠습니다. 2. Lock Evaluating Locks Controlling Interrupts Why Hardware Support..

1. Thread Concept 2. What Happens Running Multi thread program? 3. Critical Section 1. Thread Concept Thread Multi-threaded Program Context Switch between Threads Address Space of Multi-Threaded Program Thread Thread란 single running process의 새로운 Abstraction입니다. Multi-threaded program 하나 이상의 execution point가 있는 program을 Multi-threaded program 이라고 합니다. 같은 Process의 Thread들은 같은 address space를 공유합니다...

1. Concept 2. Practical Scheduling Policies 1. Concept Workload Assumption Scheduling Metrics FIFO SJF STCF New Scheduling Metrics RR Length of the Time Slicing Incoporationg I/O 저번 시간에 한번 Scheduling Policies 에 대해 알아보았죠? 그럼 이제 Policy는 어떻게 구현해야 할지 이번 글에서 다뤄보도록 하겠습니다. Workload Assumption Workload란 무엇일까요? 쉽게 말하면 어떤 entity에서 주어진 시간 동안 실행되는 작업을 의미합니다. 우리는 CPU Scheduling을 편하게 평가하기 위해서 몇가지 가정을 해 줄 텐데요 ..

Chapter : CLRS 5, 7, 9.2, 10 1. Bogosort 2. Randomized Quicksort 3. Randomize Select 4. Majority Element 5. Direct Address Tables 6. Hash Tables 7. Hash Functions 8. Universal Hash Families 9. Open - Addressing Hash table이란 sort of data structure으로 빠른 Insert/Delete/Search를 제공합니다. Hash table에서 Hash Family, 그리고 Universal Hash Tables까지 살펴보도록 하겠습니다. Direct Addressing 이 Hash family에서 목표는 Insert, Dele..

Chapter : CLRS 5, 7, 9.2, 10 1. Bogosort 2. Randomized Quicksort 3. Randomize Select 4. Majority Element 5. Direct Address Tables 6. Hash Tables 7. Hash Functions 8. Universal Hash Families 9. Open - Addressing Randomized Selection 저번 글에서 나왔던 Select function 대신, randomized select를 다시 봅시다. def randomized_select(A, k, c=100): if len(A) k: # The kth smallest element is left of the pivot return sele..

Chapter : CLRS 5, 7, 9.2, 10 1. Bogosort 2. Randomized Quicksort 3. Randomize Select 4. Majority Element 5. Direct Address Tables 6. Hash Tables 7. Hash Functions 8. Universal Hash Families 9. Open - Addressing Randomized Algorithm (Monte Carlo vs. Las Vegas) 랜덤 알고리즘이란, 알고리즘 내 연산에 랜덤성이 들어가는 알고리즘입니다. 이 알고리즘은 기능 중 어디에 초점을 맞춰서 볼 건지에 따라 몬테 카를로인지, 라스 베가스 알고리즘인지 갈립니다. 라스 베가스 알고리즘은 정확성을 보장하지만, 실행 시간이 랜..

1. CPU Virtualization 2. Limited Direction Execution 3. Context Switch 1. CPU Virtualization Mechanism vs Policy Process States Data Structures How to Efficiently Virtualize CPU? Direct Execution 저희 저번시간에 CPU Virtualization에 대해 간단하게 소개했었죠? 우리가 CPU virtualization을 어떻게 적용 할 수 있을지 한번 봅시다. Mechanism VS Policy policy라고 하는것은 뭘 할지를 정의하는 것입니다, mechanism이란 어떻게 할지 정의하는 것이죠. CPU virtualization에서의 저 둘은 뭘까요?..

Chapter : CLRS 8.1-8.2 1. Limit of Comparsion-based Sorting Algorithm 2. Counting Sort 3. Bucket Sort 4. Radix Sort Limit of Comaprsion-based Sorting 우리가 아까 이전 챕터에서 본 Algorithm들은 element 두개를 비교한다. 이것을 트리로 만들어 보면? 최소한 n!개의 leaf를 가진 tree로 변한다. 완전히 balanced tree라고 가정하면 log(n!)의 선택을 하게 되므로 복잡도는 최소 n log(n/e) = Ω(n log(n)) 이다. 더보기 log(n!) = Ω(n log(n)) log(1) + ... + log(n/2) + ... + log(n) >= log(n/..

막스 베버 (이상률 역 문예출판사) 서평 어떠한 정치인이 참된 정치인이라고 믿나요? 누구는 정치인은 악과 손잡지 않아야 할 것을 주장합니다. 또한, 자기 신념을 끝까지 밀고 나가는 것이 참된 정치라고 이야기 합니다. 다른 이들은 수단과 방법을 가리지 않고 목적 만을 달성하는 것이 중요하다고 주장합니다. 권력과 관련된 문제에서는 민주사회에서 당선이 되는 것이야 말로 옳음을 담보한다고 믿는 자와, 국민에 반하더라도 신념을 가져야 한다고 주장하는 자가 있죠. 막스 베버는 어떻게 생각할까요? 라는 책 제목을 보면 알듯 그는 정치에 있어 환상적인 기대를 하지는 않습니다. 그는 모든 면을 가진 균형의 정치인이 될 것을 요구합니다. 왜냐면 우리는 매 정치 순간마다 딜레마에 시달리기 때문입니다. 우리가 한 나라의 지도..