엘리베이터 알고리즘

Elevator algorithm

엘리베이터 알고리즘(SCAN)은 읽기 및 쓰기 요청을 처리할 때 디스크의 암과 헤드의 움직임을 결정하는 디스크 스케줄링 알고리즘입니다.

이 알고리즘은 건물 엘리베이터의 동작에서 이름을 따온 것입니다.엘리베이터는 비어 있을 때까지 현재의 방향(위 또는 아래)으로 계속 이동하다가 개인을 하차시키거나 같은 방향으로 향하는 새로운 개인을 태우기 위해서만 정지합니다.

실시의 관점에서는, 드라이브는 요구의 관련하는 실린더 번호와 함께 보류중의 읽기/쓰기 요구의 버퍼를 보관 유지합니다.이러한 실린더 번호는 일반적으로 실린더가 스핀들에 가까운 것을 나타내며, 수치가 높을수록 실린더가 더 멀리 있음을 나타냅니다.

묘사

드라이브가 유휴 상태일 때 새 요청이 도착하면 초기 암/헤드 이동은 데이터가 저장된 실린더 방향(안 또는 밖)이 됩니다.추가 요청이 도착하면 암이 디스크 가장자리에 도달할 때까지 현재 암 이동 방향으로만 요청이 처리됩니다.이 경우 암의 방향이 반대로 되어 반대 방향으로 남아 있던 요구가 처리되는 [1]등 계속됩니다.

바리에이션

이 방법을 한 가지 변형하면 모든 요구가 한 방향으로만 처리됩니다.즉, 헤드가 디스크의 바깥쪽 가장자리에 도착하면 헤드는 선두로 돌아가 이 한 방향으로만 새로운 요구를 처리합니다(또는 그 반대).이것은 「Circular Elvator Algorithm 또는 C-SCAN이라고 불립니다.리턴 시크의 시간은 낭비되지만, 중앙의 실린더가 가장 안쪽 또는 가장 바깥쪽 실린더보다 두 배 이상 자주 서비스되는 표준 엘리베이터 알고리즘과 달리 헤드로부터의 예상 거리는 항상 최대 거리의 절반이기 때문에 모든 헤드 위치에서 더 동일한 성능을 얻을 수 있습니다.

기타 변형은 다음과 같습니다.

예

다음으로 SCAN 알고리즘과 C-SCAN 알고리즘의 평균 디스크 탐색 시간을 계산하는 예를 나타냅니다.

  • 보류 중인 디스크 요청 목록(트랙 번호별로 나열됨): 100, 50, 10, 20, 75. 75.
  • 예시의 출발 트랙 번호는 35번입니다.
  • 목록은 10, 20, 50, 75, 100의 오름차순으로 정렬해야 합니다.

SCAN과 C-SCAN은 큐잉된 마지막 트랙에 도달할 때까지 동일한 방식으로 동작합니다.이 예에서는 SCAN 알고리즘이 현재 낮은 트랙 번호에서 높은 트랙 번호로 이동하고 있다고 가정합니다(C-SCAN이 하고 있는 것처럼).두 가지 방법 모두, 다음 트랙 요청과 현재 트랙 사이의 크기 차이 (절대값)를 취합니다.

  • 검색 1: 50 - 35 = 15
  • 검색 2: 75 - 50 = 25
  • 검색 3: 100 - 75 = 25

이 시점에서 둘 다 최고(종료) 트랙 요청에 도달했습니다.SCAN은 역방향으로 다음으로 가까운 디스크 요구(이 예에서는 20)를 처리합니다.C-SCAN은 항상 트랙0으로 돌아가 상위 트랙 요구로 이동합니다.

  • Seek 4(SCAN): 20 - 100 = 80
  • Seek 5(SCAN): 10 - 20 = 10
  • 합계(SCAN): 155
  • 평균(SCAN): 155 5 5 = 31
  • Seek 4(C-SCAN): 실린더가 원형 목록으로 처리될 때 0 - 100 = 0 헤드 이동(C-SCAN은 항상 첫 번째 트랙으로 돌아갑니다)
  • 시크 5(C-SCAN): 10 - 0 = 10
  • Seek 6 (C-SCAN): 20 - 10 = 10
  • 합계(C-SCAN): 85
  • 평균(C-SCAN): 85 † 5 = 17

C-SCAN 알고리즘을 사용하여 6개의 검색을 수행했지만 실제로는 5개의 I/O만 수행되었습니다.

분석.

두 버전의 엘리베이터 알고리즘에서 암 이동은 총 실린더 수의 두 배 미만이며 응답 시간의 편차가 더 작습니다.알고리즘도 비교적 간단합니다.

엘리베이터 알고리즘이 최선에 약간 가까운 최단 탐색 우선보다 항상 좋은 것은 아니지만, 기존 요구보다 새로운 요구가 계속적으로 처리될 경우 응답 시간의 편차가 심해지고 기아 상태가 될 수도 있습니다.최대 응답 시간을 보장하기 위해 최단 시크 시간 우선 알고리즘에 기아 방지 기술을 적용할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Disk scheduling". Archived from the original on 2008-06-06. Retrieved 2008-01-21.