Разделение ресурсов
Параллельные процессы - процессы, выполнение (обработка) хотя бы частично перекрывается по времени.
Независимые процессы - процессы, использующие независимое множество ресурсов
Взаимодействующие процессы - процессы, использующие ресурсы совместно. Выполнение одного процесса может повлиять на результат другого.
Разделение ресурса - совместное использование несколькими процессами ресурса ВС.
Критические ресурсы - разделяемые ресурсы, которые должны быть доступны в текущий момент времени только одному процессу.
Критическая секция или критический интервал - часть программы (набор операций), в которой осуществляется работа с критическим ресурсом.
- Race condition (требование мультипрограммирования): Результат выполнения процессов не должен зависеть от порядка переключения выполнения между процессами.
Взаимное исключение
Взаимное исключение - способ работы с разделяемым ресурсом, в котором доступ к разделяемому ресурсу предоставляется только одному процессу одновременно.
- Минусы:
- Deadlock - взаимоблокировка процессов из-за некорректной организации доступа и разделения ресурсов.
- Блокирование - процесс не получает доступ к разделяемому ресурсу из-за активности более приоритетных процессов.
Способы реализации взаимного исключения
- Запрещение прерываний и специальные инструкции
- Алгоритм Петерсона
- Активное ожидание
- Семафоры Дейкстры
- Мониторы Хоара
- Обмен сообщениями
Семафоры Дейксты
Семафоры Дейкстры - формальная модель синхронизации, предложенная голландским учёным Эдсгером В. Дейкстрой.
Это низкоуровневый инструмент. Требует либо аппаратной поддержки (системой команд), либо поддержки операционной системы (может быть нарушена атомарность).
Операции:
Атомарные операции - операции, которые обязаны выполниться, в случае вызова. (Неделимые операции)
Down(S)илиP(S)- Proberen (проверить)- S > 0 -> S -= 1
Up(S)илиV(S)- Verhogen (увеличить)- S += 1
Взаимное исключение двоичным семафором
Двоичный семафор - семафор, максимальное значение которого равно 1.
semaphore S(1);
...
down (S);
// Критическая секция процесса 1
...
up (S);Тоже самое для процесса 2. Когда значение светофора - 0, разделяемый ресурс доступен только закрывшему процессу.
Мониторы Хоара
Мониторы Хоара - совокупность процедур и структур данных, объединённых в программный модуль специального типа.
Инструмент на уровне ЯП или системы программирования - высокоуровневый.
- Особенности:
- Структуры данных монитора доступны только для процедур, входящих в этот монитор.
- Процесс “входит” в монитор по вызову одной из его процедур. (если один процесс зашёл в монитор, другие не могут этого делать)
- В любой момент времени внутри монитора может находиться не более одного процесса.
Используем прослойку из монитора для доступа к разделяемому ресурсу. В таком случае, только работающий с монитором процесс имеет доступ.
Обмен сообщениями (send-receive)
- Две функции:
send([destination,] message)receive([source,] &message)
- Они могут быть с блокировкой или без
- Обращение может быть реализовано через PID
- Функции:
- Функция передачи данных
- Функция синхронизации при использовании блокирующих операций
- Синхронизация и передача данных:
- Для однопроцессорных систем и систем с общей памятью
- Для систем с распределённой памятью
- Для взаимодействия в рамках сети
- Адресация:
- Прямая (IP, port)
- Косвенная (через почтовый ящик)
Есть процесс-сервер отвечающий за критическую секцию. Остальные процессы (процессы-клиенты) через сообщения общаются с сервером. Сервер выстраивает запросы в очередь и обрабатывает.
Классические задачи синхронизации процессов
1. Обедающие философы
- Философы размещаются за круглым столом
- Посередине тарелка со спагетти
- Слева и справа от философа есть по вилке
- Поесть спагетти можно только имея две вилки в руках
Реализация 1
#define N 5
void philosopher (int i) {
while (TRUE) {
think();
take_fork(i);
take_fork((i + 1) % N);
eat();
put_fork(i);
put_fork((i + 1) % N);
}
return;
}Если философы одновременно возьмут левую вилку, получится deadlock.
Реализация 2
#define N 5
#define LEFT (i - 1) % N
#define RIGHT (i + 1) % N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N] = {0};
semaphore mutex = 1;
semaphore s[N] = {0};Мы определили состояния для каждого философа и задали их нулём.
void philosopher(int i) {
while(TRUE) {
think();
take_forks(i);
eat();
put_forks(i);
}
}
void put_forks(int i) {
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}
void take_forks(int i) {
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void test(int i) {
if ((state[i] == HUNGRY) && (state[LEFT] != EATING) && (state[RIGHT] != EATING)) {
state[i] = EATING;
up(&s[i]);
}
}Таким образом, используя семафоры, мы исключаем deadlock.
2. Задача о читателях и писателях
Задача резервирования ресурса. Реализация через семафоры.
- Если в системе есть читающий процесс, все пишущие процессы будут заблокированы, пока читающие не закончат чтение.
Вариант с ошибкой
int rc = 0; // readers count
semaphore mutex = 1;
semaphore db = 1; // database semaphore
void reader() {
down(&mutex);
rc++;
if (rc == 1) down (&db);
up (&mutex);
read_data_base();
down(&mutex);
rc--;
if (rc == 0) up (&db);
up(&mutex);
use_data_read();
}
void writer() {
think_up_data();
down(&db);
write_data_base();
up(&db);
}В данном случае
mutexпозволяет безопасно работать сrc(readers count) (race condition выполняется).dbпозволяет давать доступ к базе данных одновременно только одному процессу.
Несколько читателей могут одновременно читать базу данных. Такая ситуация нас устраивает.
В чём ошибка? Mark
Предыдущую реализацию можно сломать, подав на вход группу писателей. Один зайдёт, закроет семафор
db- остальные будут ждать. Далее заходит читатель и неизвестно, кто зайдёт следующим: читатель или писатель. Приоритет читателей над писателями появляется для тех, писателей, которые ещё не получили доступ к записи.
Решается вопрос добавлением
int wc(writers count) иmutwдля работы с ней
semaphore mutex = 1;
semaphore mutw = 1;
semaphore mutflag = 0;
semaphore db = 1;
int r_block = 0;
int rc = 0;
int wc = 0; // writers count
void reader() {
down(&mutex); // working with rc
rc++;
if (rc == 1) {
if (wc != 0) {
r_block = 1; //
down(&mutflag); // mutflag
r_block = 0; //
};
down(&db); // working with db
};
up(&mutex); // work with rc done
read_data_base();
down(&mutex); // working with rc
rc--;
if (rc == 0) up (&db);
up(&mutex); // work with rc done
use_data_read();
}
void writer() {
down(&mutex); // working with rc
if (rc == 0) {
down(&mutw);
wc++;
up(&mutw);
}
up(&mutex); // work with rc done
think_up_data();
down(&db); // working with db
write_data_base();
up(&db); // work with db done
if (r_block == 1) { //
wc--;
if (wc == 0) up(&mutflag); // mutflag
};
up(&mutw); // work with wc done
}| Критическая секция | Семафор для работы с ней |
|---|---|
rc | mutex |
wc | mutw |
data_base | db |
| Блокировка читателей, когда есть писатели. | mutflag |
r_block - флаг, показывающий, что читатели заблокированы. |
Гипотеза: можно увести wc в меньше нуля. Для этого нужно запустить писателя и далее в нужный момент запустить читателя.
3. Задача о спящем парикмахере
Клиент-сервер с ограничением на длину очереди
- Парикмахер одновременно стрижёт одного человека
- В комнате ожидания есть ограниченное число мест
#define CHAIRS 5;
semaphore customers = 0; // waiters
semaphore barbers = 0; // state of barber. 0 - busy
semaphore mutex = 1; //
int waiting = 0; // waiting count
void barber() {
while (TRUE) {
down(&customers);
down(&mutex);
waiting -= 1;
up(&barbers);
up(&mutex);
cut_hair();
}
}
void customer() {
down(&mutex);
if (waiting < CHAIRS) {
waiting += 1;
up(&customers);
up(&mutex);
down(&barbers)
get_haircut();
} else {
up(&mutex);
}
}Используем
mutexдля измененияwaiting,barbersдля статуса парикмахера - свободен/занят,customers- флаг наличия ожидающих.
Дома смотрим