PatentDe  


Dokumentenidentifikation DE102006028310A1 03.05.2007
Titel System und Verfahren zur Mehrdimensionalen Ressourcenverwaltung
Anmelder Agilent Technologies, Inc. (n.d.Ges.d.Staates Delaware), Palo Alto, Calif., US
Erfinder Shrum, Kenneth W., Loveland, Col., US
Vertreter Schoppe, Zimmermann, Stöckeler & Zinkler, 82049 Pullach
DE-Anmeldedatum 20.06.2006
DE-Aktenzeichen 102006028310
Offenlegungstag 03.05.2007
Veröffentlichungstag im Patentblatt 03.05.2007
IPC-Hauptklasse H04L 12/24(2006.01)A, F, I, 20060620, B, H, DE
Zusammenfassung Ein Verfahren, System und Programmprodukt zum Verwalten von Systemressourcen in einem System mit einer möglicherweise großen Anzahl von Ressourcen und Aufgaben, die eine ausschließliche Verwendung der Ressourcen benötigen, um abzulaufen. Das System ist aus einer Einrichtung zum Beschreiben von Ressourcen und Ressourcenauswahlkriterien, einer Einrichtung zum Beschreiben von vollständigen Ressourcenanforderungen einer Aufgabe als eine Menge von benannten Ressourcenauswahlkriterien, einer Einrichtung zum Unterstützen alternativer Ressourcenerfordernisse für eine gegebene Aufgabe und ferner zum Priorisieren über alle Aufgaben und alle Ressourcenerfordernisse durch ein Anbringen einer Priorität an jedem Ressourcenerfordernis und Ermöglichen mehrerer alternativer Ressourcenerfordernisse pro Aufgabe, und einer effizienten Einrichtung zum simultanen Auswählen einer gesonderten Ressorce aus jedem von N möglicherweise überlappenden Sätzen von Kandidatenressourcen, derart, dass irgendeine gegebene Auswahl mit gleicher Wahrscheinlichkeit gewählt wird (d. h. fair ist), gebildet. Es sind Techniken zum Gewinnen einer erheblichen Leistungsfähigkeit offenbart, einschließlich eines Verwendens einer gierigen Ressourcengewinnung.

Beschreibung[de]

Diese Erfindung bezieht sich auf ein Verfahren, ein System und ein Programmprodukt zum Verwalten einer oder mehrerer Ressourcen eines Datennetzes bzw. Datennetzwerks.

Ein Verwalten der Verwendung von Ressourcen in einem Datennetz ist ein wesentlicher Teil eines Systementwurfs. Bei herkömmlichen Systemen gibt es verschiedene Systemressourcen, die für Aufgaben verfügbar sind, und jede Aufgabe erfordert typischerweise eine ausschließliche Verwendung der gemeinschaftlich verwendeten Ressourcen für eine bestimmte Zeitperiode, um die Ausführung derselben abzuschließen. Ein Ressourcenverwalter bzw. eine Ressourcenverwaltungseinrichtung kann in Verbindung mit einem Dienstqualitätsverwalter wirksam sein, der Dienstqualitätsgarantien (QoS-Garantien; QoS = Quality of Service) für einzelne Prozesse oder Aufgaben liefert. Ein derartiger Testverwalter ist der Wireless Quality of Service Manager (WQM) von Agilent Technologies, Inc. WQM ist ein Aktivruftestsystem, das mobiltelefonbasierte Dienste testet bzw. prüft, indem versucht wird, dieselben von einem Mobiltelefon zu einem anderen zu verwenden. Eine Beschreibung der Fähigkeiten von WQM ist in dem Informationsblatt mit dem Titel „Agilent OSS QoS Manager" vorgesehen, das unter http://we.home.agilent. com/cgi-bin/bvpub/agilent/Product/cp Product.jsp?OID=536882 909&NRV ID=536885380.536882909.00&LANGUAGE CODE=eng&COUTRY CODE=ZZ&CT=PRODUCT&JPID=/comms/firehunter betrachtet werden kann, deren Inhalte hierdurch durch Bezugnahme in ihrer Gesamtheit aufgenommen sind.

Zu einer gewissen Zeit, wenn Ressourcen verfügbar sind, derart, dass eine Aufgabe ausgeführt werden kann, wird der „Rückruf" der Aufgabe aufgerufen, was wiederum einen entfernten Java-Rückruf zu dem WQM vornehmen könnte, um den Test mit den tatsächlichen Ressourcen zu beginnen, die verwendet werden sollen. Wenn der Test abgeschlossen ist, würde der WQM erneut ein Ressourcenverwaltungssystem aufrufen, um die Ressourcen freizugeben, z. B. Schnittstellen und Identitätsmodule (IMs).

Der WQM beschäftigt sich regelmäßig mit Hunderten von Schnittstellen, einigen tausend Tests und bis zu Zehntausenden von IMs. Zusätzlich beschäftigt sich der WQM mit der Tatsache, dass bestimmte Gruppen innerhalb eines gegebenen Kunden für spezielle Schnittstellen und/oder IMs bezahlt haben und die Tests derselben folglich eine gewisse Priorität hinsichtlich eines Verwendens dieser Ressourcen aufweisen sollten.

Mehrere der Ziele von Ressourcenverwaltungssystemen, die nicht auf die Umgebung von Drahtloskommunikationstestsystemen begrenzt sind, können allgemeiner angegeben werden. Bei einem jeglichen Datennetz existiert eine Menge bzw. ein Satz von gemeinschaftlich verwendeten Ressourcen. Es besteht ein Wunsch, eine Gewinnung bzw. Akquisition und Freigabe der Ressourcen durch die Aufgaben zu verwalten, derart, dass ein ausschließlicher Zugriff auf Ressourcen garantiert ist und dass es eine hohe Nutzung von Ressourcen gibt. Um bestimmte Ressourcen besteht starke Konkurrenz, also ist es wichtig, dass die Ressourcen belegt bzw. beschäftigt gehalten werden. Es ist zusätzlich wünschenswert, eine „faire" Verwendung der Ressourcen zu erreichen, d. h. wodurch eine verfügbare Ressource, die mit einem Auswahlkriterium übereinstimmt, eine gleiche Wahrscheinlichkeit aufweist, ausgewählt zu werden. Es ist ferner erwünscht, eine „faire" Auswahl von Ausgaben zu erreichen, was bedeutet, dass eine jegliche Aufgabe, die Ressourcen gewinnen könnte, die mit allen der Auswahlkriterien derselben übereinstimmen, eine gleiche Wahrscheinlichkeit aufweist, ausgewählt zu werden. Die Gewinnung und Freigabe von Ressourcen sollte ferner relativ skalierbar und „sicher" sein, was blockierungsfrei, von mehreren Teilprozessen bzw. Threads aus verwendbar, etc. bedeutet. Während einige Anstrengungen unternommen wurden, um diese Ziele anzusprechen, bleibt ein Bedarf nach einem verbesserten Verfahren, System und Programmprodukt zum Verwalten von Ressourcen in einem System bestehen.

Es ist die Aufgabe der vorliegenden Erfindung, ein softwareimplementiertes Verfahren zur Ressourcenverwaltung, ein System zum Verwalten einer Mehrzahl von Ressourcen zum Bedienen einer Mehrzahl von Aufgaben und ein prozessorlesbares Computerprogrammprodukt mit verbesserten Charakteristika zu schaffen.

Diese Aufgabe wird durch ein Verfahren gemäß Anspruch 1, ein System gemäß Anspruch 8 und ein Produkt gemäß Anspruch 15 gelöst.

In einem ersten Aspekt sieht die vorliegende Erfindung ein softwareimplementiertes Verfahren zur Ressourcenverwaltung in einem System vor, das eine Mehrzahl von Ressourcen S zum Bedienen einer Mehrzahl von Aufgaben T umfasst. Das Verfahren verwendet simultane gierige Gewinnungsprinzipien für eine effiziente Ressourcennutzung. Das Verfahren führt auf eine Aufgabenvorlage und eine Freigabe von Ressourcen hin als eine atomare Operation für jedes Ressourcenerfordernis Ri einer Mehrzahl von Ressourcenerfordernissen R, die jeweils einer Aufgabe Tk zugeordnet sind, die eine Ausführung erfordert, in einer zufälligen Reihenfolge die iterativen Schritte eines Wählens einer Gruppe von verfügbaren Ressourcen Sj aus, die Ressourcenerfordernissen Ri genügen, derart, dass keine Ressource in Sj mehr als einmal ausgewählt wird. Falls eine derartige Gruppe von verfügbaren Ressourcen Sj existiert, werden die gewählten verfügbaren Ressourcen Sj gewonnen, was dieselben nicht mehr verfügbar macht. Die gewonnenen Ressourcen werden zu Tk weitergereicht und alle der Ressourcenerfordernisse Ri werden aus der Mehrzahl von Ressourcenerfordernissen R entfernt.

Jede der Mehrzahl von Ressourcen S ist durch eines oder mehrere benannte Attribute gekennzeichnet, die jeweils zumindest einen Wert aufweisen. Jedes der Mehrzahl von Ressourcenerfordernissen Ri ist durch eine Gruppe von zumindest einem Benannte-Ressource-Auswahlkriterium C gekennzeichnet und jedes der Ressourcenauswahlkriterien ist als ein Boolescher Ausdruck ausgedrückt.

Typischerweise ist mehr als ein Ressourcenerfordernis Ri jeder Aufgabe Tk zugeordnet und jedem Ressourcenerfordernis Ri ist vorzugsweise eine gewisse Priorität Pj zugeordnet, die eine Betrachtung der Mehrzahl von Ressourcenerfordernissen R in priorisierten Gruppen gestattet, und innerhalb jeder Gruppe das Ri in zufälliger Reihenfolge. Das Verfahren wählt die verfügbaren Ressourcen Sj mit gleicher Wahrscheinlichkeit aus dem Satz aller derartiger Gruppen Sk aus, die den Ressourcenerfordernissen Ri genügen.

