РАЗДЕЛ 12. Принципы создания параллельных взаимодействующих процессов

Тема 12.1. Задачи параллельных взаимодействующих процессов

Взаимодействующие процессы

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

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

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

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

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

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

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

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

Категории средств обмена информацией

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

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

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

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

                 

 Логическая организация механизма передачи информации

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

Как устанавливается связь?

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

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

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

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

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

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

Информационная валентность процессов и средств связи

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

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

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

Особенности передачи информации с помощью линий связи

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

Буферизация

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

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

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

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

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

Поток ввода/вывода и сообщения

Существует две модели передачи данных по каналам связи – поток ввода-вывода и сообщения. При передаче данных с помощью потоковой модели операции передачи/приема информации вообще не интересуются содержимым данных. Процесс, прочитавший 100 байт из линии связи, не знает и не может знать, были ли они переданы одновременно, т. е. одним куском или порциями по 20 байт, пришли они от одного процесса или от разных. Данные представляют собой простой поток байтов, без какой-либо их интерпретации со стороны системы. Примерами потоковых каналов связи могут служить pipe и FIFO, описанные ниже.

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

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

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

Как завершается связь?

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

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

Нити исполнения

Рассмотренные выше аспекты логической реализации относятся к средствам связи, ориентированным на организацию взаимодействия различных процессов. Однако усилия, направленные на ускорение решения задач в рамках классических операционных систем, привели к появлению совершенно иных механизмов, к изменению самого понятия "процесс".

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

Ввести массив a

Ввести массив b

Ввести массив c

a = a + b

c = a + c

Вывести массив c

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

Ввести массив a  

Ожидание окончания операции ввода               

Ввести массив b  

Ожидание окончания операции ввода               

Ввести массив с  

Ожидание окончания операции ввода               a = a + b

c = a + c

Вывести массив с                   

Ожидание окончания операции вывода

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

  Процесс 1                        Процесс 2

Ввести массив a                     Ожидание ввода

Ожидание окончания                  массивов a и b

 операции ввода

Ввести массив b

Ожидание окончания

 операции ввода

Ввести массив с

Ожидание окончания                  a = a + b

 операции ввода

c = a + c

Вывести массив с

Ожидание окончания

 операции вывода

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

Процесс 1                          Процесс 2

Создать процесс 2

               Переключение контекста

                                  Выделение общей

                                  памяти

                                  Ожидание ввода

                              a и b

              Переключение контекста

Выделение общей памяти

Ввести массив a

Ожидание окончания

 операции ввода

Ввести массив b

Ожидание окончания

 операции ввода

Ввести массив с

Ожидание окончания

 операции ввода

               Переключение контекста

                                   a = a + b

               Переключение контекста

c = a + c

Вывести массив с

Ожидание окончания

 операции вывода

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

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

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

Нить 1                      Нить 2

Создать нить 2                                                                               

       Переключение контекста нитей                   

                         Ожидание ввода a и b

           Переключение контекста нитей

Ввести массив a                      

Ожидание окончания

 операции ввода

Ввести массив b

Ожидание окончания

 операции ввода

Ввести массив с

Ожидание окончания

 операции ввода

           Переключение контекста нитей

                             a = a + b

           Переключение контекста нитей

c = a + c                    

Вывести массив с                   

Ожидание окончания

 операции вывода                  

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

Цели и средства синхронизации.

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

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

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

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

Тема 12.2. Реализация параллельных взаимодействующих процессов

Критические секции

В отличие от других объектов синхронизации, критические секции работают в пользовательском режиме, за исключением случаев, когда требуется переход в режим ядра. Если поток пытается выполнить код, который может быть критической секцией, он сначала выполняет циклическую блокировку и после заданного количества времени переходит в режим ядра, чтобы ждать критическую секцию. Фактически, критическая секция состоит из счетчика цикла и семафора; счетчик цикла предназначен для ожидания в пользовательском режиме, и семафор предназначен для ожидания в режиме ядра (режим ожидания). В Win32 API есть структура CRITICAL_SECTION, которая представляет объекты критической секции. В MFC есть класс CCriticalSection. В принципе, критическая секция - это часть исходного кода, требующая интегрированного выполнения, то есть выполнение этой части кода не должно прерываться никаким другим потоком. Такие части кода могут требоваться в случаях, когда необходимо предоставить одному потоку монополию на использование общего ресурса. Простой случай – использование глобальных переменных более чем одним потоком. Например:

int g_nVariable = 0;


UINT Thread_First(LPVOID pParam)
{
        if (g_nVariable < 100)
        {
          ...
        }
         return 0;
}

UINT Thread_Second(LPVOID pParam)
{
        g_nVariable += 50;

    ...
        return 0;
}

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

CCriticalSection g_cs;


int g_nVariable = 0;
UINT Thread_First(LPVOID pParam)
{
         g_cs.Lock();
        if (g_nVariable < 100)
        {
          ...
        }
         g_cs.Unlock();
        return 0;
}
UINT Thread_Second(LPVOID pParam)

{
        g_cs.Lock();
        g_nVariable += 20;
   g_cs.Unlock();
        ...

        return 0;
}

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

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

Можно внедрять критические секции в классы C++ , таким образом, делая их ориентированными на многопоточное исполнение. Это может потребоваться, когда объекты определенного класса должны использоваться более чем одним потоком одновременно. Выглядит это примерно так:

class CSomeClass
{
        CCriticalSection m_cs;
        int m_nData1;
        int m_nData2;
public:

        void SetData(int nData1, int nData2)
        {
           m_cs.Lock();
           m_nData1 = Function(nData1);
            m_nData2 = Function(nData2);
            m_cs.Unlock();
        }
   int GetResult()
        {
           m_cs.Lock();
           int nResult = Function(m_nData1, m_nData2);
           m_cs.Unlock();
           return nResult;
        }
};

Возможно, что в один и тот же момент два или более потока вызовут методы SetData и/или GetData для одного и того же объекта типа CSomeClass. Следовательно, путем заключения в оболочку (обертывания) содержимого тех методов мы предотвращаем искажение данных во время вызовов тех методов.

Программные алгоритмы организации взаимодействия процессов

Требования, предъявляемые к алгоритмам

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

1.Задача должна быть решена чисто программным способом на обычной машине, не имеющей специальных команд взаимоисключения. При этом предполагается, что основные инструкции языка программирования (такие примитивные инструкции, как load, store, test) являются атомарными операциями.

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

3.Если процесс Pi исполняется в своем критическом участке, то не существует никаких других процессов, которые исполняются в соответствующих критических секциях. Это условие получило название условия взаимоисключения (mutual exclusion).

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

5.Не должно возникать неограниченно долгого ожидания для входа одного из процессов в свой критический участок. От того момента, когда процесс запросил разрешение на вход в критическую секцию, и до того момента, когда он это разрешение получил, другие процессы могут пройти через свои критические участки лишь ограниченное число раз. Это условие получило название условия ограниченного ожидания (bound waiting).

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

Запрет прерываний

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

while (some condition) {

  запретить все прерывания

     critical section

  разрешить все прерывания

     remainder section

}

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

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

Переменная-замок

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

shared int lock = 0;

/* shared означает, что */

/* переменная является разделяемой */

while (some condition) {

  while(lock); lock = 1;

         critical section

  lock = 0;

         remainder section

}

К сожалению, при внимательном рассмотрении мы видим, что такое решение не удовлетворяет условию взаимоисключения, так как действие while(lock); lock = 1; не является атомарным. Допустим, процесс P0 протестировал значение переменной lock и принял решение двигаться дальше. В этот момент, еще до присвоения переменной lock значения 1, планировщик передал управление процессу P1. Он тоже изучает содержимое переменной lock и тоже принимает решение войти в критический участок. Мы получаем два процесса, одновременно выполняющих свои критические секции.

Строгое чередование

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

shared int turn = 0;

while (some condition) {

  while(turn != i);

     critical section

  turn = 1-i;

     remainder section

}

Очевидно, что взаимоисключение гарантируется, процессы входят в критическую секцию строго по очереди: P0, P1, P0, P1, P0, ... Но наш алгоритм не удовлетворяет условию прогресса. Например, если значение turn равно 1, и процесс P0 готов войти в критический участок, он не может сделать этого, даже если процесс P1 находится в remainder section.

Флаги готовности

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

shared int ready[2] = {0, 0};

Когда i-й процесс готов войти в критическую секцию, он присваивает элементу массива ready[i] значение равное 1. После выхода из критической секции он, естественно, сбрасывает это значение в 0. Процесс не входит в критическую секцию, если другой процесс уже готов к входу в критическую секцию или находится в ней.

while (some condition) {

  ready[i] = 1;

  while(ready[1-i]);

     critical section

  ready[i] = 0;

     remainder section

}

Полученный алгоритм обеспечивает взаимоисключение, позволяет процессу, готовому к входу в критический участок, войти в него сразу после завершения эпилога в другом процессе, но все равно нарушает условие прогресса. Пусть процессы практически одновременно подошли к выполнению пролога. После выполнения присваивания ready[0]=1 планировщик передал процессор от процесса 0 процессу 1, который также выполнил присваивание ready[1]=1. После этого оба процесса бесконечно долго ждут друг друга на входе в критическую секцию. Возникает ситуация, которую принято называть тупиковой (deadlock).

Алгоритм Петерсона

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

shared int ready[2] = {0, 0};

shared int turn;

while (some condition) {

  ready[i] = 1;

  turn =1-i;

  while(ready[1-i] && turn == 1-i);

         critical section

  ready[i] = 0;

     remainder section

}

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

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

Удовлетворение требований 1 и 2 очевидно.

Докажем выполнение условия взаимоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций. Заметим, что процесс Pi может войти в критическую секцию, только если ready[1-i] == 0 или turn == i. Заметим также, что если оба процесса выполняют свои критические секции одновременно, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, значения переменных измениться не могут). Пусть процесс P0 первым вошел в критический участок, тогда процесс P1 должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;). Однако после этого он не может выйти из цикла до окончания критического участка процесса P0, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.

Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P0. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P1 не готов к выполнению критического участка, то ready[1] == 0, и процесс P0 может осуществить вход. Если процесс P1 готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу P0 либо процессу P1 начать выполнение критической секции. Если процесс P1 завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P0 приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.

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

Алгоритм булочной (Bakery algorithm)

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

shared enum {false, true} choosing[n];

shared int number[n];

Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения

(a,b) < (c,d), если a < c

или если a == c и b < d

max(a0, a1, ...., an) – это число k такое, что

k >= ai для всех i = 0, ...,n

Структура процесса Pi для алгоритма булочной приведена ниже

while (some condition) {

  choosing[i] = true;

  number[i] = max(number[0], ...,

                  number[n-1]) + 1;

  choosing[i] = false;

  for(j = 0; j < n; j++){

     while(choosing[j]);

     while(number[j] != 0 && (number[j],j) <

        (number[i],i));

  }

     critical section

  number[i] = 0;

     remainder section

}

Аппаратная поддержка взаимоисключений

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

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

Команда Test-and-Set (проверить и присвоить 1)                                                            

