Disk Scheduling (디스크 스케줄링)

디스크 구조

https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/10_MassStorage.html

 

Taccess (디스크 접근시간) = Tseek (탐색 시간) + Trotation (회전 지연시간) + Ttransfer(전송 시간)

disk queue : 디스크에 오는 요청을 저장해두는 queue

 

> 디스크 스케줄링 알고리즘을 이용하여 시간을 감소시킴

 

---

Disk Scheduling Algorithm

FCFS ( First Come First Served ) 

disk queue에 요청이 들어온 순서대로 처리

https://www.geeksforgeeks.org/difference-between-fcfs-and-c-scan-disk-scheduling-algorithm/

장점 : 공평하게 요청을 처리할 수 있음, 단순한 알고리즘

단점 : 비효율적임 > 헤드가 움직이는 거리가 매우 커짐

 

SSTF ( Shortest Seek Time First )

탐색 시간이 가장 짧은 것을 선택함

 

https://www.geeksforgeeks.org/program-for-sstf-disk-scheduling-algorithm/

 

장점 : Seek Time이 적음, 처리량을 극대화할 수 있음

단점 : starvation(기아) 발생,, 최적의 알고리즘은 아님

 

▶ starvation (기아) 발생

disk queue에는 지속적으로 새로운 프로세스의 요청이 들어옴 → 헤드와 멀리 떨어져 있는 실런더는 끝내 수행하지 못하는 현상

 

SCAN (엘리베이터 기법)

지속적으로 디스크를 앞뒤로 검사하는 방법 > 진행방향에 있는 요청을 처리한 후 다시 반대 방향으로 진행하며 요청 처리

https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/

장점 : 기아 발생 가능성 제거, 응답 시간 편차 줄임

단점 : 양쪽 끝 트랙의 대기시간이 길어짐

C-Scan

Circular Scan : 한 방향으로 계속 움직이는 SCAN 방식
0부터 끝까지 처리한 후 다시 0으로 읽지 않고 빠르게 돌아와서 도는 방식

https://www.geeksforgeeks.org/c-scan-disk-scheduling-algorithm/

 

장점 : SCAN보다 시간 균등성이 좋음

단점 : 처리할 요청이 없어도 헤드가 끝까지 이동하는 것이 비효율적

* 중간에 들어오는 요청을 처리하지 않고 다시 0으로 돌아가서 돌 때 요청한것을 전부 처리함

 

Look 

실린더의 최소와 최대 범위에서만 움직이는 scan 알고리즘

https://www.geeksforgeeks.org/disk-scheduling-algorithms/?ref=gcse

장점 : 불필요한 헤드 이동시간 제거

단점 : 범위를 알기 위해 미리 큐를 검사 > 오버헤드 발생

 

C-Look

실린더의 최소와 최대 범위에서만 움직이는 C-Scan 알고리즘

https://www.geeksforgeeks.org/disk-scheduling-algorithms/?ref=gcse

장점 : 불필요한 헤드 이동시간 제거

단점 : 범위를 알기 위해 미리 큐를 검사 > 오버헤드 발생

 

RSS ( Random Scheduling )

스케줄링이 무작위 처리 시간, 무작위 마감일, 무작위 가중치 등 무작위 속성을 포함하는 경우에 사용됨

 

N-Step Scan

N개의 버퍼가 생성되어, 버퍼가 가득 차면 다음 요청 버퍼로 전송됨

장점 : 응답 시간의 편차가 적음, 기아 현상 방지 가능

 

SLTF ( Shortest Latency Time First )

실린더 내의 트랙에 대한 요청을 검사한 후 회전 지연 시간이 가장 짧은 요청부터 처리

 

 

reference

- computer systems (Bryant, Randal E.)

- https://www.geeksforgeeks.org/disk-scheduling-algorithms/?ref=gcse