Э. Таненбаум - Архитектура компьютера (1127755), страница 140
Текст из файла (страница 140)
Рассмотрим один из методов реализации команд для работы с семафорами 15 16 17 18 19 20 21 22 Сравните внутреннюю фрагментацию с внешней. Что можно сделать, чтобы избежать каждой из них? Супермаркеты часто сталкиваются с проблемой, напоминающей механизм замещения страниц в системах с виртуальной памятью. В супермаркетах есть фиксированная площадь пространства на полках, куда требуется помещать все больше и больше товаров.
Если поступает новый важный продукт, например корм для собак очень высокого качества, какой-либо другой продукт нужно убрать, чтобы освободить место для нового продукта. Мы знаем два алгоритма: ЬКУ и Р)ГО. Какой из них вы предпочли бы? В некотором смысле технологии кэширования и страничной организации памяти похожи друг на друга. В обоих случаях память разбивается на две области (на кэш и основную память в одном случае и на основную и дисковую память в другом). В тексте этой главы приводятся аргументы в пользу страниц как большого, так и малого размера. Справедливы ли эти аргументы в отношении размера строк кэш-памяти? Почему многие файловые системы требуют, чтобы файл перед чтением явным образом открывался системным вызовом ореп? Сравните применение битовой карты и списка пустот для отслеживания свободного пространства на диске.
Диск состоит из 800 цилиндров, на каждом из которых 5 дорожек по 32 сектора. Сколько понадобится пустот (неиспользуемых фрагментов), чтобы их список оказался больше, чем битовая карта? Предполагается, что блок размещения — это сектор, а для хранения информации о каждом неиспользуемом фрагменте в списке пустот требуется 32 бита.
Чтобы делать прогнозы относительно производительности диска, нужно иметь модель распределения памяти. Предположим, что диск рассматривается как линейное адресное пространство из М секторов (М» 1). Здесь сначала идет последовательность блоков данных, затем неиспользованное пространство, затем другая последовательность блоков данных и т. д. Эмпирические измерения показывают, что вероятностные распределения длин данных и пустот одинаковы, причем для каждого из этих значений вероятность занимать 1 секторов составляет 2 '.
Каково при этом ожидаемое число пустот на диске? На какой-то машине программа может создать столько файлов, сколько ей нужно, и все файлы могут увеличиваться в размерах во время выполнения программы, причем операционная система не получает никаких дополнительных данных об их конечном размере.
Как вы думаете, будут ли файлы храниться в последовательных секторах? Поясните. Согласно результатам исследования различных файловых систем, больше половины файлов занимают менее нескольких килобайтов дисковой памяти, причем подавляющее большинство — менее 8 Кбайт. С другой стороны, 10 % (в количественном отношении) всех файлов обычно занимает более 95 Ж используемого дискового пространства. Какой вывод о размере дисковых блоков можно сделать, исходя из этих данных? Всякий раз, когда центральный процессор собирается выполнить для семафора команду ир или йва (семафор — это целочисленная переменная в памяти), 554 Глава 6. Уровень операционной системы 24. 25.
26. 27. сначала он устанавливает приоритет центрального процессора таким образом, чтобы блокировать все прерывания. Затем он вызывает из памяти семафор, изменяет его и в соответствии с его значением совершает переход. После этого он снова разрешает прерывания. Будет ли этот метод работать, если: 1) существует один центральный процессор, который переключается между процессами каждые 100 миллисекунд? 2) два центральных процессора разделяют общую память, в которой расположен семафор? Компания, разрабатывающая операционные системы, получает жалобы от своих клиентов по поводу последней разработки, которая поддерживает операции с семафорами.
Клиенты решили, что аморально со стороны процессов приостанавливать свою работу (то есть спать на работе). Чтобы угодить своим клиентам, компания решила добавить третью операцию, рее1. Эта операция просто проверяет семафор, но не изменяет его и не блокирует процесс. Таким образом, программы сначала проверяют, можно ли выполнять для семафора операцию осип. Будет ли эта идея работать, если с семафором работают три и более процесса? А если два процесса? Составьте таблицу, в которой в виде функции времени от 0 до 1000 миллисекунд показано, какие из трех процессов, Р1, Р2 и РЗ, работают, а какие блокированы.
Все три процесса выполняют команды цр и даня для одного и того же семафора. Если два процесса блокированы и совершается команда ор, то запускается процесс с меньшим номером, то есть Р1 имеет преимущество над Р2 и РЗ и т. д. Изначально все три процесса работают, а значение семафора равно 1. + При Г = 100 Р1 выполняет операцию оонп. + При Г = 200 Р1 выполняет операцию оонп.
+ При г = 300 Р2 выполняет операцию ир. + При г = 400 РЗ выполняет операцию оонп. + При г = 500 Р1 выполняет операцию осип. + При г = 600 Р2 выполняет операцию ир. + При г = 700 Р2 выполняет операцию 4онп. + При г = 800 Р1 выполняет операцию цр.
+ При г = 900 Р1 выполняет операцию цр. В системе бронирования билетов на авиарейсы необходимо гарантировать, что пока один процесс использует файл, никакой другой процесс не сможет использовать этот файл. В противном случае два разных процесса, которые работают на два разных агентства по продаже билетов, смогут продать последнее оставшееся место двум пассажирам. Разработайте метод синхронизации с использованием семафоров, чтобы точно знать, что только один процесс в конкретный момент времени может получить доступ к файлу (предполагается, что процессы подчиняются определенным правилам). Чтобы сделать возможной реализацию семафоров на компьютере с несколькими процессорами и общей памятью, разработчики часто включают в машину команду проверки с блокированием (назовем ее ТЗЕ).
Команда ТЗЕ Х прове- Вопросы и задания 555 ряет ячейку Х. Если содержимое ячейки равно О, семафоры устанавливаются на 1 за один неделимый цикл памяти, а следующая команда пропускается. Если содержимое ячейки не равно О, ТЯ. работает как пустая операция. Использовав команду ТБ1., можно написать процедуры 1осК и цп1осЕ со следующими свойствами: процедура 1ос1(х) проверяет, заблокирована ли переменная х. Если нет, эта процедура блокирует переменную х и возвращает управление; процедура вп1осК снимет существующую блокировку.
Если переменная х уже заблокирована, процедура просто ждет, пока она не освободится, и только после этого блокирует х и возвращает управление. Если все процессы блокируют таблицу семафоров перед ее использованием, то в определенный момент времени только один процесс может производить операции с переменными и указателями, что предотвращает состояние гонок. Напишите процедуры 1ос)~ и ип1 ос)~ на ассемблере. (Вы можете делать любые разумные допущения, необходимые для решения задачи.) 28. Каковы будут значения 1п и ов1 для кольцевого буфера длиной в 65 слов по- еле каждой из следующих операций? Изначально значения 1п и опг равны О. 1) 22 слова помещаются в буфер; 2) 9 слов удаляются из буфера; 3) 40 слов помещаются в буфер; 4) 17 слов удаляются из буфера; 5) 12 слов помещаются в буфер; 6) 45 слов удаляются из буфера; 7) 8 слов помещаются в буфер; 8) 11 слов удаляются из буфера.
29. Предположим, что одна из версий 1)Х1Х использует блоки размером 2 Кбайт и хранит 512 дисковых адресов на каждый блок косвенной адресации (обычной косвенной адресации, двойной и тройной). Каков будет максимальный размер файла7 Предполагается, что размер файловых указателей составляет 64 бита. 30. Предположим, что следующий системный вызов 1ЛЧ1Х выполнен в контексте рис. 6.27: ап) шь("/шг!аат!Юп!9аяез") Опишите подробно, какие изменения произойдут в системе каталогов.
31. Представьте, что вам нужно разработать 1ЛЧ1Х-подобную систему для микро компьютера, где основной памяти недостаточно. После долгой работы систему все еще не удается уместить в память, и вы наугад выбираете какую-то системную функцию, чтобы пожертвовать ею для общего блага. Пусть этой функцией оказалась рзре, которая создает каналы для передачи потоков байтов от одного процесса к другому. Можно ли после этого как-то изменить ввод-вывод? Что вы можете сказать о конвейерах? Рассмотрите проблемы и возможные решения. 32. Комиссия по защите дескрипторов файлов выдвинула протест против систе- мы 1Л41Х, потому что при возвращении дескриптора файла она всегда возвращает самый маленький из свободных на данный момент номеров.
Следо- 556 Глава 6. Уровень операционной системы 33. 34. 35. 36. 37. вательно, дескрипторы файлов с большими номерами едва ли вообще когда-нибудь удастся использовать. Комиссия настаивает на том, чтобы система возвращала дескриптор с самым маленьким номером из тех, которые еще не использовались программой, а не из тех, что свободны в данный момент. Комиссия утверждает, что эту идею легко реализовать, причем это не повлияет на существующие программы и, кроме того, будет гораздо справедливее по отношению к дескрипторам.
А что вы думаете по этому поводу? В Ъ"1пдоч з ХР можно составить список управления доступом таким образом, чтобы Светлана не имела доступа ни к одному из файлов, а все остальные имели к ним полный доступ. Как это сделать? Опишите два способа программирования производителя и потребителя в Ж1пбовз ХР: с использованием общих буферов и семафоров. Подумайте о том, как можно реализовать общий буфер в каждом из двух случаев. Работу алгоритмов замещения страниц обычно проверяют путем моделирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
