Главная страница  Межпроцессное взаимодействие (состязание) 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 [ 29 ] 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

ГС = гс-1; /* Одним читающим процессом меньше */

if (гс == 0) up(&db): /* Если этот читающий процесс -/*

/* последний... */ up(&mutex); /* Отказ от монопольного доступа к гс */

use data read(): /* Вне критической области */

void writer(void) {

while (TRUE) { /* Повторять до бесконечности */

think up data(); /* Вне критической области */

down(&db); /* Получение монопольного доступа */

write data base(); /* Запись данных */

up(&db): /* Отказ от монопольного доступа */

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

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

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

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

2.3.3. Проблема спящего брадобрея

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



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


Рис. 2.8. Спящий брадобрей

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



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

Решение представлено в листинге 2.11. Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает, как показано на рис. 2.8, и спит, пока не придет первый клиент.

Листинг 2.11. Решение проблемы спящего брадобрея

#define CHAIRS 5 /* Количество стульев для посетителей */

typedef int semaphore:

semaphore customers = 0: semaphore barbers = 0: semaphore mutex = 1: int waiting = 0:

void barber(void) {

while (TRUE) { down(&customers); down(&mutex): waiting = waiting up(&barbers): up(&mutex); cut hair():

/* Догадайтесь сами */

/* Количество ожидающих посетителей */

/* Количество брадобреев, ждущих клиентов */

/* Для взаимного исключения */

/* Ожидающие (не обслуживаемые) посетители */

/* Если посетителей нет. уйти в состояние ожидания */ /* Запрос доступа к waiting */ - 1: /* Уменьшение числа ожидающих посетителей */ /* Один брадобрей готов к работе */ /* Отказ от доступа к waiting */ /* Клиента обслуживают (вне критической области)*/

void customer(void) {

down(&mutex):

if (waiting < CHAIRS) { waiting = waiting + up(&customers): up(&mutex): down(&barbers); get haircut():

} else { up(&mutex);

/* Вход в критическую область */ /* Если свободных стульев нет. придется уйти */ 1: /* Увеличение числа ожидающих посетителей */ /* При необходимости разбудить брадобрея */ /* Отказ от доступа к waiting */ /* Если брадобрей занят, уйти в состояние ожидания */ /* Клиента усаживают и обслуживают */

/* Много посетителей, из парикмахерской придется уйти */

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

Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем самым активизируя поток брадобрея. В этот момент оба - посетитель и брадобрей - активны. Когда посетитель освобождает доступ к mutex, брадобрей



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 [ 29 ] 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

© 2000 - 2018 ULTRASONEX-AMFODENT.RU.
Копирование материалов разрешено исключительно при условии цититирования.