5. Опишите основные этапы развития ос

Поскольку ОС развивались параллельно с конструированием компьютеров, для понимания, как развивались ОС, надо рассматривать и историю развития компьютеров.

1. Первое поколение (1945-1955): электронные лампы; ОС нет. Вторая мировая стимулировала работу над цифровыми компьютерами. Изобретен первый действующий цифровой компьютер с 300 электронных ламп. В то же время изобретен компьютер на электромеханическом реле. Это были весьма примитивные устройства. Все программирование велось исключительно на машинном языке или, и того хуже, за счет сборки электрических схем, а для управления основными функциями машины приходилось подключать к коммутационным панелям тысячи проводов. ОС нет.

2. Второе поколение (1955-1965): транзисторы и системы пакетной обработки. После изобретения транзисторов компьютеры стали надежнее. Существовали мэйнфреймы, дорогие и огромные. Чтобы выполнить задание, надо было сначала написать его на бумаге на фортране или ассемблере, а потом перенести на перфокарты, и в целом процесс получения данных был долгим и сложным, поэтому придумали системы пакетной обработки, которые автоматизировали всю последовательность действий оператора по организации вычислительного процесса. Ранние системы пакетной обработки явились прообразом современных ОС, они стали первыми системными программами, предназначенными не для обработки данных, а для управления вычислительным процессом. Оператор составлял пакет заданий, которые в дальнейшем без его участия последовательно запускались на выполнение управляющей программой — монитором. Кроме того, монитор был способен самостоятельно обрабатывать наиболее часто встречающиеся при работе пользовательских программ аварийные ситуации, такие как отсутствие исходных данных, переполнение регистров, деление на ноль, обращение к несуществующей области памяти и т. д. Пакет обычно представлял собой набор перфокарт, но для ускорения работы он мог переноситься на более удобный и емкий носитель, например, на магнитную ленту или магнитный диск. Сама программа-монитор в первых реализациях также хранилась на перфокартах или перфоленте, а в более поздних — на магнитной ленте и магнитных дисках.

3. Третье поколение (1965-1980): интегральные схемы и многозадачность. В это время в технической базе произошел переход от отдельных полупроводниковых элементов типа транзисторов к интегральным микросхемам. Вычислительная техника становится более надежной и дешевой. Растет сложность и количество задач, решаемых компьютерами. Повышается производительность процессоров. Самым важным достижением явилась многозадачность. Для устранения длительных простоев весьма дорогостоящего процессора память разбивалась на несколько частей, называемых разделами, в каждом из которых выполнялось отдельное задание. Пока одно задание ожидало завершения работы устройства ввода-вывода, другое могло использовать центральный процессор. Из важного: подкачка данных (при окончании выполнения каждого текущего задания операционная система могла загружать новое задание с диска в освободившийся раздел памяти и запускать это задание).

4. Четвертое поколение (с 1980 по наши дни): персональные компьютеры. Следующий период в эволюции вычислительных систем связан с появлением больших интегральных схем (БИС). В эти годы произошло резкое возрастание степени интеграции и снижение стоимости микросхем. Компьютер, не отличающийся по архитектуре от PDP-11, по цене и простоте эксплуатации стал доступен отдельному человеку, а не отделу предприятия или университета. Наступила эра персональных компьютеров. Первоначально персональные компьютеры предназначались для использования одним пользователем в однопрограммном режиме, что повлекло за собой деградацию архитектуры этих ЭВМ и их операционных систем (в частности, пропала необходимость защиты файлов и памяти, планирования заданий и т. п.).

5. Пятое поколение (с 1990 по наши дни): мобильные компьютеры. Хотя идея объединения в одном устройстве и телефона, и компьютера вынашивалась еще с 1970-х годов, первый настоящий смартфон появился только в середине 1990-х годов, когда Nokia выпустила свой N9000, представлявший собой комбинацию из двух отдельных устройств: телефона и КПК. В 1997 году в компании Ericsson для ее изделия GS88 «Penelope» был придуман термин «смартфон».

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

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

Страничная организация. Виртуальное адресное пространство состоит из блоков фиксированного размера, называемых страницами. Соответствующие блоки в физической памяти называются страничными блоками. Страницы и страничные блоки имеют, как правило, одинаковые размеры. В нашем примере их размер составляет 4 Кбайт, но в реальных системах используются размеры страниц от 512 байт до 1 Гбайт. При наличии 64 Кбайт виртуального адресного пространства и 32 Кбайт физической памяти мы получаем 16 виртуальных страниц и 8 страничных блоков. Перенос информации между оперативной памятью и диском всегда осуществляется целыми страницами.

Таблицы страниц. При простой реализации отображение виртуальных адресов на физические может быть сведено к следующему: виртуальный адрес делится на номер виртуальной страницы (старшие биты) и смещение (младшие биты). К примеру, при 16-разрядной адресации и размере страниц 4 Кбайт старшие 4 бита могут определять одну из 16 виртуальных страниц, а младшие 12 бит — смещение в байтах (от 0 до 4095) внутри выбранной страницы. Но для страницы также можно выделить 3, или 5, или какое-нибудь другое количество битов. Различные варианты выделения подразумевают различные размеры страниц. Номер виртуальной страницы используется в качестве индекса внутри таблицы страниц, который нужен для поиска записи для этой виртуальной страницы. Из записи в таблице страниц берется номер страничного блока (если таковой имеется). Номер страничного блока присоединяется к старшим битам смещения, заменяя собой номер виртуальной страницы, чтобы сформировать физический адрес, который может быть послан к памяти. Таким образом, предназначение таблицы страниц заключается в отображении виртуальных страниц на страничные блоки. С математической точки зрения таблица страниц — это функция, в которой в качестве аргумента выступает номер виртуальной страницы, а результатом является номер физического блока. При использовании результата этой функции поле виртуальной страницы в виртуальном адресе можно заменить полем страничного блока, формируя таким образом адрес физической памяти. Структура записи в таблице. Наиболее важным является поле номера страничного блока.

