Какая из схем управления памятью пригодна для организации виртуальной памяти
Среди несимметричных алгоритмов шифрования наиболее известен:
Конфиденциальная система обеспечивает:
Какая из операционных систем больше подвержена тупикам?
Известно, что для доступа к памяти через таблицу страниц необходимо 80 нс, а для доступа через ассоциативную память – 10 нс. Частота попаданий в ассоциативную память при обращении к данным (hit ratio) соcтавляет 90%. Чему равно среднее время обращения к памяти?
Какое из условий для организации корректного взаимодействия двух процессов с помощью программного алгоритма выполнено для алгоритма "переменная-замок"?
Что такое выделенный ресурс?
Пусть у нас есть локальная вычислительная сеть, достаточно долгое время работающая с неизменной топологией и без сбоев. Какие алгоритмы маршрутизации гарантируют доставку пакетов данных по кратчайшему пути?
На каких параметрах может основываться долгосрочное планирование процессов?
Как правильно бороться с тупиком, который может возникнуть при использовании принтера?
Что такое мультипрограммная вычислительная система?
Если учет свободного дискового пространства диска размером 1Гб с блоком размером 2К осуществлять при помощи битового вектора, то для хранения этого вектора потребуется:
Устройство Page Table Entry
В реализации проекта Embox тип mmu_pte_t — это указатель.
Каждая запись PTE должна ссылаться на некоторую физическую страницу, а каждая физическая страница должна быть адресована какой-то записью PTE. Таким образом, в mmu_pte_t незанятыми остаются MMU_PTE_SHIFT бит, которые можно использовать для сохранения состояния страницы. Конкретный адрес бита, отвечающего за тот или иной флаг, как и набор флагов в целом, зависит от архитектуры.
- MMU_PAGE_WRITABLE — Можно ли менять страницу
- MMU_PAGE_SUPERVISOR — Пространство супер-пользователя/пользователя
- MMU_PAGE_CACHEABLE — Нужно ли кэшировать
- MMU_PAGE_PRESENT — Используется ли данная запись директории
Можно установить сразу несколько флагов:
Здесь vmem_page_flags_t — 32-битное значение, и соответствующие флаги берутся из первых MMU_PTE_SHIFT бит.
Какая категория средств связи получила наибольшее распространение в вычислительных системах?
Какие из перечисленных алгоритмов представляют собой частные случаи планирования с использованием приоритетов?
Пусть в вычислительную систему поступают пять процессов различной длительности по следующей схеме:
Номер процесса | Момент поступления в систему | Время исполнения |
---|---|---|
1 | 2 | 4 |
2 | 1 | 3 |
3 | 4 | 5 |
4 | 3 | 2 |
5 | 0 | 9 |
Чему равно среднее время ожидания процесса (waiting time) при использовании вытесняющего алгоритма SJF? При вычислениях считать, что процессы не совершают операций ввода-вывода, временем переключения контекста пренебречь.
Сегменты – это области памяти, предназначенные для:
Внутренняя фрагментация - это:
Сколько записей в таблице страниц в системе с 32-разрядной архитектурой и размером страницы 4К?
Какие из условий для организации корректного взаимодействия двух процессов с помощью программного алгоритма выполнены для алгоритма «строгое чередование»?
Для проверки системы на наличие в ней уязвимых с точки зрения безопасности мест обычно осуществляют ее сканирование. Какие аспекты системы такое сканирование обычно не затрагивает?
Какая из схем управления памятью пригодна для организации виртуальной памяти?
Какие из перечисленных функций базовой подсистемы ввода-вывода могут быть делегированы драйверам:
Термин race condition (условие гонки) относится
Какие из перечисленных ситуаций возникают синхронно с работой процессора:
Программная поддержка
- Выделение физических страниц из некоторого зарезервированного участка памяти
- Внесение соответствующих изменений в таблицы виртуальной памяти
- Сопоставление участков виртуальной памяти с процессами, выделившими их
- Проецирование региона физической памяти на виртуальный адрес
Многие ОС поддерживают имена файлов, состоящие из двух частей (имя+расширение). Это делается для того, чтобы
Размер страницы
В реальных (то есть не в учебных) системах используются страницы от 512 байт до 64 килобайт. Чаще всего размер страницы определяется архитектурой и является фиксированным для всей системы, например — 4 KiB.
С одной стороны, при меньшем размере страницы память меньше фрагментируется. Ведь наименьшая единица виртуальной памяти, которая может быть выделена процессу — это одна страница, а программам очень редко требуется целое число страниц. А значит, в последней странице, которую запросил процесс, скорее всего останется неиспользуемая память, которая, тем не менее, будет выделена, а значит — использована неэффективно.
С другой стороны, чем меньше размер страницы, тем больше размер страничных таблиц. Более того, при отгрузке на HDD и при чтении страниц с HDD быстрее получится записать несколько больших страниц, чем много маленьких такого же суммарного размера.
Отдельного внимания заслуживают так называемые большие страницы: huge pages и large pages [вики] .
Платформа | Размер обычной страницы | Размер страницы максимально возможного размера |
x86 | 4KB | 4MB |
x86_64 | 4KB | 1GB |
IA-64 | 4KB | 256MB |
PPC | 4KB | 16GB |
SPARC | 8KB | 2GB |
ARMv7 | 4KB | 16MB |
Действительно, при использовании таких страниц накладные расходы памяти повышаются. Тем не менее, прирост производительности программ в некоторых случаях может доходить до 10% [ссылка] , что объясняется меньшим размером страничных директорий и более эффективной работой TLB.
В дальнейшем речь пойдёт о страницах обычного размера.
Применение электронной подписи предполагает:
Page Fault
Page fault — это исключение, возникающее при обращении к странице, которая не загружена в физическую память — или потому, что она была вытеснена, или потому, что не была выделена.
В операционных системах общего назначения при обработке этого исключения происходит поиск нужной странице на внешнем носителе (жёстком диске, к примеру).
В нашей системе все страницы, к которым процесс имеет доступ, считаются присутствующими в оперативной памяти. Так, например, соответствующие сегменты .text, .data, .bss; куча; и так далее отображаются в таблицы при инициализации процесса. Данные, связанные с потоками (например, стэк), отображаются в таблицы процесса при создании потоков.
Выталкивание страниц во внешнюю память и их чтение в случае page fault не реализовано. С одной стороны, это лишает возможности использовать больше физической памяти, чем имеется на самом деле, а с другой — не является актуальной проблемой для встраиваемых систем. Нет никаких ограничений, делающих невозможной реализацию данного механизма, и при желании читатель может попробовать себя в этом деле :)
Для виртуальных страниц и для физических страниц, которые могут быть использованы при работе с виртуальной памятью, статически резервируется некоторое место в оперативной памяти. Тогда при выделении новых страниц и директорий они будут браться именно из этого места.
Исключением является набор указателей на PGD для каждого процесса (MMU-контексты процессов): этот массив хранится отдельно и используется при создании и разрушении процесса.
Выделение страниц
Итак, выделить физическую страницу можно с помощью vmem_alloc_page
Функция page_alloc() ищет участок памяти из N незанятых страниц и возвращает физический адрес начала этого участка, помечая его как занятый. В приведённом коде virt_page_allocator ссылается на участок памяти, резервированной для выделения физических страниц, а 1 — количество необходимых страниц.
Выделение таблиц
Тип таблицы (PGD, PMD, PTE) не имеет значения при аллокации. Более того, выделение таблиц производится также с помощью функции page_alloc(), только с другим аллокатором (virt_table_allocator).
После добавления страниц в соответствующие таблицы нужно уметь сопоставлять участки памяти с процессами, к которым они относятся. У нас в системе процесс представлен структурой task, содержащей всю необходимую информацию для работы ОС с процессом. Все физически доступные участки адресного пространства процесса записываются в специальный репозиторий: task_mmap. Он представляет из себя список дескрипторов этих участков (регионов), которые могут быть отображены на виртуальную память, если включена соответствующая поддержка.
brk — это самый большой из всех физических адресов репозитория, данное значение необходимо для ряда системных вызовов, которые не будут рассматриваться в данной статье.
ctx — это контекст задачи, использование которого обсуждалось в разделе “Виртуальный адрес”.
struct dlist_head — это указатель на начало двусвязного списка, организация которого аналогична организации Linux Linked List.
За каждый выделенный участок памяти отвечает структура marea
Поля данной структуры имеют говорящие имена: адреса начала и конца данного участка памяти, флаги региона памяти. Поле mmap_link нужно для поддержания двусвязного списка, о котором говорилось выше.
Ранее уже рассказывалось о том, как происходит выделение физических страниц, какие данные о виртуальной памяти относятся к задаче, и теперь всё готово для того, чтобы говорить о непосредственном отображении виртуальных участков памяти на физические.
Отображение виртуальных участков памяти на физическую память подразумевает внесение соответствующих изменений в иерархию страничных директорий.
Подразумевается, что некоторый участок физической памяти уже выделен. Для того, чтобы выделить соответствующие виртуальные страницы и привязать их к физическим, используется функция vmem_map_region()
В качестве параметров передаётся контекст задачи, адрес начала физического участка памяти, а также адрес начала виртуального участка. Переменная flags содержит флаги, которые будут установлены у соответствующих записей в PTE.
Основную работу на себя берёт do_map_region(). Она возвращает 0 при удачном выполнении и код ошибки — в ином случае. Если во время маппирования произошла ошибка, то часть страниц, которые успели выделиться, нужно откатить сделанные изменения с помощью функции vmem_unmap_region(), которая будет рассмотрена позднее.
Рассмотрим функцию do_map_region() подробнее.
Макросы GET_PTE и GET_PMD нужны для лучшей читаемости кода. Они делают следующее: если в таблице памяти нужный нам указатель не ссылается на существующую запись, нужно выделить её, если нет — то просто перейти по указателю к следующей записи.
В самом начале необходимо проверить, выровнены ли под размер страницы размер региона, физический и виртуальный адреса. После этого определяется PGD, соответствующая указанному контексту, и извлекаются сдвиги из виртуального адреса (более подробно это уже обсуждалось выше).
Затем последовательно перебираются виртуальные адреса, и в соответствующих записях PTE к ним привязывается нужный физический адрес. Если в таблицах отсутствуют какие-то записи, то они будут автоматически сгенерированы при вызове вышеупомянутых макросов GET_PTE и GET_PMD.
После того, как участок виртуальной памяти был отображён на физическую, рано или поздно её придётся освободить: либо в случае ошибки, либо в случае завершения работы процесса.
Изменения, которые при этом необходимо внести в структуру страничной иерархии памяти, производятся с помощью функции vmem_unmap_region().
Все параметры функции, кроме последнего, должны быть уже знакомы. free_pages отвечает за то, должны ли быть удалены страничные записи из таблиц.
try_free_pte, try_free_pmd, try_free_pgd — это вспомогательные функции. При удалении очередной страницы может выясниться, что директория, её содержащая, могла стать пустой, а значит, её нужно удалить из памяти.
нужны как раз для случая двухуровневой иерархии памяти.
Конечно, данной статьи не достаточно, чтобы с нуля организовать работу с MMU, но, я надеюсь, она хоть немного поможет погрузиться в OSDev тем, кому он кажется слишком сложным.
Система управления памятью должна обеспечить многопрограммный режим работы, используя аппаратные средства распределения оперативной памяти.
Существует два способа распределения памяти : статический и динамический.
При работе в многопрограммном режиме и статическом распределении оперативной памяти выделяется определенная область фиксированной памяти независимо от требований задачи.
При статическом распределении памяти используется статическая адресация, т.е. используется базовый адрес и смещение. При каждой загрузке программы ей назначается базовый адрес в области оперативной памяти.
При динамическом распределении оперативной памяти - выделяется необходимый объем памяти по запросу с учетом потребности задачи. Параллельность процессов обмена и обработки данных приводит к тому, что к оперативной памяти может обращаться несколько устройств (или программ) одновременно, потому требуется организовать очередь обслуживания и использовать концепцию виртуальной памяти. Один из компонентов ядра операционной системы - диспетчер памяти - организует трансляцию виртуальных адресов, используемых программами и другими компонентами ядра, в реальные адреса физической памяти.
Организация виртуальной памяти
Виртуальная память (Virtual Memory) представляет собой программно-аппаратное средство расширения пространства памяти, предоставляемой программе в качестве оперативной. Эта память физически реализуется в оперативной и дисковой памяти под управлением соответствующей операционной системы. Требуется так организовать работу процессора с дисковой памяти, чтобы возникала иллюзия работы только с оперативной памятью.
Виртуальное пространство памяти разбито на страницы фиксированного размера, а в физической оперативной памяти в каждый момент времени присутствует только часть из них. Остальные страницы хранятся на диске, откуда операционная система может "подкачать" их в физическую память, предварительно выгрузив на диск часть неиспользуемых в данный момент модифицированных страниц. Обращение процессора к ячейке виртуальной памяти, присутствующей в физической памяти, происходит обычным способом. Если же затребованная область в данный момент не отображена в физической памяти, процессор вырабатывает исключение (внутреннее прерывание), по которому операционная система программно организует замещение страниц, называемое свопингом (Swapping). Виртуальную память поддерживают процессоры, работающие в защищенном режиме, начиная с 80286, но реально ее широко стали использовать только в операционных системах и оболочках для 32-разрядных процессоров (80386 и далее). Максимальный объем виртуальной памяти определяется размером файла подкачки (Swap File), выделяемом на жестком диске для нужд виртуальной памяти.
Общепринятая в настоящее время концепция виртуальной памяти появилась в те далекие времена, когда вычислительные системы, научившись выполнять одну программу стали переходить на новый режим работы - работу в многозадачном (мультипрограммном) режиме. Концепция виртуальной памяти позволила решить целый ряд актуальных вопросов организации вычислений.
Встал вопрос о том, как разделить между разными задачами небольшой объем оперативной памяти, чтобы каждая задача выполнялась также, как она выполнялась бы в однопрограммном режиме и как управлять при этом распределением памяти.
К этому времени у программистов уже накопился опыт выполнения задач, программный код которых не помещался в слишком маленькую оперативную память.
Программистам пришлось делить такие программы на части и затем выполнять части программы независимо, организуя оверлейные структуры, которые загружались в основную память и выгружались из нее под управлением программы пользователя.
Система организации виртуальной памяти освободила программистов от этой работы. Она автоматически управляет обменом между двумя уровнями иерархии памяти: основной памятью и внешней (дисковой) памятью.
В многопрограммном режиме работы компьютер выполняет множество задач, каждой из которых отводится свое адресное пространство в оперативной памяти. Поэтому необходим механизм разделения небольшой физической памяти между различными задачами. Виртуальная память делит физическую память на блоки и распределяет их между различными задачами. При этом обеспечивается иллюзия того, что каждая задача и в самом деле исполняется на машине с огромным количеством реальной оперативной памяти.
Системы виртуальной памяти можно разделить на два класса: системы с фиксированным размером блоков, называемых страницами, и системы с переменным размером блоков, называемых сегментами.
Очевидно, что для реализации возможности автоматического выделения памяти каждой задаче в процессе ее выполнения (динамически), необходимо обеспечить эту возможность аппаратно. Для того, чтобы программа могла действительно воспользоваться виртуальной памятью (иллюзией очень большого количества реальной оперативной памяти) требуется еще и поддержка программного обеспечения. Задача управления виртуальной памятью возлагается на операционную систему. Различные операционные системы по разному решают вопросы управления памятью. Попробуем получить общее представление о работе виртуальной памяти.
Механизмы управления памятью решают две главные задачи:
- Трансляцию виртуального адресного пространства процесса на физическую память. Это позволяет ссылаться на конкретные адреса физической памяти потокам процесса, работающим в виртуальном адресном пространстве.
- Подкачку части содержимого памяти с диска, когда потоки пытаются задействовать больший объем физической памяти, чем тот, который имеется в наличии, и выгрузку страниц обратно по мере необходимости.
Страничный механизм является составной частью системы виртуальной памяти.
Страничное преобразование позволяет сохранить линейность адресов для прикладных программ, несмотря на то, что их работающие страницы располагаются в оперативной памяти в произвольном порядке. Программы работают со своим адресным пространством, так словно у каждой из них есть своя собственная линейно адресуемая оперативная память.
Применительно к виртуальной памяти различают три адресных пространства: логическое, линейное и физическое.
Рис.1. Отражение страниц дискового пространства
на пространство оперативной памяти.
В случае динамического распределения памяти (по запросу программы), адрес содержит номер виртуальной страницы и номер слова в странице. Для защиты памяти от записи и чтения другими процессами необходима соответствующая схема трансляции адреса, которая разрешает доступ к данной области памяти только определенной задаче.
Соответствие между физическим положением данных в памяти и адресом существует только для основной (оперативной) памяти, виртуальная память использует всю иерархическую структуру памяти как непрерывно адресуемую.
Для переадресации используется глобальная ( GDT) и локальная (LDТ) таблицы переадресации.
Большинство систем виртуальной памяти используют технику, называемую страничной организацией памяти [32, 37]. Любой процесс, реализуемый в компьютере, может обратиться к множеству адресов в памяти. Адреса могут формироваться с применением индексации, базовых регистров, сегментных регистров и другими путями. Эти программно формируемые адреса, называемые виртуальными адресами, формируют виртуальное адресное пространство. На компьютерах без виртуальной памяти виртуальные адреса подаются непосредственно на шину памяти и вызывают для чтения или записи слово в физической памяти с тем же самым адресом.
Когда используется виртуальная память, виртуальные адреса не передаются напрямую шиной памяти. Вместо этого они передаются диспетчеру памяти (MMU – Memory Management Unit), который отображает виртуальные адреса на физические адреса памяти, как показано на рис. 6.9. Здесь диспетчер памяти показан как часть микросхемы процессора, как обычно и бывает чаще всего. Но логически он мог бы быть отдельной микросхемой, как было в недавнем прошлом.
Рис. 6.9. Диспетчер памяти
Все имеющееся в настоящее время множество реализаций виртуальной памяти различается в основном способом структуризации виртуального адресного пространства.
В настоящее время выделяют три метода реализации виртуальной памяти.
- Страничная виртуальная память организует перемещение данных между основной памятью и диском страницами – частями виртуального адресного пространства фиксированного и сравнительно небольшого размера.
- Сегментная виртуальная память предусматривает перемещение данных сегментами – частями виртуального адресного пространства произвольного размера, полученного с учетом смыслового значения данных.
- Сегментно-страничная виртуальная память использует двухуровневое деление: виртуальное адресное пространство делится на сегменты, а затем сегменты делятся на страницы. Единицей перемещения данных является страница.
Для временного хранения сегментов и страниц на диске отводится специальная область либо специальный файл (страничный файл или файл подкачки – paging file). Текущий размер страничного файла является важным параметром, оказывающим влияние на возможности операционной системы: чем больше страничный файл, тем больше приложений может одновременно выполнять ОС (при фиксированном размере оперативной памяти). Однако необходимо понимать, что увеличение числа одновременно работающих приложений за счет увеличения размера страничного файла замедляет их работу, так как значительная часть времени при этом тратится на перемещение данных на диск и обратно.
Размер страничного файла в современных ОС является настраиваемым параметром, который выбирается администратором системы для достижения компромисса между уровнем программирования и быстродействием системы.
При страничной организации виртуальное адресное пространство каждого процесса делится на части одинакового, фиксированного для данной системы размера, называемые виртуальными страницами (Virtual pages). В общем случае размер виртуального адресного пространства не кратен размеру страницы, поэтому последняя страница дополняется фиксированной областью.
Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками, или кадрами). Размер страницы выбирается равным степени двойки: 1024, 2048, 4096 байт и т.д. Это позволяет упростить механизм преобразования адресов.
При создании процесса ОС загружает в операционную память несколько его виртуальных страниц (начальные страницы кодового сегмента и сегмента данных). Копия всего виртуального адресного пространства процесса находится на диске. Смежные виртуальные страницы не обязательно находятся в смежных физических страницах. Для каждого процесса ОС создает таблицу страниц – информационную структуру, содержащую записи обо всех виртуальных страницах процесса (рис. 6.10).
Рис. 6.10. Таблицы страниц виртуальной памяти
Запись таблицы (дескриптор страницы) включает следующую информацию:
- номер физической страницы (N ф.с.), в которую загружена данная виртуальная страница;
- признак присутствия Р, устанавливаемый в единицу, если данная страница находится в оперативной памяти;
- признак модификации страницы D, который устанавливается в единицу всякий раз, когда производится запись по адресу, относящемуся к данной странице;
- признак обращения А к странице, называемый также битом доступа, который устанавливается в единицу при каждом обращении по адресу, относящемуся к данной странице;
- другие управляющие биты, служащие, например, для целей защиты или совместного использования памяти на уровне страниц.
Перечисленные признаки в большинстве моделей процессов устанавливаются аппаратно схемами процессора при выполнении операций с памятью. Информация из таблицы страниц используется для решения вопроса о необходимости перемещения той или иной страницы между памятью и диском, а также для преобразования виртуального адреса в физический. Сами таблицы страниц, так же как и описываемые ими страницы, размещаются в оперативной памяти.
Поскольку процесс может задействовать большой объем виртуальной памяти (например, в Windows 2000 он равен 2 32 = 4 Гбайт), при использовании страницы объемом 4 Кбайт (2 12 ) потребуется 2 20 записей в таблице страниц для каждого процесса. Понятно, что выделять такое количество оперативной памяти под таблицы страниц нецелесообразно. Для преодоления этой проблемы большинство схем виртуальной памяти хранит таблицы страниц не в реальной, а в виртуальной памяти. Это означает, что сами таблицы страниц становятся объектами страничной организации. При работе процесса как минимум часть его таблицы страниц должна располагаться в основной памяти, в том числе запись о странице, выполняющейся в настоящий момент. Адрес таблицы страниц включается в контекст процесса. При активизации очередного процесса ОС загружает адрес его таблицы страниц в специальный регистр.
При каждом обращении к памяти выполняется поиск номера виртуальной страницы, содержащей требуемый адрес, затем по этому номеру определяется нужный элемент таблицы страниц и из него извлекается описывающая страницу информация. Далее анализируется признак присутствия, и если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический. Если же нужная виртуальная страница в данный момент выгружена на диск, то происходит страничное прерывание.
Выполняющий процесс переводится в состояние ожидания, активизируя процесс из очереди процессов, находящихся в состоянии готовности. Параллельно программа обработки страничного прерывания находит на диске требуемую виртуальную страницу и пытается ее загрузить в оперативную память. Если в памяти имеется свободная физическая страница, то загрузка выполняется немедленно. Если же свободных страниц нет, то на основании принятой в данной системестратегии замещения страниц решается вопрос о том, какую страницу следует выгрузить из оперативной памяти.
После того как выбрана страница, которая должна покинуть оперативную память, обнуляется ее бит присутствия и анализируется ее признак модификации. Если удаляемая страница за время последнего требования в оперативной памяти была модифицирована, то ее новая версия должна быть переписана на диск. Если нет, то принимается во внимание, что на диске уже имеется предыдущая копия этой виртуальной страницы, и никакой записи на диск не производится. Физическая страница объявляется свободной. Из соображений безопасности в некоторых системах освобождаемая страница обнуляется, чтобы невозможно было использовать содержимое выгруженной страницы. Для хранения информации о положении вытесненной страницы в страничном файле ОС может задействовать специальные поля таблицы страниц.
Виртуальный адрес при страничном распределении может быть представлен в виде пары ( P, Sv ), где Р – номер виртуальной страницы процесса (нумерация страниц начинается с 0), а Sv – смещение в пределах виртуальной страницы (рис. 6.11). Физический адрес также может быть представлен в виде пары ( N, Sf ), где N – номер физической страницы, а Sf – смещение а пределах физической страницы. Задача подсистемы виртуальной памяти состоит в отображении пары значений ( P, Sv ) в пару ( N, Sf ).
Рис. 6.11. Преобразование виртуального адреса
Чтобы понять механизм реализации этого отображения, следует остановиться на двух базисных свойствах страничной организации. Как уже отмечалось, объем страницы, как виртуальной, так и физической, выбирается равным степени двойки – 2 к ( k = 8 и более). Отсюда следует, что смещение Sv и Sf может быть получено отделением k младших разделов в двоичной записи виртуального и, соответственно, физического адреса страницы. При этом оставшиеся старшие разделы адреса представляют собой двоичную запись номера виртуальной и, соответственно, физической страницы. Дополнив эти номера к нулям, можно получить начальный адрес виртуальной и физической страниц.
Второе свойство – линейность адресного пространства виртуальной и физической страницы – приводит к тому, что Sf = Sv. Отсюда следует простая схема преобразования виртуального адреса в физический.
При обращении к памяти по некоторому виртуальному адресу ( P, Sv ) аппаратные схемы процессора выполняют следующие действия.
- Из специального регистра процессора извлекается начальный адрес АТ таблицы страниц активного процесса. С помощью сумматора по значениям АТ, Р, L (длина отдельной записи в таблице страниц) определяется адрес нужной записи в таблице страниц:
- Считывается номер соответствующей физической страницы – N.
- К номеру физической страницы присоединяется смещение Sv.
В итоге полученный физический адрес оперативной памяти представляется парой значений ( N, Sf ).
Рассмотрим пример, поясняющий основные характеристики организации страничной виртуальной памяти. Пусть компьютер имеет оперативную память объемом Еоп= 256 Мбайт, размер страницы выбран равным Естр= 4 Кбайт. В этом случае количество физических страниц равно
Nf = Еоп / Естр = 256*20 20 / 4*2 10 = 64.000 страниц.
Для отображения физического адреса произвольного байта оперативной памяти потребуется K = log2 256*20 2 0 = 28 двоичных разрядов.
Число разрядов для отображения смещения в странице M = log2 4 Кбайт = log2 4096 = 12.
Если процессор имеет 32-разрядную структуру, то на номер виртуальной страницы отводится 32-12=20 двоичных разрядов. Таким образом, число виртуальных страниц равно Nв = 220 (примерно 1 млн виртуальных страниц).
Для каждой виртуальной страницы в таблице страниц должна быть запись, содержащая номер виртуальной страницы (20 двоичных разрядов), начальный адрес соответствующей ей физической страницы плюс дополнительные разряды, характеризующие свойства страницы (присутствие, модификация, обращение и т.п.), на которые потребуется 1 байт. Поскольку адрес начала физической страницы кратен 4096, то на него достаточно 28 – 12 = 16 двоичных разрядов (остальные 12 разрядов заполняются нулями). Таким образом, одна запись таблицы страниц займет 20 + 16 + 8 = 44 двоичных разрядов или 6 байт. Общий объем таблицы страниц составит 6 * Nв = 6 Мбайт.
Реально при выборе структуры записи таблицы страниц нужно учитывать следующие факторы. Современные компьютеры позволяют наращивать объем оперативной памяти (например, в ПК она может почти достигать объема виртуальной памяти и даже более). Поэтому на адрес физической страницы в нашем примере следует выделить 32-12 = 20 двоичных разрядов. С другой стороны, нет необходимости в записи (дескрипторе) виртуальной страницы иметь поле с номером виртуальной страницы (20 разрядов), так как адрес нужной записи можно вычислять, как это было рассмотрено выше. Следовательно, в нашем примере длина записи должна быть равной 32 - 12 + 8 = 28 двоичным разрядам, т.е. с округлением до целого числа байт – 4 байт. Таким образом, для каждого выполняющегося в компьютере процесса ОС должна создать страничную таблицу размером 4 * Nв байт = 5 * 2 20 = 4 Мбайт.
Процедура преобразования виртуального адреса в физический без принятия специальных мер (кэширование активных страниц) занимает один цикл оперативной памяти, который затрачивается на считывание номера физической страницы из таблицы страниц. Поэтому любое обращение к ОП будет занимать 2 цикла вместо одного при работе без виртуальной памяти. Другим фактором, влияющим на производительность систем, являются затраты времени на обработку страничных прерываний. При неправильно выбранной стратегии замещения страниц может возникнуть ситуация, когда система тратит большую часть времени впустую на подкачку страниц из оперативной памяти на диск и обратно.
В каких случаях производится невытесняющее кратковременное планирование процессов?
Для оповещения операционной системы об отсутствии нужной страницы в памяти используется:
Файл autoexec.bat, который обычно входит в состав файлов корневого каталога во многих ОС компании Microsoft, относится к категории:
Разделение персонала, связанного с разработкой и эксплуатацией ЭВМ, на разработчиков, специалистов по эксплуатации, операторов и программистов произошло:
Схема выделения дискового пространства связным списком блоков не нашла широкого применения, так как:
Отметьте задачи файловой системы:
Известно, что в большинстве ОС файл представляет собой неструктурированную последовательность байтов и хранится на диске. Какой способ доступа обычно применяется к таким файлам?
Какие действия производит система, хранящая пароли пользователей на диске в зашифрованном виде, после того, как пользователь ввел свой пароль?
При модернизации некоторой операционной системы, поддерживающей только три состояния процессов: готовность, исполнение, ожидание, решено ввести два новых системных вызова. Один из этих вызовов позволяет любому процессу приостановить жизнедеятельность любого другого процесса (кроме самого себя), до тех пор, пока какой-либо процесс не выполнит второй системный вызов. Сколько новых операций над процессами появится в системе?
Пусть в вычислительную систему поступают пять процессов различной длительности с разными приоритетами по следующей схеме:
Номер процесса | Момент поступления в систему | Время исполнения | Приоритет |
---|---|---|---|
1 | 3 | 10 | 1 |
2 | 6 | 4 | 0 |
3 | 0 | 4 | 3 |
4 | 2 | 1 | 4 |
5 | 4 | 3 | 2 |
Чему равно среднее время между стартом процесса и его завершением (turnaround time) при использовании вытесняющего приоритетного планирования? При вычислениях считать, что процессы не совершают операций ввода-вывода, временем переключения контекста пренебречь. Наивысшим приоритетом является приоритет 0.
Использование блока диска размером 8К по сравнению с блоком размером 4К более выгодно, поскольку:
Возможность организации структур с перекрытиями обусловлена:
Если для некоторого набора активностей условия Бернстайна не выполняются, то набор активностей является:
Какие из вариантов реализации системного вызова read могут прочитать меньше байт, чем запросил процесс?
При доступе к файлу в распределенной ОС пользователь должен знать:
Чем обусловлена эффективность иерархической схемы памяти?
При модернизации некоторой операционной системы, поддерживающей только три состояния процессов: готовность, исполнение, ожидание, решено ввести два новых системных вызова. Один из этих вызовов позволяет любому процессу приостановить жизнедеятельность любого другого процесса (кроме самого себя), до тех пор, пока какой-либо процесс не выполнит второй системный вызов. Сколько новых переходов из состояния исполнение появится в системе?
Какая из схем управления памятью подвержена внутренней фрагментации?
В операционных системах, поддерживающих нити исполнения (threads) внутри одного процесса на уровне ядра системы, процесс находится в состоянии готовность, если:
Предположим, что сетевой сервер затоплен мощным потоком запросов. К какой категории атак относится это действие:
При доступе к файлу на другом компьютере в сетевой ОС пользователь должен знать:
Работа с Page Table Entry
Для работы с записей в таблице страниц, а так же с самими таблицами, есть ряд функций:
Эти функции возвращают 1, если у соответствующей структуры установлен бит MMU_PAGE_PRESENT
Сколько таблиц страниц поддерживает ОС Windows 2000 для каждого процесса?
Таблица страниц процесса - это:
Для некоторого процесса известна следующая строка запросов страниц памяти
Сколько ситуаций отказа страницы (page fault) возникнет для данного процесса при использовании алгоритма замещения страниц OPT (оптимальный алгоритм) и трех страничных кадрах?
Файловая система включается в состав ОС для того, чтобы:
Какие из перечисленных ниже компонентов входят в регистровый контекст процесса?
Множество процессов находится в тупиковой ситуации, если:
Отладка программ, содержащих очень большое количество семафоров, затруднена, так как:
Какую информацию принято скрывать, когда применяются криптографические методы защиты?
Что нужно сделать, чтобы обнаружить тупик?
Предположим, что в системе, где работают три пользователя, имеется 11 ресурсов, а потребность пользователей в ресурсах описывается следующей таблицей
Максимальная потребность в ресурсах | Выделенное пользователям количество ресурсов | |
---|---|---|
Первый пользователь | 8 | 5 |
Второй пользователь | 11 | 3 |
Третий пользователь | 3 | 1 |
Это состояние является
В чем состоит преимущество схемы виртуальной памяти по сравнению с организацией структур с перекрытием?
Пусть у нас имеется диск с 80 цилиндрами (от 0 до 79). Время перемещения головки между соседними цилиндрами составляет 1мс. Время же перевода головки с 79-го на 0-й цилиндр составляет всего 10 мс. В текущий момент времени головка находится на 45-ом цилиндре и двигается в сторону увеличения номеров цилиндров. Сколько времени будет обрабатываться следующая последовательность запросов на чтение цилиндров: 10, 6, 15, 71, 1, 62, для алгоритма C-SCAN (временами чтения цилиндров и смены направления движения пренебречь)?
Прием взаимоисключения применяется:
Для чего применяется журнализация в файловых системах?
Для чего по окончании работы с файлом принято выполнять операцию закрытия (close) файла?
Пусть в вычислительную систему поступают пять процессов различной длительности по следующей схеме:
Номер процесса | Момент поступления в систему | Время исполнения |
---|---|---|
1 | 2 | 4 |
2 | 1 | 3 |
3 | 4 | 5 |
4 | 3 | 2 |
5 | 0 | 9 |
Чему равно среднее время ожидания процесса (waiting time) при использовании вытесняющего алгоритма SJF? При вычислениях считать, что процессы не совершают операций ввода-вывода, временем переключения контекста пренебречь.
Чем обычно определяется максимальный размер сегмента?
Какой результат может иметь анализ бита модификации, входящего в состав атрибутов страницы?
Сколько процессов могут одновременно использовать одно и то же средство связи, пользуясь симметричной прямой адресацией?
Когда процесс, находящийся в состоянии "закончил исполнение", может окончательно покинуть систему?
Трансляция виртуального адреса в физический
Как уже писалось выше, при обращении к памяти трансляция адресов производится аппаратно, однако, явный доступ к физическим адресам может быть полезен в ряде случаев. Принцип поиска нужного участка памяти, конечно, такой же, как и в MMU.
Для того, чтобы получить из виртуального адреса физический, необходимо пройти по цепочке таблиц PGD, PMD и PTE. Функция vmem_translate() и производит эти шаги.
Сначала проверяется, есть ли в PGD указатель на директорию PMD. Если это так, то вычисляется адрес PMD, а затем аналогичным образом находится PTE. После выделения физического адреса страницы из PTE необходимо добавить смещение, и после этого будет получен искомый физический адрес.
Пояснения к коду функции.
mmu_paddr_t — это физический адрес страницы, назначение mmu_ctx_t уже обсуждалось выше в разделе “Виртуальный адрес”.
С помощью функции vmem_get_idx_from_vaddr() находятся сдвиги в таблицах PGD, PMD и PTE.
Какая техническая база характерна для первого периода вычислительной техники (1945-1955 г.г.)?
Какое из условий для организации корректного взаимодействия двух процессов с помощью программного алгоритма выполнено для алгоритма «флаги готовности»?
Какую стратегию управления памятью может реализовать алгоритм выталкивания страниц LRU?
Для некоторого процесса известна следующая строка запросов страниц памяти
Сколько ситуаций отказа страницы (page fault) возникнет для данного процесса при использовании алгоритма замещения страниц LRU (the Least Recently Used) и трех страничных кадрах?
 (1) программа для своего исполнения требует блока памяти необходимой ей длины. Наличие таких блоков переменной длины обеспечивает более плотное заполнение памяти при работе ЭВМ в мультипрограммном режиме и повышает коэффициент ее использования 
 (2) при каждом конкретном исполнении в зависимости от исходных данных некоторые части программы вообще не используются 
