Горнец Н.Н., Рощин А.Г. Организация ЭВМ и систем (2006) (1186251), страница 55
Текст из файла (страница 55)
262 Семафоры Дейкстры. Семафор представляет собой переменную целого типа 5, над которой определены две операции: дочгп(5) (нли Р(о)) и ор(Ю) (или р(5)). Оригинальные обозначения Р и г', данные Дейкстрой и получившие широкое распространение в литературе, являются сокрашениями голландских слов ргоЬегеп— проверить и чегйойеп — увеличить. Операция довп(Я) проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция додав считается незавершенной. Важно отметить, что вся операция является неделимой, т.е. проверка значения, его уменьшение и, возможно, блокирование процесса производятся как одно атомарное действие, которое не может быть прервано.
Операция цр(Я) увеличивает значение семафора на 1. При этом если в системе присутствуют процессы, блокированные ранее прн выполнении довп на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции довп, т.е.
вновь уменьшил значение семафора. При этом также постулируется, что увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией. Чтобы прокомментировать работу семафора, рассмотрим пример. Представим себе супермаркет, посетители которого прежде чем войти в торговый зал должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется Ф свободных тележек — это начальное значение семафора. Каждый посетитель забирает одну из тележек, уменьшая тем самым число оставшихся на 1, и проходит в торговый зал — это аналог операции слово.
При выходе посетитель возвращает тележку на место, увеличивая число тележек на 1, — это аналог операции ор. Допустим, очередной посетитель обнаруживает, что свободных тележек нет — он вынужден «блокироваться» на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, ожидающий тележку посетитель «разблокируется», забирает тележку и проходит в зал. Таким образом, семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем Ф посетителям одновременно.
Положив Ф = 1, получим реализацию взаимного исключения. Семафор, начальное (и максимальное) значение которого равно 1, называется двоичным семафором (так как имеет только два состояния: «О» и «1»), Семафоры являются низкоуровневыми средствами синхронизации, для их корректной практической реализации необходимо наличие специальных, атомарных семафорных машинных команд. Мониторы Хоара. Идея монитора впервые сформулирована Ч.
Хоаром в 1974 г. В отличие от других средств, монитор представляет собой языковую консарукцию, т.е. некоторое средство, пре- 263 доставляемое языком программирования и поддерживаемое ком пилятором. Монитор — это совокупность процедур и структур дан ных, объединенных в программный модуль специального типа. По стулируются три основных свойства монитора: структуры данных, входящие в монитор, могут быть доступны только для процедур, входящих в этот монитор (таким образом монитор представляет собой некоторый аналог объекта в объект но-ориентированных языках и реализует инкапсуляцию данных); процесс «входит» в монитор путем вызова одной из его про цедур; в любой момент времени внутри монитора может находиться не более одного процесса.
Если процесс пытается попасть в монитор, в котором уже находится другой процесс, он блокируется, Таким образом, чтобы защитить разделяемые структуры данных, их достаточно поместить внутри монитора вместе с процедурами, представляющими критические секции для их обработки. Процедуры и данные монитора имеют особую семантику, поэтому первое условие может проверяться еще на этапе компиляции, кроме того, код для процедур монитора тоже может генерироваться особым образом, чтобы удовлетворялось третье условие. Поскольку организация взаимного исключения в данном случае возлагается на компилятор, число программных ошибок, связанных с организацией взаимного исключения, сводится к минимуму.
10.4. Управление оперативной памятью Память для процесса является таким же важным ресурсом, как и процессор. Процесс может выполняться только в том случае, если все необходимые данные находятся в оперативной памяти. Управление оперативной памятью предполагает решение следующих задач: распределение физической памяти ОЗУ между процессами; программная поддержка виртуальной памяти; подкачка; зашита памяти. Конкретные алгоритмы зависят от свойств применяемой ЭВМ. Для абстрактной ЭВМ рассмотрим страничную организацию ОЗУ, включающего в себя Ф физических страниц. Система команд машины позволяет адресовать до )г страниц памяти.
В этом случае частичные действия абстрактной ОС по управлению ОП (рис. ! 0.3) следующие. Операционная система формирует таблицу страниц (ТС). Каждая строка ТС содержит информацию о статусе соответствующей физической страницы, т. е, свободна она или принадле- 264 Рис. 10.3. Таблица страниц жит /-му процессу (в этом случае в строке помещается ссылка на контекст соответствующего процесса). Для каждого процесса, обрабатываемого в системе в данный момент времени (размещенного в БОП), ОС формирует программные структуры данных, в которых размещается информация контекста. Среди прочих значений в контексте размещается таблица страниц процесса (ТСП).
Из нее можно получить данные об используемых в процессе виртуальных страницах и их месторасположении. Под месторасположением понимают соответствие виртуальной страницы некоторой физической странице или указание координат места на ВЗУ, где размещена копия данной страницы. Соответственно поддержка решения задач управления ОП будет следующая. При поступлении процесса в БОП заполняется ТСП. В начальный момент из описателей процесса, сформированных на этапе обработки в БВП, выбирается список виртуальных страниц, который размещается в ТСП. Затем ОС анализирует содержимое ТСП и «приписывает» виртуальным страницам их физические эквиваленты (при этом идет загрузка содержимого соответствующих виртуальных страниц из внешней памяти в физические страницы ОЗУ).
Для виртуальных страниц процесса, которым не были выделены физические страницы, в ТСП устанавливается признак отсутствия физической страницы (этот признак также будет проставлен во все строки таблицы, соответствующие виртуальным страницам, не используемым процессом).
Формируется содержимое таблицы «откаченных» страниц процесса (ТОСП) (указывается номер виртуальной страницы и ее месторасположение во внешней памяти). Далее ОС из контекста данного процесса заполняет содержимое таблицы виртуальных страниц (ТВС) процессора и передает управление на начало выполнения процесса. В рассмотренном примере затронуты элементы решения задач Распределения физической памяти, поддержки использования 265 аппарата виртуальной памяти, подкачки страниц. На самом дел логика действий существенно сложнее. 10.5.
Планирование Важной проблемой, на решение которой ориентированы мно гие компоненты современных ОС, является определение задач планирования предоставления услуг или функций ОС. Традици онно эти задачи включают в себя планирование: очереди процессов на начало обработки процессором„ распределения времени ЦП между обрабатываемыми в мультипрограммном режиме процессами; порядка обработки заказов на обмен с ВУ; порядка обработки прерываний; использования ОЗУ (организация свопинга). В целом, комплексное решение задач планирования в ОС определяет основные эксплуатационные качества каждой конкретной системы.
При планировании очереди процессов на начало обработки ЦП могут применятся как примитивные стратегии организации очереди ЯРО, так и стратегии, учитывающие порядок поступления в очередь и объем ресурсов, декларированных процессами для использования. В общем случае очередь процессов в БВП может предоставляться как объединение подочередей, где каждая подочередь включает в себя определенные классы процессов (например, такая классификация может строиться на объеме запрашиваемых ресурсов и/или типе процесса). При этом возможно определение приоритета каждой из очередей (сначала рассматриваются непустые очереди с наименьшим приоритетом).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
