[OS-13] 디스크 스케줄링

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

• 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우 데이터를 액세스 하기 위해
• 디스크 헤드가 움직이는 경로를 결정하는 기법

2. 목적

• 처리량의 최대화
• 응답 시간의 최소화
• 응답 시간 편차의 최소화

3. 디스크 스케줄링 시 발생하는 병목현상 제거 방법 

• 제어장치가 포화상태가 되면 해당 제어장치에 부착된 디스크의 수를 감소시킴
• 입출력 채널이 복잡하면 그 채널에 부착된 제어장치 중 몇 개를 다른 채널로 이동 입출력 채널이 복잡하면 채널을 추가

4. 디스크 스케줄링 기법

- FIFO(=FCFS)

• 디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 기법
• 디스크 대기 큐에 있는 트랙 순서대로 디스크 헤드를 이동
• 디스크 대기 큐에 들어온 순서대로 서비스를 하기 때문에 공평성이 보장됨

- FIFO 기법 적용 예

<현재 헤드의 위치가 50에 있고, 요청 대기 열에는 아래와 같은 순서로 들어 있다고 가정>

• 이동 순서: 50→100→180→40→120→0→130→70→80→150→200
• 헤드의 이동 거리: 790 (50+80+140+80+120+130+60+10+70+50)

---

- SSTF(Shortest Seek Time First) 

• 탐색 거리가 가장 짧은 트랙에 대한 요청이 먼저 서비스받는 기법
• 현재 헤드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동시킴
• 처리량이 많은 일괄 처리 시스템에 유용
• 현재 서비스한 트랙에서 가장 가까운 트랙에 대한 서비스 요청이 계속 발생하는 경우, 먼 거리의 트랙에 대한 서비스는 무한정 기다려야 하는 기아상태가 발생할 수 있음
• 응답 시간의 편차가 크기 때문에 대화형 시스템에는 부적합

- SSTF 기법 적용 예

<현재 헤드의 위치가 50에 있고 트랙 0번 방향으로 이동하며, 요청 대기열에는 아래와 같은 순서로 들어 있다고 가정>

• 이동 순서: 50→40→70→80→100→120→130→150→180→200→0
• 헤드의 총 이동거리: 370 (10+30+10+20+20+10+20+30+20+200)

---

- SCAN

• 현재 진행 중인 방향으로 가장 짧은 탐색 거리에 있는 요청을 먼저 서비스하는 기법
• 현재 헤드의 위치에서 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스하고, 끝까지 이동한 후 역방향으로 서비스함
• 헤드의 진행 방향에 있는 대기 요청뿐만 아니라 새로운 요청도 서비스하며, 현재의 진행 방향에 더 이상의 요청이 없을 때에만 이동 방향을 바꿈
• SSTF에서 발생하는 응답 시간의 편차를 줄임

- SCAN 기법 적용 예

<현재 헤드의 위치가 50에 있고 트랙 0번 방향으로 이동하며, 요청 대기 열에는 아래와 같은 순서로 들어 있다고 가정>

• 이동 순서: 50→40→0→70→80→100→120→130→150→180→200
• 헤드의 총 이동거리: 250 (10+40+70+10+20+20+10+20+30+20)

---

- C-SCAN 

• 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색 거리를 갖는 요청을 서비스하는 기법
• 헤드는 트랙의 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 서비스하여 끝까지 이동한 후, 안쪽에 더 이상의 요청이 없으면 헤드는 가장 바깥쪽의 끝으로 이동한 후 다시 안쪽으로 이동하면서 요청을 서비스함
• 요청을 서비스하는 도중 새로운 요청이 도착하면 다음 헤드가 진행할 때 서비스함
• 트랙의 안쪽과 바깥쪽의 요청에 대한 서비스가 공평함

C-SCAN 기법 적용 예

<현재 헤드의 위치가 50에 있고, 트랙 0번 방향으로 이동하며, 요청 대기 열에는 아래와 같은 순서로 들어 있다고 가정>

• 이동 순서: 50→40→0→200→180→150→130→120→100→80→70
• 총헤드의 이동 거리: 380 (10+40+200+20+30+20+10+20+20+10)

---

- N-step SCAN 

• SCAN 기법을 기초로 하며 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청에 대해서만 서비스하고 진행 도중 도착한 요청들은 반대 방향 진행 때 서비스하는 기법
• SSTF나 SCAN 기법보다 응답 시간의 편차가 적음
• 특정 방향에 많은 수의 요청이 도착할 경우 반대 방향에서의 무한 지연을 방지함

---

- Look

• SCAN 기법을 사용하되 진행 방향의 마지막 요청을 서비스한 후 그 방향의 끝으로 이동하는 것이 아니라 바로 역방향으로 진행하는 기법

---

- C-Look

• C-SCAN 기법을 사용하며 안쪽 방향의 모든 요청을 처리한 후 바깥쪽 맨 끝으로 이동하는 것이 아니라 가장 바깥쪽의 요청 트랙으로 이동한 후 진행하는 기법