핀토스 프로젝트 2는 유저 프로그램에 관한 과제다. 첫 번째 프로젝트는 모두 커널 영역에서 진행이 되었다.(이거 덕분에 나름 디버깅이 편했던 편...) 두 번째 프로젝트는 크게 두 가지 파트로 나뉘는데, 이번 포스팅에서는 그 첫 번째를 다뤄보고자 한다. Argument Passing 첫번째로 argument passing이다. 우리가 함수를 사용할 때, 함수에 인자를 넘겨주는 방식을 구현하는 과제다! 우리가 인자를 함수로 넘겨줄 때 스택에 넣어두었다가 함수에 진입하고 나면 스택에서 argument를 꺼내 사용한다. 예를 들어 다음과 같은 코드가 있다고 생각해보자. void add(int a, int b) { printf("%d\n", a + b); } 위의 add 함수는 인자로 a와 b를 넘겨받고, 각각..
핀토스 프로젝트를 하면서 크게 두 가지 스케줄러를 구현해보았다. 물론 기본적으로 구현되어있는 busy waiting 또한 스케줄링 방식 중 하나이지만 내가 구현한 것이 아니니까.. 이번 포스팅에서는 CPU 스케줄러에 대해서 조금 더 자세히 알아보고자 한다. CPU Scheduling Criteria 먼저 스케줄러의 성능 척도에 대해서 알아보고 가자. 크게 다섯 가지가 있는데 다음과 같다. 1. CPU Utilization(프로세서 이용률) CPU를 사용한 시간의 비율을 나타낸다. CPU가 오랜 시간동안 바쁜 상태로 있을 때 높아진다. 대기 시간이 긴 I/O 작업이 많을수록 나빠지며, 단순 연산 작업만 많은 경우 높아진다. 2. Throughput(처리율) 시간당 처리한 작업의 비율을 의미한다. mallo..
드디어 대망의 핀토스다..! 프로젝트 1은 스레드에 관한 내용이다. 좀 더 정확히 짚어서 말하자면 스케줄링 알고리즘 구현이라고 볼 수 있겠다. CPU Scheduling 우리가 사용하는 컴퓨터에서는 여러 개의 프로그램들이 동시에 돌아가고 있다. 좀 더 엄밀히 말하면 동시에 돌아가는 것처럼 보이는 것이다. 사실은 한개의 프로그램만이 하나의 CPU 코어를 사용할 수 있고, 사용 주기가 굉장히 빠르게 교체되기 때문에 우리 눈에는 프로그램들이 동시에 돌아가는 것처럼 보이는 것이다. 여기까지는 우리가 컴퓨터를 보는 입장에서의 설명이었고, 프로그램의 입장에서는 CPU를 마치 자기 자신만이 소유한 것처럼 사용할 수 있게 하는 것이 CPU Scheduling의 목표이다. 현재 프로그램이 디스크에 접근하거나, 키보드의 ..
BSD 소켓이란? BSD소켓은 인터넷 소켓 또는 Unix domain 소켓에 대한 인터페이스이며, 프로세스 간의 통신(IPC)에 쓰인다. Berkeley Software Distribution에서 개발되어 BSD 소켓이라는 이름이 붙었으며, POSIX socket 이라고도 불린다. 이 인터페이스는 현재 인터넷에서 실행되는 응용 프로그램들의 표준 인터페이스이다. 흔히 소켓은 인터넷 통신 과정에서 사용하는 것으로 알려져 있다. 인터넷 통신 과정에서 소켓을 많이 활용하지만, 같은 디바이스 내에서 서로 다른 프로세스가 통신을 하는 과정에서도 소켓이 활용된다. 소켓의 연결 과정 소켓이 연결되는 과정은 위의 그림과 같다. 크게 서버와 클라이언트로 나누어서 생각해 보자 Server 1. Socket : 소켓 객체를 ..
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. 빨간색 노..
이번에는 LCP 배열에 대해 알아보자! LCP 배열을 이해하기 위해서는 이전에 쓴 글인 접미사 배열을 우선적으로 이해해야한다. 2023.03.27 - [Algorithm] - [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) 접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미 codable.tistory.com 위의 글에서 들었던 예시인 banana를 사용하자. LCP 배열을 만들기 위해서는 우선 해당 접미사가 정렬된 Suffix 배열에서 어느 위치에 있는지를 기록해야한다. 이를 위..
접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미사들을 만들어준다. 만들어진 접미사들을 맨 앞글자를 기준으로 정렬한다. 이후 정렬 기준을 앞에서 2번째 문자, 3번째 문자 ... 로 늘려가면서 최대 문자열의 길이인 n번째 문자까지 바꿔가며 정렬을 진행한다. 위의 과정을 따르면, 한번 정렬을 진행하는데 $O(n log n)$ 만큼의 시간이 걸리고, 정렬을 최대 문자열의 길이만큼 반복한다고 했으므로 총 시간복잡도는 $O(n^2 log n)$ 과 같이 나타날 것이다. 이를 맨버-마이어스 알고리즘을 통해 $O(n log^2 n)$의 시간복잡도로 단축시킬수 있다. 이제 정렬이 ..
