[운영체제-양희재 교수님]30-31강 디스크 스케줄링

경성대학교 양희재 교수님의 운영체제 30강

경성대학교 양희재 교수님의 운영체제 31강

디스크 스케줄링(Disk Scheduling)

• 디스크 접근 시간 = Seek time + rotational delay + transfer time
  • 탐색 시간(seek time)이 가장 크다.
• 다중 프로그래밍 환경
  • 디스크 큐(disk queue)에는 디스크를 사용하려는 요청(request)이 쌓임
  • 탐색 시간을 최대한 줄일 수 있는 스케줄링 방법 필요

FCFS(First-Come First-Served) Scheduling

• 디스크 큐에 먼저 온 순서대로 처리
• Simple and fair
• 예제
  • 200개의 cylinder disk(0 ~ 199)
  • Disk queue: 98 183 37 122 14 124 65 67
  • Head is currently at cylinder 53
  • Total head movement = 640 cylinders
• 단점
  • 헤드의 이동 거리가 늘어나서 비효율적

SSTF(Shortest-Seek-Time-First) Scheduling

• Select the request with the minimum seek time from the current head position
  • 헤드를 최대한 적게 움직이도록 스케줄링
• 예제
  • 200개의 cylinder disk(0 ~ 199)
  • Disk queue: 98 183 37 122 14 124 65 67
  • Head is currently at cylinder 53
  • Total head movement = 236 cylinders
• 단점
  • 헤드에서 멀리 떨어져 있는 경우 ⇒ Starvation
  • 최적의 방법은 아님

SCAN Scheduling

• Scan disk: The head continuously scans back and forth across the disk
  • 디스크의 안쪽 → 바깥쪽 → 안쪽 → 바깥쪽 → … 계속 스캔
• 예제
  • 200개의 cylinder disk(0 ~ 199)
  • Disk queue: 98 183 37 122 14 124 65 67
  • Head is currently at cylinder 53 (moving toward 0)
  • Total head movement = 53+183 cylinders (less time)
• Circular SCAN(C-SCAN)
  • 가정) a uniform distribution of requests for cylinders
  • 안쪽으로 스캔 → 다시 바깥쪽으로 스캔 → 다시 안쪽으로 스캔하면 왔던 길을 다시 되돌아가는 경우 발생 ⇒ Circular SCAN is necessary
    • 안쪽으로 스캔 → 바깥쪽으로 이동 → 안쪽으로 스캔

SCAN Variants

• C-SCAN
  • Treats the cylinders as a cicular list that wraps around from the final cylinder to the first one
• LOOK
  • The head goes only as far as the final request in each direction
    • 매번 0까지 안쪽으로 스캔할 필요 없다.
  • Look for a request before continuing to move in a given direction
    • 어디까지 스캔할지 미리 살펴본다(look).
• C-LOOK
  • LOOK version of C-SCAN
  • 미리 살펴본 뒤 가장 안쪽, 가장 바깥쪽으로 가지 않고 가장 외곽에 있는 요청까지만 스캔한다.

Elevator Algorithm

• 엘리베이터와 행동 양상이 비슷한 알고리즘
• The head behaves just like an elevator in a building, first servicing all the requests going up, and then reversing to service requests the other way