Мультипрограммирование. 
Мультипрограммирование

Вопрос 1

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

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

Для максимизации этого критерия в таких системах используется следующая схема функционирования:

• ? в начале работы системы формируется пакет заданий,
• ? каждое задание содержит требование к системным ресурсам,
• ? из этого пакета задач формируется мультипрограммная смесь, то есть, множество одновременно выполняемых задач.

Для одновременного выполнения выбираются задачи, предъявляемые разные требования к ресурсам, чтобы обеспечивалась сбалансированная загрузка всех устройств компьютера. Например, в мультипрограммной смеси желательно присутствие вычислительных задач и задач с интенсивным вводом и выводом.

Выбор нового задания из пакета зависит от внутренней ситуации в системе, то есть, выбирается выгодное для данной ситуации задание. Из этого следует, что в пакетных вычислительных системах нельзя гарантировать выполнение того или иного задания в течение определенного времени.

Рассмотрим варианты совмещения во времени операций ввода-вывода и вычислений.

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

• ? проверить состояние устройства,
• ? установить магнитную головку,
• ? установить начало листа,
• ? напечатать строку и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В системах реального времени мультипрограммная смесь представляет собой фиксированный набор заранее разработанных предсказуемых программ. Выбор конкретной программы производится по прерываниям от объекта или в соответствии с планом.

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

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

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

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

мультипрограммирование компьютер дескриптор семафор

Вопрос 2

Дескриптор сегмента — служебная структура в памяти, которая определяет сегмент. Длина дескриптора равна восьми байтам.

Дескрипторные таблицы — служебные структуры данных, содержащие дескрипторы сегментов.

В архитектуре x86 есть три вида дескрипторных таблиц:

Глобальная дескрипторная таблица (англ. Global Descriptor Table, GDT);

Локальная дескрипторная таблица (англ. Local Descriptor Table, LDT);

Таблица векторов прерываний (англ. Interrupt Descriptor Table, IDT);

Глобальная дескрипторная таблица одна. Она общая для всех задач. Её размер и расположение в физической памяти определяются регистром GDTR.

Дескрипторы LDT и сегментов задач (TSS) могут находиться только здесь.

Особенностью GDT является то, что у неё запрещён доступ к первому (№ 0) дескриптору. Обращение к нему вызывает исключение #GP, что предотвращает обращение к памяти с использованием незагруженного сегментного регистра.

Локальная дескрипторная таблица.

В отличие от GDT, LDT может быть много (соответственно количеству задач (потоков), но не обязательно). Каждая задача может иметь свою.

Размер и расположение LDT в линейной памяти определяются дескриптором LDT из GDT (но это не означает, что размер LDT может быть больше 65 536 байт).

Первый дескриптор LDT (№ 0) использовать можно.

Таблица прерываний глобальна. Размещение в физической памяти определяется регистром IDTR.

При возникновении прерывания (внешнего, аппаратного, или вызванного инструкцией Int):

из IDT выбирается дескриптор шлюза, соответственно номеру прерывания;

проверяются условия защиты (права доступа);

при соблюдении условий защиты выполняется переход на подпрограмму-обработчик этого прерывания;

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

Если длина каждого блока может задаваться, соответствуют «дыры» в виртуальном адресном пространстве, такие блоки называются сегментами. Как правило, один сегмент соответствует коду или данным одного модуля программы. Со страницей или сегментом могут быть ассоциированы права чтения записи и исполнения.

Такая адресация реализуется аппаратно. Процессор имеет специальное устройство, называемое диспетчером памяти или, как его называли в старой русскоязычной литературе, УУП (Устройство Управления Памятью, ср. MMU — Memory Management Unit). В некоторых процессорах, например в MC68020 или MC68030 или в некоторых RISC-системах, это устройство реализовано на отдельном кристалле; в других, таких как х86 или современные RISC-процессоры, диспетчер памяти интегрирован в процессор.

В PDP-11 сегментов всего восемь, поэтому дескрипторы каждого из них размещаются в отдельном регистре (на самом деле, регистров не восемь, а шестнадцать — восемь для пользовательского адресного пространства и восемь для системного). На 32-разрядных машинах количество сегментов измеряется тысячами, а страниц — иногда и миллионами, поэтому приходится прибегать к более сложной схеме.

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

Большинство реальных программ используют далеко не все адресное пространство процессора, соответственно таблица трансляции не обязательно держит все допустимые дескрипторы. Поэтому практически все диспетчеры памяти имеют еще один регистр — ограничитель длины таблицы трансляции. Страницы или сегменты, селектор которых превосходит ограничитель, не входят в виртуальное адресное пространство процесса. Как правило, диспетчер памяти имеет также кэш (cache) дескрипторов — быструю память с ассоциативным доступом. В этой памяти хранятся дескрипторы часто используемых страниц. Алгоритм доступа к памяти по виртуальному адресу page: off set состоит из следующих шагов.

