Synchronisation (Informatik)

Im Informatik, Synchronisation bezieht sich auf eines von zwei unterschiedlichen, aber verwandten Konzepten: Synchronisation von Prozesseund Synchronisation von Daten. Prozesssynchronisation bezieht sich auf die Idee, dass mehrere Prozesse zusammenarbeiten sollen oder Handschlag Zu einem bestimmten Zeitpunkt, um eine Vereinbarung zu erreichen oder sich zu einer bestimmten Abfolge von Maßnahmen zu verpflichten. Datensynchronisation bezieht sich auf die Idee, mehrere Kopien eines Datensatzes in Kohärenz miteinander zu halten oder zu warten Datenintegrität. Prozesssynchronisation Primitive werden üblicherweise zur Implementierung der Datensynchronisation verwendet.

Die Notwendigkeit einer Synchronisation

Die Notwendigkeit einer Synchronisation erfolgt nicht nur in Multi-Processor-Systemen, sondern für jegliche Art von gleichzeitigen Prozessen. Auch in einzelnen Prozessorsystemen. Nachfolgend sind einige der Hauptbedürfnisse für die Synchronisation erwähnt:

Gabeln und Beiträge: Wenn ein Job an einem Gabelpunkt ankommt, wird er in n Subjobs aufgeteilt, die dann von N-Aufgaben gewartet werden. Nach der Wartung wartet jeder Subjob, bis alle anderen Subjobs verarbeitet werden. Dann werden sie wieder verbunden und verlassen das System. Die parallele Programmierung erfordert daher eine Synchronisation, da alle parallelen Prozesse auf mehrere andere Prozesse warten.

Produzenten-Verbraucher: In einer Erzeuger-Verbraucher-Beziehung hängt der Verbraucherprozess vom Erzeugerprozess ab, bis die erforderlichen Daten erstellt wurden.

Exklusive Nutzungsressourcen: Wenn mehrere Prozesse von einer Ressource abhängen und gleichzeitig darauf zugreifen müssen, muss das Betriebssystem sicherstellen, dass nur ein Prozessor zu einem bestimmten Zeitpunkt darauf zugreift. Dies reduziert die Parallelität.

Faden- oder Prozesssynchronisation

Abbildung 1: Drei Prozesse, die auf eine gemeinsame Ressource zugreifen (Kritischer Abschnitt) gleichzeitig.

Die Fadensynchronisation ist definiert als ein Mechanismus, der sicherstellt, dass zwei oder mehr gleichzeitig gleichzeitig Prozesse oder Themen Führen Sie nicht gleichzeitig ein bestimmtes Programmsegment aus, das als als bekannt ist Kritischer Abschnitt. Der Zugriff der Prozesse auf einen kritischen Abschnitt wird unter Verwendung von Synchronisationstechniken gesteuert. Wenn ein Thread beginnt, die auszuführen Kritischer Abschnitt (Serialisiertes Segment des Programms) Der andere Thread sollte warten, bis der erste Thread beendet ist. Wenn richtige Synchronisationstechniken[1] werden nicht angewendet, es kann a verursachen Rassenbedingung wobei die Werte von Variablen unvorhersehbar sein können und je nach Zeitpunkt von variieren können Kontextschalter der Prozesse oder Fäden.

Nehmen wir beispielsweise an, dass es drei Prozesse gibt, nämlich 1, 2 und 3. alle drei von ihnen, und sie müssen eine gemeinsame Ressource (kritischer Abschnitt) teilen, wie in Abbildung 1 dargestellt. Synchronisation sollte hier verwendet werden Vermeiden Sie Konflikte für den Zugriff auf diese gemeinsame Ressource. Wenn der Prozess 1 und 2 beide versuchen, auf diese Ressource zuzugreifen, sollte sie jeweils nur einem Prozess zugewiesen werden. Wenn es dem Prozess 1 zugewiesen ist, muss der andere Prozess (Prozess 2) warten, bis der Prozess 1 diese Ressource befreit (wie in Abbildung 2 gezeigt).

Figur 2: Ein Prozess, der auf eine gemeinsame Ressource zugreift, falls verfügbar, basierend auf einer Synchronisationstechnik.

