Disk Scheduling

Request Queue

• File System에서 짧은 시간 안에 수많은 Disk 접근 요청을 보내지만, Disk는 한 sector를 읽는 데 수 ms가 걸립니다.
  이 때 접근 요청을 저장해두지 않는다면, 그 요청들은 모두 무시됩니다.
  그 요청들을 저장해두는 곳이 Request Queue입니다.
• 요청들을 어떤 순서로 저장하느냐에 따라 Disk access time이 차이가 날 수 있습니다. --> Disk Scheduling

Disk Scheduling

• Seek time, Rotational time 최소화시키는게 목적

  • Seek time >>>> Rotational time 이기 때문에 Seek time을 줄이는 것이 효과적
  • Disk arm이 먼 거리로 이동하는 것을 최대한 줄여야 합니다.
  • 따라서 앞으로 나올 그래프에서, 파란색 점과 점 사이의 거리가 짧고, 지그재그의 횟수가 적을수록 효율적인 알고리즘이라고 할 수 있습니다.

• Scheduling Algorithm

  • FCFS
  • SSTF
  • SCAN
  • C-SCAN
  • LOOK
  • C-LOOK

FCFS (First-Come First-Service)

• 가장 효율이 떨어지는 알고리즘
• Request Queue에 있는 값은 Cylinder 번호
• Queue에 존재하는 값들을 아무 절차를 거치지 않고 하나씩 pop하여 Disk에서 검색합니다.
• 예시에서 98 - 183, 183 - 37 등 먼 거리를 움직이면, 그만큼 seek time이 증가하여 속도가 느려집니다.

SSTF (Shortest Seek-Time First)

• 현재 처리하고 있는 Cylinder 번호에서 가장 가까운 곳을 탐색하는 방법
• 먼 거리를 이동하진 않지만, 현재 처리중인 Cylinder 번호에 근접한 요청이 계속 들어온다면, 상대적으로 먼 거리에 있는 요청들은 Starvation이 발생
• 사용 X

SCAN (Elevator Algorithm)

• 실제 사용되는 알고리즘 중 하나
• arm head가 요청이 없을 때에도 계속 움직이다가, 요청한 Cylinder 번호에 도달하면 해당되는 요청을 처리합니다.
• 끝까지 움직이면, 반대 방향으로 움직여서 다시 요청을 처리합니다.
• 엘리베이터가 쭉 내려가면서, 버튼이 눌린 층에 멈춰서 사람을 태우고 다시 내려갑니다. 1층에 도달하면 사람을 모두 내려주고, 다시 위층으로 올라가게 되는데, 이 모습과 비슷하여 엘리베이터 알고리즘이라 불립니다.

C-SCAN (Circular-SCAN)

• SCAN과 기본 동작은 동일
• 끝까지 움직이면, arm head를 떼고 다시 처음 부분으로 가서 요청을 처리합니다.

LOOK (improved version of SCAN) & C-LOOK

• 위 그래프는 C-LOOK을 나타냅니다.
• SCAN, C-SCAN을 실제 Disk에서 구현할 때는 각각 LOOK, C-LOOK으로 구현하게 됩니다.
• SCAN, C-SCAN과 기본 동작은 동일
• head가 끝 부분까지 도달하는게 아닌, 요청에서 제일 작거나 큰 번호에 도달하면 각각의 동작에 맞게 다시 요청을 처리하는 방식입니다.