한달꾸 한달꾸

'운영체제 - 아주 쉬운 세 가지 이야기'와 'Computer System - A Programmer's Perspective'를 읽고 작성한 글 입니다. 틀린 부분이 있을 수 있습니다. CPU 가상화 운영체제는 CPU, 메모리, 디스크와 같은 자원들을 가상화시킨다. 내 컴퓨터의 Task Manager 화면을 살펴보자. Logical processor는 4개인데(코어 수와 차이나는 이유는 하이퍼쓰레딩 때문이다.), Process는 251개가 현재 돌아가고 있다. 심지어 Thread의 개수는 3312개다. 한정된 개수의 Logical processor위에서 이렇게 많은 수의 process와 thread가 동작할 수 있는 이유는 운영체제가 CPU를 가상화시켜주기 때문이다. 한정된 자원인 CPU를 무한개의 C..

Memory Management 현재 pintos에는 lazy loading이 구현되지 않은 상황이다. lazy loading을 구현하기 위해서는 특정 virtual address에 대응되는 page에 대한 정보가 추가적으로 필요하다. 각 page에 관한 정보를 담는 page 구조체를 생성하자. 또한, 이 page들을 supplemental page table이라는 hash table을 통해 관리했다. 추가적으로, user_pool이 가득 차서 page를 더이상 할당해줄 수 없는 경우 page의 정보들을 swap out&swap in 하는 코드까지 구현해 보았다. page는 세가지의 type중 한 가지 종류로 정해지며, 최초에 할당되는 page는 lazy loading을 위한 uninit_page로 설정..

Process "메모리에 적재되어 실행중인 프로그램" 사용자의 프로그램이 OS에 의해 메모리 공간을 할당받아 실행 중인 것을 말한다. 프로세스는 프로그램에 사용되는 데이터와 메모리자원 그리고 thread로 구성된다. 하드디스크의 프로그램을 실행하면, 프로그램 실행을 위해 메모리 할당이 이루어진다. 할당된 메모리 공간에 바이너리 코드가 올라가며 프로세스가 실행된다. Thread 프로세스는 스레드라고 하는 실행 유닛으로 구성되어 있다. 모든 프로세스에서 한 개 이상의 스레드가 존재하고 스레드가 작업을 수행한다. 스레드는 서로 code, data, heap영역을 공유하고 stack영역을 별도로 사용한다. 따라서, 별도의 process를 실행시키는 것 보다 데이터 공유를 쉽게 할 수 있고 효율적이다. Pthre..

Pointer (feat. char) char* a = "hello";로 a가 "hello"의 시작점을 가리키게 하고, *a = 'H'를 통해 "hello"를 "Hello"로 바꾸려는 시도를 해보았다. 하지만, 컴파일 결과 우리가 원하던 "Hello"가 제대로 반환되지 않고, 오류가 발생했다. Code #include #include int main() { char* a = "hello"; *a = 'H'; printf("%c", *a); } 위의 코드에서 hello가 변경이 되지 않은 채 프로그램이 종료되는 것이 아니라 왜 오류가 발생하는지가 의문이었다. 여기저기 찾아보던 중 microchip-'How do i copy char b[] to the content of char* a variable?'c..

B-Tree - 삭제 B Tree 삽입에서 가득 찬 노드들을 미리 분할했던 것 처럼, 삭제시에도 최소 키의 개수를 가지는 노드들이 키를 더 많이 가질 수 있도록 미리 처리한다. k를 찾아 재귀적으로 내려가는 과정에서 방문하는 경로에 존재하는 키의 개수가 (t-1)인 경우 형제 노드에서 키를 가져오거나, 형제노드와 병합하는 과정을 거친다. 삭제 과정에서 발생할 수 있는 모든 경우의 수에 대해 알아보자. 1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다. 2. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재한다. 3. 리프 노드가 아닌 노드 x를 방문했을 때, x 내에 k가 존재하지 않는다. 1. 리프 노드 x를 방문했을 때, x 내에 k가 존재한다. 리프 노드 x 내에 k가 존재한다..

이번 포스팅에서는 트리를 단순화하기 위해, 키와 관련된 부수적인 정보는 키와 같은 노드에 있다고 가정한다. Abdul Bari 교수님의 10.2 B Trees and B+ Trees. How they are useful in Databases click 위의 강의에서 설명하는 방식과 다른 방식의 삽입을 설명합니다. 해당 포스팅에서 설명하는 방식은 루트 노드에서 리프 노드까지 Top-Down으로 내려가며 재귀적으로 탐색하는 방식입니다. B-Tree - 기본 규칙 1. 모든 노드 x는 아래와 같은 속성이 있다. a. x.n은 노드 x에 현재 저장되어 있는 키의 개수다. b. x의 key들은 x.key(1) leaf; z->n = DEGREE - 1; for (int j = 0; j < DEGREE - 1; ..

B-Tree 1월 8일 부터 1월 13일까지, B - Tree와 B+ - Tree를 구현하는 프로젝트를 진행하고 있다. 오늘(1월 11일)을 시작으로 한 주 동안 B - Tree의 원리, 삽입 그리고 삭제가 어떻게 이루어지는지에 대해 알아볼 것이다. B - Tree 관련 포스팅들은 [Introductions to Algorithms (Third Edition), Tomas H. Corman]의 내용을 토대로 부족한 설명들과 예시를 덧 붙일 예정이다. 들어가기 전에 B - Tree를 공부하며, 인터넷의 여러 강의들 그리고 블로그들을 참고했다. 그런데, B - Tree를 구현하는 방법이 조금씩 달라서 이해하는데 혼란스러웠던 점이 있다. 특히, 대부분의 자료들에서 삽입에 대한 설명보다 삭제에 대한 설명이 부족..

단순 연결 리스트 C언어의 pointer를 사용해 연결리스트를 구현해 보았다. 아래의 structure를 만들어 연결리스트의 node로 사용하였다. node는 item과 pointer로 구성했다. item은 해당 노드의 값을 저장하고, pointer는 다음에 이어질 node의 주소를 저장한다. typedef struct node { int item; //node의 값을 저장하는 변수 struct node* next; //node의 주소를 저장하는 포인터 } node; 단순 연결 리스트 중에서도 가장 간단한 형태로 구현했다. 값이 추가되지 않은 초기 상태에는 연결 리스트의 시작지점을 가리키는 'head'node가 존재한다. 현재 값이 추가되지 않았음으로, head의 pointer(head->next)는 N..