Задания для СРС

1. Каковы две главные функции операционной системы?

2. Что такое многозадачность?

3. Что такое подкачка данных (spooling)? Как вы считаете, будут ли передовые персональные компьютеры иметь в будущем подкачку данных в качестве стандартного элемента?

4. На ранних компьютерах чтение или запись каждого байта данных управлялось напрямую центральным процессором (то есть тогда не было прямого доступа к памяти – DMA). Какой смысл имеет это понятие для многозадачности?

5. Почему системы с разделением времени не были широко распространены на компьютерах второго поколения?

6. Идея семейства компьютеров родилась в 60-е годы вместе с появлением мэйнфреймов серии IBM System/360. Сейчас эта идея считается устаревшей или все еще имеет силу?

7. Одной из причин, по которой на начальной стадии очень медленно распространялся графический интерфейс (GUI), была высокая стоимость необходимого оборудования. Сколько нужно оперативной видеопамяти для поддержки монохромного текстового экрана размером 25 ´ 80 строк? И сколько необходимо для 24-битового цветного отображения на экране размером 1024 ´ 768 пикселов? Какова была стоимость такой видеопамяти в ценах 1980 года (5 долларов за килобайт)? Сколько она стоит сейчас?

8. Какая из следующих команд должна быть разрешена только в режиме ядра:

а) отключение всех прерываний;

б) чтение счетчика даты/времени;

в) изменения счетчика даты/времени;

г) изменение схемы распределения памяти.

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

10. В компьютере есть конвейер, состоящий из четырех ступеней. Каждая из них выполняет свою работу за одно и то же время, а именно, за 1 нc. Сколько команд в секунду может выполнить машина?

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

12. В чем заключается разница между эмулированным и аппаратным прерываниями?

13. Компьютер использует схему настройки адресов программы, показанную на рис. 1.9, а. Программа длиной в 10 000 байт загружена по адресу 40 000. Какие значения примут базовый и предельный регистры соответственно схеме, описанной в тексте?

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

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

16. Для каждого из следующих системных вызовов укажите условие, при котором возникнет ошибка: fork, exec и unlink.

17. Может ли вызов

a.

18. вернуть в переменной count величину, отличную от nbytes? Если да, то почему?

19. Файл, дескриптором которого является fd, содержит следующую последовательность байтов: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5. Выполняется следующий системный вызов:

где вызов 1 seek ищет байт 3 в файле. Что будет содержать буфер после завершения операции чтения?

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

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

22. Несколько задач для тренировки перевода одних единиц в другие:

а) сколько длится микрогод в секундах?

б) микрометры часто называют микронами. Какова длина гигамикрона?

в) сколько байт в памяти размером в 1 Тбайт?

г) масса земли составляет 6000 йоттаграмм. Какова она в килограммах?

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

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

25. На всех существующих компьютерах как минимум часть обработчиков прерываний написана на ассемблере. Почему?

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

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

28. В табл. 2.3 набор регистров относится к элементам потока, а не процесса. Почему? В конце концов, в компьютере всего один набор регистров.

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

30. На рис. 2.7 представлен многопоточный web-сервер. Если единственным способом прочитать информацию из файла является обычный блокирующий системный запрос read, что, по вашему мнению, используется для сервера – потоки на уровне пользователя или на уровне ядра? Почему?

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

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

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

34. В тексте был описан многопоточный web-сервер и показано, почему он лучше, чем однопоточный сервер или конечный автомат. Возможна ли ситуация, в которой однопоточный сервер будет лучше? Приведите пример.

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

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

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

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

39. В системе с потоками на уровне пользователя каждому потоку соответствует собственный стек или каждому процессу? А в системе с потоками на уровне ядра? Поясните.

40. Что такое состояние состязания?

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

42. Опишите коротко, как реализовать семафоры в операционной системе, умеющей блокировать прерывания.

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

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

45. В разделе «Примитивы межпроцессного взаимодействия» была описана ситуация с высокоприоритетным процессом H и низкоприоритетным процессом L, которая приводила к вечному зацикливанию процесса Н. Может ли возникнуть подобная проблема, если вместо приоритетного планирования использовать циклическое? Поясните.

46. Можно ли синхронизировать два потока одного процесса, используя семафор в ядре, если потоки реализованы в пространстве ядра? Если потоки реализованы в пространстве пользователя? Предполагается, что потоки остальных процессов не имеют доступа к семафору. Поясните ответы.

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

waituntil x<0 or y+z<n

48. В этом случае примитив signal больше не нужен. Эта схема существенно более общая, чем схема Хоара и Бринча Хансена, но тем не менее она не используется. Почему? Подсказка: подумайте о реализации.

49. В ресторане быстрого обслуживания есть четыре категории обслуживающего персонала: 1) работники, принимающие заказы; 2) повара, готовящие пищу; 3) специалисты по упаковке блюд и 4) кассиры, принимающие у клиентов деньги и выдающие еду. Каждому из видов персонала можно сопоставить последовательный процесс взаимодействия. Какой формой межпроцессного взаимодействия они пользуются? Свяжите эту модель с процессами в UNIX.

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

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

52. Компьютеры CDC 6600 могут обрабатывать до 10 процессов ввода-вывода одновременно, используя интересную форму циклического планирования, называемую разделением процессора. Переключение между процессами происходит после каждой команды, поэтому команда 1 поступает от первого процесса, команда 2 – от второго и т. д. Переключение процессов производится аппаратными средствами, и издержки равны нулю. Если в отсутствие других процессов процессу для выполнения работы нужно Т секунд, сколько ему потребуется времени в случае п процессов?

