여행다니는 펭귄

I/O Devices (tistory.com) I/O Devices I/O system은 컴퓨터 시스템에 매우 중요합니다. 입력을 받아야 출력도 하고, 프로그램도 실행할 수 있겠죠? 이 I/O system의 주요 세가지 이슈에 대해서 오늘 알아보도록 하겠습니다. I/O system이 어떻 penguintravler.tistory.com 1) I/O는 Hierarchy 구조를 이룸 (Physics and Cost) 2) System에 Integrate 시키는 방법 Register사용 (Status, Command, Data) Special I/O instruction 쓰기 아니면 Memory mapped I/O 쓰기 3) I/O OS 관리법 Polling ( Simple 동작잘함, CPU낭비됨 ) Inte..

Virtual Memory and Adress Translation (tistory.com) Virtual Memory and Adress Translation 1. Computer Data Storages 2. Memory Virtualization 3. Adress Translation 1. Computer Data Storages 우리가 예전에 살펴보았던 Memory는 Object Code, Program, Os data, Stack등을 포함한 Virtual한 Memory.. penguintravler.tistory.com 1) 메모리의 종류와 Multi level cell Technique에 대한 간략한 소개 2) Memory Hierarchy가 동작가능한 이유 (Temporal Locality,..

FSCK와 Journaling은 모두 Crash Consistency문제를 해결하기 위한 방법입니다. Crash Consistency 문제란 뭘까요? 많은 Data Structure과는 다르게, File system의 Data Structure은 무조건 안정되어야합니다. File System을 crash-consistency problem을 피하면서 안정시키는 것입니다. 즉 그러니 쓰다가 전원이 나가거나 해도 File System이 보존되어야 하는것이죠. Crash Consistency Problem이 어떻게 발생할지 어떤 경우에 발생할지 한번 볼까요? 저희가 파일을 쓰게 되면 Data Bitmap, Inode, Data Block에 정보를 써 주어야 합니다. 하지만 이것은 동시에 일어나는 동작이 아니라..

그전에 File System Implementation에서 살펴보았던 와 같은 구조는 간단하지만 매우 안 좋은 성능을 가지고 있습니다. Problem 1: Positining cost가 높습니다. Data가 Disk에 저장되어 있다면 AccessTime이 데이터가 조각나있을 수록 높을텐데 이를 고려하지 않은 시스템입니다. Expensive한 Positioning Cost를 가집니다. 예를들어 Data Block과 파일은 서로 자주 접근해야하는 관계임에도 불구하고 매우 멀리 떨어져있습니다. 이럴 경우 Seek Time이 늘어납니다. Problem 2: Fragmentation이 이것을 더 심각하게 만듭니다. 만약 데이터 A-B-C-D가 순서대로 저장되어 있었더라도 B와 D가 지워진 후 E를 저장하려면 E가..

Operating System은 Virtual Space를 매우 크게 할당해 줍니다. 그것이 편리하고, 사용하기 쉽기 때문이죠. 그러니 저희는 Virtual Memory가 가득 차있을지, 아닐지 신경을 쓸 필요가 없는 것입니다. 그렇다면 만약 Virtual Memory를 다 쓰는 프로그램이 아주 많아서 메모리가 부족하면 어떻게할까요? 이를 위해서 OS는 Swapping 을 사용합니다. Disk안에 Page Size의 Unit을 만들어 두고 계속해서 Swap in, Swap out 시키는 것이죠. 이럴 경우 Page Table에는 present bit가 추가됩니다. 그러니까 Memory에서 이것을 찾아야하는건지 Disk에서 찾아야 하는건지 알려주는 용도이죠. Page Hit, Page fault는 이것이 ..

Page Table 은 굉장히 크기가 큽니다. 동작중인 프로세스를 전부 저장해야 하기때문에 그 부담이 더 크죠. 그렇다고 이렇게 Page Size를 늘이면 Page Table의 크기는 줄어들지만 Internel Fragmentation이 매우 심각해집니다. 그렇다면 이것을 어떻게 해결할 수 있을까요? 일단 Hybrid Approach를 해 봅시다. 일단 Page Table의 대부분은 비어 있습니다. 모든 프로그램이 Address Space를 전부 채워서 사용하는것은 아니죠. 이 성질을 활용하여 segmentation과 paging을 합칠 겁니다. 전체 Address가 PageTable을 가지는게 아니라, cod heap stack 즉 logical Segment 하나당 PageTable을 가지는 것입니다..

BFS Search Algorithm def BFS(start): Set L_i = [] for i = 1,..,n L_0 = {start} for i = 0,...,n-1: for u in L_i: for each v in u.neighbor: if v.state = unvisited: mark v as visited, and put in L_i+1 Running Time은 O(n+m)으로 DFS와 같습니다. Application - Shortest Path 만약 Weight이 걸려 있지 않는 그래프의 경우 시작점으로부터의 최단 거리를 알 수 있습니다. Application - Bipratite Graph Biparatite Graph란 연결된 노드가 모드 Bipartite한 경우입니다. 이 Graph..

TLB에 대한 내용은 저번에 Paging에 대한 글에서 살펴보았었죠? TLB는 full associative method를 통해 관리됩니다. 보통 TLB는 32,64,128개 정도의 Entry가 있는데, Hardware가 TLB에서 이 엔트리를 parallel하게 검색하여 줍니다. TLB는 그리고 PFN 이외에도 valid bit, protection bit, ASID(address-space identifier) 등을 또 저장합니다. 이 ASID의 쓰임새는 나중에 알아보도록 하겠습니다. TLB에는 두가지 이슈가 있는데 1) TLB Miss를 누가 Handle할 것인지 (Hardware vs Software) 이고, 2) Context Switch를 어떻게 관리할 것인지 (Flush vs ASID) 입니..

저번에 Segmentation에 대해서 알아보았죠? 그런데 Segmentation에는 문제점이 많습니다. Externel fragmentation Free space management가 복잡하다는 점 Compaction이 비싸다는 점 또 Code구간 Stack구간 Heap구간이 나뉘어져있는데 Free Space가 있어도 Heap이 자라날 공간이 없다면 더이상 allocation을 해줄수 없다는 점 그래서 새로운 방식인 Paging을 도입합니다. Paging의 Concept는 다음과 같습니다. Virtual Address를 Code Heap Stack에 구분없이 fixed-size의 unit인 page로 나누고 이를 virtual page라고 부릅니다. Segmentation은 Variable Size로..

File System을 Implement하는데 있어서는 두가지를 해 주어야 합니다. Data structures On-disk File Structure를 설계해 주어야 합니다. Access methods open(), read(), write()등을 어떻게 처리할지 설계해 주어야합니다. Data Structures Disk를 Blocks로 나누는 것에서 시작합니다. 각 블록들은 Data Region, Innode Table, Bitmap, Superblock, Boot Sector로 구분되어 할당됩니다. Data Region User data를 저장하기 위한 장소입니다. Inode Table Inode 를 저장하는 장소입니다. Inode에는 File type, File size, Index of dat..