• — проверить, существует ли страница page вообще. Если страницы не существует, возникает особая ситуация ошибки сегментации (segmentation violation).
• — попытаться найти дескриптор страницы в кэше.
• — если его нет в кэше, загрузить дескриптор из таблицы в памяти.
• — проверить, имеет ли процесс соответствующее право доступа к странице, иначе также возникает ошибка сегментации.
• — проверить, находится ли страница в оперативной памяти. Если ее там нет, возникает особая ситуация отсутствия страницы или страничный отказ (page fault). Как правило, реакция на него состоит в том, что вызывается специальная программа-обработчик (trap — ловушка), которая загружает требуемую страницу с диска. В многопоточных системах во время такой загрузки может исполняться другой процесс.
• — если страница есть в памяти, взять из ее дескриптора физический адрес phys_addr.
• — если мы имеем дело с сегментной адресацией, сравнить смещение в сегменте с длиной этого сегмента. Если смещение оказалось больше, также возникает ошибка сегментации.
• — произвести доступ к памяти по адресу phys_addr[offset].

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

Во-первых, мы можем связать с каждой задачей свою таблицу трансляции, а значит и свое виртуальное адресное пространство. Благодаря этому даже в многозадачных ОС мы можем пользоваться абсолютным загрузчиком. Кроме того, программы оказываются изолированными друг от друга, и мы можем обеспечить их безопасность.

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

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

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

В большинстве систем со страничным диспетчером свободная память отслеживается при помощи битовой маски физических страниц. В этой маске свободной странице соответствует 1, а занятой — 0. Если кому-то нужна граница, система просто ищет в этой маске установленный бит. В результате виртуальное пространство программы может оказаться отображено на Физические адреса очень причудливым образом, но это никого не волнует — скорость доступа ко всем страницам одинакова.

В-четвертых, система может обеспечивать не только защиту программ друг от друга, но в определенной мере и защиту программы от самой себя — например, от ошибочной записи данных на место кода или попытки исполнить данные.

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

Перечисленные преимущества настолько серьезны, что считается невозможным реализовать многозадачную систему общего назначения, такую как UNIX или System/390 на машинах без диспетчера памяти.

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

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

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

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

После того, как выбрана страница, которая должна покинуть оперативную память, анализируется ее признак модификации (из таблицы страниц). Если выталкиваемая страница с момента загрузки была модифицирована, то ее новая версия должна быть переписана на диск. Если нет, то она может быть просто уничтожена, то есть соответствующая физическая страница объявляется свободной. Виртуальный адрес при страничном распределении может быть представлен в виде пары (p, s), где p — номер виртуальной страницы процесса (нумерация страниц начинается с 0), а s — смещение в пределах виртуальной страницы. Учитывая, что размер страницы равен 2 в степени к, смещение s может быть получено простым отделением k младших разрядов в двоичной записи виртуального адреса. Оставшиеся старшие разряды представляют собой двоичную запись номера страницы p. При каждом обращении к оперативной памяти аппаратными средствами выполняются следующие действия: на основании начального адреса таблицы страниц (содержимое регистра адреса таблицы страниц), номера виртуальной страницы (старшие разряды виртуального адреса) и длины записи в таблице страниц (системная константа) определяется адрес нужной записи в таблице, из этой записи извлекается номер физической страницы, к номеру физической страницы присоединяется смещение (младшие разряды виртуального адреса). Использование того факта, что размер страницы равен степени 2, позволяет применить операцию конкатенации (присоединения) вместо более длительной операции сложения, что уменьшает время получения физического адреса, а значит повышает производительность компьютера. На производительность системы со страничной организацией памяти влияют временные затраты, связанные с обработкой страничных прерываний и преобразованием виртуального адреса в физический. При часто возникающих страничных прерываниях система может тратить большую часть времени впустую, на свопинг страниц. Чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. Кроме того, увеличение размера страницы уменьшает размер таблицы страниц, а значит уменьшает затраты памяти. С другой стороны, если страница велика, значит велика и фиктивная область в последней виртуальной странице каждой программы. В среднем на каждой программе теряется половина объема страницы, что в сумме при большой странице может составить существенную величину. Время преобразования виртуального адреса в физический в значительной степени определяется временем доступа к таблице страниц. В связи с этим таблицу страниц стремятся размещать в «быстрых» запоминающих устройствах. Это может быть, например, набор специальных регистров или память, использующая для уменьшения времени доступа ассоциативный поиск и кэширование данных. Страничное распределение памяти может быть реализовано в упрощенном варианте, без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оперативной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю виртуальной памяти, но почти исключает фрагментацию за счет того, что программа может загружаться в несмежные области, а также того, что при загрузке виртуальных страниц никогда не образуется остатков.

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

