About: Dekker's algorithm     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatAlgorithms, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FDekker%27s_algorithm

Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions and his manuscript on cooperating sequential processes. It allows two threads to share a single-use resource without conflict, using only shared memory for communication. It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.

AttributesValues
rdf:type
rdfs:label
  • Dekker's algorithm
  • Dekker-Algorithmus
  • Algoritmo de Dekker
  • Algorithme de Dekker
  • Algoritmo di Dekker
  • デッカーのアルゴリズム
  • Algorytm Dekkera
  • Алгоритм Деккера
rdfs:comment
  • Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions and his manuscript on cooperating sequential processes. It allows two threads to share a single-use resource without conflict, using only shared memory for communication. It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.
  • Der Dekker-Algorithmus (nach Theodorus Dekker) ist wie der Peterson-Algorithmus eine vollständige Lösung des Problems, den wechselseitigen Ausschluss (Mutex) in der dezentralen Steuerung von Prozessen (Prozesssynchronisation) zu gewährleisten. Er vermeidet gegenseitiges Blockieren (Deadlock) und gewährleistet, dass stets genau ein Prozess in einen kritischen Abschnitt gelangen kann (Sequentialisierung).
  • L'algorithme de Dekker est un algorithme d'exclusion mutuelle. Il est basé sur une approche par attente active et est divisé en deux parties, à savoir le protocole d'entrée dans la section critique et le protocole de sortie. L'algorithme présenté dans cet article est une version pouvant fonctionner avec N thread, version due à Edsger Dijkstra.
  • L'algoritmo di Dekker, noto anche come algoritmo di proiezione di Dijkstra, costituisce una soluzione completa al problema della mutua esclusione nella coordinazione decentrata di processi (sincronizzazione), impedendo lo stallo (deadlock) ed assicurando che soltanto un processo alla volta possa eseguire una sezione critica (serializzazione). Tale algoritmo è attribuito al matematico olandese Th. J. Dekker da Edsger W. Dijkstra nel suo manoscritto sui processi cooperanti sequenziali.
  • Algorytm Dekkera – pierwszy algorytm poprawnie rozwiązujący problem wzajemnego wykluczania się równolegle działających procesów. Tylko jeden z nich może w danej chwili wykonywać ich wspólną sekcję krytyczną (zob. programowanie współbieżne). Rozwiązanie to zostało przypisane holenderskiemu matematykowi T. J. Dekkerowi przez Edsgera Dijkstrę w jego manuskrypcie na temat współdziałania procesów sekwencyjnych. Algorytm pozwala dwóm wątkom na bezkonfliktową pracę na danych pochodzących z jednego źródła przy użyciu do komunikacji między nimi jedynie pamięci dzielonej.
  • Алгоритм Деккера — первое известное корректное решение проблемы взаимного исключения в параллельном программировании. Эдсгер Дейкстра ссылается на голландского математика Т. Деккера как на автора данного алгоритма в своей работе о межпроцессном взаимодействии. Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации.
  • El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra. Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.
  • デッカーのアルゴリズムはオランダ人数学者 T・J・デッカーの考案した相互排他のためのアルゴリズムである。これにより、共有メモリによる通信のみで、2つのプロセスが1つのリソースを競合することなく共有することができる。 厳密に交互にとっていく素朴なアルゴリズムを避けて発明された世界初の相互排他アルゴリズムの1つである。 ふたつのプロセスが同時に同じクリティカルセクションにアクセスしようとしたとき、このアルゴリズムはどちらのプロセスがアクセス権を得るかを決定する。もしもう一方のプロセスが既にクリティカルセクションに変更を加えていたら、その完了を待つ。
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
foaf:isPrimaryTopicOf
prov:wasDerivedFrom
has abstract
  • Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions and his manuscript on cooperating sequential processes. It allows two threads to share a single-use resource without conflict, using only shared memory for communication. It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.
  • El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra. Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización. Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos los primeros cuatro. La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4. * Versión 1: Alternancia estricta. Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos. * Versión 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí. * Versión 3: Colisión región crítica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región crítica. * Versión 4: Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda. shared int cierto = 1; ''/* Definición de variables compartidas */ '' shared int bandera[2] = {0,0}; shared int turno = 0; while (cierto) { bandera[proc_id] = cierto; // Está listo para acceder a la Sección Crítica while (bandera[1-proc_id] == cierto) { // Mientras el otro esté procesando if (turno == 1-proc_id) { // si es su turno bandera[proc_id] = 0; // indicar que no está listo y while (turno == (1-proc_id)) {} // esperar activamente. bandera[proc_id] = 1; // Cuando terminó de esperar, está listo } } /* ''Sección crítica'' */ turno = 1-proc_id; // Indicar el turno del otro proceso bandera[proc_id] = 0; // Indicar que ya no está listo (para acceder a la Sección Crítica) /* ''Sección no crítica'' */ }
  • Der Dekker-Algorithmus (nach Theodorus Dekker) ist wie der Peterson-Algorithmus eine vollständige Lösung des Problems, den wechselseitigen Ausschluss (Mutex) in der dezentralen Steuerung von Prozessen (Prozesssynchronisation) zu gewährleisten. Er vermeidet gegenseitiges Blockieren (Deadlock) und gewährleistet, dass stets genau ein Prozess in einen kritischen Abschnitt gelangen kann (Sequentialisierung).
  • L'algorithme de Dekker est un algorithme d'exclusion mutuelle. Il est basé sur une approche par attente active et est divisé en deux parties, à savoir le protocole d'entrée dans la section critique et le protocole de sortie. L'algorithme présenté dans cet article est une version pouvant fonctionner avec N thread, version due à Edsger Dijkstra.
  • L'algoritmo di Dekker, noto anche come algoritmo di proiezione di Dijkstra, costituisce una soluzione completa al problema della mutua esclusione nella coordinazione decentrata di processi (sincronizzazione), impedendo lo stallo (deadlock) ed assicurando che soltanto un processo alla volta possa eseguire una sezione critica (serializzazione). Tale algoritmo è attribuito al matematico olandese Th. J. Dekker da Edsger W. Dijkstra nel suo manoscritto sui processi cooperanti sequenziali.
  • デッカーのアルゴリズムはオランダ人数学者 T・J・デッカーの考案した相互排他のためのアルゴリズムである。これにより、共有メモリによる通信のみで、2つのプロセスが1つのリソースを競合することなく共有することができる。 厳密に交互にとっていく素朴なアルゴリズムを避けて発明された世界初の相互排他アルゴリズムの1つである。 ふたつのプロセスが同時に同じクリティカルセクションにアクセスしようとしたとき、このアルゴリズムはどちらのプロセスがアクセス権を得るかを決定する。もしもう一方のプロセスが既にクリティカルセクションに変更を加えていたら、その完了を待つ。 f0 := false f1 := false turn := 0 // or 1 p0: f0 := true p1: f1 := true while f1 = true { while f0 = true { if turn ≠ 0 { if turn ≠ 1 { f0 := false f1 := false while turn ≠ 0 { while turn ≠ 1 { } } f0 := true f1 := true } } } } // Start of Critical Section ・・・ // End of Critical Section turn := 1 turn := 0 f0 := false f1 := false
  • Algorytm Dekkera – pierwszy algorytm poprawnie rozwiązujący problem wzajemnego wykluczania się równolegle działających procesów. Tylko jeden z nich może w danej chwili wykonywać ich wspólną sekcję krytyczną (zob. programowanie współbieżne). Rozwiązanie to zostało przypisane holenderskiemu matematykowi T. J. Dekkerowi przez Edsgera Dijkstrę w jego manuskrypcie na temat współdziałania procesów sekwencyjnych. Algorytm pozwala dwóm wątkom na bezkonfliktową pracę na danych pochodzących z jednego źródła przy użyciu do komunikacji między nimi jedynie pamięci dzielonej.
  • Алгоритм Деккера — первое известное корректное решение проблемы взаимного исключения в параллельном программировании. Эдсгер Дейкстра ссылается на голландского математика Т. Деккера как на автора данного алгоритма в своей работе о межпроцессном взаимодействии. Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации.
http://purl.org/voc/vrank#hasRank
http://purl.org/li...ics/gold/hypernym
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git39 as of Aug 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3232 as of Aug 9 2019, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2019 OpenLink Software