디스크 스케줄링

처리기와 주기억장치의 속도가 빨라지면서 디스크의 성능을 향상시키는 기법에 관한 고찰

디스크 성능 매개변수

탐색 시간(seek time)

디스크 암을 필요한 트랙으로 이동시키는데 걸리는 시간
약 10ms

회전 지연(rotational delay)

지정된 디스크의 주소 영역이 입출력 헤드에 의해 접근 가능한 위치까지 회전하여 도달하는데 걸리는 시간
약 2ms(15,000 rpm의 경우)

접근 시간(access time)

데이터를 읽거나 쓰기 위한 위치에 도달하는데 걸리는 시간
탐색 시간 + 회전지연시간

전송 시간(transfer time)

데이터를 디스크로 보내거나 받을 때 걸리는 전송 시간

전체 시간 계산 예시

• 회전속도 7500rpm, 트랙당 512 바이트 섹터 500개
• 2500 섹터로 구성된 1.28MB 파일 읽기(5트랙 * 500섹터/트랙)
• 순차탐색의 경우
  - 16(처음 섹터까지 도달 + 읽기) + 4(나머지 트랙) * 12(한 섹터를 읽는데 걸리는 회전지연 4 + 500섹터 읽기 8) = 64ms = 0.064초
• 무작위 탐색의 경우
  - 2500(각 섹터) * 8,016(한 섹터를 읽는데 걸리는 시간) = 20040ms = 20.04초
  => 섹터들이 디스크로부터 읽혀지는 순서는 입출력 성능에 큰 영향

디스크 스케줄링 정책

* 횡단트랙: 해당 트랙까지 움직인 거리

FIFO(First-In-First-Out)

• 선입선출 방식으로 순서대로 처리하기 때문에 공정함.
• Clustered된 파일 섹터 접근하면 효율이 좋지만 아닌 경우 구림

SSTF(우선순위 기반)

• 빨리 처리할 수 있는 거부터 처리하는 방식
• 빨리 처리하는 것만 하다가 기아 발생할 수 있음

LIFO(Last In First Out)

• 지역성을 이용하면 작업 처리량을 증가시키고 큐의 길이를 줄일 수 있음
• 디스크가 큰 작업 부하 때문에 계속해서 바쁜 상태면 기아 발생 가능성이 있음

SSTF(Shortest Service Time First)

• 현재 위치에서 디스크 헤드의 움직임을 최소로 하는 디스크 입출력 요청을 선택
• FIFO보다 더 나은 성능

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

• 엘리베이터처럼 이동 방향의 마지막 트랙에 도달하거나 그 방향으로 남아 있는 요청이 없을 때까지 한 방향으로 이동
• 끝까지 가면 방향 바꾼다음에 반대 방향으로 모두 스캔
• SSTF와 비슷하지만 지역성을 활용하지는 않음
• 가장 안쪽 트랙과 가장 바깥쪽 트랙에 가까운 트랙들에 대한 요청을 한 작업을 선호
  - C-SCAN으로 해결
• 가장 최근에 도착한 작업을 선호
  - N-step-SCAN으로 해결

C-SCAN

• 한 방향으로만 가다가 방향 바꿔서 들리지 않고 한번에 돌아가고 다시 똑같은 방향으로 스캔 반복
• 새로운 요청들이 겪게 되는 최대 지연 감소

N-step-SCAN과 FSCAN

• 디스크 요청 큐를 세그먼트로 분할하고 한 번에 한 단편에 속한 요청 전부를 처리
• N-step-SCAN
  - 디스크 요청 큐를 길이가 N인 하위 큐들로 분할
  - SCAN을 이용해서 하위 큐 처
• FSCAN
  - 두 개의 하위 큐 이용(모든 요청들을 담은 큐 + 빈 큐)
  - 스캔하면서 새로운 모든 요청들은 다른 비어있는 큐로 들어가서 원래 요청들이 완료될 때까지 대기

디스크 스케줄링 알고리즘 비교