1. Тупики: Обнаружение тупиков для повторно используемых ресурсов методом редукции графа, способы представления графа, алгоритмы обнаружения тупиков. Пример анализа состояния системы редукции графа. Методы восстановления работоспособности системы.
Тупик — это ситуация, которая возникает в результате монопольного использования разделяемых ресурсов, когда процесс, владея ресурсом, запрашивает другой ресурс, занятый непосредственно или через цепочку запросов другим процессом, ожидающим освобождения ресурса, занятого первым процессом.
В теории тупиков принято различать два типа ресурсов (эти типы обладают набором характерных особенностей, которые потребовали такой классификации):
- Повторно используемые ресурсы
- Потребляемые ресурсы
Повторное используемые ресурсы — используются многократно, использование ресурса не изменяет качества и характеристик ресурса. К повторно используемым ресурсам относится: реентерабельный код системы, системные таблицы, разделяемая память, семафоры, программные каналы.
Потребляемые ресурсы — количество в ОС переменно и произвольно. К потребяемым ресурсам относится: память, каналы, внешние устройства, процессор, сообщения (получено -> перестало существовать).
Условия возникновения тупика (в любой системе):
- Взаимоисключение. Возникает, когда процессы монопольно используют ресурсы.
- Ожидание. Когда процессы удерживают занятые ими ресурсы, ожидая предоставления им дополнительных ресурсов.
- Неперераспределяемость. Когда ресурсы нельзя отобрать у процесса до их завершения, или как говорят, добровольного особождения этих ресурсов (надпись: ресурсы у процесса нельзя принудительно отобрать).
- Круговое ожидание. Возникает замкнутая цепь запросов процессов на дополнительные ресурсы.
Методы борьбы с тупиками:
- Предотвращение или недопущение (или исключение самой возможности возникновения тупика)
- Обход или недопущение
- Обнаружение и восстановление
Обнаружение тупиков происходит с помощью графовой модели. Система может быть описана двудольным направленным графом. Два непересекающихся множества вершин: процессы и ресурсы. Вершины соединяются дугами, никакая дуга не соединяет вершины одного подмножества. Дуга, направленная из вершины ресурсов, к вершине процессов, называется выделением или приборетением ресурсов. Дуга направленная из вершины процессам к ресурсам называется запросом.
Графовая модель Холта
- Приобретение -
(r, p)(от ресурса к процессу) - Запрос -
(p, r)(от процесса к ресурсу)
Обнаружение тупиков по графовой модели выполняется методом редукции графа. Этот метод основан на предположении, что незаблокированный в тупике процесс может запрашивать приобретения любых нужных ему ресурсов, а затем освобождать их. Освободившиеся ресурсы могут быть выделены или распределены другим процессам, которые их ожидают.
P1 выделено два ресурса R1 и он запрашивает один ресурс R2. P2 выделены по одному ресурсу R1 и R2 и он запрашивает ещё один R1 и R2. Видно, что процесс P1 может завершиться, значит он может стать изолированной вершиной (освободить занимаемые им ресурсы). Когда P1 завершиться, запросы P2 могут быть удовлетворенны (и он тоже сможет завершиться. В итоге, обе вершины P1 и P2 будут изолированны. Такой редукцией определяется, что система не находится в тупике (вершины процессов изолированны).
Способы представления графа
Двудольный граф может быть описан 2 матрицами или 2 связными списками. Матричное представление более удобно, мы используем его.
Метод прямого обнаружения.
Последовательно рассматриваются запросы каждого процесса и определяется, может ли этот запрос быть удовлетворен. Последовательный просмотр матрицы запросов. В процессе просмотра определяется возможно ли сокращение соотвествующей дуги или невозможно (если возможно - сокращается). Те процессы, которые останутся в этих матрицах после всех возможных сокращений будут находится в тупике. Очевидно, что для реализации нужно выполнить (m процессов, n ресурсов) (mn)^2 проверок.
Более эффективный алгоритм.
Для каждого ресурса необходимо хранить ресурсы, упорядоченные по размеру. Для каждого процесса Pi определяется счетчик ожидания, который содержит число ресурсов каждого типа, которые вызвали блокировку процесса (или указывает на ресурсы, на которых процесс был блокирован в ожидании освобождения ресурсов). В этом алгоритме также хранится вектор свободных ресурсов. То есть если к матрице запросов и матрице распределения добавить вектор свободных ресурсов, то можно для каждого процесса анализировать его вектор запросов (если вектор запросов процессов меньше, чем вектор свободных ресурсов, то его запросы могут быть удовлетворены).
Вектор свободных единиц ресурсов: F = { ...,
— общее количество единиц j-ого ресурса.
Восстановление системы.
- Перезагрузка системы
- Дорогое решение, так как будет потеряна вся проделанная незавершившимися процессами работа.
- Для системы, работающей длительное время, такой подход невозможен.
- Последовательно завершать процессы, попавшие в тупик
- В результате, процессы, работа которых завершается, вернут занимаемые ресурсы. Этих ресурсов может оказаться достаточно, чтобы другие процессы могли успешно продолжить работу.
- Очевидный недостаток - проделанная работа завершаемого процесса будет потеряна.
- Завершать процессы, не имеющие отношения к тупику
- То есть отнимать ресурсы у процессов, вернуть их системе, и мб того процессы, попавшие в тупик, смогут завершиться.
- Решается на основе приоритетов.
2. Задача "Обедающие философы" — модели распределения ресурсов вычислительной системы. Множественные семафоры UNIX: системные вызовы, поддержка в системе, пример использования из лабораторной "производство-потребление"
На круглом столе лежит 5 тарелок. Напротив каждой тарелки стоит философ. Какое-то время фиолософ думает, какое-то ест. Есть философ может только с помощью двух приборов. Изначально у каждой тарелки только один прибор. Cуществует три способа действий философов:
- Каждый пытается взять две вилки, и если ему это удается, то он ест.
- Философ пытается взять правую вилку, после чего, удерживая ее, пытается взять левую.
- Философ пытается взять правую, если не может взять левую, то кладёт правую на место.
1 способ — бесконечное откладывание. Какой-то философ может умереть голодной смертью.
2 способ — все философы одновременно берут правую вилку и блокируют друг друга.
3 способ — захват и освобождение одних и тех же ресурсов.
Современные ОС поддерживают наборы считающих семафоров. Такие наборы представлены в системе массивами и доступ к отдельному семафору набора осуществляется по индексу. Самое важное свойство набора семафоров: одной неделимой командой можно изменить все или часть семафоров набора. Если какая-либо операция не может быть выполнена над одним семафором, то неудачной считается операция над всеми семафорами.
Семафоры поддерживаются в ядре таблицей семафоров. Набор семафоров описывается следующим образом:
- Имя - целое число, присваивается процессам, создавшим набор семафоров.
- UID - индетификатор создателя набора семафора и его группы.
- Права доступа.
- Количество семафоров в наборе.
- Время изменения одного или нескольких значений семафора последним процессом.
- Время изменения управляющих параметров
- Указатель на массив семафоров
О каждом семафоре известно:
- Значение семафора.
- ID процесса, который оперировал с семафором в последний раз.
- Число процессов заблокированных на семафоре.
Функция semget() создает новый набор семафоров или открывает уже имеющийся:
int semget(key_t key, int numb_sem, int flag);В случае успешного завершения функция возвращает дескриптор семафора, а в случае неудачи -1. Параметр numb_sem задает количество семафоров в наборе. Параметр key задает идентификатор семафора. Если значением key является макрос IPC_PRIVATE, то создается набор семафоров, который смогут использовать только процессы, порожденные процессом, создавшим семафор. Параметр flag представляет собой результат побитового сложения прав доступа к семафору и константы IPC_CREATE.
Пример использования
Cледующий системный вызов создает набор из двух семафоров с идентификатором 100, для которого устанавливаются следующие права доступа: чтение-запись - для владельца, чтение – для членов группы и остальных пользователей.
int perms = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;
int isem_descr = semget(100, 2, IRC_CREATE | perms);Функция semctl() позволяет изменять управляющие параметры набора семафоров.
int semctl(int semid, int semnum, int cmd, ...);После получения идентификатора дескриптора семафора в системе значение семафора можно изменять с помощью системного вызова semop():
int semop(int isem_descr, struct sembuf *op, int nop);Параметр op – указатель на массив объектов типа struct sembuf, параметр nop определяет количество семафоров набора, над которыми выполняется операция. Системный вызов semop оперирует не с отдельным семафором, а с множеством семафоров, применяя к нему "массив операций".
Структуры для работы с семафорами:
struct sembuf
{
unsigned short sem_num; // индекс
short sem_op; // операция
short sem_flg; // флаги
};На семафоре Unix определено 3 операции:
- Захват, декремент.
sem_op < 0. Получение ресурса. - Освобождение, инкремент.
sem_op > 0. Разблокирование процесса. - Проверка семафора на 0.
sem_op = 0. Усыпление вызывающего процесса, пока значение семафора не станет 0.
Для выполнения первых двух операций у процесса должно быть право на изменение, для выполнения третьей достаточно права на чтение.
На семафорах определены следующие флаги:
- IPC_NOWAIT — информирует ядро о нежелании процесса переходить в состояние ожидания. Позволяет избежать очереди к семафору, в случае аварийного завершения или kill, т.к. в этом случае убиваемый процесс не может осуществить освобождение семафора.
-
SEM_UNDO — указывает ядру, о том что необходимо отслеживать значение семафора. В результате завршения процесса, вызвавшего
semop, ядро отменяет все изменения, чтобы процессы не были заблокированны навсегда.
ОС выполняет операции из "массива операций" по очереди, порядок не оговаривается. Если очередная операция не может быть выполнена, то эффект предыдущих операций аннулируется. Если таковой оказалась операция с блокировкой, выполнение системного вызова приостанавливается. Если неудачу потерпела операция без блокировки, системный вызов немедленно завершается, возвращая значение -1. Другой процесс не может получить доступ к промежуточному состоянию семафоров.
Пример из ЛР
#define BIN_SEM 0
#define BUFF_FULL 1
#define BUFF_EMPTY 2
struct sembuf CONS_LOCK[] = {
{ BUFF_FULL, -1, 0 },
{ BIN_SEM, -1, 0 }
};
struct sembuf CONS_RELEASE[] = {
{ BUFF_EMPTY, 1, 0 },
{ BIN_SEM, 1, 0 }
};
int consumer_run(cbuffer_t *const buf, const int sid, const int consid) {
srand(time(NULL) + consid + 3);
if (!buf) {
return 1;
}
for (int i = 0; i < 8; i++) {
int sleep_time = rand() % CONS_TIME_RANGE + CONS_TIME_START;
sleep(sleep_time);
if (-1 == semop(sid, CONS_LOCK, SEM_SIZE)) {
return 3;
}
char symb;
if (-1 == read_buffer(buf, &symb)) {
return 2;
}
printf("Consumer %d read: %c\n", consid + 1, symb);
if (-1 == semop(sid, CONS_RELEASE, SEM_SIZE)) {
return 3;
}
}
return 0;
}
struct sembuf PROD_LOCK[] = {
{ BUFF_EMPTY, -1, 0 },
{ BIN_SEM, -1, 0 }
};
struct sembuf PROD_RELEASE[] = {
{ BUFF_FULL, 1, 0 },
{ BIN_SEM, 1, 0 }
};
int producer_run(cbuffer_t *const buf, const int sid, const int prodid) {
srand(time(NULL) + prodid);
if (!buf) {
return 1;
}
for (size_t i = 0; i < 8; i++) {
int sleep_time = rand() % PROD_TIME_RANGE + PROD_TIME_START;
sleep(sleep_time);
if (-1 == semop(sid, PROD_LOCK, SEM_SIZE)) {
return 3;
}
const char symb = (buf->write_pos % 26) + 'a';
if (-1 == write_buffer(buf, symb)) {
return 2;
}
printf("Producer %lu write: %c\n", prodid + 1, symb);
if (-1 == semop(sid, PROD_RELEASE, SEM_SIZE)) {
return 3;
}
}
return 0;
}