Курс читал: доцент И.В.Машечкин, сентябрь-декабрь 1997г. ВМиК МГУ, 2 курс

Работая на машине, мы реально не работаем с микросхемами и “железом”, наша работа происходит с программным обеспечением (ПО), которое размещено на аппаратуре. Поэтому вводится понятие Вычислительной системы.

Структуру вычислительной системы можно представить в виде пирамиды:

Аппаратные средства.

Ресурсы ВС разделяются на два типа:

1. не участвующие в управлении программой (объем винчестера и т.д.).
2. участвующие в управлении программой (размер ячейки памяти, объем оперативной памяти, скорость выполнения команд).

Ресурсы второго типа называются физическими ресурсами аппаратуры.

Управление физическими устройствами.

Управление физическими устройствами осуществляют программы, ориентированные на аппаратуру, взаимодействующие с аппаратными структурами, знающие "язык" аппаратуры.

Управление логическими устройствами.

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

Системы программирования.

Прикладное программное обеспечение.

Прикладное программное обеспечение необходимо для решения задач из конкретных областей.

Основной функцией центрального процессора (ЦП) является обработка информации и взаимодействие с устройствами. Обмениваться данными ЦП может только с ОЗУ (Оперативно Запоминающее Устройство).

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

ЦП выбирает из ОЗУ последовательность команд для выполнения. ЦП состоит из двух компонентов:

1. Устройство Управления (УУ) принимает очередное слово из ОЗУ и разбирается — команда это или данные. Если это команда — то УУ выполняет ее, иначе передает АУ.
2. Арифметическое Устройство (АУ) занимается исключительно вычислениями.

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

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

Мы определили, что нижний уровень — это чисто аппаратура, это то, что делается из металла, пластика и прочих материалов, используемых для производства “железа”, или hardware, компьютера.

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

Следующий уровень — уровень, ориентированный на сглаживание аппаратных особенностей. Он целиком и полностью предназначен для создания более комфортных условий в работе пользователя. Если, предположим, мы работаем с устройством внешней памяти “жесткий магнитный диск”, то параметры, которые характерны для конкретного диска, могут быть, например, такими: сколько считывающих и записывающих головок имеет это устройство, сколько поверхностей, на которых находится хранящий информацию слой. И, соответственно, набор команд управления этого устройства ориентирован на эти параметры. И конечно, вам, как программистам, не интересно работать в терминах “считать бит со второй поверхности десятого цилиндра такой-то дорожки”. Это тяжело и неэффективно. Уровень логических ресурсов создает некоторое обобщенное устройство, одно на всю систему, и пользователь работает в терминах этого обобщенного устройства. А уже программы логического уровня разбираются, к какой из программ управления физическими устройствами надо обратиться, чтобы запрос пользователя к логическому устройству правильно оттранслировать к конкретному физическому устройству.

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

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

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

Регистры.

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

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

Система прерываний.

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

В момент возникновения прерывания действия в аппаратуре ВС следующие:

1. В некоторые специальные регистры аппаратно заносится (сохраняется) информация о выполняемой в данный момент программе. Это минимальные действия, необходимые для начала обработки прерывания. Обычно, в этот набор данных входит счетчик команд, регистр результата, указатель стека и несколько регистров общего назначения. (Эти действия называются малым упрятыванием).
2. В некоторый специальный управляющий регистр, условно будем называть его регистром прерываний, помещается код возникшего прерывания.
3. Запускается программа обработки прерываний операционной системы.

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

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

Регистры буферной памяти (Cache, КЭШ).

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

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

Алгоритм чтения из оперативной памяти следующий:

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

Этот буфер чтения/записи служит достаточно мощным средством для минимизации обращений к ОЗУ. Наибольший эффект достигается при небольших циклах, когда все операнды размещаются в буфере, и после этого циклический процесс работает без обращений к ОЗУ. Иногда эти буфера называют КЭШ-буферами, а также ассоциативной памятью, потому что доступ к этой памяти осуществляется не по адресу (как в ОЗУ), а по значению поля. Реально, все механизмы могут быть устроены иначе, чем мы здесь изучаем, т.к. мы изучаем некоторую обобщенную систему.

Оперативная память

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

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

Виртуальная память, мультипрограммный режим

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

Оперативная память:

Предположим: в начальный момент времени какую-то часть оперативной памяти заняла операционная система (так оно и происходит). После этого была загружена программа №1 , затем программы №2, №3 (и т.д.). Операционная система начала выполнять эти программы в мультипрограммном режиме. Возникает вопрос: всегда ли любую программу можно поместить в произвольный диапазон адресного пространства оперативной памяти? Обладает ли программа свойством перемещения по памяти? Насколько задача связана с адресным пространством, на которое ее запрограммировали? Это первая проблема. Вторая проблема: этот процесс идет, и понятно, что в какие-то моменты времени какие-то из этих задач заканчиваются (например Задача №2). При этом в памяти образуются свободные фрагменты.

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

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

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

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

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

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

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

Исполнительный адрес

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

Таблица приписки

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

Для каждой программы нужна своя таблица приписки. При переходе от одной программы к другой содержимое ТП сохраняется операционной системой в некоторой своей программной таблице (массиве) и затем изменяются значения в ТП.

Внешние устройства

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

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

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

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

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

И так далее.

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

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

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

Есть еще один экзотический вид памяти — память на магнитных доменах.

Суть этой памяти в следующем:

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

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

Итак, мы рассмотрели ВЗУ с точки зрения их эффективности. Давайте посмотрим на них с точки зрения методов доступа.

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

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

Это два взгляда на ВЗУ. Давайте посмотрим на ВЗУ с точки зрения управления.

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

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

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

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

Соответственно, современные ЭВМ могут иметь множество таких каналов, которые помогают организовывать управление и забирают лишние функции у ЦП.

Это, наверное, все, что можно или нужно было рассказать о работе с внешними устройствами.

Все то, что было сказано — есть лишь небольшие ключики, которые позволяют:

а) как-то классифицировать ВУ и понять, что хорошо, что плохо;

б) постараться сформировать взгляд на все это, как на систему.

Мультипрограммный режим

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

Начертим следующую диаграмму:

Она показывает работу ЦП во времени.

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

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

Сначала программа была одна и “творила” все, что хотела — ошибка в программе приводила к ошибке в системе, но кроме самой программы по сути дела больше никто не страдал. А когда на машине появляется еще одна программа, то начинают возникать проблемы:

Кто-то взял и записал в пространство работающей программы свою информацию или

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

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

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

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

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

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

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

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

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

С одной стороны подкачка поддерживается аппаратурой (подсчет “активности” страниц памяти сложно организовать программно), с другой стороны — все реальное управление программно.

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

Теперь, если мы вернемся к нашей пирамиде

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

Это относится почти ко всему, за исключением, наверное, буферизации памяти между ОЗУ и ЦП — это практически полностью аппаратное средство.

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

Вторая же проблема, которую мы всегда видели — это буферизация и сглаживание различных скоростей работы различных компонент. Мы говорили о сглаживании ОЗУ-ЦП и ВЗУ-ОЗУ.

Это, пожалуй, все, что относится к первой теме.

Мы начинаем блок тем, называемых “Операционная система.”

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

Все это мы будем называть ресурсами вычислительной системы.

Любая ОС оперирует некоторыми сущностями, которые во многом характеризуют свойства ОС. К таким сущностям могут относиться понятия файла, процесса, объекта и т.д. Конкретно, каждая ОС имеет свой набор этих сущностей, к примеру, если мы возьмем ОС WinNT, то к таким сущностям можно отнести понятие объекта ОС, и уже через это понятие, через управление этими ресурсами, предоставляются все возможные сервисные функции ОС. Если мы посмотрим на ОС Unix, то там такой сущностью является в первую очередь понятие файла, во вторую очередь — понятие процесса. И, возвращаясь, к последнему, процесс — это некоторая сущность (мы не говорим “объект” дабы не было путаницы с ООП), которая присутствует практически во всех ОС. Давайте попробуем определить понятие процесса, как одного из фундаментальных.

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

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

Давайте посмотрим, что понимается под “управлением процессами”. Это достаточно просто:

1. Управление использованием времени ЦП. Планирование ЦП.

В какой момент времени, какая из задач будет использовать время ЦП.

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

3. Управление разделяемыми ресурсами.

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

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

Давайте теперь перейдем к более подробному рассмотрению основных функций ОС.

1. Управление использованием времени ЦП.

На самом деле от того, какой алгоритм выбора очередной задачи, для передачи ей активности ЦП, определен, зависят многие реальные эксплуатационные свойства ОС. А выбор алгоритма почти целиком и полностью определяется теми критериями эффективности, которые используются для оценки эффективности работы ОС. И поэтому управление ЦП мы рассмотрим на фоне типов ОС.

Первая ситуация: у нас есть большое число задач, требующих большого объема вычислительных мощностей системы. И эти задачи должны выполняться в одной вычислительной системе. Что будет являться критерием эффективности при работе системы для выполнения данных задач. Какой набор параметров можно взять и сказать, что если они маленькие — то хорошо, или если они большие, то хорошо или наоборот. Для такой ситуации критерием эффективности является степень загрузки ЦП. Если ЦП простаивает мало (либо ОС сама загружает процессор), то есть если потерянное время маленькое, то такая система работает хорошо и эффективно. Как добиться такой работы? С помощью хорошего алгоритма планирования. Мы запускаем для обработки тот набор задач, который у нас есть. То есть в системе работает режим мультипрограммирования. Алгоритм передачи ЦП от одного процесса к другому будет следующий — если ЦП выделен одному из процессов, то он будет владеть ЦП до одного из следующих моментов:

1. обращение к внешнему устройству
2. завершение процесса
3. зафиксированный факт зацикливания процесса

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

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

Первое подмножество — это те процессы, которые еще не готовы к продолжению выполнения (ожидающие обмена, подкачки и т.п.).

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

1. запрос на обмен
2. завершение процесса
3. исчерпание выделенного процессу кванта времени

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

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

ОС с перечисленными выше свойствами называются ОС разделения времени.

У пользователя такой ОС должна создаться иллюзия, что все ресурсы системы предоставлены только ему.

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

Реально для ОС этого класса используются достаточно простые алгоритмы планирования.

Подводя некоторую черту под этой первой функцией управления временем ЦП, следует обратить внимание на два факта:

