LOE 알고리즘

LOOK algorithm

RAK는 새 디스크 읽기 및 쓰기 요청이 처리되는 순서를 결정하는 데 사용되는 디스크 스케줄링 알고리즘이다.

설명

LOUK 알고리즘은 디스크 헤드의 양쪽 스위프 방향에 대한 요청도 존중한다는 점에서 SCAN 알고리즘과 동일하지만, 이 알고리즘 "Looks"는 헤드 이동 방향에 보류 중인 요청이 있는지 확인하기 위해 앞쪽에 있다. 헤드 이동 방향으로 보류 중인 요청이 없는 경우 디스크 헤드 트래버설이 반대 방향으로 반전되어 다른 방향으로 요청을 처리할 수 있다. LOK 스케줄링에서 암은 각 방향의 최종 요청까지만 이동한 다음 끝까지 가지 않고 방향을 반전시킨다. 예를 들어, 200개의 실린더가 있는 디스크(0-1999)를 고려할 때, 8개의 대기 중인 요청이 있다고 가정합시다: 98, 183, 37, 122, 14, 124, 65, 67, 그리고 읽기/쓰기 헤드가 현재 실린더 53에 있다고 가정합시다. 이러한 요청을 완료하기 위해 암은 먼저 증가된 순서로 이동한 다음 종료에 도달한 후 감소하는 순서로 이동한다. 그래서 집행순서는 65, 67, 98, 122, 124, 183, 37, 14이다.[1]

LOACK은 SSTF의 기아 문제를 피하기 위해 SSTF(최단 탐색 시간)와 거의 동일하게 행동한다. 이는 LOACK이 최근 횡단한 지역에 대해 편향되어 있으며, 플래터의 가장 바깥쪽과 가장 안쪽 가장자리에 모여 있는 트랙을 매우 선호하기 때문이다. LOACK은 또한 더 최근에 도착한 직업에 편중되어 있다(평균적으로

변형

  • C-LOOK(순환형 룩)
LOACK의 한 변종은 C-LOK이다. 플래터의 가장자리에 있는 트랙 군집의 Look에서 편향을 제거하기 위한 노력이다. C-LOUK는 기본적으로 한 방향으로만 스캔한다. 안쪽에서 바깥쪽으로 쓸거나 바깥쪽에서 쓸거나 둘 중 하나야. 마지막에 이르면 머리를 처음부터 끝까지 흔들기만 하면 된다. 이것은 실제로 많은 드라이브가 많은 수의 트랙을 가로질러 이동하는 경우(예: 마지막 트랙에서 트랙 0까지의 탐색 시간은 예상한 것보다 짧고 일반적으로 한 번에 하나의 트랙을 탐색하는 데 걸리는 시간보다 상당히 짧음) 많은 드라이브가 고속으로 읽기/쓰기 헤드를 이동할 수 있다는 사실을 이용한다. 한쪽 끝 요청에서 다른 쪽 끝까지의 거대한 점프는 실린더가 원형 리스트로 취급되기 때문에 머리 움직임으로 간주되지 않는다.
  • 엔룩 앤 에프룩
N과 F LOACK은 최근 일자리에 대한 LOACK의 편견을 상쇄하기 위해 고안되었다. 두 알고리즘 모두 요청 대기열을 더 작은 하위 대기열로 분할하고 하위 대기열을 순서대로 처리한다(가장 오래된 우선). 요청 대기열이 N 하위 대기열로 나뉜다고 해서 N-LOUK라고 한다. F-LOOK은 큐가 2개밖에 없는 단순화지만 이중버퍼 방식으로 사용된다. F-LOOK가 하나의 대기열을 처리하는 동안, 모든 새로운 요청은 다른 대기열로 들어간다. 이러한 알고리즘을 설명하기 위해 트랙이 200개인 디스크의 예를 사용할 것이며 읽기/쓰기 헤드는 트랙 100에서 시작한다. 요청 대기열에는 55, 58, 18, 90, 160, 38의 트랙 요청이 순서대로 들어 있으며, 가장 오래된 대기열은 55, 58, 18, 90의 트랙 요청이 포함된 것으로 가정한다. 이 경우 N-LOK와 F-LOK는 동일하게 행동한다. 또한, 이 구성에서, 머리는 어느 방향으로 이동했는지는 중요하지 않으며, 요청된 모든 트랙이 100 미만이기 때문에 트랙이 감소하는 방향으로만 이동한다는 점에 유의하십시오.
통과된 평균 트랙 수는 최악의 경우 LOACK과 동일하지만, N과 F LOACK은 어떤 의미에서는 평범하고 오래된 LOACK보다 더 공정하다. 하위 대기열 시스템은 요청과 서비스 중인 프로세스 간에 프로세스가 예상할 수 있는 최대 대기 시간을 제한한다(임의의 시간 동안 프로세스를 굶길 수 있는 SSTF와는 달리).
  • 에스룩
최단 LOUK(S-LOOK) 알고리즘은 원단 요청 사이에 디스크 헤드가 위치한 경우를 처리하기 위한 LOUK 알고리즘의 확장이다. 알고리즘은 새로운 요청이 도착하기 전에 동일한 방향으로만 계속 모색하는 것이 아니라 어느 방향으로 먼저 서비스해야 하는지를 결정하도록 설계되어 있다. 탐색 시간은 탐색 거리에 정비례하므로, 우리의 목표는 탐색 거리를 최소화하고, 따라서 탐색 시간을 줄이는 것이다.

퍼포먼스

LOACK은 SCAN보다 평균 탐색 시간이 약간 더 좋다. C-LOK은 최악의 경우 탐색 시간이 거의 절반으로 줄어들기 때문에 ROK보다 탐색 시간의 편차가 약간 낮다.

참고 항목

그 밖의 변동은 다음과 같다.

참조

  1. ^ "Lecture 17 - Disk Scheduling".