Курынин Р.В., Машечкин И.В., Терехин А.Н. - Конспект лекций по ОС (1114685), страница 56
Текст из файла (страница 56)
Это важная проблема, поскольку от качества планированияможет во многом зависеть эффективность функционирования вычислительной системы.Неправильно организованное планирование очереди заказов на обмен может привести кдеградации системы, связанной, к примеру, с началом голодания каких-то процессов и,соответственно, зависания их функциональности.6.1.3Планирование дисковых обменовРассмотрим различные стратегии организации планирования дисковых обменов. При этомпреследуется цель проиллюстрировать то многообразие подходов к решению данной проблемы,которые имеют место в мире, с краткими результатами и выводами.Будем рассматривать некоторое дисковое устройство, обмен с которым осуществляетсядорожками (т.е.
происходит обращение и считывание соответствующей дорожки). Пускай имеетсяочередь запросов к следующим дорожкам: 4, 40, 11, 35, 7, 14. Изначально головка дисковогоустройства позиционирована на 15-ой дорожке. Замети, что время на обмен складывается из трехкомпонентов: выход головки на позицию, вращение диска и непосредственно обмен. Для оценкиэффективности алгоритмов будем подсчитывать суммарный путь, выраженный в количестведорожек, который пройдет головка для осуществления всех запросов на обмен из указаннойочереди.Первая стратегия, которую мы рассмотрим, — стратегия FIFO (First In First Out).
Этастратегия основывается лишь на порядке появления запроса в очереди. В нашем случае (6.1.3)головка сначала начинает двигаться с 15 дорожки на 4, потом на 40 и т.д. После обработки всейуказанной очереди суммарная длина пути составляет 135 дорожек, что в среднем можноохарактеризовать, как 22,5 дорожки на один обмен.215Путь головкиL15 → 4114 → 403640 → 112911 → 352435 → 7287 → 147047 11 141535 40Итого: 135Средний путь: 22,5Рис. 136.Планирование дисковых обменов. Модель FIFO.Альтернативой FIFO является стратегия LIFO (Last In First Out). Этот алгоритм в нашемслучае имеет примерно те же характеристики, что и FIFO. Но данная стратегия оказываетсяполезной, когда поступают цепочки связанных обменов: процесс считывает информацию,изменяет ее и обратно записывает.
Для таких процессов эффективнее всего будет выполнениеименно цепочки обмена, иначе после считывания он не сможет продолжаться, т.к. будет ожидатьзаписи (6.1.3).Путь головкиL15 → 14114 → 777 → 352835 → 112411 → 402940 → 436Итого: 126Средний путь: 20,83Рис. 137.Планирование дисковых обменов. Модель LIFO.Следующая стратегия — SSTF (Shortest Service Time First) — основана на «жадном»алгоритме.
Термин «жадного» алгоритма обычно применяется к итерационным алгоритмам длявыделения среди них класса алгоритмов, которые на каждой итерации ищут наилучшее решение.Применительно к нашей задаче данный алгоритм на каждом шаге осуществляет поиск в очередизапросов номер дорожки, требующей минимального перемещения головки диска. В итоге в нашемпримере получаются достаточно хорошие результаты, но данный алгоритм имеет существенныйнедостаток: ему присуща проблема голодания крайних дорожек (6.1.3).216Путь головкиL15 → 14114 → 11311 → 747→434 → 353135 → 405Итого: 47Средний путь: 7,83Рис. 138.Планирование дисковых обменов. Модель SSTF.Еще один алгоритм — алгоритм, основанный на приоритетах процессов (PRI).
Данныйалгоритм подразумевает, что каждому процессу присваивается некоторый приоритет, тогда взаказе на обмен присутствует еще и приоритет. И, соответственно, очередь запросовобрабатывается согласно приоритетам. Здесь встает серьезная проблема корректной организациивыдачи приоритета, иначе будут возникать случаи голодания низкоприоритетных процессов.Следующий алгоритм, который мы рассмотрим, — «лифтовый» алгоритм, или алгоритмсканирования (SCAN).
Данный алгоритм основан на том, что головка диска перемещается сначалав одну сторону до границы диска, выбирая каждый раз из очереди запрос с номером обозреваемойголовкой дорожки, а затем — в другую. Тогда заведомо известно, что для любого набора запросовпотребуется перемещений не больше удвоенного числа дорожек на диске. Данный алгоритмможет приводить к деградации системы вследствие голодания некоторых процессов в случае,когда идет интенсивный обмен с некоторой локальной областью диска (6.1.3).Путь головкиL15 → 352035 → 40540 → 142614 → 11311 → 747→43Итого: 61Средний путь: 10,16Рис.
139.Планирование дисковых обменов. Модель SCAN.Некоторой альтернативой является алгоритм циклического сканирования (С-SCAN). Этоталгоритм основан на том, что сканирование всегда происходит в одном направлении. В очередизапросов ищется запрос с минимальным (или максимальным) номером, головка передвигается кдорожке с этим номером, а затем за один проход по диску обрабатывается вся очередь запросов.Но проблемы остаются те же самые, что и для алгоритма сканирования (6.1.3).217Путь головкиL15 → 4114→737 → 11411 → 14314 → 352135 → 405Итого: 47Средний путь: 7,83Рис.
140.Планирование дисковых обменов. Модель C-SCAN.Для решения проблемы зависания при интенсивном обмене с локальной областью дискаприменяются многошаговый алгоритм (N-step-SCAN). В этом случае очередь запросов какимлибо образом (способ разделения может быть произвольным, в частности, по локализациизапросов, по времени поступления и т.д.) делится на N подочередей, затем по какой-либостратегии выбирается очередь, которая будет обрабатываться (например, по порядку ихформирования), и начинается ее обработка. Во время обработки очереди блокируется попаданиеновых запросов в эту очередь (тогда эти запросы могут сформировать новую очередь), другиеочереди могут получать заявки.
Сама обработка очереди может осуществляться, например, поалгоритму сканирования. Данный алгоритм «уходит» от проблемы голодания.Итак, мы проиллюстрировали некоторые стратегии организации планирования дисковыхобменов. Еще раз отметим, что эти модель очень упрощенные: они основаны на использованииминимальной информации о заказе на обмен. Реальные системы, реальные очереди содержат неодиночные заказы на обмен, а целые цепочки заказов на обмен, которые произвольным образомобрабатывать нельзя. Например, если идет заказ на считывание данных, потом процесс ихизменяет, а затем обратно записывает, то эти считывание и запись могут следовать лишь в одномпорядке.6.1.4RAID-системы.
Уровни RAIDАббревиатура RAID может раскрываться двумя способами. RAID — Redundant Array ofIndependent (Inexpensive) Disks, или избыточный массив независимых (недорогих) дисков. Насегодняшний день обе расшифровки не совсем корректны. Понятие недорогих дисков родилось вте времена, когда большие быстрые диски стоили достаточно дорого, и перед многимиорганизациями, желающими сэкономить, стояла задача построения такой организации набораболее дешевых и менее быстродействующих и емких дисков, чтобы их суммарная эффективностьне уступала одному богатому диску. На сегодняшний день цены между различными похарактеристикам дисками более сглажены, но бывают и исключения, когда новейший диск чуть лине на порядок опережает по цене своих предыдущих собратьев.
Что касается независимостидисков, то она соблюдается не всегда.RAID-система — это совокупность физических дисковых устройств, котораяпредставляется в операционной системе как одно устройство, имеющее возможность организациипараллельных обменов. Помимо этого образуется избыточная информация, используемая дляконтроля и восстановления информации, хранимой на этих дисках.RAID-системы предполагают размещение на разных устройствах, составляющих RAIDмассив, порции данных фиксированного размера, называемые полосами, которым осуществляетсяобмен в данных системах.
Размер полосы зависит от конкретного устройства (при обсуждениифайловых систем была упомянута иерархия различных блоков, так RAID добавляет в этуиерархию дополнительный уровень — уровень полос RAID).218На сегодняшний день выделяют семь моделей RAID-систем (от нулевой модели дошестой). Рассмотрим их по порядку.RAID 0 (6.1.4). В этой модели полоса соизмерима с дисковыми блоками, соседние полосынаходятся на разных устройствах. Организация RAID нулевого уровня чем-то напоминаетрасслоение оперативной памяти. С каждым диском обмен может происходить параллельно.Каждое устройство независимое, т.е. движение головок в каждом из устройств несинхронизировано.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