• те алгоритмы, которые организованы в системе планирования времени ЦП, во многом определяют эксплуатационные свойства вычислительной системы.
• мы с вами рассмотрели три типовых системы (пакетные, разделения времени, реального времени). На сегодняшний день можно говорить о том, что система реального времени — это отдельный класс ОС. Например, Win95, семейство Unix и многие другие не являются системами реального времени. Система реального времени — отдельная ОС. Первые две ОС можно с эмулировать. Часто же общеупотребимые ОС являются смежными, то есть в них есть как пакетные средства, так и средства разделения времени. Примером такой схемы организации планирования может быть следующее — планировщик является двухуровневым (в системе могут быть счетные и интерактивные задачи), он определяет сначала — какому классу задач отдать приоритет, а на втором уровне он в пределах одного класса выбирает задачу на выполнение. Если в данный момент нет ни одной готовой к выполнению интерактивной задачи, то ЦП передается счетным задачам, но с условием — как только появляется хотя бы одна интерактивная задача — счетная задача прерывается и управление передается интерактивной задаче.

Это все, что касается первой функции.

2. Управление подкачкой и буфером ввода.

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

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

3. Управление разделяемыми ресурсами.

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

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

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

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

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

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

Мы рассмотрели, что есть пакетная ОС и какие алгоритмы отдачи времени ЦП приемлемы для пакетной ОС, было сказано про ОС разделения времени.

В подавляющем большинстве случаем мы работаем в режиме разделения времени.

Предварительно мы говорили, что любая ОС реализует в себе буферизацию ввода/вывода. Буферизация в ОС — есть одна из основных функций. И по аналогии борьбы с разными скоростями доступа к различным компонентам вычислительной системы, ОС вводит в своих пределах программную буферизацию запросов на ввод/вывод, которая также решает проблемы сглаживания времени доступа, а также проблемы синхронизации в целом. Синхронизацию в целом можно пояснить примером с разделением устройства печати. А сглаживание доступа заключается в том, что практически каждая современная ОС имеет кэш-буфера, которые аккумулируют обращения к ВЗУ. То есть суть такова, что также как и при работе ОЗУ, реальные обмены могут не происходить, этот механизм организован похоже, за тем исключением, что реализован он программно, в отличие от аппаратной реализации буферизации ОЗУ. Это позволяет существенно оптимизировать ОС. Признаком наличия такой буферизации является требование прекратить выполнение ОС перед завершением работы вычислительной системы (например, MS DOS такого требования не предъявляет — компьютер под его управлением можно включать и выключать в любое время без потерь, а в таких системах, как Unix, Win95 и других, подобное выключение машины может привести к потере информации, так как в момент выключения часть данных может находиться еще в буфере.) Степень этой буферизации определяет реальную эффективность системы.

Приведем пример. Если поменять процессор 486 на Pentium в системе, где работает Win95, то быстродействие системы увеличится ненамного. Это означает, что быстродействие системы упирается в работу с внешними устройствами, механизм буферизации неэффективен — реальных обменов с внешними устройствами остается также много. В то время как ОС Unix, при такой же замене ЦП, дает качественный скачок вперед по быстродействию, так как в этой ОС, буферизация организована значительно лучше.

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

Свойства файлов

Практически каждая ОС обеспечивает набор функций ввода/вывода для работы с файлами.

Указатель: Файл:

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

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

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

Структура файловой системы

Давайте рассмотрим некоторое пространство ВЗУ и рассмотрим, как мы можем организовать файлов в пределах этого пространств.

Ее суть такова — в пределах пространства ВЗУ выделяется некоторая область для хранения данных, которая называется “Каталог”. Каталог имеет следующую структуру

Соответственно, функция открытия файла сводится к тому, чтобы в этой таблице “Каталог” найти по имени нужный файл и определить начало его размещения и конец размещения. Действие очень простое, так как дополнительных обменов не требуется — весь каталог можно хранить в памяти ОС. Если создается новый файл, то он записывается на свободное место. Альтернативно каталогу имен существует таблица свободных фрагментов пространства ВЗУ.

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

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

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

Итак, организация простая, при обменах — эффективная, но в случае нехватки пространства для файлов начинается неэффективность и при долговременной работе случается фрагментация (когда имеются свободные фрагменты, которые объемом позволяют разместить файл, а расположением — нет). Это та же самая проблема, которая имела место в ОЗУ. Решить данную проблему можно путем компрессии — долгого и опасного для данных процесса, который передвигает блоки по ВЗУ с целью разместить их оптимальным образом. Можно сделать эту компрессию так, чтобы в конец каждого файла был добавлен кусок свободного места (например, по 10% от текущей длины).

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

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

Name {Блок1, Блок2, ..., БлокM}

причем эти блоки имеют произвольный порядок на ВЗУ:

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

В последнем случае с каждым файлом у нас связано несколько атрибутов:

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

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

Каталог содержит строки, каждая iая строка соответствует iому блоку файловой системы, в этой строке содержится информация о занятости блока. Если он занят, то в этой строке указывается имя файла (или ссылка на него) и имя пользователя, может быть и какая-то дополнительная информация.

При открытии файла система может, например, пробегать по ВЗУ и строить таблицу соответствия между логическими блоками файла и физическими (блоками носителя).

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

Первой такая организация появилась в ОС Multics, которая разрабатывалась в университете Беркли в конце 60х годов. Это было давно, но такое хорошее и красивое решение с тех пор стало появляться во многих ОС.

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

Защита данных в ОС

В иерархической организации пользователей есть понятие группы. А в группе есть реальные пользователи.

При регистрации конкретного пользователя его следует отнести к какой-либо группе.

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

И такое деление на группы может быть также многоуровневым с соответствующим распределением прав и возможностей.

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

Вот, наверное, и все, что следовало бы сказать о свойствах и функциях ОС. Естественно, мы рассмотрели далеко не все функции ОС. Что-то было специально упущено, так как мы рассматриваем ОС в упрощенной модели. Ибо наша цель — не изучение конкретной ОС, а научиться классифицировать ОС, с каких точек зрения следует на нее смотреть и сравнивать различные типы ОС.

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

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

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

Если мы посмотрим на нормальную программу на ассемблере, то заметим следующее — при программировании каких-то блоков мы часто используем побочный эффект (например, во время вычисления выражения мы можем получать и куда-то откладывать промежуточные результаты), также можно поступать и в языке “С”. Таким образом, понятие выражения в “С” было гораздо шире, чем в других языках того времени. И в выражениях, кроме новых операций, таких как работа с указателем, смещения сдвиги и т.п., появилась принципиально новая операция — операция присваивания. Почему она новая? Потому что во многих языках до “С”, а также и после него не было операции присваивания — был оператор присваивания. Разница в одном — если мы имеем оператор присваивания, во-первых, требуется, чтобы в правой части такой операции уже не было (мы не можем использовать побочный эффект), и второе — левая часть оператора присваивания — это некоторая ссылка на единичную область памяти. Внесение оператора присваивания внутрь выражения позволило решать проблему побочных эффектов (значения подвыражений, которые могут быть использованы во вне — а они в свою очередь сокращают число обменов с ОЗУ), а это средство эффективности.

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

И свойствам таких языков относится следующее:

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

Давайте начнем рассмотрение конкретных свойств ОС Unix. Первое, что мы будем рассматривать, это файловая система, организация работы с файлами.

Файловая система Unix, это иерархическая, многопользовательская файловая система. Ее можно представить в виде дерева:

Замечание. На самом деле файловая система Unix не является древообразной. Все то, что говорилось выше — правильно, но в системе имеется возможность нарушения красивой и удобной иерархии в виде дерева, так как имеется возможность ассоциировать несколько имен с одним и тем же содержимым файла. И могут возникать такие ситуации, когда, например, “/D4/N3” и “/D0/D1/N1” являются, по сути дела, одним файлом с двумя именами.

Еще одно замечание. В ОС Unix используется трехуровневая иерархия пользователей:

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

Это некоторые предварительные данные по файловой системе. Теперь давайте рассмотрим структуру файловой системы на диске.

Сначала определим некоторые понятия:

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

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

В любой системе принято разбиение пространства ВЗУ на некоторые области данных, которые называются блоками. Размер блока (логического блока в ОС) является фиксированным атрибутом. В ОС Unix в различных ее вариациях размер блока был параметром меняющимся в зависимости от варианта ОС. Для простоты и единообразия мы будем считать, что логический блок ВЗУ равен 512 байт.

Итак, рассмотрим структуру файловой системы. Представим адресное пространство системного ВЗУ в виде последовательности блоков.

Будем считать, что этих блоков N+M-1.

Первый блок — это блок начальной загрузки. Размещение этого блока в нулевом блоке системного устройства определяется аппаратурой, так как аппаратной загрузчик всегда обращается к конкретному блоку системного устройства (к нулевому блоку). Это последний компонент файловой системы, который зависит от аппаратуры.

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

• количестве индексных дескрипторов (ИД) в файловой системе;
• размере файловой системы;
• свободных блоках файлов;
• свободных ИД;
• еще ряд данных, которые мы не будем перечислять в силу уникальности их назначения.

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

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

Это концептуальная схема структуры файловой системы. Теперь давайте вернемся и рассмотрим некоторые ее части более детально.

Прежде всего интерес вызывают области свободных блоков файлов и свободных ИД. В Unix видно влияние двух факторов: первый — это то, что файловая система разрабатывалась тогда, когда ВЗУ объемом 5-10Мб считалось очень большим и в реализации алгоритмов по работе с системой видны старания автором по оптимизации этого процесса; и второй — это свойства файловой системы по оптимизации доступа, критерием которого является количество обменов, которые файловая система производит для своих нужд, не связанных с чтением или записью информации файлов.

Суперблок содержит список свободных блоков файлов, он состоит из 50 элементов. Суть работы с этим списком заключается в следующем — в буфере, состоящем из 50 элементов (при условии того, что блок — 512 байт, 1 блок — 16 битное слово), в них записаны номера свободных блоков пространства блоков файлов с 2 до 49. В 0 элементе содержится указатель на продолжение массива, а в последнем элементе содержится указатель на свободный элемент в массиве.

Если какому-то процессу для расширения файла требуется свободный блок, то система по указателю N/B (номер блока) выбирает элемент массива, и этот блок предоставляется файлу. Если происходит сокращение файла, то высвободившиеся номера добавляются в массив свободных блоков и корректируется указатель N/B.

Так как размер массива — 50 элементов, то возможны две критические ситуации:

1. Когда мы освобождаем блоки файлов, а они не могут поместиться в этом массиве. В этом случае из файловой системы выбирается один свободный блок и заполненный полностью массив свободных блоков копируется в этот блок, после этого значение указателя N/B обнуляется, а в нулевой элемент массива, который находится в суперблоке, записывается номер блока, который мы выбрали для копирования содержимого массива. Таким образом, если мы постоянно освобождаем блоки, то образуется список, в котором будут размещены все свободные блоки файловой системы.
2. Когда мы выбрали все свободные блоки и содержимое элементов массива свободных блоков исчерпалось. Если нулевой элемент массива равен нулю, то это означает, что исчерпано все пространство файловой системы. Если этот элемент нулю не равен, то это означает, что существует продолжение массива. Это продолжение считывается в копию суперблока в оперативной памяти.

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

