Вопросы 1.

Приведите пример взаимоблокировки, возникающей из-за неудачной политики.

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

При каких условиях может возникнуть взаимоблокировка, если дисковое пространство для буфера печати ограничено определенным объемом? Как можно избежать возникновения взаимоблокировки?

3. Какой из ресурсов в предыдущем вопросе можно отнести к выгружаемому, а какой — к невыгружаемому?

4. В листинге 6.1 ресурсы высвобождаются в порядке, обратном их запросу. А не лучше ли было бы возвращать их в другом порядке?

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

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

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

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

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

10. Посмотрите на рис. 6.2. Предположим, что на га-м шаге С запрашивает Б, а не Я. Приведет ли это к взаимоблокировке? Предположим, что запрос касается как Б, так и Я.

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

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

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

14. Рассмотрите следующее состояние системы с четырьмя процессами, P1, P2, P3 и P4, и пятью типами ресурсов, RS1, RS2, RS3, RS4 и RS5.


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

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

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

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

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

Предположим, что на рис. 6.4 для некоторых I соблюдается условие Су + Яу > Щ. Какое значение это имеет для системы?

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

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

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

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

Внимательно посмотрите на рис. 6.9, б. Если Б запросит еще одну единицу ресурса, то к какому состоянию это приведет, безопасному или небезопасному? Что, если запрос придет от С, а не от Б?

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

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

Предположим, что процесс А на рис. 6.10 запрашивает последний накопитель на магнитной ленте. Приведет ли это действие к взаимоблокировке?

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

15.

16.

17.

18.

19.

20.

21.
22.

23.

24.

25.

26.



проверки безопасности состояния, пропорционально шапь. Каковы должны быть значения а и Ь?

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


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

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

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

30. Распределенная система, использующая почтовые ящики, имеет два примитива межпроцессного взаимодействия: send (послать) и receive (получить).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Вопросы 1.:

  1. Основные ошибки при задавании вопросов. Слишком открытые вопросы.
  2. ВОПРОС О РЕЛИГИИ - ЭТО ВОПРОС О ВЛАСТИ Молитва Господня и семейные порядки
  3. Вопросы без альтернатив, или открытые вопросы
  4. 2.6. Умеем ли мы задавать вопросы? Классификация типов вопросов
  5. § 9 Критика гражданской формы брака. – Вопрос о введении ее в русское законодательство. – Браки у раскольников и вопрос о законности сих браков.
  6. Вопрошающее наблюдение: вопрос без вопроса
  7. 7.1. СКРЫТЫЕ ВОПРОСЫ
  8. 3.3.1. Неструктурированные вопросы
  9. Вопросы
  10. Вопросы
  11. Ключевой вопрос
  12. Наводящие вопросы.