Размещено на http://www.allbest.ru

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное агентство железнодорожного транспорта

САМАРСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПУТЕЙ СООБЩЕНИЯ

Кафедра «Информационные системы и телекоммуникации»

ОРГАНИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

В ЭВМ И СИСТЕМАХ

Арбитраж, планирование и диспетчеризация

Методические рекомендации для студентов специальности

«Информационные системы и технологии»

дневной и заочной форм обучения

Составители:

В.А. Засов

Н.Н. Савченков

Самара 2005

УДК 004.94

Организация вычислительных процессов в ЭВМ и системах: Арбитраж, планирование и диспетчеризация. Методические рекомендации для студентов специальности «Информационные системы и технологии» дневной и заочной форм обучения / Составители Засов В.А., Савченков Н.Н. - Самара: СамГАПС, 2005. - 52 с.

вычислительный компьютерный арбитраж мультипроцессорный

Утверждено на заседании кафедры «Информационные системы и телекоммуникации» 7 февраля 2005 г., протокол 5.

Печатается по решению редакционно-издательского совета Самарской государственной академии путей сообщения.

В методических рекомендациях рассматриваются мультипроцессорный и мультипрограммный способы организации вычислительных процессов в компьютерных системах. Для мультипроцессорных систем приводятся схемы различных вариантов арбитража, для мультипрограммных систем - алгоритмы работы планировщиков и диспетчеров процессов и потоков. На примере операционной системы Windows 2000 изучаются практические задачи использования ресурсов вычислительной системы и изменения приоритетов потоков при планировании.

Предназначены для студентов специальности «Информационные системы и технологии» для выполнения практических и лабораторных работ, курсовых и дипломных проектов. Методические указания могут быть также полезны студентам других специальностей, изучающим компьютерные информационно-управляющие системы.

Составители: Валерий Анатольевич Засов

Николай Николаевич Савченков

© Самарская государственная академия путей сообщения, 2005

ОГЛАВЛЕНИЕ

1. Мультипроцессорный и мультипрограммный способы организации вычислительных процессов

1.1 Мультипроцессорные системы и арбитраж

1.2 Мультипрограммные системы

1.3 Гиперпотоковая организация вычислений

2. Процессы и потоки в вычислительных системах

2.1 Определение процессов, потоков и ресурсов ВС

2.2 Состояния потоков

3. Основы организации планирования и диспетчеризации процессов и потоков

3.1 Принципы планирования процессов и потоков

3.2 Классификация алгоритмов планирования (вытесняющие и невытесняющие, бесприоритетные и приоритетные алгоритмы)

3.3 Линейные алгоритмы планирования

3.4 Алгоритмы планирования, основанные на квантовании

3.5 Алгоритмы планирования, основанные на приоритетах

3.5 Смешанные алгоритмы планирования

4. Планирование вычислительных процессов в системах реального времени

4.1 Принципы планирования в системах реального времени

4.2 Планирование с предельными сроками

4.3 Частотно - монотонное планирование

5. Планирование в Windows 2000

5.1 Уровни приоритетов потоков в Windows 2000

5.2 Особенности алгоритмов планирования в Windows 2000

5.3 Учет квантов и управление их величиной

5.4 Динамическое повышение приоритета

5.5 Планирование потоков в симметричных мультипроцессорных системах

6. Практические и лабораторные работы по планированию процессов и потоков

6.1 Изучение диспетчера задач и системного монитора

6.2 Мониторинг использования ресурсов вычислительной системы

6.3 Учет квантов и управление их величиной

6.4 Изучение изменения состояния потоков при планировании

6.5 Изучение динамического изменения приоритета потока активного процесса

6.6 Изучение динамического изменения приоритета GUI-потоков

6.7 Изучение динамического повышения приоритетов при нехватке процессорного времени

Библиографический список

1. МУЛЬТИПРОЦЕССОРНЫЙ И МУЛЬТИПРОГРАММНЫЙ СПОСОБЫ ОРГАНИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

1.1 Мультипроцессорные системы и арбитраж

Эффективность организации вычислительных процессов в ЭВМ и системах во многом определяет их эксплуатационные характеристики, среди которых основными являются следующие /1/:

быстродействие (номинальное, среднее) - количество команд с фиксированной точкой (MIPS) и плавающей точкой (MFLOPS), выполняемых за одну секунду;

производительность - число определенных тестовых (эталонных) задач, выполняемых за единицу времени;

пропускная способность - количество пользовательских задач, выполняемых вычислительной системой в единицу времени;

надежность - среднее время (в часах) безотказной работы (обозначается MTBF);

удобство работы пользователей - возможность интерактивной работы одновременно с несколькими приложениями на одном компьютере;

реактивность системы - временной интервал между сигналом (внешним событием), поступившим на вход системы и получением результата (реакции системы) на это событие.

Развитие архитектуры ЭВМ от простейших фон-неймановских до современных вычислительных систем (ВС) базируется на двух основных способах организации вычислительных процессов - мультипроцессорном и мультипрограммном /1-5/.