Список свободных ИД. Это буфер, состоящий из 100 элементов. В нем находится информация о 100 номерах ИД, которые свободны в данный момент. Соответственно, когда нужен новый ИД, то его номер берется из списка свободных ИД, если номер освобождается, то заносится в этот массив. Если же массив переполнен, а освобождается 101 элемент, то это никуда не записывается. Если список ИД переполняется, то система “пробегает” по списку и формирует содержимое этого буфера заново.

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

1. Больше нет свободных блоков для файлов;
2. Нет больше новых ИД.

Вот информация о суперблоке. Какие можно сделать выводы и замечания?

• суперблок всегда находится в ОЗУ;
• все операции по освобождению блоков, занятию блоков файлов, по занятию и освобождению ИД происходят в ОЗУ (минимизация обменов с диском). Если же содержимое суперблока не записать на диск и выключить питание, то возникнут проблемы (несоответствие реального состояния файловой системы и содержимого суперблока). Но это уже требование к надежности аппаратуры системы.

Индексные Дескрипторы

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

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

Как видно — в ИД нет имени файла. Давайте посмотрим, как организована адресация блоков, в которых размещается файл.

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

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

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

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

Элементы файловой системы:

Каталоги

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

Мы говорим, что в каталоге “А” содержатся файлы: “B”, “C” и “D” — из которых “В” и “С” могут быть как файлами, так и каталогами, а “D” — заведомо каталог.

Каталог имеет следующую структуру. Он состоит из элементов, объединяющих в себе два поля — номер ИД и имя файла:

Каталог = { {ИД, Имя}, {ИД,Имя}, ..., {ИД, Имя}}

Что есть номер ИД? — это порядковый номер элемента в списке индексных дескрипторов. Так, первый элемент этого списка — ИД#1 принадлежит корневому каталогу “.”.

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

{ИД_самого_каталога, “.”} и {ИД_родительского_каталога, “..”}

Так на картинке файл “А” имеет ИД#7, “D” — ИД#5, “F” — ИД#10, “G” — ИД#101. В этом случае файл-каталог D будет иметь следующее содержимое:

{{ 5, “.” },

{ 7, “..”},

{10, “F”},

{101,”G”}}

(Для корневого каталога родитель ссылается на него же самого.)

Чем отличается файл-каталог от обычного файла? Он отличается полем типа в индексном дескрипторе.

Для того, чтобы в этом случае открыть файл “B”, придется выполнить ряд косвенных операций — взять ИД родитель, и по нему выбирается содержимое файла-каталога “А”, в “А” мы выбираем строку с именем “B” и определяем его ИД. Эта процедура достаточно трудоемка, но так как открытие и закрытие файлов происходит достаточно редко, то “криминала” в этом никакого нету.

За счет такой организации каталогов у нас содержимое файла разорвано с его именем. Имя может быть определено неоднозначно.

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

Файлы устройств

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

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

Обмен данными с файлами

Количество одновременно открытых файлов (точнее, максимальное количество ФД, ассоциированных с файлами) для процесса регламентируется системой.

При организации обмена система подразделяет все данные на две категории — первая, это данные, ассоциированные с процессом пользователя, и данные, ассоциированные с ОС.

Следующее. Таблица файлов — эта таблица содержит информацию об имени открытого файла и имеет ссылку на ИД данного файла в ТИДОФ.

Подробнее эта схема будет рассмотрена на следующей лекции.

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

Для поддержания ввода-вывода в системе все данные в системе подразделяются на два типа: общесистемные данные (ТИДОФ, например). Размер ТИДОФ фиксирован — это еще один параметр настройки системы. Каждая запись этой таблицы содержит некоторую информацию, из которой нас будет интересовать следующее:

1. Копия ИД открытого файла. То есть для любого открытого файла ИД, который характеризует содержимое этого файла, копируется и размещается в ТИДОФ. После этого все манипуляции с файлами происходят через копию ИД. Не с ИД, который на диске, а с его копией. Таким образом доступ к информации осуществляется оперативно.
2. Счетчик открытых в данный момент файлов, связанных в данный момент с данным ИД. Это означает, что на любое количество открытий файла, связанного с данным ИД, система работает с одной копией этого ИД.

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

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

Для того, чтобы мы имели возможность рассмотреть все грани данного вопроса — забежим немного вперед и рассмотрим некоторые вещи, связанные с формированием процесса.

ОС Unix имеет функцию, которая называется fork(...) — это системный вызов, при обращении к которому происходит некоторое “бесполезное” действие — создается процесс двойник — полная (с некоторыми замечаниями) копия процесса, в котором встретилась эта функция. Для чего это нужно? Нужно, для чего — увидим позже.

При формировании процесса двойника есть две особенности:

• процесс-сын имеет все те же файлы открытыми, что были открыты в процессе отца;
• система позволяет идентифицировать — где сын, где отец;

Соответственно, когда мы изменяем указатель файла i (читаем или пишем), то файловый указатель j изменяться не будет. Обе записи в ТФ ссылаются на один и тот же ИД файла.

Теперь предположим, что процесс #1 выполнил обращение к функции fork(...). Образовалась копия этого процесса, причем обе копии начинают работать на выходе из процесса. И, соответственно, со вторым процессом будет ассоциирована ТОФ2.

Файлы “name” с дескрипторами i,j будут также открыты во втором процессе. Но, когда процесс получает открытые файлы в наследство от родителя, то ссылки из соответствующих строк таблицы ТОФ будут происходить не на новые строки ТФ, а на те же самые, на которые ссылались ФД родителя. Это означает, что у обоих процессов будут одинаковые указатели файлов — при перемещении указателя для ФД i в процессе-отце будет также изменен файловый указатель для ФД i в сыне и наоборот. Вообще говоря, два процесса по ФД i (или любому переданному в наследство открытому файлу) будут иметь общий указатель файла.

Вот это случай, когда нет взаимооднозначного соответствия между строками ТФ и ТОФ. И во время создания процесса сына счетчик наследственности увеличивается на единицу.

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

При любом формировании нового процесса, система автоматически связывает 0, 1 и 2 ФД с предопределенными файлами:

0 — системный файл ввода (обычно — файл устройства клавиатура);

1 — системный файл вывода (обычно — файл устройства монитор);

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

Рассмотрим типовые действия при обращении к тем или иными системным вызовам.

При обращении к функции fork(...) система создает копию процесса и дублирует ТОФ родителя в ТОФ сыновнего процесса, а также увеличивает на единицу индексы наследственности в соответствующих строках ТФ, и увеличивает счетчик связей в ТИДОФ.

При выполнении системного вызова open(...):

1. По полному имени определяется каталог, в котором размещается файл;
2. Определяется номер ИД файла;
3. По номеру ИД осуществляется поиск в ТИДОФ, если запись с данным номером обнаружена, то номер соответствующей строки ТИДОФ фиксируется и переходим к шагу 5;
4. Если такой записи не обнаружено, происходит формирование новой строки в ТИДОФ, соответствующей новому ИД и фиксируется ее номер;
5. Корректируется счетчик ссылок (количество открытых файлов, использующих данный ИД) в ТИДОФ. Номер строки ТИДОФ записывается в строку ТФ, а ее номер возвращается в ТОФ;

При операциях ввода-вывода мы идем по ссылкам и добираемся до нужного блока данных.

Взаимодействие с устройствами.

Мы говорили, что все устройства, которые обслуживает ОС Unix, могут быть подразделены на два типа: байт- и блок-ориентированные. С первыми устройствами все обмены осуществляются порциями по одному байту, с остальными — некоторыми порциями байт. С точки зрения ОС одно и то же устройство может рассматриваться как байт- и как блок-ориентированное. Примером такого устройства может быть оперативная память.

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

Основной особенностью организации работы с блок-ориентированными устройствами является возможность буферизации обмена. В оперативной памяти организован пул буферов.

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

Пусть поступил заказ на чтение Nного блока из устройства с номером M. Тогда:

1. Среди буферов пула ищется содержащий Nный блок Mмого устройства. Если он найден, то фиксируется номер этого буфера (следует отметить, что в этом случае реального обращения к устройству нет, а чтением информации является предоставление информации из найденного буфера) и переходим на четвертый шаг;
2. Если поиск оказался неудачным, то в пуле осуществляется поиск буфера для чтения и размещения содержимого данного блока. Если есть свободный буфер (реально такая ситуация может быть только при старте системы), то фиксируем его номер и переходим к пункту 3. Если же свободного буфера нет, то выбирается буфер, обращений к которому не было самое длительное время. Если для него имеется установленный признак записи информации в буфер (при последнем обращении была произведена запись) — происходит запись информации из буфера на физическое устройство (если признака записи не было, то просто игнорируем содержимое), и, фиксируя номер, переходим к шагу 3.
3. Осуществляется чтение Nного блока устройства M в найденный буфер.
4. Происходит обнуление счетчика времени для данного буфера, а счетчики времени всех остальных буферов пула увеличиваем на единицу.
5. Передаем в качестве результата содержимое буфера.

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

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

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

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

Но на самом деле с развитием ОС и аппаратуры фатальные потери информации встречаются редко.

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

Рассмотрим стандартную библиотеку stdio.h. Концептуальная суть обменов через нее такая же, как и через системные вызовы. Но если open возвращает номер ФД, то fopen возвращает указатель на некоторую структуру — это первое. Второе и основное — многие функции сервиса, которые предоставляет библиотека реализуются внутри адресного пространства процесса, в частности такой функцией сервиса является еще один уровень буферизации ввода-вывода. Суть его в том, что на ресурсах процесса можно выделить буфер, который будет работать аналогично буферному пулу ОС и будет минимизировать обращение процесса к системным вызовам ввода-вывода.

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

Говоря о двойной буферизации, следует сказать и о многоуровневой буферизации — когда ВЗУ само обладает некоторой оперативной памятью с помощью которой обеспечивает еще один уровень буферов.

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

Следует отметить, что Unix максимально экономит число обращений к внешним устройствам:

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

Продолжим рассматривать файловую систему Unix

Атрибуты файлов

Мы говорили об организации пользователей системы, она имеет иерархическую трехуровневую структуру

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

• права на чтение/запись/исполнение (RWX) владельца файла;
• права группы (для всех пользователей, кроме владельца);
• права всех пользователей (за исключением группы владельца и самого владельца);

Изменение прав доступа можно осуществить с помощью команды “chmod”.

Кроме атрибутов доступа каждый файл может иметь некоторые признаки, так называемые:

