Вопросы 1.

Можно ли систему сетевых новостей USENET или проект SETI@home считать распределенной системой? (Проект SETI@home использует несколько миллионов персональных компьютеров для анализа данных, получаемых с радиотелескопа с целью поиска внеземного разума.) Если да, то к каким категориям, показанным на рис.
8.1, они относятся?

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

3. Если центральный процессор при каждой команде совершает одно обращение к памяти, сколько понадобится центральных процессоров, работающих со скоростью 200 MIPS, чтобы переполнить данными шину, работающую с тактовой частотой 400 МГц? Предположим, что для обращения к памяти требуется один цикл шины. Теперь решите эту же задачу для системы, в которой используется кэширование и вероятность наличия в кэше нужных данных составляет 90 %. Наконец, какая потребуется частота наличия в кэше нужных данных, чтобы той же шиной, не перегружая ее, могли совместно пользоваться 32 центральных процессора?

4. Предположим, что порвется провод между коммутаторами 2A и 3B в схеме коммутации омега (см. рис. 8.5). Кто от кого окажется отрезанным?

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

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

7. Перепишите программу enter_region из листинга 2.3, используя чистое чтение, чтобы уменьшить пробуксовку системы, вызываемую применением команды TSL.

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

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

10. При применении команды TSL для синхронизации мультипроцессора блок кэша, содержащий мьютекс, будет мотаться взад-вперед между центральным процессором, удерживающим блокировку, и центральным процессором, запрашивающим ее, если оба процессора изменяют содержимое блока. Для снижения объема обмена данными по шине запрашивающий центральный процессор выполняет команду TSL один раз за каждые 50 циклов шины, но центральный процессор, удерживающий блокировку, изменяет блок кэша между командами TSL. Если блок кэша состоит из шестнадцати 32-разрядных слов, для переноса каждого из которых требуется один цикл шины, а шина работает с частотой 400 МГц, то какая часть пропускной способности шины тратится впустую на перемещение блока кэша взад-вперед?

11. В тексте предлагалось использовать алгоритм двоичной экспоненциальной задержки между вызовами команды TSL для опроса блокировки. Также предлагалось использовать максимальное значение задержки между опросами. Будет ли алгоритм правильно работать при отсутствии максимальной задержки?

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

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

14. Родственное планирование снижает частоту отсутствия в кэше нужных данных. Снижается ли при этом также частота отсутствия нужной информации в TLB? А как насчет ошибок отсутствия страниц?

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

16. Рассмотрите топологию двойного тора (см. рис. 8.16, г), расширенного до размера k х k. Чему равен диаметр сети?

Подсказка: рассматривайте четные и нечетные значения k отдельно.

17. Для измерения пропускной способности соединительной сети часто применяется метод бисекции. Для этого из сети удаляется минимальное количество связей, позволяющее разбить сеть на две равные части. Затем суммируется пропускная способность удаленных линий связи. Если способов разбиения сети несколько, выбирается тот, при котором эта сумма минимальна. Чему равна бисекционная пропускная способность соединительной сети, представляющей собой куб 8 х 8 х 8, если пропускная способность каждой линии равна 1 Гбит/с?

18. Представим себе мультикомпьютер, в котором сетевой интерфейс работает в режиме пользователя, поэтому для перемещения данных из оперативной памяти источника в оперативную память приемника требуется всего три операции копирования. Предположим, что перемещение 32-разрядного слова через карту сетевого интерфейса в обе стороны занимает 20 нс, а сама сеть работает со скоростью 1 Гбит/с. Чему будет равна задержка при пересылке 64-байтового пакета от источника к приемнику без учета времени копирования? Чему будет равна задержка с учетом времени копирования? Теперь рассмотрите случай, в котором требуются две дополнительные операции копирования: в ядро на передающей стороне и из ядра на принимающей стороне. Чему будет равна задержка в этом случае?

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

20. При переносе данных из оперативной памяти в сетевую интерфейсную плату может использоваться фиксация страницы. Предположим, что выполнение системных вызовов для фиксации и освобождения страниц занимает 1 мкс. Копирование данных занимает 5 байт/нс с использованием DMA и 20 нс на байт — при помощи программного ввода-вывода. Каким должен быть минимальный размер пакета, чтобы фиксация страницы и использование DMA были оправданны?

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

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

22. Когда в системе DSM возникает ошибка отсутствия страницы, нужно найти требуемую страницу. Назовите два возможных метода ее поиска.

23. Рассмотрите примеры распределения процессоров, приведенные на рис. 8.24. Предположим, что процесс H перемещен с узла 2 на узел 3. Чему теперь равен суммарный внешний трафик?

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

25. Почему в сети Ethernet существует ограничение на длину кабеля?

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

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

