DE69424610T2

DE69424610T2 - Datenverarbeitungs-anlage und -verfahren

Info

Publication number: DE69424610T2
Application number: DE69424610T
Authority: DE
Inventors: Souza David D
Original assignee: Microsoft Corp
Current assignee: Microsoft Corp
Priority date: 1993-09-21
Filing date: 1994-09-12
Publication date: 2000-09-28
Anticipated expiration: 2014-09-13
Also published as: EP0644484B1; EP0644484A2; JP3746798B2; EP0644484A3; DE69424610D1; CA2131406A1; JPH07152587A; US6052707A; CA2131406C

Description

Die vorliegende Erfindung betrifft allgemein Datenverarbeitungssysteme und genauer die Abwicklung bzw. Einplanung ("Scheduling") von Tasks in Datenverarbeitungssystemen.
Das Betriebssystem Microsoft Windows Version 3.1, verkauft von der Microsoft Corporation in Redmond, Washington, ist ein nachrichtengesteuertes Betriebssystem. Jedes auf dem Betriebssystem laufende Programm unterhält eine Nachrichtenqueue zum Halten eingehender Nachrichten, die für einen gewissen Teil des Programms bestimmt sind. Nachrichten sind oft für von dem Programm erzeugte Fenster bestimmt. Jedes von einem Programm erzeugte Fenster hat eine zugeordnete Prozedur. Somit werden die Nachrichten nicht an das Fenster per se gesandt, sondern werden vielmehr an die zugeordnete Prozedur geschickt.
Nachrichten werden aus der Nachrichtenqueue von dem zugeordneten Programm abgerufen und verarbeitet durch die Ausführung eines Codeblocks, der als "Nachrichtenschleife" ("Message Loop") bekannt ist. Fig. 1 ist ein Flußdiagramm der von der Nachrichtenschleife durchgeführten Schritte. Diese Schritte werden kontinuierlich in der Art einer Schleife wiederholt, solange das Programm aktiv ist. Anfänglich wird eine Nachricht aus der Queue dadurch abgerufen, daß ein Aufruf der GetMessage-Funktion durchgeführt wird (Schritt 10). Die GetMessage-Funktion ist verantwortlich für das Abrufen einer Nachricht (wenn eine existiert) aus der Queue. Ist die Nachricht aus der Queue einmal abgerufen, wird die Nachricht (falls nötig) in ein verwendbares Format durch Aufruf der TranslateMessage-Funktion übersetzt, die eine gewisse Tastaturübersetzung durchführt (Schritt 12). Ist die Nachricht einmal übersetzt, wird die Nachricht an die entsprechende Prozedur durch Aufruf der DispatchMessage-Funktion verschickt (Schritt 14). Die Nachricht enthält Informationen, die ein Zielfenster identifizieren. Die Information wird verwendet, um die Nachricht richtig zu verschicken.
Die oben beschriebene GetMessage-Funktion spielt auch eine Rolle bei der Abwicklung von Tasks in dem Betriebssystem Microsoft Windows Version 3.1. Das Betriebssystem wendet die Methode eines nicht-präemptiven oder kooperativen Multitaskings an. Ein Task ist ein Codeabschnitt, wie etwa eine Unterroutine oder ein Programm, das unabhängig ablaufen kann. Kooperatives Multitasking betrifft den Fall, daß Tasks miteinander kooperieren, indem sie untereinander die Kontrolle über einen Prozessor freiwillig weitergeben ("Yielding"). Im Gegensatz hierzu bestimmt bei präemptivem Multitasking ein Scheduler, welcher Task dem Prozessor gegeben wird, und versorgt typischerweise jeden Task mit einem gegebenen Zeitschlitz, in dem er ablaufen kann. Die GetMessage-Funktion ist ein Beispiel für ein Hilfsmittel zur Implementierung des kooperativen Multitaskings in dem Betriebssystem. Andere Funktionen, die vom Betriebssystem bereitgestellt werden und die Implementierung kooperativen Multitaskings unterstützen, schließen die PeekMessage-, Yield- und WaitMessage- Funktionen ein. Um zu verstehen, wie die GetMessage-Funktion und die anderen genannten Funktionen eine Rolle beim kooperativen Multitasking spielen, ist es hilfreich, einen genaueren Blick auf die Funktionsweise der GetMessage-Funktion zu werfen.
Fig. 2 ist ein Flußdiagramm der Schritte, die von der GetMessage-Funktion ausgeführt werden, wenn sie von einem ersten Task (z. B. einem Programm) in einer Umgebung mit mehreren aktiven Tasks aufgerufen wird. Anfänglich bestimmt die GetMessage-Funktion, ob die Nachrichtenqueue für den aufrufenden Task leer ist (Schritt 16). Wenn die Nachrichtenqueue für den aufrufenden Task leer ist, übergibt der Task den Prozessor an einen zweiten Task, der eine nicht leere Nachrichtenqueue hat (d. h. er tritt die Kontrolle über den Prozessor ab) (Schritt 18). Zu einem späteren Zeitpunkt wird eine Nachricht in der Nachrichtenqueue des ersten Tasks verfügbar (Schritt 20). Der zweite Task behält die Kontrolle über den Prozessor, bis er die Kontrolle an einen anderen Task übergibt. Eventuell übergibt ein Task die Kontrolle zurück an den ersten Task (Schritt 22). Typischerweise übergibt einer der anderen Tasks die Kontrolle zurück an den ersten Task, wenn die Nachrichtenqueue des anderen Tasks leer und die Nachrichtenqueue für den ersten Task nicht mehr leer ist. Die Nachricht in der Nachrichtenqueue des ersten Tasks wird dann aus der Nachrichtenqueue abgerufen (Schritt 24). Wenn andererseits in Schrill 16 festgestellt wird, daß die Nachrichtenqueue für den ersten Task nicht leer ist, wird der Schritt des Abrufens der Nachricht aus der Nachrichtenqueue sofort und nicht erst nach Durchführung der Schritte 18, 20 und 22 durchgeführt (Schritt 24).
Eine Schwierigkeit bei der Methode des kooperativen Multitaskings des Betriebssystems Microsoft Windows Version 3.1 besteht darin, daß ein Task den Prozessor dadurch monopolisieren kann, daß er sich weigert, an andere Tasks zu übergeben. Solange der Task Nachrichten in seiner Nachrichtenqueue hat, braucht er nicht zu übergeben.
Patent Abstracts of Japan, vol. 15, No. 251 (P-1220) offenbart ein Parallelformerzeugungsgerät, in dem Taskgruppen als zu jedem Prozessor in einem Mehrprozessorsystem zugeordnet definiert sind. Taskabwicklungsmittel führen die Tasks, die ausgeführt werden können, parallel über verschiedene Prozessoren aus. Jeder Prozessor erzeugt eine auszuführende Taskgruppe.
Es ist die Aufgabe der Erfindung, ein Datenverarbeitungssystem und ein Betriebsverfahren anzugeben, die zuverlässiger funktionieren.
Diese Aufgabe wird durch den Gegenstand der unabhängigen Patentansprüche 1 und 8 gelöst.
Bevorzugte Ausgestaltungen sind in den Unteransprüchen definiert.
Gemäß einem ersten Aspekt der vorliegenden Erfindung wird ein Verfahren in einem Datenverarbeitungssystem mit wenigstens einem Prozessor zum Ausführen von Tasks praktiziert. Die Tasks werden logisch in Gruppen von unabhängigen Tasks aufgeteilt. Die Taskgruppen werden präemptiv abgewickelt, um so ausgeführt zu werden, daß jeder Taskgruppe ein Zeitschlitz zugewiesen wird, in dem sie auf dem Prozessor ablaufen kann. Die auszuführenden Tasks innerhalb jeder Gruppe werden nicht präemptiv abgewickelt, um während des der Gruppe zugeordneten Zeitschlitzes ausgeführt zu werden.
Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird ein Verfahren in einem Datenverarbeitungssystem mit wenigstens einer Speichereinrichtung zum Speichern von Codemodulen und mit wenigstens einem Prozessor zum Ausführen von Tasks praktiziert. Während der Ausführung jedes Tasks wird wenigstens ein Codemodul ausgeführt. Bei diesem Verfahren wird für jeden Task eine Taskabhängigkeitsliste bereitgestellt. Diese Taskabhängigkeitsliste verzeichnet Module, die Kandidaten dafür sind, aufgerufen zu werden, wenn der Task auf dem Prozessor abläuft. Das Verfahren kann einen zusätzlichen Schritt des Bereitstellens einer Modulabhängigkeitsliste für jeden Codemodul enthalten. Jede Modulabhängigkeitsliste verzeichnet unabhängige Codemodule für den der Liste zugeordneten Modulcode. In einem solchen Fall wird die Taskabhängigkeitsliste für jeden Task dadurch erzeugt, daß eine logische Vereinigung der in der Modulabhängigkeitsliste verzeichneten Module vorgenommen wird, die Kandidaten dafür sind, ausgeführt zu werden, wenn der Task auf dem Prozessor abläuft.
Die Taskabhängigkeitslisten werden untersucht, um die Tasks logisch in Gruppen von unabhängigen Tasks aufzuteilen. Die Taskgruppen werden präemptiv abgewickelt, um so ausgeführt zu werden, daß jeder Taskgruppe ein Zeitschlitz in einem Zyklus zugewiesen wird, in dem ihre Tasks auf dem Prozessor ablaufen können. Für jede Taskgruppe werden die Tasks nicht präemptiv abgewickelt, um während des der Gruppe zugeordneten Zeitschlitzes ausgeführt zu werden.
Gemäß eines wiederum anderen Aspekts der vorliegenden Erfindung enthält ein Datenverarbeitungssystem einen Partitionierungsmechanismus zum Aufteilen von Tasks in Gruppen unabhängiger Tasks. Das Datenverarbeitungssystem enthält auch einen Ausführungsmechanismus zum Ausführen des Tasks. Ein präemptiver Scheduler wickelt präemptiv die Taskgruppe so ab, daß jeder Gruppe ein Zeitschlitz gegeben wird, in dem einer ihrer Tasks ausgeführt wird. Auch ein nicht-präemptiver Scheduler wird in dem Datenverarbeitungssystem zum nicht-präemptiven Abwickeln von Tasks innerhalb jeder Gruppe bereitgestellt.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Flußdiagramm, das die von einer Nachrichtenschleife in dem Betriebssystem Microsoft Windows Version 3.1 durchgeführten Schritte verdeutlicht.
Fig. 2 ist ein Flußdiagramm, das die von der GetMessage-Funktion der Nachrichtenschleife von Fig. 1 durchgeführten Schritte verdeutlicht.
Fig. 3 ist ein Blockdiagramm eines Datenverarbeitungssystems, das zur Verwendung einer bevorzugten Ausgestaltung der vorliegenden Erfindung geeignet ist.
Fig. 4 ist ein Flußdiagramm, das eine allgemeine Übersicht der von der bevorzugten Ausgestaltung der vorliegenden Erfindung beim Abwickeln von Tasks zur Ausführung durchgeführten Schritte bereitstellt.
Fig. 5 ist ein Blockdiagramm, das ein Beispiel der präemptiven Abwicklung von Gruppen in der bevorzugten Ausgestaltung der vorliegenden Erfindung verdeutlicht.
Fig. 6 ist eine Verdeutlichung einer exemplarischen Gruppenliste, die in der bevorzugten Ausgestaltung der vorliegenden Erfindung angewendet wird.
Fig. 7 ist ein Flußdiagramm, das die Schritte verdeutlicht, die beim Zusammenfassen von Tasks zu einer einzigen Mischgruppe in der bevorzugten Ausgestaltung der vorliegenden Erfindung durchgeführt werden.
Fig. 8 ist ein Flußdiagramm, das die Schritte genauer verdeutlicht, die in der bevorzugten Ausgestaltung der vorliegenden Erfindung durchgeführt werden, um einen Task in eine Gruppe mit anderen Tasks zu bringen, die eine gleiche DLL verwenden.
Fig. 9 ist eine Verdeutlichung einer exemplarischen Gruppenstatustabelle, die in der bevorzugten Ausgestaltung der vorliegenden Erfindung verwendet wird.
Fig. 10 ist eine Verdeutlichung einer exemplarischen Modulabhängigkeitsliste, die in der bevorzugten Ausgestaltung der vorliegenden Erfindung verwendet wird.
Fig. 11 ist ein Flußdiagramm, das die Schritte verdeutlicht, die durchgeführt werden, um eine Modulabhängigkeitsliste in der bevorzugten Ausgestaltung der vorliegenden Erfindung anwachsen zu lassen.
Fig. 12 ist ein Flußdiagramm, das die Schritte verdeutlicht, die durchgeführt werden, um eine Taskabhängigkeitsliste in der bevorzugten Ausgestaltung der vorliegenden Erfindung zu erzeugen.