Мультипроцессорный способ организации вычислительного процесса основан на использовании в составе ВС нескольких процессоров, на которых могут одновременно выполняться несколько задач (или разных частей одной задачи). ВС, реализующие мультипроцессорный способ организации вычислительного процесса, называются мультипроцессорными. За счет применения параллельной обработки мультипроцессорные системы имеют высокие быстродействие и производительность, их несложно масштабировать, а благодаря возможности перераспределения функций отказавшего процессорного модуля на работоспособные, т. е. реконфигурирования, эти системы являются высоконадежными.

Мультипроцессорные системы разделяются на два класса - симметричные и асимметричные ВС /1,2/.

Симметричные (SMP - Symmetric Multi Processors) ВС отличаются следующими особенностями:

· процессоры, составляющие систему, являются одинаковыми или близкими по характеристикам;

· все процессоры системы равноправны и способны выполнять одинаковый набор функций;

· все процессоры имеют доступ к общей памяти системы, через которую, главным образом, осуществляется их взаимодействие;

· доступ процессоров к общей памяти осуществляется через общую системную магистраль или посредством специальной коммуникационной среды (коммутаторов), обеспечивающих равное время доступа к ресурсам памяти каждого из процессоров;

· все процессоры имеют доступ к общим ресурсам ввода - вывода, т.е. разделяют их;

· симметричная ВС управляется общей для всех процессоров децентрализованной операционной системой (ОС), расщепленной на отдельные модули, которые могут выполняться параллельно во времени на разных доступных процессорах, таким образом, все процессоры равноправно участвуют как в управлении вычислительным процессом, так и в выполнении прикладных задач.

Классическим примером симметричных ВС являются высокопроизводительные серверы корпоративного класса, содержащие 2,4,8,…центральных процессоров и обеспечивающие высокую степень готовности 0,99999, что соответствует допустимому времени простоя - не более 5 мин. в год.

Асимметричные (ASMP - Asymmetric Multi Processors) ВС отличает следующее:

· процессоры, образующие систему, являются существенно различными по характеристикам, функциональным возможностям и роли, выполняемой в ВС;

· процессоры в системе неравноправны: в качестве ведущего (host, master) выделен универсальный процессор, управляющий всеми остальными ведомыми (slave) процессорами, которые, как правило, являются специализированными (цифровыми сигнальными процессорами, контроллерами дисковой памяти, прямого доступа к памяти и т.п.);

· на ведущем процессоре работает ОС, и этот процессор берет на себя функции распределения задач и ресурсов, а ведомые процессоры работают только как обрабатывающие устройства и никаких действий по организации вычислительного процесса не выполняют;

· доступ ведомых процессоров к общей памяти осуществляется через ведущий процессор или общую системную магистраль, к которой ведомые процессоры подключаются специализированными шинами;

· так как ОС работает только на одном ведущем процессоре, эта ОС является централизованной и по сложности близка сложности ОС однопроцессорной системы.

Организация вычислительного процесса в асимметричных мультипроцессорных ВС по принципу «ведущий-ведомый» существенно проще по сравнению с симметричными системами. Поэтому этот способ организации вычислительного процесса используется в рассчитанных на широкое применение типовых моделях ПК и рабочих станциях. С другой стороны, асимметричные ВС из-за большей централизации управления имеют меньшие производительность и надежность, так как процессоры не являются взаимозаменяемыми.

Симметричные мультипроцессорные системы позволяют получить лучшие эксплуатационные характеристики по сравнению с асимметричными системами, но увеличение числа процессоров (масштабирование) в симметричных системах требует решения ряда задач фундаментального характера.

Одна из главных проблем состоит в том, что зависимость увеличения быстродействия и производительности ВС от числа процессоров является нелинейной зависимостью: накладные расходы ресурсов ВС, связанные с организацией управления системой, при увеличении числа процессоров растут гораздо быстрее, чем вызываемый этим увеличением рост быстродействия и производительности /6/. Поэтому, начиная с определенного числа процессоров, неизбежно возникает вопрос об экономической целесообразности повышения быстродействия и производительности за счет применения этого способа организации вычислительных процессов. Заметим, однако, что в случаях, когда основной характеристикой системы является надежность, в симметричных системах специально вводят избыточное число процессоров, ибо их дублирование, хотя и неэффективное с точки зрения роста производительности, существенно увеличивает отказоустойчивость ВС.

Другой проблемой является создание мультипроцессорной ОС, которая может управлять вычислительным процессом большого числа совместно работающих процессоров. Такая ОС должна быть децентрализованной, легко расщепляемой на отдельные параллельно во времени исполняемые модули, и ее создание является сложной задачей.

Сложной проблемой в симметричных мультипроцессорных системах является управление доступом многих равноправных и независимых процессоров к общим системным ресурсам - памяти, устройствам ввода-вывода, системной шине. Процессоры разделяют эти ресурсы и конкурируют из-за доступа к ним. Поэтому в симметричные ВС вводят специальные аппаратно-программные средства, осуществляющие арбитраж. Система арбитража получает запросы от процессоров на системные ресурсы, формирует разрешения тем или иным процессорам на основе принятых критериев, например приоритетов.

Существуют различные системы арбитража: централизованный параллельный или последовательный, централизованный или децентрализованный опрос, децентрализованный арбитраж и ряд других /2-5/, отличающихся сложностью, временем арбитража, возможностью перепрограммирования в процессе работы.