О выполнении команды Test-and-Set, осуществляющей проверку значения логической переменной с одновременной установкой ее значения в 1, можно думать как о выполнении функции

int Test_and_Set (int *target){

  int tmp = *target;

  *target = 1;

  return tmp;

}

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

shared int lock = 0;

while (some condition) {

  while(Test_and_Set(&lock));

     critical section

  lock = 0;

     remainder section

}

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

Команда Swap (обменять значения)

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

void Swap (int *a, int *b){

  int tmp = *a;

  *a = *b;

  *b = tmp;

}

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

shared int lock = 0;

int key;

while (some condition) {

  key = 1;

  do Swap(&lock,&key);

  while (key);

     critical section

  lock = 0;

     remainder section

}

Решение проблемы производитель-потребитель с помощью семафоров

Одной из типовых задач, требующих организации взаимодействия процессов, является задача producer-consumer (производитель-потребитель). Пусть два процесса обмениваются информацией через буфер ограниченного размера. Производитель закладывает информацию в буфер, а потребитель извлекает ее оттуда. Если буфер забит, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то потребитель должен дожидаться нового сообщения. Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация. Семафор empty будем использовать для организации ожидания производителя при заполненном буфере, а семафор mutex - для организации взаимоисключения на критических участках, которыми являются действия  insert_item и consume_item (операции положить информацию и взять информацию не могут пересекаться, так как тогда возникнет опасность искажения информации). Тогда решение задачи выглядит так:

Задача производителя и потребителя, решаемая

с помощью семафоров

#define N 100 /* Количество мест в буфере */

typedef int semaphore; /* Семафоры - это специальная разновидность

целочисленной переменной */

semaphore mutex =1; /* управляет доступом к критической области */

semaphore empty = N; /* подсчитывает пустые места в буфере */

semaphore full = 0; /* подсчитывает занятые места в буфере */

void producer(void)

{

int item;

while (TRUE) {

item = produce_item( )

down(&empty);

down(&mutex);

insert_itern(item);

up(&mutex);

upC&full);

               }

}

void consumer(void)

