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

206  

 Глава 2. Процессы и потоки 

4.  Когда в результате прерывания или системного вызова управление передается 

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

5.  У компьютерной системы достаточно места, чтобы хранить в основной памяти 

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

6.  У компьютера имеется 4 Гбайт оперативной памяти, 512 Мбайт из которых зани-

мает операционная система. Все процессы, имеющие (для простоты) одинаковые 
характеристики, занимают еще 256 Мбайт. Каким будет допустимое время ожида-
ния ввода-вывода, если цель заключается в задействовании времени центрального 
процессора на 99 %?

7.  Несколько заданий могут быть запущены параллельно и смогут завершить работу 

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

8.  Представьте себе мультипрограммную систему со степенью 6 (то есть имеющую 

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

9.  Представьте, что вы пытаетесь загрузить из Интернета файл размером 2 Гбайт. 

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

10.  В тексте главы утверждалось, что модель на рис. 2.8, а не подходит для файлового 

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

11.  При разветвлении многопоточного процесса возникает проблема при копирова-

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

12. На 

рис. 2.6 показан многопоточный веб-сервер. Если единственным способом про-

читать данные из файла является обычный блокирующий системный вызов read, 
то какие потоки были использованы для веб-сервера — реализованные на уровне 
пользователя или реализованные на уровне ядра? Почему?

13. В 

тексте 

главы мы описали многопоточный веб-сервер, показывая, почему он луч-

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

Вопросы  

207

14.  В табл. 2.4 набор регистров упомянут в качестве элемента, присущего каждому 

потоку, а не каждому процессу. Почему? Ведь у машины, в конечном счете, только 
один набор регистров.

15.  Зачем потоку добровольно отказываться от центрального процессора, вызывая 

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

16.  Может ли поток быть приостановлен таймерным прерыванием? Если да, то при 

каких обстоятельствах, а если нет, то почему?

17.  Нужно сравнить чтение файла с использованием однопоточного и многопоточного 

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

18.  В чем заключается самое большое преимущество от реализации потоков в поль-

зовательском пространстве? А в чем заключается самый серьезный недостаток?

19.  В листинге 2.1 создание потоков и сообщения, выводимые потоками, чередуются 

в произвольном порядке. Существует ли способ задать строгий порядок: создан 
поток 1, поток 1 выводит сообщение о существовании потока 1, создан поток 2, 
поток 2 выводит сообщение о существовании потока 2 и т. д.? Если существует, то 
как он реализуется? А если нет, то почему?

20.  Рассматривая использование в потоках глобальных переменных, мы применили 

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

21.  Рассмотрим систему, в которой потоки реализованы целиком в пользовательском 

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

22.  Предположим, что у операционной системы отсутствуют средства, подобные 

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

23.  Будет ли решение активного ожидания, использующее переменную turn 

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

208  

 Глава 2. Процессы и потоки 

24.  Будет ли показанное в листинге 2.2 решение Петерсона, позволяющее добиться 

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

25.  Может ли проблема инверсии приоритетов, рассмотренная в разделе «Приостанов-

ка и активизация», проявиться в потоках, реализованных на уровне пользователя? 
Почему да или почему нет?

26.  В разделе «Приостановка и активизация» была описана ситуация, возникающая 

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

27.  Какие стеки существуют в системе, имеющей потоки, реализованные на пользо-

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

28.  Обычно в процессе разработки компьютера его работа сначала моделируется 

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

29.  Задача производителя и потребителя может быть расширена для использования на 

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

30.  Рассмотрите следующее решение задачи взаимного исключения, затрагивающей 

два процесса, P0 и P1. Предположим, что переменная turn имеет исходное значе-
ние 0. Код процесса P0 показан далее:

    /* Другой код */
    while (turn != 0) { } /* Do nothing and wait. */
    Critical Section /* . . . */
    turn = 0;
    /* Другой код */

31.  Для процесса P1 замените в показанном выше коде значение 0 значением 1. 

Определите, отвечает ли решение всем требуемым условиям для решения задачи 
взаимного исключения.

32.  Как в операционной системе, способной отключать прерывания, можно реализо-

вать семафоры?

33.  Дайте краткое описание того, как могут быть реализованы семафоры в операци-

онной системе, способной блокировать прерывания.

34.  Если в системе имеется только два процесса, есть ли смысл в использовании ба-

рьера для их синхронизации? Почему да или почему нет?

35.  Могут ли два потока, принадлежащие одному и тому же процессу, быть син-

хронизированы с помощью семафора, реализованного в ядре, если эти потоки 
реализованы на уровне ядра? Ответьте на тот же вопрос применительно к по-

Вопросы  

209

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

36.  При синхронизации внутри мониторов используются условные переменные 

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

    waituntil x < 0 or y + z < n

Теперь примитив signal больше не нужен. Эта схема, несомненно, является более 
универсальной, чем схема Хоара и Бринча Хансена, но тем не менее она не ис-
пользуется. Почему? 

Подсказка

: подумайте о ее реализации.

37. В ресторанах быстрого обслуживания есть четыре категории обслуживающего 

персонала:

•  работники, принимающие заказы клиентов; 

•  повара, готовящие еду; 

•  работники, упаковывающие еду;

•  кассиры, выдающие упаковку с едой клиентам и принимающие от них деньги. 

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

38.  Предположим, что у нас есть система передачи сообщений, использующая почто-

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

39.  Компьютеры CDC 6600 могут обрабатывать до 10 процессов ввода-вывода одно-

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

. Переключение процессов происходит после каждой 

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

40.  Рассмотрите следующий код на языке C:

    void main( ) {
         fork( );
         fork( );
         exit( );
    }

Сколько дочерних процессов создается во время исполнения этой программы?

210  

 Глава 2. Процессы и потоки 

41.  При циклическом планировании обычно ведется список всех запущенных про-

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

42.  Можно ли путем анализа исходного кода определить, к какой категории относится 

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

43.  Объясните, как значение кванта времени и время переключения контекста влияют 

друг на друга в алгоритме циклического планирования.

44.  Измерения, проведенные в конкретной системе, показали, что время работы 

среднестатистического процесса до того, как он будет заблокирован на операции 
ввода-вывода, равно T. На переключение процессов уходит время S, которое 
теряется впустую. Напишите формулу расчета эффективности использования 
центрального процессора для циклического планирования с квантом времени Q, 
принимающим следующие значения:

а) Q = ∞;

б) Q > T;

в) S < Q < T;

г) Q = S;

д) Q ≈ 0.

45.  В состоянии готовности к выполнению находятся пять заданий. Предполагаемое 

время их выполнения составляет 9, 6, 3, 5 и x. В какой последовательности их 
нужно запустить, чтобы свести к минимуму среднее время отклика? (Ответ будет 
зависеть от x.)

46.  Пять пакетных заданий, от A до E, поступают в компьютерный центр практически 

одновременно. Время их выполнения приблизительно составляет 10, 6, 2, 4 и 8 мин 
соответственно. Их (ранее определенные) приоритеты имеют, значения 3, 5, 2, 1 и 4 
соответственно, причем 5 является наивысшим приоритетом. Определите среднее 
оборотное время для каждого из следующих алгоритмов планирования, игнорируя 
при этом издержки на переключение процессов:

а) для циклического планирования;

б) для приоритетного планирования;

в) для планирования по принципу «первым пришел — первым обслужен» (в по-
рядке 10, 6, 2, 4, 8);

г) для планирования по принципу «сначала выполняется самое короткое задание».

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

47.  Процессу, запущенному в системе CTSS, для завершения необходимо 30 квантов 

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