PatentDe  


Dokumentenidentifikation DE69926820T2 29.06.2006
EP-Veröffentlichungsnummer 0000932101
Titel Verfahren, Anordnung und Rechnerprogrammprodukt zur Verriegelung von verbundenen Datenstrukturen in einer multithreading-fähigen Rechnerumgebung
Anmelder Sun Microsystems, Inc., Mountain View, Calif., US
Erfinder Furlani, John L., Palo Alto, California 94301, US;
Ohlson, Alexandra R., Palo Alto, California 94301, US
Vertreter Kahler, Käck & Mollekopf, 86899 Landsberg
DE-Aktenzeichen 69926820
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 13.01.1999
EP-Aktenzeichen 991003393
EP-Offenlegungsdatum 28.07.1999
EP date of grant 24.08.2005
Veröffentlichungstag im Patentblatt 29.06.2006
IPC-Hauptklasse G06F 9/46(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]
Gebiet der Erfindung

Diese Erfindung betrifft das Gebiet der Verriegelung von Datenstrukturen in einer multithreading-fähigen Rechnerumgebung. Insbesondere betrifft diese Erfindung ein Verfahren, eine Vorrichtung und ein Computerprogrammprodukt zum Verriegeln von zusammenhängenden Gruppen von Datenstrukturen in einer multithreading-fähigen Rechnerumgebung.

Hintergrund

Datenstrukturen enthalten eine organisierte Information in einem Computerspeicher. Jede dieser Datenstrukturen kann von anderen Datenstrukturen unabhängig sein oder mit diesen zusammenhängen. Der Zugriff auf die Datenstrukturen ist einfach, wenn der Zugriff in einer Rechnerumgebung stattfindet, die einen einzigen Ausführungsablauf (Ausführungsthread) aufweist, da die Daten in den zusammenhängenden Datenstrukturen während der Ausführung des einzelnen Threads immer konsistent sind. Wenn jedoch eine asynchrone Operation stattfindet (wie z.B. eine Unterbrechung, eine Prozesskontextumschaltung oder eine ähnliche Operation, die einen gleichzeitigen Zugriff auf die Datenstruktur ermöglicht), kann der Inhalt der Datenstruktur inkonsistent gemacht werden, wenn eine asynchrone Operation die Datenstruktur ändert, während eine andere Operation auf die Datenstruktur zugreift. Moderne Rechnersysteme verwenden häufig Ausführungsthreads, um Computeroperationen parallel zu machen.

Ein Ausführungsthread (ein Thread) ist eine Steuersequenz innerhalb eines programmierten Prozesses. Ein herkömmlicher einfachthreading-fähiger programmierter Prozess folgt während der Ausführung einer einzelnen Steuersequenz. Ein multithreading-fähiger programmierter Prozess weist mehrere Steuersequenzen auf und ist zu mehreren unabhängigen Handlungen in der Lage. Eine spezielle Implementierung einer multithreading-fähigen Rechnerumgebung ist in SunOS Multi-thread Architecture, von Powell, Kleiman, Barton, Shah, Stein und Weeks, USENIX, Winter 1991, Seite 65, erörtert. Posi®-Threads sind in Programming with POSIX Threads von David R. Butenhof, © 1997, von Addison Wesley Longman, Inc., ISBN 0-201-63392-2, Seiten 35–95, beschrieben.

Die anschließend offenbarte Erfindung wird im Zusammenhang mit einem objektorientierten Programmierungs- (OOP) Musterbeispiel beschrieben. Das OOP-Musterbeispiel verwendet Objekte. Objekte ordnen Daten eines Objekts OOP-Verfahren zum Verarbeiten der Daten dieses Objekts zu. Gewöhnlich werden OOP-Objekte in einem Freispeicherbereich konkret dargestellt und basieren auf Klassen, die auf die programmierten Verfahren für das OOP-Objekt verweisen. Auf konkret dargestellte OOP-Objekte wird durch Zeiger Bezug genommen und sie enthalten Daten (in Feldern), die für dieses spezielle konkret dargestellte OOP-Objekt spezifisch sind. Vorstellungsgemäß enthält ein OOP-Objekt eine mit dem Objekt in Zusammenhang stehende Information (wie z.B. die Anzahl von Feldern im Objekt), Datenstrukturen zum Speichern der Felder des Objekts und Adressen von aufgerufenen Routinen (OOP-Verfahren), die auf den Inhalt der Felder im Objekt zugreifen und/oder diesen verarbeiten. Da jedoch Objekte häufig aufgerufene Routinen und eine mit dem Objekt in Zusammenhang stehende Information gemeinsam nutzen, wird diese gemeinsam genutzte Information gewöhnlich in eine Klasse extrahiert. Somit enthält das konkret dargestellte Objekt einfach seine Felder und einen Zeiger auf seine Klasse. Eine weitere Information über OOP-Konzepte ist in Not Just Java von Peter van der Linden, Sun Microsystems Press/Prentice Hall PTR Corp., Upper Saddle River, NJ, (1997), ISBN 0-13-864638-4, Seiten 136–149, zu finden.

Datenstrukturen können auch innerhalb des OOP-Musterbeispiels als Objekte behandelt werden. Solche Datenstrukturobjekte umfassen die konkret dargestellten Daten, die die Datenstruktur bilden, programmierte Verfahren, um auf diese Daten zuzugreifen, und potentielle Verkettungen mit anderen Datenstrukturobjekten.

Eine nützliche Datenstruktur für Bildverarbeitungszwecke (und viele anderen Zwecke) ist ein modifizierter gerichteter azyklischer Graph (DAG), der Bilder und die Operationen, die auf diese Bilder angewendet werden, darstellt. Die DAG-Elemente können als Objekte dargestellt werden. Ein oder mehrere DAGs können durch eine Abbildungsbibliothek konstruiert werden, wenn die Bibliothek eine Reihe von Abbildungsoperationen erfasst, die auf ein oder mehrere Quellenbilder gerichtet sind. Die resultierenden DAGs sind innerhalb einer Objektsammlung enthalten. Die Objektsammlung enthält im Allgemeinen sowohl unabhängige als auch zusammenhängende DAG-Objekte. Unabhängige Objekte sind diejenigen, die nicht von anderen Objekten abhängen. Zusammenhängende Objekte greifen aufeinander zu, um ihre Operation durchzuführen. Ein unabhängiges Objekt kann durch einen Thread verriegelt werden, um einen ausschließlichen Zugriff auf den Thread sicherzustellen. Um ein zusammenhängendes Objekt zu verriegeln, muss jedoch jedes zusammenhängende Objekt auch verriegelt werden, um sicherzustellen, dass die Information im Objekt nicht durch einen zweiten Thread geändert wird, während ein erster Thread arbeitet.

Eine Methode des Standes der Technik zum Verriegeln von Objekten verwendet einen Mutex, um den Threadzugriff auf die Objektsammlung zu serialisieren. Die Schwierigkeit bei dieser Methode besteht darin, dass, während ein Thread Objekte in der Objektsammlung verarbeitet, andere Threads dies nicht können. Folglich können unabhängige Operationen, die durch Threads gesteuert werden, die auf ein Objekt in der Objektsammlung zugreifen müssen, den Zugriff nicht durchführen, bis der verriegelnde Thread die Objektsammlung freigibt. Diese Methode begrenzt die Vorteile einer multithreading-fähigen Rechnerumgebung, indem die Objektsammlung zu einem blockierenden Betriebsmittel gemacht wird.

Eine weitere Methode des Standes der Technik weist einen Mutex (im Allgemeinen innerhalb eines Steuerobjekts) zu, um den Zugriff auf jede Gruppe von Objekten zu serialisieren, die in der Objektsammlung zusammenhängen können. Somit kann die Objektsammlung mehrere Steuerobjekte aufweisen, die jeweils den Zugriff auf eine unabhängige Gruppe der Objektsammlung steuern, wobei jede Gruppe Objekte enthält, die untereinander zusammenhängen können. Die Schwierigkeit bei dieser Methode des Standes der Technik besteht darin, dass das Steuerobjekt verwendet wird, um den Zugriff auf eine Gruppe von Objekten zu steuern, von denen angenommen wird, dass sie zusammenhängen, aber häufig nicht tatsächlich zusammenhängen. Dies bedeutet, dass die Steuerobjekte übereinschließend sind und mehr als die erforderlichen Objekte verriegeln. Dies führt zu einer erhöhten Threadblockierung und folglich einer verringerten Leistung.

GB 2 301 204 A offenbart ein Datenverarbeitungssystem und -verfahren zum gleichzeitigen Verarbeiten von Datenobjekten. Um in Konflikt stehende Zugriffe auf Datenobjekte von gemeinsam genutzten Daten durch verschiedene Prozesse zu vermeiden, weisen zumindest einige der Datenobjekte Verkettungen mit anderen zugehörigen Datenobjekten auf. Die Verkettungen stellen Ausgangswege für die Prozesse, die das Datenobjekt verwenden, dar.

In dem Mehrbenutzersystem von US 5 319 780 ist eine gemeinsam genutzte Datenbank für den Zugriff auf mehrere Benutzer vorgesehen. Beim Zugriff einer Datenverarbeitungsprozedur auf spezielle Daten werden die im Prozess befindlichen Daten verriegelt, um den Zugriff von anderen Benutzern zu begrenzen.

Es wäre vorteilhaft zu überwachen, welche Objekte in der Objektsammlung tatsächlich zusammenhängen, und folglich jedes Steuerobjekt zu verwenden, um den Zugriff auf die minimale Gruppe der zusammenhängenden Objekte zu begrenzen.

