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(원하는 숫자 인덱스 찾기) : 원하는 숫자가 어느 자릿수 인덱스에 위치하는지 반환..
퀵 정렬 (Quick Sort) 기본적으로 배열 요소 갯수가 0이나 1개가 될 때까지 쪼개는 합병정렬과 유사하다. 여기서 피벗포인트라 부르는 단일 요소를 선택하여 수행하는 것이 차이점이다. 중앙점이 아닌, 이 피벗포인트를 기준으로 배열을 한 번 순회하여 기준보다 작은 수를 왼쪽 그룹으로, 큰 수를 오른쪽 그룹으로 이동시킨다. 로직을 이해하고 구현하는 데에 난이도가 좀 있는.. 알고리즘이다. 1. 피벗 헬퍼 앞선 합병정렬에서 합병로직을 먼저 구현했던 것처럼, 퀵정렬에서도 피벗 헬퍼를 통해 퀵정렬에 사용할 메서드를 모듈화해준다. 피벗 헬퍼는 주어진 배열 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치한다. 좌/우 배열 내의 정렬 여부는 당장 중요하지 않다. 피벗의 선택 기준 배열의 모든 요소 값들을 알..
앞서 배운 정렬 알고리즘들은.. (버블, 삽입, 선택) 작은 규모의 배열에서는 잘 작동하지만, 규모가 커질수록 잘 적용되지 않는다. 합병정렬 (Merge Sort) 0. 개요 배열을 더 작은 배열로 나누는 방식 (분할정복 알고리즘), 요소 배열이 0개나 1개가 될 때까지 반복 0개나 1개가 된 요소 배열 모음을 다시 병합함. 이 과정에서 정렬이 이루어짐. 예를 들어 8개의 원소를 가진 배열을 합병정렬하고자 한다면, 4 -> 2 -> 1개의 원소 그룹으로 나누고 1 -> 2 -> 4 -> 8개로 합치는 과정에서 정렬 1. 로직 구현 의사코드 정렬된 두 배열의 합병을 담당할 함수 구현. 입력 배열 두 개에 있는 모든 요소를 포함 초기값이 0인 I와 J 카운터를 두 배열에 각각 배치하여 While문을 통해 구..
File Allocation 파일에서는 블록 단위로 데이터를 저장한다. 블록 하나의 크기는 4,096Byte이다. 파일 내부에 여러 개의 블록이 존재할 때, 이들을 연결해주는 것을 File Allocation이라 한다. Allocation에는 아래와 같은 방법이 존재한다. Contiguous Allocation 디스크 내부에 존재하는 연속된 블록들을 할당해 파일을 저장하는 방법. 파일 구성 테이블이 존재하는데, 이 테이블에 파일명 - 시작 블록 인덱스 - 블록 길이가 들어있다. 장점 Read/Write 처리하는 데에 시간이 적게 걸린다 단점 External Fragmentation이 발생. 먼저 Fragmatation이란 메모리에 생기는 작은 빈 공간을 말하는데, 빈 공간이 덩어리로 이루어져 있지 않고,..
선택정렬 큰 값을 배열 마지막 인덱스에 위치시키는 버블정렬과 달리, 작은 값을 한 번에 하나씩 위치시킨다. 기준 값과 나머지 원소들을 전부 순회하며 비교하여, 가장 작은 값과 자리를 바꾼다. 의사코드 최솟값 인덱스를 저장할 변수 필요. 초기값은 시작하는 기준 값과 동일하게 설정해주면 될 듯. 기준값부터 나머지 원소를 순회하며 최소값 인덱스를 갱신, 저장 기준값과 최소값 교환 원래 기준값 다음 인덱스부터 1,2,3 과정 반복 구현 function selectSort(arr) { for (var i = 0; i arr[minIdx]) { let tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } } return arr; } const arr = [4, 24,..
데이터를 정렬할 수 있는 방법은 무수히 많고, 각 알고리즘은 장단점을 갖고 있다. 같은 결과값을 갖더라도 결과를 내기까지의 과정이 제각기 다르다. 특정 상황에 유난히 잘 작동하는 정렬 방법이 존재하고, 이를 잘 활용하게 하기 위함 버블 정렬 자바스크립트 내장 정렬 메서드 array.sort() : num1 - num2 가 양수를 반환하면 num2가 앞에, 음수를 반환하면 num1이 앞에 온다. 숫자 뿐 아니라 문자열으 길이를 음수/양수로 구분하여 정렬할수도 있다. function numberCompare(num1,num2){ return num1 - num2; } [ 6, 4, 16,10 ].sort(numberCompare); 개념 현재 항목과 다음 항목을 한 번씩 비교하여 교환. 제일 끝에서부터 차례..
0. 검색 (Search) IndexOf 메서드 같은 배열 인덱싱, 문자열 파싱과 관련된 파트 내장함수의 처리 과정을 이해하고, 직접 구현하여 활용할 수 있게 하기 위함 1. 선형 검색 (Linear Search) 모든 개별 항목을 한 번씩 확인하는 방법 첫부분부터 끝부분으로 이동하며 탐색할수도, 역순으로 탐색할수도 있음 indexOf, includes, find, findIndex 메서드를 통해 선형 검색을 구현 기본적인 선형 검색 구현 function linearSearch(arr,value){ for (var i=0; i
1. 데드락 (Deadlock) 프로세스나 쓰레드가 사용하고자 하는 컴퓨터 자원을 다른 프로세스가 갖고 종료 조건이 서로 맞물려 있는 상태로 무한정 대기하는 상황을 데드락(Deadlock)이라고 한다. 프로그램 설계 시 데드락이 발생하지 않도록 유의하여야 한다. 각자 설계한 프로그램이 단독적으로 실행될 때는 문제가 없을 수 있지만, 여러 개의 프로그램이 함께 실행되는 과정에서 발생할 수도 있기 때문에 문제점을 발견하거나 예방하기 쉽지 않다. 컴퓨터 자원의 분류 재사용 가능한 자원(Reusable Resources)과 소비성 자원 (Comsumable Resources)으로 나뉘어진다. CPU나 입출력 장치, 메모리 등 대부분의 하드웨어 자원은 사용 후 소멸되지 않으므로 재사용 가능한 자원에 속한다. 이러..
