디스크 스케쥴링 방법

디스크 스케줄링(Disk Scheduling)

 

운영체제의 역할 중 하나는 효율적인 하드웨어 사용이다. 디스크 드라이브의 경우에는 빠른 접근 시간과 높은 전송량을 제공해야 함을 의미한다. 디스크 접근시간은 두 가지 요소로 이루어지는데 탐색시간(seek time, 디스크 암이 헤드를 해당 실린더로 움직이는데 걸린 시간)과 회전 지연(rotational latency, 디스크 헤드가 원하는 섹터 위치로 도달하기까지 회전에 소요되는 추가적인 시간)시간 이다.  디스크 대역폭(bandwidth)은 단위 시간 당 전송되는 총 바이트 수이다. 효율적인 스케줄링은 접근 시간과 대역폭을 모두 향상 시킬 수 있다.

 

 

프로세스가 입/출력을 필요로 할 때마다 운영체제에 시스템 호출(system call)을 한다. 이 호출에는 여러 가지 인수가 주어 진다.

l  입력인가 출력인가

l  디스크 주소

l  메모리 주소

l  전송될 섹터 수

 

디스크 드라이브가 유휴 상태라면 이 요청은 즉시 처리 되고 아니면 큐(queue)에 들어가 기다려야 한다. 다중 프로그래밍에서는 많은 프로세스들이 디스크를 공유하므로 이 큐에는 여러 디스크 입/출력 요청들이 함께 대기하고 있을 수 있다.

 

디스크는 대기하는 작업의 처리 순서를 제어하는 여러 알고리즘을 사용하는데 그 종류에 대해서 알아 보자.

 

[선입 선처리 스케줄링 (FCFS Scheduling)]

가장 간단한 형태인 선입 선처리(first-come-first-served)이다. 이 알고리즘은 본질적으로는 공평해 보이지만 빠른 서비스를 제공하지는 못한다. 예를 들어 다음과 같은 입/출력 요청이 디스크 큐에 있다고 가정한다.

98, 183, 37, 122, 65, 67

 

디스크 헤드가 현재 53 실린더에 있다면 헤드는 53->98->183->37 … 67로 이동하여 총 640 실린더 헤드를 이동하는데 비용이 많이 든다.

 

 

 

[최소 탐색 시간 우선 스케줄링 (SSTF Scheduling)]

헤드(head)가 다른 곳으로 이동을 시작하기 전에 근처에 있는 요구들을 먼저 처리해 주고 헤드를 이동하는 것이 합리적이다. 최소 탐색 시간 우선(Shortest Seek Time First)알고리즘은 이러한 논리에 근거한 것이다. 이 알고리즘은 현재 위치로부터 가장 가까운 요청을 우선 선정한다. 탐색 시간은 헤드가 경유하는 실린더 수에 따라 증가하므로 최소 탐색 시간 우선은 현재 위치로 가장 가까이 요청된 것을 선택 한다.

 

현재 헤드가 53 실린더에 있다면 가장 가까운 65 -> 67 -> 37 …-> 183 순서로 처리 된다.

 

최소 탐색 시간 우선(SSTF) 알고리즘은 최소 작업 우선(Shortest Job First) 스케줄링과 유사하지만 몇 개의 요청들은 매우 오래 기다리게 되는 기아(starvation) 상태가 발생하게 된다. 새로운 요청이 기존의 위치와 가까운 요청이 계속 들어온다면 멀리 있는 요청은 무한정 기다려야 하는 현상이 발생한다. 이 같은 현상은 큐의 길이가 길어질수록 심해 진다.

 

최소 탐색 시간 우선 알고리즘은 선입 선처리 보다는 상당히 개선되었지만 최적의 방법은 아니다.

 

[SCAN 스케줄링(SCAN Scheduling)]

SCAN 알고리즘에서는 디스크 암(disk arm)이 디스크의 한 끝에서 시작하여 다른 끝으로 이동하며 가는 길에 있는 모든 요청을 처리 한다. 다른 한쪽 끝에 도달하면 역 방향으로 이동하면서 오는 길에 있는 요청을 처리 한다. 엘리베이터처럼 왕복하며 처리하므로 엘리베이터(elevator algorithm)이라고도 부른다.

 

 

[C-SCAN 스케줄링 (C-SCAN Scheduling)]

C-SCAN 스케줄링은 각 요청에 걸리는 시간을 좀 더 균등하게 하기 위한 SCAN의 변형이다. SCAN과 같이 C-SCAN은 한쪽 방향으로 헤드를 이동해 가면서 요청을 처리하지만 한쪽 끝에 다다르면 반대 방향으로 헤드를 이동하며 처리하는 것이 아니라 처음 시작했던 자리로 다시 되돌아가서 서비스를 시작한다. C-SCAN 스케줄링 알고리즘은 실린더들을 마지막 실린더가 처음 실린더와 맞닿은 원형 리스트로 간주 한다.

 

 

[LOOK 스케줄링 (LOOK Scheduling)]

SCAN나 C-SCAN 스케줄링은 헤드를 디스크의 끝에서 끝으로 이동한다는 점에 유의해야 한다. 그러나 실제로 이런 방식으로 구현하지는 않는다. 보통 헤드는 각 방향으로 가다가 그 방향에서 아무도 기다리는 요청이 없으면 헤드의 이동 방향을 즉시 반대로 바꾸면 된다. SCAN과 C-SCAN 스케줄링의 이런 변형을 한 방향으로 계속 움직이기 전에 요구가 있는지 확인(look for)하기 때문에 각각 LOOK, C-LOOK 스케줄링 이라 한다.

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사

[출처] 디스크 스케줄링(Disk Scheduling)|작성자 SungWook Kang