- •19. Динамическое распределение памяти.
- •20. Система двойников.
- •21. Страничная организация памяти.
- •22. Сегментирование.
- •23. Виртуальная память. Принцип локализации.
- •24. Страничная организация и виртуальная память. Таблица страниц. Буфер поиска трансляции.
- •26. Выбор размера страниц. Комбинация сегментации и страничной организации.
- •27. Стратегии выборки и размещения страниц.
27. Стратегии выборки и размещения страниц.
Стратегия выборки
Определяет, когда страница будет передана в основную память. Возможны два варианта –
по требованию и предварительно. При выборке по требованию страница передается в
основную память только при обращении к ячейке памяти, расположенной на этой
странице. Согласно принципу локализации, кол-во прерываний (т.е. обращений к
вторичной памяти) из-за отсутствия в памяти нужной страницы снижается до достаточно
низкого уровня.
В случае предварительной выборки загружается не только та страница, на которой
находится необходимая ячейка. В связи с физическими характеристиками уст-в вторичной
памяти, более эффективной является загрузка нескольких последовательных страниц за
один раз, чем загрузка этих страниц по одной. Но такая стратегия не дает выигрыша, если
обращения к загруженным вместе с запрошенной страницам.
Стратегия размещения
Определяет, где именно в физической памяти будут располагаться части процесса. Для
систем, использующих страничную или комбинированную организацию, стратегия
размещения не является критичной, т.к. аппаратная трансляция адреса эффективна при
любых сочетаниях страница-кадр. Эта стратегия важна в случае чистой сегментации.
28.Стратегия замещения.
Стратегия замещения
Определяет выбор страниц в основной памяти для замещения их загружаемыми с диска.
Все стратегии направлены на то, чтобы выгрузить страницу, обращений к которой не будет
в ближайшем будущем.
В соответствии с принципом локализации с большей вероятностью использоваться в
будущем будут те страницы, к которым уже обращались в последнее время. Чем более
интеллектуальная стратегия используется, тем выше накладные расходы на его
выполнение.
29. Резидентное множество процессов. Область видимости замещения.
Часть процесса, располагающаяся в некоторый момент времени в основной памяти,
называется резидентным множеством процесса. С помощью таблицы страниц или
сегментов процессор может определить, загружен ли запрашиваемый блок в основную
память. Если в основной памяти нет нужного логического адреса, ОС необходимо
загрузить в основную память нужный блок. Процесс блокируется, ОС осуществляет
операцию ввода-вывода (загружает нужный блок), после чего переводит процесс в
состояние готовности.
Область видимости замещения
Область видимости замещения можно разделить на локальную и глобальную.
Локальная стратегия замещения выбирает страницу только среди резидентных страниц
того процесса, страницу которого нужно загрузить в память. Глобальная стратегия
замещения рассматривает все незаблокированные страницы памяти для возможного
замещения, независимо от их принадлежности процессам.
Локальная стратегия проще для анализа, глобальная – проста в реализации.
При
30. Стратегия очистки. Управление загрузкой и приостановкой процессов.
Стратегия очистки
Является противоположностью стратегии выборки. Ее задача – определить момент,
когда измененная страница должна быть записана во вторичную память. Возможны 2
варианта: очистка по требованию и предварительная очистка. В первом варианте страница
записывается только тогда, когда выбирается для замещения. Предварительная очистка
записывает модифицированные страницы до того, как потребуется их выгрузка, поэтому
страницы могут записываться пакетами.
Управление загрузкой
Это определение кол-ва процессов, которые будут резидентными в основной
памяти, является критической частью системы управления памятью. При возрастании
уровня многозадачности эффективность использования процессора возрастает. Но
резидентное мн-во каждого отдельного процесса может стать неадекватно маленьким,
провоцируя постоянные прерывания и тем самым, наоборот, снижая эффективность
работы процессора.
Существуют различные варианты решения данной проблемы. Выполняться могут
только процессы, резидентные множества которых достаточно велики. Обеспечивая для
активных процессов необходимый размер резидентного мн-ва, стратегия определяет и кол-
во активных процессов.
Один из подходов заключается в том, что среднее врем между прерываниями
должно быть равно среднему времени обработки прерывания. Исследования показали,
что в этом случае достигается максимальная производительность процессора.
Приостановка процессов
Если кол-во резидентных процессов становится слишком большим, часть из них
должны быть приостановлены, т.е. полностью выгружены из памяти.
Существуют следующие возможности:
1. Процесс с наименьшим приоритетом.
2. Процесс, вызывающий прерывания. (он и так почти всегда в заблокированном
состоянии).
3. Последний активированный процесс. (маленькое резидентное мн-во)
4. Процесс с минимальным резидентным мн-вом. (минимизирует будущие затраты
на загрузку)
5. Наибольший процесс. Освобождаем большое кол-во кадров, меньше процессов
будут деактивированы.
6. Процесс с максимальным остаточным окном исполнения. (предоставляется
преимущество процессам с наименьшим временем работы (кол-вом квантов
времени до деактивации)).
31. Устройства ввода-вывода, их классификация. Эволюция функций ввода-вывода
Устройства ввода-вывода.
Внешние устройства ввода вывода могут быть разделены на три группы:
1. Работающие с пользователем. Используются для связи с пользователем:
принтеры, мониторы, мышь, клавиатура.
2. Работающие с компьютером. Используются для связи с электронным
оборудованием: дисковые устройства, датчики, контроллеры.
3. Коммуникации. Используются для связи с удаленными устройствами: модемы,
драйверы цифровых линий.
Устройства ввода-вывода могут различаться по следующим критериям:
1. Скорость передачи данных.
2. Применение. Функции устройств требуют соответствующего программного
обеспечения и изменения стратегии ОС.
3. Сложность управления. Например, для диска требуется гораздо более сложный
интерфейс управления по сравнению с принтером.
4. Единицы передачи данных. Могут передаваться как поток символов (терминал),
блоками (при выполнении дисковых операций).
5. Представление данных. Устройства использую разные схемы кодирования
данных.
6. Условия ошибок. Способ сообщения об ошибках и их последствии могут
значительно различаться у разных устройств.
Разнообразие устройств ввода-вывода приводит к невозможности разработки
единого подхода к задаче ввода-вывода.
Мы уже рассматривали три способа ввода-вывода: программируемый ввод-вывод,
ввод-вывод, управляемый прерываниями и прямой доступ к памяти. В настоящее время в
большинстве систем основным способом является прямой доступ к памяти.
Рассмотрим основные этапы развития управления вводом-выводом:
1. Процессор непосредственно управляет устройством.
2. Появляется контроллер или модуль ввода-вывода. Процессор отделяется от
некоторых деталей операций ввода-вывода, контроллер берет эти функции на себя,
предоставляя процессору более удобный и унифицированный интерфейс ввода
вывода.
3. Добавляются прерывания, благодаря которым процессор может переключиться на
другие задачи при выполнении операций ввода-вывода.
4. Появляется прямой доступ к памяти, который позволяет перемещать блоки данных
без участи процессора за исключением начала и окончания передачи.
5. Модуль ввода-вывода становится отдельным процессором со специальной
системой команд. Центральный процессор дает контроллеру команду – выполнить
программу ввода-вывода, после чего контроллер самостоятельно считывает и
выполняет ее команды, тем самым еще больше разгружая и увеличивая
производительность центрального процессора.
6. Модуль ввода-вывода теперь обладает своей локальной памятью, при этом
управление устройствами ввода-вывода происходит при минимальном участии
процессора.
32. Основные цели при проектировании ввода-вывода в ОС. Иерархия управления вводом-выводом.
Вопросы проектирования ввода-вывода в ОС
При разработке средств ввода-вывода преследуются 2 важнейшие цели:
эффективность и универсальность. Медленное выполнение операций ввода-вывода
приводит к неэффективной работе процессора, когда он простаивает из-за того, что все
процессы блокированы в ожидании операций ввода-вывода. Это частично решается с
помощью свопинга. Но выгрузка и загрузка процессов с диска в основную память сама по
себе является операцией ввода-вывода. Поэтому организация эффективного ввода-вывода
в ОС является критичной задачей.
Универсальность необходима для того, чтобы упростить работу с устройствами
ввода-вывода и снизить вероятность возникновения ошибок. Пользовательские процессы
как правило обращаются к устройствам с высокоуровневыми универсальными вызовами,
которые скрывают детали работы с конкретным устройством
Логическая структура функций ввода-вывода
Для универсальности и обеспечения модульности разработки, функции ввода-
вывода организованы в виде иерархической структуры, где каждый уровень обращается к
следующему для вызова команд. Работает это примерно по таким схемам. (см. рис 1)
Самый простой случай – когда локальное периферийное устройство
осуществляет связь с помощью потока байтов. При этом задействованы следующие
уровни:
1. Логический ввод-вывод. На этом уровне обращение к устройству ввода-вывода
осуществляется как к логическому ресурсу, детали фактического управления
устройством неизвестны. Т.е. логический модуль служит посредником между
пользовательскими процессами и более низкими уровнями ввода-вывода.
2. Устройство ввода-вывода. Запрошенные операции и данные конвертируются в
нужные последовательности инструкций и команды контроллера. Может
применяться буферизация.
3. Планирование и контроль. Здесь происходит организация очередей и планирование
операций, работа с прерываниями, получение информации о состоянии устройства,
взаимодействие с аппаратным обеспечением.
Для устройств связи схема почти такая же, но вместо логического вывода присутствует
некоторая архитектура коммуникаций, которая также может состоять из нескольких
уровней.
Рассмотрим теперь схему ввода-вывода для запоминающего устройства с
файловой системой. Здесь кроме трех нижних уровней из предыдущих схем, есть еще три
уровня:
1. Управление каталогами. На этом уровне имена файлов преобразуются в
идентификаторы. Также здесь происходят операции добавления и удаления
каталогов.
2. Файловая система. Здесь происходит работа с логической структурой файлов, их
открытием, закрытием, чтением, записью, а также осуществляется управление
правами доступа.
Физическая организация. Логические ссылки на файлы и записи должны быть
преобразованы в физические адреса конкретного устройства (например, номера дорожек,
секторов и т. д.)
33. Буферизация ввода-вывода.
Буферизация операций ввода-вывода.
Допустим, пользовательскому процессу необходимо выполнить считывание данных, они
будут считаны в область памяти внутри адресного пространства процесса. Самый простой
путь – выполнение команды ввода-вывода и ожидание, когда данные будут доступны
(активное либо посредством прерывания).
При этом возникают 2 проблемы: первая состоит в том, что процесс будет
приостановлен для ожидания ввода вывода, вторая в том, что такой подход мешает
свопингу. Адреса, в которые будут считываться данные должны находиться в основной
памяти. Таким образом, при страничной организации, по крайней мере одна страница
должна быть заблокирована в основной памяти. Полный свопинг процесса в этом случае
невозможен. Все это относится и к операции вывода.
Чтобы увеличить эффективность, иногда удобно выполнить чтение данных заранее,
до запроса, а запись – немного позже. Эта методика называется буферизацией.
Существуют устройства двух типов: блочно-ориентированные и поточно-
ориентированные. Первые сохраняют и передают информацию блоками (диски и
магнитные ленты). Вторые передают данные в виде потоков байтов (терминалы, принтера,
клавиатура и т.д.)
Одинарный буфер
Простейший тип буферизации. Когда пользовательский процесс запрашивает операцию
ввода-вывода, ОС назначает ему буфер в основной памяти, выделенной для системных
нужд.
Например, при операции чтения сначала происходит передача всех данных в
системный буфер. После ее завершения процесс перемещает блок в адресное
пространство и сразу же запрашивает следующий блок. Такая процедура называется
опережающим считыванием, т.к. предполагается что следующий блок будет затребован.
Этого не происходит только при окончании считывания.
Таким образом, процесс обрабатывает один блок, когда происходит считывание
следующего. Также процесс может быть выгружен при выполнении операции ввода-
вывода, т.к. передача данных осуществляется в системную память, а не в память процесса.
Это усложняет работу ОС, необходимо отслеживать назначение буферов процессам.
При поточном вводе-выводе буферизация может осуществляться построчно.
Двойной буфер
Более эффективная схема буферизации. Процесс может считывать данные из одного
буфера в то время как ОС заполняет другой. Двойная буферизация может оказаться
недостаточной, если процесс часто выполняет ввод или вывод. В этом случае можно
увеличить кол-во буферов и организовать циклическую буферизацию, что еще больше
повышает эффективность системы.
34. Параметры производительности диска. Стратегии дискового планирования
Дисковое планирование
Разрыв между скоростью обращения к дискам и скоростью обращения к основной памяти
постоянно увеличивается, поэтому улучшение дисковой системы очень актуально.
Параметры производительности диска
Скорость вращения диска постоянна. Чтобы выполнить чтение или запись, головка
должна находиться над искомой дорожкой и над началом искомого сектора на этой
дорожке. Выбор дорожки включает в себя перемещение головки (если они подвижны) или
электронные выбор нужной головки (если неподвижны).
В системе с подвижными головками на позиционирование головки над дорожкой
затрачивается время, называемое временем поиска. Затем контроллер диска ожидает
момент, когда начало нужного сектора достигнет головки – это время называется
временем задержки из-за вращения (или время ожидания вращения). Сумма времени
поиска (если он выполняется) и времени ожидания вращения называется временем
доступа.
Когда головка оказывается в нужной позиции, выполняется чтение или запись при
движении сектора под головкой. Таким образом, время операции ввода вывода состоит из
времени ожидания устройства, времени доступа и времени передачи данных.
Время доступа при считывании некоторого блока данных (например, файла) сильно
зависит от его расположения на диске. Если данные размещены компактно, в
последовательных секторах, то общее время доступа оказывается намного меньше, чем в
случае, когда данные случайным образом распределены по разным секторам диска. Таким
образом, порядок чтения секторов оказывает сильное влияние на производительность
ввода-вывода.
Стратегии дискового планирования
Для повышения производительности необходимо уменьшить время, затрачиваемое
на поиск дорожки. В многозадачной системе имеется очередь запросов ввода-вывода от
различных процессов, которые используют один и тот же диск. Допустим система
поддерживает отдельную очередь запросов для каждого устройства.
Если выбирать запросы случайным образом, то искомые дорожки будут
располагаться в произвольном порядке, что приводит к низкой производительности.
Простейшей формой планирования является «первым вошел – первым
вышел»(FIFO), запросы обрабатываются в порядке их поступления. Преимущество
стратегии – в ее беспристрастности. Пусть в очереди находятся запросы к дорожкам: 55,
58, 39, 18, 90, 160, 150, 38, 184, а изначально головка находится на дорожке 100.
Рассмотрим график зависимости времени поиска от последовательности
считывание дорожек.
Такая стратегия может давать неплохие результаты только при малом кол-ве
процессов и запросах к близким группам секторов. При других условиях
производительность сравнима со случайным выбором запроса.
Приоритеты
При этом методе не оптимизируется использование диска, но принимаются в расчет
другие критерии производительности ОС. Коротким заданиям и интерактивным
процессам, как правило, присваивается более высокий приоритет. При данном методе в
первую очередь выбираются запросы тех процессов, приоритет которых выше. Это
позволяет быстро выполнить много коротких заданий и уменьшить время отклика
системы. Однако, у больших заданий время ожидания может стать очень долгим.
Последним вошел – первым вышел
В данном случае выбираются запросы, поступившие последними. Здесь
используется принцип локализации ( с большей вероятностью недавние запросы будут
запрашивать сектора, близкие к запрошенным ранее). При большой нагрузке на диск
велика вероятность голодания некоторых процессов.
Рассмотри более интеллектуальные стратегии дискового планирования.
SSTF (shortest service time first) – стратегия выбора наименьшего времени
обслуживания
При такой стратегии из очереди выбирается тот запрос, который требует
наименьшего перемещения головки из ткущей позиции, так минимизируется время
поиска. Однако это не дает гарантии, что среднее время поиска будет минимальным (рис)
SCAN
Эта стратегия позволяет избежать голодания, т.е. такой ситуации, при которой
некоторые запросы длительное время будут оставаться в очереди, т.к. для выполнения
операций ввода-вывода будут постоянно выбираться другие, более новые запросы.
В данном случае перемещение головки может происходить только в одном
направлении, выполняя те запросы, которые соответствуют этому направлению. После
достижения последней дорожки направление меняется на противоположное.
C-SCAN
В этом случае сканирование происходит только в одном направлении. После
достижения последней дорожки головка возвращается на противоположный конец диска,
и сканирование начинается снова. (рис)
35. Дисковый кэш. Алгоритмы замещения.
Дисковый кэш
Мы уже знакомы с понятием кэш-памяти – это память находящаяся между
регистрами процесса и основной памятью по производительности, она уменьшает среднее
время доступа к памяти благодаря принципу локализации.
Такой же принцип может применяться к дисковой памяти. Кэш диска – это буфер в
основной памяти, который может содержать несколько секторов диска. При запросе
некоторого сектора, он сначала ищется в КЭШе, и если находится там, то немедленно
возвращается. В противном случае происходит операция ввода-вывода, и сектор
считывается в буфер. По принципу локализации, есть вероятность, что этот сектор может
снова потребоваться в ближайшем будущем.
При разработке дискового КЭШа возникают следующие вопросы:
1. Если необходимый сектор найден в КЭШе, он может копироваться в область
памяти процесса. Или возможна передача процессу указателя на сектор в
КЭШе, но при этом требуется обеспечение совместного использования КЭШа
несколькими процессами (установка блокировки при доступе и т.д.)
2. Вопрос стратегии замещения. Если весь кэш заполнен, и необходимо
считывание нового блока с диска, какой блок из КЭШа выбрать для замещения?
Алгоритмы замещения
Наиболее подходящим и распространенным оказался алгоритм замены блока, к
которому дольше всего не было обращений. В этом случае кэш организован в виде
стека. На вершине стека – блок, к которому было последнее обращение. При запросе
блока, он перемещается наверх (используется не прямое перемещение памяти, а стек
указателей). При необходимости замещения, удаляется самый нижний блок стека.
Алгоритм замены блоков, обращение к которым происходи наименее часто.
Каждому блоку в КЭШе назначается счетчик. Изначально ему присваивается значение 1. С
каждым обращением счетчик увеличивается на 1. При замещении выбирается блок с
наименьшим счетчиком. Недостаток – удаление из КЭШа блоков, которые используются
относительно редко, но промежуток между обращениями к ним небольшой вследствие
локализации.
Замещение, основанное на частоте обращений. Блоки организованы в виде стека.
Часть
блоков верхней части стека – новый
раздел. При успешном обращении к КЭШу
нужный блок перемещается наверх. Если блок уже находился в новом разделе, его счетчик
не меняется, иначе счетчик увеличивается на 1. Счетчики блоков, к которым происходят
частые обращения за короткий промежуток времени, останутся неизменными. Если
запрошен блок, которого нет в КЭШе, для замены выбирается блок с наименьшим
счетчиком
