Калюжа

13. Основным решением проблем, связанных с совместным использованием памяти файлов и т.д., является запрет одновременной записи и чтения разделенных (общих) данных более, чем одним процессом. Иными словами, необходимо взаимное исключение. Это означает, что в момент, когда один процесс использует разделяемые данные, другому процессу это делать запрещено. В рассмотренном примере (см.дальше) эта ситуация возникла из-за того, что процесс В начал работу с одной из совместно используемых переменных до того, как процесс А ее закончил. Часть программы, в которой есть обращение к совместно используемым данным, называется критической областью. Если удастся избежать одновременного нахождения процессов в критической области, можно избежать состязаний. Несмотря на то, что это требование исключает состязания, оно не достаточно для правильной совместной работы квазипараллельных процессов и эффективного использования данных. Для этого необходимо выполнение 4-х условий.

1) Два процесса не должны одновременно находиться в критических областях (в программе, но в одно и тоже время).

2) В программе не должно быть предложений о скорости или количестве процессов.

3) Процесс, находящийся в критической области не может, или не должен блокировать другой процесс.

4) Недопустима ситуация, в которой процесс неопределенно долго ждет попадания в критическую область.

ЗАПРЕЩЕНИЯ ПРЕРЫВАНИЙ И ПЕРЕМЕННЫЕ БЛОКИРОВКИ

Попытка аппаратного решения проблемы

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

Рассмотрим программные решения

Пусть имеется одна совместно используемая переменная блокировки, изначально = 0. Если процесс хочет попасть в критическую область, он предварительно считывает значение переменной блокировки; если переменная = 0, то процесс изменяет ее на 1 и входит в критическую область; если переменная = 1, то процесс ждет, пока ее значение не изменится на 0. Т.о. 0 означает, что ни одного процесса в критической области нет, а 1 – наоборот, что есть процессы в критической области. У этого метода те же проблемы, что и в примере с каталогом спулера, а именно: 1 процесс считывает переменную блокировки, обнаруживает, что она = 0, но прежде, чем успевает изменить ее на 1, управление получает другой процесс, изменяющий ее на 1. Когда первый процесс снова получает управление, он тоже заменяет переменную блокировки на 1, и два процесса одновременно оказываются в критической области. Проблема не решается повторной проверкой значения переменной. Второй процесс может получить управление как раз после того, как первый процесс закончил вторую проверку, но еще не заменил значение переменной блокировки.

АЛГОРИТМ ПЕТЕРСОНА. КОМАНДА TSL

Датский математик Деккер был первым, кто разработал программное решение проблемы взаимного исключения. В 1981 г. Петерсон разработал алгоритм, состоящий из двух процедур, написанных на языке Си. Прежде, чем обратиться к совместно используемым переменным процесс вызывает процедуру enter region со своим номером 0 или 1 в качестве параметра, поэтому процессу при необходимости придется подождать, прежде чем войти в критическую область. После выхода из критической области процесс вызывает процедуру have region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область. Команда TSL используется в современных микропроцессорах

ПРИМИТИВЫ МЕЖПРОЦЕССОРНОГО ВЗАИМОДЕЙСТВИЯ

Оба решения корректны, но они обладают одним и тем же недостатком: использование активного ожидания. Они реализуют следующий алгоритм: перед входом в критическую область процесс проверяет, можно ли это сделать. Если нельзя, то процесс входит в цикл, ожидая возможности войти в критическую область. Этот алгоритм не только бесцельно тратит процессорное время, но, кроме того, может возникнуть ситуация, которую называют проблемой инверсий приоритета. Возможность вхождения в критическую область должен предвидеть пользователь. Примитивы блокируют процессы в случае запрета на вход в критическую область. Одной из простейших является пара примитивов sleep и wake up. Примитив sleep – это системный запрос, в результате которого вызывающий процесс блокируется, пока его не разбудит другой процесс. У системного запроса wake up один параметр – это процесс, который следует запустить. Также возможно наличие одного параметра у обоих запросов: адрес ячейки памяти, используемой для согласования запросов ожидания и запуска.

ПРОБЛЕМА ПРОИЗВОДИТЕЛЯ И ПОТРЕБИТЕЛЯ

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

14. СЕМАФОРЫ

