Слайд 1Лекция 8:
Система управления
вводом-выводом
АНТОНОВ ЕВГЕНИЙ АНДРЕЕВИЧ
ноябрь 2011 г.
Слайд 2ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
ФИЗИЧЕСКИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ ВВОДА-ВЫВОДА
Слайд 3ОПЕРАЦИОННЫЕ СИСТЕМЫ
ОПЕРАЦИОННЫЕ СИСТЕМЫ
Общие сведения об архитектуре компьютера
ЦП
Память
Диски
Принтер
Монитор
Клавиатура
Системная шина (магистраль)
Перифе-
рийное
устройство
Слайд 4ОПЕРАЦИОННЫЕ СИСТЕМЫ
Шины в современных компьютерах
Шина данных. Состоит из линий данных
и служит для передачи информации между процессором, памятью, устройствами ввода-вывода
и внешними устройствами;
Адресная шина. Состоит из линий адреса и служит для задания адреса ячейки памяти или указания устройства ввода-вывода, участвующих в обмене информацией;
Шина управления. Состоит из линий управления локальной магистралью и линий ее состояния, определяющих поведение локальной магистрали.
Слайд 5ОПЕРАЦИОННЫЕ СИСТЕМЫ
ОПЕРАЦИОННЫЕ СИСТЕМЫ
Общие сведения об архитектуре компьютера
ЦП
Память
Диски
Принтер
Монитор
Клавиатура
Шина данных
Шина адреса
Шина
управления
Перифе-
рийное
устройство
Слайд 6ОПЕРАЦИОННЫЕ СИСТЕМЫ
Разрядность шины
Количество линий, входящих в состав шины, принято называть
разрядностью (шириной) этой шины.
Ширина адресной шины, например, определяет максимальный размер
оперативной памяти, которая может быть установлена в вычислительной системе.
Ширина шины данных определяет максимальный объем информации, которая за один раз может быть получена или передана по этой шине.
Слайд 7ОПЕРАЦИОННЫЕ СИСТЕМЫ
Пример передачи информации из процессора в память
На адресной
шине процессор должен выставить сигналы, соответствующие адресу ячейки памяти, в
которую будет осуществляться передача информации.
На шину данных процессор должен выставить сигналы, соответствующие информации, которая должна быть записана в память.
На шину управления выставляются сигналы, соответствующие операции записи и работе с памятью, что приведет к занесению необходимой информации по нужному адресу.
Слайд 8ОПЕРАЦИОННЫЕ СИСТЕМЫ
Порты ввода-вывода
Внешние устройства разнесены пространственно и могут подключаться к
локальной магистрали в одной точке или множестве точек, получивших название
портов ввода-вывода.
Порты ввода-вывода можно взаимно однозначно отобразить в адресное пространство ввода-вывода. При этом каждый порт ввода-вывода получает свой номер или адрес в этом пространстве.
Слайд 9ОПЕРАЦИОННЫЕ СИСТЕМЫ
Пример передачи данных в порт
На адресной шине процессор
должен выставить сигналы, соответствующие адресу порта, в который будет осуществляться
передача информации.
На шину данных процессор должен выставить сигналы, соответствующие информации, которая должна быть передана в порт.
На шину управления выставляются сигналы, соответствующие операции записи и работе с устройствами ввода-вывода (переключение адресных пространств!), что приведет к передаче необходимой информации в нужный порт.
Слайд 10ОПЕРАЦИОННЫЕ СИСТЕМЫ
Отличие памяти от устройств ввода-вывода
Занесение информации в память является
окончанием операции записи, в то время как занесение информации в
порт зачастую представляет собой инициализацию реального совершения операции ввода-вывода.
Что именно должны делать устройства, приняв информацию через свой порт, и каким именно образом они должны поставлять информацию для чтения из порта, определяется электронными схемами устройств — контроллерами.
Слайд 11ОПЕРАЦИОННЫЕ СИСТЕМЫ
ОПЕРАЦИОННЫЕ СИСТЕМЫ
Работа контроллера
ЦП
Память
Диски
Принтер
Монитор
Клавиатура
Системная шина
Ввод/вывод
Перифе-
рийное
устройство
Контроллер
Слайд 12ОПЕРАЦИОННЫЕ СИСТЕМЫ
Важные моменты организации ввода-вывода
Устройства ввода-вывода подключаются к системе через
порты.
Могут существовать два адресных пространства: пространство памяти и пространство ввода-вывода.
Порты,
как правило, отображаются в адресное пространство ввода-вывода и иногда — непосредственно в адресное пространство памяти.
Слайд 13ОПЕРАЦИОННЫЕ СИСТЕМЫ
Важные моменты организации ввода-вывода
Использование того или иного адресного пространства
определяется типом команды, выполняемой процессором.
Физическим управлением устройством ввода-вывода, передачей информации
через порт и выставлением некоторых сигналов на магистрали занимается контроллер устройства.
Единообразие подключения внешних устройств к вычислительной системе позволяет добавлять новые устройства без перепроектирования всей системы.
Слайд 14ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
СТРУКТУРА КОНТРОЛЛЕРА УСТРОЙСТВА
Слайд 15ОПЕРАЦИОННЫЕ СИСТЕМЫ
Взаимодействие ОС и контроллера устройства
ОС обычно имеет дело не
с устройством, а с контроллером. Контроллер, как правило, выполняет простые
функции, например, преобразует поток бит в блоки, состоящие из байт, и осуществляют контроль и исправление ошибок.
Каждый контроллер имеет несколько регистров, которые используются для взаимодействия с центральным процессором.
ОС выполняет ввод-вывод, записывая команды в регистры контроллера.
Слайд 16ОПЕРАЦИОННЫЕ СИСТЕМЫ
Регистры контроллера
Обычно каждый контроллер имеет по крайней мере четыре
внутренних регистра, называемых регистрами
- состояния,
- управления,
- входных данных и
- выходных
данных.
Для доступа к содержимому этих регистров вычислительная система может использовать один или несколько портов.
Для простоты изложения будем считать, что каждому регистру соответствует свой порт.
Слайд 17ОПЕРАЦИОННЫЕ СИСТЕМЫ
Регистр состояния
Регистр состояния содержит биты, значение которых определяется состоянием
устройства ввода-вывода и которые доступны только для чтения вычислительной системой.
Эти
биты индицируют
- завершение выполнения текущей команды на устройстве (бит занятости),
- наличие очередного данного в регистре выходных данных (бит готовности данных),
- возникновение ошибки при выполнении команды (бит ошибки) и т. д.
Слайд 18ОПЕРАЦИОННЫЕ СИСТЕМЫ
Регистр управления
Регистр управления получает данные, которые записываются вычислительной системой
для инициализации устройства ввода-вывода или выполнения очередной команды, а также
изменения режима работы устройства.
Часть битов в этом регистре может быть отведена под код выполняемой команды, часть битов будет кодировать режим работы устройства, бит готовности команды свидетельствует о том, что можно приступить к ее выполнению.
Слайд 19ОПЕРАЦИОННЫЕ СИСТЕМЫ
Регистры входных и выходных данных
Регистр выходных данных служит для
помещения в него данных для чтения вычислительной системой, а регистр
входных данных предназначен для помещения в него информации, которая должна быть выведена на устройство.
Обычно емкость этих регистров не превышает ширину линии данных (а чаще всего меньше ее), хотя некоторые контроллеры могут использовать в качестве регистров очередь FIFO для буферизации поступающей информации.
Слайд 20ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
ОПРОС УСТРОЙСТВ И ПРЕРЫВАНИЯ
Слайд 21ОПЕРАЦИОННЫЕ СИСТЕМЫ
Пример команды вывода данных на внешнее устройство
Процессор в цикле
читает информацию из порта регистра состояний и проверяет значение бита
занятости. Если бит занятости установлен, то это означает, что устройство еще не завершило предыдущую операцию, и процессор уходит на новую итерацию цикла. Если бит занятости сброшен, то устройство готово к выполнению новой операции, и процессор переходит на следующий шаг.
Процессор записывает код команды вывода в порт регистра управления.
Слайд 22ОПЕРАЦИОННЫЕ СИСТЕМЫ
Пример команды вывода данных на внешнее устройство
Процессор записывает данные
в порт регистра входных данных.
Процессор устанавливает бит готовности команды.
Когда
контроллер замечает, что бит готовности команды установлен, он устанавливает бит занятости.
Контроллер анализирует код команды в регистре управления и обнаруживает, что это команда вывода. Он берет данные из регистра входных данных и инициирует выполнение команды.
Слайд 23ОПЕРАЦИОННЫЕ СИСТЕМЫ
Пример команды вывода данных на внешнее устройство
После завершения операции
контроллер обнуляет бит готовности команды.
При успешном завершении операции контроллер
обнуляет бит ошибки в регистре состояния, при неудачном завершении команды – устанавливает его.
Контроллер сбрасывает бит занятости.
При необходимости вывода новой порции информации все эти шаги повторяются.
Слайд 24ОПЕРАЦИОННЫЕ СИСТЕМЫ
Поведение процессора при работе с внешним устройством
Если процессор интересует,
корректно или некорректно была выведена информация, то после шага 4
он должен в цикле считывать информацию из порта регистра состояний до тех пор, пока не будет сброшен бит занятости устройства, после чего проанализировать состояние бита ошибки.
Как видим, на первом шаге (и, возможно, после шага 4) процессор ожидает освобождения устройства, непрерывно опрашивая значение бита занятости.
Слайд 25ОПЕРАЦИОННЫЕ СИСТЕМЫ
Проблема скорости опроса устройств
Такой способ взаимодействия процессора и
контроллера получил название polling — способ опроса устройств.
Если скорости работы
процессора и устройства ввода-вывода примерно равны, то это не приводит к существенному уменьшению полезной работы, совершаемой процессором. Если же скорость работы устройства существенно меньше скорости процессора, то указанная техника резко снижает производительность системы и необходимо применять другой подход.
Слайд 26ОПЕРАЦИОННЫЕ СИСТЕМЫ
Механизм прерываний
Для того чтобы процессор не дожидался состояния готовности
устройства ввода-вывода в цикле, а мог выполнять в это время
другую работу, необходимо, чтобы устройство само умело сигнализировать процессору о своей готовности.
Технический механизм, который позволяет внешним устройствам оповещать процессор о завершении команды вывода или команды ввода, получил название механизма прерываний.
Слайд 27ОПЕРАЦИОННЫЕ СИСТЕМЫ
ОПЕРАЦИОННЫЕ СИСТЕМЫ
Линия прерываний
ЦП
Память
Диски
Принтер
Монитор
Клавиатура
Системная шина
Ввод/вывод
Прерывание
Перифе-
рийное
устройство
Контроллер
Линия прерывания
Слайд 28ОПЕРАЦИОННЫЕ СИСТЕМЫ
Идея реализации механизма прерываний
При наличии только одной линии прерываний
процессор при выполнении этой программы должен опросить состояние всех устройств
ввода-вывода, чтобы определить, от какого именно устройства пришло прерывание (polling прерываний), выполнить необходимые действия (например, вывести в это устройство очередную порцию информации или перевести соответствующий процесс из состояния ожидание в состояние готовность) и сообщить устройству, что прерывание обработано (снять прерывание).
Слайд 29ОПЕРАЦИОННЫЕ СИСТЕМЫ
Практическая реализация механизма прерываний
В большинстве современных компьютеров процессор стараются
полностью освободить от необходимости опроса внешних устройств, в том числе
и от определения с помощью опроса устройства, сгенерировавшего сигнал прерывания.
Устройства сообщают о своей готовности процессору не напрямую, а через специальный контроллер прерываний, при этом для общения с процессором он может использовать не одну линию, а целую шину прерываний.
Слайд 30ОПЕРАЦИОННЫЕ СИСТЕМЫ
Практическая реализация механизма прерываний
Каждому устройству присваивается свой номер прерывания
(хранится в регистре состояния контроллера).
Номер прерывания обычно служит индексом в
специальной таблице прерываний, хранящейся по адресу, задаваемому при инициализации вычислительной системы, и содержащей адреса программ обработки прерываний — векторы прерываний.
При наличии множества устройств на один номер прерывания подключается несколько устройств.
Слайд 31ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
ИСКЛЮЧИТЕЛЬНЫЕ СИТУАЦИИ И СИСТЕМНЫЕ ВЫЗОВЫ
Слайд 32ОПЕРАЦИОННЫЕ СИСТЕМЫ
Использование механизма обработки прерываний
Механизм обработки прерываний, по которому процессор
прекращает выполнение команд в обычном режиме и, частично сохранив свое
состояние, отвлекается на выполнение других действий, оказался настолько удобен, что зачастую разработчики процессоров используют его и для других целей (не относящихся к операциям ввода-вывода).
Похожим образом процессор обрабатывает исключительные ситуации и программные прерывания.
Слайд 33ОПЕРАЦИОННЫЕ СИСТЕМЫ
Исключительные ситуации и программные прерывания
Исключительные ситуации возникают во время
выполнения процессором команды.
К их числу относятся ситуации переполнения, деления на
ноль, обращения к отсутствующей странице памяти и т. д.
Программные прерывания возникают после выполнения специальных команд,
как правило, для выполнения привилегированных действий внутри системных вызовов.
Слайд 34ОПЕРАЦИОННЫЕ СИСТЕМЫ
Особенности внешних прерываний
Внешнее прерывание обнаруживается процессором между выполнением команд.
Процессор
при переходе на обработку прерывания сохраняет часть своего состояния перед
выполнением следующей команды.
Прерывания происходят асинхронно с работой процессора и непредсказуемо (никоим образом нельзя предугадать, в каком именно месте работы программы произойдет прерывание).
Слайд 35ОПЕРАЦИОННЫЕ СИСТЕМЫ
Особенности исключительных ситуаций
Исключительные ситуации обнаруживаются процессором во время выполнения
команд.
Процессор при переходе на выполнение обработки исключительной ситуации сохраняет часть
своего состояния перед выполнением текущей команды.
Исключительные ситуации возникают синхронно с работой процессора, но непредсказуемо для программиста, если только тот специально не заставил процессор делить некоторое число на ноль.
Слайд 36ОПЕРАЦИОННЫЕ СИСТЕМЫ
Особенности программных прерываний
Программное прерывание происходит в результате выполнения специальной
команды.
Процессор при выполнении программного прерывания сохраняет свое состояние перед выполнением
следующей команды.
Программные прерывания, естественно, возникают синхронно с работой процессора и абсолютно предсказуемы программистом.
Слайд 37ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
ВОПРОСЫ
Слайд 38ОПЕРАЦИОННЫЕ СИСТЕМЫ
Вопрос 1
В каком внутреннем регистре контроллер устройства хранит бит
ошибки?
регистр входных данных
регистр управления
регистр состояния
регистр выходных данных
Слайд 39ОПЕРАЦИОННЫЕ СИСТЕМЫ
Вопрос 2
Какие из перечисленных ситуаций возникают синхронно с работой
процессора?
внешние прерывания
исключительные ситуации
программные прерывания
Слайд 40ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
СТРУКТУРА СИСТЕМЫ ВВОДА-ВЫВОДА
Слайд 41ОПЕРАЦИОННЫЕ СИСТЕМЫ
Различие устройств
ввода-вывода
По скорости обмена информацией
от Б/с (keyboard) до Гб/с
(NIC)
По способу использования (разделяемые и монопольный захвата процессом)
По способности запоминать
информацию и способу доступа к ней (последовательный и случайный)
По способу передачи данных
(символьные и блочные устройства)
По направлению ввода/вывода информации
(только ввод, только вывод, и то и другое)
Слайд 42ОПЕРАЦИОННЫЕ СИСТЕМЫ
Идея универсализации устройств
Мы можем разделить устройства на относительно небольшое
число типов, отличающихся по набору операций, которые могут быть ими
выполнены, считая все остальные различия несущественными.
Мы можем затем специфицировать интерфейсы между ядром ОС, осуществляющим некоторую общую политику ввода-вывода, и программными частями, непосредственно управляющими устройствами, для каждого из таких типов.
Слайд 43ОПЕРАЦИОННЫЕ СИСТЕМЫ
Идея универсализации устройств
Более того, разработчики ОС получают возможность освободиться
от написания и тестирования этих специфических программных частей, получивших название
драйверов, передав эту деятельность производителям самих внешних устройств.
Фактически мы приходим к использованию принципа уровневого или слоеного построения системы управления вводом-выводом для ОС.
Слайд 44ОПЕРАЦИОННЫЕ СИСТЕМЫ
Структура системы
ввода-вывода
hardware
software
Остальная часть ядра ОС
Базовая подсистема ввода-вывода
Драйвер
клавиатуры
Драйвер
мыши
IDE
драйвер
Драйвер
монитора
•••
Контроллер
клавиатуры
Контроллер
мыши
IDE
контроллер
Контроллер
монитора
•••
Клавиатура
Мышь
IDE-диски
Монитор
•••
Слайд 45ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
ФУНКЦИИ
БАЗОВОЙ ПОДСИСТЕМЫ ВВОДА-ВЫВОДА
Слайд 46ОПЕРАЦИОННЫЕ СИСТЕМЫ
Трансляция системных вызовов к драйверам устройств
Базовая подсистема ввода-вывода служит
посредником между процессами вычислительной системы и набором драйверов.
Системные вызовы для
выполнения операций ввода-вывода трансформируются ею в вызовы функций необходимого драйвера устройства.
Однако обязанности базовой подсистемы не сводятся к выполнению только действий трансляции общего системного вызова в обращение к частной функции драйвера.
Слайд 47ОПЕРАЦИОННЫЕ СИСТЕМЫ
Другие функции базовой подсистемы ввода-вывода
Базовая подсистема предоставляет вычислительной системе
такие услуги, как:
поддержка блокирующихся, неблокирующихся и асинхронных системных вызовов,
буферизация и
кэширование входных и выходных данных,
осуществление spooling'a и монопольного захвата внешних устройств,
обработка ошибок и прерываний, возникающих при операциях ввода-вывода,
планирование последовательности запросов на выполнение этих операций.
Слайд 48ОПЕРАЦИОННЫЕ СИСТЕМЫ
Блокирующиеся системные вызовы
Применение такого вызова приводит к блокировке
инициировавшего его процесса (процесс переводится из состояния исполнение в состояние
ожидание).
Завершив выполнение всех операций ввода-вывода, ОС переводит процесс из состояния ожидание в состояние готовность.
После того как процесс будет снова выбран для исполнения, в нем произойдет окончательный возврат из системного вызова.
Слайд 49ОПЕРАЦИОННЫЕ СИСТЕМЫ
Неблокирующиеся системные вызовы
В простом случае процесс, применивший неблокирующийся
вызов, не переводится в состояние ожидание вообще. Системный вызов возвращается
немедленно, выполнив предписанные ему операции ввода-вывода полностью, частично или не выполнив совсем.
В более сложных ситуациях процесс может блокироваться, но условием его разблокирования является завершение всех необходимых операций или окончание некоторого промежутка времени.
Слайд 50ОПЕРАЦИОННЫЕ СИСТЕМЫ
Асинхронные системные вызовы
Процесс, использовавший асинхронный системный вызов, никогда
в нем не блокируется. Системный вызов инициирует выполнение необходимых операций
ввода-вывода и немедленно возвращается, после чего процесс продолжает свою регулярную деятельность.
Об окончании завершения операции ввода-вывода ОС впоследствии информирует процесс изменением значений некоторых переменных, передачей ему сигнала или сообщения или каким-либо иным способом.
Слайд 51ОПЕРАЦИОННЫЕ СИСТЕМЫ
Буферизация
Под буфером обычно понимается некоторая область памяти для запоминания
информации при обмене данных между двумя устройствами, двумя процессами или
процессом и устройством.
Обмен информацией между двумя процессами относится к области кооперации процессов. Здесь нас будет интересовать использование буферов в том случае, когда одним из участников обмена является внешнее устройство.
Слайд 52ОПЕРАЦИОННЫЕ СИСТЕМЫ
Причины буферизации
Разные скорости приема и передачи информации, которыми
обладают участники обмена.
Разные объемы данных, которые могут быть приняты или
получены участниками обмена единовременно.
Необходимость копирования информации из приложений, осуществляющих ввод-вывод, в буфер ядра ОС и обратно.
Слайд 53ОПЕРАЦИОННЫЕ СИСТЕМЫ
Кэширование
Под словом кэш (cache) обычно понимают область быстрой
памяти, содержащую копию данных, расположенных где-либо в более медленной памяти,
предназначенную для ускорения работы вычислительной системы.
Не следует смешивать два понятия, хотя зачастую для выполнения этих функций отводится одна и та же область памяти.
Буфер часто содержит единственный набор данных, существующий в системе, в то время как кэш по определению содержит копию данных, существующих где-нибудь еще.
Слайд 54ОПЕРАЦИОННЫЕ СИСТЕМЫ
Spooling
Под словом spool мы подразумеваем буфер, содержащий входные или
выходные данные для устройства, на котором следует избегать чередования его
использования различными процессами.
К примеру, для параллельной печати разными процессами ОС вместо передачи информации напрямую на принтер накапливает выводимые данные в буферах на диске, в виде spool-файлов для каждого процесса. После spool-файл ставится в очередь для реальной печати.
Слайд 55ОПЕРАЦИОННЫЕ СИСТЕМЫ
Захват устройств
В некоторых ОС вместо использования spooling для
устранения race condition применяется механизм монопольного захвата устройств процессами.
Если устройство
свободно, то один из процессов может получить его в монопольное распоряжение. При этом все другие процессы при попытке осуществления операций над этим устройством будут либо блокированы, либо получат информацию о невозможности выполнения операции до завершения текущего процесса.
Слайд 56ОПЕРАЦИОННЫЕ СИСТЕМЫ
Обработка прерываний и ошибок
Если при работе с внешним устройством
вычислительная система не пользуется методом опроса его состояния, а задействует
механизм прерываний, то при возникновении прерывания, процессор, частично сохранив свое состояние, передает управление специальной программе обработки прерывания.
После возникновения прерывания осуществляются следующие действия: сохранение контекста, обработка прерывания, планирование использования процессора, восстановление контекста.
Слайд 57ОПЕРАЦИОННЫЕ СИСТЕМЫ
Обработка прерываний и ошибок
Поскольку прерывание возникает как при удачном,
так и при неудачном ее выполнении, следующее, что мы должны
сделать, — это определить успешность завершения операции, проверив значение бита ошибки в регистре состояния устройства.
В некоторых случаях операционная система может предпринять определенные действия, направленные на компенсацию возникшей ошибки.
Слайд 58ОПЕРАЦИОННЫЕ СИСТЕМЫ
Обработка прерываний и ошибок
Действия по обработке прерывания и компенсации
возникающих ошибок могут быть частично переложены на плечи соответствующего драйвера.
Для
этого в состав интерфейса между драйвером и базовой подсистемой ввода-вывода добавляют еще одну функцию — функцию обработки прерывания — intr.
Слайд 59ОПЕРАЦИОННЫЕ СИСТЕМЫ
Планирование запросов
При использовании неблокирующегося системного вызова может оказаться,
что нужное устройство уже занято выполнением некоторых операций. В этом
случае неблокирующийся вызов может немедленно вернуться, не выполнив запрошенных команд.
При организации запроса на совершение операций ввода-вывода с помощью блокирующегося или асинхронного вызова занятость устройства приводит к необходимости постановки запроса в очередь к данному устройству.
Слайд 60ОПЕРАЦИОННЫЕ СИСТЕМЫ
Планирование запросов
В результате с каждым устройством оказывается связан
список неудовлетворенных запросов процессов, находящихся в состоянии ожидания, и запросов,
выполняющихся в асинхронном режиме. Состояние ожидание расщепляется на набор очередей процессов, дожидающихся различных устройств.
После завершения выполнения текущего запроса ОС (по ходу обработки возникшего прерывания) должна решить, какой из запросов в списке должен быть удовлетворен следующим, и инициировать его исполнение.
Слайд 61ОПЕРАЦИОННЫЕ СИСТЕМЫ
Планирование запросов
Точно так же, как для выбора очередного процесса
на исполнение из списка готовых нам приходилось осуществлять краткосрочное планирование
процессов, здесь нам необходимо осуществлять планирование применения устройств, пользуясь каким-либо алгоритмом этого планирования.
Критерии и цели такого планирования мало отличаются от критериев и целей планирования процессов.
Слайд 62ОПЕРАЦИОННЫЕ СИСТЕМЫ
Планирование запросов
Задача планирования использования устройства обычно возлагается на базовую
подсистему ввода-вывода, однако для некоторых устройств лучшие алгоритмы планирования могут
быть тесно связаны с деталями их внутреннего функционирования.
В таких случаях операция планирования переносится внутрь драйвера соответствующего устройства. Для этого в интерфейс драйвера добавляется еще одна специальная функция, осуществляющая выбор очередного запроса, — strategy.
Слайд 63ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
АЛГОРИТМЫ ПЛАНИРОВАНИЯ ЗАПРОСОВ К ЖЕСТКОМУ ДИСКУ
Слайд 64ОПЕРАЦИОННЫЕ СИСТЕМЫ
Строение жесткого диска и параметры планирования
Слайд 65ОПЕРАЦИОННЫЕ СИСТЕМЫ
Строение жесткого диска и параметры планирования
При планировании использования жесткого
диска естественным параметром планирования является время, которое потребуется для выполнения
очередного запроса.
Время, необходимое для чтения или записи определенного сектора на определенной дорожке определенного цилиндра, можно разделить на две составляющие:
время обмена информацией между магнитной головкой и компьютером,
и время, необходимое для позиционирования головки над заданным сектором.
Слайд 66ОПЕРАЦИОННЫЕ СИСТЕМЫ
Строение жесткого диска и параметры планирования
Время обмена информацией между
магнитной головкой и компьютером обычно не зависит от положения данных
и определяется скоростью их передачи (transfer speed).
Время, необходимое для позиционирования головки над заданным сектором, называют временем позиционирования (positioning time).
Слайд 67ОПЕРАЦИОННЫЕ СИСТЕМЫ
Строение жесткого диска и параметры планирования
Время позиционирования, в свою
очередь, состоит из времени, необходимого для перемещения головок на нужный
цилиндр, — времени поиска (seek time) и времени, которое требуется для того, чтобы нужный сектор довернулся под головку, — задержки на вращение (rotational latency).
Времена поиска пропорциональны разнице между номерами цилиндров предыдущего и планируемого запросов, и их легко сравнивать, а разницей в задержках на вращение пренебрегают.
Слайд 68ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм First Come First Served (FCFS)
Простейшим алгоритмом является алгоритм
First Come First Served (FCFS) — первым пришел, первым обслужен.
Все
запросы организуются в очередь FIFO и обслуживаются в порядке поступления.
Алгоритм прост в реализации, но может приводить к достаточно длительному общему времени обслуживания запросов.
Слайд 69ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм First Come First Served (FCFS)
Пусть у нас на
диске из 100 цилиндров (от 0 до 99) есть следующая
очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63-м цилиндре. Тогда положение головок будет меняться следующим образом:
63236755143178410
Всего головки переместятся на 329 цилиндров.
Слайд 70ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм First Come First Served (FCFS)
Неэффективность алгоритма хорошо иллюстрируется
двумя последними перемещениями с 7 цилиндра через весь диск на
84 цилиндр и затем опять через весь диск на цилиндр 10.
Простая замена порядка двух последних перемещений (71084) позволила бы существенно сократить общее время обслуживания запросов.
Слайд 71ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм Short Seek Time First (SSTF)
Как мы убедились,
достаточно разумным является первоочередное обслуживание запросов, данные для которых лежат
рядом с текущей позицией головок, а уж затем далеко отстоящих.
Алгоритм Short Seek Time First (SSTF) — короткое время поиска первым – как раз и исходит из этой позиции. Для очередного обслуживания будем выбирать запрос, данные для которого лежат наиболее близко к текущему положению магнитных головок.
Слайд 72ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм Short Seek Time First (SSTF)
Естественно, что при
наличии равноудаленных запросов решение о выборе между ними может приниматься
исходя из различных соображений, например по алгоритму FCFS.
Для предыдущего примера алгоритм даст такую последовательность положений головок:
63675531231410784
и всего головки переместятся на 141 цилиндр.
Слайд 73ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм Short Seek Time First (SSTF)
Как и алгоритм
SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса.
Необходимо
вспомнить, что запросы в очереди могут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянно группируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.
Слайд 74ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритм Short Seek Time First (SSTF)
Точный алгоритм SJF
являлся оптимальным для заданного набора процессов с заданными временами CPU
burst.
Очевидно, что алгоритм SSTF не является оптимальным. Если мы перенесем обслуживание запроса 67-го цилиндра в промежуток между запросами 7-го и 84-го цилиндров, мы уменьшим общее время обслуживания.
Это наблюдение приводит нас к идее целого семейства других алгоритмов — алгоритмов сканирования.
Слайд 75ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритмы сканирования
(SCAN, C-SCAN, LOOK, C-LOOK)
В простейшем из алгоритмов сканирования
— SCAN — головки постоянно перемещаются от одного края диска
до другого, по ходу дела обслуживая все встречающиеся запросы.
По достижении другого края направление движения меняется, и все повторяется снова.
Пусть в предыдущем примере в начальный момент времени головки двигаются в направлении уменьшения номеров цилиндров. Тогда мы получим порядок:
635531231410706784
и всего перемещений — на 147 цилиндров.
Слайд 76ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритмы сканирования
(SCAN, C-SCAN, LOOK, C-LOOK)
Если мы знаем, что обслужили
последний попутный запрос в направлении движения головок, то мы можем
не доходить до края диска, а сразу изменить направление движения на обратное:
63553123141076784
и всего головки переместятся на 133 цилиндра. Полученная модификация алгоритма SCAN получила название LOOK.
Слайд 77ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритмы сканирования
(SCAN, C-SCAN, LOOK, C-LOOK)
Допустим, что к моменту изменения
направления движения головки в алгоритме SCAN, т.е. когда головка достигла
одного из краев диска, у этого края накопилось большое количество новых запросов, на обслуживание которых будет потрачено достаточно много времени (не забываем, что надо не только перемещать головку, но еще и передавать прочитанные данные!).
Тогда запросы, относящиеся к другому краю диска и поступившие раньше, будут ждать обслуживания несправедливо долго.
Слайд 78ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритмы сканирования
(SCAN, C-SCAN, LOOK, C-LOOK)
Для сокращения времени ожидания запросов
применяется другая модификация алгоритма SCAN — циклическое сканирование.
Когда головка достигает
одного из краев диска, она без чтения попутных запросов перемещается на другой край, откуда вновь начинает движение в прежнем направлении.
Для этого алгоритма, получившего название C-SCAN, последовательность перемещений будет выглядеть так:
63553123141070998467
Слайд 79ОПЕРАЦИОННЫЕ СИСТЕМЫ
Алгоритмы сканирования
(SCAN, C-SCAN, LOOK, C-LOOK)
По аналогии с алгоритмом LOOK
для алгоритма SCAN можно предложить и алгоритм C-LOOK для алгоритма
C-SCAN:
63553123141078467
Существуют и другие разновидности алгоритмов сканирования, и совсем другие алгоритмы, но мы закончим на этом рассмотрение примеров, ибо никто не обнимет необъятного.
Слайд 80ОПЕРАЦИОННЫЕ СИСТЕМЫ
Система управления
вводом-выводом
ЗАКЛЮЧЕНИЕ
Слайд 81ОПЕРАЦИОННЫЕ СИСТЕМЫ
Заключение
Функционирование любой вычислительной системы обычно сводится к выполнению двух
видов работы: обработка информации и операции по осуществлению ее ввода-вывода.
Несмотря
на все многообразие устройств ввода-вывода, управление их работой и обмен информацией с ними строятся на относительно небольшом количестве принципов.
Слайд 82ОПЕРАЦИОННЫЕ СИСТЕМЫ
Заключение
Основными физическими принципами построения системы ввода-вывода являются следующие:
возможность использования
различных адресных пространств для памяти и устройств ввода-вывода;
подключение устройств к
системе через порты ввода-вывода;
существование механизма прерывания для извещения процессора о завершении операций ввода-вывода;
наличие механизма прямого доступа устройств к памяти, минуя процессор.
Слайд 83ОПЕРАЦИОННЫЕ СИСТЕМЫ
Заключение
Механизм, подобный механизму прерываний, может использоваться также и для
обработки исключений и программных прерываний, однако это целиком лежит на
совести разработчиков вычислительных систем.
Для построения программной части системы ввода-вывода характерен «слоеный» подход.
Для непосредственного взаимодействия с hardware используются драйверы устройств, скрывающие от остальной части ОС все особенности их функционирования.
Слайд 84ОПЕРАЦИОННЫЕ СИСТЕМЫ
Заключение
Драйверы устройств через жестко определенный интерфейс связаны с базовой
подсистемой ввода-вывода, в обязанности которой входят:
организация работы блокирующихся, неблокирующихся и
асинхронных сист. вызовов,
буферизация и кэширование вход. и вых. данных,
осуществление spooling и монопольного захвата внешних устройств,
обработка ошибок и прерываний, возникающих при операциях ввода-вывода,
планирование последовательности запросов на выполнение этих операций.
Слайд 85ОПЕРАЦИОННЫЕ СИСТЕМЫ
Заключение
Доступ к базовой подсистеме ввода-вывода осуществляется посредством системных вызовов.
Часть
функций базовой подсистемы может быть делегирована драйверам устройств и самим
устройствам ввода-вывода.
Слайд 86ОПЕРАЦИОННЫЕ СИСТЕМЫ
Логические принципы организации ввода-вывода
ВОПРОСЫ
Слайд 87ОПЕРАЦИОННЫЕ СИСТЕМЫ
Вопрос 1
Какие проблемы не являются причиной буферизации?
разные скорости приема
и передачи информации участники обмена
разные объемы данных передаваемых участниками обмена
единовременно
увеличение скорости обмена данными с устройствами ввода-вывода
необходимость копирования информации из приложений, осуществляющих ввод-вывод, в буфер ядра ОС и обратно
Слайд 88ОПЕРАЦИОННЫЕ СИСТЕМЫ
Вопрос 2
Какие из вариантов реализации системного вызова read могут
прочитать меньше байт, чем запросил процесс?
асинхронный
блокирующийся
неблокирующийся