Eine weitere Synchronisationsanforderung, die berücksichtigt werden muss, ist die Reihenfolge, in der bestimmte Prozesse oder Threads ausgeführt werden sollten. Zum Beispiel kann man vor dem Kauf eines Tickets nicht in ein Flugzeug einsteigen. In ähnlicher Weise kann man E-Mails nicht überprüfen, bevor die entsprechenden Anmeldeinformationen bestätigt werden (z. B. Benutzername und Kennwort). Auf die gleiche Weise bietet ein Geldautomaten keinen Service an, wenn er eine korrekte PIN erhält.

Abgesehen von der gegenseitigen Ausgrenzung befasst sich auch die Synchronisation mit den folgenden:

  • Sackgasse, was auftritt, wenn viele Prozesse auf eine gemeinsame Ressource (kritischer Abschnitt) warten, die von einem anderen Prozess gehalten wird. In diesem Fall warten die Prozesse einfach weiter und führen nicht weiter aus.
  • Hunger, was auftritt, wenn ein Prozess darauf wartet, den kritischen Abschnitt zu betreten, aber andere Prozesse monopolisieren den kritischen Abschnitt, und der erste Prozess ist gezwungen, unbegrenzt zu warten.
  • Prioritätsinversion, was auftritt, wenn sich ein hoher Prioritätsprozess im kritischen Abschnitt befindet, und wird durch einen Prozess mit mittlerer Priorität unterbrochen. Dieser Verstoß gegen die Vorrangsregeln kann unter bestimmten Umständen erfolgen und zu schwerwiegenden Folgen in Echtzeitsystemen führen.
  • beschäftigt zu warten, was auftritt, wenn ein Prozess häufig umfragt, um festzustellen, ob er Zugriff auf einen kritischen Abschnitt hat. Diese häufige Umfrage raubt die Verarbeitungszeit aus anderen Prozessen.

Minimierung der Synchronisation

Eine der Herausforderungen für das Design des Exascale -Algorithmus besteht darin, die Synchronisation zu minimieren oder zu reduzieren. Die Synchronisation braucht mehr Zeit als die Berechnung, insbesondere beim verteilten Computer. Die Reduzierung der Synchronisation lenkt jahrzehntelang von Informatikern auf die Aufmerksamkeit. Während es in letzter Zeit zu einem immer erheblichen Problem wird, wenn die Lücke zwischen der Verbesserung von Computer und Latenz zunimmt. Experimente haben gezeigt, dass (globale) Kommunikation aufgrund der Synchronisation auf verteilten Computern einen dominierten Anteil an einem spärlichen iterativen Löser entspricht.[2] Dieses Problem wird nach dem Auftreten einer neuen Benchmark -Metrik, des Hochleistungs -Konjugat -Gradienten (HPCG), zunehmend Aufmerksamkeit erhalten.[3] zum Rankieren der Top 500 Supercomputer.

Klassische Probleme der Synchronisation

Das Folgende sind einige klassische Probleme der Synchronisation:

Diese Probleme werden verwendet, um nahezu jedes neu vorgeschlagene Synchronisationsschema oder primitive Synchronisationsschema zu testen.

Hardware -Synchronisation

Viele Systeme bieten Hardwareunterstützung für Kritischer Abschnitt Code.

Ein einzelner Prozessor oder UniProcessor -System könnte deaktivieren Interrupts Durch Ausführen von aktueller Code ohne Ausführung ohne Präsentation, was sehr ineffizient ist Multiprozessor Systeme.[4] "Die wichtigste Fähigkeit, die wir für die Implementierung der Synchronisation in einem Multiprozessor benötigen Die Prozessorzahl nimmt zu. Es gibt eine Reihe alternativer Formulierungen der grundlegenden Hardware -Primitiven, die alle die Möglichkeit bieten, einen Ort atomisch zu lesen und zu ändern, zusammen mit einer Möglichkeit, zu erkennen, ob das Lese- und Schreiben atomisch durchgeführt wurde. Diese Hardware -Primitiven wurden durchgeführt. sind die grundlegenden Bausteine, mit denen eine Vielzahl von Synchronisierungsvorgängen auf Benutzerebene erstellt wird, einschließlich Dingen wie z. Schlösser und Barrieren. Im Allgemeinen erwarten Architekten nicht, dass Benutzer die grundlegenden Hardware -Primitiven einsetzen, sondern erwarten, dass die Primitiven von Systemprogrammierern verwendet werden, um eine Synchronisierungsbibliothek zu erstellen, ein Prozess, der häufig komplex und schwierig ist. "[5] Viele moderne Hardware bieten spezielle Atomic -Hardware -Anweisungen von beiden testen und einstellen das Gedächtniswort oder vergleiche und swap Inhalt von zwei Gedächtniswörtern.

