여행다니는 펭귄

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/..

Chapter : CLRS 2.3 4.3~4.6 9 1. Correctness of Merge Sort (1) 2. Running Time Analysis : recurrence relation , Master method , Substitution method (1) 3. Linear time selection (2) Not Today! Merge Sort와 Selection Sort의 알고리즘만 Jupyter Notebook에서 Code 참조 바람. Correctness of Merge Sort 이제 Merge Sort Alg의 타당성을 증명하여 보자. * 알고리즘의 타당성 증명법 iterative case non iterative case (recursive) # 1) Find the loop in..

1. Hardware 2. C code to Process 3. Process 1. Hardware Intel x86 Processor Architecture Programmer's View 왜 Operating System에 대해서 공부하는데 하드웨어에 대해 알아야 하냐구요? 프로세스랑 CPU랑 무슨 상관이라고 왜 갑자기 하드웨어에 대해 이야기 하는지 이해가 잘 안가실 텐데요 모든 프로그램은 그 하드웨어의 특성과 구조에 영향을 받거든요. 고로 하드웨어에 대한 기본적인 이해는 있어야 한다. 이정도 알아두시고 대충 읽고 넘어가주세요. Intel x86 Processor laptop/desktop/server에서는 거의 독점적인 위치를 가지고 있으므로, 위 Cpu를 기준으로 소개하도록 하겠습니다. 혹시 임베..

Q1. 프로그램이 실행(Process, Task)되면 컴퓨터 내에서는 어떤 일이 일어날까요? Process란? 실행되는 프로그램을 의미, Processor(=CPU)로 Process와는 다르다. Task는 Process를 Linux 개발환경에서 칭하는 말. Program 이란? 다수의 Instruction으로 이루어진 Binary File. Disk(Program) -> Memory(Task[Code, Data]) ①- Cpu(② ③[Instructions]) 0. Disk에 저장되어 있는 Program이 Memory로 올라오고 1. CPU가 instruction을 Memory로 부터 ①Fetch(가져오다) 합니다 2. ② Decode : 어떤 Instruction을 실행해야 할지 알아냅니다. 3. ..