Алгоритм edf (Earliest Deadline First)

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

Процессы	Период, мс	Время работы, мс
A	30	15
B	40	15
C	50	5

Меж процессное взаимодействия Основные понятия

Операции

1. Передача данных

2. Предотвращение конфликта процессов при одновременном обращении к определенному ресурсу.

3. Синхронизация процессов

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

Пример ситуации состязаний:

A		B
считывает значение int 6
		Считывает значение int= 6 Записывает значение in значение 7
Записывает значение in значение 7

	3.txt	curt
	4.txt
in	5.txt
	5.txt
	6.txt
	7.txt

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

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

Условия запретов без состояния состязаний

1. 2 или более процессов не должны находится одновременно в своих критических областях

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

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

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

Взаимное исключение с активным ожиданием

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

Алгоритм строгого чередования

Turn= {0,1}

Алгоритм Петерсона

Реализация исключающей системы с исключающей командой.

Xchg

Res,mem reg mem

Flag dw 0; флаг h сегмент данных: 0- резрешено;=- задано в коде

Mov ax, 1; 1→рег АХ

Retry: xchg ax, flag; ax flas

Cmp ax, 0; ЛХ =0?

Jnz retry ; повторить, есл

Критический объем

Mov flag, 0; 0→flag-реализовать оставшиеся процессы

Примитивы межпроцессного взаимодействия

Sleep()-блокирует текущий процесс

Wakeup(процесс)-разблокирует заданный процесс

Задача: производителя и потребителя:

Производитель:

Потребитель:

Задача: Семафор:

Семафор- некоторая целочисленная переменная над которой определены 2 операции:

P -операция (down())- если значение семафора равно 0, вызвавши процесс блокируется, иначе значение уменьшается на 1, а вызвавший процесс продолжается.

V-операция (up())-если на семафоре имеются заблокированные процессы, то один из них запускается, иначе значение семафора увеличивается на 1.

Любая операция с семафором исполняется как единое непрерывное (атомарное) действие. По этому операции с семафором реализуются с помощью системных вызовов.

Семафор mntex

Down(& mutex);

Критический область

Up(0 mutex)

Пример на Си:

#define N=100

Typedef int semaphore;

Semaphore mutex=1;

Semaphore empty=N

Semaphore empty=0

Void producer(void)

{

Int item;

While(1){

Item=producer.item();

Down(& empty);

Down(& mutex);

put_data(item);

up(& mutex);

up(& ful);

}

}

Void consumer(void)

{

Int item;

While(1){

Dawn(& full);

Down(& mutex);

Intem=get_dta()

Up(& mutex);

Up(& emptu);

}

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

Проблема обедающих философов

Каждый филосов может есть или не есть, но для еды ему нужно 2 вилки.

Проблема читателей и писателей

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

Проблема спящего продабрея

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

Ресурсы и взаимоблокировка

Ресурсы:

• выгружаемые- можно забрать

• не выгружаемые- нельзя забрать

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

Условия, необходимые для взаимоблокировки:

1. Условия взаимного исключении: ресурс либо отдан одному процессу, либо свободен.

2. Условие удержания и ожидания: процесс, удерживающий ресурсы, может ждать дополнительных ресурсов.

3. Условие отсутствия принудительной выгрузки ресурса.

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