Викиконспекты - Вклад участника [ru]

Часы с прямой зависимостью

2018-02-23T12:35:02Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Логические часы с прямой зависимостью''' ''(direct dependency)'' - функция из множества событий распределенных систем (внутреннее событие, событие отправки сообщения и событие приема сообщения) в вектор из целых чисел.

* Каждый поток имеет целочисленный ''n''-мерный вектор (''n'' – количество потоков), проинициализированный нулями;
* В случае любого события, поток увеличивает на единицу свою компоненту вектора;
* При посылке сообщения от первого потока ко второму, отправляющий поток отправляет свою компоненту вектора, а при приеме сообщения второй поток обновляет свой вектор путем выбора максимума только у той компоненты вектора, которая была отправлена.

В отличие от [[Векторные часы|векторных часов]]:
*при посылке сообщения передаем только свою компоненту вектора;
*при приеме сообщения обновляем путем выбора максимума только компоненты, отвечающие отсылающему и принимающему процессам;

Оказывается, что если ввести [[Частичный порядок|частичный порядок]] предшествования на событиях несколько иным образом (потребовать прямую зависимость), то имеет место следующее утверждение:
:''a'' предшествует ''b'', тогда и только тогда, когда логическое время часов с прямой зависимостью события ''a'' меньше логического времени события ''b'' (''a.v[a.p] ≤ b.v[a.p]'', где ''a.p'' – номер процесса, в котором происходит событие ''a'').

Требование '''прямой зависимости''' звучит следующим образом: между событиями ''a'' (процесс ''u'') и ''b'' (процесс ''v'') процесс ''u'' передал процессу ''v'' сообщение, процесс ''v'' его принял. Если говорить более формально, при транзитивном замыкании, упомянутом в определении частичного порядка предшествования, первое правило можно использовать только один раз.

Векторные часы

2018-02-23T12:24:00Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Логическими векторными часами''' называется функция из множества событий распределенных систем (внутреннее событие, событие отправки сообщения и событие приема сообщения) в вектор из целых чисел.

* каждый поток имеет целочисленный n-мерный вектор (n – количество потоков), проинициализированный нулями.
* в случае внутреннего события счётчик текущего процесса увеличивается на 1;
* перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению;
* при получении сообщения счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в максимум от текущего и полученного.

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

Оказывается, что если в распределенной системе ввести [[Параллельное программирование: Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:<br>
''a'' предшествует ''b'', тогда и только тогда, когда логическое время векторных часов события ''a'' меньше логического времени события ''b'' (при этом вектор ''x'' меньше вектора ''y'', если для каждой компоненты выполяется <tex>x_i \le y_i</tex> и <tex>\exists j: x_j < y_j</tex>).

Важным свойством векторных часов в распределенных системах с введенным [[Параллельное программирование: Частичный порядок|частичным порядком предшествования]] оказывается то, что при сравнении векторов времени двух событий достаточно сравнивать только компоненты процессов, которым эти события принадлежат.

Логические часы Лампорта

2018-02-23T12:22:52Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Логическими часами Лампорта''' называется функция из множества событий распределенных систем (внутреннее событие, событие отправки сообщения и событие приема сообщения) в множество неотрицательных целых чисел.

Часы Лампорта присваивают каждому событию единственное число, монотонно увеличивая счётчик каждого процесса согласно следующим правилам:

* счётчик увеличивается перед каждым внутренним событием процесса;
* при отправке сообщения значение счётчика увеличивается и прикрепляется к сообщению;
* при получении сообщения значение счётчика процесса-получателя выставляется в максимум текущего и полученного значения и увеличивается на 1.

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

Оказывается, что если в распределенной системе ввести [[Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:
:Если ''a'' предшествует ''b'', то логическое время часов Лампорта события ''a'' меньше логического времени события ''b'' (обратное, вообще говоря, не верно).

Распределённые вычислительные системы

2018-02-23T12:20:31Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Распределенные вычислительные системы''' — это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.

Отличия распределенных систем от систем с разделяемой памятью:
# В каждом узле распределенной системы свое время (невозможность задания глобального времени)
# Связь между узлами распределенной системы не мгновенная, а с существенной задержкой
# Связь ненадежна, т.е. сообщения могут теряться
# Любой узел может в любой момент быть выключен или отказать.

Распределённая система состоит из конечного множества N независимых процессов {P1...PN}. Множеством возможных событий, происходящих внутри процессов, называют множество из:
* внутренних событий
* событий отправки
* событий получения сообщения.

Распределённые вычислительные системы

2018-02-23T12:19:34Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Распределенные вычислительные системы''' — это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.

Отличия распределенных систем от систем с разделяемой памятью:
# В каждом узле распределенной системы свое время (невозможность задания глобального времени)
# Связь между узлами распределенной системы не мгновенная, а с существенной задержкой
# Связь ненадежна, т.е. сообщения могут теряться
# Любой узел может в любой момент быть выключен или отказать.

Распределённая система состоит из конечного множества N независимых процессов {P1...PN}. Множеством возможных событий, происходящих внутри процессов называются следующие события:
* внутренние события
* события отправки
* события получения сообщения.

Логические часы Лампорта

2018-02-23T12:12:48Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Логическими часами Лампорта''' называется функция из множества событий распределенного вычисления (внутреннее событие, событие отправки сообщения и событие приема сообщения) в множество неотрицательных целых чисел.

Часы Лампорта присваивают каждому событию единственное число, монотонно увеличивая счётчик каждого процесса согласно следующим правилам:

* счётчик увеличивается перед каждым внутренним событием процесса;
* при отправке сообщения значение счётчика увеличивается и прикрепляется к сообщению;
* при получении сообщения значение счётчика процесса-получателя выставляется в максимум текущего и полученного значения и увеличивается на 1.

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

Оказывается, что если в распределенной системе ввести [[Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:
:Если ''a'' предшествует ''b'', то логическое время часов Лампорта события ''a'' меньше логического времени события ''b'' (обратное, вообще говоря, не верно).

Векторные часы

2018-02-23T11:38:37Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Логическими векторными часами''' называется функция из множества событий (прием/посылка сообщений) в вектор из целых чисел.

* каждый поток имеет целочисленный n-мерный вектор (n – количество потоков), проинициализированный нулями.
* в случае внутреннего события счётчик текущего процесса увеличивается на 1;
* перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению;
* при получении сообщения счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в максимум от текущего и полученного.

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

Оказывается, что если в распределенной системе ввести [[Параллельное программирование: Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:<br>
''a'' предшествует ''b'', тогда и только тогда, когда логическое время векторных часов события ''a'' меньше логического времени события ''b'' (при этом вектор ''x'' меньше вектора ''y'', если для каждой компоненты выполяется <tex>x_i \le y_i</tex> и <tex>\exists j: x_j < y_j</tex>).

Важным свойством векторных часов в распределенных системах с введенным [[Параллельное программирование: Частичный порядок|частичным порядком предшествования]] оказывается то, что при сравнении векторов времени двух событий достаточно сравнивать только компоненты процессов, которым эти события принадлежат.

Логические часы Лампорта

2018-02-23T11:28:37Z

5.18.232.183:

[[Категория: Параллельное программирование]]
'''Логическими часами Лампорта''' называется целочисленная функция из множества событий (прием/посылка сообщений).

Часы Лампорта присваивают каждому событию единственное число, монотонно увеличивая счётчик каждого процесса согласно следующим правилам:

* счётчик увеличивается перед каждым внутренним событием процесса;
* при отправке сообщения значение счётчика прикрепляется к сообщению;
* при получении сообщения значение счётчика процесса-получателя выставляется в максимум текущего и полученного значения и увеличивается на 1.

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

Оказывается, что если в распределенной системе ввести [[Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:
:Если ''a'' предшествует ''b'', то логическое время часов Лампорта события ''a'' меньше логического времени события ''b'' (обратное, вообще говоря, не верно).