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

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

Версия от 11:10, 15 февраля 2008; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Владимир Бахтин
Владимир Бахтин

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

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

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

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

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

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

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

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

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

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

Простой пример: есть два процесса, один процесс выполняет операцию 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

Ответы на задачи


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы