7.-Конспект-лекций.-ОП.01-ОСиСреды.-09.02.07_compressed. Конспекты лекций по дисциплине оп. 01 Операционные системы и среды

• Название: Конспекты лекций по дисциплине оп. 01 Операционные системы и среды
• Дата: 04.10.2022
• Размер: 1 Mb.
• Имя файла: 7.-Конспект-лекций.-ОП.01-ОСиСреды.-09.02.07_compressed.pdf
• Тип: Конспект; #713942
• страница: 5 из 6

Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса.
Сегментно-страничная организация разделения памяти

Данный метод представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов.
Виртуальное пространство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страницы, которые нумеруются в пределах сегмента.
Оперативная память делится на физические страницы. Загрузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура которой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов, в которой указываются адреса таблиц страниц для всех сегментов данного процесса. Адрес таблицы сегментов загружается в специальный регистр процессора, когда активизируется соответствующий процесс.
Достоинство: данный механизм поддерживается процессорами, поэтому работает быстрее.
Недостаток: большие объемы таблиц.
Принцип кэширования данных в ОС
Кэш-память - это способ организации совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным за счет динамического копирования в "быстрое" ЗУ наиболее часто используемой информации из "медленного" ЗУ.
Кэш-памятью часто называют не только способ организации работы двух типов запоминающих устройств, но и одно из устройств - "быстрое" ЗУ. Оно стоит дороже и, как правило, имеет сравнительно небольшой объем. Важно, что механизм кэш-памяти является прозрачным для пользователя, который не должен сообщать никакой информации об интенсивности использования данных и не должен никак участвовать в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами.

В системах, оснащенных кэш-памятью, каждый запрос к оперативной памяти выполняется в соответствии со следующим алгоритмом:
1. Просматривается содержимое кэш-памяти с целью определения, не находятся ли нужные данные в кэш-памяти; кэш-память не является адресуемой, поэтому поиск нужных данных осуществляется по содержимому - значению поля "адрес в оперативной памяти", взятому из запроса.
2. Если данные обнаруживаются в кэш-памяти, то они считываются из нее, и результат передается в процессор.
3. Если нужных данных нет, то они вместе со своим адресом копируются из оперативной памяти в кэш-память, и результат выполнения запроса передается в процессор. При копировании данных может оказаться, что в кэш-памяти нет свободного места, тогда выбираются данные, к которым в последний период было меньше всего обращений, для вытеснения из кэш-памяти. Если вытесняемые данные были модифицированы за время нахождения в кэш-памяти, то они переписываются в оперативную память. Если же эти данные не были модифицированы, то их место в кэш- памяти объявляется свободным.
Контрольные вопросы
1. Расскажите про функции управления памятью в ОС?
2. Какие типы адресов используют ОС?
3. Охарактеризуйте методы распределения памяти в ОС?
4. Что такое кэширования данных в ОС?
Лекция 13
Алгоритмы посещения страниц
План
1. Страничная организация памяти (также таблицы страниц)
2. Сегментная организация пямяти (таблицы сегментов)
3. Страничное прерывание (page fauet) и виртуальная память
4. Механизмы замещения страниц: Алгоритм Belady, FIFO Алгоритм LRU (Last recently used) – наименее используемое, Not Frequently Used (алгоритм clock – часовой)
5. Рабочее множество
6. Алгоритм Page Fault Frequency

Организация памяти в виде страниц борется с двумя проблемами:
1. Внешней фрагментацией – используются блоки фиксированного размера в виртуальной и физической памяти, т.е. все запросы на выделение памяти будут кратны, не будет оставаться некратных зон.
2. Внутренней фрагментацией – блоки достаточно малого размера, поэтому (К) будет мал.
С точки зрения программиста:

Процессам виртуальное адресное пространство предоставляется непрерывным, от байта 0 до байта N;

N зависит от аппаратной поддержки (например 32бита — адрресное пространство 4Гб), делится соответственно.

В реальности виртуальные страницы распределены по страницам физической памяти далеко не непрерывно и не один к одному. Это два разных мира – физические страницы и виртуальные страницы. Это ключевой аспект, который надо понимать.
С точки зрения менеджера памяти:

Эффективное использование памяти из-за очень низкой внутренней фрагментации.

Внешняя фрагментация полностью отсутствует и не нужно дефрагментировать.
С точки зрения защиты:

Процесс имеет доступ только к своему адресному пространству.
Допущение – все страницы виртуальной памяти всегда находятся в страницах физической памяти.
Не будем думать, что есть только виртуальные страницы, а физических – их нет, т.е. полное отображение виртуальной и физической памяти.
Предположим, что все страницы резидентно в памяти, это необходимо, чтобы понять как работает трансляция адресов.
Трансляция адресов
Трансляция виртуального адреса: Виртуальный адрес состоит из двух частей: номер виртуальной страницы (VPN) и смещение внутри страницы
Номер виртуальной страницы (VPN- virtual page number) это индекс в таблице страниц (Pagetable).
Запись в таблице страниц (PTE – page table entry) содержит номер фрейма
(PFN –page frame number).
Номер фрейма – это номер физической страницы.
Фрейм – это страница физической памяти.
Смысл таблицы страниц – одна запись в таблице страниц (PTE) на одну страницу виртуального адресного пространства (VPN), отображает VPN на PFN.
Какая виртуальная страница соответствует какому фрейму физической памяти.

