[운영체제] 디스크 스케줄링

1. 디스크 스케줄링의 개요

- 디스크 스케줄링(Disk Scheduling)은 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우 데이터를 액세스하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법이다.

- 디스크 스케줄링은 일반적으로 탐색 시간을 최적화하기 위해 수행되며, 다음과 같은 목적을 갖고 있다.

- 처리량 최대화 : 일정 시간에 디스크 입출력 요구를 서비스 해주는 수를 최대화한다.

- 응답 시간의 최소화 : 어떤 요청이 있은 후 결과가 나올 때까지 걸리는 시간을 최소화한다.

- 응답 시간 편차의 최소화 : 각 요청의 응답 시간과 평균 응답 시간의 편차를 최소화한다.

- 디스크 스케줄링의 종류에는 FCFS, SSTF, SCAN, C-SCAN, N-step SCAN, 에센바흐, SLTF 스케줄링 기법이 있다.

2. FCFS(First Come First Service) = FIFO(First In First Out)

- FCFS는 가장 간단한 스케줄링으로, 디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 기법이다.

- 디스크 대기 큐에 있는 트랙 순서대로 디스크 헤드를 이동시킨다.

- 디스크 대기 큐에 들어온 순서대로 서비스하기 떄문에 더 높은 우선순위의 요청이 입력되어도 순서가 바뀌지 않아 공평성이 보장된다.

- 디스크 오버헤드가 적을 때 효율적이며, 프로그래밍이 쉽다.

- 헤드 이동 거리가 상당히 길어질 수 있다.

- 디스크 오버헤드가 커지면 응답 시간이 길어진다.

- 탐색 시간을 최적화하려는 시도가 없는 기법이다.

3. SSTF(Shortest Seek Time First)

- SSTF는 탐색 거리(Seek Distance)가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법이다.

- 현재 헤드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동시킨다.

- FCFS보다 처리량이 많고, 평균 탐색 시간이 짧다.

- 처리량이 많은 일괄 처리 시스템에 유용하다.

- 현재 서비스한 트랙에서 가장 가까운 트랙에 대한 서비스 요청이 계속 발생하는 경우, 먼 거리의 트랙(안쪽이나 바깥쪽)에 대한 서비스는 무한정 기다려야 하는 기아 상태가 발생할 수 있다.

- 응답 시간의 편차가 크기 때문에 대화형 시스템에는 부적합하다.

4. SCAN

- SCAN은 SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법이다.

- Denning이 개발한 것으로, 대부분의 디스크 스케줄링에서 기본 전략으로 이용된다.

- 현재 헤드의 위치에서 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스하고, 끝까지 이동한 후 역방향의 요청 사항을 서비스한다.

- 헤드가 안쪽과 바깥쪽을 왔다갔다 하면서 지나는 길에 있는 대기 요청뿐만 아니라 새로운 요청도 서비스하며, 현재의 진행 방향에 더 이상의 요청이 없을 때에만 이동 방향을 바꾼다.

- SSTF에서 발생하는 응답 시간의 편차를 줄일 수 있다.

- 오버헤드가 적을 경우 가장 효율적인 기법이다.

5. C-SCAN(Circular SCAN)

- C-SCAN은 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색 거리를 갖는 요청을 서비스하는 기법이다.

- 헤드는 트랙의 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 서비스하여 끝까지 이동한 후, 안쪽에 더 이상의 요청이 없으면 헤드는 가장 바깥쪽의 끝으로 이동한 후 다시 안쪽으로 이동하면서 요청을 서비스한다.

- 마치 처음과 마지막 트랙(Track)을 인접시킨 것과 같은 원형 형태로 Disk를 처리한다.

- 요청을 서비스하는 도중 새로운 요청 사항이 도착하면 다음 헤드가 진행할 떄 서비스 한다.

- 트랙의 안쪽과 바깥쪽의 요청에 대한 서비스가 공평하다.

6. N-SCAN(N-step SCAN)

- N-step SCAN은 SCAN 기법의 무한 대기 발생 가능성을 제거한 것으로, 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비스하고, 진행 도중 도착한 요청들은 한데 모아서 다음의 반대 방향 진행 때 서비스하는 기법이다.

- SSTF나 SCAN 기법보다 응답 시간의 편차가 적다.

- 특정 방향에 많은 수의 요청이 도착할 경우 반대 방향에서의 무한 지연 발생을 방지할 수 있다.

- 진행 도중 도착한 요청은 반대 방향 진행 시 서비스하기 위해 디스크 대기 큐에 저장한다.

7. 에션바흐(Eschenbach) 기법

- 에센바흐는 부하가 매우 큰 항공 예약 시스템을 위해 개발되었다.

- 탐색 시간과 회전 지연 시간을 최적화하기 위한 최초의 기법이다.

- 헤드는 C-SCAN처럼 움직이며 예외적으로 모든 실린더에는 그 실린더의 요청이 있던 없던 간에 전체 트랙이 한 바퀴 회전할 동안에 서비스를 받는다.

8. SLTF(Shortest Latency Time First)

- SLTF는 섹터 큐잉(Sector Queuing)이라고 하며, 회전 지연 시간의 최적화를 위해 구현된 기법이다.

- 디스크 대기 큐에 있는 여러 요청을 섹터 위치에 따라 재정렬하고, 가장 가까운 섹터를 먼저 서비스 한다.

- 헤드의 이동이 거의 없고 고정 헤드 장치인 드럼과 같은 장치에서 사용된다.