Планировщик процессов

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

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

Проблема состоит в разработке синхронизации философов.

Простое решение:

#define №5

void philosoher(int i)

{

while(true)

{

think();

take_fork(i);

take_fork((I+1)%N);

cat();

puttork(i);

put_fork((i+1)%N)

}

}

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

Starvation – зависание.

Правильное решение:

#define №5

#define LEFT (i+N.1)%N

#define RIGHT (i+1)%N

#define THINKING 0

#define HUNGRY 1

#define EATING 2

tepedef int semaphore;

int state[N]; // массив для отслеживания состояния каждого философа.

semaphore mntex;

semaphore S[N];

void philosopher(int i)

{

while(true)

{

think();

take_forks(i);

cat();

puttork(i);

put_forks(i);

}

}

void take_forks(int i)

{

down(&utex);

state[i]=HUNGRY;

test(i);

up(&mutex);

down(&S[i]);

}

void put_forcs(int i)

{

down(&mutex);

state[I]= THINKING;

test(LEFT);

up(&mutex);

}

void test(int i)

{

if(state[i]== HUNGRY && state[LEFT]!= EATING && state[RIGHT]!=[A]Na)

{

state[i]=EATING;

}

}

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

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

typedef int semaphore;

semaphore mytex = 1;

semaphore db = 1;

int rc = 0;

void reader()

{

while(true)

{

down(&mutex);

rc++;

if(rc==1)down(&db);

up(&mutex);

real_data_base();

down(&mutex);

rc--;

if(rc==1)up(&db);

up(&mutex);

use_data_read();

}

}

void writer()

{

while(true)

{

think_up_data();

down(&db);

write_data_base();

up(&db);

}

}

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

Есть несколько подходов:

1. Ограничить количество запросов читателя во временном промежутке.

2. Ввести в алгоритм дополнительные переменные блокировки, сформировав ограничение таким образом: если писатель заблокирован не один читатель не получит доступа.

3. Постановка процессов в очередь с помощью планировщика процессов.

4. Предоставить пишущему процессу более высокий приоритет при этом все читатели будут заблокированы ОС.

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

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

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

#define CHAIRS 5

#define int semaphore;

semaphore customers=0; //очередь

semaphore barbers = 0; //количество спящих брадобреев

semaphore mutex = 1; // управление доступа в критическую секцию

int waiting = 0; // очередь посетителей в очереди

void barber()

{

while(true)

{

down(&customers);

down(&mutex);

waiting--;

up(&burbers);

up(&mutex);

cnt_hair();

}

}

void customers ()

{

down(&mutex);

if(waiting< CHAIRS)

{

waiting++;

up(&customer);

up(&mutex);

down(&borber);

get_haieut();

}

else

up(&mutex);

}

}

Наиболее частая задача планирования это разрешить доступ к процессору одному из активных процессов отвечает за это часть ОС называемая планировщиком, планировщик использует алгоритм планирования, существует несколько алгоритмов планирования. При разработке алгоритмов решается 5 задач:

1. Равноправие – предоставление каждому процессу адекватные доли процессорного времени.

2. поддержка максимальной занятости процессора;

3. Обеспечение быстрой реакции на запросы;

4. Сокращение оборотного времени т.е. сумарного времени на ожидание времени и обработку задачи;

5. Повышение пропускной способности – это повышение количества решаемых задач в единицу времени.

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

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

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

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

Дата добавления: 2013-12-12