• t-bit: так как открытие файла — действие долгое, то для оптимизации этой процедуры введен этот атрибут, которым помечаются исполняемые файлы. Тогда при первом вызове файла за сеанс работы системы происходит копирование тела файла в область сохранения. При каждом повторном вызове файла сначала происходит просмотр области сохранения, если файл там есть, то он забирается оттуда, а в области сохранения накладных расходов на открытие файлов нет. T-bit устанавливается системным администратором, обычно это делается для наиболее часто запускаемых процессов.
• s-bit: все средства системы кому-то принадлежат, так как представляются в виде файлов, поэтому у каждой самой простой команды имеется владелец файла. Соответственно, каждая из этих команд может обращаться за чтением или записью в системные файлы. И возникает проблема — с одной стороны должна быть защита от несанкционированного доступа к файлу, а с другой стороны какие-то файлы должны быть доступны всем командам. Такие файлы помечаются s-bit’ом, суть его в следующем: владелец файла с s-bit’ом остается неизменным, но при запуске владельцу запустившего процесса предоставляются права по доступу к данным, как у владельца файла с s-bit’ом. Поясним на примере:

Для установки s- и t-bit’а также существует определенная команда системы.

Итак, мы разобрались с доступом к конкретным файлам, а как же быть с каталогами? Как интерпретируются права доступа к каталогам?

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

Предположим, мы исполняем команду “ls */mash*”. Это означает, что мы ищем в текущем каталоге подкаталоги, внутри которых есть файлы, начинающиеся с “mash”. При этом выполняется поиск файлов. Это и есть тот поиск, который ассоциируется с выполнением файла-каталога.

Структура файловой системы с точки зрения пользователя

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

Файлы “\”:

“unix” — этот файл запускается программным загрузчиком и в итоге формирует ядро системы;

“passwd” — все пользователи зарегистрированы в этом файле, то есть каждому пользователю соответствует строка в этом файле, которая содержит набор некоторых данных, разделенных между собой некоторым разделителем. В частности, эта строка содержит номер группы пользователя, она может содержать закодированный пароль на вход пользователя. Однако, современные unix’ы хранят пароли обычно в специальной защищенной базе данных, так как находятся умельцы, которые с помощью переборных задач (алгоритм кодирования паролей известен) подбирают пароли. Далее, строка содержит ФИО пользователя, его статус, домашний каталог (каталог, который устанавливается при входе пользователя), тип интерпретатора команд, с которым будет работать пользователь.

“rc” — в этом файле в текстовом виде находится набор команд, которые будут выполнены при загрузке ОС.

И так далее...

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

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

Каталоги:

“etc” — содержит стандартные файлы данных системы и команды, обеспечивающие управление некоторым уровнем функционирования системы;

“bin” — здесь находится подавляющее число команд, доступных пользователю, таких как: “rm”,”ls”,...

“mnt” — каталог, к которому можно “примонтировать” локальные файловые системы. Мы говорили об организации файловой системы на одном внешнем устройстве, но реально для систем этого мало. Обычно требуется иметь основную файловую систему и любое число локальных, расположенных на других устройствах. Они монтируются с помощью команды “mount”. Это означает, что корень локальной файловой системы после монтирования ассоциируется с этим каталогом, и доступ к любому файлу из локальной файловой системы есть лишь указание пути от корня файловой системы до соответствующего узла через каталог “mnt”.

“dev” — в этом каталоге размещаются файлы, ассоциированные с конкретными драйверами внешних устройств. К примеру, “tty01”, “tty02”, “consolp”, ... Как было сказано ранее — эти файлы не имеют содержимого, но имеют специальные поля в ИД, определяющие ссылки на таблицу драйверов и некоторую другую информацию.

“usr”: “lib” — содержит библиотеки группового пользования, как то — компилятор Си, например.

“bin” — каталог для размещения команд. Есть некоторые негласные правила, которые определяют — стоит положить команду в “\bin” или в “\usr\bin”. Обычно в “\bin” кладут стандартные команды.

“include” — здесь лежат файлы заголовков, которые, например, используются компилятором Си, когда мы употребляем команду “include <stdio.h>” файл “stdio.h” ищется как раз в “\usr\include”. Также интерес представляет подкаталог “\usr\include\sys” — здесь лежат файлы-заголовки, которые несут в себе информацию о системных функциях.

На этом мы заканчиваем рассмотрение файловой системы Unix. Подведем итог —

Файловая система Unix:

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

Рассмотрим информативную нагрузку таблицы.

В строке (записи) таблицы находится ссылка на контекст процесса, там же находится ссылка на тело процесса.

Телом процесса мы будем называть набор команд и данных, которыми оперирует процесс.

Контекст содержит:

Если K пользователей вызывают один текстовой редактор, то в системе находится одна копия этого редактора и K копий сегмента данных и контекстов (копии, надо заметить, не идентичные). Это вещь полезная, так как отсюда сразу же можно увеличить “разум” планировщика откачки (он может, например, откачивать сегмент данных, а не сегмент текста).

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

Мы говорили, каким образом в Unix можно создать копию текущего процесса — это функция fork(), она работает следующим образом:

fork(): >0 PID сыновнего процесса (мы находимся в процессе-отце)

=-1 ошибка — невозможность создать новый процесс (остаемся в процессе-отце), эта ошибка может возникнуть при недостатке места в таблице процессов, при нехватке места в системных областях данных и т.п.

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

При порождении сыновнего процесса с использованием fork() порожденный процесс наследует:

• окружение. При формировании процесса ему передается некоторый набор параметров переменных, используя которые процесс может взаимодействовать с операционным окружением (интерпретатором команд и т.д.);
• файлы, открытые в процессе-отце, за исключением тех, которым было запрещено передаваться специальным параметром при открытии;
• способы обработки сигналов;
• разрешение переустановки действующего идентификатора пользователя (это то, что связано с s-bit’ом)*
• установленный режим отладки. В ОС имеется возможность системными вызовами осуществлять отладку (профилирование) программы, в процессе может быть указано — разрешено или нет профилирование;
• все присоединенные разделяемые сегменты памяти. У нас есть механизм управления разделяемыми ресурсами и в качестве одного из разделяемых ресурсов может выступать оперативная память, в ней может быть выделен сегмент, к которому одновременно имеют доступ несколько процессов. При формировании сыновнего процесса эта часть памяти также будет унаследована;
• текущий рабочий каталог и корневой каталог;

Не наследуется при создании нового процесса идентификатор процесса (почему — очевидно).

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

Суть exec в следующем: при обращении к ней происходит замена тела текущего процесса, оно заменяется в соответствии с именем исполняемого файла, указанного одним из параметров функции. Функция возвращает: -1, если действие не выполнено и код отличный от -1, если операция прошла успешно. Здесь следует отметить следующий факт — в Unix при работе с системными вызовами иногда возникают диагностические сообщения в виде кода ответа, которые невозможно разделить на конкретные причины, вызвавшие возврат этого кода. Примером этого являются коды “-1” для fork() и exec(...). Для того, чтобы обойти это неудобство, следует включить в программу файл “errno.h”, и после этого при возникновении отказов в выполнении системных вызовов в переменной “errno” будет код конкретной причины отказа выполнения заказа. Всевозможные коды отказа описаны в самом “errno.h”.

Давайте приведем небольшой пример:

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

main(argc, argv)

int argc;

char **argv;

{ int i, pid;

for (i=1; i<argc; i++) {

if (pid=fork()) continue; /* отец*/

execlp(argv[i], argv[i], (char *) 0);

}

}

Здесь, в случае, если pid=0, то мы замещаем тело процесса-сына процессом, имя файла которого нам передается в качестве параметра. Если же pid>0, то есть мы находимся в процессе-отце, то продолжаем создавать сыновьи процессы пока есть аргументы.

В качестве иллюстрации работы fork() можно привести следующую картинку:

Здесь процесс с PID=105 создается процессом с PID=101.

Также следует отметить, что если убивается процесс-отец, то новым отцом становится 1ый процесс ОС.

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

Мы начали рассматривать организацию процессов. Мы на пальцах показали, как размещается информация в ОС.

В принципе, вся информация, которая отражает оперативное состояние ОС, а также программы ОС, которые управляют этой информацией, которые управляют наиболее важными устройствами составляют ядро ОС.

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

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

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

Функция exec позволяет заменять тело процесса, т.е. при обращении к этой функции, в случае успешного выполнения ее, тело процесса меняется на новое содержимое, которое указано в виден аргументов функции exec, точнее в виде имени некоторого файла. Мы говорили о том, что сама по себе функция fork почти бессмысленна. Смысл функции exec можно уловить, т.е. можно выполнять в рамках одного процесса несколько задач. Возникает вопрос: почему формирование этого процесса раздроблено на две функции fork и exec, чем это обосновано? Во многих системах есть одна функция, формирующая процесс с заданным содержимым. Дело в том, что при обращении к функции fork, как уже неоднократно было сказано, создается копия процесса, в том числе процесс сын наследует все те файлы, которые были открыты в процессе отце и многие другие права и привилегии. Бывает ситуация, когда не хотелось бы, чтобы наследник наследовал все особенности отца. И есть возможность между выполнением функций fork и exec выполнить какие-то действия по закрытию файлов, открытию новых файлов, по переопределению чего-то, и т.д. В частности, вы при практических занятиях должны освоить отладчик системы deb. Какова суть его работы?

Пусть есть процесс-отладчик deb, запускается процесс, который отлаживается, и передавая некоторою информацию от отладчика к отлаживаемому процессу происходит процесс отладки. Но отлаживать процесс можно только тот, который разрешил себя отлаживать. Как раз здесь используется раздвоение fork/exec. Сначала я делаю копию своего процесса deb’ , после этого я разрешаю проводить трассировку текущего процесса, а после этого я запускаю функцию exec с отлаживаемой программой. Получается ситуация, что в процессе образуется именно та программа, которую надо отладить, и она, не зная ничего, уже работает в режиме отладки.

Загрузка операционной системы и образование начальных процессов.

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

Процесс getty при запуске запрашивает сразу же login. Копия процесса getty работает на один сеанс работы с пользователем, т.е. пользователь подтвердил свое имя и пароль, выполняет какие-то действия, и когда он выполняет команду завершения работы, то копия процесса getty завершает свою работу. И после завершения работы процесса getty, связанного с конкретным терминалом, запускается новая копия процесса getty.

Вот такая схема. Это те нетрадиционные формы формирования процессов в UNIX-е. Нетрадиционно формируется нулевой процесс (и он сам по себе нетрадиционен), нетрадиционно формируется первый процесс (который также нетрадиционен). Все остальные процессы работают по схеме fork/exec.

Эффективные и реальные идентификаторы процесса.

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

Планирование процессов в ОС UNIX.

