10.1.Введение

10.1.Введение

Семафор представляет собой простейшее средство синхронизации процессов и потоков. Мы рассматриваем три типа семафоров:

? именованные семафоры Posix, идентифицируемые именами, соответствующими стандарту Posix для IPC (см. раздел 2.2);

? размещаемые в разделяемой памяти семафоры Posix;

? семафоры System V (глава 11), обслуживаемые ядром.

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

Рис. 10.1. Два процесса взаимодействуют с помощью бинарного семафора

На этом рисунке изображен бинарный семафор, хранящийся в ядре (семафор System V).

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

Рис. 10.2. Два процесса, использующие бинарный именованный семафор Posix

ПРИМЕЧАНИЕ

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

На рис. 10.1 и 10.2 мы указали три операции, которые могут быть применены к семафорам:

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

2. Ожидание изменения значения семафора (wait). При этом производится проверка его значения и процесс блокируется, если значение оказывается меньшим либо равным 0, а при превышении 0 значение уменьшается на 1. Это может быть записано на псевдокоде как

while (semaphore_value <= 0); /* wait: т.е. поток или процесс блокируется */

semaphore_value--; /* семафор разрешает выполнение операций */

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

У этой операции есть несколько общеупотребительных имен. Изначально она называлась Р, от голландского proben (проверка, попытка), — это название было введено Эдсгером Дейкстрой. Используются также и термины down (поскольку значение семафора уменьшается) и lock, но мы будем следовать стандарту Posix и говорить об ожидании (wait). 

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

semaphore_value++;

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

Для этой операции также имеется несколько общеупотребительных терминов. Изначально она называлась V, от голландского verhogen (увеличивать). Называют ее up (значение семафора увеличивается), unlock и signal. Мы, следуя стандарту Posix, называем эту операцию post.

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

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

ПРИМЕЧАНИЕ

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

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

Листинг 10.1. Сравнение бинарных семафоров и взаимных исключений

инициализация взаимного исключения;  инициализация семафора единицей;

pthread_mutex_lock(&mutex);          sem_wait(&sem);

критическая область                  критическая область

pthread_mutex_unlock(&mutex);        sem_post(&sem);

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

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

Рис. 10.3. Задача производителя и потребителя с общим буфером

В листинге 10.2 приведен текст соответствующей программы на псевдокоде.

Листинг 10.2. Псевдокод для задачи производителя и потребителя

Producer                                Consumer

инициализация семафора get значением 0;

инициализация семафора put значением 1;

for (;;) {                              for (;;) {

 sem_wait(&put);                         sem_wait(&get);

 помещение данных в буфер;               обработка данных в буфере;

 sem_post(&get);                         sem_post(&put);

}                                       }

Семафор put oгрaничивaeт возможность помещения объекта в общий буфер, а семафор get управляет потребителем при считывании объекта из буфера. Работает эта пpoгрaммa в такой последовательности:

1. Производитель инициализирует буфер и два семафора.

2. Пусть после этого запускается потребитель. Он блокируется при вызове sem_wait, поскольку семафор get имеет значение 0.

3. После этого запускается производитель. При вызове sem_wait значение put уменьшается с 1 до 0, после чего производитель помещает объект в буфер. Вызовом sem_post значение семафора get увеличивается с 0 до 1. Поскольку имеется поток, заблокированный в ожидании изменения значения этого семафора, этот поток помечается как готовый к выполнению. Предположим, тем не менее, что производитель продолжает выполняться. В этом случае он блокируется при вызове sem_wait в начале цикла for, поскольку значение семафора put — 0. Производитель должен подождать, пока потребитель не извлечет данные из буфера.

4. Потребитель возвращается из sem_wait, уменьшая значение семафора get с 0 до 1. Затем он обрабатывает данные в буфере и вызывает sem_post, увеличивая значение put с 0 до 1. Заблокированный в ожидании изменения значения этого семафора поток-производитель помечается как готовый к выполнению. Предположим опять, что выполнение потребителя продолжается. Тогда он блокируется при вызове sem_wait в начале цикла for, поскольку семафор get имеет значение 0.

5. Производитель возвращается из sem_wait, помещает данные в буфер, и все повторяется.

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

Перечислим три главных отличия семафоров и взаимных исключений в паре с условными переменными:

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

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

3. Поскольку состояние семафора хранится в определенной переменной, изменение его значения оказывает влияние на процессы, которые вызовут функцию wait уже после этого изменения, тогда как при отправке сигнала по условной переменной в отсутствие ожидающих его потоков сигнал будет утерян. Взгляните на листинг 10.2 и представьте, что при первом проходе цикла производителем потребитель еще не вызвал sem_wait. Производитель сможет поместить объект в буфер, вызвать sem_post для семафора get (увеличивая его значение с 0 до 1), а затем он заблокируется в вызове sem_wait для семафора put. Через некоторое время потребитель дойдет до цикла for и вызовет sem_wait для переменной get, что уменьшит значение этого семафора с 1 до 0, а затем потребитель приступит к обработке содержимого буфера.

