Рубрики

Алгоритмы планирования диска

Планирование диска выполняется операционными системами для планирования поступающих на диск запросов ввода-вывода. Планирование диска также известно как планирование ввода / вывода.

Планирование диска важно, потому что:

  • Несколько запросов ввода-вывода могут поступать от разных процессов, и только один запрос ввода-вывода может обслуживаться одновременно контроллером диска. Таким образом, другие запросы ввода-вывода должны ждать в очереди и должны быть запланированы.
  • Два или более запроса могут находиться далеко друг от друга, что может привести к большему перемещению рычага диска.
  • Жесткие диски являются одной из самых медленных частей компьютерной системы, поэтому к ним необходимо обращаться эффективно.

Существует много алгоритмов планирования дисков, но прежде чем их обсуждать, давайте кратко рассмотрим некоторые важные термины:

  • Время поиска: Время поиска это время , необходимое для обнаружения диска руку к указанной дорожке , где данные должны быть чтения или записи. Таким образом, алгоритм планирования диска, который дает минимальное среднее время поиска, лучше.
  • Задержка вращения: Задержка вращения — это время, которое требуемый сектор диска поворачивает в положение, обеспечивающее доступ к головкам чтения / записи. Таким образом, алгоритм планирования диска, который дает минимальную задержку вращения, лучше.
  • Время передачи: время передачи — это время для передачи данных. Это зависит от скорости вращения диска и количества передаваемых байтов.
  • Время доступа к диску: Время доступа к диску:
             
      Disk Access Time = Seek Time + 
                         Rotational Latency + 
                         Transfer Time

  • Время отклика диска. Время отклика — это среднее время, затраченное запросом, ожидающим выполнения операции ввода-вывода. Среднее время ответа — это время ответа на все запросы. Дисперсионное время отклика является мерой того, как отдельный запрос обрабатывается относительно среднего времени отклика. Таким образом, алгоритм планирования диска, который дает минимальное время отклика на отклонения, лучше.

Алгоритмы планирования диска

  1. FCFS: FCFS — самый простой из всех алгоритмов планирования дисков. В FCFS запросы обрабатываются в порядке их поступления в очередь на диске.

Преимущества:

  • Каждый запрос получает реальный шанс
  • Никакой неопределенной отсрочки

Недостатки:

  • Не пытается оптимизировать время поиска
  • Может не предоставлять лучший сервис
  1. SSTF: в SSTF (сначала самое короткое время поиска) запросы, имеющие самое короткое время поиска, выполняются первыми. Таким образом, время поиска каждого запроса заранее рассчитывается в очереди, а затем они планируются в соответствии с их рассчитанным временем поиска. В результате, запрос рядом с кронштейном диска будет выполнен первым. SSTF, безусловно, является улучшением по сравнению с FCFS, поскольку уменьшает среднее время отклика и увеличивает пропускную способность системы.

Преимущества:

  • Среднее время отклика уменьшается
  • Пропускная способность увеличивается

Недостатки:

  • Накладные расходы, чтобы рассчитать время поиска заранее
  • Может вызвать голодание для запроса, если у него более высокое время поиска по сравнению с входящими запросами
  • Высокая дисперсия времени ответа, так как SSTF поддерживает только некоторые запросы
  1. SCAN: в алгоритме SCAN плечо диска перемещается в определенном направлении и обслуживает запросы, поступающие на его пути, и после достижения конца диска оно меняет направление и снова обслуживает запрос, поступающий на его пути. Таким образом, этот алгоритм работает как лифт и, следовательно, также известен как алгоритм лифта. В результате запросы на среднем уровне обслуживаются больше, и тем, кто приходит за плечо диска, придется ждать.

Преимущества:

  • Высокая пропускная способность
  • Низкая дисперсия времени отклика
  • Среднее время отклика

Недостатки:

  • Длительное время ожидания запросов на места, которые только что посетили диск
  1. CSCAN : В алгоритме SCAN рычаг диска снова сканирует путь, который был отсканирован, после изменения его направления. Таким образом, может случиться так, что слишком много запросов ожидает на другом конце или может быть ноль или несколько запросов, ожидающих в сканируемой области.

Этих ситуаций избегают в алгоритме CSCAN , в котором плечо диска вместо изменения направления направляется на другой конец диска и начинает обслуживать запросы оттуда. Таким образом, рычаг диска движется по кругу, и этот алгоритм также похож на алгоритм SCAN и, следовательно, он известен как C-SCAN (Круговое SCAN).

Преимущества:

  • Обеспечивает более равномерное время ожидания по сравнению со SCAN
  1. СМОТРИТЕ: Это похоже на алгоритм планирования диска SCAN за исключением того, что плечо диска, несмотря на переход к концу диска, обращается только к последнему запросу на обслуживание перед головкой, а затем меняет свое направление оттуда только. Таким образом, это предотвращает дополнительную задержку, которая произошла из-за ненужного обхода конца диска.
  1. CLOOK: Так как LOOK похож на алгоритм SCAN, CLOOK похож на алгоритм планирования диска CSCAN. В CLOOK рычаг диска, несмотря на переход к концу, переходит только к последнему запросу, который должен быть обслужен перед головкой, а затем оттуда переходит к последнему запросу другого конца. Таким образом, это также предотвращает дополнительную задержку, которая произошла из-за ненужного обхода конца диска.

Каждый алгоритм по-своему уникален. Общая производительность зависит от количества и типа запросов.
Примечание. Средняя задержка вращения обычно принимается равной 1/2 (задержка вращения).
Упражнение

1) Предположим, что диск имеет 201 цилиндр, пронумерованный от 0 до 200. В какой-то момент рычаг диска находится на цилиндре 100, и существует очередь запросов доступа к диску для цилиндров 30, 85, 90, 100, 105, 110, 135 и 145. Если для планирования доступа к диску используется время первичного поиска (SSTF), запрос на цилиндр 90 обслуживается после обслуживания ____________ числа запросов. (GATE CS 2014
(А) 1
(БИ 2
(С) 3
(D) 4
Смотрите это для решения.

2) Рассмотрим операционную систему, способную загружать и выполнять один последовательный пользовательский процесс одновременно. Используемый алгоритм планирования заголовка диска — First Come First Served (FCFS). Если FCFS будет заменена на Shortest Seek Time First (SSTF), который, как утверждает производитель, даст на 50% лучшие результаты тестов, каково ожидаемое улучшение производительности ввода-вывода пользовательских программ? (GATE CS 2004)
(А) 50%
(Б) 40%
(С) 25%
(D) 0%
Смотрите это для решения.

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

4) Рассмотрим типичный диск, который вращается со скоростью 15000 оборотов в минуту (об / мин) и имеет скорость передачи 50 × 10 ^ 6 байт / с. Если среднее время поиска диска вдвое превышает среднюю задержку вращения, а время передачи контроллера в 10 раз больше времени передачи диска, среднее время (в миллисекундах) чтения или записи 512-байтового сектора диска составляет _____________
Смотрите это для решения.

Эта статья предоставлена Анкит Миттал . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Алгоритмы планирования диска

0.00 (0%) 0 votes