В 1965 г. Дейкстра предложил использовать целую переменную для подсчета сигналов запуска, сохраненных на будущее. Им был предложен новый тип переменных – семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активации) или некоторым положительным числом, соответствующим количеству отложенных активирующих сигналов. Он предложил две операции: down и up. Операция down сравнивает значение семафора с нулем. Если значение семафора >0, то операция down уменьшает его, т.е. расходует один из отложенных сигналов активации, и возвращает управление. Если значение семафора равно нулю – то процедура не возвращает управление процессу, а он сам переводится в состояние ожидания. Все операции проверки значения семафора, его изменение или переводы процессов в состоянии ожидания, выполняется как единое, не делимое, элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания, либо блокировки операции. Операция up – увеличивает значение семафора. Если с ним связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой, напр., случайным образом, и ему разрешается завершить свою операцию down. Т.О. после операции up, примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и остается равным нулю. Но за то число ожидающих процессов уменьшается на единицу. Операция увеличения значения семафора и активации процесса также неделимы, т.е. ни один процесс не может быть блокирован во время выполнения операции up, также, как ни один процесс не может быть блокирован во время выполнения операции.

Семафоры. Решение проблемы производителя и потребителя

Проблему потерянных сигналов запуска можно решить с помощью семафоров. Стандартным решением является реализация операций down и up в виде системных запросов с запретом ОС всех прерываний на время проверки семафора, изменение его значения и возможного перевода процесса в состояние ожидания. Поскольку для выполнения всех этих действий требуется лишь несколько команд процессора запрет прерываний на столь короткий промежуток времени не приносит вреда. Если используется несколько процессов, каждый семафор необходимо защитить переменной блокировки с использованием команды ТSL, чтобы гарантировать обращение к семафору лишь одного процесса. Использование команды ТSL принципиально отличается от активного ожидания, при котором производитель и потребитель ждут опорожнения или пополнения буфера. Операции с семафором занимают лишь несколько микросекунд, тогда как активное ожидание может затянуться на время, больше нескольких порядков.

МЬЮТЕКСЫ

Взаимное исключение. Иногда используется упрощенная версия семафора, называемая мьютексом. Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса проста и эффективна, что делает их использование особенно удобным в случае потоков, действующих только в пространстве пользователя. Мьютекс – это переменная, которая может находиться в одном из двух состояний, блокированном и не блокированном. Потому для описания мьютекса нужен всего 1 бит, хотя чаще используется целочисленная переменная, у которой: 0 – не блокируемое состояние, а любое другое положительное целое, соответствует блокируемому состоянию. Значение мьютекса устанавливается двумя процедурами. Если поток (процесс) собирается войти в критическую область – он вызывает процедуру мьютекс-lock. Если Мьютекс не заблокирован (вход в критическую область разрешен), запрос выполняется и вызывающий поток может попасть в критическую область. Напротив, если Мьютекс заблокирован, вызывающий поток блокируется до тех пор, пока другой поток, находящийся в критической области не выйдет из нее, вызвав процедуру Мьютекс-anlock. Если мьютекс блокирует несколько потоков, то из них случайным образом выбирается один. Мьютексы легко реализуются в пространстве пользователя, если доступна команда DSL.

15. Под памятью будем понимать оперативную память ПК (RAM или ОЗУ), в отличие от жесткого диска (storage). Оперативной памяти для сохранения информации требуется постоянное электропитание.

Функции ОС по управлению памятью в мультипрограммной системе:

1) Отслеживание свободной и занятой памяти.

2) Выделение памяти процессам и освобождение памяти по мере их завершения.

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

4) Настройка адресов программы на конкретную область физической памяти.

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

16. Для идентификации переменных и команд на разных этапах жизненного цикла программы используются: символьные имена (метки), виртуальные адреса и физические адреса. Символьные имена присваивает программист при написании программы на алгоритмическом языке или ассемблере. Виртуальные адреса (математические или логические) выбирает транслятор, переводящий программу на машинный язык. Поскольку во время трансляции в общем случае неизвестно в какое место оперативной памяти будет загружена программа, то транслятор присваивает переменным или командам виртуальные (условные) адреса, обычно считая по умолчанию, что начальным адресом программы будет нулевой адрес. Физические адреса – соответствуют номерам ячеек памяти, где в действительности расположены или будут расположены переменные и команды. Совокупность виртуальных адресов процесса называется его виртуальным адресным пространством. Диапазон возможных адресов вирт. пространства у всех процессов является одним и тем же. Напр., при использовании 32-разрядных вирт. адресов этот диапазон определяется границами: 00000000₁₆ ÷ FFFFFFFF₁₆ , 2³² примерно равно 4 Gb

Если у ПК 32-разрядная шина адреса, максимальное значение вирт. памяти 4 Gb. Количество физической памяти не может превышать эту величину. ОЗУ делятся: динамические устройства; статические устройства.

Триггер – это спусковое устройство, которое может неопределенно долго находиться в одном из двух состояний устойчивого равновесия до тех пор, пока специальный сигнал не изменит его состояний. Т.О. триггер может хранить 1 бит информации. Самый простой триггер можно реализовать на 4-х транзисторах. На статических триггерах выполняют регистры разных типов, а также ячейки памяти статического ОЗУ. Такая статическая память используется довольно редко. Чаще используют динамическую память, которая проще в реализации и дешевле. Однако, у динамической памяти есть один существенный недостаток – нуждается в постоянно регенерации, т.е. в периодическом поддержании своих ячеек в прежнем состоянии. Принцип действия динамической памяти прост. Он основан на том, что некоторые транзисторы определенных типов имеют значительную емкость между их выводами. Заряд такой емкости (вирт.) = 1. Если заряжен – 1, разряжен – 0. Тем не менее, каждый процесс имеет собственное виртуальное адресное пространство, т.е. транслятор присваивает виртуальные адреса переменным и кодам каждой программы независимо. Совпадение адресов переменных и команд различных процессов не приводят к конфликтам, т.к. в том случае, когда эти переменные одновременно присутствуют в памяти, ОС отображает их на разные физические адреса.

Следует различать величину адресного пространства (физического и виртуального) и объем памяти, в которой это пространство помещается. Количество возможных сочетаний дает количество ячеек адресуемой физической памяти (2³²). Между тем в ячейке находится 1 бит, а число – кратное байту

Шина

12 32

Пример. На первых ПК была шина на 20 разрядов (шина адреса)и шина данных на 8 разрядов (РС ХР 8088 Intel) 32 р – 04 р, тактовая частота возрастет в 2 раза.

17. Содержимое назначенного процессу вирт. адресного пространства, т.е. коды команд, исходящие и промежуточные данные, а также результаты вычислений, представляют собой образ процесса. Во время работы процесса постоянно выполняются переходы от прикладных кодов к кодам ОС, которые либо явно вызываются из прикладных процессов как системные функции; либо вызываются как реакция на внешние события или исключительные ситуации, возникающие при некорректном поведении прикладных кодов. Для того, чтобы упростить передачу пр-я от прикладного кода к коду ОС, а также для легкого доступа модулей ОС к прикладным данным (например, для вывода их на внешние устройства) в большинстве ОС ее сегмент разделяют вирт. адресное пространство с прикладными сегментами активного процесса, т.е. сегменты ОС и сегменты активного процесса образуют единое виртуальное адресное пространство. Обычно вирт. адресное пространство процесса делится на две непрерывные части: системную; пользовательскую. В некоторых ОС, напр., Windows NT ОS/2 (консольная система), эти части делятся поровну и имеют одинаковый размер по 2 Gb. Хотя соотношение может быть и другим, напр., 1Gb для ОС, а остальное – пользователю. Часть вирт. адресного пространства каждого процесса, отводимая для сегментов ОС является идентичной для всех процессов. Поэтому при смене активного процесса заменяется только вторая часть вирт. адресного пространства, содержащая его индивидуальные сегменты, как правило, коды и данные прикладной программы.

ПВ 2…

ПВ 1 ПВ N Индивидуальные части ВП

Paged

Unpaged Общая часть виртуального адресного пространства

Системная часть виртуальной памяти ОС любого типа включает область, подвергаемую страничному вытеснению, Paged (листание); и область, на которую страничное вытеснение не распространяется Unpaged. В не вытесняемой области размещаются модули ОС, требующие быстрой реакции и/или постоянного присутствия в памяти. Напр., диспетчер потоков или код, который управляет заменой страниц памяти (загрузка – выгрузка страниц). Остальные модули ОС могут подвергаться страничному вытеснению как и пользовательские сегменты.

18. Все алгоритмы распределения (управления) памятью можно разделить на 2 класса: 1) Алгоритмы, в которых используется перемещение сегментов процессов между оперативной памятью и диском. 2) Алгоритмы, в которых внешняя память не используется.

Распределение памяти фиксированными разделами

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

Подсистема управления памятью в этом случае выполняет задачи:

1) Сравнивает объем памяти, требуемой для вновь поступившей задачи с размерами свободных разделов и выбирает подходящий размер.

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

Распределение памяти динамическими разделами

Каждому поступившему вновь на выполнение приложению на этапе создания процесса, выделяется вся необходимая ему память (если достаточный объем памяти отсутствует – процесс не создается). После завершения процесса память освобождается и на это место может быть загружен другой процесс. Таким образом, в производный момент времени ОЗУ представляет собой случайную последовательность занятых и свободных участков (разделов произвольного размера). Функции ОС, предназначенные для реализации данного метода следующие: 1) Ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков. 2) При создании нового процесса анализ требуемой памяти, просмотр таблицы свободных областей и выбор раздела, размер которого достаточен для размещения кодов и данных нового процесса. Такой выбор может осуществляться по разным правилам, напр.: «Первый попавшийся раздел достаточного размера»; «Раздел, имеющий наименьший достаточный размер».

