- •Дайте определение диспетчеру памяти и адресным пространствам. Поясните механизм использования базового и ограничительного регистров.
- •Приведите классификацию ос
- •Проведите обзор файловых систем (ntfs и ufs) Структура ntfs
- •Структура ufs
- •Дайте определение ос, опишите функции ос
- •Опишите основные этапы развития ос
- •Дайте определение виртуальной памяти, страничной организации памяти. Опишите структуру таблиц страниц
- •Опишите механизмы работы буфера быстрого преобразования адреса, многоуровневых и инвертированных таблицы страниц.
- •Дайте определение процессу и опишите блок управления процессом.
- •Опишите механизмы создания и уничтожения процессов Создание процесса
- •Удаление процесса
- •Опишите основные состояния процессов и возможные переходы между ними. Дайте определение переключению контекста.
- •Опишите механизмы диспетчеризации процессов.
- •Дайте определение свопинг. Опишите механизм управления свободной памятью при свопинге (битовые матрицы)
- •Опишите механизм управления свободной памятью при свопинге (связные списки и поиск по ним)
- •Проведите обзор аппаратного обеспечения пк
- •Дайте определение состязательной ситуации, критической области. Поясните механизм работы барьеров и обмена сообщениями
- •Проведите обзор файловых систем (общая информация и fat)
- •Опишите алгоритм замещения страниц wsClock
- •Опишите алгоритм замещения страниц lru
- •Опишите алгоритм замещения страниц ws.
- •Опишите алгоритм замещения страниц Clock
- •Опишите алгоритм замещения страниц nru
- •Опишите оптимальный алгоритм замещения страниц
- •Опишите алгоритм замещения страниц Second Chance
- •Опишите алгоритм замещения страниц fifo
- •Опишите алгоритм диспетчеризации процессов rr
- •Опишите алгоритм диспетчеризации процессов srtf
- •Опишите алгоритм диспетчеризации процессов fcfs
- •Опишите алгоритм диспетчеризации процессов sjf
- •Перечислите основные команды языка сценариев bat
- •Решите задачу производителя/потребителя через sleep и wakeup
- •Решите задачу производителя/потребителя через алгоритм Петерсона
- •Решите задачу производителя/потребителя через семафоры и мьютексы
- •Решите задачу обедающих философов через семафоры и мьютексы
Опишите алгоритм замещения страниц wsClock
Базовый алгоритм рабочего набора слишком трудоемок. Усовершенствованный алгоритм, основанный на алгоритме «часы», но также использующий информацию о рабочем наборе, называется WSClock. Изначально список страничных блоков пуст. При загрузке первой страницы она добавляется к списку. По мере загрузки следующих страниц они попадают в список, формируя замкнутое кольцо. В каждой записи содержится поле времени последнего использования из базового алгоритма рабочего набора, а также бит R и бит M.
При каждой ошибке отсутствия страницы проверяется страница, на которую указывает «стрелка», т.е. самая старая. Если бит R равен 1, то он просто сбрасывается в 0, а стрелка перемещается на следующую страницу. Если бит R равен 0, проверяется возраст страницы. Если он больше T, а бит M равен 0 – то страница удаляется. Если он больше T, а бит M равен 1, планируется ее запись на диск, а стрелка перемещается на следующую страницу. Если стрелка сделала «полный круг», но не удалилось ни 1 страницы – стрелка идет на второй круг. К тому моменту все запланированные записи страниц на диск выполнятся, и соответствующие биты M будут сброшены в 0, а значит, первая из старых страниц будет удалена. В случае, если ни 1 записи на диск запланировано не было – удаляется случайная страница с битами M и R равными 0 или (если таких нет) с битом R равным 0. +: простая реализация и хорошая производительность.
|
|
|
|
Работа алгоритма WSClock: а и б — пример того, что происходит, когда R = 1; в и г — пример того, что происходит, когда R = 0 |
Опишите алгоритм замещения страниц lru
Замещение наименее востребованной страницы. Сложно реализовать практически. Для его полной реализации необходимо вести связанный список всех страниц, находящихся в памяти. В начале этого списка должна быть только что востребованная страница, а в конце — наименее востребованная. Сложность в том, что этот список должен обновляться при каждом обращении к памяти. Для поиска страницы в списке, ее удаления из него и последующего перемещения этой страницы вперед потребуется довольно много времени, даже если это будет возложено на аппаратное обеспечение (если предположить, что такое оборудование можно создать).
Существуют и другие способы реализации LRU с использованием специального оборудования. Самый простой: для реализации аппаратное обеспечение необходимо оснастить 64-разрядным счетчиком C, значение которого автоматически увеличивается после каждой команды. Кроме этого каждая запись в таблице страниц должна иметь довольно большое поле, чтобы содержать значение этого счетчика. После каждого обращения к памяти текущее значение счетчика C сохраняется в записи таблицы страниц, относящейся к той странице, к которой было это обращение. При возникновении ошибки отсутствия страницы операционная система проверяет все значения счетчика в таблице страниц, чтобы найти наименьшее из них. Та страница, к чьей записи относится это значение, и будет наименее востребованной.