Свойства и классификация процессов

Свойства и классификация процессов

По динамическим свойствам процессы разделяются:

- реального времени (для них необходимо обеспечивать завершение к определённому времени)

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

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

По варианту организации процессов:

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

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

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

- порождающий (родительский)

- порождённый (дочерний)

По результатам работы:

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

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

Если у тождественных процессов совпадают трассы, то они считаются равными.

В остальных случаях процессы различные.

По взаимодействию

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

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

Если на выбранном участке времени существуют оба процесса, то они считаются параллельными.

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

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

Если между процессами установлена информационная связь, то они считаются взаимосвязывающими.

Если процессы используют одни и те же ресурсы, то они считаются конкурирующими.

 

Свойства и классификация ресурсов. Потребляемые и восстанавливаемые ресурсы

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

Схема работы:

- запрос

- использование

- освобождение

Если состояние ресурса не сохранится после использования процессом, то такой ресурс — потребляемый.

Схема работы:

- освобождение (создание ресурса)

- запрос

- использование

 

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

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

В каждом конкретном случае синхронизация задаётся с помощью синхронных правил. Реализация синхронизирующих правил осуществляется с помощью механизмов синхронизации.

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

Задача взаимного исключения

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

1) Одновременно внутри критической области должно находиться не более одного процесса

2) Критическая область параллельных процессов не должны иметь приоритетов относительно друг друга

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

4) Решение о вхождении процессов в их критическую область при одинаковом времени поступления запросов и равенства приоритетов не должно откладываться и является конечным.

5) Относительная скорость развития процессов независимо от производной

6) Любой процесс может переходить в любое состояние вне пределов своей критической области.

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

Решение задачи взаимного исключения:

В языке предоставлены некоторые вещи для решения задачи взаимного исключения: любой объект, метод или участок кода может быть объявлен со спецификатором synchronized. Участок кода, выделенный таким образом всегда выполняется, по отношению к другим потокам, в режиме взаимного исключения, т. е. Если этот участок вызван потом из потока ни в одном другом потоке этот участок выполняться не будет до момента выхода из него первого потока. Для синхронизации потоков так же можно использовать синхронизирующие операторы, например для метода или объекта можно использовать методы wait() и notify(). Так же могут использоваться семафоры.

Типовые задачи синхронизации. Производитель-потребитель

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

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

 

Типовые задачи синхронизации. Читатели и писатели

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

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

 

Механизмы синхронизации. Использование механизма прерываний

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

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

Такое решение не эффективно, т. к. всё сводится к однозадачному решению.

Указанного недостатка лишена двуступенчатая схема.

 

Событийные переменные в java.

 

Семафоры в java.

Семафор со счетчиком позволяет n задачам одновременно обращаться к ресурсу. Можно считать, что семафор «выдает разрешение» на использование ресурса, хотя никаких реальных объектов в этой схеме нет. Класс Semaphore содержится в библиотеке java.concurrent. Объект класса Semaphore в java имеет метод acquire() для закрытия и release() для открытия. При создании объекта семафора конструктору класса передается целое значение — начальное состояние семафора и логическое значение, определяющее будут ли потоки выполняться в порядке очереди, или в произвольном порядке.

Организация подзадач в Win

Win 32: Create Thread

Delphi/C Builder function: Begin Thread

Deplhi/C Builder Class: Tthread

Организация подзадач в ОС Windows возможна на 3 уровнях:

1) Базовый — непосредственное использование средств ОС

2) Подразумевает использование низкоуровневых средств, встроенных в системы программирования

3) Использование специализированных классов

Рассмотрим организацию подзадач осуществляется вызовом функции Begin Thread.

Sa — указатель на запись, описывающий права доступа, имеет смысл знач. NiL

stacksize размер стека, выделяемой подзад. (0 по умолчанию)

Thread Function — указатель на функцию потока содерж. Ссылку на функцию, кот. Выполн-ся в рамках подзадачи

р — указатель на область памяти, содержащий параметры функции потока

creationFlag1 — режим созд. Подзадач.

1) Создание и запуск

2) Созд. Приост. Передач. Которое нужно старт.

Function Begin Thread(

sa: Pointer;

stacksize: Integer;

ThreadFunction: TthreadFunc;

p: pointer;

creationflag1: Integer;

var Threadld: Integer

): Thadle;

var Threadld: Integer — индикатор создания подзад.

): Функция возвращает дескриптор, созданный подзадачей т. е. Это указатель на ячейку кот. Содержит

Создание подзад. Доступна через дескриптор.

Функция подзадачи:

ThreadFunction: TthreadFunc;

type TthreadFunc = function(parameter: pointer):Integer; // возвращаем результат

Указатель на параметр(параметры)

p: pointer; p-> array(record)

Подзад. Работает до тех пор пока выполняется функция подзадачи

Операции для подзадачи:

function SuspendThread(threadHandle: TthreadID): Dword //приостанавливает

function ResumeThread(threadHandle: TthreadID): Dword //запустить

результат — код ошибки

 

Приоритеты подзадачей Чтобы получить значение текущего приоритета используют функцию get, а что бы установить приоритет — set.

Приоритеты для подзадач являются относительные (± относительно приоритета основной задачи)

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

Стандартный способ завершения если заранее неизвестно кол-во итераций, используется специальный флаг.

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

Окончательное удаление подзадачи из системы осуществляется вызовом фкнции CloseHandle(Handle)

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

Подзадача переходит в сигнализирующее состояние в момент завершения.

Function WaitForSingleObject(

1 параметр — дескриптор

2 параметр: timeout — время в течении которого ожидается сигнал

Handle:Thandle;

dw Milliseconds:LongInt): DWORD;

function WaitForMultipleObject(n

IpHandle: pWOHhandleArray;

dWaitAll: BOOL;

dwMilliseconds: LongInt): DWORD

параметр: 1) ссылка для дескриптора

2)

3) режим ожидания dWaitAll

Мониторы Хоара

Монитор — высокоуровневое языковое средство синхронизации процессов.

Б. Хансен — 1973

С. Хоар — 1974

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

Нотации монитора:

<name>: MONITOR;

begin // В описании локальных данных монитора

var... // h набор процедур монитора Y

procedure <name1> (…);

begin... end;

….

procedure <namen> (…);

begin... end;

В инициализации локальных данных} end

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

Условная переменная М:condition реализует некоторую очередь процессы в которой выполняются при М.WAIT. Если какой-то процесс выполнил примитив M.SIGNAL, то первый процесс из очереди переходит в состояние готовности.

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

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

Соответственно после выхода из монитора процесс, который был в очереди ожидания, передает управление «разбудившему» процессу (кот. Выполнил SIGNAL)

Для реализации монитора:

В составе локальных переменных используется ФЛАГ (двоич. Перем.), которая означает есть или нет шифрование (0-пусто, 1-инф. Занес.)

DATA:monitor;

BEGIN

var БАЗА<данные>

флаг:0...1

непуст, пусто: condition

и 2 условные переменные для организации очереди ожидания.

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

Реализация монитора:

Любое высокоуровневое средство синхронизации при взаимодействии процессов может быть построено с помощью низкуровневых средств.

Рассмотрим реализацию монитора с использованием семафора:

1. Если в состав монитора входит n процедур m-условных переменных и k-локальных переменных. Потребуется: один двоичный семафор для реализации взаимного исключения. Начальное значение одно.

2. Один двоичный семафор для решения задачи сигнализации (SIGM)

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

Если имеется очередь условной переменной сигнализирующий процесс должен разбудить 1 процесс из этой очереди и передать ему право входа в монитор. Уступающий — должен перейти в состояние ожидания. Для этого сигнализаций процессора выполняет операцию открытия семафора, а что бы самому остановиться выполнение закрытие этого же семафора соответственно начальному значению семафору = 0. Для учета длины очереди «уступивших процессоров» понадобится перечисление переменных — ПРАВО

3. По одному двоичному семафору на каждый из n условных переменных для организации очередей процессов, остановившихся на операции WAIT.

4. Счетчики для условных переменных (длины очереди)

 

Распределенное программирование. Основные понятия

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

П1 <=> П2

| |

ЛП1 ЛП2

В распределенных системах для построения механизмов синхронизации вместо разделяемых переменных используются средства передачи сообщений. Для поддержки механизма обмена сообщениями узлы распределённой системы «соединяются» с помощью специальных аппаратно-программных средств, называемых каналами. Каналы бывают разные...;)

Передача сообщений:

Обмен сообщениями может быть осуществлён в 2 режимах: синхронная передача сообщений и асинхронная передача сообщений.

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

При асинхронной передаче такое подтверждение не требуется.

Соответственно для отправки сообщения используется примитив SEND, для получения сообщения RECIEVE.

SEND — поддерживает асинхронный режим передачи и является неблокирующим примитивом. Для синхронной передачи применяется SYNCH_SEND.

При блокировке — приостановка процесса.

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

 

Каналы и передача сообщений

Канал

Для описания каналов используется следующая нотация:

chan ch(type1id1,...,typeNidN)

В скобках описываем имена полей и их типы

chan input(char)

chan disk_a(int cyl, int block, int count, char* buf)

chan result[n](int)

Процесс управляет сигналами используя send ch (expr1,...,expr n) //поле сообщ.

Recieve ch (var1,...,varn)

empty(ch)

Так как recieve является блокир. Вводится режим проверки в случае если сообщение в канале отсутствует.

Каналы являются глобальными для всех процессов, тоесть канал можнт и читать и писать данные в V канал.

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

 

Свойства и классификация процессов

По динамическим свойствам процессы разделяются:

- реального времени (для них необходимо обеспечивать завершение к определённому времени)

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

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

По варианту организации процессов:

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

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

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

- порождающий (родительский)

- порождённый (дочерний)

По результатам работы:

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

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

Если у тождественных процессов совпадают трассы, то они считаются равными.

В остальных случаях процессы различные.

По взаимодействию

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

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

Если на выбранном участке времени существуют оба процесса, то они считаются параллельными.

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

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

Если между процессами установлена информационная связь, то они считаются взаимосвязывающими.

Если процессы используют одни и те же ресурсы, то они считаются конкурирующими.