Добавлен: 29.10.2018
Просмотров: 48055
Скачиваний: 190
Вопросы
211
48. Представьте себе систему реального времени с двумя голосовыми вызовами
с периодичностью, равной 5 мс для каждого из них, со временем центрального
процессора, затрачиваемого на каждый вызов, равным 1 мс, и с одним видеопо-
током с периодичностью, равной 33 мс, со временем центрального процессора,
затрачиваемого на каждый вызов, равным 11 мс. Можно ли спланировать работу
такой системы?
49. Можно ли добавить к условию предыдущей задачи еще один видеопоток, сохраняя
при этом пригодность системы к планированию?
50. Для предсказания времени выполнения используется алгоритм распределения
по срокам давности с a = 1/2. Предыдущие четыре значения времени от самого
позднего до самого недавнего составляли 40, 20, 40 и 15 мс. Каким будет прогноз
на следующее время выполнения?
51. Гибкая система реального времени имеет четыре периодически возникающих
события с периодами для каждого, составляющими 50, 100, 200 и 250 мс. Предпо-
ложим, что эти четыре события требуют 35, 20, 10 мс и x процессорного времени
соответственно. Укажите максимальное значение x, при котором система все еще
поддается планированию.
52. Примените к задаче обедающих философов следующий протокол: каждый четный
философ перед тем, как взять ту вилку, которая лежит справа, всегда берет ту вил-
ку, которая лежит слева от него, а каждый нечетный философ перед тем, как взять
левую вилку, всегда берет ту вилку, которая лежит справа от него. Обеспечит ли
данный протокол проведение операции, не вызывающей взаимной блокировки?
53. Системе реального времени необходимо обработать два голосовых телефонных
разговора, каждый из которых запускается каждые 6 мс и занимает 1 мс про-
цессорного времени при каждом использовании процессора, и один видеопоток
со скоростью 25 кадров в секунду, где каждый кадр требует 20 мс процессорного
времени. Поддается ли эта система планированию?
54. Рассмотрите систему, в которой желательно разделить политику и механизм
планирования потоков, реализованных на уровне ядра. Предложите средства для
достижения этой цели.
55. Почему в решении задачи обедающих философов (см. листинг 2.14) в процедуре
take_forks переменной состояния state присвоено значение HUNGRY?
56. Рассмотрим
процедуру
put_forks в листинге 2.14. Предположим, что переменной
state[i] было присвоено значение THINKING после двух вызовов test, а не перед
ними. Как это изменение повлияет на решение?
57. Задача читателей и писателей может быть сформулирована несколькими спосо-
бами в зависимости от того, процесс какой категории и когда должен запускаться.
Опишите в точности три различные разновидности задачи, в каждой из которых
предпочтение отдается (или не отдается) какой-нибудь категории процессов.
Определите для каждой разновидности, что произойдет, когда читатель или писа-
тель перейдет в состояние готовности к доступу к базе данных, и что произойдет,
когда процесс завершит использование базы данных.
58. Напишите сценарий оболочки, производящей файл, содержащий последователь-
ные числа, появляющиеся за счет считывания последнего числа из файла, при-
бавления к нему единицы и добавления получившегося числа к файлу. Запустите
212
Глава 2. Процессы и потоки
один экземпляр сценария в фоновом режиме и один экземпляр в приоритетном
режиме, чтобы каждый из этих экземпляров имел доступ к одному и тому же
файлу. Через какое время проявится состязательная ситуация? Что здесь будет
являться критической областью? Измените сценарий, чтобы избежать состяза-
тельной ситуации.
Подсказка
: для блокировки файла данных воспользуйтесь выражением ln file file.
lock.
59. Представьте, что у вас есть операционная система, предоставляющая семафоры.
Создайте систему сообщений. Напишите процедуры для отправки и получения
сообщений.
60. Решите задачу обедающих философов с помощью мониторов, используя их вместо
семафоров.
61. Предположим, что некий университет в США решил продемонстрировать свою
политкорректность, применив известную доктрину Верховного суда США «От-
деленный, но равный — по сути неравный» не только к расовой, но и к половой
принадлежности, положив конец устоявшейся практике раздельных душевых
для мужчин и женщин в своем кампусе. Но уступая традиции, университет вы-
нес решение, что если в душевой находится женщина, то туда может зайти другая
женщина, но не мужчина, и наоборот. Символ на сдвижном индикаторе на двери
душевой показывает три возможных состояния:
а) свободно;
б) душевая занята женщинами;
в) душевая занята мужчинами.
Напишите на любом избранном вами языке программирования следующие про-
цедуры: для женщины, желающей войти, — woman_wants_to_enter; для мужчины,
желающего войти, — man_wants_to_enter; для женщины, выходящей из душе-
вой, — woman_leaves; для мужчины, выходящего из душевой, — man_leaves. При
этом можно использовать какие угодно счетчики и технологии синхронизации.
62. Перепишите программу, изображенную на рис. 2.17, для управления более чем
двумя процессами.
63. Напишите решение задачи производителя — потребителя, в котором использу-
ются потоки и общий буфер. Но при этом для защиты общей структуры данных
не пользуйтесь семафорами или другими примитивами синхронизации. Просто
дайте каждому потоку возможность иметь к ним произвольный доступ. Для
управления условиями переполнения и опустошения используйте примитивы
sleep и wakeup. Посмотрите, сколько пройдет времени до возникновения состя-
зательной ситуации. К примеру, можно сделать так, чтобы производитель время
от времени выводил какое-нибудь число. Не нужно выводить более одного числа
в минуту, поскольку операции ввода-вывода могут повлиять на возникновение
состязательного состояния.
64. Для придания процессу более высокого уровня приоритета он может быть поме-
щен в циклическую очередь более одного раза. Того же эффекта можно добиться
запуском нескольких экземпляров программы, каждый из которых будет работать
в другой части пула данных. Сначала напишите программу, проверяющую спи-
сок чисел на их принадлежность к простым числам. Затем разработайте метод,
Вопросы
213
позволяющий нескольким экземплярам программы запускаться одновременно
таким образом, чтобы никакие два экземпляра не работали с одним и тем же чис-
лом. Можно ли фактически ускорить перебор списка путем запуска нескольких
копий программы? Учтите, что результаты будут зависеть от того, чем еще занят
ваш компьютер. На персональном компьютере, запустившем только одну копию
этой программы, улучшения ожидать не приходится, но на системе с другими про-
цессами будет возможность захватить таким образом более существенную часть
процессорного времени.
65. Цель этого упражнения заключается в реализации многопоточного решения для
определения того, является ли заданное число совершенным. Число N является
совершенным, если сумма всех его делителей, исключая само это число, равна N
(примерами могут послужить числа 6 и 28). На входе задается целое число N. На
выходе будет значение true, если число является совершенным, или false, если оно
таковым не является. Основная программа будет читать числа N и P из командной
строки. Числа от 1 до N будут делиться между этими потоками, чтобы два потока
не работали с одним и тем же числом. Для каждого числа в этом наборе поток
будет определять, является ли число делителем числа N. Если оно таковым яв-
ляется, то это число добавляется к общему буферу, хранящему делители числа N.
Родительский процесс ожидает, пока не завершат работу все потоки. Воспользуй-
тесь соответствующим примитивом синхронизации. Затем родительский поток
определяет, является ли введенное число совершенным, то есть является ли оно
суммой всех делителей, а затем выдает соответствующий отчет.
Примечание
: вычисление можно ускорить, ограничив количество чисел, проводя
поиск от 1 до корня квадратного из N.
66. Создайте программу для подсчета частоты появления слов в текстовом файле. Тек-
стовый файл делится на N сегментов. Каждый сегмент обрабатывается отдельным
потоком, который выводит промежуточный счетчик частоты для своего сегмента.
Основной процесс ожидает окончания работы потоков, затем он вычисляет свод-
ные данные частоты появления слов на основе выводов отдельных потоков.
Гл а в а 3
.
Управление памятью
Память представляет собой очень важный ресурс, требующий четкого управления.
Несмотря на то что в наши дни объем памяти среднего домашнего компьютера в де-
сятки тысяч раз превышает ресурсы IBM 7094, бывшего в начале 1960-х годов самым
большим компьютером в мире, размер компьютерных программ растет быстрее, чем
объем памяти. Закон Паркинсона можно перефразировать следующим образом:
«Программы увеличиваются в размерах, стремясь заполнить всю память, доступную
для их размещения». В этой главе мы рассмотрим, как операционные системы созда-
ют из памяти абстракции и как они этими абстракциями управляют.
В идеале каждому программисту хотелось бы иметь предоставленную только ему не-
ограниченную по объему и скорости работы память, которая к тому же не теряет своего
содержимого при отключении питания. Раз уж мы так размечтались, то почему бы не
сделать память еще и совсем дешевой? К сожалению, существующие технологии пока
не могут дать нам желаемого. Может быть, способ создания такой памяти удастся изо-
брести именно вам.
Тогда чем же нам придется довольствоваться? Со временем была разработана кон-
цепция иерархии памяти, согласно которой компьютеры обладают несколькими
мегабайтами очень быстродействующей, дорогой и энергозависимой кэш-памяти,
несколькими гигабайтами памяти, средней как по скорости, так и по цене, а так-
же несколькими терабайтами памяти на довольно медленных, сравнительно де-
шевых дисковых накопителях, не говоря уже о сменных накопителях, таких как
DVD и флеш-устройства USB. Превратить эту иерархию в абстракцию, то есть
в удобную модель, а затем управлять этой абстракцией — и есть задача операционной
системы.
Та часть операционной системы, которая управляет иерархией памяти (или ее частью),
называется менеджером, или диспетчером, памяти. Он предназначен для действен-
ного управления памятью и должен следить за тем, какие части памяти используются,
выделять память процессам, которые в ней нуждаются, и освобождать память, когда
процессы завершат свою работу.
В этой главе будут рассмотрены несколько разных моделей управления памятью,
начиная с очень простых и заканчивая весьма изощренными. Поскольку управление
кэш-памятью самого нижнего уровня обычно осуществляется на аппаратном уровне,
основное внимание будет уделено программистской модели оперативной памяти и спо-
собам эффективного управления ее использованием. Все, что касается абстракций,
создаваемых для энергонезависимого запоминающего устройства — диска, и управле-
ния этими абстракциями, будет темой следующей главы. Начнем с истоков и в первую
очередь рассмотрим самую простую из возможных схем, а затем постепенно будем
переходить к изучению все более сложных.
3.1. Память без использования абстракций
215
3.1. Память без использования абстракций
Простейшей абстракцией памяти можно считать полное отсутствие какой-либо аб-
стракции. Ранние универсальные машины (до 1960 года), ранние мини-компьютеры
(до 1970 года) и ранние персональные компьютеры (до 1980 года) не использовали
абстракции памяти. Каждая программа просто видела физическую память. Когда про-
грамма выполняла команду
MOV REGISTER1,1000
компьютер просто перемещал содержимое физической ячейки памяти 1000
в REGISTER1. Таким образом, модель памяти, предоставляемая программисту, была
простой физической памятью, набором адресов от 0 до некоторого максимального
значения, где каждый адрес соответствовал ячейке, содержащей какое-то количество
бит (обычно 8).
При таких условиях содержание в памяти сразу двух работающих программ не пред-
ставлялось возможным. Если первая программа, к примеру, записывала новое значение
в ячейку 2000, то она тем самым стирала то значение, которое сохраняла там вторая
программа. Работа становилась невозможной, и обе программы практически сразу же
давали сбой.
Даже в условиях, когда в качестве модели памяти выступает сама физическая па-
мять, возможны несколько вариантов использования памяти. Три из них показаны
на рис. 3.1. Операционная система может (рис. 3.1, а) размещаться в нижней части
адресов, в оперативном запоминающем устройстве (ОЗУ), или, по-другому, в памяти
с произвольным доступом — RAM (Random Access Memory). Она может размещаться
также в постоянном запоминающем устройстве (ПЗУ), или, иначе, в ROM (Read-
Only Memory), в верхних адресах памяти (рис. 3.1, б). Или же драйверы устройств
могут быть в верхних адресах памяти, в ПЗУ, а остальная часть системы — в ОЗУ,
в самом низу (рис. 3.1, в). Первая модель прежде использовалась на универсальных
машинах и мини-компьютерах, а на других машинах — довольно редко. Вторая модель
использовалась на некоторых КПК и встроенных системах. Третья модель использо-
валась на ранних персональных компьютерах (например, на тех, которые работали
под управлением MS-DOS), где часть системы, размещавшаяся в ПЗУ, называлась
базовой системой ввода-вывода — BIOS (Basic Input Output System). Недостаток
моделей, изображенных на рис. 3.1, а и в, заключается в том, что ошибка в программе
пользователя может затереть операционную систему, и, возможно, с весьма пагубными
последствиями.
Единственный способ добиться хоть какой-то параллельности в системе, не имеющей
абстракций памяти, — это запустить программу с несколькими потоками. Поскольку
предполагается, что все имеющиеся в процессе потоки видят один и тот же образ памяти,
их принудительное применение проблемы не составляет. Хотя эта идея вполне работо-
способна, она не нашла широкого применения, поскольку людям зачастую необходим
одновременный запуск не связанных друг с другом программ, а этого абстракция потоков
не обеспечивает. Более того, столь примитивные системы, не обеспечивающие абстрак-
ций памяти, вряд ли могут предоставить абстракцию потоков.
Тем не менее даже в отсутствие абстракций памяти одновременный запуск несколь-
ких программ вполне возможен. Для этого операционная система должна сохранить
все содержимое памяти в файле на диске, а затем загрузить и запустить следующую