{

int item;

while (TRUE) {

down(&full);

down(&mutex);

item = remove_item(

up(&mutex);

up(&empty);

consume_itern(item);

}

}

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

Решение проблемы читателей-писателей

В задаче читателей и писателей моделируется доступ к базе данных. Представим, к примеру, систему бронирования авиабилетов, в которой есть множество соревнующихся процессов, желающих обратиться к ней по чтению и записи. Вполне допустимо наличие нескольких процессов, одновременно  считывающих информацию из базы данных, но если один процесс обновляет базу данных (проводит операцию записи), никакой другой процесс не может получить доступ к базе данных даже для чтения информации. Вопрос в том, как создать программу для читателей и писателей? Одно из решений показано ниже. В этом решении первый читатель для получения доступа к базе данных  выполняет в отношении семафора db операцию down. А все следующие читатели просто увеличивают значение счетчика гс. Как только читатели прекращают свою работу, они уменьшают значение счетчика, а последний из них выполняет в отношении семафора операцию up, позволяя заблокированному писателю, если таковой  имеется, приступить к работе. В представленном здесь решении есть одна достойная упоминания  недостаточно очевидная особенность. Допустим, что какой-то читатель уже использует базу данных, и тут появляется еще один читатель. Поскольку одновременная работа двух читателей разрешена, второй читатель допускается к базе данных. По мере появления к ней могут быть допущены и другие дополнительные читатели. Теперь допустим, что появился писатель. Он может не получить доступ к базе данных, поскольку писатели должны иметь к базе данных исключительный доступ, поэтому писатель приостанавливает свою работу Позже появляются и другие читатели. Доступ дополнительным читателям будет открыт до тех пор, пока будет активен хотя бы один читатель. Вследствие этой стратегии, пока продолжается наплыв читателей, они все будут получать доступ к базе по мере своего прибытия. Писатель будет приостановлен до тех пор, пока не останется ни одного читателя. Если новый читатель будет прибывать, скажем, каждые 2 с, и каждый читатель  затрачивает на свою работу по 5 с, писатель доступа никогда не дождется. Чтобы предотвратить такую ситуацию, программу можно слегка изменить: когда писатель находится в состоянии ожидания, то вновь прибывающий читатель не получает немедленного доступа, а приостанавливает свою работу и встает в очередь за писателем. При этом писатель должен переждать окончания работы тех читателей, которые были активны при его прибытии, и не должен пережидать тех читателей, которые прибывают уже после него. Недостаток этого решения заключается в снижении производительности за счет меньших показателей параллельности в работе.

Решение задачи читателей и писателей

typedef int semaphore;

semaphore mutex =1;

semaphore db = 1;

int гс = 0;

void reader(void)

{

while (TRUE) {

down(&mutex);

гс = гс + 1;

if (гс == 1) down(&db);

up(&mutex);

read_data_base( );

down(&mutex);

re = re - 1;

if (re == 0) up(&db);

up(&mutex);

use data readO;

}

}

void writer(void)

{

while (TRUE) {

think_up_data( );

down(&db);

write_data_base( );

up(&db);

}

}

РАЗДЕЛ 13. Особенности реализаций современных ОС

Тема 13.1. Программные интерфейсы современных операционных систем.

Системный вызов

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

Системные вызовы в общем случае защищают доступ к ресурсам, которыми управляет ядро, при этом самые большие категории системных вызовов имеют дело с вводом/выводом (open, close, read, write, poll и многие другие), процессами (fork, execve, kill и т.д.), временем (time, settimeofday и т.п.) и памятью (mmap, brk и пр.) Под это категории подпадают практически все системные вызовы.

Однако за сценой системный вызов может и не оказаться тем, чем выглядит. Во-первых, библиотека С в Linux реализует некоторые системные вызовы полностью в терминах других системных вызовов. Например, реализация waitpid сводится к простому вызову wait4, однако в документации на обе функции ссылаются как на системные вызовы. Другие, более традиционные системные вызовы, наподобие sigmask и ftime, реализованы почти полностью в библиотеке С, а не в ядре Linux.

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

Интерфейс программирования приложений

Интерфейс программирования приложений (иногда интерфейс прикладного программирования) (application programming interface, API) — набор готовых классов, процедур, функций, структур и констант, предоставляемых приложением (библиотекой, сервисом) для использования во внешних программных продуктах. Используется программистами для написания всевозможных приложений. API операционных систем. Проблемы, связанные с многообразием API

Практически все операционные системы (Unix, Windows, Mac OS, и т. д.) имеют API, с помощью которого программисты могут создавать приложения для этой операционной системы. Главный API операционных систем — это множество системных вызовов.

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

С другой стороны, отличия в API различных операционных систем существенно затрудняют перенос приложений между платформами. Существуют различные методы обхода этой сложности — написание «промежуточных» API (API графических интерфейсов Qt, Gtk, и т. п.), написание библиотек, которые отображают системные вызовы одной ОС в системные вызовы другой ОС (такие среды исполнения, как Wine, cygwin, и т. п.), введение стандартов кодирования в языках программирования (например, стандартная библиотека языка C), написания интерпретируемых языков, реализуемых на разных платформах (sh, python, perl, php, tcl, Java, и т. д.).

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

Основными сложностями существующих многоуровневых систем API являются:

Windows API (англ. application programming interfaces) — общее наименование целого набора базовых функций интерфейсов программирования приложений операционны систем семейств Windows и Windows NT корпорации «Майкрософт». Является самым прямым способом взаимодействия приложений с Windows. Для создания программ, использующих Windows API, «Майкрософт» выпускает SDK, который называется Platform SDK и содержит документацию, набор библиотек, утилит и других инструментальных средств.

Windows API был изначально спроектирован для использования в программах, написанных на языке C (или C++). Работа через Windows API — это наиболее близкий к системе способ взаимодействия с ней из прикладных программ. Более низкий уровень доступа, необходимый только для драйверов устройств, в текущих версиях Windows предоставляется через Windows Driver Model.

POSIX® (Portable Operating System Interface for Unix — Переносимый интерфейс операционных систем Unix) — набор стандартов, описывающих интерфейсы между операционной системой и прикладной программой. Стандарт создан для обеспечения совместимости различных UNIX-подобных операционных систем и переносимости прикладных программ на уровне исходного кода, но может быть использован и для не-Unix систем. Серия стандартов POSIX была разработана комитетом 1003 IEEE. Международная организация по стандартизации (ISO) совместно c Международной электротехнической комиссией (IEC) приняли данный стандарт (POSIX) под названием ISO/IEC 9945.

Базовые системные вызовы стандарта POSIX

Open - открывет файл.

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>

int open(const char *pathname, int flags);

int open(const char *pathname, int flags, mode_t mode);

int creat(const char *pathname, mode_t mode);

Вызов open() используется, чтобы преобразовать путь к файлу в описатель файла (небольшое неотрицательно целое число, которое используется с вызовами read, write и т.п. при последующем вводе-выводе). Если системный вызов завершается успешно, возвращенный файловый описатель является наименьшим описателем, который еще не открыт процессом. В результате этого вызова появляется новый открытый файл, не разделяемый никакими процессами (разделяемые открытые файлы могут возникнуть, когда посылается системный вызов fork). Новый описатель файла будет оставаться открытым при выполнении функции exec (смотри описание fcntl). Указатель устанавливается в начале файла. Параметр flags - это флаги O_RDONLY, O_WRONLY или O_RDWR, открывающие файлы "только для чтения", "только для записи" и для чтения и записи соответственно.

open возвращают новый описатель файла или -1 в случае ошибки (в этом случае

значение переменной errno устанавливается должным образом).

Close - закрыть файловый дескриптор  

#include <unistd.h>

int close(int fd);

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

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

close возвращает ноль при успешном завершении или -1, если произошла ошибка.  

Write - производит запись в описатель файла  

#include <unistd.h>

ssize_t read(int fd, void *buf, size_t count);

read() пытается записать count байтов файлового описателя fd в буфер, адрес которого начинается с buf.

Если количество count равно нулю, то read() возвращает это нулевое значение и завершает свою работу. Если count больше, чем SSIZE_MAX, то результат не может быть определен.

При успешном заешении вызова возвращается количество байтов, которые были считаны (нулевое значение означает конец файла), а позиция файла увеличивается на это значение. Если количество прочнных байтов меньше, чем количество запрошенных, то это не считается ошибкой: например, данные могли быть почти в конце файла, в канале, на терминале, или read() был прерван сигналом. В случае ошибки возвращаемое значение равно -1, а переменной errno присваивается номер ошибки. В этом случае позиция файла не определена.  

read - cчитывает данные файлового описателя  

#include <unistd.h>

ssize_t read(int fd, void *buf, size_t count);

read() пытается записать count байтов файлового описателя fd в буфер, адрес которого начинается с buf.

Если количество count равно нулю, то read() возвращает это нулевое значение и завершает свою работу. Если count больше, чем SSIZE_MAX, то результат не может быть определен.

При успешном завершении вызова возвращается количество байтов, которые были считаны (нулевое значение означает конец файла), а позиция файла увеличивается на это значение. Если количество прочитанных байтов меньше, чем количество запрошенных, то это не считается ошибкой: например, данные могли быть почти в конце файла, в канале, на терминале, или read() был прерван сигналом. В случае ошибки возвращаемое значение равно -1, а переменной errno присваивается номер ошибки. В этом случае позиция файла не определена.

Тема 13.2. ОС, как среда взаимодействующих процессов

Командные языки и командные интерпретаторы

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

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

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

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

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

Общая характеристика командных языков

В этом пункте мы будем более конкретно говорить о командных языках семейства shell. Основное назначение этих языков (их разновидностей существует достаточно много, но мы рассмотрим только три наиболее распространенные варианта - Bourne-shell, C-shell и Korn-shell) состоит в том, чтобы предоставить пользователям удобные средства взаимодействия с системой. Что это означает? Языки недаром называются командными. Они предназначены для того, чтобы дать пользователю возможность выполнять команды, предназначенные для исполнения некоторых действий операционной системы. Существует два вида команд.

Собственные команды shell (cd, echo, exec и т.д.) выполняются непосредственно интерпретатором, т.е. их семантика встроена в соответствующий язык. Имена других команд на самом деле являются именами файлов, содержащих выполняемые программы. В случае вызова такой команды интерпретатор командного языка с использованием соответствующих системных вызовов запускает параллельный процесс, в котором выполняется нужная программа. Конечно, смысл действия подобных команд является достаточно условным, поскольку зависит от конкретного наполнения внешних файлов. Тем не менее, в описании каждого языка содержатся и характеристики "внешних команд" (например, find, grep, cc и т.д.) в расчете на то, что здравомыслящие пользователи (и их администраторы) не будут изменять содержимое соответствующих файлов.

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

Очень важной особенностью семейства языков shell являются возможности перенаправления ввода/вывода и организации конвейеров команд. Естественно, эти возможности опираются на базовые средства ОС UNIX.Для каждого пользовательского процесса (а внешние команды shell выполняются в рамках отдельных пользовательских процессов) предопределены три выделенных дескриптора файлов: файла стандартного ввода (standard input), файла стандартного вывода (standard output) и файла стандартного вывода сообщений об ошибках (standard error). Хорошим стилем программирования в среде ОС UNIX является такой, при котором любая программа читает свои вводные данные из файла стандартного ввода, а выводит свои результаты и сообщения об ошибках в файлы стандартного вывода и стандартного вывода сообщений об ошибках. Поскольку любой порожденный процесс "наследует" все открытые файлы своего предка, то при программировании команды рекомендуется не задумываться об источнике вводной информации программы, а также конкретном ресурсе, поддерживающим вывод основных сообщений и сообщений об ошибках. Нужно просто пользоваться стандартными файлами, за конкретное определение которых отвечает процесс-предок.

Если вы пишете в командной строке конструкцию

com1 par1, par2, ..., parn > file_name ,

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

file_name < com1 par1, par2, ..., parn ,

то команда com1 будет использовать файл с именем file_name в качестве источника своего стандартного ввода. Если же вы пишете

com1 par1, par2, ..., parn | com2 par1, par2, ..., parm ,

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

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

ls -l | sort -r

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

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

Базовые возможности семейства командных интерпретаторов

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

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

Любая разновидность языка shell представляет собой развитый компьютерный язык.

Bourne-shell

Bourne-shell является наиболее распространенным командным языком (и одновременно командным интерпретатором) системы UNIX. Вот основные определения языка Bourne-shell:

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

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

Параметр - имя, цифра или один из символов *, @, #, ?, -, $, !.

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

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

Значение простой команды - это код ее завершения, если команда заканчивается нормально, либо 128 + код ошибки, если завершение команды не нормальное (все значения выдаются в текстовом виде).

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

Командная строка - текстовая строка на языке shell.

shell-процедура (shell-script) - файл с программой, написанной на языке shell.

Конвейер - последовательность команд, разделенных символом "|". При выполнении конвейера стандартный вывод каждой команды конвейера, кроме последней, направляется на стандартный вход следующей команды. Интерпретатор shell ожидает завершения последней команды конвейера. Код завершения последней команды считается кодом завершения всего конвейера.

Список - последовательность нескольких конвейеров, соединенных символами ";", "&", "&&", "||", и, может быть, заканчивающаяся символами ";" или "&". Разделитель между конвейерами ";" означает, что требуется последовательное выполнение конвейеров; "&" означает, что конвейеры могут выполняться параллельно. Использование в качестве разделителя символов "&&" (и "||") означает, что следующий конвейер будет выполняться только в том случае, если предыдущий конвейер завершился с кодом завершения "0" (т.е. абсолютно нормально). При организации списка символы ";" и "&" имеют одинаковые приоритеты, меньшие, чем у разделителей "&&" и "||".

В любой точке программы может быть объявлена (и установлена) переменная с помощью конструкции "имя = значение" (все значения переменных - текстовые). Использование конструкций $имя или ${имя} приводит к подстановке текущего значения переменной в соответствующее слово.

Предопределенными переменными Bourne-shell, среди прочих, являются следующие:

HOME - полное имя домашнего каталога текущего пользователя;

PATH - список имен каталогов, в которых производится поиск команды, при ее указании коротким именем;

PS1 - основное приглашение shell ко вводу команды;

и т.д.

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

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

C-shell

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

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

Механизм псевдонимов (alias) позволяет связать с именем полностью (или частично) определенную командную строку и в дальнейшем пользоваться этим именем.

Кроме того, в C-shell по сравнению с Bourne-shell существенно расширен набор предопределенных переменных, а также введены более развитые возможности вычислений (по-прежнему, все значения представляются в текстовой форме).

Korn-shell

Если C-shell является синтаксической вариацией командного языка семейства shell по направлению к языку программирования Си, то Korn-shell - это непосредственный последователь Bourne-shell.

Если не углубляться в синтаксические различия, то Korn-shell обеспечивает те же возможности, что и C-shell, включая использование протокола и псевдонимов.

Тема 13.3. Рассмотрение конкретных реализаций ОС

ИСТОРИЯ И ОБЩАЯ ХАРАКТЕРИСТИКА СЕМЕЙСТВА ОПЕРАЦИОННЫХ СИСТЕМ UNIX

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

UNIX зародился в лаборатории Bell Labs фирмы AT&T более 20 лет назад. В то время Bell Labs занималась разработкой многопользовательской системы разделения времени MULTICS (Multiplexed Information and Computing Service) совместно с MIT и General Electric, но эта система потерпела неудачу, отчасти из-за слишком амбициозных целей, не соответствовавших уровню компьютеров того времени, а отчасти и из-за того, что она разрабатывалась на языке PL/1, а компилятор PL/1 задерживался и вообще плохо работал после своего запоздалого появления. Поэтому Bell Labs вообще отказалась от участия в проекте MULTICS, что дало возможность одному из ее исследователей, Кену Томпсону, заняться поисковой работой в направлении улучшения операционной среды Bell Labs. Томпсон, а также сотрудник Bell Labs Денис Ритчи и некоторые другие разрабатывали новую файловую систему, многие черты которой вели свое происхождение от MULTICS. Для проверки новой файловой системы Томпсон написал ядро ОС и некоторые программы для компьютера GE-645, который работал под управлением мультипрограммной системы разделения времени GECOS. У Кена Томпсона была написанная им еще во времена работы над MULTICS игра "Space Travel" - "Космическое путешествие". Он запускал ее на компьютере GE-645, но она работала на нем не очень хорошо из-за невысокой эффективности разделения времени. Кроме этого, машинное время GE-645 стоило слишком дорого. В результате Томпсон и Ритчи решили перенести игру на стоящую в углу без дела машину PDP-7 фирмы DEC, имеющую 4096 18-битных слов, телетайп и хороший графический дисплей. Но у PDP-7 было неважное программное обеспечение, и, закончив перенос игры, Томпсон решил реализовать на PDP-7 ту файловую систему, над который он работал на GE-645. Из этой работы и возникла первая версия UNIX, хотя она и не имела в то время никакого названия. Но она уже включала характерную для UNIX файловую систему, основанную на индексных дескрипторах inode, имела подсистему управления процессами и памятью, а также позволяла двум пользователям работать в режиме разделения времени. Система была написана на ассемблере. Имя UNIX (Uniplex Information and Computing Services) было дано ей еще одним сотрудником Bell Labs, Брайаном Керниганом, который первоначально назвал ее UNICS, подчеркивая ее отличие от многопользовательской MULTICS. Вскоре UNICS начали называть UNIX.Первыми пользователями UNIX'а стали сотрудники отдела патентов Bell Labs, которые нашли ее удобной средой для создания текстов.

Большое влияние на судьбу UNIX оказала перепись ее на языке высокого уровня С, разработанного Денисом Ритчи специально для этих целей. Это произошло в 1973 году, UNIX насчитывал к этому времени уже 25 инсталляций, и в Bell Labs была создана специальная группа поддержки UNIX. Широкое распространение UNIX получил с 1974 года, после описания этой системы Томпсоном и Ритчи в компьютерном журнале CACM. UNIX получил широкое распространение в университетах, так как для них он поставлялся бесплатно вместе с исходными кодами на С. Широкое распространение эффективных C-компиляторов сделало UNIX уникальной для того времени ОС из-за возможности переноса на различные компьютеры. Университеты внесли значительный вклад в улучшение UNIX и дальнейшую его популяризацию. Еще одним шагом на пути получения признания UNIX как стандартизованной среды стала разработка Денисом Ритчи библиотеки ввода-вывода stdio. Благодаря использованию этой библиотеки для компилятора С, программы для UNIX стали легко переносимыми.

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

Наибольшее распространение получили две весьма несовместимые линии версий UNIX: линия AT&T - UNIX System V, и линия университета Berkeley-BSD. Многие фирмы на основе этих версий разработали и поддерживают свои версии UNIX: SunOS и Solaris фирмы Sun Microsystems, UX фирмы Hewlett-Packard, XENIX фирмы Microsoft, AIX фирмы IBM, UnixWare фирмы Novell (проданный теперь компании SCO), и список этот можно еще долго продолжать. Наибольшее влияние на унификацию версий UNIX оказали такие стандарты как SVID фирмы AT&T, POSIX, созданный под эгидой IEEE, и XPG4 консорциума X/Open. В этих стандартах сформулированы требования к интерфейсу между приложениями и ОС, что дает возможность приложениям успешно работать под управлением различных версий UNIX.Независимо от версии, общими для UNIX чертами являются:

Особенности архитектуры и межпроцессного взаимодействия в OC семейства UNIX

Знакомство с архитектурой UNIX начнем с рассмотрения таких неотъемлимых для неё характеристических понятий, как стандартизация и многозадачность:

Стандартизация

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

Многозадачность

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

Файлы и процессы

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

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

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

Взгляд на архитектуру UNIX

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

Рис.13.3.1 Архитектура операционной системы UNIX

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

Ядро UNIX

Операционная система UNIX обладает классическим монолитным ядром в котором можно выделить следующие основные части:

Файловая подсистема

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

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

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

Драйверы устройств

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

Ядро операционной системы UNIX

Рис 13.3.2 Файловая система UNIX

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

Особенности файловой системы

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

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

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

Файлы и каталоги идентифицируются не по именам, а по индексным узлам (i-node) – индексам в общем массиве файлов для данной файловой системе. В этом массиве хранится информация об используемых блоках данных на носителе, а также – длина файла, владелец файла, права доступа и другая служебная информация под общим названием «метаданные о файле». Логические же связки типа «имя–i-node» – есть ни что иное как содержимое каталогов.

Таким образом, каждый файл характеризуется одним i-node, но может быть связан с несколькими именами – в UNIX это называют жёсткими ссылками . При этом, удаление файла происходит тогда, когда удаляется последняя жёсткая ссылка на этот файл.

Рис 13.3.3 Пример жесткой ссылки

Рис 13.3.4 Пример символической ссылки

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

Важной особенностью таких файловых систем является то, что имена файлов зависят от регистра, другими словами файлы test.txt и TEST.txt отличаются (т.е. являются разными строками в файле директории).

В определенных (фиксированных для данной файловой системы) блоках физического носителя данных находится т.н. суперблок. Суперблок – это наиболее ответственная область файловой системы, содержащая информацию для работы файловой системы в целом, а также – для ёе идентификации. В суперблоке находится «магическое число» – идентификатор файловой системы, отличающий её от других файловых систем, список свободных блоков, список свободных i-node'ов и некоторая другая служебная информация.

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

Специальный файл устройства

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

Именованный канал

        Используется для передачи данных между процессами, работает по принципу         двунаправленной очереди (FIFO). Является         одним из способов обмена между         изолированными процессами         

Символическая ссылка

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

        

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

Сокет

        Предназначен для взаимодействия между процессами через специальное API, схожее с TCP/IP-сокетеми.         

Такие файловые системы наследуют особенности оригинального UNIX. К ним можно отнести, например: s5 (используемая в версиях UNIX System V), ufs (BSD UNIX), ext2, ext3, reiserfs (Linux), qnxfs (QNX). Все эти файловые системы различаются форматами внутренних структур, но совместимы с точки зрения основных концепций.

Дерево каталогов

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

Файловая подсистема операционной системы UNIX имеет имеет уникальную систему обработки запросов к файлам – переключатель файловых систем или виртуальная файловая система (VFS). VFS предоставляет пользователю стандартный набор функций (интерфейс) для работы с файлами, вне зависимости от места их расположения и принадлежности к разным файловым системам.

В мире стандартов UNIX определено, что корневой каталог единого дерева файловой системы должен иметь имя /, как и символ-разделитель при формировании полного имени файла. Тогда полное имя файла может быть, например, /usr/share/doc/bzip2/README. Задача VFS – по полному имени файла найти его местоположение в дереве файловой системы, определить её тип в этом месте дерева и «переключить», т.е. передать файл на дальнейшую обработку драйверу конктретной файловой системы. Такой подход позволяет использовать практически неограниченое количество различных файловых систем на одном компьютере под управлением одной операционной системы, а пользователь даже не будет знать, что файлы физически находятся на разных носителях информации.

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

Рис 13.3.5 Стандартные каталоги в файловой системе UNIX

Приведем краткое описание основных каталогов системы, формально описываемых специальным стандартом на иерархию файловой системы (Filesystem Hierarchy Standart). Все каталоги можно разделить на две группы: для статической (редко меняющейся) информации – /bin, /usr и динамической (часто меняющейся) информации – /var, /tmp. Исходя из этого администраторы могут разместить каждый из этих каталогов на собственном носителе, обладающем соответствующими характеристиками.

Корневой каталог

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

/bin

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

/boot

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

/dev

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

/etc

        В этом каталоге находятся системные         конфигурационные файлы. В качестве         примеров можно привести файлы /etc/fstab,         содержащий список монтируемых файловых         систем, и /etc/resolv.conf,         который задаёт правила составления         локальных DNS-запросов. Среди наиболее         важных файлов – скрипты инифиализации         и деинициализации системы. В системах,         наследующих особенности UNIX System V, для         них отведены каталоги с /etc/rc0.d         по /etc/rc6.d         и общий для всех файл описания –         /etc/inittab.                 

/home (необязательно)

        Директория содержит домашние директории         пользователей. Её существование в         корневом каталоге не обязательно и её         содержимое зависит от особенностей         конкретной UNIX-подобной операционной         системы.

/lib

        Каталог для статических и динамических         библиотек, необходимых для запуска         программ, находящихся в директориях         /bin         и /sbin.                 

/mnt

        Стандартный каталог для временного         монтирования файловых систем –         например, гибких и флэш-дисков,         компакт-дисков и т.п..

/root (необязательно)

        Директория содержит домашюю директорию         суперпользователя. Её существование         в корневом каталоге не обязательно.

/sbin

        В этом каталоге находятся команды и         утилиты для системного администратора.         Примерами таких команд являются: route,         halt, init и т.п.. Для         аналогичных целей применяются директории         /usr/sbin         и /usr/local/sbin.                 

/usr

        Эта директория повторяет структуру         корневой директории – содержит         каталоги /usr/bin,         /usr/lib,         /usr/sbin,         служащие для аналогичных целей.         

        

Каталог /usr/include         содержит заголовочные файлы языка C         для всевозможные библиотек, расположенных         в системе.         

        

Каталог /usr/local         является следующим уровнем повторения         корневого каталога и служит для хранения         программ, установленных администратором         в дополнение к стандартной поставке         операционной системы.         

        

Каталог /usr/share         хранит неизменяющиеся данные для         установленных программ. Особый интерес         представляет каталог /usr/share/doc,         в который добавляется документация ко         всем установленным программам.         

/var, /tmp

        Используются для хранения временных         данных процессов – системных и         пользовательских соответственно.

Контекст процесса

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

Статическая часть контекста процесса системного уровня включает следующее:

Идентификатор процесса (PID)

        Уникальный номер, идентифицирующий         процесс. По сути, это номер строки в         таблице процессов – специальной         внутренней структуре ядра операционной         системы, хранящей информацию о процессах.

        

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

Идентификатор родительского процесса (PPID)

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

        

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

Состояние процесса

Каждый процесс может находиться в одном из возможных состояний: инициализация, исполнение, приостановка, ожидание ввода-вывода, завершение

Рис 13.3.6 Состояния процесса в UNIX

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

Идентификаторы пользователя

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

Приоритет процесса

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

Таблица дескрипторов открытых файлов

        Список структур ядра, описывающий все         файлы, открытые этим процессом для         ввода-вывода.

Другая информация, связанная с процессом

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

Windows NT

Windows NT (в просторечии просто NT) — линейка операционных систем (ОС) производства корпорации Microsoft и название первых версий ОС.

Windows NT была разработана «с нуля», развивалась отдельно от других ОС семейства Windows (Windows 3.x и Windows 9x) и, в отличие от них, позиционировалась как надёжное решение для рабочих станций (Windows NT Workstation) и серверов (Windows NT Server). Windows NT дала начало семейству операционных систем, в которое входят Windows 2000, Windows XP, Windows Server 2003, Windows Vista, Windows Server 2008, Windows 7.

Нужно отметить, что в качестве программных интерфейсов ОС NT изначально планировались API OS/2 и затем POSIX, поддержка Windows API была добавлена в последнюю очередь. Кроме того, в качестве аппаратной платформы для NT изначально планировались Intel i860 и затем MIPS, поддержка Intel x86 также была добавлена позднее. Затем, в процессе эволюции этой ОС, исчезла поддержка обоих изначально запланированных программных интерфейсов и обеих изначально запланированных аппаратных платформ. Для i860 даже не было ни одной релизной версии этой ОС, хотя именно от кодового названия этого процессора, N10, происходит название самой ОС NT. Ныне Microsoft расшифровывает абревиатуру NT как New Technology. А в качестве альтернативы POSIX-подсистеме Microsoft стала предлагать пакет Сервисы Microsoft Windows для UNIX.

Для прикладных программ системой Windows NT предоставляется несколько наборов API. Самый основной из них — так называемый «родной» API (NT Native API), реализованный в динамически подключаемой библиотеке ntdll и состоящий из двух частей: системные вызовы ядра NT (функции с префиксами Nt и Zw, передающие выполнение функциям ядра ntoskrnl с теми же названиями) и функции, реализованные в пользовательском режиме (с префиксом Rtl). Часть функций второй группы используют внутри себя системные вызовы; остальные целиком состоят из непривилегированного кода, и могут вызываться не только из кода пользовательского режима, но и из драйверов. Кроме функций Native API, в ntdll также включены функции стандартной библиотеки языка Си.

В отличие от большинства «свободных» Unix-подобных ОС, Windows NT сертифицирована институтом NIST на совместимость со стандартом POSIX.1, и даже с более строгим стандартом FIPS 151-2. Библиотекой psxdll экспортируются стандартные функции POSIX, а также некоторые функции Native API, не имеющие аналогов в POSIX — например, для работы с кучей, со структурными исключениями, с кодировкой Unicode. Внутри этих функций используются как Native API, так и LPC-вызовы в подсистему psxss, являющуюся обычным Win32-процессом. Для загрузки этой подсистемы и выполнения POSIX-программы используется консольная программа-оболочка posix. Поддержка POSIX, включённая в Windows NT, не содержит расширений для работы с графикой или многопоточными приложениями.

РАЗДЕЛ 14. Форматы исполняемых файлов и загрузка программ

Тема 14.1. Форматы исполняемых файлов

Исполняемый файл (executable file) - это файл, который может быть загружен в память загрузчиком операционной системы и затем исполнен. В операционной системе Windows исполняемые файлы, как правило, имеют расширения ".exe" и ".dll". Расширение ".exe" имеют программы, которые могут быть непосредственно запущены пользователем. Расширение ".dll" имеют так называемые динамически связываемые библиотеки (dynamic link libraries). Эти библиотеки экспортируют функции, используемые другими программами.

Для того чтобы загрузчик операционной системы мог правильно загрузить исполняемый файл в память, содержимое этого файла должно соответствовать принятому в данной операционной системе формату исполняемых файлов. В разных операционных системах в разное время существовало и до сих пор существует множество различных форматов. рассмотрим формат Portable Executable (PE). Формат PE - это основной формат для хранения исполняемых файлов в операционной системе Windows. Сборки .NET тоже хранятся в этом формате.

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

Управление памятью в Windows

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

Управление памятью в Windows NT/2k/XP/2k3 осуществляет менеджер виртуальной памяти (virtual-memory manager). Он использует страничную схему управления памятью, при которой вся физическая память делится на одинаковые отрезки размером в 4096 байт, называемые физическими страницами. Если физических страниц не хватает для работы системы, редко используемые страницы могут вытесняться на жесткий диск, в один или несколько файлов подкачки (pagefiles). Вытесненные страницы затем могут быть загружены обратно в память, если возникнет необходимость. Таким образом, программы могут использовать значительно большее количество памяти, чем реально присутствует в системе.

Виртуальное адресное пространство процесса
Каждый процесс в Windows запускается в своем виртуальном адресном пространстве размером в 4 Гб. При этом первые 2 Гб адресного пространства могут непосредственно использоваться процессом, а остальные 2 Гб резервируются операционной системой для своих нужд .

Рис 14.1.1 Виртуальное адресное пространство процесса

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

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

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

Рис 14.1.2 Перевод виртуального адреса в физический адрес

Рассмотрим на примере, как осуществляется перевод некоторого виртуального адреса vx в физический адрес px. Сначала вычисляется номер vnum виртуальной страницы, соответствующий виртуальному адресу vx, а также смещение delta виртуального адреса относительно начала этой виртуальной страницы:

vnum := vx div 4096;

delta := vx mod 4096;

Далее возможны три варианта развития событий:

  1. Виртуальная страница vnum         недоступна. В этом случае перевод         виртуального адреса vx в физический         адрес невозможен, и процесс завершается         с сообщением "Access Violation";
  2. Виртуальная страница находится в файле         страничной подкачки, и ее надо сначала         загрузить в память. Тогда пусть pnum будет         номером физической страницы, в которую         мы загружаем нашу виртуальную страницу;
  3. Виртуальная страница уже находится в         памяти, и ей соответствует некоторая         физическая страница. В этом случае pnum         - номер этой физической страницы.

После чего адрес px вычисляется следующим образом:

px := pnum*4096 + delta;

Такая организация памяти процесса обладает следующими свойствами:

Отображаемые в память файлы

Отображаемые в память файлы (memory-mapped files) - это мощная возможность операционной системы. Она позволяет приложениям осуществлять доступ к файлам на диске тем же самым способом, каким осуществляется доступ к динамической памяти, то есть через указатели. Смысл отображения файла в память заключается в том, что содержимое файла (или часть содержимого) отображается в некоторый диапазон виртуального адресного пространства процесса, после чего обращение по какому-либо адресу из этого диапазона означает обращение к файлу на диске. Естественно, не каждое обращение к отображенному в память файлу вызывает операцию чтения/записи. Менеджер виртуальной памяти кэширует обращения к диску и тем самым обеспечивает высокую эффективность работы с отображенными файлами.

Обзор структуры PE-файла

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

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

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

Рис 14.1.3 PE-файл на диске и в оперативной памяти

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

Секции

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

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

Каждая секция имеет имя. Оно не используется загрузчиком и предназначено главным образом для удобства человека. Разные компиляторы и компоновщики дают секциям различные имена. Например, компоновщик от Microsoft размещает код в секции ".text", константы - в секции ".rdata", таблицы импорта и экспорта - в секциях ".idata" и ".edata", таблицу релокаций - в секции ".reloc", ресурсы - в секции ".rsrc". В то же время компоновщик фирмы Borland использует имена "CODE" для секций, содержащих код, и "DATA" для секций с данными.

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

Выбор базового адреса образа PE-файла в памяти

Давайте обсудим, каким образом загрузчик определяет базовый адрес, по которому нужно загрузить PE-файл. Для exe-файлов это тривиальная задача: в заголовках файла присутствует поле ImageBase, содержащее значение базового адреса. Так как для выполнения exe-файла создается отдельный процесс со своим виртуальным адресным пространством, то обычно не возникает никаких проблем с тем чтобы отобразить файл в это адресное пространство по заданному адресу. Как правило, все exe-файлы содержат в поле ImageBase значение 0x400000.

А вот выбор базового адреса для dll-файла куда сложнее. Дело в том, что динамическая библиотека, как правило, загружается в адресное пространство уже существующего процесса, и хотя dll-файл тоже содержит некоторое значение в поле ImageBase, очень часто может так получиться, что этот адрес уже занят чем-то другим (например, по нему уже загружена другая динамическая библиотека). Что же делать загрузчику, если он не может загрузить dll-файл по заданному адресу? Ему ничего не остается, как загрузить этот файл по какому-то другому адресу. Но тут возникает новая проблема - в файле могут содержаться инструкции с абсолютными адресами (это, в основном, инструкции абсолютных переходов, инструкции вызова подпрограмм, а также инструкции для работы с глобальными данными). При загрузке динамической библиотеки по другому адресу все адреса, содержащиеся в этих инструкциях, становятся неправильными, и загрузчик вынужден их поправить. Для того, чтобы загрузчик мог это сделать, в файле содержится таблица релокаций, в которой прописаны RVA всех абсолютных адресов.

Импорт функций

В PE-файле существует специальная секция ".idata", описывающая функции, который этот файл импортирует из динамических библиотек. Описание импортируемых функций в секции ".idata" приводит к тому, что библиотеки загружаются загрузчиком операционной системы еще до запуска программы. В принципе, необязательно описывать каждую импортируемую функцию в этой секции, так как динамические библиотеки можно загружать с помощью функции LoadLibrary из Win32 API прямо во время выполнения программы.

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

Секция ".idata" в сборках .NET в некотором смысле носит вспомогательный характер, так как импортируемые сборкой динамические библиотеки описываются в метаданных. Задача этой секции - обеспечить запуск среды выполнения .NET, поэтому в ней описывается только одна импортируемая из mscoree.dll функция (_CorExeMain для exe-файлов и _CorDllMain - для dll-файлов). При запуске сборки .NET управление сразу же передается этой функции, которая запускает Common Language Runtime, осуществляющий JIT-компиляцию программы и контролирующий в дальнейшем ее выполнение.

Экспорт функций

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

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

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

Форматы Linear eXecutable и ELF

Linear eXecutable (LX) - 32-битный формат исполняемого файла, появившийся в OS/2 2.0. Может быть идентифицирован по сигнатуре "LX" (ASCII).

Linear Executable (LE) - Смешанный 16/32-битный формат исполняемого файла, появившийся в OS/2 2.0. Может быть идентифицирован по сигнатуре "LE" (ASCII). Не используется в настоящее время в OS/2, но использовался для драйверов VxD под Windows 3.x и Windows 9x.

ELF ( Executable and Linkable Format — формат исполняемых и компонуемых файлов) — формат файлов, используемый во многих UNIX-подобных операционных системах, например, в GNU/Linux и Solaris

Общее устройство.

Формат ELF был разработан и представлен Лабораторией Юникс (UNIX System Laboratories), как часть интерфейса ABI (Application Binary Interface - ABI). Затем он был выбран в качестве основного файлового формата для работы машин с 32-битным процессором. Elf достаточно быстро набрал популярность и в настоящее время успешно работает и на 64-битных процессорах. Он является основным файловым форматом во всех Unix и Unix-подобных операционных системах, при этом постепенно «захватывая» мобильные платформы.

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

Общую структуру elf файла можно изобразить следующим образом:

Рис 14.1.4 Структура ELF файла

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

• elf-заголовка (Elf header), в котором указаны общие характеристики файла: тип файла, его версия, адрес загрузки и прочие;

• таблицы программных заголовков (Program header table), которая служит для описания сегментов файла;

• таблицы заголовков секций (Section header table), которая, как несложно догадаться, характеризует секции файла.

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

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

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

Тема 14.2. Загрузка исполняемых файлов

Понятие динамически подключаемых библиотек.

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

Для того чтобы библиотеки можно было отличить от самостоятельно выполняемых приложений, они имеют расширение .dll. Программы, написанные на Object Pascal, могут использовать библиотеки, написанные на других языках. С другой стороны, приложения Windows могут использовать библиотеки, написанные на Object Pascal.

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

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

Преимущества использования динамических библиотек (по сравнению со статическим подключением подпрограмм на этапе сборки приложения) следующие:

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

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

3 Библиотеки обеспечивают также послепродажную поддержку (after-market support). Например, дисплейный драйвер, предоставляемый библиотекой, может быть обновлен для того, чтобы поддерживать дисплей, который не существовал в момент продажи приложения.

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

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

Связывание исполняемого файла с библиотекой DLL

Исполняемый файл связывает (или загружает) библиотеку DLL одним из двух способов:

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

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

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

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

Неявное связывание

Для неявного связывания с библиотекой DLL в исполняемых файлах необходимо использовать следующие компоненты, предоставляемые поставщиком библиотеки DLL:

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

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

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

Явное связывание

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

РАЗДЕЛ 15. Модель сетевых интерфейсов и поддержка сетевых служб в ОС

Тема 15.1. Концепции распределённой обработки

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

По-другому обстоит дело с вычислительными сетями.

Для чего компьютеры объединяют в сети

Для чего вообще потребовалось объединять компьютеры в сети? Что привело к появлению сетей?

Сетевые и распределенные операционные системы

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

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

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

Изучение строения распределенных операционных систем не входит в задачи нашего курса. Этому вопросу посвящены другие учебные курсы – Advanced operating systems, как называют их в англоязычных странах, или «Современные операционные системы», как принято называть их в России.

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

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

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

  1. При взаимодействии локальных         процессов и процесс–отправитель         информации, и процесс-получатель         функционируют под управлением одной         и той же операционной системы. Эта же         операционная система поддерживает и         функционирование промежуточных         накопителей данных при использовании         непрямой адресации. Для организации         взаимодействия процессы пользуются         одними и теми же системными вызовами,         присущими данной операционной системе,         с одинаковыми интерфейсами. Более того,         в автономной операционной системе         передача информации от одного процесса         к другому, независимо от используемого         способа адресации, как правило (за         исключением микроядерных операционных         систем), происходит напрямую – без         участия других процессов-посредников.         Но даже и при наличии процессов-посредников         все участники передачи информации         находятся под управлением одной и той         же операционной системы. При организации         сети, конечно, можно обеспечить прямую         связь между всеми вычислительными         комплексами, соединив каждый из них со         всеми остальными посредством прямых         физических линий связи или подключив         все комплексы к общей шине (по примеру         шин данных и адреса в компьютере). Однако         такая сетевая топология не всегда         возможна по ряду физических и финансовых         причин. Поэтому во многих случаях         информация между удаленными процессами         в сети передается не напрямую, а через         ряд процессов-посредников, «обитающих»         на вычислительных комплексах, не         являющихся компьютерами отправителя         и получателя и работающих под управлением         собственных операционных систем. Однако         и при отсутствии процессов-посредников         удаленные процесс-отправитель и         процесс-получатель функционируют под         управлением различных операционных         систем, часто имеющих принципиально         разное строение.
  2. Физической основой «общения» процессов         на автономной вычислительной машине         является разделяемая память. Поэтому         для локальных процессов надежность         передачи информации определяется         надежностью ее передачи по шине данных         и хранения в памяти машины, а также         корректностью работы операционной         системы. Для хороших вычислительных         комплексов и операционных систем мы         могли забыть про возможную ненадежность         средств связи. Для удаленных процессов         вопросы, связанные с надежностью         передачи данных, становятся куда более         значимыми. Протяженные сетевые линии         связи подвержены разнообразным         физическим воздействиям, приводящим         к искажению передаваемых по ним         физических сигналов (помехи в эфире)         или к полному отказу линий (мыши съели         кабель). Даже при отсутствии внешних         помех передаваемый сигнал затухает по         мере удаления от точки отправления,         приближаясь по интенсивности к внутренним         шумам линий связи. Промежуточные         вычислительные комплексы сети,         участвующие в доставке информации, не         застрахованы от повреждений или         внезапной перезагрузки операционной         системы. Поэтому вычислительные сети         должны организовываться исходя из         предпосылок ненадежности доставки         физических пакетов информации.
  3. При организации взаимодействия локальных         процессов каждый процесс (в случае         прямой адресации) и каждый промежуточный         объект для накопления данных (в случае         непрямой адресации) должны были иметь         уникальные идентификаторы – адреса –         в рамках одной операционной системы.         При организации взаимодействия удаленных         процессов участники этого взаимодействия         должны иметь уникальные адреса уже в         рамках всей сети.
  4. Физическая линия связи, соединяющая         несколько вычислительных комплексов,         является разделяемым ресурсом для всех         процессов комплексов, которые хотят         ее использовать. Если два процесса         попытаются одновременно передать         пакеты информации по одной и той же         линии, то в результате интерференции         физических сигналов, представляющих         эти пакеты, произойдет взаимное искажение         передаваемых данных. Для того чтобы         избежать возникновения такой ситуации         (race condition!) и обеспечить эффективную         совместную работу вычислительных         систем, должны выполняться условия         взаимоисключения, прогресса и         ограниченного ожидания при использовании         общей линии связи, но уже не на уровне         отдельных процессов операционных         систем, а на уровне различных вычислительных         комплексов в целом.

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

Основные вопросы логической организации передачи информации между удаленными процессами

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

  1. Как нужно соединять между         собой различные вычислительные системы         физическими линиями связи для организации         взаимодействия удаленных процессов?         Какими критериями при этом следует         пользоваться?
  2. Как избежать возникновения race condition         при передаче информации различными         вычислительными системами после их         подключения к общей линии связи? Какие         алгоритмы могут при этом применяться?
  3. Какие виды интерфейсов могут быть         предоставлены пользователю операционными         системами для передачи информации по         сети? Какие существуют модели         взаимодействия удаленных процессов?         Как процессы, работающие под управлением         различных по своему строению операционных         систем, могут общаться друг с другом?
  4. Какие существуют подходы к организации         адресации удаленных процессов? Насколько         они эффективны?         
  5. Как организуется доставка         информации от компьютера-отправителя         к компьютеру-получателю через         компьютеры-посредники? Как выбирается         маршрут для передачи данных в случае         разветвленной сетевой структуры, когда         существует не один вариант следования         пакетов данных через компьютеры-посредники?                 

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

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

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

Понятие протокола

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

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

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

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

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

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

В литературе принято говорить о локальных   вычислительных сетях   (LAN – Local Area Network) и глобальных   вычислительных сетях   (WAN – Wide Area Network). Строгого определения этим понятиям обычно не дается, а принадлежность сети к тому или иному типу часто определяется взаимным расположением вычислительных комплексов, объединенных в сеть. Так, например, в большинстве работ к локальным сетям относят сети, состоящие из компьютеров одной организации, размещенные в пределах одного или нескольких зданий, а к глобальным сетям – сети, охватывающие все компьютеры в нескольких городах и более. Зачастую вводится дополнительный термин для описания сетей промежуточного масштаба – муниципальных или городских   вычислительных сетей   (MAN – Metropolitan Area Network) – сетей, объединяющих компьютеры различных организаций в пределах одного города или одного городского района. Таким образом, упрощенно можно рассматривать глобальные сети как сети, состоящие из локальных и муниципальных сетей. А муниципальные сети, в свою очередь, могут состоять из нескольких локальных сетей. На самом деле деление сетей на локальные, глобальные и муниципальные обычно связано не столько с местоположением и принадлежностью вычислительных систем, соединенных сетью, сколько с различными подходами, применяемыми для решения поставленных вопросов в рамках той или иной сети, – с различными используемыми протоколами.

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

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

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

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

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

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

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

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

Эталоном многоуровневой схемы построения сетевых средств связи считается семиуровневая модель открытого взаимодействия систем (Open System Interconnection – OSI), предложенная Международной организацией Стандартов (International Standard Organization – ISO) и получившая сокращенное наименование OSI/ISO .

Давайте очень кратко опишем, какие функции выполняют различные уровни модели OSI/ISO [Олифер, 2001]:

Семиуровневая эталонная         модель OSI/ISO

Надо отметить, что к приведенной эталонной модели большинство практиков относится без излишнего пиетета. Эта модель не предвосхитила появления различных семейств протоколов, таких как, например, семейство протоколов TCP/IP, а наоборот, была создана под их влиянием. Ее не следует рассматривать как готовый оптимальный чертеж для создания любого сетевого средства связи. Наличие некоторой функции на определенном уровне не гарантирует, что это ее наилучшее место, некоторые функции (например, коррекция ошибок) дублируются на нескольких уровнях, да и само деление на 7 уровней носит отчасти произвольный характер. Хотя в конце концов были созданы работающие реализации этой модели, но наиболее распространенные семейства протоколов лишь до некоторой степени согласуются с ней. Как отмечено в книге [Таненбаум, 2002], она больше подходит для реализации телефонных, а не вычислительных сетей. Ценность предложенной эталонной модели заключается в том, что она показывает направление, в котором должны двигаться разработчики новых вычислительных сетей.

Проблемы адресации в сети

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

Одноуровневые адреса

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

Двухуровневые адреса

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

Удаленная адресация и разрешение адресов

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

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

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

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

Один из таких способов, используемый в Internet, получил английское наименование Domain Name Service или сокращенно DNS. Эта аббревиатура широко используется и в русскоязычной литературе. Давайте рассмотрим данный метод подробнее.

Организуем логически все компьютеры сети в некоторую древовидную структуру, напоминающую структуру директорий файловых систем, в которых отсутствует возможность организации жестких и мягких связей и нет пустых директорий. Будем рассматривать все компьютеры, входящие во Всемирную сеть, как область самого низкого ранга (аналог корневой директории в файловой системе) – ранга 0. Разобьем все множество компьютеров области на какое-то количество подобластей (domains). При этом некоторые подобласти будут состоять из одного компьютера (аналоги регулярных файлов в файловых системах), а некоторые – более чем из одного компьютера (аналоги директорий в файловых системах). Каждую подобласть будем рассматривать как область более высокого ранга. Присвоим подобластям собственные имена таким образом, чтобы в рамках разбиваемой области все они были уникальны. Повторим такое разбиение рекурсивно для каждой области более высокого ранга, которая состоит более чем из одного компьютера, несколько раз, пока при последнем разбиении в каждой подобласти не окажется ровно по одному компьютеру. Глубина рекурсии для различных областей одного ранга может быть разной, но обычно в целом ограничиваются 3 – 5 разбиениями, начиная от ранга 0.

В результате мы получим дерево, неименованной вершиной которого является область, объединяющая все компьютеры, входящие во Всемирную сеть, именованными терминальными узлами – отдельные компьютеры (точнее – подобласти, состоящие из отдельных компьютеров), а именованными нетерминальными узлами – области различных рангов. Используем полученную структуру для построения имен компьютеров, подобно тому как мы поступали при построении полных имен файлов в структуре директорий файловой системы. Только теперь, двигаясь от корневой вершины к терминальному узлу – отдельному компьютеру, будем вести запись имен подобластей справа налево и отделять имена друг от друга с помощью символа «.».

Допустим, некоторая подобласть, состоящая из одного компьютера, получила имя serv, она входит в подобласть, объединяющую все компьютеры некоторой лаборатории, с именем crec. Та, в свою очередь, входит в подобласть всех компьютеров Московского физико-технического института с именем mipt, которая включается в область ранга 1 всех компьютеров России с именем ru. Тогда имя рассматриваемого компьютера во Всемирной сети будет serv.crec.mipt.ru. Аналогичным образом можно именовать и подобласти, состоящие более чем из одного компьютера.

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

Рассмотрим теперь, как процесс на компьютере serv.crec.mipt.ru может узнать числовой адрес компьютера ssp.brown.edu. Для этого он обращается к своему DNS-серверу, отвечающему за область crec.mipt.ru, и передает ему нужный адрес в символьном виде. Если этот DNS-сервер не может сразу представить необходимый числовой адрес, он передает запрос DNS-серверу, отвечающему за область mipt.ru. Если и тот не в силах самостоятельно справиться с проблемой, он перенаправляет запрос серверу DNS, отвечающему за область 1-го ранга ru. Этот сервер может обратиться к серверу DNS, обслуживающему область 1-го ранга edu, который, наконец, затребует информацию от сервера DNS области brown.edu, где должен быть нужный числовой адрес. Полученный числовой адрес по всей цепи серверов DNS в обратном порядке будет передан процессу, направившему запрос.

Пример разрешения имен с использованием DNS-серверов

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

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

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

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

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

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

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

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

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

Полные адреса. Понятие сокета (socket)

Таким образом, полный адрес удаленного процесса или промежуточного объекта для конкретного способа связи с точки зрения операционных систем определяется парой адресов: <числовой адрес компьютера в сети, порт>. Подобная пара получила наименование socket (в переводе – «гнездо» или, как стали писать в последнее время, сокет), а сам способ их использования – организация связи с помощью   сокетов. В случае непрямой адресации с использованием промежуточных объектов сами эти объекты также принято называть сокетами. Поскольку разные протоколы   транспортного уровня требуют разных адресных пространств портов, то для каждой пары надо указывать, какой транспортный протокол она использует, – говорят о разных типах сокетов.

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

Проблемы маршрутизации в сетях

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

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

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

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

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

  Простая таблица маршрутизации

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

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

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

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

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

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

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

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

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

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

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

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

Синхронизация удаленных процессов

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

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

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

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

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

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

Во время функционирования РОС могут возникать параллельные вычислительные процессы между процессами:

•   внутри одной задачи;

•   принадлежащими разным задачам;

•   задачи пользователя и операционной системы;

•   самой операционной системы.

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

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

•   копии программ часто используемых функций ОС имеются на всех компьютерах, редко используемых – на одной или на немногих ЭВМ;

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

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

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

Выделяют три элемента взаимодействия асинхронных параллельных процессов – инициацию, завершение и синхронизацию.

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

В вычислительных системах для синхронизации процессов широко используется механизм событий, назначение которого аналогично назначению семафоров. Алгоритмы синхронизации, основанные на механизме событий, в различных операционных системах различаются деталями, но в силу своей идеологической близости могут быть проиллюстрированы механизмом событий, используемым в вычислительной машине IВМ/390, который базируется на блоке управления событием и двух макрокомандах WAIT и POST. Синхронизация событий в системах с общей памятью может выполняться с его помощью, но при этом любая операция синхронизации приводит, фактически, к одному межмашинному обмену или нескольким. Поэтому в системах с раздельной памятью для синхронизации событий необходим еще один оператор – оператор посылки сообщений.

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

Существуют три типа доступа к ресурсу (закрытия ресурса):

•   монопольный – только одна транзакция получает доступ к ресурсу (монопольный тип доступа обычно используется при записи информации);

•   разделяемый – несколько транзакций получают доступ к ресурсу (разделяемый тип доступа обычно используется при чтении информации);

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

Всякая транзакция при обращении к ресурсу узла должна:

•   закрывать доступ к ресурсу одним из типов закрытия;

•   не закрывать монопольный доступ к ресурсу, если он уже закрыт другой транзакцией;

•   перед окончанием работы с ресурсом открывать его, т. е. снимать ограничение на доступ к нему;

•   закрыв его, не закрывать доступ к ресурсу повторно.

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

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

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

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

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

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

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

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

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

Тема 15.2. Реализация сетевого взаимодействия

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

Модель клиент - сервер (при использовании сокетов)

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

Типы сокетов. Понятие коммуникационного домена.

Существует несколько типов сокетов в зависимости от коммуникации соединений: 1)виртуальный канал, 2)дейтаграмма.

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

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

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

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

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

