гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Блок управления процессом Представителем процесса в операционной системе является блок управления процессом (РСВ). Это структура данных, содержащая определенную важную информацию о процессе, в том числе: • текущее состояние процесса; • уникальный идентификатор процесса; • приоритет процесса; • указатели памяти процесса; • указатели выделенных процессу ресурсов; • область сохранения регистров. Блок управления процессом является центральным пунктом, в котором операционная система может сосредоточить всю ключевую информацию о процессе. Когда операционная система переключает ЦП с процесса на процесс, она использует области сохранения регистров, предусмотренные в РСВ, чтобы за- помнить информацию, необходимую для рестарта (повторного запуска) каждого процесса, когда этот процесс в следующий раз получит в свое распоряжение ЦП. Таким образом, РСВ — это объект, который определяет процесс для операционной системы. По- скольку операционная система должна иметь возможность быстро выполнять операции с различными РСВ, во многих вычислительных машинах предусматривается специальный аппаратный регистр, кото- рый всегда указывает на РСВ текущего выполняемого процесса. Зачастую имеются также аппаратно- реализованные команды, которые обеспечивают быструю загрузку информации состояния в РСВ и по- следующее быстрое восстановление этой информации. Операции над процессами Системы, управляющие процессами, должны иметь возможность выполнять определенные операции над процессами, в том числе: • создание (образование) процесса; • уничтожение процесса; • возобновление процесса; • изменение приоритета процесса; • блокирование процесса; • пробуждение процесса; • запуск (выбор) процесса. Создание процесса состоит из многих операций, включая: • присвоение имени процессу; • включение этого имени в список имен процессов, известных • системе; • определение начального приоритета процесса; • формирование блока управления процессом РСВ; • выделение процессу начальных ресурсов. Процесс может породить новый процесс. В этом случае первый, порождающий процесс называется родительским процессом, а второй, созданный процесс - дочерним процессом. Для создания дочернего процесса необходим. Только один родительский процесс. При таком подходе создается иерархическая структура процессов, подобная показанной на рис. 2, в которой у дочернего процесса есть только один родительский процесс, но у каждого родительского процесса может быть много дочерних процессов. Рис. 2 Иерархия создания процессов. Уничтожение процесса означает его удаление из системы. Ресурсы, выделенные этому процессу, возвращаются системе, имя процесса в любых системных списках или таблицах стирается, и блок управления процессом освобождается. Приостановленный процесс не может продолжить свое выполнение до тех пор, пока его не активи- зирует какой-либо другой процесс. Приостановка — важная операция, которая реализуется во многих различных системах по-разному. Приостановки, как правило, длятся лишь небольшое время. Зачастую система прибегает к приостановкам для кратковременного исключения определенных процессов в пе- риоды пиковой нагрузки. В случае длительной приостановки процесса его ресурсы должны быть осво- бождены. Решение о необходимости освобождения конкретного ресурса в значительной степени зави- сит от природы этого ресурса. Основная память при приостановке процесса должна освобождаться не- медленно. Закрепленное за процессом лентопротяжное устройство в случае кратковременной приоста- новки процесса может быть за ним сохранено, однако его необходимо освобождать, если процесс при- останавливается на длительный или неопределенный период времени. Возобновление (или активация) процесса — операция подготовки процесса к повторному запуску с той точки, в которой он был приостановлен. 23 24 Уничтожение процесса усложняется, если это родительский процесс. В некоторых системах дочер- ний процесс уничтожается автоматически, когда уничтожается его родительский процесс, в других сис- темах порожденные процессы начинают существовать независимо от своих родительских процессов, так что уничтожение родительского процесса не оказывает влияния на его потомков. Изменение приоритета процесса, как правило, означает просто модификацию значения приоритета в блоке управления данным процессом. Приостановка и возобновление В предыдущем разделе были введены понятия о приостановке и возобновлении процессов. Эти опера- ции играют важную роль по нескольким причинам. • Если система работает ненадежно и есть признаки, что она может отказать, то текущие процессы можно приостановить, чтобы вновь активизировать впоследствии после исправления ошибки. • Пользователь, у которого отдельные промежуточные результаты работы процесса вызвали со- мнение, может приостановить его (а не выбросить совсем), пока он не выяснит, правильно ли ра- ботает этот процесс. • Некоторые процессы можно приостанавливать в моменты кратковременных пиков нагрузки сис- темы, с тем чтобы возобновлять их выполнение после того, как нагрузка возвратится к обычному уровню. На рис. 3 показана диаграмма состояний процесса, модифицированная с учетом операций приоста- новки и возобновления. В диаграмму введены два новых состояния, а именно «приостановлен готов» и «приостановлен блокирован», состояния «приостановлен выполняет» не бывает. На рисунке выше штриховой линии изображены активные состояния, а ниже — состояния приостановки. Инициатором приостановки может быть либо сам процесс, либо другой процесс. В однопроцессор- ной машине выполняющийся процесс может приостановить только сам себя, ни один другой процесс не может работать одновременно с ним, чтобы выдать сигнал приостановки. В мультипроцессорной ма- шине выполняющийся процесс может быть приостановлен и другим процессом, выполняющимся на другом процессоре. Процесс, находящийся в состоянии готовности, может быть приостановлен только другим процес- сом. При этом происходит следующая смена состояния: приостановка (имя процесса): готов > приостановлен готов Процесс, находящийся в состоянии «приостановлен готов», может быть переведен в состояние го- товности другим процессом. Состояния меняются следующим образом: возобновление (имя процесса): приостановлен готов > готов Заблокированный процесс может быть переведен в состояние приостановки другим процессом. При этом состояния меняются: приостановка (имя процесса): блокирован > приостановлен блокирован Процесс, находящийся в состоянии «приостановлен блокирован», может быть активизирован другим процессом. При этом состояния меняются: возобновление (имя процесса): приостановлен блокирован > блокирован Рис. 3 Диаграмма состояний процесса с операциями приостановки и возобновления. У читателя может возникнуть вопрос, не лучше ли вместо перевода заблокированного процесса в со- стояние приостановки подождать, пока не завершится выполнение операции ввода-вывода или не про- изойдет другое событие, необходимое для того, чтобы данный процесс стал готовым к выполнению. К сожалению, завершение операции ввода-вывода или ожидаемое событие может никогда не произойти или может задержаться на неопределенно долгий срок. Поэтому перед разработчиком возникает ди- лемма: либо выполнять приостановку заблокированного процесса, либо предусмотреть механизм, кото- рый позволял бы переводить процесс из состояния готовности в состояние приостановки, когда завер- шится операция ввода-вывода или наступит другое ожидаемое событие. Поскольку приостановка часто является операцией высокого приоритета, ее следует выполнять немедленно. Когда ожидаемое событие в конце концов происходит (если оно все-таки происходит), процесс, находящийся в состоянии «приос- тановлен блокирован», меняет свое состояние следующим образом: наступление события (имя процесса): приостановлен блокирован > приостановлен готов Сложные взаимодействия процессов - простая связь между работой и процедурами утрачивается в мультисистемах (технических и программных) a 1 a 2 a 3 a 4 b 1 b 2 b 3 b 4 A работы B процедуры S ⊆A×B R(S|a 2 )={b 1 ,b 2 ,b 3 ,b 4 } R(S|b 2 )={a 3 ,a 4 } 25 Уровни параллелизма Как известно, принцип параллелизма в ЭВМ применяеться для повышения эффективности и используеться на разных уровнях: 1. Уровень заданий + между заданиями + между фазами задания 2. Программный уровень + между частями программы + в пределах цикла ПО 3. Командный уровень + между фазами выполнений команды + между отдельными командами 4. Арифметический и разрядный уровени + между элементами векторной операции + внутри логических схем арифм. уст-ва. Итак, от самого низкого уровня параллелизма (арифметический уровень) - до самого верхнего уровня => господствует одна идея - повышение эффективности Классификация Флинна По-видимому, самой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 году М.Флинном [1,2]. Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD,MISD,SIMD,MIMD. SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - как машина CDC 6600 со скалярными функциональными устройст- вами, так и CDC 7600 с конвейерными попадают в этот класс. SIMD (single instruction stream / multiple data stream) - одиночный по- ток команд и множественный поток данных. В архитектурах подобно- го рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - эле- ментами вектора. Способ выполнения векторных операций не огова- ривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью кон- вейера, как, например, в машине CRAY-1. 26 MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в об- ласти архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной систе- мы, построенной на данном принципе. Ряд исследователей [3,4,5] от- носят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. Будем считать, что пока данный класс пуст. MIMD (multiple instruction stream / multiple data stream) - множествен- ный поток команд и множественный поток данных. Этот класс пред- полагает, что в вычислительной системе есть несколько устройств об- работки команд, объединенных в единый комплекс и работающих ка- ждое со своим потоком команд и данных. Итак, что же собой представляет каждый класс? В SISD, как уже говорилось, входят однопроцессорные последовательные компьютеры типа VAX 11/780. Однако, многими критиками подмечено, что в этот класс можно включить и векторно-конвейерные машины, если рассматривать вектор как одно недели- мое данное для соответствующей команды. В таком случае в этот класс попадут и такие системы, как CRAY-1, CYBER 205, машины семейства FACOM VP и многие другие. Бесспорными представителями класса SIMD считаются матрицы процессоров: ILLIAC IV, ICL DAP, Goodyear Aerospace MPP, Connection Machine 1 и т.п. В таких системах единое управляющее устройство контролирует множество процессорных элементов. Каждый процессорный элемент получает от устрой- ства управления в каждый фиксированный момент времени одинаковую команду и выполняет ее над своими локальными данными. Для классических процессорных матриц никаких вопросов не возникает, однако в этот же класс можно включить и векторно-конвейерные машины, например, CRAY-1. В этом случае каждый элемент вектора надо рассматривать как отдельный элемент потока данных. Класс MIMD чрезвычайно широк, поскольку включает в себя всевозможные мультипроцессорные сис- темы: Cm* , C.mmp , CRAY Y-MP, Denelcor HEP ,BBN Butterfly, Intel Paragon, CRAY T3D и многие дру- гие. Интересно то, что если конвейерную обработку рассматривать как выполнение множества команд (операций ступеней конвейера) не над одиночным векторным потоком данных, а над множественным скалярным потоком, то все рассмотренные выше векторно-конвейерные компьютеры можно располо- жить и в данном классе. Предложенная схема классификации вплоть до настоящего времени является самой применяемой при начальной характеристике того или иного компьютера. Если говорится, что компьютер принадлежит классу SIMD или MIMD, то сразу становится понятным базовый принцип его работы, и в некоторых случаях этого бывает достаточно. Однако видны и явные недостатки. В частности, некоторые заслужи- вающие внимания архитектуры, например dataflow и векторно--конвейерные машины, четко не вписы- ваются в данную классификацию. Другой недостаток - это чрезмерная заполненность класса MIMD. Необходимо средство, более избирательно систематизирующее архитектуры, которые по Флинну попа- дают в один класс, но совершенно различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования. Наличие пустого класса (MISD) не стоит считать недостатком схемы. Такие классы, по мнению некото- рых исследователей в области классификации архитектур [6,7], могут стать чрезвычайно полезными для разработки принципиально новых концепций в теории и практике построения вычислительных систем. 27 Эта классификация слишком широка – приписывает все параллельные ЭВМ, кроме мультипроцес- сорных, к классу ОКМД. Кроме того, классификация является запутанной, ибо, например, конвейерная векторная ЭВМ помещается в класс ОКОД, поскольку она обрабатывает один поток векторных данных. Классификация Шора - базируется на том, как построена машина из своих составных частей – было определено шесть различных типов машин, различаемых по цифровому обозначению УО – устройство обработки ПК – память команд ПД – память данных УУ – устройство управления Классификация Дж.Шора [9,10], появившаяся в начале 70-х годов, интересна тем, что представляет собой попытку выделе- ния типичных способов компоновки вычислительных систем на основе фиксированного числа базисных блоков: устройства управления, арифметико-логического устройства, памяти команд и памяти данных. Дополнительно предполагается, что вы- борка из памяти данных может осуществляться словами, то есть выбираются все разряды одного слова, и/или битовым сло- ем - по одному разряду из одной и той же позиции каждого слова (иногда эти два способа называют горизонтальной и вер- тикальной выборками соответственно). Конечно же, при анализе данной классификации надо делать скидку на время ее по- явления, так как предусмотреть невероятное разнообразие параллельных систем настоящего времени было в принципе не- возможно. Итак, согласно классификации Шора все компьютеры разбиваются на шесть классов, которые он так и называет: машина типа I, II и т.д. Машина I - это вычислительная система, которая содержит устройство управления, арифметико-логическое устройство, память команд и память данных с пословной выборкой. Считывание данных осуществляется вы- боркой всех разрядов некоторого слова для их параллельной обработки в арифметико-логическом устройстве. Состав АЛУ специально не оговари- вается, что допускает наличие нескольких функциональных устройств, быть может конвейерного типа. По этим соображениям в данный класс по- падают как классические последовательные машины (IBM 701, PDP-11, VAX 11/780), так и конвейерные скалярные (CDC 7600) и векторно- конвейерные (CRAY-1). Если в машине I осуществлять выборку не по словам, а выборкой содер- жимого одного разряда из всех слов, то получим машину II. Слова в памя- ти данных по прежнему располагаются горизонтально, но доступ к ним осуществляется иначе. Если в машине I происходит последовательная об- работка слов при параллельной обработке разрядов, то в машине II - по- следовательная обработка битовых слоев при параллельной обработке множества слов. Структура машины II лежит в основе ассоциативных компьютеров (напри- мер, центральный процессор машины STARAN), причем фактически такие компьютеры имеют не одно арифметико-логическое устройство, а множе- ство сравнительно простых устройств поразрядной обработки. Другим примером служит матричная система ICL DAP, которая может одновре- менно обрабатывать по одному разряду из 4096 слов. 28 Если объединить принципы построения машин I и II, то получим машину III. Эта машина имеет два арифметико-логических устройства - горизон- тальное и вертикальное, и модифицированную память данных, которая обеспечивает доступ как к словам, так и к битовым слоям. Впервые идею построения таких систем в 1960 году выдвинул У.Шуман , называвший их ортогональными (если память представлять как матрицу слов, то доступ к данным осуществляется в направлении, "ортогональном" традиционному - не по словам (строкам), а по битовым слоям (столбцам)). В принципе, как машину STARAN, так и ICL DAP можно запрограммировать на выполне- ние функций машины III, но поскольку они не имеют отдельных АЛУ для обработки слов и битовых слоев, отнести их к данному классу нельзя. Полноправными представителями машин класса III являются вычисли- тельные системы семейства OMEN-60 фирмы Sanders Associates, постро- енные в прямом соответствии с концепцией ортогональной машины. Если в машине I увеличить число пар арифметико-логическое устрой- ство <==> память данных (иногда эту пару называют процессорным элементом) то получим |