Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Дикстра-Шолтен алгоритмі (Эдсгер В. Дикстра мен Карел С. Шолтеннің есімдерімен аталған) – таратылған жүйеде тоқтауды анықтауға арналған алгоритм. Алгоритм 1980 жылы Дикстра мен Шолтен тарапынан ұсынылған. Біріншіден, қарапайым процесс графигін, яғни ағаш тәрізді графикті қарастырайық. Ағаш құрылымды таратылған есептеулер жиі кездеседі. Мұндай процесс графигі есептеу қатаң түрде «бөл және билей» типінде болғанда туындауы мүмкін. Бір түйін есептеуді бастайды және мәселені екіге (немесе одан да көп, әдетте 2-нің есесінен) шамамен тең бөліктерге бөліп, осы бөліктерді басқа процессорларға жібереді. Бұл процесс проблемалар бір процессорда шешілуге жеткілікті кіші болғанша рекурсивті түрде жалғасады.
The Dijkstra–Scholten algorithm (named after Edsger W. Dijkstra and Carel S. Scholten) is an algorithm for detecting termination in a distributed system. The algorithm was proposed by Dijkstra and Scholten in 1980. First, consider the case of a simple process graph which is a tree. A distributed computation which is tree structured is not uncommon. Such a process graph may arise when the computation is strictly a divide and conquer type. A node starts the computation and divides the problem in two (or more, usually a multiple of 2) roughly equal parts and distribute those parts to other processors. This process continues recursively until the problems are of sufficiently small size to solve in a single processor.
Ағаш үшін DijkstraScholten алгоритмі
Ағаштың аяқталуын анықтау оңай. Жапырақ процесі өзі аяқталғанын білгенде, ол өз ата-анасына сигнал жібереді. Әдетте, процесс өзінің барлық балаларынан сигналдарды күтеді, содан кейін ол өзінің ата-анасына сигнал жібереді. Бағдарлама тамыр барлық балаларынан сигнал алғанда тоқтатылады.
For a tree, it is easy to detect termination. When a leaf process determines that it has terminated, it sends a signal to its parent. In general, a process waits for all its children to send signals and then it sends a signal to its parent. The program terminates when the root receives signals from all its children.
Дийкстра-Шолтеннің бағытталған ациклді графиктер үшін алгоритмі
Ағаш алгоритмі ациклді бағытталған графтарға дейін кеңейтілуі мүмкін. Біз әр қабырғаға дефицит деп аталатын қосымша бүтін сан атрибутын қосамыз. Келіп түсетін қабырғада дефицит – алынған хабарламалар саны мен жауап ретінде жіберілген сигналдар саны арасындағы айырмашылықты көрсетеді. Түйін тоқтағысы келгенде, оның шығар қабырғаларынан дефициттерін нөлге дейін азайтатын сигналдарды алуын күтеді. Содан кейін ол әрбір кіретін қабырғада дефицит нөлге тең болуын қамтамасыз ету үшін жеткілікті сигналдар жібереді. Граф ациклді болғандықтан, кейбір түйіндерде шығар қабырғалары болмайды, және осы түйіндер кіретін қабырғаларына жеткілікті сигналдар жібергеннен кейін бірінші болып тоқтайды. Одан кейін жоғары деңгейдегі түйіндер деңгейлеп тоқтайды.
The algorithm for a tree can be extended to acyclic directed graphs. We add an additional integer attribute Deficit to each edge. On an incoming edge, Deficit will denote the difference between the number of messages received and the number of signals sent in reply. When a node wishes to terminate, it waits until it has received signals from outgoing edges reducing their deficits to zero. Then it sends enough signals to ensure that the deficit is zero on each incoming edge. Since the graph is acyclic, some nodes will have no outgoing edges and these nodes will be the first to terminate after sending enough signals to their incoming edges. After that the nodes at higher levels will terminate level by level.