3) Загрузка программы в выделенный раздел и корректировка таблиц свободных и занятых областей. Данный способ предполагает, что программный код не перемещается во время выполнения, а значит, настройка адресов может быть проведена единовременно во время загрузки. 4) После завершения процесса корректировка таблиц свободных и занятых областей.

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

Перемещаемые разделы

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

19. Swopping – подкачка. В мультипрограммном режиме помимо активного процесса, который в настоящий момент выполняется процессором, имеются приостановленные процессы, находящиеся в состоянии ожидания ввода/вывода или освобождения ресурсов. Образы таких неактивных процессов могут быть временно выгружены на диск до следующего цикла активности. К моменту, когда приходит очередь выполнения такого выгруженного процесса, его образ возвращается с диска в оперативную память (целиком). Если при этом выясняется, что свободного места в ОЗУ не хватает, то на диск загружается другой процесс. Такая подмена ОЗУ дисковой памятью позволяет повысить уровень мультипрограммирования. Транслятор, используя вирт. адреса, переводит программу в машинный код, как будто в ее распоряжении имеется однородная оперативная память большого объема. Виртуализация оперативной памяти осуществляется совокупностью программных кодов ОС и аппаратных средств процессора.

Включает решение следующих задач

1) Размещение данных в запоминающих устройствах разного типа. Напр., часть кода программы в ОЗУ, а часть – на диске.

2) Перемещение по мере необходимости данных между памятью и диском.

3) Выбор образов процессов, их частей, для перемещения из ОЗУ на диск и обратно.

4) Преобразование вирт. адресов в физические.

Виртуальная оперативная память может быть осуществлена на основе двух разных подходов: Swopping – образы процессов при этом выгружаются на диск и возвращаются в ОЗУ целиком (в чистом виде сейчас не используется); виртуальная память – между ОЗУ и диском перемещают части (сегменты, страницы и т.п.) образов процессов.

Swopping является частным случаем виртуальной памяти. Своппингу в чистом виде свойственна избыточность: когда ОС решает активизировать процесс, для его выполнения, как правило, не требуется загружать весь процесс, а достаточно загрузить небольшую часть кодового сегмента, подлежащей выполнению команды и частей сегментов данных, с которыми в данный момент работает программа, а также отвести место под стек. Аналогично при освобождении памяти для загрузки нового процесса часто не требуется выгружать другой процесс целиком. Достаточно вытеснить на диск только часть его образца. Кроме того, свопинг в чистом виде имеет еще один недостаток: при его использовании часто не удается загрузить для выполнения процесс, виртуальное адресное пространство которого превышает имеющуюся в наличии свободную память.

В настоящее время все множество реализаций вирт. памяти может быть представлено тремя классами:

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

2) Сегментная виртуальная память. Предполагает перемещение кодов сегментами, т.е. частями виртуального адресного пространства произвольного размера, полученного с учетом смыслового значения перемещаемых кодов.

3) Сегментно-страничная вирт. память. Использует двух уровневое деление: вирт. адресное пространство делится на сегменты, затем сегменты делятся на страницы. Единицей перемещения кодов является страница. Этот способ управления памятью объединяет в себе элементы обоих предыдущих подходов.

20. Виртуальное адресное пространство каждого процесса делится на части одинакового фиксированного системы размера, называемые виртуальными страницами. В общем случае размер виртуального адресного пространства процесса не кратен размеру страницы, поэтому последняя страница каждого процесса самодополняется фиктивной областью. Вся оперативная память компьютера также делится на части такого же размера, называемые физическими страницами (блоками). Размер страницы выбирается равным степени двойки. 4096, 512, 1024 – наиболее часто используемые страницы. Это позволяет упростить механизм преобразования адресов. При создании процесса ОС загружает о оперативную память несколько его виртуальных страниц (начальные страницы каждого сегмента и сегмента данных). Копия всего вирт. адресного пространства процесса находится на диске. Смежные виртуальные страницы не обязательно располагаются в смежных физических страницах. Для каждого процесса ОС создает таблицу страниц – информационную структуру, содержащую записи обо всех вирт. страницах процесса. Запись из таблицы называется дескриптером страницы и включает следующую информацию:

1) Номер физич. страницы, в которую загружена данная виртуальная страница.

2) Признак присутствия (флаг), устанавливаемый в единицу, если вирт. страница находится в ОЗУ.

3) Признак модификации страницы (флаг), который устанавливается в единицу всякий раз когда происходит запись по адресу, относящемуся к данной странице.