디스크 스케쥴링(Disk scheduling) - FCFS,SSTF, SCAN

1. 디스크 스케쥴링

디스크 접근 시간은 Seek time + rotational delay + transfer time 의 합이다.

이때 다음 실린더를 탐색하는 시간(seek time)이 가장 오래 걸린다.

 

다중 프로그래밍 환경

다중 프로그래밍 환경에서 디스크 큐(disk queue)에는 많은 요청(request) 들이 쌓여있다. 프로세스들이 디스크로 계속해서 읽기, 쓰기 요청을 하기 때문이다.

이러한 요청들을 어떻게 처리해야 탐색시간을 줄일 수 있을까?

  　

2. 디스크 스케쥴링 알고리즘

1) FCFS Scheduling

FCFS는 First-Come First-Served의 약자로 먼저 들어온 요청을 먼저 처리하는 방법이다.

가장 단순하며 공정한 방법이다.

• 예제
• 200 cylinder disk, 0 ... 199
• Disk queue : 98 183 37 122 14 124 65 67
• Head is currently at cylinder 53
• Total head movement = 640 cylinders

FCFS 스케쥴링, 헤더의 움직임이 굉장히 비효율적임을 알 수 있다.

그림에서 보듯 FCFS는 단순하나, 요청온 순서대로 헤더가 움직이기에 굉장히 비효율적일 수 있다.

  　

2) SSTF Scheduling

SSTF은 Shortest-Seek-Time-First 의 약자이며, 헤더를 가능한 적게 움직일 수 있는 곳을 먼저 탐색하는 방법이다.

• 예제
• 200 cylinder disk, 0 ... 199
• Disk queue : 98 183 37 122 14 124 65 67
• Head is currently at cylinder 53
• Total head movement = 236 cylinders

SSTF 스케쥴링 방식은 2가지 문제점이 있다.

a. 기아(Starvation)

다중 프로그래밍 환경에서는 끊임없이 디스크 요청이 들어오는데, 당장 가장 가까운 요청만을 처리하면 계속해서 뒤로 밀리는 요청이 있기 마련이다. 그래서 결국 디스크 할당을 영영 받지 못하고 굶어죽는 현상이 발생한다.b. 가장 최적의 방법이 아니다.   　

3) SCAN Scheduling (=Elevator Algorithm)

스캔 알고리즘은 디스크 요청을 위아래로 훑듯이 양 끝점을 번갈아가며 읽는 방식이다.

• 예제
• 200 cylinder disk, 0 ... 199
• Disk queue : 98 183 37 122 14 124 65 67
• Head is currently at cylinder 53
• Total head movement = 53+183 cylinders

SCAN, C-SCAN 스케쥴링

4) SCAN Scheduling 변종들

a. C-SCAN

C-SCAN 에서 C는 Circular의 약자이다. 즉 한 끝 지점(14)을 찍으면, 그 즉시 바로 다른 끝지점(183)으로 넘어가 계속해서 한 방향으로만 탐색하는 방식을 말한다.

 

b. LOOK

LOOK 방식은 양 끝 지점을 찍는 대신 양 끝(0, 199)에 위치한 디스크 요청을 찍는 방식이다. 위의 그림에서 꼭 0과 199를 찍을 필요는 없다. 그래서 양 끝단인 14와 183만을 왔다갔다 하는 방식이다.

 

c. C-LOOK

C-LOOK 방식은 LOOK에서 한 끝에 위치한 디스크(14)를 찍으면 바로 다른 끝에 위치한 디스크(183)로 헤더가 넘어가는 방식이다.