Операционные системы
Краткий очерк истории операционных систем. Классификация периферийных устройств и их архитектура. Характеристики файлов и архитектура файловых систем. Распределение памяти без использования виртуальных адресов. Драйверы устройств в Windows, UNIX.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 01.02.2011 |
| Размер файла | 418,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Функция CreateFile может использоваться для работы с файлами любой файловой системы, поддерживаемой Windows (в частности, FAT и NTFS).
Параметры этой функции многочисленны и дают достаточно хорошее представление о возможностях работы с файлами в Windows. Некоторые параметры имеют смысл только для NTFS (но не для FAT) или только для Windows NT (но не для Windows 95). Список параметров включает в себя следующие параметры.
Имя файла (включая путь к каталогу, если файл расположен не в текущем каталоге). Вместо имени файла может также быть указано специальное имя устройства, в том числе даже имя физического или логического диска.
Режим доступа. Может быть указан доступ для чтения, для записи или их комбинация.
Режим разделения. Он может включать в себя разрешение другим процессам читать файл, записывать данные в файл, удалять файл или любую комбинацию этих разрешений, в том числе, разумеется, и отсутствие всех разрешений.
Атрибуты защиты. Их использование будет описано в п. 3.8.4.2.
Режим создания. Определяет действия функции в случаях, когда файл с заданным именем уже существует и когда не существует. Определены следующие режимы.
CREATE_NEW - Создается новый файл. Если файл уже существует, выдается ошибка.
CREATE_ALWAYS - Создается новый файл в любом случае, даже если файл с таким именем уже существует.
OPEN_EXISTING - Открывается существующий файл. Выдает ошибку, если файл не существует.
OPEN_ALWAYS - Если файл существует, то он открывается, если не существует - создается новый файл.
TRUNCATE_EXISTING - Открывается существующий файл, но все его содержимое удаляется. Если файл не существует, выдается ошибка.
Большой набор атрибутов и флагов, который следует рассмотреть подробнее. В данном случае атрибутами называются признаки файла, которые устанавливаются при его создании, а флагами - признаки, уточняющие режим работы с открытым файлом.
К атрибутам файла относятся все те, которые Windows унаследовала от MS-DOS (только для чтения, скрытый, системный, архивный), а также атрибут «сжатый» (т.е. файл, создаваемый в NTFS, будет храниться в сжатом виде) и атрибут «временный». Этот атрибут означает, что файл, вероятно, будет скоро удален, а поэтому система должна попытаться удержать его данные в памяти, не тратя зря время на запись файла на диск.
Флаги функции предоставляют, в частности, следующие возможности:
при операциях записи немедленно выполнять запись на диск (очищать кэш-буфера файла);
вообще исключить использование кэша для данного файла, всегда записывать и читать секторы данных непосредственно с диска;
указать системе желательность оптимальной буферизации для последовательного доступа или, наоборот, для произвольного доступа;
открыть файл для выполнения асинхронных операций;
указать системе, что файл должен быть автоматически удален сразу же, как только он будет закрыт.
Функция CreateFile возвращает хэндл открытого файла. Этот хэндл может затем использоваться при обращении к функциям чтения, записи, перемещения указателя, очистки буферов, блокирования фрагментов, закрытия фала и др.
Чтение и запись данных при синхронных операциях начинается с текущей позиции указателя и сопровождается смещением указателя чтения/записи вперед на количество прочитанных/записанных байт. Однако если при открытии файла был указан флаг асинхронных операций, то указатель не используется. Вместо этого при каждом вызове функции чтения или записи должен задаваться дополнительный параметр - смещение от начала файла тех данных, которые следует прочитать или записать.
Как вы думаете, почему при асинхронных операциях не используется указатель чтения/записи?
Процесс, запустивший асинхронную операцию чтения/записи, может затем проверить ее результат с помощью вызова системной функции, которая, в зависимости от параметров, либо ожидает завершения операции, либо просто проверяет, завершилась ли она. Кроме того, есть возможность связать с завершением асинхронной операции либо событие (event), либо функцию завершения, которая будет вызвана, если операция завершена, а нить процесса, начавшая операцию, вызвала функцию ожидания (см. пп.4.5.5.2, 4.5.5.3 о событиях и функциях ожидания).
Некоторые файловые функции не требуют хэндла, т.е. выполняются над закрытыми файлами. Сюда относятся удаление файла, копирование, переименование, перемещение файла, поиск файла по заданному пути и шаблону имени и т.п. В качестве интересных особенностей файловых операций Windows можно отметить следующие.
Операции копирования файла или перемещения его на другой диск можно выполнить вызовом одной системной функции, даже не открывая файл. В других ОС подобные операции требуют написания целой процедуры.
Специально для замены версий системных программ предусмотрен вариант переименования/перемещения файла с откладыванием фактического выполнения до перезагрузки системы. Иным способом невозможно было бы, например, установить новые версии системных библиотек, поскольку существующие версии постоянно открыты и потому не могут быть удалены иначе как при старте системы.
3.8.4. Защита данных
Средства безопасности в Windows NT/2000/XP представляют собой отдельную подсистему, которая обеспечивает защиту не только файлов, но и других типов системных объектов. Файлы и каталоги NTFS представляют собой наиболее типичные примеры защищаемых объектов.
Как известно, Windows позволяет использовать различные файловые системы, при этом возможности защиты данных определяются архитектурой конкретной файловой системы. Например, если на дисковом томе используется система FAT (где, как нам известно, никаких средств защиты не предусмотрено), то Windows может разве что ограничить доступ ко всему тому, но не к отдельным файлам и каталогам.
3.8.4.1. Аутентификация пользователя
Важным элементом любой системы защиты данных является процедура входа в систему, при которой выполняется аутентификация пользователя. В Windows NT для вызова диалога входа в систему используется известная «комбинация из трех пальцев» - Ctrl+Alt+Del. Как утверждают разработчики, никакая «троянская» программа не может перехватить обработку этой комбинации и использовать ее с целью коллекционирования паролей.
Не хочет ли кто-нибудь попробовать?
Система ищет введенное имя пользователя сначала в списке пользователей данного компьютера, а затем и на других компьютерах текущего домена локальной сети. В случае, если имя найдено и пароль совпал, система получает доступ к учетной записи (account) данного пользователя.
На основании сведений из учетной записи пользователя система формирует структуру данных, которая называется маркером доступа (access token). Маркер содержит идентификатор пользователя (SID, Security IDentifier), идентификаторы всех групп, в которые включен данный пользователь, а также набор привилегий, которыми обладает пользователь.
Привилегиями называются права общего характера, не связанные с конкретными объектами. К числу привилегий, доступных только администратору, относятся, например, права на установку системного времени, на создание новых пользователей, на присвоение чужих файлов. Некоторые скромные привилегии обычно предоставляются всем пользователям (например, такие, как право отлаживать процессы, право получать уведомления об изменениях в файловой системе).
В дальнейшей работе, когда пользователю должен быть предоставлен доступ к каким-либо защищаемым ресурсам, решение о доступе принимается на основании информации из маркера доступа.
3.8.4.2. Дескриптор защиты
Для любого защищаемого объекта Windows (файла, каталога, диска, устройства, семафора, процесса и т.п.) может быть задана специальная структура данных - атрибуты защиты.
Основным содержанием атрибутов защиты является другая структура - дескриптор защиты. Этот дескриптор содержит следующие данные:
идентификатор защиты (SID) владельца объекта;
идентификатор защиты первичной группы владельца объекта;
пользовательский («дискреционный», «разграничительный») список управления доступом (DACL, Discretionary Access Control List);
системный список управления доступом (SACL, System Access Control List).
Пользовательский список управляет разрешениями и запретами доступа к данному объекту. Изменять этот список может только владелец объекта.
Системный список управляет только аудитом доступа данному объекту, т.е. задает, какие действия пользователей по отношению к данному объекту должны быть запротоколированы в системном журнале. Изменять этот список может только пользователь, имеющий права администратора системы.
В Windows, в отличие от многих других ОС, администратор не всесилен. Он не может запретить или разрешить кому бы то ни было, даже самому себе, доступ к чужому файлу. Другое дело, что администратор имеет право объявить себя владельцем любого файла, но потом он не сможет вернуть файл прежнему хозяину. Подобные ограничения вытекают из понимания, что администратор тоже не всегда ангел и, хотя он должен иметь в системе большие права, его действия следует хоть как-то контролировать.
Оба списка управления доступом имеют одинаковую структуру, их основной частью является массив записей управления доступом (ACE, Access Control Entity).
Рассмотрим структуру записи ACE. Она содержит:
тип ACE, который может быть одним из следующих: разрешение, запрет, аудит;
флаги, уточняющие особенности действия данной ACE;
битовая маска видов доступа, указывающая, какие именно действия следует разрешить, запретить или подвергнуть аудиту;
идентификатор (SID) пользователя или группы, чьи права определяет данная ACE.
Более интересен пользовательский список. Он может содержать только записи разрешения и запрета. В начале списка всегда идут запрещающие записи, затем разрешающие.
Когда пользователь запрашивает доступ к объекту (т.е., например, программа, запущенная этим пользователем, вызывает функцию открытия файла), происходит проверка прав доступа. Она выполняется на основе сравнения маркера доступа пользователя со списком DACL. Система просматривает по порядку все записи ACE из DACL, для каждой ACE определяет записанный в ней SID и сверяет, не является ли он идентификатором текущего пользователя или одной из групп, куда входит этот пользователь. Если нет, то данная ACE не имеет к нему отношения и не учитывается. Если да, то выполняется сравнение прав, необходимых пользователю для выполнения запрошенной операции с маской видов доступа из ACE. При этом права анализируются весьма детально: например, открытие файла на чтение подразумевает наличие прав на чтение данных, на чтение атрибутов (в том числе владельца и атрибутов защиты), на использование файла как объекта синхронизации (см. п. 4.5.5.2).
Если в запрещающей ACE найдется хотя бы один единичный бит в позиции, соответствующей одному из запрошенных видов доступа, то вся операция, начатая пользователем, считается запрещенной и дальнейшие проверки не производятся.
Если такие биты будут найдены в разрешающей ACE, то проверка следующих ACE выполняется до тех пор, пока не будут разрешены и все остальные запрошенные виды доступа.
Как выдумаете, почему в списке DACL сначала идут запрещающие ACE, а только потом разрешающие?
Таким образом, говоря кратко, пользователь получит доступ к объекту только в том случае, если все запрошенные им виды доступа явным образом разрешены и ни один их них не запрещен.
В годы перестройки много писалось о двух противоположных принципах: «запрещено все, что не разрешено» или «разрешено все, что не запрещено». В Windows все гораздо строже: запрещено все, что запрещено, и все, что не разрешено.
Список DACL со всеми необходимыми разрешениями и запретами может быть установлен программно при создании файла, а впоследствии программно же может быть изменен владельцем. Можно также изменять разрешения в диалоге, воспользовавшись окном свойств файла.
Имеются также два крайних случая. Список DACL может совсем отсутствовать (для этого достаточно, например, при создании файла указать NULL вместо атрибутов защиты), при этом права доступа не проверяются, все действия разрешены всем пользователям. Список DACL может присутствовать, но иметь нулевую длину (нет ни одной ACE). Как следует из общих правил, в этом случае в доступе будет отказано всем, в том числе и хозяину файла.
4. Управление процессами
4.1. Основные задачи управления процессами
Под управлением процессами понимаются процедуры ОС, обеспечивающие запуск системных и прикладных программ, их выполнение и завершение.
В однозадачных ОС управление процессами решает следующие задачи:
загрузка программы в память, подготовка ее к запуску и запуск на выполнение;
выполнение системных вызовов процесса;
обработка ошибок, возникших в ходе выполнения;
нормальное завершение процесса;
прекращение процесса в случае ошибки или вмешательства пользователя.
Все эти задачи решаются сравнительно просто.
В многозадачном режиме добавляются значительно более серьезные задачи:
эффективная реализация параллельного выполнения процессов на единственном процессоре, переключение процессора между процессами;
выбор очередного процесса для выполнения с учетом заданных приоритетов процессов и статистики использования процессора;
исключение возможности несанкционированного вмешательства одного процесса в выполнение другого;
предотвращение или устранение тупиковых ситуаций, возникающих при конкуренции процессов за системные ресурсы;
обеспечение синхронизации процессов и обмена данными между ними.
4.2. Реализация многозадачного режима
4.2.1. Понятия процесса и ресурса
Согласно определению, данному в /7/, «последовательный процесс (иногда называемый «задача») есть работа, производимая последовательным процессором при выполнении программы с ее данными».
Проанализируем это определение. Оно подчеркивает последовательный характер процесса, т.е. выполнение команд в определенном порядке. Термин «задача» мы будем понимать как синоним термина «процесс» (в некоторых ОС эти термины различаются). Далее, процесс - понятие динамическое. Программа - это текст, процесс - выполнение этого текста. Конечно, на практике мы часто говорим: «программа вызывает функцию», «программа ждет ввода» и т.п., однако, строго говоря, правильнее было бы «процесс, выполняющий программу, вызывает…».
Еще один важный момент в определении - упоминание данных. В многозадачных системах зачастую одна и та же программа может запускаться несколько раз (например, можно несколько раз открыть текстовый редактор Notepad для разных файлов). Это означает, что несколько процессов могут использовать одну и ту же программу, но с разными данными.
При описании работы многозадачных систем основное внимание уделяется вопросам, связанным с параллельным выполнением, т.е. с одновременной работой нескольких процессов. Однако общий термин «параллельное выполнение» объединяет два существенно различных способа организации выполнения процессов - синхронный и асинхронный параллелизм.
Синхронный параллелизм предполагает наличие общей тактовой последовательности, управляющей шагами выполнения параллельно работающих процессов. Синхронная организация используется в некоторых типах многопроцессорных вычислительных систем.
При асинхронном параллелизме никакого общего такта нет. Процессы выполняются независимо друг от друга, при этом не делается никаких предположений об их сравнительной скорости, о соотношении времени выполнения различных фрагментов программ и т.п. Сопоставить продвижение разных процессов можно только в явно заданных точках программы процессов, называемых точками синхронизации. Синхронизация обычно означает ожидание одним процессом какого-либо события, связанного с другим процессом. Например, после разветвления выполнения на две параллельные ветви и выполнения ветвями определенных задач может понадобиться свести ветви воедино: та ветвь, которая закончила свое выполнение раньше, должна дождаться завершения другой ветви. Другой пример: процесс, выполняющий обработку введенных строк, может ждать, пока другой процесс не прочтет очередную строку из файла или с клавиатуры.
Точка синхронизации может быть связана также с обменом данными между процессами. Когда процесс-приемник завершает прием данных, то можно быть, по крайней мере, уверенным, что процесс-источник достиг того места в программе, где он должен был передать данные.
В дальнейшем всюду будет рассматриваться только асинхронный параллелизм, поскольку он характерен для работы ОС.
Другим основополагающим понятием, тесно связанным с управлением процессами, является понятие ресурса. Под ресурсом понимается любой аппаратный или программный объект, который может понадобиться для работы процессов и доступ к которому может при этом вызвать конкуренцию процессов. Говоря упрощенно, ресурс - это нечто дефицитное в вычислительной системе. К важнейшим ресурсам любой системы относятся процессор (точнее сказать, процессорное время), основная память, периферийные устройства, файлы. В зависимости от конкретной ОС, к дефицитным ресурсам могут относиться места в таблице процессов или в таблице открытых файлов, буферы кэша, блоки в файле подкачки и другие системные структуры данных.
Если два процесса никак не связаны логикой своей работы, то никакой синхронизации или обмена данными между ними нет, однако такие процессы все же могут оказывать косвенное влияние друг на друга вследствие конкуренции за ресурсы. Многозадачная ОС управляет доступом процессов к ресурсам. В некоторых случаях система временно закрепляет ресурс за одним процессом, отказывая другим процессам в доступе или заставляя их ждать освобождения ресурса. В других случаях оказывается возможным совместный доступ нескольких процессов к одному ресурсу.
4.2.2. Квазипараллельное выполнение процессов
С точки зрения внешнего наблюдателя, в хорошей многозадачной ОС происходит одновременная, параллельная работа нескольких процессов. Однако понятно, что эта одновременность кажущаяся. На самом деле, если в системе работает лишь один процессор, то в каждый момент времени он выполняет команды, относящиеся только к одному из имеющихся процессов. Иллюзия параллельности создается за счет того, что процессы сменяют друг друга через малые интервалы времени, которые человек-наблюдатель не в силах отследить. Подобная организация работы называется квазипараллельным выполнением процессов.
Разумеется, если в системе имеется несколько процессоров, то может быть организовано настоящее параллельное выполнение процессов, количество которых не превышает количества процессоров. При большем числе процессов может использоваться смешанная организация, сочетающая истинную параллельность и квазипараллельность.
Важно отметить, что для большинства задач взаимодействия процессов нет разницы, какого рода параллельность используется в данной ОС. Вообще, основные проблемы управления процессами можно разбить на два уровня:
проблемы корректной и эффективной реализации параллельного (т.е. обычно квазипараллельного) выполнения процессов - это проблемы нижнего уровня;
проблемы корректного взаимодействия параллельных процессов - это проблемы верхнего уровня, при рассмотрении которых считается, что низкоуровневые проблемы реализации процессов так или иначе решены.
Такое разбиение облегчает проектирование и отладку систем, а также позволяет лучше понять существо рассматриваемых проблем.
4.2.3. Состояния процесса
Любой процесс в многозадачной ОС многократно испытывает переход из одного состояния в другое.
Основных состояний всего три.
Работа (running) - в этом состоянии находится процесс, программу которого в данный момент выполняет процессор. Работающий процесс иногда удобно называть также текущим процессом.
Готовность (ready) - состояние, их которого процесс может быть переведен в состояние работы, как только это сочтет нужным сделать ОС.
Блокировка или, что то же самое, сон (sleeping, waiting) - состояние, в котором процесс не может продолжать выполнение, пока не произойдет некоторое внешнее по отношению к процессу событие.
Первые два состояния часто объединяют понятием активного состояния процесса.
Для состояний готовности и сна общее то, что процесс не работает. В чем разница между этими двумя «способами не работать»?
Готовый к выполнению процесс не выполняется только потому, что есть другие не менее готовые процессы, по мнению системы более достойные занимать сейчас процессорное время. В каждый момент времени выбор одного из готовых процессов на роль работающего определяется логикой работы ОС. Этот выбор должен обеспечивать эффективную квазипараллельную работу готовых процессов. Как решается эта задача - будет рассмотрено ниже.
В отличие от этого, спящий процесс - это всегда процесс, ожидающий некоторого конкретного события. Спящий процесс не сможет заработать, даже если процессор вдруг окажется свободным. Такой процесс, в соответствии со своей собственной логикой, ждет чего-то, что должно произойти.
Чего он может ждать? Ну, например:
завершения начатой операции синхронного ввода/вывода (т.е., например, процесс ждет нажатия клавиши Enter или окончания записи на диск);
освобождения запрошенного у системы ресурса (например, дополнительной области памяти или открытого файла);
истечения заданного интервала времени («посплю-ка я минут десять!») или достижения заданного момента времени («разбудите меня ровно в полночь!») (в обоих случаях процесс ждет сигнала от запрограммированного таймера);
сигнала на продолжение действий от другого, взаимосвязанного процесса;
сообщения от системы о необходимости выполнить определенные действия (например, перерисовать содержимое окна).
В любом из названных (и многих неназванных) случаев должно произойти некоторое событие, источник которого лежит вне данного процесса.
Чисто условно можно сказать, что если бы в вычислительную систему вдруг было добавлено еще несколько процессоров, то «готовые» процессы могли бы сразу перейти в состояние «работа», но «спящие» продолжили бы свой сон.
Разумеется, как мы видели в п. 2.5, процесс может выполнять ожидание путем циклической проверки ожидаемого условия. При этом он формально будет оставаться активным, растрачивая драгоценное процессорное время на то, что в п. 2.5.2 было названо активным ожиданием. Однако такое решение будет говорить лишь о вопиющей неквалифицированности программиста. Любая многозадачная ОС предоставляет в распоряжение прикладных программ набор функций, переводящих вызвавший их процесс в состояние сна, в котором процесс не пытается использовать процессорное время (другими словами, состояние сна есть состояние пассивного ожидания). Такие системные функции называются блокирующими. К их числу относятся функции синхронного ввода/вывода, запроса ресурсов, приостановки до заданного времени, получения сообщений и многие другие.
Поскольку ОС берет на себя блокировку, «усыпление» процесса, она должна обеспечить и его разблокировку, «пробуждение». Чтобы это стало возможным, система должна для каждого спящего процесса помнить, «чего он ждет», т.е. помнить условия пробуждения процесса. Система отслеживает все события, способные разблокировать какой-либо процесс (во многих случаях используя для этого аппаратные прерывания) и, когда для одного или сразу нескольких процессов наступает ожидаемое событие, переводит эти события из состояния сна в состояние готовности.
На рис. 4 _ 1 показаны основные состояния процесса и переходы между ними. Этот рисунок кочует из книги в книгу, поскольку он действительно наглядно отражает самую суть работы многозадачных систем.
Рис. 4 _ 1
Рассмотрим возможные переходы между состояниями процесса, показанные на рисунке стрелками.
Переход Работа Сон представляет собой блокировку процесса, которая может произойти при вызове блокирующей системной функции.
Переход Сон Готовность - это пробуждение процесса, оно выполняется системой при возникновении соответствующего условия.
Переход Работа Готовность ранее не рассматривался. Он называется вытеснением процесса и выполняется системой, когда она принимает решение о смене текущего процесса.
Для обратного перехода Готовность Работа нет общепринятого термина. Будем называть его выбором процесса для выполнения. Отметим, что этот переход почти всегда связан либо с блокировкой, либо с вытеснением прежнего текущего процесса.
Ответьте сами на вопрос: почему «почти всегда», а не «всегда»? Какие еще возможны варианты?
Двух стрелок нет на диаграмме. Прямой переход от сна к работе нелогичен, т.к. он совмещал бы два совершенно разных действия.
Каких именно?
Переход от готовности ко сну невозможен в принципе.
Кстати, почему?
Помимо трех основных состояний, в различных ОС могут использоваться и другие состояния.
Состояние старта означает, что процесс находится на этапе создания и пока не готов вступить в работу.
Состояние завершения (в UNIX оно почти официально называется «зомби») означает, что процесс завершил свою работу, но пока присутствует в системе в виде записи о результатах и причине завершения.
Состояние приостановки (suspended) означает, что выполнение процесса временно прервано оператором (или, может быть, другим процессом) и позднее должно быть им же возобновлено.
В некоторых системах (например, в UNIX) основные состояния раздроблены на ряд более мелких: работа в системном и в пользовательском режиме, готовность в памяти и готовность на диске и т.п. Необходимый набор состояний определяется алгоритмами работы конкретной ОС.
4.2.4. Вытесняющая и невытесняющая многозадачность
Все многозадачные ОС можно разделить на два класса, различающиеся по способам организации переключения процессов.
В системах с невытесняющей диспетчеризацией (non-preemptive multitasking) работа любого процесса может быть прервана только «по инициативе самого процесса», а точнее - только когда процесс вызывает определенные системные функции. К ним относятся, в частности, описанные выше блокирующие функции. Может также иметься функция, специально предназначенная для добровольной уступки процессом очереди на выполнение (Yield). Вызов такой функции не приводит к блокировке, но может привести к вытеснению процесса Налицо некоторый разнобой в общепринятой терминологии: в системе с невытесняющей диспетчеризацией вытеснение процесса все-таки возможно, но только по инициативе самого процесса.. Если работающий процесс не вызывает системных функций, а занимается, например, долгими расчетами, то все остальные процессы вынуждены простаивать. Когда же системная функция, наконец, вызвана, то система, прежде всего, проверяет, может ли эта функция быть выполнена сразу или предполагает ожидание некоторого события (требуемый ресурс может быть занят другим процессом; операция ввода/вывода обычно требует определенного времени на свое выполнение; очередь сообщений, требующих обработки, может быть пуста). Если требуется ожидание, то система блокирует процесс, выбирая какой-либо другой из готовых процессов для выполнения. Не исключена ситуация, когда заблокированными по разным причинам оказываются все пользовательские процессы.
Но даже если действие, требуемое процессом, может быть выполнено без блокировки, система не обязательно спешит выполнить его и вернуть управление текущему процессу. На самом деле, момент вызова системной функции удобен для того, чтобы система могла решить, не пора ли процессу «отдохнуть», поскольку имеются другие процессы, давно претендующие на процессорное время или обладающие более высоким приоритетом. В этом случае система переводит процесс в состояние готовности к выполнению, а один из других готовых к выполнению процессов становится текущим. Что же касается вызванной системной функции, то ее выполнение будет завершено позднее, когда вызвавший процесс вновь станет текущим.
В предыдущем п. 4.2.3 смена текущего процесса, не связанная с его блокировкой, была названа вытеснением процесса.
Та часть ОС, которая по определенным в системе правилам выбирает, следует ли вытеснить текущий процесс и какой процесс должен стать следующим текущим, называется планировщиком (scheduler) или диспетчером процессов.
В системе с невытесняющей диспетчеризацией планировщик получает управление при вызове процессом одной из блокирующих или вытесняющих функций. Планировщик проверяет, не выполнены ли условия активизации одного из спящих процессов, а затем принимает решение о выборе одного из активных процессов для выполнения. Не исключено, что будет опять выбран тот же процесс (если только он не блокируется).
Использование невытесняющей диспетчеризации позволило разработать достаточно впечатляющие примеры ОС, из которых наиболее известной является Windows версий 1, 2 и 3. Обычно в таких системах большая часть процессов находится в спящем состоянии, ожидая, пока пользователь обратится к соответствующему приложению. Для пользователя это выглядит совершенно естественно.
Главный недостаток многозадачности невытесняющего типа заключается в том, что любой процесс в принципе имеет возможность полностью и надолго захватить процессор. Это «многозадачность на честном слове», основанная на предположении, что программы всех процессов написаны так, чтобы достаточно часто вызывать блокирующие функции. Даже если программист пишет программу для выполнения сложных многочасовых вычислений, он должен искусственно вставлять в некоторых местах вызов системных функций, передающих управление планировщику. Если же это не сделано, то система фактически теряет многозадачность и будет выполнять один процесс, не реагируя на действия пользователя, до тех пор, пока либо «нахальный» процесс завершится, либо рассвирепевший пользователь снимет его по Ctrl+Alt+Del.
Более сложным и совершенным типом многозадачных ОС являются системы с вытесняющей диспетчеризацией процессов (preemptive multitasking). Их отличие заключается в том, что планировщик вступает в работу не только (и не столько) при вызове системных функций, но и в следующих двух случаях (или хотя бы в одном из них):
когда активизируется (т.е. пробуждается или запускается) процесс, обладающий более высоким приоритетом, чем текущий;
когда истекает квант времени, выделенный планировщиком для текущего процесса.
Понятие приоритета процесса будет подробно рассмотрено чуть ниже. Приоритет характеризует относительную важность или срочность данного процесса. Надо отметить, что немедленный вызов планировщика при активизации высокоприоритетного процесса характерен не для всех систем с вытесняющей диспетчеризацией, а только для одного их подкласса - систем с абсолютными приоритетами. В системах с относительными приоритетами процесс с высоким приоритетом будет все же вынужден подождать истечения кванта времени.
Системы, в которых перепланировка процесса выполняется после истечения каждого кванта времени, называют системами с квантованием времени Иногда используют также термин «разделение времени» (time sharing). Однако этот термин лучше оставить для обозначения многотерминальных ОС, описанных в п. 1.3.3. К системам с квантованием времени относятся также ОС реального времени, заметно отличающиеся от систем разделения времени. (time slicing). Если величина кванта достаточно мала, то для пользователя процесс периодической смены текущего процесса будет незаметен и создастся впечатление, что все активные процессы работают как бы одновременно. С другой стороны, чем меньше величина кванта, тем большую долю процессорного времени будет занимать процедура переключения текущего процесса.
Вызов планировщика не обязательно означает смену процесса. Если нет других активных процессов с таким же или более высоким приоритетом, то планировщик может продолжить выполнение того же процесса.
Принципиальной чертой систем с вытесняющей диспетчеризацией является то, что текущий процесс может быть прерван и вытеснен практически в любой точке своей программы. Это заметно усложняет реализацию таких систем по сравнению с невытесняющими системами, где смена текущего процесса может произойти только в момент вызова системной функции.
4.2.5. Дескриптор и контекст процесса
С каждым процессом связаны описывающие его данные в основной памяти, необходимые ОС для поддержки выполнения процесса. Все эти данные можно разбить на две большие структуры: дескриптор процесса и контекст процесса.
Дескриптор процесса включает в себя все те данные о процессе, которые могут понадобиться ОС при различных состояниях процесса. В число элементов дескриптора могут входить, например, идентификатор процесса (некое условное число, обозначающее данный процесс); текущее состояние процесса; его приоритет; владелец процесса (т.е. идентификатор пользователя, запустившего процесс); статистика затраченного процессом общего и процессорного времени; указатель местоположения контекста процесса и др. Дескрипторы всех процессов, существующих в системе, собраны в таблицу процессов.
Контекст процесса включает данные, необходимые только для текущего процесса. Суда относятся, прежде всего, значения всех регистров процессора, включая указатель текущей команды; таблица файлов, открытых процессом; указатели на области памяти, которые должен занимать процесс при его выполнении; значения системных переменных, используемых процессом (например, текущий диск и каталог, информация о последней ошибке при выполнении системных функций); другие системные флаги и режимы, которые могут иметь разные значения для разных процессов.
Точный состав дескриптора и контекста сильно зависят от конкретной ОС.
При переключении текущего процесса система должна каждый раз переключать и текущий контекст, т.е. сохранять в своей памяти или на диске контекст предыдущего выполнявшегося процесса и восстанавливать ранее сохраненный контекст того процесса, который будет выполняться.
4.2.6. Реентерабельность системных функций
В многозадачной системе нельзя исключить возможность того, что переключение процессов произойдет во время выполнения вытесняемым процессом какой-либо из системных функций. При этом выполнение функции не будет завершено, оно будет прервано на середине. Предполагается, что выполнение функции будет завершено позднее, когда прерванный процесс снова будет выбран на выполнение.
Проблема заключается в том, что новый текущий процесс может вызвать ту же самую системную функцию. Возникает вопрос: возможно ли корректное выполнение второго вызова функции, если к этому моменту не закончено выполнение первого вызова той же функции?
Простой пример подобной ситуации - запуск в ОС нескольких программ, каждая из которых блокируется на ожидании клавиатурного ввода, вызвав для этого одну и ту же системную функцию ввода.
Функция или процедура, для которой возможно корректное выполнение ее повторного вызова до завершения первого вызова, называется реентерабельной или повторно-входимой.
Проблема реентерабельности функций возникает в программировании и по совершенно другому поводу, не связанному с реализацией ОС. Речь идет о рекурсивных функциях, т.е. функциях, которые могут прямо или косвенно вызывать сами себя. Давно известна и основная причина нереентерабельности функций. Она заключается в использовании одних и тех же ячеек памяти для формальных параметров и локальных переменных при разных вызовах функции. Действительно, если при первом вызове функции в ячейку локальной переменной X будет занесено, например, число 10, а при втором - число 20, то после возобновления выполнения первого вызова значение X будет неверным.
Лекарство от этой формы нереентерабельности также давно известно и встроено во все уважающие себя языки программирования, начиная с C и Pascal. Оно заключается в том, что память для формальных параметров и локальных переменных должна выделяться в стеке программы, при этом каждый новый вложенный вызов получает свой набор ячеек для переменных.
Для случая многозадачной системы использование единого стека неприемлемо, поскольку вызовы функций не являются вложенными, т.е. первый вызов может завершиться раньше, чем второй, что привело бы к неверному использованию стека. Каждый процесс получает свой собственный стек, являющийся частью контекста процесса.
Еще одна причина нереентерабельности касается тех функций ввода/вывода, которые запускают операцию и затем дожидаются ее завершения. Повторное обращение к тому же устройству до завершения первого вызова может привести к ошибке. В данном случае система должна отслеживать состояние устройства и блокировать второй вызов до освобождения устройства.
Проблема реентерабельности системных функций значительно острее стоит для ОС с вытесняющей диспетчеризацией, поскольку переключение процесса может случиться при выполнении любой функции. При невытесняющей диспетчеризации достаточно обеспечить реентерабельную реализацию лишь небольшого числа блокирующих функций.
При переходе от невытесняющей Windows 3.x к вытесняющей Windows 95 одна из серьезных проблем состояла в сохранении кода большого количества нереентерабельных системных функций. Проблему «решили» путем введения семафора, блокирующего повторный вызов для большого числа функций. Неприятным следствием этого стало взаимное тормозящее влияние процессов. В Windows NT этой проблемы нет, все функции реализованы реентерабельно.
4.2.7. Дисциплины диспетчеризации и приоритеты процессов
Когда планировщик процессов получает управление, его основной задачей является выбор следующего процесса, который должен получить управление. Алгоритмы, лежащие в основе этого выбора, определяют дисциплину диспетчеризации, принятую в данной ОС.
Одной из самых очевидных дисциплин является простая круговая диспетчеризация (round robin scheduling). Ее суть в следующем. Все активные процессы считаются равноправными и образуют круговую очередь. Каждый процесс получает от системы квант времени, по истечении которого планировщик выбирает для выполнения следующий процесс из очереди. Таким образом, если все процессы остаются активными, то система обеспечивает их равномерное продвижение, имитирующее параллельное выполнение всех процессов. Если текущий процесс блокируется, он выпадает из круга и попадает в список спящих процессов. Когда система активизирует один из спящих процессов, он включается в круговую очередь.
В некотором смысле противоположной дисциплиной является фоново-оперативная диспетчеризация (foreground/background scheduling) - одна из самых старых форм организации многозадачной работы. В простейшем случае она включает два процесса: фоновый процесс и оперативный процесс (процесс переднего плана). Фоновый процесс выполняется только тогда, когда спит оперативный процесс. При активизации оперативного процесса происходит немедленное вытеснение фонового, т.е. оперативный процесс имеет более высокий абсолютный приоритет. Обычно при такой дисциплине предполагается, что активизация оперативного процесса не потребует много процессорного времени, так что выполнение фонового процесса будет скоро возобновлено. Одним из примеров эффективного использования фоново-оперативной диспетчеризации является так называемая «фоновая печать», которую позволяет выполнить даже однозадачная MS-DOS. При этом процесс вывода файла на принтер рассматривается как процесс переднего плана, а обычная диалоговая работа с ОС - как фоновый процесс. Поскольку обслуживание прерываний от принтера занимает лишь доли процента процессорного времени, пользователь не ощущает никакого замедления работы.
Между описанными двумя крайностями лежит большое разнообразие дисциплин приоритетной диспетчеризации. Все они основаны на приписывании каждому процессу при его создании некоторого числа - приоритета. Более высокий приоритет должен давать процессу определенные преимущества перед низкоприоритетными процессами при работе планировщика.
Назначение приоритетов выполняется пользователем либо администратором системы, возможно также программное изменение приоритета процесса. На выбор оптимального уровня приоритета влияют в основном два соображения:
важность, ответственность данного процесса либо привилегированное положение запускающего процесс пользователя;
количество процессорного времени, на которое будет претендовать процесс (как мы видели в примере с фоновой печатью, высокий приоритет процесса, мало загружающего процессор, почти не приводит к замедлению работы остальных процессов).
Основной алгоритм приоритетного планирования напоминает простое круговое планирование, однако круговая очередь активных процессов формируется отдельно для каждого уровня приоритета. Пока есть хоть один активный процесс в очереди с самым высоким приоритетом, процессы с более низкими приоритетами не могут получить управление. Только когда все процессы с высшим приоритетом заблокированы либо завершены, планировщик выбирает процесс из очереди с более низким приоритетом.
Приоритет, присваиваемый процессу при создании, называется статическим приоритетом. Дисциплина планирования, использующая только статические приоритеты, имеет один существенный недостаток: низкоприоритетные процессы могут надолго оказаться полностью отлученными от процессора. Иногда это приемлемо (если высокоприоритетные процессы несравнимо важнее, чем низкоприоритетные), однако чаще хотелось бы, чтобы и на низкие приоритеты хоть что-нибудь перепадало, пусть даже реже и в меньшем количестве, чем на высокие. Для решения этой задачи предложено множество разных алгоритмов планирования процессов, основанных на идее динамического приоритета.
Динамический приоритет процесса - это величина, автоматически рассчитываемая системой на основе двух основных факторов: статического приоритета и степени предыдущего использования процессора данным процессом. Общая идея следующая: если процесс слишком долго не получал процессорного времени, то его приоритет следует повысить, чтобы дать процессу шанс на будущее. Наоборот, если процесс слишком часто и долго работал, есть смысл временно понизить его приоритет, чтобы пропустить вперед изголодавшихся конкурентов.
Могут учитываться и другие соображения, влияющие на динамический приоритет. Например, если процесс ведет диалог с пользователем, то имеет смысл повысить его приоритет, чтобы сократить время реакции и избежать досадных задержек при нажатии клавиш. Если процесс в последнее время часто блокировался, не использовав до конца выделенный ему квант времени, то это тоже основание для повышения приоритета: вполне возможно, процесс и впредь будет так же неприхотлив.
4.3. Проблемы взаимодействия процессов
4.3.1. Изоляция процессов и их взаимодействие
Одна из важнейших целей, которые ставятся при разработке многозадачных систем, заключается в том, чтобы разные процессы, одновременно работающие в системе, были как можно лучше изолированы друг от друга. Это означает, что процессы (в идеале) не должны ничего знать даже о существовании друг друга. Для каждого процесса ОС предоставляет виртуальную машину, т.е. полный набор ресурсов, имитирующий выполнение процесса на отдельном компьютере.
Изоляция процессов, во-первых, является необходимым условием надежности и безопасности многозадачной системы. Один процесс не должен иметь возможности вмешаться в работу другого или получить доступ к его данным, ни по случайной ошибке, ни намеренно.
Во-вторых, проектирование и отладка программ чрезвычайно усложнились бы, если бы программист должен был учитывать непредсказуемое влияние других процессов.
С другой стороны, есть ситуации, когда взаимодействие необходимо. Процессы могут совместно обрабатывать общие данные, обмениваться сообщениями, ждать ответа и т.п. Система должна предоставлять в распоряжение процессов средства взаимодействия. Это не противоречит тому, что выше было сказано об изоляции процессов. Чтобы взаимодействие не привело к полному хаосу, оно должно выполняться только с помощью тех хорошо продуманных средств, которые предоставляет процессам ОС. За пределами этих средств действует изоляция процессов.
Это как граница государств - пересекать ее в произвольных местах запрещено, но должна быть хорошо обустроенная система пропускных пунктов, где легко проконтролировать соблюдение правил пересечения границы.
Понятие взаимодействия процессов включает в себя несколько видов взаимодействия, основными из которых являются:
синхронизация процессов, т.е., упрощенно говоря, ожидание одним процессом каких-либо событий, связанных с работой других процессов;
обмен данными между процессами.
Набор средств, предназначенных для взаимодействия процессов, часто обозначают аббревиатурой IPC (InterProcess Communication).
Состав функций и методов обусловлен многолетним опытом как программистов-практиков, так и теоретиков, рассматривающих проблемы взаимодействия параллельных процессов.
Следует еще раз отметить, что проблемы взаимодействия процессов не зависят от способа реализации параллельной работы процессов в конкретной ОС.
Большая часть этих проблем имеет место в равной степени и для квазипараллельной реализации, и для истинной параллельности с использованием нескольких процессоров.
Средства решения проблем, правда, могут зависеть от реализации.
4.3.2. Проблема взаимного исключения процессов
Серьезная проблема возникает в ситуации, когда два (или более) процесса одновременно пытаются работать с общими для них данными, причем хотя бы один процесс изменяет значение этих данных.
Проблему часто поясняют на таком, немного условном, примере.
Пусть имеется система резервирования авиабилетов, в которой одновременно работают два процесса.
Процесс A обеспечивает продажу билетов, процесс B возврат билетов.
Не углубляясь в детали, будем считать, что оба процесса работают с переменной N - числом оставшихся билетов, причем соответствующие фрагменты программ на псевдокоде выглядят примерно так
|
Процесс A: |
Процесс B: |
|
|
. . . R1 := N; R1 := R1 - 1; N := R1; . . . |
. . . R2 := N; R2 := R2 + 1; N := R2; . . . |
Представим себе теперь, что при квазипараллельной реализации процессов в ходе выполнения этих трех операторов происходит переключение процессов.
В результате, в зависимости от непредсказуемых случайностей, порядок выполнения операторов может оказаться различным, например
1) R1 := N; R2 := N; R2 := R2 + 1; N := R2; R1 := R1 - 1; N := R1;
2) R2 := N; R2 := R2 + 1; R1 := N; R1 := R1 - 1; N := R1; N := R2;
3) R1 := N; R1 := R1 - 1; N := R1; R2 := N; R2 := R2 + 1; N := R2;
Ну и что? А то, что в случае 1 значение N в результате окажется уменьшенным на 1, в случае 2 - увеличенным на 1, и только в случае 3 значение N, как и положено, не изменится.
Можно привести менее экзотические примеры.
Если два процесса одновременно пытаются отредактировать одну и ту же запись базы данных, то в результате разные поля одной записи могут оказаться несогласованными.
Если один процесс добавляет сообщение в очередь, а другой в это время пытается взять сообщение из очереди для обработки, то он может прочесть не полностью сформированное сообщение.
Если два процесса одновременно пытаются обратиться к диску, каждый со своим запросом, то что именно каждый из них в результате прочтет или запишет на диск - сказать трудно.
Ситуация понятна: нельзя разрешать двум процессам одновременно обращаться к одним и тем же данным, если при этом происходит изменение этих данных.
То, что мы рассматривали квазипараллельную реализацию процессов, не столь существенно. Для процессов, работающих на разных процессорах, но одновременно обращающихся к одним и тем же данным, ситуация примерно та же.
Задолго до создания многозадачных систем разработчики средств автоматики столкнулись с неприятным эффектом зависимости результата операции от случайного и непредсказуемого соотношения скоростей распространения разных сигналов в электронных схемах. Этот эффект они назвали «гонками». Мы здесь ведем речь, в сущности, о том же.
Для более четкого описания ситуации было введено понятие критической секции.
Критической секцией процесса по отношению к некоторому ресурсу называется такой участок программы процесса, при прохождении которого необходимо, чтобы никакой другой процесс не находился в своей критической секции по отношению к тому же ресурсу.
В примере с билетами приведенные три оператора в каждом из процессов составляют критическую секцию этого процесса по отношению к общей переменной N. Алгоритм работы каждого процесса в отдельности правилен, но правильная работа двух процессов в совокупности может быть гарантирована, только если они не сунутся одновременно каждый в свою критическую секцию.
А как им это запретить?
На первый взгляд кажется, что эта проблема (ее называют проблемой взаимного исключения процессов) решается просто. Например, можно ввести булеву переменную Free, доступную обоим процессам и имеющую смысл «критическая область свободна». Каждый процесс перед входом в свою критическую область должен ожидать, пока эта переменная не станет истинной, как показано ниже
|
Процесс A: |
Процесс B: |
|
|
. . . while not Free do ; Free := false; (критическая секция A) Free := true; . . . |
. . . while not Free do ; Free := false; (критическая секция B) Free := true; . . . |
В обоих процессах цикл while не делает ничего, кроме ожидания, пока другой процесс выйдет из своей критической секции.
А не нужно ли было что-нибудь сделать с переменной Free еще до запуска процессов A и B?
Прежде всего, отметим, что предложенное решение использует такую неприятную вещь, как активное ожидание: процессорное время растрачивается на многократную проверку переменной Free. Но это полбеды.
Беда в том, что такое решение ничего не решает. Если реализовать его на практике, то «неприятности» станут реже, но не исчезнут. В первом, бесхитростном варианте программы угрожаемыми участками были критические секции обоих процессов. Теперь же уязвимый участок сузился до одной точки, отмеченной в программе каждого процесса штриховой линией. Это точка между проверкой переменной Free и изменением этой переменной. Если переключение процессов произойдет, когда вытесняемый процесс будет находиться именно в этой точке, то сначала в критическую секцию войдет (с полным правом на это) другой процесс, а потом, когда управление вернется к первому процессу, он без дополнительной проверки тоже войдет в свою критическую секцию.
Разработчики первых программных систем, использующих взаимодействие параллельных процессов, не сразу осознали сложность проблемы взаимного исключения. Были испробованы различные программные решения, прежде чем удалось найти такое, которое удовлетворяло трем естественным условиям:
в любой момент времени не более, чем один процесс может находиться в критической секции;
если критическая секция свободна, то процесс может беспрепятственно войти в нее;
Подобные документы
Проектирование ОС Windows 2000, ее архитектура. Процессы и потоки. Уровни запросов на прерывания. Менеджер объектов. Распределение виртуальной памяти. Трансляция виртуальных адресов в физические. Локальный вызов процедуры. Структура сообщения LPC.
презентация [1,5 M], добавлен 24.01.2014Сущность и принцип работы операционной системы, правила и преимущества ее использования. Возможности различных операционных систем, их сильные и слабые стороны. Сравнительная характеристика систем Unix и Windows NT, их потенциал и выполняемые задачи.
реферат [10,5 K], добавлен 09.10.2009Три группы компонентов в составе современной операционной системы: ядро (планировщик и драйверы устройств), системные библиотеки, оболочка с утилитами. Типы архитектур ядер операционных систем: монолитное, модульное, гибридное, микро-, экзо-, наноядро.
курсовая работа [22,1 K], добавлен 27.05.2014Важность операционной системы для мобильных устройств. Популярность операционных систем. Доля LINUX на рынке операционных систем. История OS Symbian, BlackBerry OS, Palm OS. Отличия смартфона от обычного мобильного телефона. Учет ограничений по памяти.
презентация [477,3 K], добавлен 01.12.2015Назначение и функции операционных систем компьютера. Аппаратные и программные ресурсы ЭВМ. Пакетные ОС. Системы с разделением времени: Multics, Unix. Многозадачные ОС для ПК с графическим интерфейсом: Windows, Linux, Macintosh. ОС для мобильных устройств.
курсовая работа [53,4 K], добавлен 05.12.2014Характеристика, функции, типы, виды и состав операционных систем. Первая коммерческая система unix system. Операционные системы, основанные на графическом интерфейсе, пи–система, семейство unix. История и основные предпосылки появления ОС Windows.
курсовая работа [66,9 K], добавлен 18.01.2011Основные классификации операционных систем. Операционные системы семейства OS/2, UNIX, Linux и Windows. Разграничение прав доступа и многопользовательский режим работы. Пользовательский интерфейс и сетевые операции. Управление оперативной памятью.
реферат [22,8 K], добавлен 11.05.2011Разграничение прав пользователя в операционной системе. Предварительная настройка операционной системы с последующей установкой драйверов для периферийных устройств и системных комплектующих. Классификация операционных систем и периферийных устройств.
реферат [2,1 M], добавлен 26.10.2022Основные понятия об операционных системах. Виды современных операционных систем. История развития операционных систем семейства Windows. Характеристики операционных систем семейства Windows. Новые функциональные возможности операционной системы Windows 7.
курсовая работа [60,1 K], добавлен 18.02.2012Эволюция и классификация ОС. Сетевые операционные системы. Управление памятью. Современные концепции и технологии проектирования операционных систем. Семейство операционных систем UNIX. Сетевые продукты фирмы Novell. Сетевые ОС компании Microsoft.
творческая работа [286,2 K], добавлен 07.11.2007