Виртуальное адресное пространство процесса делится на сегменты, размер которых определяется программистом с учетом смыслового значения содержащейся в них информации. Отдельный сегмент может представлять собой подпрограмму, массив данных и т. п. Иногда сегментация программы выполняется по умолчанию компилятором. При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов операционная система подыскивает подходящий участок свободной памяти), а часть сегментов размещается в дисковой памяти. Сегменты одной программы могут занимать в оперативной памяти несмежные участки. Во время загрузки система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация. Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единственном экземпляре. Распределение памяти сегментами Система с сегментной организацией функционирует аналогично системе со страничной организацией: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту. Виртуальный адрес при сегментной организации памяти может быть представлен парой (g, s), где g — номер сегмента, а s — смещение в сегменте. Физический адрес получается путем сложения начального физического адреса сегмента, найденного в таблице сегментов по номеру g, и смещения s. Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса. Странично-сегментное распределение Как видно из названия, данный метод представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов. Виртуальное пространство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страницы, которые нумеруются в пределах сегмента. Оперативная память делится на физические страницы. Загрузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура которой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов, в которой указываются адреса таблиц страниц для всех сегментов данного процесса. Адрес таблицы сегментов загружается в специальный регистр процессора, когда активизируется соответствующий процесс.

Вопрос 3

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.

Концепция семафоров.

Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen — проверять) и V (от verhogen — увеличивать). Классическое определение этих операций выглядит следующим образом:

P (S): пока S = 0 процесс блокируется;

S := S — 1;

V (S): S := S + 1;

Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1. В момент создания семафор может быть инициализирован любым неотрицательным значением.

Подобные переменные-семафоры могут с успехом применяться для решения различных задач организации взаимодействия процессов. В ряде языков программирования они были непосредственно введены в синтаксис языка (например, в ALGOL-68), в других случаях реализуются с помощью специальных системных вызовов. Соответствующая целая переменная располагается внутри адресного пространства ядра операционной системы. Операционная система обеспечивает атомарность операций P и V, используя, например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным, например, FIFO.

Решение проблемы producer-consumer с помощью семафоров.

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

Producer: while true do begin.

produce_item;

put_item;

end;

Consumer: while true do begin.

get_item;

consume_item;

end;

Если буфер заполнен, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то потребитель должен дожидаться нового сообщения. Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора: empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация. Семафор empty будем использовать для организации ожидания производителя при заполненном буфере, а семафор mutex — для организации взаимоисключения на критических участках, которыми являются действия put_item и get_item (операции «положить информацию» и «взять информацию» не могут пересекаться, так как в этом случае возникнет опасность искажения информации). Тогда решение задачи на выглядит так:

Semaphore mutex := 1;

Semaphore empty := N; (* где N — емкость буфера*).

Semaphore full := 0;

Producer:

while true do begin.

produce_item;

P (empty);

P (mutex);

put_item;

V (mutex);

V (full);

end;

Consumer:

while true do begin.

P (full);

P (mutex);

get_item;

V (mutex);

V (empty);

consume_item;

end;

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

Программная реализация для двух потоков. Поток-производитель заполняет LIFO-буфер простыми числами, а поток-потребитель выводит их на экран. Написано на Borland Pascal 7.

program semaphores;

uses.

Crt;

const.

Nmax = 10;

type.

Semaphore = Integer;

T = Longint;

var.

Empty, Full, Mutex: Semaphore;

Buffer: Array[0.Nmax] of T;

Top: Integer;

CurPrimeNumber: Longint;

F: Boolean;

procedure P (var S: Semaphore);

begin.

if S = 0 then.

begin.

F := True;

Exit;

end;

Dec (S);

end;

procedure V (var S: Semaphore);

begin.

Inc (S);

end;

function PrimeNumber (const x: Longint): Boolean;

var.

i: Integer;

begin.

PrimeNumber := False;

if x < 2 then Exit;

for i := 2 to Trunc (Sqrt (x)) do.

if x mod i = 0 then Exit;

PrimeNumber := True;

end;

function Produce_Item: T;

begin.

repeat.

Inc (CurPrimeNumber);

until PrimeNumber (CurPrimeNumber) or (CurPrimeNumber = High (CurPrimeNumber));

if not PrimeNumber (CurPrimeNumber) then Halt;

Produce_Item := CurPrimeNumber;

end;

procedure Consume_Item (const Item: T);

begin.

Write (Item, ' '); {Delay (7000);}.

end;

procedure Put_Item (const Item: T);

begin.

Inc (Top);

Buffer[Top] := Item;

end;

function Get_Item: T;

begin.

Dec (Top);

Get_Item := Buffer[Top + 1];

end;

procedure Producer;

var.

Item: T;

begin.

F := False;

while True do.

begin.

P (Empty); if F then Break;

P (Mutex); if F then Break;

Item := Produce_Item;

Put_Item (Item);

V (Mutex);

V (Full);

end;

end;

procedure Consumer;

var.

Item: T;

begin.

F := False;

while True do.

begin.

P (Full); if F then Break;

P (Mutex); if F then Break;

Item := Get_Item;

V (Mutex);

V (Empty);

Consume_Item (Item);

end;

end;

begin.

ClrScr;

CurPrimeNumber := 1;

Mutex := 1;

Empty := Nmax;

Full := 0;

Top := 0;

repeat.

Producer;

Consumer;

until KeyPressed;

ReadLn;

end.