Welche praktische Relevanz haben Algorithmen zum gegenseitigen Ausschluss von Lehrbüchern?

Es wurde viel über Algorithmen zum gegenseitigen Ausschluss geforscht - z. B. wird ein Großteil davon in klassischen Lehrbüchern wie The Art of Multiprocessor Programming vorgestellt , in denen ihnen ein ganzes Kapitel gewidmet ist.

Ich frage mich, in welchen praktischen Situationen diese Algorithmen möglicherweise während des Engineerings eines gleichzeitigen Systems benötigt werden, anstatt typische sprach- und betriebssystembasierte Synchronisationsprimitive zu verwenden (z. B. von der pthread-Bibliothek bereitgestellt).

Ich kann mir viele Sonderfälle vorstellen, in denen ich mir vorstellen würde, dass die Standardprimitive nicht speziell auf sie abgestimmt sind, z. B. "ein häufiger Leser und ein seltener Schreiber" oder umgekehrt oder "genau eine Schreiboperation, viele Leser" usw. - Ist einer der Lehrbuch-Algorithmen zum gegenseitigen Ausschluss in solchen Situationen in der Praxis wesentlich besser?

Um es kurz zu machen: Welche Algorithmen für den gegenseitigen Ausschluss sind für einen Ingenieur von praktischer Relevanz, der bereits über eine typische sprachbasierte Bibliothek von Parallelitätsprimitiven verfügt?

Antwort: keine. Darum geht es in diesen Abschnitten von Herlihy und Shavits The Art of Multiprocessor Programming nicht. In den Kapiteln zum gegenseitigen Ausschluss geben Herlihy und Shavit Ihnen keine Alternativen zur pthreadBibliothek, sondern zeigen Ihnen, wie sie das Äquivalent der Bibliothek implementierenpthread .

Kapitel 2 von Herlihy und Shavit trägt den Titel "Gegenseitiger Ausschluss". Es bietet eine Vielzahl klassischer Algorithmen zur Implementierung des Äquivalents pthread_mutex_lock()mit nur sequentiell konsistentem gemeinsam genutztem Speicher. Meine Antworten https://cs.stackexchange.com/a/12632/7459 und https://cs.stackexchange.com/a/30249/7459 diskutieren die Bedeutung dieser Implementierungen und haben einen Zeiger auf eine, die für praktisch ist Verwendung auf Computern ohne integrierte Hardware-Synchronisierungsvorgänge. (Lamports 1987er Artikel in ACM Trans. On Computer Systems).

Kapitel 7 von Herlihy und Shavit enthält eine Vielzahl von Spin- und Queue-Lock-Implementierungen, die dem Äquivalent von entsprechen pthread_mutex_lock(), und Kapitel 8 wird erweitert, um pthread_cond_t(Bedingungsvariablen) pthread_rwlock_t(Lese- / Schreibsperren) zu diskutieren und kurz darauf einzugehen semaphores. Es kann Situationen geben, in denen aus Leistungsgründen (aber normalerweise nicht) pthread_rwlock_teine Alternative verwendet werden kann, pthread_lock_tund in Posix müssen Sie diese semaphoresfür die Synchronisation zwischen Prozessen verwenden.

In den Kapiteln 9 bis 16 werden hauptsächlich Anwendungen (verschiedene Arten von gleichzeitigen Containern) behandelt. Kapitel 17 beschreibt kurz das Äquivalent von pthread_barrier_t.

Alles in allem sind Herlihy und Shavit zwei der lautstärksten Befürworter des Transaktionsgedächtnisses und einer Vielzahl von Arten der nicht blockierenden (und wartungsfreien) Synchronisation. Diese Techniken sind in bestimmten Fällen als Alternativen zum gegenseitigen Ausschluss gedacht . Herlihy und Shavit streuen in den Kapiteln 9 bis 16 verschiedene nicht blockierende Implementierungen und gehen dann in Kapitel 18 auf das Transaktionsgedächtnis ein.

Transaktionsspeicher und andere nicht blockierende Synchronisationstechniken sollen das Problem lösen, dass einige schlecht entworfene Algorithmen Threads erfordern, um ihre kritischen Abschnitte für eine sehr lange Zeit zu halten. Transaktionsspeicher und wirklich nicht blockierende Synchronisation sind derzeit in keiner realen Situation praktische Alternativen, aber die Techniken zum Transformieren blockierender Datenstrukturen in nicht blockierende Datenstrukturen sind in der Praxis nützlich, um die Zeit zu minimieren, die eine blockierende Datenstruktur in ihrem kritischen Bereich verbleibt Sektion. (Oft können Sie die Größe des kritischen Abschnitts auf nur ein paar Maschinenanweisungen reduzieren.)