[OS] 디스크 스케줄링 알고리즘 개념 및 종류 (FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK)

 디스크 스케줄링 알고리즘에 대해 알아봅니다. 디스크 스케줄링 알고리즘에는 FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK이 있습니다. 각 종류별 스케줄링 방식도 살펴봅니다.

 

[ Contents ]

 

 

1. 디스크 스케줄링 알고리즘

디스크 I/O 요청을 어떤 순서로 처리할지 결정하는 방식

 

 디스크 스케줄링 알고리즘은 디스크 입출력을 효율적으로 처리하기 위해, 탐색 시간(Seek Time)을 최소화하는 게 핵심 목표입니다.

 CPU 스케쥴링과 달리, 디스크는 물리적으로 헤드가 옮겨다니며 데이터를 읽어야 하므로 조금 차이가 있습니다.

 

2023.07.21 - [CS/OS] - [OS] CPU 스케줄링 기법: FCFS, SJF, SRT, 라운드 로빈, Multi Level (Feedback) Queue

[OS] CPU 스케줄링 기법: FCFS, SJF, SRT, 라운드 로빈, Multi Level (Feedback) Queue

 

 

 

2. 디스크 알고리즘 종류

1) FCFS (First Come First Served)

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

 

 선착순 알고리즘으로, 구현이 가장 단순하지만 헤드가 디스크 양 끝을 왔다갔다 하며 탐색시간이 길어질 수 있습니다.

 

 

2) SSTF (Shortest Seek Time First)

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

 

 평균 탐색 시간은 줄어들지만, 헤드에서 멀리 있는 요청이 계속 밀려나는 기아(Starvation) 문제가 발생할 수 있습니다.

 

 

3) SCAN (엘리베이터 알고리즘)

헤드가 한 방향으로 끝까지 이동하면서 요청을 처리하고, 끝에 도달하면 반대 방향으로 되돌아옴

 

 엘리베이터처럼 양끝을 순회하며 요청을 처리합니다. 기아문제는 발생하지 않지만, 양 끝 트랙의 요청은 상대적으로 대기 시간이 길어질 수 있습니다.

 

 

4) C-SCAN (Circular SCAN)

한 방향으로만 요청을 처리하며, 끝에 도달하면 반대쪽 끝으로 즉시 이동한 후 같은 방향으로 다시 처리

 

 SCAN과 유사하지만, 한 방향으로만 요청을 처리합니다. 그 때문에 SCAN보다 대기 시간의 균등성이 높아집니다.

 

 

5) LOOK

디스크 끝까지 가지 않고 해당 방향의 마지막 요청까지만 이동한 후 뒷 방향으로 이동

 

 SCAN의 개선형으로 불필요한 헤드 이동을 줄여줍니다.

 

 

6) C-LOOK

한 방향의 마지막 요청까지만 이동한 후, 반대쪽 첫 번째 요청 위치로 이동

 

 C-SCAN의 개선형으로, 마찬가지로 불필요한 헤드 이동을 줄여줍니다.

---

 

 

반응형

3. 알고리즘 효율순서

FCFS < SSTF < SCAN < C-SCAN < LOOK < C-LOOK