При централизованном арбитраже в ВС имеется специальное устройство - контроллер арбитра, ответственное за предоставление доступа к шине только одному из запросивших ведущих модулей (процессоров).

В централизованном параллельном арбитраже, схема которого изображена на рис.1.1, контроллер арбитра связан с каждым потенциальным ведущим модулем индивидуальными линиями «Запрос» и «Разрешение» шины. Получив запрос от ведущего модуля, приоритет которого выше, чем у текущего ведущего, контроллер арбитра снимает сигнал разрешения шины на входе текущего ведущего модуля и выдает сигнал разрешения шины запросившему ведущему. В свою очередь, текущий ведущий, обнаружив, что контроллер арбитра снял с его входа сигнал разрешения шины, завершает передачу информации по шине, снимает сигналы запроса и занятости шины. После этого запросивший шину ведущий модуль получает право управления шиной, т.е. доступ к системным ресурсам. Эта система арбитража выгодно отличается высоким быстродействием и гибкостью, так как допускает динамическое изменение приоритетов модулей путем перепрограммирования контроллера арбитра. Однако эта система имеет повышенную сложность и стоимость из-за большого числа линий арбитража, которые требуется ввести в системную шину.

Размещено на http://www.allbest.ru

В централизованном последовательном арбитраже, схема которого приведена на рис.1.2, запросы ведущих модулей объединяются на единственной линии запроса шины по схеме «монтажное ИЛИ». Получив сигнал запроса шины, контроллер арбитра анализирует состояние линии занятости шины и, если шина свободна, формирует сигнал разрешения шины. Сигнал разрешения шины последовательно распространяется по цепочке от одного ведущего к другому до тех пор, пока не поступит в первый из модулей, которые запрашивали доступ к шине. Этот модуль блокирует дальнейшее распространение сигнала разрешения шины по цепочке, формирует активный сигнал занятости шины и получает управление шиной.

Размещено на http://www.allbest.ru

Основные достоинства этой системы арбитража заключаются в простоте реализации, в малом количестве используемых линий и простом наращивании числа модулей, подключаемых к шине. Недостатками централизованного последовательного арбитража являются низкие быстродействие и надежность, а также статическое (фиксированное) распределение приоритетов, определяемое положением модулей в цепочке.

Размещено на http://www.allbest.ru

Пример системы арбитража на основе централизованного опроса приведен на рис.1.3. В этой системе, как и в предыдущей, запросы ведущих модулей объединяются на единственной линии запроса шины по схеме «монтажное ИЛИ». Получив сигнал запроса шины, контроллер арбитра анализирует состояние линии занятости шины и, если шина свободна, формирует сигналы опроса модулей. Опрос модулей может производиться путем формирования последовательности адресов модулей. Когда запрашивающий модуль распознает свой адрес, он формирует активный сигнал занятости шины и получает право на использование ее. Эта система арбитража является гибкой, так как позволяет динамически изменять приоритеты ведущих модулей путем изменения последовательности их опроса, требует сравнительно небольшого числа линий шины, но очевидно, что быстродействие этой системы арбитража невелико.

При децентрализованном, или распределенном арбитраже единый контроллер арбитра отсутствует. Вместо этого каждый ведущий модуль содержит локальный контроллер арбитра, управляющий доступом к шине своего модуля. Эти локальные контроллеры взаимодействуют друг с другом, разделяя между собой ответственность за доступ к шине. По сравнению с централизованным арбитражем децентрализованный более надежен, т.к. отсутствует единственная точка отказа.

Одна из возможных систем децентрализованного параллельного арбитража показана на рис.1.4. Каждый ведущий модуль имеет собственный локальный арбитр, который задает свой уровень приоритета. Сигналы запроса шины от любого ведущего модуля поступают на входы всех остальных ведущих. В каждом из локальных контроллеров арбитра сигнал разрешения шины формируется следующим образом:

(разреш. шины N) = (запр. шины N); ____________

(разреш. шины N-1) = (запр. шины N-1)&(запр. шины N);

____________ ______________

(разреш. шины N-2) = (запр. шины N-2)&(запр. шины N)&(запр. шины N-1) и т.д.

Размещено на http://www.allbest.ru

Получив сигнал разрешения шины, контроллер арбитра анализирует состояние линии занятости шины и, если шина свободна, занимает шину и формирует сигнал занятости шины.

Вне зависимости от принятой системы арбитража должна быть реализована стратегия ограничения времени использования шины каждым из ведущих модулей. Одним из вариантов является разрешение ведущему занимать шину в течение одного цикла шины с предоставлением ему возможности конкуренции за шину в последующих циклах.

Сложной проблемой в симметричных мультипроцессорных системах является создание высокоскоростной коммуникационной среды, посредством которой осуществляется доступ процессоров к общим системным ресурсам, и межпроцессорный обмен сообщениями. Типовые системные шины, например, PCI, PCI-X имеют недостаточную скорость обмена, а коммутаторы, многопортовая память и специальные высокоскоростные сети сложны и дороги для широкого применения /4,5/. Одним из возможных решений этой проблемы является выделение для каждого из процессоров ВС локальных ресурсов - памяти и каналов ввода-вывода, которые подключаются к процессору с помощью локальных шин. Этими локальными ресурсами каждый из процессоров владеет монопольно, что сокращает число обращений к общим системным ресурсам и снижает требования к пропускной способности коммуникационной среды. По сути наблюдается переход от мультипроцессорных к мультикомпьютерным системам, реализуемым на основе высокоскоростных сетей - к кластерным системам /4,5/. Если в качестве коммуникационной сети используется типовая локальная сеть, такая ВС называется распределенной /4,5/.