Трансляция адресов
Есть виртуальный адрес, состоящий из двух частей:
1. №виртуальной страницы, по нему идет поиск в таблице страниц и находится № фрейма, он составляет одну часть физического адреса;
2. Смещение – берется напрямую – вторая часть физического адреса.
По новому адресу осуществляется поиск уже в физической памяти и доступ к данным.
Существуют два процесса 0 и 1, у 0 есть две страницы у 1 процесса четыре страницы. И мы видим, что они могут отображаться как угодно, вплоть до того, что две виртуальные страницы могут отображаться на одной физической.
Зачастую это бывает полезно, простор для манипуляций ограниченный и в этом состоит вся прелесть виртуального адресного пространства.
Страничная организация памяти — Пример
-32битная разрядность адресов
-Размер страницы 4096байт
-VPN длиной 20бит, смещение 12бит (20+12=32бита)
-Преобразуем виртуальный адрес 0* 43456 323
— № вирт. страницы смещение внутри страницы
-VPN=43456 смещение=323
-Допустим, что в ячейке таблицы страниц по индексу 0*43456 находится значение фрейма PFN= 0*1002.
Получаем физический адрес 0*01002323
Таблица страниц (PTE)
Если есть таблица страниц, которая содержит преобразование адреса, то необходимо воспользоваться и нагрузить ее дополнительными функциями:

Добавить защиту доступа;

Добавить дополнительную вспомогательную информацию (например, используется эта вирт.страница или нет, был ли к ней когда-либо осуществлен доступ, была ли в нее осуществлена запись…);

Таблица страниц превращается в сложную структуру данных, которые начинает использоваться множеством всяких дополнительных полей.
Все это нужно, чтобы сохранить память для других процессов, делать все быстро и не плодить десятки новых таблиц с данными – все по возможности хранить внутри таблицы РТЕ.
Приведем пример стректуры таблицы страниц PTE. таблица страниц PTE
Если мы посмотрим на запись в РТЕ, то мы увидим, что туда можно поместить:

V— может ли использоваться данная запись РТЕ (valid or not) – бит валидности, бит присутствия;

R- был ли доступ к этой странице;

M– была ли страница модифицирована;

P– какие операции разрешены (битовая маска операций);

PFN– номер фрейма (как основной, как основная нагрузка).
Преимущества страничной памяти

Легко выделять физическую память
— Списки свободных фреймов, выделить фрейм
– просто удалить из списка свободных; — Внешняя фрагментация не проблема, т.к. фреймы одного размера;

Естественный подход
— Всей программе не нужно быть резидентной – это «побочный» продукт;
— Все страницы одного размера;
— Основа – устранение внешней фрагментации.
Недостатки страничной памяти

Внутренняя фрагментация
— Процессам может быть нужны размеры, некратные размеру страницы;
— По сравнению с размером адресного пространства, размер страницы очень мал.

Накладные расходы при обращении к памяти
– вначале к таблице страниц, а затем уже к памяти.
Решение: аппаратный КЭШ для обращений к таблице страниц (TLB translation lookaside buffer – буфер внутри процессора).

Большой объем памяти, требуемый для хранения таблиц страниц.
Один РТЕ на одну страницу в виртуальном адресном пространстве
Пример:
Архитектура х86 32-битное АП с 4КБ страницами = 2 в 20 степени РТЕ= 1048576записей РТЕ
4 байта на РТЕ = 4Мб памяти на таблицу страниц.
В ОС создаются отдельные таблицы страниц для каждого процесса.
Итого, например 25процессов * 4Мб = 100Мб
Соответственно нужны отдельные таблицы страниц для каждого процесса.
Решение: хранить таблицы страниц в страничной памяти)
Страничная организация памяти (обобщение)

Решает разные проблемы, типа фрагментации


Адресное пространство – линейный массив байтов

Разделяется на страницы одинакового размера (например 4Кб)

Использует таблицы страниц для отображения виртуальной страницы на физический фрейм
Сегментное распределение памяти (Сегментация)
Сегментация подходит к распределению памяти более «продвинуто», чем страничная — выделяются разные логические сегменты памяти: стек, код программы, куча, т.е. адресное пространство делится на логические блоки.
Блоки имеют свой размер, расположение и права доступа, например, куча – для динамической памяти программы – все это отдельные логические блоки памяти.
Их не нужно мешать в одно, поэтому следующим этапом было разделение всего названного и ввод виртуального адреса в виде пары: Сегмент, смещение.
Виртуальный адрес в виде – сегмент + смещение.
Страничная организация предполагает куски памяти, как в примере выше,
4096байт (4Кб), таких кусков можно брать сколько угодно.
Сегментация:

Позволяет разделить разные участки памяти в соответствии с их назначением

Динамический (изменяемый) размер у сегментов
Два варианта
1. Один сегмент на процесс – переменный раздел
2. Много сегментов на процесс — сегментация
Аппаратная поддержка сегментации

Одна пара база-предел(лимит) на сегмент

Сегменты идентифицируются №, который является индексом в таблице

Виртуальный адрес = пара <СЕГМЕНТ, СМЕЩЕНИЕ>

Физический адрес = база сегмента + смещение
Недостатки:

Все недостатки, присущие организации памяти разделами переменной длины присущи и сегментной организации

Внешняя фрагментация
Лучшим, как можно заметить является организация этих подходов в один.
Давайте объединим страничную и сегментную адресацию.
Архитектура х86 поддерживает и страничную и сегментную адресацию.

Сегменты используются для управления логическими блоками, обычно сегменты большие (помещают множество страниц).

Сегменты разбиваются на страницы, у каждого сегмента своя таблица страниц
В современных ОС достаточно ограниченно применяются сегменты, много их не применяется. Пример ОС Linux

Один сегмент кода ядра, Один сегмент данных ядра

Один сегмент кода пользователя, Один сегмент данных пользователя

Все сегменты организованы странично.
Страничная виртуальная память
Мы предполагали ранее, что вся память резидентная — не рассматривался вариант, что какой-либо страницы может не быть в физической памяти.
Сейчас, допустим, что адресное пространство может и не быть полностью резидентным. На практике так в основном и есть – память никогда не резидентна.

