Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Среднее время выполнения – 21.5 ед.

3.SSTF

П риоритет имеет обмен, для которого потребуется наименьшее время. «Жадный» алгоритм на каждом шаге пытается получить максимальный эффект. Общая нагрузка на систему с точки зрения обмена сокращается в 3 раза. Возможно «залипание» головки в том случае, если обмен идет интенсивно с одними и теми же дорожками. Некоторые процессы будут отделены.

4.LIFO

Смысл – попытка развязать последовательность обмена, связанную с новыми источниками.

Приоритетный алгоритм (RPI) – это алгоритм, когда последовательность обменов (очередь) имеет характеристику приоритетов. При использовании приоритетных алгоритмов может возникать проблема голодания или дискриминации. Проблема дискриминации возникает при непрерывном поступлении более приоритетных запросов на обмен, в это время как менее приоритетные запросы простаивают.

Находясь в начальной позиции сначала двигаемся в одну сторону до конца, затем в другую до конца.

Для " набора запросов

перемещений £ 2 х число_дорожек

Выходим на минимальную (максимальную дорожку, а затем движемся в одну сторону. Пройдем не более двух маршрутов.

N-step-SCAN

Разделение очереди на подочереди длины £ N запросов каждая (из соображений FIFO). Последовательная обработка очередей. Обрабатываемая очередь не обновляется. Обновление очередей, отличных от обрабатываемой.

Этот алгоритм срывает головку с залипания.

Распространенный пример: 2 очереди, одна обрабатывается, другая собирает вновь поступающие запросы.

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 (сравнение)

OC Unix: Работа с внешними устройствами

Файлы устройств, драйверы

Особенность UNIX- все устройства обслуживаются в системе виде файлов.

Характеристики

Список файлов лекций