여행다니는 펭귄

영어로 과학 논문을 쓰는것은 생각보다 귀찮은 일입니다. 학술적이면서 알아듣기 쉬워야하는 문체부터 따지는 것이 매우 많죠. 이 복잡한 문제를 차근차근 풀어봅시다. 한국어인 학술논문에도 포함되는 것이니 전 한국어로 논문 쓸건데요? 하시는 분도 봐주시면 감사하겠습니다. 1. 토픽을 분류하라 첫번째 알아봐야 할 것은 어떤 Field에 내 연구가 속하느냐는 것입니다. 단순히 Biology와 같이 큰 대분류부터 시작하는 것이죠. 이 대분류를 아는것은 내가 이 논문을 어디에 투고해야 할지도 영향을 미치기 때문에 정확하게 아셔야 합니다. 필자의 친구의 경우 IEEE에 게제할 내용을 이거 Computer Science 아님? 난 컴공과지 전자과가 아닌데? 몰?루하였다가 교수님께 한 소리를 들은 바가 있습니다. 두번째 확..

파일 시스템과 그 문제점은 무엇일까요? 파일 시스템의 경우 응용 프로그래머가 파일 시스템, 즉 자료구조에 대해 알고 있어야 데이터에 대한 접근을 구현 할 수 있습니다. 이 경우 문제가 생기는 것을 데이터 종속성과 데이터 중복성이라고 합니다. 만약 데이터의 저장 방법이나 접근 방법이 변경 될 경우 응용프로그래머는 이를 알고 다시 응용 프로그램을 수정해 주어야 합니다. ( 데이터 종속성 ) 데이터가 한 시스템 내에 중복되어 저장되기도 합니다. RAID구조와 같은 것이 이렇습니다. ( 데이터 중복성 ) 데이터 중복성은 한 데이터가 수정되었을때 서로 불일치하면 데이터의 일관성이 없어지며 모순이 발생하는 문제, 동일 수준의 보안 유지가 어려워 보안성이 낮아지는 문제, 하드웨어를 비효율적으로 사용하게 되어 경제성이..

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) 입니..