Процессов сотни, на них выделяется много виртуальной памяти и ее не хватит на отображение в физической памяти.
Например, 100 процессов 100П*4Гб=400ГБ ОП.
Соответственно какая то часть адресного пространства находится в физической памяти, какая то часть в некоторой вторичной памяти (понимается дисковая подсистема), абстрагируется от физической реализации.
С точки зрения опрерационной системы важно, что ОС использует основную память, как КЭШ.
У ОС есть медленная память (это дисковая подсистема), она может туда загружать процессы и выгружать их оттуда, а основная память используется как ограниченный ресурс, сродни классическому кэшированию.
Принцип работы достаточно простой – нужная страница перемещается в
свободный фрейм физической памяти из вторичной памяти. А если свободных
фреймов нет, то какая-либо страница выгружается на диск, таким образом
освобождается драгоценный фрейм физической памяти.
Важно отметить, запись во вторичной памяти происходит только тогда, когда страница в основной памяти была модифицирована, если она не была модифицирована, то соответственно и выгружать нечего.
Весь процесс происходит прозрачно для программы. Никакая программа не управляет напрямую, какую страницу ей выгрузить в основную память, какую загрузить.
Менеджер памяти операционной системы все абстрагирует и делает все прозрачным для программиста, чтобы он не «напрягался» на данную тему, это сложно реализовывать самостоятельно.
Контрольные вопросы
1. Как функционирует страничная организация памяти?
2. Как функционирует сегментная организация пямяти?
3.Что такое страничное прерывание и виртуальная память
4. Какие механизмы замещения страниц вы знаете?
Лекция 14
Сегментация памяти
План
1. Определение сегментации памяти;
2. Аппаратная реализация;
3. Сегментация без разбиения на страницы;
4. Сегментация с разбиением на страницы;
5. Совместное использование сегментов
Сегментация - это деление памяти на сегменты. Это механизм адресации, обеспечивающий существование нескольких независимых адресных пространств как в пределах одной задачи, так и в системе в целом для защиты задач от взаимного влияния. С точки зрения разработчиков программного обеспечения, сегментация дает удобный способ совместного использования информации несколькими процессами. Конкретный сегмент может использоваться совместно с другими без нарушения требований его

защиты. Сегментация также предполагает естественное разделение программных строк и данных и отделение модуля от модуля.
[1]
Аппаратная реализация
В системе, использующей сегментацию, адреса памяти компьютера состоят из идентификатора сегмента и смещения в сегменте. Аппаратный блок управления памятью
(MMU) ответственен за перевод сегмента и смещения в адрес физической памяти, и за выполнение проверок, чтобы удостовериться, что перевод может быть произведен и что ссылка на сегмент и смещение разрешены.
У каждого сегмента есть длина и связанный с ним набор полномочий (например, чтение, запись, выполнение). Процессу позволяют сделать ссылку в сегмент в том случае, если тип ссылки разрешен полномочиями, и если смещение в сегменте находится в диапазоне, определенном длиной сегмента. Иначе возникает ошибка сегментации.
Сегменты могут также использоваться, чтобы реализовать виртуальную память. В этом случае у каждого сегмента есть связанный флаг, указывающий, присутствует ли сегмент в оперативной памяти или нет. Если сегмент, к которому получают доступ, не присутствует в оперативной памяти, выбрасывается исключение, и операционная система считает сегмент в память из внешнего хранилища.
Сегментация - это один метод реализации защиты памяти. Разбивка на страницы - другой, и они могут быть объединены. Размер сегмента памяти обычно не фиксирован и может иметь размер в 1 байт.
Сегментация была реализована несколькими различными способами на различных аппаратных средствах, с или без разбивки на страницы. Сегментация памяти Intel x86 не соответствует ни одной модели и обсуждена отдельно ниже.
Сегментация без разбиения на страницы
Связанная с каждым сегментом информация, которая указывает, где сегмент расположен в памяти— база сегмента. Когда программа ссылается на ячейку памяти, смещение добавляется к базе, чтобы генерировать адрес физической памяти.
Реализация виртуальной памяти в системе, используя сегментацию без разбивки на страницы требует, чтобы все сегменты перемещались между оперативной памятью и внешней памятью. Когда сегмент загружен, операционная система должна выделить достаточное количество непрерывной свободной памяти, чтобы содержать весь сегмент.
Часто результатом фрагментации является невозможность выделить именно непрерывный участок заданной памяти.
Сегментация с разбиением на страницы
Вместо фактической ячейки памяти информация о сегменте включает адрес таблицы страниц для сегмента. Когда программа ссылается на ячейку памяти, смещение переводится в адрес памяти, используя таблицу страниц. Сегмент может быть расширен, просто выделением другой страницы памяти и добавлением ее к таблице страниц сегмента.
Реализация виртуальной памяти в системе, используя сегментацию с разбивкой на страницы обычно только перемещает отдельные страницы назад и вперед между оперативной памятью и внешней памятью, подобно простой страничной реализации адресации памяти. Страницы сегмента могут быть расположены где угодно в оперативной памяти и не должны быть непрерывными. Обыкновенно это приводит к уменьшению ввода/вывода между основной и внешней памятью, а также к уменьшению фрагментации памяти.

Совместное использование сегментов
Сегментирование физической памяти не только не позволяет виртуальной памяти отъедать физическую, но также даёт возможность совместного использования физических сегментов с помощью виртуальных адресных пространств разных процессов.
Если дважды запустить задачу А, то кодовый сегмент у них будет один и тот же: в обеих задачах выполняются одинаковые машинные инструкции. В то же время у каждой задачи будут свои стек и куча, поскольку они оперируют разными наборами данных.
При этом оба процесса не подозревают, что делят с кем-то свою память. Такой подход стал возможен благодаря внедрению битов защиты сегмента (segment protection bits).
Для каждого создаваемого физического сегмента ОС регистрирует значение bounds, которое используется MMU для последующей переадресации. Но в то же время регистрируется и так называемый флаг разрешения (permission flag). Поскольку сам код нельзя модифицировать, то все кодовые сегменты создаются с флагами RX. Это значит, что процесс может загружать эту область памяти для последующего выполнения, но в неё никто не может записывать. Другие два сегмента — куча и стек — имеют флаги RW, то есть процесс может считывать и записывать в эти свои два сегмента, однако код из них выполнять нельзя. Это сделано для обеспечения безопасности, чтобы злоумышленник не мог повредить кучу или стек, внедрив в них свой код для получения root-прав. Так было не всегда, и для высокой эффективности этого решения требуется аппаратная поддержка.
В процессорах Intel это называется “NX bit”.
Флаги могут быть изменены в процессе выполнения программы, для этого используется mprotect().
Под Linux все эти сегменты памяти можно посмотреть с помощью утилит /proc/{pid}/maps или /usr/bin/pmap.
Вот пример на PHP:

Здесь есть все необходимые подробности относительно распределения памяти.
Адреса виртуальные, отображаются разрешения для каждой области памяти. Каждый совместно используемый объект (.so) размещён в адресном пространстве в виде нескольких частей (обычно код и данные). Кодовые сегменты являются исполняемыми и совместно используются в физической памяти всеми процессами, которые разместили подобный совместно используемый объект в своём адресном пространстве.
Shared Objects — это одно из крупнейших преимуществ Unix- и Linux-систем, обеспечивающее экономию памяти.
Также с помощью системного вызова mmap() можно создавать совместно используемую область, которая преобразуется в совместно используемый физический сегмент. Тогда у каждой области появится индекс s, означающий shared.
Ограничения сегментации
Итак, сегментация позволила решить проблему неиспользуемой виртуальной памяти. Если она не используется, то и не размещается в физической памяти благодаря использованию сегментов, соответствующих именно объёму используемой памяти.
Но это не совсем верно.
Допустим, процесс запросил у кучи 16 Кб. Скорее всего, ОС создаст в физической памяти сегмент соответствующего размера. Если пользователь потом освободит из них 2
Кб, тогда ОС придётся уменьшить размер сегмента до 14 Кб. Но вдруг потом программист запросит у кучи ещё 30 Кб? Тогда предыдущий сегмент нужно увеличить более чем в два раза, а возможно ли это будет сделать? Может быть, его уже окружают другие сегменты, не позволяющие ему увеличиться. Тогда ОС придётся искать свободное место на 30 Кб и перераспределять сегмент.
Главный недостаток сегментов заключается в том, что из-за них физическая память сильно фрагментируется, поскольку сегменты увеличиваются и уменьшаются по мере того, как пользовательские процессы запрашивают и освобождают память. А ОС приходится поддерживать список свободных участков и управлять ими.
Фрагментация может привести к тому, что какой-нибудь процесс запросит такой объём памяти, который будет больше любого из свободных участков. И в этом случае ОС придётся отказать процессу в выделении памяти, даже если суммарный объём свободных областей будет существенно больше.
ОС может попытаться разместить данные компактнее, объединяя все свободные области в один большой чанк, который в дальнейшем можно использовать для нужд новых процессов и перераспределения.

Но подобные алгоритмы оптимизации сильно нагружают процессор, а ведь его мощности нужны для выполнения пользовательских процессов. Если ОС начинает реорганизовывать физическую память, то система становится недоступной.
Так что сегментация памяти влечёт за собой немало проблем, связанных с управлением памятью и многозадачностью.Нужно как-то улучшить возможности сегментации и исправить недостатки. Это достигается с помощью ещё одного подхода — страниц виртуальной памяти.
Сравнение сегментированной памяти с использованием одного адресного пространства.
Одно адресное пространство

Недостатки такой системы:
1. Один участок может полностью заполниться, но при этом останутся свободные участки. Можно конечно перемещать участки, но это очень сложно.
2. Эти проблемы можно решить, если дать каждому участку независимое адресное пространство, называемое сегментом.
[1]
Сегментированная память
Каждый сегмент может расти или уменьшаться независимо от других. Сегмент - это логический объект. В этом случае адрес имеет две части:
 номер сегмента
 адрес в сегменте
Преимущества сегментации:
1. Сегменты не мешают друг другу.

2. Начальный адрес процедуры всегда начинается с (n,0). Что упрощает программирование.
3. Облегчает совместное использование процедур и данных.
4. Раздельная защита каждого сегмента (чтение, запись).
[2]
Контрольные вопросы
1. Что такое сегментация памяти?
2. Как реализуется аппаратная сегментация?
3. Сегментация без разбиения на страницы?
4. Как работает сегментация с разбиением на страницы?
5. Как работает совместное использование сегментов?
Лекция 15
Основные концепции организации ввода-вывода
План
1. Система ввода-вывода;
2. Устройства ввода-вывода;
3. Менеджмент ввода-вывода;
4. Средства организации ввода-вывода.
Как известно, ввод / вывод считается одной из самых сложных областей проектирования операционных систем, в которой сложно применить общий подход из-за изобилия частных методов. Сложность возникает из-за огромного числа устройств ввода / вывода разнообразной природы, которые должна поддерживать ОС. При этом перед создателями ОС встает очень непростая задача - не только обеспечить эффективное управление устройствами ввода / вывода, но и создать удобный и эффективный виртуальный интерфейс устройств ввода / вывода, позволяющий прикладным программистам просто считывать или сохранять данные, не обращая внимание на специфику устройств и проблемы распределения устройств между выполняющимися задачами. Система ввода / вывода, способная объединить в одной модели широкий набор устройств, должна быть универсальной. Она должна учитывать потребности существующих устройств, от простой мыши до клавиатур, принтеров, графических дисплеев, дисковых накопителей, компакт-дисков и даже сетей. С другой стороны, необходимо обеспечить доступ к устройствам ввода / вывода для множества параллельно выполняющихся задач, причем так, чтобы они как можно меньше мешали друг другу.
Поэтому самым главным является следующий принцип: любые операции по управлению вводом / выводом объявляются привилегированными и могут выполняться только кодом самой ОС. Для обеспечения этого принципа в большинстве процессоров даже вводятся режимы пользователя и супервизора. Как правило, в режиме супервизора выполнение команд ввода / вывода разрешено, а в пользовательском режиме - запрещено.
Использование команд ввода / вывода в пользовательском режиме вызывает исключение, и управление через механизм прерываний передаётся коду ОС. Хотя возможны и более сложные системы, в которых в ряде случаев пользовательским программам разрешено непосредственное выполнение команд ввода / вывода.