Genaue Beschreibung der Erfindung

Die bevorzugte Ausgestaltung der vorliegenden Erfindung kombiniert präemptives Multitasking mit kooperativem Multitasking, um die Abwicklung von Tasks in einem Betriebssystem zu optimieren. Genauer gesagt werden Tasks logisch in Gruppen von unabhängigen Tasks aufgeteilt. Wie unten genauer beschrieben werden wird, stehen die unabhängigen Tasks in einer solchen Beziehung, daß Probleme beim gemeinsamen Verwenden von Code und Daten entstehen könnten, wenn die Tasks asynchron abgewickelt werden würden. Ein Zeitschlitz der Prozessorzeit wird für jede Gruppe bereitgestellt. Die Abwicklung innerhalb der Gruppe wird jedoch in kooperativer Art und Weise durchgeführt, ganz wie sie von dem Betriebssystem Microsoft Windows Version 3.1, verkauft von der Microsoft Corporation in Redmond Washington, durchgeführt wird. Da Gruppen präemptiv abgewickelt werden, kann ein Task den Prozessor nicht monopolisieren und alle ausführenden Tasks verlangsamen. Allgemein gesagt wird die Antwortzeit für den vollständigen Taskablauf durch die vorliegende Erfindung verbessert. Des weiteren kann der Scheduler, wenn ein Task hängt, zu einer anderen Gruppe schalten, so daß nicht alle Tasks hängen werden. Zusätzlich stellt die vorliegende Erfindung aus Gründen der Kompatibilität sicher, daß Abhängigkeiten zwischen Tasks nicht ignoriert werden. Frühere Versionen des Betriebssystems Microsoft Windows verwendeten kooperatives Multitasking. Daher berücksichtigen Anwendungen, die für solch frühere Versionen des Betriebssystems geschrieben worden sind, die präemptive Abwicklung nicht und Abhängigkeitsprobleme können daher auftreten, wenn solche Anwendungen in einer präemptiv abgewickelten Umgebung laufen. Diese Abhängigkeiten nicht zu erkennen, könnte Probleme in einer rein präemptiv abgewickelten Umgebung verursachen.
Die bevorzugte Ausgestaltung der vorliegenden Erfindung wird in einem Datenverarbeitungssystem 26 angewendet, wie etwa dem in Fig. 3 gezeigten. Obwohl das in Fig. 3 gezeigte Datenverarbeitungssystem 26 ein Einzelprozessorsystem ist, werden Fachleute erkennen, daß die vorliegende Erfindung auch in Mehrprozessorsystemen wie etwa verteilten Systemen angewendet werden kann. Das Datenverarbeitungssystem 26 von Fig. 3 enthält eine zentrale Verarbeitungseinheit (CPU) 27, die den Betrieb des Systems steuert. Das Datenverarbeitungssystem 26 enthält auch einen Speicher 28 und einen Plattenspeicher 30 zum Speichern von Dateien und Daten. Der Speicher 28 kann irgendeinen von vielerlei Typen von Speichereinrichtungen enthalten, einschließlich eines RAM, eines ROM oder anderer bekannter Typen von Speichereinrichtungen. Das Datenverarbeitungssystem 26 kann weiterhin eine Tastatur 32, eine Maus 34 und einen Videodisplay 36 enthalten. Es sollte erkannt werden, daß zusätzliche oder andere Typen von Eingabe/Ausgabeeinrichtungen ebenso in dem Datenverarbeitungssystem 26 enthalten sein können.
Der Speicher 28 hält eine Kopie von einem Betriebssystem 40 und von Codemodulen 38. Das Betriebssystem kann eine erweiterte Version des Betriebssystems Microsoft Windows Version 3.1 sein, das erweitert worden ist, um die bevorzugte Ausgestaltung zu unterstützen, die hier beschrieben wird. Das Betriebssystem 40 enthält einen Scheduler 42, der verantwortlich ist für die Abwicklung der Ausführung von Tasks auf der CPU 28. Die bevorzugte Ausgestaltung der vorliegenden Erfindung ist großenteils im Scheduler 42 implementiert.
Fig. 4 ist ein Übersichtsflußdiagramm, das die Schritte zeigt, die beim Abwickeln von Tasks innerhalb der bevorzugten Ausgestaltung der vorliegenden Erfindung ausgeführt werden. Zunächst werden Tasks in logische Gruppen von unabhängigen Tasks organisiert (Schritt 44). Diese Tasks weisen untereinander solche Abhängigkeiten auf, daß sie nicht in separaten Zeitschlitzen ausgeführt werden können. Beispielsweise können die Tasks einen gemeinsamen DLL-Modul (Dynamic Link Library) oder einen anderen gemeinsamen Modul aufrufen. Wenn ein solcher Task in separaten Zeitschlitzen ausgeführt werden würde, würde ein Problem bei der gemeinsamen Verwendung von Daten auftreten. Einer der Tasks könnte unbeabsichtigterweise die Daten für die DLL ändern und so die anderen Tasks nachteilig beeinträchtigen. Die Organisation von Tasks in logische Gruppen wird vom Betriebssystem 40 durchgeführt und unten genauer beschrieben. Die Diskussion unten wird sich zunächst auf den präemptiven Abwicklungsaspekt der vorliegenden Erfindung und dann später auf den kooperativen Abwicklungsaspekt der vorliegenden Erfindung konzentrieren.
Die verschiedenen Gruppen von auf dem Betriebssystem 40 auszuführenden Tasks werden präemptiv abgewickelt, so daß jeder Gruppe ein bestimmter Zeitschlitz der Verarbeitungszeit zugewiesen wird, um auf der CPU 28 abzulaufen (Schritt 46 in Fig. 4). Fig. 5 stellt eine Veranschaulichung dar, wie Zeitschlitze in einem Fall zugewiesen werden können, wenn es vier logische Gruppen gibt: Gruppe 1, Gruppe 2, Gruppe 3 und Gruppe 4. In der in Fig. 5 gezeigten Veranschaulichung wird der Gruppe 1 der Zeitschlitz 1 im Zyklus 1 und dann später der Zeitschlitz 5 im Zyklus 2 zugewiesen. In dem in Fig. 5 gezeigten Beispiel wird der Gruppe 2 der Zeitschlitz 2 im Zyklus 1, der Gruppe 3 der Zeitschlitz 3 in Zyklus 1 und der Gruppe 4 der Zeitschlitz 4 im Zyklus 1 zugewiesen. Jeder Gruppe wird ein entsprechender Zeitschlitz innerhalb des nächsten Zyklus zugewiesen. Der Gruppe 1 wird also der Zeitschlitz 5 im Zyklus 2 zugewiesen, der Gruppe 2 der Zeitschlitz 6 in Zyklus 2, der Gruppe 3 der Zeitschlitz 7 im Zyklus 2 und der Gruppe 4 der Zeitschlitz 8 im Zyklus 2.
Da die Abwicklung dynamisch erfolgt und Gruppen im Laufe der Zeit hinzugefügt und/oder entfernt werden können, muß die Abfolge von Zeitschlitzen nicht fixiert bleiben; vielmehr kann sich die Abwicklung mit der Zeit ändern. Der Scheduler 42 stellt jedoch sicher, daß jede aktive Gruppe einen Zeitschlitz in jedem Zyklus erhält.
Die Abwicklung von Tasks innerhalb jeder Gruppe wird nicht präemptiv durchgeführt; die Abwicklung wird vielmehr kooperativ durchgeführt (Schritt 48 in Fig. 4). Wie oben erläutert, erfordert kooperatives Multitasking, daß ein Task freiwillig an einen anderen Task abtritt. Das in dem Abschnitt, der sich mit dem Hintergrund der Erfindung befaßt, beschriebene Beispiel konzentrierte sich auf die GetMessage-Funktion als ein Hilfsmittel zum Übergeben von Tasks untereinander. Allgemein gesagt wird das kooperative Multitasking innerhalb einer Gruppe ganz so wie die Abwicklung in dem Betriebssystem Microsoft Windows Version 3.1 durchgeführt. Wie genauer unten beschrieben werden wird, prüft die vorliegende Erfindung zusätzlich auf Abhängigkeiten, bevor sie einen Task entsperrt. APIs wie etwa GetMessage, PeekMessage, Yield und WaitMessage erlauben es Anwendungen, an andere Tasks in derselben Gruppe abzutreten.
Zusammenfassend gesagt, wird jeder Gruppe ein Zeitschlitz der Prozessorzeit in jedem Zyklus zugewiesen. Welcher Task während des Zeitschlitzes, der einer Gruppe zugewiesen ist, läuft, hängt von der kooperativen Abwicklung der Tasks innerhalb der Gruppe ab. Ein Task, der gegenwärtig für eine Gruppe läuft, wird also während jedes aufeinanderfolgenden Zeitschlitzes, der der Gruppe zugewiesen ist, zu laufen fortfahren, bis der Task an einen anderen Task in der Gruppe mittels eines Hilfsmittels wie etwa einem Aufruf der GetMessage-Funktion abtritt.
Das Betriebssystem 40 unterhält Datenstrukturen zum Überwachen, welche Tasks in jeder Gruppe vorkommen. Die primäre Datenstruktur für diesen Zweck ist die Gruppenliste 50 (Fig. 6). Die Gruppenliste 50 kann in dem Datenfeld des Betriebssystems 40 im Speicher 28 gespeichert werden. Die Gruppenliste 50 enthält jeweils einen Eintrag 52A, 52B, 52C und 52D für jeden in der Gruppe enthaltenen Task. Jeder Eintrag 52A, 52B, 52C und 52D hält einen Handle für einen Task, der Teil der Gruppe ist. Ein Handle ist eine Zahl, die einen Task inmitten der Tasks in dem System 26 eindeutig identifiziert. In dem in Fig. 6 gezeigten Beispiel enthält die Gruppenliste 50 Einträge 52A, 52B, 52C und 52D für vier Tasks: Task 1, Task 2, Task 7 und Task 8.
Die in Gruppenlisten enthaltenen Tasks können sich im Laufe der Zeit ändern. Fig. 7 ist ein Flußdiagramm, das die Schritte verdeutlicht, die ausgeführt werden, um Gruppen zusammenzufassen. Zunächst beginnt ein Task in seiner eigenen Gruppe (Schritt 54). Während des Verlaufs der Ausführung des Tasks führt der Task API-Aufrufe durch, um zu DLLs zu verknüpfen, wie etwa LoadLibrary, LoadModule, WinExec oder bestimmte Formen von SendMessage (Schritt 56). Das Betriebssystem 40 bringt den Task in eine Gruppe mit anderen Anwendungen, die dieselben DLLs verwenden, um Probleme beim gemeinsamen Verwenden von Daten zu vermeiden (Schritt 58).
Fig. 8 ist ein Flußdiagramm, das genauer verdeutlicht, wie Schritt 58 von Fig. 7 durchgeführt wird, um einen Task in eine Gruppe mit anderen Tasks zu bringen. Die Anwendung, die von einer ersten Gruppe in eine zweite Gruppe gebracht werden soll, wird in einen suspendierten Zustand versetzt, anstatt sofort von der LoadLibrary- oder LoadModule-API zurückzukehren (Schritt 60). Die erste Gruppe befindet sich zu diesem Zeitpunkt im "Synching-up"-Zustand. Das Betriebssystem 40 wartet, bis kein Anwendungscode für die zweite Gruppe läuft (Schritt 62). Mit anderen Worten wartet es, bis jeder der Tasks in Gruppe 2 eine API wie etwa GetMessage, WaitMessage oder Yield aufruft. Der Task aus der ersten Gruppe wird dann zu der zweiten Gruppe hinzugefügt (Schritt 64) und der Task kann dann zur Ausführung eingeplant werden (Schritt 66).
Damit der Scheduler 42 Zeitschlitze an Gruppen richtig zuweisen kann, muß er den gegenwärtigen Status jeder Gruppe kennen und wissen, welcher Task, wenn überhaupt, zur Ausführung während des nächsten Zeitschlitzes, der für die Gruppe bereitgestellt wird, eingeplant ist. Eine Gruppenstatustabelle 68, wie etwa die in Fig. 9 gezeigte, wird vom Betriebssystem 40 im Speicher 28 gespeichert, um den Scheduler 42 beim präemptiven Abwickeln von Tasks von verschiedenen Gruppen zu unterstützen. In dem in Fig. 9 gezeigten Beispiel hat das System 26 gegenwärtig vier aktive Taskgruppen. Ein separater Eintrag 70A, 70B, 70C und 70D wird für jede Gruppe bereitgestellt. Jeder der Einträge 70A, 70B, 70C und 70D enthält ein Statusfeld 72A, 72B, 72C bzw. 72D. Die Statusfelder 72A, 72B, 72C und 72D halten Statusinformationen, die detailliert angeben, ob einer der Tasks in den jeweiligen Gruppen zur Ausführung während des nächsten Zeitschlitzes eingeplant ist oder ob sich die Gruppe in einem "Synching-up"-Zustand befindet (was genauer unten beschrieben werden wird). Die Statusinformationen können als Gruppen von Bits kodiert sein, die in den Statusfeldern 72A, 72B, 72C und 72D gehalten werden. Jeder Eintrag 70A, 70B, 70C und 70D enthält auch ein Tasknamensfeld 74A, 74B, 74C bzw. 74D. Die Tasknamensfelder 74A, 74B, 74C und 74D halten die Tasknamen aller Tasks, die während des nächstverfügbaren Zeitschlitzes für die Gruppen laufen. Wenn also der Eintrag 70A Statusinformationen für Gruppe 1 hält, hält das Tasknamensfeld 74A einen Namen (oder ein Handle) des Tasks in Gruppe 1, der abläuft.
Das Betriebssystem 40 unterhält auch eine Modulabhängigkeitsliste für jeden der Module 38. Die Modulabhängigkeitsliste spielt eine Rolle bei der Zuweisung von Tasks/Modulen an Gruppen, wenn ein neuer Task oder ein neuer Modul zu einer Gruppe hinzugefügt oder wenn festgestellt wird, zu welcher Gruppe ein Task hinzugefügt werden wird. Die Modulabhängigkeitslisten werden untersucht um festzustellen, welcher Gruppe ein Task zugewiesen werden sollte. Präemptiv abgewickelte Gruppen besitzen stets disjunkte Modulabhängigkeitslisten. Ein Task/Modul wird in seine eigene Gruppe oder in eine Gruppe mit unabhängigen Tasks/Modulen gebracht. Eine beispielhafte Modulabhängigkeitsliste 76 wird in Fig. 10 gezeigt. Jeder Task kann einen einzelnen Modul oder mehrere Module enthalten. Die Modulabhängigkeitsliste 76 verzeichnet Module, die Kandidaten dafür sind, aufgerufen oder von dem zugeordneten Modul geladen zu werden. Die verzeichneten Module und die zugeordneten Module weisen untereinander eine Abhängigkeit auf. Einträge 64A, 64B und 64C halten Handles für die jeweiligen Module. Die Modulabhängigkeitsliste 76 hält Einträge 78A, 78B und 78C für jeden der aufgerufenen oder von dem der Liste zugeordneten Modul geladenen Module. In Fig. 10 ruft das Modul das Modul 1, die DLL 1 und die DLL 2 auf oder lädt sie.
Die Modulabhängigkeitsliste 76 ist nicht statisch; vielmehr ändert sich die Liste mit der Zeit. Fig. 11 ist ein Flußdiagramm, das die Schritte verdeutlicht, die ausgeführt werden, um eine Modulabhängigkeitsliste 76 während des Ablaufs der Ausführung des zugeordneten Moduls zu aktualisieren. Anfänglich wird eine Modulabhängigkeitsliste für jeden Modul unterhalten (Schritt 80). Ein Vorgang wird dann durchgeführt, der eine Abhängigkeit bezüglich des der Liste zugeordneten Moduls hinzufügt (Schritt 82). Dieser Vorgang kann beispielsweise das Laden eines Librarymoduls, das Laden eines DLL- Moduls, das Ausführen eines Anwendungsmoduls oder das Erlangen der Adresse eines exportierten DLL-Moduls einschließen. In dem Betriebssystem Microsoft Windows Version 3.1 fügen API-Aufrufe wie etwa LoadLibrary, LoadModule, GetProcAddress und WinExec eine Abhängigkeit bezüglich eines Moduls hinzu. Die neuen Module, die durch solche API-Aufrufe geladen, ausgeführt oder exportiert werden, werden dann zu der Modulabhängigkeitsliste hinzugefügt (Schritt 84). Auf diese Weise kann die Modulabhängigkeitsliste dynamisch während des Ablaufs der Ausführung des zugeordneten Moduls anwachsen.
Da jeder Task mehrere Module enthalten kann, stellt sich die Frage, wie eine Modulabhängigkeitsliste für einen Task zu entwickeln ist. Fig. 12 ist ein Flußdiagramm, das die Schritte zeigt, die ausgeführt werden, um eine Abhängigkeitsliste für einen Task zu erzeugen. Zunächst wird ein Task erzeugt (Schritt 86). Eine Taskabhängigkeitsliste für den Task wird dann dadurch erzeugt, daß die Vereinigung der Modulabhängigkeitsliste der Module des Tasks vorgenommen wird (Schritt 88). Auf diese Weise stellt die bevorzugte Ausgestaltung in der vorliegenden Erfindung sicher, daß alle Abhängigkeiten eines Tasks berücksichtigt werden, wenn dem Task eine Gruppe zugewiesen wird.
Es ist vielleicht hilfreich, die von dem Scheduler 42 vorgenommene Abwicklung zusammenzufassen. Der Scheduler weist jeder der aktiven Gruppen Zeitschlitze zu. Der Scheduler 42 muß auch bestimmen, welcher Task innerhalb einer Gruppe ausgeführt werden soll oder ob die Gruppe sich in einem Synching-up-Zustand befindet. Der gegenwärtig ablaufende Task wird innerhalb der Tasknamensfelder 74A, 74B, 74C und 74D (Fig. 9) der Einträge 70A, 70B, 70C und 70D der Gruppenstatustabelle 68 bestimmt. Die APIs GetMessage, PeekMessage, Yield und WaitMessage werden in der bevorzugten Ausgestaltung der vorliegenden Erfindung erweitert, um die Gruppenstatustabelle beim Übergeben oder Blockieren zu aktualisieren. Somit enthält die Gruppenstatustabelle 68 aktuelle Informationen und der geeignete Task in jeder Gruppe wird abgewickelt.
Die vorliegende Erfindung ist gut geeignet zur Verwendung in einem verteilten System. Darüber hinaus kann die vorliegende Erfindung in anderen Umgebungen implementiert werden als dem Betriebssystem Microsoft Windows Version 3.1. Weiterhin braucht die vorliegende Erfindung nicht einen einzelnen Scheduler zu verwenden; vielmehr können mehrere Scheduler zusammen verwendet werden.

