Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

Предположим, что задана следующая последовательность запросов диска (номера дорожек) для диска с 100 дорожками: 45, 20, 90, 10, 50, 60, 80, 25, 70. Предположим, что начальная позиция головки R / W включена дорожка 50. Дополнительное расстояние, которое будет проходить головкой R / W при использовании алгоритма кратчайшего времени поиска (SSTF) по сравнению с алгоритмом SCAN (лифт) (при условии, что алгоритм SCAN перемещается к 100, когда он начинает выполнение), составляет _________ треки
(А) 8
(Б) 9
(С) 10
(D) 11

Ответ: (с)
Объяснение: В кратчайшем поиске сначала (SSTF) ближайший запрос к текущей позиции головы, а затем обслуживает этот запрос следующим.

В алгоритме SCAN (или Elevator) запросы обслуживаются только в текущем направлении движения рычага, пока рука не достигнет края диска. Когда это происходит, направление руки меняется на противоположное, а запросы, оставшиеся в противоположном направлении, обслуживаются и так далее.

Given a disk with 100 tracks 

And Sequence 45, 20, 90, 10, 50, 60, 80, 25, 70.

Initial position of the R/W head is on track 50.

In SSTF, requests are served as following

Next Served     Distance Traveled
  50                   0
  45                   5
  60                  15   
  70                  10   
  80                  10   
  90                  10
  25                  65   
  20                   5   
  10                  10
-----------------------------------     
Total Dist         =  130


If Simple SCAN is used, requests are served as following

Next Served     Distance Traveled
  50                   0
  60                  10   
  70                  10   
  80                  10   
  90                  10
  45                  65 [disk arm goes to 100, then to 45]
  25                  20   
  20                   5   
  10                  10
-----------------------------------     
Total Dist         =  140


 Distance traveled in SSTF = 130 - 140 =  10 

Следовательно, оно не является дополнительным, но оно меньше пройденного SSTF, чем SCAN.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

0.00 (0%) 0 votes