Билеты (Graur) (1114774), страница 31
Текст из файла (страница 31)
планирование выполнения операций обмена – возникает, когда возникаетконкуренция за доступ к ресурсу.Билет 46. Управление внешними устройствами.Буферизация обмена. Планирование дисковых обменов,основные алгоритмы.Буферизация обменаT – время обмена;С – время выполнения программы между обменамиt – общее время выполнения программыСхемы буферизации ввода-выводаа) Без буферизацииЕсли обмен проходит без буферизации, то совокупное время выполненияпрограммы будет складываться из времени обмена и времени выполненияпрограммы между обменами.б) Одинарная буферизацияПри использовании одиночной буферизации подавляется заказ на обмен с ОП, ипроцесс может в этом случае не ожидать. Целесообразно использовать, когда идетинтенсивный поток заказов на обмен.в) Двойная буферизацияМодель использования двойной буферизации следующая: в один буферпомещаются данные по обмену, в другой ОС готовит данные за предыдущийобмен.г) Циклическая буферизацияКакую схему выбрать зависит от интенсивности буферизации и особенностидействийПланирование дисковых обменовВозможна ситуация, когда поток заказов на обмен > пропускной способностисистемы в некоторые моменты.Тогда есть несколько вариантов действий:1.Принимаем решения о порядке обработки запросов2.
начинаем учитывать приоритеты3. осуществляем случайный выбор.Проблема: Обмены могут быть зависимы друг от друга. В таком случае некоторыеварианты не подходят.Пусть наш диск может сразу переходить i-ой дорожки на j-ую без начальногопозиционирования.Рассмотрим модельную ситуацию:головка HDD позиционирована на дорожке 15Очередь запросов к дорожкам: 4, 40, 11, 35, 7, 14Варианты решения1.
простейшая модель – случайная выборка из очереди2.Общее время выполнения – 135ед.Среднее время выполнения – 21.5 ед.3.SSTFПриоритет имеет обмен, для которого потребуется наименьшеевремя. «Жадный» алгоритм на каждом шаге пытается получитьмаксимальный эффект. Общая нагрузка на систему с точки зренияобмена сокращается в 3 раза.
Возможно «залипание» головки втом случае, если обмен идет интенсивно с одними и теми жедорожками. Некоторые процессы будут отделены.4.LIFOСмысл – попытка развязать последовательность обмена, связанную с новымиисточниками.Приоритетный алгоритм (RPI) – это алгоритм, когда последовательность обменов(очередь) имеет характеристику приоритетов. При использовании приоритетныхалгоритмов может возникать проблема голодания или дискриминации. Проблемадискриминации возникает при непрерывном поступлении более приоритетныхзапросов на обмен, в это время как менее приоритетные запросы простаивают.Находясь в начальной позиции сначала двигаемся в одну сторонудо конца, затем в другую до конца.Для " набора запросовперемещений £ 2 х число дорожекВыходим на минимальную (максимальную дорожку, а затемдвижемся в одну сторону).
Пройдем не более двух маршрутов.N-step-SCANРазделение очереди на подочереди длины £ N запросов каждая (из соображенийFIFO). Последовательная обработка очередей. Обрабатываемая очередь необновляется. Обновление очередей, отличных от обрабатываемой.Этот алгоритм срывает головку с залипания.Распространенный пример: 2 очереди, одна обрабатывается, другая собирает вновьпоступающие запросы.Билет 47 .RAID системы.Существуют проблемы с организацией больших потоков данных.В общем случае для дисковых систем имеют место как минимум две проблемы:1. Эффективность. Допустим, в системе присутствуют все уровни КЭШ, нопроизводительности не хватает, так как обмены, которые производятся надисковых устройствах, медленные.2.
Надежность. Является одним из основных качеств любого программногорешения. Соответственно есть необходимость создания надежных дисковыхсистем.Все это обусловило появление так называемых RAID систем. Вначале RAIDпереводили как избыточный массив недорогих дисков.
Со временем понятие RAIDсистемы изменилось и на сегодняшний день оно переводится как избыточныймассив независимых дисков.Итак, RAID система представляет собой набор независимых дисков, которыерассматриваются ОС как единое дисковое устройство, где данные представляютсяв виде последовательности записей, которые называются полосы. /*Полосыцилиндрически распределены по дисковому устройству.
*/Рассмотрим модели организации многодисковых систем, которые относятся кклассу RAID.Семь уровней RAID систем.RAID 0 (без избыточности)Не является настоящим RAID уровнем, поскольку не использует избыточность дляповышения эффективности.Пользовательские и системные данные распределяются по всем дискам массива.Это лучше, чем использовать один большой диск, так как появляется вероятностьтого, что дваразличных блока памяти, к которым поступили два различных запросаввода\вывода, размещены на различных дисках, вследствие чего эти два запросамогут обрабатываться параллельно.Все пользовательские и системные данные рассматриваются как хранящиеся наодном логическом диске. Диск делится на полосы, которые могут бытьфизическими блоками, селекторами или другими единицами хранения.
Полосыциклически размещаются на последовательных дисках массива. В n-дисковоммассиве первые n полос располагаются как первые полосы каждого из n дисков;вторые n- как вторые полосы каждого из n дисков и т.д.«+» Если один запрос ввода\вывода обращается к множеству логическипоследовательных полос, то параллельно может быть обработано до n полос.Уменьшается время обработки.RAID 1 (зеркалирование Предполагает наличие массивов устройств.
1ая группа –циклическое распределение устройств по уровням 2ая группа-копия первой. Записьидет параллельно и независимо)«+»1. Запрос на чтение может быть обслужен любым из двух дисков, содержащихнеобходимые данные; для обслуживания выбирается диск, у которогоминимальное время поиска.2.
Для запроса на запись необходимо обновление обеих полос, что может бытьвыполнено в параллельном режиме. Поэтому скорость записи определяетсясамой медленной из них (т.е. той, для которой время поиска оказываетсябольшим). Однако никаких дополнительных расходов на запись нетребуется.3. Простота восстановления данных в случае сбояRAID первого уровня это достаточно дорогостоящая конструкция, потому чтополучается двойное резервирование, но тем не менее эта система наиболее простоорганизована.RAID 2 избыточность с кодами Хэмминга (Hamming, исправляет одинарные ивыявляет двойные ошибки) Также используется разделение на полосы.
Полосыоказываются очень малыми; нередко они соответствуют одному байту или слову.Обмен с синхронизацией головок чтения записи. Часть дисковых устройствпредназначены для хранения содержательной части информации. Существуетнесколько дисковых устройств, в которых реализованы коды Хемминга.При считывании осуществляется одновременный доступ ко всем дискам. Данныезапроса и код коррекции ошибок передаются контролеру массива. При наличииоднобитовой ошибки контролер способен быстро ее откорректировать, так чтодоступ для чтения в этой схеме не замедляется.При записи происходит одновременное обращение ко всем дискам массива..
Имеют место 2 проблемы:1.Соответственно избыточность меньше, чем у RAID 1, но все равно онаприсутствует.2. Есть зависимые обмены, т.е. обмены, которые организованы наспециализированных движениях головок. И соответственно информация сильнораспределена по RAID массиву. Т.е. последовательная информация за счетмаленького размера полосок распределена. Т.е. одновременно происходитобращение ко всей цепочке. Т.е. нет независимых обменов в каждом дисковомустройстве.RAID 3 (четность с чередующимися битами) 4 диска содержательные – дляразмещения логических данных. 5ый – контрольная избыточная информация.Суть: Если представить, что модель RAID состоит из 5 дисков. В этих 5 дисках 4диска содержательные, т.е. для размещения логического диска ссоответствующими полосками.
5-й диск – это контрольная избыточнаяинформация. Содержимое пятого диска выражается по формулам черезсодержимое первых 4.То есть определенный разряд 5-го диска представляется как«исключающее или» для соответствующих ему содержательных разрядов. В случаегибели какого-нибудь из устройств утверждается, что информацию на этомустройстве можно восстановить по второй, приведенной ниже, формуле. Т.е. имеетместо избыточность, которая с одной стороны дает синхронизированныйпараллельный доступ, а с другой имеется функция, которая восстанавливаетинформацию в случае гибели устройства.Пример: 4 диска данных, один – четности:Потеря данных на первом дискеX4(i)=X3(i)XOR X2(i)XOR X1(i)XOR X0(i)X1(i)=X4(i)XOR X3(i)XOR X2(i)XOR X0(i)RAID 4Он не синхронизированный, т.е.
в этом плане он аппаратно организован проще,чем предыдущие. Схема примерно та же самая: имеется 4 устройства длялогического диска, на которых располагаются полосы, и 5-е устройство, в которомнаходятся контрольные суммы. Контрольная сумма вычисляется по той же самойформуле, что и в RAID 3. И здесь есть проблема работы в случае независимогообмена.Пример: 4 диска данных, один – четности:При независимом обмене происходит обновление следующим образом:предположим, что обновление произошло на первом диске.X4(i)=X3(i)XOR X2(i)XOR X1(i)XOR X0(i)все разряды на 4-м будут обновлены по следующей формуле:X4new(i)=X4(i)XOR X1(i)XOR X1new(i)Восстановление информации проходит по предыдущей схеме (это схемаобновления, потому что обмены могут быть независимыми, т.е.
обмен можетпроисходить только по одной полоске, но для этого необходимо скорректироватьсодержимое контрольной полоски и использовать ее для восстановления).RAID 5 (распределенная четность – циклическое распределение «четности»)RAID 5 - это использование циклического распределения контрольного диска.Суть: в RAID 3 и RAID 4 есть некоторая диспропорция в распределении потокаобмена, т.е. сильно нагружено последнее устройство (это плохо тем, что рано илипоздно это устройство выйдет из строя первым), на котором находитсяконтрольная сумма. Т.о. контрольный диск циклически распределен по всемустройствам, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
