Взаимодействие процессов

Параллельные процессы могут быть либо независимыми (independed processes), либо взаимодействующими (cooperating processes).

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

· Сигнал (signal) - передается минимум информации: один бит, “да” или “нет”. Используется для извещения процесса о наступлении какого-либо события. Примитив signal извещает о наступлении события, примитив wait выдает процесс, ожидающий этого события;

· Сообщение (message) - передается блок данных вместе с управляющей информацией, определяющей тип сообщения;

· Разделяемая память (shared memory). Два или более процессов могут совместно использовать некоторую область адресного пространства;

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

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

Здесь можно выделить три принципиальных варианта:

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

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

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

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

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

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

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

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

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

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

· выполнение совместной работы двумя процессами, где один является «производителем», а другой – «потребителем» (producer - consumer);

· клиент-сервер;

· «обедающие философы»;

· «читатали-писатели».

Схема producer – consumer подразумевает использование буфера. Если буфер заполнен, то процесс «производитель» должен ожидать его освобождения «потребителем», если буфер пуст, то должен ожидать процесс «потребитель».

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

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

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

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

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

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

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

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

Основная литература

Учебник / Учебное пособие	Раздел	Страницы
Таненбаум Э. Современные операционные системы. 3-е изд. - СПб.: Питер, 2010. - 1120 е.: ил.	2.3.1-2.3.5	150-164

Тема 4. Управление данными в ОС. Файловая система

Лекция №4. Управление данными в ОС

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

· Обмен с внешними устройствами

· Иерархия памяти

· Кэширование.

· Управление основной памятью.

· Отображение на физическую память

· Страничная, сегментная, сегментно-страничная организация памяти

· Свопинг.

· Организация виртуальной памяти.

· Алгоритмы замещения страниц.

· Типы и атрибуты файлов.

· Логический и физический уровень файловой системы.

· Доступ к файлам. Операции с файлом

· Каталоги. Операции с каталогом.

· Совместно используемые файлы.

· Журнализация в файловой системе.

Как отмечалось ранее, имеются два вида памяти: основная (оперативная) память и внешняя. Основная память используется для кратковременного хранения информации (данных программ, промежуточных и конечных результатов обработки), непосредственно используемой в процессе выполнения операций в арифметическо-логическом устройстве и устройстве управления. Внешняя память служит для долговременного хранения данных и программ и отличается разнообразием носителей, используемых для хранения этих данных и программ. Примерами носителей могут быть: жесткий диск, цифровой многофункциональный диск (DVD), ПЗУ на компакт-диске (CD-ROM), уже не используемый магнитный диск 3,5”.

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

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

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

· символьные (клавиатура, модем, терминал и т.п.);

· блочные (магнитные и оптические диски и ленты, и т.д.);

· сетевые (сетевые карты);

· все остальные (таймеры, графические дисплеи, телевизионные устройства, видеокамеры и т.п.);

Символьным устройствам обычно предписывается выполнение двух основных операций: получить (get) символ (байт) из буфера устройства и поместить (put) символ (байт) в буфер устройства. Блочные устройства выполняют операции чтения и записи блока информации – read и write. Устройства прямого доступа имеют дополнительно операцию поиска требуемого блока информации – seek.

Что касается внешних ЗУ, то они относятся к блочным устройствам, единицей обмена с которыми на физическом уровне является блок данных. Размер блока зависит от типа ЗУ и в частности - от его объема и быстродействия (времени доступа к данным). Кроме того, учитывается стоимость хранения одного бита.

Иерархия запоминающих устройств

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

DRAM – динамическая оперативная память, время доступа равно примерно 10-20 наносекунд.

SRAM - быстродействующее ЗУ на основе статической оперативной памяти, объем которых составляет от нескольких десятков до нескольких сотен килобайт, а время доступа к данным обычно не превышает 8 нс.

Объем регистров составляет несколько десятков байт, а время доступа определяется быстродействием процессора и равно в настоящее время примерно 2-3 нс.

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

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