Планирование основывается на понятии приоритета. Чем выше числовое значение приоритета, тем меньше приоритет. Приоритет процесса — это параметр, который размещен в контексте процесса, и по значению этого параметра осуществляется выбор очередного процесса для продолжения работы или выбор процесса для его приостановки. В вычислении приоритета используются две составляющие — P_NICE и P_CPU. P_NICE — это пользовательская составляющая приоритета. Она наследуется от родителя и может изменяться по воле процесса. Изменяться она может только в сторону увеличения значения (до некоторого предельного значения). Т.е. пользователь может снижать приоритет своих процессов. P_CPU — это системная составляющая. Она формируется системой следующим образом: по таймеру через предопределенные периоды времени P_CPU увеличивается на единицу для процесса, работающего с процессором (когда процесс откачивается на ВЗУ, то P_CPU обнуляется).

Процессор выделяется тому процессу, у которого приоритет является наименьшим. Упрощенная формула вычисления приоритета такова:

ПРИОРИТЕТ = P_USER + P_NICE + P_CPU

Константа P_USER различается для процессов операционной системы и остальных пользовательских процессов. Для процессов операционной системы она равна нулю, для процессов пользователей она равна некоторому значению (т.е. “навешиваются гирьки на ноги” процессам пользователя, что бы они не “задавливали” процессы системы). Это позволяет априори повысить приоритет системных процессов.

Схема планирования свопинга.

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

На прошлой лекции мы с вами посмотрели каким образом может осуществляться планирование в операционной системе UNIX. Мы с вами определили, что в принципе планированию в системе поддаются два типа процессов. Первый тип — это те процессы, которые находятся в оперативной памяти и между которыми происходит разделение времени ЦП. Мы выяснили, что этот механизм достаточно прост и строится на вычислении некоторого значения приоритета. А что будет, если системная составляющая достигнет максимального значения? В этом случае у процесса просто будет низший приоритет. Второй тип процессов, процессы которые находятся на диске, поддается планированию свопинга. Любой процесс в системе может находиться в двух состояниях — либо он весь откачан на ВЗУ, либо он весь находится в оперативной памяти. И в том и в другом случае с процессом ассоциирована некоторое значение P_TIME, которое растет по мере нахождения процесса в том конкретном состоянии. Это значение обнуляется, когда процесс меняет свое состояние (то есть перекачивается в оперативную память или обратно). В свою очередь система использует P_TIME как значение некоторого приоритета (чем больше это значение, тем более вероятно, что процесс сменит свой статус).

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

Мы с вами говорили о том, что разные UNIX-ы могут по-разному представлять процесс в ходе его обработки. Некоторые UNIX-ы представляют тело процесса как единое целое (и код и данные) и все перемещения осуществляются согласно тому, что это единое целое. Некоторые (современные) UNIX-ы рассматривают процесс как объединение двух сегментов — сегмента кода и сегмента данных. С этим связаны проблемы запуска процессов, планирования времени процессора и планирования свопинга.

С этого момента времени мы начинаем долго и упорно рассматривать различные способы взаимодействия процессов в операционной системе UNIX. Маленькое техническое добавление. Я сейчас вам продекларирую две системные функции, которыми мы будем пользоваться впоследствии. Это функции дублирования файловых дескрипторов (ФД).

Пример:

Программные каналы.

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

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

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

Сигналы

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

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

• некоторое событие внутри программы, например, деление на ноль или переполнение;
• событие, связанное с приходом некоторой информации от устройства, например, событие, связанное с передачей от клавиатуры комбинации “Ctrl+C”;
• событие, связанное с воздействием одного процесса на другой, например, “sig_kill”.

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

Перечень сигналов находится в include-файле “signal.h”.

Есть сигналы, которые присутствуют практически во всех Unix, но также есть сигналы, специфичные лишь для конкретной версии Unix (FreeBSD, SCO Unix, Linux, ...) Например, в версии BSD есть сигнал приостановки работы процесса, реакцией на него является замораживание процесса, а есть сигнал, который размораживает процесс. Это сигнал FreeBSD версии.

Прототип функции обработки сигнала:

void (* signal (sig, fun)) ()

int sig;

void (* fun) ();

При обращении к signal мы передаем:

sig — имя сигнала;

fun — указатель на функцию, которая будет обрабатывать событие, связанное с возникновением этого сигнала. Она возвращает указатель на предыдущую функцию обработки данного сигнала.

Мы говорили о том, что событие, связанное с возникновением сигнала может быть обработано в системе тремя способами:

1. SIG_DEF — стандартная реакция на сигнал, которая предусмотрена системой;
2. SIG_IGN — игнорирование сигнала (следует отметить, что далеко не все сигналы можно игнорировать, например, SIG_KILL);
3. Некоторая пользовательская функция обработки сигнала.

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

Приведем пример программы “Будильник”. Средствами ОС мы будем “заводить” будильник. Функция alrm инициализирует появление сигнала SIG_ALRM.

main ()

{ char s[80];

signal(SIG_ALRM, alrm); /* установка режима связи с событием SIG_ALRM на функцию alrm */

alarm(5); /* заводим будильник */

printf(“Введите имя \n”);

for (;;) {

printf(“имя:”);

if (gets(s,80) != NULL) break;

};

printf(“OK! \n”);

}

alrm () {

printf(“\n жду имя \n”);

alarm(5);

signal (SIG_ALRM,alrm);

}

В начале программы мы устанавливаем реакцию на сигнал SIG_ALRM на функцию alrm, далее мы заводим будильник, запрашиваем “Введите имя” и ожидаем ввода строки символов. Если ввод строки задерживается, то будет вызвана функция alrm, которая напомнит, что программа “ждет имя”, опять заведет будильник и поставит себя на обработку сигнала SIG_ALRM еще раз. И так будет до тех пор, пока не будет введена строка.

Здесь имеется один нюанс: если в момент выполнения системного вызова возникает событие, связанное с сигналом, то система прерывает выполнение системного вызова и возвращает код ответа, равный “-1”. Это мы можем также проанализировать по функции errno.

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

Еще две функции, которые необходимы нам для организации взаимодействия между процессами:

Давайте рассмотрим еще один пример. Наш будильник будет уже многопроцессный.

alr() { printf(“\n Быстрее!!! \n”);

signal (SIG_ALRM, alr);

}

main () { char s[80; int pid;

signal(SIG_ALRM, alr);

if (pid=fork()) for (;;)

{sleep(5); kill(pid, SIG_ALRM);}; /* приостанавливаем процесс на 5 секунд и отправляем сигнал SIG_ALRM процессу сыну */

print(“имя?”);

for (;;) {printf(“имя?”);

if gets(s,80)!=NULL) break;

}

printf(“OK!\n”);

kill(getpid(), SIG_KILL); /* убиваем зациклившегося отца */

}

Следует заметить, что в разных версиях Unix имена сигналов могут различаться.

Наша программа реализуется в двух процессах.

Таким образом, мы описали базовые средства взаимодействия процессов в Unix: порождение процесса, замена тела процесса, взаимодействие при помощи передач/приемов сигналов.

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

Трассировка

1. Установка контрольной точки;
2. Обработка ситуации, связанной с приходом в контрольную точку;
3. Чтение/запись информации в отлаживаемой программе;
4. Остановка/продолжение выполнения отлаживаемого процесса;
5. Шаговый режим отладки (режим, при котором отлаживаемая программа будет останавливаться после выполнения каждой инструкции);
6. Передача управления на произвольную точку отлаживаемой программы;
7. Обработка аварийных остановок;

Итак, есть функция, которая называется

int ptrace(int op, pid, addr, data)

Суть этой функции заключается в следующем: ptrace в подавляющем большинстве случаев работает в отцовском процессе, и через возможности ptrace организуется управление сыном. В общем случае нельзя трассировать любой процесс. Для того, чтобы процесс можно было отлаживать, процесс-сын должен подтвердить согласие на собственную трассировку, в последнем случае следует в самом начале выполнения вызвать ptrace с кодом операции равном нулю (op=0), этот вызов разрешает в дальнейшем трассироваться процессом-отцом. После этого в сыновнем процессе обращений к ptrace может и не быть.

Посмотрим, какие возможности есть у отцовского процесса по управлению процессом-сыном. Для начала разберем параметры функции ptrace:

op — код операции;

pid — PID сыновнего процесса;

addr — некоторый адрес внутри сыновнего процесса (будет объяснено при описании параметра op);

data — слово информации;

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

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

1. Послать сыну сигнал SIG_TRAP;
2. Выполнить wait;
3. После того, как сын остановился, отец получает соответствующий код ответа от функции wait.

После этого считается, что можно выполнять все действия, которые были описаны выше.

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

Что происходит при установке контрольной точки? При запросе на установку контрольной точки по заданному адресу отладчик читает содержимое отлаживаемого процесса по этому адресу и записывает это содержимое в таблицу (Сохраненное слово). Затем, отладчик по указанному адресу записывает машинную команду, которая вызовет возникновение события, связанного с некоторым сигналом (например, команда деления на ноль, вызов программного прерывания или любая команда, вызывающая событие, которое должно быть известно), после этого мы можем запустить отлаживаемый процесс (ptrace, op=7). В тот момент, когда управление придет на адрес, где мы установили контрольную точку, произойдет прерывание процесса и событие, связанное с известной установкой. Для отладчика это будет видно следующим образом — после запуска на продолжение отлаживаемого процесса выполняется функция wait, которая ожидает события в отлаживаемом процессе. Событие произошло, его причиной был некоторый сигнал. Действия отладчика:

1. Не совпадает ли сигнал, который прервал процесс с сигналом, который является контрольным сигналом. Если не совпадает, то произошла какая-то ситуация, которая обрабатывается по-своему. Если же совпадает, то мы, скорее всего, попали на контрольную точку (предположим, что у нас это сигнал деления на ноль).
2. После этого мы читаем из контекста процесса точку останова — если она совпала с одной из позиций таблицы отладчика, то это означает, что мы совершенно точно попали на контрольную точку. Если такого совпадения не обнаружено, то это означает, что тревога ошибочна и обработка сигнала уходит по другому направлению.
3. Если все-таки мы оказались на контрольной точке, то можем выполнить какие-то действия над отлаживаемым процессом (чтение/запись регистров, ячеек памяти и прочее).
4. Наконец, нам хочется продолжить выполнение программы, но при этом мы бы хотели сохранить контрольную точку. Что может сделать отладчик? Он восстанавливает оригинальное содержимое машинного слова. Включает режим трассировки и запускает программу с прерванного адреса. После чего выполняется команда, которую мы восстановили и процесс приостанавливается (так как включена трассировка) на следующей команде. Теперь мы опять по нужному адресу пишем команду деления на ноль и продолжаем процесс уже вне режима трассировки. Таким образом мы восстановили контрольную точку.

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

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

Итак, мы обсудили с точностью до некоторых деталей структуру адресного отладчика.

Приведем небольшой пример трассировки:

Процесс-сын:

int main()

{ int i;

return i/0;

}

Процесс отец:

(Мы будем писать программу в нотации ОС FreeBSD)

#include <stdio.h>

#include <unistd.h>