Упражнение 1.1. Вывести формулы для определения числа линий шины для вышерассмотренных систем арбитража.

Упражнение 1.2. Разработать функциональные схемы контроллеров арбитров для централизованного параллельного арбитража (фиксированные и динамические уровни приоритетов), централизованного опроса (фиксированные и динамические уровни приоритетов), централизованного и децентрализованного последовательного арбитража.

1.2 Мультипрограммные системы

Мультипрограммный способ (многозадачный (multitasking)) организации вычислительного процесса позволяет на одном процессоре попеременно выполнять сразу несколько программ. Эти программы совместно используют не только процессор, но и другие ресурсы компьютера: оперативную и внешнюю память, устройства ввода-вывода, данные. Заметим, что компьютер может быть выполнен на базе асимметричной мультипроцессорной системы.

Основой мультипрограммного способа является быстрый рост производительности процессоров. Согласно эмпирическому закону Мура сложность и производительность процессоров каждые восемнадцать месяцев удваиваются /2/. Высокопроизводительный процессор полностью загрузить одной программой (задачей) практически сложно, поэтому эта цель достигается одновременным выполнением процессором группы программ. Помимо эффективного использования ресурсов процессора, мультипрограммный режим позволяет пользователям (или одному пользователю) интерактивно работать сразу с несколькими программами, что повышает удобство работы пользователей.

Следует заметить, что в отличие от мультипроцессорных систем, где имеет место подлинная параллельность во времени выполнения нескольких программ, в мультипрограммных системах может идти речь только о псевдопараллельности выполнения группы программ (задач). Эта кажущаяся параллельность во времени достигается за счет попеременного выделения каждой из программ коротких (порядка десяти миллисекунд) квантов процессорного времени, причем кванты времени также выделяются через короткие (десятки миллисекунд) интервалы времени. Так как человек начинает воспринимать задержки ответа системы, если эти задержки превышают 100 мсек, у пользователя ВС создается иллюзия параллельного выполнения нескольких приложений.

Мультипрограммные системы разделяются на следующие классы: системы пакетной обработки, системы разделения времени и системы реального времени /1,7/.

Системы пакетной обработки предназначаются для решения задач в основном вычислительного характера, не требующих быстрой реакции системы. Главной целью этого способа организации вычислительного процесса является получение максимальной пропускной способности ВС. Для этого необходимо минимизировать простои всех устройств компьютера, и, прежде всего, центрального процессора. Алгоритм функционирования систем пакетной обработки следующий: в начале работы формируется пакет задач с указанием требований к системным ресурсам для каждой из задач; далее из этого пакета заданий формируется мультипрограммная смесь, т.е. множество одновременно выполняемых задач, предъявляющих разные требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств ВС. Например, целесообразно одновременное выполнение вычислительных задач и задач с интенсивным вводом-выводом. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой происходит по инициативе самой активной задачи, например, когда она отказывается от процессора из-за необходимости выполнить операцию ввода-вывода. Поэтому существует высокая вероятность того, что одна задача может надолго занять процессор, и выполнение интерактивных задач станет невозможным. Другими словами, невозможно гарантировать выполнение той или иной задачи в течение определенного периода времени /1/.

Размещено на http://www.allbest.ru

Преимущества мультипрограммной пакетной обработки иллюстрируются диаграммой, приведенной на рис.1.5.

Из диаграммы видно, что общее время Т_мп выполнения задач А и В в мультипрограммной системе меньше, чем их суммарное время Т_оп последовательного выполнения в однопрограммной системе. Действительно, Т_мп=3+5+3+3=14 единиц времени и Т_оп=3+3+3+5+2+3=19 единиц, т.е. Т_мп<Т_оп, что является следствием совмещения вычислений одной задачи с вводом-выводом другой.

Однако выполнение отдельных задач А и В в мультипрограммной пакетной системе занимает больше времени, чем при монопольном выделении процессора каждой из этих задач (однопрограммной системе), т.е. Т_А(мп)=3+5+3=11, Т_В(мп)=5+3+3=11, Т_А(оп)=3+3+3=9, Т_В(оп)=5+2+3=10, следовательно Т_А(мп) >Т_А(оп) и Т_В(мп) > Т_В(оп). Это происходит из-за ожидания задачами, готовыми для выполнения, освобождения процессора, занятого выполнением других задач.

В системах разделения времени всем программам по очереди выделяется квант процессорного времени, таким образом, у пользователя, запустившего группу программ на выполнение, возникает возможность интерактивного взаимодействия с каждой из программ. Хотя кванты времени короткие, выделяются они часто, поэтому ни одна из программ не занимает процессор надолго, и время реакции ВС оказывается приемлемым, что важно в интерактивных, например диспетчерских, системах управления. Очевидно, что системы разделения времени обладают меньшей пропускной способностью, чем системы пакетной обработки, но благодаря возможности интерактивного взаимодействия с каждой из программ, системы разделения времени распространены гораздо шире, и этот способ организации вычислительных процессов используется практически во всех ПК. Поэтому мультипрограммные системы разделения времени ниже будут рассмотрены более подробно.

