Файл: Debian Таненбаум Бос.pdf

Вопросы  

521

предотвращения пробок, действующий в Нью-Йорке, называется «не блокировать 
квартал» и запрещает автомобилям въезжать на перекресток, пока не освободится 
пространство за этим перекрестком. К какому типу алгоритмов предотвращения 
взаимоблокировок он относится? Можете ли вы предложить какой-нибудь другой 
алгоритм предотвращения пробок?

7.  Предположим, что к перекрестку одновременно с четырех разных сторон подъ-

езжают четыре автомобиля. На каждом углу перекрестка имеется знак остановки. 
Предположим, что правила дорожного движения требуют, чтобы при одновремен-
ном приближении двух машин к смежным знакам остановки та машина, которая 
находится слева, уступала дорогу той машине, которая находится справа. Таким 
образом, когда четыре машины подъезжают к своему знаку остановки, каждая из 
них, прежде чем продолжить движение, ждет (бесконечно долго), пока проедет 
та машина, которой она должна уступить дорогу. Является ли данная аномальная 
ситуация коммуникационной взаимоблокировкой? А может быть, она относится 
к ресурсной взамоблокировке?

8.  Возможно ли вовлечение в ресурсную взаимоблокировку нескольких устройств 

одного типа и одного устройства другого типа? Если да, то приведите пример.

9.  На рис. 6.1 показана концепция графа ресурсов. Существует ли недопустимый 

граф, то есть такой граф, структура которого нарушает модель, используемую нами 
применительно к ресурсам? Если да, то приведите пример.

10.  Посмотрите на рис. 6.2. Предположим, что на n-м шаге C запрашивает S, а не R. 

Приведет ли это к взаимоблокировке? Предположим, что запрос касается как S, 
так и R.

11.  Предположим, в системе возникла взаимоблокировка. Приведите пример, по-

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

12.  Чтобы управлять трафиком, сетевой маршрутизатор А периодически отправляет 

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

13. При рассмотрении страусиного алгоритма упоминалось о возможности запол-

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

14.  Рассмотрите следующее состояние системы с четырьмя процессами, P1, P2, P3 

и P4, и пятью типами ресурсов, RS1, RS2, RS3, RS4 и RS5.

522  

 Глава 6. Взаимоблокировка 

0

1

1

1

2

1

1

0

2

1

C  =

0

1

0

1

0

 R =

0

1

0

2

1

E = (24144)
A = (01021)

0

0

0

0

1

0

2

0

3

1

2

1

0

0

0

0

2

1

1

0

15. Используя алгоритм обнаружения взаимоблокировки, рассмотренный в разде-

ле 6.4.2, покажите наличие в системе взаимоблокировки. Определите процессы, 
вовлеченные во взаимоблокировку.

16.  Объясните, как система может быть восстановлена из взаимоблокировки, воз-

никшей из-за предыдущей проблемы, используя:

а) восстановление через принудительный отбор ресурсов;

б) восстановление путем отката;

в) восстановление путем уничтожения процессов.

17.  Предположим, что на рис. 6.4 для некоторых i соблюдается условие Cij + Rij > Ej. 

Какое значение это имеет для системы?

18.  Все траектории на рис. 6.6 либо горизонтальные, либо вертикальные. Можете 

ли вы представить себе какие-либо обстоятельства, при которых возможны диа-
гональные траектории?

19.  Может ли схема траектории ресурса, показанная на рис. 6.6, также быть использо-

вана для иллюстрации проблемы взаимоблокировки с тремя процессами и тремя 
ресурсами? Если да, то как это можно сделать? Если нет, то почему?

20. Теоретически графики траектории ресурсов могут быть использованы для уклоне-

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

21.  Может ли система находиться в состоянии, которое нельзя назвать ни взаимобло-

кировкой, ни безопасным состоянием? Если да, то приведите пример. Если нет, 
докажите, что все состояния могут быть либо безопасными, либо состояниями 
взаимоблокировки.

22.  Внимательно посмотрите на рис. 6.9, б. Если D запросит еще одну единицу ресурса, 

то к какому состоянию это приведет, безопасному или небезопасному? Что, если 
запрос придет от C, а не от D?

23. У 

системы есть два процесса и три одинаковых ресурса. Каждому процессу нужны 

максимум два ресурса. Возможно ли при этом возникновение взаимоблокировки? 
Обоснуйте свой ответ.

24.  Рассмотрим еще раз предыдущую проблему, но теперь с p процессами, каждый из 

которых нуждается максимум в m ресурсах при общем количестве доступных ре-
сурсов, равном r. Какие условия должны соблюдаться, чтобы система не попадала 
в состояние взаимоблокировки?

