Операционные системы (шпаргалка)

1. Операционная система. Определение. Функции операционных систем.

Функции:

По современным представлениям, ОС должна уметь делать следующее:

Обеспечивать загрузку пользовательских программ в оперативную память и их исполнение.

Обеспечивать работу с устройствами долговременной памяти, такими как магнитные диски, ленты, оптические диски и т.д. Как правило, ОС управляет свободным пространством на этих носителях и структурирует пользовательские данные.

Предоставлять более или менее стандартный доступ к различным устройствам ввода/вывода, таким как терминалы, модемы, печатающие устройства.

Предоставлять некоторый пользовательский интерфейс. Слово некоторый здесь сказано не случайно - часть систем ограничивается командной строкой, в то время как другие на 90% состоят из средств интерфейса пользователя.

Более развитые ОС предоставляют также следующие возможности:

Параллельное (точнее, псевдопараллельное, если машина имеет только один процессор) исполнение нескольких задач.

Распределение ресурсов компьютера между задачами.

Организация взаимодействия задач друг с другом.

Взаимодействие пользовательских программ с нестандартными внешними устройствами.

Организация межмашинного взаимодействия и разделения ресурсов.

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

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

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

ДОС (Дисковые Операционные Системы)

Это системы, берущие на себя выполнение только первых четырех функций. Как правило, это просто некий резидентный набор подпрограмм, не более того. Он загружает пользовательскую программу в память и передает ей управление, после чего программа делает с системой все, что ей заблагорассудится. Считается желательным, чтобы после завершения программы машина оставалась в таком состоянии, чтобы ДОС могла продолжить работу. Если же программа приводит машину в какое-то другое состояние...\ что ж, ДОС ничем ей в этом не может помешать. Характерный пример - различные загрузочные мониторы для машин класса Spectrum. Как правило, такие системы работают одновременно только с одной программой.

Дисковая операционная система MS DOS для IBM PC-совместимых машин является прямым наследником одного из таких резидентных мониторов. Она, правда, умеет загружать несколько программ, но не предоставляет средств для исполнения этих программ. Более того, с точки зрения документированных функций, этим программам нельзя работать. Конечно, есть еще недокументированные задние двери (backdoors)...\

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

ОС

К этому классу относятся системы, берущие на себя выполнение всех вышеперечисленных функций. Разделение на ОС и ДОС идет, по-видимому, от систем IBM DOS/360 и OS/360 для больших компьютеров этой фирмы, клоны которых известны у нас в стране под названием ЕС ЭВМ серии 10XX. (Кстати, у IBM была еще TOS/360, Tape Operating System - Ленточная Операционная Система).

Здесь под ОС мы будем подразумевать системы ``общего назначения'', то есть рассчитанные на интерактивную работу одного или нескольких пользователей в режиме разделения времени, при не очень жестких требованиях на время реакции системы на внешние события. Как правило, в таких системах уделяется большое внимание защите самой системы, программного обеспечения и пользовательских данных от ошибочных и злонамеренных программ и пользователей. Обычно такие системы используют встроенные в архитектуру процессора средства защиты и виртуализации памяти. К этому классу относятся такие широко распространенные системы, как VAX/VMS, системы семейства Unix и OS/2, хотя последняя не обеспечивает одновременной работы нескольких пользователей и защиты пользователей друг от друга.

Системы реального времени

Это системы, предназначенные для облегчения разработки так называемых приложений реального времени. Это программы, управляющие некомпьютерным по природе оборудованием, часто с очень жесткими ограничениями по времени. Примером такого приложения может быть программа бортового компьютера крылатой ракеты, системы управления ускорителем элементарных частиц или промышленным оборудованием. Такие системы обязаны поддерживать многопроцессность, гарантированное время реакции на внешнее событие, простой доступ к таймеру и внешним устройствам. Такие системы могут по другим признакам относиться как к классу ДОС (RT-11), так и к ОС (OS-9, QNX). Часто такие системы (например, VxWorks) рассчитаны на работу совместно с управляющей host-машиной, исполняющей ``нормальную'' операционную систему.

5) Архитектура операционной системы. Режимы ядра и приложений. Многослойная архитектура.

Под архитектурой понимается организация ОС. Из основных программных модулей обычно выделяют две группы:

ядро – модули, выполняющие основные функции ОС

модули, выполняющие вспомогательные функции.

Вспомогательные модули делятся на группы:

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

Системные обрабатывающие программы – текстовые или графические редакторы, компиляторы, компоновщики, трансляторы

Программы представляющие пользователю дополнительные услуги

Библиотеки процедур различного назначения

Модули ОС, оформленные в виде утилит, системных обрабатывающих программ и библиотек - ? –

Ядро в привилегированном режиме.

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

Аппаратура компьютера должна поддерживать минимум два режима работы – пользовательский и привилегированный (режим ядра)

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

Системный вызов инициирует переключение процессора из пользовательского в привилегированный режим, а при возврате к приложению – обратный процесс.

2. Операционная система. Определение. Эволюция операционных систем.

1945-55:

Были созданы первые ламповые вычислительные устройства. Программирование исключительно на машинном языке. ОС не было. Для программирования использовался пульт управления. Из системного обеспечения были библиотеки математических и служебных подпрограмм.

1955-65:

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

1965-80:

Произошел переход к ИМС. Появились программно-совместимые машины, что потребовало появления совместимых ОС. Большое распространение получили системы подобные ОС/360. Главным достоинством ОС было появление мультипрограммирования – это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются несколько программ. Появились системы разделения времени, при которых создавалась иллюзия единоличного использования машины каждым пользователем.

1980-…

Потребовалась разработка дружественного интерфейса, из-за широкого распространения компьютеров. Первыми такими ОС были MS-DOS и Unix.

6. Микроядерная архитектура

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

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

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

Достоинства:

− более простая организация чем у монолитных ОС;

− с микроядром функция операционной системы разбивается на модульные части, которые могут быть сконфигурированы целым рядом способов, позволяя строить большие системы добавлением новых частей;

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

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

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

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

Недостатки:

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

7. Средства аппаратной поддержки ОС

-- средства поддержки привелигерованного режима: обычно реализуется на основе системы регистров процессора;

-- средства трансляции адресов: выполняются операции преобразования виртуальных адресов (в кодах процессора) а адреса физической памяти;

-- средства переключения процессов: предназначены для быстрого сохранения приостанавливаемого контекста и восстановления контекста, который становится активным (контекст – содержимое всех регистров общего назначения, регистров флага, а также всех системных регистров, которые связаны с отдельным процессом);

-- системный таймер: быстродействующий регистр, счетчик используемый ОС для выдержки интервалов времени;

-- прерывания, система прерываний;

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

8. Иерархия памяти. Управление памятью без использования внешней памяти.

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

9. Способы управления оперативной памятью. Типы адресов. Страничное распределение памяти, сегментное, сегментно-страничное распределение.

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

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

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

12.Кэширование данных. Принцип работы кэш-памяти. Способы отображения данных на кэш.

Кэширование данных. Кэш-память - это способ организации совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным за счет динамического копирования в "быстрое" ЗУ наиболее часто используемой информации из "медленного" ЗУ.

Механизм кэш-памяти является прозрачным для пользователя, который не должен сообщать никакой информации об интенсивности использования данных и не должен никак участвовать в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами.

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

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

1.Просматривается содержимое кэш-памяти с целью определения, не находятся ли нужные данные в кэш-памяти; кэш-память не является адресуемой, поэтому поиск нужных данных осуществляется по содержимому - значению поля "адрес в оперативной памяти", взятому из запроса.

Многослойная архитектура.

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

Ядро ОС имеет также сложную структуру и может содержать следующие слои

средства аппаратной поддержки ОС

машинно-зависимые модули

базовые механизмы ядра

менеджеры ресурсов

интерфейс системных вызовов.

Средства аппаратной поддержки включают в себя несколько пунктов

средства поддержки привилегированного режима

средства трансляции адресов

средства переключения процессов

системный таймер

система прерываний

средства защиты областей памяти

* Гарантированное время реакции на внешнее событие является отличительным признаком систем РВ. Требование гарантированного времени реакции налагает специфические требования на архитектуру ОС; большинство современных ОС общего назначения непригодно для задач РВ.
*

