Заметки к лекциям распределённые системы (2014) (1162754), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Load r2, y load r3, x

Add r1, r2 load r4, y

Store r1, x sub r3, r4

Store r3, x

Store r1, x

Тут беда в том, что если это 2 операции, которые выполняют нити, то результат будет зависеть от того, кто за кем выполняется, что приводит к некоторым проблемам синхронизации, и к непредсказуемости поведения программы при её параллельном выполнении.

Критические интервалы – способ решения разграничения управления в нити, пока нить находится в критическом интервале – её нельзя прервать, но чтобы захватить критический интервал (процессорное время), то придётся отстоять в очереди, но тогда проблема с тем, что никто не должен ждать входа в критическую секцию бесконечно долго.

Алгоритм «Деккера» для входа и выхода из критической секции:

int turn;

int flag[2];

turn = 0;

flag[0]=flag[1]=false;

proc(0) && proc(1)

Некоторое улучшение (Алгоритм Петерсона):

void enter_region (int i)

{

int other;

other = 1 - i;

flag[i]=true;

turn = i;

while (turn == i && flag[other] == true);

}

TSL – Test and Set Lock

TSL (r, s) это операция [r=s, s=1], главная особенность в том, что эти 2 операции выполняются неделимо.

enter_region:

tsl reg, flag

cmp reg, #0

jnz enter_region

ret

leave_region:

move flag, #0

ret

Во всех случаях есть проблема – процесс, который ожидает, находится в активной фазе, т.е. он своими проверками и запросами забивает ресурсы машины.

Семафоры (by Дейкстра)

P(s)

[

if (s == 0)

<заблокировать процесс>

else

s = s-1;

]

V(s)

[

if (s == 0)

<разблокировать один из ранее заблокированных процессов>

s = s + 1;

]

Задача – есть процесс, который записывает данные, а второй их считывает, и нужно их развести в правильном порядке.

semaphore mutex = 1; // Нужно на момент записи, чтобы пока один писал или читал, то никто ничего не делал

semaphore full = 0; // Говорит, что место записи занято

semaphore empty = N; // Говорит, записали ли данные или нет

void producer ()

{

while (true)

{

int item;

produce_item(&item);

P(empty); // Заняли слот владения информацией

P(mutex);

emter_item(&item);

V(mutex);

V(full); // Объявили о том, что в буфер положили

}

}

