Реклама:

1. Почему операционная система интерпретирует только некоторые команды уровня 3 (см. рис. 1.2), тогда как микропрограмма интерпретирует все команды уровня архитектуры команд?

2. Машина содержит 32-разрядное виртуальное адресное пространство с побайтовой адресацией. Размер страницы составляет 4 Кбайт. Сколько существует страниц виртуального адресного пространства?

3. Должен ли размер страницы соответствовать степени двойки? Есть ли теоретическая возможность реализации страницы размером, скажем, 4000 байт? Если да, насколько такой размер оправдан?

4. Виртуальная память содержит 8 виртуальных страниц и 4 физических страничных кадра. Размер страницы составляет 1024 слова. Соответствующая таблица страниц выглядит так, как табл. 6.10.

Таблица 6.10. Таблица страниц для задания 4

Виртуальная страница

Страничный кадр

Нет в основной памяти

Нет в основной памяти

Нет в основной памяти

Нет в основной памяти

1) Создайте список виртуальных адресов, обращение к которым будет вызывать ошибку отсутствия страницы.

2) Каковы физические адреса для виртуальных адресов 0, 3728, 1023, 1024, 1025, 7800 и 4096?

5. Компьютер имеет 16 страниц виртуального адресного пространства и только 4 страничных кадра. Изначально память пуста. Программа обращается к виртуальным страницам в следующем порядке:

0, 7, 2, 7, 5, 8, 9, 2, 4

1) Какие из обращений по алгоритму LRU вызовут ошибку отсутствия страницы?

2) Какие из обращений по алгоритму FIFO вызовут ошибку отсутствия страницы?

6. В подразделе "Политика замещения страниц" раздела "Виртуальная память" был предложен алгоритм замещения страниц FIFO. Разработайте более эффективный алгоритм. Подсказка: можно обновлять счетчик во вновь загружаемой странице, оставляя все другие.

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

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

9. Сегментированная память содержит сегменты страниц. Каждый виртуальный адрес содержит 2-разрядный номер сегмента, 2-разрядный номер страницы и 11-разрядное смещение внутри страницы. Основная память содержит 32 Кбайт, которые разделены на страницы по 2 Кбайт. Каждый сегмент разрешается либо только читать, либо читать и выполнять, либо читать и записывать, либо читать, записывать и выполнять. Таблицы страниц и варианты защиты приведены в табл. 6.11.

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

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

Таблица 6.11. Таблицы страниц для задания 9

Сегмент 0

Сегмент 1

 

Сегмент 2

Сегмент 3

Только чтение

Чтение и выполнение

Чтение,

Чтение и запись

Виртуаль- Страничная ный страница кадр

Виртуальная страница

Страничный кадр

запись и выполнение

Виртуаль- Страничная ный кадр страница

0 9

На диске

Таблицы страниц нет в основной памяти

0 14

1 3

Таблицы страниц нет в основной памяти

1 1

2 На диске

Таблицы страниц нет в основной памяти

2 6

3 12

Таблицы страниц нет в основной памяти

3 На диске

Таблица 6.12. Варианты доступа к виртуальной памяти для задания 9

Доступ

Сегмент Страница Смещение внутри страницы

1. Вызов данных

 

2. Вызов данных

 

3. Вызов данных

2047

 

4. Сохранение данных

 

5. Сохранение данных

 

6. Сохранение данных

 

7. Переход

 

8. Вызов данных

 

9. Вызов данных

 

10. Переход

 

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

ниц. Например, если у нас есть 4-килобайтные страницы, файл может быть отображен, начиная с виртуального адреса 4096, а не с виртуального адреса 5000. Зачем это нужно?

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

13. Программа в компьютере Pentium 4 обращается к локальному сегменту 10 со смещением 8000. Поле BASE сегмента 10 в локальной таблице дескрипторов содержит число 10000. Какой элемент таблицы страниц использует Pentium 4? Каков номер страницы? Каково смещение?

