какие существуют требования к способу выполнения цепей ввода вывода информации в устройства асду
Архитектура ЭВМ
Компоненты ПК
Интерфейсы
Мини блог
Самое читаемое
Ввод-вывод
Требования к организации и решения систем ввода-вывода
Организация взаимодействия и обмена информации в вычислительной информационной системе требует решения целого ряда проблем, среди которых выделим следующие:
Указанные требования решаются за счет:
Интерфейс — это совокупность программных и аппаратных средств, предназначенных для передачи информации между компонентами ЭВМ и включающих в себя электронные схемы, линии, шины и сигналы адресов, данных и управления, алгоритмы передачи сигналов и правила интерпретации сигналов устройствами. Интерфейсы характеризуются следующими параметрами:
Основным назначением интерфейса является унификация внутрисистемных и межсистемных связей и устройств сопряжения с целью эффективной реализации прогрессивных методов проектирования функциональных элементов вычислительных систем.
Основными архитектурами соединений устройств являются:
Схема магистрально-модульного соединения
На интерфейсные схемы модулей возлагаются следующие задачи:
Эти интерфейсные схемы могут быть достаточно сложными и по своим возможностям соответствовать универсальным микропроцессорам. Такие схемы принято называть контроллерами.
Унификация программирования достигается за счет унифицированных форматов команд в ЭВМ и унифицированных форматов регистров ПУ. На уровне операционной системы унификация достигается путем использования драйверов внешних устройств.
ОРГАНИЗАЦИЯ ВВОДА-ВЫВОДА ИНФОРМАЦИИ В МИКРОПРОЦЕССОРНЫХ СИСТЕМАХ.
В предыдущей статье раздела читатель познакомился с основными периферийными устройствами, предназначенными для организации ввода-вывода информации. Несмотря на многообразие этих устройств, существуют стандартные методы обмена информацией между ними и микропроцессором, а также типовые способы их подключения.
Обмен информацией между внешними устройствами и микропроцессорной системой может быть организован тремя способами: программным, по прерываниям, в режиме прямого доступа.
Программный ввод-вывод инициируется и управляется микропроцессором. Внешние устройства при этом могут лишь сигнализировать о своем состоянии, показывая готовность (неготовность) к приему или передаче.
Ввод-вывод по прерываниям происходит под управлением внешнего устройства. При готовности принять или передать информацию внешнее устройство подает микропроцессору сигнал запроса прерывания INT. Поэтому сигналу прекращается выполнение основной программы, и процессор переходит к реализации специальной подпрограммы управления обменом данными. После ее окончания система продолжает работать по основной программе.
Обмен данными в режиме прямого доступа в память характеризуется тем, что по сигналу требования захвата HOLD микропроцессор, отключается от системных шин, предоставляя их внешнему устройству. Последнее может обращаться к основной памяти системы, минуя микропроцессор. Рассмотрим эти способы подробнее. Но прежде обратим внимание на следующее. Из-за разного быстрого действия микропроцессорной системы и внешних устройств процессор может оказаться готовым к приему или выдаче данных, в то время как внешнее устройство еще не успеет обработать данные, полученные ранее. В такой ситуации возникает необходимость синхронизировать их работу. Иначе говоря, нужно заставить более быстрое устройство ждать до того момента, пока медленное не закончит обработку данных и подаст сигнал готовности. Более того, для большинства внешних устройств перед началом ввода-вывода необходима проверка готовности к обмену данными. Такой способ передачи данных называют синхронным или вводом-выводом с квитированием.
Некоторые внешние устройства, например светодиодные индикаторы, всегда готовы к приему информации и специальных сигналов проверки их готовности не требуется. В таких случаях ввод-вывод называют асинхронным.
Информация, передаваемая между микропроцессорной системой и внешними устройствами, может быть разделена на управляющие сигналы и данные. Управляющие сигналы от периферийного устройства принято называть сигналами состояния. Совокупность сигналов состояния или слово состояния сообщает микропроцессору о готовности внешнего устройства к обмену, а также о наличии ошибок при обмене, запроса прерывания и др.
Управляющие сигналы от микропроцессорной системы или командные слова инициируют действия, STBD в 0 и переходит к выполнению основной программы.
Как только внешнее устройство закончит обработку полученной информации, оно вновь вырабатывает сигнал RDU = 0 и ждет новую порцию данных, которые могут появиться в результате выполнения основной программы.
DQ — сигнал запроса данных, вырабатываемый процессором; RDY — сигнал готовности внешнего устройства выдать данные.
Нетрудно заметить, что при отсутствии сигнала RDY система занята только анализом его состояния.
Эта подпрограмма занимает в памяти 31 байт, а время ее выполнения зависит от быстродействия внешнего устройства и может быть довольно большим. Отсюда виден недостаток программного асинхронного ввода-вывода — микропроцессорная система значительную часть времени простаивает, ожидая сигнал готовности от внешнего устройства и не выполняя никаких полезных действий.
К достоинствам программного ввода-вывода можно отнести достаточно простую аппаратную реализацию.
Организация ввода-вывода по прерываниям сокращает время непроизводительных простоев процессора, но требует дополнительных аппаратурных затрат. При использовании такого способа чередуется выполнение основной программы и подпрограммы ввода-вывода. Внешнее устройство, готовое к обмену, выдает сигнал запроса прерывания на вход специального блока приоритетных прерываний, например, К589ИК14 или программируемого контроллера прерываний, о котором пойдет речь в следующей статье. Эти блоки выдают на вход INT микропроцессора сигналы запроса прерывания. Если прерывание разрешено, на выходе INTE микропроцессора присутствует логическая 1, и он принимает код команды RST N или CALL ADDR.
Напомним, что в процессе выполнения указанных команд микропроцессор загружает в стек текущее значение счетчика команд, а в счетчик — начальный адрес подпрограммы обслуживания прерывания, по которой реализуется управление вводом-выводом.
Команда RET, стоящая в конце подпрограммы обслуживания прерывания, извлекает из стека и загружает в счетчик команд старое значение, тем самым вызывая продолжение основной программы.
Запрещая или разрешая прерывания с помощью команд DI и EI, можно запрещать или разрешать процессору общение с устройствами ввода-вывода. Иногда саму подпрограмму реализации обмена начинают с команды D1 и заканчивают командой EI для того, чтобы другое прерывание с более высоким приоритетом «не отвлекало» микропроцессорную систему от обслуживания данного внешнего устройства. Такая процедура может привести к потере поступивших запросов прерывания более высокого приоритета от быстродействующих устройств. Если это недопустимо, то команду DI использовать нельзя, так как должна существовать возможность многоуровневого прерывания, при котором происходит вложение подпрограммы ввода-вывода.
При прерываниях с использованием команды RST для подпрограммы обслуживания обмена отводится только 8 байт. Если такая подпрограмма требует большего количества ячеек памяти, то в начале 8-баитовой области, определяемой RST N, располагают команду безусловного перехода IMP ADDR по адресу, который соответствует подпрограмме обслуживания прерывания.
В тех случаях, когда подпрограмма изменяет содержимое регистров и признаков, рекомендуется в начале подпрограммы заносить в стек их содержимое, а в конце восстанавливать его.
Большинство микроЭВМ имеют в составе своего математического обеспечения набор подпрограмм для выполнения операций ввода-вывода с использованием стандартных периферийных устройств. Такие подпрограммы иногда называют драйверами. Например, драйвер вывода для дисплея может выводить на экран из аккумулятора один символ или содержимое определенной области памяти.
Приведем пример подпрограммы ввода информации с клавиатуры по прерыванию и ее записи по адресу, хранящемуся в ВС.
Эта подпрограмма занимает в памяти 7 байт и выполняется за 52 машинных такта, что существенно меньше времени реакции человека. Иначе говоря, реализация такой подпрограммы не внесет неудобств в работу оператора. Чтобы исключить возможность повторного считывания одинаковых данных, нужно в начале обмена сбрасывать сигнал запроса прерывания от клавиатуры, например, сигналом INTE («Подтверждение прерывания») от микропроцессора. Разумеется, дребезг контактов клавиатуры в таком случае должен быть исключен, например, аппаратно.
Обратим внимание на то, что во всех рассмотренных процедурах обмена данные сначала записываются в аккумулятор микропроцессора, а потом передаются в память системы или во внешнее устройство. Естественно, что такая двухступенчатая передача, особенно при большой длине блоков информации, становится неэффективной по времени. Здесь на помощь приходит режим прямого доступа в память. Иначе говоря, быстродействующему устройству предоставляется право обмениваться данными с памятью, минуя микропроцессор.
Режим прямого доступа в память в микропроцессорных системах на базе КР580ИК80А реализуется следующим образом. Внешнее устройство подает на вход микропроцессора HOLD («Требование захвата») запрос для предоставления ему шины системы для обмена с памятью. Процессор отвечает сигналом HLDA («Подтверждение захвата») и переводит шины адреса и данных в высокоимпедансное состояние, одновременно устанавливая на своих управляющих выходах (кроме WR и HLDA) уровни логического 0. Получив сигнал HLDA, внешнее устройство вырабатывает необходимые управляющие сигналы, выдает на шину адреса адрес первой ячейки памяти и начинает обмен. Состояние захвата возможно только в том случае, если на входе READY («Готовность») микропроцессора присутствует напряжение логической 1. Переход в состояние захвата происходит в такте ТЗ машинного цикла «Чтение памяти» или в следующем за ним такте, если выполняется машинный цикл «Запись в память».
Заметим, что для организации режима прямого доступа в память существует программируемый контроллер КР580ВТ57, представляющий специализированный четырехканальный процессор. Его описание будет дано в одной из следующих статей раздела.
Применение режима прямого доступа в память наиболее эффективно с точки зрения временных затрат.
При реализации простых микропроцессорных систем процедуру, эквивалентную программному вводу-выводу с квитированием, иногда удобнее реализовать аппаратурным путем, используя режим ожидания микропроцессора. При этом внешнее устройство выдает на вход READY микропроцессора управляющий сигнал, свидетельствующий о готовности к обмену. Если на входе READY появится напряжение логического 0, то микропроцессор отвечает сигналом WAIT («Ожидание») и выполняет целое число тактов ожидания, во время которых состояния шин адреса, данных и управления микропроцессора не меняются и соответствуют их состояниям в такте ТЗ.
При появлении на входе READY уровня логической 1 микропроцессор переходит от выполнения тактов ожидания к продолжению рабочих машинных тактов выполняемой команды.
Реализация ввода-вывода с аппаратным анализом сигнала готовности от внешнего устройства освобождает от необходимости программного опроса этого сигнала и, следовательно, создает экономию памяти за счет сокращения подпрограмм ввода-вывода. Но этот способ, как и программный ввод-вывод с квитированием, имеет тот же недостаток — непроизводительное использование микропроцессора во время ожидания ответа от внешнего устройства. Кроме того, при подключении нескольких внешних устройств аппаратная сложность значительно возрастает.
Режим ожидания наиболее часто применяют при работе с «медленной» полупроводниковой памятью, которая все же во много раз быстрее типового внешнего устройства. Время цикла обращения к такой памяти ненамного превышает время реакции микропроцессора. Этот режим очень удобно использовать при отладке микропроцессорных систем, так как при этом можно легко контролировать состояние всех шин системы, например, простым логическим пробником.
Как уже отмечалось в начале статьи, большое влияние на эффективность обмена данными оказывают способы подключения внешних устройств. Поясним два наиболее широко применяющихся способа, один из которых основан на подключении внешних устройств через подсистему ввода-вывода, второй — через подсистему памяти. Эти способы иногда называют соответственно изолированным и совмещенным вводом-выводом.
При изолированном вводе-выводе микропроцессор способен адресовать 256 устройств ввода, столько же устройств вывода и память объемом 64 Кбайт. Реализация этого способа требует включения в состав микропроцессорной системы системного контроллера, вырабатывающего сигналы ВВОД и ВЫВОД. Такой контроллер, выполненный на микросхемах средней степени интеграции, был рассмотрен ранее. Отметим, что в настоящее время уже появилась БИС КР580ВК28, выполняющая функции системного контроллера и шинного формирователя, которая предназначена для систем на базе процессора серии КР580.
При совмещенном вводе-выводе внешние устройства адресуются как ячейки памяти с использованием сигналов WR («Запись в память») и DBIN («Чтение памяти»). Обращение к внешним устройствам происходит по командам обращения к памяти. Такой способ организации ввода-вывода ведет к сокращению адресного пространства, предназначенного для памяти, за счет адресации внешних устройств. При этом, с одной стороны, можно отказаться от использования контроллера состояний, а с другой — может существенно усложниться дешифрация адреса.
Замена инструкций OUT и IN командами обращения к памяти повышает гибкость программирования обмена. При этом появляется возможность обращения внешнего устройства не только к аккумулятору, но и к любому регистру общего назначения или ячейке памяти, совмещения ввода-вывода с выполнением арифметико-логической операции, программного вычисления адреса внешнего устройства. Это невозможно при использовании команд OUT и IN, где адрес является непосредственным операндом. Программа ввода-вывода при таком способе обычно короче, а число подключаемых внешних устройств но сравнению с изолированным вводом-выводом может быть значительно увеличено.
Интересно отметить, что наличие в микропроцессоре КР580ИК80А косвенной адресации позволяет использовать шину адреса для выдачи данных, хранящихся в регистровых парах. Это удобно при подключении к микропроцессорной системе внешних устройств, разрядность которых превышает длину машинного слова микропроцессора. Например, выдача из процессора во внешнее устройство 24-разрядной информации может быть выполнена всего за одну команду 2-байтной пересылки данных PUSH RP, причем два байта выдаются по шине данных последовательно во времени, а третий передается по шине адреса. Оставшаяся половина адресных разрядов используется по прямому назначению. В этом случае внешнее устройство занимает адресное пространство, соответствующее 256 ячейкам памяти. Однако потеря памяти компенсируется более высокой скоростью обмена. Кроме того, появляется возможность выдавать данные по шине адреса одновременно с приемом информации по шине данных, что оказывается полезным при обмене информацией между микропроцессорной системой и быстродействующими функциональными преобразователями.
Длина этой программы 7 байт, время выполнения 37 тактов.
Рассмотрев общие принципы сопряжения микропроцессора с внешними устройствами, предложим читателю самостоятельно разработать схему подключения 24-разрядного устройства вывода информации и написать для нее программу обмена данными. Основным критерием разработки должно быть минимальное время выполнения программы выдачи данных.
Какие существуют требования к способу выполнения цепей ввода вывода информации в устройства асду
Глава 13. Система управления вводом-выводом
Функционирование любой вычислительной системы обычно сводится к выполнению двух видов работы: обработке информации и операций по осуществлению ее ввода-вывода. Поскольку в рамках модели, принятой в этом курсе, все, что выполняется в вычислительной системе, организовано как набор процессов, эти два вида работы выполняются процессами. Процессы занимаются обработкой информации и выполнением операций ввода-вывода.
Содержание понятий “обработка информации” и “операции ввода-вывода” зависит от того, с какой точки зрения мы смотрим на них. С точки зрения программиста под “обработкой информации” понимается выполнение команд процессора над данными, лежащими в памяти независимо от уровня иерархии – в регистрах, кэше, оперативной или вторичной памяти. Под “операциями ввода-вывода” программист понимает обмен данными между памятью и устройствами, являющимися внешними по отношению к памяти и процессору, такими как магнитные ленты, диски, монитор, клавиатура, таймер. С точки зрения операционной системы “обработкой информации” являются только операции, совершаемые процессором над данными, находящимися в памяти на уровне иерархии не ниже, чем оперативная память. Все остальное относится к “операциям ввода-вывода”. Чтобы совершить операции над данными, временно расположенными во вторичной памяти, операционная система, как мы обсуждали в части III нашего курса, сначала производит их подкачку в оперативную память, а лишь затем процессор совершает необходимые действия.
Рассмотрение того, что именно делает процессор при обработке информации, как он решает задачу и какой алгоритм выполняет, не входит в задачи нашего курса. Это скорее относится к курсу “Алгоритмы и структуры данных”, с которого обычно начинается изучение информатики. Как операционная система управляет обработкой информации, мы разобрали в части II, в деталях описав два состояния процессов – исполнение (а что его описывать то?) и готовность (очереди планирования и т.д.), а также правила, по которым осуществляется перевод процессов из одного состояния в другое (алгоритмы планирования процессов).
Прежде чем говорить о работе операционной системы при осуществлении операций ввода-вывода, нам придется вспомнить часть сведений из курса “Архитектура современных ЭВМ и язык ассемблера”, чтобы понять, как осуществляется передача информации между оперативной памятью и внешним устройством, и почему для подключения к вычислительной системе новых разнообразных устройств ее не требуется перепроектировать.
13.1 Физические принципы организации ввода-вывода.
13.1.1. Общие сведения об архитектуре компьютера.
Шину данных, состоящую из линий данных и служащую для передачи информации между процессором и памятью, процессором и устройствами ввода-вывода, памятью и внешними устройствами.
Адресную шину, состоящую из линий адреса и служащую для задания адреса ячейки памяти или указания устройства ввода-вывода, участвующих в обмене информацией.
Шину управления, состоящую из линий управления локальной магистралью и линий ее состояния, определяющих поведение локальной магистрали. В некоторых архитектурных решениях линии состояния выносятся из этой шины в отдельную шину состояния.
Количество линий, входящих в состав шины, принято называть разрядностью ( шириной ) этой шины. Ширина адресной шины, например, определяет максимальный размер оперативной памяти, которая может быть установлена в вычислительной системе. Ширина шины данных определяет максимальный объем информации, которая за один раз может быть получена или передана по этой шине.
Операции обмена информацией осуществляются при одновременном участии всех шин. Рассмотрим, к примеру, действия, которые должны быть выполнены для передачи информации из процессора в память. В простейшем случае необходимыми являются три действия:
На адресной шине процессор должен выставить сигналы, соответствующие адресу ячейки памяти, в которую будет осуществляться передача информации.
На шину данных процессор должен выставить сигналы, соответствующие информации, которая должна быть записана в память.
После выполнения действий 1 и 2 на шину управления выставляются сигналы, соответствующие операции записи и работе с памятью, что приведет к занесению необходимой информации по требуемому адресу.
Естественно, что приведенные выше действия являются необходимыми, но недостаточными при рассмотрении работы конкретных процессоров и микросхем памяти. Конкретные архитектурные решения могут требовать дополнительных действий, например, выставления на шину управления сигналов частичного использования шины данных (для передачи меньшего количества информации, чем позволяет ширина этой шины), выставления сигнала готовности магистрали после завершения записи в память, разрешающего приступить к новой операции, и т.д., однако общие принципы выполнения операции записи в память остаются одинаковыми.
В то время как память легко можно представить себе в виде последовательности пронумерованных адресами ячеек, локализованных внутри одной микросхемы или набора микросхем, подобный подход неприменим к устройствам ввода-вывода. Внешние устройства разнесены пространственно и могут подключаться к локальной магистрали в одной точке или множестве точек, получивших название портов ввода-вывода. Тем не менее, точно так же, как ячейки памяти взаимно однозначно отображались в адресное пространство памяти, порты ввода-вывода можно взаимно однозначно отобразить в другое адресное пространство – адресное пространство ввода-вывода. При этом каждый порт ввода-вывода получает свой номер или адрес в этом пространстве. В некоторых случаях, когда адресное пространство памяти (размер которого определяется шириной адресной шины) задействовано не полностью (остались адреса, которым не соответствуют физические ячейки памяти), и протоколы работы с внешним устройством совместимы с протоколами работы с памятью, часть портов ввода-вывода может быть отображена непосредственно в адресное пространство памяти (так, например, поступают с видеопамятью дисплеев), правда тогда эти порты уже не принято называть портами. Надо отметить, что при отображении портов в адресное пространство памяти для организации доступа к ним в полной мере могут быть задействованы существующие механизмы защиты памяти без организации специальных защитных устройств.
В ситуации прямого отображения портов ввода-вывода в адресное пространство памяти действия, требуемые для записи информации и управляющих команд в эти порты или для чтения данных из них и их состояний, ничем не отличаются от действий, производимых для передачи информации между оперативной памятью и процессором, и для их выполнения применяются те же самые команды. Если же порт отображен в адресное пространство ввода-вывода, то процесс обмена информацией инициируется специальными командами ввода-вывода и включает в себя несколько другие действия. Например, для передачи данных в порт необходимо выполнить следующее:
На адресной шине процессор должен выставить сигналы, соответствующие адресу порта, в который будет осуществляться передача информации, в адресном пространстве ввода-вывода.
На шину данных процессор должен выставить сигналы, соответствующие информации, которая должна быть передана в порт.
После выполнения действий 1 и 2 на шину управления выставляются сигналы, соответствующие операции записи и работе с устройствами ввода-вывода (переключение адресных пространств!), что приведет к передаче необходимой информации в требуемый порт.
Современные вычислительные системы могут иметь разнообразную архитектуру, множество шин и магистралей, мосты для перехода информации от одной шины к другой и т.п. С точки зрения нашего рассмотрения важными является только следующие моменты:
Устройства ввода-вывода подключаются к системе через порты.
Могут существовать два адресных пространства: пространство памяти и пространство ввода-вывода.
Порты, как правило, отображаются в адресное пространство ввода-вывода и, иногда, непосредственно в адресное пространство памяти.
Использование того или иного адресного пространства определяется типом команды, выполняемой процессором, или типом ее операндов.
Физическим управлением устройством ввода-вывода, передачей информации через порт, и выставлением некоторых сигналов на магистрали занимается контроллер устройства.
Именно единообразие подключения внешних устройств к вычислительной системе является одной из составляющих идеологии, позволяющих добавлять новые устройства без перепроектирования всей системы.
13.1.2. Структура контроллера устройства.
Регистр состояния содержит биты, значение которых определяется состоянием устройства ввода-вывода, и которые доступны только для чтения вычислительной системой. Эти биты индицируют завершение выполнения текущей команды на устройстве ( бит занятости ), наличие очередного данного в регистре выходных данных ( бит готовности данных ), возникновения ошибки при выполнении команды ( бит ошибки ) и т.д.
Регистр управления получает данные, которые записываются вычислительной системой для инициализации устройства ввода-вывода или выполнения очередной команды, а также изменения режима работы устройства. Часть битов в этом регистре может быть отведена под код выполняемой команды, часть битов кодировать режим работы устройства, бит готовности команды свидетельствует о том, что можно приступить к ее выполнению.
Регистр выходных данных служит для помещения в него данных для чтения вычислительной системой, а регистр входных данных предназначен для помещения в него информации, которая должна быть выведена на устройство. Обычно емкость этих регистров не превышает ширину линии данных (а чаще всего меньше ее), хотя некоторые контроллеры могут использовать в качестве регистров очередь FIFO для буферизации поступающей информации.
Разумеется, набор регистров и составляющих их битов является приблизительным, он призван послужить нам моделью для описания процесса передачи информации от вычислительной системы к внешнему устройству и обратно, но в том или ином виде он обычно присутствует во всех контроллерах устройств.
13.1.3. Опрос устройств и прерывания. Исключительные ситуации и системные вызовы
Контроллер анализирует код команды в регистре управления и обнаруживает, что это команда вывода. Он берет данные из регистра входных данных и инициирует выполнение команды.
При успешном завершении операции контроллер обнуляет бит ошибки в регистре состояния, при неудачном завершении команды устанавливает его.
В простейшем случая для реализации механизма прерываний необходимо к имеющимся у нас шинам локальной магистрали добавить еще одну линию, соединяющую процессор и устройства ввода-вывода – линию прерываний. По завершении выполнения операции внешнее устройство выставляет на эту линию специальный сигнал, по которому процессор после выполнения очередной команды (или после завершения очередной итерации при выполнении цепочечных команд, т.е. команд, повторяющихся циклически со сдвигом по памяти) изменяет свое поведение. Вместо выполнения очередной команды из потока команд, он частично сохраняет содержимое своих регистров и переходит на выполнение программы обработки прерывания, расположенной по заранее оговоренному адресу. При наличии только одной линии прерываний процессор при выполнении этой программы должен опросить состояние всех устройств ввода-вывода, чтобы определить от какого именно устройства пришло прерывание (polling прерываний!), выполнить необходимые действия (например, вывести в это устройство очередную порцию информации или перевести соответствующий процесс из состояния ожидание в состояние готовность ) и сообщить устройству, что прерывание обработано (снять прерывание).
В большинстве современных компьютеров процессор стараются полностью освободить от необходимости опроса внешних устройств, в том числе и от определения с помощью опроса устройства, сгенерировавшего сигнал прерывания. Устройства сообщают о своей готовности процессору не напрямую, а через специальный контроллер прерываний, при этом для общения с процессором он может использовать не одну линию, а целую шину прерываний. Каждому устройству присваивается свой номер прерывания, который при возникновении прерывания контроллер прерывания заносит в свой регистр состояния и, возможно, после распознавания процессором сигнала прерывания и получения от него специального запроса, выставляет на шину прерываний или шину данных для чтения процессором. Номер прерывания обычно служит индексом в специальной таблице прерываний, лежащей по адресу, задаваемому при инициализации вычислительной системы, и содержащей адреса программ обработки прерываний – вектора прерываний. Для распределения устройств по номерам прерываний необходимо, чтобы от каждого устройства к контроллеру прерываний шла специальная линия, соответствующая одному номеру прерывания. При наличии множества устройств, такое подключение становится невозможным, и на один проводник (один номер прерывания) подключается несколько устройств. В этом случае процессор при обработке прерывания все равно вынужден заниматься опросом устройств для определения устройства, выдавшего прерывание, но в существенно меньшем объёме. Обычно при установке в систему нового устройства ввода-вывода требуется аппаратно или программно определить, каким будет номер прерывания, вырабатываемый этим устройством.
Когда мы с вами рассматривали кооперацию процессов и взаимоисключения, мы говорили о существовании критических секций внутри ядра операционной системы, при выполнении которых необходимо исключить всякие прерывания от внешних устройств. Для запрещения прерываний, а, точнее, для невосприимчивости процессора к внешним прерываниям, обычно существуют специальные команды, которые могут маскировать (запрещать) все или некоторые из прерываний устройств ввода-вывода. В то же время, определенные кризисные ситуации в вычислительной системе (например, неустранимый сбой в работе оперативной памяти), должны требовать ее немедленной реакции. Такие ситуации вызывают прерывания, которые невозможно замаскировать или запретить и которые поступают в процессор по специальной линии шины прерываний, называемой линией немаскируемых прерываний (NMI – Non-Maskable Interrupt).
Не все внешние устройства являются одинаково важными с точки зрения вычислительной системы (“все животные равны, но некоторые равнее других”). Соответственно, некоторые прерывания являются более существенными, чем другие. Контроллер прерываний обычно позволяет устанавливать приоритеты для прерываний от внешних устройств. При почти одновременном возникновении прерываний от нескольких устройств (во время выполнения одной и той же команды процессора), процессору сообщается номер наиболее приоритетного прерывания, для его обслуживания в первую очередь. Менее приоритетное прерывание при этом не пропадает, о нем процессору будет доложено после обработки более приоритетного прерывания. Более того, при обработке возникшего прерывания процессор может быть извещен о возникновении прерывания с более высоким приоритетом, и переключиться на его обработку.
Механизм обработки прерываний, по которому процессор прекращает выполнение команд в обычном режиме и, частично сохранив свое состояние, ответвляется на выполнение других действий, оказался настолько удобен, что зачастую разработчики процессоров используют их и для других целей. Хотя эти случаи и не относятся к операциям ввода-вывода, мы вынуждены упомянуть их здесь, для того, чтобы их не путали с прерываниями. Похожим образом процессор обрабатывает исключительные ситуации и программные прерывания.
Для внешних прерываний характерны следующие особенности:
Внешнее прерывание обнаруживается процессором между выполнением команд (или между итерациями в случае выполнения цепочечных команд).
Процессор при переходе на обработку прерывания сохраняет часть своего состояния перед выполнением следующей команды.
Исключительные ситуации возникают во время выполнения процессором команды. К их числу относятся ситуации переполнения, деления на ноль, обращения к отсутствующей странице памяти (см. часть III) и т.д. Для исключительных ситуаций характерно следующее:
Исключительные ситуации обнаруживаются процессором во время выполнения команд.
Процессор при переходе на выполнение исключительной ситуации сохраняет часть своего состояния перед выполнением текущей команды.
Исключительные ситуации возникают синхронно с работой процессора, но непредсказуемо для программиста, если только тот специально не заставил процессор делить некоторое число на ноль.
Программные прерывания возникают после выполнения специальных команд, как правило, для выполнения привилегированных действий внутри системных вызовов. Программные прерывания имеют следующие свойства:
Программное прерывание происходит в результате выполнения специальной команды.
Процессор при выполнении программного прерывания сохраняет свое состояние перед выполнением следующей команды.
Программные прерывания, естественно, возникают синхронно с работой процессора и абсолютно предсказуемы программистом.
Надо честно сказать, что похожие механизмы обработки внешних прерываний, исключительных ситуаций и программных прерываний лежат целиком на совести разработчиков процессоров. Существуют вычислительные системы, где все эти три ситуации обрабатываются по-разному.
13.1.4. Прямой доступ к памяти (Direct Memory Access – DMA).
Использование механизма прерываний позволяет разумно загружать процессор в то время, когда устройство ввода-вывода занимается своей работой. Однако запись или чтение большого количества информации из адресного пространства ввода-вывода (например, с диска) приводят к большому количеству операций ввода-вывода, которые должен совершать процессор. Для разгрузки процессора от операций последовательного вывода данных из оперативной памяти или последовательного ввода в нее был предложен механизм прямого доступа внешних устройств к памяти – ПДП или Direct Memory Access – DMA. Давайте кратко рассмотрим, как работает этот механизм.
Для того чтобы какое-либо устройство помимо процессора могло записать информацию в память или прочитать ее из памяти, необходимо чтобы это устройство могло забрать у процессора управление локальной магистралью для выставления соответствующих сигналов на шины адреса, данных и управления. Для централизации эти обязанности обычно возлагаются не на каждое устройство в отдельности, а на специальный контроллер – контроллер прямого доступа к памяти. Контроллер прямого доступа к памяти имеет несколько спаренных линий – каналов DMA, которые могут подключаться к различным устройствам. Перед началом использования прямого доступа к памяти этот контроллер необходимо запрограммировать, записав в его порты информацию о том, какой канал или каналы предполагается задействовать, какие операции они будут совершать, какой адрес памяти является начальным для передачи информации, и какое количество информации должно быть передано. Получив по одной из линий каналов DMA сигнал запроса на передачу данных от внешнего устройства, контроллер по шине управления сообщает процессору о желании взять на себя управление локальной магистралью. Процессор, возможно через некоторое время, необходимое для завершения его действий с магистралью, передает управление ею контроллеру DMA. известив его специальным сигналом. Контроллер DMA выставляет на адресную шину адрес памяти для передачи очередной порции информации и по второй линии канала прямого доступа к памяти сообщает устройству о готовности магистрали к передаче данных. После этого, используя шину данных и шину управления, контроллер DMA, устройство ввода-вывода и память осуществляют процесс обмена информацией. Затем контроллер прямого доступа к памяти извещает процессор о своем отказе от управления магистралью, и тот берет руководящие функции на себя. При передаче большого количества данных весь процесс повторяется циклически.
При прямом доступе к памяти процессор и контроллер DMA по очереди управляют локальной магистралью. Это, конечно, несколько снижает производительность процессора, так как при выполнении некоторых команд или при чтении очередной порции команд во внутренний кэш он должен поджидать освобождения магистрали, но в целом производительность вычислительной системы существенно возрастает.
При подключении к системе нового устройства, которое умеет использовать прямой доступ к памяти, обычно необходимо программно или аппаратно задать номер канала DMA, к которому будет приписано устройство. В отличие от прерываний, где один номер прерывания мог соответствовать нескольким устройствам, каналы DMA всегда находятся в монопольном владении устройств.
13.2. Логические принципы организации ввода-вывода.
13.2.1. Структура системы ввода-вывода.
Если поручить неподготовленному пользователю сконструировать систему ввода-вывода, способную работать со всем множеством внешних устройств, то, скорее всего, он окажется в ситуации, в которой находились биологи и зоологи до появления трудов Линнея. Все устройства разные, отличаются по выполняемым функциям и своим характеристикам, и кажется, что принципиально невозможно создать систему, которая без больших постоянных переделок позволяла бы охватывать все многообразие видов. Вот перечень лишь несколько направлений (далеко не полный), по которым различаются устройства:
Скорость обмена информацией может варьироваться в диапазоне от нескольких байт в секунду (клавиатура) до нескольких гигабайт в секунду (сетевые карты).
Некоторые устройства могут быть использованы параллельно несколькими процессами (являются разделяемыми), в то время как другие требуют монопольного захвата процессом.
Устройства могут запоминать выведенную информацию для ее последующего ввода или не обладать этой функцией. Устройства, запоминающие информацию, в свою очередь, могут дифференцироваться по формам доступа к сохраненной информации: обеспечивать к ней последовательный доступ в жестко заданном порядке или уметь находить и передавать только необходимую порцию данных.
Часть устройств умеет передавать данные только по одному байту последовательно ( символьные устройства ), а часть устройств умеет передавать блок байт как единое целое ( блочные устройства ).
Существуют устройства, предназначенные только для ввода информации, устройства, предназначенные только для вывода информации, и устройства, которые могут совершать и ввод, и вывод.
В области технического обеспечения удалось выделить несколько основных принципов взаимодействия внешних устройств с вычислительной системой, т. е. создать единый интерфейс для их подключения, возложив все специфические действия на контроллеры самих устройств. Тем самым конструкторы вычислительных систем переложили головную боль, связанную с подключением внешней аппаратуры, на разработчиков самой аппаратуры, заставляя их придерживаться определенного стандарта.
Два нижних уровня этой слоеной системы составляет hardware: сами устройства, непосредственно выполняющие операции, и их контроллеры, служащие для организации совместной работы устройств и остальной вычислительной системы. Следующий уровень составляют драйвера устройств ввода-вывода, скрывающие от разработчиков операционных систем особенности функционирования конкретных приборов и обеспечивающие четко определенный интерфейс между hardware и вышележащим уровнем – уровнем базовой подсистемы ввода-вывода, которая, в свою очередь, предоставляет механизм взаимодействия между драйверами и программной частью вычислительной системы в целом.
Рис 13.1. Структура системы ввода-вывода
В последующих разделах мы подробнее рассмотрим организацию и функции набора драйверов и базовой подсистемы ввода-вывода.
13.2.2. Систематизация внешних устройств и интерфейс между базовой подсистемой ввода-вывода и драйверами.
Как и система видов Линнея, система типов устройств является далеко не полной и не строго выдержанной. Устройства обычно принято разделять по преобладающему типу интерфейса на следующие типы:
символьные (клавиатура, модем, терминал и т.п.);
блочные (магнитные и оптические диски и ленты, и т.д.);
сетевые (сетевые карты);
все остальные (таймеры, графические дисплеи, телевизионные устройства, видеокамеры и т.п.);
Такое деление является весьма условным. В некоторых операционных системах сетевые устройства могут не выделяться в отдельную группу, в некоторых – отдельные группы составляют звуковые устройства и видеоустройства и т.д. Некоторые группы в свою очередь могут разбиваться на подгруппы: подгруппа жестких дисков, подгруппа мышек, подгруппа принтеров. Нас такие детали не интересуют. Нашей целью не является построение стройной и единственно возможной систематизации всех возможных устройств, которые могут быть подключены к вычислительной системе. Единственное, для чего нам понадобится эта классификация – так это для иллюстрации того, что устройства могут быть разделены на группы по выполняемым ими функциям, и для понимания функций драйверов и интерфейса между ними и базовой подсистемой ввода-вывода.
Для этого мы рассмотрим только две группы устройств: символьные и блочные. Как уже упоминалось в предыдущем разделе, символьные устройства – это устройства, которые умеют передавать данные только последовательно байт за байтом, а блочные устройства – это устройства, которые могут передавать блок байт как единое целое.
Драйвера символьных и блочных устройств должны предоставлять базовой подсистеме ввода-вывода функции для осуществления описанных общих операций. Помимо общих операций некоторые устройства могут выполнять операции специфические, свойственные только им – например, звуковые карты умеют увеличивать или уменьшать среднюю громкость звучания, дисплеи умеют изменять свою разрешающую способность. Для выполнения таких специфических действий в интерфейс между драйвером и базовой подсистемой ввода-вывода обычно входит еще одна функция, позволяющая непосредственно передать драйверу устройства произвольную команду с произвольными параметрами, что позволяет задействовать любую возможность драйвера без изменения интерфейса. В операционной системе UNIX такая функция получила название ioctl (от i nput- o utput c on t ro l ).
Функцию временного завершения работы с устройством (может, например, вызывать отключение устройства) – close.
Функцию опроса состояния устройства (если по каким-либо причинам работа с устройством производится методом опроса его состояния – например, в операционных системах Windows NT и Windows 9x так построена работа с принтерами через параллельный порт) – poll.
Существует еще ряд действий, выполнение которых может быть возложено на драйвер, но поскольку, как правило, они являются действиями базовой подсистемы ввода-вывода, мы поговорим о них в следующем разделе. Приведенные выше названия функций, конечно, являются условными и могут меняться от одной операционной системы к другой, но действия, выполняемые драйверами, характерны для большинства операционных систем, и соответствующие функции присутствуют в интерфейсах к ним.
13.2.3. Функции базовой подсистемы ввода-вывода.
Базовая подсистема ввода-вывода служит посредником между процессами вычислительной системы и набором драйверов. Системные вызовы для выполнения операций ввода-вывода трансформируются ею в вызовы функций необходимого драйвера устройства. Однако обязанности базовой подсистемы не сводятся к выполнению только действий трансляции общего системного вызова в обращение к частной функции драйвера. Базовая подсистема предоставляет вычислительной системе такие услуги, как поддержка блокирующихся, не блокирующихся и асинхронных системных вызовов, буферизация и кэширование входных и выходных данных, осуществление spooling’а и монопольного захвата внешних устройств, обработку ошибок и прерываний, возникающих при операциях ввода-вывода, планирование последовательности запросов на выполнение этих операций. Давайте остановимся на этих услугах подробнее.
13.2.3.1. Блокирующиеся, не блокирующиеся и асинхронные системные вызовы.
Все системные вызовы, связанные с осуществлением операций ввода-вывода, можно разбить на три группы по способам реализации взаимодействия процесса и устройства ввода-вывода.
Ко второй группе относятся не блокирующиеся системные вызовы. Их название не совсем точно отражает суть дела. В простейшем случае, процесс, применивший не блокирующийся вызов, не переводится в состояние ожидание вообще. Системный вызов возвращается немедленно, выполнив предписанные ему операции ввода-вывода полностью, частично или не выполнив совсем, в зависимости от текущей ситуации (состояния устройства, наличия данных и т.д.). В более сложных ситуациях процесс может блокироваться, но условием его разблокирования является завершение всех необходимых операций или окончание некоторого промежутка времени. Типичным случаем применения не блокирующегося системного вызова может являться периодическая проверка на поступление информации с клавиатуры при выполнении трудоемких расчетов.
К третьей группе относятся асинхронные системные вызовы. Процесс, использовавший асинхронный системный вызов, никогда в нем не блокируется. Системный вызов инициирует выполнение необходимых операций ввода-вывода и немедленно возвращается, после чего процесс продолжает выполнять свою регулярную деятельность. Об окончании завершения операции ввода-вывода операционная система впоследствии информирует процесс изменением значений некоторых переменных, передачей ему сигнала или сообщения, или каким-либо еще способом. Необходимо четко понимать разницу между не блокирующимися и асинхронными вызовами. Не блокирующийся системный вызов для выполнения операции read вернется немедленно, но может прочитать запрошенное количество байт, меньшее количество или вообще ничего. Асинхронный системный вызов для этой операции также вернется немедленно, но требуемое количество байт рано или поздно будет прочитано в полном объеме.
13.2.3.2. Буферизация и кэширование.
Под буфером обычно понимается некоторая область памяти для запоминания информации при обмене данных между двумя устройствами, двумя процессами или процессом и устройством. Обмен информацией между двумя процессами относится к области кооперации процессов, и мы подробно рассмотрели его организацию в соответствующей главе. Нас здесь будет интересовать использование буферов в том случае, когда одним из участников обмена является внешнее устройство. Существуют три причины, приводящие к использованию буферов в базовой подсистеме ввода-вывода:
Первая причина буферизации – это разные скорости приема и передачи информации, которыми обладают участники обмена. Рассмотрим, например, случай передачи потока данных от клавиатуры на модем. Скорость, с которой поставляет информацию клавиатура, определяется скоростью набора текста человеком и обычно существенно меньше скорости передачи данных модемом. Для того чтобы не занимать модем на все время набора текста, делая его недоступным для других процессов и устройств, разумно накапливать введенную информацию в буфере или нескольких буферах достаточного размера и отсылать ее через модем после заполнения буферов.
Вторая причина буферизации – это разные объемы данных, которые могут быть приняты или получены участниками обмена единовременно. Возьмем другой пример. Пусть информация поставляется модемом и записывается на жесткий диск. Помимо обладания разными скоростями совершения операций модем и жесткий диск относятся к разным типам устройств. Модем является символьным устройством и выдает данные байт за байтом, в то время как диск является блочным устройством и для проведения операции записи для него требуется накопить необходимый блок данных в буфере. Здесь также можно применять более одного буфера. После заполнения первого буфера модем начинает заполнять второй одновременно с записью первого на жесткий диск. Поскольку скорость работы жесткого диска в тысячи раз больше, чем скорость работы модема, то к моменту заполнения второго буфера операция записи первого будет завершена, и модем снова может заполнять первый буфер одновременно с записью второго на диск.
Под словом кэш (cache – “наличные”), этимологию которого мы не будем здесь рассматривать, обычно понимают область быстрой памяти, содержащую копию данных, расположенных где-либо в более медленной памяти, предназначенную для ускорения работы вычислительной системы. Мы с вами сталкивались с этим понятием при рассмотрении иерархии памяти. В базовой подсистеме ввода-вывода не следует смешивать два понятия: буферизация и кэширование, хотя зачастую для выполнения этих функций отводится одна и та же область памяти. Буфер часто содержит единственный набор данных, существующий в системе, в то время как кэш, по своему определению, содержит копию данных, существующих где-нибудь еще. Например, буфер, используемый базовой подсистемой для копирования данных из пользовательского пространства процесса при выводе на диск, может в свою очередь использоваться как кэш для этих данных, если операции модификации и повторного чтения этого блока выполняются достаточно часто.
Функции буферизации и кэширования не обязательно должны быть локализованы в базовой подсистеме ввода-вывода. Они могут быть частично реализованы в драйверах и даже в контроллерах устройств, скрытно по отношению к базовой подсистеме.
13.2.3.3. Spooling и захват устройств.
О понятии spooling мы с вами говорили в первой главе нашего курса, как о механизме, впервые позволившем совместить реальные операции ввода-вывода одного задания с выполнением другого задания. Теперь мы можем определить это понятие более аккуратно. Под словом spool мы будем понимать буфер, который содержит входные или выходные данные для устройства, на котором следует избегать чередования его использования (возникновения interleaving – см. раздел 5.1. главы 5) различными процессами. Правда, в современных вычислительных системах spool практически не используется для ввода данных, а в основном предназначен для накопления выходной информации.
Рассмотрим в качестве внешнего устройства принтер. Хотя принтер не может печатать информацию, поступающую одновременно от нескольких процессов, может оказаться желательным разрешить процессам совершать вывод на принтер параллельно. Для этого операционная система вместо передачи информации напрямую на принтер накапливает выводимые данные в буферах на диске, организованных в виде отдельного spool файла для каждого процесса. После завершения некоторого процесса, соответствующий ему spool файл ставится в очередь для реальной печати. Механизм, обеспечивающий подобные действия, и получил название spooling.
В некоторых операционных системах вместо использования spooling’а для устранения race condition применяется механизм монопольного захвата устройств процессами. Если устройство свободно, то один из процессов может получить его в монопольное распоряжение. При этом все другие процессы при попытке осуществления операций над этим устройством будут либо блокированы (переведены в состояние ожидание ), либо получат информацию о невозможности выполнения операции до тех пор, пока процесс, захвативший устройство, не завершится или явно не сообщит операционной системе о своем отказе от его использования.
Обеспечение spooling’а и механизма захвата устройств является прерогативой базовой подсистемы ввода-вывода.
13.2.3.4. Обработка прерываний и ошибок.
Если при работе с внешним устройством вычислительная система не пользуется методом опроса его состояния, а использует механизм прерываний, то при возникновении прерывания, как мы уже говорили раньше, процессор, частично сохранив свое состояние, передает управление специальной программе обработки прерывания. Мы уже рассматривали действия операционной системы над процессами, происходящими при возникновении прерывания в разделе 2.3.5. – “Переключение контекста”, где после возникновения прерывания осуществлялись следующие действия: сохранение контекста, обработка прерывания, планирование использование процессора, восстановление контекста, обратив пристальное внимание на действия, связанные с сохранением и восстановлением контекста и планированием использования процессора. Давайте теперь подробнее остановимся на том, что скрывается за словами “обработка прерывания”.
Действия по обработке прерывания и компенсации возникающих ошибок могут быть частично переложены на плечи соответствующего драйвера. Для этого в состав интерфейса между драйвером и базовой подсистемой ввода-вывода добавляют еще одну функцию – функцию обработки прерывания intr.
13.2.3.5. Планирование запросов.
После завершения выполнения текущего запроса операционная система (по ходу обработки возникшего прерывания) должна решить, какой из запросов в списке должен быть удовлетворен следующим, и инициировать его исполнение. Точно так же, как для выбора очередного процесса на исполнение из списка готовых нам приходилось осуществлять краткосрочное планирование процессов, здесь нам необходимо осуществлять планирование использования устройств, пользуясь каким-либо алгоритмом этого планирования. Критерии и цели такого планирования мало отличаются от критериев и целей планирования процессов.
В следующем разделе мы рассмотрим некоторые алгоритмы планирования, связанные с удовлетворением запросов, на примере жесткого диска.
13.2.4. Алгоритмы планирования запросов к жесткому диску.
Прежде, чем приступить к непосредственному изложению самих алгоритмов, давайте вспомним внутренне устройство жесткого диска и определимся с тем, какие параметры запросов мы можем использовать для планирования.
13.2.4.1. Строение жесткого диска и параметры планирования.
Современный жесткий магнитный диск представляет собой набор круглых пластин, находящихся на одной оси, и покрытых с одной или двух сторон специальным магнитным слоем (см. рисунок 13.2.). Около каждой рабочей поверхности каждой пластины расположены магнитные головки для чтения и записи информации. Эти головки присоединены к специальному рычагу, который может перемещать весь блок головок над поверхностями пластин как единое целое. Поверхности пластин разделены на концентрические кольца, внутри которых собственно и может храниться информация. Набор концентрических колец на всех пластинах для одного положения головок (т.е. все кольца равноудаленные от оси) образует цилиндр. Каждое кольцо внутри цилиндра получило название дорожки (по 1-й или 2-е дорожки на каждую пластину). Все дорожки делятся на равное число секторов. Количество дорожек, цилиндров и секторов может варьироваться от одного жесткого диска к другому в достаточно широких пределах. Как правило, сектор является минимальным объемом информации, которое может быть прочитано с диска за один раз.
При работе диска набор пластин вращается вокруг своей оси с высокой скоростью, подставляя по очереди под головки соответствующих дорожек все их сектора. Номер сектора, номер дорожки и номер цилиндра однозначно определяют положение данных на жестком диске и, наряду с типом совершаемой операции – чтение или запись, полностью характеризуют часть запроса, связанную с устройством, при обмене информацией в объеме одного сектора.
Рис 13.2. Схема жесткого диска
13.2.4.2. Алгоритм First Come First Served (FCFS)
Простейшим алгоритмом, к которому мы уже должны были привыкнуть, является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен. Все запросы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм прост в реализации, но может приводить к достаточно большим общим временам обслуживания запросов. Рассмотрим пример. Пусть у нас на диске из 100 цилиндров (от 0 до 99) есть следующая очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63 цилиндре. Тогда положение головок будет меняться следующим образом:
и всего головки переместятся на 329 цилиндров. Неэффективность алгоритма хорошо иллюстрируется двумя последними перемещениями с 7 цилиндра через весь диск на 84 цилиндр и, затем опять через весь диск на цилиндр 10. Простая замена порядка двух последних перемещений (7->10->84) позволила бы существенно сократить общее время обслуживания запросов. Поэтому давайте перейдем к рассмотрению другого алгоритма.
13.2.4.3. Алгоритм Short Seek Time First (SSTF).
и всего головки переместятся на 141 цилиндр. Заметим, что наш алгоритм похож на алгоритм SJF планирования процессов, если за аналог оценки времени очередного CPU burst процесса выбирать расстояние между текущим положением головки и положением, необходимым для удовлетворения запроса. И точно так же, как алгоритм SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса. Необходимо вспомнить, что запросы в очереди могут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянного группируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.
Точный алгоритм SJF являлся оптимальным для заданного набора процессов с заданными временами CPU burst. Легко видеть, что алгоритм SSTF не является оптимальным. Если мы перенесем обслуживание запроса 67 цилиндра в промежуток между запросами 7 и 84 цилиндров, мы уменьшим общее время обслуживания. Это наблюдение приводит нас к идее целого семейства других алгоритмов – алгоритмов сканирования.
13.2.4.4. Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)
В простейшем из алгоритмов сканирования – SCAN – головки постоянно перемещаются от одного края диска до его другого края, по ходу дела обслуживая все встречающиеся запросы. По достижении другого края направление движения меняется, и все повторяется снова. Пусть в предыдущем примере в начальный момент времени головки двигаются в направлении уменьшения номеров цилиндров. Тогда мы и получим порядок обслуживания запросов, подсмотренный в конце предыдущего раздела. Последовательность перемещения головок выглядит следующим образом:
и всего головки переместятся на 147 цилиндров.
Если мы знаем, что обслужили последний попутный запрос в направлении движения головок, то мы можем не доходить до края диска, а сразу изменить направление движения на обратное:
и всего головки переместятся на 133 цилиндра. Полученная модификация алгоритма SCAN получила название LOOK.
Допустим, что к моменту изменения направления движения головки в алгоритме SCAN, т.е. когда головка достигла одного из краев диска, у этого края накопилось большое количество новых запросов, на обслуживание которых будет потрачено достаточно большое время (не забываем, что надо не только перемещать головку, но еще и передавать прочитанные данные!). Тогда запросы, относящиеся к другому краю диска и поступившие раньше, будут ждать обслуживания несправедливо долгое время. Для сокращения времени ожидания запросов применяется другая модификация алгоритма SCAN – циклическое сканирование. Когда головка достигает одного из краев диска, она без чтения попутных запросов (иногда существенно быстрее, чем при выполнении обычного поиска цилиндра) перемещается на другой край, откуда вновь начинает свое движение. Для этого алгоритма, получившего название C-SCAN, последовательность перемещений будет выглядеть так:
По аналогии с алгоритмом LOOK для алгоритма SCAN можно предложить и алгоритм C-LOOK для алгоритма C-SCAN:
Функционирование любой вычислительной системы обычно сводится к выполнению двух видов работы: обработке информации и операций по осуществлению ее ввода-вывода. С точки зрения операционной системы “обработкой информации” являются только операции, совершаемые процессором над данными, находящимися в памяти на уровне иерархии не ниже, чем оперативная память. Все остальное относится к “операциям ввода-вывода”, т.е. к обмену информацией с внешними устройствами.
Механизм, подобный механизму прерываний, может использоваться также и для обработки исключений и программных прерываний, однако это целиком лежит на совести разработчиков вычислительных систем.
Для построения программной части системы ввода-вывода характерен слоеный подход. Для непосредственного взаимодействия с hardware используются драйвера устройств, скрывающие от остальной части операционной системы все особенности их функционирования. Драйвера устройств через жестко определенный интерфейс связаны с базовой подсистемой ввода-вывода, в функции которой входят: организация работы блокирующихся, не блокирующихся и асинхронных системных вызовов, буферизация и кэширование входных и выходных данных, осуществление spooling’а и монопольного захвата внешних устройств, обработка ошибок и прерываний, возникающих при операциях ввода-вывода, планирование последовательности запросов на выполнение этих операций. Доступ к базовой подсистеме ввода-вывода осуществляется посредством системных вызовов.
Часть функций базовой подсистемы может быть делегирована драйверам устройств и самим устройствам ввода-вывода.