Взаимодействие процессов в UNIX.
Вариант 1
Вопрос 1
Существует много способов обмена информацией между процессами. В версии V системы UNIX для этого существует пакет IPC (interprocess communication) который включает в себя три механизма:
Механизм сообщений дает процессам возможность посылать другим процессам потоки сформатированных данных;
механизм разделения памяти позволяет процессам совместно использовать отдельные части виртуального адресного пространства;
механизм семафоров - синхронизировать свое выполнение с выполнением параллельных процессов.
Несмотря на то, что они реализуются в виде отдельных блоков, им присущи общие свойства.
С каждым механизмом связана таблица, в записях которой описываются все его детали.
В каждой записи содержится числовой ключ (key), который представляет собой идентификатор записи, выбранный пользователем.
В каждом механизме имеется системная функция типа “get”, используемая для создания новой или поиска существующей записи; параметрами функции являются идентификатор записи и различные флаги (flag). Ядро ведет поиск записи по ее идентификатору в соответствующей таблице. Процессы могут с помощью флага IPC_PRIVATE гарантировать получение еще неиспользуемой записи. С помощью флага IPC_CREAT они могут создать новую запись, если записи с указанным идентификатором нет, а если еще к тому же установить флаг IPC_EXCL, можно получить уведомление об ошибке в том случае, если запись с таким идентификатором существует. Функция возвращает некий выбранный ядром дескриптор, предназначенный для последующего использования в других системных функциях, таким образом, она работает аналогично системным функциям creat и open.
В каждом механизме ядро использует следующую формулу для поиска по дескриптору указателя на запись в таблице структур данных: указатель = значение дескриптора по модулю от числа записей в таблице. Если, например, таблица структур сообщений состоит из 100 записей, дескрипторы, связанные с записью номер 1, имеют значения, равные 1, 101, 201 и т.д. Когда процесс удаляет запись, ядро увеличивает значение связанного с ней дескриптора на число записей в таблице: полученный дескриптор станет новым дескриптором этой записи, когда к ней вновь будет произведено обращение при помощи функции типа “get”. Процессы, которые будут пытаться обратиться к записи по ее старому дескриптору, потерпят неудачу. Обратимся вновь к предыдущему примеру. Если с записью 1 связан дескриптор, имеющий значение 201, при его удалении ядро назначит записи новый дескриптор, имеющий значение 301. Процессы, пытающиеся обратиться к дескриптору 201, получат ошибку, поскольку этого дескриптора больше нет. В конечном итоге ядро произведет перенумерацию дескрипторов, но пока это произойдет, может пройти значительный промежуток времени.
Каждая запись имеет некую структуру данных, описывающую права доступа к ней и включающую в себя пользовательский и групповой коды идентификации, которые имеет процесс, создавший запись, а также пользовательский и групповой коды идентификации, установленные системной функцией типа “control” (об этом ниже), и двоичные коды разрешений чтения - записи - исполнения для владельца, группы и прочих пользователей, по аналогии с установкой прав доступа к файлам.
В каждой записи имеется другая информация, описывающая состояние записи, в частности, идентификатор последнего из процессов, внесших изменения в запись (посылка сообщения, прием сообщения, подключение разделяемой памяти и т.д.), и время последнего обращения или корректировки.
В каждом механизме имеется системная функция типа “control”, запрашивающая информацию о состоянии записи, изменяющая эту информацию или удаляющая запись из системы. Когда процесс запрашивает информацию о состоянии записи, ядро проверяет, имеет ли процесс разрешение на чтение записи, после чего копирует данные из записи таблицы по адресу, указанному пользователем. При установке значений принадлежащих записи параметров ядро проверяет, совпадают ли между собой пользовательский код идентификации процесса и идентификатор пользователя (или создателя), указанный в запи си, не запущен ли процесс под управлением суперпользователя; одного раз решения на запись недостаточно для установки параметров. Ядро копирует сообщенную пользователем информацию в запись таблицы, устанавливая значения пользовательского и группового кодов идентификации, режимы доступа и другие параметры (в зависимости от типа механизма). Ядро не изменяет значения полей, описывающих пользовательский и групповой коды идентификации создателя записи, поэтому пользователь, создавший запись, сохраняет управляющие права на нее. Пользователь может удалить запись, либо если он является суперпользователем, либо если идентификатор процесса совпадает с любым из идентификаторов, указанных в структуре записи. Ядро увеличивает номер дескриптора, чтобы при следующем назначении записи ей был присвоен новый дескриптор. Следовательно, как уже ранее говорилось, если процесс попытается обратиться к записи по старому дескриптору, вызванная им функция получит отказ.
Вопрос2
Спинлок (англ. Spinlock — циклическая блокировка) — низкоуровневый примитив синхронизации, применяемый в многопроцессорных системах для реализациивзаимного исключения.
Спин-блокировка - простейший механизм синхронизации. Спин-блокировка может быть захвачена, и освобождена. Если спин-блокировка была захвачена, последующая попытка захватить спин-блокировку любым потоком приведет к бесконечному циклу с попыткой захвата спин-блокировки (состояние потока busy-waiting). Цикл закончится только тогда, когда прежний владелец спин-блокировки освободит ее. Использование спин-блокировок безопасно на мультипроцессорных платформах, то есть гарантируется, что, даже если ее запрашивают одновременно два потока на двух процессорах, захватит ее только один из потоков.
Спин-блокировки предназначены для защиты данных, доступ к которым производится на различных, в том числе повышенных уровнях IRQL. Теперь представим такую ситуацию: код, работающий на уровне IRQL PASSIVE_ LEVEL захватил спин-блокировку для последующего безопасного изменения некоторых данных. После этого код был прерван кодом с более высоким уровнем IRQL DISPATCH_LEVEL, который попытался захватить ту же спин-блокировку, и, как следует из описания спин-блокировки, вошел в бесконечный цикл ожидания освобождения блокировки. Этот цикл никогда не закончится, так как код, который захватил спин-блокировку и должен ее освободить, имеет более низкий уровень IRQL и никогда не получит шанса выполниться! Чтобы такая ситуация не возникла, необходим механизм, не позволяющий коду с некоторым уровнем IRQL прерывать код с более низким уровнем IRQL в тот момент когда код с более низким уровнем IRQL владеет спин-блокировкой. Таким механизмом является повышение текущего уровня IRQL в момент захвата спин-блокировки до некоторого уровня IRQL, ассоциированного со спин-блокировкой, и восстановление старого уровня IRQL в момент ее освобождения. Из сказанного следует, что код, работающий на повышенном уровне IRQL, не имеет права обращаться к ресурсу, защищенному спин-блокировкой, если уровень IRQL спин-блокировки ниже уровня IRQL производящего доступ к ресурсу кода. При попытке таким кодом захватить спин-блокировку его уровень IRQL будет понижен до уровня IRQL спин-блокировки, что приведет к непредсказуемым последствиям.
В NT имеется два вида спин-блокировок:
- Обычные спин-блокировки, особым случаем которых являются спин-блокировки отмены запроса ввода/вывода, используемые при организации очередей запросов ввода/вывода (см. раздел «Отмена запросов ввода/вывода»).
- Спин-блокировки синхронизации прерываний.
С обычными спин-блокировками связан IRQL DISPATCH_LEVEL, то есть:
- все попытки их захвата должны производиться на уровне IRQL, меньшим или равным DISPATCH_LEVEL;
- в случае захвата спин-блокировки текущий уровень IRQL поднимается до уровня DISPATCH_LEVEL.
Со спин-блокировками синхронизации прерываний связан один из уровней DIRQL. Использование обычных спин-блокировок будет описано ниже (за исключением спин-блокировок отмены запросов ввода/вывода, которые были описаны в предыдущем разделе). Использование спин-блокировок синхронизации прерываний будет описано в разделе, посвященном обработке прерываний.
Использование обычных спин-блокировок
- 1. VOID KeInitializeSpinLock(IN PKSPIN_LOCK SpinLock); Эта функция инициализирует объект ядра KSPIN_LOCK. Память под спин-блокировку уже должна быть выделена в невыгружаемой памяти.
2. VOID KeAcquireSpinLock(IN PKSPIN_LOGK SpinLock, OUT PKIRQL Oldlrql); Эта функция захватывает спин-блокировку. Функция не вернет управление до успеха захвата блокировки. При завершении функции уровень IRQL повышается до уровня DISPATCH_LEVEL. Во втором параметре возвращается уровень IRQL, который был до захвата блокировки (он должен быть <= DISPATCH_LEVEL).
3. VOID KeReleaseSpinLock(IN PKSPINJLOCK SpinLock, OUT PKIRQL Newlrql); Эта функция освобождает спин-блокировку и устанавливает уровень IRQL в значение параметра Newlrql. Это должно быть то значение, которое вернула функция KeAcquireSpinLock() в параметре Oldlrql.
4. VOID KeAcquireLockAtDpcLevel(IN PKSPIN_LOCK SpinLock); Эта оптимизированная функция захватывает спин-блокировку кодом, уже работающем на уровне IRQL DISPATCH_LEVEL. В этом случае изменение уровня IRQL не требуется. На однопроцессорной платформе эта функция вообще ничего не делает, так как синхронизация обеспечивается самой архитектурой IRQL.
5. VOID KeReleaseLockFromDpcLevel(IN PKSPIN_LOCK SpinLock); Эта функция освобождает спин-блокировку кодом, захватившим блокировку с помощью функции KeAcquireLockAtDpcLevel(). На однопроцессорной платформе эта функция ничего не делает.
Пример использования обычных спин-блокировок:
typedef struct _DEVICE_EXTENSION
KSPIN_LOCK spinlock }DEVICE_EXTENSION, *PDEVICE_EXTENSION;
*
NTSTATUS DriverEntry (....)
KelnitializeSpinLock(&extension->spinlock); }
NTSTATUS DispatchReadWrite( ...)
{
KIRQL Oldlrql;
KeAcquireSpinLock(&extension->spinlock, &01dlrql); // произвести обработку данных, // защищенных спин-блокировкой
KeReleaseSpinLock(&extension->spinlock, Oldlrql); }
вариант2
вопрос1
Синхронизация процессов
Описатели объектов ядра зависимы от конкретного процесса (process specific). Проще говоря, handle объекта, полученный в одном процессе, не имеет смысла в другом. Однако существуют способы работы с одними и теми же объектами ядра из разных процессов.
Во-первых, это наследование описателя. При создании объекта можно указать будет ли его описатель наследоваться дочерними (порожденными этим процессом) процессами.
Во-вторых, дублирование описателя. Функция DuplicateHandle дублирует описатель объекта одного процесса в другой, т.е. по сути, берет запись в таблице описателей одного процесса и создает ее копию в таблице другого.
И, наконец, именование объекта ядра. При создании объекта ядра для синхронизации (мьютекса, семафора, ожидаемого таймера или события) можно задать его имя. Оно должно быть уникальным в системе. Тогда другой процесс может открыть этот объект ядра, указав в функции Open…(OpenMutex, OpenSemaphore, OpenWaitableTimer, OpenEvent) это имя.
| На самом деле, при вызове функции Create... () система сначала проверяет, не существует ли уже объект ядра с таким именем. Если нет, то создается новый объект. Если да, ядро проверяет тип этого объекта и права доступа. Если типы не совпадают или же вызывающий процесс не имеет полных прав на доступ к объекту, вызов Create… функции заканчивается неудачно и возвращается NULL. Если все нормально, то просто создается новый описатель (handle) существующего уже объекта ядра. По коду возврата функции GetLastError() можно понять что произошло: создался новый объект или Create() вернула уже существующий. |
Поэтому, синхронизировать потоки внутри разных процессов можно точно также как и в пределах одного. Нужно только правильно передать описатель синхронизирующего объекта от одного процесса к другому любым из перечисленных выше способов.
| Пример 10. Многие приложения при запуске проверяют, запущен ли еще один экземпляр этой программы. Стандартный способ реализации этой проверки - использование поименованного Мьютекса. |
| int main(int argc, char* argv[]) { HANDLE Mutex; Mutex = CreateMutex(NULL,FALSE,"MyMutex"); if (ERROR_ALREADY_EXISTS == GetLastError()) // Такой мьютекс уже кем-то создан... { MessageBox(0,"Приложение уже запущено","Error",0); CloseHandle( Mutex); exit(0); } ... } |
Вопрос2
Монитор — в языках программирования, высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающий доступ к неразделяемым ресурсам.[1] Подход к синхронизации двух или более компьютерных задач, использующих общий ресурс, обычно аппаратуру или набор переменных.
При многозадачности, основанной на мониторах, компилятор или интерпретатор прозрачно для программиста вставляет код блокировки-разблокировки в соответствующим образом оформленные процедуры, избавляя программиста от явного обращения к примитивам синхронизации.
Изобретён Пером Бринчем Хансеном, впервые воплощён в языке Concurrent Pascal и использован для структурирования межпроцессного взаимодействия в операционной системе Solo.
Монитор состоит из:
· набора процедур, взаимодействующих с общим ресурсом
· мьютекса
· переменных, связанных с этим ресурсом
· инварианта, который определяет условия, позволяющие избежать состояние гонки
Процедура монитора захватывает мьютекс перед началом работы и держит его или до выхода из процедуры, или до момента ожидания условия (см. ниже). Если каждая процедура гарантирует, что перед освобождением мьютекса инвариант истиннен, то никакая задача не может получить ресурс в состоянии, ведущем к гонке.
Простой пример. Рассмотрим монитор, выполняющий транзакции банковского счёта.
monitor account { int balance := 0 function withdraw(int amount) { if amount < 0 then error "Счёт не может быть отрицательным" else if balance < amount then error "Недостаток средств" else balance := balance - amount } function deposit(int amount) { if amount < 0 then error "Счёт не может быть отрицательным" else balance := balance + amount }}Инвариант здесь просто утверждает, что баланс должен отразить все прошедшие операции до того, как начнётся новая операция. Обычно это не выражено в коде, но подразумевается и может быть упомянуто в комментариях. Однако, есть языки программирования, такие как Эйфель или D, которые могут проверять инварианты. Блокировка добавлена компилятором. Это делает мониторы безопаснее и удобнее, чем другие подходы, требующие от программиста вручную добавлять операции блокировки-разблокировки, — поскольку программист может забыть добавить их.
Монітори
Семафори надають потужний і гнучкий механізм реалізації безпечної взаємодії процесів. Проте гнучкість завжди має зворотну сторону – програми, що створюються з використанням таких засобів, схильні до помилок, причиною яких є їх неминуче підвищений рівень складності.
В якості ілюстрації можна знову звернутися до програми з лістингу 9. Можете перевірити, що випадкова зміна порядку викликів примітивів синхронізації здатна зробити програму непрацездатною, притому це не дуже очевидно. Але це всього лише коротенький учбовий приклад. Помилки, пов'язані з неправильним використанням семафорів, можуть приводити до непередбачуваних і невідтворних критичних станів обчислювальної системи.
Звідси очевидна необхідність, в першу чергу для цілей прикладного програмування, мати засіб синхронізації більш високого рівня, який міг би забезпечити підвищення надійності паралельних програм. Таким засобом стали монітори, запропоновані Хоаром (Hoare) і Брінч Хансеном (Brinch Hansen) в 1974 р. Основна ідея полягає в тому, щоб «заховати» ресурс, що захищається, всередину об'єкту який забезпечує взаємні виключення.
Монітор (версія Хоара - Хансена) – програмний модуль, що складається з послідовності, що ініціалізувала, однієї або кількох процедур і локальних даних. Основні його характеристики:
Локальні змінні монітора доступні тільки його процедурам; зовнішні процедури доступу до локальних даних монітора не мають.
Процес входить в монітор шляхом виклику однієї з його процедур.
У моніторі в певний момент часу може виконуватися тільки один процес; будь-який інший процес, що викликав монітор, буде припинений в очікуванні доступності останнього.
Очевидно, що об'єктно-орієнтовані ОС або мови програмування можуть легко реалізувати монітор як об'єкт із спеціальними характеристиками. Якщо дані в моніторі являють собою якийсь ресурс, то монітор забезпечує взаємне виключення при зверненні до ресурсу.
Для застосування в паралельних обчисленнях монітори повинні забезпечувати синхронізацію процесів. Нехай процес, знаходячись в моніторі, повинен бути призупинений до виконання деякої умови. При цьому потрібен механізм, який не тільки призупиняє процес, але і звільняє монітор, дозволяючи увійти до нього іншому процесу. Пізніше, по виконанню умови, і коли монітор стане доступним, призупинений процес зможе продовжити свою роботу.
Монітор підтримує синхронізацію за допомогою змінних умови, розміщених і доступних тільки в моніторі. Працювати з цими змінними можуть дві функції:
cwait(c) припиняє виконання викликавшого процесу по умові c. Монітор при цьому доступний для використання іншим процесом.
csignal(c) відновлює виконання деякого процесу, призупиненого викликом cwait з тією ж умовою. Якщо є декілька таких процесів, вибирається один з них; якщо таких процесів немає, функція не робить нічого.
Як бачимо, операції cwait / csignal монітора відрізняються від відповідних операцій семафора. Якщо процес в моніторі передає сигнал, але при цьому немає жодного очікуючого його процесу, то сигнал просто втрачається. Це означає, що змінні умови, на відміну від семафорів, не є лічильниками.
Хоаровськоє визначення моніторів (які ще називають моніторами з сигналами) вимагає, щоб у випадку, якщо черга очікування виконання умови не порожня, при виконанні яким-небудь процесом операції csignal для цієї умови був негайно запущений процес з вказаної черги. Тобто процес, що виконав csignal повинен або негайно вийти з монітора, або завершитися.
У такого підходу є два недоліки:
Якщо процес, що виконав csignal не завершив своє перебування в моніторі, то потрібно два додаткових перемикання процесів: для призупинення даного процесу і для відновлення його роботи, коли монітор стане доступним.
Планувальник процесів, пов'язаних з даним сигналом, повинен бути ідеально надійним. При виконанні csignal процес з відповідної черги повинен бути негайно активований до того, як до монітора увійде інший процес і умова активації при цьому може змінитися. В результаті можливе взаємне блокування всіх процесів, пов'язаних з даною умовою.
Лемпсон і Ределл (Lampson, Redell) розробили інше визначення монітора для мови Mesa (така ж структура монітора використана і в мові Modula-3). Примітив csignal замінений примітивом cnotify(x), який інтерпретується наступним чином. Якщо
процес, що виконується в моніторі, викликає cnotify(x), про це сповіщається черга умови x, але виконання процесу продовжується. Результат сповіщення полягає в тому, що процес на початку черги умови відновить свою роботу в найближчому майбутньому, коли монітор виявиться вільним. Проте, оскільки немає гарантії, що інший процес не увійде до монітора раніше, при відновленні роботи процес повинен перевірити, чи виконана умова.
Важливо, що для монітора Лемпсона-Ределла можна ввести граничний час очікування, пов'язаний з примітивом cnotify. Процес, який прочекав повідомлення на протязі граничного часу, поміщається в чергу активних, незалежно від того, чи було повідомлення про виконання умови. При активації процес перевіряє виконання умови і або продовжує роботу, або знову блокується. Це запобігає голодуванню у випадку, якщо інші процеси збоять перед сповіщенням про виконання умови.
Також в систему команд можна включити примітив cbroadcast (широкомовне повідомлення), який викликає активізацію всіх очікуючих процесів. Це зручно, коли повідомляючий процес нічого не знає про кількість очікуючих процесів або не в змозі визначити, який з них треба викликати. Тому монітори Лемпсона-Ределла ще мають називу монітори із сповіщенням і широкомовленням.
Додатковою перевагою монітора Лемпсона-Ределла перед монітором Хоара, є менша схильність до помилок. Якщо прийшло помилкове сповіщення, процес все одно перевірить виконання умови.
Монітори є структурним компонентом мови програмування і відповідальність за організацію взаємного виключення лежить на компіляторі. Останній зазвичай використовує мьютекси і змінні умов. Деякі ОС надають підтримку реалізації моніторів саме через ці засоби (ОС Solaris). Типовим представником мов програмування, в якому монітори є основним засобом синхронізації потоків, є Java. Додавання в опис методу ключового слова synchronized гарантує, що в разі якщо один потік почав виконання цього методу, жоден інший потік не зможе виконувати інший синхронізований метод цього об'єкту. Тобто, у мові Java у кожного об'єкту, що має синхронізовані методи, є пов'язаний з ним монітор.
Вариант 3
Вопрос1
Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций wait и signal и операции инициализации init. Двоичные семафоры могут принимать только значения 0 и 1. Семафоры со счетчиками могут принимать неотрицательные целые значения.
Семафоры могут использоваться для контролирования доступа к ресурсам: число в семафоре представляет собой количество процессов, которые могут получить доступ к данным. Каждый раз, когда процесс обращается к данным, значение в семафоре, должно быть уменьшено на единицу, и увеличено, когда работа с данными будет прекращена. Если ресурс эксклюзивный, то есть к данным должен иметь доступ только один процесс, то начальное значение в семафоре следует установить единицей.
Семафоры можно использовать и для других целей, например для счётчика ресурсов. В этом случае число в семафоре — количество свободных ресурсов (например количество свободных ячеек памяти).
Применение семафоров
Вот некоторые из проблем, которые могут решать семафоры.
· запрет одновременного выполнения заданных участков кода;
· поочерёдный доступ к критическому ресурсу (важному ресурсу, для которого невозможен одновременный доступ).
Следующий пример показывает, как наладить поочерёдный доступ к консоли.
semaphore.init(1);Поток 1:semaphore.enter();cout << "Состояние массива: ";for (int i=0; i<n; i++) cout << a[i] << ' ';cout << '\n';semaphore.leave();Поток 2:semaphore.enter();cout << "Нажато Esc.\n";semaphore.leave();Этот код поможет предотвратить появление листинга наподобие
Состояние массива: 1 2 3 Нажато Esc.4 5 6Семафори в мовах програмування і ОС
Семафори — високорівневий механізм взаємних виключень, який може надаватися мовою програмування або ОС. Здається першою мовою програмування, що отримала семафори, став Algol-68. Примітиви, які ми назвали wait і signal, в Algol-68 отримали імена down і up відповідно.
Інша класична мова програмування, що підтримує синхронізацію процесів за
допомогою семафорів, – Modula-2. Рекомендований автором мови Н. Віртом як стандартний модуль визначень Processes приведений в ліст. 3.7:
Лістинг 3.7.
DEFINITION MODULE Processes;
TYPE SIGNAL;
PROCEDURE StartProcess(P:PROC; n:CARDINAL); (* Почати паралельний процес, що задається програмою Р з робочою областю розміром n *)
PROCEDURE SEND(VAR s:SIGNAL); (* Відновлює один з процесів,
що чекають на s *)
PROCEDURE WAIT(VAR s:SIGNAL); (* Чекати поки не пришлють сигнал s *)
PROCEDURE Awaited(VAR s:SIGNAL): BOOLEAN; (* Якщо TRUE –
хоча б один процес чекає на s *)
PROCEDURE Init(VAR s:SIGNAL); (* Обов'язкова ініціалізація *)
END Processes.
Відзначимо наявність процедури обов'язкової ініціалізації семафора Init і неблокуючу процедуру перевірки черги процесів, що очікують на семафор Awaited.
Що стосується сучасних систем програмування на мовах C/C++, то вони, як правило, мають в своєму складі бібліотеки підтримки засобів синхронізації процесів які спираються на можливості, що надаються ОС. Так наприклад, бібліотека MFC фірми Microsoft містить класи CSemaphore і CMutex, що надають механізми семафорів і м'ютексів для багатопотокових застосувань.
Розгляд підтримки взаємних виключень засобами ОС почнемо з систем сімейства UNIX.
Системні виклики для управління потоками в UNIX-подібних ОС стандартизовані в частині стандарту POSIX (P1003.1c). Стандартом не обумовлюється спосіб реалізації викликів, так що вони можуть бути як справжніми викликами сервісів ядра системи, так і викликами бібліотечних функцій, що працюють в просторі користувача.
Деякі виклики стандарту POSIX для роботи з семафорами
| Таблиця 3.2. Виклик | Опис |
| pthread_mutex_init | Створює новий м'ютекс |
| pthread_mutex_destroy | Знищує м'ютекс |
| pthread_mutex_lock | Захоплення м'ютекса (див. wait) |
| pthread_mutex_unlock | Звільнення м'ютекса (див. signal) |
| sem_init | Ініціалізація семафору |
| sem_wait | Зменшує значення лічильника (див. wait) |
| sem_post | Збільшує значення лічильника (див. signal) |
| sem_getvalue | Читає поточне значення лічильника семафору |
Вопрос2
Задача виробника/споживача
Однією з фундаментальних задач паралельних обчислень є задача виробника/споживача. Важливість цієї задачі зокрема зумовлена тим, що ядру будь-якої ОС доводиться розвязувати її безліч разів. Задача формулюється так: є один або кілька виробників, що генерують дані (елементи) деякого типу (витратний ресурс) і поміщають їх в буфер (повторно використовуваний ресурс) і єдиний споживач, який вибирає з буфера елементи поодинці і використовує їх. Потрібно захистити програмну систему від перекриття операцій з буфером, тобто забезпечити одночасний доступ до буфера тільки для одного процесу.
Можна запропонувати багато вирішень з використанням тих або інших засобів синхронізації. Одне з них приведене в ліст. 3.9:
Лістинг 3.9.
#include <pthread.h> // Оголошення POSIX-функцій для потоків
#include <semaphore.h> // Оголошення POSIX-функцій для семафорів
const int SizeOfBuffer = 64; // Такого розміру буде буфер
pthread_t PRODUCERID, CONSUMERID; // Ідентифікатори потоків
sem_t s; // Цей семафор захищає буфер
sem_t occupied; // Кількість елементів в буфері
sem_t available; // Розмір вільного місця в буфері
char chin, chout; // Глобальні змінні для символів
char Buffer[SizeOfBuffer]; // Ось він буфер для символів
void Produce() { /* Тут реалізація виробництва елементу chin */ }
void Consume() { /* Тут реалізація використання елементу chout */ }
void Producer() { // Це «оболонка безпеки» для процедури виробника
static int NextFree = 0;
while(true){
Produce(); // ВИРОБНИЦТВО ЕЛЕМЕНТУ
sem_wait(&available); // Чекаємо на вільне місце в буфері sem_wait(&s); // і намагаємося отримати доступ до нього
Buffer[NextFree]= chin; // елемент в кільцевий буфер
NextFree = (NextFree + 1) % SizeOfBuffer;
sem_post(&s); // Кінець критичного розділу
sem_post(&occupied); // Плюс один елемент в буфері
}
void Consumer() { // Це «оболонка безпеки» для процедури споживача
static int NextChar = 0;
while(true){
sem_wait(&occupied); // Чекаємо хоча б одного елементу в буфері sem_wait(&s); // і намагаємося отримати доступ до нього
chout = Buffer[NextChar]; // вибирати з буфера
NextChar = (NextChar + 1) % SizeOfBuffer;
sem_post(&s); // Кінець критичного розділу
sem_post(&available); // Плюс одне вільне місце в буфері
Consume(); // ВИКОРИСТАННЯ ЕЛЕМЕНТУ
}
void main() {
/* ІНІЦІАЛІЗУЄМО СЕМАФОРИ: */
sem_init(&s, 0, 1); // Буфер доступний
sem_init(&occupied, 0, 0); // Спочатку в буфері немає нічого, sem_init(&available, 0, SizeOfBuffer); // тобто от стільки місця
/* І СТАРТУЄМО ПОТОКИ: */
pthread_create(&PRODUCERID, NULL, Producer, NULL);
pthread_create(&CONSUMERID, NULL, Consumer, NULL);
} // Для тих, хто забув: NULL – це нульовий покажчик
Тут для взаємних виключень при роботі з кільцевим буфером виробника і споживача використані семафори-лічильники в стандарті POSIX. Після деякого доопрацювання програму можна відкомпілювати і виконати наприклад в ОС Linux. Відмітьте, що з трьох семафорів тільки один використовується “по прямому призначенню”. Подумайте, як можна обійтися без двох інших, не вводячи додаткових змінних.
Вариант4
Вопрос1
Засоби взаємних виключень та синхронізації процесів
3.9.1. Програмний підхід
Програмний підхід до реалізації взаємних виключень полягає в програмуванні критичних розділів таким чином, щоб вони відповідали викладеним вище вимогам. Подивимось наскільки це просто (чи складно). Напишемо перший варіант взаємного виключення скажімо так.
Лістинг 3.1.
boolean flag = false; /* змінна блокування */
/* Процесс 1 */ /* Процесс 2 */
while(flag); /*АКТИВНЕ ОЧІКУВАННЯ*/ while(flag);
flag = true; flag = true;
/* КРИТИЧНИЙ РОЗДІЛ */ /* КРИТИЧНИЙ РОЗДІЛ */
flag = false; flag = false;
/* РЕШТА КОДУ */ /* РЕШТА КОДУ */
Тут flag– глобальна змінна, яка. управляє доступом до критичного розділу для всіх процесів. Такі змінні називаються змінними блокування. Недолік алгоритмів такого типу – наявність стану активного очікування, тобто ситуації коли в очікуванні можливості входу в критичний розділ процес безцільно споживає процесорний час виконуючи постійні перевірки стану змінної блокування. Блокування, що використовує активне очікування, називається спін-блокуванням (spinlock).
На жаль, приведений приклад (ліст. 3.1.) непрацездатний. Причину знайти неважко — припустимо процес 1 виконав перевірку змінної flag, вийшов із циклу і був переведений диспетчером в стан готового до виконання не встигнувши виставити ознаку зайнятості критичного розділу. Далі продовжив виконуватись процес 2, який також виконує перевірку змінної блокування. Оскільки значення flag, все ще false, він входить в критичний розділ і теж переривається. Тепер перший процес, продовжуючи свою роботу, також опиниться в критичному розділі! Проблема виявляється в тому, що виконання процесу може бути перерване між перевіркою змінної блокування та її установкою. Задача виявилась зовсім не простою. Першим задовільне програмне рішення задачі взаємного виключення для двох процесів отримав Деккер (T. Dekker). Більш простій алгоритм був запропонований в 1981 р. Петерсоном (G.L. Peterson). Детальніше обидва алгоритми розглядаються в [2].
3.9.2. Апаратна підтримка
В однопроцесорній системі для того, щоб гарантувати взаємне виключення досить захистити процес від переривання його роботи на час перебування в критичному розділі. При цьому структура програми виглядає так (ліст. 3.2.).
Лістинг 3.2.
/* БЕЗПЕЧНИЙ КОД */;
/* Заборона апаратних переривань */;
/* КРИТИЧНИЙ РОЗДІЛ */;
/* Дозвіл апаратних переривань */;
/* БЕЗПЕЧНИЙ КОД */;
Недоліки такого підходу: неможливість ефективної роботи диспетчера (ми його просто відключили) і неможливість застосування такого підходу в багатопроцесорній архітектурі (подумайте, чому).
Значно кращі результати дає використання спеціальних машинних команд. Усунути
проблему з ліст. 3.1 можна, наприклад, об'єднанням перевірки стану змінної блокування і установки її значення в одній машинній операції. В цьому випадку забезпечується коректний вхід в критичний розділ будь-якого процесу, що виконується в одно- або багатопроцесорній системі, оскільки елемент пам'яті, що зберігає змінну блокування, на час машинного циклу виявляється захищеним від доступу до нього з боку решти процесорів.
Алгоритм операції перевірки і установки значення наприклад такий як на ліст. 3.3.
Лістинг 3.3.
boolean testset(int i){
if(i==0){
i=1;
Return true;
}
Else
Return false;
}
Все це виглядає як одна машинна команда (т. зв. атомарна операція). У деталях реалізація команди testsetна різних комп'ютерах може відрізнятися. Так, процесори сімейства Pentium мають команду CMPXCHG reg/mem,reg1(порівняти і замінити), що використовує три операнди: операнд-джерело в регістрі reg1, операнд призначення в регістрі або в пам'яті reg/memі акумулятор (регістр EAX). Якщо значення в приймачі і в акумуляторі рівні, операнд призначення замінюється на операнд-джерело. Інакше початкове значення операнда призначення завантажується в акумулятор.
На ліст. 3.4 приведений приклад реалізації взаємних виключень через спін-блокування з використанням інструкції перевірки і установки:
Лістинг 3.4.
const int n = /* кількість паралельних процесів */;
Int bvar;
void P(int i){
while(1){
while(!testset(bvar)); /* АКТИВНЕ ОЧІКУВАННЯ */
/* Критичний розділ */;
bvar = 0;
/* Решта коду */;
}
void main(){
bvar = 0;
parbegin(P(1),P(2),...,P(n)); /* Стартуємо паралельні процеси */
}
Переваги підходу з використанням апаратної підтримки:
Застосовується до будь-якої кількості процесів як в одно-, так і в багатопроцесорних системах.
Простий, а тому легко перевіряється.
Може використовуватися для підтримки багатьох критичних розділів (для кожного з них виділяється власна змінна блокування).
Недоліки:
Використовується перечікування зайнятості. Тобто в очікуванні входу в критичний розділ процес продовжує споживати процесорний час.
Можливе голодування. Якщо процес покидає критичний розділ, а в черзі на вхід чекають кілька інших, то вибір “щасливчика” довільний.
Можливе взаємне блокування.
Можливість взаємного блокування пояснимо на такому прикладі. Нехай процес Р1
виконує testset і входить в критичний розділ, а потім Р1 переривається процесом Р2 з вищим пріоритетом. Якщо Р2 спробує звернутися до того ж ресурсу, йому буде відмовлено і він увійде в цикл очікування. Проте і Р1 не може продовжити виконання, оскільки є активний процес з більш високим пріоритетом (т. зв. проблема інверсії пріоритетів).
Спін-блокування як простий і ефективний механізм синхронізації потоків широко використовується в ядрах ОС. Проблема перечікування зайнятості там стоїть не так гостро з тієї причини, що спін-блокування використовують для доступу до ресурсів на короткий час, а отже і очікувати їх вивільнення недовго. Але залишається проблема інверсії пріоритетів. Розглянемо її вирішення на прикладі ОС сімейства Windows NT.
В ядрі Windows NT спін-блокування призначені в основному для захисту даних, доступ до яких проводиться на підвищених рівнях IRQL (Interrupt ReQuest Level – рівні запитів переривань). Для вирішення можливої проблеми інверсії пріоритетів потрібний механізм, що не дозволяє коду з деяким рівнем IRQL переривати код з нижчим рівнем IRQL в той момент, коли останній володіє спін-блокуванням. Таким механізмом є підвищення поточного рівня IRQL потоку у момент захоплення ним спін-блокування до деякого рівня, що асоціюється із даним спін-блокуванням, і відновлення колишнього IRQL потоку після його звільнення. Код, що працює на підвищеному рівні IRQL, не має права звертатися до ресурсу, захищеного спін-блокуванням у якого рівень IRQL нижчий, ніж у самого викликаючого коду.
Вопрос2
Задача читачів/письменників
Іншою класичною задачею паралельних обчислень є задача читачів/письменників. Вона формулюється таким чином. Є багаторазовий ресурс (наприклад, файл бази даних) і невизначена кількість процесів одні з яких тільки читають зміст файлу (читачі), а інші можуть як читати, так і вносити зміни (письменники). Кілька читачів можуть одночасно працювати з ресурсом, а для письменника потрібен монопольний доступ. При вирішенні цієї задачі можна віддати приоритет на право доступу до ресурсу читачам чи письменникам. В першому випадку новий процес-читач отримає доступ до ресурсу, з яким уже працює інший читач, навіть якщо в черзі є процес-письменник. При приоритеті на запис допуск нових читачів до ресурсу призупиняється як тільки в черзі з'являється процес-письменник.
Досить просте вирішення задачі запропонував H. Ballhausen із Інституту теоретичної фізики Гейдельбергського університету (Ліст. 3.10.).
Лістинг 3.10.
var semaphore mutex = 1; // семафор взаємовиключення
var semaphore access = m; // семафор для умовної синхронізації
process reader( integer i = 1 ... m ) { // може бути до m читачів
do {
Wait(access);
// ... ЧИТАЄМО ...
Signal(access);
// ... інші операції ...
}
}
process writer( integer j = 1 ... n ) { // може бути до n письменників
integer k;
do {
wait(mutex); // заборонили вхід іншому письменнику
for k = 1 ... m do wait(access); // забороняємо вхід
// новим читачам і чекаємо виходу решти
// ... ПИШЕМО ...
for k = 1 ... m do signal(access);
signal(mutex);
// ... інші операції ...
}
}
void main(){
// Стартуємо паралельні процеси:
parbegin(reader(1),...,reader(m),writer(1),...,writer(n));
}
Задача читачів/письменників на практиці зустрічається настільки часто, що деякі ОС навіть мають призначені для неї спеціалізовані примітиви синхронізації.
Вариант 5 Вопрос 1
Механізми захисту ресурсів
Отже не важко прийти до висновку – глобальні змінні, що розділяються (тобто використовуються спільно кількома процесами), як і інші глобальні ресурси, потребують захисту. Єдиний спосіб зробити це – управляти кодом, що здійснює доступ до цих ресурсів.
Для подальшого викладу істотно, що способи взаємодії процесів відносно ресурсів, доступ до яких вони розділяють між собою, можна класифікувати по ступеню обізнаності один про одного [2] як показано в Табл. 3.1.
Види взаємодії процесів
| Таблиця 3.1. Ступінь обізнаності | Вид взаємодії | Вплив одного процесу на на іншій | Потенційні проблеми |
| Процеси не обізнані про наявність один одного. | Спостерігається конкуренція за володінням ресурсом. | Результат роботи одного процесу не залежить від дій інших. Можливий вплив роботи одного процесу на час роботи іншого. | Необхідність взаємних виключень. Взаємне блокування (для повторно використовуваних ресурсів). Голодування. |
| Процеси побічно обізнані про наявність один одного. | Співпраця з використанням розділення ресурсів. | Результат роботи одного процесу може залежати від інформації, отриманої від інших процесів (через ресурси, що розділяються). Можливий вплив роботи одного процесу на час роботи іншого. | Необхідність взаємних виключень. Взаємне блокування (для повторно використовуваних ресурсів). Голодування. Зв'язок даних. |
| Процеси безпосередньо обізнані про наявність один одного (знають імена). | Співпраця з використанням зв'язку. | Результат роботи одного процесу може залежати від інформації, отриманої від інших процесів. Можливий вплив роботи одного процесу на час роботи іншого. | Взаємне блокування (для витратних ресурсів). Голодування. |
Якщо процес не знає про можливість існування інших процесів, він вважає всі наявні ресурси своєю власністю. Такі процеси конкурують за монопольний доступ до ресурсів. Єдиним арбітром в цій конкурентній боротьбі є ОС.
У разі конкуренції процесів ми стикаємося з трьома проблемами:
Необхідність взаємних виключень (mutual exclusion) - тобто виключення процесом, який дістав доступ до ресурсу, що розділяється, можливості одночасного доступу до цього ресурсу для решти процесів. При цьому такий ресурс називають критичним ресурсом, а частину програми, яка його використовує, називають критичним розділом (секцією) (critical section). Украй важливо, щоб в критичному розділі у будь-який момент могла знаходитися тільки одна програма. Здійснення взаємних виключень створює дві додаткові проблеми:
Взаємне блокування (deadlock). Наприклад, два процеси Р1 і Р2 для свого виконання мають потребу в двох одних і тих же ресурсах R1 і R2 одночасно. При цьому кожний з них утримує по одному ресурсу (наприклад так: P1 – R1, P2 – R2) і безуспішно намагається захопити інший.
Голодування (starvation). Нехай три процеси Р1, Р2, Р3 періодично потребують одного і того ж ресурсу. Теоретично можлива ситуація при якій доступ до ресурсу отримуватимуть Р1 і Р2 в порядку черговості, а Р3 ніколи не отримає доступу до нього, хоча ніякого взаємного блокування немає.
Треба розуміти, що взаємні виключення в даному випадку є базовим механізмом захисту даних, а взаємні блокування і голодування — його неприємними наслідками.
Якщо процес припускає наявність в системі інших процесів (процеси побічно обізнані про наявність один одного), він може демонструвати тактику співпраці, приймаючи заходи до підтримки цілісності спільно використовуваних ресурсів.
Коли ж процеси безпосередньо обізнані про наявність один одного (це також зазвичай справедливо для потоків одного процесу), вони здатні спілкуватися з використанням “імен” процесів і з самого початку створені для спільної роботи з використанням зв'язку. Зв'язок забезпечує можливість синхронізації або координації дій процесів. Зазвичай можна вважати, що зв'язок складається з посилки повідомлень певного типу. Примітиви для відправлення і отримання повідомлень надаються мовою програмування або ядром ОС. При цьому можна обійтись без взаємних виключень, проте проблеми взаємних блокувань і голодування залишаються. Так, наприклад, два процеси можуть заблокуватся взаємним очікуванням повідомлень один від одного. В ролі ресурсів в даному випадку виступають ті ж повідомлення — це витратний ресурс.
Отже в більшості випадків без взаємних виключень не обійтися. Втім, будь-яка можливість підтримки взаємних виключень повинна відповідати таким вимогам:
Взаємні виключення повинні здійснюватися в примусовому порядку.
Процес, що завершує (перериває) роботу поза критичним розділом, не повинен впливати на інші процеси.
Не повинна виникати ситуація нескінченного очікування входу в критичний розділ (виключення взаємних блокувань і голодування).
Коли в критичному розділі немає жодного процесу, будь-який процес, що запросив можливість входу в нього, повинен негайно її отримати.
Не робиться ніяких припущень щодо кількості процесів або їх відносних швидкостей виконання.
Процес залишається в критичному розділі тільки протягом обмеженого часу.
Розроблені і використовуються ряд підходів до реалізації цих вимог:
Передача відповідальності за відповідність вимогам самому процесу (програмний підхід).
Використання машинних команд спеціального призначення.
Надання певного рівня підтримки з боку мови програмування або ОС.
Вопрос2
Mutex позволяет проводить синхронизацию не только между потоками(thread), но и процессами(process), то есть между приложениями.
Данный объект синхронизации регистрирует доступ к ресурсам и может находиться в двух состояниях:
· установлен
· сброшен
Mutex - установлен в тот момент когда ресурс свободен. Если к объекту есть доступ, то говорят, что сброшен. Для работы с Mutex есть ряд функций. Сначала объект нужно создать CreateMutex(), для доступаOpenMutex(), а для освобождения ресурса ReleaseMutex(). Для доступа к объекту Mutex используется ожидающая функция WaitForSingleObject(). Тонкость здесь следующая. Каждая программа создает объектMutex по имени. То есть Mutex это именованный объект. А если такой объект синхронизации уже создала другая программа, то по вызову CreateMutex() мы получим указатель на объект, который уже создала первая программа. То есть у обоих программ будет один и тот же объект. Вот это и позволяет производить синхронизацию.
Мьютекс (взаимоисключение, mutex) - это объект синхронизации, который устанавливается в особое сигнальное состояние, когда не занят каким-либо потоком. Только один поток владеет этим объектом в любой момент времени, отсюда и название таких объектов - одновременный доступ к общему ресурсу исключается. Например, чтобы исключить запись двух потоков в общий участок памяти в одно и то же время, каждый поток ожидает, когда освободится мьютекс, становится его владельцем и только потом пишет что-либо в этот участок памяти. После всех необходимых действий мьютекс освобождается, предоставляя другим потокам доступ к общему ресурсу.
Два (или более) процесса могут создать мьютекс с одним и тем же именем, вызвав метод CreateMutex . Первый процесс действительно создает мьютекс, а следующие процессы получают хэндл уже существующего объекта. Это дает возможность нескольким процессам получить хэндл одного и того же мьютекса, освобождая программиста от необходимости заботиться о том, кто в действительности создает мьютекс. Если используется такой подход, желательно установить флаг bInitialOwner в FALSE, иначе возникнут определенные трудности при определении действительного создателя мьютекса.
Несколько процессов могут получить хэндл одного и того же мьютекса, что делает возможным взаимодействие между процессами. Вы можете использовать следующие механизмы такого подхода:
- Дочерний процесс, созданный при помощи функции CreateProcess может наследовать хэндл мьютекса в случае, если при его (мьютекса) создании функией CreateMutex был указан параметр lpMutexAttributes .
- Процесс может получить дубликат существующего мьютекса с помощью функции DuplicateHandle .
- Процесс может указать имя существующего мьютекса при вызове функций OpenMutex или CreateMutex .
Вообще говоря, если вы синхронизируете потоки одного процесса, более эффективным подходом является использование критических секций.
#include <windows.h>#include <process.h>
#include <stdio.h>
HANDLE hMutex;
int a[ 5 ];
void Thread( void* pParams )
{
int i, num = 0;
while ( TRUE )
{
WaitForSingleObject( hMutex, INFINITE );
for ( i = 0; i < 5; i++ ) a[ i ] = num;
ReleaseMutex( hMutex );
num++;
}
}
int main( void )
{
hMutex = CreateMutex( NULL, FALSE, NULL );
_beginthread( Thread, 0, NULL );
while( TRUE )
{
WaitForSingleObject( hMutex, INFINITE );
printf( "%d %d %d %d %d\n",
a[ 0 ], a[ 1 ], a[ 2 ],
a[ 3 ], a[ 4 ] );
ReleaseMutex( hMutex );
}
return 0;
}