Любопытно, что новомодное течение в компьютерной технике - multimedia - при качественной реализации предъявляет к системе те же требования, что и промышленные задачи реального времени. В multimedia основной проблемой является синхронизация изображения на экране со звуком. Именно в таком порядке. Звук обычно генерируется внешним аппаратным устройством с собственным таймером, и изображение синхронизуется с ним же. Человек способен заметить довольно малые временные неоднородности в звуковом потоке. Напротив, пропуск кадров в визуальном потоке не так заметен, а расхождение звука и изображения заметно уже при задержках около 30 мс. Поэтому системы качественного multimedia должны обеспечивать синхронизацию с такой же или более высокой точностью, что мало отличается от систем мягкого реального времени

Кросс-загрузчики

Это системы - полностью ориентированные на работу с host-машиной. Чаще всего они используются для написания и отладки кода, позднее прошиваемого в ПЗУ. Это системы программирования микроконтроллеров семейства Intel 8048 и подобных им, TDS (Transputer Development System) фирмы Inmos, и многие другие. Такие системы, как правило, включают в себя набор компиляторов и ассемблеров, работающих на host-системе (реже - загружаемых с host-машины в целевую систему), библиотеки, выполняющие большую часть функций ОС при работе программы (но не загрузку этой программы!), и средства отладки.

Системы промежуточных типов

Существуют системы, которые с первого взгляда нельзя отнести к одному из вышеперечисленных классов. Такова, например, система RT-11, которая, по сути своей, является ДОС, но позволяет одновременное исполнение нескольких программ с довольно богатыми средствами взаимодействия и синхронизации. Другим примером промежуточной системы являются MS Windows 3.x и Windows 95 которые, как ОС, используют аппаратные средства процессора для защиты и виртуализации памяти и даже могут обеспечивать некоторое подобие многозадачной работы, но не защищают себя и программы от ошибок других программ.

В последнее время вошел в употребление еще один термин: сетевые ОС, или сокращенно NOS (Networking Operating System). На взгляд авторов, сложившееся использование этого термина несколько неудачно. Его можно употреблять в двух различных смыслах:

Системы, предназначенные для предоставления сетевых услуг, аналогично тому, как ДОС предназначена для предоставления средств работы с диском. Под такое понимание NOS подходят узкоспециализированные системы, такие как Novell Netware, K9Q или программное обеспечение маршрутизаторов Cisco.

Системы, способные предоставлять сетевые услуги. Под такое определение подходят практически все современные ОС общего назначения.

Судя по тому, что большинство ``обзоров сетевых операционных систем'' в компьютерных журналах сравнивают не маршрутизатор Cisco с K9Q, а Windows NT с SunSoft Solaris или OS/2, термин NOS в этих публикациях понимается во втором смысле. Как уже говорилось, практически все современные ОС и некоторые ДОС способны предоставлять сетевые сервисы, поэтому этот термин почти эквивалентен словам ``Современная ОС общего назначения'' и, таким образом, почти не несет полезной информации.

2.Если данные обнаруживаются в кэш-памяти, то они считываются из нее, и результат передается в процессор.

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

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

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

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

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

Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса.

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

. Распределение памяти разделами переменной величины(динамическими). В этом случае память машины не делится заранее на разделы. Сначала вся память свободна. Каждой вновь поступающей задаче выделяется необходимая ей память. Если достаточный объем памяти отсутствует, то задача не принимается на выполнение и стоит в очереди. После завершения задачи память освобождается, и на это место может быть загружена другая задача. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. Например в момент t0 в памяти находится только ОС, а к моменту t1 память разделена между 5 задачами, причем одна из задач, завершаясь, покидает память. На освободившееся место после этой задачи загружается другая задача, поступившая в момент t3. Задачами операционной системы при реализации данного метода управления памятью является: (1) ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти; (2)при поступлении новой задачи - анализ запроса, просмотр таблицы свободных областей и выбор раздела, размер которого достаточен для размещения поступившей задачи; (3) загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых областей; (4) после завершения задачи корректировка таблиц свободных и занятых областей. По сравнению с методом распределения памяти фиксированными разделами данный метод обладает гораздо большей гибкостью, но ему присущ очень серьезный недостаток - фрагментация памяти. Фрагментация - это наличие большого числа несмежных участков свободной памяти очень маленького размера (фрагментов). Настолько маленького, что ни одна из вновь поступающих программ не может поместиться ни в одном из участков, хотя суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый объем памяти. Распределение памяти перемещаемыми разделами. Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших либо в сторону младших адресов, так, чтобы вся свободная память образовывала единую свободную область. В дополнение к функциям, которые выполняет ОС при распределении памяти переменными разделами, в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется "сжатием". Сжатие может выполняться либо при каждом завершении задачи, либо только тогда, когда для вновь поступившей задачи нет свободного раздела достаточного размера.

