Составители:
Рубрика:
Для иллюстрации рассмотрим процесс сортировки n чисел в по-
рядке возрастания. Пусть имеется два канала: input — входной ка-
нал, output — выходной и sent[i] — i-е значение, отправляемое в
output.
Процесс сортировки может быть описан следующим образом:
SORT: ( ∀ i: 1≤i<n: sent[i]≤sent[i+1])
V
{значения, отправляемые в output, состоят из чисел,
полученных в input}
Схема процесса такова:
process Sort {
получить значения из канала input;
отсортировать числа;
передать отсортированные числа в канал output
}
Напомним, что процесс receive является блокирующим. Для
того, чтобы Sort начал работу требуется, чтобы он определил мо-
мент получения всех n чисел, либо это число n должно быть переда-
но процессу Sort заранее, либо (поскольку поставляющий процесс
обычно не имеет информации о количестве чисел заранее) поток
чисел, подлежащих сорти ровке, должен заканчиваться специаль-
ным маркером EOS.
Интересно использовать параллелизм при слиянии (соедине-
нии). Это можно сделать следующим образом: пусть имеется про-
цесс сливающий (соединяющий) два отсортированных потока чисел
в один отсортированный поток (in1, in2 — входные каналы, out —
выходной канал):
GLUE: in1 и in2 пусты
V
sent[n+1]==EOS
V
(∀i: 1≤i<n: sent[i]≤sent[i+1])
V
{значения, отправляемые в канал out, являются
перестановкой чисел, полученных из каналов in1 и in2 }
П о я с н е н и я : в первой строке процесса GLUE сказано, что
in1 и in2 полностью использованы и в конец строки sent поставлен
символ EOS, во второй строке процесса указано, что значения в sent
расположены в порядке возрастания. В конце сказано, что значения
на выходе являются перестановкой значений входа.
11
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