void consumer(

{

while (true)

{

int item;

P(full); // убедились что в буфере что-то действительно есть

P(mutex);

leave_item(&item);

V(mutex);

V(empty); // Сообщили, что слот хранения информации свободен

consume_item(item);

}

}

Задача об обедающих философах.

Каждый философ должен взять вилку слева и справа, чтобы поесть. Однако, если каждый возьмёт по одной вилке слева, то все зависнут и никто не поест.

Поэтому можно решать как в сетях – подождали и опустили вилку, при неудаче. В сетях – этот подход хорошо работает.

Но лучше решать проблему deadlock через семафоры.

Задача Читателей и Писателей – нужно чтобы могло быть любое количество читателей, но всегда один писатель.

Неправильное решение (будет небольшой недостаток):

int rc = 0; // Количество читателей

void reader_reading ()

{

while (true)

{

P(mutex);

rc++;

if (rc == 1)

P(reader)

V(mutex);

read_DB();

P(mutex);

rc--;

if (rc == 0)

V(reader);

V(mutex);

reading();

}

}

void writer ()

{

while (true)

{

produce_data();

P(reader);

write_db();

V(reader);

}

}

Алгоритм не справедлив к писателю, потому что может случиться так, что писателя блокировать будут вечно, ибо прорва читателей, а надо было бы, чтобы писатель блокировал приход новых читак, (ну т.е. останавливал их, чтобы они подождали его).

Задание – исправить алгоритм выше.

Лекция 4

Правильное решение проблемы философов (так чтобы не случалось, что каждый философ возьмёт по одной вилке и будет ждать 2-ю, и так все зависнут)

philisopher(int i) // Как живёт философ

{

while (true)

{

think();

get_fork(i);

eating();

put_fork(i);

}

}

#define N 5 // количество философов и вилок

#define HUNGRY 0

#define EAT 1

#define THINK 2

int state[N]; // Массив вилок

semaphore S[N];

semaphore mutex = 1; // Массив для контроля доступа к state, на основании которого, везде происходит решение, чего делать

#define RIGHT (i+1)%N

#define LEFT (i+N-1)%N

test(int i)

{

if (state[i] == HUNGRY && state[LEFT] != EAT && state[RIGHT] != EAT)

{

state[i] = EAT;

V(S[i]); // Опустили семафор, и тем самым мы разрешаем тому кто вызвал эту функцию продолжить работать

}

}

get_fork(int i)

{

P(mutex);

state[i] = HUNGRY;

test(i);

V(mutex);

P(S[i]); // Мы тут не блокируемся, если test прошёл успешно, т.е. нам будет разрешено продолжить есть, а иначе мы заблокируемся, и будем ждать, пока сосед нас разблокирует

}

put_fork(int i)

{

P(mutex);

state[i] = THINK;

test(LEFT); // Если для левого всё хорошо, то мы опустим ему семафор и он, если был в застое, то разблокируется

test(RIGHT); // Если для правого всё хорошо, то мы опустим ему семафор и он, если был в застое, то разблокируется

V(mutex);

}

Механизм событий

Алгоритм последовательной верхней релаксации (неявная вычислительная схема)

Пусть дано:

float A[L1][L2];

for (i = 1; i < L1 - 1; i++)

for (j = 1; j < L2 - 1; j++)

A[i][j] = (A[i - 1][j] + A[i][j - 1] + A[i + 1]A[j] + A[i][j + 1]) / 4;

Наша задача – параллельно выполнить этот цикл, так чтобы результат не отличался от того, как его выполняют последовательно (проблема в том, что ветки цикла взаимосвязаны)

Суть будет в том, что мы попытаемся семафорами разделить, в соседних потоках обработку зависимых клеток (каждое ядро вычисляет столбик сверху вниз, по мере продвижения его вниз, можно подключать второе ядро для просчёта соседнего столбика, но нельзя допустить, чтобы 2-е обогнало 1-е) (мы собираемся начать вычисление из верхнего, левого угла и продолжать вычислять по диагонали сверху вниз, подключая всё новые столбцы для вычисления) (своего рода конвейер)

float A[L1][L2];

semaphore s[L1][L2]; // По умолчанию они все закрыты (инициализируем дальше)

for (j = 1; j < L2 - 1; j++)

V(s[0][j]);

parfor (i = 1; i < L1 - 1; i++) // parfor - означает, что каждая ветвь цикла будет выполняться отдельно на своём ядре

for (j = 1; j < L2 - 1; j++)

P(S[i-1][j]);

A[i][j] = (A[i - 1][j] + A[i][j - 1] + A[i + 1]A[j] + A[i][j + 1]) / 4;

V(S[i][j]);

Но если у нас ядер больше, чем столбцов, то, чтобы они не простаивали, то в данном случае можно разбить и второй цикл на части (т.е. запустить аналогично предыдущему рассуждению, но по строкам)

float A[L1][L2];

semaphore s[L1][L2]; // По умолчанию они все закрыты (инициализируем дальше)

for (i = 1; i < L2 - 1; i++)

V(s[i][0]);

for (j = 1; j < L2 - 1; j++)

V(s[0][j]);

parfor (i = 1; i < L1 - 1; i++)

parfor (j = 1; j < L2 - 1; j++)

P(S[i-1][j]);

P(S[i][j-1]);

A[i][j] = (A[i - 1][j] + A[i][j - 1] + A[i + 1]A[j] + A[i][j + 1]) / 4;

V(S[i][j]);

Заметим, что мы ждём процесс сверху и процесс снизу, сами мы освобождаем только один свой семафор – и это проблема, потому что ждут 2-е. Поэтому надо пользовать события:

События:

POST (S) – событие произошло – разблокируется сразу вся очередь процессов, которые ждут (в отличие от V, которое освобождало только один процесс)

WAIT (S) – (похоже на P) – процесс останавливается и стоит в очереди

CLEAR (S) – чтобы процесс забыл, был ли там раньше POST

float A[L1][L2];

event S[L1][L2]; // По умолчанию они все закрыты (инициализируем дальше)

for (i = 1; i < L2 - 1; i++)

POST(s[i][0]);

for (j = 1; j < L2 - 1; j++)

POST(s[0][j]);

for (i = 0; i < L1; i++)

for (j = 0; j < L2; j++)

CLEAR(S[i][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]A[j] + A[i][j + 1]) / 4;

POST(S[i][j]);

Как промоделировать события через семафоры P и V:

POST – V

WAIT – P(S)V(S)

Сообщения:

Примерно в 78 году появилась работа, предлагающая использование не разделяемой памяти, а только сообщений.

SEND (destination, &message, m_size)

RECEIVE ([source, ] &message, m_size)

Посылки сообщений бывают блокирующие, неблокирующие, …

Задача – есть производитель и потребитель, если в очереди есть, что делать – то производитель работает, а потребитель ждёт, причём потребитель должен уметь послать N сообщений наперёд, не ожидая ответа (тут типо в этом суть – нужно уметь работать с очередью в N элементов (и забить помаксимуму)). (подразумевается один производитель и один потребитель, которые работают на разных ядрах, рассинхронизованно)

#define N 100

#define msize 4

typedef int message[msize];

producer()

{

message m;

int item;

while (true)

{

produce_item(&item);

RECEIVE(consumer, &m, msize);

build_message(&m, item);

SEND(consumer, &m, msize);

}

}

consumer()

{

message m;

int item;

for (int i = 0; i < N; i++)

SEND(producer, &m, msize);

while (true)

{

RECEIVE(producer, &m, msize);

extract_item(&m, item);

SEND(producer, &m, msize);

consume_item(item);

}

}

Лекция 5

Читай лекции самого лектора

Алгоритмы с маркерами хороши, когда процессы входят в критическую секцию с разной частотой, и тогда, если кому-то нужно несколько раз подряд войти в критическую секцию – то он сделает это, получив маркер.

DSM – распределённая общая память

Лекция 6

Читай лекции самого лектора.

Лекция 7

Распределённые файловые системы (немного теории, и реальный пример - NTFS)

С появлением сетей, хотелось бы:

Сетевая прозрачность (т.е. работа с удалёнными файлами не шибко отличается от работы с локальным файлом) и доступность (не должно быть каких-то больших проблем с доступностью к файлу (например у суперкомпьютеров есть проблема – миллионы ядер и все хотят читать из одного места жёсткого диска – ну и wtf?))

Файловый сервис – это как бы интерфейс, который система предоставляет своим пользователям.

Файловый сервер – тот, кто читает файл и отдаёт в интернет

Сервер директории – он указывает нам путь к файлу

Существует много разных систем:

AFS (какой-то университет)

NFS – корпорация sun

Характеристики

Список файлов лекций