KOCW - 양희재 교수님 강의를 기반으로 운영체제 정리
디스크 스케줄링
디스크 접근 시간
- seek time(헤더 움직임, 가장 긴 시간) + rotational delay(원하는 블럭으로 회전) + transfer time(데이터 읽기)
이전 시간에 학습한 내용처럼 하드디스크에 접근하는 시간 seek time이 가장 큰 피중을 차지하고 있습니다.
현재 사용하고 있는 컴퓨터는 다중 프로그래밍 환경이기 때문에 디스크에 접근하는 것도 프로세스 별로 순서가 필요합니다. 따라서 프로세스는 디스크 큐(disk queue)에 요청을 기다리고 있습니다.
디스크 처리를 빠르게 하려면 가장 비중이 큰 seek time을 줄여야 하는데 이번 시간에 알아볼 내용이 효율적인 탐색을 위한 디스크 스케줄링 알고리즘 입니다.
FCFS (First-Come First-Served)
200 cylinder dist (0,1...,199)
Disk queue : [98, 183, 37, 122, 14, 124, 65, 67]
Head is currently at cylinder 53가장 간단한 방법은 먼저 디스크 큐에 도착한 순서대로 처리하는 방법입니다.
예제를 통해 FCFS의 성능을 알아보겠습니다.
현재 하드디스크는 실린더(같은 위치의 트랙의 모음)의 개수가 200개 입니다. 위의 그래프는 queue에 도착한 순서대로 헤더를 움직였을 때의 이동거리를 나타냅니다.
헤드가 움직인 거리는 (183 - 53) + (183 - 37) + (122 - 37) + (122 - 14) + (124 - 14) + (124 - 65) + (67- 65) = 640 cylinder를 이동한 것을 확인할 수 있습니다.
SSTF (Shortest-Seek-Time-First)
SSTF는 현재 헤더의 위치에서 가장 가까운 위치부터 처리하는 방식입니다. 이 방식으로 헤더의 이동거리는 계산해본다면 236 cylinder입니다.
실제로 디스크를 사용하는 요청은 지속적으로 들어오고 있습니다. 그렇다면 현재 헤더의 위치에서 먼 곳은 우선순위가 계속 밀리는 기아(starvation)현상이 발생할 수 있습니다.
또한 현재 위치에서 가장 가까운 실린더를 선택하는 것이 최적의 알고리즘은 아닙니다. 만약 53번 실린더에서 65번이 아닌 37번으로 이동한다면 최종적으로 208 cylinder를 이동하는 것을 확인할 수 있습니다.
SCAN
디스크 헤더가 디스크 헤더의 전체를 SCAN하는 방식입니다. 결국 헤더를 안쪽으로 끝까지 읽고 다시 바깥쪽으로 끝까지 읽는 방식으로 작동합니다.
위의 예시는 안쪽으로 들어가는게 먼저 일어난다고 가정하고 헤더의 이동거리를 구하는 방법입니다. 결과적으로 53 + 183 = 236 cylinder 입니다.
토론
많은 프로세스가 존재한다면 읽으려고 하는 실린더는 골고루 퍼져 있습니다. 따라서 양방향으로 움직이기 보다는 현재 위치에서 한방향으로 헤더를 움직이고(53 -> 0) 빠르게 끝까지 움직여 시작위치로 헤더를 움직이는(199 -> 53) 방법이 더 효과적일 수 있습니다. 이러한 아이디어에서 나온 스케줄링 방식을 Circular SCAN이라고 합니다.
SCAN Variants
C-SCAN
C(Circular)-SCAN 방식은 토론에서 설명한 방법입니다. 위의 그래프는 헤더를 바깥으로 빼는 방향으로 움직이고 빠르게 안쪽으로 움직여서 바깥쪽으로 움직이는 방식입니다.
LOOK
SCAN 방식의 그래프를 살펴보면 14번 실린더에서 요청이 끝났음에도 끝까지 들어가는 것을 볼 수 있습니다. 그러므로 존재하는 실린더의 최소와 최대 범위안에서 움직이는 알고리즘을 LOOK 알고리즘입니다. 하지만 이 방식을 최소,최대값을 구하기 위해 큐를 탐색하는 추가 작업이 필요합니다.
C-LOOK
C(Circular)-LOOK 방식은. Circular방식과 LOOK방식을 합친 기법입니다. 기본적으로 Circular방식처럼 한 방향으로 움직이지만 끝까지 가는 것이 아니라 최소, 최대 범위 안에서 움직이는 Circular 방식입니다.(53->14, 183->65)
Elevator Algorithm
Elevator Algorithm은 위에서 소개한 SCAN, C-SCAN, LOOK, C-LOOK 방식의 그래프를 90도 회전하면 엘리베이터 모습과 유사하여 붙여진 이름입니다.
