Афонин П.Н. Информационные таможенные технологии

Подождите немного. Документ загружается.

Распараллеливание ускоряет выполнение процесса за счет отсутствия

переключения О С с одного адресного пространства на другое, котор ое имеет

место при выполнении процессов. Программы становятся более логичны.

Особый эффект при этом достигается в мультипроцессорных системах.

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

запросов MS SQL Server.

С понятиями процесс и поток тесно связано понятие

мультипрограммирования. Мультипрограммирование, или многозадачность

(multitasking) – это способ организации вычислительного процесса, при

котором на одном процессоре попеременно выполняются сразу несколько

задач (программ).

Общие критерии эффективности мультипрограммирования:

• пропускная способность;

• удобство работы пользователей;

• реактивность системы (заданные интервалы времени).

В зависимости от критерия различают:

• системы пакетной обработки;

• разделения времени;

• системы реального времени.

Мультипрограммирование в системах пакетной обработки. Главная

цель мультипрограммирования такого вида: минимизация простоев всех

устройств компьютера. Это , как правило, задачи вычислительног о

характера. Оператор формирует пакет заданий и вводит его тем или иным

способом во внеш нюю память. ОС выбирает из пакета мультипрограммную

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

В этом режиме невозможно гарантировать выполнение задачи в

течении определенного времени. Мультипрограммирование организованно

за счет параллельной работы канала или контроллера и процессора.

Переключение процессора с одной задачи на другую – инициатива

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

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

Мультипрограммирование в системах разделения времени.

Основной критерий систем разделения времени – организация

интерактивной работы пользователей с несколькими приложениями.

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

задаче неко торого, достаточно небольшого отрезка времени – кванта. По

завершению кванта задачи принудительно п рио станавл ивается и в

соответствии с заложенн ым алгоритмом, выбирается на выполнение новая

задача.

Системы разделения времени имеют меньшую пропускную

способность по сравнению с системами пакетной обр аботки при прочи х

равных условиях. Это обусловлено потерей времени на переключение

процессора с задачи на задачу.

ОС MS Windows 98/NT/2000/XP, Unix являются примерами систем

разделения времени.

Мультипрограммирование в системах реального времени. ОС

реального времени используются при управлении техническими объектами

или технологическими процессами. Их особенностью является наличие

предельного времени в течении которого должна быть выполнена та или

иная задача.

Мультипрограммная смесь (набор одновременно выполняемых задач)

представляет собой фиксированный набор заранее разработанных программ,

переключение которых осуществляется по прерываниям или по расписанию.

Для систем реального времени важна скорость обработки прерываний.

Задача максимальной загрузки устройств – не актуальна.

Мультипрограммирование на основе прерываний. Прерывание –

это способ переключения процессора на выполнен ие потока команд,

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

Различают внешние (аппаратные), внутренние и программные

прерывания.

Внешние прерывания происходят асинхронно, то есть происходят в

случайный момент времени в процессе выполнения программы (например, от

внешних устройств), внутренние – синхронно, т.е. возникают по конкретной

причине и можно предугадать возникновение такого прерывания (например,

при делении на ноль).

Программные прерывания не являются "истинными" прерываниями.

Они возникают при выполнении определенной команды процессора и

применяются в том случае, когда необходимо выполнить некоторые

привилегированные действия (например, обратится к порту компьютера).

Прерываниям равного значения приписываются уровни приоритетов (уровни

– IRQ). Кажд ое из прерываний обс луж ив ает ся о бра бот чик ом прерываний

(Interrupt Service Routine).

Внешние прерывания – обрабатываются драйверами, внутренние –

модулями ядра, а программные – процедурами из API.

1.2.4. Мультипроцессорная обработка

Мультипроцессорная обработка – это способ организации

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

отличие от организации мультипрограммирования на одном процессоре,

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

выполнение нескольких процессов. Это приводит к усложнению всех

алгоритмов ОС.

Симметричная архитектура предполагает однородность всех

процессоров и единообразное их включение в общую схему. Традиционно

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

одном корпусе.

При асимметричной архитектуре процессоры могут отличаться

своими техническими характеристиками и функционал ьной ролью.

Требование единого корпуса отсутствует. Система может состоять из

нескольких корпусов (в каждом может быть один или несколько

процессоров). Такие устройства называются кластерами.

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

строиться симметричным образом (все процессоры р авноп равн ы) или

асимметричным (процессоры различаются функционально). Для

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

организации.

В мультипроцессорных компьютерах имеется несколько процессоров,

каждый из которых мож ет относительно независимо от остальных выполнять

свою про грамм у. В мульти проц ессоре существует общая для всех

процессоров операционная система, которая оперативно распределяет

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

отдельными процессорами организуется наиболее простым способом – через

общую оперативную память.

Сам по себе процессорный блок не является законченным

компьютером и поэтому не может выполнять программы без остальных

блоков мультипроцессорного компьютера – памяти и периферийных

устройств. Все периферийные устройства являются для всех процессоров

мультипроцессорной системы общими. Территориальную распределённость

мультипроцессор не поддер жи вает – все его блоки располагаются в одном

или насколько близко расположенных конструктивах, как и у обычн ого

компьютера.

Основное достоинство мультипроцессора – высокая

производительность, которая достигается за счет параллельной или

конвейерной работы нескольких процессоров. Так как при наличии общей

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

мультипроцессоры могут эффективно выполнять даже приложения с

высокой степенью связи по данным.

Еще одним важным свойством мультипроцессорных систем является

отказоустойчивость, то есть способность к продолжению работы при отказах

некоторых элементов, например процессоров или блоков памяти. При этом

производительность, естественно, снижается, но не до нуля, как в обычных

системах, в которых отсутствует избыточность.

Параллельная обработка. Необходимость параллельной обработки

может возникнуть, когда требуется уменьшить время решения данной

задачи, увеличить пропускную способность, улучшить использован ие

системы.

Для распараллеливания необходимо соответствующим образом

организовать вычисления. Сюда входит следую щее:

• составление параллельных программ, то есть отображение в явной

форме параллельной обработки с помощью надлежащих конструкций

языка, ориентированного на параллельные вычисления;

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

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

выявлена явная или скрытая параллельная обработка. П оследняя

должна быть преобразована в явную.

Рассмотрим граф, описывающий последовательность процессов

большой программы, представленный на рис. 3. Видно, что вы полнени е

процесса P

не может начаться до завершения процессов Р

и Р

и, в свою

очередь, выполнение процессов Р

и Р

не может начаться до завершения

процесса Р

В данном случае для выполнения программы достаточно трех

процессоров.

Ускорение обработки на мультипроцессоре определяется отношением

времени однопроцессорной обработки к времени многопроцессорной

обработки:

U =

Рис. 1.3. Граф выполнения большой программы

Конвейерная обработка улучшает использование аппаратных

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

ресурсы заранее предусмотренным способом. Хорошим примером

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

на котором изделие последовательно проходит все стадии вплоть до готового

продукта. П реимущество этого способа состоит в том , что каж дое изделие

вдоль своего пути использует одни и те же ресурсы, и как только некоторый

ресурс освобождается данным изделием , он сразу же может быть

использован следующим изделием, не ожидая, пока предыдущее изделие

достигнет конца сборочной линии. Если транспортер несет аналогичные, но

не тождественные изделия, то это последовательный конвейер; если же все

изделия одинаковы, то это векторный конвейер.

Последовательные конвейеры. На рис. 1.4, а показано устройство

обработки команд, в котором имеется четыре ступени: выборка команды из

памяти, декодирование, определение адреса и выборка операнда,

исполнение.

Ускорение обработки в данном устройстве измеряется отношением

времени T

, необходимого для последо в ате л ьн о го выпо л н ен и я L заданий (то

есть выполнения L циклов на одной обрабатывающей ступени), ко времени

вы полнения той же обработки на конвейере. Обозначим через t

время

обработки на 1-й ступени, а через t

– соответствующее время для самой

медленной ступени (рис. 4, б). Тогда если L заданий (команд) п ро ходят через

конвейер с п ступенями, то эффективность конвейера определяется

следующим выражением:

( )

tLt

−+

∑

для

1−+

→=

Рис. 4. Четырехступенное устройство обработки команд:

а – ступени конвейера; б – временная диаграмма работы

Векторные конвейеры. В них создается множество функциональных

элементов, каждый из которых выполняет определенную операцию с парой

операндов, принадлежащих двум разным векторам. Эти пары подаются на

функциональное устройство и со всеми элементами пар векторов

функциональные преобразования проводят одновременно. Для

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

векторные регистры, на которых собираются подлежащие обработке

векторы.