Номер 3
Ответ:
 (1) память, объем которой равен сумме объемов ОЗУ и внешних запоминающих устройств данного компьютера 
 (2) память, организация которой позволяет статически выделять программам блоки памяти произвольной длины при параллельном развитии нескольких процессов в мультипрограммном режиме 
 (3) память, используемая программистом при написании программ, и имеющая объем, равный максимально возможному при заданной разрядности адресной шины 
Упражнение 3: Номер 1
Ответ:
 (2) смещение в физической странице есть сумма по модулю 2 смещения в виртуальной странице и величины n , где n – определяется размером страницы ( V=2 n ) 
Номер 2
Ответ:
 (1) фиксированная длина страницы обеспечивает эффективное заполнение оперативной памяти в процессе выполнения программ 
 (3) отсутствует фрагментация оперативной памяти при обменен информацией между внешней и оперативной памятью 
Номер 3
Ответ:
Упражнение 4: Номер 1
Ответ:
 (2) увеличение степени использования оперативной памяти при параллельном развитии нескольких процессов в мультипрограммном режиме 
Номер 2
Ответ:
Упражнение 5: Номер 1
Ответ:
 (1) страницы имеют меньший объем, по сравнению с программой, что позволяет проводить более плотную упаковку оперативной памяти 
 (2) страницы используются программистом при написании программы, поэтому могут быть легко интерпретированы средства управления памяти для организации виртуальной памяти 
 (3) при страничном разбиении памяти объемы физической и виртуальной страниц совпадают, что позволяет заменять страницу оперативной памяти новой страницей из внешней памяти без возникновения проблем фрагментации памяти 
