🖥 Computer Science

이전 글에 이어지는 내용으로, 가용 블록을 관리하는 첫번째 방법인 묵시적 리스트 방식을 살펴보도록 하겠습니다. 🧐 묵시적 리스트 방식 (Implicit List) 👉 헤더(Header) 모든 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 합니다. 대부분의 할당기가 해당 정보를 블록 내부에 저장합니다. 일반적인 방법으로는 추가적으로 1블록을 사용하여 블록 앞에 블록의 크기를 저장하는 방법이 있습니다. 이때 추가적으로 사용되는 1 워드를 헤더(Header)라고 합니다. 헤더는 블록 크기와 블록이 할당되었는지, 혹은 가용 상태인지를 인코딩합니다. 만약 더블 워드(8바이트) 정렬 제약조건을 설정한다면, 블록 크기는 항상 8의 배수입니다. 즉 블록 크기의 하위 3비트는 ..

🧐 동적 메모리 할당 프로그램이 실행되기 전에는 그 크기를 알 수 없는 메모리 영역을 런타임 시에 획득하기 위해 동적 메모리 할당을 사용합니다. 동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상메모리 영역을 관리합니다. 자세한 내용은 시스템마다 다르지만, 일반화의 오류를 범하지 않는 한도에서, 힙 영역이 초기화되지 않은 데이터 영역 이후부터 시작하여 위쪽(주소가 증가하는 방향)으로 커지는 메모리 영역이라 가정하겠습니다. 각각의 프로세스에 할당되는 가상 메모리에 대하여, 커널은 힙 영역의 꼭대기를 가리키는 포인터(brk ptr)를 사용합니다. 메모리 할당기는 힙을 다양한 크기의 블록 단위로 관리합니다. 메모리를 할당하는 방법에는 명시적(Explicit)으로 할당하는 방법과 묵시적(Implici..

🧐 Trace00 EOF(ctrl + d) 입력을 받으면 프로그램을 종료시켜야 합니다. 더보기 main문을 보면 다음과 같이 이미 구현되어 있는 것을 알 수 있습니다. while(1)을 통해 쉘을 계속 실행시키다가 ctrl + d가 입력되면 프로그램을 종료합니다. 🧐 Trace01 quit 명령어를 built-in command로 등록합니다. quit이 입력되면 프로그램이 종료되어야 합니다. 더보기 void eval(char *cmdline) { cahr * argv[MAXARGS]; parseline(cmdline, argv); builtin_cmd(argv); return; } int builtin_cmd(char **argv) { char * cmd = argv[0]; if (!strcmp(cmd,..

🧐 단일 사이클 구현 단일 사이클 구현은 비록 올바르게 동작한다 하더라도 비효율성 때문에 사용되지 않습니다. 이유는 너무 분명한데, 단일 사이클 설계에서는 클럭 사이클이 모든 명령어에 대해서 같은 길이를 가져야 하기 때문에 클럭 사이클을 가장 오래 걸리는 명령어에 맞추어야 하기 때문입니다. 해당 명령어는 적재 명령어라는 것이 거의 확실한데, 적재 명령어는 명령어 메모리, 레지스터 파일, ALU, 데이터 메모리, 레지스터 파일의 5개 기능을 모두 사용하기 때문입니다. 🧐 파이프라이닝의 이해 파이프라이닝은 여러 명령어가 중첩되어 실행되는 구현 기술입니다. 파이프라이닝의 이해를 돕기 위해 세탁을 진행하는 예시를 들어 살펴보도록 하겠습니다. 우선 파이프라이닝을 사용하지 않은 세탁 방법은 다음과 같습니다. 세탁기..

🧐 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 음의 사이클이 없는 그래프 상에 존재하는 모든 정점에 대하여, 각 정점 간의 최단거리를 구할 수 있는 알고리즘으로, 기본 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다. V = { 1, 2, ..., n } 으로 두고, G의 임의의 두 정점 i, j에 대하여 dist(i, j, k)를 다음과 같이 정의합니다. 정점 (1, 2, ..., k) 만을 path의 중간 정점(intermediate vertex)으로 포함시킬 수 있을 때, i 에서 j로의 최단 경로의 길이 🧐 Recurrence Relation Base Case( k = 0 ) dist (i, j, 0) = 0 : i = j 인 경우 dist (i, j, 0) = w(i, j)..

🧐 최단 경로 문제 그래프 G = (V, E) 상에서 정점 u에서 v로의 가장 짧은 path의 길이를 구하는 문제를 의미합니다. 유명한 방법으로는 다익스트라 알고리즘이 있습니다. 그러나 다익스트라 알고리즘은 음수 가중치를 가지는 간선이 없는 그래프에 대해서만 올바르게 동작한다는 제약이 있습니다. 🧐 Bellman-Ford 알고리즘 최단 경로 문제를 해결하는 dp 기반의 알고리즘입니다. 다익스트라 알고리즘과 마찬가지로 시작 정점 s에서 그래프 G에 존재하는 다른 모든 정점으로의 최단경로를 구하며, 매 단계마다 해당 최단거리의 길이를 업데이트하며 진행되는 알고리즘입니다. 기본적으로는 방향(directed) 그래프를 가정하지만, 무방향 그래프에 대해서도 이를 방향 그래프로 생각하여 적용할 수 있습니다. 벨만포..

🧐 Edit Distance 어떤 단어와 비슷한(가까운) 단어는 어떻게 정의할 수 있을까요? 예를 들어 Word의 spell check 기능을 보면 다음과 같이 비슷한 단어들을 알려주는 것을 알 수 있습니다. Edit distance는 두 string이 얼마나 가까운지 나타내는 척도입니다. 두 문자열 $S_1$ 과 $S_2$ 간의 edit distance는 $S_1$ 에서 아래 3가지 종류의 연산을 최소한 몇 번 수행하여 $S_2$ 를 만들 수 있는가로 정의됩니다. Insertion : $S_1$ 의 아무 위치에 문자 하나를 추가합니다. MONDT -> MONEDT Deletion : $S_1$ 의 아무 위치에서 문자 하나를 제거합니다. MONEDT -> MOMED Substitution : $S_1$ ..

🧐 시그널 이벤트가 시스템에 발생했다는 것을 프로세스에게 알려주는 짧은 메세지 시그널은 상위수준의 소프트웨어 형태의 예외적인 제어흐름으로써, 시그널은 프로세스와 커널이 다른 프로세스를 중단하도록 합니다. 시그널은 예외상황과 인터럽트를 커널에서 추상화한 개념으로써, 대부분의 경우 커널이 프로세스에게로 시그널을 보내주는 형태를 가집니다. 시그널에는 30개의 종류가 있으며, 각 시그널은 정수 아이디로 구분합니다.(1 - 30) 시그널에 포함된 정보는 시그널의 아이디와 시그널이 도착했다는 사실입니다. 다음은 주로 사용되는 몇몇 시그널들입니다. 시그널을 목적지 프로세스로 전달하는 것은 시그널 송신과 시그널 수신의 두 단계로 이루어집니다. 🧐 시그널 송신 커널은 목적지 프로세스의 컨텍스트 내에 있는 일부 상태를 갱..