Типичное использование векторного конвейера – это процесс,

вырабатывающий по двум исходным векторам А и В результирующий вектор

С для арифмети ческой операции С

←

А+В. В этом случае на конвейер

поступает множество одинаковых команд.

Классификация архитектур многопроцессорных систем.

Мультипроцессоры, ориентированные на достижение сверхбольших

скоростей работы, могут содержать по нескольку сравнительно простых

процессоров с упрощенными блоками управления.

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

Флина, которая строи тся по признаку одинарности или множественности

потоков команд и данных.

Структура ОКОД (один поток команд, один поток данных) –

однопроцессорная ЭВМ (рис. 1.5).

Рис. 1.5. Структура ОКОД

Рис. 1.6. Структура ОКМД

Структура ОКМД (один пот ок команд, много потоков данных) –

матричная многопроцессорная структура. Система содержит некоторое число

одинаковых сравнительно пр остых быстродействующих процессоров,

соединенных друг с другом и с памятью данных регулярным образом так, что

образуется сетка (матрица), в узлах которой размещаются процессоры (рис.

1.6). Здесь возникает сложная задача распараллеливания алгоритмов

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

вопросы лучше решаются в конвейерной системе.

Структура МКОД (много потоков команд, один поток данных) –

конвейерная многопроцессорная структура (рис. 1.7). Система имеет

регулярную структуру в виде цепочки последовательно соединенных

процессоров, так что инф ормация на выходе одного процессора является

входной информацией для следующего в конвейерной цепочке.

Процессоры образуют конвейер, на вход которого одинарный поток

данных доставляет операнды из памяти. Кажды й процессор обр абатывает

соответствующую часть задачи, передавая результаты соответствующему

процессору, который использует их в качестве исходных данных. Таким

образом, решение задач для некоторых ис ходны х данных развертывается

последовательно в конвейерной ц епочке. Это обеспечивает подведение к

каждому процессору своего потока команд, то есть имеется множественный

поток команд.

Структура МКМД (много потоков команд, много потоков данных)

представлена на рис. 1.8.

Рис. 1.7. Структура МКОД

Рис. 1.8. Структура МКМД

Существует несколько типов МКМД. К ним относятся:

мультипроцессорные, системы, системы с мультиобр аботкой ,

многомашинные системы, компьютерные сети.

1.2.5. Управление памятью

Оперативная память, или ОЗУ играет особую роль. Это обусловлено

тем, что программа может выполнятся только в том случае если он а

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

системными программами ОС.

Функции ОС по управлению памятью. К основным функциям ОС по

управлению памятью относятся:

• учет свободной и занятой памяти;

• выделение памяти процессам и ee освобождение;

• вытеснение кодов и данных процессов на диск, когда памяти не

хватает и возврат на место;

• настройка адресов на конкретную область физической памяти;

• дефрагментация;

• защита памяти.

Типы адресов. Для идентификации команд программы и данных

используются адреса. Адреса подразделяются на следующие виды:

• символьные имена (присваивает программист, наприме р ме тки );

• виртуальные адреса (формирует транслятор, начальный адрес равен

0);

• физические адреса – номера ячеек памяти, где в действительности

будут расположены команды и данные.

Совокупность виртуальных адресов составляет виртуальное адресное

пространство (ВАП). Виртуальное ад рес ное пространство опр еде ляется

разрядностью компьютера. Для 32-разрядного Intel Pentium – это максимум

FFFFFFFF, что составляет 4 Гб.

Существует два основных типа представления виртуальных адресов:

• линейное – адрес начала ВАП всегда равен нулю;

• деление на сегменты, при котором адрес – это пара чисел (n, m), где n

– номер сегмента, m – смещение;

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

Его также называют образом процесса. Назначенное ВАП может превышать

физический объем памяти. На этом основан механизм виртуальной памяти.

ВАП и виртуальная память – это разные механизмы для ОС. ОС может

поддерживать ВАП, но механизм виртуальной памяти может при этом

отсутствовать, например, в случае превыш ения физической памяти над ВАП

любого процесса.

Алгоритмы распределения памяти без использования внешней

памяти

При распределении памяти фиксированными разделами память

изначально разделена на сегменты фиксированной величины.

При распределении памяти динамическими разделами память в

начальный момент времени считается свободной (за исключением памяти

отведенной под ОС). Каждому процессу отводится вся необходимая память.