Synchronisationsstrategien in Programmiersprachen

Im JavaUm Fehlern von Thread -Störungen und Speicherkonsistenz zu verhindern, werden Codeblöcke eingebunden synchronisiert (lock_object) Abschnitte. Dies zwingt jeden Thread, das besagte Sperrobjekt zu erwerben, bevor er den Block ausführen kann. Das Schloss wird automatisch freigegeben, wenn der Thread, der das Schloss erworben hat, und dann den Block ausführt, den Block verlässt oder in den Wartezustand innerhalb des Blocks eingeht. Alle variablen Updates, die von einem Thread in einem synchronisierten Block erstellt wurden, werden für andere Threads sichtbar, wenn sie das Sperre in ähnlicher Weise erwerben und den Block ausführen.

Java synchronisiert Blocks ermöglichen zusätzlich zum Aktivieren der gegenseitigen Ausschluss und der Speicherkonsistenz die Signalisierung - d. H. Senden von Ereignissen aus Threads, die das Sperre erfasst haben und den Codeblock an diejenigen ausführen, die auf die Sperre innerhalb des Blocks warten. Dies bedeutet, dass Java -synchronisierte Abschnitte die Funktionalität von Mutexen und Ereignissen kombinieren. Solch ein primitiv ist bekannt als als Synchronisationsmonitor.

Jedes Objekt kann als Sperre/Monitor in Java verwendet werden. Das deklarierende Objekt ist ein Sperrobjekt, wenn die gesamte Methode mit markiert ist synchronisiert.

Das .NET Framework hat Synchronisation Primitive. "Die Synchronisation ist als kooperativ ausgelegt und fordert, dass jeder Thread oder Prozess den Synchronisationsmechanismus folgt, bevor er auf geschützte Ressourcen (kritischer Abschnitt) für konsistente Ergebnisse zugreift." In .NET, Verriegelung, Signalisierung, leichte Synchronisationstypen, Spinwait und ineinandergreifende Operationen sind einige der Mechanismen, die mit der Synchronisation zusammenhängen.[6]

Implementierung der Synchronisation

Spinlock

Eine weitere effektive Methode zur Implementierung der Synchronisation ist die Verwendung von Spinlocks. Vor dem Zugriff auf gemeinsame Ressourcen oder Code -Stück -Code überprüft jeder Prozessor ein Flag. Wenn das Flag zurückgesetzt wird, setzt der Prozessor das Flag und führt den Thread fort. Wenn das Flag jedoch eingestellt ist (gesperrt), würden sich die Threads weiter in einer Schleife drehen und überprüfen, ob das Flag eingestellt ist oder nicht. Spinlocks sind jedoch nur dann wirksam, wenn das Flag für niedrigere Zyklen zurückgesetzt wird. Andernfalls kann es zu Leistungsproblemen führen, da viele Prozessorzyklen warten.[7]

Barrieren

Barrieren sind einfach zu implementieren und bieten eine gute Reaktionsfähigkeit. Sie basieren auf dem Konzept der Implementierung von Wartezyklen, um eine Synchronisation bereitzustellen. Betrachten Sie drei Threads, die gleichzeitig ausgeführt werden, beginnend mit Barriere 1. Nach T Thread1 erreicht Thread1 die Barriere 2, muss jedoch noch auf Thread 2 und 3 warten, um Barrier2 zu erreichen, da es nicht die richtigen Daten hat. Sobald alle Fäden Barriere 2 erreicht haben, beginnen sie alle von vorne. Nach T -T -Thread 1 erreicht Thread 1 Barrier3, muss jedoch wieder auf Threads 2 und 3 und die richtigen Daten warten.

