Планировщик процессов
Классические проблемы межпроцессорного взаимодействия.
Проблема обедающих философов.
Проблема состоит в разработке синхронизации философов.
Простое решение:
#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. Невытесняющие алгоритмы не находят для многоцелевых и многопользовательских систем т.к. по определению может предоставить преймущества одному из пользователей случайным образом.