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

16. Проведите обзор файловых систем (общая информация и fat)

Файлы являются логическими информационными блоками, создаваемыми процессами. Файлами управляет операционная система. Структура файлов, их имена, доступ к ним, их использование, защита, реализация и управление ими являются основными вопросами разработки операционных систем.

С позиции пользователя наиболее важным аспектом файловой системы является ее представление, то есть что собой представляет файл, как файлы именуются, какой защитой обладают, какие операции разрешено проводить с файлами.

Файловые системы хранятся на дисках. Большинство дисков может быть разбито на один или несколько разделов, на каждом из которых будет независимая файловая система. Сектор 0 на диске называется главной загрузочной записью (MBR) и используется для загрузки компьютера.

В конце MBR содержится таблица разделов. Из этой таблицы берутся начальные и конечные адреса каждого раздела. Один из разделов в этой таблице помечается как активный. При загрузке компьютера BIOS (базовая система ввода-вывода) считывает и выполняет MBR. Первое, что делает программа MBR, — находит расположение активного раздела, считывает его первый блок, который называется загрузочным, и выполняет его. Программа в загрузочном блоке загружает операционную систему, содержащуюся в этом разделе. Во всем остальном, кроме того, что раздел начинается с загрузочного блока, строение дискового раздела значительно различается от системы к системе.

Первым элементом является суперблок. В нем содержатся все ключевые параметры файловой системы, которые считываются в память при загрузке компьютера или при первом обращении к файловой системе. Обычно в информацию суперблока включаются «магическое» число, позволяющее идентифицировать тип файловой системы, количество блоков в файловой системе, а также другая важная административная информация.

В некоторых файловых системах используются файловые блоки, отслеживающиеся через таблицу размещения файлов (FAT — file allocation table), содержащуюся в оперативной памяти. В файловой системе FAT дисковое пространство любого логического диска делится на две области:

1. системную область (создается и инициализируется при форматировании, а впоследствии обновляется при манипулировании файловой структурой)

2. область данных (содержит файлы и каталоги, подчиненные корневому)

Картой области данных является Таблица размещения файлов (File Allocation Table - FAT) Каждый элемент таблицы FAT (12, 16 или 32 бит) соответствует одному кластеру диска и характеризует его состояние: свободен, занят или является сбойным кластером (bad cluster).

— Если кластер распределен какому-либо файлу (т.е., занят), то соответствующий элемент FAT содержит номер следующего кластера файла;

— последний кластер файла отмечается числом в диапазоне FF8h - FFFh (FFF8h - FFFFh);

— если кластер является свободным, он содержит нулевое значение 000h (0000h);

— кластер, непригодный для использования (сбойный), отмечается числом FF7h (FFF7h).

Таким образом, в таблице FAT кластеры, принадлежащие одному файлу, связываются в цепочки. Таблица размещения файлов хранится сразу после загрузочной записи логического диска, ее точное расположение описано в специальном поле в загрузочном секторе.

Существуют три версии файловой системы, использующей FAT: FAT-12, FAT-16 и FAT32 в зависимости от разрядности дискового адреса. Еще есть exFAT, введенная для больших съемных устройств.

17. Опишите алгоритм замещения страниц wsClock

Базовый алгоритм рабочего набора слишком трудоемок. Усовершенствованный алгоритм, основанный на алгоритме «часы», но также использующий информацию о рабочем наборе, называется WSClock. Изначально список страничных блоков пуст. При загрузке первой страницы она добавляется к списку. По мере загрузки следующих страниц они попадают в список, формируя замкнутое кольцо. В каждой записи содержится поле времени последнего использования из базового алгоритма рабочего набора, а также бит R и бит M.

При каждой ошибке отсутствия страницы проверяется страница, на которую указывает «стрелка», т.е. самая старая. Если бит R равен 1, то он просто сбрасывается в 0, а стрелка перемещается на следующую страницу. Если бит R равен 0, проверяется возраст страницы. Если он больше T, а бит M равен 0 – то страница удаляется. Если он больше T, а бит M равен 1, планируется ее запись на диск, а стрелка перемещается на следующую страницу. Если стрелка сделала «полный круг», но не удалилось ни 1 страницы – стрелка идет на второй круг. К тому моменту все запланированные записи страниц на диск выполнятся, и соответствующие биты M будут сброшены в 0, а значит, первая из старых страниц будет удалена. В случае, если ни 1 записи на диск запланировано не было – удаляется случайная страница с битами M и R равными 0 или (если таких нет) с битом R равным 0. +: простая реализация и хорошая производительность.