In einem anderen Aspekt sieht die vorliegende Erfindung ein System und einen Ressourcenverwalter bzw. eine Ressourcenverwaltungseinrichtung zum Verwalten einer Mehrzahl von Ressourcen zum Bedienen einer Mehrzahl von Aufgaben vor. Das System und der Ressourcenverwalter sind wirksam, um eine Gewinnung und Freigabe von Ressourcen gemäß dem oben beschriebenen Verfahren zu gestatten.

In einem anderen Aspekt sieht die vorliegende Erfindung ein maschinenlesbares Computerprogrammprodukt vor, das an einer oder mehreren programmierbaren Speichervorrichtungen codiert ist. Das Computerprogrammprodukt ist durch einen oder mehrere Prozessoren ausführbar, um Verfahrensschritte zum Verwalten einer Mehrzahl von Ressourcen S eines Systems zum Bedienen einer Mehrzahl von Aufgaben T durchzuführen.

Diese und andere Aspekte der vorliegenden Erfindung werden nun mit Bezug auf die folgenden Figuren detaillierter beschrieben.

Für ein besseres Verständnis der vorliegenden Erfindung, gemeinsam mit anderen und weiteren Aufgaben derselben, wird Bezug auf die zugehörigen Zeichnungen und die detaillierte Beschreibung genommen.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeichnungen näher erläutert. Es zeigen:

1 ein Blockdiagramm, das die Beziehungen zwischen Aufgaben, Ressourcenerfordernissen und Ressourcenauswahlkriterien gemäß einem Ausführungsbeispiel der Erfindung darstellt;

2 eine Tabelle, die Bespiele von Ressourcen und zugeordneten Attributen gemäß einem Ausführungsbeispiel der Erfindung vorsieht;

3 ein Blockdiagramm, das die Beziehungen unter Aufgaben, Ressourcenerfordernissen und Ressourcenauswahlkriterien und die Darstellungen des jeweiligen inneren Zustands derselben gemäß einem Ausführungsbeispiel der Erfindung darstellt;

4 ein Prozessflussdiagramm, das ein Verfahren zur Ressourcenverwaltung gemäß der vorliegenden Erfindung darstellt;

5 ein Prozessflussdiagramm, das ein Verfahren zum Freigeben und/oder Hinzufügen von Ressourcen zu einem System gemäß der vorliegenden Erfindung darstellt;

6 ein Prozessflussdiagramm, das ein Verfahren zur einheitlichen zufälligen Auswahl von Ressourcengruppen gemäß der vorliegenden Erfindung darstellt; und

7 eine Darstellung einer spezifischen Betriebsumgebung für einen Ressourcenverwalter gemäß der vorliegenden Erfindung.

Konzeptioneller Überblick

Gemäß einem Ausführungsbeispiel der vorliegenden Erfindung ist ein System zum Verwalten einer Mehrzahl von Ressourcen S zum Bedienen einer Mehrzahl von Aufgaben T vorgesehen, die eine Ausführung erfordern, wobei das System einen Ressourcenverwalter bzw. eine Ressourcenverwaltungseinrichtung umfasst, der bzw. die zumindest teilweise aus einem prozessorlesbaren Computerprogrammprodukt gebildet ist, das an einer oder mehreren programmierbaren Speichervorrichtungen codiert ist.

Der Ressourcenverwalter empfängt typischerweise simultan vorgelegte Anforderungen, um einige hundert Aufgaben (Tasks) T auszuführen, wobei jede Aufgabe Tk einen einzigen Test darstellt, entweder einseitig oder zweiseitig. Mit Bezug auf 1 benötigt jede Aufgabe Tk 10, die eine Ausführung erfordert, eine ausschließliche Verwendung bestimmter Ressourcen aus der Menge bzw. dem Satz von Ressourcen S für eine bestimmte Zeitperiode, nach der die Aufgabe die Ressourcen freigibt. Jede Aufgabe 10 beschreibt, welche Ressourcen dieselbe erfordert, hinsichtlich Kombinationen von benannten Attributen, die hierin als Ressourcenerfordernisse (RR = Resource Requirements 12) bezeichnet sind. Ressourcenauswahlkriterien (RSC = Ressource Selection Criteria 14) beschreiben, welche Ressourcen für eine Verwendung durch eine Aufgabe annehmbar wären. RR 12 ist eine Gruppe von benannten RSC, die alle erfüllt sein müssen, um die RR einzuhalten. Eine Aufgabe kann irgendeine Anzahl von priorisierten RR 12 aufweisen, von denen jede für die Bedürfnisse der Aufgabe annehmbar ist. Ein RR 12 mit höherer Priorität gibt lediglich eine Präferenz für dieses RR anstelle eines anderen an. Vollständige Ressourcenerfordernisse einer Aufgabe können somit als ein Satz von benannten RSC 14 beschrieben werden und der Ressourcenverwalter ist zum Unterstützen alternativer Ressourcenerfordernisse für eine gegebene Aufgabe und Priorisieren über alle Aufgaben T und alle RR durch ein Anbringen einer Priorität an jedem RR 12 und ein Ermöglichen einer Gewinnung von alternativen RR pro jeder Aufgabe in der Lage.

Zu diesem Zweck verwendet ein Ressourcenverwalter gemäß der vorliegenden Erfindung einen gierigen simultanen Gewinnungsansatz, um sicherzustellen, dass das System blockierungsfrei ist. Es ist jedoch immer noch möglich, dass ein gewisser externer Klient eine erste Ressource A gewinnt und dann versucht, eine zweite Ressource B zu gewinnen, während ein anderer externer Klient B gewonnen hat und versucht, A zu gewinnen. Für eine optimale Ressourcenverwendung sollten Klienten die erforderlichen Ressourcen alle simultan bei dem Beginn der Aufgabe gewinnen. Ressourcen können ohne Schwierigkeit entweder simultan oder wenige zu einer Zeit freigegeben werden. Der Ressourcenverwalter wählt simultan eine gesonderte Ressource aus jedem von N möglicherweise überlappenden Sätzen von Kandidatenressourcen aus, derart, dass irgendeine gegebene Auswahl mit gleicher Wahrscheinlichkeit gewählt ist (d. h. fair ist).

Eine gierige Gewinnung weist den Vorteil auf, dass dieselbe die Ressourcen zu einem jeglichen gegebenen Moment so belegt wie möglich hält. Der Ressourcenverwalter gewinnt ferner eine erhebliche Leistungsfähigkeit durch ein Beibehalten eines Satzes von RSC 14, die mit derselben übereinstimmen, für jede Ressource S und eines Satzes von verfügbaren übereinstimmenden Ressourcen Sj für jedes RSC 14. Der Ressourcenverwalter ist in der Lage, schnell zufällige Aufgaben für eine Ausführung auszuwählen, wobei RR mit höher Priorität bevorzugt sind, bis keine weiteren Aufgaben mit den aktuell bekannten verfügbaren Ressourcen ausgeführt werden können. Wenn Ressourcen durch die Aufgaben freigelassen werden (z. B. ein WQM-Test eine Ausführung abschließt oder die Ressource nicht mehr benötigt) oder zusätzliche Ressourcen zu dem System hinzugefügt werden, identifiziert der Ressourcenverwalter schnell, welche anderen Aufgaben, falls es irgendwelche gibt, ausgeführt werden können.

Systemhardwareüberblick

In einem anderen Aspekt sieht die vorliegende Erfindung ein prozessorlesbares Computerprogrammprodukt vor, das an einer oder mehreren programmierbaren Speichervorrichtungen codiert ist und durch einen oder mehrere Prozessoren ausführbar ist, um hierin beschriebene Verfahrensschritte zum Verwalten einer Mehrzahl von Ressourcen S eines Systems zum Bedienen einer Mehrzahl von Aufgaben T durchzuführen. Ein Prozessor, der den Softwarecode des prozessorlesbaren Mediums ausführt, würde die unten beschriebenen Schritte des Ressourcenverwalters durchführen. Ein derartiger Prozessor ist Teil eines Systems, das ein Datenkommunikationsmedium (verdrahtet oder drahtlos) zwischen dem Prozessor und den Ressourcen und Ressourcensteuerungen und einen Hauptspeicher umfasst, wie beispielsweise einen Direktzugriffsspeicher (RAM = Random Access Memory) oder eine andere dynamische Speicherungsvorrichtung zum Speichern von Informationen und Anweisungen, die durch den Prozessor ausgeführt werden sollen. Der Hauptspeicher kann ferner zum Speichern temporärer Variablen oder anderer Zwischeninformationen während einer Ausführung von Anweisungen durch den Prozessor verwendet werden. Eine Speicherungsvorrichtung, wie beispielsweise eine Magnetplatte oder optische Platte, kann ebenfalls zum Speichern von Informationen oder Anweisungen vorgesehen sein.

Der Ausdruck „prozessorlesbares Computerprogrammprodukt", bezieht sich, wie hierin verwendet, auf irgendein Medium, das an einem Liefern von Daten teilnimmt, die bewirken, dass eine Maschine in einer spezifischen Weise wirksam ist.

Ein derartiges Medium kann viele Formen annehmen, einschließlich aber nicht begrenzt auf nichtflüchtige Medien, flüchtige Medien und Übertragungsmedien. Nichtflüchtige Medien umfassen beispielsweise optische oder magnetische Platten. Flüchtige Medien umfassen einen dynamischen Speicher, wie beispielsweise einen Hauptspeicher. Häufige Formen von maschinenlesbaren Medien umfassen beispielsweise eine Diskette, eine flexible Platte, eine Festplatte, ein Magnetband oder irgendein anderes Magnetmedium, eine CD-ROM, irgendein anderes optisches Medium, Lochkarten, ein Papierband, irgendein anderes spezifisches Medium mit Mustern von Löchern, einen RAM, einen PROM und einen EPROM, einen FLASH-EPROM, irgendeinen anderen Speicherchip oder eine Kassette, eine Trägerwelle, wie es hierin im Folgenden beschrieben ist, oder irgendein anderes Medium, von dem ein Computer lesen kann.