Die Erfindung ist in den Ansprüchen 1, 7 bzw. 13 definiert. Spezielle Ausführungsbeispiele sind in den abhängigen Ansprüchen dargelegt.

Zusammenfassung der Erfindung

Die vorliegende Erfindung verbessert die Leistung einer multithreading-fähigen Computeranwendung, die Gruppen von zusammenhängenden Datenstrukturen verwendet, die Werte enthalten, auf die von einem Thread ausschließlich zugegriffen werden muss. Die Erfindung überwacht Beziehungen zwischen den Datenstrukturen und stellt Mechanismen bereit, um den minimalen Satz von Datenstrukturen, der für den ausschließlichen Threadzugriff erforderlich ist, zu verriegeln. Die Erfindung verriegelt nur zusammenhängende Datenstrukturen, die eine Gruppe bilden, während sie unabhängige Datenstrukturen oder nicht in Zusammenhang stehende Gruppen von Datenstrukturen unverriegelt und für andere Threads erhältlich lässt. Da die Gruppe einen minimalen Satz von zusammenhängenden Datenstrukturen enthält, wenn die Gruppe verriegelt wird, werden andere Threads weniger wahrscheinlich durch die Sperre blockiert. Somit können diese anderen Threads wahrscheinlicher Datenstrukturen in anderen Gruppen simultan verarbeiten.

Ein Aspekt der Erfindung ist ein computergesteuertes Verfahren zum Verriegeln eines interessierenden Objekts in einer Objektsammlung, ohne ein nicht-zusammenhängendes Objekt verriegelt zu halten. Auf die Objektsammlung wird durch einen oder mehrere Threads in einer multithreading-fähigen Rechnerumgebung zugegriffen. Eine Gruppensperre steuert den Threadzugriff auf eine jeweilige Gruppe von zusammenhängenden Objekten, die das interessierende Objekt enthält. Das Verfahren umfasst den Schritt des Zuordnens einer Bezugssperre zur Objektsammlung, um den Threadzugriff auf eine Vielzahl von Gruppensperrenverkettungen zu steuern, die von der Gruppensperre verwendet werden. Das Verfahren umfasst auch den Schritt des Modifizierens der Vielzahl von Gruppensperrenverkettungen als Reaktion auf eine Änderung der Beziehung zwischen einem ersten Objekt innerhalb der jeweiligen Gruppe von zusammenhängenden Objekten zu einem zweiten Objekt. Ein zusätzlicher Verfahrensschritt besteht im Verriegeln der jeweiligen Gruppe von zusammenhängenden Objekten, die das interessierende Objekt erhält. Somit verriegelt dieser Schritt das interessierende Objekt und seine zusammenhängenden Objekte.

Ein weiterer Aspekt der Erfindung ist eine Vorrichtung mit einer Zentralverarbeitungseinheit (CPU) und einem Speicher, der mit der CPU gekoppelt ist, zum Verriegeln eines interessierenden Objekts in einer Objektsammlung, ohne ein nicht-zusammenhängendes Objekt verriegelt zu halten. Auf die Objektsammlung wird durch einen oder mehrere Threads in einer multithreading-fähigen Rechnerumgebung zugegriffen. Eine Gruppensperre steuert den Threadzugriff auf eine jeweilige Gruppe von zusammenhängenden Objekten, die das interessierende Objekt enthält. Die Vorrichtung umfasst einen Bezugssperrmechanismus, der dazu ausgelegt ist, der Objektsammlung eine Bezugssperre zuzuordnen, so dass der Bezugssperrmechanismus den Threadzugriff auf eine Vielzahl von Gruppensperrenverkettungen steuert, die von der Gruppensperre verwendet werden. Die Vorrichtung umfasst auch einen Gruppenmodifikationsmechanismus, der dazu ausgelegt ist, die jeweilige Gruppe von zusammenhängenden Objekten zu ändern. Diese Änderung wird durch Ändern der Beziehung zwischen einem ersten Objekt innerhalb der jeweiligen Gruppe von zusammenhängenden Objekten zu einem zweiten Objekt durchgeführt. Außerdem umfasst die Vorrichtung einen Gruppenverriegelungsmechanismus, der dazu ausgelegt ist, die jeweilige Gruppe von zusammenhängenden Objekten zu verriegeln, die das interessierende Objekt enthält, wodurch das interessierende Objekt und seine zusammenhängenden Objekte verriegelt werden.

Noch ein weiterer Aspekt der Erfindung ist auf ein Computerprogrammprodukt gerichtet, das in ein vom Computer verwendbares Medium eingebettet ist, um einen Computer zu veranlassen, ein interessierendes Objekt in einer Objektsammlung zu verriegeln, ohne ein nicht-zusammenhängendes Objekt verriegelt zu halten. Auf die Objektsammlung wird durch einen oder mehrere Threads in einer multithreading-fähigen Rechnerumgebung zugegriffen. Eine Gruppensperre steuert den Threadzugriff auf eine jeweilige Gruppe von zusammenhängenden Objekten, die das interessierende Objekt enthält. Wenn er auf einem Computer ausgeführt wird, veranlasst der maschinenlesbare Code, dass ein Computer einen Bezugssperrmechanismus, einen Gruppenmodifikationsmechanismus und einen Gruppenverriegelungsmechanismus durchführt. Jeder von diesen Mechanismen weist dieselben Funktionen wie die entsprechenden Mechanismen für die vorher beschriebene Vorrichtung auf.

Die vorangehenden und viele weitere Aspekte der vorliegenden Erfindung werden für Fachleute zweifellos offensichtlich, nachdem sie die folgende ausführliche Beschreibung der bevorzugten Ausführungsbeispiele gelesen haben, die in den verschiedenen Zeichnungsfiguren dargestellt sind.

Beschreibung der Zeichnungen

1 stellt ein Computersystem, das zur Verwendung der Erfindung in der Lage ist, gemäß einem bevorzugten Ausführungsbeispiel dar;

2A stellt eine Objektsammlung mit zwei Gruppen von zusammenhängenden Objekten gemäß einem bevorzugten Ausführungsbeispiel dar;

2B stellt eine Gruppenverkettungsstruktur gemäß einem bevorzugten Ausführungsbeispiel dar;

2C stellt eine kombinierte Gruppe gemäß einem bevorzugten Ausführungsbeispiel dar;

3 stellt eine Verriegelungsdatenstruktur gemäß einem bevorzugten Ausführungsbeispiel dar;

4 stellt einen Objektverriegelungsprozess zum Erhalten eines ausschließlichen Threadzugriffs auf das Objekt gemäß einem bevorzugten Ausführungsbeispiel dar;

5A & B stellen einen Einfüge- und Verriegelungsprozess gemäß einem bevorzugten Ausführungsbeispiel dar;

6 stellt einen Gruppenkombinationsprozess gemäß einem bevorzugten Ausführungsbeispiel dar;

7A stellt einen Gruppenverriegelungsprozess des Standes der Technik dar; und

7B stellt einen Objektverriegelungsprozess des Standes der Technik dar.

Beschreibung der bevorzugten Ausführungsbeispiele Anmerkungen und Nomenklatur

Die folgenden "Anmerkungen und Nomenklatur" werden bereitgestellt, um das Verständnis der vorliegenden Erfindung und von deren bevorzugten Ausführungsbeispielen zu fördern.

Bedingungsvariable – Eine Bedingungsvariable ist ein bedingter Threadsynchronisationsmechanismus. Eine Bedingungsvariable ermöglicht, dass ein Thread einen Mutex erfasst, eine Bedingung prüft, den Mutex freigibt und unterbrochen wird, wenn die Bedingung FALSCH ist. Der Thread wird wieder aufgenommen, wenn die Bedingung WAHR wird, und erfasst wieder den Mutex. Somit prüft der Thread eine Bedingung und, wenn die Bedingung erfüllt ist, erfasst der Thread den Mutex und fährt mit der Verarbeitung fort.

Datenstruktur – Eine Datenstruktur ist eine geordnete Speicheranordnung in einem Speicher für Variablen. Eine Datenstruktur ist im Allgemeinen innerhalb eines OOP-Objekts enthalten.

Mutex – Ein Mutex (Sperre mit gegenseitigem Ausschluss) ist eine Threadsynchronisations-Grundstruktur. Der erste Thread, der den Mutex aufruft, erfasst den Mutex. Weitere Aufrufe des Mutex bewirken, dass der aufrufende Thread blockiert. Der Thread, der den Mutex erfasst hat, kann dann den Mutex freigeben. Sobald der Mutex freigegeben (entriegelt) ist, kämpfen die blockierten Threads darum, den Mutex zu erfassen.

Objekt – Ein Objekt im objektorientierten Programmierungsmusterbeispiel ist ein Zusammenhang zwischen programmierten Verfahren und den Datenstrukturen, der durch eine Klasse und den konkret dargestellten Speicher, der ein Objekt der Klasse darstellt, definiert ist.

Objektsammlung – Eine Objektsammlung ist eine Sammlung von OOP-Objekten (die programmierte Verfahren und Datenstrukturen enthalten). In einem bevorzugten Ausführungsbeispiel enthält die Objektsammlung Objekte, die gerichtete azyklische Graphen (DAG) enthalten, die zur Bildverarbeitung verwendet werden.

Zeiger – Ein Zeiger ist ein Datenwert, der verwendet wird, um auf eine Datenstruktur oder ein Objekt zu verweisen. Ein Fachmann wird verstehen, dass "Zeiger" ohne Begrenzung eine Speicheradresse zur interessierenden Information oder einen wert, der zum Berechnen der Adresse zu dieser verwendet wird, und beliebige funktionale Äquivalente, einschließlich Zugriffsnummern und ähnlichen Gebilden, umfasst.