Мультипрограммные системы реального времени /1,7,8,9/ предназначены для компьютерного управления различными техническими объектами (например, двигателями локомотива, железнодорожным переездом, станком и т.д.) или технологическими процессами (например, роспуском поездов на горках, управлением движения поезда по режимной карте машиниста и т.п.).

Во всех этих случаях существует предельно допустимое время, в течение которого должна быть выполнена та или иная управляющая объектом программа, в противном случае может произойти авария. Поэтому важнейшей характеристикой систем реального времени является время реакции системы, или реактивность. Другими словами, в системах реального времени управляющее воздействие на объект должно быть не только логически правильным, но и своевременным, т.е. не отставать от реальных событий. Требования ко времени реакции зависят от специфики управляемого процесса, например, компьютер системы автоматического ведения поезда должен выдавать управляющее воздействие в течение десятков миллисекунд, а компьютер системы кондиционирования - нескольких секунд.

В системах реального времени мультипрограммная смесь представляет собой фиксированный набор заранее разработанных программ, а выбор программы на выполнение осуществляется по прерываниям (исходя из текущего состояния объекта) или в соответствии с расписанием выполнения задач /1,9/.

Способность аппаратуры компьютера и ОС к быстрому ответу зависит в основном от скорости переключения с одной задачи на другую, и в частности от скорости обработки сигналов прерывания. Если при возникновении прерывания процессор должен опросить сотни потенциальных источников прерывания, то реакция системы будет слишком медленной. Время обработки прерывания в системах реального времени часто определяет требования к классу процессора даже при небольшой его загрузке.

В системах реального времени не стремятся максимально загружать все устройства, наоборот, при проектировании программного управляющего комплекса обычно закладывается некоторый «запас» вычислительной производительности на случай пиковой нагрузки. Статистические аргументы о низкой вероятности возникновения пиковой нагрузки, основанные на том, что вероятность одновременного возникновения большого количества независимых событий очень мала, неприменимы ко многим ситуациям в системах управления. Если система реального времени не спроектирована для поддержания пиковой нагрузки, то может случиться так, что система не справится с работой именно тогда, когда она нужна в наибольшей степени.

1.3 Гиперпотоковая организация вычислений

Мультипроцессорный и мультипрограммный способы организации вычислительных процессов в ВС - это два полюса, между которыми существует многие ВС, использующих в той или иной мере средства того и другого способов.

Например, в основе гиперпотоковой технологии (hyperthreading), используемой в ВС на базе процессоров Pentium 4, лежит то, что современные процессоры в большинстве своем являются суперскалярными и суперконвейерными, т.е. состоят из группы вычислительных блоков различного функционального назначения /2/. Поддерживающая гиперпотоковую технологию ОС воспринимает один физический процессор как несколько (в частности в виде двух) независимых логических процессоров и организует выполнение программ на каждом из этих логических процессоров. Это не означает, что в процессоре имеются несколько вычислительных ядер, - логические процессоры используют ресурсы единственного вычислительного ядра. Вследствие этого вычислительные блоки процессора загружаются более эффективно, и увеличивается его производительность. Действительно, часть программ, использующих разные вычислительные блоки единственного процессора, может выполняться параллельно, а не псевдопараллельно, как в системах с разделением времени. Поэтому гиперпотоковые системы занимают промежуточное положение между мультипроцессорными и мультипрограммными системами.

2. ПРОЦЕССЫ И ПОТОКИ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

2.1 Определение процессов, потоков и ресурсов ВС

Для реализации мультипрограммного способа организации вычислительного процесса необходимо определить единицы работы, между которыми ОС разделяются ресурсы компьютера. Такими базовыми единицами работы ОС являются процессы (process) и потоки (threads - нити) /1,7,8/.

Процесс - это некоторый динамический объект, включающий код и данные выполняемой программы, а также набор системных ресурсов ВС, используемых в процессе выполнения программы. Другими словами, процесс - это отдельная программа с ее данными, выполняющаяся на последовательном процессоре в ВС /7/.

Поток - более мелкая единица работы, реализуемая внутри процесса, т.е. процесс состоит из нескольких параллельно выполняемых потоков.

Ресурсы ВС - это аппаратные программные средства ВС, выделяемые процессам и потокам для их выполнения. Процессы запрашивают ресурсы, получают и используют их, а затем освобождают и возвращают ОС. Ресурсы могут быть разделяемыми, когда несколько процессов используют их параллельно (псевдопараллельно) или неразделяемыми.

Основными видами ресурсов являются: процессор (точнее процессорное время), оперативная и внешняя память, каналы ввода-вывода и периферийные устройства. Большая часть ресурсов являются разделяемыми, но некоторые, например принтер, относятся к неразделяемым.

Важным видом ресурсов являются системные программные модули и объекты для организации синхронизации процессов и потоков (семафоры и мониторы), обеспечения их взаимодействия (почтовые ящики, конвейеры и очереди сообщений), контроля взаимных блокировок и тупиков /1,7,8,10/.

