메모리 관리 방식 메모리 관리의 역할은 크게 두 가지로 나뉘어진다. 프로세스에게 메모리를 분배하는 메모리 할당, 처리 중인 프로세스들의 메모리를 관리하는 메모리 보호이다. Relocation 프로세스가 특정 번지의 메모리 주소에 할당되어 있을 때 주소를 옮겨주는 것을 말한다. 메모리 부족 현상을 해결하기 위해 주기억장치에 있던 프로세스를 잠시 보조기억장치로 옮겨 놓는 Swapping이나 메모리 공간을 조각모음하는 Compaction 등의 처리 과정에서 발생한다. 메모리 할당 고정분할식 메모리 할당 한정된 크기의 메인 메모리 공간을 여러 프로세스들에게 분배해주는 방법으로서, 초기 연구된 메모리 할당 방식이다. 파티션을 분할해놓고 프로세스가 생성되면 빈 파티션 중 하나를 부여해준다. 인덱싱 측면에서 유용하며..
운영체제에서 입출력을 관리하는 기능은 커널 I/O Subsystem과 디바이스 드라이버로 나눌 수 있다. 전자는 입출력 관리의 상위 기능을, 후자는 전자의 지시를 받아 직접 하드웨어를 제어하며 입출력을 수행한다. 디바이스 드라이버 초기화 인터페이스 : 드라이버는 모듈 형식으로 구성되는데, 모듈을 생성할 때나 갱신할 때 Init 함수가 호출된다. 파일 시스템 인터페이스 : Open, Read, Write, Release .. 하드웨어 인터페이스 : Inturrpt, Recieve .. 장치와 커널 간 스위치 테이블을 통해 데이터를 교환하는데 Character Driver의 경우 chrdevs[] 테이블을, Block Driver의 경우 blkdevs[] 테이블을 이용한다. 초기화 시 register함수를 ..
1. 트리 자료 구조 트리 트리란 연결 리스트와 같이 노드로 이루어진 데이터 구조를 말한다. 또한 노드 간 Branches들을 통해 연결되어 부모-자식 관계를 갖는다. 배열과 연결 리스트는 선형적인 특성을 갖지만, 트리는 비선형성을 갖고 갈 수 있는 경로가 여러 갈래로 나뉘어 진다. 트리 구조에서 노드는 부모-자식 관계에 따라 자식인 노드만을 가리킬 수 있다. *역행할 수 없으며, 형제 노드 또한 가리킬 수 없다. 하나의 출발점(Root)을 갖는다. 자식 노드를 갖지 않는 끝단의 노드를 리프(Leaf)라 한다. 노드에는 정수 뿐 아니라, 문자열이나 배열 등 다양한 형태의 데이터가 들어올 수 있다. 예시 HTML DOM은 하위 요소로서 자식을 중첩해서 가지고 있는 형태의 대표적인 트리 구조이다. 외에도 개..
1. 스택 스택이란 후입선출 원칙을 따르는 데이터 집합을 말한다. 재귀 파트에서의 호출 스택으로 사례를 접해본 적이 있다. 외에도 Undo / Redo Funtion 혹은 방문기록 라우팅 등에 스택 알고리즘이 사용된다. 배열에서는 Push / Pop 혹은 Shift / Unshift 메서드를 통해 스택을 구현할 수 있다. 맨 앞의 요소를 제어할지, 맨 마지막 요소를 제어할지의 차이이다. 연산도 측면에서는 맨 앞 요소를 변경할 경우 뒤따르는 모든 요소를 새로 배정해주어야 하기 때문에 Shift / Unshft가 열세하다. 그렇기 때문에 배열로 스택을 구현하는 것은 가능은 하지만, 효율 측면에 있어 선호하는 방법은 아니다. 연결 리스트를 통한 구현 단일 연결 리스트와 유사하다. 단, 스택에서의 메서드는 상수..
단일 연결 리스트 글과 이어집니다. 1. 이중 연결 리스트 단일 연결 리스트에서 추가적인 포인터가 하나 더 붙는게 다지만, 메서드 구현 시 많은 추가 코드를 필요로 한다. 따라서 지난 학습 때 구현했던 메서드들을 비교해보며 구현할 예정이다. 인덱스가 없고, 노드의 집합으로 이루어졌다는 연결 리스트의 특징을 여전히 갖고 있다. 추가적으로, 각 노드는 이전의 노드를 가리키는 prev 속성을 추가로 갖는다. 그러면 루프를 통해 Head부터 타고 들어갈 필요 없이, Tail부터 연산을 시작할 수 있으니 Reverse()같은 메서드를 구현하기는 더 쉬워질 것 같다. 노드 클래스 셋업 Node - val, next, prev DLL - head, tail, length class Node { constructor(..
1. 2분기의 첫 번째 주간. 1년 중 내가 가장 좋아하는 시즌이다. 2. 요즘 컨퍼런스나 회고들을 간간이 보고 드는 생각인데, 아직 전문적인 내용들에 대해선 이해가 쉽지 않다. 물론 실무다운 실무를 아직 접해보지 못해서 그렇겠지만, 구현이나 기술에 발목 잡히지 않을 정도의 궤도로 올려 놓는 것이 급선무인 듯 하다. 당장의 상황에서는 리액트가 이에 해당하고, 더 나아가 타입스크립트와 NextJS도 탄탄하게 준비해야 겠다고 생각한다. 3. 다음 주 중으로 네이버 부스트캠프와 현대차 소프티어 캠프 지원 기간이다. 최종까지 가지 못하더라도 자소서나 실전 코테 경험을 쌓으려 하고 있다. 4. 졸작 프로젝트도 본격적으로 시작됐다. 디자인과 레이아웃에 대한 윤곽이 어느 정도 잡혔고, 열심히 만드는 중. 개발 로그를..
1. 단일 연결 리스트 (Single Linked List) 연결 리스트란 데이터를 저장하는 자료구조로, 배열과 같이 순서에 따라 다수의 데이터를 담는다. 그러나 가장 큰 차이점이 있다면, 요소 각각의 인덱스가 존재하지 않는다. 튜플과 유사한 듯. 연결 리스트에서는 각각으 요소들을 노드(Node)라고 부른다. 각각의 노드는 문자열 혹은 숫자와 같은 하나의 데이터 엘리먼트를 저장한다. 추가로 다음 노드를 가리키는 정보(포인터, Pointer)를 저장하고 있어야 하며, 다음 노드가 더 이상 없을 경우 Null을 저장하게 된다. 연결 리스트에는 세 가지 속성이 존재하는데, 가장 앞단 노드인 헤드(Head), 말단 노드인 테일(Tail), 리스트의 길이(Length)를 통해 데이터를 관리한다. 인덱스가 존재하지..
Disk Scheduling 일반적인 입출력 장치 스케쥴링 알고리즘은 '선입선출'이나, 디스크 스케쥴링은 이를 따르지 않음 디스크 구조 디스크는 크기가 큰 순으로 표면(Surface) - 트랙(Track) - 섹터(Sector)로 구성되어 있음. 표면 하나당 20 ~ 1,500개의 트랙이 존재하며, 양면을 모두 사용함. 트랙의 가장 바깥쪽이 0번으로 넘버링되며, 안쪽으로 들어갈 때마다 증가. y축을 기준으로 봤을 때 다른 표면에서 동일한 트랙 넘버를 갖고 쌓이는 집합을 실린더(Cylinder)라고 함. 실린더의 수는 트랙의 갯수와 동일. 한 섹터 영역이 저장될 때마다 섹터의 끝에서 저장된 데이터들에 대한 CheckSum - Parity 연산이 이루어짐. 이는 디스크를 접근하며 주기적으로 오류를 검사할 때..
1. Interrupt 디바이스에 비동기적인 이벤트가 발생했을 때, 처리를 위해 운영체제(커널)에 부탁하는 것을 인터럽트라 한다. 인터럽트는 커널에 접근하여 구현된 함수를 실행하게끔 하는 Kernel entry point 중 한 가지 방식이며, 이외에도 트랩(Trap, Software Interrupt), 시스템콜(System call)이 존재한다. 비동기적이라 함은 이벤트가 발생하는 시점이 미리 정해지지 않은 경우를 말한다. Interrupt Handling 장치들은 PIC(Programmable Interrupt Controller)를 거쳐 CPU로 신호를 전송하고, 이를 커널 스택에 저장 후 유저 모드에서 모드 체인지를 통해 커널에 진입한다. 인터럽트 처리 과정 유저 모드에서 인터럽트 발생 시, C..
앞서 학습한 버블정렬, 선택정렬, 삽입정렬, 합병정렬, 퀵정렬은 '비교 정렬' 그룹에 속함. 주어진 시간에 두 가지 요소를 비교하는 방식. 이러한 비교 정렬은 한계점이 존재하며, 최선의 경우 O(n log n)의 복잡도를 갖는다 (합병정렬, 퀵정렬) 기수정렬 (Radix Sort) 비교를 수행하지 않는 특별한 정렬 알고리즘으로, 숫자 크기에 대한 정보를 이진수로 인코딩하여 정렬한다. 작동방식 배열 요소의 0의 자리 수부터 분리한다. 모든 값들은 (0-9) 사이로 레이블링되고, 이를 0 레이블의 먼저 들어온 값부터 꺼내 배열한다. 자릿수를 좌측으로 옮겨가며 레이블링을 반복하면, 정렬이 완료된다. 헬퍼함수 1. getDigit(원하는 숫자 인덱스 찾기) : 원하는 숫자가 어느 자릿수 인덱스에 위치하는지 반환..
