Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
У. Столлингс ГЛАВА 6 Межзадачное взаимодействие...doc
Скачиваний:
3
Добавлен:
01.03.2025
Размер:
3 Мб
Скачать
☆

6.12. Задачи

  1. Опишите каждый из шести приведенных на рис. 6.3 путей так же, как это сделано для рис. 6.2 в разделе 6.1.

  2. Как указывалось, в ситуации, изображенной на рис. 6.3, взаимоблокировка возникнуть не может. Обоснуйте это утверждение.

  3. Рассмотрим следующее состояние системы, в котором в данный момент не имеется никаких очередей неудовлетворенных запросов.

а. Определите, какие ресурсы может запросить каждый из процессов, и заполните столбцы "Требуется" таблицы.

б. В каком состоянии — опасном или безопасном — находится система в настоящий момент? Обоснуйте свой ответ.

в. Заблокирована система в настоящий момент или нет? Обоснуйте свой ответ.

г. Какой процесс (если таковой имеется) находится в состоянии взаимоблокировки (или может быть заблокирован)?

д. Если процессом р3 будет выполнен запрос (0,1,0,0), безопасно ли его немедленное удовлетворение? В каком именно состоянии окажется система после его немедленного удовлетворения? Какие процессы (если таковые имеются) окажутся (или могут оказаться) заблокированными при немедленном удовлетворении этого запроса?

6.4. Примените алгоритм обнаружения взаимоблокировки из раздела 6.4 к приведенным данным.

Доступность = (2100),

Требования = Распределение =

6.5. Система буферизации, представленная на рис. 6.10, состоит из процесса ввода I, пользовательского процесса Р и процесса вывода О, соединенных с двумя буферами. Процессы обмениваются блоками данных одинакового размера, которые буферизуются на диске; граница между входным и выходным буферами динамическая, зависящая от скорости работы процессов. Используемые процессами примитивы гарантируют выполнение условия i+ о < max , где

max — максимальное количество блоков на диске;

i — количество входных блоков на диске;

о — количество выходных блоков на диске.

О работе процессов известно следующее.

  1. Пока система производит данные, процесс I записывает их на диск (если на диске имеется свободное место).

  2. Пока на диске имеются входные данные, процесс Р считывает их и для каждого считанного блока выводит некоторое конечное количество данных (если на диске имеется свободное место).

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

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

  2. Во многозадачной системе THE [DIJK68] барабан (предшественник магнитных дисков) разделен на входные буферы, рабочую область и выходные буферы с подвижными границами, зависящими от скорости работы процессов. Текущее состояние барабана можно охарактеризовать следующими параметрами:

max — максимальное количество страниц на барабане;

i — количество входных страниц на барабане;

р — количество страниц рабочей области на барабане;

о — количество выходных страниц на барабане;

reso — минимальное количество страниц, зарезервированных для выхода; resp — минимальное количество страниц, зарезервированных для работы.

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

6.8. В многозадачной системе THE возможны следующие переходы между состояниями страницы.

1. Пустая  входной буфер (ввод данных).

2. Входной буфер  рабочая область (использование ввода).

  1. Рабочая область  выходной буфер (вывод данных).

  2. Выходной буфер  пустая (использование вывода).

5. Пустая  рабочая область (вызов процедуры).

6. Рабочая область  пустая (возврат из процедуры).

а. Опишите действие этих переходов в терминах величин i, о и р.

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

6.9. Рассмотрим систему с общим количеством памяти, равным 150 единицам, распределенным между процессами следующим образом:

Процесс Максимум Получено

  1. 70 45

  2. 60 40

  3. 60 15

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

а. Начинает работу четвертый процесс с максимальными требованиями к памяти, равными 60 единицам, и начальным запросом на 25 единиц памяти.

б. Начинает работу четвертый процесс с максимальными требованиями к памяти, равными 60 единицам, и начальным запросом на 35 единиц памяти.

  1. Оцените применимость алгоритма банкира в реальной жизни.

  2. Алгоритм конвейера реализован таким образом, что поток элементов данных типа Т, производимых процессом Р0, проходит через последовательность процессов P1, Р2,…, Рn-1, обрабатывающих проходящие данные в указанном порядке.

а. Определите обобщенный буфер сообщений, который содержит все частично использованные элементы данных, и разработайте алгоритм работы процесса Pi, 0<=i<= п -1. Алгоритм должен иметь следующий вид:

repeat

Получение информации от предшественника;

Использование полученного элемента;

Послать информацию преемнику;

