본문 바로가기

프로그래밍/JUNGLE

PintOS Project 4. File System Project4. File System 1.Indexed and Extensible Files 1번과제는 2가지 목표가 있다. 하나는 FAT을 이용해 File system을 구현하는 것이다. 또, 현재는 파일의 크기가 limit이 있는데 얼마든지 확장할 수 있는 구조를 만들어야 한다. 파일은 의미 있는 정보를 담는 논리적인 단위이다. 이 파일은 메타데이터 (파일의 진짜 정보!)를 가지고, 이름 길이 등등을 가진다. 원하는 파일을 열고 닫고 쓰고 읽기 위해서는 파일에 접근해야한다. 이 방법론에 관한 내용이 핵심이다. 한 섹터는 512 bytes이고 어떤 파일이 총 10개의 섹터가 필요하다고 하자. 10개의 연결된 섹터로 파일을 저장하면 좋겠지만 이럴 경우 외부단편화가 발생하기 쉬워진다. 때문에 우리는 10.. 더보기
Project3. Virtual Memory (PintOS) Project3. Virtual Memory 1. Memory Management 늘 그래왔듯, 가장 기초 즉 이 project3가 흘러가는 코드의 시작을 공부한다. Project2까지는 load를 어떻게 해왔는지 생각해보자. 우리는 process_exec -> load -> load_segment -> setup_stack 등의 방식으로 메모리를 적재했다. (load_segment, setup_stack은 주의깊게 보지 못했을 수 있다.) 그러나 프로그램 전체를 메모리에 load 하는 것은 매우 비효율적이다. 그래서 우리는 lazy_load를 사용한다. 지금 당장 사용해야할 부분만 load하고, 사용하지 않는 부분은 표시만 해둔다고 생각하면 될 것 같다. 이렇게 하면 당장 큰 프로그램을 모두 load하.. 더보기
PintOS project2. User Program Project2. User Program 1. Argument passing 첫 과제는 Argument passing이다. 이를 이해하기에 앞서, 2주차 과제에서 우리가 배워야 할 것이 무엇이고 목적이 뭔지 생각해보자. 쉘에서 우리는 프로그램을 실행할 때, echo 'Hello World' 처럼 echo라는 프로그램을 'Hello World'라는 인자값을 주어 실행한다. 혹은 더블 클릭으로 폴더를 열거나, 파일을 실행하는 것도 같은 맥락일 것이다. 이렇게 사용자가 어떤 프로그램을 실행하겠다고 명령했을 때, 그 명령을 컴퓨터가 이해할 수 있게 잘 전달해줘야 한다. 즉, project2의 목표는 User Program을 어떻게 컴퓨터가 식별하고 실행하는가! 에 관한 것이다. 더 구체적으로 말하자면, Pint.. 더보기
PintOS project1. Threads PintOS 1주차의 기록 기본 구성 thread의 status는 Thread_Running, Thread_Ready, Thread_blocked, Thread_dying 로 4가지이다. 이 개략적인 그림을 알고 있으면 상태 변화를 이해하기 쉽다. (참고: https://poalim.tistory.com/33?category=758538) [Pintos] Project 1 : Thread(스레드) - Priority Scheduling(1) 스케쥴링은 ready 상태에 있는 스레드들의 순서를 관리하여 가장 높은 priority 를 가진 스레드가 running 상태가 될 수 있도록 만들어주는 것이다. 현재상태 우선 현재 pintos 가 스케쥴링을 어떻게 관 poalim.tistory.com 추가로 Pint.. 더보기
[C] 재귀함수를 만드는 Global 변수 vs argument C로 코딩을 하다가, 문득 문제를 만났다!! 짜고자 하는 함수는, tree의 중위순회한 결과 (작은 값부터 오름차순으로)를 arr에 담아주는 함수이다. 함수는 짧으니 아래를 보며 이해하자! int i = 0; int inorder_array(node_t *n, key_t *arr) { if (n) { inorder_array(n -> left, arr); // printf("%d \n %d \n", n -> key, i); arr[i++] = n -> key; inorder_array(n -> right, arr); } return 0; } 이렇게 짤 경우, int i = 0 이라고 i라는 global 변수를 선언했다. 그래서 함수 내부에서 i 값을 증가시키고, arr[i]에 중위순회의 값을 넣어주는 방.. 더보기
RB Tree 삽입 Red-Black Tree의 삽입 RB의 삽입에 대해 알아보자. 색 변환과 rotate를 제외하면 Binary Search Tree의 삽입과 같다. (BST를 이해하고 오자!) 위 그림과 같이 insert 하려는 node를 X, X의 부모를 P, 부모의 부모는 G, 부모의 형제인 삼촌노드는 U로 표현하자. 그리고 BST의 insert 과정이 끝났다고 생각하자. (즉, x가 어디에 위치할지 찾고 삽입한 것이다!) X는 항상 빨간색이다! X가 루트인 경우 X노드가 루트라면, RB의 특성 1을 유지하기 위해 BLACK으로 변경해준다. X가 루트가 아닌 경우 부모가 검은색인 경우 X는 항상 RED이므로 부모가 BLACK이면 삽입해도 RB가 깨지지 않는다!! (5가지 특성이 모두 지켜진다.) 때문에 검은색인 경우.. 더보기
이진 탐색 트리(Binary Search Tree) C로 구현하기 #include #include typedef struct _Node { int value; struct _Node *left_child; struct _Node *right_child; }Node; Node* search(Node *root, int x); Node* insert(Node *root, int x); Node* find_min(Node *root); Node* delete(Node *root, int x); int count = 0; int main() { Node *root; int N; int i, input; root = NULL; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &input); root = insert(root, i.. 더보기
RB Tree [레드 블랙 트리] https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 ko.wikipedia.org Red-Black Tree Red-Black Tree(이하 rb)는 이진 트리의 한 종류이다. 그 중에서도 balanced search tree의 하나이다. rb는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 O.. 더보기

티스토리툴바