гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Элементарное определение и свойства процесса. - процесс есть основная еденица работы в системе ++ знакомый тип работы - последовательная программа ++ разделение процесса - программы на более короткие элементы, называемые процедурами ++ если рекурсия исключена, то процедура никогда не может приводиться в действие несколь- кими обращениями одновременно. ++ следовательно, любой работе, которая выполняеться в данный момент времени, однозначно соответствует действущая процедура Введение В этой главе мы вводим понятие процесса, наиболее важное для получения представления о работе современных многоабонентских вычислительных машин. Здесь приведено несколько наиболее распро- страненных определений процесса, однако следует отметить, что «идеального» определения в литера- туре пока еще нет. Мы представим концепцию дискретных состояний процесса, а также рассмотрим, каким образом процессы переходят из состояния в состояние. Кроме того, будет описан ряд основных операций, кото- рые могут выполняться над процессами. 17 Приведенные здесь определения и концепции послужат основой для обсуждения асинхронных па- раллельных процессов и планирования процессов в последующих главах. Создавать современные операционные системы без теоретической базы стало затруднительно, так как невозможно повторить условия, приведшие к ошибке во время работы, а следовательно, выявить ее источник. Все это привело к появле- нию понятия процесса. Понятие "процесс" в последнее время встречается в литературе по операционным системам довольно часто, однако вкладываемый в это понятие смысл иногда сильно различается. Мы будем пользоваться следующим опреде- лением. Процесс есть тройка (Q, f, g), где Q – множество состояний процесса; f – функция действия f : Q → Q; g ⊆ Q – на- чальное состояние процесса. Действия, реализуемые процессом, будем рассматривать как результат выполнения некоторой программы на реаль- ном (виртуальном) процессоре. Перечислим некоторые свойства процесса: • процесс не является закрытой системой и может взаимодействовать с другими процессами, воспринимая или изменяя часть среды, которую он с ними разделяет; • каждый процесс живет лишь временно. Имеется и "главный" процесс, выполняемый вручную при включении компьютера, который начинает всю цепочку процессов; • в любой момент процесс может быть описан его состоянием. Все параметры (переменные), характеризующие текущее состояние процесса, объ-единяются в "вектор состояний" или "слово состояний", которые позволяют возобновить процесс после его прерывания, в том числе и локальную среду. Определения термина «процесс» Термин «процесс» впервые начали применять разработчики системы MULTICS в 60-х годах. За прошедшее время термин «процесс», используемый в ряде случаев как синоним «задачи», получил мно- го различных определений. Мы приведем здесь некоторые из них: • программа в стадии выполнения; • асинхронная работа; • «живая душа» процедуры; • «концентрация средств управления» для выполняемой процедуры; • нечто, представленное в виде «блока управления процессом» в операционной системе; • объект, которому выделяются процессоры; • «диспетчируемый» модуль. Встречаются и многие другие определения. Таким образом, общепринятого определения пока нет, однако чаще всего, по-видимому, под процессом понимается «программа во время выполнения». Состояния процесса В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний: ВЫПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необхо- димыми ресурсами и непосредственно выполняется процессором; ОЖИДАНИЕ - пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ре- сурса; ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в свя- зи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса. В ходе жизненного цикла каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе. Типичный граф со- стояний процесса показан на рисунке 2.1. Рис. 2.1. Граф состояний процесса в многозадачной среде Смену состояний процесса могут вызывать различные события. Говорят, что процесс выполняется (т. е. находится в состоянии выполнения), если в данный момент ему выделен центральный процессор (ЦП). Говорят, что процесс готов (т. е. находится в состоянии го- товности), если он мог бы сразу использовать ЦП, предоставленный в его распоряжение. Говорят, что процесс заблокирован (т. е. находится в состоянии блокировки), если он ожидает появления некоторого события (например, завершения операции ввода-вывода), чтобы получить возможность продолжать вы- полнение. Существуют и другие состояния процесса, однако для первоначального обсуждения можно ограничиться этими тремя. Для простоты рассмотрим машину с одним центральным процессором, хотя все приведенные ниже рассуждения нетрудно распространить и на мультипроцессорную систему. В однопроцессорной маши- не в каждый конкретный момент времени может выполняться только один процесс, однако несколько процессов могут находиться в состоянии готовности, а несколько — в состоянии блокировки. Поэтому мы можем создать список готовых к выполнению процессов и список заблокированных процессов. Спи- сок готовых процессов упорядочен по приоритету, так что следующим процессом, получающим в свое распоряжение ЦП, будет первый процесс этого списка. Список заблокированных процессов не упоря- дочен — не предусматривается никакого приоритетного порядка разблокировки процессов (т. е. их пе- ревода в состояние готовности), разблокировка процессов осуществляется в том порядке, в котором происходят ожидаемые ими события. Так как большинство существующих ВС имеет один центральный процессор, то этот случай изучим подробнее. Рассмотрим абстрактную ВС с ОП, одним ЦП, устройством ввода и устройством печати. Структура такой ВС дана на рис. 5.4. Рис. 5.4. Структура ВС с одним ЦП 18 Пусть в исходном состоянии все периферийные устройства (ПУ) находятся в состоянии покоя, а ЦП выполняет процесс P i , управляемый последовательностью команд. Если в момент t i этот процесс выдает код, возбуждающий процесс в ПУ, то ЦП переходит в управляющий режим и посылает сигнал по линии связи A 1 , A 2 или A 3 . Затем ЦП возвращается к вы- полнению своего процесса. По окончании работы одно из ПУ посылает сигнал прерывания по линии B i , устанавливая тем самым i-й разряд регистра прерываний в соответствующее состояние. ЦП переходит в управляющий режим, анализирует состояние регистра прерываний для опознания ПУ, вызвавшего прерывания, и выполняет соответствующие действия. До перехода в режим управления ЦП запоминает состояние прерываемого процесса. Если во время обработки прерывания приходит новое прерывание, обработка предыдущего прерывания будет до- ведена до конца. Управление процессами в многопроцессорном компьютере Рассмотрим проекты ВС, включающие три компоненты: среду, процессоры и управление. Отметим, что централь- ный процессор управляется последовательностью команд, вызываемых откуда-то из среды, а периферийный процессор дей- ствует в соответствии с фиксированной, встроенной последовательностью команд. ПРОЕКТ 1. Предположим, что имеется достаточное количество процессоров различного типа, чтобы обслуживать любой родившийся процесс (рис. 5.3). Рис. 5.3. Структура МВС (проект 1) Управление будет состоять из центрального процессора (ЦП), управляемого процедурой, расположенной в памяти. Управляющий процессор соединен линиями связи с другими процессорами, запуская их и получая всю информацию о их состоянии. Обычное состояние ЦП – ожидание какого-нибудь события. При возбуждении управления оно определяет при- чину возбуждения, обрабатывает ее и, если возможно, запускает этот и/или другой процесс. Закончив обслуживание какого- то устройства, ЦП, прежде чем перейти в режим ожидания, проверяет, пуста ли очередь на обслуживание. Важной особенностью таких структур является необходимость защиты информации от несанкционированного чте- ния-записи. ПРОЕКТ 2. На втором этапе снимем наше предположение о бесконечном количестве процессоров различных типов. Теперь процессы будут выстраиваться в очередь из-за отсутствия свободного процессора. При освобождении очередного процессора управляющий процессор (УП) должен решать, кому его предоставить. Если снабдить УП механизмом прерыва- ния всех процессоров, то УП после сигнала об освободившемся процессоре может перераспределить работу всех процессо- ров заново. Этот проект оптимальнее предыдущего. ПРОЕКТ 3. На третьем этапе из-за того, что УП часто простаивает, мы можем функции УП распределять между все- ми ЦП. Центральные процессоры, работая в обычном режиме, выполняют какой-то процесс и могут быть прерваны ЦП, ра- ботающим в режиме управления. Последний не может быть прерван. Работой всех ЦП в управляющем режиме руководит одна и та же управляющая процедура. ПРОЕКТ 4. На четвертом этапе предположим, что в управляющем режиме могут работать одновременно несколько ЦП. В этом случае следует принять меры защиты информации при операциях с таблицами состояния процессов. Возбуждение управляющей процедуры (УП) может происходить одним из следующих способов: • если процесс, выполняющийся в ЦП, выдает сигнал связи, то этот же ЦП переключается в управляющий режим и вы- полняет соответствующие действия; • освободившийся от управления ЦП передает себя какому-нибудь процессу; • прерывание от периферийного устройства переводит один из ЦП в режим управления. Просмотр всех ЦП происходит поочередно, и если все они находятся в режиме управления, прерывание помещается в очередь. В целях упрощения реализации можно все прерывания адресовать одному ЦП. Однако при этом увеличивается вре- мя обработки каждого события. 19 Переход процесса из состояния в состояние Когда в систему поступает некоторое задание, она создает соответствующий процесс, который затем устанавливается в конец списка готовых процессов. Этот процесс постепенно продвигается к головной части списка — по мере завершения выполнения предыдущих процессов. Когда процесс оказывается первым в списке готовых и когда освобождается центральный процессор, этому процессу выделяется ЦП и говорят, что происходит смена состояния процесса — он переходит из состояния готовности в состояние выполнения (рис. 1). Предоставление центрального процессора первому процессу списка го- товых процессов называется запуском, или Рис. 1 Диаграмма переходов процесса из состояния в состояние. выбором процесса для выполнения, и это делается при помощи системной программы, называемой дис- петчером. Подобную смену состояния мы обозначаем следующим образом: запуск (имя процесса): готов > выполняется Про процесс, имеющий в своем распоряжении ЦП, говорят, что он выполняется. Чтобы предотвра- тить либо случайный, либо умышленный монопольный захват ресурсов машины каким-то одним про- цессом, операционная система устанавливает в специальном аппаратном таймере прерываний некото- рое значение, определяющее временной интервал, или квант времени, в течение которого данному процессу пользователя разрешается занимать ЦП. Если процесс добровольно не освободит ЦП до исте- чения указанного временного интервала, таймер выработает сигнал прерывания, по которому управле- ние будет передано операционной системе. После этого операционная система переведет ранее выпол- нявшийся процесс в состояние готовности, а первый процесс списка готовых — в состояние выполне- ния. Эти смены состояний обозначаются следующим образом: истечение кванта (имя процесса): выполняется > готов и запуск (имя процесса): готов > выполняется Если выполняющийся процесс до истечения отпущенного ему кванта времени инициирует операцию ввода-вывода, этот процесс тем самым добровольно освобождает ЦП (т. е. сам себя блокирует в ожида- нии завершения указанной операции ввода-вывода). Эта смена состояния изображается так: блокирование (имя процесса): выполняется > блокирован 20 В нашей модели с тремя состояниями может иметь место еще лишь одна допустимая смена состоя- ния — когда завершается операция ввода-вывода (или происходит какое-либо другое событие, ожидае- мое процессом). При этом процесс переходит из состояния блокировки в состояние готовности. Эта 21 смена состояния обозначается так: пробуждение (имя процесса); блокирован > готов Таким образом, мы определили четыре возможные смены состояния процесса: запуск (имя процесса): готов > выполняется истечение кванта (имя процесса): выполняется > готов блокирование (имя процесса): выполняется > блокирован пробуждение (имя процесса): блокирован > готов Отметим, что единственная смена состояния, инициируемая самим процессом пользователя,— это блокирование, остальные три смены состояния инициируются объектами, внешними по отношению к данному процессу. Контекст и дескриптор процесса На протяжении существования процесса его выполнение может быть многократно прервано и про- должено. Для того, чтобы возобновить выполнение процесса, необходимо восстановить состояние его опе- рационной среды. Состояние операционной среды отображается состоянием регистров и программного счетчика, режимом работы процессора, указателями на открытые файлы, информацией о незавершенных операциях ввода-вывода, кодами ошибок выполняемых данным процессом системных вызовов и т.д. Эта информация называется контекстом процесса. Кроме этого, операционной системе для реализации планирования процессов требуется дополни- тельная информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса, место нахождения кодового сегмента и другая информация. В некоторых ОС (например, в ОС UNIX) информацию такого рода, используемую ОС для планирования процессов, называют дескриптором процесса. Дескриптор процесса по сравнению с контекстом содержит более оперативную информацию, кото- рая должна быть легко доступна подсистеме планирования процессов. Контекст процесса содержит менее актуальную информацию и используется операционной системой только после того, как принято решение о возобновлении прерванного процесса. Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки. Таким образом, каждый дескриптор, кроме всего прочего, содержит по крайней мере один указатель на дру- гой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупо- рядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое. Программный код только тогда начнет выполняться, когда для него операционной системой будет создан процесс. Создать процесс - это значит: 1. создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст; 2. включить дескриптор нового процесса в очередь готовых процессов; 3. загрузить кодовый сегмент процесса в оперативную память или в область свопинга. Форматы таблиц процессов Рассмотрим структуру записей в памяти компьютера, описывающих соответствующие процессы. Любой процесс, управляемый хранящейся в памяти программой, имеет два важных параметра: • адрес, по которому выбирается следующая команда; • адрес страницы (блока) данных, который следует прибавлять к каждой ссылке на данные во время обращения. Периферийный процесс характеризуется типом устройства и адресом данных, участвующих в обмене. Кроме того, каждый процесс может быть "свободным" или "занятым", пока не выполнится определенное условие. Каждому процессу в памяти компьютера соответствует запись примерно следующего формата (рис. 5.5) Процесс Тип требуемого процессора Параметры … Статус процесса Рис. 5.5. Структура записи процесса Статус процесса указывает, готов ли процесс к обработке или он ждет выполнения некоторого условия. Действия управляющей процедуры сводятся к обработке этих записей. Рассмотрим некоторые события процесса и 22 действия управляющей процедуры на эти события (табл. 5.1) Таблица 5.1. Примеры действий управляющей процедуры № п/п Событие процесса Реакция управляющей процедуры 1 Сигнал (запрос) образования нового процесса Формирует новую запись формата (рис.7.5) и добавляет ее в список за- писей процессов 2 Запрос прерывания процес- са до выполнения некоторо- го условия Проверяет, выполнено ли требуемое условие. Если нет, то находится соответствующая этому процессу запись и отмечается, что процесс ждет выполнения данного условия. 3 Сигнал прекращения процесса Находит и убирает нужную запись, подключая ее к списку "свободного места". Затем выбирает запись, в поле "статус" которой имеется по- метка "готов", и запускает соответствующий ей процесс. 4 Сигнал изменения значения семафора Изменяет значение семафора. Проверяет все записи прерванных процес- сов, не ждут ли они изменения состояния этого семафора и если да, то изменяет их статус на "готов". Для ускорения обработки управляющей процедурой всех записей последние хранятся не в виде последовательных записей (массива), а в виде списковой структуры. При организации списковой структуры проблема "сборки мусора" решает- ся автоматически, ибо свободная запись сразу подключается к списку "свободного места". Операции над процессами служат для их создания, обработки и уничтожения. Наиболее типичные операции над процессами: создать новый процесс; уничтожить процесс; приостановить процесс; активизировать процесс; установить при- оритет процесса; определить состояние процесса. |