Околения компьютеров
 Скачать 1.67 Mb.
|
|
Варианты решения 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 есть некоторая диспропорция в распределении потока обмена, т.е. сильно нагружено последнее устройство (это плохо тем, что рано или поздно это устройство выйдет из строя первым), на котором находится контрольная сумма. Т.о. контрольный диск циклически распределен по всем устройствам, т.е. вся работа равномерно распределяется. RAID 6 (двойная избыточность – циклическое распределение четности с использованием двух схем контроля: N+2 дисков) RAID 6 – это двойная избыточность. Делается еще одно дополнительное устройство для хранения избыточной информации. Какие-то из RAID массивов можно реализовать чисто программно. Какие-то из них можно реализовать только аппаратно. Какие-то из них можно реализовать в зависимости от решения. Это все относится к проблеме управления внешними устройствами: качеством и свойством работы внешних устройств в системе. Уровни RAID (сравнение) Категория Ур ов ен ь Описание Скорость обработки запросов Скорость передачи данных Типичное применение Расщепле ние 0 Без избыточно сти Большие полосы: отлично Малые полосы: отлично Приложения с некритическим и данными, требующие высокой производитель ности Зеркалиро вание 1 Зеркалиро вание Хорошо/ удовлетвор ительно удовлетвори тельно/ удовлетвори тельно Системные диски, важные файлы Параллель ный доступ 2 Избыточн ость с кодами Хэмминга Плохо Отлично 3 Четность с чередующ имися битами Плохо Отлично Приложения с большими запросами ввода/вывода (графич. редакторы, САПР) Независи мый доступ 4 Четность с чередующ имися блоками Отлично/ удовлетвор ительно Удовлетвори тельно/ плохо 5 Распредел енная четность с чередующ имися блоками Отлично/ удовлетвор ительно Удовлетвори тельно/ плохо Высокая скорость запросов, интенсивное чтение, поиск данных 6 Двойная распредел енная четность с чередующ имися блоками Отлично/пл охо Удовлетвори тельно/ плохо Приложения, требующие исключительн о высокой надежности Билет 48 OC Unix: Работа с внешними устройствами Файлы устройств, драйверы Особенность UNIX- все устройства обслуживаются в системе виде файлов. С точки зрения внутренней организации системы, как и в подавляющем большинстве других операционных систем, работа с внешними устройствами осуществляется посредством использования иерархии драйверов, которые позволяют организовывать взаимодействие ядра ОС с конкретными устройствами. В системе Unix существует единый интерфейс организации взаимодействия с внешними устройствами, для этих целей используются специальные файлы устройств, размещенные в каталоге /dev. Файл устройства позволяет ассоциировать некоторое имя (имя файла устройства) с драйвером того или иного устройства. Следует отметить, что здесь мы несколько замещаем понятие устройства понятием драйвер устройства, так как несмотря на то, что мы используем термин специальные файлы устройств, на практике, мы используем ассоциированный с данным специальным файлом драйвер устройства, и таких драйверов у одного устройства может быть произвольное число. Возможно, более удачным было бы использовать специальный файл-драйвер устройства. В системе существуют два типа специальных файлов устройств: - файлы байт-ориентированных устройств (драйверы обеспечивают возможность побайтного обмена данными и, обычно, не используют централизованной внутрисистемной кэш-буферизации ); - файлы блок-ориентированных устройств (обмен с данными устройствами осуществляется фиксированными блоками данных, обмен осуществляется с использованием специального внутрисистемного буферного кэша). Следует отметить, файловая система может быть создана только на блок- ориентированных устройствах. В общем случае тип файла определяется свойствами конкретного устройства и организацией драйвера. Конкретное физическое устройство может иметь, как байт- ориентированные драйверы драйверы, так и блок-ориентированные. Например, если рассмотреть физическое устройство Оперативная память, для него можно реализовать, как байт-ориентированный интерфейс обмена (и соответствующий байт-ориентированный драйвер), так и блок-ориентированный. Содержимое файлов устройств размещается исключительно в соответствующем индексном дескрипторе, структура которого для файлов данного типа, отличается от структуры индексных дескрипторов других типов файлов. Итак индексный дескриптор файла устройства содержит: - тип файла устройства – байт-ориентированный или блок-ориентированный; - «старший номер» (major number) устройства - номер драйвера в соответствующей таблице драйверов устройств; - «младший номер» (minor number) устройства – служебная информация, передающаяся драйверу устройства. Система поддерживает две таблицы драйверов устройств. bdevsw – таблица драйверов блок-ориентированных устройств. cdevsw - таблица байт-ориентированных устройств. Выбор конкретной таблицы определяется типом файла устройства. Соответственно, поле старший номер определяет строку таблицы с которой ассоциирован драйвер устройства. Драйверу устройства может быть передана дополнительная информация через поле младший номер это может быть, например, номер конкретного однотипного устройства или некоторая информация, определяющая дополнительные функции драйвера Каждая запись этих таблиц содержит так называемый коммутатор устройства – структуру, в которой размещены указатели на соответствующие точки входа (функции) драйвера. Таким образом, в системе определяется базовый уровень взаимодействия с драйвером устройства (конкретный состав точек входа определяется конкретной версией системы). В случае, если конкретный драйвер устройства не поддерживает работу с той или иной точкой входа, на ее место устанавливается специальная ссылка-заглушка на точку ядра. В качестве примера, рассмотрим типовой набор точек входа в драйвер (b - префикс точки входа, характеризующий конкретный драйвер): - bopen() открытие устройства, обеспечивается инициализация устройства и внутренних структур данных драйвера; - bclose() закрытие драйвера устройства, например в том случае, если ни один из процессов не работает с драйвером; - bread() чтение данных; - bwrite() запись данных; - bioctl() управление устройством, задание режимов работы драйвера, определение набора внутренних операций/команд драйвера; - bintr() – обработка прерывания, вызывается ядром при возникновении прерывания в устройстве с которым ассоциирован драйвер; - bstrategy() управление стратегией организации блок-ориентированного обмена (некоторые функции оптимизации организации обмена, обработка специальных ситуаций, связанных с функционированием конкретного устройства и т.п.). Так в некоторых реализациях системы возможно отсутствие точек входа чтения и записи для блок-ориентированных устройств. В этом случае блок- ориентированный обмен реализуются путем передачи управления на точу bstrategy(). В системе возможно обращение к функциям драйвера в следующих ситуациях: 1. старт системы, определение ядром состава доступных устройств. 2. обработка запроса ввода/вывода (запрос может быть инициирован, любыми процессами, в том числе и ядром); 3. обработка прерывания, связанного с данным устройством, в этом случае ядро вызывает специальную функцию драйвера; 4. выполнение специальных команд управления (например, остановка устройства, приведение устройства в некоторое начальное состояние и т.п.). Существует два, традиционных способа включения драйверов новых устройств в систему: путем «жесткого», статического встраивания драйвера в код ядра, требующего перекомпиляцию исходных текстов ядра или пересборку объектных модулей ядра. за счет динамического включения драйвера в систему. Динамическое включение драйверов в систему предполагает выполнение следующей последовательности действий: - загрузка и динамическое связывание драйвера с кодом ядра (выполняется специальным загрузчиком); - инициализация драйвера и соответствующего ему устройства (создание специальных структур данных драйвера, формирование данных коммутатора устройства, связывание обработчика прерываний ядра с данным драйвером). Для обеспечения динамического включения/выключения драйверов предоставляется набор системных вызовов, обеспечивающий установку и удаление драйверов в систему. Билет 49. Внешние устройства в ОС UNIX. Системная организация обмена с файлами. Буферизация обменов с блокоориентированными устройствами. На практике, наиболее часто мы имеем дело с обменами, связанными с доступом к содержимому обыкновенных файлов. Рассмотрим обобщенную схему организации обмена данными с файлами, т.е. внутреннюю организацию программ и данных, обеспечивающих доступ к содержимому файловой системы (файловая система может быть создана исключительно на блок-ориентированных устройствах). Рассмотрим ряд информационных структур и таблиц, используемых системой для организации интерфейса работы с файлами. Для организации интерфейса работы с файлами ОС использует информационные структуры и таблицы двух типов: - ассоциированные с процессом; - ассоциированные с ядром операционной системой. Таблица индексных дескрипторов открытых файлов. Для каждого открытого в рамках системы файла формируется запись в таблице ТИДОФ, содержащая: копия индексного дескриптора (ИД) открытого файла; кратность - счетчик открытых в системе файлов, связанных с данным ИД. Вся работа с содержимым открытых файлов происходит посредством использования копии ИД, размещенной в таблице ТИДОФ. Данная таблица размещается в памяти ядра ОС. Если один и тот же файл открыт неоднократно, то запись в ТИДОФ создается одна, но каждое дополнительное открытие этого файла увеличивает счетчик на единицу |