 |
Алгоритмы сканирования (scan, c-scan, look, c-look)
|
|
|
|
В простейшем из алгоритмов сканирования scan головки постоянно перемещаются от одного края диска до другого, по ходу обслуживая все встречающиеся запросы. По достижении другого края диска направление движения меняется и все начинается снова. Предположим головки двигаются в направлении уменьшения номеров цилиндров. Последовательность перемещения головок будет выглядеть следующим образом: 63, 55, 31, 23, 14, 10, … 7, 0, 67, 84
Если нам известно что мы обслужили последний попутный запрос в направлении движения головок, то мы можем не доходить до края диска, а сразу изменять направления на обратное. Тогда: 63, 55, 31, 23, 14, 10, 7, 67, 84 (всего пройдено 133)
Получим модификацию алгоритма scan вносит название look.
Допустим что к моменту изменения направления движение головки в алгоритме scan (т.е. когда головка, у этого края находилось большое количество новых запросов, на обслуживание которых будет потрачено много времени, т.к. надо не только перемещать головку, но еще и перемещать прочитанные данные, тогда запросы относящиеся к другому краю диска и поступившие ранее будут ждать несправедливо долго).
Для сокращения времени ожидания применяется циклическое сканирование (c-scan), когда головка достигает 1го из краев диска она без чтения попутных запросов перемещается на другой край, откуда вновь начинает движение в прежнем направлении. Последовательность перемещений: 63, 55, 31, 23, 14, 10, 7, 0, 99, 84, 67
По аналогии с look для алгоритма scan можно предложить алгоритм c-look для алгоритма c-scan.
Последовательность: 62, 55, 31, 23, 14, 10, 7, 84, 67
Спулинг и захват устройств.
Спулинг рассматривается как механизм позволяющий совместить реальные операции ввода/вывода одного задания с выполнением другого задания, т.е. мы подразумеваем буфер (спул), кот содержит входные и выходные данные для устройств на котором следует избегать чередования его использования различными процессами. В современных системах спул для ввода данных практически не используется, а в основном предназначен для накопления выходной информации. Пример: в качестве внешнего устройства рассмотрим принтер, как мы знаем принтер не может печатать информацию поступающих одновременно от нескольких процессов, хотя может возникнуть такая ситуация когда желательно разрешить процессам совершать вывод на принтер параллельно, для этого ОС вместо передачи информации напрямую на принтер накапливает выводимые данные в буферах на диске, которые организованны в виде отдельного спул файлов для каждого процесса. Соответственно после завершения некоторого процесса соответствующий ему спул файл ставится в очередь для печати. Механизм который обеспечивает подобные действия получил названия спулинг. В некоторых ОС вместо использования спулинг применяется механизм монопольного захвата устройств процессами. Если устройство свободно, то один из процессов может получить его монопольное распоряжение. При этом все другие процессы при попытки осуществления операции над этим устройством будут либо блокированы, т.е. переведены в состояние ожидание, либо получит информацию о невозможности выполнения операций до тех пор пока захватившее его устройство не завершится или не сообщит ОС об отказе его использования или обслуживания. Обеспечение спулинга и механизма захвата устройств это прерогатива базовой подсистемы ввода/вывода.
|
|
|
Обработка прерываний и ошибок
Если при работе с внешним устройством система не использует метод опроса его состояния а задействует механизм прерываний, то при возникновении прерывания процессор частично сохранив свое состояние передает управление специальной программе обработке прерывания. Одна и та же процедура обработки прерывания может применятся для нескольких устройств ввода/вывода, поэтому первое действие программы обработки состоит в том, чтобы определить какое устройство выдало прерывание. Зная устройство можно выявить процесс кот инициировал выполнение соответствующей программы(операции),т.к. прерывание возникает как при удачном, так и не преудачном ее выполнении следующее что надо сделать определить успешность завершения операции, проверив значение бита ошибки в регистре состояния устройства. В некоторых случаях ОС может предпринять определенные действия направленные на компенсацию возникшей ошибки (например: в случаи возникновения ошибки чтения с гибкого диска можно попробовать несколько раз повторить выполнение команды). Если компенсация ошибки невозможна, то ОС в последствии известит процесс запросивший выполнение операции, если этот процесс был заблокирован до выполнения завершившейся операции, то ОС переводит его в состояние готовность. При наличии других не удовлетворенных(не выполненных) запросов к освободившемуся устройству ОС может инициировать выполнение следующего запроса, одновременно известив устройство, что прерывание обработано. На этом обработка прерывания заканчивается и система может приступить к планированию использования процессора. Действие по обработке прерывания и компенсации возникающих ошибок может быть частично переложено на плечи соответствующего драйвера. Для этого в состав интерфейса между драйвером и базовой подсистемой ввода/вывода добавляют еще одну функцию – функцию обработки прерывания intr.
|
|
|
Планирование запросов
При использовании не блокирующегося системного вызова может оказаться, что нужное устройство уже занято выполнением некоторых операций. В этом случаи не блокирующийся вызов может немедленно вернуться не выполнив запрошенных команд. При организации запроса на совершение операции ввода/вывода с помощью блокирующегося и асинхронного вызова занятость устройства приводит к необходимости постановки в очередь запроса к данному устройству. В результате с каждым устройством оказывается связан список неудовлетворенных запросов процессов находящихся в состоянии ожидания и запросов выполняющихся в асинхронном режиме. Состояние ожидание расщепляется на набор очередей процессов, дожидающихся различных устройств ввода/вывода. После завершения выполнения текущего запроса, ОС должна решить какой из запросов в списке должен быть удовлетворен следующим и инициировать его исполнение. Здесь необходимо осуществлять планирование применения устройств, пользуясь каким – либо алгоритмом этого планирования. Задача планирования использования устройства обычно возлагается на базовую подсистему ввода/вывода. Однако для некоторых устройств лучшие алгоритмы планирования могут быть тесно связаны с деталями их внутреннего функционирования. В таких случаях операция планирования переносится внутрь драйвера соответствующего устройства, т.к. эти детали скрыты от базовой подсистемы. Для этого в интерфейс драйвера добавляется еще одна специальная функция, которая осуществляет выбор очередного запроса – функция strategy.
|
|
|
Алгоритм планирования запросов к жесткому диску
Строение жесткого диска и параметры планирования
При планировании использования жесткого диска параметром планирования является время, которое потребуется для выполнения очередного запроса.
Время, которое необходимо для чтения или записи определенного сектора на определенной дорожке определенного цилиндра можно разделить на 2 составляющих:
1. Время обмена информации между магнитной головкой и компьютером, который не зависит от положения данных и определяется скоростью их передач, называется transfer speed
2. Время необходимое для позиционировании головки над заданным сектором, называется positioning time
Время позиционирования в свою очередь состоит из времени необходимого для перемещения головок над нужными цилиндрами seek time (время поиска) и времени, которое нужно для того чтоб новый сектор повернулся под головку rotational latency (задержка на вращения)
Времена поиска пропорциональны разнице между номера цилиндра предыдущего и планируемого запроса. Задержка на вращение определяется довольно сложным соотношениями между номерами цилиндров и секторов предыдущего и планируемого запросов и скоростями вращения диска и перемещения головок, поэтому набор параметров планирования сокращается до времени поиска различных запросов, определяемого текущим положением головки и номера требуемых цилиндров, разницей в задержках на вращении пренебрегают.
|
|
|
