РОС, 02 лекция (от 15 февраля)

Материал из eSyr's wiki.

Версия 10:25, 15 февраля 2008

Владимир Бахтин

Взаимодействие процессов

Есть закон Гордона Мура об удвоении производительности, раньше это делали увеличением частоты, но в последнее время увеличивать её всё сложнее, при увеличении такт. частоты на 1 процент энергпотребление увеличивается на 3---10 процентов. Выход нашли в многоядерности и многопоточности.

Что будем понимать под процессом: выполнение программ

1. сама программа
2. Данные
3. Ресурсы
4. Данные, связанные с программой (контекст, дескрипторы...), то есть, достаточно большой объём информации, котрый надо сохранять при переключении процессов

Процессы можно разделить на

• Независимые
• Взаимодействующие

Независимые --- те, которрые не требуют никакого взаимодействия (обмена данных), синхронизации, тем не менее, они могут конкурировать за ресурсы системы

Виды взаимодействия:

• Обмен сообщениями
• Разделяемая память
  • Оперативная память
  • Внешняя память

Простой пример: есть два процесса, один процесс выполняет операцию I = I + J

• Если выполнится первый, потом второй: 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)? Он позволяет разблокировать всю очередь и можно попытаться реализовать события через семафоры. Мы видим, что алгоритмы близки и их можно реализовать один через другой.