이번 포스팅에서는 개념에 관한 정리보다는 프로젝트를 진행하면서 궁금했던 점을 위주로 정리해보려고 한다! 프로젝트 3을 진행하다 보면, anon page나 file page에서 swap in 함수로 load_segment 함수를 사용할 일이 생긴다. 이때 load를 할 주소 값을 user virtual address로 넘겨주는 경우와 kernel virtual address로 넘겨주는 경우의 차이가 발생한다. 이 차이가 왜 발생하는지, 또 user virtual address의 경우 kernel virtual address와의 mapping 정보를 page table에 추가해 주었기 때문에 참조가 가능한데, kernel virtual address는 어떻게 바로 참조가 가능한지에 대해 알아보았다. User..
핀토스 프로젝트 2의 시작은 시스템 콜부터다. 사실상 argument passing은 몸풀기... 문제는 몸풀기 수준이었던 argument passing조차도 쉽지만은 않았다는 거..! 이번 포스팅에서는 시스템 콜 중에서 파일 입출력과 관련된 시스템 콜들을 다뤄볼 예정이다. 저번에 웹 프록시 서버를 구현할 때 소켓을 파일로 추상화하여 소켓에게도 파일 디스크립터가 붙었는데, 이번에도 파일 디스크립터 개념을 사용한다. 파일 디스크립터와 관련해서는 다뤘던 포스팅이 있으니 참고하자. https://codable.tistory.com/19 [Computer System] File Descriptor File Descriptor 유닉스 시스템에서는 많은 것들을 파일로 관리한다. 정규 파일들뿐만 아니라 디렉터리, 소..
핀토스 프로젝트 1의 extra 과제이다. multi-level feedback queue scheduler의 구현인데, 일단 저번 포스팅에서 소개했던 스케줄러들과 비교해서 어떤 점이 좋은지 살펴보자. 기존 Priority Scheduler의 문제점 기존 우선순위 스케줄러는 저번 포스팅에서도 언급했다시피 우선순위가 낮은 작업이 계속해서 순서가 밀려 CPU를 얻지 못하는 Starvation 현상이 발생할 수 있다는 점이 있었다. 물론 핀토스에서 구현하는 우선순위 스케줄러에서는 priority donation도 있어 우선순위가 낮은 작업도 충분히 실행될 기회를 잡을 수 있지만, 특별히 락을 소유하지 않고 우선순위도 낮은 작업들은 이러한 조정도 받지 못할 수 있다. 이로 인해 task들의 평균 대기 시간이 길..
드디어 대망의 핀토스다..! 프로젝트 1은 스레드에 관한 내용이다. 좀 더 정확히 짚어서 말하자면 스케줄링 알고리즘 구현이라고 볼 수 있겠다. CPU Scheduling 우리가 사용하는 컴퓨터에서는 여러 개의 프로그램들이 동시에 돌아가고 있다. 좀 더 엄밀히 말하면 동시에 돌아가는 것처럼 보이는 것이다. 사실은 한개의 프로그램만이 하나의 CPU 코어를 사용할 수 있고, 사용 주기가 굉장히 빠르게 교체되기 때문에 우리 눈에는 프로그램들이 동시에 돌아가는 것처럼 보이는 것이다. 여기까지는 우리가 컴퓨터를 보는 입장에서의 설명이었고, 프로그램의 입장에서는 CPU를 마치 자기 자신만이 소유한 것처럼 사용할 수 있게 하는 것이 CPU Scheduling의 목표이다. 현재 프로그램이 디스크에 접근하거나, 키보드의 ..
File Descriptor 유닉스 시스템에서는 많은 것들을 파일로 관리한다. 정규 파일들뿐만 아니라 디렉터리, 소켓, 기타 입출력 장치들 모두 파일의 형태로 취급하는데, 이 파일들을 구분하기 위해 파일 디스크립터라는 개념을 사용한다. 우선 각각의 프로세스들이 실행될때 file descriptor table도 함께 생성된다. file descriptor table은 배열 형태로 관리가 되며, file descriptor table의 각 element는 Inode table의 특정 위치 또는 연결된 소켓을 가리킨다. 우리가 open을 통해 파일을 열거나, socket 함수를 통해 소켓을 생성하면 int 형태의 파일 디스크립터가 리턴된다. 이때 이 파일 디스크립터는 file descriptor table 상..
이번에는 저번 글에 이어서 동적 메모리 할당기의 종류에 대해 알아보자. 일단 메모리 할당기는 크게 두 가지 분류로 나눌 수 있다. Implicit allocator implicit allocator는 자바나 자바스크립트 등의 언어에서의 garbage collector 역할을 하는 동적 메모리 할당기이다. 이 할당기들은 Heap에서 특정 메모리 공간이 더 이상 참조되지 않을 때, 참조되지 않는다는 것을 detecting 하여 스스로 메모리를 반환시키는 할당기들이다. Explicit allocator 오늘 중점적으로 알아볼 할당기이다. explicit allocator는 implicit allocator와는 달리 응용 프로그램이 특정 메모리 공간을 반환한다고 명시적으로 요청해야 한다. 즉 더 이상 사용하지 ..
동적 메모리 vs 정적 메모리 우리가 특정 프로세스를 실행하면, 운영체제는 실행된 프로세스에게 특정 메모리 공간을 할당해 준다. 그 메모리 공간을 그림으로 간단하게 나타내면 아래와 같다. 위의 그림에서 .bss, .data, .text 영역은 정적인 데이터들이 저장되는 공간이다. 정적 메모리는 데이터들이 컴파일 단계에서 메모리 할당이 이루어지는 공간이다. 이와 달리 Heap 영역이나 Stack 영역은 컴파일 이후에 프로그램이 실행되고 나서 메모리 할당이 발생하는 공간이다. Stack 영역은 함수의 지역 변수 또는 매개 변수가 저장되는 공간이고, Heap 영역이 바로 우리가 malloc 또는 free 함수를 통해 변수에 메모리를 할당하고 해제할 수 있는 영역이다. 이렇게만 표현해서는 정확히 정적 메모리와 ..
RB Tree란? Red-Black Tree는 이진 탐색 트리의 한 종류이다. 가장 기본적인 형태의 이진 탐색 트리는 최악의 경우 트리의 높이가 n으로 나타나 비효율적인 면이 있는데, 이를 보완하기 위해 삽입 또는 삭제 연산 시 트리의 균형을 맞추는 트리들이 나타났다. 이를 자가 균형 트리라고 부르며, 대표적으로 AVL Tree와 Red-Black Tree가 있다. 이번에는 Red-Black Tree에 대해 알아보자. RB Tree에는 총 다섯 가지의 규칙이 있으며, 이 규칙을 통해 트리의 밸런스를 유지한다. 다섯 가지의 규칙은 아래와 같다. RB Tree의 다섯 가지 규칙 1. 모든 노드는 빨간색 혹은 검은색 노드이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드들은 검은색이다. 4. 빨간색 노..
이번에 풀 문제는 그래프 수정 문제이다. 위상 정렬을 활용하는 문제인데, 일단 문제를 보고 가자. - N개의 정점으로 구성된 그래프가 입력으로 주어진다. 이때 노드의 번호는 1보다 크거나 같고 N보다 작거나 같다. - 만약 노드 U에서 노드 V로 연결되는 간선이 존재한다면, 노드 V의 번호는 노드 U의 번호보다 커야 한다. - 위의 조건을 만족하도록 노드의 번호를 바꾸고, 원래의 1번 노드부터 N번 노드까지 각각 바뀐 노드의 번호를 출력해야 한다. 위의 말만 봐서는 문제에서 원하는 것이 무엇인지 정확히 감이 오지 않을 수 있다. 다음 입력값을 그림으로 나타내서 이해해 보자! n = 5 node1 : 00110 node2 : 00001 node3 : 00000 node4 : 01000 node5 : 000..
https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 이번에 풀 문제는 가장 가까운 두 점이다. 2차원 평면상에 n개의 점이 주어졌을 때, 가장 가까운 두 점의 거리를 구하는 간단한 문제이다. 설명은 아주 간단하지만 풀이는 그렇지 않다! n의 범위가 최대 100,000 이기 때문에 완전 탐색으로 문제를 풀게 되면 시간 초과를 피하지 못한다... 나는 이 문제를 분할 정복 방식으로 풀었는데, 풀이가 이전에 풀었던 히스토..
