디스크에 접근하는 시간은 보통 Seek Time + Rotational Delay + Transfer Time으로 이루어져 있고, 이 중 Seek Time (탐색시간)이 가장 크다.
현대 PC 환경은 대부분 다중 프로그래밍 환경을 따르고 있다. 여러 개의 프로세스가 같이 진행되다보니 디스크 큐 (Disk Queue)에는 서로 다른 프로세스가 보내는 많은 요청 (Request)들이 쌓여 있다. 그렇다면 이렇게 많은 요청들을 어떻게 처리하면 탐색시간을 줄일 수 있을까? 하는 고민이 생긴다.
이를 해결하기 위해 디스크 스케줄링 알고리즘이 등장했다.
선입선출의 느낌이 강한 알고리즘이다. 이름에서 알 수 있듯이 가장 먼저 도착한 요청을 가장 먼저 처리한다. 제일 간단하면서도 제일 공평한 방식이다.
0 ~ 200 까지의 실린더 위치가 있다고 하자. 현재 요청은 Disk Queue : {98, 183, 37, 122, 14, 124, 65, 67} 으로 들어와있다. 현재 Head의 위치는 53에 있다.
First-Come First-Served의 원칙에 따라 가장 먼저 들어온 요청을 순서대로 처리한다.
총 움직임은 640 Cylinders이다.
하지만 과연 FCFS가 효율적이라고 할 수 있을지는 의문이다. 움직이는 거리를 더 최소화할 수 있는 방법이 없을까?
현재 위치에서부터 Seek Time이 가장 짧은 요청을 먼저 처리한다.
마찬가지로
Disk Queue : {98, 183, 37, 122, 14, 124, 65, 67}
Head : 53
현재 53부터 거리가 가장 짧은 요청을 먼저 처리하므로, 총 이동 거리는 236 Cylinders이다.
확실히 FCFS에 비해 이동거리가 매우 짧다는 점을 알 수 있다. 하지만 SSTF는 치명적인 단점을 갖고 있는데 바로, 기아 (Starvation) 현상이 발생할 수 있다. PC를 계속해서 사용하면 Disk Queue에는 지속적으로 새로운 프로세스의 요청이 들어온다. 현재 Head와 더 가까운 거리의 요청이 계속해서 들어온다면, 결국 멀리 떨어져 있는 실린더는 끝내 수행하지 못하는 현상이 발생하게 된다.
또한 SSTF은 최적의 알고리즘이라고 할 수 없다. 가령, SSTF은 처음에 53번에서 바로 65번으로 이동하는데, 만약 53번에서 37번으로 이동한 후 SSTF를 수행하면 208 Cylinders의 움직임으로 해결할 수 있다.
Scan 알고리즘에서 Head는 디스크 전체를 끊임없이 앞뒤로 스캔한다. 즉, 디스크의 한 끝에서 시작하여 다른 끝으로 이동하며 가는 길에 있는 모든 요청을 처리한다. 다른 한쪽 끝에 도달하면 다시 반대 방향으로 이동하면서 오는 길에 있는 요청을 처리한다. 엘리베이터처럼 왕복하며 처리하므로 엘리베이터(elevator algorithm)라고도 부른다.
예시를 살펴보면,
Disk Queue : {98, 183, 37, 122, 14, 124, 65, 67}
Head : 53
Scan 알고리즘은 그림에서 보다시피 한쪽 끝까지 이동한 후, 역방향으로 이동한다. 하지만 처음부터 한 방향으로 끝까지 움직이고 다시 처음으로 되돌아가서 같은 방향으로 끝까지 움직이는 것이 더 효율적이라고 볼 수 있다.
53번에서 시작해서 0번까지 이동한 후 199번까지 이동을 하는데, 예를 들어 이미 지나가버린 자리에 새로운 요청이 들어왔다고 해보자. {20, 23, 30, 32}에 새로운 요청이 들어왔는데 현재 Head는 199를 향해 가고 있다. 따라서 {20, 23, 30, 32}의 요청은 Head가 199를 찍고, 다시 199부터 0으로 돌아오기까지 기다려야만 한다. 이러한 비효율성을 해결하기 위해 등장한 개념이 C-Scan이다.
C-Scan은 실린더를 마치 하나의 원처럼 생각해서 순환한다. 즉, 실린더의 처음과 끝이 연결되어있다고 본다. 0의 이전이 199이고, 199의 이후가 0이라고 보는 것이다. 따라서 C-Scan은 199까지 이동하면, 다시 역방향으로 오는 것이 아니라, 다시 0으로 가서 0부터 199까지 이동한다.
또한 한쪽 끝을 찍고, 다시 처음으로 돌아가는 길에는 요청을 읽지 않는다. 즉, 재빠르게 처음으로 돌아가서 다시 끝까지 훑은 개념이다. 이렇게 하면 총 움직이는 거리는 더 길어질 수 있지만 다시 처음 위치로 되돌아갈 때는 데이터를 읽지 않으므로 더 빠른 속도로 움직일 수 있다.
Scan과 C-Scan은 이동하는 거리에 요청이 있든 없든 무조건 끝에서 끝까지 이동한다. 굳이 이동하지 않아도 될 거리까지 이동하므로 비효율적이라고 볼 수 있다. 이를 보완해서 나온 개념이 LOOK이다.
LOOK은 굳이 끝에서 끝까지 가지 않고, 이동하다가 더 이상의 요청이 없으면 방향을 반전하여 되돌아간다.
하지만 더 이상의 요청이 있는지 없는지를 파악하기 위해 Disk Queue를 미리 검사해놓아야한다는 단점이 있다.
C-LOOK은 Circular Look의 약자로서, C-Scan의 동작 방식과 같지만 Scan이 아니라 Look 버전이다.
Scan은 요청이 있든 없든 끝에서 끝까지 무조건 이동하지만, LOOK은 더 이상 요청이 없으면 방향을 전환한다고 했다.
C-Scan은 끝을 찍으면 다시 돌아오는데, 훑으면서 돌아오지 않고 처음부터 다시 훑어간다고 했다. C-LOOK도 마찬가지인데 여기서 끝은 그 방향의 가장 마지막 요청까지이다. 더 이상의 요청이 없으면 다시 가장 처음에 있는 요청으로 돌아와서 다시 끝까지 훑는다.
