메뉴 닫기

디스크 스케줄링 알고리즘

(사실 글을 쓰는 이유는 C-SCAN의 C가 무슨 의미인지 궁금해서 쓴다.)

FCFS

First come, First serve, 이름답게 오는 순서대로 정직하게 처리해주는 방식. 별도의 최적화가 없기 때문에 평균 대기시간이 느리다.

SSTF

Shortest Seek Time First, 현재 위치에서 탐색 시간이 가장 짧은 블럭을 먼저 처리해주는 방식. 헤드가 자주 움직일 수 있고, 어떤 블럭은 중간에 끼어든 블럭으로 인해 처리가 너무 느리거나, 영영 처리되지 않을 수 있다. (Starvation)

SCAN

엘리베이터 알고리즘의 일종. 일반적인 엘리베이터는 움직이는 방향의 변화와 사람들이 기다리는 평균 대기시간을 줄이기 위해서 한쪽으로만 움직이다가, 다른 쪽으로 움직이게 되는데,1혹시 엘리베이터의 작동 요령에 관심이 없던 사람을 위해 적는다면, 엘리베이터는 움직이는 방향으로 오는 요청을 먼저 처리한다. 즉, 8층에서 내려가고 있는 엘리베이터에서 11층과 1층의 사람이 동시에 눌렀다면, 1층의 사람이 먼저 처리되고, 만약, 1층 가기전에 엘리베이터가 5층에 있을 때, 3층 사람이 버튼을 누르면, 3층에 있는 사람이 먼저 탄다. 그러한 특성을 반영한 알고리즘. 다만 엘리베이터 알고리즘을 그대로 적용한 SCAN은 플래터의 중간에 있는 블럭들이 두번이나 처리되는 문제도 있고, 아무래도 상대적으로 상하로 이동하면서 요청 블럭들의 처리 시간이 꽤 차이가 나게 된다. 그래서 아래의 C-SCAN이 고안되었다.

C-SCAN

Circular-SCAN. 가상으로 플래터에 위치한 실린더들이 끊어져 있지 않고, 가장 바깥쪽 실린더와 가장 안쪽 실린더가 연결되어 있다고 생각하면, 그저 한쪽 방향으로만 쭈욱 읽는 것이 더욱 공평하게 처리 가능하기 때문에 고안되었다. (실린더를 원소의 끝과 처음이 연결된 환형 리스트라고 생각한다.) 한쪽 방향으로만 읽다가, 헤드를 다시 가장 끝쪽으로 다시 위치시키는 방법이기 때문에, (예를 들어 바깥에서 안 쪽으로 읽는다면, 안쪽에 도달했을 때는 그냥 헤드의 위치를 바깥쪽으로 재위치 시키기만 한다. 중간에 읽기 작업을 안하고.) 헤드를 재위치 시키는 것은 그냥 손실된 시간에 불과함.

C-LOOK

C-SCAN의 개선 버전, 무작정 가장 바깥에서 가장 안쪽으로 읽지 말고, 읽을 원소가 있는 부분에서만 이동하는 방법

SSD 처럼 전자적 저장장치는 그냥 FCFS을 써도 무방하고 (데이터의 Seek Time에 차이가 없으니까), 하드디스크는 제조사에 따라 다르겠지만 SCAN을 쓰는 듯하다. (딱히 무슨 알고리즘을 쓰는지 공개해놓은 제조사는 없는 것 같다.)