Еще раз подчеркнем, что, прежде всего, мы говорим о мультипрограммных ОС, для которых существует проблема разделения ресурсов. Одним из основных видов ресурсов являются устройства ввода / вывода и соответствующее программное обеспечение, с помощью которого осуществляется управление обменом данными между внешними устройствами и оперативной памятью. Помимо разделяемых устройств ввода / вывода
(эти устройства допускают разделение посредством механизма доступа) существуют неразделяемые устройства. Примерами разделяемого устройства могут служить накопитель на магнитных дисках, устройство для чтения компакт-дисков. Это устройства с прямым доступом. Примеры неразделяемых устройств - принтер, накопитель на магнитных лентах. Это устройства с последовательным доступом. Операционные системы должны управлять и теми и другими устройствами, предоставляя возможность параллельно выполняющимся задачам использовать различные устройства ввода / вывода.
Можно назвать три основные причины, по которым нельзя разрешать каждой отдельной пользовательской программе обращаться к внешним устройствам непосредственно:
Необходимость разрешать возможные конфликты доступа к устройствам ввода / вывода. Например, две параллельно выполняющиеся программы пытаются вывести на печать результаты своей работы. Если не предусмотреть внешнее управление устройством печати, то в результате мы можем получить абсолютно нечитаемый текст, так как каждая программа будет время от времени выводить свои данные, которые будут перемежаться данными другой программы. Другой пример: ситуация, когда одной программе необходимо прочитать данные с некоторого сектора магнитного диска, а другой - записать результаты в другой сектор того же накопителя. Если операции ввода / вывода не будут отслеживаться каким-то третьим
(внешним) процессом-арбитром, то после позиционирования магнитной головки для первого запроса может тут же появиться команда позиционирования головки для второй задачи, и обе операции ввода / вывода не смогут быть выполнены корректно.
Желание увеличить эффективность использования этих ресурсов. Например, у накопителя на магнитных дисках время подвода головки чтения/записи к необходимой дорожке и обращение к определенному сектору может значительно (до тысячи раз)

превышать время пересылки данных. В результате, если задачи по очереди обращаются к цилиндрам, далеко отстоящим друг от друга, то полезная работа, выполняемая накопителем, может быть существенно снижена.
Ошибки в программах ввода / вывода могут привести к краху всех вычислительных процессов, ибо часть операций ввода / вывода осуществляется для самой операционной системы. В ряде ОС системный ввод/вывод имеет существенно более высокие привилегии, чем ввод/вывод задач пользователя. Поэтому системный код, управляющий операциями ввода / вывода, очень тщательно отлаживается и оптимизируется для повышения надёжности вычислений и эффективности использования оборудования.
Итак, управление вводом / выводом осуществляется операционной системой, компонентом, который чаще всего называют супервизором ввода / вывода. В перечень основных задач, возлагаемых на супервизор, входят следующие: супервизор ввода / вывода получает запросы на ввод/вывод от прикладных задач и от программных модулей самой операционной системы. Эти запросы проверяются на корректность, и если запрос выполнен по спецификациям и не содержит ошибок, он обрабатывается дальше, в противном случае пользователю (задаче) выдается соответствующее диагностическое сообщение о недействительности (некорректности) запроса; супервизор ввода / вывода вызывает соответствующие распределители каналов и контроллеров, планирует ввод/вывод (определяет очерёдность предоставления устройств ввода / вывода задачам, затребовавшим их). Запрос на ввод/вывод либо тут же выполняется, либо ставится в очередь на выполнение; супервизор ввода / вывода инициирует операции ввода / вывода (передаёт управление соответствующим драйверам) и в случае управления вводом/выводом с

использованием прерываний предоставляет процессор диспетчеру задач с тем, чтобы передать его первой задаче, стоящей в очереди на выполнение; при получении сигналов прерываний от устройств ввода / вывода супервизор идентифицирует их и передаёт управление соответствующей программе обработки прерывания; супервизор ввода / вывода осуществляет передачу сообщений об ошибках, если таковые происходят в процессе управления операциями ввода / вывода; супервизор ввода / вывода посылает сообщения о завершении операции ввода / вывода запросившему эту операцию процессу и снимает его с состояния ожидания ввода / вывода, если процесс ожидал завершения операции.
В случае, если устройство ввода / вывода является инициативным, управление со стороны супервизора ввода / вывода будет заключаться в активизации соответствующего вычислительного процесса (перевод его в состояние готовности к выполнению).
Таким образом, прикладные программы (а в общем случае - все обрабатывающие программы) не могут непосредственно связываться с устройствами ввода / вывода независимо от использования устройств (монопольно или совместно). Установив соответствующие значения параметров в запросе на ввод/вывод, определяющих требуемую операцию и количество потребляемых ресурсов, они могут передать управление супервизору ввода / вывода, который и запускает необходимые логические и физические операции.
Упомянутый выше запрос на ввод/вывод должен удовлетворять требованиям API той операционной системы, в среде которой выполняется приложение. Параметры, указываемые в запросах на ввод/вывод, передаются не только в вызывающих последовательностях, создаваемых по спецификациям API, но и как данные, хранящиеся в соответствующих системных таблицах. Все параметры, которые будут стоять в вызывающей последовательности, поставляются компилятором и отражают требования программиста и постоянные сведения об операционной системе и архитектуре компьютера в целом. Переменные сведения о вычислительной системе (её конфигурация, состав оборудования, состав и особенности системного программного обеспечения) содержатся в специальных системных таблицах. Процессору, каналам прямого доступа в память, контроллерам необходимо передавать конкретную двоичную информацию, с помощью которой и осуществляется управление оборудованием. Эта конкретная двоичная информация в виде кодов и данных часто готовится с помощью препроцессоров, но часть её хранится в системных таблицах.
Контрольные вопросы
1. Зачем нужна система ввода-вывода?
2. Какие устройства ввода-вывода могут находится в ОС?
3. Как осуществляется менеджмент ввода-вывода?
4. Как организуется ввод-вывод?
Лекция 16
Работа ОС с устройствами ввода-вывода
План
1. режим обмена с опросом готовности УВВ;
2. режим обмена с прерываниями;

