본문 바로가기
My Image
전공지식/OS

[운영체제] 디스크 스케줄링이란?(Disk Scheduling)

by Lim-Ky 2018. 11. 5.
반응형





디스크 스케줄링이란?(Disk Scheduling)


일반적으로 컴퓨터는 데이터를 저장할때, 순차적으로 하드웨어 디스크에 저장하지 않는다. 그때 그때 필요에 따라 상황에 맞게! 데이터를 저장하기 때문에 데이터를 찾기 위해선, 산재되서 저장된 데이터를 찾아와야 한다. 이때, 어떻게 효율적으로 산재된 데이터를 액세스 할 것인가에 대한 고민과 방법을 디스크 스케줄링이라 한다. 


디스크 스케줄링 목표


디스크 스케줄링은 디스크 스케줄러가 실행한다. 디스크 스케줄러는 몇가지 목표를 가지고 데이터를 액세스한다.


1. 하드 디스크 검색으로 낭비되는 시간을 최소화 

2. 특정한 프로세스의 입출력 요청의 우선순위를 정함

3. 디스크 대역을 실행중인 각 프로세스에 할당

4. 정해진 기한까지 요청을 처리


디스크 스케줄링 종류


그럼 대표적인...디스크 스케줄링은 뭐가 있을까..?


  1. FCFS 스케줄링(First Come First Served) : 요청이 들어온 순서대로 처리한다.
  2. SSTF 스케줄링(Shortest Seek Time First) : 현재 디스크의 헤드 위치에서 가장 가까운 실린더에 대한 요청을 우선적으로 처리한다.
  3. SCAN 스케줄링 : 디스크의 한 쪽 끝에서 반대쪽 끝으로 이동하면서 처리하며, 마지막 실린더에 도착하면 반대 방향으로 스캔을 진행한다.
  4. C-SCAN 스케줄링 : 디스크의 한 쪽 끝에서 반대쪽 끝으로 이동하면서 처리하며, 마지막 실린더에 도착하면 시작점으로 되돌아간 후 다시 스캔을 진행한다.
  5. C-LOOK 스케줄링 : C-SCAN에서는 양 끝까지 이동하던 것을 요청된 실린더 중 마지막까지만 이동하는 방식으로 처리한다.
  6. N단계 SCAN 스케줄링 : SCAN 스케줄링과 같이 진행 방향 상의 요청을 서비스하지만 진행 중에 새로이 추가된 요청은 서비스하지 않고 다음 진행 시에 서비스하는 기법이다.
  7. 에센바흐 기법(Eschenbach scheme) : 탐색 시간 최적화뿐만 아니라 회전 지연 시간도 최적화하고자 하는 최초의 기법이다.(항공 예약시스템을 위해 개발됨)
  8. SLTF 스케줄링(Shortest Latency Time First) : 회전 지연 시간 최적화를 위한 대표적 알고리즘으로 디스크 헤드가 특정 실린더에 도착하면 그 실린더 내의 여러 트랙에 대한 요청들을 검사한 후 회전 지연 시간이 가장 짧은 요청부터 서비스하는 기법이다.

등등...


오늘은 FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK 에 대해서 알아보자.


1) FCFS(First Come First Served)


First Come First Served 즉, 큐에 가장먼저 요청이 온 순서대로 서비스한다.

장점 : 알고리즘이 다른 기법보다 단순하며, 공평하게 요청을 처리한다.

단점 : 비용이 많이 발생되어, 비효율적임...


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

current head starts at : 53




큐에서 요청오는 순서대로 처리하는 것을 알 수 있다. 만약 요청이 온것들 중 가장 차이가 큰 데이터들이 연속으로 요청이 들어올때, 극단적으로 양쪽을 왔다 갔다 하기 때문에 비효율적이다... 그림만 봐도 비효율적으로 보인다. 이동거리가 640이나 된다...



2) SSTF(Shortest Seek Time First)


현재 헤드에서 가장 가까운 트랙의 요청을 먼저 처리한다. 즉 현재 헤드셋을 처리하고, 다음 요청 중에 이동거리가 가장 적은거리에 있는 트랙을 처리한다.


장점 : Seek Time 이 적다. 즉 트랙을 찾는 시간을 최소화 할 수 있고, 처리량(Throughput)을 극대화 할 수 있다.

단점 : 안쪽 및 바깥쪽에 있는 요청들은 기아 현상이 발생할 수 있다. 도한, 응답 시간 편차가 크다.


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

current head starts at : 53