18. Опишите алгоритм замещения страниц lru

Замещение наименее востребованной страницы. Сложно реализовать практически. Для его полной реализации необходимо вести связанный список всех страниц, находящихся в памяти. В начале этого списка должна быть только что востребованная страница, а в конце — наименее востребованная. Сложность в том, что этот список должен обновляться при каждом обращении к памяти. Для поиска страницы в списке, ее удаления из него и последующего перемещения этой страницы вперед потребуется довольно много времени, даже если это будет возложено на аппаратное обеспечение (если предположить, что такое оборудование можно создать).

Существуют и другие способы реализации LRU с использованием специального оборудования. Самый простой: для реализации аппаратное обеспечение необходимо оснастить 64-разрядным счетчиком C, значение которого автоматически увеличивается после каждой команды. Кроме этого каждая запись в таблице страниц должна иметь довольно большое поле, чтобы содержать значение этого счетчика. После каждого обращения к памяти текущее значение счетчика C сохраняется в записи таблицы страниц, относящейся к той странице, к которой было это обращение. При возникновении ошибки отсутствия страницы операционная система проверяет все значения счетчика в таблице страниц, чтобы найти наименьшее из них. Та страница, к чьей записи относится это значение, и будет наименее востребованной.

23. Опишите алгоритм замещения страниц Second Chance

Модификация FIFO, исключающая проблему удаления часто востребуемой страницы через проверку бита R самой старой страницы. Если бит R удаляемой страницы равен 0 – она сразу удаляется. Если бит R удаляемой страницы равен 1 – он сбрасывается в 0, а страница помещается в конец списка страниц и время ее загрузки обновляется, как будто она только что поступила в память. Затем поиск продолжается. Предположим, что ошибка отсутствия страницы возникла на отметке времени 20. Самой старой является страница A, время поступления которой соответствует началу процесса и равно 0. Если бит R для страницы A сброшен, страница либо удаляется из памяти с записью на диск (если она измененная), либо просто удаляется (если она неизмененная). Но если бит R установлен, то A помещается в конец списка и ее «время загрузки» переключается на текущее (20). Также при этом сбрасывается бит R. А поиск подходящей страницы продолжается со страницы B. Алгоритм «второй шанс» занимается поиском ранее загруженной в память страницы, к которой за только что прошедший интервал времени таймера не было обращений. Если обращения были ко всем страницам, то алгоритм «второй шанс» превращается в простой алгоритм FIFO. У всех страниц на рис. а бит R установлен. ОС поочередно перемещает страницы в конец списка, очищая R при каждом добавлении страницы к концу списка. В конце концов она возвращается к странице A, у которой бит R теперь уже сброшен. И тогда страница A выселяется. Таким образом, алгоритм всегда завершает свою работу.

24. Опишите алгоритм диспетчеризации процессов RR с приоритетами

Cтратегия Round Robin (RR, круговая система) – это предоставление всем процессам по очереди одинаковых квантов времени. Название стратегии происходит от названия популярной в США карточной игры. При данной стратегии каждый процесс получает небольшой квант процессорного времени, обычно – 10-100 миллисекунд. После того, как это время закончено, процесс прерывается и помещается в конец очереди готовых процессов. Если процесс переходит в заблокированное состояние или завершает свою работу до истечения кванта времени, то переключение ЦП происходит именно в этот момент. Если всего имеется n процессов в очереди готовых к выполнению, и квант времени равен q, то каждый процесс получает 1/ n процессорного времени порциями самое большее по q единиц за один раз. Ни один процесс не ждет больше, чем (n-1) q единиц времени. При использовании приоритетов первым в очереди будет выставляться процесс с наивысшим приоритетом.

