[운영체제] 120601 03.디스크 스케줄링

* 디스크 스케줄링 전략
  1. 입출력장치(디스크 드라이버) 는 요청(Request)을 위한 큐를 가짐
   1) 프로세스는 입출력이 필요할 때마다 운영체제에 시스템 호출을 보냄
   2) 요청은 다음과 같은 정보를 포함
    (1) 입력/출력 구분 정보
    (2) 디스크 주소
    (3) 메모리 주소
    (4) 전송할 정보의 총량(바이트 또는 word 수)

  3) 디스크 드라이버와 제어기를 사용할 수 있다면 요청을 즉시 처리 가능
  4) 다른 프로세스가 둘 주 ㅇ하나라도 사용하고 있다면 요청은 디스크 대기 큐에 저장
  5) 디스크 대기 큐에서 시스템의 스케줄링은 아래 몇가지 기준으로 평가 가능
   (1) 처리량 단위
   (2) 탐색 시간
   (3) 평균반응시간
   (4) 반응 시간 변화
% 스케줄링 정책은 처리량을 최대화하고 평균반응시간과 탐색시간을 최소화해야 함
% 처리량 및 평균반응시간 최적화로 시스템 성능 향상은 가능하나 개별 요쳥에 지연 발생 가능


* 선입 선처리 스케줄링(FCFS, First Come First Served)
 1. 디스크 스케줄링의 가장 간단한 형태
  1) 요청이 도착한 순서에 따라 처리
  2) 프로그램하기 쉽고 어떤 요청도 무기한 연기되는 경우가 없으며 본질적으로 공평성이 유지됨
  3) 문제점 - 디스크 요청이 흩어져 있는 경우 실행시간 오버헤드는 적으나 탐색시간이 오래 걸려 처리량 감소


* 최소 탐색시간 우선 스케줄링(SSTF, Shortest Seek Time First)
 1. 최소 위치결정 시간 우선(SPTF, Shortest Positioning TIme First) 알고리즘이라고도함
  1) 디스크 요청을 처리하기 위해서 헤드가 먼 곳까지 이동하기 전에 현재 헤드 위치에 가까운 모든 요구를 먼저 처리하는 방법
  2) 디스크 처리시간을 실질적으로 줄일 수 있으나, 디스크 요구의 기아상태 발생 가능
% 배치 처리 시스템의 경우 괜찮지만 대화식 처리 시스템의 경우 기아상태 발새 가능


* 스캔(SCAN) 스케줄링
 1. 요청 큐의 동적 특성 반영
  (1) 입출력 헤드가 디스크의 한 끝에서 다른 끝으로 이동
  (2) 한쪽 끝에 도달했을 때는 역방향으로 이동하면서 요청한 트랙을 처리.
  (3) 엘리베이터와 동작이 유사하여 엘리베이터 알고리즘이라 부르며, 눈 치우기와 비슷함. - 밀도가 높은 쪽의 요청은 오랜 시간 기다리게 됨


* 순환 스캔 스케줄링(C-SCAN, Circular SCAN scheduling)
 1. 스캔 알고리즘을 변형, 대기시간을 균등하게
  1) 스캔 스케줄링처럼 헤드는 한쪽 방향으로 이동하면서 요청을 처리하지만, 한쪽 끝에 다다르면 반대 방향으로 헤드가 이동하지 않고 다시 처음부터 요청을 처리
  2) 처음과 마지막 트랙을 서로 인접시킨 것과 같은 원형처럼 디스크르 처리, 처리량 향상
  3) 바깥 트랙과 안쪽 트랙에 대한 차별이 없어 반응시간의 변화를 줄임
  4) 동일한 실린더(트랙)에 대한 요청이 연속적으로 발생되면 처리가 무기한 연기될 수 있음


* 룩(Look) 스케줄링
 1. 스캔 또는 순환 스캔 방법은 원리와 달리 구현됨
  1)  헤드는 요청에 따라 각 방향으로 이동, 현재 방향에 더이상 요청이 없을때 이동 방향을 바꿈
  2) 스캔 스케줄링의 개선버전이 Look,   순환 스캔스케줄링의 개선버전은 C-Look


* 회전 최적화
 1) 디스크 스케줄링 알고리즘은 대기시간과 총 처리시간을 줄이기 이ㅜ해 디스크 헤드 이동을 최소화하는데 목적을 가짐
 2) 초기 시스템과 달리 현재의 디스크 시스템은 탐색시간과 평균 지연시간이 비슷하여 회전 최적화로도 성능 개선이 가능함
 3) 일괄처리 프로세스들은 데이터의 트랙 전체를 엑세스하므로 회전 최적화의 효과를 얻지 못함
 4) 대화식 프로세스 같은 디스크의 실린더에 분산된 소량으 데이터만 요구하는 요청이 많을 경우, 회전 최적화로 성능 개선 가능함

 1. 최소 지연시간 우선 스케줄링(SLFT, Shortest Latency Time First)
  1) 모든 요청 중 회전 지연시간이 가장 짧은 요청을 먼저 처리
  2)
  3) 트랙을 일정한 수의 블록으로 나눈 섹터를 토대로 요청들을 섹터 위치에 따라 큐에 넣고 가장 가까운 섹터에 대한 요청을 먼저 처리
   - 회전지연시간만이 지연시간이 되므로 드럼과 같이 고정헤드를 사용하는 경우 효과적
  4) 섹터 큐잉(SectorQueueing)알고리즘이라 표현
  5) 고정헤드 디스크의 다음 섹터를 위한 경로 선택 시, 섹터 지원 시간의 간격은 트랙이 전환하는데 걸리는 시간

 2. 최소 위치결저시간 우선 스케줄링(SPTF, Shortest Positioning Time FIrst)
  1) 가장 짧은 위치결정시간, 즉 탐색시간과 회전지연시간의 합이 가장 짧은 요청을 다음 서비스 대상으로 선택
  2) 최소 탐색시간 우선(SSTF)과 같이 처리량이 많고 평균 반응시간은 짧으나, 가장 안쪽과 바깥쪽 실린더에 대한 요청이 무기한 연기될 가능성이 있음

 3. 에션바흐 기법(Eschenbach Scheme)
  1) 탐색시간과 회전지역시간을 최적화하기 위한 기법
  2) 헤드는 순환스캔 스케줄링과 같이 진행하나 요청과 관계없이 트랙 한바퀴 회전할 동안 요청을 처리하도록 요청을 재배열함
  3) 1회전 동안 섹터 내의 많은 레코드들이 처리되어 회전지연시간을 줄임
  4) 회전은 한방향으로 진행되므로 두개의 요청이 실린더의 같은 섹터에 있으면 한 개의 요청만 처리되어 순환스캔스케줄링보다 성능 감소


* 디스크 스케줄링 알고리즘의 선택
 1. 성능은 요청의 형태와 요청의 수에 좌우됨
  1) 큐가 하나정도밖에 요청하지 않는다면 모든 스케줄링 알고리즘의 효과가 거의 같음 - 이경우 FCFS 선입선처리 가 적당함
  2) 디스크 서비스의 요청은 파일 할당 방법에 많은 영향을 받음
  3) 디렉터리 위치에 따라 이동거리가 달라짐
  4) 디스크는 시스템의 성능과 신뢰성 측면에서 병목현상의 주요 원인이 됨 - 컴퓨터 장치중 가장 느림, 시스템의 성능은 디스크의 신뢰성에 좌우됨