<< Пред.           стр. 2 (из 8)           След. >>

Список литературы по разделу

  в) по степени активности – на пассивные и активные (способные выполнять действия по отношению к другим ресурсам);
  г) по времени существования – на постоянные (доступные на протяжении всего времени существования процесса, а также до и после его работы) и временные;
  д) по степени важности – на основные и второстепенные (допускающие альтернативное развитие процесса);
  е) по функциональной избыточности при распределении – на дорогие (но предоставляемые быстро) и дешевые (но предоставляемые с ожида­нием);
  ж) по структуре – на со­ставные и простые (которые не содержат составных элементов и могут находиться только в одном из двух состояний: «доступен» или «занят»);
  з) по характеру использования – на потребляе­мые и воспроизводимые (допускающие многократное использо­вание и освобожде-ние), а также – на ис­пользуемые последовательно и ис­пользуемые параллельно (использующиеся несколькими процессами);
  и) по форме реализации – на жесткие (не допускающие копи­рования) и мягкие (допускающие тиражирование и в свою очередь подразделяющиеся на программные и информационные ресурсы).
 
  Примерами ресурсов являются некоторые аппартные устройства ВМ (процессоры, запоминающие устройства, устройства ввода-вывода) или некоторые наборы информации (в частности, совокупности записей определенной структуры – так называемые «файлы»).
 
 1.2. Планирование процессов
 
  Важнейшей частью операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами. Для операционной системы процесс представляет собой единицу работы, заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами.
  За время своего существования процесс многократно изменяет свое состояние. Обычно различают следующие состояния процесса:
  • новый (процесс только что создан);
  • готовый (процесс ожидает освобождения CPU);
  • выполняемый (команды программы выполняются в CPU);
  • ожидающий (процесс ожидает завершения некоторого собы­тия, чаще всего операции ввода-вывода);
  • завершенный (процесс завершил свою работу).
  Переход из одного состояния в другое не может выполняться произвольным образом. Каждый процесс представлен в операционной системе набором данных, называемых «таблица управления процессом» или сокращенно – ТУП (process control block – РСВ). В ТУП процесс описывается набором значе­ний и параметров, характе-ризующих его текущее состояние и ис­пользуемых операционной системой для управления прохождением процесса через ВМ.
  Распределение процессов между имеющимися ресурсами носит название «планирование процессов».
  На протяжении существования процесса его выполнение может быть многократно прервано и продолжено. Для того, чтобы возобновить выполнение процесса, необходимо восстановить состояние его операционной среды. Состояние операционной среды отображается состоянием регистров и программного счетчика, режимом работы процессора, указателями на открытые файлы, информацией о незавершенных операциях ввода-вывода, кодами ошибок выполняемых процессом системных вызовов и т.д. Эта информация называется контекстом процесса. Кроме этого, операционной системе для реализации планирования процессов требуется дополнительная информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса, место нахождения кодового сегмента и другая информация. Информацию такого рода, используемую в некоторых ОС для планирования процессов, называют дескриптором процесса. Дескриптор процесса по сравнению с контекстом содержит более оперативную информацию, которая должна быть легко доступна подсистеме планирования процессов. Контекст процесса содержит менее актуальную информацию и используется операционной системой только после того, как принято решение о возобновлении прерванного процесса.
  Одним из методов планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов. Новые процессы находятся во входной очереди, часто называемой очередью работ – заданий. Входная очередь располагается во внешней памяти, во входной очереди процессы ожидают освобождения ресурса – адресного про­странства основной памяти. Готовые к выполнению процессы располагаются в основной па­мяти и связаны очередью готовых процессов. Процессы в этой очере­ди ожидают освобождения ресурса «процессорное время». Выделение процессу процессорного времени производится многократно с целью достижения внешнего эффекта как бы «одновременного» выполнения нескольких программ. Такой механизм называется диспетчеризацией.
  Процесс в состоянии ожидания, например, завершения операции ввода-вы­вода находится в одной из очередей к оборудованию ввода-вывода. Таким образом при прохождении через ВМ процесс мигрирует между различными очередями под управлением программы, которая назы­вается «планировщик» (scheduler).
  Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки. Каждый дескриптор, кроме всего прочего, содержит по крайней мере один указатель на другой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое.
 
  Планирование процессов включает в себя решение следующих задач:
  1) определение момента времени для смены выполняемого процесса;
  2) выбор процесса на выполнение из очереди готовых процессов;
  3) переключение контекстов «старого» и «нового» процессов.
  Первые две задачи решаются программными средствами, а последняя – в значительной степени аппаратно.
  Существует множество различных алгоритмов планирования процессов, по-разному решающих вышеперечисленные задачи, преследующих различные цели и обеспечивающих различную степень многозадачности. Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов: алгоритмы, основанные на квантовании, и алгоритмы, основанные на приоритетах.
  В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит в следующих случаях:
 – процесс завершился и покинул систему;
 – произошла ошибка;
  – процесс перешел в состояние «ожидание»;
  – исчерпан квант процессорного времени, отведенный данному процессу.
  Процесс, который исчерпал свой квант, переводится в состояние «готовый» и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один из процессов не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.
  Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. Очередь готовых процессов может быть организована циклически по правилу FCFS (First Come First Served – «первым пришел – первым обслужен»), часто называемого правилом FIFO (First In First Out – «первым вошел – первым вышел»), или по правилу стека LCFS (Last Come First Served – «последним пришел – первым обслужен»), имеющего также наименование правила LIFO (Last In First Out – «последним вошел – первым вышел»).
  Другая группа алгоритмов использует понятие «приоритет» процесса. Приоритет – это число, характеризующее степень привилегированности процесса при использовании ресурсов ВМ, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целым или дробным, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам. Приоритет может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими.
  Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.
  В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние «ожидание» (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности.
  Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.
  Существует два основных типа процедур планирования процессов – вытесняющие (preemptive) и невытесняющие (non-preemptive).
 
  Невытесняющая многозадачность (non-preemptive multitasking) – это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.
  Вытесняющая многозадачность (preemptive multitasking) – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.
  Вытесняющая и невытесняющая многозадачность – это более широкие понятия, чем типы приоритетности. Приоритеты задач могут как использоваться, так и не использоваться как при вытесняющих, так и при невытесняющих способах планирования процессов. Например, в случае использования приоритетов дисциплина относительных приоритетов может быть отнесена к классу систем с невытесняющей многозадачностью, а дисциплина абсолютных приоритетов – к классу систем с вытесняющей многозадачностью. Бесприоритетная дисциплина планирования, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам.
  Основным различием между вытесняющими и невытесняющими вариантами многозадачности является степень централизации механизма планирования задач.
  При вытесняющей многозадачности механизм планирования задач целиком сосредоточен в операционной системе, а программист пишет свое приложение, не заботясь о том, что оно будет выполняться «параллельно» с другими задачами. При этом ОС выполняет следующие функции: определяет момент снятия с выполнения активной задачи, запоминает ее контекст, выбирает из очереди готовых задач следующую и запускает ее на выполнение, загружая ее контекст.
  При невытесняющей многозадачности механизм планирования распределен между ОС и прикладными программами. Прикладная программа, получив управление от ОС, сама определяет момент завершения своей очередной итерации и передает управление ОС с помощью какого-либо системного вызова, а ОС формирует очереди задач и выбирает в соответствии с некоторым алгоритмом (например, с учетом приоритетов) следующую задачу на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков. Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например, на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирование могло бы продолжаться в фоновом режиме.
  Поэтому разработчики приложений для невытесняющей операционной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить «дружественное» отношение своей программы к другим выполняемым «одновременно» с ней программам, достаточно часто отдавая им управление. Крайним проявлением «недружественности» приложения является его «зависание», которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет «зависшую» задачу с выполнения.
  Однако распределение функций планировщика между ОС и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент времени передачи управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Значительным преимуществом невытесняющих систем является более высокая скорость переключения с задачи на задачу.
  Одними из основных движущих сил, изменяющих состояния процессов, являются определенные системные события, называемые «прерываниями».
  Прерывания представляют собой механизм, позволяющий коор-динировать па­раллельное функционирование отдельных устройств ВМ и реагировать на особые состояния, возникающие при работе процессора. Таким образом, прерывание – это принудительная передача управления от выполняе­мой программы к системе (а через нее – к соответствующей программе обработ­ки прерывания), происходящая при возникновении определенного события.
  Идея прерываний была предложена в середине 1950-х годов и внесла весомый вклад в развитие вычислитель­ной техники. Основная цель введения прерываний – реализация асинхронного режима работы и распараллеливание работы отдельных устройств вычислитель­ного комплекса. Механизм прерываний реализуется аппаратно-программными средствами. Струк­туры систем прерывания (в зависимости от аппаратной архитектуры) могут быть самыми разными, но все они имеют одну общую особенность – прерывание не­пременно влечет за собой изменение порядка выполнения команд процессором.
  Механизм обработки прерываний независимо от архитектуры ВМ включает следующие основные этапы-шаги:
  1. Установление факта прерывания (прием сигнала на преры-вание) и иденти­фикация прерывания (в операционных системах иногда осуществляется по­вторно на шаге 4).
  2. Запоминание состояния прерванного процесса. Состояние процесса определя­ется прежде всего значением счетчика команд (адресом следующей команды), содержимым регистров процессора и может включать также спецификацию режима (например, режим пользовательский или при­вилегированный) и другую информацию.
  3. Передача управления (аппаратно) подпрограмме обработки прерывания. В про­стейшем случае в счетчик команд заносится начальный адрес подпрограммы обработки прерываний, а в соответствующие регистры – информация из сло­ва состояния. В более развитых процессорах осуществляется достаточно сложная процедура определения начального адреса соответствую­щей подпрограммы обработки прерывания и не менее сложная процедура инициализации рабочих регистров процессора.
  4. Сохранение информации о прерванной программе, которую не удалось спа­сти на шаге 2 с помощью действий аппаратуры. В некоторых ВМ предусматривается запоминание довольно большого объема информации о состоянии прерванного процесса.
  5. Обработка прерывания. Эта работа может быть выполнена той же подпро­граммой, которой было передано управление на шаге 3, но в ОС чаще всего она реализуется путем последующего вызова соответствующей подпрограммы.
  6. Восстановление информации, относящейся к прерванному процессу (этап, обратный шагу 4).
  7. Возврат в прерванную программу.
  Шаги 1–3 реализуются аппаратно, а шаги 4–7 – программно.
  При возникновении запроса на прерывание естествен­ный ход вычислений нарушается и управление передается программе обработ­ки возникшего прерывания. При этом средствами аппаратуры сохраняется (как правило, с помощью механизмов стековой памяти) адрес той команды, начиная с которой следует продолжить выполнение прерванной программы. После выполнения про­граммы обработки прерывания управление возвращается прерванной ранее про­грамме посредством занесения в указатель команд сохраненного адреса команды. Однако такая схема используется только в самых простых программных средах. В многозадачных ОС обработка прерываний происхо­дит по более сложным схемам.
  Итак, главные функции механизма прерываний:
  – распознавание или классификация прерываний;
  – передача управления соответственно обработчику прерываний;
  – корректное возвращение к прерванной программе.
  Переход от прерываемой программы к обработчику и обратно должен выпол­няться как можно быстрей. Одним из быстрых методов является использование таблицы, содержащей перечень всех допустимых для данной ВМ прерываний и адресов соответствующих обработчиков. Для корректного возвращения к пре­рванной программе перед передачей управления обработчику прерываний со­держимое регистров процессора запоминается либо в памяти с прямым досту­пом, либо в системном стеке.
  Прерывания, возникающие при работе ВМ, можно разде­лить на два основных класса: внешние (их иногда называют асинхронными) и внутренние (синхронные).
  Внешние прерывания вызываются асинхронными событиями, которые происхо­дят вне прерываемого процесса, например:
  – прерывания от таймера;
  – прерывания от внешних устройств (прерывания по вводу-вы-воду);
  – прерывания по нарушению питания;
  – прерывания от другого процессора или другой ВМ.
  Внутренние прерывания вызываются событиями, которые связаны с работой про­цессора и являются синхронными с его операциями. Примерами являются сле­дующие запросы на прерывания:
  – при нарушении адресации (в адресной части выполняемой команды указан запрещенный или несуществующий адрес, обращение к отсутствующему сег­менту или странице при организации механизмов виртуальной памяти);
  – при наличии в поле кода операции незадействованной двоич-ной комбинации;
  – при делении на нуль;
  – при переполнении или исчезновении порядка;
  – при обнаружении средствами контроля ошибок четности, ошибок в работе различных внутренних аппаратных устройств.
  В не­которых ВМ часть команд может использовать только операционная система, а не пользо­ватели. Соответственно в аппаратуре предусмотрены различные режимы работы, при этом пользовательские программы выполняются в режиме, в котором названные привиле­гированные команды не исполняются. При попытке использовать команду, за­прещенную в данном режиме, происходит внутреннее прерывание. К привилегированным командам относятся и ко­манды переключения режима работа центрального процессора.
  Наконец, существуют собственно программные прерывания. Эти прерывания возникают по особой команде про­цессора, выполнение которой приводит к переходу на новую последовательность исполняемых инструкций. То есть по этой команде про­цессор осуществляет практически те же действия, что и при обычных внутрен­них прерываниях. Данный механизм был специально введен для того, чтобы переключение на системные программные модули происходило не просто как переход в подпрограмму, а точно таким же образом, как и обычное прерывание. Этим обеспечивается автоматическое переключение процессора в привилегиро­ванный режим с возможностью исполнения любых команд.
  Сигналы, вызывающие прерывания, формируются вне процессора или в самом процессоре. Они могут возникать одновременно. Выбор одного из них для обра­ботки осуществляется на основе приоритетов, приписанных каждому типу пре­рывания. Очевидно, что прерывания от схем контроля процессора должны обла­дать наивысшим приоритетом (если аппаратура работает неправильно, то не имеет смысла продолжать обработку информации). Учет приоритета может быть встроен в технические средства, а также определяться ОС, то есть кроме аппаратно реализованных приоритетов прерываний большинство вычислительных машин и систем допускают программно-аппаратное управление порядком обработки сигналов прерывания. Второй способ, дополняя первый, позволяет применять различные дисциплины обслуживания прерываний.
  Наличие сигнала прерывания не обязательно должно вызывать прерывание исполняющейся программы. Процессор может обладать средствами защиты от прерываний: отключение системы прерываний, маскирование (запрет) отдель­ных сигналов прерывания. Программное управление этими средствами использует специальные команды для управления работой системы прерываний и по­зволяет операционной системе регулировать обработку сигналов прерывания, заставляя процессор обрабатывать их сразу по приходу, откладывать их обработ­ку на некоторое время или полностью игнорировать. Обычно операция прерыва­ния выполняется только после завершения выполнения текущей команды. По­скольку сигналы прерывания возникают в произвольные моменты времени, то на момент прерывания может существовать несколько сигналов прерывания, ко­торые могут быть обработаны только последовательно. Чтобы обработать сигна­лы прерывания в разумном порядке им (как уже отмечалось) присваиваются приоритеты. Сигнал с более высоким приоритетом обрабатывается в первую очередь, обработка остальных сигналов прерывания откладывается.
  Программное управление специальными регистрами маски (так называемое маскирование сиг­налов прерывания) позволяет реализо-вать различные дисциплины обслужива­ния, такие как:
  1) дисциплина обслужива­ния с относительными приоритетами, то есть обслуживание не прерывается даже при наличии запросов с более высокими приоритетами. После окончания об­служивания данного запроса обслуживается запрос с наивысшим приоритетом. Для организации такой дисциплины необходимо в программе обслуживания данного запроса наложить маски на все остальные сигналы прерывания или просто отключить систему прерываний;
  2) дисциплина обслужива­ния с абсолютными приоритетами, то есть всегда обслуживается прерывание с наивысшим приоритетом. Для реализации этого режима необходимо на вре­мя обработки прерывания замаскировать все запросы с более низким приори­тетом. При этом возможно многоуровневое прерывание, то есть прерывание программ обработки прерываний. Число уровней прерывания в этом режиме изменяется и зависит от приоритета запроса;
  3) дисциплина обслужива­ния по принципу стека (дисциплина LCFS или, по-другому, LIFO), то есть когда запросы с более низким приоритетом могут прерывать обработку прерывания с более вы­соким приоритетом. Для этого необходимо не накладывать маски ни на один сигнал прерывания и не выключать систему прерываний.
  Следует особо отметить, что для правильной реализации последних двух дисци­плин нужно обеспечить полное маскирование системы прерываний при выпол­нении шагов 1–4 и 6–7. Это необходимо для того, чтобы не потерять запрос и правильно его обслужить. Многоуровневое прерывание должно происходить на этапе собственно обработки прерывания, а не на этапе перехода с одного процес­са на другой.
  Управление ходом выполнения задач со стороны ОС заключается в организации реакций на прерывания, в организации обмена информацией (данными и про­граммами), предоставлении необходимых ресурсов, в динамике выполнения за­дачи и в организации сервиса. Причины прерываний определяет сама ОС, она же и выполняет действия, необходимые при данном прерывании и в данной ситуации. Поэтому в состав любой ОС реального времени прежде всего входят программы управления сис­темой прерываний, контроля состояний задач и событий, синхронизации задач, средства распределения памяти и управления ею, а уже потом средства органи­зации данных (с помощью файловых систем и т. д.).
  Как уже было сказано, при появлении запроса на прерывание система прерываний идентифицирует сигнал и, если прерывания разрешены, управление передается на соответствующую подпрограмму обработки прерывания. В подпро­грамме обработки прерывания имеются две служебные секции. Это первая секция, в которой осуществляется сохранение контекста прерванной задачи, не сохраненного на шаге 2, и последняя, заключительная секция, в которой, наоборот, осуществляется восстановление контекста. Для того, чтобы система прерываний не среагировала повторно на сигнал запроса на прерывание, она обычно автоматически «закрывает» (отключает) прерывания, поэтому необ­ходимо потом в подпрограмме обработки прерываний вновь включать систему прерываний. Установка рассмотренных режимов обработки прерываний (с отно­сительными и абсолютными приоритетами, по дисциплине LCFS) осуществляется в конце первой секции подпрограмм обработки прерываний. Таким образом, на время вы­полнения центральной секции (в случае работы в режимах с абсолютными при­оритетами) прерывания разрешены. На время работы заключительной секции подпрограммы обработки прерывания система прерываний должна быть отключена и после восстановления контекста вновь включена. Поскольку эти действия необходимо выполнять практически в каждой подпрограмме обра­ботки прерываний, во многих операционных системах первые секции подпро­грамм обработки прерываний выделяются в специальный системный программ­ный модуль, называемый супервизором прерываний.
  Супервизор прерываний прежде всего сохраняет в дескрипторе текущей задачи рабочие регистры процессора, определяющие контекст прерываемого вычисли­тельного процесса. Далее он определяет ту подпрограмму, которая должна выполнить действия, связанные с обслуживанием настоящего (текущего) запроса на прерывание. Наконец, перед тем как передать управление этой подпрограмме, супервизор прерываний устанавливает необходимый режим обработки прерыва­ния. После выполнения подпрограммы обработки прерывания управление вновь передается супервизору, на этот раз уже на тот модуль, который занимается дис­петчеризацией задач. И уже диспетчер задач, в свою очередь, в соответствии с принятым режимом распределения процессорного времени (между выполняю­щимися процессами) восстанавливает контекст той задачи, которой будет решено выделить процессор. Для прямого непосредственного возврата достаточно адрес возврата сохра­нить в стеке, что и делает аппаратура процессора. При этом стек легко обеспе­чивает возможность возврата в случае вложенных прерываний, поскольку он всегда реализует дисциплину LCFS.
  Однако если бы контекст процессов сохранялся просто в стеке, как это обычно реализуется аппаратурой, а не в описанных выше дескрипторах задач, то не имелось бы возможности гибко подходить к выбору той задачи, которой нужно пе­редать процессор после завершения работы подпрограммы обработки прерыва­ния. Естественно, что это только общий принцип. В конкретных процессорах и в конкретных ОС могут существовать некоторые отступления от рассмотренной схемы и (или) дополнения к ней. Например, в современных процессорах часто имеются специальные аппаратные возможности для сохранения контекста прерываемого процесса непосредственно в его дескрипторе, то есть дескриптор про­цесса (по крайней мере его часть) становится структурой данных, которую под­держивает аппаратура.
 
  1.3. Межпроцессное взаимодействие
 
  Существенное значение имеет возможность взаимодействия процессов между собой. Например, один процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла. Во всех этих случаях возникает проблема синхронизации процессов, которая может решаться приостановкой и активизацией процессов, организацией очередей, блокированием и освобождением ресурсов. Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме многозадачности, может привести к их неправильной работе или даже к «краху» системы.
  Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций. Очень часто все определяется взаимными скоростями процессов и моментами их прерывания. Поэтому отладка взаимодействующих процессов является сложной задачей. Ситуации, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов, называются гонками.
  Важным понятием синхронизации процессов является понятие «критическая секция» или «критическая область» программы. Критическая секция (критическая область) – это часть программы, в которой осуществляется доступ к разделяемым данным. Для исключения эффекта гонок по отношению к некоторому ресурсу, необходимо обеспечивать такие ситуации, чтобы в каждый момент времени в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение – позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ далеко не всегда пригоден, так как весьма опасно доверять управление системой пользовательскому процессу: он может надолго занять процессор, а при «крахе» процесса в критической области «крах» потерпит вся система, потому что прерывания никогда не будут разрешены.
  Другим способом взаимного исключения является использование блокирующих переменных. При этом каждому разделяемому ресурсу ставится в соответствие двоичная переменная, которая принимает, например, значение 0, если ресурс свободен (то есть ни один из процессов не находится в данный момент в критической секции, связанной с данным процессом), и значение 1, если ресурс занят.
  Если все процессы реализуются с использованием вышеописанных соглашений, то взаимное исключение гарантируется. Необходимо подчеркнуть, что операция проверки и установки блокирующей переменной должна быть неделимой, что может быть пояснено на следующем примере.
  Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 1, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к нежелательным последствиям.
  Во избежание указанных ситуаций в системе команд машины следует иметь единую команду «проверка-установка», или же реализовывать системными средствами соответствующие программные примитивы, которые бы запрещали прерывания на протяжении всей операции проверки и установки.
  Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Такую постоянную проверку иногда называют активным ожиданием. При этом блокирующая переменная (блокировка), использующая активное ожидание, называется спин-блокировкой. Для устранения таких ситуаций может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения.
  Например, если ресурс занят, то процесс не выполняет циклический опрос, а вызывает некоторую системную функцию wait(D), где D обозначает событие, заключающееся в освобождении ресурса D. Функция wait(D) переводит активный процесс в состояние «ожидание» и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию post(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние «готовность».
  Для организации синхронизации процессов могут применяться специальные механизмы высокого уровня, блокирующие процесс, ожидающий входа в критическую область или наступления своей очереди использования совместного ресурса. Один из подобных механизмов – механизм так называемых семафоров, являющихся определенным обобщением понятия блокирующих переменных. Семафоры представляют собой такой тип переменных, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активизации процессов) или некоторым положительным числом, соответствующим количеству отложенных активизирующих сигналов.
  Для работы с семафорами применяются две операции: down и up. Операция down сравнивает значение семафора с нулем. Если значение семафора больше нуля, операция down уменьшает его (то есть расходует один из сохраненных сигналов активации) и просто возвращает управление. Если значение семафора равно нулю, процедура down не возвращает управление процессу, а процесс переводится в состояние ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции. Элементарность операции чрезвычайно важна для разрешения пробле­мы синхронизации и предотвращения состояния состязания.
  Операция up увеличивает значение семафора. Если с этим семафором связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой (например, случайным образом) и ему разрешается завершить свою операцию down. Таким образом, после операции up, примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и останется равным 0, но число ожидающих процессов уменьшится на единицу. Операция увеличения значения семафора и активизации процесса тоже неделима. Ни один процесс не может быть блокиро­ван во время выполнения операции up.
  Часто используется упрощенная версия семафора, называемая мьютексом (от англоязычного термина mutex, происходящего от сокращения словосочетания mutual exclusion – «взаимное исключение»).
  Мьютекс не может считать сигналы, а может лишь управлять взаимным исключением доступа к совместно используемым ресурсам. Реализация мьютекса проста и эффективна. Мьютекс является переменной, которая может находиться в одном из двух состояний: блокированном или неблокированном. Поэтому для описания мьютекса требует­ся всего один бит, хотя чаще используется целая переменная, у которой 0 означает неблокированное состояние, а все остальные значения соответствуют блокирован­ному состоянию. Значение мьютекса устанавливается двумя процедурами. Если процесс собирается войти в критическую секцию, он вызывает проце­дуру mutex_lock. Если мьютекс не заблокирован (то есть вход в критическую секцию разрешен), запрос выполняется и вызывающий процесс может попасть в критическую секцию. Напротив, если мьютекс заблокирован, вызывающий процесс блокируется до тех пор, пока другой процесс, находящийся к критической секции, не выйдет из нее, вызвав процедуру mutex_unlock. Если мьютекс блокирует несколько процессов, то из них случайным образом выбирается один.
  Одним из наиболее простых, удобных и интуитивных интерфей­сов межпроцессного взаимодействия является буфер обмена. Буфер обмена может содержать в себе один информаци­онный объект – фрагмент текста, рисунок и т. д. С помощью сис­темного вызова процесс может получить копию информации, со­держащейся в буфере обмена, или сам поместить объект в буфер, при этом старое содержимое буфера теряется. Таким образом, про­граммы получают простой, но эффективный способ взаимного обмена инфор­мацией во время своей работы.
  Существенной проблемой синхронизации процессов являются взаимные блокировки (взаимоблокировки) или тупики, называемые также дедлоками (deadlock) или клинчами (clinch). Ниже описан характерный пример взаимоблокировки.
  Пусть двум процессам А и В, выполняющимся в режиме многозадачности, для выполнения их работы нужно два ресурса, например, принтер и диск. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком тупиковом положении процессы А и В могут находиться сколь угодно долго.
  Процессы в зависимости от соотношения собственных скоростей могут либо совершенно независимо использовать разделяемые ресурсы, либо образовывать очереди к разделяемым ресурсам, либо взаимно блокировать друг друга. Тупиковые ситуации следует отличать от простых очередей, хотя те и другие возникают при совместном использовании ресурсов и внешне похожи друг на друга: процесс приостанавливается и ждет освобождения ресурса. Однако очередь – это нормальное явление, неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов. Она возникает тогда, когда ресурс недоступен в данный момент, но через некоторое время он освобождается, и процесс продолжает свое выполнение. Тупик же, что видно из его названия, является в некотором роде неразрешимой ситуацией. В рассмотренном примере тупик (взаимоблокировка) был образован двумя процессами, но взаимно блокировать друг друга может и большее число процессов. Проблема взаимоблокировок включает в себя задачи предотвращения взаимоблокировок, распознавания взаимоблокировок и восстановления системы после взаимоблокировок.
  Взаимоблокировки могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы взаимоблокировка не могла возникнуть ни при каком соотношении взаимных скоростей процессов. Так, если бы в рассмотренном выше примере процесс А и процесс В запрашивали ресурсы в одинаковой последовательности, то тупиковая ситуация была бы в принципе невозможна.
  Второй подход к предотвращению взаимоблокировок называется динамическим и заключается в использовании определенных правил при назначении ресурсов процессам (например, ресурсы могут выделяться в определенной последовательности, общей для всех процессов).
  В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими множество ресурсов, распознавание взаимоблокировки является нетривиальной задачей. Существуют формальные программно-реализованные методы распознавания взаимоблокировок, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них (при этом освобождаются ресурсы, ожидаемые остальными процессами), можно вернуть некоторые процессы в область свопинга (см. раздел 2), можно совершить «откат» некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в тех местах, после которых возможно возникновение тупика.
  Для того, чтобы облегчить написание корректных программ, было предложено высокоуровневое средство синхронизации, называемое монитором. В данном случае под монитором понимается набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют важное свойство, которое делает их полезными для достижения взаимного исключения: только один процесс может быть активным по отношению к монитору. Компилятор обрабатывает вызовы процедур монитора особым образом. Обычно, когда процесс вызывает процедуру монитора, то первые несколько инструкций этой процедуры проверяют, не активен ли какой-либо другой процесс по отношению к этому монитору. Если да, то вызывающий процесс приостанавливается, пока другой процесс не освободит монитор. Таким образом, исключение входа нескольких процессов в монитор реализуется не программистом, а компилятором, что делает ошибки менее вероятными.
  1.4. Понятия потока («нити») и многопоточности
 
  Когда говорят о процессах, то тем самым хотят отметить, что операци­онная система поддерживает их обособленность: у каждого процесса имеется свое виртуальное адресное пространство, каждому процессу назначаются свои ресур­сы – файлы, окна, семафоры и так далее. Такая обособленность нужна для того, чтобы защитить один процесс от другого, поскольку они, совместно используя все ре­сурсы ВМ, конкурируют друг с другом. В общем случае процессы могут быть никак не связаны между собой и даже могут принадлежать раз­ным пользователям, разделяющим одну вычислительную машину. Другими сло­вами, в случае процессов ОС считает их совершенно несвязанными и независимыми. При этом именно ОС берет на себя роль арбитра в конкуренции между процессами по поводу ресурсов.
  Однако желательно иметь еще и возможность задействовать внутренний парал­лелизм, который может быть в самих процессах. Такой внутренний параллелизм встречается достаточно часто, а его использование позволяет ускорить реализацию процессов. Например, некоторые операции, выполняемые приложением, могут требо­вать для своего исполнения достаточно длительного использования центрального процессора. В этом случае при интерактивной работе с приложением пользова­тель вынужден долго ожидать завершения заказанной операции и не может управ­лять приложением до тех пор, пока операция не выполнится до самого конца. Такие ситуации встречаются достаточно часто, например, при обработке боль­ших изображений в графических редакторах. Если же программные модули, исполняющие такие длительные операции, оформлять в виде самостоятельных «подпроцессов» (так называемых легковесных или облегченных процессов), которые будут выполняться парал­лельно с другими подобными «подпроцессами», то у пользователя по­является возможность параллельно выполнять несколько операций в рамках од­ного приложения (процесса). Такие «подпроцессы» принято называть потоками или «нитями» (thread). «Подпроцессы» (потоки) называют легковесными потому, что операционная система не должна для них организовывать полноценную вирту­альную машину. Потоки не имеют своих собственных ресурсов, они развива­ются в том же виртуальном адресном пространстве, могут пользоваться теми же файлами, виртуальными устройствами и иными ресурсами, что и данный про­цесс. Единственное, что им необходимо иметь, – это процессорный ресурс. В од­нопроцессорной машине потоки разделяют между собой процессорное время так же, как это делают обычные процессы, а в многопроцессорной машине могут выполняться одновременно, если не встречают конкуренции из-за об­ращения к иным ресурсам.
  Многопоточность обеспечивает возможность параллельного вы­полнения нескольких видов операций в одной прикладной программе. Параллель­ные вычисления (а, следовательно, более эффективное использование ресур­сов центрального процессора и меньшее суммарное время выполнения задач) теперь уже часто реализуется на уровне потоков, и программа, оформленная в виде нескольких потоков в рамках одного процесса, может быть выполнена быстрее за счет параллельного выполнения ее отдельных частей. При этом желательно уменьшать взаимо­действие потоков между собой, так как ускорение от одновременного выполнения параллельных потоков может быть сведено к минимуму из-за задержек синхро­низации и обмена данными.
  В качестве примера использования многопоточности можно привести электрон­ную таблицу или текстовый процессор. Если они были разработаны с учетом возможностей многопоточной обработки, то пользователь может запросить пересчет своего ра­бочего листа или слияние нескольких документов и одновременно продолжать заполнять таблицу или открывать для редактирования следующий документ. Особенно эффективно можно использовать многопоточ-ность для выполнения распределенных приложений: например, многопоточный сервер может парал­лельно выполнять запросы сразу нескольких клиентов.
  Итак, сущность «поток» была введена для того, чтобы именно с помощью этих единиц распределять процессорное время между возможными работами. Сущ­ность «процесс» предполагает, что при диспетчеризации нужно учитывать все ресурсы, закрепленные за ним. А при манипулировании потоками можно менять только их контекст, если происходит переключение с одного потока на другой в рам­ках одного процесса. Все остальные вычислительные ресурсы при этом не затра­гиваются. Каждый процесс всегда состоит по крайней мере из одного потока, и только в случае наличия внутреннего параллелизма становится возможным «расще­пление» этого одного потока на несколько параллельных.
  Потребность в потоках возникла еще на однопроцессорных ВМ, поскольку потоки позволяют организовать вычисления более эф­фективно. Для использования достоинств многопроцессорных ВМ с общей памятью потоки уже являются необходимыми, так как позволяют не только реально ускорить выполнение тех задач, которые допускают их естественное распаралле­ливание, но и загрузить процессоры, исключая таким образом их возможное «простаи­вание».
  Каждый поток выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Потоки, как и процессы, могут порождать потоки-по­томки, поскольку любой процесс состоит по крайней мере из одного потока. По­добно традиционным процессам (то есть процессам, состоящим из одного потока), каждый поток может находиться в одном из активных состояний. Пока один поток заблокирован (или просто находится в очереди готовых к исполнению задач), другой поток того же процесса может выполняться. Потоки разделяют процессор­ное время так же, как это делают обычные процессы, в соответствии с различны­ми вариантами диспетчеризации.
  Все потоки имеют одно и то же виртуальное адресное про­странство своего процесса. Это означает, что они разделяют одни и те же гло­бальные переменные. Поскольку каждый поток может иметь доступ к каждому виртуальному адресу, один поток может исполь-зовать стек другого потока.
  Между потоками нет полной защиты, так как это не является необходимым. Все потоки одного процесса всегда решают общую задачу одного поль­зователя, и механизм потоков используется здесь для более быстрого решения задачи путем ее распараллеливания. При этом программисту очень важно полу­чить в свое распоряжение удобные средства организации взаимодействия разных частей одной программы.
  Вследствие того, что потоки, относящиеся к одному процессу, выполняются в од­ном и том же виртуальном адресном пространстве, между ними легко организо­вать тесное взаимодействие (в отличие от процессов, для которых нужны специ­альные механизмы взаимодействия). Более того, программист, создающий многопоточное приложение, может заранее продумать работу мно­жества потоков процесса таким образом, чтобы они могли взаимодействовать наи­более выгодным способом, а не участвовать в конкуренции за предоставление ресурсов тогда, когда этого можно избежать.
 
 Резюме
 
  Ключевыми понятиями операционных систем являются понятия «процесса» и «ресурса». Процесс представляет собой некоторую последовательность операций при выполнении программы или ее части в совокупности с используемыми данными. Процессы обладают рядом характеристик и признаков, основными из которых являются временные характеристики, генеалогические признаки, характеристики результативности, времени и места развития, связности и принадлежности к операционной системе.
 
  Под ресурсом понимается любой потребляемый или расходуемый процессом объект. Ресурсы классифицируются по различным свойствам, важнейшими из которых являются реальность и активность, продолжительность времени существования, характер использования, форма реализации.
  За время своего существования процессы могут неоднократно изменять свое состояние, проходя через стадии создания, готовности, выполнения, ожидания и завершения своей работы. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами. Одним из методов планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов. Процессы мигрируют между различными очередями под управлением специальной программы операционной системы – планировщика. Наиболее часто используемые на практике алгоритмы планирования процессов – это алгоритмы, основанные на квантовании, и алгоритмы, основанные на приоритетах.
  Основные типы процедур планирования процессов – вытесняющие и невытесняющие. При невытесняющей процедуре планирования (невытесняющей многозадачности) активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс. При вытесняющей процедуре планирования (вытесняющей многозадачности) решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.
  Одними из основных движущих сил, изменяющих состояния процессов, являются так называемые прерывания, которые представляют собой механизм принудительной передачи управления от выполняе­мой программы к соответствующей программе обработ­ки прерывания. Прерывания классифицируются на аппаратные (которые могут быть внешними и внутренними) и программные. Порядок обработки прерываний зависит от типа используемой дисциплины обслуживания прерываний.
 
  Порядок взаимосвязи процессов определяется правилами синхро­низации. Часть программы, в которой осуществляется доступ к разделяемым данным, называется критической секцией (критической областью) программы. Ситуации, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов, называются гонками. Исключение эффекта гонок по отношению к некоторому ресурсу обеспечивается различными способами взаимного исключения, такими как использование механизмов блокирующих переменных, семафоров, мьютексов.
  Существенной проблемой синхронизации процессов являются их взаимные блокировки или тупики. Проблема взаимоблокировок требует решения задач предотвращения взаимоблокировок, распознавания взаимоблокировок и восстановления системы после взаимоблокировок. Высокоуровневым средством синхронизации процессов, исключающим взаимоблокировки, является так называемый монитор, который представляет собой набор процедур, переменных и структур данных.
  Потоки («нити») представляют собой «легковесную» (или «облегченную») форму процессов. Потоки в отличие от процессов не имеют своих собственных ресурсов, они развива­ются в том же виртуальном адресном пространстве, могут пользоваться теми же файлами, виртуальными устройствами и иными ресурсами, что и данный про­цесс. Единственное, что им необходимо иметь, – это процессорный ресурс. Многопоточность обеспечивает возможность параллельного вы­полнения несколько видов операций в одной прикладной программе. Параллель­ные вычисления способствуют более эффективному использованию ресур­сов центрального процессора и существенно уменьшают суммарное время выполнения программ.
 
 
 
 
 
 
 
 
 
 Контрольные вопросы и задания
 
 1. Дайте определение понятиям «вычислительный процесс» и «ресурс».
 2. Как классифицируются процессы и ресурсы?
 3. Решение каких задач включает в себя планирование процессов?
 4. Перечислите виды состояний процессов.
 5. Что такое контекст и дескриптор процесса?
 6. Каковы возможные причины выхода процесса из состояния выполнения?
 7. Охарактеризуйте наиболее распространенные алгоритмы плани-рования процессов.
 8. В чем заключается сущность алгоритмов планирования процес-сов, основанных на квантовании?
 9. Опишите различия между относительными и абсолютными прио-ритетами.
 10. Дайте определение понятиям вытесняющая и невытесняющая многозадачность.
 11. Дайте определение понятию «прерывание».
 12. Какие этапы реализуются механизмом обработки прерываний?
 13. Приведите примеры внешних прерываний.
 14. Какими событиями вызываются внутренние прерывания?
 15. Поясните понятие программного прерывания.
 16. Охарактеризуйте применяемые дисциплины обслуживания прерываний.
 17. В чем заключается механизм синхронизации процессов?
 18. Что такое «критическая область» программы и с какими целями она используется?
 19. С помощью каких механизмов осуществляется взаимодействие процессов?
 20. В чем различие понятий очередей процессов и взаимоблоки-ровок процессов?
 21. Перечислите способы преодоления тупиковых ситуаций при взаимодействии процессов.
 22. Опишите понятие монитора как высокоуровневого средства синхронизации процессов.
 23. В чем различие понятий «процесс» и «поток»?
 24. С какой целью в ОС используется механизм потоков («нитий»)?
 2. Управление ресурсами в автономных
 однопроцессорных компьютерах
 
 2.1. Управление памятью
 
  Память является важнейшим ресурсом, требующим тщательного управления со стороны операционной системы. Распределению подлежит вся оперативная память, не занятая операционной системой. Обычно ОС располагается в самых младших адресах, однако может занимать и старшие адреса. Функциями ОС по управлению памятью являются: отслеживание свободной и занятой памяти, выделение памяти процессам и освобождение памяти при завершении процессов, вытеснение процессов из оперативной памяти на диск (когда размеры основной памяти не достаточны для размещения в ней всех процессов) и возвращение их в оперативную память (когда в ней освобождается место), а также настройка адресов программы на конкретную область физической памяти.
  Для идентификации команд и переменных используются символьные имена (метки), виртуальные адреса и физические адреса.
  Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере.
  Виртуальные адреса вырабатывает транслятор, переводящий программу на машинный язык. Так как во время трансляции в общем случае неизвестно, в какое место оперативной памяти будет загружен процесс, то транслятор присваивает командам и переменным виртуальные (условные) адреса, обычно считая по умолчанию, что процесс будет размещен, начиная с нулевого адреса. Совокупность виртуальных адресов процесса называется виртуальным адресным пространством. Каждый процесс имеет собственное виртуальное адресное пространство. Максимальный размер виртуального адресного пространства ограничивается разрядностью адреса, присущей данной архитектуре ВМ, и, как правило, не совпадает с объемом физической памяти, имеющимся в машине.
  Физические адреса соответствуют номерам ячеек оперативной памяти, где в действительности расположены или будут расположены команды и переменные. Переход от виртуальных адресов к физическим может осуществляться двумя способами.
 
  В первом случае замену виртуальных адресов на физические делает специальная системная программа – перемещающий загрузчик. Перемещающий загрузчик на основании имеющихся у него исходных данных о начальном адресе физической памяти, в которую предстоит загружать процесс, и предоставленной транслятором информации об адресно-зависимых константах программы, выполняет загрузку процесса, совмещая ее с заменой виртуальных адресов физическими.
  Второй способ заключается в том, что процесс загружается в память в неизмененном виде в виртуальных адресах, при этом операционная система фиксирует смещение действительного расположения программного кода относительно виртуального адресного пространства. Во время выполнения процесса при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Второй способ является более гибким, он допускает перемещение процесса во время выполнения, в то время как перемещающий загрузчик жестко привязывает процесс к первоначально выделенному участку памяти. Вместе с тем использование перемещающего загрузчика уменьшает накладные расходы, так как преобразование каждого виртуального адреса происходит только один раз во время загрузки, а во втором случае – каждый раз при обращении по данному адресу.
  В некоторых случаях (обычно в специализированных системах), когда заранее точно известно, в какой области оперативной памяти будет выполняться процесс, транслятор выдает исполняемый код сразу в физических адресах.
  Все методы управления памятью могут быть разделены на два класса: методы, которые используют перемещение процессов между оперативной памятью и диском, и методы, которые не делают этого. Начнем с последнего, более простого класса методов.
  Самым простым способом управления оперативной памятью является разделение ее на несколько разделов фиксированной величины. Это может быть выполнено вручную администратором во время старта системы или во время ее генерации. Очередной процесс, поступивший на выполнение, помещается либо в общую очередь, либо в очередь к некоторому разделу. Подсистема управления памятью в этом случае выполняет следующие задачи:
  1) выбирает свободный раздел, размер которого достаточен для размещения поступившего на выполнение процесса;
  2) осуществляет загрузку процесса и настройку адресов.
  При очевидном преимуществе – простоте реализации – данный метод имеет существенный недостаток, которым является его «жесткость». Так как в каждом разделе может размещаться только один процесс, то степень «многозадачности» заранее ограничена числом разделов не зависимо от того, какой размер требуется процессам. Другим существенным недостатком является то, что в предлагае­мой схеме очень часто может наблюдаться так называемая фрагментация памяти, то есть потери части памяти разделов вследствие того, что процессы не полностью занимают выделенные им разделы. Например, если процессу требуется небольшой объем, но ему выделяется целый раздел, то оставшаяся память этого раздела не будет использоваться (то есть в этом разделе останется неиспользуе­мый фрагмент памяти). Снижение же степени фрагментации па­мяти за счет уменьшения размеров разделов может на определенном этапе привести к тому, что в малые разделы не смогут быть за­гружены процессы, для которых требуются более объемные разделы. Кроме того, недостат­ком рассматриваемого способа управления оперативной памятью является и то, что если даже весь объем оперативной памяти машины позволяет разместить некоторый процесс, требующий большого объема, наличие фик­сированного разбиения памяти на разделы не позволит сделать это, так как требуемый объем может превосходить по размеру отдельные (пусть и очень большие), но фиксированные разделы памяти.
  В случае распределения памяти разделами переменной величины память ВМ не делится заранее на разделы. Сначала вся оперативная память свободна. Каждому вновь поступившему процессу выделяется необходимая память. Если достаточный объем памяти отсутствует, то процесс не принимается на выполнение и стоит в очереди. После завершения процесса память освобождается, и на это место может быть загружен другой процесс. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера.
  Задачами операционной системы при реализации данного метода управления памятью являются следующие:
  1) ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти;
  2) при поступлении нового процесса – анализ запроса, просмотр таблицы свободных областей и выбор раздела, размер которого достаточен для размещения поступившего процесса;
  3) загрузка процесса в выделенный раздел и корректировка таблиц свободных и занятых областей;
  4) после завершения процесса – корректировка таблиц свободных и занятых областей.
  Выбор раздела для вновь поступившего процесса может осуществляться по разным правилам, таким, например, как «первый попавшийся раздел достаточного размера», или «раздел, имеющий наименьший достаточный размер», или «раздел, имеющий наибольший достаточный размер». Все эти правила имеют свои преимущества и недостатки.
  По сравнению с методом распределения памяти фиксированными разделами метод распределения памяти разделами переменной величины обладает гораздо большей гибкостью, но ему также присуща фрагментация памяти. Это связано с образованием через определенный промежуток времени функционирования системы некоторого числа несмежных участков свободной памяти (фрагментов), образовавшихся в результате выгрузки выполнившихся процессов, и загрузки на их место новых процессов, требующих меньшие объемы памяти. При этом может возникнуть ситуация, при которой ни для одного из вновь поступающих процессов не будет иметься достаточного участка памяти, хотя суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый процессу объем памяти.
  Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших либо в сторону младших адресов, так, чтобы вся свободная память образовывала единую свободную область. В дополнение к функциям, которые выполняет ОС при распределении памяти переменными разделами, в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется «сжатием». Сжатие может выполняться либо при каждом завершении процесса, либо только тогда, когда для вновь поступившего процесса нет свободного раздела достаточного размера. В первом случае требуется меньше вычислительной работы при корректировке таблиц, а во втором – реже выполняется процедура сжатия. Так как процессы перемещаются по оперативной памяти в ходе своего выполнения, то преобразование адресов из виртуальной формы в физическую должно выполняться динамическим способом. Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто является тем недостатком, который преобладает над преимуществами данного метода.
  Развитие методов организации вычислительного процесса привело к появлению метода, использующего так называемую виртуальная память. В общем случае виртуальным называется ресурс, который пользователю или пользовательской программе представляется обладающим некими свойствами, которыми он в действительности не обладает. Так, например, пользователю может быть предоставлена виртуальная оперативная память, размер которой превосходит всю имеющуюся в системе реальную оперативную память. Пользователь пишет программы так, как будто в его распоряжении имеется однородная оперативная память большого объема, но в действительности для реализации программы предоставляются несколько разнородных запоминающих устройств, включая дисковые устройства.
  Таким образом, виртуальная память – это совокупность программно-аппаратных средств, позволяющих пользователям писать программы, которые для своей реализации требуют такие объемы памяти, которые превосходят реально существующие объемы оперативной памяти ВМ. Для этого виртуальная память решает следующие задачи:
  1) размещает процессы в запоминающих устройствах разного типа, например, часть – в оперативной памяти, а часть – на диске;
  2) перемещает процессы по мере необходимости между запоминающими устройствами разного типа, например, подгружает процесс или его часть с диска в оперативную память;
  3) преобразует виртуальные адреса в физические.
  Все эти действия выполняются автоматически, без участия программиста, то есть механизм виртуальной памяти является прозрачным по отношению к пользователю.
  Наиболее распространенными способами реализации виртуальной памяти является страничное, сегментное и странично-сегментное распределение памяти, а также свопинг.
  При страничном распределении памяти виртуальное адресное пространство каждого процесса делится на части одинакового, фиксированного для данной системы размера. Эти части называют виртуальными страницами. В общем случае размер виртуального адресного пространства не является кратным размеру страницы, поэтому последняя страница каждого процесса дополняется фиктивной областью. Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками). Размер страницы обычно выбирается равным степени числа 2, например: 512, 1024 и т.д. Это позволяет упростить механизм преобразования адресов.
  При загрузке процесса часть его виртуальных страниц помещается в оперативную память, а остальные – на диск. Смежные виртуальные страницы не обязательно располагаются в смежных физических страницах. При загрузке операционная система создает для каждого процесса информационную структуру – таблицу страниц, в которой устанавливается соответствие между номерами виртуальных и физических страниц для страниц, загруженных в оперативную память, или делается отметка о том, что виртуальная страница выгружена на диск. Кроме того, в таблице страниц содержится управляющая информация, такая как признак модификации страницы, признак невыгружаемости (выгрузка некоторых страниц может быть запрещена), признак обращения к странице (используется для подсчета числа обращений за определенный период времени) и другие данные, формируемые и используемые механизмом виртуальной памяти.
  При активизации очередного процесса в специальный регистр процессора загружается адрес таблицы страниц данного процесса. При каждом обращении к памяти происходит чтение из таблицы страниц информации о виртуальной странице, к которой произошло обращение. Если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический. Если же нужная виртуальная страница в данный момент выгружена на диск, то происходит так называемое страничное прерывание. Выполняющийся процесс переводится в состояние ожидания, и активизируется другой процесс из очереди готовых. Параллельно программа обработки страничного прерывания находит на диске требуемую виртуальную страницу и пытается загрузить ее в оперативную память. Если в памяти имеется свободная физическая страница, то загрузка выполняется немедленно, если же свободных страниц нет, то решается вопрос, какую страницу следует выгрузить из оперативной памяти.
  В данной ситуации может быть использовано много разных критериев выбора, наиболее популярные из них – «первая попавшаяся страница» или «страница, к которой в последнее время было меньше всего обращений».
  В некоторых системах используется понятие рабочего множества страниц. Рабочее множество определяется для каждого процесса и представляет собой перечень наиболее часто используемых страниц, которые должны постоянно находиться в оперативной памяти и поэтому не подлежат выгрузке.
  После того, как выбрана страница, которая должна покинуть оперативную память, анализируется ее признак модификации (по таблице страниц). Если выталкиваемая страница с момента загрузки была модифицирована, то ее новая версия должна быть переписана на диск. Если нет, то она может быть просто уничтожена, то есть соответствующая физическая страница объявляется свободной.
  При каждом обращении к оперативной памяти с помощью аппаратных средств выполняются следующие действия:
  1) на основании начального адреса таблицы страниц (содержимое регистра адреса таблицы страниц), номера виртуальной страницы (старшие разряды виртуального адреса) и длины записи в таблице страниц (системная константа) определяется адрес нужной записи в таблице;
  2) из этой записи извлекается номер физической страницы;
  3) к номеру физической страницы присоединяется смещение (младшие разряды виртуального адреса).
  Использование в последнем пункте того факта, что размер страницы равен степени числа 2, позволяет применить операцию конкатенации (присоединения) вместо более длительной операции сложения, что уменьшает время получения физического адреса, а, следовательно, повышает производительность системы.
  На производительность системы со страничной организацией памяти влияют затраты времени, связанные с обработкой страничных прерываний и преобразованием виртуального адреса в физический. При часто возникающих страничных прерываниях система может тратить большую часть времени впустую. Чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. Кроме того, увеличение размера страницы уменьшает размер таблицы страниц, а значит, уменьшает затраты памяти. С другой стороны, если страница велика, следовательно, велика и фиктивная область в последней виртуальной странице каждого процесса. В среднем на каждом процессе теряется половина объема страницы, что в сумме при большой странице может составить существенную величину. Время преобразования виртуального адреса в физический в значительной степени определяется временем доступа к таблице страниц. В связи с этим таблицу страниц стремятся размещать в «быстрых» запоминающих устройствах. Это может быть, например, набор специальных регистров или память, использующая для уменьшения времени доступа ассоциативный поиск и кэширование данных.
  Страничное распределение памяти может быть реализовано в упрощенном варианте без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оперативной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю виртуальной памяти, но почти исключает фрагментацию за счет того, что, во-первых, программа может загружаться в несмежные области, а, во-вторых, при загрузке виртуальных страниц никогда не образуется остатков.
  При сегментном распределение памяти виртуальное адресное пространство процесса делится на сегменты, размер которых определяется программистом с учетом смыслового значения содержащейся в них информации. Отдельный сегмент может представлять собой подпрограмму, массив данных и т.п. Иногда сегментация выполняется по умолчанию компилятором. При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов операционная система подыскивает подходящий участок свободной памяти), а часть сегментов размещается в дисковой памяти. Сегменты одного процесса могут занимать в оперативной памяти несмежные участки. Во время загрузки система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация. Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единственном экземпляре.
  Система с сегментной организацией функционирует аналогично системе со страничной организацией: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту.
  Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное преобразование адреса по сравнению со страничной организацией памяти.
  Странично-сегментное распределение памяти представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов. Виртуальное пространство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страницы, которые нумеруются в пределах сегмента. Оперативная память делится на физические страницы. Загрузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура которой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов, в которой указываются адреса таблиц страниц для всех сегментов данного процесса. Адрес таблицы сегментов загружается в специальный регистр процессора, когда активизируется соответствующий процесс.
  Разновидностью виртуальной памяти является так называемый свопинг (swapping). В соответствии с методом свопинга некоторые процессы (обычно находящиеся в состоянии ожидания) временно выгружаются на диск. Планировщик операционной системы не исключает их из своего рассмотрения, и при наступлении условий активизации некоторого процесса, находящегося в области свопинга на диске, этот процесс перемещается в оперативную память. Если свободного места в оперативной памяти не хватает, то выгружается другой процесс.
  При свопинге, в отличие от рассмотренных ранее методов реализации виртуальной памяти, процесс перемещается между памятью и диском целиком, то есть в течение некоторого времени процесс может полностью отсутствовать в оперативной памяти. Существуют различные алгоритмы выбора процессов на загрузку и выгрузку, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу.
  Рассмотрим иерархию запоминающих устройств (ЗУ) и принцип кэширования информации.
  Память ВМ представляет собой иерархию ЗУ, включающую внутренние регистры процессора, различные типы сверхоперативной, оперативной и постоянной памяти, внешнюю память на магнитных дисках и других типах устройств. Разные типы ЗУ отличаются средним временем доступа и стоимостью хранения данных в расчете на один бит.
  Кэширование информации – это способ организации совместного функционирования двух типов ЗУ, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным за счет динамического копирования наиболее часто используемой информации из относительно более «медленного» ЗУ в более «быстрое» ЗУ. Кэш-памятью обычно называют одно из таких взаимодействующих устройств, а именно «быстрое» ЗУ. Оно стоит дороже и, как правило, имеет сравнительно небольшой объем. Таким образом кэширование представляет собой некоторое компромиссное решение проблемы стоимости и быстродействия памяти. Важно, что механизм кэш-памяти является прозрачным для пользователя, то есть пользователь не должен сообщать никаких сведений об интенсивности использования информации и никак не должен участвовать в перемещении информации из ЗУ одного типа в ЗУ другого типа. Все это делается автоматически системными средствами.
  Представим частный случай использования кэш-памяти для уменьшения среднего времени доступа к данным, хранящимся в оперативной памяти. Для этого между процессором и оперативной памятью помещается «быстрое» ЗУ – кэш-память. Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных. Каждая запись об элементе данных включает в себя адрес, который этот элемент данных имеет в оперативной памяти, и управляющую информацию: признак модификации и признак обращения к данным за некоторый последний период времени.
  В системах, оснащенных кэш-памятью, каждый запрос к оперативной памяти выполняется в соответствии со следующим алгоритмом:
  1) просматривается содержимое кэш-памяти с целью определения, не находятся ли нужные данные в кэш-памяти (кэш-память не является адресуемой, поэтому поиск нужных данных осуществляется по содержимому – значению поля «адрес в оперативной памяти», взятому из запроса);
  2) если данные обнаруживаются в кэш-памяти, то они считываются из нее, и результат передается в процессор;
  3) если нужных данных нет, то они вместе со своим адресом копируются из оперативной памяти в кэш-память, и результат выполнения запроса передается в процессор.
  При копировании данных может оказаться, что в кэш-памяти нет свободного места, тогда для вытеснения из кэш-памяти выбираются данные, к которым в последний период было меньше всего обращений. Если вытесняемые данные были модифицированы за время нахождения в кэш-памяти, то они переписываются в оперативную память. Если же эти данные не были модифицированы, то их место в кэш-памяти объявляется свободным.
  На практике в кэш-память считывается не один элемент данных, к которому произошло обращение, а целый блок данных. Это увеличивает вероятность так называемого «попадания в кэш», то есть нахождения нужных данных в кэш-памяти. В реальных системах вероятность попадания в кэш составляет примерно 0,9.
  Высокое значение вероятности нахождения данных в кэш-памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.
  Под пространственной локальностью данных в кэш-памяти понимается такой случай, когда произошло обращение по некоторому адресу и с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам.
  Под временной локальностью данных в кэш-памяти понимается случай большой вероятности обращения по этому же адресу в ближайшее время.
  Все предыдущие рассуждения справедливы и для других пар запоминающих устройств, например, для оперативной памяти и внешней памяти. В этом случае уменьшается среднее время доступа к данным, расположенным, например, на магнитном диске, а роль кэш-памяти выполняет буфер в оперативной памяти.
 2.2. Управление вводом-выводом
 
  Одной из главных функций ОС является управление всеми устройствами ввода-вывода ВМ. ОС должна передавать устройствам команды, перехватывать прерывания и обрабатывать ошибки; она также должна обеспечивать интерфейс между устройствами и остальной частью машины. В целях развития интерфейс должен быть одинаковым для всех типов устройств (принцип независимости от устройств).
  Устройства ввода-вывода делятся на два типа: блок-ориентированные устройства и байт-ориентированные устройства.
  Блок-ориентированные устройства ввода-вывода хранят информацию в блоках фиксированного размера, каждый из которых имеет свой собственный адрес. Самое распространенное блок-ориентированное устройство – диск.
  Байт-ориентированные устройства ввода-вывода не адресуемы и не позволяют производить операцию поиска, они генерируют или потребляют последовательность байтов. Примерами являются мониторы, принтеры, сетевые адаптеры. Однако некоторые внешние устройства не относятся ни к одному классу, например, часы, которые, с одной стороны, не адресуемы, а с другой стороны, не порождают потока байтов. Это устройство только выдает сигнал прерывания в некоторые моменты времени.
  Любое внешнее устройство обычно состоит из механического и электронного компонента. Электронный компонент называют контроллером устройства или адаптером. Механический компонент представляет собственно устройство. Некоторые контроллеры могут управлять несколькими устройствами. Если интерфейс между контроллером и устройством стандартизован, то независимые производители могут выпускать совместимые как контроллеры, так и устройства.
  ОС обычно имеет дело не с устройством, а с его контроллером. Контроллер, как правило, выполняет простые функции, например, преобразует поток бит в блоки (состоящие из байт), осуществляют контроль и исправление ошибок. Каждый контроллер имеет несколько регистров, которые используются для взаимодействия с центральным процессором. В некоторых ВМ эти регистры являются частью физического адресного пространства. В таких ВМ нет специальных операций ввода-вывода. В других машинах адреса регистров ввода-вывода, называемых часто портами, образуют собственное адресное пространство за счет введения специальных операций ввода-вывода.
  ОС выполняет ввод-вывод, записывая команды в регистры контроллера. Когда команда принята, процессор оставляет контроллер и занимается другой работой. При завершении команды контроллер организует прерывание для того, чтобы передать управление процессором операционной системе, которая должна проверить результаты операции. Процессор получает результаты и статус устройства, читая информацию из регистров контроллера.
  Основная идея организации программного обеспечения ввода-вывода состоит в разбиении его на несколько уровней, причем нижние уровни обеспечивают экранирование особенностей аппаратуры от верхних, а те, в свою очередь, обеспечивают удобный интерфейс для пользователей. Ключевым принципом является независимость от устройств ввода-вывода. Вид программы не должен зависеть от того, читает ли она данные с гибкого диска или с жесткого диска.
  Очень близкой к идее независимости от устройств является идея единообразного именования, то есть для именования устройств должны быть приняты единые правила.
  Другим важным вопросом для программного обеспечения ввода-вывода является обработка ошибок. В лучшем случае ошибки следует обрабатывать как можно ближе к аппаратуре. Если контроллер обнаруживает ошибку чтения, то он должен попытаться ее скорректировать. Если же это ему не удается, то исправлением ошибок должен заняться драйвер устройства. Многие ошибки могут исчезать при повторных попытках выполнения операций ввода-вывода, например, ошибки, вызванные наличием пылинок на головках чтения или на диске. И только если нижний уровень не может справиться с ошибкой, он сообщает об ошибке верхнему уровню.
  Еще один ключевой вопрос – это использование блокирующих (синхронных) и неблокирующих (асинхронных) передач. Большинство операций физического ввода-вывода выполняется асинхронно – процессор начинает передачу и переходит на другую работу, пока не наступает прерывание. Пользовательские программы намного легче писать, если операции ввода-вывода блокирующие. ОС выполняет операции ввода-вывода асинхронно, но представляет их для пользовательских программ в синхронной форме.
  Проблема состоит также в том, что одни устройства ввода-вывода являются разделяемыми, а другие – выделенными. Диски – это разделяемые устройства, так как одновременный доступ нескольких пользователей к диску не является проблемой. Принтеры – это выделенные устройства, потому что нельзя смешивать строчки, печатаемые различными пользователями. Наличие выделенных устройств создает для операционной системы некоторые проблемы.
  Для решения имеющихся проблем целесообразно разделить программное обеспечение ввода-вывода на четыре слоя:
  1) обработка прерываний;
  2) драйверы устройств;
  3) слой операционной системы, независимый от устройств;
  4) пользовательский слой программного обеспечения.
  Прерывания должны быть скрыты как можно глубже в «недрах» ОС, чтобы как можно меньшая часть ОС имела с ними дело. Наилучший способ состоит в разрешении процессу, инициировавшему операцию ввода-вывода, блокировать себя до завершения операции и наступления прерывания. При наступлении прерывания процедура обработки прерывания выполняет разблокирование процесса, инициировавшего операцию ввода-вывода. В любом случае эффект от прерывания будет состоять в том, что ранее заблокированный процесс теперь продолжит свое выполнение.
  Весь зависимый от устройства код помещается в драйвер устройства. Каждый драйвер управляет устройствами одного типа или, может быть, одного класса. В ОС, как правило, только драйвер устройства обладает информацией о конкретных особенностях какого-либо устройства. Например, только драйвер диска имеет дело с дорожками, секторами, цилиндрами, временем установления головки и другими факторами, обеспечивающими правильную работу диска.
  Драйвер устройства принимает запрос от устройств программного слоя и решает, как его выполнить. Типичным запросом является, например, чтение N блоков данных. Если драйвер был свободен во время поступления запроса, то он начинает выполнять запрос немедленно. Если же он был занят обслуживанием другого запроса, то вновь поступивший запрос присоединяется к очереди уже имеющихся запросов, и он будет выполнен, когда наступит его очередь.
  Первый шаг в реализации запроса ввода-вывода, например, для диска, состоит в преобразовании его из абстрактной формы в конкретную. Для дискового драйвера это означает, во-первых, преобразование номеров блоков в номера цилиндров, головок, секторов, во-вторых, проверку, работает ли двигатель, находится ли головка над нужным цилиндром и т.п. Короче говоря, он должен решить, какие операции контроллера нужно выполнить и в какой последовательности. После передачи команды контроллеру драйвер должен решить следующий вопрос: блокировать ли себя до окончания заданной операции или нет. Если операция занимает значительное время (например, при печати некоторого блока данных), то драйвер блокируется до тех пор, пока операция не завершится, и обработчик прерывания не разблокирует его. Если команда ввода-вывода выполняется быстро (например, прокрутка экрана), то драйвер ожидает ее завершения без блокирования.
  Большая часть программного обеспечения ввода-вывода является независимой от устройств. Точная граница между драйверами и программами, независимыми от устройств, определяется системой, так как некоторые функции, которые могли бы быть реализованы независимым способом, в действительности выполнены в виде драйверов для повышения эффективности или по другим причинам.
  Типичными функциями слоя операционной системы, независимого от устройств, являются:
  – обеспечение общего интерфейса к драйверам устройств;
  – именование устройств;
  – защита устройств;
  – обеспечение независимого размера блока;
  – буферизация;
  – распределение памяти на блок-ориентированных устройствах;
  – распределение и освобождение выделенных устройств;
  – уведомление об ошибках.
  Остановимся на некоторых функциях данного перечня. Верхним слоям программного обеспечения неудобно работать с блоками разной величины, поэтому данный слой обеспечивает единый размер блока, например, за счет объединения нескольких различных блоков в единый логический блок. В связи с этим верхние уровни имеют дело с абстрактными устройствами, которые используют единый размер логического блока независимо от размера физического сектора.
  При создании файла или заполнении его новыми данными необходимо выделить ему новые блоки. Для этого ОС должна вести список или битовую карту свободных блоков диска. На основании информации о наличии свободного места на диске может быть разработан алгоритм поиска свободного блока, независимый от устройства и реализуемый программным слоем, находящимся выше слоя драйверов.
  Хотя большая часть программного обеспечения ввода-вывода находится внутри ОС, некоторая его часть содержится в библиотеках, связываемых с пользовательскими программами. Системные вызовы, включающие вызовы ввода-вывода, обычно делаются библиотечными процедурами. В частности, форматирование ввода или вывода выполняется библиотечными процедурами. Стандартная библиотека ввода-вывода содержит значительное число процедур, которые выполняют ввод-вывод и работают как часть пользовательской программы.
  Другой категорией программного обеспечения ввода-вывода является подсистема спулинга (spooling). Спулинг – это способ работы с выделенными устройствами в многозадачной системе. Одно из типичных устройств, требующих спулинга, – принтер. Хотя технически легко позволить каждому пользовательскому процессу открыть специальный файл, связанный с принтером, такой способ опасен из-за того, что пользовательский процесс может монополизировать принтер на произвольное время. Вместо этого создается специальный процесс-монитор, который получает исключительные права на использование этого устройства. Также создается специальный каталог, называемый каталогом спулинга. Для того, чтобы напечатать файл, пользовательский процесс помещает выводимую информацию в этот файл и помещает его в каталог спулинга. Процесс-монитор по очереди распечатывает все файлы, содержащиеся в каталоге спулинга.
  Запись или чтение большого количества информации из ад-ресного пространства ввода-вывода (например, с диска) приводят к большому количеству операций ввода-вывода, которые должен выполнять процессор. Для освобождения процессора от операций последовательного вывода данных из оперативной памяти или последовательного ввода в нее был предложен механизм прямого доступа внешних устройств к памяти – ПДП или DMA (Direct Memory Access). Суть работы этого механизма заключается в следующем. Для того чтобы какое-либо устройство, кроме процессора, могло за­писать информацию в память или прочитать ее из памяти, необходимо чтобы это устройство могло забрать у процессора управление локальной магистралью для выставления соответствующих сигналов на шины адреса, данных и управления. Для централизации эти обязанности обычно возла­гаются не на каждое устройство в отдельности, а на специальный контрол­лер – контроллер прямого доступа к памяти. Контроллер прямого доступа к памяти имеет несколько спаренных линий – каналов DMA, которые мо­гут подключаться к различным устройствам. Перед началом использова­ния прямого доступа к памяти этот контроллер необходимо запрограмми­ровать, записав в его порты информацию о том, какой канал или каналы предполагается задействовать, какие операции они будут совершать, ка­кой адрес памяти является начальным для передачи информации и какое количество информации должно быть передано. Получив по одной из ли­ний – каналов DMA – сигнал запроса на передачу данных от внешнего уст­ройства, контроллер по шине управления сообщает процессору о желании взять на себя управление локальной магистралью. Процессор (возможно, через некоторое время, необходимое для завершения его действий с маги­стралью) передает управление маги­стралью контроллеру DMA, известив его специ­альным сигналом. Контроллер DMA выставляет на адресную шину адрес памяти для передачи очередной порции информации и по второй линии канала прямого доступа к памяти сообщает устройству о готовности маги­страли к передаче данных. После этого, используя шину данных и шину управления, контроллер DMA, устройство ввода-вывода и память осуще­ствляют процесс обмена информацией. Затем контроллер прямого досту­па к памяти извещает процессор о своем отказе от управления магистра­лью, и тот берет руководящие функции на себя. При передаче большого количества данных весь процесс повторяется циклически.
  При прямом доступе к памяти процессор и контроллер DMA по очереди управляют локальной магистралью. Это, конечно, несколько снижает производительность процессора, так как при выполнении некоторых команд или при чтении очередной порции команд во внутренний кэш он должен дожидаться освобождения магистрали, но в целом производительность ВМ существенно возрастает.
  При подключении к системе нового устройства, которое умеет ис­пользовать прямой доступ к памяти, обычно необходимо программно или аппаратно задать номер канала DMA, к которому будет приписано уст­ройство. В отличие от прерываний, где один номер прерывания может соот­ветствовать нескольким устройствам, каналы DMA всегда находятся в монопольном владении устройств.
  2.3. Управление файлами и файловая система
 
  Под файлом обычно понимают набор данных, организованных в виде совокупности записей одинаковой структуры. Для управления этими дан­ными создаются соответствующие системы управления файлами. Возможность иметь дело с логическим уровнем структуры данных и операций, выполняемых над ними в процессе их обработки, предоставляет файловая система. Таким об­разом, файловая система – это набор спецификаций и соответствующее им про­граммное обеспечение, которые отвечают за создание, уничтожение, организацию, чтение, запись, модификацию и перемещение файловой информации, а также за управление доступом к файлам и за управление ресурсами, которые используют­ся файлами. Именно файловая система определяет способ организации данных на диске или на каком-нибудь ином носителе данных.
  Следует различать файловую систему и систе­му управления файлами. Система управления файлами является основной подсистемой в абсолютном большинстве современных ОС (хотя в принципе можно обхо­диться и без нее). Во-первых, через систему управления файлами связываются по данным все системные обрабатывающие программы. Во-вторых, с помощью этой системы решаются проблемы централизованного распределения дискового про­странства и управления данными. В-третьих, благодаря использованию той или иной системы управления файлами пользователям предоставляются следующие возможности:
  – создание, удаление, переименование (и другие операции) именованных набо­ров данных (именованных файлов) из своих программ или посредством спе­циальных управляющих программ, реализующих функции интерфейса пользо­вателя с его данными и активно использующих систему управления файлами;
  – работа с не дисковыми периферийными устройствами как с файлами;
  – обмен данными между файлами, между устройствами, между файлом и уст­ройством (и наоборот);
  – работа с файлами с помощью обращений к программным модулям системы управления файлами;
  – защита файлов от несанкционированного доступа.
  В некоторых ОС может быть несколько систем управления файлами, что обеспе­чивает им возможность работать с несколькими файловыми системами. Очевид­но, что системы управления файлами, будучи компонентом ОС, не являются не­зависимыми от этой ОС, поскольку они активно используют соответствующие вызовы прикладного программного интерфейса API (application program interface). С другой стороны, системы управления файлами сами дополняют API новыми вызовами. Можно сказать, что основное назначение файловой системы и соот­ветствующей ей системы управления файлами – организация удобного доступа к данным, организованным как файлы, то есть вместо низкоуровневого доступа к данным с указанием конкретных физических адресов нужной записи ис­пользуется логический доступ с указанием имени файла и записи в нем.
  Другими словами, термин «файловая система» определяет, прежде всего, прин­ципы доступа к данным, организованным в файлы. Этот же термин часто исполь­зуют и по отношению к конкретным файлам, расположенным на том или ином носителе данных. А термин «система управления файлами» следует употреблять по отношению к конкретной реализации файловой системы. То есть система управления файлами – это ком­плекс программных модулей, обеспечивающих работу с файлами в конкретной операционной системе.

<< Пред.           стр. 2 (из 8)           След. >>

Список литературы по разделу