Programmiertes Verfahren – Ein programmiertes Verfahren ist eine programmierte Prozedur, die zu einem Objekt gehört. Das programmierte Verfahren wird aufgerufen, um zu bewirken, dass das Objekt eine Operation durchführt. Im Prozedur-Programmierungsmusterbeispiel ist ein programmiertes Verfahren äquivalent zu einer programmierten Routine oder Funktion.

Prozedur – Eine Prozedur ist eine selbstkonsistente Sequenz von Schritten, die zu einem gewünschten Ergebnis führen. Diese Schritte sind diejenigen, die eine physikalische Verarbeitung von physikalischen Größen erfordern. Gewöhnlich nehmen diese Größen die Form von elektrischen oder magnetischen Signalen an, die gespeichert, übertragen, kombiniert, verglichen und anderweitig verarbeitet werden können. Diese Signale werden als Bits, Werte, Elemente, Symbole, Zeichen, Terme, Zahlen oder dergleichen bezeichnet. Es ist für Fachleute selbstverständlich, dass alle diese und ähnliche Begriffe den geeigneten physikalischen Größen zugeordnet sind und lediglich zweckmäßige Bezeichnungen sind, die auf diese Größen angewendet werden.

Überblick

Die von einem Computer bei der Ausführung von Befehlen durchgeführten Verarbeitungen werden häufig mit Begriffen bezeichnet, wie z.B. Addieren oder Vergleichen, die üblicherweise geistigen Operationen zugeordnet sind, die von einem menschlichen Operator durchgeführt werden. In der vorliegenden Erfindung ist keine solche Fähigkeit eines menschlichen Operators bei irgendeiner der hierin beschriebenen Operationen erforderlich. Die Operationen sind Maschinenoperationen. Nützliche Maschinen zum Durchführen der Operationen der Erfindung umfassen programmierte digitale Universalcomputer oder ähnliche Vorrichtungen. In allen Fällen wird das Berechnungsverfahren vom Betriebsverfahren beim Betreiben eines Computers unterschieden. Die vorliegende Erfindung betrifft Verfahrensschritte zum Betreiben eines Computers bei der Verarbeitung von elektrischen oder anderen (z.B. mechanischen, chemischen) physikalischen Signalen, um andere gewünschte physikalische Signale zu erzeugen.

Die Erfindung betrifft auch eine Vorrichtung zum Durchführen dieser Operationen. Diese Vorrichtung kann für die erforderlichen Zwecke speziell konstruiert sein oder kann einen Universalcomputer umfassen, der durch ein im Speicher eines Computers gespeichertes Computerprogramm selektiv aktiviert oder rekonfiguriert wird. Die hierin dargestellten Prozeduren betreffen nicht von Natur aus einen speziellen Computer oder eine andere Vorrichtung. Insbesondere können verschiedene Universalmaschinen mit Programmen verwendet werden, die gemäß den Lehren hierin geschrieben sind, oder es kann sich als zweckmäßiger erweisen, eine spezialisiertere Vorrichtung zu konstruieren, um die erforderlichen Verfahrensschritte durchzuführen. Die erforderliche Struktur für eine Vielzahl dieser Maschinen zeigt sich aus der folgenden Beschreibung. Die Erfindung kann auch in einem maschinenlesbaren Speichermedium verkörpert sein, das mit einem Programm codiert ist, das bewirkt, dass ein Computer die programmierte Logik durchführt.

Betriebsumgebung

Ein Fachmann wird verstehen, dass, obwohl die folgende Beschreibung der Erfindung innerhalb eines objektorientierten Musterbeispiels erstellt ist, die offenbarten Verfahren auf andere Programmiermusterbeispiele anwendbar sind.

Ein bevorzugtes Ausführungsbeispiel verwendet einen modifizierten gerichteten azyklischen Graphen (DAG), um Bilder und die auf diese Bilder angewendeten Operationen darzustellen. Ein Fachmann wird verstehen, dass andere Datenstrukturen als ein DAG mit ähnlichen Ergebnissen verwendet werden können. Der DAG wird durch eine Abbildungsbibliothek konstruiert, wenn die Bibliothek eine Reihe von Abbildungsoperationen erfasst. Ein Fachmann wird verstehen, dass die Erfindung auf einem anderen Gebiet als der Bildverarbeitung ausgeführt werden kann und dass die Erfindung auf andere Objekte und Datenstrukturen als diejenigen, die anschließend zum Erläutern der Verwendung der Erfindung verwendet werden, angewendet werden kann.

Die Erfindung verwendet einen Computer. Einige der Elemente eines Computers, wie durch das allgemeine Bezugszeichen 100 angegeben, die dazu ausgelegt sind, die Erfindung zu unterstützen, sind in 1 gezeigt, in der ein Prozessor 101 mit einer Zentralverarbeitungseinheit (CPU) 103, einem Speicherabschnitt 105 und einem Eingabe/Ausgabe- (E/A) Abschnitt 107 gezeigt ist. Der E/A-Abschnitt 107 ist mit einer Tastatur 109, einer Anzeigeeinheit 111, einer Plattenspeichereinheit 113 und einer CD-ROM-Laufwerkeinheit 115 verbunden. Die CD-ROM-Laufwerkeinheit 115 kann ein CD-ROM-Medium 117 lesen, das typischerweise ein Programm und Daten 119 enthält. Die CD-ROM-Laufwerkeinheit 115 zusammen mit dem CD-ROM-Medium 117 und die Plattenspeichereinheit 113 bilden einen Dateispeichermechanismus. Ein Fachmann wird verstehen, dass die CD-ROM-Laufwerkeinheit 115 gegen eine Diskette, eine Magnetbandeinheit oder eine ähnliche Vorrichtung ausgetauscht werden kann, die entnehmbare Medien aufnimmt, die das Programm und die Daten 119 enthalten können. Ein solches Computersystem ist in der Lage, Anwendungen auszuführen, die die Erfindung verkörpern.

2A stellt eine gruppierte Objektsammlung dar, die durch das allgemeine Bezugszeichen 200 gekennzeichnet ist und die zwei unabhängige Gruppen umfasst, die jeweils zusammenhängende Objekte enthalten. Die zwei Gruppen können durch separate Threads parallel verarbeitet werden. In diesem Beispiel umfasst eine "erste Gruppe von zusammenhängenden" Objekten 201 ein "erstes Bild"-Objekt 203, das verwendet wird, um ein erstes Bild darzustellen, ein "zweites Bild"-Objekt 205, das verwendet wird, um ein zweites Bild darzustellen, ein "Summierungsoperations"-Objekt 207, das verwendet wird, um eine Bildoperation darzustellen, die die Summe des "ersten Bild"-Objekts 203 und des "zweiten Bild"-Objekts 205 erzeugt. Dieses summierte Bild wird durch ein Objekt 209 eines "ersten Ergebnisbildes" dargestellt. Ein Fachmann wird verstehen, dass alle der Objekte in der "ersten Gruppe von zusammenhängenden" Objekten 201 durch das "Summierungsoperations"-Objekt 207 miteinander in Zusammenhang stehen und dass ein Thread, der die Operation ausführt, die durch das "Summierungsoperations"-Objekt 207 dargestellt wird, einen ausschließlichen Zugriff auf die gesamte Gruppe von Objekten 203, 205, 207, 209 haben muss.

Eine zweite Gruppe von zusammenhängenden Objekten 211, die von der "ersten Gruppe von zusammenhängenden" Objekten 201 unabhängig ist, umfasst ein "drittes Bild"-Objekt 213 und ein "LUT-Operations"-Objekt 215, das auf ein "Nachschlagetabellendaten"-Objekt 217 zugreift. Das "LUT-Operations"-Objekt 215 verarbeitet das "dritte Bild"-Objekt 213 unter Verwendung des "Nachschlagetabellendaten"-Objekts 217, um ein Objekt 219 eines "zweiten Ergebnisbildes" zu erzeugen. Auf eine Weise ähnlich zur "ersten Gruppe von zusammenhängenden" Objekten 201 hängen alle Objekte in der zweiten Gruppe von zusammenhängenden Objekten 211 zusammen. Folglich muss ein Thread, der die Operation ausführt, die durch das "LUT-Operations"-Objekt 215 dargestellt wird, einen ausschließlichen Schreibzugriff auf die gesamte Gruppe von Objekten 213, 215, 217, 219 haben. Die Objekte in der "ersten Gruppe von zusammenhängenden" Objekten 201 und der zweiten Gruppe von zusammenhängenden Objekten 211 bilden eine Objektsammlung 221. Da die zwei Gruppen voneinander unabhängig sind (insofern als die Objekte einer Gruppe in Bezug auf die Objekte in der anderen Gruppe ein nicht-zusammenhängendes Objekt sind), kann auf diese durch separate Threads zugegriffen werden. Die "erste Gruppe von zusammenhängenden" Objekten 201 kann durch ein Objekt 223 einer "ersten Gruppensperre" verriegelt werden. Die zweite Gruppe von zusammenhängenden Objekten 211 kann durch ein Objekt 225 einer "zweiten Gruppensperre" verriegelt werden. Die Verkettungen, die die Gruppensperren und die Objekte in der Objektsammlung 221 miteinander in Zusammenhang bringen, können durch ein "Bezugssperren"-Objekt 227 verriegelt werden. Jedes der Sperrenobjekte wird anschließend beschrieben.