14. Рассмотрите возможные алгоритмы для удаления сегментов в сегментированной памяти без страничной организации.

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

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

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

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

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

20. Чтобы делать прогнозы относительно производительности диска, нужно иметь модель распределения памяти. Предположим, что диск рассматривается как линейное адресное пространство из N секторов (N" 1). Здесь сначала идет последовательность блоков данных, затем неиспользованное пространство, затем другая последовательность блоков данных и т. д. Эмпирические измерения показывают, что вероятностные распределения длин данных и пустот одинаковы, причем для каждого из этих значений вероятность занимать г секторов составляет 2~\ Каково при этом ожидаемое число пустот на диске?

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

22. Согласно результатам исследования различных файловых систем, больше половины файлов занимают менее нескольких килобайтов дисковой памяти, причем подавляющее большинство - менее 8 Кбайт. С другой стороны, 10 % (в количественном отношении) всех файлов обычно занимает более 95 % используемого дискового пространства. Какой вывод о размере дисковых блоков можно сделать, исходя из этих данных?

23. Рассмотрим один из методов реализации команд для работы с семафорами. Всякий раз, когда центральный процессор собирается выполнить для семафора команду up или down (семафор - это целочисленная переменная в памяти), сначала он устанавливает приоритет центрального процессора таким образом, чтобы блокировать все прерывания. Затем он вызывает из памяти семафор, изменяет его и в соответствии с его значением совершает переход. После этого он снова разрешает прерывания. Будет ли этот метод работать, если:

1) существует один центральный процессор, который переключается между процессами каждые 100 миллисекунд?

2) два центральных процессора разделяют общую память, в которой расположен семафор?

24. Компания, разрабатывающая операционные системы, получает жалобы от своих клиентов по поводу последней разработки, которая поддерживает операции с семафорами. Клиенты решили, что аморально со стороны процессов приостанавливать свою работу (то есть спать на работе). Чтобы угодить своим клиентам, компания решила добавить третью операцию, peek. Эта операция просто проверяет семафор, но не изменяет его и не блокирует процесс. Таким образом, программы сначала проверяют, можно ли выполнять для семафора операцию down. Будет ли эта идея работать, если с семафором работают три и более процесса? А если два процесса?

25. Составьте таблицу, в которой в виде функции времени от 0 до 1000 миллисекунд показано, какие из трех процессов, PI, Р2 и РЗ, работают, а какие блокированы. Все три процесса выполняют команды up и down для одного и того же семафора. Если два процесса блокированы и совершается команда up, то запускается процесс с меньшим номером, то есть Р1 имеет преимущество над Р2 и РЗ и т. д. Изначально все три процесса работают, а значение семафора равно 1.

♦ При t = 100 PI выполняет операцию down.

♦ При t = 200 PI выполняет операцию down.

♦ При t = 300 Р2 выполняет операцию up.

+ При t = 400 РЗ выполняет операцию down. + При t = 500 PI выполняет операцию down.

♦ При t = 600 Р2 выполняет операцию up.

♦ При t = 700 Р2 выполняет операцию down.

♦ При t = 800 PI выполняет операцию up. + При t = 900 PI выполняет операцию up.

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

27. Чтобы сделать возможной реализацию семафоров на компьютере с несколькими процессорами и общей памятью, разработчики часто включают в машину команду проверки с блокированием (назовем ее TSL). Команда TSL X проверяет ячейку X. Если содержимое ячейки равно 0, семафоры устанавливаются на 1 за один неделимый цикл памяти, а следующая команда пропускается. Если содержимое ячейки не равно О, TSL работает как пустая операция. Использовав команду TSL, можно написать процедуры lock и unlock со следующими свойствами: процедура lock(x) проверяет, заблокирована ли переменная х. Если нет, эта процедура блокирует переменную х и возвращает управление; процедура uni ock снимет существующую блокировку. Если переменная х уже заблокирована, процедура просто ждет, пока она не освободится, и только после этого блокирует х и возвращает управление. Если все процессы блокируют таблицу семафоров перед ее использованием, то в определенный момент времени только один процесс может производить операции с переменными и указателями, что предотвращает состояние гонок. Напишите процедуры 1 ock и unlock на ассемблере. (Вы можете делать любые разумные допущения, необходимые для решения задачи.)