#include <signal.h>

#include <sys/types.h>

#include <sys/ptrace.h>

#include <sys/wait.h>

#include <machine/reg.h>

int main(int argc; char *argv[])

{ pid_t pid;

int status;

struct reg REG;

switch (pid=fork()) {

case 0: ptrace(PT_TRACE_ME,0,0,0); /* если в сыне, то разрешаем трассировку */

execl(“son”,”son”,0); /* и замещаем тело процесса */

/* после входа в сына, процесс-сын будет остановлен с сигналом SIG_TRAP, это правила игры — как только отлаживаемый процесс меняет тело, то происходит приостановка в самом начале */

default: break; /* если в отце, то выходим из switch */

}

/* в отце */

for (;;) {

wait(&status); /* ждем, когда отлаживаемый процесс приостановится (первый раз это произойдет сразу после замены тела сыновнего процесса), то есть, когда в нем возникнет событие */

ptrace(PT_GET_REGS,pid, (caddr_t) &REGS, 0); /* теперь мы можем прочесть и вывести содержимое некоторых регистров */

printf(“EIP=%O.8X\+ESP=%O.8X\n”, REG.r_eip, REG.r_esp);

if (WIFSTOPPED(status) || WIFSIGNALED(status)) {

/* Выше написанные макросы описаны в файлах include, они обрабатывают структуру, возвращаемую функцией wait, если у нас условия приостановки нормальные, то начинаем разбирать причину */

printf(“сигнал:”);

switch(WSTOPSIG(status)) {

case SIGINT: printf(“INT\n”); break;

case SIGTRAP: ...

...

defalt: printf(“%d”, WSTOPSIG(status));

};

if (WSTOPSIG(status)!=SIGTRAP) exit(1);

};

if (WIFEXITED(status)) { /* если отлаживаемый процесс завершился */

printf(“процесс закончен с кодом = %d\n”, WEXITSTATUS(status));

exit};

ptrace (PT_CONTINUE, pid, (caddr_t) 1, 0); /* продолжаем выполнение трассируемого процесса */

}

exit(0);

}

При первой итерации бесконечного цикла мы остановимся при получении сыном сигнала SIG_TRAP, посмотрим, не закончился ли наш процесс нормально (а он нормально закончиться не может, так как делит на ноль), то мы обратимся к ptrace, которая продолжит выполнение трассируемого процесса. На второй итерации мы попадем на событие деления на ноль. Таким образом, мы получим две порции информации — первая связана с самой первой приостановкой сыновнего процесса, когда заменяется его тело, а вторая — связана с делением на ноль.

Теперь мы с вами обсудим некоторые дополнительные возможности по организации управления ходом вычисления в процессах Unix.

Нелокальные переходы

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

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

Для решения второй проблемы в Unix имеется две функции, которые обеспечивают нелокальные переходы:

#include <setjmp.h>

int setjmp(jmp_buf env);

void longjmp(jmp_buf env, int val);

Нелокальный переход. При обращении к longjmp переходит передача управления на точку, атрибуты которой зафиксированы в env.

Если мы сделали setjmp, а затем откуда-то longjmp с той же переменной env, то мы вернемся на обращение к функции setjmp и в качестве кода ответа setjmp получим значение val.

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

Пример:

#include <setjmp.h>

jmp_buf save; /* объявляем глобальный буфер save */

main()

{ int ret;

switch(ret=setjmp(save)){

case 0: printf(“до нелокального перехода\n”);

a();

printf(“после нелокального перехода\n”); /* этот текст никогда не будет напечатан */

default: break;

}

}

a() {longjmp(save,1)};

Рассмотрим функцию main() — в переключателе мы обращаемся к setjmp, она запомнит состояние процесса на тот момент и вернет ноль. После этого мы перейдем по варианту связанному с нулем — печатаем текст и вызываем a(). В a() мы вызываем longjmp(save,1), после этого мы попадем опять на переключатель, но на этот раз переменная ret будет равна единице. Произойдет завершение процесса.

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

Как работает длинный переход со стеком? Он не запоминает стек, он запоминает указатель стека и восстанавливает его. Конечно, мы можем смоделировать ситуацию, в которой переход будет работать некорректно, например, вызовем функцию, в ней сделаем setjmp, выйдем из функции, как-то поработаем дальше и попробуем сделать longjmp на функцию, из которой уже вышли. Информация в стеке будет уже потеряна и наш переход приведет к ошибке. Такие ситуации отдаются на откуп программистам.

Нелокальный переход работает в пределах одного процесса.

До этого мы говорили о взаимодействии между родственными процессами (отцом и сыном, детьми одного отца и т.п.). Реально же Unix имеет набор средств, поддерживающих взаимосвязь между произвольными процессами. Один из таких механизмов — система межпроцессного взаимодействия (IPC- interprocess communication). Суть этой системы заключается в следующем — имеется некоторое количество ресурсов, которые называют в системе разделяемыми. К одному и тому же разделяемому ресурсу может быть организован доступ произвольного количества произвольных процессов. При этом возникает некоторая проблема именования ресурсов. Если мы вспомним каналы, то в них за счет наследования нужные файловые дескрипторы были известны и с именованием проблем не возникало.

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

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

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

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

Сразу возникает вопрос — а если сразу трое подошли к ресурсу? То есть очевидна проблема синхронизации доступа к разделяемому ресурсу.

Мы с вами будем рассматривать конкретные средства IPC, которые будем рассматривать далее. А пока отмечу, что IPC поддерживает три разновидности разделяемых ресурсов:

1. Разделяемая память. Возможность иметь в нескольких произвольных процессах общее поле оперативной памяти и работать с ним, как с неким массивом, на который имеется указатель. Мы видим, что проблема синхронизации здесь огромна, хотя базово никакой синхронизации не предусмотрено;
2. Механизм передачи сообщений. В качестве разделяемого ресурса — очередь сообщений. Суть в том, что есть объект, который называется очередью сообщений, он может содержать произвольное в пределах разумного количество сообщений разной длины и типа. Тип сообщения — атрибут, который приписывается сообщению. Соответственно, очередь сообщений может рассматриваться как единое хронологическое объединение, так и множество объединенных по типам подочередей. Есть возможность читать и писать сообщения. Проблема синхронизации также имеется;
3. Семафоры. Это есть нечто, что позволяет синхронизировать доступ к разделяемым ресурсам;

Вот об этом мы будем говорить далее.

Interprocess Communication

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

1. Именование;
2. Синхронизация;

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

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

Решения этих проблем мы и будем рассматривать.

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

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

#include <sys/types.h>

#include <sys/ipc.h>

key_t ftok(char *s, char c);

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

Давайте посмотрим конкретные средства работы с разделяемыми ресурсами.

Разделяемая память.

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

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

Первая функция — создание общей памяти.

int shmget (key_t key, int size, int shmemflg);

key — ключ разделяемой памяти

size — размер раздела памяти, который должен быть создан

shmemflg — флаги

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

Следующая функция — доступ к разделяемой памяти:

char *shmat(int shmid, char *shmaddr, int shmflg);

shmid — идентификатор разделяемого ресурса

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

shmflg — флаги. Они определяют разные режимы доступа, в частности, SHM_RDONLY.

Эта функция возвращает указатель на адрес, начиная с которого будет начинаться запрашиваемая разделяемая память. Если происходит ошибка, то возвращается -1.

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

Третья функция — открепление разделяемой памяти:

int shmdt(char *shmaddr);

shmaddr — адрес прикрепленной к процессу памяти, который был получен при подключении памяти в начале работы.

Четвертая функция — управление разделяемой памятью:

int shmctl(int shmid, int cmd, struct shmid_ds *buf);

shmid — идентификатор разделяемой памяти

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

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

Передача сообщений.

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

Система IPC позволяет создавать разделяемый ресурс, называемый “очередь сообщений” — таких очередей может быть произвольное количество. По аналогии с разделяемой памятью — мы можем создать очередь, подключиться к ней, послать сообщение, принять сообщение, уничтожить очередь и т.д. Рассмотрим функции работы с очередями сообщений:

Создание очереди сообщений:

int msgget(key_t key, int flags);

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

Отправка сообщения:

int msgsnd( int id, struct msgbuf *buf, int size, int flags);

id — идентификатор очереди сообщения;

struct msgbuf {long type; char mtext[s]} *buf — первое поле — тип сообщения, а второе — указатель на тело сообщения;

size — размер сообщения, здесь указывается размер сообщения, размещенного по указателю buf;

flags — флаги, в частности, флагом может быть константа IPC_NOWAIT. При наличии такого флага будут следующие действия — возможна ситуация, когда буфера, предусмотренные системой под очередь сообщений, переполнены. В этом случае возможны два варианта — процесс будет ожидать освобождения пространства, если не указано IPC_NOWAIT, либо функция вернет -1 (с соответствующим кодом в errno), если было указано IPC_NOWAIT.

Прием сообщения:

int msgrcv( int id, struct msgbuf *buf, int size, long type, int flags);

id — идентификатор очереди;

buf — указатель на буфер, куда будет принято сообщение;

size — размер буфера, в котором будет размещено тело сообщения;

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

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

Управление очередью:

int msgctl( int id, int cmd, struct msgid_dl *buf);

id — идентификатор очереди;

cmd — команда управления, для нас интерес представляет IPC_RMID, которая уничтожит ресурс.

buf — этот параметр будет оставлен без комментария.

Мы описали два средства взаимодействия между процессами.

Что же мы увидели? Понятно, что названия и описания интерфейсов мало понятны. Прежде всего следует заметить то, что как только мы переходим к вопросу взаимодействия процессов, у нас возникает проблема синхронизации. И здесь мы уже видим проблемы, связанные с тем, что после того, как мы поработали с разделяемой памятью или очередью сообщений, в системе может оставаться “хлам”, например, процессы, которые ожидают сообщений, которые в свою очередь не были посланы. Так, если мы обратились к функции получения сообщений с типом, которое вообще не пришло, и если не стоит ключ IPC_NOWAIT, то процесс будет ждать его появления, пока не исчезнет ресурс. Или мы можем забыть уничтожить ресурс (и система никого не поправит) — этот ресурс останется в виде загрязняющего элемента системы.

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

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

Итак, мы к текущему моменту разобрали два механизма взаимодействия процессов в системе IPC: разделяемую память и механизм сообщений.

Давайте попробуем написать программу, в которой первый процесс будет принимать некую текстовую строку и в случае, если некоторая строка начинается с буквы “a”, то эта текстовая строка будет передана процессу A, если “b” — процессу B, если “q”, то сообщение будет передано процессам A и B, и будет осуществлен выход

Основной процесс:

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

#include <stdio.h>

struct { long mtype;

char Data[256];

} Message;

int main(void)

