운영체제 - 디스크 스케쥴링

< 운영체제 – 디스크 스케쥴링 >

 

# 디스크 스케쥴링 개념

   디스크 스케쥴링은 대기중인 요청들에 대해 서비스하는 순서를 어떻게 결정하는가에 따라

   디스크 시스템의 전체 성능이 달라지기 때문에 스케쥴링을 통해 성늘을 향상시키고자 수행되어진다.

   스케쥴링은 단위 시간당 처리량, 평균 응답시간, 응답 시간의 예측성 등이 기준이 되어진다.

   단위시간당처리량 - 단위시간 당의 처리량을 극대화 시켜야 한다.

   평균응답시간 – 통계 값과 평균값의 차이인 편차를 제곱하여 얻은 값들의 산술평균, 분산이 작으면 자료는

              평균값 주위에 모여 있게 되고 분산이크면 자료 가운데 평균값에서 멀리 떨어진 것이 많게 됨.

# 디스크 스케쥴링 종류

 

   1) FCFS (First Come Fist Servded)

      - 가장 간단한 스케쥴링 기법으로, 디스크 입출력 요청 대기 큐에 들어온 순서대로 서비스 한다.

        장점 : 모든 작업 공평성 유지, 알고리즘 간단

               프로그래밍이 쉽다. 대기큐에 들어온 순서대로 서비스하기 때문에 더 높은 우선순위의 요청이

               입력 되어도 순서가 바뀌지 않아 공평성이 보장된다.

        단점 : 대기 큐에 있는 요청들의 트랙위치에 대한 고려가 전혀 없음, 이동 헤드디스크 탐색시간이 많이

              걸리는 문제 발생.

              디스크 부하가 많음, 디스크 입출력 부하가 적은 경우에 적합한 기법임.

 

   2) SSTR ( Shortest SeekTime Fitst)

      - SSTF는 트랙위치를 정렬한 후 출발 위치에서 가장 입접한 트랙으로 이동하는 방식임.

       장점 : 해드이동거리 극소화(FIFO에 비해 짧은 탐색거리)

              평균 응답시간도 비교적 낮게 처리가능

              처리량 많은 경우 유용 (일괄처리)

       단점 : 응답시간 예측성 저하, 편차 큼(대화형 부적당)

             바깥쪽 트랙의 처리밀도가 낮아 기아상태 발생가능 (무기한연기현상)

 

   3) SCAN

      - SSTF 가 갖는 탐색시간의 편차를 해소하기 위한 방법으로, 디스크 해드가 맨 바깥쪽 가장 안쪽 트랙

       쪽으로 이동하면서 해당되는 트랙에 대한 요구를 차례대로 서비스 해주는 방식임.

       장점 : SSTF의 응답시간 차별대우, 큰 편차 해결 (예측성 저하해결)

             단위시간당 처리량/평균응답시간면에서 우수함.

       단점 : 가장 안쪽과 바깥쪽 차별대우

             요청밀도가 높은 경우 오랜시간 걸림

             요청이 균등할 때, 헤드가 방향을 바꾸어야 할 시점에서 다른 반대쪽 끝의 요청밀도 높아짐.

 

    4) C – SCAN ( CircularSCAN )

        - 헤드가 항상 바깥쪽실린더에서 안쪽 실린더로 이동하면서 가장 짦은 탐색 시간을 갖는 요청을 서비스

          하는 방법이다. 진행도중도착한 요청은 다음 수행 시 서비스응답시간의 편차가 매우 적고 회전 시간의

          최적화가 가능하며 오버헤드가 많이 걸리는 경우에 효과적임.

         장점 : 응답시간의 분산과 편차가 매우 작음

               회전시간 최적화 가능

               오버해드가 많이 걸리는 경우 효과적 (부하소: SCAN 효과적, 부하대: C-SCAN 효과적)

         단점 : 이동방향으로 마지막 실린더까지 이동

 

    5) SLTF (Shortest LatencyTime First) 스케쥴링

        - 디스크 헤드가 특정 실린더에 도착하면 도착한 순서에 관계 없이 대기 큐에 지정된 순서대로 서비스

         특징 : 최소지연시간 우선 스케쥴링

               디스크 시스템의 각 섹터별로 별도 큐 관리

               헤드 아래 먼저 도착하는 순서대로 각 섹터에 대해 서비스함.

         장점 : 거의 최적에 가까움

                대부분 시스템에서 필요한 경우 사용하는 기법

 

    6) N-Step SCAN

        - N-단계 SCAN에서는 어떤 방향의 진행이 시작될 당시 대기중이던 요청들만 서비스 한다.

         즉, 진행도중 도착한 요구들은 한데 모아져서 다음의 반대방향 진행 때 최적으로 서비스를 할수 있도록

         정렬한다.  (무한정 대기 가능성을 배제한다) 

         N-단계 SCAN은 처리량과 평균 응답시간에서 좋은 효율을 보이며, 응답시간의 편차가 작다.

 

    7) Eschnbach Scheme

        - 부하가 큰 항공 예약 시스템을 위해 개발된 방법으로 탐색시간뿐만 아니라 회전지연시간도

          최적화하려는 최초의 시도

          해드는 C-SCAN 처럼 움직이는데 예외로 모든 실린더는 그 실린더에 요청이 있든지 없든지간에

          전체 트랙이 한바퀴 동안의 서비스를 받음

 

# 디스크 스케쥴링 기법 간 특징 비교

 

종 류	처리 방법	특 징
FCFS	First Come First Serve 작업의 요청 순서대로 서비스 받음	구현이 용이, 공평한 서비스 트랙 탐색 패턴의 최적화 시도 없음 응답시간이 길어지는 경향
SSTF	Shortest Seek Time First 현재의 헤더 위치에서 탐색거리가 가장 짦은 요청이 먼저 처리됨	FCSC 보다 처리량 많고 응답시간이 짧아 진다. 응답시간 편차가 심화 가능성
SCAN	진행 방향상의 가장 가까운 곳에 있는 요청을 먼저 처리 실제 디스크 스케쥴링 기법의 근간	가장 바깥쪽 실린더에 도달할 때까지 진행방향을 바꾸지 않음. SSTF처럼 처리량과 응답시간을 많이 개선
C-SCAN	Circular SCAN 한쪽 방향으로만 해드를 이동하며 서비스함 끝에 도착하면 처음부터 진행	안쪽,바깥쪽 트랙의 차별대우 완전제거 응답시간의 편차적고, 회전시간의 최적화 가능
N-STEP SCAN	SCAN 알고리즘에서 방향 전환시 먼저 요구한 N개의 요청만 처리	헤더가 있는 실린더에 요청이 집중될 때에 발생하는 무한대기를 제거
LOOK	SCAN을 개선 해드가 끝까지 도착하지 않아도 앞쪽에 요청이 없으면 해드 방향 전환