25.  Предположим, что процесс A на рис. 6.10 запрашивает последний накопитель на 

магнитной ленте. Приведет ли это действие к взаимоблокировке?

26. Алгоритм банкира работает на системе, имеющей m классов ресурсов и n про-

цессов. Для больших значений m и n количество операций, необходимых для 

Вопросы  

523

проверки безопасности состояния, пропорционально m

a

n

b

. Каковы должны быть 

значения a и b?

27.  У системы имеется четыре процесса и пять распределяемых ресурсов. Текущее 

распределение и максимальные потребности приведены в следующей таблице.

Процесс

Распределено

Максимальные потребности

Доступно

A

1 0 2 1 1

1 1 2 1 3

0 0 x 1 1

B

2 0 1 1 0

2 2 2 1 0

C

1 1 0 1 0

2 1 3 1 0

D

1 1 1 1 0

1 1 2 2 1

Каково наименьшее значение x, при котором это состояние безопасно?

28.  Один из способов избавиться от циклического ожидания заключается в соблю-

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

29.  Имеется два процесса, A и B, каждому из которых нужны три записи в базе дан-

ных — 1, 2 и 3. Если A запрашивает эти записи в следующем порядке: 1, 2, 3, и B 
запрашивает их в том же порядке, взаимоблокировка невозможна. Но если B за-
прашивает их в порядке 3, 2, 1, то появляется возможность возникновения взаи-
моблокировки. При трех ресурсах имеется три или шесть возможных комбинаций, 
в которых каждый процесс может запросить ресурсы. Какая часть комбинаций 
гарантирует свободу от взаимоблокировок?

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

межпроцессного взаимодействия: send (послать) и receive (получить). Второй 
примитив указывает процесс, от которого следует получить сообщение, и блоки-
руется, если сообщения от процесса недоступны, даже несмотря на то, что могут 
ожидаться сообщения от других процессов. Здесь нет общих ресурсов, но процес-
сам необходимо часто связываться друг с другом по другим причинам. Возможно 
ли возникновение взаимоблокировки? Обоснуйте ответ.

31. В электронной системе платежей задействованы сотни одинаковых процессов, 

которые работают следующим образом. Каждый процесс читает входную строку, 
определяющую количество денег для перевода, кредитовый и дебетовый счета. 
Затем он блокирует оба счета и переводит деньги, а после завершения перевода 
снимает блокировку. При параллельно работающем большом количестве про-
цессов существует реальная опасность того, что, имея заблокированный счет x, 
процесс не сможет заблокировать счет y, поскольку y уже был заблокирован про-
цессом, который теперь ожидает счет x. Придумайте схему, позволяющую избегать 
взаимоблокировки. Не освобождайте запись счета до тех пор, пока не завершите 
транзакцию. (Иными словами, решение, которое блокирует один счет, а затем не-
медленно его освобождает, если другой счет заблокирован, не допускается.)

32.  Один из способов предотвращения взаимоблокировок заключается в устранении 

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

524  

 Глава 6. Взаимоблокировка 

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

33.  Студент, изучающий информатику, получил работу в области взаимоблокировок 

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

34. В системах, допускающих подкачку и имеющих виртуальную организацию па-

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

35.  Объясните разницу между активной взаимоблокировкой, простой взаимоблоки-

ровкой и зависанием.

36.  Предположим, что два процесса выдали поисковую команду на перемещение ме-

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

37.  В локальных сетях используется метод доступа к среде, называемый CSMA/CD 

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

а) Какой взаимоблокировкой это является, ресурсной или активной?

б) Можете ли вы предложить решение этой аномалии?

в) Может ли при таком сценарии произойти зависание?

38.  Программа содержит ошибку в порядке следования механизмов сотрудничества 

и соперничества, приводящую к тому, что потребляющий процесс блокирует 
мьютекс (семафор взаимного исключения) до того, как он блокирует пустой бу-
фер. Производящий процесс блокируется на мьютексе еще до того, как он может 
поместить значение в пустой буфер и разбудить потребителя. Таким образом, оба 
процесса блокируются навсегда, производитель ожидает разблокировки мьютекса, 

Вопросы  

525

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

39.  Золушка и Принц расторгают брак. Чтобы разделись свое имущество, они согла-

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

40. Студент, 

специализирующийся на антропологии и попутно изучающий информа-

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

41.  Вернитесь к предыдущей задаче, но теперь постарайтесь избежать зависания. 

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

42.  Напишите программу, моделирующую алгоритм банкира. Ваша программа должна 

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

43.  Напишите программу, реализующую алгоритм обнаружения взаимоблокировки 

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