3. Структура ввода-вывода;
4. Совместное использования устройств.
В области технического обеспечения выделяется несколько основных принципов взаимодействия внешних устройств с вычислительной системой, в основе которого лежит единый интерфейс для их подключения, позволяющий возложить все специфические действия на контроллеры самих устройств. Тем самым конструкторы вычислительных систем переложили головную боль, связанную с подключением внешней аппаратуры, на разработчиков самой аппаратуры, заставляя их придерживаться определенного стандарта.
Похожий подход оказался продуктивным и в области программного подключения устройств ввода-вывода. Достаточно разделить устройства на относительно небольшое число типов, отличающихся по набору операций, которые могут быть ими выполнены, считая все остальные различия несущественными. Затем специфицировать интерфейсы между ядром операционной системы, осуществляющим некоторую общую политику ввода-вывода, и программными частями, непосредственно управляющими устройствами, для каждого из таких типов. При этом разработчики операционных систем получают возможность освободиться от написания и тестирования этих специфических программных частей, получивших название драйверов, передав эту деятельность производителям самих внешних устройств (рис.1).
Рис 1. Структура системы ввода-вывода
Два нижних уровня этой системы составляет hardware: сами устройства, непосредственно выполняющие операции, и их контроллеры, служащие для организации совместной работы устройств и остальной вычислительной системы. Следующий уровень составляют драйвера устройств ввода-вывода, скрывающие от разработчиков операционных систем особенности функционирования конкретных приборов и обеспечивающие четко определенный интерфейс между hardware и вышележащим уровнем – уровнем базовой подсистемы ввода-вывода, которая, в свою очередь,

предоставляет механизм взаимодействия между драйверами и программной частью вычислительной системы в целом.
Самым главным является следующий принцип организации управления вводом/выводом: любые операции по управлению вводом/выводом объявляются привилегированными и могут выполняться только кодом операционной системы. Для обеспечения этого принципа в большинстве процессоров вводятся режим пользователя и режим супервизора. В режиме супервизора выполнение команд ввода/вывода разрешено, а пользовательском режиме – запрещено.
В системах мультипрограммирования одним из основных видов ресурсов являются
УВВ и соответствующее программное обеспечение, с помощью которого осуществляется управление обменом данными между внешними устройствами и оперативной памятью.
Помимо разделяемых устройств ввода/вывода (эти устройства допускают разделение посредством механизма доступа) существуют неразделяемые устройства. Примерами разделяемого устройства являются HDD, CD-ROM – устройства с прямым доступом. К неразделяемым устройствам относятся принтеры – устройства с последовательным доступом.
Управление вводом/выводом осуществляется операционной системой, для чего в ее состав включается супервизор ввода/вывода, основными функциями которого является:
· получение запросов на ввод/вывод от прикладных задач и программных модулей самой ОС. Эти запросы проверяются на корректность, и если запрос выполнен по спецификациям и не содержит ошибок, он обрабатывается дальше, в противном случае пользователю (программе) выдается соответствующее диагностическое сообщение о недействительности (некорректности) запроса;
· вызов соответствующих распределителей каналов и контроллеров, планирование ввода/вывода (определяет очередность предоставления УВВ задачам). Запрос на ввод/вывод либо сразу выполняется, либо ставится в очередь на выполнение;
· инициирование операции ввода/вывода (передает управление соответствующим драйверам) и в случае управления вводом/выводом с использованием прерываний предоставление процессора диспетчеру задач с тем, чтобы передать его первой задаче, стоящей в очереди на выполнение;
· идентификация сигналов прерываний от УВВ и передача управления соответствующей программе обработке прерываний;
· передача сообщений об ошибках, если таковые происходят в процессе управления операциями ввода/вывода;
· посылка сообщения о завершении операции ввода/вывода запросившему эту операцию процессу и снятие его с состояния ожидания ввода/вывода, если процесс ожидал завершения операции ввода/вывода.
Запросы на ввод/вывод должны удовлетворять требованиям API той ОС, в среде которой выполняется приложение.
Имеются два основных режима ввода/вывода:
1. режим обмена с опросом готовности УВВ;
2. режим обмена с прерываниями.
2. Режимы управления вводом/выводом. Основные системные таблицы ввода/вывода.

1. Управление вводом/выводом осуществляет центральный процессор. В этом случае имеет место программный канал обмена данными между внешними устройствами и оперативной памятью). ЦП посылает устройству управления команду выполнить некоторое действие устройству ввода/вывода. Последнее исполняет команду, транслируя сигналы, понятные центральному процессору и устройству управления в сигналы, в сигналы понятные УВВ. Однако, быстродействие УВВ намного меньше быстродействия центрального процессора (рис. 2).
Рис. 2.
Поэтому сигнал готовности (транслируемый или генерируемый устройством управления и сигнализирующий процессору о том, что команда ввода/вывода выполнена и можно выдать новую команду для продолжения обмена данными) приходится очень долго ожидать, постоянно опрашивая существующую линию интерфейса на наличие или отсутствие нужного сигнала. Посылать новую команду, не дождавшись сигнала готовности, сообщающего об исполнении предыдущей команды, бессмысленно. До тех пор, пока не появится сигнал готовности, драйвер в цикле опрашивает УВВ, расходуя при этом ресурс процессора.
2. Гораздо выгоднее выдав команду ввода/вывода на время «забыть» об УВВ и перейти на выполнение другой программы. А появление сигнала готовности трактовать как запрос на прерывание от УВВ.
Режим обмена с прерываниями по своей сути является режимом асинхронного управления. Для того чтобы не потерять связь с устройством (после того как процессор выдал очередную команду по управлению обменом данными и переключился на выполнение других программ), может быть запущен отсчет времени, в течение которого устройство должно обязательно выполнить команду и выдать сигнал запроса на прерывание. Максимальный интервал времени, в течение УВВ или его контроллер должны выдать сигнал запроса на прерывание, называют установкой тайм-аута. Если это время истекло после выдачи устройству очередной команды, а устройство так и не ответило, то делается вывод о том, что связь с устройством потеряна и управлять им больше нет возможности. Пользователь и/или задача получают соответствующее диагностическое сообщение.
Многие устройства не допускают совместного использования. Такие устройства могут быть закрепленными, т.е. предоставленными некоторому вычислительному процессу. При этом вычислительные процессы не могут выполняться параллельно, т.к. они ожидают освобождения устройств ввода/вывода. Для организации использования многим параллельно выполняющимися задачами устройств ввода/вывода, которые не

