РОС, 02 лекция (от 15 февраля)
Материал из eSyr's wiki.
Владимир Бахтин
Взаимодействие процессов
Есть закон Гордона Мура об удвоении производительности, раньше это делали увеличением частоты, но в последнее время увеличивать её всё сложнее, при увеличении такт. частоты на 1 процент энергпотребление увеличивается на 3---10 процентов. Выход нашли в многоядерности и многопоточности.
Что будем понимать под процессом: выполнение программ
- сама программа
- Данные
- Ресурсы
- Данные, связанные с программой (контекст, дескрипторы...), то есть, достаточно большой объём информации, котрый надо сохранять при переключении процессов
Процессы можно разделить на
- Независимые
- Взаимодействующие
Независимые --- те, которрые не требуют никакого взаимодействия (обмена данных), синхронизации, тем не менее, они могут конкурировать за ресурсы системы
Виды взаимодействия:
- Обмен сообщениями
- Разделяемая память
- Оперативная память
- Внешняя память
Простой пример: есть два процесса, один процесс выполняет операцию I = I + J
P2 : I = I - K | P1: I = I + J |
---|---|
LOAD R1, I | LOAD R1, I |
LOAD R2, K | LOAD R2, J |
SUB R1, R2 | ADD R1, R2 |
STORE I, R1 | STORE I, R1 |
- Если выполнится первый, потом второй: I = I + J - K
- Если второй, потом первый: I = I - K + J
- Если подошли одновременно: I = I - K или I + J, в зависимости от того, кто последним сохранит.
В последнем случае возникает race condition.
Какие способы есть:
- Координация процессов. На программиста накладывается некая работа по планированию процессов
- Механизм взаимного исключения критических интервалов
Каким условиям должен удовлетворять механизм интервалов:
- В любой момент времени должен выполняться только один процесс
- Если внутри критического интервала никого нет, то доступ без задержки
- Ни один процесс не должен ждать входа в интервал бесконечно долго, при условии, что там никто не находится бесконечно долго
- Не должно быть никаких предположений о скорости процессора
Мы сформулировали ряд критериев и дальше посмотрим, насколько те алгоритмы, которые будут далее, удовлетворяли им.
Как решается эта проблема для однопроцесорных ЭВМ:
Каждому процессу выделяется квант, потом происходит переключение. И если блокируем внешние прерывания, то прерывания не будет. Понятно, что когда мы гворим о многопроцессорной ЭВМ, такой вариант не подходит.
Рассмотрим алгоритм Деккера (1968 год)
PROC (int i) { WHILE (TRUE) { //вычисления enter_region(i); //критический интервал leave_region(i); } }
Мы запустили PROC(0) AND PROC(1).
Что используется:
- boolean flag[2];
- int turn;
enter_region(int i) { try: flag[i] = TRUE; while (flag[(i + 1) % 2]) { if (turn == i) continue; flag[i] = FALSE; while (turn != i); goto try; } }
leave_region(int i) { turn = (i + 1) % 2; flag[i] = false; }
Инициализация:
turn = 0 flag[0] = flag[1] = FALSE;
При одновременном входе переменная turn определяет порядок входа в интервал.
Есть немного модифицированный алгоритм, алгоритм Петерсона. У каждого процесса заводится дополнительная переменная other (номер другого процесса)
enter_region(int i) { int other; other = 1 - i; flag[i] = TRUE; turn = i; while ((turn == i) && (flag[other] == TRUE)); }
leave_region(int i) { turn = (i + 1) % 2; flag[i] = false; }
Допустим, сначала заходит нулевой процесс (рассказ пооператорный).
Что будет, когда два процесса войдут в крит. интервал. Входят два процесса в крит. интервал.
Экзамен проходит в форме задач. На решении задач проверяется знание теории. в частности, какую задачу можно получить. Будет рассказываться темма распред. общая память, когда на кластере пытаются эмулировать общую память. Обновление производится с задержками и есть понятие консистентность, и есть порядок записи, который может отличаться от порядка по времени, и можно получить задачу, каким моделям консист. удовл. эти алгоритмы. Надо найти ситуации, при которых эти алгоритмы перестают работать. Можно получить задачу улучшить и расширить на 3 процессора.
Главный недостаток алгоритмов --- ограничение на 2 процессора.
Рассмотрим алгоритм tsl (test and set lock)
tsl(r, S) [r = S, s = 1] --- неделимая операция.
enter_region: tsl reg, flag cmp reg, #0 jnz enter_region ret
leave_region: move flag, #0
ret
Флаг должен быть обнулён перед началом работы.
Для чего можно использовать операцию tsl? Например, для семафоров. С семаформами связана очередь ожидающих процессов, и используя этот оператор, можно получать доступ к очереди.
Семафоры
Операция захвата семафора: P(S) [if (S == 0) <заблокировать текущий процесс>; else S = S - 1]
Операция освобождения семафора: V(S) [if (S == 0) <разблокировать один из заблокированных процессов>, S = S + 1]
После разблокировки операция начинается сначала.
Задача производитель/потребитель. Есть зацикленный буфер на N переменных, производитель пишет, потребитель считает. Производитель должен останавливаться на заполненном буфере, потребитель не должен получать сырых данных. Для реализации исп. два семафора:
- semaphore S = 0
- semaphore full = 0
- semaphore empty = N
produce () { int item; while (TRU) { produce_item(&item); P(empty); P(S); enter_item(item); V(S); V(full); } }
consumer() { int item; while (TRUE) { P(full); P(S); remove_item(&item); V(S); V(empty); consume_item(item); } }
Помимо координации буфера присутствует координация процессов.
Если у нас возникнет несколько потребителей, то возникнут проблемы, потребуется столько семафоров, сколько потребителей. В этом случае лучше использовать механизм событий.
Существуют разные реализации механизма событий:
- С памятью/без памяти
- повторяющиеся/однократные
Алгоритм релаксации.
semaphore S[L1][L2] float A[L1]{L2}; for (i = 0; i < L1; i++) for (j = 0; j < L2; j++) CLEAR(S[i][j]); for (i = 0; i < L1; i++) POST(S[i][0]); for (j = 0; j < L1; j++) POST(S[0][j]); parfor (i = 1; i < L1 - 1; i++) parfor (j = 1; j < L2 - 1; j++) { WAIT(S[i - 1][j]); WAIT(S[i][j - 1]); A[i][j] = (A[i - 1][j] + A[i][j - 1] + A[i + 1][j] + A[i][j + 1]) / 4; POST(A[i][j]); }
Тту довольно тяжёлая зависимость по данным, и использование механизма событий позволяет его реализовать.
Пример задачи на экзамене: убрать один параллельный цикл.
Какая ещё может быть задача: можно попытаться реализовать через семафоры. В чём основная разница: есть операция V(S), похожая операция POST(S). Разница заключается в том, что тут освобождается один процесс, а тут все. Есть операция P(S), есть WAIT(S). И там, и там блокируем процесс. Что нужно добавтиь, чтобы при освобождении процесса? Нам нужно добавить, что когда один брочесс разблокировался, он дложен разблокировать все процессы в очереди. Что, если добавить V(S)? Он позволяет разблокировать всю очередь и можно попытаться реализовать события через семафоры. Мы видим, что алгоритмы близки и их можно реализовать один через другой.
Распределённые операционные системы
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Календарь
пт | пт | пт | пт | пт | |
Февраль
| 08 | 15 | 22 | 29 | |
Март
| 06 | 13 | 20 | 27 | |
Апрель
| 04 | 11 | 18 | 25 | |
Май
| 02 | 16 | 23 |