[운영체제] 11. 디스크 관리 : 디스크 스케줄링 (Disk Management & Scheduling 1, 2)

1. Disk Scheduling Algorithm

디스크 스케줄링 알고리즘은 디스크에 대한 외부 요청을 효율적으로 처리하기 위해 사용됩니다.

 

스케줄링 알고리즘이 구현되는 곳은 디스크 내부가 아니기 때문에, 대부분 스케줄러는 디스크의 정확한 위치를 알지 못합니다. 그래서 섹터와 매핑된 논리 블록 번호를 기반으로 스케줄링을 하게 됩니다. 실제 구현에서는 자주 사용되는 방법은 아니지만 이해를 돕기 위해서, 이번 포스팅에서는 각각의 알고리즘을 실린더 번호를 예시로 살펴보겠습니다.

 

 

(1) FCFS (First Come First Serve)

FCFS disk scheduling

이 알고리즘은 먼저 도착한 순서대로 요청을 처리합니다. 이로 인해 헤드의 이동거리가 길어져 비효율적일 수 있습니다.

 

 

(2) SSTF (Shortest Seek Time First)

 현재 헤드 위치에서 가장 가까운 요청을 먼저 처리합니다.

 

 이렇게 함으로써 헤드의 이동거리를 줄일 수 있지만, starvation 문제가 발생할 수 있습니다. Queue에 가까운 위치의 요청들이 계속해서 들어오면 먼 위치의 요청을 처리하지 못할 수 있기 때문입니다.

 

 

(3) SCAN

SCAN disk scheduling

 엘리베이터 스케줄링이라고도 불리는 SCAN 방식은 헤드가 한 방향으로 이동하면서 요청을 처리합니다. 바깥에서 안쪽으로 이동하면서 요청을 처리한 후, 반대 방향으로 이동하면서 다시 요청을 처리합니다. 

 

 이 방식은 한 방향으로 이동하기 때문에 Starvation 문제도 발생하지 않고, 효율적인 디스크 헤드 이동거리를 가집니다. 

 

 하지만 위치에 따라 대기 시간이 다를 수 있습니다. 예를 들어 가운데 부분은 기다리는 시간의 기대 시간이 짧습니다. 디스크 헤드가 지나간 뒤에 요청을 늦게 했더라도, 끝에 위치한 부분에 비해서 디스크 헤드가 다시 돌아오는 길이가 짧기 때문입니다.

 

 

 

(4) C-SCAN (Circular Scan)

C-SCAN disk scheduling

 SCAN의 변형 알고리즘으로, SCAN에서의 문제인 대기 시간의 편차를 줄이기 위한 방법입니다. 헤드가 끝에 도달했을 때 반대 방향으로 돌아가지 않고 다시 시작점으로 이동합니다. 이를 통해 대기 시간의 균일성을 높입니다.

 

(5) LOOK

SCAN과 유사하지만, 헤드가 끝에 도달했을 때 바로 반대 방향으로 돌아가지 않고 대기 중인 요청이 없을 때에만 반대 방향으로 이동합니다.

 

(6) C-LOOK

C-SCAN과 유사하지만, 헤드가 끝에 도달했을 때 반대 방향으로 돌아가지 않고 대기 중인 요청이 없을 때에만 반대 방향으로 이동합니다.

 

 

 

 

 

2. Disk - Scheduling 알고리즘의 결정

 일반적으로 디스크 입출력이 많은 시스템에서 SCAN에 기반한 알고리즘을 많이 사용하고 있습니다. 주로 디스크 헤드의 이동거리를 줄이는 것에 초점을 두는 것이 효율적이기 때문입니다.

 

 파일의 할당 방법도 디스크 요청에 영향을 미칩니다. 연속 할당 방식을 사용하면 디스크 헤드가 이동하는 거리를 줄일 수 있어 스케줄링 알고리즘의 성능을 향상시킬 수 있습니다. 반면에 불연속 할당 방식을 사용하면 디스크 헤드가 더 많은 이동을 해야 하므로 성능이 저하될 수 있습니다.

 

 그래서 디스크 스케줄링 알고리즘을 결정할 때에는 디스크 헤드의 이동거리를 최소화하는 것과 파일 할당 방법을 고려해야 합니다.

 

 

 

 

 

참고자료

[KOCW 이화여대 반효경 교수님 - File Systems Implementation 2]

https://core.ewha.ac.kr/publicview/C0101020140523142954456205?vmode=f

반효경 [운영체제] 26. File System Implementations 2

 

[ Operating System Concepts - Abraham Silberschatz ]

https://www.yes24.com/Product/Goods/89496122

운영체제 - 예스24