Наконец, имеются информационные ресурсы, в качестве которых выступают данные. Информационные ресурсы могут существовать, например, в виде файлов или же в виде переменных, находящихся в оперативной памяти. Если же процессы используют данные только для чтения, такие информационные ресурсы можно разделять, в противном случае работу с данными надо специальным образом организовывать.

Мультипрограммный способ реализует две концепции организации мультизадачности - мультипроцессность и мультипоточность, т.е. задачи могут быть организованы как процессы и как потоки. Рассмотрим принципиальные отличия в организации задач как процессов и как потоков.

Если задачи независимы, их целесообразно организовывать как процессы. ОС считает процессы совершенно несвязанными, у каждого процесса есть свое виртуальное адресное пространство, каждому процессу выделяются свои ресурсы - каналы ввода-вывода, файлы, семафоры и т.д. Каждый процесс выполняется как бы на отдельной виртуальной машине. Такая обособленность нужна для того, чтобы защитить один процесс от другого, поскольку они, совместно используя все ресурсы ВС, конкурируют друг с другом за доступ к ресурсам. Средства защиты ОС обеспечивают невмешательство одного вычислительного процесса в другой вычислительный процесс, в противном случае ВС не будет надежной. С другой стороны, взаимная изоляция и защищенность процессов затрудняет (в частности замедляет) передачу каких бы то ни было данных между процессами.

Если некоторые задачи зависимы и активно взаимодействуют при работе ВС, то их целесообразно организовывать как потоки. Существует множество таких ситуаций, например результаты вычислений одной задачи требуются для начала и продолжения работы другой. Группы же взаимосвязанных задач, организованных как потоки, далее оформляются как процессы. Потоки, относящиеся к одному процессу, используют одни и те же ресурсы, выполняются в одном и том же виртуальном адресном пространстве, поэтому между ними легко организовать взаимодействие, в отличие от процессов, для которых нужны специальные средства для обмена сообщениями и данными. Потоки одного процесса используют общий набор открытых файлов, устройств ввода-вывода, семафоров и т.п. Собственными для потоков являются программный счетчик, стек, регистры процессора, потоки-потомки. Параллельная работа потоков в процессе позволяет быстрее выполнять его, но, с другой стороны, между потоками нет полной защиты, что снижает надежность мультипоточной системы.

При манипулировании с задачами-процессами нужно учитывать все ресурсы, закрепленные за каждой из них. При манипулировании с задачами-потоками нужно менять только контекст задачи, если производится переключение с одной задачи на другую в рамках одного процесса. Для хранения контекста задачи имеется специальный сегмент состояния задачи - Task State Segment (TSS), в котором при переключении с задачи на задачу автоматически сохраняется содержимое регистров процессора. На местоположение TSS в процессорах с архитектурой i32 указывает специальный регистр - Task Register (TR).

Таким образом, мультипрограммный способ предполагает, что ОС организует параллельное выполнение нескольких вычислительных процессов на одном компьютере, причем каждый из процессов в свою очередь может «расщепляться» на несколько параллельно выполняемых потоков.

Для того, чтобы ОС могла управлять процессами, на каждый из них заводится специальная информационная структура, называемая дескриптором процесса (описателем задачи). Дескриптор процесса содержит следующую информацию:

идентификатор процесса (Process Identifier, PID);

тип процесса;

приоритет процесса;

переменную состояния, которая определяет состояние процесса (ожидание, готовность, выполнение);

контекст задачи - область памяти или адрес такой области, в которой хранятся текущие значения регистров процессора, когда процесс прерывается, не закончив работы;

информация о ресурсах, которыми процесс владеет или имеет право пользоваться;

указатель на место и его адрес для организации общения с другими процессами;

параметры времени запуска.

Упражнение 2.1. Осуществить просмотр и анализ текущего количества дескрипторов процессов и потоков для Windows 2000/XP.

Для этого следует нажать одновременно комбинацию клавиш Ctrl+Shift+Esc и открыть окно «Диспетчер задач». На вкладке «Быстродействие» этой программы в поле «Всего дескрипторов» указано их число. Определить количество дескрипторов для управления потоками, число вычислительных процессов и их назначение.

2.2 Состояния потоков

В мультипрограммной системе поток может находиться в одном из трех основных состояний /1/:

выполнение (running) - активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно управляется процессором;

ожидание (waiting) - пассивное состояние потока, находясь в котором поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса);

готовность (ready) - также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему событием (имеет все требуемые для него ресурсы, готов выполняться, однако процессор занят выполнением другого потока).

В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе.

Размещено на http://www.allbest.ru

Типичный граф состояний потока изображен на рис.2.1.

Только что созданный поток находится в состоянии готовности, он готов к выполнению и стоит в очереди к процессору. Когда в результате планирования ОС принимает решение об активации данного потока, он переходит в состояние выполнения и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ожидания какого-либо события, либо будет принудительно вытеснен из процессора, например, вследствие исчерпания отведенного данному потоку кванта процессорного времени. В последнем случае поток возвращается в состояние готовности. В это же состояние поток переходит из состояния ожидания, после того как ожидаемое событие произойдет. В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности - несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки дескрипторов (описателей) отдельных потоков. Таким образом, каждый описатель потока обязательно содержит по крайней мере один указатель на другой описатель, соседствующий с ним в очереди. Очевидно, что движущей силой, меняющей состояния потоков, являются события, среди которых одними из основных являются прерывания.

