Week11 PintOS Filesystem File Allocation Table (FAT) swift-shame-3ee.notion.site File Allocation Table (FAT) sector 각 sector들은 sector number를 통해 접근할 수 있다 → disk에서 주소 역할 disk는 일정한 크기(512bytes)를 가지는 sector로 나누어져있다 cluster file을 저장하는 단위 1개 혹은 다수의 sector로 구성 → pintos에서는 1 cluster = 1 sector 큰 file의 경우 다수의 cluster에 저장된다 하나의 file을 저장하는 다수의 cluster를 배치하는 방법 여러가지가 있다 연속된 space에 배치 external fragmentation..
Week10 PintOS Virtual Memory 참조 swift-shame-3ee.notion.site [ELF] ELF Header ELF 란 용어를 많이 들어보셨을텐데요, ELF는 Executable and Linking Format의 약어입니다. UNIX / LINUX 기반에서 사용되는 실행 및 링킹 파일 포맷입니다. 이번 글에서는 ELF 파일 포맷에 대해 알아보겠습니 sonseungha.tistory.com [ELF] Segment와 Program Header ELF 란 용어를 많이 들어보셨을텐데요, ELF는 Executable and Linking Format의 약어입니다. UNIX / LINUX 기반에서 사용되는 실행 및 링킹 파일 포맷입니다. 지난 글에 이어 이번 글에서는 ELF 파일 포..
Week 09 PintOS UserProgram Argument Passing swift-shame-3ee.notion.site Argument Passing 프로시저 실행 순서 user app은 %rdi, %rsi, %rdx, %rcx, %r8, %r9의 값을 argument로 가져온다 caller는 return address를 자신의 stack에 저장한 후에 callee로 간다(CALL instruction) callee 실행 callee가 return이 있으면 %rax에 저장 return address으로 다시 돌아감(RET instruction) %rdi(첫번째 인자) → int argc %rci(두번째 인자) → char **argv argv는 user stack에 저장 및 stack point..
Week 08 PintOS Threads 1. Alarm Clock swift-shame-3ee.notion.site 1. Alarm Clock 현재 thread를 정해진 시간 후에 다시 시작하는 system call 기존에는 Busy waiting 방식 정해진 시간 동안 계속 바쁜 일을 시켜서 기다리게 하는 방식 pintos에서는 정해진 시간이 지나기 전까지 해당 thread가 cpu를 점유할 때마다 yield시켜버리는 방식 → 다시 ready list로 돌아감 → 다시 cpu 점유하러 올 수 있음 바로 yield되지만 context switching은 계속 일어나기 때문에 자원 낭비 Sleep-Wakeup 방식으로 변경 정해진 시간 동안 해당 thread를 block시켜서(sleep) ready li..
Week 05 개발일지 C 언어 swift-shame-3ee.notion.site C 언어 기억부류(storage class) auto int num = 0; register int i; static int count; extern int global; static void f(void); auto 선언된 위치에서 자동 생성, 선언된 블록을 빠져나갈 때 자동 해제 지역 변수의 default register 레지스터는 주소가 없기 때문에 주소 관련 연산을 할 수 없다대부분의 C 컴파일러는 코드 최적화 단계에서 자동으로 레지스터 변수를 설정하는 기능을 제공 접근 속도가 빠르다 변수를 메모리가 아닌 CPU의 레지스터에 할당 extern(external linkage) 메모리를 할당하지 않고 사용 범위만 늘려준..
Week 03 개발일지 그래프 탐색 기본 swift-shame-3ee.notion.site 그래프 탐색 기본 preorder, inorder, postorder 순회(traversal) 최소 비용 신장 트리(Minimum Spanning Tree) 트리에서 모든 노드를 방문하는 최소 비용 Prim Kruskal 기준 Vertex Edge 이동 방문한 Node에서 이어져나감 전체가 이어져있지 않은 Edge에서도 가능 제한 전체가 연결되어있는 Graph에서만 가능 나눠져있는 Graph에서도 가능 시간 정렬 여부에 따라 O(E log v) ~ O(v^2) 항상 O(E log v) Kruskal 매번 최소 edge를 선택해서 트리 형성 edge 선택으로 트리가 합쳐질 때 Find-Union 사용 Prim 어떤 ..
Week 02 개발일지 이진 탐색 swift-shame-3ee.notion.site 이진 탐색 정렬된 배열에서만 사용 가능 시간 복잡도 O(logN) Python Bisect 라이브러리 분할 정복 Stack LIFO push, pop, top Queue FIFO enqueue, dequeue, front, rear Ring buffer(원형 큐) Deque 양방향으로 삽입과 삭제가 가능한 자료구조 Python collections 라이브러리의 deque Priority Queue 대표적으로 Heap Tree 데이터에 우선순위를 부여하여 우선순위가 높은 데이터부터 Dequeue하는 방식 기타 Line Sweep 알고리즘 정렬된 요소들을 한번만 순회하면서 연산을 하면 답이 나오는 알고리즘 던더 함수(Doub..