Номер 2
Ответ:
 (1) номер виртуальной страницы заменяется номером физической. Смещение в странице не меняется 
 (2) смещение, составляющее часть виртуального адреса, заменяется смещением в физической странице 
 (3) виртуальный адрес преобразуется как единое целое с помощью таблицы преобразования, уникальной для каждой выполняемой программы 
Упражнение 6: Номер 1
Ответ:
 (3) сложность обмена между оперативной и внешней памятью при выделении оперативной памяти пользователю 
 (4) невозможность выделения оперативной памяти, объем которой в точности равен программе пользователя 
Привет, Хабрахабр!
В предыдущей статье я рассказал про vfork() и пообещал рассказать о реализации вызова fork() как с поддержкой MMU, так и без неё (последняя, само собой, со значительными ограничениями). Но прежде, чем перейти к подробностям, будет логичнее начать с устройства виртуальной памяти.
Конечно, многие слышали про MMU, страничные таблицы и TLB. К сожалению, материалы на эту тему обычно рассматривают аппаратную сторону этого механизма, упоминая механизмы ОС только в общих чертах. Я же хочу разобрать конкретную программную реализацию в проекте Embox. Это лишь один из возможных подходов, и он достаточно лёгок для понимания. Кроме того, это не музейный экспонат, и при желании можно залезть “под капот” ОС и попробовать что-нибудь поменять.
Любая программная система имеет логическую модель памяти. Самая простая из них — совпадающая с физической, когда все программы имеют прямой доступ ко всему адресному пространству.
При таком подходе программы имеют доступ ко всему адресному пространству, не только могут “мешать” друг другу, но и способны привести к сбою работы всей системы — для этого достаточно, например, затереть кусок памяти, в котором располагается код ОС. Кроме того, иногда физической памяти может просто не хватить для того, чтобы все нужные процессы могли работать одновременно. Виртуальная память — один из механизмов, позволяющих решить эти проблемы. В данной статье рассматривается работа с этим механизмом со стороны операционной системы на примере ОС Embox. Все функции и типы данных, упомянутые в статье, вы можете найти в исходном коде нашего проекта.
Будет приведён ряд листингов, и некоторые из них слишком громоздки для размещения в статье в оригинальном виде, поэтому по возможности они будут сокращены и адаптированы. Также в тексте будут возникать отсылки к функциям и структурам, не имеющим прямого отношения к тематике статьи. Для них будет дано краткое описание, а более полную информацию о реализации можно найти на вики проекта.
- Расширение реального адресного пространства. Часть виртуальной памяти может быть вытеснена на жёсткий диск, и это позволяет программам использовать больше оперативной памяти, чем есть на самом деле.
- Создание изолированных адресных пространств для различных процессов, что повышает безопасность системы, а также решает проблему привязанности программы к определённым адресам памяти.
- Задание различных свойств для разных участков участков памяти. Например, может существовать неизменяемый участок памяти, видный нескольким процессам.
Что было прообразом современных ОС?
Какой уровень эталонной модели OSI/ISO отвечает за доставку информации от процесса-отправителя процессу-получателю?
Какой уровень эталонной модели OSI/ISO отвечает за создание контрольных точек при общении удаленных процессов?
Какие процессы могут обмениваться информацией через Pipe?
Виртуальный адрес
Page Global Directory (далее — PGD) — таблица (здесь и далее — то же самое, что директория) самого высокого уровня, каждая запись в ней — ссылка на Page Middle Directory (PMD), записи которой, в свою очередь, ссылаются на таблицу Page Table Entry (PTE). Записи в PTE ссылаются на реальные физические адреса, а также хранят флаги состояния страницы.
То есть, при трёхуровневой иерархии памяти виртуальный адрес будет выглядеть так:
Значения полей PGD, PMD и PTE — это индексы в соответствующих таблицах (то есть сдвиги от начала этих таблиц), а offset — это смещение адреса от начала страницы.
В зависимости от архитектуры и режима страничной адресации, количество битов, выделяемых для каждого из полей, может отличаться. Кроме того, сама страничная иерархия может иметь число уровней, отличное от трёх: например, на x86 нет PMD.
Для обеспечения переносимости мы задали границы этих полей с помощью констант: MMU_PGD_SHIFT, MMU_PMD_SHIFT, MMU_PTE_SHIFT, которые в приведённой выше схеме равны 24, 18 и 12 соответственно их определение дано в заголовочном файле src/include/hal/mmu.h. В дальнейшем будет рассматриваться именно этот пример.
На основании сдвигов PGD, PMD и PTE вычисляются соответствующие маски адресов.
Эти макросы даны в том же заголовочном файле.
Для работы с виртуальной таблицами виртуальной памяти в некоторой области памяти хранятся указатели на все PGD. При этом каждая задача хранит в себе контекст struct mmu_context, который, по сути, является индексом в этой таблице. Таким образом, к каждой задаче относится одна таблица PGD, которую можно определить с помощью mmu_get_root(ctx).
Для решения проблемы информационной безопасности необходимо:
В вычислительной системе со страничной организацией памяти и 32-х битовым адресом размер страницы составляет 8 Mбайт. Для некоторого процесса таблица страниц в этой системе имеет вид:
Номер страницы | Адрес начала страницы |
---|---|
1 | 0x00000000 |
2 | 0x02000000 |
5 | 0x06000000 |
6 | 0x10000000 |
Какому физическому адресу соответствует виртуальный адрес 0х00827432 ?
Средства авторизации:
Преимущество локального алгоритма замещения страниц перед глобальным состоит в том, что
При модернизации некоторой операционной системы, поддерживающей только три состояния процессов: готовность, исполнение, ожидание, принято решение ввести два новых системных вызова. Один из этих вызовов позволяет любому процессу приостановить жизнедеятельность любого другого процесса (кроме самого себя), до тех пор, пока какой-либо процесс не выполнит второй системный вызов. Сколько новых состояний процессов появится в системе?
Применение модели рабочего множества позволяет:
Аутентификация пользователя осуществляется для:
Для некоторого процесса, запущенного в вычислительной системе со страничной организацией памяти с использованием LRU алгоритма замещения страниц, выделение процессу 4 кадров памяти приводит к 11 page faults, а выделение 6 кадров памяти – к 9 page faults (вначале все кадры свободны). Какой вариант количества page faults для того же процесса и того же количества кадров может быть получен при использовании OPT алгоритма замещения страниц?
В функциях-методах мониторов Хора обычно реализовываются
В вычислительной системе моделируется движение самосвалов от карьера к заводу и обратно по дороге со стареньким мостом. Движение по мосту может осуществляться в обоих направлениях, но на нем не может быть одновременно более трех машин, иначе он рухнет. Каждый самосвал представлен программистом процессом следующей структуры:
Что может произойти в результате такого моделирования?
Чем запись в таблице страниц в схеме виртуальной памяти отличается от соответствующей записи в случае простой страничной организации?
Какие из перечисленных ситуаций возникают предсказуемо?
Возможность интерактивного взаимодействия пользователя и программы возникает с появлением:
Сколько удаленных адресов может иметь сетевой компьютер?
Какие из параметров запроса к жесткому диску обычно учитываются при планировании последовательности запросов?
Почему операционная система OS/2 не вправе претендовать на соответствие классу защиты C2?
Условные переменные в мониторах Хора обычно используются:
В маленьком ресторанчике, где готовят пиццу, работают отец и три его дочери. Приготовление пиццы требует трех ингредиентов: теста, соуса и сыра. Одна дочь должна непрерывно поставлять тесто, вторая - соус, третья - тертый сыр. Приготовление пиццы происходит следующим образом: первая дочь формирует из теста основу пиццы, после чего вторая дочь намазывает лепешку соусом, а третья - посыпает сыром. Отец берет подготовленную дочерьми пиццу и помещает ее в печь. Используя классические мониторы Хора, программист предложил следующую модель приготовления пиццы с помощью четырех процессов: для отца и для каждой из дочерей.
Что может произойти в результате такого моделирования?
Пусть у нас имеется диск с 80 цилиндрами (от 0 до 79). Время перемещения головки между соседними цилиндрами составляет 1мс. Время же перевода головки с 79-го на 0-й цилиндр составляет всего 10 мс. В текущий момент времени головка находится на 45-м цилиндре и двигается в сторону увеличения номеров цилиндров. Сколько времени будет обрабатываться следующая последовательность запросов на чтение цилиндров: 10, 6, 15, 71, 1, 62, для алгоритма SSTF (временами чтения цилиндров и смены направления движения пренебречь)?
В число событий, имеющих отношение к безопасности компьютерной системы, которые регистрирует система аудита, обычно не входит:
Предположим, что один из файлов в ОС Unix жестко связан с двумя различными каталогами, принадлежащими различным пользователям. Что произойдет, если один из пользователей удалит файл?
Для некоторого процесса известна следующая строка запросов страниц памяти
Сколько ситуаций отказа страницы (page fault) возникнет для данного процесса при использовании алгоритма замещения страниц FIFO (First Input First Output) и трех страничных кадрах?
Какому классу безопасности, согласно оранжевой книге, соответствует ОС Windows NT?
В операционных системах, поддерживающих нити исполнения (threads) внутри одного процесса на уровне ядра системы, наряду с блоками управления процессами (PCB) существуют структуры данных для управления нитями - TCB (Thread Control Block). Укажите, какие данные из перечисленных ниже хранятся, по вашему мнению, в TCB.
Рассмотрим две активности, P и Q :
P | Q |
---|---|
y=x+2 | z=x-3 |
f=y-4 | f=z+1 |
Набор из этих двух активностей является:
Аппаратная поддержка
Обращение к памяти хорошо описанно в этой хабростатье. Происходит оно следующим образом:
Процессор подаёт на вход MMU виртуальный адрес
Если MMU выключено или если виртуальный адрес попал в нетранслируемую область, то физический адрес просто приравнивается к виртуальному
Если MMU включено и виртуальный адрес попал в транслируемую область, производится трансляция адреса, то есть замена номера виртуальной страницы на номер соответствующей ей физической страницы (смещение внутри страницы одинаковое):
Если запись с нужным номером виртуальной страницы есть в TLB [Translation Lookaside Buffer], то номер физической страницы берётся из нее же
Если нужной записи в TLB нет, то приходится искать ее в таблицах страниц, которые операционная система размещает в нетранслируемой области ОЗУ (чтобы не было промаха TLB при обработке предыдущего промаха). Поиск может быть реализован как аппаратно, так и программно — через обработчик исключения, называемого страничной ошибкой (page fault). Найденная запись добавляется в TLB, после чего команда, вызвавшая промах TLB, выполняется снова.
Таким образом, при обращении программы к тому или иному участку памяти трансляция адресов производится аппаратно. Программная часть работы с MMU — формирование таблиц страниц и работа с ними, распределение участков памяти, установка тех или иных флагов для страниц, а также обработка page fault, ошибки, которая происходит при отсутствии страницы в отображении.
В тексте статьи в основном будет рассматриваться трёхуровневая модель памяти, но это не является принципиальным ограничением: для получения модели с бóльшим количеством уровней можно действовать аналогичным образом, а особенности работы с меньшим количеством уровней (как, например, в архитектуре x86 — там всего два уровня) будут рассмотрены отдельно.
Какой из вариантов адресации может использоваться для организации передачи информации через pipe?
К какому из перечисленных алгоритмов стремится поведение алгоритма RR по мере увеличения кванта времени?
Читайте также: