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

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

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

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

Листинг 2.8. Неверное решение проблемы обедающих философов

#define N 5 /* Количество философов */

void philosospher(int i) /* i - номер философа, от О до 4 */

while(TRUE) {

thinkO: /* Философ размышляет */

take fогк(i): /* Берет левую вилку */

take fork((i+l) * N): /* Берет правую вилку */ eatO: /* Спагетти, ням-ням */

put fork(i): /* Кладет на стол левую вилку */

put fork((i+l) * N): /* Кладет на стол правую вилку */

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

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



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

В листинг 2.8 можно внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию up на переменной mutex. С теоретической точки зрения решение вполне подходит. С позиций практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам.

Решение, представленное в листинге 2.9, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа г определяются макросами LEFT и RIGHT (то есть если i = 2, то LEinr = 1 и RIGHT = 3).

Листинг 2.9. Решение задачи обедающих философов

#define N #define LEFT #define RIGHT #define THINKING #define HUNGRY #define EATING

(i+N.l)*N

(i+l)*N

/* Количество философов */

/* Номер левого соседа философа с номером i */

/* Номер правого соседа философа с номером i */

typedef int semaphore:

int state[N]:

semaphore mutex - 1: semaphore s[N]:

void philosopher(int i) {

while (TRUE) { thinkO: take forks(i): eatO:

put forks(i):

Философ размышляет */ Философ пытается получить вилки */ Философ ест */

Семафоры - особый вид целочисленных переменных */

Массив для отслеживания состояния каждого /* философа */

/* Взаимоисключение для критических областей */ /* Каждому философу по семафору */

/* i - номер философа, от О до N-1 */

/* Повторять до бесконечности */

/* Философ размышляет */

/* Получает две вилки или блокируется */

/* Спагетти, ням-ням */

/* Кладет на стол обе вилки */

void take forks(int i) {

downC&mutex): state:i] = HUNGRY: test(i): up(&mutex): down(&s[i]):

/* i - номер философа, от О до N-l*/

/* Вход в критическую область */

/* Фиксация наличия голодного философа */

/* Попытка получить две вилки */

/* Выход из критической области */

/* Блокировка, если вилок не досталось */



void put forks(i) {

down(&mutex); stateCi] = THINKING: test(LEFT): test(RIGHT): upC&mutex):

/* 1 - номер философа, от О до N-1*/

/* Вход в критическую область */

/* Философ перестал есть */

/* Проверить, может ли есть сосед слева */

/* Проверить, может ли есть сосед справа */

/* Выход из критической области */

void test(i)

/* i - номер философа, от О до N-1*/

state[RIGHT] != EATING) {

if (state[i] == HUNGRY && state[LEFT] != EATING state[i] = EATING: up(&s[i]):

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

2.3.2. Проблема читателей и писателей

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

Листинг 2.10. Решение проблемы читателей и писателей

typedef int semaphore; semaphore mutex = 1: semaphore db = 1: int rc = 0:

/* Воспользуйтесь своим воображением */

/* Контроль доступа к гс */

/* Контроль доступа к базе данных */

/* Количество процессов, читающих или желающих */

/* читать */

void reader(void) {

while (TRUE) { down(&mutex): rc = rc+1:

if (rc == 1) down(&db): up(&mutex): read data base(): down(&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.
Копирование материалов разрешено исключительно при условии цититирования.