ПРИМЕЧАНИЕ

В Обосновании Posix.1 (Rationale) содержится следующий комментарий по поводу добавления семафоров помимо взаимных исключений и условных переменных: «Семафоры включены в стандарт в первую очередь с целью предоставить средства синхронизации выполнения процессов; эти процессы могут и не использовать общий сегмент памяти. Взаимные исключения и условные переменные описаны как средства синхронизации потоков, у которых всегда есть некоторое количество общей памяти. Оба метода широко используются уже много лет. Каждое из этих простейших средств имеет свой предпочтительный круг задач». В разделе 10.15 мы увидим, что для реализации семафоров-счетчиков с живучестью ядра требуется написать около 300 строк кода на С, использующего взаимные исключения и условные переменные. Несмотря на предпочтительность применения семафоров для синхронизации между процессами и взаимных исключений для синхронизации между потоками, и те и другие могут использоваться в обоих случаях. Следует пользоваться тем набором средств, который удобен в данном приложении.

Выше мы отмечали, что стандартом Posix описано два типа семафоров: именованные (named) и размещаемые в памяти (memory-based или unnamed). На рис. 10.4 сравниваются функции, используемые обоими типами семафоров.

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

Рис. 10.4. Вызовы для семафоров Posix

Рис. 10.5. Семафор, размещенный в общей памяти двух потоков

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

Рис. 10.6. Семафор, размещенный в разделяемой двумя процессами памяти

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

Мы рассмотрим три реализации именованных семафоров Posix: с использованием каналов FIFO, отображаемых в память файлов и семафоров System V. 

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

Следующая глава >

Похожие главы из других книг

Введение

Из книги Язык программирования С# 2005 и платформа .NET 2.0. [3-е издание] автора Троелсен Эндрю

Введение Я помню время, много лет тому назад, когда я предложил издательству Apress книгу, посвященную еще не выпущенному на тот момент пакету инструментальных средств разработки под названием Next Generation Windows Services (NGWS - сервисы Windows следующего поколения). Вы, наверное, знаете,


Введение

Из книги Delphi. Учимся на примерах автора Парижский Сергей Михайлович

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


Введение

Из книги Эффективное делопроизводство автора Пташинский Владимир Сергеевич

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


Введение

Из книги Excel. Мультимедийный курс автора Мединов Олег

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


Введение

Из книги Office 2007. Мультимедийный курс автора Мединов Олег

Введение По своей популярности пакет офисных приложений Microsoft Office может сравниться, пожалуй, лишь с операционной системой Windows. Его активно используют школьники и студенты, бухгалтеры и топ-менеджеры, ИТ-специалисты и писатели, руководители и офисные сотрудники. Сегодня


Введение

Из книги 3ds Max 2008 для дизайна интерьеров автора Семак Рита

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


Введение

Из книги Эффективное использование STL автора Мейерс Скотт

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


Введение

Из книги MySQL: руководство профессионала автора Паутов Алексей В

Введение Это не совсем книга. Просто по ходу работы и изучения пакета у меня накопилось немало заметок, которые я в конце концов собрал воедино и опубликовал с оглавлением и под единым названием.Данные заметки относятся к версиям 4 и 5 пакета MySQL. По ходу текста особо


10.0. Введение

Из книги C++. Сборник рецептов автора Диггинс Кристофер

10.0. Введение Потоки (streams) являются одной из самых мощных (и сложных) компонент стандартной библиотеки С++. Их применение при простом, неформатированном вводе-выводе в целом не представляет трудностей, однако ситуация усложняется, если необходимо изменить формат с помощью


11.0. Введение

Из книги MySQL 5.0. Библиотека программиста автора Гольцман Виктор Иосифович

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


12.0. Введение

Из книги Photoshop CS4 автора Жвалевский Андрей Валентинович

12.0. Введение В данной главе даются рецепты написания многопоточных программ на C++ с использованием библиотеки Boost Threads, автором которой является Вильям Кемпф (William Kempf). Boost — это набор переносимых, высокопроизводительных библиотек с открытым исходным кодом, неоднократно


13.0. Введение

Из книги автора

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


14.0. Введение

Из книги автора

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


15.0. Введение

Из книги автора

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


Введение

Из книги автора

Введение MySQL – это система управления базами данных (СУБД) с открытым кодом. Это высокопроизводительная и масштабируемая СУБД с множеством программных интерфейсов. Она обладает огромными функциональными возможностями и подходит для решения самых разных задач.Данная


Введение

Из книги автора

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