13.Кэш-память. Случайное отображение данных на кэш. Выполнение запроса в системах с кэш памятью.

Кэш-память-способ организации совместного функц-ия двух типов ЗУ, отличающихся временем доступа и стоимостью хранения данных, кот. позволяет уменьшить время доступа к данным за счет динамического копирования в "быстрое" ЗУ наиболее часто используемой информации из "медленного" ЗУ.

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

В реальных системах вероятность попадания в кэш составляет примерно 0,9. Высокое значение вероятности связано с наличием у данных свойств: пространственной и временной локальности.

Пространственная локальность. Если произошло обращение по некоторому адресу, то с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам.

Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по этому же адресу с большой вероятностью произойдет в ближайшее время.

В системах, оснащенных кэш-памятью, каждый запрос к оперативной памяти выполняется в соответствии со следующим алгоритмом:

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

Если данные обнаруживаются в кэш-памяти, то они считываются из нее, и результат передается в процессор.

14.Кэш-память. Прямое отображение данных на кэш. Выполнение запроса в системах с кэш памятью.

Если данные обнаруживаются в кэш-памяти, то они считываются из нее, и результат передается в процессор.

15.Двухуровневое кэширование. Принцип работы. Выполнение запроса с системах с многоуревневой кэш памятью.

Каждый процессор для своей работы использует двухуровневый кэш со свойствами охвата. Это означает, что кроме внутреннего кэша первого уровня (кэша L1), встроенного в каждый процессор PowerPC, имеется связанный с ним кэш второго уровня (кэш L2). При этом каждая строка в кэше L1 имеется также и в кэше L2. В настоящее время объем кэша L2 составляет 1 Мбайт на каждый процессор, а в будущих реализациях предполагается его расширение до 4 Мбайт. Сама по себе кэш-память второго уровня позволяет существенно уменьшить число обращений к памяти и увеличить степень локализации данных. Для повышения быстродействия кэш L2 построен на принципах прямого отображения. Длина строки равна 32 байт (размеру когерентной гранулированности системы). Следует отметить, что, хотя с точки зрения физической реализации процессора PowerPC, 32 байта составляют только половину строки кэша L1, это не меняет протокол когерентности, который управляет операциями кэша L1 и гарантирует что кэш L2 всегда содержит данные кэша L1.

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

16.Способы загрузки программ. Относительная и абсолютная загрузка. Оверлеи.

Абсолютная загрузка. Самый простой вариант состоит в том, что мы всегда будем загружать программу с одного и того же адреса. Это возможно если: система может предоставить программе свое адресное пространство, Система может исполнять в каждый момент только одну программу. Такой модуль называется абсолютным загрузочным модулем – это копия содержимого виртуального пространства проги в момент ее запуска. В системе UNIX используется абсолютная загрузка. Загружаемый файл начинается с заголовка, который содержит: ''магическое число'' - признак того, что это загружаемый модуль, число TEXT_SIZE - длину области кода программы (TEXT), DATA_SIZE - длину области инициализованных данных программы (DATA), BSS_SIZE - длину области неинициализованных данных программы (BSS), Стартовый адрес программы. За заголовком следует содержимое областей TEXT и DATA. Затем может следовать отладочная информация. При загрузке система выделяет программе TEXT_SIZE байтов виртуальной памяти, доступной для чтения/исполнения, и копирует туда содержимое сегмента TEXT. Затем отматывается DATA_SIZE байтов памяти, доступной для чтения/записи, и туда копируется содержимое сегмента DATA. Затем отматывается еще BSS_SIZE байтов памяти. После этого выделяется пространство под стек, в стек помещаются позиционные аргументы и среда исполнения, и управление передается на стартовый адрес. Программа начинает исполняться.

Относительная загрузка. Загрузка состоит в том, что мы грузим программу каждый раз с нового адреса. При этом мы должны настроить ее на новые адреса, а для этого прога представляет собой послед-ть команд. В процессорах 70-80-х гг у команды м.б. переменное количество таких полей(0-6). У современных RISC-процессоров кол-во полей меньше. Существуют три способа вычисления адреса в команде. 1: берется адресное поле и говорится, что это будет наш виртуальный адрес. Это называется абсолютной адресацией.

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

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

