гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
машину IV. Единственное устройство управ- ления выдает команду за командой сразу всем процессорным элемен- там. С одной стороны, отсутствие соединений между процессорными элементами делает дальнейшее наращивание их числа относительно простым, но с другой, сильно ограничивает применимость машин это- го класса. Такую структуру имеет вычислительная система PEPE, объ- единяющая 288 процессорных элементов. Если ввести непосредственные линейные связи между соседними про- цессорными элементами машины IV, например в виде матричной конфигурации, то получим схему машины V. Любой процессорный элемент теперь может обращаться к данным как в своей памяти, так и в памяти непосредственных соседей. Подобная структура характерна, например, для классического матричного компьютера ILLIAC IV. Заметим, что все машины с I-ой по V-ю придерживаются концепции разделения памяти дан- ных и арифметико-логических устройств, предполагая наличие шины данных или какого- либо коммутирующего элемента между ними. Машина VI, названная матрицей с функцио- нальной памятью (или памятью с встроенной логикой), представляет собой другой подход, предусматривающий распределение логики процессора по всему запоминающему устройст- ву. Примерами могут служить как простые ассоциативные запоминающие устройства, так и сложные ассоциативные процессоры. Формальное определение процесса, модель Хорнинга-Ренделла. Неформально, процесс можно представить себе как группу ячеек памяти, содержимое которых меняет- ся по определенным правилам. 29 30 В ЭВМ эти правила описываются программой, которую интерпретирует процессор. Синоним термина «Процесс», – «задача», «программа». − «Задача – основная единица, подчиняющаяся управляющей программе в мультипрограмм- ном режиме»; − «Процесс – это программа, выполняемая псевдопроцессором»; − «Процесс – это то, что происходит при выполнении программы на ЭВМ». Хорнинг и Ренделл (1973) построили формальное определение понятие процесса. Основные термины модели: − набор переменных состояния; − состояние; − пространство состояний; − действия; − работа; − функция действия; − процесс; − начальное состояние. Набор переменных состояния – набор Х={x 0 ,x 1 ,…,x N ,…}, характеризующих состояние. Состояние описывается заданием значений всех элементов, входящих в набор переменных состояния Х={x 0 =a,x 1 =b,…,x N =z,…}. Пространство состояний – множество состояний, которое может принимать набор переменных состоя- ния. Действие – присваивание значений некоторым из переменных набора. Работа – последовательность состояний, принадлежащих пространству состояний. Произвести работу – значит выполнить несколько действий. Функция действия – функция, отображающая состояния в действия. Функция перерабатывает новые состояния, получая последовательность состояний. Процесс P=(R x ,{f},R 0 ) – есть процесс, где R x -пространство состояний, {f}-множество функций дейсвия, R 0 -множество начальных точек начальных состояний, R 0 ⊂R x Начальные состояния – некоторые особые элементы пространства состояний. Пусть процесс Р определен на Х={x,y}. Работу процесса опишем последовательностью состояний {(2,1),(4,2),(6,3),(8,4),…,(2i,i),…} где (2,1) – начальное состояние; (x,y) →(x+2,y+1) –функция действия. Для общего случая – начальное состояние {(i,j),где i,j-натуральные числа} и функция действия f(x,y) →(f(x),f(y)). Каждое состояние процесса x ∈R x под воздействием функции действия f переходит в новое состояние x t=0 →x t=1 →x t=2 … В программе ЭВМ выполнение программы однозначно определяется значениями яче- ек памяти и регистров, содержащих элементы набора переменных состояния. Последовательность состояний x t=0 →… описывает ход работы программы в конкретной среде. Большинство идей, относящихся к процессам, можно сформулировать в терминам модели Хоннинга– Ренделла: взаимодействие, независимость, присвоение значений, синхронизация, тупики и т.д. Реализация процесса. Каждый программный процесс однозначно определяется некоторой информационной структурой, на- зываемой дескриптором процесса. Дескриптор процесса состоит из: 1. переменной состояния – («готов к работе», «работающий» и «заблокирован»); 2. защищенной области памяти, хранящей текущие значения регистров при прерывании про- цесса не окончившего работу; 3. информация о ресурсах, которыми владеет, может владеть или имеет право пользоваться. Свойства процессов: Процессы могут порождать новые процессы, уничтожать процессы и управлять процессами через спе- цификации «ядра» системы. Команды управления процессами: создать, активизировать, заблокировать, удалить, остановить и т.д. Много процессов в системе «разделяют» ресурсы системы: процессорное время (процессоры в много- процессорных системах), память, каналы, устройства. Процессы в системе функционируют в своих адресных пространствах и не должны нарушать независи- мость других процессов. Процессы в системе могут взаимодействовать через общие элементы своих состояний (память процес- сов). Процессы могут вступать в сложные структурные отношения через правила: «породить», «удалить», «уничтожить». Между родительскими и порожденными процессами могут иметь или не иметь место: наследование ре- сурсов, наименование приоритетов, наследование безопасности и т.д. Алгоритмы планирования процессов Планирование процессов включает в себя решение следующих задач: 1. определение момента времени для смены выполняемого процесса; 2. выбор процесса на выполнение из очереди готовых процессов; 3. переключение контекстов "старого" и "нового" процессов. Первые две задачи решаются программными средствами, а последняя в значительной степени аппа- ратно (см. раздел 2.3. "Средства аппаратной поддержки управления памятью и многозадачной среды в микропроцессорах Intel 80386, 80486 и Pentium"). Существует множество различных алгоритмов планирования процессов, по разному решающих вы- шеперечисленные задачи, преследующих различные цели и обеспечивающих различное качество мульти- программирования. Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов: алгоритмы, основанные на квантовании, и алгоритмы, основанные на приори- тетах. В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если: • процесс завершился и покинул систему, • произошла ошибка, • процесс перешел в состояние ОЖИДАНИЕ, • исчерпан квант процессорного времени, отведенный данному процессу. Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определен- ным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф со- стояний процесса, изображенный на рисунке 2.1, соответствует алгоритму планирования, основанному на квантовании. 31 32 Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные пе- риоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По разному может быть организована очередь готовых про- цессов: циклически, по правилу "первый пришел - первый обслужился" (FIFO) или по правилу "последний пришел - первый обслужился" (LIFO). Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет - это число, харак- теризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значени- ем.Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной пла- ты, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на про- тяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В послед- нем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относитель- ные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: вы- бирается процесс, имеющий наивысший приоритет. По разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса преры- вается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовно- сти. На рисунке 2.2 показаны графы состояний процесса для алгоритмов с относительными (а) и абсолют- ными (б) приоритетами. Во многих операционных системах алгоритмы планирования построены с использованием как кван- тования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов. Вытесняющие и невытесняющие алгоритмы планирования Существует два основных типа процедур планирования процессов - вытесняющие (preemptive) и не- вытесняющие (non-preemptive). Non-preemptive multitasking - невытесняющая многозадачность - это способ планирования процес- сов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс. Рис. 2.2. Графы состояний процессов в системах (а) с относительными приоритетами; (б)с абсолютными приоритетами Preemptive multitasking - вытесняющая многозадачность - это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей. Понятия preemptive и non-preemptive иногда отождествляются с понятиями приоритетных и беспри- оритетных дисциплин, что совершенно неверно, а также с понятиями абсолютных и относительных приори- тетов, что неверно отчасти. Вытесняющая и невытесняющая многозадачность - это более широкие понятия, чем типы приоритетности. Приоритеты задач могут как использоваться, так и не использоваться и при вы- тесняющих, и при невытесняющих способах планирования. Так в случае использования приоритетов дис- циплина относительных приоритетов может быть отнесена к классу систем с невытесняющей многозадач- ностью, а дисциплина абсолютных приоритетов - к классу систем с вытесняющей многозадачностью. А бес- приоритетная дисциплина планирования, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам. Основным различием между preemptive и non-preemptive вариантами многозадачности является сте- пень централизации механизма планирования задач. При вытесняющей многозадачности механизм плани- рования задач целиком сосредоточен в операционной системе, и программист пишет свое приложение, не заботясь о том, что оно будет выполняться параллельно с другими задачами. При этом операционная систе- ма выполняет следующие функции: определяет момент снятия с выполнения активной задачи, запоминает ее контекст, выбирает из очереди готовых задач следующую и запускает ее на выполнение, загружая ее кон- текст. При невытесняющей многозадачности механизм планирования распределен между системой и при- кладными программами. Прикладная программа, получив управление от операционной системы, сама опре- деляет момент завершения своей очередной итерации и передает управление ОС с помощью какого-либо системного вызова, а ОС формирует очереди задач и выбирает в соответствии с некоторым алгоритмом (на- пример, с учетом приоритетов) следующую задачу на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков. Для пользователей это означает, что управление системой теряется на произвольный период време- ни, который определяется приложением (а не пользователем). Если приложение тратит слишком много вре- мени на выполнение какой-либо работы, например, на форматирование диска, пользователь не может пере- ключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирова- 33 ние продолжалось бы в фоновом режиме. Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу. Поэтому разработчики приложений для non-preemptive операционной среды, возлагая на себя функ- ции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими час- тями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматиро- вания, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между зада- чами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить "дружественное" отношение своей про- граммы к другим выполняемым одновременно с ней программам, достаточно часто отдавая им управление. Крайним проявлением "недружественности" приложения является его зависание, которое приводит к обще- му краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения. Однако распределение функций планировщика между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данно- го фиксированного набора задач. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом исключаются нерациональные прерывания программ в "неудобные" для них мо- менты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто дру- гой не изменит эти данные. Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу. Примером эффективного использования невытесняющей многозадачности является файл-сервер NetWare, в котором, в значительной степени благодаря этому, достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование невытесняющей многозадачности в операци- онной среде Windows 3.х. Однако почти во всех современных операционных системах, ориентированных на высокопроизводи- тельное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая много- задачность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно в связи с этим вытесняющую многозадачность часто называют истинной многоза- дачностью. Синхронизация процессов Процессы, выполняемые в мультипрограммном режиме, можно рассматривать как набор последовательных слабо- связанных процессов, которые действуют почти независимо друг от друга, лишь изредка используя общие ресурсы. Взаимо- связь между такими процессами устанавливается с помощью различных сообщений и так называемого механизма синхрони- зации, который позволяет согласовывать и координировать работу процессов. А, В, С – разделяемый ресурс С В А Р 2 Критические участки процесса Р 1, Р 2 Р 1 Р1 Р2 – процессы Что бы не допустить одновременного выполнения обоих критических участков различных процессов для какого-нибудь разделяемого ресурса в системе должен существовать механизм, который бы син- хронизировал два этих процесса. Свойства этого механизма: 1. в каждый момент времени разрешается находится в своем критическом участ- ке не более, чем одному процессу (от- носительно фиксированного ресурса); 2. если один или несколько процессов хотят обратится к своим критическим участкам, то по меньшей мере один из них должен в конце концов получить разрешение войти в свой критический участок; Процессы должны общаться не только ради синхронизации с целью взаимного исключения, но и для обмена информацией посредством механизма передачи сообщений. 34 35 Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограмми- рования, может привести к их неправильной работе или даже к краху системы. Рассмотрим, например (ри- сунок 2.3), программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "зака- зов" другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой для определенности предполо- жим равным 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, в следствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полу- ченным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла про- цесса S. Таким образом, процесс S никогда не увидит свой файл распечатанным. Сложность проблемы син- хронизации состоит в нерегулярности возникающих ситуаций: в предыдущем примере можно представить и другое развитие событий: были потеряны файлы нескольких процессов или, напротив, не был потерян ни один файл. В данном случае все определяется взаимными скоростями процессов и моментами их прерыва- ния. Поэтому отладка взаимодействующих процессов является сложной задачей. Ситуации подобные той, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соот- ношения скоростей процессов, называются гонками. |