Примечание. Взаимодействие введенных выше понятий (процесс, поток, ресурсы, состояния) можно пояснить следующей жизненной аналогией. Положим, студентка на кухне по рецептам готовит обед из нескольких блюд. На кухне есть плита с одной газовой горелкой, различные приспособления для приготовления продуктов (миксер, мясорубка, овощерезка, посуда, ножи и т.д.) и собственно продукты. Тогда кухня со студенткой, тексты рецептов, плита, набор приспособлений и продукты - это однопроцессорный компьютер, а приготовление обеда - процесс. Плита, набор кухонных приспособлений, продукты - это ресурсы компьютера, где плита - главный ресурс - процессор, кухонные приспособления - внешние устройства и устройства ввода-вывода компьютера, а продукты - данные для обработки. Рецепты приготовления отдельных блюд обеда - это выполняемые программы, а собственно студентка - это операционная система, управляющая компьютером. Приготовление отдельных блюд обеда - это параллельно выполняющиеся потоки одного процесса, которые разделяют ресурсы (плиту, кухонные принадлежности, продукты). Отдельные блюда (потоки) могут находиться на плите (выполняться), ждать своей очереди у плиты (быть в состоянии готовности) или ожидать каких-либо действий, например добавления определенных продуктов по рецептам. Эти действия могут производиться по сигналам таймера - аналогов сигналов прерываний.

Если студентка по просьбе друзей готовит на кухне одновременно несколько разных обедов - это аналогия выполнения однопроцессорным компьютером группы процессов, изолированных друг от друга (вкусы друзей могут не совпадать). Очевидно, что наличие на кухне нескольких плит - это аналогия мультипроцессорного компьютера - позволяет приготовить несколько обедов или один обед существенно быстрее.

В ряде ОС, например Windows 2000, вводят некоторые дополнительные состояния потоков /11/:

инициализирован (initialized) - в это состояние поток входит в процессе своего создания;

завершен (terminated) - в это состояние поток переходит, заканчивая свое выполнение;

простаивает (standby) - это промежуточное состояние между готовностью и выполнением.

3. ОСНОВЫ ОРГАНИЗАЦИИ ПЛАНИРОВАНИЯ И ДИСПЕТЧЕРИЗАЦИИ ПРОЦЕССОВ И ПОТОКОВ

3.1 Принципы планирования процессов и потоков

Переход от одного потока к другому осуществляется в результате планирования и диспетчеризации. Работа по определению того, в какой момент необходимо прервать выполнение текущего активного потока и какому потоку предоставить возможность выполняться, называется планированием. Планирование реализуется компонентой ОС, называемой планировщиком (scheduler).

Планирование потоков осуществляется на основе информации, хранящейся в описателях (дескрипторах) процессов и потоков. При планировании могут приниматься во внимание приоритет потоков, время их ожидания в очереди, накопленное время выполнения, интенсивность обращений к вводу-выводу и другие факторы. ОС планирует выполнение потоков независимо от того, принадлежат ли они одному или разным процессам. Так, например, после выполнения потока некоторого процесса ОС может выбрать для выполнения другой поток того же процесса или же назначить к выполнению поток другого процесса. Планирование потоков по существу включает в себя решение двух задач /1/:

1) определение момента времени для смены текущего активного потока;

2) выбор для выполнения потока из очереди готовых потоков.

Существует множество различных алгоритмов планирования потоков, по-своему решающих каждую из приведенных выше задач. Алгоритмы планирования (иногда их называют дисциплины диспетчеризации) могут преследовать различные цели и обеспечивать разное качество мультипрограммирования.

Например, в одном случае выбирается такой алгоритм планирования, при котором гарантируется, что ни один поток/процесс не будет занимать процессор дольше определенного времени, в другом случае целью является максимально быстрое выполнение «коротких» задач, а в третьем случае - преимущественное право занять процессор получают потоки интерактивных приложений. Именно особенности реализации планирования потоков в наибольшей степени определяют специфику операционной системы, в частности, является ли она системой пакетной обработки, системой разделения времени или системой реального времени.

В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации. ОС работает в условиях неопределенности - потоки и процессы появляются в случайные моменты времени и также непредсказуемо завершаются. Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси. Для того чтобы оперативно найти в условиях такой неопределенности оптимальный порядок выполнения задач, ОС должна затрачивать значительные ресурсы.

Другой тип планирования - статический (off-line) - может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например в системах реального времени. Планировщик называется статическим (или предварительным планировщиком), если он принимает решения о планировании не во время работы системы, а заранее.

Соотношение между статическим и динамическим планировщиками аналогично соотношению между диспетчером железной дороги, который пропускает поезда строго по предварительно составленному расписанию, и регулировщиком на перекрестке автомобильных дорог, не оснащенном светофорами, который решает, какую машину остановить, а какую пропустить, в зависимости от ситуации на перекрестке.

Результатом работы статического планировщика является таблица, называемая расписанием, в которой указывается, какому процессу/потоку, когда и на какое время должен быть предоставлен процессор. Для построения расписания планировщику нужны как можно более полные предварительные знания о характеристиках набора задач, например о максимальном времени выполнения каждой задачи, ограничениях предшествования, ограничениях по взаимному исключению, предельным срокам и т.д.