Сокеты могут использоваться как для локального, так и для удаленного взаимодействия. Возникает вопрос о пространстве адресов сокетов. При создании сокета указывается коммуникационный домен, которому данный сокет будет принадлежать. Он определяет формат адресов и правила их интерпретации: 1) для локального взаимодействия AF_UNIX; 2) для взаимодействия в рамках сети AF_INET. В домене AF_UNIX формат адреса допускает имя файла. В AF_INET адрес - это имя хоста плюс номер порта.

Реальный коммуникационный домен определяет также использование семейства протоколов - внутренние протоколы и протоколы TCP IP

Создание сокетов.

#include <sys\types.h>

#include <sys\socket.h>

int socket(int domain; int type; int protocol)

domain - номер домена, которому будет принадлежать сокет;

type - тип соединения, которым будет пользоваться сокет;

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

Sock_STREM - с использованием виртуального канала.

Sock_DGRAM - с использованием дейтаграмм.

Если значение protocol=0, то система сама выбирает нужный протокол (удобно использовать константы IPRROTO_TCP -  для первого типа, IPRROTO_UDP - для второго типа, аналогия с разделяемой памятью). В противном случае будет генерироваться “-1” (если не корректное сочетание аргументов.)

Связь с сокетом

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

int bind(int sockfd, struct sockaddr *myaddr, int addrlen)