Механизм планирования должен оказывать предпочтение коротким заданиям с лимитируемым вводом-выводом, чтобы обеспечить хороший коэффициент использования устройств ввода-вывода; как можно быстрее определять характер задания, чтобы соответствующим образом ппланировать его выполнение. Многоуровневые очереди с обратными связями позволяют достичь этих целей.

Важной концепцией, лежащей в основе многих вытесняющих алгоритмов планирования (в том числе, RR), является приоритетное обслуживание. Оно предполагает наличие у процессов некоторой изначально известной характеристики – приоритета, на основании которого определяется порядок выполнения потоков. Чем выше приоритет, тем выше привилегии потока, тем меньше времени поток находится в очередях. Приоритет процесса назначается операционной системой при его создании, его значение включается в дескриптор процесса. При назначении приоритетов вновь созданному процессу ОС учитывается, является ли этот процесс системным или прикладным, каков статус пользователя, запустившего процесс (администратор, пользователь, часть и т.п.), было ли явное указание пользователя на присвоение процессу определенного уровня приоритета.

При диспетчеризации по приоритетам возникает проблема «голодания» (starvation) - ситуации, когда процессы с низким приоритетом могут никогда не исполниться и бесконечно ждать. Традиционным способом решение данной проблемы в операционных системах является учет возраста процесса (aging): c течением времени приоритет процесса повышается системой.

20. Опишите алгоритм замещения страниц Clock

Алгоритм Clock модифицирует список в циклический список в виде часов, где «стрелка» указывает на самую старую страницу. При возникновении ошибки отсутствия страницы проверяется та страница, на которую указывает стрелка. Если ее бит R равен 0 – страница удаляется, на ее место вставляется новая страница, а стрелка передвигается вперед на одну позицию. Если значение бита R равно 1, то он сбрасывается в 0, а стрелка перемещается на следующую страницу. Этот процесс повторяется до тех пор, пока не будет найдена страница с битом R равным 0.

21. Опишите алгоритм замещения страниц nru

Чтобы позволить операционной системе осуществить сбор полезной статистики востребованности страниц, большинство компьютеров, использующих виртуальную память, имеют два бита состояния, R и M, связанных с каждой страницей. Бит R устанавливается при каждом обращении к странице (при чтении или записи). Бит M устанавливается, когда в страницу ведется запись (то есть когда она модифицируется).

При возникновении ошибки отсутствия страницы ОС просматривает все страницы, и на основе текущих значений битов R и M делит их на 4 класса:

1. Класс 0 – в последнее время не было ни обращений, ни модификаций

2. Класс 1 – обращений в последнее время не было, но страница модифицирована (Сброс бита R без сброса бита M и приводит к возникновению страниц класса)

3. Класс 2 – в последнее время были обращения, но модификаций не было

4. Класс 3 – в последнее время были и обращения, и модификации

Алгоритм NRU удаляет произвольную страницу, относящуюся к самому низкому непустому классу. В этот алгоритм заложена идея, суть которой в том, что лучше удалить модифицированную страницу, к которой не было обращений по крайней мере за последний такт системных часов (обычно это время составляет около 20 мс), чем удалить интенсивно используемую страницу.

22. Опишите оптимальный алгоритм замещения страниц

На момент возникновения ошибки отсутствия страницы в памяти находится определенный набор страниц. К некоторым из этих страниц будет осуществляться обращение буквально из следующих команд (эти команды содержатся на странице). К другим страницам обращения может не быть и через 10, 100 или, возможно, даже 1000 команд. Каждая страница может быть помечена количеством команд, которые должны быть выполнены до первого обращения к странице. Оптимальный алгоритм замещения страниц гласит, что должна быть удалена страница, имеющая пометку с наибольшим значением. Если какая-то страница не будет использоваться на протяжении 8 млн команд, а другая какая-нибудь страница не будет использоваться на протяжении 6 млн команд, то удаление первой из них приведет к ошибке отсутствия страницы, в результате которой она будет снова выбрана с диска в самом отдаленном будущем. Компьютеры, как и люди, пытаются по возможности максимально отсрочить неприятные события. Единственная проблема алгоритма – невозможность его реализации. К тому времени, когда произойдет ошибка отсутствия страницы, у операционной системы не будет способа узнать, когда каждая из страниц будет востребована в следующий раз.