Claims

1. Verfahren zum Betreiben eines Datenverarbeitungssystems (26) mit wenigstens einem Prozessor (27) zum Ausführen von Tasks, wobei das Verfahren die folgenden Schritte umfaßt:

logisches Aufteilen (44) von Tasks in Gruppen untereinander abhängiger Tasks;

präemptives Abwickeln (46) der Gruppen von auszuführenden Tasks, so daß jeder Gruppe von Tasks ein Zeitschlitz in einem Zyklus zugewiesen wird, in dem ihre Tasks auf dem Prozessor ablaufen können; und

nicht-präemptives Abwickeln (48) von auszuführenden Tasks innerhalb jeder Gruppe während des der Gruppe zugeordneten Zeitschitzes für jede Gruppe.

2. Verfahren nach Anspruch 1, wobei das Datenverarbeitungssystem (26) wenigstens eine Speichereinrichtung (30) enthält und das Verfahren weiterhin den Schritt des Speicherns einer Gruppenliste (50) für jede zugeordnete Gruppe in der Speichereinrichtung umfaßt, wobei jede Gruppenliste Identifizierungsinformationen (52A- 52D) für in der zugeordneten Gruppe enthaltene Tasks enthält.

3. Verfahren nach Anspruch 1, weiterhin den Schritt des Speicherns einer Gruppenliste (50) für jede Gruppe umfassend, die Identifizierungsinformationen für in der Gruppe enthaltene Tasks hält.