Для решение этой проблемы используется:

- Сквозная запись (write through). При каждом запросе к основной памяти просматривается кэш. Если данные по запрашиваемому адресу отсутствуют, то запись выполняется только в основную память. Иначе запись выполняется одновременно в кэш и основную память.

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

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

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

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

· отображение адресов пространства символических имен программы на языке высокого уровня на пространство виртуальных и физических адресов;

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

· выделение памяти процессам и освобождение памяти при завершении процессов;

· отслеживание свободной и занятой памяти и сборка «мусора».

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

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

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

· фиксированными разделами;

· разделами переменной величины;

· перемещаемыми разделами.

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

В OS/2 была предложена реализация динамической компоновки (связей) исполнимых модулей в виде подключаемых библиотек (Dynamic Link Library, файлы с расширением.DLL), компоновка с которыми выполняется не до загрузки, а при появлении ссылки на модуль во время исполнения программы. Это уменьшает размеры программ и позволяет вносить изменения только в один DLL-файл, а не отдельно в каждую программу, в которой он используется.

Многопрограммная работа требует, чтобы в оперативную память можно было загружать несколько процессов. Поскольку оперативная память физически ограничена конкретным размером, то для возможности размещения и одновременного исполнения большого количества процессов используется способ расширения объёма адресуемой физической памяти специальной областью на быстром устройстве с прямым доступом. Такое устройство обычно является диском, область на диске называется страничным файлом, или файлом подкачки (swap file).Оперативная память разбивается либо на страницы (page) фиксированного размера, либо на сегменты переменной длины и организуется выгрузка неактивных страниц в страничный файл на диске и загрузка из него необходимых страниц. Преимущество использования виртуальной памяти в том, что программу не нужно разбивать на подгружаемые с внешнего ЗУ при её выполнении сегменты, называемые оверлеями (overlay). Можно загружать на исполнение большое количество приложений и обрабатывать в программе большие массивы данных: оперативная память для программиста представляется однородной и имеющей большой объем.

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

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

Размер страницы обычно выбирается равным степени двойки: 512, 1024 и т.д.

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

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

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

Существуют различные алгоритмы выбора вытесняемой станицы:

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

· Алгоритм FIFO (First-In, First-Out, «первой пришла, первой ушла»). Модификация алгоритма FIFO для исключения проблемы удаления часто востребуемой - проверка бита R самой старой страницы. Если его значение равно нулю, значит, страница не только старая, но и невостребованная, поэтому она удаляется. Если бит R имеет значение 1, он сбрасывается, а страница помещается в конец списка страниц, и время ее загрузки обновляется, как будто она только что поступила в память.

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

· «Часы». Проверяется та страница, на которую указывает стрелка «часов». Если ее бит R имеет значение 0, страница выселяется, на ее место в «часах» вставляется новая страница, и стрелка передвигается вперед на одну позицию. Если значение бита R равно 1, то он сбрасывается, и стрелка перемещается на следующую страницу. Этот процесс повторяется до тех пор, пока не будет найдена страница с R = 0.

· Алгоритм LRU (Least Recently Used). Замещает наиболее давней по использованию страницы. Необходим связан ный список всех страниц, находящихся в памяти. В начале списка находится только что востребованная страница, а в конце - наименее востребованная. Список должен обновляться при каждом обращении к памяти.

· Алгоритм NFU (Not Frequently Used), или нечастого использования. Требуется программный счетчик с начальным нулевым значением, связанный с каждой страницей. При каждом прерывании от таймера операционная система сканирует всё находящиеся в памяти страницы. Для каждой страницы к счетчику добавляется значение бита R, равное 0 или 1. Счетчики позволяют приблизительно отследить частоту обращений к каждой странице. При возникновении ошибки отсутствия страницы для замещения выбирается та страница, чей счетчик имеет наименьшее значение.

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

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

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

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

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

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

· из этой записи извлекается номер физической страницы,

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

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

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

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

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