Es ist nun nützlich, die Verwendung der Bezugs- und Gruppensperren zusammenzufassen. Diese Sperren sind in nicht-zusammenhängenden Objekten enthalten. Diese Sperrenobjekte hängen nicht mit dem interessierende Objekt oder Objekten innerhalb einer Gruppe zusammen, da die Sperrenobjekte ein Ergebnis der Beziehungen zwischen den Objekten in einer Gruppe sind, aber nicht selbst Elemente einer Gruppe sind (und die Sperrenobjekte müssen sich auch nicht innerhalb der Objektsammlung befinden). Um auf ein unabhängiges Objekt zuzugreifen, erfasst ein Thread eine Sperre an diesem Objekt. Um auf ein zusammenhängendes Objekt zuzugreifen, erfasst der Thread die zugehörige Gruppensperre (wie z.B. das Objekt 223 der "ersten Gruppensperre") und die Objektsperre. Um die Beziehung zwischen Objekten und/oder Gruppen zu ändern, erfasst der Thread das "Bezugssperren"-Objekt 227. Folglich muss ein Thread zuerst das Objekt 223 der "ersten Gruppensperre" erfassen, um die durch das "Summierungsoperations"-Objekt 207 dargestellte Operation durchzuführen.

2B stellt eine Gruppenverkettungsstruktur, die durch das allgemeine Bezugszeichen 230 gekennzeichnet ist, zum Zuordnen von zusammenhängenden Objekten zu einer Gruppe dar. Dieses Beispiel gibt an, wie die zweite Gruppe von zusammenhängenden Objekten 211 dem Objekt 225 der "zweiten Gruppensperre" zugeordnet wird. Jedes Objekt 213, 215, 217, 219 in der zweiten Gruppe von zusammenhängenden Objekten 211 umfasst einen Zeiger auf ein "Gruppensperrenzeiger"-Objekt 231. Folglich umfasst das "dritte Bild"-Objekt 213 eine Verkettung 233 des "dritten Bildes", die auf das "Gruppensperrenzeiger"-Objekt 231 zeigt. Auf eine ähnliche Weise umfasst das "LUT-Operations"-Objekt 215 eine "LUT-Operations"-Verkettung 235; das "Nachschlagetabellendaten"-Objekt 217 umfasst eine "Nachschlagetabellendaten"-Verkettung 237; und das Objekt 219 des "zweiten Ergebnisbildes" umfasst eine Verkettung 239 des "zweiten Ergebnisbildes"; die jeweils auf das "Gruppensperrenzeiger"-Objekt 231 zeigen. Das "Gruppensperrenzeiger"-Objekt 231 umfasst eine Gruppenverkettung 241 mit dem Objekt 225 der "zweiten Gruppensperre". Außerdem umfasst das Objekt 225 der "zweiten Gruppensperre" eine umgekehrte Gruppenverkettung 243. Ein Fachmann wird verstehen, dass die vorher beschriebenen Verkettungen ermöglichen, dass jedes Objekt 213, 215, 217, 219 in der Gruppe an eine andere Gruppe angehängt wird, indem der Zeigerwert im "Gruppensperrenzeiger"-Objekt 231 geändert wird (zusammen mit geeigneten Modifikationen am Objekt 225 der "zweiten Gruppensperre" und der umgekehrten Gruppenverkettung 243), und folglich die Gruppenverkettung 241 von einer Gruppensperre zu einer anderen Gruppensperre ändern, ohne die Verkettungen für jedes Objekt 213, 215, 217, 219 zu ändern.

Häufig werden zwei unabhängige Gruppen von zusammenhängenden Objekten selbst zusammenhängend. Unter diesem Umstand müssen die Gruppen und ihre Gruppensperren kombiniert werden.

2C stellt eine Objektsammlung dar, die mit dem allgemeinen Bezugszeichen 250 gekennzeichnet ist, das heißt das Ergebnis der Kombination der "ersten Gruppe von zusammenhängenden" Objekten 201 mit der zweiten Gruppe von zusammenhängenden Objekten 211. Diese zwei Gruppen wurden durch die Einfügung eines "Bildmultiplikations"-Objekts 251 zusammenhängend, das das Objekt 209 des "ersten Ergebnisbildes" mit dem Objekt 219 des "zweiten Ergebnisbildes" multiplizierte, um ein Objekt 253 eines "dritten Ergebnisbildes" zu erzeugen. Da das "Bildmultiplikations"-Objekt 251 die "erste Gruppe von zusammenhängenden" Objekten 201 mit der zweiten Gruppe von zusammenhängenden Objekten 211 in Zusammenhang brachte, müssen die zwei Gruppen zu einer Gruppe kombiniert werden. Dies wird, wie anschließend mit Bezug auf 6 beschrieben wird, durch Ändern des Werts des "Gruppensperrenzeiger"-Objekts 231 für die zweite Gruppe von zusammenhängenden Objekten 211 so, dass er auf das Objekt 223 der "ersten Gruppensperre" zeigt, bewerkstelligt. Ein Fachmann wird verstehen, dass es im Allgemeinen mehr als zwei Gruppen von zusammenhängenden Objekten in der Objektsammlung gibt.

