Проблемы взаимодействующих процессов.
Проблемы:
.1) Возможность столкновения процессов (нужен одинаковый ресурс)
.2) Возможное отсутствие прогресса в работе (если процессы стоят на месте, например: когда ни кому не войти в критическую секцию)
.3) Возможная взаимоблокировка (заблокировали вход друг другу в критическую секцию)
.4) Возможные голодания (не выполняет критическую секцию и не дает выполнить другому процессу)
Алгоритмы реализации взаимоисключений.
Алгоритм:
Блокирующая глобальная переменная(замок):
shared int lock = 0; // замок открыт
process1
while (lock); // пролог
//Если тут прерывания, то произойдет ппц. Сюда может зайти второй и тогда оба могу зайти в //к.р.
lock = 1; // пролог
{к.с.}
locl = 0; // эпилог
Строгое чередование:
shared int turn = 0;
process I
while(turn != I );
{к.с.}
turn = 1-i;
если 1 из процессов не выполняет свою секцию, то он не отдаст второму.
Алгоритм флагов готовности:
shared int ready[2]={0,0};
process I
ready[i]=1;
Прерывание оба процесса тут. Оба подняли флаги, тогда оба насмерть вешаются(взаим.блок).
while (ready[1-i]);
{к.с.}
ready[i]=0;
Алгоритм Пэтерсона (взаимной вежливости):
shared int ready[2]= {0,0}
shared int turn;
process I
ready[i]=1;
turn = 1 – I;
while(ready[1-i] && turn == 1- I)
{к.с.}
ready[i]=0;
Проблема появляется, когда много процессов, много проверок будет. Большое время разрешения коллизий. Эффективен для малого количества процессов.
Среди ресурсов ОС существуют такие, которые могут быть использованы только одним процессом.
Лучшее решение: блокировать только в момент, когда коду требуется обратиться к такому ресурсу. Такая секции кода называется критической секцией. В таком случае в стеке команд у процесса будет: пролог{ крит секция } эпилог.В момент входа и выхода в крит секцию требуется объявлять об этом системе.
Методы решения проблем взаимоблокировки:
1. однопрограммное выполнение. В прологе блокируются выполнение любых процессов с этими данными. В unix – psw используется для обновления pcb
2. блокирующая глобальна переменная (мьютекс/замок). При не атомарности между while и lock = 1, возникает одновременное использование крит секции.
shared int lock = 0;
процесс 1
while (lock);
lock = 1;
{крит секция}
lock = 0;
3. алгоритм строго чередовании (семафор) Недостаток – передача управлении над критической секцией когда другому процессу она не нужна.
i = 0 или 1;
shared int turn = 0;
процесс i:
while (turn != i);
{крит секция}
turn = 1-i;
4. Алгоритм флагов готовности. Недостаток: при прерывание между ready[i] и while(ready[1-i]) возникает взаимоблокрировка.
shared int ready[2] = {0, 0};
процесс i:
ready[i] = 1;
while (ready[1-i]);
{ крит секция}
ready [i] = 0;
Семафоры Дейкстра. Решение проблемы «производитель-потребитель» с помощью семафоров.
Семафор (S) – целочисленная переменная >=0
p(S): пока S == 0 – блокировать процесс; S--; (атомарная операция)
v(S): S++ (атомарная операция)
Модель работы:
Producer ->buffer[n] -> Consumer; если буфер не полный – producer отправляет туда данные, иначе ждет. Consumer читает данные если есть, иначе ждет.
Объявим 3 семафора.
1. mutex = 1 (0 или 1)
2. empty = N (количество свободных мест в буфере)
3. full = 0 (сколько байт занято в буфере)
Producer:
while (true)
{
produce_item();
p(empty);
p(mutex)
put_item();
v(mutex);
v(full);
}
Consumer:
while (true)
{
p(full)
p(mutex)
get_item()
v(mutex)
v(empty)
consume_item()
}
Тупики. Условия возникновения и направления борьбы с тупиками.
Тупик- Взаимоблокировка (Когда процессы не могут продолжать своё выполнение)
Условия возникновения тупиков:
1. Каждый ресурс может использовать только один процесс.
2. Условие ожидание ресурса. Держит 1 ресурс и запрашивает другой.
3. Не перераспределяемость ресурсов: нельзя отобрать ресурс у процесса.
4. Круговое ожидание: каждый процесс удерживает ресурс нужный кому-то дальше по цепочке.
Решения:
Игнорировать тупики
Предотвращать тупики
Процессы становятся в очередь за ресурсом, но при этом считают, что получили ресурс. (проблема 1)
Процессы если не могут получить ресурс, отпускают все свои ресурсы. (проблема 2)
Передача ресурсов более высокоприоритетному процессу и убийство процесса с более низким приоритетом, который занимает этот ресурс. (проблема 3)
Проиндексировать все ресурсы и выдавать их в строго заданном порядке. (проблема 4)
Обнаруживать тупики
Делать восстановление после тупиков
25. Принципы управления памятью вычислительной системы. Виртуальная память и преобразование адресов.
ПАМЯТЬ КОМПЬЮТЕРА
0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
-------------------------------------
0 - 1 - 2 - 3 - 4
ПАМЯТЬ КАКОЙ-ТО ПРОГРАММЫ
Виртуализация памяти- это явление когда часть физической памяти выделяется для определенного процесса и ее адреса для данного процесса преобразуются в новые, начинающиеся с нуля.
Принципы управления памятью вычислительной системы
Функции ОС по управлению оперативной памятью:
– Отслеживание наличия свободной и занятой памяти;
– Контроль доступа к адресным пространствам процессов;
– Вытеснение кодов и данных из оперативной памяти на диск, когда размеров памяти недостаточно для размещения всех процессов, и возвращение их обратно;
– Настройка адресов программы на конкретную область физической памяти;
– Защита выделенных областей памяти процессов от взаимного вмешательства.