Bei der Barriere -Synchronisation mehrerer Threads gibt es immer einige Threads, die auf andere Threads warten, wie im obigen Beispiel Thread 1 wartet immer wieder auf Thread 2 und 3. Dies führt zu einem starken Abbau der Prozessleistung.[8]

Die Barriersynchronisation Wartefunktion für ith Thread kann dargestellt werden als:

(WBarrier) i = f ((tBarrier) i, (rThread) i)

Wo WBarrier die Wartezeit für einen Thread ist, ist Tbarrier die Anzahl der Threads, und RThread ist die Ankunftsrate der Fäden.[9]

Experimente zeigen, dass 34% der Gesamtausführungszeit für andere langsamere Fäden aufgewartet werden.[8]

Semaphoren

Semaphoren sind Signalmechanismen, mit denen ein oder mehrere Threads/Prozessoren auf einen Abschnitt zugreifen können. Ein Semaphor verfügt über ein Flag, das einen bestimmten festen Wert zugeordnet ist. Jedes Mal, wenn ein Thread auf den Abschnitt zugreifen möchte, wird das Flag verringert. In ähnlicher Weise wird das Flag, wenn der Faden den Abschnitt verlässt, erhöht. Wenn das Flag Null ist, kann der Thread nicht auf den Abschnitt zugreifen und wird blockiert, wenn er wartet.

Einige Semaphoren würden im Abschnitt Code nur einen Thread oder einen Prozess zulassen. Solche Semaphoren werden als binäres Semaphor bezeichnet und sind Mutex sehr ähnlich. Wenn der Wert des Semaphors 1 ist, darf der Thread zugreifen und wenn der Wert 0 ist, wird der Zugriff verweigert.[10]

Mathematische Grundlagen

Die Synchronisation war ursprünglich ein prozessbasiertes Konzept, bei dem ein Schloss auf einem Objekt erhalten werden konnte. Die Hauptverwendung war in Datenbanken. Es gibt zwei Arten von (Datei) sperren; schreibgeschützte und lesen-Schreiben Sie. Schreibgeschützte Schlösser können durch viele Prozesse oder Threads erhalten werden. Leser - Schreiberschlösser sind exklusiv, da sie möglicherweise nur von einem einzelnen Prozess/Thread gleichzeitig verwendet werden.

Obwohl Sperren für Dateidatenbanken abgeleitet wurden, werden Daten auch im Speicher zwischen Prozessen und Threads gemeinsam genutzt. Manchmal wird mehr als ein Objekt (oder eine Datei) gleichzeitig gesperrt. Wenn sie nicht gleichzeitig gesperrt sind, können sie sich überlappen, was zu einer Deadlock -Ausnahme führt.

Java und Ada haben nur exklusive Schlösser, weil sie auf Thread basieren und sich auf die verlassen vergleiche und swap Prozessoranweisung.

Eine abstrakte mathematische Grundlage für Synchronisation Primitive wird durch die gegeben Geschichte Monoid. Es gibt auch viele theoretische Geräte auf höherer Ebene, wie z. Prozesskalkül und Petri Nets, die auf der Geschichte Monoid aufgebaut werden kann.

Synchronisationsbeispiele

Im Folgenden finden Sie einige Synchronisationsbeispiele in Bezug auf verschiedene Plattformen.[11]

Synchronisation in Windows

Fenster bietet:

Synchronisation unter Linux

Linux bietet:

Aktivieren und Deaktivieren der Kernel -Präsentation ersetzt Spinlocks auf UniCessor -Systemen. Vor Kernel Version 2.6, Linux Deaktiviert unterbrechen, um kurze kritische Abschnitte zu implementieren. Seit Version 2.6 und später ist Linux vollständig präventiv.

Synchronisation in Solaris

Solaris bietet:

  • Semaphoren;
  • Zustandsvariablen;
  • Adaptive Mutexes, binäre Semaphoren, die je nach Bedingungen unterschiedlich implementiert werden;
  • Leser - Schalterschlösser:
  • Drehkreuze, Warteschlange von Threads, die auf erworbenes Schloss warten.[13]