Для AF_UNIX формат структуры описан в файле <sys\on.h>.

struct sockaddr_UN {

shortsun_family;

char sun_pth[108]

};

Для AF_INET формат структуры описан в<netinet\in.h>.

struct sockaddr_in {

short sin_family;

U_short sin_port;

struct in_addrsin_addr;

char sin_zero[8];

}

Если локальные сокеты и адрес сокета - имя файла, то система создает файл с таким именем. В случае успеха возвращвется 0, в противном случае “-1”.

Сокеты с предварительно установленным соединением и без него. Запрос на соединение.

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

Функция connect.

int connect(int sockfd,struct sockaddr *serv_addr, int addrbn)

sockfd - ДФ сокета.

*serv_addr - указатель на структуру, с которой устанавливается соединение.

В случае успеха возвращает 0, иначе “-1”.

Замечание. В рамках рассмотренной системы клиенту не важно какой адрес будет назначен сокету. Клиент может не вызывать функцию bind, тогда при вызове connect система автоматически выбирет адрес (в рамках AF_INET).

Сервер: прослушивание сокета и подтверждение соединения

2 вызова, которые используются сервером, в случае если используются сокеты с предварительно установленным соединением.

1) int listen (int sockfd, int backbag);

backbag - максимальный размер очередного запроса на соединение.

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

