여행다니는 펭귄

DFS Algorithm DFS(w, current_Time): w.start_Time = current_Time currentTime++ w.state = in_progress for v in w.neighbors: if v.state is unvisited: current_Time = DFS(v,current_Time) current_Time++ w.finish_Time = currentTime w.state = all_done return current_Time Why it is called depth? Running time n이 vertice의 개수고, m이 edge 의 개수라고 하면 우리는 edge를 단 한번씩만 방문하게 되므로 Running time은 O(m)이 되어야합니다. (Linked-..

전 글에서 Process Virtualization, Memory Virtualization에 대해 모두 다루었죠? 이제는 마지막 Virtualization인 Storage Virtualization에 대해서 다뤄보도록 하겠습니다. 우리가 어떤 저장장치를 쓰던 관계없이, 저희는 일관적인 방식으로 Storage에 접근할 수 있어야 해요. 여기엔 두 가지 Concept가 필요합니다. File File은 연속된 array의 bit으로, 저희가 읽고 쓸 수 있습니다. 이것의 내용은 제작자에 의해 정의됩니다 ( text 파일인지 binary 파일인지) 그리고 inode number로 식별되죠 ( pid 와 비슷한 개념 ) Directory Directory는 특별한 종류의 파일로 다른 파일과 다른 디렉토리를 Co..

SSD란 뭘까요? Solid State Storage Drives는 mechanical(moving parts)한 부분이 없습니다. 그래서 HDD보다 응답시간이 빠르고, 작업을 처리하는 양도 더 많죠. 다만 DRAM과는 다르게 파워가 끊겨도 정보가 손실되지 않습니다. 이 SSD의 핵심 기술이 바로 NAND flash memory 입니다. NAND Flash는 electronic circuits를 사용하여 read와 write 할 수 있는 특성을 가집니다. Floating Gate Transistor를 쓰기 때문에 파워가 없어져도 값을 유지 가능하다는 특성이 있습니다. SSD는 어떻게 동작할까요? SSD는 세개의 Operation을 통해 관리되고, 각 셀의 초기상태를 1이라고 부릅니다. Program : ..

Hard Disk Drive Hard Disk Drives, Disk Scheduling, RAID Hard Disk Drive 하드 디스크는 실제로 디스크로 이루어져있고 이 디스크를 돌리면서 Arm으로 데이터를 읽는 구조입니다. 구체적인 구조를 한번 볼까요? 이것은 HDD안의 Platter 입니다. Plater은 두개의 Surface를 앞뒤로 가지고 있죠. 각 Surface는 동심원들로 이루어져 있는데 이를 Track이라고 부릅니다. Track은 gap으로 구분되는 Sector로 이루어져 있고 이 Sector에 데이터를 저장하게 됩니다. 그럼 정보는 어떻게 Read/Write 할까요? Surface는 track으로 이루어져있고 track은 Sector로 이루어져 있습니다. Disk platter들은 반..

I/O system은 컴퓨터 시스템에 매우 중요합니다. 입력을 받아야 출력도 하고, 프로그램도 실행할 수 있겠죠? 이 I/O system의 주요 세가지 이슈에 대해서 오늘 알아보도록 하겠습니다. I/O system이 어떻게 system에 integrate될 것인지 general mechanism이 무엇인지 우리가 이것을 어떻게 더 효율적으로 만들지 알아보기 전 간단하게 I/O device와 System에 대해 소개하도록 하겠습니다. I/O System Architectures은 다음과 같이 생겼습니다. 각 장치는 Bus를 통해서 통신합니다. 1번 Bus 는 Memory Bus 이며 예시는 AIX가 있습니다 2번 Bus는 General I/O Bus로 예시는 PCIe가 있습니다 3번 Bus는 Periphe..

우리는 그래서 남는 공간을 어떻게 관리해 주어야 할까요? Free space management는 variable sized unit이 포함되어 있어 매우 까다롭습니다. (segmentation 사용할 경우, heap allocation 사용할 경우 발생) 그리고 Externel fragmentation문제가 반드시 발생하게 되어있죠. 이를 minimize 해주는 것이 좋은 Free space management algorithm이라고 할 수 있습니다. Low-level mechanisms 기본적인 mechanism에 대해 살펴보자면 Memory interfaces는 다음과 같은 두개의 함수가 사용됩니다. void* malloc(size_t size) void free(void* ptr) Compacti..

1. Computer Data Storages 2. Memory Virtualization 3. Adress Translation 1. Computer Data Storages 우리가 예전에 살펴보았던 Memory는 Object Code, Program, Os data, Stack등을 포함한 Virtual한 Memory 였습니다. 실제로는 Physical Memory는 Virtual Memory처럼 간단하지 않습니다. 그렇다면 실제 Data를 저장하는 저장장치들은 무엇일까요? RAM RAM은 Random Acess Memory의 약자입니다. Key Features of RAM RAM은 Chip으로 Package 되어 있습니다 램의 저장 단위는 보통 Cell로 Cell당 One bit가 저장됩니다 여러개의..

1. Concept 2. Contents 1. Concept What is Machine Learning Machine Learning vs Deep Learning What is Machine Learning? AI에서 machine learning이 가지는 가장 큰 특징은 data based 라는 겁니다. 예를 들어 설명하자면, 스팸메일을 제거하는 프로그램의 경우 Traditional programming 은 "신용카드", "환영" 등의 단어가 들어가면 스팸메일이라고 구분하는 rule을 기반으로 제거합니다. Machine Learning 은 스팸메일에는 라벨을 1로 하고 아닌 것에 0을 해서 학습을 시켜 나오는 function 을 얻어 이를 기반으로 제거합니다. Machine Learning vs D..

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