а) видео по запросу, передаваемое через Интернет;

б) загрузка веб-страницы?

28. DNS-имена имеют иерархическую структуру, например cs.uni.edu или sales. generallwidget.com. Один из способов реализации DNS-имен может заключаться в поддержании централизованной базы данных, но этот метод не применяется, так как такая база данных будет получать слишком большой поток запросов. Предложите свой метод реализации базы данных DNS, которую можно будет поддерживать на практике.

29. При рассмотрении метода обработки браузером URL-указателей утверждалось, что соединения устанавливаются через порт 80. Почему?

30. Когда браузер извлекает веб-страницу, он сначала устанавливает TCP-соединение, чтобы получить текст страницы (на языке HTML). Затем он разрывает соединение и изучает страницу. Если она содержит графические изображения или значки, он снова создает отдельные TCP-соединения для извлечения каждого изображения. Предложите две альтернативные схемы для улучшения производительности.

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

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

33. При выполнении операции in для обнаружения кортежа в системе Linda линейный поиск по всему пространству кортежей крайне неэффективен. Разработайте метод организации пространства кортежей, который ускорит выполнение операций in.

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

35. Напишите на языке C функции, которые могли бы использоваться в качестве клиентской и серверной заглушек для выполнения RPC-вызова стандартной функции print/, а также головной модуль для тестирования этих функций. Клиент и сервер должны общаться при помощи структуры данных, которая может передаваться по сети. Вы можете наложить разумные ограничения на длину строки формата и число, типы и размеры переменных, которые будет принимать ваша клиентская заглушка.

36. Напишите программу, реализующую рассмотренные ранее алгоритмы балансирования нагрузки по инициативе отправителя и по инициативе получателя. В качестве входных данных алгоритмы должны брать список недавно созданных заданий, определяемых как (creating_processor, start_time, required_CPU_time), где creating_processor — это номер центрального процессора, создавшего задание, start_time — время создания задания, а required_CPU_time — количество времени центрального процессора, требуемого для завершения задания (в секундах). Предположим, что узел перегружается, если у него уже есть одно задание, а на нем создается еще одно задание. Предположим, что узел недогружен, когда у него нет заданий. Выведите на печать количество пробных сообщений, отправляемых обоими алгоритмами при сильной и слабой загруженности. Также выведите на печать максимальное и минимальное количество проверок, посланных и полученных любым хостом. Чтобы создать рабочую нагрузку, напишите два генератора рабочей нагрузки. Первый должен имитировать тяжелую нагрузку, генерируя, в среднем, N заданий каждые AJL секунд, где AJL — эта средняя продолжительность выполнения задания и N — количество процессоров. Продолжительности выполнения заданий должны быть последовательностью из длинных и коротких заданий, но средняя продолжительность задания должна быть равна AJL. Задания должны создаваться (распределяться) всеми процессорами случайным образом. Второй генератор должен имитировать слабую нагрузку, случайным образом генерируя N/3 заданий каждые AJL секунд. Поэкспериментируйте с установками остальных параметров для генераторов нагрузки и посмотрите, как это повлияет на количество пробных сообщений.

37. Один из простейших способов реализации системы публикации-подписки — через центрального посредника, получающего публикуемые статьи и распространяющего эти статьи подписчикам. Напишите многопотоковое приложение, эмулирующее систему публикации-подписки на основе использования посредника. Потоки издателя и подписчика могут обмениваться с посредником данными через общую память. Каждое сообщение должно начинаться с поля длины, за которым следует указанное в нем число символов. Издатели отправляют посреднику сообщения, где в первой строке сообщений содержится иерархическая строка темы с точками в качестве разделителей, за которой следуют одна или более строк, содержащих публикуемую статью. Подписчики отправляют посреднику сообщения из одной строки, содержащей иерархическую строку заинтересованности, разделенную точками, обозначающими статьи, которыми они интересуются. Строка заинтересованности может содержать групповой символ «*». Посредник должен ответить отправкой всех (прошлых) статей, соответствующих интересам подписчика. Статьи в сообщении разделены строкой «BEGIN NEW ARTICLE». Подписчик должен выводить на печать каждое получаемое сообщение наряду со своим идентификатором подписчика (то есть его строки заинтересованности). Подписчик должен продолжать получать любые вновь публикуемые статьи, соответствующие его интересам. Потоки издателя и подписчика должны создаваться в динамическом режиме из терминала путем набора «P» или «S» (для издателя или подписчика), за которыми следует иерархическая строка темы или заинтересованности. Затем издатели выдают приглашение на ввод статьи. Ввод одиночной строки, содержащей «.», будет сигнализировать окончание статьи. (Этот проект может быть реализован также с использованием обмена данными между процессами через TCP.)


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

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

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