2) int accept (int sockfd, struct sockaddr *addr, int *addrlen);

*addr - адрес клиентского сокета

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

РАЗДЕЛ 16. Защитные механизмы ОС

Тема 16.1. Локальные механизмы контроля доступа

Идентификация и аутентификация

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

Обычно аутентификация базируется на одном или более из трех пунктов:

Пароли, уязвимость паролей

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

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

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

Есть два общих способа угадать пароль. Один связан со сбором информации о пользователе. Люди обычно используют в качестве паролей очевидную информацию (скажем, имена животных или номерные знаки автомобилей). Для иллюстрации важности разумной политики назначения идентификаторов и паролей можно привести данные исследований, проведенных в AT&T, показывающие, что из 500 попыток несанкционированного доступа около 300 составляют попытки угадывания паролей или беспарольного входа по пользовательским именам guest, demo и т. д.

Другой способ - попытаться перебрать все наиболее вероятные комбинации букв, чисел и знаков пунктуации (атака по словарю). Например, четыре десятичные цифры дают только 10 000 вариантов, более длинные пароли, введенные с учетом регистра символов и пунктуации, не столь уязвимы, но тем не менее таким способом удается разгадать до 25% паролей. Чтобы заставить пользователя выбрать трудноугадываемый пароль, во многих системах внедрена реактивная проверка паролей, которая при помощи собственной программы-взломщика паролей может оценить качество пароля, введенного пользователем.

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