3 stellt eine Verriegelungsdatenstruktur dar, die mit dem allgemeinen Bezugszeichen 300 gekennzeichnet ist und die in einem Ausführungsbeispiel verwendet wird. Die Verriegelungsdatenstruktur 300 umfasst ein "Bezugssperren"-Objekt 301, ein "Gruppensperren"-Objekt 303, ein "Gruppensperrenzeiger"-Objekt 304 (das einen "Sperrenobjekt-Zeiger 305 und ein "Bezugszählwert"-Feld 306 enthält) und ein verriegelbares Objekt 307. Das "Bezugssperren"-Objekt 301 wird verwendet, um einen ausschließlichen Zugriff auf anschließend beschriebene Gruppensperrenverkettungen bereitzustellen. Die Objektsammlung kann mehr als ein zugehöriges "Gruppensperren"-Objekt 303 aufweisen. Jede Gruppe in der Objektsammlung enthält zusammenhängende Objekte, die zusammen verriegelt werden müssen, bevor auf irgendeines der zusammenhängenden Objekte zugegriffen wird. Somit kann auf jede Gruppe in der Objektsammlung durch separate Threads unabhängig zugegriffen werden. Das "Gruppensperrenzeiger"-Objekt 304 enthält den "Sperrenobjekt"-Zeiger 305 und das "Gruppensperren"-Objekt 303. Jedes zusammenhängende Objekt in der Objektsammlung enthält einen Zeiger auf das "Gruppensperrenzeiger"-Objekt 304, das wiederum auf das "Gruppensperren"-Objekt 303 für diese Gruppe zeigt. Somit kann jedes der zusammenhängenden Objekte in einer Gruppe einem anderen "Gruppensperren"-Objekt 303 zugewiesen werden, indem der existierende Wert des "Sperrenobjekt"-Zeigers 305 gegen einen Zeiger auf das neue "Gruppensperren"-Objekt ausgetauscht wird, anstatt dass jedes Objekt durchgegangen wird und sein Zeiger aktualisiert wird. Das verriegelbare Objekt 307 ist ein Objekt innerhalb der Objektsammlung. In einem bevorzugten Ausführungsbeispiel sind das "Bezugssperren"-Objekt 301, das "Gruppensperren"-Objekt 303 und das Gruppensperrenzeiger"-Objekt 304 nicht innerhalb der Objektsammlung enthalten.

Das "Bezugssperren"-Objekt 301 enthält einen "Bezugssperren"-Mutex 309 und eine Bedingungsvariable 311, die gut bekannte Verfahren verwendet, um den Threadzugriff zu serialisieren. Das "Bezugssperren"-Objekt 301 wird verwendet, um einen ausschließlichen Zugriff auf die Gruppensperrenverkettungen zu erhalten. Das "Bezugssperren"-Objekt 301 enthält auch ein Feld 313 "maximale Sperrenobjekt-ID", das einen monoton steigenden Wert enthält, der verwendet wird, um Sperrenobjekte eindeutig zu identifizieren. Das "Bezugssperren"-Objekt 301 enthält auch programmierte Verfahren, die eine Funktionalität für das "Bezugssperren"-Objekt 301 vorsehen. Diese programmierten Verfahren umfassen ein programmiertes Verfahren 315 lockRefCreator, ein programmiertes Verfahren 317 waitForLockObjUnlock und ein programmiertes Verfahren 319 signalUnlock. Das programmierte Verfahren 315 lockRefCreator erzeugt ein neues "Gruppensperren"-Objekt 303, wenn ein unabhängiges Objekt in der Objektsammlung mit einem anderen Objekt in Zusammenhang kommt. Das programmierte Verfahren 315 lockRefCreator inkrementiert auch und speichert den Wert des Feldes 313 "maximale Sperrenobjekt-ID" im neu erzeugten "Gruppensperren"-Objekt 303. Das programmierte Verfahren 317 waitForLockObjUnlock wird von einer threading-fähigen Prozedur aufgerufen, um einen ausschließlichen Zugriff auf die Objektsammlung anzufordern, und führt schließlich dazu, dass der anfordernde Thread den "Bezugssperren"-Mutex 309 und den ausschließlichen Zugriff auf die Verkettungen in der Objektsammlung erhält. Das programmierte Verfahren 319 signalUnlock wird aufgerufen, um die Freigabe des "Bezugssperren"-Mutex 309 zu signalisieren, was anzeigt, dass der Thread den ausschließlichen Zugriff auf die Verkettungen in der Objektsammlung nicht mehr benötigt.

Das "Gruppensperren"-Objekt 303 umfasst einen Gruppensperren-Mutex 321, der verwendet wird, um den Threadzugriff auf eine Gruppe von zusammenhängenden Objekten zu serialisieren. Um auf das "Gruppensperren"-Objekt 303 zuzugreifen, muss das Programm zuerst das "Bezugssperren"-Objekt 301 erfassen. Das "Gruppensperren"-Objekt 303 umfasst auch ein Feld 323 der "Anzahl von Referenzen", das die Anzahl der Objekte in der Objektsammlung enthält, die vom "Gruppensperren"-Objekt 303 gesteuert wird. Ein Fachmann wird verstehen, dass das Feld 323 der "Anzahl von Referenzen" und das "Bezugszählwert"-Feld 306 verwendet werden, um jeweils festzustellen, wenn das "Gruppensperren"-Objekt 303 und das "Gruppensperrenzeiger"-Objekt 304 nicht mehr verwendet werden. Das "Gruppensperren"-Objekt 303 enthält auch ein "Gruppensperrenidentifikations"-Feld 325, das einen monoton steigenden Identifikationswert enthält, der vom programmierten Verfahren 315 lockRefCreator erzeugt wird, wie vorher beschrieben. Das "Gruppensperren"-Objekt 303 umfasst auch ein "Bezugssperrenzeiger"-Feld 327, das einen Zeiger auf das "Bezugssperren"-Objekt 301 enthält. Außerdem umfasst das "Gruppensperren"-Objekt 303 einen "Bezugszeiger"-Speicher 328, der einen Zeiger auf jedes "Gruppensperrenzeiger"-Objekt 304, das auf das "Gruppensperren"-Objekt 303 Bezug nimmt, liefert oder mit diesem verknüpft.

Das verriegelbare Objekt 307 ist eines der Objekte in der Objektsammlung. Ein Programm verwendet die Objekte, die sich in der Objektsammlung befinden, um (ohne Begrenzung) Dienste durchzuführen oder eine Information zum Programm zu liefern. Das verriegelbare Objekt 307 umfasst einen Objektsperren-Mutex 329, der verwendet werden kann, um das verriegelbare Objekt 307 zu verriegeln. Das verriegelbare Objekt 307 enthält auch ein "Gruppenbezugszeiger"-Feld 331, das einen Zeiger auf das "Gruppensperrenzeiger"-Objekt 304 enthält, das zur Gruppe von zusammenhängenden Objekten gehört. Das verriegelbare Objekt 307 enthält auch einen Speicher 333 für "Zeiger auf zusammenhängende Objekte", der einen Speicher für Zeiger auf die Objekte vorsieht oder mit diesem verknüpft, die mit dem verriegelbaren Objekt 307 zusammenhängen. Wenn eine Gruppe sowohl ein erstes als auch ein zweites Exemplar des verriegelbaren Objekts 307 enthält, würde folglich jedes auf einen Zeiger auf das andere Objekt durch einen Zeiger, der im jeweiligen Speicher 333 für "Zeiger auf zusammenhängende Objekte" gespeichert ist, Bezug nehmen. Das verriegelbare Objekt 307 enthält auch einen Speicher 335 für "Objektdaten und programmiertes Verfahren", der in einem objektorientierten System die Objektfelder und Zugriffsmittel auf die programmierten Verfahren des Objekts umfasst.

Das "Bezugssperren"-Objekt 301 schützt das "Gruppensperren"-Objekt 303, den "Sperrenobjekt"-Zeiger 305 und das "Gruppenbezugszeiger"-Feld 331, so dass der Thread, der das "Bezugssperren"-Objekt 301 erfasst hat, einen ausschließlichen Zugriff auf diese Gruppensperrenverkettungen hat.

Ein Fachmann wird verstehen, dass die Verriegelungsdatenstruktur 300 nicht auf eine objektorientierte Weise implementiert werden muss und dass herkömmliche Prozedur-Datenstrukturierungsverfahren verwendet werden können, um die vorher beschriebenen Beziehungen und Fähigkeiten zu implementieren.

4 stellt einen Objektverriegelungsprozess dar, der mit dem allgemeinen Bezugszeichen 400 angegeben ist und der die Schritte zeigt, die verwendet werden, um ein interessierendes Objekt in der Objektsammlung zu verriegeln. Der Prozess 400 beginnt an einer "Start"-Station 401 und fährt zu einer Prozedur 403 "Bezugssperre verriegeln" fort. Die Prozedur 403 "Bezugssperre verriegeln" verriegelt den "Bezugssperren"-Mutex 309 im "Bezugssperren"-Objekt 301, um einen ausschließlichen Threadzugriff auf die Gruppensperrenverkettungen in der Objektsammlung (beispielsweise das "Gruppensperren"-Objekt 303) vor dem Zugriff auf ein interessierendes Objekt wie z.B. das verriegelbare Objekt 307 zu erhalten. Sobald ein Thread den "Bezugssperren"-Mutex 309 erfasst, werden die Gruppen- und Objektbeziehungen in der Objektsammlung vor einem Zugriff durch andere Threads geschützt. Sobald diese Beziehungen vor anderen Threads geschützt sind, kann der aktuelle Thread die Beziehungen ändern. Als nächstes fährt der Prozess 400 zu einer Prozedur 405 "Objekt verriegeln" fort, die den Objektsperren-Mutex 329 des interessierenden Objekts erfasst. Dann stellt eine Entscheidungsprozedur 407 "Objekt zusammenhängend" fest, ob das verriegelbare Objekt 307, auf das zugegriffen wird (das interessierende Objekt), mit anderen Objekten zusammenhängt oder ob es von anderen Objekten unabhängig ist. Diese Feststellung wird durch Untersuchen des "Gruppenbezugszeiger"-Feldes 331 innerhalb des verriegelbaren Objekts 307 durchgeführt. Wenn der Wert des "Gruppenbezugszeiger"-Feldes 331 keinen Zeiger auf den "Sperrenobjekt"-Zeiger 305 enthält, ist das verriegelbare Objekt 307 von anderen Objekten in der Objektsammlung unabhängig. Wenn das verriegelbare Objekt 307 nicht unabhängig ist, fährt der Prozess 400 zu einer Prozedur 409 "Gruppe verriegeln" fort, die den Gruppensperren-Mutex 321 erfasst. Dann fährt der Prozess 400 zu einer Prozedur 411 "Bezugssperre entriegeln" fort. Die Prozedur 411 "Bezugssperre entriegeln" wird auch direkt ausgeführt, wenn die Entscheidungsprozedur 407 "Objekt zusammenhängend" festgestellt hat, dass das interessierende Objekt unabhängig war. Die Prozedur 411 "Bezugssperre entriegeln" entriegelt den "Bezugssperren"-Mutex 309. Als nächstes fährt der Prozess 400 zu einer Prozedur 413 "Objekt verarbeiten" fort, die die gewünschte Operation am interessierenden Objekt durchführt. Sobald die Operation endet, fährt der Prozess 400 zu einer Prozedur 415 "Bezugssperre verriegeln" fort, die den "Bezugssperren"-Mutex 309 wieder verriegelt, um andere Threads am Modifizieren von Gruppensperrenverkettungen in der Objektsammlung zu hindern. Als nächstes prüft eine Entscheidungsprozedur 417 "bjekt zusammenhängend" wieder, um festzustellen, ob das interessierende Objekt unabhängig ist oder mit anderen Objekten zusammenhängt. Wenn das interessierende Objekt zusammenhängt, gibt eine Prozedur 419 "Gruppe entriegeln", die durch die Prozedur 409 "Gruppe verriegeln" verriegelte Gruppe frei. Sobald die Gruppe entriegelt ist, oder wenn das interessierende Objekt unabhängig war, fährt der Prozess 400 zu einer Prozedur 421 "Objekt entriegeln" fort, die den Objektsperren-Mutex 329 freigibt, der von der Prozedur 405 "Objekt verriegeln" erfasst wurde. Sobald das interessierende Objekt entriegelt ist, fährt der Prozess 400 zu einer Prozedur 423 "Bezugssperre entriegeln" fort, die den "Bezugssperren"-Mutex 309, der von der Prozedur 415 "Bezugssperre verriegeln" verriegelt wurde, entriegelt. Der Prozess 400 endet über eine "Ende"-Station 425.

Fachleute werden verstehen, dass das "Bezugssperren"-Objekt 301 für eine sehr kurze Zeit verriegelt wird, um Verzögerungen für andere Threads zu minimieren, die Beziehungen zwischen Objekten und Gruppen in der Objektsammlung ändern.

5A stellt einen Einfüge- und Verriegelungsprozess dar, der mit dem allgemeinen Bezugszeichen 500 gekennzeichnet ist und der ein interessierendes Objekt in die Objektsammlung einfügt, wobei das interessierende Objekt ein anderes Objekt in Beziehung bringen kann. Der Einfüge- und Verriegelungsprozess 500 startet an einer "Start"-Station 501 und fährt zu einer Prozedur 503 "Bezugssperre verriegeln" fort. Die Prozedur 503 "Bezugssperre verriegeln" verriegelt das "Bezugssperren"-Objekt 301. Sobald das "Bezugssperren"-Objekt 301 verriegelt ist, stellt der Einfüge- und Verriegelungsprozess 500 in einer Entscheidungsprozedur 505 "interessierendes Objekt in Gruppe" fest, ob das interessierende Objekt unabhängig ist oder einer Gruppe zugewiesen ist. Diese Feststellung wird durch Untersuchen des "Gruppenbezugszeiger"-Feldes 331 im interessierenden Objekt durchgeführt. Wenn das "Gruppenbezugszeiger"-Feld 331 NULL ist, ist das interessierende Objekt unabhängig. Ansonsten gehört das interessierende Objekt zu irgendeiner Gruppe. Wenn das interessierende Objekt bereits zu einer Gruppe gehört, fährt der Einfüge- und Verriegelungsprozess 500 zu einer Prozedur 507 "Gruppe verriegeln" fort, die das "Gruppensperren"-Objekt 303 verriegelt, das das interessierende Objekt enthält, indem sie den Gruppensperren-Mutex 321 verriegelt. Als nächstes gibt eine Prozedur 511 "Bezugssperre entriegeln" das "Bezugssperren"-Objekt 301 frei, so dass andere Threads Verkettungen zwischen den Objekten in anderen Gruppen verarbeiten können. Dann endet der Einfüge- und Verriegelungsprozess 500 durch eine "Ende"-Station 513.

Wenn jedoch die Entscheidungsprozedur 505 "interessierendes Objekt in Gruppe" feststellt, dass das interessierende Objekt nicht in irgendeiner Gruppe enthalten ist, fährt der Einfüge- und Verriegelungsprozess 500 zu einer Prozedur 515 "Gruppenbezugszeiger sammeln" fort. Die Prozedur 515 "Gruppenbezugszeiger sammeln" sammelt die Gruppenbezugszeiger von jedem Objekt, das mit dem interessierenden Objekt zusammenhängt. Als nächstes stellt eine Entscheidungsprozedur 517 "alle Gruppenbezugszeiger NULL" fest, ob alle Gruppenbezugszeiger in den zusammenhängenden Objekten NULL sind. Wenn alle Gruppenbezugszeiger NULL sind, ist weder das interessierende Objekt noch irgendwelche seiner zusammenhängende Objekte einer Gruppe zugewiesen. Folglich geht der Einfüge- und Verriegelungsprozess 500 zu einer Prozedur 519 "neue Gruppe erzeugen" weiter, die eine neue Gruppe erzeugt. Sobald die neue Gruppe erzeugt ist, fährt der Einfüge- und Verriegelungsprozess 500 zu einer Prozedur 521 "interessierendes Objekt neuer oder ausgewählter Gruppe (zugewiesener Gruppe) zuweisen" fort. Die Prozedur 521 "interessierendes Objekt einer Gruppe zuweisen" wird anschließend beschrieben.

Wenn jedoch die Entscheidungsprozedur 517 "alle Gruppenbezugszeiger NULL" einen von NULL verschiedenen Gruppenbezugszeiger gefunden hat (was bedeutet, dass eines der zusammenhängenden Objekte bereits ein Teil einer Gruppe ist), fährt der Einfüge- und Verriegelungsprozess 500 zu einer Prozedur 523 "Gruppe auswählen" fort. Die Prozedur 523 "Gruppe auswählen" wählt irgendeine Gruppe aus den Gruppenbezugszeigern aus, die durch die Prozedur 515 "Gruppenbezugszeiger sammeln" gesammelt wurden. Der Einfüge- und Verriegelungsprozess 500 fährt dann zur Prozedur 521 "interessierendes Objekt einer Gruppe zuweisen" fort. Die Prozedur 521 "interessierendes Objekt einer Gruppe zuweisen" weist die Gruppe entweder der neuen Gruppe, die durch die Prozedur 519 "neue Gruppe erzeugen" erzeugt wurde, oder der Gruppe, die durch die Prozedur 523 "Gruppe auswählen" ausgewählt wurde, zu. Diese Gruppe wird nun als "zugewiesene Gruppe" bezeichnet. Als nächstes fährt der Einfüge- und Verriegelungsprozess 500 bis zu einer Station 527 "zu AA gehen" fort, die den Einfüge- und Verriegelungsprozess 500 in 5B fortsetzt.

5B stellt eine Fortsetzung des Einfüge- und Verriegelungsprozesses dar, die mit dem allgemeinen Bezugszeichen 560 gekennzeichnet ist und die den Einfüge- und Verriegelungsprozess 500 von 5A fortsetzt. Der Einfüge- und Verriegelungsprozess fährt an einer Station 561 "AA-Fortsetzung" von der Station 527 "zu AA gehen" fort. Der Einfüge- und Verriegelungsprozess fährt zu einer Prozedur 563 "zusammenhängende Objekte iterieren" fort, die jeden Gruppenbezugszeiger von jedem zusammenhängenden Objekt iteriert. Wenn jeder Gruppenbezugszeiger iteriert wird, fährt der Einfüge- und Verriegelungsprozess zu einer Entscheidungsprozedur 565 "Gruppenbezugszeiger NULL" fort, die feststellt, ob der Gruppenbezugszeiger NULL ist. Wenn der Gruppenbezugszeiger NULL ist, ist das zugehörige Objekt keiner Gruppe zugewiesen. Somit setzt eine Prozedur 569 "Objekt zu zugewiesener Gruppe zuweisen" das "Gruppenbezugszeiger"-Feld 331 des zugehörigen Objekts so, dass es auf das "Gruppensperrenzeiger"-Objekt 304 für die dem interessierenden Objekt zugewiesene Gruppe zeigt. Dann fährt der Einfüge- und Verriegelungsprozess zur Prozedur 563 "zusammenhängende Objekte iterieren" fort, um andere Gruppenbezugszeiger zu iterieren.

Wenn jedoch der Gruppenbezugszeiger in der Entscheidungsprozedur 565 "Gruppenbezugszeiger NULL" nicht NULL ist, fährt der Einfüge- und Verriegelungsprozess zu einer Entscheidungsprozedur 571 "ist Gruppe zugewiesene Gruppe" fort, die feststellt, ob die dem zusammenhängenden Objekt zugeordnete Gruppe dieselbe Gruppe ist, die dem interessierenden Objekt zugewiesen wurde. Als nächstes fährt der Einfüge- und Verriegelungsprozess zur Prozedur 563 "zusammenhängende Objekte iterieren" fort, um andere Gruppenbezugszeiger zu iterieren.

Wenn jedoch der Gruppenbezugszeiger nicht NULL ist und nicht derselbe ist wie die zugewiesene Gruppe, fährt der Einfüge- und Verriegelungsprozess zu einer Prozedur 573 "zugewiesene Gruppe und Bezugsgruppe kombinieren" fort, die anschließend mit Bezug auf 6 beschrieben wird und die die zwei Gruppen kombiniert. Sobald die zwei Gruppen kombiniert sind, setzt eine Prozedur 574 "Iteration zurücksetzen" die Iteration der Prozedur 563 "zusammenhängende Objekte iterieren" zurück, so dass alle Gruppenbezugszeiger von der neu kombinierten Gruppe iteriert werden. Folglich kann die Prozedur 573 "zugewiesene Gruppe und Bezugsgruppe kombinieren" wieder aufgerufen werden, um andere Gruppen mit der gerade kombinierten Gruppe zu kombinieren.

Sobald die Prozedur 563 "zusammenhängende Objekte iterieren" endet, fährt der Einfüge- und Verriegelungsprozess zu einer Prozedur 575 "zugewiesene Gruppe verriegeln" fort, die die dem interessierenden Objekt zugewiesene Gruppe verriegelt. Sobald die Gruppe verriegelt ist, iteriert eine Prozedur 577 "Bezüge zusammenhängender Objekte freigeben" wieder durch die Liste der von NULL verschiedenen Gruppenzeiger und gibt jede Gruppe frei. Sobald die entsprechenden Gruppen freigegeben sind, entriegelt eine Prozedur 581 "Bezugssperre entriegeln" wieder das "Bezugssperren"-Objekt 301. Dann endet der Einfüge- und Verriegelungsprozess durch eine "Ende"-Station 583, die die verriegelte und zugewiesene Gruppe zurückgibt, die das interessierende Objekt enthält.

6 stellt einen Gruppenkombinationsprozess, der mit dem allgemeinen Bezugszeichen 600 gekennzeichnet ist, zum Kombinieren von zwei Gruppen, die zusammenhängend geworden sind, dar. Der Gruppenkombinationsprozess 600 wird durch die Prozedur 573 "ugewiesene Gruppe und Bezugsgruppe kombinieren" von 5B aufgerufen und beginnt an einer "Start"-Station 601. Dann fährt der Gruppenkombinationsprozess 600 zu einer Prozedur 603 "ältere Gruppe verriegeln" fort, die die Gruppe mit dem niedrigeren Identifikationswert im "Gruppensperrenidentifikations"-Feld 325 verriegelt. Die gut bekannte Verriegelungsprozedur wird anschließend mit Bezug auf 7A und 7B beschrieben. Als nächstes stellt eine Entscheidungsprozedur 605 "Sperrenprüfung" fest, ob die relevanten Verkettungen durch einen anderen Thread geändert wurden, während die ältere Gruppe verriegelt war. wenn die relevanten Verkettungen geändert wurden, fährt der Gruppenkombinationsprozess 600 zu einer Prozedur 607 "ältere Gruppe entriegeln" fort, die die ältere Gruppe entriegelt. Unter diesem Umstand endet der Gruppenkombinationsprozess 600 durch eine "Ende"-Station 609. Ein Fachmann wird verstehen, dass, da die Prozedur 574 "Iteration zurücksetzen" immer nach der Prozedur 573 "zugewiesene Gruppe und Bezugsgruppe kombinieren" aufgerufen wird, die Verriegelungsunbeständigkeit, die die Prozedur 607 "ältere Gruppe entriegeln" aufgerufen hat, anschließend wieder aufgenommen wird.

Wenn jedoch die ältere Gruppe verriegelt wurde und die relevanten Verkettungen unverändert sind, wie durch die Entscheidungsprozedur 605 "Verriegelungsprüfung" festgestellt, fährt der Gruppenkombinationsprozess 600 zu einer Prozedur 611 "neuere Gruppe verriegeln" fort, die die Gruppe mit dem höheren Identifikationswert (die neuere Gruppe) verriegelt. Als nächstes stellt eine Entscheidungsprozedur 613 "Verriegelungsprüfung" fest, ob die relevanten Verkettungen durch einen anderen Thread geändert wurden, während die neuere Gruppe verriegelt war. Wenn die relevanten Verkettungen nicht geändert wurden, fährt der Gruppenkombinationsprozess 600 zu einer Prozedur 615 "neuere Gruppe mit älterer Gruppe kombinieren" fort, die den Gruppenbezug der neueren Gruppe (der Gruppe mit dem größeren Gruppensperren-Identifikationswert) auf den Gruppensperren-Identifikationswert der älteren Gruppe setzt. Als nächstes fährt der Gruppenkombinationsprozess 600 zu einer Prozedur 617 "neuere Gruppe entriegeln", die die neuere Gruppe entriegelt, und zu einer Prozedur 619 "ältere Gruppe entriegeln", die die ältere Gruppe entriegelt, fort. Der Gruppenkombinationsprozess 600 endet dann durch die "Ende"-Station 609.

Wenn jedoch die Entscheidungsprozedur 613 "Sperrenprüfung" feststellt, dass die relevanten Verkettungen geändert wurden, endet der Gruppenkombinationsprozess 600 einfach durch die Prozedur 617 "neuere Gruppe entriegeln", die Prozedur 619 "ältere Gruppe entriegeln" und die "Ende"-Station 609. Ein Fachmann wird verstehen, dass, da die Prozedur 574 "Iteration zurücksetzen" immer nach der Prozedur 573 "zugewiesene Gruppe und Bezugsgruppe kombinieren" aufgerufen wird, die Verriegelungsunbeständigkeit, die von der Entscheidungsprozedur 613 "Sperrenprüfung" erfasst wird, anschließend wieder aufgenommen wird. Ein Fachmann wird verstehen, dass es wichtig ist, die Gruppensperren in einer speziellen Reihenfolge zu verriegeln, um mögliche Bedingungen einer gegenseitigen Blockierung zu vermeiden.

Es wurde als nützlich festgestellt, die Verriegelungsprozeduren des Standes der Technik darzustellen. 7A stellt einen Gruppenverriegelungsprozess dar, der mit dem allgemeinen Bezugszeichen 700 gekennzeichnet ist und der verwendet wird, um eine Gruppe zu verriegeln. Der Gruppenverriegelungsprozess 700 beginnt an einer "Start"-Station 701 und fährt zu einer "Verriegelungsversuchs"-Prozedur 703 fort, die versucht, den Gruppensperren-Mutex 321 zu verriegeln. Wenn der Gruppensperren-Mutex 321 nicht bereits durch irgendeinen anderen Thread verriegelt ist, erhält die "Verriegelungsversuchs"-Prozedur 703 den Gruppensperren-Mutex 321. Die "Verriegelungsversuchs"-Prozedur 703 kehrt jedoch einfach zurück, wenn der Gruppensperren-Mutex 321 bereits verriegelt ist. Ungeachtet dessen stellt eine Entscheidungsprozedur 705 "Sperre erhalten" fest, ob der Gruppensperren-Mutex 321 durch die "Verriegelungsversuchs"-Prozedur 703 erfolgreich verriegelt wurde. Wenn der Gruppensperren-Mutex 321 erfolgreich verriegelt wurde, endet der Gruppenverriegelungsprozess 700 durch eine "Ende"-Station 707. Wenn der Gruppensperren-Mutex 321 nicht erhalten wurde, fährt der Gruppenverriegelungsprozess 700 zu einer Prozedur 709 "auf Bedingungsvariable warten" fort, die den "Bezugssperren"-Mutex 309 entriegelt und den aufrufenden Thread in Abhängigkeit von einem Prädikat, dass der Gruppensperren-Mutex 321 entriegelt wurde, in Ruhe versetzt. Sobald das Prädikat erfüllt ist, wird der aktuelle Thread mit dem verriegelten "Bezugssperren"-Mutex 309 fortgesetzt. Sobald der aktuelle Thread fortgesetzt wird, fährt der Gruppenverriegelungsprozess 700 zur "Verriegelungsversuchs"-Prozedur 703 fort, um wieder zu versuchen, den Gruppensperren-Mutex 321 zu verriegeln.

Das Verriegeln eines Objekts ist ähnlich zum Verriegeln einer Gruppe. 7B stellt einen Objektverriegelungsprozess dar, der mit dem allgemeinen Bezugszeichen 750 gekennzeichnet ist und verwendet wird, um ein Objekt zu verriegeln. Der Objektverriegelungsprozess 750 beginnt an einer "Start"-Station 751 und fährt zu einer "Verriegelungsversuchs"-Prozedur 753 fort, die versucht, den Objektsperren-Mutex 329 zu verriegeln. Wenn der Objektsperren-Mutex 329 nicht bereits durch irgendeinen anderen Thread verriegelt ist, erhält die "Verriegelungsversuchs"-Prozedur 753 den Objektsperren-Mutex 329. Die "Verriegelungsversuchs"-Prozedur 753 kehrt jedoch einfach zurück, wenn der Objektsperren-Mutex 329 bereits verriegelt ist. Ungeachtet dessen stellt eine Entscheidungsprozedur 755 "Sperre erhalten" fest, ob der Objektsperren-Mutex 329 durch die "Verriegelungsversuchs"-Prozedur 753 erfolgreich verriegelt wurde. Wenn der Objektsperren-Mutex 329 erfolgreich verriegelt wurde, endet der Objektverriegelungsprozess 750 durch eine "Ende"-Station 757. Wenn der Objektsperren-Mutex 329 nicht erhalten wurde, fährt der Objektverriegelungsprozess 750 zu einer Prozedur 759 "auf Bedingungsvariable warten" fort, die den "Bezugssperren"-Mutex 309 entriegelt und den aufrufenden Thread in Abhängigkeit von einem Prädikat, dass der Objektsperren-Mutex 329 entriegelt wurde, in Ruhe versetzt. Sobald das Prädikat erfüllt ist, wird der aktuelle Thread mit dem verriegelten "Bezugssperren"-Mutex 309 fortgesetzt. Sobald der aktuelle Thread fortgesetzt wird, fährt der Objektverriegelungsprozess 750 zur "Verriegelungsversuchs"-Prozedur 753 fort, um wieder zu versuchen, den Objektsperren-Mutex 329 zu verriegeln.

Ein Fachmann wird verstehen, dass die Erfindung eine oder mehrere Gruppen von zusammenhängenden Objekten oder Datenstrukturen verwaltet. In einer multithreading-fähigen Umgebung kann nur ein einzelner Thread auf eine Gruppe in irgendeinem gegebenen Fall zugreifen. Somit serialisiert die Erfindung den Threadzugriff auf eine Gruppe mit minimaler Größe, um die Anzahl von Threads, die verwendet werden können, um die Gruppen von zusammenhängenden Datenstrukturen zu verarbeiten, zu maximieren.

Aus dem Vorangehenden ist zu erkennen, dass die Erfindung (ohne Begrenzung) die folgenden Vorteile aufweist:

  • 1) Die Erfindung verwaltet eine minimale Gruppe von zusammenhängenden Objekten, auf die durch einen Thread ohne Unterbrechung durch einen anderen Thread zugegriffen wird.
  • 2) Die Erfindung verriegelt nicht unnötig nicht-zusammenhängende Objekte und blockiert folglich nicht unnötig Threads, indem sie eine minimale Gruppe von zusammenhängenden Objekten verwaltet.
  • 3) Die Erfindung stellt einen effizienten Mechanismus zum Kombinieren von Gruppen von Objekten in einer Objektsammlung bereit.