Das System umfasst ferner eine Kommunikationsschnittstelle, die mit einem Bus für Datenkommunikationen zwischen den Ressourcen und dem Ressourcenverwalter gekoppelt ist. Kommunikationsschnittstellen liefern vorzugsweise eine Zweiwegedatenkommunikationskopplung mit einer Netzverbindung, die mit einem lokalen Netz verbunden ist. Die Kommunikationsschnittstelle kann beispielsweise eine Dienstintegriertes-Digitalnetz-Karte (ISDN-Karte; ISDN = Integrated Services Digital Network) oder ein Modem sein, um eine Datenkommunikationsverbindung mit einem entsprechenden Typ einer Telefonleitung zu liefern. Als ein anderes Beispiel kann die Kommunikationsschnittstelle eine Lokales-Netz-Karte (LAN-Karte; LAN = Local Area Network) sein, um eine Datenkommunikationsverbindung mit einem kompatiblen LAN zu liefern. Drahtlose Verbindungen können ebenfalls implementiert sein. Bei irgendeiner derartigen Implementierung sendet und empfängt die Kommunikationsschnittstelle elektrische, elektromagnetische oder optische Signale, die digitale Datenströme tragen, die verschiedenen Typen von Informationen darstellen.

Systemsoftwareüberblick Interne Strukturen

Eine „Ressource", wie hierin verwendet, weist keine Identität in oder von sich selbst auf. Vielmehr ist eine Ressource einfach die benannten Attribute derselben. Folglich ist es nicht möglich, zwei Ressourcen aufzuweisen, die über alle benannten Attribute identisch sind. Für Ressourcen, die bekanntermaßen eine unabhängige Identität aufweisen, ist ein Hinzufügen eines eindeutigen „id"-Attributs zu derartigen Ressourcen ein Ansatz, um eine unabhängige Behandlung zu garantieren. Irgendein gegebenes Attribut weist einen Namen und einen Satz von Werten auf. Der Ausdruck „Menge" bzw. Satz wird hierin in dem mathematischen Sinn verwendet, dahin gehend, dass keine Reihenfolge impliziert oder betrachtet wird.

Unter erneuter Bezugnahme auf 1 beschreiben „Ressourcenauswahlkriterien" (RSC 14), welche Ressource für eine Verwendung durch eine Aufgabe annehmbar wäre. Jedes RSC ist vorzugsweise als ein Boolescher Ausdruck in einer primitiven Termform ausgedrückt, wie beispielsweise „ein benanntes Attribut einer Ressource umfasst einen speziellen Wert", „ein benanntes Attribut einer Ressource umfasst einen Wert, der mit einem regulären Ausdruck übereinstimmt", und „eine Ressource ist identisch mit einer speziellen Ressource hinsichtlich aller genannter Attribute". Ein beliebig komplexes RSC kann unter Verwendung von Kombinationen dieser Formen aufgebaut werden. Beispielsweise würde eine Ressource mit „Dienste = {a, b, c}" mit einem Auswahlkriterium mit „Dienste umfasst b" übereinstimmen.

„Ressourcenerfordernisse" (RR 12) ist eine Gruppe von benannten RSC 14, die alle erfüllt sein müssen, um die RR 12 einzuhalten. Das RR 12 beschreibt den exakten Satz von Ressourcen, den eine Aufgabe anfordert. Um ein Erfordernis zu erfüllen, muss eine gesondert verfügbare Ressource ohne eine Duplikation jedem der benannten RSC zugewiesen sein. Die gleiche verfügbare Ressource kann nicht simultan mehr als einem benannten RSC zugewiesen sein. In dem Fall, dass ein RR 12 erfüllbar ist, was bedeutet, dass es zumindest eine Kombination von Ressourcen S gibt, die den mehreren RSC zugewiesen sein können, sieht die vorliegende Erfindung vor, dass jede derartiger Kombinationen mit einer gleichmäßigen Wahrscheinlichkeit ausgewählt wird.

Wie hierin verwendet, ist eine „Aufgabe" (wie beispielsweise die Aufgabe 10) ein Satz von priorisierten RR. Die RR werden in einer Prioritätsreihenfolge versucht und die Aufgabe wird schließlich einem Satz von Ressourcen zugewiesen, der dem erfüllbaren RR mit der höchsten Priorität genügt. Mit anderen Worten, falls die Aufgabe einem Satz von Ressourcen zugewiesen ist, der dem RR „X" genügt, gibt es garantiert kein RR „Y" mit höherer Priorität für diese Aufgabe, das mit den verfügbaren Ressourcen erfüllt werden könnte.

2 sieht nicht einschränkende Beispiele von Ressourcen 16A16D (durch die Attribute 18 derselben gekennzeichnet) vor, die Identitätsmodule (IMs) bei einem WQM-Ausführungsbeispiel darstellen. Internationale Mobilstationsidentitäten (IMSIs = International Mobile Station Identities) sind in der Realität viel länger aber sind eindeutige Identifizierer für die IMs. Es ist zu beachten, dass die Ressourcen 16A und 16B außer der IMSI derselben identisch sind. Dies ist ein häufiger Fall. Die Ressourcen 16A16D sind durch die Attribute 18 derselben vollständig beschrieben, die mehrwertig sein können (z. B. unterstützte Dienste). Falls ein RSC betrachtet wird, das ausgedrückt ist als nicht (PLMN umfasst Vodaphone) und (unterstützte Dienste umfasst Sprache) und (unterstützte Dienste umfasst FAX), dann genügt lediglich die Ressource 16D dem RSC. Im Allgemeinen genügt eine große Anzahl von Ressourcen irgendeinem gegebenen RSC.

Aufgaben, RRs, RSCs und Ressourcen sind bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung alle direkt für einen Benutzer sichtbare, externe Elemente und sind aufgebaut, um die Bereichsentitäten auszudrücken. Aufgaben können ferner einem „Rückruf" zugeordnet sein, der aufgerufen wird, wenn eine Aufgabe Ressourcen zugewiesen ist, um die zugewiesenen benannten Ressourcen der Aufgabe zu übergeben. Die Ressourcen sind mit den gleichen Namen benannt, die in dem RR verwendet werden, um das RSC zu benennen. Eine Ressource, die mit einem RSC übereinstimmt, das mit B benannt ist, würde mit dem Namen B zurückgegeben, wodurch ermöglicht ist, dass die Aufgabe die zugewiesenen Ressourcen ohne Weiteres zuordnet. Die einzigen Beziehungen zwischen diesen externen Strukturen weisen die Beziehung auf, dass eine Aufgabe priorisierte RR aufweist und ein RR ein benanntes RSC aufweist. Es gibt keine explizite Beziehung zu Ressourcen, nur Implizite von Ressourcen, die dem RSC genügen.

Mit Bezug auf 3 gibt es vier interne Strukturen, die die externen Strukturen „umhüllen": Aufgabenzustand 20, Ressourcenerforderniszustand (RRS = Resource Requirement State 22), Ressourcenauswahlkriterienzustand (RSCS = Resource Selection Criteria State 24) und Ressourcenzustand (RS = Resource State 26). Die internen Strukturen können zusätzliche Informationen beibehalten, die für einen Benutzer nicht von Belang sind, und denen der Benutzer nicht ausgesetzt sein sollte. Jeder Aufgabenzustand 20 weist zugeordnete priorisierte RRS 22 auf, die nicht gemeinschaftlich verwendet sind (d. h. dieselben sind eindeutig für einen gegebenen Aufgabenzustand 20). Jeder RRS 22 weist zugeordnete benannte RSCS 24 auf, sowie die Aufgabe 28, die das RR 30 aufweist, das dem RRS 22 entspricht. Die RSCS 24sind gemeinschaftlich verwendet; irgendwelche zwei RSC 32, die identisch sind, können die gleichen RSCS 24 verwenden.

Jeder RSCS 24 weist ein entsprechendes RSC 32 desselben auf und ferner einen Satz der Ressourcenzustände (RS 26) für die Ressourcen 34, die durch das RSC 32 ausgewählt sind und die aktuell verfügbar sind. Wie es oben erwähnt ist, sind die RSCS 24 gemeinschaftlich verwendet. Da ein RSC 32 einfach ein Boolescher Ausdruck ist, kann der gleiche Boolesche Ausdruck überall austauschbar verwendet werden. Jeder RS 26 weist eine entsprechende Ressource 34 desselben, einen Satz der RSCS 36, die die Ressource 34 auswählen, und ein Flag auf, das markiert, ob die Ressource 34 verfügbar ist oder nicht. Jeder RSCS 36 verfolgt lediglich diese Ressourcen 34, die derselbe jeweils auswählt und die für eine Verwendung verfügbar sind. Jeder RS 26 verfolgt alle RSCS, die denselben auswählen, ob die Ressource 34 für eine Verwendung verfügbar ist oder nicht. Wenn Ressourcen gewonnen und freigegeben werden, werden die RSCS 24, 36 aktualisiert, um dieselben „synchronisiert" zu halten.

Die „Zustände" 20, 22, 24, 26, 36 weisen Identitätssemantik auf, und nicht Wertesemantik. Die extern sichtbaren Elemente 28, 30, 32, 34 weisen Wertesemantik auf, was bedeutet, dass irgendwelche zwei äquivalenten Ressourcen beispielsweise austauschbare Ressourcen sind. Dieselben weisen ferner relativ kurze Lebensdauern auf, ungleich den „Zuständen" und insbesondere den RSCS 24, 36 und dem RS 26, die sehr lange Lebensdauern aufweisen und verwendet werden, um die implizite Beziehung zwischen den RSC 32 und den Ressourcen 34, die dieselben auswählen, explizit zu machen. Die Verwendung von „Zuständen" ist in der Praxis wichtig, da die extern sichtbaren Elemente (Aufgaben 28, RR 30, RSC 32, Ressourcen 34, etc.) von einem anderen Prozess in einem anderen Adressraum aus verwendet werden können und auf dieselben zugegriffen werden kann. In einer derartigen Umgebung ist die Ressource, die freigegeben ist, nicht die identische Ressource, die gewonnen wurde, sondern anstelle dessen eine äquivalente Ressource mit identischen Attributen. Durch ein internes Umgehen mit den Zuständen und Sammlungen von Zuständen sind Nachschlag- und Anpassungsoperationen in der Lage, in den Tiefen der Ressourcenverwaltungsalgorithmen, die durch die vorliegende Erfindung vorgesehen sind, viel schneller abzulaufen.

Ressourcengewinnung und -freigabe

Die vorliegende Erfindung benutzt einen gierigen Simultangewinnungsansatz, um alle Ressourcen zu gewinnen, die für eine Aufgabe benötigt werden, was nun mit Bezug auf 4 beschrieben wird, die ein Flussdiagramm darstellt, das ein softwareimplementiertes Verfahren 500 darstellt, das durch den Ressourcenverwalter durchgeführt wird, wenn eine Aufgabe oder Aufgaben vorgelegt wird bzw. werden.

Bei einem Schritt 501 wird ein Aufgabenzustand für jede vorgelegte Aufgabe Tk erzeugt. Dann wird ein RRS für jedes RR Ri jeder vorgelegten Aufgabe Tk erzeugt (Schritt 502). Dann wird bei einem Schritt 504 der entsprechende RSCS für jedes RSC Ci jedes RR Ri jeder vorgelegten Aufgabe gefunden.

Bei Schritten 506508 wird, falls kein derartiger RSCS gefunden wird (d. h. kein RCSC diesem RSC entspricht), ein neuer RSCS erzeugt, werden alle RS, die durch den neu erzeugten RSCS ausgewählt sind, gefunden, wobei der RSCS zu dem Satz aller RSCS hinzugefügt wird, die jeden derartigen RS auswählen, und für jeden derartigen RS, der verfügbar ist, der RS zu dem Satz aller verfügbaren RS für das RSC Ci hinzugefügt wird. Ein Durchführen der Schritte 506508 resultiert in einer Abtastung durch alle Ressourcen hindurch, die durchgeführt wird, wenn benötigt, aber in der Praxis selten erforderlich ist.

Bei einem Schritt 512 werden die RRS für die vorgelegten Aufgaben in Gruppen betrachtet, die nach einer Priorität mit der höchsten Priorität zuerst und in einer zufälligen Reihenfolge innerhalb jeder Gruppe gruppiert sind (Schritt 514).

Bei Schritten 516522 als eine atomare Operation versucht der Ressourcenverwalter für jedes RR Ri, das einer Aufgabe Tk zugeordnet ist, die eine Ausführung erfordert, eine Gruppe von verfügbaren Ressourcen Sj auszuwählen, die RR Ri genügen, derart, dass keine Ressource in Sj mehr als einmal ausgewählt wird. Falls eine derartige Gruppe von verfügbaren Ressourcen Sj existiert und gewählt wird, gewinnt der Ressourcenverwalter dann die verfügbaren Ressourcen Sj, wobei die verfügbaren Ressourcen Sj nicht mehr verfügbar gemacht werden, und gibt dann die verfügbaren Ressourcen Sj an die Aufgabe Tk und entfernt den Aufgabenzustand, der Tk entspricht, und alle RRSs, die diesem Aufgabenzustand zugeordnet sind, aus dem System. Die RSCs, die Tk zugeordnet sind, werden alle immer noch beibehalten und nicht aus dem System entfernt. Hinsichtlich der Zustände ausgedrückt, die die Aufgaben, Ressourcen, Ressourcenerfordernisse und Ressourcenauswahlkriterien darstellen, versucht bei einem Schritt 516 der Ressourcenverwalter für jeden RRS, einen gesonderten RS für jeden der RSCS desselben auszuwählen. Jeder ausgewählte RS wird als nicht verfügbar markiert, wobei dieser RS aus dem Satz von verfügbaren RS für jeden RSCS entfernt wird, der diesen RS bei einem Schritt 518 auswählt. Bei einem Schritt 520 wird die Aufgabe Tk „zurückgerufen" und den benannten Ressourcen übergeben, die erfolgreich gewonnen wurden. Und bei einem Schritt 522 werden der Aufgabenzustand und der RRS desselben aus dem System entfernt. Ein Durchlaufen von Schleifen durch die Schritte 516522 ist implizit, wobei jede Gruppe von RRS innerhalb einer aktuellen Gruppe in Reihe betrachtet wird und die Gruppen in Reihe betrachtet werden. Eine Verarbeitung geht weiter, bis es keine verbleibenden Gruppen mehr gibt.

Der andere „Eintrittspunkt" zu den Prozessen, die durch den Ressourcenverwalter durchgeführt werden, tritt auf, wenn Ressourcen freigegeben oder zu dem System hinzugefügt werden. Lediglich zu diesen Zeiten wird eine Aufgabe eventuell bereit, um abzulaufen. Mit Bezug auf 5 wird ein Verfahren 600 eingeleitet, wenn Ressourcen freigegeben oder zu dem System hinzugefügt werden.

Bei Schritten 602606 werden Ressourcen zu dem System durch ein Bestimmen hinzugefügt, welche RSCS A, die den RS B für jede Ressource auswählen, die dem System nicht bereits bekannt ist, durch eine einfache Iteration über alle RSCS, wobei B zu dem Satz von verfügbaren RS von A hinzugefügt werden und A zu dem Satz von RSCS von B hinzugefügt werden, die denselben auswählen. Von diesem Schritt an geht eine Verarbeitung identisch zu derselben des Verfahrens 500 beginnend bei dem Schritt 512 weiter. Definitionsgemäß folgt eine freigegebene Ressource niemals dem Weg „kein derartiger Zustand" von dem Schritt 602 zu dem Schritt 604. Im Gegensatz dazu nehmen neue Ressourcen immer den Weg „kein derartiger Zustand".

Mehrere Merkmale und/oder Techniken zum Verbessern einer Leistungsfähigkeit und Skalierbarkeit des Systems sind eine erneute Darlegung wert. RSC werden implizit über mehrere Aufgaben gemeinschaftlich verwendet. Jede Aufgabe weist mehrere RR auf, die nicht gemeinschaftlich verwendet werden, und jedes RR weist mehrere benannte RSC auf, die alle simultan erfüllt sein müssen, damit eine Aufgabe abläuft. In der Praxis gibt es lediglich so viele gesonderte RSC in dem System, typischerweise viel weniger als die Anzahl von Aufgaben. Zweitens behält das System explizit für alle bekannten RSC Ci eine Gruppe von verfügbaren Ressourcen Sj bei, die Ci erfüllen, und für alle bekannten Ressourcen Ui eine Gruppe von RSC-Kriterien Cj, die Ui erfüllen. Drittens werden die RSCS über sehr lange Zeitperioden hinweg beibehalten, viel länger als die Ausführung irgendeiner spezifischen Aufgabe. Es wird erwartet, dass eine Aufgabe periodisch (z. B. in dem WQM) ausgeführt wird, so dass alle Ausführungen der gleichen Aufgabe die gleichen RSCS intern wiederverwenden können. Da sowohl die RSCS als auch die Ressourcen sehr langlebig sind, ist es eventuell lediglich notwendig, zu bestimmen, welche Ressourcen durch welche RSCS ausgewählt werden, wenn eine Ressource oder ein RSCS zu dem System hinzugefügt wird. Viertens verfolgt für jede Ressource das System, welche RSC die Ressource auswählt, für jedes RSC verfolgt das System, welche aktuell verfügbaren Ressourcen Sj dasselbe auswählt.

In Kombination reduzieren diese Techniken stark die Menge an Zeit, die erforderlich ist, um eine Aufgabe zu finden, die angesichts der verfügbaren Ressourcen ausgeführt werden kann. Es ist kein Suchen erforderlich: eine schnelle Überprüfung betrifft einfach ein Überprüfen jedes RR, um zu bestimmen, ob alle zugeordneten RSC desselben zumindest eine verfügbare Ressource aufweisen.

Einheitliche zufällige Auswahl von Ressourcengruppen

Eine betriebliche Betrachtung besteht darin, dass die RSC in einem gegebenen Satz Sätze von möglichen Ressourcen auswählen könnte, die nicht getrennt sind. Somit muss die zufällige Auswahl von Ressourcen über die möglichen Auswahlen ohne Duplikate einheitlich sein. Beispielsweise könnte RSC-1 mit verfügbaren Ressourcen {a, b} übereinstimmen und RSC-2 könnte mit verfügbaren Ressourcen {b, c} übereinstimmen. Dies ergibt drei mögliche Ressourcenauswahlen für den Satz: (1→a, 2→b), (1→a, 2→c) und (1→b, 2→c). Die Ressourcenauswahl (1→a, 2→b) ist nicht möglich, da Ressourcen ausschließlich zugeteilt werden (d, h. RSC-1 und RSC-2 können nicht beide simultan die Ressource b gewinnen). Der Ressourcengewinnungsansatz muss ein Auswählen einer der drei möglichen Auswahlen mit gleicher Wahrscheinlichkeit betreffen.

Irgendeine gegebene Aufgabe kann mehrere Sätze von RSC aufweisen, die derselben zugeordnet sind, jeder mit einer eigenen Priorität desselben. Dies ermöglicht, dass eine Aufgabe im Wesentlichen die Nachricht „ich würde X bevorzugen, aber würde mit auf Y einlassen, und falls nicht das, dann Z". Das System wendet Prioritäten über Aufgaben an, wobei die Sätze von RSC mit der höchsten Priorität einen bevorzugten Zugriff auf verfügbare Ressourcen aufweisen. Somit könnte beispielsweise die Priorisierung von mehreren Aufgaben in der folgenden Reihenfolge resultieren: Aufgabe A mit RSC X, dann Aufgabe B mit RSC Y, dann Aufgabe A mit RSC Z.

Dieser Punkt entspricht dem Schritt 516 in dem Prozess 500 und betrifft ein Bestimmen, wie eine Ressource für jedes von N RSC auszuwählen ist, derart, dass die gleiche Ressource nicht für mehr als ein RSC verwendet wird und dann die Auswahl zufällig vorgenommen wird, was bedeutet, dass jede gültige „Ressourcengruppe" einheitlich ausgewählt wird.

Es gibt zwei offensichtliche Wege, um eine derartige Auswahl durchzuführen. Erstens könnte eine Ressource zufällig für jedes RSC gewählt werden, wobei das Wählen von dem Anfang an wiederholt wird, bis es keine Duplikate gibt, aber betrifft ein Wiederauswählen aller Ressourcen. Andernfalls werden bestimmte Kombinationen in dem Ergebnis überrepräsentiert. Zweitens könnten alle gültigen (oder „legalen") Kombinationen von Ressourcen erzeugt werden und dann wird eine derartige Kombination ausgewählt.

Das Verfahren „Wählen und Wiederholen" weist einige Nachteile auf. Insbesondere gibt es eventuell keine legalen Kombinationen von Ressourcen, obwohl jedes RSC zumindest eine verfügbare Ressource aufweist. Der offensichtliche Fall besteht in einem Auswählen von {A}, aus {A}. Selbst falls es legale Kombinationen gibt, könnte die Anzahl derselben ein sehr kleiner Bruchteil der Gesamtanzahl von Kombinationen sein. Um dasselbe darzustellen, präsentiert ein Wählen von fünf eindeutig aus einem Satz {A, B, C, D, E} zwar 5! = 120 legale Kombinationen, aber insgesamt 5^5 = 3125 Kombinationen. Eine erhebliche Anzahl von zufälligen Versuchen könnte erforderlich sein, bevor eine legale Kombination gefunden wird. Als ein anderes Beispiel weist ein Wählen von sechs eindeutig aus {A} {A, B} {A, B, C} ... {A, B, C, D, E, F} eventuell lediglich eine gültige Kombination, aber insgesamt 6! = 720 Kombinationen auf.

Das Erzeugen aller gültiger Kombinationen weist ebenfalls Nachteile auf. Einige der Sätze von verfügbaren Ressourcen könnten Hunderte oder Tausende von Ressourcen enthalten und die Kombinatorische Explosion führt schnell zu sehr großen Anteilen von Kombinationen. Ein Ansatz, der sich bei kleinen Sätzen vollständig ausdehnt und nach großen Sätzen sondiert, könnte verwendet werden, aber lässt immer noch den großen „Graubereich" in der Mitte.

Eine praktische Lösung für dieses Problem erfordert ein Entwickeln von Informationen über die minimale Anzahl von legalen Kombinationen und die Gesamtanzahl von Kombinationen für eine Gruppe von Sätzen Si.

Die Gesamtanzahl von Kombinationen ist einfach das Produkt der Größen von Si.

Um eine minimale Anzahl von legalen Kombinationen zu ermitteln, werden die Sätze Si zuerst in einer nichtabsteigenden Reihenfolge nach Größe platziert, d. h. der kleinste Satz zuerst. Dann wird die minimale Anzahl von legalen Kombinationen als das Produkt (Größe(Si)-i) mit auf Null basierenden Indizes berechnet. Diese Formel kann wie folgt intuitiv verifiziert werden. Der schlimmste Fall für die Anzahl von legalen Kombinationen tritt auf, wenn jeder Satz Si ein Teilsatz von Si+1 ist. In diesem Fall kann eine jegliche erwünschte Auswahl aus dem nullten Satz, S0, vorgenommen werden. Aus dem nächsten Satz kann man für irgendeine gegebene Auswahl aus dem nullten Satz lediglich Größe(S1)-1 Einträge wählen: für jede Wahl aus dem nullten Satz wäre einer der Einträge in dem ersten Satz ein Duplikat. Gleichermaßen sind zwei der Einträge S2 möglicherweise Duplikate, etc.

Am Rande bemerkt beträgt die Anzahl von Permutationen, die n aus einem Abtastwert von N ziehen, N!/(N – n)!. In dem obigen Absatz würde dies n identischen Sätzen einer Größe N entsprechen. Wenn man erweitert, erhält man das Produkt (N – i) für i mit Werten von Null bis n – 1, was genau das obige Ergebnis ist.

Kurz gesagt besteht der verwendete Ansatz darin, eine Sammlung von legalen Kombinationen von Si zu bilden, aber lediglich bis zu etwa m ≤ n. Die Erweiterung dieser Sammlung wird Satz für Satz durchgeführt, bis die erwarteten Kosten einer zufälligen Abastung geringer als die Kosten eines weiteren Erweiterungsschritts werden.

Ein Verfahren 700 gemäß diesen Prinzipien ist in 6 dargestellt. Bei einem Schritt 702 schlägt der Ressourcenverwalter für jedes benannte RSC Tj in RR Ri die Gruppe von verfügbaren Ressourcen Sj nach, die Cj genügen. Dieser Satz kann möglicherweise leer sein. Bei einem Schritt 704 werden die verfügbaren Ressourcen Sj nach der Anzahl von verfügbaren Ressourcen in Sj geordnet, die geringste Anzahl von verfügbaren Ressourcen zuerst (d. h. um so die kleinsten Sätze zuerst zu betrachten).

Bei einem Schritt 706 wird eine Sammlung von Teilressourcenauswahlen Dk aufgebaut, die aus je einer verfügbaren Ressource aus S0...m-1 gebildet ist, derart, dass Dk keine Ressource mehr als einmal umfasst. Bei dem Schritt 706 umfasst die Auswahl einen einzigen leeren Eintrag, {<>}, der eine bisherige Möglichkeit darstellt, wobei Hinzufügungen folgen.

Iterative Schritte 708718 dienen dazu, zufällig eine Teilressourcenauswahl Dk und je eine verfügbare Ressource aus dem verbleibenden Sm...n-1 auszuwählen, derart, dass die Gruppe von Ressourcen keine Ressource mehr als einmal umfasst, um so eine endgültige Gruppe von Ressourcen zu erhalten. Bei dem Schritt 708 schlägt der Prozess fehl, wobei keine legalen Kombinationen zurückgegeben werden, falls bestimmt wird, dass die Sammlung leer ist, andernfalls geht der Prozess zu dem Schritt 710 über. Bei dem Schritt 710 wird eine Bestimmung vorgenommen, ob es weniger aufwendig ist, durch ein zufälliges Sondieren als durch ein Erweitern von D mögliche Übereinstimmungen zu finden. Die relativen Kosten eines Erweiterns von D zu D' werden durch ein Hinzufügen von Größe(D) × Größe(Si) (d. h. der Anzahl von Ressourcen in dem aktuellen Satz) in dem aktuellen Satz Si als dem Produkt berechnet. Die relativen Kosten eines Durchführens des Zufallsauswahlschritts werden als Produkt (Größe (Sj))i...n-1/Produkt (Größe (Sj)-j)i...n-1 berechnet. Die erwartete Anzahl von zufälligen Sonden, die eine legale Kombination finden, ist die Gesamtanzahl von Kombinationen geteilt durch die minimale Anzahl von legalen Kombinationen. Dies ist ein pessimistischer Schätzwert, da an diesem Punkt die tatsächliche Anzahl von legalen Kombinationen nicht bekannt ist. Die Kosten jeder zufälligen Sonde betragen grob 1 + die Anzahl von verbleibenden Sätzen (einen aus D wählen, dann einen aus jedem verbleibenden Si, wobei auf Duplikate hin geprüft wird).

Falls die erwarteten Sondierungskosten geringer als die Kosten eines Erweiterns von D sind, bewegt sich der Prozess zu iterativen Schritten 714718, wobei aus D Tupel iterativ ausgewählt werden und aus jedem verbleibenden Si Ressourcen Ri, bis der Prozess bei einem Schritt 720 mit einem nicht doppelten Satz D von legalen Kombinationen austritt.

Falls die erwarteten Kosten eines Erweiterns von D zu D' geringer als die Kosten eines zufälligen Sondierens sind, bewegt sich andernfalls der Prozess zu dem iterativen Schritt 712 zum Erweitern von D durch ein Addieren von Si durch ein Aufbauen mehrerer Teilressourcenauswahlen Dk aus Dj in D, wobei jede Dk aus Dj gebildet ist, die um eine einzige Ressource U1 aus Si erweitert ist, derart, dass Dj U1 nicht umfasst. Bei dem Schritt 712 werden für jedes Tupel T in D, bestehend aus <R0, R1, R2, ...>, neue Tupel T' <R0, R1, R2, ..., Ri> für jede Ressource Si erzeugt, die durch den aktuellen RSCS ausgewählt ist, derart, dass Si nicht bereits in T existiert.

In Situationen, in denen alle der Sätze klein sind (d. h. nicht viele verfügbare Ressourcen), wird ein Erzeugen von Kombinationen bevorzugt und kann der einzige verwendete Algorithmus sein. In Situationen, in denen alle der Sätze groß sind (viele verfügbare Ressourcen), kann ein zufälliges Sondieren der einzige verwendete Algorithmus sein. Es kann ein expliziter Kompromiss geschlossen werden, bei dem ein Algorithmus anfänglich (wenn die ersten paar Sätze klein sind) verwendet wird und der andere am Ende (die Verbleibenden sind groß), was in einer guten Leistungsfähigkeit resultiert.

Einheitliche zufällige Auswahl von Aufgaben

Eine einheitliche zufällige Auswahl von Aufgaben ist einfach. Die Lösung verfolgt tatsächlich RS anstelle von Aufgaben, da eine gegebene Aufgabe mehrere Erfordernisse aufweisen kann. Die RS sind nach Priorität gruppiert, so dass dieselben in einer absteigenden Prioritätsreihenfolge betrachtet werden können. Innerhalb jeder Gruppe werden die RS in eine zufällige Reihenfolge gemischt und dann einzeln verarbeitet. Dieser Ansatz garantiert, dass jeder RS verarbeitet wird und ferner dass die Reihenfolge innerhalb einer Prioritätsgruppe zufällig ist.

Datenstruktur für schnelles Hinzufügen/Entfernen/Umfassen und zufällige Auswahl

Die RSCS müssen jeweils die Sammlung derselben von übereinstimmenden verfügbaren RS verwalten. Diese Sammlung kann groß sein, wird häufig modifiziert und muss eine schnelle zufällige Auswahl unterstützen. Ein Java-Satz erfüllt alle der Kriterien, außer einer schnellen zufälligen Auswahl. Eine Java-Arrayliste unterstützt eine schnelle zufällige Auswahl, aber benötigt eine lineare Zeit für eine Modifikation.

Die verwendete Datenstruktur kombiniert eine Java-Map bzw. Java-Abbildung und eine Arrayliste. Die Arrayliste hält die Elemente in keiner speziellen Reihenfolge und unterstützt eine schnelle zufällige Auswahl. Die Abbildung bildet die Elemente zu den Indizes derselben in der Arrayliste ab.

Ein Hinzufügen eines Elements erfordert ein Überprüfen der Abbildung, um zu sehen, ob das Element bereits vorhanden ist. Falls es dasselbe nicht ist, wird das Element zu dem Ende der Liste hinzugefügt und der Eintrag Element→Index wird zu der Abbildung hinzugefügt.

Ein Entfernen eines Elements bewirkt ein Nachschlagen in der Abbildung, um den Index zu finden. Falls das Element vorhanden ist, wird das letzte Element in der Liste mit dem zu entfernenden Element vertauscht (in der Liste), wobei die Indizes in der Abbildung aktualisiert werden. Dann wird das Element sowohl aus der Abbildung als auch der Liste entfernt, eine O(1)-Operation.

Ein Prüfen, um zu sehen, ob das Element vorhanden ist, ist nur ein Abbildungsnachschlagen. Ein zufälliges Auswählen eines Elements wird in der Liste erzielt. Es wird eine Arrayliste verwendet, was einen O(1)-Zugriff auf irgendein Element liefert.

Beispielhaftes WQM-Ausführungsbeispiel

Mit Bezug auf ein bevorzugtes Ausführungsbeispiel, das in 7 gezeigt ist, kann ein Ressourcenverwalter bzw. eine Ressourcenverwaltungseinrichtung 40 gemäß der vorliegenden Erfindung bei dem WQM-System implementiert sein, von dem viele Aspekte auf http://we.home.agilent.com/cgi-bin/bvpub/agilent/Product/cp Product.jsp?OID=536882909&NAV ID=5368853 80.536882909.00&LANGUAGE CODE=eng&COUTRY CODE=ZZ&CT=PRODUCT &JPID=/comms/firehunter beschrieben sind, deren Inhalte hierin durch Bezugnahme aufgenommen sind. Ein WQM-System umfasst typischerweise einen zentralisierten Server 42 für Tausende von IMs und möglicherweise Hunderte von geografisch verteilten ATPs 44, 46, 48, die jeweils näherungsweise sechs eindeutig identifizierte Schnittstellenkarten aufweisen, wie beispielsweise Schnittstellenkarten wie die Schnittstellenkarten 50, 52 und 54. Der Ressourcenverwalter 40 gewinnt jede dieser Ressourcen, wie benötigt, um Aufgaben in einem Testprogrammablauf in einer effizienten Weise zu erzielen, die Fairness und hohe Nutzungsraten für gemeinschaftlich verwendete Ressourcen mit hoher Nachfrage sicherstellt.

Bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung ist jede der Aktivtestsonden 44, 46, 48 ein einzelner Agent in dem System und kann einen gewissen Abschnitt eines Ressourcenverwaltersoftwarecodes aufweisen, der auf denselben resident ist, aber andere Konfigurationen sind möglich und fallen in den Schutzbereich der vorliegenden Erfindung. Jeder Agent sollte eine Servlet-Funktionalität besitzen, obwohl eine derartige Funktionalität eventuell mit Bezug auf ein gegebenes Servlet gemäß einer speziellen Systemkonfiguration nicht verwendet wird.

Ein einziger Test „A zu B" innerhalb des WQM muss zwei Schnittstellen gewinnen, eine für den Punkt A und eine für den Punkt B; und zwei IMs für diese zwei Schnittstellen. In der Praxis sind die IMs und die Schnittstellen ziemlich breit spezifiziert, was bedeutet, dass die Auswahlkriterien, die dieselben auswählen, möglicherweise eine erhebliche Anzahl von Ressourcen auswählen könnten. Als ein spezifisches Beispiel gibt es typischerweise mehrere Schnittstellen bei einer einzigen physischen Position. Irgendwelche dieser Schnittstellen wären für den Test angemessen.

Der Test kann diese Ressourcen gewinnen durch: ein Erzeugen einer neuen Aufgabe; ein Erzeugen eines neuen Ressourcenerfordernisses mit einer nominalen Priorität; ein Hinzufügen von vier Kriterien zu diesem Ressourcenerfordernis: eines für jede Schnittstelle und eines für jede SIM; und ein Vorlegen der Aufgabe einem Ressourcenverwalter 40.

Jede Ressource der Mehrzahl von Ressourcen S in dem System ist durch zumindest ein benanntes Attribut gekennzeichnet, wie beispielsweise die Attribute 56, 58, 60, wobei irgendein gegebenes Attribut mehrere Werte aufweisen kann. Bei dem WQM sind IMs beispielsweise durch unterstützte Dienste, durch ein PLMN (Public Land Mobile Network = öffentliches Mobilfunknetz), durch einen Ländercode und möglicherweise andere Attribute gekennzeichnet und auswählbar. Schnittstellenkarten sind nach ATP-Position, ATP-Region, ATP-Land (die sukzessive weniger einschränkende Spezifizierer der physischen Position einer Schnittstellenkarte sind), durch einen unterstützten Dienst und möglicherweise andere Attribute ausgewählt. Ein zweiseitiger WQM-Test erfordert typischerweise eine Verwaltung mehrerer Ressourcen, einschließlich einer Testsondenschnittstellenkarte A 52 der Aktivtestsonde 44 und eines IM1 62 auf der „A"-Seite, die jeweils die gewünschten Charakteristika aufweisen, und ähnlicher Ressourcen auf der „B"-Seite, d. h. einer Testsondenschnittstellenkarte B 54 der Aktivtestsonde 46 und eines IM4 64. Die zwei IMs müssen gesonderte Identitätsmodule sein (die gesonderte tatsächliche Ressourcen darstellen) und die zwei Schnittstellenkarten müssen ebenfalls gesondert sein (z. B. nicht von und zu der gleichen Karte anrufend). Unter Verwendung der oben beschriebenen Verfahren gewinnt der Ressourcenverwalter 40 die Ressourcen effizient und gibt dieselben an die Aufgaben ab, die erforderlich sind, um das System zu testen.

Die vorliegende Erfindung kann erfolgreich über einem breiten Bereich von Drahtlosnetztypen und -Standards verwendet werden, einschließlich, aber nicht begrenzt auf wifi 802.11a, wifi 802.11b, wifi 802.11g, wimax, GSM/GPRS und CDMA, sowie andere Standards, die noch entworfen oder implementiert werden. Zudem ist die vorliegende Erfindung in einem Schutzbereich nicht auf drahtlose mehrseitige Testanwendungen begrenzt und umfasst innerhalb des Schutzbereichs derselben Wireline-Testanwendungen, wie beispielsweise Ethernet/LAN und Einwählnetze.

Obwohl die Erfindung mit Bezug auf verschiedene Ausführungsbeispiele beschrieben wurde, ist zu erkennen, dass diese Erfindung ferner zu einer breiten Vielfalt weiterer und anderer Ausführungsbeispiele innerhalb der Wesensart der Erfindung in der Lage ist.


Anspruch[de]
Softwareimplementiertes Verfahren (500) zur Ressourcenverwaltung in einem System, das eine Mehrzahl von Ressourcen S (16, 52, 54, 62, 64) zum Bedienen einer Mehrzahl von Aufgaben T umfasst und folgende Schritte aufweist:

auf eine Aufgabenvorlage und eine Freigabe von Ressourcen hin, als eine atomare Operation für jedes Ressourcenerfordernis Ri einer Mehrzahl von Ressourcenerfordernissen R (12), die jeweils einer Aufgabe Tk (10) zugeordnet sind, die eine Ausführung erfordert, in zufälliger Reihenfolge:

Wählen einer Gruppe von verfügbaren Ressourcen Sj, die Ressourcenerfordernissen Ri genügen, derart, dass keine Ressource Sj mehr als einmal ausgewählt wird;

falls eine Gruppe von verfügbaren Ressourcen Sj gewählt wurde:

Gewinnen der gewählten verfügbaren Ressourcen Sj, wobei die gewonnenen verfügbaren Ressourcen Sj nicht mehr verfügbar gemacht werden;

Übergeben der verfügbaren Ressourcen Sj an Tk; und

Entfernen aller Ressourcenerfordernisse Ri aus der Mehrzahl von Ressourcenerfordernissen R (12).
Verfahren (500) gemäß Anspruch 1, bei dem:

jede der Mehrzahl von Ressourcen S (16, 52, 54, 62, 64) durch eines oder mehrere benannte Attribute (18, 56, 58, 60) gekennzeichnet ist, die jeweils zumindest einen Wert aufweisen;

jedes der Mehrzahl von Ressourcenerfordernissen Ri durch eine Gruppe von zumindest einem benannten Ressourcenauswahlkriterium C (14) gekennzeichnet ist;

jedes der Ressourcenauswahlkriterien das ein Boolescher Ausdruck in einer primitiven Termform ausgedrückt ist, die aus der Gruppe ausgewählt ist, die besteht aus (a) ein benanntes Attribut (18, 56, 58, 60) einer Ressource umfasst einen speziellen Wert, (b) ein benanntes Attribut (18, 56, 58, 60) einer Ressource umfasst einen Wert, der mit einem regulären Ausdruck übereinstimmt, und (c) eine Ressource ist identisch mit einer speziellen Ressource mit Bezug auf alle benannten Attribute (18, 56, 58, 60).
Verfahren (500) gemäß Anspruch 1 oder 2, bei dem:

zumindest ein Ressourcenerfordernis Ri jeder Aufgabe Tk (10) zugeordnet ist, die eine Ausführung erfordert;

jedes Ressourcenerfordernis Ri eine gewisse Priorität Pj aufweist; und

die Ressourcen durch ein Betrachten der Mehrzahl von Ressourcenerfordernissen R (12) in priorisierten Gruppen mit der höchsten Priorität zuerst gewonnen werden, derart, dass alle Ressourcenerfordernisse Ri in jeder Gruppe die gleiche Priorität Pj aufweisen und die Ressourcenerfordernisse Ri in einer zufälligen Reihenfolge innerhalb jeder Gruppe betrachtet werden.
Verfahren (500) gemäß einem der Ansprüche 1 bis 3, bei dem die Gruppe von verfügbaren Ressourcen Sj, die den Ressourcenerfordernissen Ri genügen, mit gleicher Wahrscheinlichkeit aus der Menge aller derartigen Gruppen Sk, die Ri genügen, gewählt wird. Verfahren (500) gemäß einem der Ansprüche 2 bis 4, das ferner folgende Schritte aufweist:

Hinzufügen jedes Ressourcenauswahlkriteriums Ci, das jedem Ressourcenerfordernis Rj zugeordnet ist, das jeder vorgelegten Aufgabe Tk (10) zugeordnet ist, zu der Menge aller bekannten Ressourcenauswahlkriterien C;

explizites Beibehalten der Gruppe von verfügbaren Ressourcen Sj, die Ci genügen, für alle bekannten Ressourcenauswahlkriterien Ci; und

explizites Beibehalten, für alle bekannten Ressourcen Ui, der Gruppe von Ressourcenauswahlkriterien Cj, denen Ui genügt;

wobei irgendwelche zwei identischen Ressourcenauswahlkriterien als das gleiche Ressourcenauswahlkriterium betrachtet werden.
Verfahren (500) gemäß Anspruch 5, bei dem der Wählschritt ferner folgende Schritte aufweist:

Nachschlagen der Gruppe von verfügbaren Ressourcen Sj, die Cj genügen, für jedes benannte Ressourcenauswahlkriterium Cj in dem Ressourcenerfordernis Ri;

Ordnen von Sj nach einer Anzahl von verfügbaren Ressourcen in Sj mit der geringsten Anzahl von verfügbaren Ressourcen zuerst;

Aufbauen einer Gruppe von Teilressourcenauswahlen Dk, die aus je einer verfügbaren Ressource aus S0...m-1 gebildet ist, derart, dass Dk keine Ressource mehr als einmal umfasst; und

zufälliges Auswählen einer Teilressourcenauswahl Dk und je einer verfügbaren Ressource aus den verbleibenden Sm...n-1, derart, dass die Gruppe von Ressourcen keine Ressource mehr als einmal umfasst, wodurch eine endgültige Gruppe von Ressourcen erhalten wird.
Verfahren (500) gemäß Anspruch 6, bei dem der Aufbauschritt ferner folgende Schritte aufweist:

Aufbauen einer anfänglichen Gruppe von Teilressourcenauswahlen D, die aus der einzigen Teilressourcenauswahl D0 gebildet ist, die keine Ressourcen umfasst;

iteratives Betrachten jeder Si in einer Reihenfolge nach Größe:

falls D keine Teilressourcenauswahlen umfasst, Abbrechen des Wählschritts ohne mögliche Wahl;

Bestimmen der relativen Kosten eines Erweiterns von D auf D' durch ein Addieren von Si als Größe (D) × Größe (Si);

Bestimmen der relativen Kosten eines Durchführens des Zufallsauswahlschritts als Produkt (Größe (Sj))i...n-1/Produkt (Größe(Sj)-j)i...n-1;

falls ein Durchführen der zufälligen Auswahl weniger aufwendig als ein Erweitern von D ist, zurückgeben von D als das Ergebnis des Aufbauschritts, andernfalls Erweitern von D zu D', wobei Si addiert wird durch ein Aufbauen mehrerer Teilressourcenauswahlen Dk aus Dj in D, wobei jede Dk aus Dj gebildet ist, die um eine einzige Ressource U1 aus Di erweitert ist, derart, dass Dj U1 nicht umfasst.
System (40) zum Verwalten einer Mehrzahl von Ressourcen zum Bedienen einer Mehrzahl von Aufgaben, wobei das System folgende Merkmale aufweist:

eine Mehrzahl von Ressourcen S (16, 52, 54, 62, 64) zu Bedienen einer Mehrzahl von Aufgaben T, wobei jede der Mehrzahl von Ressourcen S (16, 52, 54, 62, 64) durch eines oder mehrere benannte Attribute (18, 56, 58, 60) gekennzeichnet ist, die jeweils zumindest einen Wert aufweisen;

eine Mehrzahl von Ressourcenerfordernissen R (12), wobei jede Ressource Ri der Mehrzahl von Ressourcenerfordernissen einer Aufgabe Tk (10) zugeordnet ist, die eine Ausführung erfordert, und durch eine Gruppe von zumindest einem benannten Ressourcenauswahlkriterium C (14) gekennzeichnet ist;

einen Ressourcenverwalter, um auf eine Aufgabenvorlage und eine Freigabe von Ressourcen hin als eine atomare Operation für jedes Ressourcenerfordernis Ri einer Mehrzahl von Ressourcenerfordernissen R (12), die jeweils einer Aufgabe Tk (10) zugeordnet sind, die eine Ausführung erfordert, in zufälliger Reihenfolge folgende Schritte durchzuführen:

Wählen einer Gruppe von verfügbaren Ressourcen Sj, die Ressourcenerfordernissen Ri genügen, derart, dass keine Ressource Sj mehr als einmal ausgewählt wird;

falls eine Gruppe von verfügbaren Ressourcen Sj gewählt wurde:

Gewinnen der gewählten verfügbaren Ressourcen Sj, wobei die gewonnenen verfügbaren Ressourcen Sj nicht mehr verfügbar gemacht werden;

Übergeben der verfügbaren Ressourcen Sj an Tk; und

Entfernen aller Ressourcenerfordernisse Ri aus der Mehrzahl von Ressourcenerfordernissen R (12).
System (40) gemäß Anspruch 8, bei dem jedes der Ressourcenauswahlkriterien das ein Boolescher Ausdruck in einer primitiven Termform ausgedrückt ist, die aus der Gruppe ausgewählt ist, die besteht aus (a) ein benanntes Attribut (18, 56, 58, 60) einer Ressource umfasst einen speziellen Wert, (b) ein benanntes Attribut (18, 56, 58, 60) einer Ressource umfasst einen Wert, der mit einem regulären Ausdruck übereinstimmt, und (c) eine Ressource ist identisch mit einer speziellen Ressource mit Bezug auf alle benannten Attribute (18, 56, 58, 60). System (40) gemäß Anspruch 8 oder 9, bei dem:

zumindest ein Ressourcenerfordernis Ri jeder Aufgabe Tk (10) zugeordnet ist, die eine Ausführung erfordert;

jedes Ressourcenerfordernis Ri eine gewisse Priorität Pj aufweist; und

die Ressourcen durch ein Betrachten der Mehrzahl von Ressourcenerfordernissen R (12) in priorisierten Gruppen mit der höchsten Priorität zuerst gewonnen werden, derart, dass alle Ressourcenerfordernisse Ri in jeder Gruppe die gleiche Priorität Pj aufweisen und die Ressourcenerfordernisse Ri in einer zufälligen Reihenfolge innerhalb jeder Gruppe betrachtet werden.
System (40) gemäß einem der Ansprüche 8 bis 10, bei dem der Ressourcenverwalter die Gruppe von verfügbaren Ressourcen Sj, die den Ressourcenerfordernissen Ri genügen, mit gleicher Wahrscheinlichkeit aus der Menge aller derartigen Gruppen Sk auswählt, die Ri genügen. System (40) gemäß einem der Ansprüche 9 bis 11, bei dem der Ressourcenverwalter ferner angepasst ist zum:

Hinzufügen jedes Ressourcenauswahlkriteriums Ci, das jedem Ressourcenerfordernis Rj zugeordnet ist, das jeder vorgelegten Aufgabe Tk (10) zugeordnet ist, zu der Menge aller bekannten Ressourcenauswahlkriterien C;

explizites Beibehalten der Gruppe von verfügbaren Ressourcen Sj, die Ci genügen, für alle bekannten Ressourcenauswahlkriterien Ci; und

explizites Beibehalten, für alle bekannten Ressourcen Ui, der Gruppe von Ressourcenauswahlkriterien Cj, denen Ui genügt;

wobei irgendwelche zwei identischen Ressourcenauswahlkriterien als das gleiche Ressourcenauswahlkriterium betrachtet werden.
System (40) gemäß Anspruch 12, bei dem der Ressourcenverwalter ferner angepasst ist zum:

Nachschlagen der Gruppe von verfügbaren Ressourcen Sj, die Cj genügen, für jedes benannte Ressourcenauswahlkriterium Cj in dem Ressourcenerfordernis Ri;

Ordnen von Sj nach einer Anzahl von verfügbaren Ressourcen in Sj mit der geringsten Anzahl von verfügbaren Ressourcen zuerst;

Aufbauen einer Gruppe von Teilressourcenauswahlen Dk, die aus je einer verfügbaren Ressource aus S0...m-1 gebildet ist, derart, dass Dk keine Ressource mehr als einmal umfasst; und

zufälliges Auswählen einer Teilressourcenauswahl Dk und je einer verfügbaren Ressource aus den verbleibenden Sm...n-1, derart, dass die Gruppe von Ressourcen keine Ressource mehr als einmal umfasst, wodurch eine endgültige Gruppe von Ressourcen erhalten wird.
System (40) gemäß Anspruch 13, bei dem der Ressourcenverwalter ferner angepasst ist zum:

Aufbauen einer anfänglichen Gruppe von Teilressourcenauswahlen D, die aus der einzigen Teilressourcenauswahl D0 gebildet ist, die keine Ressourcen umfasst;

iteratives Betrachten jeder Si in einer Reihenfolge nach Größe:

falls D keine Teilressourcenauswahlen umfasst, Abbrechen des Wählschritts ohne mögliche Wahl;

Bestimmen der relativen Kosten eines Erweiterns von D auf D' durch ein Addieren von Si als Größe (D) × Größe (Si);

Bestimmen der relativen Kosten eines Durchführens des Zufallsauswahlschritts als Produkt (Größe (Sj))i...n-i/Produkt (Größe (Sj)-j)i...n-1;

falls ein Durchführen der zufälligen Auswahl weniger aufwendig als ein Erweitern von D ist, zurückgeben von D als das Ergebnis des Aufbauschritts, andernfalls Erweitern von D zu D', wobei Si addiert wird durch ein Aufbauen mehrerer Teilressourcenauswahlen Dk aus Dj in D, wobei jede Dk aus Dj gebildet ist, die um eine einzige Ressource U1 aus Si erweitert ist, derart, dass Dj U1 nicht umfasst.
Prozessorlesbares Computerprogrammprodukt, das an einer oder mehreren programmierbaren Speicherungsvorrichtungen codiert ist, wobei das Computerprogrammprodukt durch einen oder mehrere Prozessoren ausführbar ist, um Verfahrensschritte zum Verwalten einer Mehrzahl von Ressourcen S eines Systems zum Bedienen einer Mehrzahl von Aufgaben T durchzuführen, die Anweisungen aufweisen zum:

auf eine Aufgabenvorlage und eine Freigabe von Ressourcen hin, als eine atomare Operation für jedes Ressourcenerfordernis Ri einer Mehrzahl von Ressourcenerfordernissen R (12), die jeweils einer Aufgabe Tk (10) zugeordnet sind, die eine Ausführung erfordert, in zufälliger Reihenfolge:

Wählen einer Gruppe von verfügbaren Ressourcen Sj, die Ressourcenerfordernissen Ri genügen, derart, dass keine Ressource Sj mehr als einmal ausgewählt wird;

falls eine Gruppe von verfügbaren Ressourcen Sj gewählt wurde:

Gewinnen der gewählten verfügbaren Ressourcen Sj, wobei die gewonnenen verfügbaren Ressourcen Sj nicht mehr verfügbar gemacht werden;

Übergeben der verfügbaren Ressourcen Sj an Tk; und

Entfernen aller Ressourcenerfordernisse Ri aus der Mehrzahl von Ressourcenerfordernissen R (12).
Computerprogrammprodukt gemäß Anspruch 15, bei dem:

jede der Mehrzahl von Ressourcen S (16, 52, 54, 62, 64) durch eines oder mehrere benannte Attribute (18, 56, 58, 60) gekennzeichnet ist, die jeweils zumindest einen Wert aufweisen;

jedes der Mehrzahl von Ressourcenerfordernissen Ri durch eine Gruppe von zumindest einem benannten Ressourcenauswahlkriterium C (14) gekennzeichnet ist;

jedes der Ressourcenauswahlkriterien das ein Boolescher Ausdruck in einer primitiven Termform ausgedrückt ist, die aus der Gruppe ausgewählt ist, die besteht aus (a) ein benanntes Attribut (18, 56, 58, 60) einer Ressource umfasst einen speziellen Wert, (b) ein benanntes Attribut (18, 56, 58, 60) einer Ressource umfasst einen Wert, der mit einem regulären Ausdruck übereinstimmt, und (c) eine Ressource ist identisch mit einer speziellen Ressource mit Bezug auf alle benannten Attribute (18, 56, 58, 60).
Computerprogrammprodukt gemäß Anspruch 15 oder 16, bei dem:

zumindest ein Ressourcenerfordernis Ri jeder Aufgabe Tk (10) zugeordnet ist, die eine Ausführung erfordert;

jedes Ressourcenerfordernis Ri eine gewisse Priorität Pj aufweist; und

die Ressourcen durch ein Betrachten der Mehrzahl von Ressourcenerfordernissen R (12) in priorisierten Gruppen mit der höchsten Priorität zuerst gewonnen werden, derart, dass alle Ressourcenerfordernisse Ri in jeder Gruppe die gleiche Priorität Pj aufweisen und die Ressourcenerfordernisse Ri in einer zufälligen Reihenfolge innerhalb jeder Gruppe betrachtet werden.
Computerprogrammprodukt gemäß einem der Ansprüche 15 bis 17, das ferner Anweisungen zum Wählen der Gruppe von verfügbaren Ressourcen Sj, die den Ressourcenerfordernissen Ri genügen, mit gleicher Wahrscheinlichkeit aus der Menge aller derartiger Gruppen Sk, die Ri genügen, aufweist. Computerprogrammprodukt gemäß einem der Ansprüche 16 bis 18, das ferner Anweisungen aufweist zum:

Hinzufügen jedes Ressourcenauswahlkriteriums Ci, das jedem Ressourcenerfordernis Rj zugeordnet ist, das jeder vorgelegten Aufgabe Tk (10) zugeordnet ist, zu der Menge aller bekannten Ressourcenauswahlkriterien C;

explizites Beibehalten der Gruppe von verfügbaren Ressourcen Sj, die Ci genügen, für alle bekannten Ressourcenauswahlkriterien Ci; und

explizites Beibehalten, für alle bekannten Ressourcen Ui, der Gruppe von Ressourcenauswahlkriterien Cj, denen Ui genügt;

wobei irgendwelche zwei identischen Ressourcenauswahlkriterien als das gleiche Ressourcenauswahlkriterium betrachtet werden.
Computerprogrammprodukt, gemäß Anspruch 19, das ferner Anweisungen aufweist zum:

Nachschlagen der Gruppe von verfügbaren Ressourcen Sj, die Cj genügen, für jedes benannte Ressourcenauswahlkriterium Cj in dem Ressourcenerfordernis Ri;

Ordnen von Sj nach einer Anzahl von verfügbaren Ressourcen in Sj mit der geringsten Anzahl von verfügbaren Ressourcen zuerst;

Aufbauen einer Gruppe von Teilressourcenauswahlen Dk, die aus je einer verfügbaren Ressource aus S0...m-1 gebildet ist, derart, dass Dk keine Ressource mehr als einmal umfasst; und

zufälliges Auswählen einer Teilressourcenauswahl Dk und je einer verfügbaren Ressource aus den verbleibenden Sm...n-1, derart, dass die Gruppe von Ressourcen keine Ressource mehr als einmal umfasst, wodurch eine endgültige Gruppe von Ressourcen erhalten wird.
Computerprogrammprodukt gemäß Anspruch 20, das ferner Anweisungen aufweist zum:

Aufbauen einer anfänglichen Gruppe von Teilressourcenauswahlen D, die aus der einzigen Teilressourcenauswahl D0 gebildet ist, die keine Ressourcen umfasst;

iteratives Betrachten jeder Si in einer Reihenfolge nach Größe:

falls D keine Teilressourcenauswahlen umfasst, Abbrechen des Wählschritts ohne mögliche Wahl;

Bestimmen der relativen Kosten eines Erweiterns von D auf D' durch ein Addieren von Si als Größe (D) × Größe (Si);

Bestimmen der relativen Kosten eines Durchführens des Zufallsauswahlschritts als Produkt (Größe (Sj))i...n-1/Produkt (Größe (Sj)-j)i...n-1;

falls ein Durchführen der zufälligen Auswahl weniger aufwendig als ein Erweitern von D ist, zurückgeben von D als das Ergebnis des Aufbauschritts, andernfalls Erweitern von D zu D', wobei Si addiert wird durch ein Aufbauen mehrerer Teilressourcenauswahlen Dk aus Dj in D, wobei jede Dk aus Dj gebildet ist, die um eine einzige Ressource U1 aus Si erweitert ist, derart, dass Dj U1 nicht umfasst.






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

Patent Zeichnungen (PDF)

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