28. Каковы будут значения in и out для кольцевого буфера длиной в 65 слов после каждой из следующих операций? Изначально значения in и out равны 0.

1) 22 слова помещаются в буфер;

2) 9 слов удаляются из буфера;

3) 40 слов помещаются в буфер;

4) 17 слов удаляются из буфера;

5) 12 слов помещаются в буфер;

6) 45 слов удаляются из буфера;

7) 8 слов помещаются в буфер;

8) 11 слов удаляются из буфера.

29. Предположим, что одна из версий UNIX использует блоки размером 2 Кбайт и хранит 512 дисковых адресов на каждый блок косвенной адресации (обычной косвенной адресации, двойной и тройной). Каков будет максимальный размер файла? Предполагается, что размер файловых указателей составляет 64 бита.

30. Предположим, что следующий системный вызов UNIX выполнен в контексте рис. 6.27:

uni ink("/usr/ast/bi n/game3")

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

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

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

33. В Windows ХР можно составить список управления доступом таким образом, чтобы Светлана не имела доступа ни к одному из файлов, а все остальные имели к ним полный доступ. Как это сделать?

34. Опишите два способа программирования производителя и потребителя в Windows ХР: с использованием общих буферов и семафоров. Подумайте о том, как можно реализовать общий буфер в каждом из двух случаев.

35. Работу алгоритмов замещения страниц обычно проверяют путем моделирования. Предположим, что вам нужно написать моделирующую программу, реализующую виртуальную память со страничной организацией для машины, содержащей 64 страницы по 1 Кбайт. Программа должна поддерживать одну таблицу из 64 элементов, по одному элементу на страницу. Каждый элемент таблицы содержит номер физической страницы, который соответствует данной виртуальной странице. Моделирующая программа должна считывать файл, содержащий виртуальные адреса в десятичной системе счисления, по одному адресу на строку. Если соответствующая страница находится в памяти, просто фиксируйте факт наличия страницы. Если ее нет в памяти, вызовите процедуру замещения страниц, чтобы выбрать страницу, которую можно удалить (то есть переписать элемент таблицы) и зафиксируйте факт отсутствия страницы. Никакой передачи страниц реализовывать не нужно. Создайте файл, состоящий из непоследовательных адресов, и проверьте производительность двух алгоритмов: LRU и FIFO. А теперь создайте файл адресов, в котором х % адресов находятся на 4 байта выше, чем предыдущие. Проведите тесты для различных значений х и отчитайтесь о полученных результатах.

36. В программе, показанной в листинге 6.1, имеет место фатальная гонка, так как два программных потока бесконтрольно обращаются к общим переменным. При этом не задействуются ни семафоры, ни какие-либо другие методики взаимного исключения. Запустите эту программу, и вы увидите, что через некоторое время она зависнет. Если она все же не зависнет, попробуйте сделать код более уязвимым, разместив между операторами корректировки значений m. in и т.out и операторами их проверки какие-нибудь вычисления. Какой объем вычислений нужно ввести в эту программу, чтобы она зависала, скажем, раз в час?

37. Напишите программу для UNIX или Windows ХР, которая на входе получает имя каталога. Программа должна печатать список файлов этого каталога, каждый файл на отдельной строке, а после имени файла - его размер. Имена файлов должны располагаться в том порядке, в котором они располагаются в каталоге. Неиспользованные слоты в каталоги должны выводиться с пометкой (не использован).

Краткое содержание главы6 || Оглавление || Глава 7. Уровень ассемблера