Pthreads -Synchronisation

Phreads ist eine plattformunabhängige API das liefert:

  • Mutexes;
  • Zustandsvariablen;
  • Leser -Schalterschlösser;
  • Spinlocks;
  • Barrieren.

Datensynchronisation

Figur 3: Änderungen vom Server und Clients (s) werden synchronisiert.

Ein deutlich anderes (aber verwandtes) Konzept ist das von Datensynchronisation. Dies bezieht sich auf die Notwendigkeit, mehrere Kopien einer Reihe von Daten miteinander zu übernehmen oder zu warten DatenintegritätAbbildung 3. Beispielsweise wird die Datenbankreplikation verwendet, um mehrere Kopien von Daten mit Datenbankservern synchronisiert zu halten, die Daten an verschiedenen Stellen speichern.

Beispiele beinhalten:

  • Dateisynchronisation, wie das Synchronisieren eines handgehaltenen MP3-Players auf einen Desktop-Computer;
  • Cluster -Dateisysteme, welche sind Dateisysteme Dadurch werden Daten oder Indizes in einer Ganze zusammengefasst Computercluster;
  • Cache -KohärenzAufrechterhaltung mehrerer Kopien von Daten synchronisiert über mehrere Caches;
  • ÜBERFALLEN, wo Daten überflüssig über mehrere Festplatten geschrieben werden, so dass der Verlust einer Festplatte nicht zu einem Datenverlust führt;
  • Datenbankreplikation, wo Kopien von Daten auf a Datenbank werden synchron gehalten, trotz möglicher großer geografischer Trennung;
  • Tagebuch schreiben, Eine Technik, die von vielen modernen Dateisystemen verwendet wird, um sicherzustellen, dass die Dateimetadaten auf einer Festplatte in einer kohärenten, konsistenten Weise aktualisiert werden.

Herausforderungen bei der Datensynchronisation

Einige der Herausforderungen, denen sich der Benutzer bei der Datensynchronisation stellen kann:

  • Datenformate Komplexität;
  • Realitätszeit;
  • Datensicherheit;
  • Datenqualität;
  • Leistung.

Datenformate Komplexität

Datenformate wachsen tendenziell komplexer mit der Zeit, wenn die Organisation wächst und sich weiterentwickelt. Dies ergibt sich nicht nur beim Erstellen einfacher Schnittstellen zwischen den beiden Anwendungen (Quelle und Ziel), sondern auch, um die Daten zu transformieren, während sie an die Zielanwendung weitergegeben werden. ETL (Extraktionstransformationsbelastung) Tools können in dieser Phase hilfreich sein, um die Komplexität des Datenformates zu verwalten.

Realitätszeit

In Echtzeitsystemen möchten Kunden den aktuellen Status ihrer Bestellung in E-Shop, den aktuellen Status einer Paket-Lieferung-eine Echtzeit-Paketverfolgung-, den aktuellen Saldo auf ihrem Konto usw. sehen. Dies zeigt die Notwendigkeit von Bedarf an Ein Echtzeitsystem, das ebenfalls aktualisiert wird, um einen reibungslosen Herstellungsprozess in Echtzeit zu ermöglichen, z. B. Bestellmaterial, wenn Unternehmensbestand auf Lager wird, Kundenaufträge mit dem Herstellungsprozess usw. synchronisieren usw. aus dem wirklichen Leben gibt es so viele, so viele gibt es so viele Beispiele, bei denen die Echtzeitverarbeitung erfolgreiche und wettbewerbsfähige Vorteile bietet.

Datensicherheit

Es gibt keine festen Regeln und Richtlinien zur Durchsetzung der Datensicherheit. Es kann abhängig von dem System, das Sie verwenden, variieren. Obwohl die Sicherheit korrekt im Quellsystem gewartet wird, das die Daten erfasst, müssen die Berechtigungen für Sicherheit und Informationszugriff auch für die Zielsysteme durchgesetzt werden, um potenzielle Missbrauch der Informationen zu verhindern. Dies ist ein ernstes Problem und insbesondere wenn es darum geht, geheime, vertrauliche und persönliche Informationen zu behandeln. Aufgrund der Sensibilität und Vertraulichkeit müssen die Datenübertragung und alle Zwischeninformationen verschlüsselt werden.