Если ее не хватает, то процесс не создается. В произвольный момент времени

память представляет собой случайную последовательность занятых и

свободных у частков. Достоинство данного вида распределения памяти −

большая гибкость, по сравнению с методом распределения фиксированными

разделами. Недостаток – высокий уровень фрагментации.

В методе распределения памяти перемещаемыми разделами

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

Например, для борьбы с фрагментацией применяется дефрагментация –

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

Такой метод был применен в ранних версиях OS/2. Недостаток этого метода

– низкая производительность.

Алгоритмы распределения памяти с использовани ем внешней

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

интерактивных задач. Все они должны быть размещены в памяти, большая

часть которых находится в состоянии ожидания. Логично было бы на время

ожидания, в случае нехватки ф изической памяти, в ытеснять их на диск, а

когда необходимо, возвращать в п амять. Такая подм ена (виртуализация)

оперативной памяти дисковой памятью существенно повышает уро вень

мультипрограммирования. Важно, что все действия по перемещению

происходят автоматически, без участия программиста.

Для виртуализации применяются два основных подхода: Свопинг – образ

процесса выгруж ается на диск и возвращается в память целиком. Свопинг

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

выгружается на диск и возвращается в память частями (сегментами,

страницами).

Реализация виртуальной памяти, представлена тремя классами:

страничное распределение, сегментное, сегментно-страничное

распределение.

Страничное распределение. При страничном распределении

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

данной си стемы размера, называемыми виртуальны ми страницами. Вся

оперативная память также делится на части такого же размера, называемые

физическими страницами.

При страничном распределении виртуальное адресное пространство

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

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

исходные данные. Такой подход не позволяет обеспечить раздельную

обработку, например защиту, совместный доступ и т.д.

Сегментное распределение. Разбиение адресного пространства на

"осмысленные" части устраняет недостатки страничного распределения и

называется сегментным распределением. Пример ы сегментов: код

программы, массив исходных данных и пр.

К недостаткам сегментного распределения можно отнести следующие:

1. Использование операции сложения при формировании ф изическ ого

адреса приводит к понижению произв одительн ости.

2. Избыточность. Поскольку сегмент в общем случае может быть

больше страницы , то следовательно единица обмена между ОЗУ и диском

более крупная, что приводит к замедлению работы.

Сегментно-страничное распределение. Данный метод представляет

собой комбинацию стран ичного и сегментного механизмов управления

памятью и направлен на реализацию достоинств обоих подходов.

Виртуальная память делится на сегменты, а каждый сегмент – на страницы.

Все современные ОС используют именно такой способ организации.

1.2.6. Кэш-память

Кэш-память (cache) – это способ совместного функционирован ия двух

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

динамического копирования часто используемой информации из

“медленного” в “быстрое” запоминающее устройство (ЗУ).

Функционирование кэш происходит незаметно для програм м и

пользователей.

Принцип действия кэш-памяти представлен на рис. 9.

Рис. 1.9. Принцип действия кэш-памяти

Как видно из рис. 1.9 запись в кэш выполняется при чтении, в том

случае, если эти данные в кэш отсутству ют. Если же в кэш данные есть, то

обращение к основной памяти не происходит, и в этом случае они

считываются из кэш.

Содержание кэш-памяти представляет собой совокупность записей о

всех данных из основной памяти (ОП), загруженных в нее (рис. 10).

Рис. 1.10. Содержание кэш-памяти.

Время доступа пропорционально вероятности попадания в кэш,

которая составляет не менее 90%. Такая высокая степень попадания в кэш

объясняется некоторыми объективными свойствами компьютерных данных:

Временная локальность. Если произошло обращение по некоторому

адресу, то следующее обращение с больш ой вероятностью произойдет в

ближайшее время. Временная локальность позволяет надеяться, что имеет

смысл копировать данные в кэш, т.к. вско ре вероятно все равно к ним будет

обращение.

Пространственная локальность. Если произошло обращение по

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

произойдет обращение к соседним адресам. Свойство пространственной

локальности делает целесообразным копировать в кэш не одну единицу

данных, а целый блок данных. Алгоритм действия кэш-памяти представлен

на рис. 1.11.

Рис. 1.11. Алгоритм действия кэш-памяти

Проблема согласования данных. Две копии данных: в памяти и кэше

порождает проблему согласования, то есть версии данн ых в п амяти и кэш е в