4. Verfahren nach einem der Ansprüche 1 bis 3, weiterhin den Schritt umfassend des Speicherns von Statusinformationen (72A-72D) für jede Gruppe (70A-70D), die angeben, ob die Gruppe einen Task besitzt, der abläuft, und des Haltens von Identifizierungsinformationen (74A-74D) über jeden Task, der abläuft.

5. Verfahren nach einem der Ansprüche 1 bis 4, wobei der Schritt des logischen Aufteilens (44) von Tasks in Gruppen untereinander abhängiger Tasks die folgenden Schritte umfaßt:

anfängliches Plazieren (54) jedes Tasks in seine eigene Gruppe; und

nachfolgendes Kombinieren (58) von Gruppen von Tasks zu einer Mischgruppe, wobei jeder Task in der Mischgruppe einen gemeinsamen Modul aufruft, wenn er ausgeführt wird.

6. Verfahren nach einem der Ansprüche 1 bis 5, wobei der Schritt des logischen Aufteilens (44) von Tasks in Gruppen untereinander abhängiger Tasks die folgenden Schritte umfaßt:

Bereitstellen einer Taskabhängigkeitsliste für jeden Task, wobei die Taskabhängigkeitsliste Codemodule verzeichnet, die Kandidaten dafür sind, aufgerufen zu werden, wenn der Task auf dem Prozessor ausgeführt wird; und

