[운영체제] Disk Scheduling Algorithm

Disk Scheduling Algorithm

• Access time의 구성
  • Seek time
    • 헤드를 해당 실린더로 움직이는데 걸리는 시간
  • Rotational latency
    • 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간
  • Transfer time
    • 실제 데이터의 전송 시간

• Seek time을 최소화하는 것이 목표
• Seek time ~= seek distance

FCFS(First Come First Served)

SSTF(Shortest Seek Time First)

• 현재 섹터에서 가까운 섹터로 스케줄링

SCAN

• Disk arm이 디스크의 한쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리합니다.

• 다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동합니다.

• 문제점: 실린더 위치에 따라 대기 시간이 다릅니다.

C-SCAN

• 헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리

• 다른 쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동

• SCAN보다 균일한 대기 시간을 제공합니다.

Other Algorithms

• N-SCAN
  • SCAN의 변형 알고리즘
  • 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service
    • 대기 시간의 편차를 줄일 수 있음, 먼저 들어온 요청이 먼저 처리됨

• LOOK and C-LOCK
  • SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동
  • LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시 반대로 이동합니다.

Disk-Scheduling Algorithm의 결정

• SCAN, C-SCAN 및 그 응용 알고리즘은 LOOK, C-LOOK 등이 일반적으로 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있음

• File의 할당 방법에 따라 디스크 요청이 영향을 받음

• 디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직합니다.