forever

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

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

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

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

6.13. Рассмотрим следующие способы работы с взаимоблокировками.

  1. Алгоритм банкира.

  2. Обнаружение взаимоблокировки и прекращение работы потока с освобождением всех ресурсов.

  3. Резервирование всех ресурсов заранее.

  4. Перезапуск потока и освобождение всех ресурсов, если поток должен находиться в состоянии ожидания.

  5. Упорядочение ресурсов.

  6. Обнаружение взаимоблокировки и откат потока.

а. Одним из критериев оценки различных подходов к проблеме блокировки является оценка максимальной допустимой параллельности вычислений, иными словами, какой из методов позволяет работать наибольшему количеству потоков без ожидания и возникновения взаимоблокировок? Упорядочьте перечисленные ранее методы борьбы с взаимоблокировками в порядке уменьшения обеспечи­ваемой ими степени параллельности и прокомментируйте ваше решение.

б. Еще одним критерием может служить эффективность; другими словами, какой из методов требует меньших накладных расходов процессорного времени? Считая, что взаимоблокировка — весьма редкое событие, упорядочьте перечисленные ранее методы борьбы с взаимоблокировками в порядке уменьшения их эффективности и прокомментируйте ваше решение. Изме­нится ли порядок, если взаимоблокировки будут происходить часто?

  1. Прокомментируйте следующее решение задачи об обедающих философах. Проголодавшийся философ сперва берет вилку слева от себя. Затем, если вилка справа свободна, он берет ее и приступает к еде; в противном случае он кладет левую вилку на стол и повторяет цикл.

  2. Данное упражнение демонстрирует тонкости задачи об обедающих философах и сложность написания корректной программы с использованием семафоров. В листинге 6.4 приведено решение этой задачи из книги, посвященной операционным системам ([TANE97], [TANE92]).

а. Опишите принцип решения задачи словами.

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

Листинг 6.4. Предлагаемое решение задачи об обедающих философах

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

idefine LEFT (i-l)%N /* Левый сосед 1-го философа */

Idefine RIGHT (i+l)%N /* Правый сосед 1-го философа */

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

#define HUNGRY 1 /* Философ пытается взять вилки */

idefine EATING 2 /* Философ ест*/

typedef int semaphore; /* Семафор - специальный тип int*/

int state[N]; /* Массив для отслеживания

состояний философов */

semaphore mutex = 1; /* Взаимоисключение для

критического раздела */

semaphore s[N] ;

void philosopher(int i) /* Номер философа от 0 до N-1 */

{

while(TRUE) /* Бесконечный цикл */

{

think(); /* Философ думает */

take_forks(i); /* Берет две вилки, или

блокируется */

eat(); /* Философ ест спагетти */

put_forks(i); /* кладет вилки на стол */

}

}

void,take_forks(int i) /* Номер философа от 0 до N-1 */

{

wait(mutex); /* Вход в критический раздел */

state[i] = HUNGRY; /* Запоминаем, что философ

проголодался */

test(i); /* Пытаемся взять две вилки */

signal(mutex); /* Выход из критического раздела*/

wait(s[i]); /* Блокирование, если обе вилки

в настоящий момент недоступны*/

}

void put_forks(int i) /* Номер философа от 0 до N-1 */

{

wait(mutex); /* Вход в критический раздел */

state [i] = THINKING; /* Философ завершил обед */

test(LEFT); /* Может ли обедать сосед слева */

test(RIGHT); /* Может ли обедать сосед справа*/

signal(mutex); /* Выход из критического раздела*/

}

void test(int i) /* Номер философа от 0 до N-1 */

{

if (state[i] = = HUNGRY &&

state[LEFT] != EATING &&

state[RIGHT] != EATING)

{

state [i] = EATING;

signal(s[i]);

}

}

6.16. Предположим, что имеется два типа философов — "левые", которые всегда берут первой вилку слева, и "правые", которые начинают с правой вилки. Поведение левых философов показано в листинге 6.2; поведение правых — в приведенном фрагменте кода.

begin

repeat

think();

wait(fork[(i+l) mod 5] ) ;

wait (fork[i]);

eat();

signal(fork[i]);

signal(fork[(i+1) mod 5]);

forever

end;

Докажите следующие утверждения.

а. Любое размещение за столом левых и правых философов с присутствием как минимум по одному философу каждого типа позволит устранить взаимоблокировку.

б. Любое размещение за столом левых и правых философов с присутствием как минимум по одному философу каждого типа позволит предотвратить голодание.