Шифрование пароля

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

Например, в ряде версий Unix в качестве односторонней функции используется модифицированный вариант алгоритма DES. Введенный пароль длиной до 8 знаков преобразуется в 56-битовое значение, которое служит входным параметром для процедуры crypt(), основанной на этом алгоритме. Результат шифрования зависит не только от введенного пароля, но и от случайной последовательности битов, называемой привязкой (переменная salt). Это сделано для того, чтобы решить проблему совпадающих паролей. Очевидно, что саму привязку после шифрования необходимо сохранять, иначе процесс не удастся повторить. Модифицированный алгоритм DES выполняется, имея входное значение в виде 64-битового блока нулей, с использованием пароля в качестве ключа, а на каждой следующей итерации входным параметром служит результат предыдущей итерации. Всего процедура повторяется 25 раз. Полученное 64-битовое значение преобразуется в 11 символов и хранится рядом с открытой переменной salt.

В ОС Windows NT преобразование исходного пароля также осуществляется многократным применением алгоритма DES и алгоритма MD4.

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

При удаленном доступе к ОС нежелательна передача пароля по сети в открытом виде. Одним из типовых решений является использование криптографических протоколов. В качестве примера можно рассмотреть протокол опознавания с подтверждением установления связи путем вызова - CHAP (Challenge Handshake Authentication Protocol).

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

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

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

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

Авторизация. Разграничение доступа к объектам ОС

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

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

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

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

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

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

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

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

Отметим, что данная модель разработана для хранения секретов, но не гарантирует целостности данных. Например, здесь лейтенант имеет право писать в файлы генерала. Более подробно о реализации подобных формальных моделей рассказано в [Столлингс, 2002], [Таненбаум, 2002].

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

Тема 16.2. Модели управления доступом

Домены безопасности

Чтобы рассмотреть схему дискреционного доступа более детально, введем концепцию домена безопасности (protection domain). Каждый домен определяет набор объектов и типов операций, которые могут производиться над каждым объектом. Возможность выполнять операции над объектом есть права доступа, каждое из которых есть упорядоченная пара <object-name, rights-set>. Домен, таким образом, есть набор прав доступа. Hапример, если домен D имеет права доступа <file F, {read, write}>, это означает, что процесс, выполняемый в домене D, может читать или писать в файл F, но не может выполнять других операций над этим объектом. Пример доменов можно увидеть на рисунке.

Рис 16.2.1 Специфицирование прав доступа к ресурсам

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

Рассмотрим стандартную двухрежимную модель выполнения ОС. Когда процесс выполняется в режиме системы (kernel mode), он может выполнять привилегированные инструкции и иметь полный контроль над компьютерной системой. С другой стороны, если процесс выполняется в пользовательском режиме, он может вызывать только непривилегированные инструкции. Следовательно, он может выполняться только внутри предопределенного пространства памяти. Наличие этих двух режимов позволяет защитить ОС (kernel domain) от пользовательских процессов (выполняющихся в user domain). В мультипрограммных системах двух доменов недостаточно, так как появляется необходимость защиты пользователей друг от друга. Поэтому требуется более тщательно разработанная схема.

В ОС Unix домен связан с пользователем. Каждый пользователь обычно работает со своим набором объектов.

Матрица доступа

Модель безопасности, специфицированная в предыдущем разделе, имеет вид матрицы, которая называется матрицей доступа. Какова может быть эффективная реализация матрицы доступа? В общем случае она будет разреженной, то есть большинство ее клеток будут пустыми. Хотя существуют структуры данных для представления разреженной матрицы, они не слишком полезны для приложений, использующих возможности защиты. Поэтому на практике матрица доступа применяется редко. Эту матрицу можно разложить по столбцам, в результате чего получаются списки прав доступа (access control list - ACL). В результате разложения по строкам получаются мандаты возможностей (capability list или capability tickets).

Список прав доступа. Access control list

Каждая колонка в матрице может быть реализована как список доступа для одного объекта. Очевидно, что пустые клетки могут не учитываться. В результате для каждого объекта имеем список упорядоченных пар <domain, rights-set>, который определяет все домены с непустыми наборами прав для данного объекта.

Элементами списка могут быть процессы, пользователи или группы пользователей. При реализации широко применяется предоставление доступа по умолчанию для пользователей, права которых не указаны. Например, в Unix все субъекты-пользователи разделены на три группы (владелец, группа и остальные), и для членов каждой группы контролируются операции чтения, записи и исполнения (rwx). В итоге имеем ACL - 9-битный код, который является атрибутом разнообразных объектов Unix.

Мандаты возможностей. Capability list

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

Примерами систем, использующих перечни возможностей, являются Hydra, Cambridge CAP System [Denning, 1996].

Другие способы контроля доступа

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

Существует также схема lock-key, которая является компромиссом между списками прав доступа и перечнями возможностей. В этой схеме каждый объект имеет список уникальных битовых шаблонов (patterns), называемых locks. Аналогично каждый домен имеет список уникальных битовых шаблонов, называемых ключами (keys). Процесс, выполняющийся в домене, может получить доступ к объекту, только если домен имеет ключ, который соответствует одному из шаблонов объекта.

Как и в случае мандатов, список ключей для домена должен управляться ОС. Пользователям не разрешается проверять или модифицировать списки ключей (или шаблонов) непосредственно. Более подробно данная схема изложена в [Silberschatz, 2002].

Смена домена

В большинстве ОС для определения домена применяются идентификаторы пользователей. Обычно переключение между доменами происходит, когда меняется пользователь. Но почти все системы нуждаются в дополнительных механизмах смены домена, которые используются, когда некая привилегированная возможность необходима большому количеству пользователей. Hапример, может понадобиться разрешить пользователям иметь доступ к сети, не заставляя их писать собственные сетевые программы. В таких случаях для процессов ОС Unix предусмотрена установка бита set-uid. В результате установки этого бита в сетевой программе она получает привилегии ее создателя (а не пользователя), заставляя домен меняться на время ее выполнения. Таким образом, рядовой пользователь может получить нужные привилегии для доступа к сети.

Недопустимость повторного использования объектов

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

Выявление вторжений. Аудит системы защиты

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

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

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

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

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

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

Анализ некоторых популярных ОС с точки зрения их защищенности

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

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

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

MS-DOS