53. Обычно планировщики с циклическим алгоритмом поддерживают список процессов, готовых к работе, причем каждый процесс находится в списке в единственном экземпляре. Что произойдет, если процесс окажется в списке дважды? Существует ли причина, по которой подобное изменение будет полезным?

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

55. В разделе «Когда планировать?» упоминалось, что планирование может быть усовершенствовано, если важный процесс может сыграть свою роль в выборе процесса, следующего за ним. Опишите ситуацию, в которой это можно использовать, и объясните, как.

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

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

58. Пять пакетных задач, А, В, С, D, Е поступают в компьютерный центр практически одновременно. Ожидается, что время их выполнения составит 10, 6, 2, 4 и 8 мин. Их установленные приоритеты составляют 3, 5, 2, 1 и 4, причем 5 – высший приоритет. Определите среднее оборотное время для каждого из следующих алгоритмов планирования, пренебрегая временем, теряющимся при переключении между процессами:

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

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

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

г) «кратчайшая задача – первая».

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

60. Процессу, запущенному в системе CTSS, для завершения необходимо 30 квантов. Сколько раз он будет перекачан на диск, считая самый первый раз (прежде, чем он был запущен)?

61. Предложите защиту от обмана системы приоритетов CTSS случайными нажатиями клавиши возврата каретки.

62. Для предсказания времени выполнения используется алгоритм старения с а = 1/2. Предыдущие четыре значения времени составляли 40,20,40 и 15 мс (первое значение – самое давнее). Оцените следующее время выполнения.

63. В гибкую систему реального времени поступает четыре периодических сигнала с периодами 50, 100, 200 и 250 мс. На обработку каждого сигнала требуется 35, 20, 10 и х мс времени процессора. Укажите максимальное значение х, при котором система остается поддающейся планированию.

64. Объясните причины широкого использования двухуровневого планирования.

65. Рассмотрите систему, в которой желательно разделить механизм и стратегию планирования потоков на уровне ядра. Предложите средства достижения этой цели.

66. Напишите сценарий оболочки, которая создает файл, содержащий последовательные числа, путем считывания последнего числа, прибавления к нему единицы и записывания результата в конец файла. Запустите одну копию сценария в качестве фонового процесса и одну – в качестве приоритетного процесса. Сколько времени пройдет, прежде чем возникнет состояние соревнования? Что в данной модели является критической областью? Измените сценарий, чтобы избежать состояния состязания. (Подсказка: воспользуйтесь следующим выражением, чтобы заблокировать файл данных.)

In file file. lock

67. Предположим, что у вас есть операционная система с семафорами. Реализуйте систему сообщений. Напишите процедуры для отсылки и получения писем.

68. Решите задачу обедающих философов, используя мониторы вместо семафоров.

69. Некий университет решил продемонстрировать свою политкорректность, применив известную доктрину верховного суда США «Равенство порознь равенством не является» не только к цвету кожи, но и к полу. Результатом этого решения явились совместные ванные комнаты в общежитиях. Тем не менее в поддержку исторически сложившейся традиции университет постановляет, что если в ванной комнате есть женщина, то другая женщина может туда зайти, а мужчина не может, и наоборот. На двери ванной есть индикатор, показывающий, в каком из трех состояний находится ванная:

а) никого нет;

б) в ванной женщины;

в) в ванной мужчины.

70. Напишите на своем любимом языке программирования следующие процедуры: woman _wants_to_enter, man_wants_to_enter, woman_leaves, man_leaves. Вы можете использовать любые счетчики и методы синхронизации.

71. Напишите алгоритм для решения задачи производителя и потребителя с использованием потоков и разделенного буфера. Однако не используйте семафоры и другие примитивы синхронизации для защиты совместно используемых структур данных, разрешите каждому потоку доступ по мере необходимости. Воспользуйтесь для обработки условий полного и пустого буфера функциями sleep и wakeup. Посмотрите, сколько времени пройдет до появления неустранимого состояния состязания. Например, производитель может периодически выдавать на печать число, но не чаще, чем раз в минуту, поскольку процесс ввода-вывода может повлиять на состояние состязания.

72. Для получения большего приоритета процесс можно поместить в очередь кругового алгоритма планирования больше одного раза. Этого же эффекта можно достигнуть, запустив несколько копий программы, каждая из которых будет обрабатывать свою часть пула данных. Для начала напишите программу, которая проверяет простоту чисел из списка. Затем разработайте способ разрешить одновременный запуск нескольких копий программы, причем так, чтобы две копии программы не обращались к одному числу. Удастся ли вам ускорить обработку списка, запустив несколько копий программы? Имейте в виду, что результат будет зависеть от того, чем еще занят ваш компьютер: при отсутствии других процессов улучшения результатов не будет, но если параллельно решаются другие задачи, несколько копий программы позволят получить больший процент времени процессора.

ЛИТЕРАТУРА:

1. Э. Таненбаум. Современные операционные системы. 2-е изд. – СПб.: Питер, 2002. – 1040 с.: ил

2. Партыка Т. Л., Попов И. И. Операционные системы, среды и оболочки: Учебное пособие. - М.: ФОРУМ: ИНФРА-М, 2003. - 400 с.: ил. - (Серия «Про­фессиональное образование»).