본문 바로가기
IT 이론/운영체제

디스크 스케쥴링 알고리즘

by 지식id 2014. 10. 17.
반응형


Head Pointer = 53

Request : 98, 183, 37, 122, 14, 124, 65, 67

Range : 0 ~ 199


FCFS : First Come First Served

가장 먼저 들어온놈 부터 처리한다. 차례대로 차를 다 더하면 된다.

(98 - 53) + (183 - 93) + (183 - 37) + (122 - 37) + (37 -14) + (124 - 14) + (124 - 65) + (67 - 65)  = 640


SSTF : Shortest Seek Time First

가장 가까운놈 부터 처리한다. 바로 앞에서 처리한 값과 가장 가까운 값의 차를 모두 더한다.

(65 - 53) + (67 - 65) + ... + 생략. 답은 236


SCAN (Elevator Algorithm)

시작점에서 한 방향으로 끝까지 갔다가 되돌아 온다. *request가 없더라도 가장 마지막 0 까지 갔다가 되돌아 오는 것을 명심!

53 -> 37 -> 14 -> 0 -> 65 ... 이 순서대로 차를 구하면 답은 236


C-SCAN

시작점에서 한 방향으로 끝까지 갔다가 되돌아 와서 다시 출발한다. SCAN과의 차이점은 돌아오는 과정에서 거치는 request는 처리 하지 않는다는 것이다. 돌아와서 다시 출발한 후에 거치는 것만 처리한다. 

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37 순서대로 진행된다. 계산은 생략


LOOK

SCAN의 개선된 형태이다. 끝까지 갔다가 되돌아 오는데 0이나 199까지 가는게 아니라 끝 값 까지만 갔다가 되돌아 온다.

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 14 -> 37


에센바흐(Eschenbach)

부하가 큰 시스템을 위해 개발되었으며 담색 시간과 회전 지연 시간을 최적화 하기 위한 최초의 기법이다.

헤드는 C-SCAN처럼 움직이며 모든 실린더는 그 실린더에 요청이 있던 없던 간에 전체 트랙이 한 바퀴 회전할 동안에 서비스를 받는다.


SLTF : Shortest Latency Time First

섹터 큐잉(Sector Queuing)이라고도 불린다. 회전 시간을 최적화하기 위해 구현되었다. 디스크 대기 큐에 있는 여러 요청을 섹터 위치에 따라 재정렬하고, 가장 가까운 섹터를 먼저 서비스한다. 헤드의 이동이 거의 없는 고정 헤드 장치인 드럼과 같은 장치에서 사용된다.


*에센바흐와 SLTF는 실제로 이동거리를 구하는 문제로는 나오지 않는다. 개념을 묻는 문제가 나오니 어떤 특징이 있는지 외워 둘것.

반응형

댓글