ОС MS-DOS функционирует в реальном режиме (real-mode) процессора i80x86. В ней невозможно выполнение требования, касающегося изоляции программных модулей (отсутствует аппаратная защита памяти). Уязвимым местом для защиты является также файловая система FAT, не предполагающая у файлов наличия атрибутов, связанных с разграничением доступа к ним. Таким образом, MS-DOS находится на самом нижнем уровне в иерархии защищенных ОС.

NetWare, IntranetWare

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

OS/2

OS/2 работает в защищенном режиме (protected-mode) процессора i80x86. Изоляция программных модулей реализуется при помощи встроенных в этот процессор механизмов защиты памяти. Поэтому она свободна от указанного выше коренного недостатка систем типа MS-DOS. Но OS/2 была спроектирована и разработана без учета требований по защите от несанкционированного доступа. Это сказывается прежде всего на файловой системе. В файловых системах OS/2 HPFS (high performance file system) и FAT нет места ACL. Кроме того, пользовательские программы имеют возможность запрета прерываний. Следовательно, сертификация OS/2 на соответствие какому-то классу защиты не представляется возможной.

Считается, что такие операционные системы, как MS-DOS, Mac OS, Windows, OS/2, имеют уровень защищенности D (по оранжевой книге). Но, если быть точным, нельзя считать эти ОС даже системами уровня безопасности D, ведь они никогда не представлялись на тестирование.

Unix

Рост популярности Unix и все большая осведомленность о проблемах безопасности привели к осознанию необходимости достичь приемлемого уровня безопасности ОС, сохранив при этом мобильность, гибкость и открытость программных продуктов. В Unix есть несколько уязвимых с точки зрения безопасности мест, хорошо известных опытным пользователям, вытекающих из самой природы Unix [Дунаев, 1996]. Однако хорошее системное администрирование может ограничить эту уязвимость.

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

Обычно, говоря о защищенности Unix, рассматривают защищенность автоматизированных систем, одним из компонентов которых является Unix-сервер. Безопасность такой системы увязывается с защитой глобальных и локальных сетей, безопасностью удаленных сервисов типа telnet и rlogin/rsh и аутентификацией в сетевой конфигурации, безопасностью X Window-приложений. Hа системном уровне важно наличие средств идентификации и аудита.

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

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

По отношению к конкретному файлу все пользователи делятся на три категории:

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

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

Аналогичным образом защищены и другие объекты ОС Unix, например семафоры, сегменты разделяемой памяти и т. п.

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

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

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

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

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

Windows NT/2000/XP

С момента выхода версии 3.1 осенью 1993 года в Windows NT гарантировалось соответствие уровню безопасности C2. В настоящее время (точнее, в 1999 г.) сертифицирована версия NT 4 с Service Pack 6a с использованием файловой системы NTFS в автономной и сетевой конфигурации. Следует помнить, что этот уровень безопасности не подразумевает защиту информации, передаваемой по сети, и не гарантирует защищенности от физического доступа.

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

ОС Windows 2000 сертифицирована по стандарту Common Criteria. В дальнейшем линейку продуктов Windows NT/2000/XP, изготовленных по технологии NT, будем называть просто Windows NT.

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

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

Система защиты ОС Windows NT состоит из следующих компонентов:

Microsoft Windows NT - относительно новая ОС, которая была спроектирована для поддержки разнообразных защитных механизмов, от минимальных до C2, и безопасность которой наиболее продумана. Дефолтный уровень называется минимальным, но он легко может быть доведен системным администратором до желаемого уровня.

Тема 16.3. Сетевые механизмы контроля доступа

Криптография как одна из базовых технологий безопасности ОС

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

Шифрование – процесс преобразования сообщения из открытого текста (plaintext) в шифротекст (ciphertext) таким образом, чтобы:

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

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

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

В системах шифрования с открытым или асимметричным ключом (public/ assymmetric key) используется два ключа (см. рис. 15.1). Один из ключей, называемый открытым, несекретным, используется для шифрования сообщений, которые могут быть расшифрованы только с помощью секретного ключа, имеющегося у получателя, для которого предназначено сообщение. Иногда поступают по-другому. Для шифрования сообщения используется секретный ключ, и если сообщение можно расшифровать с помощью открытого ключа, подлинность отправителя будет гарантирована (система электронной подписи). Этот принцип изобретен Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 г.

Рис. 16.3.1  Шифрование открытым ключом

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

Среди несимметричных алгоритмов наиболее известен RSA, предложенный Роном Ривестом (Ron Rivest), Ади Шамиром (Adi Shamir) и Леонардом Эдлманом (Leonard Adleman). Рассмотрим его более подробно.

Шифрование с использованием алгоритма RSA

Идея, положенная в основу метода, состоит в том, чтобы найти такую функцию y=Φ(x), для которой получение обратной функции x=f-1(y) было бы в общем случае очень сложной задачей (NP-полной задачей). Например, получить произведение двух чисел n=p×q просто, а разложить n на множители, если p и q достаточно большие простые числа, – NP-полная задача с вычислительной сложностью ~ n10. Однако если знать некую секретную информацию, то найти обратную функцию x=f-1(y) существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом.

Применяемые в RSA прямая и обратная функции просты. Они базируются на применении теоремы Эйлера из теории чисел.

Прежде чем сформулировать теорему Эйлера, необходимо определить важную функцию Φ(n) из теории чисел, называемую функцией Эйлера. Это число взаимно простых (взаимно простыми называются целые числа, не имеющие общих делителей) с n целых чисел, меньших n. Например, Φ(7)=6. Очевидно, что, если p и q – простые числа и pq, то Φ(p)=p-1, и Φ(pq)=(p-1)×(q-1).

Протокол сетевой аутентификации Kerberos 5

Протокол Kerberos был создан более десяти лет назад в Массачусетском технологическом институте в рамках проекта Athena. Однако общедоступным этот протокол стал, начиная с версии 4. После того, как специалисты изучили новый протокол, авторы разработали и предложили очередную версию — Kerberos 5, которая была принята в качестве стандарта IETF. Требования реализации протокола изложены в документе RFC 1510, кроме того, в спецификации RFC 1964 описывается механизм и формат передачи жетонов безопасности в сообщениях Kerberos.

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

Основные концепции.

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

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

Теперь Стасу и Ольге осталось только решить, каким образом показать знание пароля. Можно просто включить его в текст сообщения, например, после подписи: "Ольга, нашПароль". Это было бы просто, удобно и надёжно, если бы Ольга и Стас были уверены, что никто другой не читает их письма. К сожалению, в реальном мире об этом можно только мечтать. Почта передаётся по сети, в которой работают и другие пользователи, а среди них есть Женя, который очень любит выведывать чужие секреты, и постоянно подключает к сети свой анализатор пакетов. Совершенно ясно, что Ольга не может просто указать пароль в теле письма. Чтобы пароль оставался секретом, о нём нельзя говорить открыто, нужно лишь дать собеседнику знать, что пароль известен отправителю.

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

Аутентификаторы.

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

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

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

  1. Ольга посылает Стасу         сообщение, содержащее её имя в открытом         виде и аутентификатор, зашифрованный         с помощью секретного ключа. В протоколе         аутентификации такое сообщение         представляет собой структуру данных         с двумя полями. Первое поле содержит         имя, второе поле — текущее время на         рабочей станции Ольги.         
  2. Стас получает сообщение и         видит, что оно пришло от кого-то, кто         называет себя Ольгой. Он использует         секретный ключ и дешифрует время         отправления сообщения. Задача Стаса         сильно упрощается, если его компьютер         работает синхронно с компьютером Ольги,         поэтому предположим, что часы на         компьютерах Стаса и Ольги никогда не         расходятся больше, чем на пять минут.         В этом случае Стас может сравнить         расшифрованное время со временем на         своих часах, и, если разница составит         более пяти минут, он откажется признавать         подлинность аутентификатора. Если же         время оказывается в пределах допустимого         отклонения, то можно с большой долей         уверенности предположить, что         аутентификатор поступил именно от         Ольги.         
  3. Стас шифрует время из         сообщения Ольги и включает его в         собственное сообщение, которое отправляет         Ольге.
  4. Обратите внимание, что Стас         возвращает Ольге не всю информацию из         её аутентификатора, а только время.         Если бы он отправил всё сртазу, то у         Ольги могло бы зародиться подозрение,         что кто-то, притворившись Стасом, просто         скопировал аутентификатор из её         исходного сообщения и без изменений         отправил его назад.         
  5. Ольга получает ответ Стаса,         дешифрует его, и сравнивает полученное         время со временем, которое было указано         в исходном аутентификаторе. Если оно         совпадает, то человек на другом конце         смог расшифровать её сообщение, а         значит, он знает секретный ключ. А так         как ключ знает только Ольга и Стас, то         это означает, что именно Стас получил         сообщение Ольги и ответил на него.         

Управление ключами.

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

Само название протокола Kerberos говорит о том, как здесь решена проблема управления ключами. Кербер (или Цербер) — персонаж классической греческой мифологии. Этот свирепый пёс о трёх головах, по поверьям греков, охраняет врата подземного царства мёртвых. Трём головам Кербера в протоколе Kerberos соответствуют три участника безопасной связи: клиент, сервер и доверенный посредник между ними. Роль посредника здесь играет так называемый центр распределения ключей Key Distribution Center, KDC.

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

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

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

Сеансовые мандаты.

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

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

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

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

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

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

Мандаты на выдачу мандатов.

Как уже отмечалось, долговременный ключ пользователя генерируется на основе его пароля. Чтобы лучше понять это, вернемся к нашему примеру. Когда Ольга проходит регистрацию, клиент Kerberos, установленный на ее рабочей станции, пропускает указанный пользователем пароль через функцию одностороннего хеширования (все реализации протокола Kerberos 5 должны обязательно поддерживать алгоритм DES-CBC-MD5, хотя могут применяться и другие алгоритмы). В результате генерируется криптографический ключ.

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

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

На запрос пользователя KDC отвечает специальным сеансовым мандатом для самого себя, так называемый мандат на выдачу мандатов (ticket-granting ticket), или мандат TGT. Как и обычный сеансовый мандат, мандат TGT содержит копию сеансового ключа для связи службы (в данном случае – центра KDC) с клиентом. В сообщение с мандатом TGT также включается копия сеансового ключа, с помощью которой клиент может связаться с KDC. Мандат TGT шифруется посредством долговременного ключа службы KDC, а клиентская копия сеансового ключа – с помощью долговременного ключа пользователя.

Получив ответ службы KDC на свой первоначальный запрос, клиент дешифрует свою копию сеансового ключа, используя для этого копию долговременного ключа пользователя из своей кэш-памяти. После этого долговременный ключ, полученный из пользовательского пароля, можно удалить из памяти, поскольку он больше не понадобится: вся последующая связь с KDC будет шифроваться с помощью полученного сеансового ключа. Как и все другие сеансовые ключи, он имеет временный характер и действителен до истечения срока действия мандата TGT, либо до выхода пользователя из системы. По этой причине такой ключ называют сеансовым ключом регистрации (logon session key).

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

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

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

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

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

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

Среди современных ОС вопросы безопасности лучше всего продуманы в ОС Windows NT.