헤드셋이 53부터 시작해서 다음 요청중 가장 가까운 65를 처리하고 그다음 67을 처리한다. 이렇게 가까운 요청부터 처리를 하다보니 seek time은 적을 수 있으나, 바깥쪽에 있는 요청들은 기아상태가 될 수 있다.



3) SCAN


헤드셋의 진행방향에 있는 요청을 처리하고, 다시 반대 방향으로 틀어 반대방향에 있는 요청들을 처리한다. 마치 엘레베이터가 동작하는 원리가 같아서 엘레베이터 기법이라고도 한다. 


장점 : SSTF의 바깥쪽 트랙의 기아가능성을 제거할 수 있고, 응답시간의 편차를 줄일 수 있다.

단점 : 양 쪽 끝 트랙 가운데 위치한 트랙보다 대기 시간이 길어진다. 엘레베이터로 비유하자면, 맨 꼭대기 층이 중간층보다 응답시간이 늦어질 수 있다는 뜻.





헤드셋이 0 쪽인 방향으로 진행하고 있었기 때문에, 0 방향 상에 있는 트랙들을 먼저 처리한다. 헤드셋은 0 까지 도달하고 나서야 반대방향인 199로 향하며 반대방향 상에 있는 트랙들을 처리한다. 여기서 주목할 것은 20, 23, 30, 43 이다. 이미 요청이 들어온 것이 아니라, 이후에 치고 들어와도 가는 방향에 아직 지나치지 않고 있다면 요청을 처리한다. 



4) C-SCAN


항상 한쪽 방향에서 반대방향으로 진행하며 트랙의 요청을 처리한다. 즉 바깥쪽에서 안쪽으로 진행하며 요청을 처리한다. SCAN의 변형된 형태로 조금더 시간을 균등하게 배분할 수 있다.


장점 : 응답시간의 편차가 매우 적음, SCAN보다 시간균등성이 좋음

단점 : 안쪽이나, 바깥쪽으로 처리할 요청이 없어도 헤드셋이 끝까지 이동하기 때문에 비효율적




53 헤드셋이 0방향으로 시작하며 0 방향상에 있는 요청을 처리하고 0에 도달한다. SCAN은 0에 도착하면 반대방향으로 방향을 틀었겠지만, C-SCAN은 다시 199 지점으로가서 같은 방향인 0 방향으로 다시 트랙을 처리한다. 여기서 주목할 것은 SCAN과 다르게 중간에 치고들어오는 요청이 있어도 요청을 처리하지 않고 큐에 모았다가 일전에 요청한 것들을 다 처리한 후 처리한다.



5) LOOK, C-LOOK


LOOK 과 C-LOOK 은 SCAN과 C-SCAN을 보완하기 위한 스케쥴링 기법이다. SCAN과 C-SCAN의 비효율적인 부분은 위에 눈치채셨겠지만, 끝단에 요청이 없어도 끝단까지 도달하고야만다는 것이다. 따라서 요청이 진행방향에서 더이상 없다면, 끝단까지 가지않고 반대방향으로 가던가(SCAN), 다시 같은 같은 방향으로 진행(C-SAN)하게 한다.


장점 : 불필요한 헤드 이동시간을 제거

단점 : 끝단까지 가야할지 말아야할지 판단하는데 있어서 오버헤드 발생


LOOK (SCAN을 변형)



C-LOOK (C-SCAN을 변형)





6) N-STEP SCAN 



N-STEP-SCAN 방법은 SCAN 기법을 기초로 두고 있으며, 시작하기 전 대기하고 있는 요청들을 우선적으로 처리하고, 처리하는 과정 중에 요청이 들어오는 것들은 이후에 모아서, 반대방향으로 진행할 때 서비스한다.


장점 : SSTF, SCAN 보다 응답시간의 편차가 적음, 특정 방향에서의 많은 요청으로 인해 반대방향에 들어온 요청들에 대해 기아현상을 방지할 수 있음



7) 에션바흐(Eschenbach)기법


에션바흐 기업은 부하가 큰 항공시스템을 위해 개발되었고, 탐색시간 및 회전지연시간도 최적화 할 수 있는 기법이다. 



8) SLTF(Shortest Latency Time Fisrt) 기법


회전 지연 시간을 최적화 하기 위한 대표적인 기법이며, 디스크 헤드가 틀정 실린더에 도착하면 그 실더 내의 여러 트랙에 대한 요청을 검사한 후 회전 지연시간이 가장 짧은 요청부터 서비스 하는 기법

헤드의 이동이 거의 없어, 고정 헤드 장치인 드럼에 사용




참고 : http://www.jidum.com/jidums/view.do?jidumKindCd=Oh











반응형

댓글