<운영체제> Disk Scheduling - FCFS, SSTF, SCAN, C-SCAN
본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨
Disk Scheduling이란?
- OS의 목표 중 하나인 디스크-드라이버로의 효율적인 접근을 위해서, OS는 빠른 접근 시간과 높은 전송량을 제공해야한다.
- 디스크로의 접근 시간에는 Seek-Time과 Lotational-Latency가 있으며, Seek-Time은 디스크 암이 헤드를 원하는 실린더로 움직이는데 소요된 시간이고, Lotational-Latency는 디스크 헤더가 원하는 섹터에 도달하기까지 걸리는 회전 소요 시간이다.
- 높은 전송량은 Disk-Bandwidth와 관련이 깊으며, 이는 Disk Scheduling으로는 직접적으로 향상 시키긴 어렵다.
- 결국 Disk Scheduling은 Seek-Time과 Lotational-Latency를 어떻게 줄여서 디스크에 존재하는 데이터에 접근하는가에 대한 정책이다.
Disk Access 구조
Moving-head Disk Mechanism
FCFC란?
- CPU 스케쥴러에서의 정책과 동일한 알고리즘을 가진다.즉, 요청이 들어온 순서대로 디스크에 접근하여 요청을 처리하는 방식이다.
- 공정하고, 순서대로 진행해서 overhead가 낮다는 장점이 있지만, throughput 을 극도로 낮출수 있어서 상당히 비효율적인 알고리즘이다.(오래 걸리는 요청이 앞 쪽에 많으면, 처리량이 굉장히 낮아짐)
- Seek-Time을 줄이기 위한 정책이다.
FCFC 이미지
SSTF란?
- Shortest Seek Time First의 약자로써 CPU 스케쥴러의 SJF와 동일한 형태의 알고리즘이라 봐도 무방하다.
- 현제 헤드의 위치 기준으로 가장 가까이 있는 디스크로의 요청을 수행한다. 즉 seek-Time 이 짧은 요청을 먼저 수행하는 정책이다.
- Throughput을 극대화 시킬 수 있는 장점이 있어 Batch processing systems에 알맞은 정책이다.
- 하지만, 특정한 조건의 요청이 계속 무시될 수 있는 starvation이 발생 가능성이 있고, 이는 공정하지 못한 알고리즘이라 볼 수 있다. 그래서 interactive system에는 알맞지 않은 정책이다.
SSTF 이미지
SCAN이란?
- Elevator algorithm이라는 별명이 있으며, 우리가 이용하는 엘리베이터 처럼 작동하는 방식이다.
- 현재 헤더의 위치를 기준으로 오른쪽/왼쪽으로 하나의 방향을 잡고 최대값/최소값까지 헤더를 이동시키면서 해당 경로에 있는 요청들을 요청이 들어온 시간에 상관없이 처리해나가는 방식이다.
- 만약 헤더가 경로를 이동하는 중에 요청이 들어오면, 해당 요청이 해당 경로에 있는 경우에는 요청을 처리해준다. 아래 그림에서는 시작 헤더위치에서 왼쪽으로 시작하고 나서 4위치의 작업이 들어오면 가는 경로에 4가 있으므로 처리해준다.
- 위와 같은 특성은 가까운 경로의 요청은 바로바로 처리해준다는 장점도 있지만, 반대쪽의 요청들은 response-time 증가되거나 starvation이 일어 날 수 있는 단점도 있다.
SCAN 이미지
C-SCAN이란?
- Circular-Scan의 약자이다.
- SCAN의 Response-Time 문제를 보완한 정책으로써, 오른쪽/왼쪽 방향을 설정후, 해당 방향으로 들어온 시간에 관계없이 요청을 처리해주다가 end-point에 도달하면,반대쪽의 end-point로 디스크 헤더를 옮긴 후,설정한 방향으로 들어온 요청들을 처리해준다.
- Endpoit에서 endpoint로 이동 시에는 요청을 처리하지 않는다. 아래 그림에서는 빨간색 경로로 디스크 헤더가 이동 할때는 작업 요청을 받아들이지 않는다.
C-SCAN 이미지