{ key_t key;

int msgid;

char str[256];

key = ftok(“/usr/mash”,’S’); /* создаем ключ для работы с ресурсом — ключ уникальный и однозначно определяет доступ к разделяемому ресурсу одного типа, то есть с одним ключом могут быть связаны разделяемые ресурсы памяти, очередь сообщений и семафоров, но две области памяти связаны одним ключом быть не могут */

msgid = msgget(key, 0666 | IPC_CREAT); /* создаем очередь сообщений, 0666 — права доступа к очереди, разрешают всем читать и писать */

for (;;) {

gets(str); /* получаем строку */

strcpy(Message.Data, str); /* копируем ее в буфер сообщения */

switch(str[0]) {

case ‘a’:

case ‘A’: Message.mtype = 1; /* если строка начинается с “a”, то ставим тип сообщения равным единице, это означает, что приемником будет первый процесс */

msgsnd(msgid, (struct msgbuf *) &Message), 1+strlen(str),0); /* отправляем сообщение */

break;

case ‘b’:

case ‘B’: Message.mtype = 2; /* посылаем сообщение второму процессу */

msgsnd(msgid, (struct msgbuf *) &Message), 1+strlen(str),0);

break;

case ‘q’:

case ‘Q’: Message.mtype = 1;

msgsnd(msgid, (struct msgbuf *) &Message), 1+strlen(str),0);

Message.mtype = 2;

msgsnd(msgid, (struct msgbuf *) &Message), 1+strlen(str),0);

sleep(10); /* берем таймаут для гарантии, что все предыдущие сообщения дошли */

msgctl(msgid, IPC_RMID, NULL); /* убиваем разделяемый ресурс */

exit(0); /* завершаем процесс */ }

}

Давайте рассмотрим процесс-приемник. Рассмотрим только процесс A, так как B будет аналогичен, за исключением указания типа сообщений для приема.

proc_A:

...

int main(void)

{ key_t key;

int msgid;

key = ftok(“/usr/mash”, ‘S’); /* получаем ключ к очереди по параметрам, аналогичным процессу-отправителю */

msgid = msgget(key, 0666 | IPC_CREAT); /* создаем или подключаемся к очереди сообщений */

if (Message.Data[0]==’q’) || (Message.Data[0]==’Q’) break; /* если сообщение начинается с “q” — заканчиваем выполнение процесса-получателя */

printf(“...”);

}

exit(0);

}

Семафоры.

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

Это мы рассмотрели семафоры в общем случае. Сейчас же рассмотрим семафоры в системе IPC.

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

int semget(key_t key, int n, int flags)

Данная функция создает массив размерности n семафоров с заданным ключом и флагами. Функция возвращает идентификатор ресурса или -1, если произошла ошибка.

int semop(int semid, struct sembuf *SOPS, int n)

semid — идентификатор ресурса семафоров;

SOPS — указатель на структуру sembuf;

n — количество указателей на эту структуру, которые передаются функции semop, соответственно в структуре sembuf передается вся информация о необходимом действии;

struct sembuf

short sem_op; /* код операции над семафором */

short sem_flg; /* флаги */ }

Все это интерпретируется следующим образом. Пусть значение семафора с номером sem_num есть число sem_val. Если значение операции semop не равно нулю, то оценивается значение сумма sem_val+semop, если эта сумма больше или равна нулю, то значение данного семафора устанавливается новым, равным сумме предыдущего значения плюс код операции (semop), если эта сумма меньше нуля, то действие процесс будет приостановлено до наступления одного из следующих событий: до тех пор, пока значение этой суммы не станет >=0; придет сигнал (при приходе сигнала процесс снимется с ожидание) при этом semop будет равно “-1”. Если же semop=0, то процесс будет ожидать обнуления значения семафора, при этом, если мы обратились к функции semop c нулевым кодом операции, а значение семафора уже было нуль, то ничего не произойдет. Если значение флага равно нулю, то флаги не используются. Флагов на самом деле нет, но, например, есть флаг IPC_NOWAIT, когда процесс ничего ждать не будет.

Заметим, что мы можем передать n структур и выполнить действия с n семафорами.

Управление массивом семафоров:

int semctl(int semid, int n, int cmd, union semun arg);

semid — идентификатор ресурса

n — номер семафора

cmd — команда (команды над семафорами, в том числе IPC_RMID)

arg — объединение, содержащее информацию о семафорах.

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

1. программа пишется человеком, а прерывается аппаратурой, отсюда возможно нарушение неразделяемости;
2. в развитых вычислительных системах, которые поддерживают многопроцессорную обработку или обработку разделяемых ресурсов в рамках одного процесса, предусмотрены семафорные команды, которые фактически реализовывают операции P и V. Это важно.

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

Каждый элемент массива — семафор. Для управления работой семафора есть функции:

Давайте приведем пример, которым попытаемся проиллюстрировать использование семафоров на практике.

Наша программа будет оперировать с разделяемой памятью.

1 процесс — создает ресурсы “разделяемая память” и “семафоры”, далее он начинает принимать строки со стандартного ввода и записывает их в разделяемую память.

2 процесс — читает строки из разделяемой памяти.

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

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

1й процесс:

#include <stdio.h>

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

int main(void)

{ key_t key;

int semid, shmid;

struct sembuf sops;

char *shmaddr;

char str[256];

key = ftok(“/usr/mash/exmpl”,’S’); /* создаем уникальный ключ */

shmid = shmget(key,256, 0666 | IPC_CREAT); /*создаем разделяемую память на 256 элементов */

shmaddr = shmat(shmid, NULL, 0); /* подключаемся к разделу памяти, в shaddr — указатель на буфер с разделяемой памятью*/

semctl(semid,0,IPC_SET, (union semun) 0); /*инициализируем семафор со значением 0 */

sops.sem_num = 0; sops.sem_flg = 0;

/* запуск бесконечного цикла */

while(1) { printf(“Введите строку:”);

if ((str = gets(str)) == NULL) break;

sops.sem_op=0; /* ожидание обнуления */

semop(semid, &sops, 1); /* семафора */

strcpy(shmaddr, str); /* копируем строку в разд. память */

sops.sem_op=3; /* увеличение семафора на 3 */

semop(semid, &sops, 1);

}

sops.sem_op=3; /* что пора завершаться */

semop(semid, &sops, 1);

sops.sem_op = 0; /* ждем, пока обнулится семафор */

semop(semid, &sops, 1);

shmdt(shmaddr); /* отключаемся от разд. памяти */

shmctl(shmid, IPC_RMID, NULL); /* уничтожаем разделяемую память */

exit(0);

}

2й процесс:

/* здесь нам надо корректно определить существование ресурса, если он есть — подключиться, если нет — сделать что-то еще, но как раз этого мы делать не будем*/

#include <stdio.h>

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

int main(void)

{ key_t key; int semid;

struct sembuf sops;

char *shmaddr;

char st=0;

/* далее аналогично предыдущему процессу — инициализации ресурсов */

semid = semget(key,1,0666 | IPC_CREAT);

shmid = shmget(key,256, 0666 | IPC_CREAT);

shmaddr = shmat(shmid, NULL, 0);

sops.sem_num = 0; sops.sem_flg = 0;

/* запускаем цикл */

while(st!=’Q’) {

printf(“Ждем открытия семафора \n”);

/* ожидание положительного значения семафора */

sops.sem_op=-2;

semop(semid, &sops, 1);

/* будем ожидать, пока “значение семафора”+”значение sem_op” не перевалит за 0, то есть если придет “3”, то “3-2=1” */

/* теперь значение семафора равно 1 */

st = shmaddr[0];

{/*критическая секция — работа с разделяемой памятью — в этот момент первый процесс к разделяемой памяти доступа не имеет*/}

/*после работы — закроем семафор*/

sem.sem_op=-1;

semop(semid, &sops, 1);

}

shmdt(shmaddr); /* освобождаем разделяемую память и выходим */

exit(0);

}

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

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

Наша самоцель — не изучение тех средств, которые предоставляет Unix, а изучение принципов, которые предоставляет система для решения тех или иных задач, так как другие ОС предоставляют аналогичные или похожие средства управления процессами.

Мы с вами в начале курса говорили о системах программирования.

Проектирование.

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

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

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

Но тем не менее следует понимать, что период проектирования есть очень важный момент.

Кодирование.

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

Основной компонент системы кодирования — язык программирования. В голове каждого программиста лежит иерархия языков программирования — от машинного кода и ассемблера до универсальных языков программирования (FORTRAN, Algol, Pascal, C и т.д.), специализированных языков (SQL, HTML, Java и т.д.)

Мы имеем ЯП и программу, которая написана в нотации этого языка. Система программирования обеспечивает перевод исходной программы в объектный язык. Этот процесс перевода называется трансляцией. Объектный язык может быть как некоторым языком программирования высокого уровня (трансляция), так и машинный язык (компиляция). Мы можем говорить о трансляторах-компиляторах и трансляторах-интерпретаторах.

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

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

На сегодняшний день каждый из методов — и компиляция и интерпретация занимают свои определенные ниши.

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

• проектирование
• кодирование
• тестирование
• отладка

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

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

Этап кодирования

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

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

Кросс-трансляторы.

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

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

Обработка модульной программы.

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

Пусть есть некоторая группа модулей и есть соответствующие этим модулям тексты программ, на языках, используемых для программирования. Языковыми средствами определены связи между модулями.

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

В эту же схему также часто добавляется этап оптимизации программы, причем оптимизация может происходить до этапа трансляции (т.е. в терминах исходного языка) или/и после трансляции (в терминах машинного кода). Например до трансляции можно вычислить все константные подвыражения и т.д. Для машин типа PC этап оптимизации может быть не столь важен, потому что этот вопрос обычно разрешается покупкой какого-нибудь более быстрого компонента, но есть класс машин (mainframe), для которых этот этап необходим.

Давайте посмотрим на проблему кодирования с другой стороны. Мы посмотрим как устроен этап трансляции.

Каждый транслятор при обработке программы выполняет следующие действия.

1. Лексический анализ.
2. Синтаксический анализ.
3. Семантический анализ и генерация кода.

Лексический анализ.

Лексический анализатор производит анализ исходного текста на предмет правильности записи лексических единиц входного языка. Затем он переводит программу из нотации исходного текста в нотацию лексем.

Лексические единицы — это минимальные конструкции, которые могут быть продекларированы языком. К лексическим единицам относятся:

• идентификаторы
• ключевые слова
• код операции
• разделители
• константы

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

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

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

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

Синтаксический анализ.

Семантический анализ.

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

Проходы трансляторов.

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

Есть трансляторы однопроходные. Это означает, что транслятор просматривает исходный текст от начала и до конца, и к концу просмотра (в случае правильности программы) он получает объектный модуль.