После того как расписание готово, оно может использоваться ОС для переключения потоков и процессов. При этом накладные расходы ОС на исполнения расписания оказываются значительно меньшими, чем при динамическом планировании, и сводятся лишь к диспетчеризации потоков/процессов.

Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статического) решения, то есть в переключении процессора с одного потока на другой. Прежде чем прервать выполнение потока, ОС запоминает его контекст, с тем чтобы впоследствии использовать эту информацию для последующего возобновления выполнения данного потока. Контекст отражает, во-первых, состояние аппаратуры компьютера в момент прерывания потока: значение счетчика команд, содержимое регистров общего назначения, режим работы процессора, флаги, маски прерываний и другие параметры. Во-вторых, контекст содержит параметры операционной среды, а именно ссылки на открытые файлы, данные о незавершенных операциях ввода-вывода, коды ошибок, выполняемых данным потоком системных вызовов и т.д. Процесс диспетчеризации осуществляется диспетчером (dispatcher) ОС.

Диспетчеризация сводится к следующему:

1)сохранению контекста текущего потока, который требуется сменить;

2)загрузке контекста нового потока, выбранного в результате планирования;

3)запуску нового потока на выполнение.

Поскольку операция переключения контекстов существенно влияет на производительность ВС, программные модели ОС выполняют диспетчеризацию потоков совместно с аппаратными средствами процессора.

3.2 Классификация алгоритмов планирования (вытесняющие и невытесняющие, бесприоритетные и приоритетные алгоритмы)

С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие алгоритмы планирования /1,7,8,10/.

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.

Вытесняющие (preemptive) алгоритмы - это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается ОС, а не активной задачей.

Основным различием между вытесняющими и невытесняющими алгоритмами является степень централизации механизма планирования потоков. При вытесняющем мультипрограммировании функции планирования потоков целиком сосредоточены в операционной системе и программист разрабатывает свое приложение, не заботясь о том, что оно будет выполняться одновременно с другими задачами. При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения активного потока, запоминает его контекст, выбирает из очереди готовых потоков следующий, запускает новый поток на выполнение, загружая его контекст.

При невытесняющем мультипрограммировании механизм планирования распределен между ОС и прикладными программами. Прикладная программа, получив управление от ОС, сама определяет момент завершения очередного цикла своего выполнения и только затем передает управление ОС с помощью какого-либо системного вызова. ОС формирует очереди потоков и выбирает в соответствии с некоторым правилом (например с учетом приоритетов) следующий поток на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков приложений.

Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, допустим на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме.

Поэтому разработчики приложений для операционной среды с невытесняющей многозадачностью вынуждены, возлагая на себя часть функций планировщика, создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам. Для этого в программе должны быть предусмотрены частые передачи управления ОС. Крайним проявлением «недружественности» приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм имеет возможность снять зависшую задачу с выполнения.

Однако распределение функций планирования потоков между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложения самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент возвращения управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко решаются проблемы совместного использования данных: задача во время каждого цикла выполнения использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит данные. Существенным преимуществом невытесняющего планирования является более высокая скорость переключения с потока на поток.

В большинстве современных ОС, например Windows 2000/XP, используются вытесняющие алгоритмы планирования/11/.

Далее среди множества алгоритмов планирования выделяются два больших класса - бесприоритетные и приоритетные алгоритмы (рис.3.1) /7,8,12/.

При бесприоритетном планировании выбор процессов или потоков производится в соответствии с некоторым заранее установленным порядком без учета их относительной важности и времени обслуживания.

При реализации приоритетных дисциплин обслуживания отдельным процессам и потокам предоставляется преимущественное право перейти в состояние выполнения в соответствии с установленными для них приоритетами. Приоритеты могут быть фиксированными (постоянными) и динамическими (изменяемыми в ходе вычислительного процесса), что, конечно, требует дополнительных ресурсов ВС на вычисление приоритетов и усложняет ОС.

Размещено на http://www.allbest.ru

Рассмотрим кратко некоторые наиболее часто используемые алгоритмы планирования.

3.3 Линейные алгоритмы планирования

Эти алгоритмы планирования реализуют выполнение процессов и потоков в порядке очереди, которая организуется согласно тем или иным соглашениям/7,8,12/.

Самой простой в реализации является дисциплина обслуживания, при которой процессы и потоки выполняются в порядке их появления в ВС. Этот алгоритм называется «первым пришел - первым обслужен» или FCFS (First come - First Served). Те процессы и потоки, которые были заблокированы в процессе выполнения, после перехода в состояние готовности вновь ставятся в очередь готовности. При этом возможны два варианта.

В первом наиболее простом варианте разблокированный процесс или поток ставится в конец очереди готовых процессов и потоков.

Во втором варианте планировщик помещает разблокированный процесс или поток перед теми процессами или потоками, которые еще не выполнялись. Таким образом, образуются две очереди: одна очередь образуется из новых процессов или потоков, а вторая очередь - из ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать стратегию обслуживания «заканчивать выполнение процессов или потоков в порядке их появления». Рассмотренный алгоритм относится к невытесняющим.