2011. Машбук (1114722), страница 66
Текст из файла (страница 66)
происходит обращение и считывание соответствующейдорожки). Пустьй имеется очередь запросов к следующим дорожкам: 4, 40, 11, 35, 7, 14 ипусть изначально головка дискового устройства позиционирована на 15-ой дорожке.Замети, что время на обмен складывается из трех компонентов: выход головки напозицию, вращение диска и непосредственно обмен. Для оценки эффективностиалгоритмов будем подсчитывать суммарный путь (выраженный в количестве дорожек),который пройдет головка для осуществления всех запросов на обмен из указаннойочереди.246Первая стратегия, которую мы рассмотрим, — стратегия FIFO (First In First Out).Эта стратегия основывается лишь на порядке появления запроса в очереди. В нашемслучае (Рис.
146) головка сначала начинает двигаться с 15 дорожки на 4, потом на 40 и т.д.После обработки всей указанной очереди суммарная длина пути составляет 135 дорожек,что в среднем можно охарактеризовать, как 22,5 дорожки на один обмен.Путь головкиL15 → 4114 → 403640 → 112911 → 352435 → 7287 → 147047 11 14 1535 40Итого: 135Средний путь: 22,5Рис. 146. Планирование дисковых обменов. Модель FIFO.Альтернативой FIFO является стратегия LIFO (Last In First Out). Этот алгоритм внашем случае имеет примерно те же характеристики, что и FIFO.
Но данная стратегияоказывается полезной, когда поступают цепочки связанных обменов: процесс считываетинформацию, изменяет ее и обратно записывает. Для таких процессов эффективнее всегобудет выполнение именно цепочки обмена, иначе после считывания он не сможетпродолжаться, т.к.
будет ожидать записи (Рис. 147).Путь головкиL15 → 14114 → 777 → 352835 → 112411 → 402940 → 436Итого: 126Средний путь: 20,83Рис. 147. Планирование дисковых обменов. Модель LIFO.Следующая стратегия — SSTF (Shortest Service Time First) — основана на«жадном» алгоритме. Термин «жадного» алгоритма обычно применяется к итерационнымалгоритмам для выделения среди них класса алгоритмов, которые на каждой итерацииищут наилучшее решение. Применительно к нашей задаче данный алгоритм на каждомшаге осуществляет поиск в очереди запросов номера дорожки, требующей минимальногоперемещения головки диска. В итоге, в нашем примере получаются достаточно хорошиерезультаты, но данный алгоритм имеет существенный недостаток: ему присуща проблемаголодания крайних дорожек (Рис.
148).247Путь головкиL15 → 14114 → 11311 → 747→434 → 353135 → 405Итого: 47Средний путь: 7,83Рис. 148. Планирование дисковых обменов. Модель SSTF.Еще один алгоритм — алгоритм, основанный на приоритетах процессов (PRI).Данный алгоритм подразумевает, что каждому процессу присваивается некоторыйприоритет, тогда в заказе на обмен присутствует еще и приоритет. И, соответственно,очередь запросов обрабатывается согласно приоритетам. Здесь встает серьезная проблемакорректной организации выдачи приоритета, иначе будут возникать случаи голоданиянизкоприоритетных процессов.Следующий алгоритм, который мы рассмотрим, — «лифтовый» алгоритм, илиалгоритм сканирования (SCAN).
Данный алгоритм основан на том, что головка дискаперемещается сначала в одну сторону до границы диска, выбирая каждый раз из очередизапрос с номером обозреваемой головкой дорожки, а затем — в другую. Тогда заведомоизвестно, что для любого набора запросов потребуется перемещений не большеудвоенного числа дорожек на диске. Данный алгоритм может приводить к деградациисистемы вследствие голодания некоторых процессов в случае, когда идет интенсивныйобмен с некоторой локальной областью диска (Рис.
149).Путь головкиL15 → 352035 → 40540 → 142614 → 11311 → 747→43Итого: 61Средний путь: 10,16Рис. 149. Планирование дисковых обменов. Модель SCAN.Некоторой альтернативой является алгоритм циклического сканирования (СSCAN). Этот алгоритм основан на том, что сканирование всегда происходит в одномнаправлении. В очереди запросов ищется запрос с минимальным (или максимальным)номером, головка передвигается к дорожке с этим номером, а затем за один проход подиску обрабатывается вся очередь запросов.
Но проблемы остаются те же самые, что идля алгоритма сканирования (Рис. 150).248Путь головкиL15 → 4114→737 → 11411 → 14314 → 352135 → 405Итого: 47Средний путь: 7,83Рис. 150. Планирование дисковых обменов. Модель C-SCAN.Для решения проблемы зависания при интенсивном обмене с локальной областьюдиска применяются многошаговый алгоритм (N-step-SCAN). В этом случае очередьзапросов каким-либо образом делится на N подочередей (способ разделения может бытьпроизвольным, в частности, по локализации запросов, по времени поступления и т.д.);затем по какой-либо стратегии выбирается очередь, которая будет обрабатываться(например, по порядку формирования), и начинается ее обработка. Во время обработкиочереди блокируется попадание новых запросов в эту очередь (тогда эти запросы могутсформировать новую очередь), другие очереди могут получать заявки.
Сама обработкаочереди может осуществляться, например, по алгоритму сканирования. Данный алгоритм«уходит» от проблемы голодания.Итак, мы проиллюстрировали некоторые стратегии организации планированиядисковых обменов. Еще раз отметим, что эти модель очень упрощенные: они основаны наиспользовании минимальной информации о заказе на обмен. Реальные системы, реальныеочереди содержат не одиночные заказы на обмен, а целые цепочки заказов на обмен,которые произвольным образом обрабатывать нельзя. Например, если идет заказ насчитывание данных, потом процесс их изменяет, а затем обратно записывает, то этисчитывание и запись могут следовать лишь в одном порядке.6.1.4 RAID-системы.
Уровни RAIDАббревиатура RAID может раскрываться двумя способами. RAID — RedundantArray of Independent (Inexpensive) Disks, или избыточный массив независимых (недорогих)дисков. На сегодняшний день обе расшифровки не совсем корректны. Понятие недорогихдисков родилось в те времена, когда большие быстрые диски стоили достаточно дорого, иперед многими организациями, желающими сэкономить, стояла задача построения такойорганизации набора более дешевых и менее быстродействующих и емких дисков, чтобыих суммарная эффективность не уступала одному «дорогому» диску. На сегодняшнийдень цены между различными по характеристикам дисками более сглажены, но бывают иисключения, когда новейший диск чуть ли не на порядок опережает по цене своихпредыдущих собратьев.
Что касается независимости дисков, то она соблюдается не всегда.RAID-система — это совокупность физических дисковых устройств, котораяпредставляется в операционной системе как одно устройство, имеющее возможностьорганизации параллельных обменов. Помимо этого образуется избыточная информация,используемая для контроля и восстановления информации, хранимой на этих дисках.RAID-системы предполагают размещение на разных устройствах, составляющихRAID-массив, порций данных фиксированного размера, называемых полосами, которымиосуществляется обмен в таких системах. Размер полосы зависит от конкретногоустройства (при обсуждении файловых систем была упомянута иерархия различных249блоков; RAID добавляет в эту иерархию дополнительный уровень — уровень полосRAID).На сегодняшний день выделяют семь моделей RAID-систем (от нулевой модели дошестой).
Рассмотрим их по порядку.RAID 0 (Рис. 151). В этой модели полоса соизмерима с дисковыми блоками,соседние полосы находятся на разных устройствах. Организация RAID нулевого уровнячем-то напоминает расслоение оперативной памяти. С каждым диском обмен можетпроисходить параллельно. Каждое устройство независимое, т.е.
движение головок вкаждом из устройств не синхронизировано. Данная модель не хранит избыточнуюинформацию, поэтому в ней могут храниться данные объемом, равным суммарнойемкости дисков, при этом за счет параллельного выполнения обменов доступ кинформации становится более быстрым.полоса 0полоса 1полоса 2полоса 3полоса 4полоса 5полоса 6полоса 7полоса 8полоса 9полоса 10полоса 11полоса 12полоса 13полоса 14полоса 15Рис. 151. RAID 0.RAID 1, или система зеркалирования (Рис. 152). Предполагается наличие двухкомплектов дисков. При записи информации она сохраняется на соответствующем дискеи на диске-дублере. При чтении информации запрос направляется лишь одному из дисков.К диску-дублеру происходит обращение при утере информации на первом экземпляредиска.полоса 0полоса 0полоса 1полоса 1полоса 2полоса 2полоса 3полоса 3Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