Другая проблема - это проблема реентерабельности (reenterability - повтоpной входимости, от re-enter) разделяемых программ.

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

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

Первая, состоит в вопросе - если одна задача производит данные, а вторая их потребляет, то как задача-потребитель узнает, что готова очередная порция данных? Или, что еще интереснее, как она узнает, что очередная порция данных еще не готова?

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

Прерывания и сигналы

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

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

22. Семафор Дийкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих процессов. Над семафором возможно проведение только двух операций - “открытия” и “закрытия”, названных соответственно P- и V- операциями. Существенно, что операции над семафорами являются неделимыми (непрерываемыми), поэтому их часто называют примитивами.

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

Наиболее простым случаем семафора является двоичный семафор. Начальное значение такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна программа.

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

17.Способы загрузки программ. Относительная и абсолютная загрузка. Загрузка операционной системы.

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

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

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

Состояние процессов: в многозадачной системе процесс может находиться в одном из трех основных состояний:

ВЫПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

ОЖИДАНИЕ - пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

В ходе жизненного цикла каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе. Типичный граф состояний процесса показан на рисунке

19. Контекст и дескриптор процесса

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

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

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

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

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

создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст;

включить дескриптор нового процесса в очередь готовых процессов;

загрузить кодовый сегмент процесса в оперативную память или в область свопинга.

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

3 Если нужных данных нет, то они вместе со своим адресом копируются из оперативной памяти в кэш-память, и результат выполнения запроса передается в процессор. При копировании данных может оказаться, что в кэш-памяти нет свободного места, тогда выбираются данные, к которым в последний период было меньше всего обращений, для вытеснения из кэш-памяти. Если вытесняемые данные были модифицированы за время нахождения в кэш-памяти, то они переписываются в оперативную память. Если же эти данные не были модифицированы, то их место в кэш-памяти объявляется свободным. При ассоциативной организации кэша имеются несколько блоков, из кот. надо выбрать кандидата в случае промаха. Для замещения блоков применяются две основных стратегии: случайная и LRU. 1: блоки-кандидаты выбираются случайно. В некоторых системах, чтобы получить воспроизводимое поведение, которое полезно во время отладки аппаратуры, используют псевдослучайный алгоритм замещения. 2: все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех (LRU - Least-Recently Used). Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным. различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма.

Например, один процесс копирует данные со стримера на кассету Exabyte, а другой - в обратном направлении. Доступ к стримеру контролируется семафором sem1, а к кассете - семафором sem2.

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

Эта проблема может быть решена несколькими способами. Первый способ - разрешить программе в каждый момент времени держать закрытым только один семафор - прост и решает проблему в корне, но часто оказывается неприемлемым. Более приемлемым оказывается соглашение, что семафоры всегда должны закрываться в определенном порядке. Этот порядок может быть любым, важно только чтобы он всегда соблюдался. Третий, наиболее радикальный, вариант состоит в предоставлении возможности объединить семафоры и/или операции над ними в неразделяемые группы. При этом программа может выполнить операцию закрытия семафоров sem1 и sem2 единой командой, во время исполнения которой никакая другая программа не может получить

При доступе к нескольким различным ресурсам с использованием семафоров может возникнуть специфическая проблема, называемая мертвой блокировкой (dead lock). Остановимся на ней несколько подробнее.(Тупик)

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

При завершении процедуры обработки вызывается команда RTI (ReTurn from Interrupt - возврат из прерывания). Эта команда выталкивает из стека адрес прерванной команды и старое слово состояния.

Блокировка участков файлов

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

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

В UNIX возможны два режима блокировки: допустимая (advisory) и обязательная (mandatory). Как та, так и другая блокировка может быть блокировкой на чтение либо на запись. Допустимая блокировка является ``блокировкой для честных'': она не оказывает влияния на подсистему ввода/вывода, поэтому программа, не проверяющая блокировок или игнорирующая их, сможет писать или читать из заблокированного участка без проблем. Обязательная блокировка требует больших накладных расходов, но запрещает физический доступ к файлу: чтение или запись, в зависимости от типа блокировки.

Семафоры смотри билет 22