могут быть разделяемыми, вводится понятие виртуальных устройств, позволяющие повысить эффективность вычислительной системы.
Понятие виртуального устройства основывается на понятии SPOOLing
(simultaneous peripheral operation on-line – имитация работы с устройством в режиме «он- лайн»). Главная задача спулинга создать видимость параллельного разделение УВВ с последовательным доступом, которое фактически должно использоваться только монопольно. Например, каждому вычислительному процессу можно предоставить не реальный, а виртуальный принтер и поток выводимых символов сначала направлять в специальный файл. Затем, по окончании виртуальной печати, в соответствии с принятой дисциплиной обслуживания и приоритетами приложений выводить содержимое спул- файла на принтер. Системный процесс, который управляет спул-файлом, называется спулером.
Контрольные вопросы
1. Как работает режим обмена с опросом готовности УВВ?
2. Как работает режим обмена с прерываниями?
3. Что из себя представляет собой структура ввода-вывода?
4. Как реализуется совместное использования устройств?
Лекция 17
Логическая и физическая организация файловой системы
План
1. Логическая организация ФС;
2. Физическая организация ФС;
3. Таблицы размещения файлов;
5. Нежурналируемые и журналируемые ФС.
Файловая система (ФС) — это часть операционной системы, включающая совокупность всех файлов на диске, служебные структуры, включая каталоги, системные программные средства.
Файл — это именованная область внешней памяти, в которую можно записывать и из которой можно считывать данные. Файловые системы поддерживают функционально различные типы файлов, напри-
- обычные файлы (ОС не контролирует содержимое этих файлов);
- каталоги (содержат системную информацию о наборе файлов);
- специальные файлы (фиктивные файлы, соответствующие устройствам ввода- вывода);
- отображаемые в память файлы и т. д.
Иерархическая структура файловой системы. Большинство файловых систем имеют иерархическую структуру. Структура может быть организованна как дерево (рис.
12, а) или как сеть (Unix) (рис. 12, б).
В древовидной структуре действует принцип: один файл — одно полное имя. В сетевой: один файл — много полных имен (за счет наличия уникального цифрового имени).
Атрибуты файлов. Понятие файл включает в себя не только данные, но и атрибуты. Атрибуты — это информация, описывающая свойства файла (тип, владелец,

пароль, информация для авторизации доступа, время создания и доступа, размер, признаки и пр.)
Набор атрибутов зависит от ОС. Значения атрибутов могут храниться в каталогах
(FAT) или в специальных таблицах, ссылки на которые хранятся в каталогах (NTFS).
Физическая организация файловой системы. Представление пользователя о ФС и физическое хранение файлов на диске имеют мало общего. Диск в общем случае состоит из пакета пластин. На каждой пластине — две поверхности. На каждой поверхности размечены дорожки, на которых хранятся данные. Дорожки нумеруются с нуля, начиная от края к середине. Для каждой поверхности пластины имеется магнитная головка, которая, переме-щаясь, может позиционироваться над каждой дорожкой. Все головки закреплены на одном механизме и перемещаются синхронно.
Дорожки одного радиуса на всех поверхностях называются цилиндром. Каждая дорожка делится на фрагменты, называемые секторами. Чаще размер сектора равен 512 байтам.
Сектор — наименьшая адресуемая единица обмена. Для поиска контроллер должен задать: номер цилиндра, поверхности и сектора.
ОС для работы с диском использует собственную единицу — кластер, или блок.Раз-мер кластера чаще всего равен 1024 байта. Увеличение объемов дисковых накопителей, а также размеров обрабатываемых файлов обусловило переход от понятия
«кластер», понимаемого как минимальный объем единовременного обмена данными в ПК
(запись/чтение/ передача), к более общему понятию «порция», или «отрезок». В ФС
FAT32 порцией назы-вается участок дискового пространства, состоящий из одного или
нескольких кластеров (блоков), содержащих непрерывную часть данных файла.
Дорожки и секторы создаются в результате низкоуровневого форматирования диска и не зависят от типа ОС. Диск может быть разделен на логические устройства —
разделы (тома): а, b, с, ... Разметку раздела под конкретный тип файловой системы выполняют процедуры логического форматирования. При этом определяется размер кластера и записывается информация о границах файлов и каталогов, поврежденных областях, о доступном пространстве. Также записывается загрузчик ОС. В одном разделе может быть создана только одна ФС, но любого доступного типа (FAT16, FAT32, NTFS и пр.).
На этапе разбиения диска на разделы в блоке данных первого физического сектора дис-ка (0 цилиндр, 0 поверхность, 1 сектор) с адреса 1BEh формируется таблица разделов
(Partition table), состоящая из 4-х шестнадцатибайтных строк. Обычно системную информацию, записанную в блок данных этого сектора в процессе форматирования, называют Master Boot Record (MBR).
Физическая организация FAT.