Untersuchen der Taskabhängigkeitslisten, um die Tasks logisch in Gruppen untereinander abhängiger Tasks aufzuteilen.

7. Verfahren nach einem der Ansprüche 1 bis 6, wobei der Schritt des logischen Aufteilens (44) von Tasks in Gruppen untereinander abhängiger Tasks die folgenden Schritte umfaßt:

Bereitstellen einer Modulabhängigkeitsliste (76) für jeden zugeordneten Codemodul, wobei jede Modulabhängigkeitsliste untereinander abhängige Codemodule (78A-78C) des zugeordneten Codemoduls verzeichnet;

Erzeugen einer Taskabhängigkeitsliste für jeden Task durch Vornehmen einer logischen Vereinigung von Modulen, die in den Modulabhängigkeitslisten von Modulen verzeichnet sind, die Kandidaten dafür sind, aufgerufen zu werden, wenn der Task auf dem Prozessor ausgeführt wird; und

Untersuchen der Taskabhängigkeitslisten, um die Tasks in Gruppen untereinander abhängiger Tasks logisch aufzuteilen.

8. Datenverarbeitungssystem (26), umfassend:

Partitionierungsmittel (27) zum Aufteilen von Tasks in Gruppen untereinander abhängiger Tasks;

Ausführungsmittel (27) zum Ausführen von Tasks;

einen präemptiven Scheduler (42) zum präemptiven Abwickeln von Gruppen von Tasks, so daß jeder Gruppe ein Zeitschlitz zugewiesen wird, in dem einer ihrer Tasks auszuführen ist; und

einen nicht-präemptiven Scheduler (42) zum nicht-präemptiven Abwickeln von Tasks innerhalb jeder Gruppe.

9. System nach Anspruch 8, weiterhin Speichermittel (30) zum Speichern einer Gruppenliste (50) für jede Gruppe umfassend, wobei jede Gruppenliste Identifizierungsinformationen (52A-52D) für in der Gruppe enthaltene Tasks enthält.

10. System nach Anspruch 8 oder 9, weiterhin Mittel umfassend zum Speichern von Statusinformationen (72A-72D) für jede Gruppe (70A-70D), die angeben, ob die Gruppe einen Task besitzt, der abläuft, und zum Halten von Identifizierungsinformationen (74A- 74D) über jeden Task, der abläuft.