Datenqualität

Die Datenqualität ist eine weitere schwerwiegende Einschränkung. Um eine bessere Verwaltung und eine gute Datenqualität aufrechtzuerhalten, besteht die gängige Praxis darin, die Daten an einem Ort zu speichern und mit verschiedenen Personen und unterschiedlichen Systemen und/oder Anwendungen von verschiedenen Standorten zu teilen. Es hilft bei der Verhinderung von Inkonsistenzen in den Daten.

Leistung

Am Datensynchronisationsprozess sind fünf verschiedene Phasen beteiligt:

Jeder dieser Schritte ist kritisch. Bei großen Datenmengen muss der Synchronisationsprozess sorgfältig geplant und ausgeführt werden, um negative Auswirkungen auf die Leistung zu vermeiden.

Siehe auch

Verweise

  1. ^ Gramoli, V. (2015). Mehr als Sie jemals über die Synchronisation wissen wollten: Synchroben, Messung der Auswirkungen der Synchronisation auf gleichzeitige Algorithmen (PDF). Verfahren des 20. ACM -Sigplan -Symposiums über Prinzipien und Praxis paralleler Programmierung. ACM. S. 1–10.
  2. ^ Shengxin, Zhu und Tongxiang Gu und Xingping Liu (2014). "Minimierung der Synchronisationen in spärlichen iterativen Löser für verteilte Supercomputer". Computer und Mathematik mit Anwendungen. 67 (1): 199–209. doi:10.1016/j.camwa.2013.11.008.
  3. ^ "HPCG Benchmark".
  4. ^ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (11. Juli 2008). "Kapitel 6: Prozesssynchronisation". Betriebssystemkonzepte (Achte Ausgabe). John Wiley & Sons. ISBN 978-0-470-12872-5.
  5. ^ Hennessy, John L.; Patterson, David A. (30. September 2011). "Kapitel 5: Parallelität auf Thread-Ebene". Computerarchitektur: Ein quantitativer Ansatz (Fünfter Aufl.). Morgan Kaufmann. ISBN 978-0-123-83872-8.
  6. ^ "Synchronisation Primitive in .NET Framework". MSDN, das Microsoft Developer -Netzwerk. Microsoft. Abgerufen 23. November 2014.
  7. ^ Massa, Anthony (2003). Eingebettete Softwareentwicklung mit ECOs. Pearson Education Inc. ISBN 0-13-035473-2.
  8. ^ a b Meng, Chen, Pan, Yao, Wu, Jinglei, Tianzhou, Ping, Jun. Minghui (2014). "Ein spekulativer Mechanismus für die Barriere -Sychronisation". 2014 IEEE International Conference für Hochleistungs -Computing and Communications (HPCC), 2014 IEEE 6. Internationales Symposium für Cyberspace Safety and Security (CSS) und 2014 IEEE 11. International Conference on Embedded Software and Systems (ICESS).{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  9. ^ Rahman, Mohammed Mahmudur (2012). "Prozesssynchronisation im Multiprozessor und im Multi-Core-Prozessor". 2012 Internationale Konferenz über Informatik, Elektronik und Vision (ICIEV). S. 554–559. doi:10.1109/iciev.2012.6317471. ISBN 978-1-4673-1154-0.
  10. ^ Li, Yao, Qing, Carolyn (2003). Echtzeitkonzepte für eingebettete Systeme. CMP -Bücher. ISBN 978-1578201242.
  11. ^ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (7. Dezember 2012). "Kapitel 5: Prozesssynchronisation". Betriebssystemkonzepte (Neunte Ausgabe). John Wiley & Sons. ISBN 978-1-118-06333-0.
  12. ^ "Was ist RCU grundsätzlich? [Lwn.net]". lwn.net.
  13. ^ Mauro, Jim. "Drehkreuze und Prioritätserbanz - Sunworld - August 1999". sunsite.uakom.sk.
  • Schneider, Fred B. (1997). Bei gleichzeitiger Programmierung. Springer-Verlag New York, Inc. ISBN 978-0-387-94942-0.

Externe Links