DE69937593T2

DE69937593T2 - Verfahren und Vorrichtung zur Integrierung von Zug- und Druck-Aufgaben in Fliessband-Datenverarbeitung

Info

Publication number: DE69937593T2
Application number: DE69937593T
Authority: DE
Inventors: Dennis L. Marion Venable; Patrick A. Rochester Fleckenstein; James E. Williamson Bollman
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1998-08-17
Filing date: 1999-08-13
Publication date: 2008-03-06
Anticipated expiration: 2019-08-14
Also published as: EP0981082A2; JP2000090055A; DE69937593D1; EP0981082A3; US6286026B1; JP4318806B2; EP0981082B1

Description

Die vorliegende Erfindung betrifft Datenverarbeitung mit Pull- und Push-Aufgaben.
In einem System, das eine Multiprozessorverarbeitungs-Pipeline unter Verwendung einer Umgebung mit Ein-Prozessor-Verarbeitung emuliert, ist jeder Abschnitt der Pipeline ein instantiierte Funktion bzw. Aufgabe, die eine oder mehrere gewünschte Funktionen, wie beispielsweise Bildverarbeitungsfunktionen, durchführt, und eine ausreichende Datenstruktur, um den Status der Aufgabe selbst zu definieren.
In Funktion wird, wenn eine Host-Anwendung Daten von einer Rohdatenquelle zur Verarbeitung anfordert, so beispielsweise Bilddaten von einem Scanner oder einer Bilddatendatei, eine Verarbeitungspipeline zwischen der Datenquelle und der Host-Anwendung ausgebildet. Die Datenverarbeitungs-Pipeline gibt die Rohdaten von der Datenquelle ein, verarbeitet die Daten so, dass sie in einer Form sind, die die Host-Anwendung nutzen kann, und stellt sie dann der Host-Anwendung bereit.
Die Bildverarbeitungs-Pipeline wird ausgebildet, indem beispielsweise eine der Funktionen in einer Bildverarbeitungsbibiliothek aufgerufen wird und die aufgerufene Funktion instantiiert wird, um eine erste Aufgabe auszubilden. Die erste Aufgabe wird zu einem am weitesten stromauf liegenden bzw. vorgelagerten Abschnitt der Pipeline. Der am weitesten vorgelagerte Pipelineabschnitt bezieht ein zu verarbeitendes Datenelement von der Datenquelle. In einem Bildverarbeitungssystem könnte das Datenelement eine einzelne Scanzeile eines Rasterscans eines Bildes sein. Die Datenquelle könnte ein Scanner, ein Faxgerät, ein entfernter Computer, ein Sensor oder dergleichen sein, der ein serielles oder paralleles Datensignal ausgibt, oder ein Block gespeicherter Daten in einem Speicher, wie einem ROM, einem RAM oder einer Platte in einem Plattenlaufwerk. Das Datenelement kann auch direkt durch den ersten Pipeline-Abschnitt selbst erzeugt werden. In diesem letzteren Fall kann das Datenelement aus dem Wert einer initialisierten Variable, aus dem Zustand des ersten Pipeline-Abschnitts oder dergleichen gewonnen werden. Wenn der erste Pipeline-Abschnitt instantiiert ist, wird eine Rückwärts- oder Stromauf-Verbindung der Host-Anwendung zu dem ersten Pipeline-Abschnitt eingerichtet.
Ein zweiter Pipeline-Abschnitt wird dann im Allgemeinen benötigt, um das durch den ersten Pipeline-Abschnitt gewonnene Datenelement zu verarbeiten. Daher erzeugt die Host-Anwendung eine weitere Aufgabe durch Instantiieren einer der Funktionen in der Bibiliothek, um einen zweiten Pipeline-Abschnitt auszubilden. Wenn dieser zweite Pipeline-Abschnitt erzeugt wird, wird er automatisch mit dem ersten Pipeline-Abschnitt verbunden. Zusätzlich wird die Verbindung der Host-Anwendung auf den zweiten Pipeline-Abschnitt zurückgesetzt. Wenn keine weiteren Bildverarbeitungsoperationen erforderlich sind, bleibt die Verbindung der Host-Anwendung zwischen dem Abschnitt der Host-Anwendung, der die zu verarbeitenden Daten benötigt, und dem zweiten Pipeline-Abschnitt bestehen.
Verarbeitungsaufgaben in einer Pipeline-Verarbeitung sind üblicherweise so ausgelegt, dass sie auf effiziente Weise miteinander in Verbindung stehen, so dass ein Minimum an externer Steuerung zum Verarbeiten der Daten erforderlich ist. Herkömmlicherweise sind jedoch nur ähnliche Typen von Verarbeitungsaufgaben zusammengefasst, um ein Verarbeitungsziel zu erreichen. Diese Einschränkung ist unvorteilhaft, und daher ist die neue Technologie erforderlich, um größere Flexibilität bei Pipeline-Datenverarbeitung zu ermöglichen.
Die vorliegende Erfindung schafft eine Vorrichtung sowie ein Verfahren zum Verarbeiten von Daten mit einer Datenverarbeitungskette, die Push- und Pull-Aufgaben aufweist. Push-Aufgaben verarbeiten Daten und führen den Ausgang der Verarbeitung nachgelagerten Push-Aufgaben auf Basis von Verbindungswegen im Push-Verfahren zu. Pull-Aufgaben hingegen senden Datenanforderungen über vorgelagerte Verbindungen zu vorgelagerten Pull-Aufgaben, um Daten zur Verarbeitung zu erfassen.
Datenverarbeitungsketten sind üblicherweise entweder nur mit Push-Aufgaben oder nur Pull-Aufgaben konfiguriert, um Konsistenz in der Richtung von Verbindungen aufrechtzuerhalten. Die bevorzugten Ausführungen der vorliegenden Erfindung schaffen ein Verfahren und eine Vorrichtung zum Einfügen von Push-Aufgaben in eine Kette von Pull-Aufgaben und/oder zum Einfügen von Pull-Aufgaben in eine Kette von Push-Aufgaben. Die eingefügten Push- und Pull-Aufgaben werden mit Vorwärts- und Rückwärtsnachrichtenverbindungen verstärkt und Schnittstellen-Aufgaben werden bereitgestellt, um Schnittstellen zwischen den eingefügten Pull- oder Push-Aufgaben in den Ketten von Push- bzw. Pull-Aufgaben zu schaffen.
Wenn Pull-Aufgaben in eine Kette von Push-Aufgaben eingefügt werden, wird eine erste Schnittstellen-Aufgabe zwischen vorgelagerten Push-Aufgaben und eingefügten Pull-Aufgaben angeordnet, und eine zweite Schnittstelle wird zwischen den eingefügten Pull-Aufgaben und nachgelagerten Push-Aufgaben angeordnet. Wenn vorgelagerte Push- Aufgaben Daten im Push-Verfahren der ersten Schnittstellen-Aufgabe zugeführt werden, ruft die erste Schnittstellen-Aufgabe eine Vorwärts-Nachricht auf, die die Menge an Daten für die nachgelagerten eingefügten Pull-Aufgaben anzeigt. Jede der aufeinanderfolgenden Pull-Aufgaben erzeugt auch Vorwärts-Nachrichten, die die Menge an Daten anzeigen, die verfügbar sind, bis die Informationen zu der zweiten Schnittstellen-Aufgabe gelangen. Die zweite Schnittstellen-Aufgabe erzeugt dann eine Datenanforderung und leitet die Datenanforderung über die eingefügten Pull-Aufgaben bis zu der ersten Schnittstellen-Aufgabe. Die erste Schnittstellen-Aufgabe reagiert, indem sie Daten stromab sendet, bis die zweite Schnittstellen-Aufgabe die verarbeiteten Daten empfängt und die verarbeiteten Daten im Push-Verfahren nachgelagerten Push-Aufgaben zuführt.
Wenn Push-Aufgaben in eine Kette von Pull-Aufgaben eingefügt werden, wird eine dritte Schnittstellen-Aufgabe zwischen vorgelagerte Pull-Aufgaben und eingefügte Push-Aufgaben eingefügt, und eine vierte Schnittstellen-Aufgabe wird zwischen die eingefügten Push-Aufgaben und nachgelagerte Pull-Aufgaben eingefügt. Wenn die nachgelagerten Pull-Aufgaben eine Datenanforderung zu der vierten Schnittstellen-Aufgabe senden, sendet die vierte Schnittstellen-Aufgabe eine Rückwärts-Nachricht zu vorgelagerten eingefügten Pull-Aufgaben. Die Rückwärts-Nachricht wird über die eingefügten Pull-Aufgaben weitergeleitet, bis eine Rückwärts-Nachricht zu der dritten Schnittstellen-Aufgabe gesendet wird. Die dritte Schnittstellen-Aufgabe reagiert, indem sie eine Datenanforderung zu den vorgelagerten Pull-Aufgaben sendet, was dazu führt, dass eine erste Pull-Aufgabe Daten im Pull-Verfahren aus einer Datenbank bezieht. Wenn die vorgelagerten Pull-Aufgaben die Daten aus der Datenbank verarbeiten und die Daten zu der dritten Schnittstellen-Aufgabe zurückführen, führt die dritte Schnittstellen-Aufgabe die Daten den eingefügten Push-Aufgaben im Push-Verfahren zu, was dazu führt, dass Daten im Push-Verfahren der vierten Schnittstellen-Aufgabe zugeführt werden. Wenn die vierte Schnittstellen-Aufgabe die im Push-Verfahren von den eingefügten Push-Aufgaben zugeführten Daten empfängt, werden die Daten zu der nachgelagerten Pull-Aufgabe zurückgeführt, die die Daten ursprünglich anforderte.
Wie aus dem Obenstehenden hervorgeht, ermöglichen es die erste, die zweite, die dritte und die vierte Schnittstellen-Aufgabe sowie die Vorwärts-Nachrichten und Rückwärts-Nachrichtenverbindungen, Push-Aufgaben in eine Kette von Pull-Aufgaben einzufügen und Pull-Aufgaben in eine Kette von Push-Aufgaben einzufügen.
Die vorliegende Erfindung wird im Zusammenhang mit den folgenden Figuren beschrieben, in denen sich gleiche Bezugszeichen auf gleiche Elemente beziehen, wobei:
1 eine Datenverarbeitungs-Pipeline zeigt, die nur Pull-Aufgaben aufweist;
2 ein Blockschema einer Pull-Aufgabe zeigt;
3 einen ersten Satz von Prozess-Stack-Status für eine der in 1 dargestellten Verarbeitungsketten zeigt;
4 einen zweiten Satz von Prozess-Stack-Status für die gleiche Verarbeitungskette in 3 zeigt;
5 eine Datenverarbeitungs-Pipeline zeigt, die nur Push-Aufgaben aufweist;
6 ein Blockschema einer Push-Aufgabe zeigt;
7 eine Pipeline-Verarbeitungskette zeigt, bei der Pull-Aufgaben in eine Kette von Push-Aufgaben eingefügt sind;
8–10 Blockschemata der Schnittstellen-Aufgaben und der in 7 gezeigten Pull-Aufgaben zeigen;
11 ein Blockschema einer Verarbeitungseinrichtung zum Verarbeiten von Datenverarbeitungs-Pipelines zeigt;
12 ein Flussdiagramm des Prozesses für die in 7 dargestellte Datenverarbeitungskette zeigt;
13 eine Datenverarbeitungskette zeigt, bei der Push-Aufgaben in eine Kette von Pull-Aufgaben eingefügt sind;
14–16 Blockschemata für die Schnittstellen-Aufgaben und die in 13 gezeigten Push-Aufgaben zeigen; und
17 ein Flussdiagramm für den in 13 gezeigten Prozess zeigt.
Eine Funktion in einer Umgebung mit Ein-Prozessor-Verarbeitung kann als Pull-Aufgabe oder als Push-Aufgabe instantiiert sein. Pull-Aufgaben bilden eine Verarbeitungskette durch vorgelagerte bzw. Stromauf-Verbindungen. Wenn Daten zur Verarbeitung erforderlich sind, gibt eine Pull-Aufgabe eine Datenanforderung an eine vorgelagerte Pull- Aufgabe aus. Die Datenanforderung bleibt aktiv, bis die angeforderten Daten durch die vorgelagerte Pull-Aufgabe zugeführt werden. Daher beginnt in einer Pipeline von Pull-Aufgaben eine Host-Anwendung, die den Ausgang der Pipeline empfängt, indem sie Daten von einer "letzten" Pull-Aufgabe anfordert, und die Datenanforderung wird bis zu einer ersten Pull-Aufgabe der Pipeline weitergeleitet, die ihrerseits die erforderlichen Daten von einer Datenquelle, wie beispielsweise einer Datenbank, abruft. So verläuft in einer Verarbeitungskette oder -Pipeline von Pull-Aufgaben die Richtung der Datenanforderungen stromauf, während der Datenfluss stromab verläuft.
In einer Verarbeitungskette oder -Pipeline aus Push-Aufgaben gibt es keine Datenanforderungen, da Daten von einer Push-Aufgabe im "Push"-Verfahren zu einer verbundenen nachgelagerten Push-Aufgabe geleitet werden. Die Host-Anwendung beginnt, indem sie Daten im Push-Verfahren einer ersten Push-Aufgabe der Pipeline zuführt. Daten werden verarbeitet und anschließend im Push-Verfahren stromab auf Basis der Verbindungen zugeführt, bis Ausgangsdaten durch eine letzte Push-Aufgabe im Pushverfahren aus der Pipeline ausgegeben werden. Das heißt, bei Push-Aufgaben verlaufen sowohl die Richtung von Verbindungen als auch die Richtung des Datenflusses stromab.
Daten werden durch die Pull- und die Push-Aufgaben in Standard-Größeneinheiten verarbeitet. Bei Bildverarbeitung in Vorrichtungen wie beispielsweise Digitalkameras, Druckern, Scannern und Faxgeräten usw. kann die Größeneinheit beispielsweise eine Zeile sein. So kann eine Pull-Aufgabe Daten von einer vorgelagerten Pull-Aufgabe jeweils zeilenweise anfordern. Wenn mehrere Zeilen für einen bestimmten Prozess benötigt werden, werden mehrere Datenanforderungen ausgegeben und die Daten werden in dem Speicher gepuffert, bis die benötigte Anzahl von Zeilen empfangen ist. Ein ähnlicher Speicher kann für Push-Aufgaben erforderlich sein. Daten, die im Push-Verfahren von vorgelagerten Push-Aufgaben zugeführt werden, werden in dem Speicher gepuffert, bis ausreichend Daten zur Fortsetzung des dazugehörigen Prozesses empfangen sind.
Pull- oder Push-Aufgaben können die Bilddaten beispielsweise um einen Faktor 2:1 verkleinern. So können zwei Zeilen erforderlich sein, bevor der Prozess ausgeführt werden kann, um eine Ausgabezeile zu erzeugen. In einer Pipeline aus Pull- oder Push-Aufgaben kann jede beliebige der Aufgaben mehrere Eingabeeinheiten erfordern, bevor die Verarbeitung beginnen kann. So kann es zu zahlreichen Stromauf-Pull-Vorgängen und Stromab-Push-Vorgängen kommen, ehe Daten schließlich durch die letzte Aufgabe ausgegeben werden.
1 beispielsweise zeigt ein Blockschema 200 einer Datenverarbeitung unter Verwendung von Pull-Aufgaben 202–214. Das Blockschema 200 weist drei Verarbeitungsketten auf, wobei jede der Verarbeitungsketten zwei seriell verbundene Pull-Aufgaben enthält. Die erste Kette beispielsweise enthält die Pull-Aufgaben 202 und 204 mit Datenwegen 220 und 222 und Verbindungswegen 240 und 242, die zweite Kette enthält Pull-Aufgaben 206 und 208 und hat Datenwege 226 und 228 sowie Verbindungswege 246 und 248 und die dritte Kette enthält Pull-Aufgaben 210 und 212 und hat Datenwege 232 und 234 sowie Verbindungswege 252 und 254.
Die drei Ketten von Pull-Aufgaben sind zu einer Misch(merge)-Pull-Aufgabe 214 (die eine letzte Pull-Aufgabe ist) über die Datenwege 224, 230 und 236 sowie die Verbindungswege 244 und 250 und 256 gekoppelt. Die Misch-Pull-Aufgabe 214 kann eine Anwendung, eine physikalische Vorrichtung oder eine andere Pull-Aufgabe sein, die ihre eigene Funktion ähnlich wie beispielsweise die anderen Pull-Aufgaben 202–212 erfüllt. Wenn die Misch-Pull-Aufgabe 214 eine weitere Pull-Aufgabe ist, dann wäre ein Verbindungsweg (nicht dargestellt) als Eingang in die Misch-Pull-Aufgabe 214 vorhanden. Die Misch-Pull-Aufgabe 214 erzeugt Ausgangsdaten, die über Datenweg 238 ausgegeben werden.
Das Blockschema 200 kann einen Prozess zum Verarbeiten von Farbdaten darstellen, wobei jede der Ketten einen Typ Farbe verarbeitet und die Misch-Pull-Aufgabe 214 alle drei Farben zu einem abschließendem Bild zur Ausgabe kombiniert. Wenn davon ausgegangen wird, dass die Misch-Pull-Aufgabe 214 jeweils eine Zeile der Bilddaten verarbeitet, kann, wenn die Verarbeitung für eine aktuelle Zeile abgeschlossen ist, die Pull-Aufgabe 214 Daten von den vorgelagerten Pull-Aufgaben 204, 208 und 212 über die Verbindungswege 244, 250 und 256 für eine nächste Datenzeile anfordern. Beim Empfangen der entsprechenden Datenanforderung fordert jede der Pull-Aufgaben 204, 208 und 212 Daten über die Verbindungswege 242, 248 und 254 von weiteren vorgelagerten Pull-Aufgaben 202, 206 bzw. 210 die Daten an, die zum Erzeugen der durch die Pull-Aufgabe 214 angeforderten Zeile von Daten erforderlich sind.
In Reaktion auf die Datenanforderung von den Pull-Aufgaben 204, 208 und 212 geben die Pull-Aufgaben 202, 206 und 210 auch Datenanforderungen an weitere Pull-Aufgaben, die ihnen vorgelagert sind, über die Verbindungswege 240, 246 bzw. 252 aus. Dies setzt sich fort, bis erste Pull-Aufgaben Datenanforderungen von entsprechenden nachgelagerten Pull-Aufgaben empfangen. Die ersten Pull-Aufgaben beziehen Da ten im Pull-Verfahren aus einer Datenbank, wenn derartige Daten verfügbar sind. Wenn die Daten von der Datenbank empfangen werden, verarbeiten die ersten Pull-Aufgaben die Daten und führen ihre Ausgänge zu den jeweiligen nachgelagerten Pull-Aufgaben zurück. Die nachgelagerten Pull-Aufgaben verarbeiten die Daten weiter und führen die Ausgänge an weiter nachgelagerte Pull-Aufgaben zurück usw., bis die Daten in der Kette von Pull-Aufgaben weitergeleitet werden und schließlich die Misch-Pull-Aufgabe 214 erreichen. Die Pull-Aufgabe 214 kombiniert alle von denen drei unabhängigen Ketten empfangenen Daten und verarbeitet die Daten entsprechend zur Ausgabe über den Datenweg 238. So verläuft die Richtung von Verbindungswegen, wie durch Pfeil 260 dargestellt, stromauf, während die Richtung des Datenflusses, wie mit Pfeil 262 dargestellt, stromab verläuft.
2 zeigt ein Blockschema einer allgemeinen Pull-Aufgabe 102 detaillierter. Die Pull-Aufgabe 102 enthält eine Stromauf-Verbindung 106 und einen Datenpuffer 108. Die Stromauf-Verbindung 106 verleiht, wie bereits erläutert, die Fähigkeit Datenanforderung zu angegebenen vorgelagerten Aufgaben zu senden, wenn Daten zur Verarbeitung benötigt werden. Der Datenpuffer 108 speichert empfangene Daten, bis genügend Daten (beispielsweise Zeilen) empfangen worden sind, um den Prozess der Pull-Aufgabe abzuschließen. Der Datenpuffer 108 ist möglicherweise nicht nötig, wenn der Prozess der Pull-Aufgabe für jede empfangene Zeile mit der Verarbeitung beginnen kann.
Die Pull-Aufgaben 202–214 sind, wie bereits erläutert, in einer Umgebung mit Einzel-Prozessor-Verarbeitung instantiiert. Wenn Daten von einer Pull-Aufgabe zu einer anderen weitergeleitet werden, werden die Daten in einem Speicher gespeichert, und ein Zeiger auf die Adresse der Daten wird von einer instantiierten Pull-Aufgabe zur nächsten weitergeleitet. Daher muss, wenn eine bestimmte Pull-Aufgabe mehr als eine Dateneinheit (z.B. eine Zeile) erfordert, ein Datenpuffer (Speicherplatz) für die spezielle Pull-Aufgabe zugewiesen werden.
3 zeigt ein Beispiel eines Prozess-Stacks 400 der Umgebung mit Einzel-Controller-Verarbeitung für die erste Verarbeitungskette, die Pull-Aufgaben 202, 204 und 214 enthält. Der Prozess-Stack 400 zeichnet die Sequenz von Aufgaben (in den Prozess-Stack 400 im Push-Verfahren eingeleitet) auf, die den Einzel-Controller gesteuert haben. Diese Sequenz muss durch die Aufgaben in umgekehrter Reihenfolge nachverfolgt werden, um entsprechende Kontrolle über die Verarbeitungsumgebung zu behalten. Die Daten, die in den Prozess-Stack 400 eingegeben werden, können der Befehlszähler und mögli cherweise der Maschinenstatus des Controllers sein, der einer Aufgabe entspricht, so dass Steuerung an die Aufgabe zurückgegeben werden kann, wenn die Daten beispielsweise von dem Prozess-Stack-400 abgehoben (zurückgewonnen) werden.
Die Sequenz von Datenanforderungen beginnt, wie in 1 gezeigt, mit der Pull-Aufgabe 214, die über den Verbindungsweg 244 Daten von der Pull-Aufgabe 204 anfordert. Wenn die Pull-Aufgabe 214 eine solche Datenanforderung stellt, wird die Datenanforderung DR(244) im Push-Verfahren dem Prozess-Stack 400 zugeführt, wodurch ein Prozess-Stack-Status 404 entsteht. In Reaktion auf die Datenanforderung von der Pull-Aufgabe 214 wird Steuerung an die Pull-Aufgabe 204 übergeben, die eine Datenanforderung über Verbindungsweg 242 an Pull-Aufgabe 202 stellt, und die Datenanforderung DR(242) wird im Push-Verfahren dem Prozess-Stack 400 zugeführt, wodurch ein Prozess-Stack-Status 406 entsteht und die Steuerung wird an die Pull-Aufgabe 202 übergeben.
Wenn davon ausgegangen wird, dass die Pull-Aufgabe 202 ein erste Pull-Aufgabe ist, zeigt der Verbindungsweg 204 zu einer Datenquelle, wie beispielsweise einer Datenbank, in der Daten zur Verarbeitung gesammelt sind. So sendet die Pull-Aufgabe 202 eine Datenanforderung an die Datenbank über den Verbindungsweg 240, und die Datenanforderung DR(240) wird im Push-Verfahren dem Prozess-Stack 400 zugeführt, wodurch ein Prozess-Stack-Status 408 entsteht. An diesem Punkt wird die Steuerung an die Datenbank übergeben und der Prozess-Stack 400 enthält drei Datenanforderungen, die den Verbindungswegen 240, 242 und 244 in dieser Reihenfolge entsprechen.
Wenn die Datenbank die Daten D(222) auf dem Datenweg 200 entsprechend der durch die Pull-Aufgabe 202 ausgegebenen Datenanforderungen zurückführt, wird die Datenanforderung DR(240) von dem Prozess-Stack 400 abgehoben, wodurch ein Prozess-Stack-Status 410 entsteht, und die Steuerung wird an die Pull-Aufgabe 202 zurückgeführt. Die Pull-Aufgabe 202 verarbeitet die von der Datenbank empfangenen Daten und gibt das Ergebnis D(222) auf dem Datenweg 222 an die Pull-Aufgabe 204 aus, und die Datenanforderung DR(242) wird von dem Prozess-Stack 400 abgehoben, wie dies durch Prozess-Stack-Status 412 dargestellt ist, und die Steuerung wird zu der Pull-Aufgabe 204 zurückgeführt. Die Pull-Aufgabe 204 ihrerseits verarbeitet die von der Pull-Aufgabe 202 empfangenen Daten und gibt das Ergebnis D(224) auf dem Datenweg 224 an die Misch-Pull-Aufgabe 214 aus, die die Datenanforderung DR(244) abhebt, wodurch ein leerer Prozess-Stack 400 entsteht, wie dies mit dem Prozess-Stack-Status 414 darge stellt ist, und die Steuerung wird zu der Misch-Pull-Aufgabe 214 zurückgeführt, bei der die Sequenz begann. So werden durch die Datenanforderungen auf den Verbindungswegen 244, 242 und 240 die Datenanforderungen DR(244, 242 und 240) im Push-Verfahren dem Prozess-Stack 400 zugeführt, und die über die Datenwege 220, 222 und 224 zurückgeführten Daten heben die Datenanforderungen DR(244, 242 und 240) aus dem Prozess-Stack 400 ab. Steuerung wird von der Misch-Pull-Aufgabe 214 an die Pull-Aufgabe 204 und die Pull-Aufgabe 202 sowie die Datenbank weitergegeben und zu der Pull-Aufgabe 202, der Push-Aufgabe 204 und schließlich zu der Misch-Pull-Aufgabe 214 zurückgeführt.
4 zeigt eine Situation, in der die Pull-Aufgabe 204 zwei Datenzeilen anfordert, bevor eine Ausgabe an die Pull-Aufgabe 214 über den Datenweg 224 erzeugt wird. Die Prozess-Stack-Status 404, 412 sind identisch mit den in 3 dargestellten. Jedoch verfügt, nachdem die Daten von der Pull-Aufgabe 202 über den Datenweg 222 empfangen worden sind, die Pull-Aufgabe 204 nicht über genug Daten, um mit der Verarbeitung zu beginnen. So fordert die Pull-Aufgabe 204 erneut Daten von der Pull-Aufgabe 202 über den Verbindungsweg 244 für die zusätzlichen Daten an, die benötigt werden, um mit der Verarbeitung zu beginnen. So wird DR(242) erneut im Push-Verfahren dem Prozess-Stack 400 zugeführt, wie dies mit dem Prozess-Stack-Status 416 dargestellt ist. Die Pull-Aufgabe 202 reagiert, indem sie eine Datenanforderung DR(240) über Verbindungsweg 240 für zusätzliche Daten von der Datenbank sendet, was durch den Prozess-Stack-Status 418 dargestellt wird. Wenn die Pull-Aufgabe 202 Daten D(220) von der Datenbank über den Datenweg 220 empfängt, wird die Datenanforderung DR(240) aus dem Stack abgehoben, wie dies in dem Prozess-Stack-Status 420 dargestellt ist, und wenn die Pull-Aufgabe 202 ihre Daten D(222) an die Pull-Aufgabe 204 ausgibt, wird die Datenanforderung DR(242) ebenfalls aus dem Prozess-Stack 400 abgehoben, wie dies mit dem Prozess-Stack-Status 422 dargestellt ist. An diesem Punkt verfügt die Pull-Aufgabe 204 über genügend Daten, um mit der Verarbeitung zu beginnen. Wenn der Ausgang der Pull-Aufgabe 204 über den Datenweg 224 zu der Pull-Aufgabe 214 gesendet wird, wird die verbleibende Datenanforderung DR(244) aus dem Prozess-Stack 400 abgehoben, so dass der Stack leer zurückbleibt, wie dies mit dem Prozess-Stack-Status 424 dargestellt ist.
5 zeigt ein Blockschema eines Prozesses 300 mit drei Ketten von Push-Aufgaben 302–314. Die erste Push-Aufgabe 302 ist eine Verzweigungs-Push-Aufgabe, die Daten von einigen vorgelagerten Prozessen empfängt, die Daten verarbeitet und die Verarbei tungsergebnisse im Push-Verfahren nachgelagerten Push-Aufgaben 304, 308 und 312 über Datenwege 322, 328 und 334 zuführt. Die Push-Aufgabe 302 identifiziert die nachgelagerten Push-Aufgaben über Verbindungswege 340, 346 und 352. Wenn Daten im Push-Verfahren einer nachgelagerten Push-Aufgabe zugeführt werden, werden die Daten, die die vorgelagerte Push-Aufgabe steuern, so beispielsweise der Programmzähler usw., ebenfalls im Push-Verfahren dem Prozess-Stack 400 zugeführt. Dies wird durch die folgende Erläuterung dargestellt, indem die Verbindung im "Push"-Verfahren dem Prozess-Stack 400 zugeführt wird. Die Push-Aufgaben 304, 308 und 312 verarbeiten die von der Push-Aufgabe 302 empfangenen Daten und führen ihre Verarbeitungsergebnisse im Push-Verfahren weiteren nachgelagerten Push-Aufgaben 306, 310 und 314 über Datenwege 324, 330 bzw. 336 zu. Die Push-Aufgaben 306, 310 und 314 geben ihre jeweiligen Verarbeitungsergebnisse, an weitere nachgelagerte Push-Aufgaben, Ausgabepuffer und/oder Vorrichtungen aus, wie sie durch die Verbindungswege 344, 350, 356 identifiziert werden. So ist bei Ketten von Push-Aufgaben die Richtung der Verbindungswege, wie sie mit Pfeil 360 gezeigt wird, die gleiche wie die Richtung des Datenflusses, wie sie mit Pfeil 362 gezeigt wird.
Wenn beispielsweise die Verzweigungs-Push-Aufgabe 302 die Daten im Push-Verfahren der Push-Aufgabe 304 über Verbindungsweg 340 zuführt, wird die Verbindung 340 L(340) im Push-Verfahren dem Prozess-Stack 400 zugeführt. Wenn die Daten schließlich im Push-Verfahren durch die Verarbeitungskette geleitet werden, hebt die Anwendung oder Vorrichtung am Ende der Verarbeitungskette bzw. -Pipeline die letzte Verbindung aus dem Prozess-Stack 400 ab, um Steuerung an die vorgelagerte Push-Aufgabe zurückzuführen, die ihrerseits die nächste Verbindung abhebt, die Steuerung zu der nächsten vorgelagerten Push-Aufgabe zurückführt usw., bis die Steuerung zu der Anwendung oder Vorrichtung zurückgeführt wird, die der Verzweigungs-Push-Aufgabe 302 vorgelagert ist.
6 zeigt ein Blockschema einer allgemeinen Push-Aufgabe 112. Die Push-Aufgabe 112 hat einen Datenpuffer 116, eine Stromab-Verbindung 118, einen Eingangs-Datenweg 114 und einen Ausgangs-Datenweg 120. Der Datenpuffer 116 empfängt Daten von einer vorgelagerten Push-Aufgabe und speichert die Daten, bis ausreichend Daten empfangen worden sind, um die Verarbeitung der Push-Aufgabe auszuführen. Wenn die Push-Aufgabe 112 die Verarbeitung abgeschlossen hat, wird der Ausgang, wie mit dem Stromab-Verbindungsweg 118 gezeigt, im Push-Verfahren nachgelagerten Push-Aufgaben zugeführt.
Eine Datenverarbeitungskette besteht, wie oben beschrieben, entweder nur aus Pull-Aufgaben oder nur aus Push-Aufgaben, so dass die Richtung von Verbindungen und die Richtung von Datenstrom über alle Aufgaben der Datenverarbeitungskette konsistent sind. Die bevorzugten Ausführungen der vorliegenden Erfindung schaffen die Möglichkeit, Pull-Aufgaben in eine Datenverarbeitungskette von Push-Aufgaben einzufügen oder Push-Aufgaben in eine Datenverarbeitungskette von Pull-Aufgaben einzufügen, indem lediglich geringfügige Änderungen an den Push- oder Pull-Aufgaben vorgenommen werden und Schnittstellenmodule zugefügt werden.
7 zeigt Pull-Aufgaben 536 und 538, die in eine Kette von Push-Aufgaben 530, 532 und 540 eingefügt sind. 7 zeigt des Weiteren zwei Schnittstellen-Aufgaben 542 und 544, die Schnittstellen zwischen Push-Aufgaben und Pull-Aufgaben bzw. Pull-Aufgaben und Push-Aufgaben bilden.
8–10 zeigen Blockschemata der Schnittstellen-Aufgaben 542, 544 sowie einer allgemeinen Pull-Aufgabe 534, die in Ketten aus Push-Aufgaben eingefügt werden. In 8 enthält Schnittstellen-Aufgabe 542 einen sogenannten Smart-Buffer 602 sowie eine Vorwärts-Nachrichtenverbindung 604, die Verbindung mit nachgelagerten Pull-Aufgaben herstellt. Der Smart-Buffer 402 sammelt Daten, die im Push-Verfahren von vorgelagerten Push-Aufgaben 532 zugeführt werden, und reguliert die Größe des Puffers auf Basis der Menge an Daten, die beispielsweise von der vorgelagerten Push-Aufgabe 532 im Push-Verfahren zugeführt und von der Pull-Aufgabe 536 im Pull-Verfahren bezogen werden. Wenn Daten von der vorgelagerten Push-Aufgabe 532 über den Datenweg 506 empfangen werden, sendet die Schnittstellen-Aufgabe 542 eine Vorwärts-Nachricht über Vorwärts-Verbindungsweg 522 zu der nachgelagerten Pull-Aufgabe 536, die die Menge an Daten (beispielsweise Anzahl von Zeilen) anzeigt, die zur Verarbeitung für die Pull-Aufgabe 536 verfügbar sind. Diese Vorwärts-Nachricht FM(522) wird im Push-Verfahren dem Prozess-Stack 400 zugeführt, und Steuerung wird an die Pull-Aufgabe 536 übergeben. Die Steuerung wird erst an die Schnittstellen-Aufgabe 542 übergeben, wenn eine Datenanforderung von der Pull-Aufgabe 536 empfangen wird oder die Vorwärts-Nachricht FM(522) zurückgeführt wird. Wenn eine derartige Datenanforderung empfangen wird, wird Steuerung an die Schnittstellen-Aufgabe 542 übergeben, und die Schnittstellen-Aufgabe 542 gibt die angeforderten Daten über den Datenweg 508 an die nachgelagerte Pull-Aufgabe 536 aus.
9 zeigt ein Blockschema der Pull-Aufgabe 534. Die Pull-Aufgabe 534 enthält eine Stromauf-Verbindung 610 und eine Vorwärts-Nachrichtenverbindung 612. Die Pull-Aufgabe 534 wird im Folgenden unter Verwendung der Pull-Aufgabe 536 aus 7 als ein Beispiel erläutert. Wenn eine Vorwärts-Nachricht von der Schnittstellen-Aufgabe 542 empfangen wird, bestimmt die Pull-Aufgabe 536, ob ausreichend Daten vorhanden sind, um mit dem Ausführen der Verarbeitung bzw. des Prozesses der Pull-Aufgabe zu beginnen. Wenn nicht ausreichend Daten vorhanden sind, gibt die Pull-Aufgabe 536 die Steuerung einfach an die Schnittstellen-Aufgabe 542 zurück, die die Vorwärts-Nachricht FM(522) aus dem Prozess-Stack 400 abhebt. Wenn jedoch die Menge an Daten, die durch die von der Schnittstellen-Aufgabe 542 empfangene Vorwärts-Nachricht angezeigt wird, eine ausreichende Anzahl von Daten (beispielsweise eine Zeile) zum Ausführen der Pull-Aufgabe anzeigt, sendet die Pull-Aufgabe 536 eine eigene Vorwärts-Nachricht über den Vorwärts-Verbindungsweg 524 zu der nachgelagerten Pull-Aufgabe 538, die eine Anzahl von Zeilen anzeigt, die die Pull-Aufgabe der Pull-Aufgabe 538 zur Verarbeitung bereitstellen kann. Diese Vorwärts-Nachricht FM(526) wird dem Prozess-Stack 400 im Push-Verfahren zugeführt, und die Steuerung wird an die Schnittstellen-Aufgabe 544 weitergeleitet. Die Pull-Aufgabe 538 stellt fest, ob die durch die Pull-Aufgabe 536 angezeigte Anzahl von Zeilen ausreicht, um die Verarbeitung der Pull-Aufgabe 538 auszuführen. Wenn die durch die Pull-Aufgabe 536 angezeigte Anzahl von Zeilen ausreicht, um die Pull-Aufgabe 538 auszuführen, sendet die Pull-Aufgabe 538 eine Vorwärts-Nachricht zu der nachgelagerten Schnittstellen-Aufgabe 544, die die Anzahl von Zeilen anzeigt, die die Pull-Aufgabe 538 erzeugen kann.
Die Schnittstellen-Aufgabe 544 enthält, wie in 10 dargestellt, eine Stromauf-Verbindung 606 und eine Stromab-Verbindung 608. Die Stromauf-Verbindung 606 ermöglicht es der Schnittstellen-Aufgabe, 544 Daten im Pull-Verfahren von vorgelagerten Pull-Aufgaben zu beziehen, während es die die Stromab-Verbindung 608 der Schnittstellen-Aufgabe 544 ermöglicht, Daten im Push-Verfahren nachgelagerten Push-Aufgaben zuzuführen.
Wenn die Vorwärts-Nachricht FM(526) von der Pull-Aufgabe 538 empfangen wird, sendet, wie unter erneuter Bezugnahme auf 7 ersichtlich ist, die Schnittstellen-Aufgabe 544 eine Datenanforderung DR(529) über den Verbindungsweg 529 zu der Pull-Aufgabe 538, um die Anzahl von Zeilen (beispielsweise eine Zeile) anzufordern, die durch die Vorwärts-Nachricht FM(526) der Pull-Aufgabe 538 angezeigt wird. Die Datenanforderung DR(529) wird im Push-Verfahren dem Prozess-Stack 400 zugeführt, und die Steue rung wird an die Pull-Aufgabe 538 übergeben. Nachdem die Datenanforderung DR(529) empfangen worden ist, sendet die Pull-Aufgabe 538 eine Datenanforderung DR(531) über die Verbindung 531 zu der Pull-Aufgabe 536, die Daten von der Pull-Aufgabe 536 anfordert. Die Pull-Aufgabe 536 ihrerseits sendet eine Datenanforderung DR(533) über Verbindungsweg 533 zu der Schnittstellen-Aufgabe 542 zur Überführung von Daten aus dem Smart-Buffer 602 zu der Pull-Aufgabe 536. Nach der oben stehenden Abfolge von Ereignissen werden DR(529), DR(531) und DR(533) sämtlich im Push-Verfahren dem Prozess-Stack 400 zugeführt, und die Steuerung wird über die Schnittstellen-Aufgabe 544 und die Pull-Aufgaben 538 und 536 an die Schnittstellen-Aufgabe 542 übergeben.
Die Schnittstellen-Aufgabe 542 reagiert auf die Datenanforderung DR(533), indem sie die angeforderten Daten über den Datenweg (538) zu der Pull-Aufgabe 536 sendet, wodurch die Datenanforderung DR(533) aus dem Prozess-Stack 400 abgehoben wird und die Steuerung an die Pull-Aufgabe 536 übergeben wird. Wenn die Pull-Aufgabe 536 mehr Daten (beispielsweise mehrere Zeilen) benötigt, ehe die Verarbeitung der Pull-Aufgabe 536 ausgeführt werden kann, stellt die Pull-Aufgabe 538 mehrere Datenanforderungen an die Schnittstellen-Aufgabe 542, bis eine ausreichende Menge an Daten zu der Pull-Aufgabe 536 überführt worden ist, um mit der Ausführung der Verarbeitung der Pull-Aufgabe zu beginnen. Die Pull-Aufgabe 536 gibt verarbeitete Daten über den Datenweg 510 an die Pull-Aufgabe 538 aus, wodurch die Datenanforderung DR(529) aus dem Prozess-Stack 400 abgehoben wird und die Steuerung an die Pull-Aufgabe 538 übergeben wird. Wenn zusätzliche Daten erforderlich sind, gibt die Pull-Aufgabe 538 erneut über den Verbindungsweg 531 eine Datenanforderung an die Pull-Aufgabe 536 aus, und die Verarbeitung bzw. der Prozess wiederholt sich. Wenn ausreichend Daten empfangen worden sind, führt die Pull-Aufgabe 538 die Verarbeitung ihrer Pull-Aufgabe aus und gibt die verarbeiteten Daten über den Datenweg 512 an die Schnittstellen-Aufgabe 544 aus, wodurch die Datenanfrage DR(529) aus dem Prozess-Stack 400 abgehoben wird und die Steuerung an die Schnittstellen-Aufgabe 544 übergeben wird.
Wenn Daten empfangen werden, führt die Schnittstellen-Aufgabe 544 der Push-Aufgabe 540 Daten im Push-Verfahren über Datenweg 524 zu und führt dem Prozess-Stack 400 die Verbindung 528 L(528) im Push-Verfahren zu. Die Push-Aufgabe 540 leitet die Daten im Push-Verfahren weiter stromab, bis eine Anwendung erreicht wird, so beispielsweise am Ende der Verarbeitungskette, wodurch die Stromauf-Verbindung aus dem Prozess-Stack 400 abgehoben wird und die Steuerung stromauf fließt, bis sie die Schnittstellen-Aufgabe 544 erreicht. Die Schnittstellen-Aufgabe 544 hebt dann die Vor wärts-Nachricht FM(526) aus dem Prozess-Stack 400 ab und verschiebt die Steuerung zu der Pull-Aufgabe 538, und dann wird die Vorwärts-Nachricht FM(524) aus dem Prozess-Stack 400 abgehoben usw., bis die Steuerung zu der Anwendung am Beginn der Verarbeitungskette zurückgeführt ist.
11 zeigt ein Blockschema einer beispielhaften Verarbeitungseinrichtung 650, die die Datenverarbeitungskette ausführen kann, wie sie in 7 dargestellt ist. Die Verarbeitungseinrichtung 650 enthält einen Controller 651, einen Speicher 652, eine Datenbank 654 und eine Eingabe-/Ausgabe-Vorrichtungs-Schnittstelle 656. Die oben aufgeführten Komponenten sind über Signalbus 658 miteinander verbunden.
Die Verarbeitungseinrichtung 650 kann beispielsweise eine Datenverarbeitungseinrichtung für einen Drucker, eine Digitalkamera, ein Scanner, ein Faxgerät, ein CD-ROM-Archiv-System usw. sein. Die Verarbeitungseinrichtung 650 kann mit einer Bedienungsperson über die Eingabe-/Ausgabe-Vorrichtungs-Schnittstelle 656 in Verbindung stehen, um Befehle, wie beispielsweise Druckbefehle oder Befehle zum Einstellen des Druckmodus zu empfangen. Eingabedaten können ebenfalls über die Eingabe-/Ausgabe-Vorrichtungs-Schnittstelle 656 von anderen Verarbeitungseinrichtungen in der Datenbank 654 empfangen werden. Wenn die Verarbeitungseinrichtung 650 beispielsweise eine Druck-Verarbeitungseinrichtung ist, kann die Eingabe-/Ausgabe-Vorrichtungs-Schnittstelle 656 mit einem Computer verbunden sein, der Informationen zum Drucken über einen Drucker in die Datenbank 654 lädt.
Wenn Daten in der Datenbank 654 empfangen werden und der Controller 651 feststellt, dass eine ausreichende Menge an Daten (d.h. eine Seite Daten) empfangen worden ist, kann der Controller 651 den Datenverarbeitungsvorgang in 7 beginnen, indem er die in der Datenbank 654 gespeicherten Daten Zeile für Zeile im Push-Verfahren der Push-Aufgabe 530 über den Signalweg 502 zuführt. Die Daten müssen, wie bereits erläutert, nicht physisch verschoben werden, sondern statt dessen kann der Controller 651 einfach einen Zeiger zu der Push-Aufgabe 530 senden, der eine Adresse in der Datenbank 654 anzeigt. Nachdem die Daten im Push-Verfahren der Push-Aufgabe 530 zugeführt worden sind, kann die Steuerung an die Steuerprogramme der Datenverarbeitungskette zum Ausführen der Datenverarbeitungskette, wie sie in 7 dargestellt ist, übergeben werden.
Der Controller 651 führt wie oben erläutert, einen Prozess-Stack 400, um Steuerung der Datenverarbeitungskette aufrechtzuerhalten. So führt der Controller 651, wenn eine Vorwärts-Nachricht oder eine Datenanforderung erzeugt wird, die jeweilige Vorwärts-Nachricht oder die Datenanforderung im Push-Verfahren dem Prozess-Stack 400 zu. Wenn eine Rückführung erzeugt wird, hebt der Controller 651 die jeweilige Vorwärts-Nachricht oder Datenanforderung aus dem Prozess-Stack ab.
12 zeigt ein Flussdiagramm eines Beispiels, bei dem Pull-Aufgaben in eine Kette von Push-Aufgaben eingefügt sind. Dieses Flussdiagramm stellt nur die Prozess-Stack-Funktion dar, die mit dem Abheben von Vorwärts-Nachrichten und der Zurückführung von Steuerung von vorgelagerten Aufgaben zusammenhängen, die sich auf mehrere Daten-Pull-Vorgänge bezieht. Die anderen Prozess-Stack-Funktionen sind oben erläutert und werden hier, um die Erläuterung zu vereinfachen, nicht detailliert aufgeführt. In Schritt S1000 beginnt der Controller 651 die Verarbeitung durch Empfangen von Daten, die den Push-Aufgaben 530 und 532 im Push-Verfahren zugeführt werden und geht zu Schritt S1002 (Push-Aufgaben 530 und 532 werden als eine einzelne Push-Aufgabe behandelt) über. In Schritt S1002 führt der Controller 651 die Verarbeitungsvorgänge der Push-Aufgaben 530 und 532 aus und führt die Daten der Schnittstellen-Aufgabe 542 (I₁) im Push-Verfahren zu und geht zu Schritt S1004 über. In Schritt S1004 führt der Controller 651 die Verarbeitung der Schnittstellen-Aufgabe 542 (I₁) durch, indem er eine Vorwärts-Nachricht zu einer folgenden Pull-Aufgabe, wie beispielsweise Pull-Aufgabe 536, aufruft, und geht zu Schritt S1006 über. In Schritt S1006 prüft der Controller 651, ob die Menge an Daten, die in der Vorwärts-Nachricht angezeigt ist, ausreicht, um die Pull-Aufgabe zu beginnen. Wenn nicht ausreichend Daten vorhanden sind, geht der Controller 651 zu Schritt S1008 über und ansonsten geht der Controller 651 zu Schritt S1010 über.
In Schritt S1008 hebt der Controller die Vorwärts-Nachricht ab und führt die Steuerung zu der Schnittstellen-Aufgabe 542 zurück und geht zu Schritt S1004 über. In Schritt S1010 ruft der Controller 651 eine Vorwärts-Nachricht zu einer nächstfolgenden Pull-Aufgabe auf und geht zu Schritt S1012 über. In Schritt S1012 prüft der Controller 651, ob die Vorwärts-Nachricht ausreichend Daten anzeigt, so dass die nächstfolgende Pull-Aufgabe (z.B. Pull-Aufgabe 538) mit der Ausführung beginnen kann. Wenn die Menge an Daten nicht ausreicht, geht der Controller 651 zu Schritt S1014 über, ansonsten geht der Controller zu S1022 über (wenn angenommen wird, dass die nächstfolgende Pull-Aufgabe eine letzte Pull-Aufgabe ist). In Schritt S1014 hebt der Controller 651 die vorgelagerte Vorwärts-Nachricht ab, führt die Steuerung zu der vorgelagerten Aufgabe zurück und geht zu Schritt S1008 über.
In Schritt S1022 ruft der Controller 651 eine Vorwärts-Nachricht von der letzten Pull-Aufgabe zu der Schnittstellen-Aufgabe 544 (I₂) auf und geht zu Schritt S1024 über. In Schritt S1024 sendet der Controller 651 eine Datenanforderung an die letzte Pull-Aufgabe von der Schnittstellen-Aufgabe 544, führt die Datenanforderung im Push-Verfahren dem Prozess-Stack 400 zu und geht zu Schritt S1026 über. In Schritt S1026 sendet der Controller 651 eine Datenanforderung an die nächste vorgelagerte Pull-Aufgabe, führt die Datenanforderung im Push-Verfahren dem Prozess-Stack 400 zu und geht zu Schritt S1028 über. In Schritt S1028 bezieht der Controller 651 Daten im Pull-Verfahren von der Schnittstellen-Aufgabe 542 und geht zu Schritt S1030 über. In Schritt S1030 führt der Controller die Daten zu der nachgelagerten Pull-Aufgabe zurück, wodurch ebenfalls die Datenanforderung abgehoben wird und die Steuerung an die nachgelagerte Pull-Aufgabe übergeben wird, und geht zu Schritt S1032 über.
In Schritt S1032 bestimmt der Controller 651, ob ausreichend Daten zum Ausführen der Verarbeitung der nachgelagerten Pull-Aufgabe vorhanden sind. Wenn mehr Daten benötigt werden, kehrt der Controller 651 zu Schritt S1028 zurück. Ansonsten geht der Controller zu Schritt S1034 über. In Schritt S1034 führt der Controller Daten zu der Schnittstellen-Aufgabe 544 zurück, wodurch ebenfalls die entsprechende Datenanforderung abgehoben wird und die Steuerung an die Steuerung an die Schnittstellen-Aufgabe 544 übergeben wird, und geht zu Schritt S1040 über (wenn angenommen wird, dass die nachgelagerte Pull-Aufgabe die letzte Pull-Aufgabe ist). In Schritt S1040 führt der Controller 651 Daten im Push-Verfahren der nachgelagerten Push-Aufgabe (beispielsweise Push-Aufgabe 540) zu und geht zu Schritt S1042 über und beendet die Daten-Pipeline-Verarbeitung).
Die auf die letzte Aufgabe folgende Anwendung hebt, obwohl dies durch das Flussdiagramm in 12 nicht dargestellt ist, die Verbindung aus dem Prozess-Stack 400 ab und führt die Steuerung zu der letzten Push-Aufgabe zurück. Die Verbindungen werden nacheinander durch vorgelagerte Push-Aufgaben abgehoben, bis die Schnittstelle 544 erreicht ist. Die Schnittstellen-Aufgabe 544 hebt die Vorwärts-Nachricht von der vorgelagerten Pull-Aufgabe ab, die ihrerseits die nächste Vorwärts-Nachricht aus dem Prozess-Stack 400 abhebt, bis die Schnittstellen-Aufgabe 542 erreicht ist. Die Schnittstellen-Aufgabe 542 hebt die Verbindung von der vorgelagerten Push-Aufgabe ab und die vorgelagerte Push-Aufgabe hebt die Verbindung von der vorgelagerten Push-Aufgabe ab, bis die Anwendung am Beginn der Daten-Pipeline-Verarbeitung erreicht ist.
Wie durch die unterbrochenen Linien dargestellt, sind alle in dem Kasten 1050 eingeschlossenen Schritte mit einer Zwischen-Pull-Aufgabe verbunden, die zwischen Schnittstellen-Aufgaben 542 und 544 angeordnet ist. Diese Schritte können einmal für jede zusätzliche Pull-Aufgabe wiederholt werden, die zwischen die Schnittstellen-Aufgaben 542 und 544 eingefügt ist. Wenn sich nur eine Pull-Aufgabe zwischen 542 und 544 befindet, werden alle Pull-Aufgaben in dem Kasten 1050 aufgehoben und nur die letzte Pull-Aufgabe verbleibt.
13 zeigt eine Daten-Pipeline, die Push-Aufgaben in eine Kette von Pull-Aufgaben einbettet. Die Daten-Pipeline enthält Pull-Aufgaben 734, 736 und 746. Zwei Push-Aufgaben 740 und 742 werden in diese Kette von der Pull-Aufgaben eingefügt und Schnittstellen-Aufgaben 738 und 744 trennen die Pull-Aufgaben von den Push-Aufgaben.
14–16 zeigen Blockschemata von Schnittstellen-Aufgaben 738 und 744 sowie der allgemeinen Push-Aufgabe 739. 14 zeigt die Schnittstellen-Aufgabe 738, die eine Stromauf-Verbindung 802 und eine Stromab-Verbindung 804 enthält. Die Stromauf-Verbindung 802 ermöglicht es Schnittstellen-Aufgabe 738, Daten im Pull-Verfahren von einer vorgelagertern Pull-Aufgabe zu beziehen, während es die Stromab-Verbindung 804 der Schnittstellen-Aufgabe 738 ermöglicht, Daten im Push-Verfahren nachgelagerten Push-Aufgaben zuzuführen. 15 zeigt ein Blockschema der Push-Aufgabe 739 (Die Push-Aufgabe 739 stellt eine beliebige der Push-Aufgaben dar, die zwischen den Schnittstellen-Aufgaben 738 und 744 angeordnet sind.). Die Push-Aufgabe 739 enthält eine Rückwärts-Nachrichtenverbindung 808, die die Push-Aufgabe 739 in die Lage versetzt, einer vorgelagerten Aufgabe eine Datenanforderung anzuzeigen, einen Datenpuffer 810 und eine Stromab-Verbindung 812. 16 zeigt die Schnittstellen-Aufgabe 744, die eine Rückwärts-Nachricht 806 enthält, die einer vorgelagerten Aufgabe eine Datenanforderung anzeigt.
Wenn die Pull-Aufgabe 746 bereit ist, mehr Daten zu verarbeiten, sendet sie, wie unter erneuter Bezugnahme auf 13 zu sehen ist, eine Datenanforderung an die Schnittstellen-Abgabe 744 über Verbindungsweg 726. Die Pull-Aufgabe 746 kann entweder eine Datenanforderung von einer nachgelagerten Pull-Aufgabe oder ein Signal von einer Ausgabevorrichtung empfangen haben, das mehr Daten anfordert. Die Pull-Aufgabe 746 kann beispielsweise in Reaktion auf eine nachgelagerte Druckvorrichtung eine Zeile von Daten von der Schnittstellen-Aufgabe 744 anfordern. Wenn die Datenanforderung emp fangen wird, gibt die Schnittstellen-Aufgabe 744 eine Rückwärts-Nachricht über Verbindungsweg 725 an die vorgelagerte Push-Aufgabe 742 dahingehend aus, dass eine Zeile Daten erforderlich ist. Die Rückwärts-Nachricht wird im Push-Verfahren dem Prozess-Stack 400 zugeführt und die Steuerung wird an die vorgelagerte Push-Aufgabe 742 übergeben. Die Rückwärts-Nachricht enthält keine Anzahl von Zeilen, wie dies bei der Vorwärts-Nachricht der Fall war. Die Rückwärts-Nachricht zeigt lediglich an, dass nachgelagerte Prozesse mehr Daten benötigen. Die Push-Aufgabe 742 reagiert, indem sie eine Rückwärts-Nachricht über Verbindungsweg 724 zu der nächsten vorgelagerten Push-Aufgabe 740 sendet, die ihrerseits eine Rückwärts-Nachricht über Verbindungsweg 723 zu der Schnittstellen-Aufgabe 738 sendet. So wird die von der Pull-Aufgabe 746 ausgegebene Datenanforderung über die Rückwärts-Nachrichten zu der Schnittstellen-Aufgabe 738 weitergeleitet, so dass eine Abfolge von Rückwärts-Nachrichten in dem Prozess-Stack 400 verbleibt.
Wenn die Rückwärts-Nachricht empfangen wird, bezieht die Schnittstellen-Aufgabe 738 über Verbindungsweg 722 Daten im Pull-Verfahren von der vorgelagerten Pull-Aufgabe 736, die ihrerseits Daten im Pull-Verfahren von der nächsten vorgelagerten Pull-Aufgabe 734 über Verbindungsweg 720 bezieht. Wenn davon ausgegangen wird, dass die Pull-Aufgabe 734 eine erste Pull-Aufgabe ist, sendet die Pull-Aufgabe 734 eine Datenanforderung an eine Datenbank über Verbindungsweg 718 und empfängt die Daten über den Datenweg 702. Die Pull-Aufgabe 734 sendet weiter Datenanforderungen an die Datenbank, bis ausreichend Daten über den Datenweg 702 zum Verarbeiten der Daten empfangen worden sind und sendet dann die Verarbeitungsausgabe zu der nachgelagerten Pull-Aufgabe 736 über Datenweg 704. Die Pull-Aufgabe 736 wartet ebenfalls, bis eine ausreichende Menge an Eingangsdaten von der vorgelagerten Pull-Aufgabe 734 empfangen worden sind, so dass die entsprechende Verarbeitung der Pull-Aufgabe ausgeführt werden kann, und der Ausgang wird über Datenweg 706 zu der Schnittstellen-Aufgabe 738 gesendet.
Wenn die Schnittstellen-Aufgabe 738 Daten von der Pull-Aufgabe 736 empfängt, werden die Daten im Push-Verfahren über den Datenweg 708 der nachgelagerten Push-Aufgabe 740 zugeführt, wie dies durch den Verbindungsweg 728 identifiziert wird. Die Verbindung 728 wird im Push-Verfahren dem Prozess-Stack 400 zugeführt, und Steuerung wird an die nachgelagerte Push-Aufgabe übergeben. Die Push-Aufgabe 740 speichert die von der Schnittstellen-Aufgabe 738 empfangenen Daten. Wenn mehr Daten erforderlich sind, sendet die Push-Aufgabe 740 erneut eine Rückwärts-Nachricht, bis ausreichend Daten zum Ausführen der Verarbeitung der Push-Aufgabe 740 empfangen worden sind. Wenn ausreichend Daten zur Verfügung stehen, führt die Push-Aufgabe 740 die Verarbeitung der Push-Aufgabe aus und führt den Ausgang im Push-Verfahren über Datenweg 710 der nachgelagerten Push-Aufgabe 742 zu, wie dies durch den Verbindungsweg 730 angezeigt wird, führt die Verbindung 730 im Push-Verfahren dem Prozess-Stack 400 zu und übergibt die Steuerung an die Push-Aufgabe 742. Die Push-Aufgabe 742 bestimmt auch, ob eine ausreichende Menge an Daten zur Verarbeitung zur Verfügung steht, und wenn sie zur Verfügung steht, führt sie die Verarbeitung der Push-Aufgabe aus und führt den Ausgang im Push-Verfahren über Datenweg 712 der Schnittstellen-Aufgabe 744 zu, wie dies durch Verbindungsweg 732 angezeigt wird, führt die Verbindung 732 im Push-Verfahren dem Prozess-Stack 400 zu und übergibt die Steuerung an die Schnittstellen-Aufgabe 744.
Wenn die Schnittstellen-Aufgabe 744 die Daten von der Push-Aufgabe 742 empfängt, werden die Verbindungen 732, 730 und 728 der Reihe nach zugeführt und aus dem Prozess-Stack 400 abgehoben. Nachdem die Schnittstellen-Aufgabe 738 die Steuerung übernommen hat, werden Rückwärts-Nachrichten 723, 724 und 725 zurückgeführt und der Reihe nach aus dem Prozess-Stack 400 abgehoben, und die Steuerung geht an die Schnittstellen-Aufgabe 744 zurück.
Wenn die Schnittstellen-Aufgabe 744 die Steuerung übernimmt, werden die Daten zu der Pull-Aufgabe 746 weitergeleitet, die Datenanforderung, die zuvor über den Verbindungsweg 726 gesendet wurde, wird abgehoben und die Steuerung wird an die Pull-Aufgabe 746 übergeben. Wenn die Pull-Aufgabe 746 zusätzliche Daten (eine weitere Zeile Daten) benötigt, sendet die Pull-Aufgabe 746 eine weitere Datenanforderung über den Verbindungsweg 726, und die Verarbeitung wiederholt sich, bis die Pull-Aufgabe 746 ausreichend Daten empfängt, um die Verarbeitung der Pull-Aufgabe auszuführen, und gibt die verarbeiteten Daten über Datenweg 716 beispielsweise an nachgelagerte Aufgaben oder Vorrichtungen am Ende der Pipeline-Verarbeitung aus. So ermöglicht es die Rückwärts-Nachricht, die Datenanforderung der Pull-Aufgabe 746 zu der Pull-Aufgabe 736 weiterzuleiten, um so den Mangel an Stromauf-Verbindungen der Push-Aufgaben 740 und 742 zu überwinden.
17 zeigt ein Flussdiagramm eines Prozesses, der von dem Controller 650 für die in 13 dargestellte Daten-Pipeline ausgeführt wird. In Schritt S2000 empfängt der Controller 653 eine Datenanforderung, die von der nachgelagerten Pull-Aufgabe 746 an die Schnittstellen-Aufgabe 744 gerichtet ist, und geht zu Schritt S2002 über. In Schritt S2002 ruft der Controller 651 eine Rückwärts-Nachricht von der Schnittstellen-Aufgabe 744 zu der vorgelagerten Push-Aufgabe 742 auf und geht zu Schritt S2004 über. In Schritt S2004 ruft der Controller 651 eine Rückwärts-Nachricht von der Push-Aufgabe 742 zu der nächsten vorgelagerten Push-Aufgabe (beispielsweise Push-Aufgabe 740) auf und geht zu Schritt S2006 über. In Schritt S2006 ruft der Controller 651 eine Rückwärts-Nachricht von der nächsten vorgelagerten Push-Aufgabe zu der Schnittstellen-Aufgabe 738 auf und geht zu Schritt S2008 über. In Schritt S2008 sendet die Schnittstellen-Aufgabe 738 eine Datenanforderung zu der vorgelagerten Pull-Aufgabe 736 und geht zu Schritt S2010 über. In Schritt S2010 sendet der Controller 651 eine Datenanforderung von der vorgelagerten Pull-Aufgabe 736 zu der nächsten vorgelagerten Pull-Aufgabe (beispielsweise Pull-Aufgabe 734) und geht zu Schritt S2012 über. In Schritt S2012 bezieht der Controller 651 Daten im Pull-Verfahren von einer Datenquelle, wie beispielsweise einer Datenbank (wenn davon ausgegangen wird, dass beispielsweise die vorgelagerte Pull-Aufgabe 734 eine erste Pull-Aufgabe ist), und geht zu Schritt S2014 über.
In Schritt S2014 bestimmt der Controller, ob die von der Datenquelle empfangenen Daten ausreichen, um die vorgelagerte Pull-Aufgabe 734 in Gang zu setzen. Wenn die Menge an Daten ausreicht, geht der Controller 651 zu Schritt S2016 über und ansonsten kehrt der Controller zu Schritt S2012 zurück und sendet eine weitere Datenanforderung an die Datenquelle. In Schritt S2016 verarbeitet der Controller 651 die Daten für die vorgelagerte Pull-Aufgabe 734 und führt die Daten zu der rufenden nachgelagerten Pull-Aufgabe 736 zurück und geht zu Schritt S2018 über. In dem Schritt S2018 bestimmt die nachgelagerte Pull-Aufgabe 736, ob eine ausreichende Menge an Daten zum Ausführen der Verarbeitung bzw. des Prozesses der Pull-Aufgabe vorhanden ist. Wenn ausreichend Daten vorhanden sind, geht der Controller 651 zu Schritt S2020 über und ansonsten kehrt der Controller 651 zu Schritt S2010 zurück und bezieht weitere Daten im Pull-Verfahren von der vorgelagerten Pull-Aufgabe 734. In Schritt S2020 führt die nachgelagerte Pull-Aufgabe die Verarbeitung der Pull-Aufgabe aus und führt die Daten zurück, wodurch auch die Datenanforderung zu der weiteren nachgelagerten Pull-Aufgabe oder der Schnittstellen-Aufgabe 738 zurückgeführt wird, und geht zu Schritt S2022 über. In Schritt S2022 führt der Controller 651 die von der vorgelagerten Pull-Aufgabe 736 empfangenen Daten im Push-Verfahren der nachgelagerten Push-Aufgabe 740 zu, führt die Verbindung 728 im Push-Verfahren dem Prozess-Stack 400 zu und führt die Steuerung zu der nachgelagerten Push-Aufgabe 740 zurück und geht zu Schritt S2024 über.
In Schritt S2024 bestimmt der Controller 651, ob ausreichend Daten von der vorgelagerten Push-Aufgabe (oder der Schnittstellen-Aufgabe 738) empfangen worden sind. Wenn eine ausreichende Menge an Daten vorhanden ist, geht der Controller 651 zu Schritt S2026 über und ansonsten geht der Controller zu Schritt S2006 über. In Schritt S2026 führt der Controller 651 die Verarbeitung der Push-Aufgabe aus, führt die Daten im Push-Verfahren der nachgelagerten Push-Aufgabe 742 zu, führt die Verbindung 730 im Push-Verfahren dem Prozess-Stack 400 zu, führt Steuerung zu der nachgelagerten Push-Aufgabe 742 zurück und geht zu Schritt S2030 über. In Schritt S2030 bestimmt der Controller 651, ob ausreichend Daten zum Ausführen der nachgelagerten Push-Aufgabe 742 vorhanden sind. Wenn eine ausreichende Menge an Daten vorhanden ist, geht der Controller 651 zu Schritt S2032 über und ansonsten geht der Controller 651 zur Schritt S2004 über.
In Schritt S20323 führt der Controller 651 die Verarbeitung der nachgelagerten Push-Aufgabe 742 für die empfangenen Daten durch, führt den Ausgang der Schnittstellen-Aufgabe 744 im Push-Verfahren zu, führt die Verbindung 732 im Push-Verfahren dem Prozess-Stack 400 zu, führt die Steuerung zu der Schnittstellen-Aufgabe 744 zurück und geht zu Schritt S2038 über. In Schritt S2038 führt der Controller 651 die Verbindungen 732, 730 und 728 sowie die Rückwärts-Nachrichten 723, 724 und 725 der Reihe nach zurück und hebt die jeweiligen Elemente aus dem Prozess-Stack 400 ab und geht zu Schritt S2040 über. in Schritt S2040 führt der Controller 651 die von der vorgelagerten Push-Aufgabe 742 empfangenen Daten im Push-Verfahren der nachgelagerten Pull-Aufgabe zu und geht zu Schritt S2042 über und beendet den Vorgang.
Obwohl die Erfindung in Verbindung mit spezifischen Ausführungen derselben beschrieben worden ist, ist klar, dass viele Alternativen, Abwandlungen und Veränderungen für den Fachmann auf der Hand liegen. So kann die Verarbeitungseinrichtung 650 beispielsweise unter Verwendung einer Vielzahl von Hardware, so beispielsweise anwendungsspezifischer integrierter Schaltungen (ASIC), FPGA, PLA usw.), implementiert werden. Die Verarbeitungseinrichtung führt die oben erläuterten Funktionen durch und kann in beliebige Datenverarbeitungsvorrichtungen, wie beispielsweise Drucker, Scanner, Digitalkameras, Faxgeräte, digitale Fernsehgeräte usw., integriert werden.
Des Weiteren können, obwohl die oben stehende Beschreibung Prozess-Stacks, Rückführen von Vorwärts- und Rückwärts-Nachrichten sowie Rückführen von Datenanforderungen erläutert, diese Funktionen unter Verwendung anderer Techniken, wie beispielsweise Multi-Thread-Verarbeitung oder mehrerer Vorrichtungen, die Funktionen von Pull- oder Push-Aufgaben durchführen, erfüllt werden. Der Prozess-Stack 400 ist als ein Beispiel vorhanden. Andere Verfahren zum Steuern von Verarbeitungsketten können ebenfalls verwendet werden, so beispielsweise Task-Messaging-Verfahren, Mutex oder Semiphore, die verwendet werden, wenn die Push- oder Pull-Aufgaben verteilt sind. Dementsprechend sind bevorzugte Ausführungen der Erfindung, wie sie hier aufgeführt sind, veranschaulichend und nicht beschränkend zu verstehen. Verschiedene Veränderungen können vorgenommen werden, ohne vom Schutzumfang der Erfindung abzuweichen.