Следующим по значимости является бит присутствия-отсутствия. Если он установлен в 1, запись имеет смысл и может быть использована. А если он установлен в 0, то виртуальная страница, которой принадлежит эта запись, в данный момент в памяти отсутствует. Обращение к записи таблицы страниц, у которой этот бит установлен в 0, вызывает ошибку отсутствия страницы. Биты защиты сообщают о том, какого рода доступ разрешен. В простейшей форме это поле состоит из 1 бита со значением 0 для чтения-записи и значением 1 только для чтения. При более сложном устройстве имеется 3 бита, по одному для разрешения чтения, записи и исполнения страницы. Биты модификации и ссылки отслеживают режим использования страницы. Когда в страницу осуществляется запись, аппаратура автоматически устанавливает бит модификации. Этот бит имеет значение, когда операционная система решает регенерировать страничный блок. Если содержащаяся в нем страница изменена, ее нужно сбросить обратно на диск. Если же она не изменена, от нее можно отказаться. Бит ссылки устанавливается при обращении к странице как для чтения, так и для записи. Он призван помочь операционной системе выбрать выселяемую страницу при возникновении ошибки отсутствия страницы. Страницы, к которым не было обращений, являются более предпочтительными кандидатами, чем востребуемые. Оставшийся бит позволяет блокировать кэширование страницы. Эта возможность актуальна для тех страниц, которые отображаются на регистры устройств, а не на память. Если ОС вошла в цикл ожидания отклика какого-нибудь устройства ввода-вывода на только что выданную ею команду, чтобы аппаратура продолжала извлечение слова из устройства, а не из старой копии в кэше. Благодаря этому биту кэширование может быть отключено. Те машины, у которых есть отдельное пространство ввода-вывода и которые не используют ввод-вывод с отображением данного пространства в память, в этом бите не нуждаются.

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

7. Опишите механизмы работы буфера быстрого преобразования адреса, многоуровневых и инвертированных таблицы страниц.

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

+: простота и отсутствие каких-либо обращений к памяти во время отображения.

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

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

+: позволяет отображению виртуальной памяти на физическую меняться при переключении контекста путем перезагрузки всего лишь одного регистра.

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

Буферы быстрого преобразования адреса (увеличение скорости). При страничной организации памяти понадобится как минимум еще одно обращение к памяти для доступа к таблице страниц. Поскольку скорость выполнения обычно ограничена скоростью, с которой центральный процессор может извлечь инструкцию и данные из памяти, необходимость осуществления при каждом обращении к памяти двух обращений снижает производительность вдвое. При таких условиях использовать страничную организацию памяти никто не станет. Найденное решение — в оснащении компьютеров небольшим устройством для отображения виртуальных адресов на физические без просмотра таблицы страниц. Состояние этого устройства, названного буфером быстрого преобразования адреса (TLB), которое иногда еще называют ассоциативной памятью (зачастую это устройство находится внутри диспетчера памяти и состоит из небольшого количества записей):

Это циклический процесс, занимающий виртуальные страницы 19, 20 и 21, поэтому их записи в TLB имеют коды защиты, разрешающие чтение и исполнение. Основные данные, используемые в этот момент, занимают страницы 129 и 130. Страница 140 содержит индексы, используемые при вычислениях, производимых с элементами массива. И наконец, стек занимает страницы 860 и 861.

Многоуровневые и инвертированные таблицы страниц (обслуживание больших пространств). Многоуровневые. Секрет метода использования многоуровневой таблицы страниц в отказе от постоянного хранения всех таблиц страниц в памяти. В частности, вообще не должны храниться те таблицы, в которых нет необходимости. Предположим, к примеру, что процессу требуются 12 Мбайт: нижние 4 Мбайт памяти — для текста программы, следующие 4 Мбайт — для данных и верхние 4 Мбайт — для стека. Между верхней границей данных и дном стека образуется огромная неиспользуемая дыра.

На б показано, как работает двухуровневая таблица страниц. Слева — таблица страниц верхнего уровня, содержащая 1024 записи, соотносящиеся с 10-битным полем PT1. Когда диспетчеру памяти предоставляется виртуальный адрес, то сначала он извлекает поле PT1 и использует его значение в качестве индекса для таблицы страниц верхнего уровня. Из записи, место которой определяется путем индексирования таблицы страниц верхнего уровня, извлекается адрес или номер страничного блока таблицы страниц второго уровня. Запись 0 таблицы страниц верхнего уровня указывает на таблицу страниц для текста программы, запись 1 — на таблицу страниц для данных, а запись 1023 — на таблицу страниц для стека. Другие (закрашенные) записи не используются. Поле PT2 теперь используется в качестве индекса на выбранную таблицу страниц второго уровня для поиска номера страничного блока для самой страницы.