Ответы к операционным системам. Вопросы по дисциплине Операционные системы
 Скачать 1.44 Mb.
|
|
Алгоритмы управления виртуальной памятью LRU и NFU Алгоритм LRU Технология (LRU – Least Recently Used) позволяет для вытеснения выбрать страницу, которая не использовалась в течение самого долгого времени. Создается связанный список всех страниц в памяти,в начале которого будут хранится недавно использованные страницы. Список обновляется при каждом обращении к памяти. На каждую страницу отводится специальный 64-битный счетчик.Счетчик автоматически увеличивается на единицу после выполнения каждой инструкции. В таблице страниц имеется соответствующее поле, в которое заносится значение счётчика при каждой ссылке на страницу. При возникновении страничного нарушения выгружается страница с наименьшим значением этого поля. Проблема заключается в том, что не существует аппаратной поддержки реализации алгоритма LRU. Алгоритм NFU Технология NFU (Not Frequently Used) предусматривает выгрузку редко используемой страницы. На каждую страницу отводится счетчик числа обращений и флаг обращения R(ead). Достоинство этого алгоритма заключается в том, что он может быть реализован в виде программы и позволяет организовать выгрузку страниц в соответствии с алгоритмом LRU. Рассмотрим особенности данного алгоритма. - счетчик и флаг R получают начальные значения равные нулю и связаны с каждой страницей; - при каждом прерывании от таймера ОС сканирует всё находящиеся в памяти страницы. Для каждой страницы к счетчику добавляется значение бита R, равное 0 или 1. Значение 1 означает, что к станице было выполнено обращение процессом; - счетчики позволяют приблизительно отследить частоту обращений к каждой странице; - при возникновении ошибки отсутствия страницы для замещения выбирается та страница, чей счетчик имеет наименьшее значение. Рассмотренный алгоритм обладает «памятью». При многопроходной компиляции те страницы, которые интенсивно использовались при первом проходе, могут по-прежнему сохранять большие значения счетчиков и при последующих проходах. Таким образом, если на первый проход компиляции затрачивается больше времени, чем на все остальные проходы, то страницы, содержащие код для последующих проходов, могут всегда иметь более низкие показатели счетчиков, чем страницы, использовавшиеся при первом проходе. Поэтому ОС будет замещать нужные страницы вместо тех, надобность в которых уже отпала. Для устранения этого недостатка применяется модифицированный алгоритм NFU. Значение счетчика сдвигается в право, а в крайней левой части счетчика устанавливается бит, значение которого представляет собой бит обращения к странице R. Как правило, разрядность счетчика равна 8 битам. Приведем пример состояния счетчика страницы (табл. 5.1). К странице было произведено обращение, а затем обращения прекратились. На каждом такте значение счетчика сдвигается вправо и соответственно уменьшается. В результате будет корректно обнаружена страница, подлежащая вытеснению.  Архитектура подсистемы ввода-вывода ОС  В состав ЭВМ входит память, которая подразделяется на оперативную память ОЗУ (оперативное запоминающее устройство), которая содержит код исполняемой программы и данные, необходимые для ее работы, и ПЗУ (постоянное запоминающее устройство), которое содержит программы, управляющие работой ЭВМ и выполняющие ее тестирование при подаче питания до момента загрузки ОС. Микропроцессор, состоящий из устройства управления и арифметико-логического устройства, выполняет инструкции – команды программы, находящиеся в ОЗУ. Системная шина Процессор, память и многочисленные внешние устройства связаны большим количеством электрических соединений – линий. Линии принято называть локальной магистралью компьютера – системной шиной. Внутри системной шины находятся линии, служащие для передачи сходных сигналов и предназначенные для выполнения сходных функций. Их принято группировать в магистрали. Магистрали такжепринято называть шинами. Таких шин три. Шина данных– служит для передачи информации между процессором и памятью, процессором и устройствами ввода-вывода, памятью и внешними устройствами. Адресная шина– служит для задания адреса ячейки памяти или указания устройства ввода-вывода, участвующих в обмене информацией. Шина управления– состоит из линий управления системнойшины и линий ее состояния, определяющих поведение системнойшины. В некоторых ЭВМ линии состояния выносятся из этой шины вотдельную шину состояния. Характеристики шин Разрядность – количество линий, входящих в состав шины. Ширина адресной шины – максимальный размер оперативной памяти, которая может быть установлена в вычислительной системе. Ширина шины данных – максимальный объем информации, которая за один раз может быть получена или передана по этой шине. Подключение устройств к шине Внешнее устройство подключается к шине через порт ввода – вывода. Порт ввода-вывода – точка подключения устройства к магистрали. Адресное пространство ввода-вывода – служит для отображения портов. При этом каждый порт ввода-вывода получает свой номер или адрес. Занесение информации в порт представляет собой инициализацию операции ввода-вывода. Что именно должны делать устройства, приняв информацию через свой порт, и каким именно образом они должны поставлять информацию для чтения из порта, определяется контроллером устройства. Механизм ввода-вывода Устройства ввода-вывода подключаются к системе через порты. Могут существовать два адресных пространства: пространство памяти и пространство ввода-вывода. Порты отображаются в адресное пространство ввода-вывода и иногда – непосредственно в адресное пространство памяти. Использование того или иного адресного пространства определяется типом команды, выполняемой процессором, или типом ее операндов. Физическим управлением устройством ввода-вывода, передачей информации через порт и выставлением некоторых сигналов на магистрали занимается контроллер устройства. Архитектура контроллера Основу архитектуры контроллера образуют его регистры. Регистр – внутренняя память контроллера. Для доступа к содержимому этих регистров вычислительная система может использовать один или несколько портов. Базовый состав регистров контроллера: Регистр состояния содержит биты, значение которых определяется состоянием устройства ввода-вывода и которые доступны только для чтения вычислительной системой. В его составе выделяют флаги, биты: Бит занятости – завершение выполнения текущей команды на устройстве. Бит готовности данных – наличие очередного данного в регистре выходных данных. Бит ошибки – возникновение ошибки при выполнении команды. Регистр управления получает данные, которые записываются вычислительной системой для инициализации устройства ввода-вывода или выполнения очередной команды, а также изменения режима работы устройства. Регистр выходных данных служит для помещения в него данных для чтения вычислительной системой. Регистр входных данныхпредназначен для помещения в него информации, которая должна быть выведена на устройство. Если бит занятости установлен, то это означает, что устройство еще не завершило предыдущую операцию и процессор уходит на новую итерацию цикла. Если бит занятости сброшен, то устройство готово к выполнению новой операции и процессор переходит на следующий шаг. Процессор записывает код команды вывода в порт регистра управления. Процессор записывает данные в порт регистра входных данных. Стратегии взаимодействия с контроллером – Ожидание освобождения устройства путём непрерывного опроса значение бита занятости. Если скорости работы процессора и устройства ввода-вывода примерно равны, то это не приводит к существенному уменьшению полезной работы, совершаемой процессором. – Более эффективный способ взаимодействия между устройством и процессором является оповещение внешним устройством процессора о завершении команды вывода или команды ввода путем использования механизма прерываний. |