Очевидно, что если мы захотим ''сдвинуть'' прогу по адресам виртуальной памяти, то мы должны будем найти все команды с абсолютными адресными полями и прибавить ко всем этим полям разность нового и старого адресов. 2: мы берем значение одного из регистров процессора, прибавляем к нему значение адресного поля и получаем адрес.Такая адресация называется базовой. Если адрес формируется сложением двух или более регистров c адресным полем, то это называется базово-индексной адресацией. В более сложных ситуациях мы должны: запомнить все места в программе, где загружаются базовые регистры, и добавить к загружаемым значениям новый стартовый адрес. Преимущество состоит в том, что таких мест в программе гораздо меньше, чем при абсолютной адресации. В перемещаемой программе мы должны запоминать все ссылки на абсолютные адреса и в момент загрузки производить их настройку на начальный адрес. Такой файл гораздо сложнее абсолютного загружаемого модуля, и носит название относительного или перемещаемого загрузочного модуля. Именно такой формат имеют .exe-файлы в системе ms-dos. оверлей (over-lay - лежащий сверху) или перекрытие. Смысл оверлея состоит в том, чтобы не загружать программу в память целиком, а разбить ее на несколько модулей и затаскивать их в память по мере необходимости. Потребность в таком способе загрузки появляется, если у нас виртуальное адресное пространство мало, а программа велика. Основная проблема при оверлейной загрузке состоит в следующем: прежде чем ссылаться на оверлейный адрес, мы должны понять, какой из оверлейных модулей в данный момент там находится. Для ссылок на функции это просто: вместо точки входа функции мы вызываем некую процедуру, называемую менеджером перекрытий. Эта процедура знает, какой модуль куда загружен, и при необходимости подкачивает то, что загружено не было. Каждый оверлейный модуль должен быть самодостаточным. Каждый оверлейный модуль может быть как абсолютным, так и перемещаемым.

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

Состояние процессов: в многозадачной системе процесс может находиться в одном из трех основных состояний:

В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

. Очевидно, что если мы захотим ''сдвинуть'' прогу по адресам виртуальной памяти, то мы должны будем найти все команды с абсолютными адресными полями и прибавить ко всем этим полям разность нового и старого адресов. 2: мы берем значение одного из регистров процессора, прибавляем к нему значение адресного поля и получаем адрес. Такая адресация называется базовой. Если адрес формируется сложением двух или более регистров c адресным полем, то это называется базово-индексной адресацией. В более сложных ситуациях мы должны: запомнить все места в программе, где загружаются базовые регистры, и добавить к загружаемым значениям новый стартовый адрес. Преимущество состоит в том, что таких мест в программе гораздо меньше, чем при абсолютной адресации. В перемещаемой программе мы должны запоминать все ссылки на абсолютные адреса и в момент загрузки производить их настройку на начальный адрес. Такой файл гораздо сложнее абсолютного загружаемого модуля, и носит название относительного или перемещаемого загрузочного модуля. Именно такой формат имеют .exe-файлы в системе ms-dos. Загрузка ОС. Рассмотрим на примере UNIX. Имеется специальная инициализационная программа, которая так и называется - init. Эта программа запускает различные процессы-демоны, например cron - программу, которая умеет запускать другие заданные ей программы в заданные моменты времени, различные сетевые сервисы, программы, которые ждут ввода с терминальных устройств (getty) то, что она запускает задается в специальном файле /etc/inittab. Администратор системы может редактировать этот файл и устанавливать те сервисы, которые в данный момент нужны, избавляться от тех, которые не нужны, и т.д. Существуют ОСы, которые не умеют самостоятельно выполнять весь цикл . Они используют более примитивную операционную систему, которая исполняет их вторичный загрузчик, и помогает этому загрузчику затянуть в память ядро ОС. На пример MS Windows используют DOS.

20. Планирование процессов включает в себя решение следующих задач: 1) определение момента времени для смены выполняемого процесса; 2) выбор процесса на выполнение из очереди готовых процессов; 3) переключение контекстов "старого" и "нового" процессов.

Наиболее часто встречаются алгоритмы, основанные: на квантовании, на приоритетах.

В алгоритмах, основанных на квантовании, смена активного процесса происходит, если: 1) процесс завершился и покинул систему; 2) произошла ошибка; 3) процесс перешел в состояние ОЖИДАНИЕ; 4) исчерпан квант процессорного времени, отведенный данному процессу.

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

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

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