На этапе логического форматирования раздела (тома) диска под ФС FAT создаются четыре логических области:
• загрузочный сектор (boot sector), в который помещается программа загрузки ОС;
• таблица FAT, которая является таблицей размещения файлов (создаются её основная и резервная копии FAT1 и FAT2);
• корневой каталог — содержит 256 записей (для FAT16), или 65 535 записей (для
FAT32) по 32 байта каждая (для FAT32 он может находиться в любом месте диска);
• область данных — кластеры размером от 1 до 128 секторов.
Разрядность элемента таблицы FAT равна 16 бит (2 байта) для ФС FAT16 и 32 бита
(4 байта) для ФС FAT32. Она определяет количество кластеров, к которым может физически адресоваться ФС. В области данных для FAT16 это 65525 кластеров. Для
FAT32 это 288 435 445 кластеров.
Элемент в таблице FAT может принимать следующие значения: кластер свободен, за-нят и не последний, занят и последний, дефектный, резервный.
При запуске компьютера программа, запускаемая из главной загрузочной записи
(MBR), ищет активный раздел на жестком диске. Если активный раздел найден, то управле-ние передаётся программе находящейся в загрузочном секторе (boot sector) этого раздела, которая запускает операционную систему, установленную в этом разделе жесткого диска.
При необходимости обращения к какому-либо файлу, адрес начального кластера корне-вого каталога раздела считывается из загрузочного сектора раздела. Часть корневого каталога, относящаяся к искомому файлу, отыскивается в корневом каталоге по имени файла. Каждый элемент корневого каталога содержит для каждого файла, расположенного на диске: имя файла, адрес первого кластера файла, размер файла, дату и время создания, модификации, последнего доступа к файлу и номер элемента таблицы
FAT, содержащего адрес второго кластера файла. Каждый элемент таблицы FAT содержит (указывает) номер следующего кластера файла. Поэтому элемент таблицы FAT называется указателем. Одновременно, этот номер является номером элемента таблицы
FAT, который содержит адрес третьего кластера файла и т. д. до последнего кластера файла.
Существуют три основных способа физического размещения файлов на
диске
2
:
• способ непрерывного размещения;
• способ связанных блоков (цепочечный);
• способ индексированных блоков.
Рассматривая ранее физическую организацию ФС FAT, мы говорили о том, что в каж-дом элементе таблицы FAT хранится адрес (номер) кластера файла. Так было, когда объёмы жестких дисков были сравнительно не велики. Сейчас объёмы жестких дисков существенно выросли и достигают нескольких терабайт. Поэтому для реальных больших жестких дисков в каждом элементе таблицы FAT хранится не адрес отдельного кластера.
Содержимое элемента таблицы FAT зависит от способа физического размещения файла на диске.
1. Способ непрерывного размещения (рис. 13а, 13б).

В элементе таблицы FAT содержится адрес первого кластера порции данных на диске и количества кластеров в порции. Количество кластеров в порции в данном случае равно количеству кластеров в файле. Этот способ используется для хранения коротких файлов.
2. Способ связанных блоков (цепочечный). См. рис. 13в, 13г. Для хранения больших файлов.
В элементе таблицы FAT содержится адрес первого кластера порции данных файла на жестком диске, количество блоков в порции и номер элемента таблицы FAT, содержащего адрес (номер) первого кластера (блока) следующей порции данных файла.
Каждый кластер в порции данных содержит внутри себя индекс – указатель на последующий блок (кластер) внутри порции. На рис. 13в, 13 г для простоты изображен случай, когда количество класте-ров в файле не превышает количества кластеров в порции.
3. Способ индексированных блоков (рис. 13д, рис. 13е). Для хранения сверхбольших файлов.
В элементе таблицы FAT содержится адрес первого индексного блока порции данных файла на жестком диске, номер элемента таблицы FAT, содержащего адрес индексного блока следующей порции данных файла (в случае больших файлов, для которых количество указателей на блоки одной порции столь велико, что не помещается в

один индексный блок (кластер)). На рис. 13в, 13 г количество кластеров в файле не превышает количества класте-ров в порции.
Физическая организация NTFS.
Файловая система NTFS была разработана в качестве основной для Windows NT.
Ее особенностями являются поддержка больших файлов и дисков (до 264 Гбайт), восстанавливаемость после сбоев, низкий уровень фрагментации.
Непрерывная область кластеров в NTFS называется отрезком. Порядковый номер кластера тома называется логическим номером кластера (Logical Cluster Number - LCN).
Порядковый номер кластера внутри файла называется виртуальным номером
кластера (Virtual Cluster Number - VCN).
Часть файла в отрезке характеризуется числом, образованным значениями трех параметров: LCN, VCN, К, где К — длина отрезка. Для хранения номера кластера используются 64-разрядные указатели. Весь том (раздел) — это последовательность кластеров.
Файловая система NTFSпредставляет собой один и более файлов. Каталог тоже файл. Основа структуры тома NTFS – главная таблица файлов MFT (Master File
Table). Это тоже файл. MFT содержит, по крайней мере, одну запись для каждого файла тома, включая одну запись для самой себя. MFT состоит из записей, размер которых равен размеру кластера и зависит от размера тома -1, 2, или 4 Кбайта. По умолчанию 2 Кбайта.
Порядковый номер записи в MFT является номером файла в томе. Изначально под зону
MFT отводится 12,5% объема тома NTFS.
Структура тома NTFS показана на рисунке 14. Загрузочный блок тома NTFS располагается в начале тома, а его копия - в середине области данных тома. Загрузочный блок содержит стандартный блок параметров BIOS, количество блоков в томе, а также начальные логические номера кластеров основной копии MFT и зеркальной копии MFT.
В NTFS файл целиком размещается в записи таблицы MFT, если это позволяет сделать его размер. В том же случае, когда размер файла больше размера записи MFT, в запись помещаются только некоторые атрибуты файла, а остальная часть файла размещается в отдельном отрезке тома (или нескольких отрезках).