Операционные системы 2011 (1114689), страница 66
Текст из файла (страница 66)
144.В). Процессор генерировалпоследовательность управляющих команд, указывая координаты в оперативной памяти,куда надо положить или откуда надо взять данные, а DMA-контроллер занималсяперемещением данных между ОЗУ и внешним устройством. Таким образом, поток данныхшел в обход процессора.И, наконец, можно отметить последнюю модель, основанную на том, чтоуправлениевнешнимиустройствамиосуществляетсясиспользованиемспециализированного процессора (или даже специализированных компьютеров) иликаналов ввода-вывода. Данная модель подразумевает снижение нагрузки нацентральный процессор с точки зрения обработки потока управления: ЦПУ теперьоперирует функционально-емкими макрокомандами. Решение задачи осуществлениянепосредственного обмена, а также решение всех связанных с обменом вопросов (в т.ч.оптимизация операций обмена, например, за счет использования аппаратной буферизациив процессоре ввода-вывода) ложится «на плечи» специализированного процессора.6.1.2 Программное управление внешними устройствамиРассмотрим архитектуру программного управления внешними устройствами,которую можно представить в виде некоторой иерархии (Рис.
145). В основании лежитаппаратура, а далее следуют программные уровни: программы обработки прерываний,драйверы физических устройств, а на вершине иерархии лежит уровень драйверовлогических устройств, причем каждый уровень строится на основании нижележащегоуровня.Драйверы виртуальных устройствДрайверы физических устройствПрограммы обработки прерыванийАппаратураРис. 145. Иерархия архитектуры программного управления внешнимиустройствами.Можно выделить следующие цели программного управления устройствами. Вопервых, это унификация программных интерфейсов доступа к внешним устройствам.Иными словами, это стандартизация правил использования различных устройств.Преследуя данную цель, мы абстрагируемся от аппаратных характеристик обмена.
Еслиданная цель достигнута, то, например, пользователю, пожелавшему распечататьтекстовый файл, не надо будет заботиться об организации управления конкретнымпечатающим устройством - ему достаточно воспользоваться некоторым общимпрограммным интерфейсом.245Следующая цель — это обеспечение конкретной модели синхронизации привыполнении обмена (синхронный или асинхронный обмен).
Отметим здесь, что,несмотря на то, что синхронный вид обмена появился хронологически одним из первых,он остается актуальным и по сей день. Таким образом, ставится цель поддерживать обавида обмена, а выбор конкретного типа зависит от пользователя.Еще одной целью является выявление и локализация ошибок, а такжеустранение их последствий.
Для любой системы справедливо, что чем более она сложна,тем больше статистически в ней возникает сбоев. Соответственно, система должна бытьорганизована таким образом, чтобы она могла выявить момент появления сбоя и старатьсяобработать эту сбойную ситуацию: либо самостоятельно ее обойти, либо известитьпользователя.Следующая цель — буферизация обмена — связана с различнойпроизводительностью основных компонентов системы. Известно, что любое внешнееустройство работает медленнее центральной части компьютера, и, соответственно, стоитпроблема сглаживания разброса производительностей различных компонентов системы.Причем, если речь идет об устройствах, не являющихся устройствами оперативногодоступа (т.е.
не являющихся устройствами, к которым идет массовое обращение на обменот процессов), то для таких устройств проблема сглаживания отодвигается на второйплан. Например, если это медленное устройство печати, то для него особо не требуетсяреализация буфера, а если дело касается магнитного диска, рассчитанного наиспользование в качестве массового устройства, то тут операции обмена должныобрабатываться по возможности быстро. Решением указанной задачи являетсяорганизация разного рода кэширования в системе.Также необходимо отметить такую цель, как обеспечение стратегии доступа кустройству (распределенный или монопольный доступ). Во время рассмотренияфайловых систем ОС Unix говорилось, что один и тот же файл может быть доступен черезмножество файловых дескрипторов, которые могут быть распределены междуразличными процессами, т.е.
файл может быть многократно открыт в системе, и системапозволяет организовывать распределенный доступ к его информации. Система позволяеторганизовать управление этим доступом и синхронизацию. Система также позволяеторганизовать и монопольный доступ к устройству.И, наконец, последней целью, которую стоит отметить, является планированиевыполнения операций обмена. Это важная проблема, поскольку от качествапланирования может во многом зависеть эффективность функционированиявычислительной системы.
Неправильно организованное планирование очереди заказов наобмен может привести к деградации системы, связанной, к примеру, с началом голоданиякаких-то процессов и, соответственно, зависания их функциональности.6.1.3 Планирование дисковых обменовРассмотрим различные стратегии организации планирования дисковых обменов.При этом преследуется цель проиллюстрировать то многообразие подходов к решениюданной проблемы, которые имеют место в мире, с краткими результатами и выводами.Будем рассматривать некоторое дисковое устройство, обмен с которымосуществляется дорожками (т.е. происходит обращение и считывание соответствующейдорожки). Пустьй имеется очередь запросов к следующим дорожкам: 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-система — это совокупность физических дисковых устройств, котораяпредставляется в операционной системе как одно устройство, имеющее возможностьорганизации параллельных обменов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