Claims

Verfahren zum Verarbeiten von Daten mit einer Datenverarbeitungskette in einer Pipeline, das umfasst: Bereitstellen wenigstens einer Aufgabe (532, 736) eines ersten Typs mit einer ersten Verbindung (520, 722) in einer ersten Richtung in der Datenverarbeitungskette; Bereitstellen wenigstens einer Aufgabe (536, 740) eines zweiten Typs mit einer zweiten Verbindung (533, 730) in einer zweiten Richtung und einer dritten Verbindung (522, 723) in der Datenverarbeitungskette; und Koppeln der Aufgabe (532, 736) des ersten Typs und der Aufgabe (536, 740) des zweiten Typs mit einer ersten Schnittstellenaufgabe (542, 738), wobei die erste Schnittstellenaufgabe (542, 738) eine Schnittstelle zwischen der ersten Verbindung (520, 722) und der dritten Verbindung (522, 723) bildet.
Verfahren nach Anspruch 1, wobei die Aufgabe des ersten Typs eine Pull-Aufgabe (736) ist, die erste Verbindung (722) eine Datenanforderungs-Verbindung zu einer vorgelagerten Aufgabe ist und die erste Richtung der Richtung des Datenflusses entgegengesetzt ist.
Verfahren nach Anspruch 2, wobei die Aufgabe des zweiten Typs eine Push-Aufgabe (740) ist, die zweite Verbindung (730) eine vorgelagerte Aufgabe anzeigt, der Daten von der Aufgabe des zweiten Typs im Push-Verfahren zugeführt werden, und die zweite Richtung die gleiche Richtung ist wie die des Datenflusses.
Verfahren nach Anspruch 3, wobei die Aufgabe (736) des ersten Typs der ersten Schnittstellenaufgabe (738) und der Aufgabe (740) des zweiten Typs vorgelagert ist und das Verfahren des Weiteren umfasst: Empfangen einer Nachricht über die dritte Verbindung (723) von der Aufgabe (740) des zweiten Typs; und Erzeugen einer Datenanforderung von der ersten Schnittstellenaufgabe (738) zu der Aufgabe (736) des ersten Typs auf Basis der über die dritte Verbindung (723) empfangenen Nachricht.
Verfahren nach Anspruch 1, wobei die Aufgabe des ersten Typs eine Push-Aufgabe (532) ist, die erste Verbindung (520) eine nachgelagerte Aufgabe anzeigt, der Daten von der Aufgabe des ersten Typs im Push-Verfahren zugeführt werden, und die erste Richtung die Richtung des Datenflusses ist.
Verfahren nach Anspruch 5, wobei die Aufgabe des zweiten Typs eine Pull-Aufgabe (536) ist, die zweite Verbindung (533) eine Datenanforderungsverbindung zu einer vorgelagerten Aufgabe ist und die zweite Richtung der Richtung des Datenflusses entgegengesetzt ist.
Verfahren nach Anspruch 6, wobei die Aufgabe (532) des ersten Typs der ersten Schnittstellenaufgabe (542) und der Aufgabe (536) des zweiten Typs vorgelagert ist und das Verfahren des Weiteren umfasst: Empfangen von Daten von der Aufgabe (532) des ersten Typs in einem Puffer (602), der mit der ersten Schnittstellenaufgabe (542) verbunden ist; und Erzeugen einer Nachricht von der ersten Schnittstellenaufgabe (542) zu der Aufgabe (536) des zweiten Typs auf Basis von der Aufgabe (532) des ersten Typs empfangener Daten, wobei die Nachricht eine Menge von der Aufgabe (532) des ersten Typs empfangener Daten enthält.
Verfahren nach Anspruch 7, wobei die Aufgabe (536) des zweiten Typs Daten aus dem Puffer (602) der ersten Schnittstellenaufgabe (542) im Pull-Verfahren bezieht und eine Größe des Puffers (602) auf Basis einer Menge an Daten reguliert wird, die in dem Puffer (602) enthalten sind.
Verfahren nach Anspruch 1, das des Weiteren umfasst: Bereitstellen wenigstens einer Aufgabe (540, 746) eines dritten Typs; Bereitstellen einer zweiten Schnittstellenaufgabe (544, 744); und Koppeln der Aufgabe (742) des zweiten Typs mit der Aufgabe (540, 746) des dritten Typs mit der zweiten Schnittstellenaufgabe (544, 744).
Verfahren nach Anspruch 9, wobei die Aufgaben des ersten Typs und des dritten Typs Pull-Aufgaben (736, 746) sind und das Verfahren umfasst: Empfangen einer Datenanforderung in der zweiten Schnittstellenaufgabe (744) von der Aufgabe (746) des dritten Typs; und Erzeugen einer Nachricht von der zweiten Schnittstellenaufgabe (744) zu der Aufgabe (742) des zweiten Typs über die zweite Verbindung (725), um anzuzeigen, dass Daten angefordert worden sind.
Verfahren nach Anspruch 9, wobei die Aufgabe des ersten Typs und die des dritten Typs Push-Aufgaben (532, 540) sind und das Verfahren umfasst: Empfangen einer Nachricht von der Aufgabe (538) des zweiten Typs über die zweite Verbindung (526); Erzeugen einer Datenanforderung von der zweiten Schnittstellenaufgabe (544) zu der Aufgabe (538) des zweiten Typs; Empfangen von Daten von der Aufgabe (538) des zweiten Typs; und Zuführen der von der Aufgabe (538) des zweiten Typs empfangenen Daten zu der Aufgabe (540) des dritten Typs im Push-Verfahren.