Anspruch[de]
  1. Computergesteuertes Verfahren zum Verriegeln eines interessierenden Objekts in einer Objektsammlung (221), ohne ein nicht-zusammenhängendes Objekt verriegelt zu halten, wobei auf die Objektsammlung durch einen oder mehrere Threads in einer multithreading-fähigen Rechnerumgebung zugegriffen wird und eine Gruppensperre (223, 225) den Threadzugriff auf eine jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211), die das interessierende Objekt enthält, steuert, wobei das Verfahren gekennzeichnet ist durch:

    (a) zuordnen einer Bezugssperre (227) zu der Objektsammlung (221), um den Threadzugriff auf eine Vielzahl von Gruppensperrenverkettungen, die von der Gruppensperre (223, 225) verwendet werden, zu steuern;

    (b) Modifizieren der Vielzahl von Gruppensperrenverkettungen als Reaktion auf eine Änderung einer Beziehung zwischen einem ersten Objekt innerhalb der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zu einem zweiten Objekt; und

    (c) Verriegeln der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211), die das interessierende Objekt enthält, wodurch das interessierende Objekt und seine untereinander zusammenhängenden Objekte verriegelt werden.
  2. Computergesteuertes Verfahren nach Anspruch 1, wobei Schritt (c) umfasst:

    (c1) Verriegeln der Bezugssperre (227); dann

    (c2) Verriegeln der Gruppensperre (223, 225), die der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zugeordnet ist; und dann

    (c3) Entriegeln der Bezugssperre (227).
  3. Computergesteuertes Verfahren nach Anspruch 1, wobei die jeweilige Gruppe von untereinander zusammenhängenden Objekten eine erste Gruppe von untereinander zusammenhängenden Objekten (201) ist, die einer ersten Gruppensperre (223) zugeordnet ist, wobei das zweite Objekt zu einer zweiten Gruppe von untereinander zusammenhängenden Objekten (211) gehört, die einer zweiten Gruppensperre (225) zugeordnet ist, und Schritt (b) ferner umfasst:

    (b1) Verriegeln der Bezugssperre (227); dann

    (b2) Kombinieren der ersten Gruppe von untereinander zusammenhängenden Objekten (201) und der zweiten Gruppe von untereinander zusammenhängenden Objekten (211) zu einer kombinierten Gruppe von untereinander zusammenhängenden Objekten, die einer einzelnen Gruppensperre zugeordnet ist; und dann

    (b3) Entriegeln der Bezugssperre (227).
  4. Computergesteuertes Verfahren nach Anspruch 1, wobei das zweite Objekt unabhängig ist und Schritt (b) ferner umfasst:

    (b1) Verriegeln der Bezugssperre (227); dann

    (b2) Zuweisen des zweiten Objekts zur jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211); und dann

    (b3) Entriegeln der Bezugssperre (227).
  5. Computergesteuertes Verfahren nach Anspruch 1, wobei das interessierende Objekt ein gerichtetes azyklisches Graphenobjekt ist, das die jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211) und eine der Gruppensperren (223, 225) in Zusammenhang bringt.
  6. Computergesteuertes Verfahren nach Anspruch 1, wobei das gerichtete azyklische Graphenobjekt eine Bildverarbeitungsoperation (207, 215) beschreibt.
  7. Vorrichtung mit einer Zentralverarbeitungseinheit (103) und einem Speicher (105), der mit der CPU (103) gekoppelt ist, um ein interessierendes Objekt in einer Objektsammlung (221) zu verriegeln, ohne ein nicht-zusammenhängendes Objekt verriegelt zu halten, wobei auf die Objektsammlung (200) durch einen oder mehrere Threads in einer multithreading-fähigen Rechnerumgebung zugegriffen wird und eine Gruppensperre (223, 225) den Threadzugriff auf eine jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211), die das interessierende Objekt enthält, steuert, wobei die Vorrichtung gekennzeichnet ist durch:

    einen Bezugssperrmechanismus, der dazu ausgelegt ist, der Objektsammlung (221) eine Bezugssperre (227) zuzuordnen, um den Threadzugriff auf eine Vielzahl von Gruppensperrenverkettungen, die von der Gruppensperre (223, 225) verwendet werden, zu steuern;

    einen Gruppenmodifikationsmechanismus, der dazu ausgelegt ist, die jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211) durch Ändern der Beziehung zwischen einem ersten Objekt innerhalb der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zu einem zweiten Objekt zu modifizieren; und

    einen Gruppenverriegelungsmechanismus, der dazu ausgelegt ist, die jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211), die das interessierende Objekt enthält, zu verriegeln, wodurch das interessierende Objekt und seine untereinander zusammenhängenden Objekte verriegelt werden.
  8. Vorrichtung nach Anspruch 7, wobei der Gruppenverriegelungsmechanismus umfasst:

    einen Bezugssperren-Verriegelungsmechanismus, der dazu ausgelegt ist, die Bezugssperre (227) zu verriegeln; dann

    einen jeweiligen Gruppenverriegelungsmechanismus, der dazu ausgelegt ist, die Gruppensperre (223, 225), die der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zugeordnet ist, zu verriegeln, nachdem die Bezugssperre (227) durch den Bezugssperren-Verriegelungsmechanismus verriegelt wurde; und

    einen Bezugssperren-Entriegelungsmechanismus, der dazu ausgelegt ist, die Bezugssperre (227) zu entriegeln, nachdem die Gruppensperre (223, 225) durch den jeweiligen Gruppenverriegelungsmechanismus verriegelt wurde.
  9. Vorrichtung nach Anspruch 7, wobei die jeweilige Gruppe von untereinander zusammenhängenden Objekten (223, 225) eine erste Gruppe von untereinander zusammenhängenden Objekten (201) ist, die einer ersten Gruppensperre (223) zugeordnet ist, wobei das zweite Objekt zu einer zweiten Gruppe (211) von untereinander zusammenhängenden Objekten gehört, die einer zweiten Gruppensperre (225) zugeordnet ist, und der Gruppenmodifikationsmechanismus ferner umfasst:

    einen Gruppenkombinationsmechanismus, der dazu ausgelegt ist, die erste Gruppe von untereinander zusammenhängenden Objekten (201) und die zweite Gruppe von untereinander zusammenhängenden Objekten (211), die durch den Gruppenzuweisungsmechanismus untereinander in Zusammenhang gebracht werden, zu einer kombinierten Gruppe von untereinander zusammenhängenden Objekten (201, 211), die einer einzelnen Gruppensperre zugeordnet ist, zu kombinieren, während die Bezugssperre (227) verriegelt ist.
  10. Vorrichtung nach Anspruch 7, wobei das zweite Objekt unabhängig ist und der Gruppenmodifikationsmechanismus ferner einen Gruppenzuweisungsmechanismus umfasst, der dazu ausgelegt ist, das zweite Objekt der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zuzuweisen, während die Bezugssperre (227) verriegelt ist.
  11. Vorrichtung nach Anspruch 7, wobei das interessierende Objekt ein gerichtetes azyklisches Graphenobjekt ist, das die jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211) und eine der Gruppensperren (223, 225) in Zusammenhang bringt.
  12. Vorrichtung nach Anspruch 7, wobei das gerichtete azyklische Graphenobjekt eine Bildverarbeitungsoperation (207, 215) beschreibt.
  13. Computerprogrammprodukt mit:

    einem vom Computer verwendbaren Speichermedium (105, 117) mit einem in diesem verkörperten maschinenlesbaren Code (119), um einen Computer (100) zu veranlassen, ein interessierendes Objekt in einer Objektsammlung (221) zu verriegeln, ohne ein nicht zusammenhängendes Objekt verriegelt zu halten, wobei auf die Objektsammlung durch einen oder mehrere Threads in einer multithreading-fähigen Rechnerumgebung zugegriffen wird und eine Gruppensperre (223, 225) den Threadzugriff auf eine jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211), die das interessierende Objekt enthält, steuert, wobei der maschinenlesbare Code (119) gekennzeichnet ist durch:

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Bezugssperrmechanismus auszuführen, der dazu ausgelegt ist, der Objektsammlung (221) eine Bezugssperre (227) zuzuordnen, um den Threadzugriff auf eine Vielzahl von Gruppensperrenverkettungen, die von der Gruppensperre (223, 225) verwendet werden, zu steuern;

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Gruppenmodifikationsmechanismus auszuführen, der dazu ausgelegt ist, die jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211) durch Ändern der Beziehung zwischen einem ersten Objekt innerhalb der jeweiligen Gruppe von untereinander zusammenhängenden Objekten zu einem zweiten Objekt zu modifizieren; und

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Gruppenverriegelungsmechanismus auszuführen, der dazu ausgelegt ist, die jeweilige Gruppe von untereinander zusammenhängenden Objekten (201, 211), die das interessierende Objekt enthält, zu verriegeln, wodurch das interessierende Objekt und seine untereinander zusammenhängenden Objekte verriegelt werden.
  14. Computerprogrammprodukt nach Anspruch 13, wobei der Gruppenverriegelungsmechanismus umfasst:

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Bezugssperren-Verriegelungsmechanismus auszuführen, der dazu ausgelegt ist, die Bezugssperre (227) zu verriegeln; dann

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen jeweiligen Gruppenverriegelungsmechanismus auszuführen, der dazu ausgelegt ist, die Gruppensperre (223, 225), die der jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zugeordnet ist, zu verriegeln, nachdem die Bezugssperre (227) durch den Bezugssperren-Verriegelungsmechanismus verriegelt wurde; und

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Bezugssperren-Entriegelungsmechanismus auszuführen, der dazu ausgelegt ist, die Bezugssperre (227) zu entriegeln, nachdem die Gruppensperre (223, 225) durch den jeweiligen Gruppenverriegelungsmechanismus verriegelt wurde.
  15. Computerprogrammprodukt nach Anspruch 13, wobei die jeweilige Gruppe von untereinander zusammenhängenden Objekten eine erste Gruppe von untereinander zusammenhängenden Objekten (201) ist, die einer ersten Gruppensperre (223) zugeordnet ist, wobei das zweite Objekt zu einer zweiten Gruppe von untereinander zusammenhängenden Objekten (211) gehört, die einer zweiten Gruppensperre (225) zugeordnet ist, und der Gruppenmodifikationsmechanismus ferner umfasst:

    einen maschinenlesbaren Programmcode, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Gruppenkombinationsmechanismus auszuführen, der dazu ausgelegt ist, die erste Gruppe von untereinander zusammenhängenden Objekten (201) und die zweite Gruppe von untereinander zusammenhängenden Objekten (211), die durch den Gruppenzuweisungsmechanismus untereinander in Zusammenhang gebracht werden, zu einer kombinierten Gruppe von untereinander zusammenhängenden Objekten zu kombinieren, die einer einzelnen Gruppensperre zugeordnet ist, während die Bezugssperre (227) verriegelt ist.
  16. Computerprogrammprodukt nach Anspruch 13, wobei das zweite Objekt unabhängig ist und der Gruppenmodifikationsmechanismus ferner einen maschinenlesbaren Programmcode umfasst, der dazu ausgelegt ist, den Computer (100) zu veranlassen, einen Gruppenzuweisungsmechanismus auszuführen, der dazu ausgelegt ist, das zweite Objekt zur jeweiligen Gruppe von untereinander zusammenhängenden Objekten (201, 211) zuzuweisen, während die Bezugssperre (227) verriegelt ist.
  17. Computerprogrammprodukt nach Anspruch 13, wobei das interessierende Objekt ein gerichtetes azyklisches Graphenobjekt ist, das die jeweilige Gruppe von untereinander zusammenhängenden Objekten und eine der Gruppensperren in Zusammenhang bringt.
  18. Computerprogrammprodukt nach Anspruch 13, wobei das gerichtete azyklische Graphenobjekt eine Bildverarbeitungsoperation beschreibt.
Es folgen 10 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com