Если мы посмотрим Си-компилятор, с которым вы работаете, то скорее всего он двухпроходный. Первый проход — это работа препроцессора. После первого прохода появляется чистая Си-программа без всяких препроцессорных команд. На Втором проходе происходит лексический, синтаксический и семантический анализ, и в итоге вы получаете объектную программу в виде ассемблера.

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

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

Этапы тестирования и отладки

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

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

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

Традиционными интерпретаторами команд Unix являются: sh, csh, bash и некоторые другие. В принципе, все эти интерпретаторы похожи друг на друга и являются развитием sh.

Рассмотрим csh.

Интерпретатор распознает структуру вводимой команды. Предполагается, что команда, это последовательность слов, заканчивающихся некоторым символом. Слово — последовательность символов, не содержащая разделителей. Разделители — это набор фиксированных символов, позволяющих разделять слова в командной строке (например, пробел, запятая, точка с запятой и т.д.), при этом разделители имеют в csh свою интерпретацию. В частности разделитель “||” — создание конвейера между командами (стандартный ввод одной команды будет стандартным выводом другой, например, “ls||more”).

Unix поддерживает в своих интерпретаторах так называемые метасимволы. Они обычно встречаются в словах команд и интерпретируются по специальным правилам. Рассмотрим некоторые из них:

“*”: означает любую последовательность символов. Например, команда “rm *” удалит все файлы, которые не начинаются с символа “точка” (чтобы их удалить следует набрать “rm *.*”);

“?”: означает, что на месте этого символа может быть любой символ. Например “rm ?” удалит все файлы, имена которых состоят из одного символа;

“квадратные скобки”: внутри скобок указываются альтернативные группы. Например, “[abc]” означает, что вместо квадратных скобок может быть подставлен один символ из набора “abc”. Можно указать диапазон, например “[0-9]”;

Командный интерпретатор csh позволяет объединять команды. Для этого также используются метасимволы:

“(...)” — Если внутри скобок перечислены команды, например “(cd /etc; ls -la || grep pas)”, то фактически запустится новый интерпретатор команд, который выполнит последовательность команд, находящуюся в круглых скобках. Заметим отличие такого запуска от обычного — если мы выполним команду “cd /etc” обычным способом, то наш интерпретатор сменит каталог, тогда как при запуске еще одного интерпретатора каталог у основного интерпретатора не изменится.

“{...}” — все команды, перечисленные внутри фигурных скобок будут запущены последовательно слева направо, но при этом на стандартный вывод будет положена объединенная последовательность стандартных выводов всех команд. Например, “{more t.b; more t.c} > tt.b”. В результате в файле tt.b окажутся стандартные выводы обеих команд “more”, если бы фигурных скобок не было, то указатель перенаправления ввода вывода относился бы лишь к последней, в нашем случае второй, команде.

Интерпретатор команд имеет набор встроенных команд. Все команды, которые мы используем делятся на два типа: первый — это те, которые находятся в отдельных файлах, их можно добавлять, удалять, модифицировать; второй — которые “зашиты” внутри интерпретатора. В частности, команда “kill” — команда интерпретатора, то есть передача сигнала осуществляется от имени интерпретатора. Есть, например, встроенная команда “alias” — она используется для переименования существующих команд.

Интерпретатор команд предоставляет возможность программирования на уровне csh. Для этого в csh предусмотрена декларация переменных, присвоения им значения, а также набор высокоуровневых операторов, которые по своей семантике похожи на операторы языка C (поэтому он и называется cshell). Оперируя с переменными, csh можно создавать программы и выполнять многие другие действия. Кроме всего, имеются предопределенные имена переменных cshell, которые отвечают за настройку системы (например, количество строк в предыстории, ее сохранение — переменные HISTORY, SAVEHISTORY). Кроме таких переменных, через которые осуществляется настройка и которые мы можем изменять, есть еще один класс переменных cshell — это внутренние переменные, такие переменные, которые имеют предопределенные имена и определяют свое значение через внутренние функции интерпретатора команд.

Другие переменные:

home — имя домашнего каталога.

ignoreeof — установка этой переменной блокирует завершение сеанса по вводу Ctrl-D.

prompt — в системе можно варьировать приглашение (по умолчанию — “$”), оно может быть достаточно интеллектуальным (включить дату, путь и прочее).

Все переменные окружения можно модифицировать средствами cshell’а.

Работа с файлами.

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

Команды cshell можно вводить построчно, а можно cshell программу записать как файл и исполнять его.

Cshell имеет две разновидности этих файлов, это файлы, которые могут выполняться при старте cshell, и которые могут выполняться при завершении сеанса.

При старте cshell работает с файлами:

.cshrc — Это командный файл, в котором пользователь по своему усмотрению может размещать произвольное число команд на cshell, то есть там могут быть перечислены команды, которые пользователь хочет выполнить при старте системы (проверка файловой системы, например)

.login — Этот файл запускается после “.cshrc“, он запускается при входе в систему (“.cshrc” запускается при запуске cshell), то есть при запуске еще одного csh для нового сеанса будет запущен “.cshrc”, но “.login” запущен уже не будет. С учетом этого следует его использовать (указывать, например, переобозначения команд).

При завершении работы cshell выполняется

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

Имеется стандартный файл, который образуется в ходе работы системы — это файл “.history”, если определена возможность savehistory, то история пишется в этот файл.

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

Первые многомашинные ассоциации появились в начале 60х годов, это было связано с двумя проблемами:

• проблема массового доступа к некоторым вычислительным ресурсам;
• появление задач, требовавших для их решения привлечения более, чем одной машины;

К первым многомашинным комплексам можно отнести терминальные комплексы.

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

К некоторому каналу передачи данных вычислительной системы подключен мультиплексор. Это устройство, назначением которого является взаимодействие внешних устройств (У) с вычислительной системой через один канал ввода-вывода. То есть любое сообщение, поданное на один из входов мультиплексора, как-то преобразовывается и попадает в вычислительную систему через один единственный канал.

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

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

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

Виды каналов связи.

В качестве локальных терминалов в системе могут присутствовать и компьютеры, эмулирующие работу терминала.

Соответственно, в МВК возникают все те проблемы, которые возникают при использовании различными процессами общих ресурсов.

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

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

Абонентские машины (АМ) могут взаимодействовать друг с другом с использованием коммутационной среды через каналы связи и коммутационные машины.

Существует ряд классических разновидностей сетей:

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

Вот некоторая предыстория развития многомашинных ассоциаций (МА).

Развитие МА вообще и сетей ЭВМ в частности определило тот факт, что возникла необходимость в стандартизации взаимодействия, происходящего в сети. Поэтому в конце 70хх, начале 80хх годов, международная организация стандартизации предложила стандарт взаимодействия открытых систем ISO/OSI.

Была предложена семиуровневая модель организации взаимодействия компьютеров со средой передачей данных.

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

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

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

Эта модель ISO/OSI требует жесткой стандартизации всех уровней, интерфейсов, протоколов. Если эти стандарты есть, то мы можем просто менять содержимое уровней (например, если у нас есть стандарты на вилки и розетки, то мы можем включать в электрическую сеть абсолютно разные приборы).

Теперь мы поговорим об Интернете, но поговорим о нем с внутренней — технической стороны.

Несколько слов предыстории:

В начале 80хх годов началась стандартизация протоколов взаимодействия в сети. Вся стандартизация проходила естественным путем (что нестандартно — то нежизнеспособно). Сначала стандартизации подверглись языки программирования, потом протоколы и взаимодействие в ОС. Также появилась модель ISO/OSI.

С этого момента (появления стандартов) можно говорить о начале Интернета.

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

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

Internet основан на протоколах TCP/IP. Иногда говорят: “протокол TCP/IP” — но это неправильно, так как под этой аббревиатурой скрывается целый набор протоколов, объединенных под одним названием. Кстати, здесь есть отдельно протокол TCP и протокол IP.

Семейство TCP/IP строится по 4х уровневой схеме. Рассмотрим таблицу соответствия TCP/IP модели ISO/OSI:

Уровень доступа к сети TCP/IP обеспечивают аппаратные интерфейсы и драйверы аппаратных средств. К примеру, протоколом уровня доступа к сети являются протоколы Ethernet. Их суть в следующем:

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

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

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

Следует обратить внимание, что когда мы говорим Интернет — сеть, то это также верно, как и то, что TCP/IP — протокол. То есть Интернет — это объединение сетей.

С этой точки зрения можно выделить два вида компьютеров, которые можно выделить в сети:

Это хост-компьютеры (host) и шлюзы (gate). В двух словах покажем, что есть что. Реально каждый из компьютеров, которые работают в сети, может классифицироваться по двум признакам: в компьютере расположена только одна сетевая карта или интерфейс (это хост-компьютер) и обычно он принадлежит какой-нибудь одной сети; в компьютере находится две и более сетевых карты, при этом каждая из карт подключается к своей сети (это компьютеры-шлюзы). Соответственно, через шлюзы можно объединять сети.

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

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

Класс А.

Первый байт кодирует номер сети, при этом его старший бит является нулевым (это признак класса А), остальные биты определяют номер сети. Сетей класса А может быть 126 штук. Соответственно, последние три байта — номер компьютера в сети. Сети класса А — гигантские сети, которые могут принадлежать крупнейшим корпорациям.

Класс B.

Признак класса B — старшие два бита равны “10”. Для нумерации сети используется остаток первого и целиком второй байт. 3 и 4 байты — номер компьютера в сети. Это также большие сети, их может быть большое количество, но также ограниченное.

Класс C.

Признак класс C — старшие три бита равны “110”. Для нумерации сети используются: остаток первого байта, второй и третий байты целиком. Номер компьютера определяется четвертым байтом. Соответственно, класс C представляет большой набор небольших сетей.

Есть еще два класса — класс D и Е, но они достаточно специфичны, и мы не будем о них говорить.

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

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

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

Следующие протоколы — транспортные. Здесь присутствует два типа протоколов — UDP и TCP.

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

Протокол UDP — это быстрая доставка сообщений без осуществления контроля доставки.

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

Далее идет уровень прикладных систем. TCP/IP обладает тем свойством, что в семействе этих протоколов стандартизованы протоколы, на которых базируются прикладные системы. В частности, FTP (file transfer protocol). Реально система FTP присутствует в каждой системе. Но за счет того, что имеется стандарт FTP, все эти приложения работают единообразно. Есть сетевой продукт Telnet — сетевая эмуляция алфавитно-цифрового терминала.

То есть в системе стандартизованы протоколы с помощью которых организованы прикладные системы. И мы можем строить свои приложения FTP или Telnet из предоставленных кирпичиков.

Далее, разные прикладные системы общаются с разными протоколами — кто-то с UDP, кто-то с TCP. FTP и Telnet, например, работают через TCP, а сетевая файловая система NFS, которая позволяет объединять файловые системы разных машин в одну (и видеть их, как свою локальную), основывается на UDP.

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