Во многих ОС алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.

Вопрос 23. Потоки (нити) управления. Определение, назначение, состояния, операции.

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

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

Нити иногда называют облегченными процессами или мини-процессами. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ.

Вопрос 24. Программное и аппаратное обеспечение устройств ввода-вывода.

Устройства ввода-вывода делятся на два типа: блок-ориентированные устройства и байт-ориентированные устройства. Блок-ориентированные устройства хранят информацию в блоках фиксированного размера, каждый из которых имеет свой собственный адрес. Самое распространенное блок-ориентированное устройство - диск. Байт-ориентированные устройства не адресуемы и не позволяют производить операцию поиска, они генерируют или потребляют последовательность байтов. Примерами являются терминалы, строчные принтеры, сетевые адаптеры. Электронный компонент называется контроллером устройства или адаптером. Операционная система имеет дело с контроллером. Контроллер выполняет простые функции, осуществляет контроль и исправляет ошибки. Каждый контроллер имеет несколько регистров, которые используются для взаимодействия с центральным процессором. ОС выполняет ввод-вывод, записывая команды в регистры контроллера. Контроллер гибкого диска IBM PC принимает 15 команд, таких как READ, WRITE, SEEK, FORMAT и т.д. Когда команда принята, процессор оставляет контроллер и занимается другой работой. При завершении команды контроллер организует прерывание для того, чтобы передать управление процессором операционной системе, которая должна проверить результаты операции. Процессор получает результаты и статус устройства, читая информацию из регистров контроллера.

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

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

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

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

Вопрос 25. Файловая система. Файлы с точки зрения пользователя и системы. Логическая организация файла.

Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совместное использование файлов несколькими пользователями и процессами. В широком смысле понятие "файловая система" включает: 1)совокупность всех файлов на диске 2) наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске 3)комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами.

Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времени эти границы были весьма узкими. Так в популярной файловой системе FAT длина имен ограничивается известной схемой 8.3 (8 символов - собственно имя, 3 символа - расширение имени). Однако пользователю гораздо удобнее работать с длинными именами. При переходе к длинным именам возникает проблема совместимости с ранее созданными приложениями, использующими короткие имена. Таким образом, одной из важных задач становится проблема генерации соответствующих коротких имен. При реализации нового варианта FAT важной задачей была задача хранения длинных имен при условии, что принципиально метод хранения и структура данных на диске не должны были измениться.

Файлы бывают разных типов: 1)обычные файлы 2)специальные файлы 3)файлы-каталоги.

1)Обычные файлы в свою очередь подразделяются на текстовые и двоичные. Текстовые файлы состоят из строк символов, представленных в ASCII-коде. Это могут быть документы, исходные тексты программ и т.п. Двоичные файлы не используют ASCII-коды, они часто имеют сложную внутреннюю структуру, например, объектный код программы или архивный файл. 2)Специальные файлы - это файлы, ассоциированные с устройствами ввода-вывода, которые позволяют пользователю выполнять операции ввода-вывода, используя обычные команды записи в файл или чтения из файла.

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

Вопрос 26. Файловые системы. Общая структура и функционирование.

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

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

Рис. 1. Физическая организация файла

Популярным способом является использование связанного списка индексов. С каждым блоком связывается некоторый элемент – индекс (см. рис 1,в). Индексы располагаются в отдельной области диска (в MS-DOS это таблица FAT). Если некоторый блок распределен некоторому файлу, то индекс этого блока содержит номер следующего блока данного файла.

Определить права доступа к файлу - значит определить для каждого пользователя набор операций, которые он может применить к данному файлу. Этот список может включать следующие операции: 1)создание файла 2)уничтожение файла 3)открытие файла и т.д. Права доступа могут быть описаны матрицей прав доступа (см. рис. 2). В некоторых системах пользователи могут быть разделены на отдельные категории. Для всех пользователей одной категории определяются единые права доступа.

Вопрос 27. Примеры организации файловых систем.

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

Рис. 1. Архитектура современной файловой системы

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

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

Cписок вопросов
к экзамену «Операционные системы»

Введение в операционные системы:

Операционная система. Определение. Функции операционных систем.

Операционная система. Определение. Эволюция операционных систем.

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

Обзор современных операционных систем.

Архитектура операционной системы и ядра:

Архитектура операционной системы. Режимы ядра и приложений. Многослойная архитектура.

Архитектура операционной системы. Режимы ядра и приложений. Микроядерная архитектура. Достоинства и недостатки микроядерной архитектуры.

Архитектура операционной системы. Режимы ядра и приложений. Средства программной и аппаратной поддержки операционной системы.

Управление памятью:

Иерархия памяти. Управление памятью без использования внешней памяти.

Способы управления оперативной памятью. Типы адресов. Страничное распределение памяти, сегментно-страничное распределение.

Способы управления оперативной памятью. Типы адресов. Сегментное распределение памяти, сегментно-страничное распределение.

Способы управления оперативной памятью. Типы адресов. Сегментно-страничное распределение.

Кэширование данных. Принцип работы кэш-памяти. Способы отображения данных на кэш.

Кэш-память. Случайное отображени данных на кэш. Выполнение запроса с системах с кэш памятью.

Кэш-память. Прямое отображени данных на кэш. Выполнение запроса с системах с кэш памятью.

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

Для решения поставленных проблем целесообразно разделить программное обеспечение ввода-вывода на четыре слоя (см. рис. 1) 1)Обработка прерываний 2)Драйверы устройств 3)Независимый от устройств слой операционной системы 4)Пользовательский слой программного обеспечения.

Рис.1. Многоуровневая организация подсистемы ввода-вывода

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

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

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

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

Нити имеют собственные: 1)программный счетчик 2)стек 3)регистры 4)нити-потомки 5)состояние.

Нити разделяют: 1)адресное пространство 2)глобальные переменные 3)открытые файлы 4)таймеры 5)семафоры 6)статистическую информацию.

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

Вытесняющие и не вытесняющие алгоритмы планирования

Non-preemptive multitasking - невытесняющая многозадачность - это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику ОС для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.

Preemptive multitasking - вытесняющая многозадачность - это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком ОС, а не самой активной задачей.

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

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

Однако распределение функций планировщика между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом исключаются нерациональные прерывания программ в "неудобные" для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу.

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

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

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

Рис. 2. Матрица прав доступа

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

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

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

Рис. 3. Общая модель файловой системы

Иерархия каталогов может быть деревом или сетью. Каталоги образуют дерево, если файлу разрешено входить только в один каталог, и сеть - если файл может входить сразу в несколько каталогов. В MS-DOS каталоги образуют древовидную структуру, а в UNIX'е - сетевую.

Рис. 1. Логическая организация файловой системы
а - одноуровневая; б - иерархическая (дерево); в - иерархическая (сеть)

Программист имеет дело с логической организацией файла, представляя файл в виде определенным образом организованных логических записей. Логическая запись - это наименьший элемент данных, которым может оперировать программист при обмене с внешним устройством. Даже если физический обмен с устройством осуществляется большими единицами, операционная система обеспечивает программисту доступ к отдельной логической записи. На рис. 2 показаны несколько схем логической организации файла. Записи могут быть фиксированной длины или переменной длины. Записи могут быть расположены в файле последовательно (последовательная организация) или в более сложном порядке. В файловых системах ОС UNIX и MS-DOS файл имеет простейшую логическую структуру - последовательность однобайтовых записей.

Рис. 2. Способы логической организации файлов

Процессы:

Способы загрузки программ. Относительная и абсолютная загрузка. Оверлеи.

Способы загрузки программ. Относительная и абсолютная загрузка. Загрузка операционной системы.

Определение термина "процесс". Процессы и программы. Состояния процесса. Операции над процессами.

Контекст и дескриптор процесса. Определение термина "процесс". Состояния процесса.

Планирование процессов. Вытесняющие и невытесняющие алгоритмы планирования.

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

Cемафоры: определение, назначение, реализация.

Потоки (нити) управления. Определение, назначение, состояния, операции.

Устройства ввода-вывода, файловая система:

Программное и аппаратное обеспечение устройств ввода-вывода.

Файловая система. Файлы с точки зрения пользователя и системы. Логическая организация файла.

Файловые системы. Общая структура и функционирование.

Примеры организации файловых систем.

Аппаратная поддержка операционных систем:

Механизм прерываний процессоров семейства i80x86.

Устройство процессоров i80x86. Назначение и традиционное применение регистров.

Кодогенерация для языков высокого уровня: базовые блоки и способы адресации структур данных.