Planen von Reservierungen (kein Restaurant) mit Python

Question

Ich schreibe eine Python-Anwendung, die OpenStack verwendet, um Schülern Zugang zu einer begrenzten Anzahl von virtuellen Maschinen zu ermöglichen.

Studenten können jetzt oder in Zukunft Reservierungen vornehmen.

Ich muss die Anzahl der virtuellen Maschinen, die zu jeder Zeit geplant sind, auf X begrenzen, während die Schüler immer noch VMs reservieren können, wenn Slots/Reservierungen verfügbar sind.

Reservierungsobjekte sehen wie folgt aus (sqlalchemy). Ich würde die Startzeit und die Dauer der Reservierung wissen, an welcher Stelle ich bestehende Reservierungen durchgehen muss und sehen muss, ob es in dem angeforderten Zeitraum zu viele Reservierungen gibt. Die * _job-Felder sind die Namen von APScheduler-Jobs.

class Reservation(Entity): 
    student = ManyToOne('Student', required=True) 
    class_id = ManyToOne('Class', required=True) 
    image = ManyToOne('Image', required=True) 
    # openstack image id filled in once the instance is started 
    instance_id = Field(UnicodeText) 

    # apscheduler jobs 
    stop_instance_job = Field(UnicodeText) 
    start_instance_job = Field(UnicodeText) 
    warn_reservation_ending_job = Field(UnicodeText) 
    check_instance_job = Field(UnicodeText) 

Gibt es irgendwelche Hinweise darauf, wo man nach Beispielen für Zeitplanalgorithmen oder so etwas suchen sollte? Ich bin nicht einmal klar, was zu suchen ist ...

Danke.

Answer 1

Sie sollten Grid-basierte Scheduler nachschlagen. Normalerweise kennen Scheduler nicht die tatsächliche Ausführungszeit (oder Zeit der Ressourcennutzung) und komplizierte Heuristiken werden verwendet, um zu erraten, wie lange ein Problem dauert (siehe solche Heuristiken in einem Grid-Scheduler unter: PDF download Describing Scheduling on Grid basis). Ein einfacherer Ansatz mit einem Grundraster zur Darstellung der Arbeitslast im Laufe der Zeit wird höchstwahrscheinlich Ihren Anforderungen entsprechen. Python hat keine genialen Grid-Objekt-Bibliotheken, die ich kenne (ich habe vorher ein paar in C++ und Python implementiert und sie sind nicht zu schwer). Sie sollten das numpy-Paket für die leichtere Interpretation von mehrdimensionalen Objekten betrachten, die Raster einfach emulieren oder implementieren können.

Msw erwähnt Dijkstra's Banker's Algorithmus, der eine Form der Job-Scheduling ist - aber Ihr Problem kümmert sich um den zukünftigen Zustand mehr als den aktuellen Zustand und Sie können genau sagen (wissen den wahren Wert von) Task-Zeiten. Somit würde ein T (Zeitschritte) mal N (Anzahl der Ressourcen - könnte nur 1 sein) durch M Gitter (maximale Ressourcenreservierung), das Sie ausfüllen, wenn Jobs registriert sind, ausreichen. Das Bestimmen, ob ein bestimmter Job in einem bestimmten Zeitfenster eingeplant werden kann, ist ein O (task_length * M) prüft auf einen Unterabschnitt des Gitters (start, stop) x (required_resources) x (1, M) für einen leeren Slot.

Die Suche nach einem geeigneten Ort für einen bestimmten Job (die Startzeit auswählen) ist eine schwierigere Aufgabe und würde durch einen modifizierten Dijkstra-Algorithmus oder einen beliebigen Standard-Scheduler erreicht (der Kommentar von msw ist für diese Aufgabe hilfreicher als für einen Überprüfung der Zeitfensterfähigkeit). Beachten Sie, dass ein großer Teil des Online-Scheduler-Inhalts spezifisch für die OS-Prozessplanung ist, die sich mehr um die Art der Operation (E/A oder nicht) und Strafen für die längere Nutzung als über die abstrakte Ressourcenverwendung kümmert. Google-Suchvorgänge nach Schedulern geben Ihnen häufig Linux-Scheduler-Implementierungen und keine Techniken für beliebige Daten. Versuchen Sie, die kürzesten Job-Scheduler zu finden, die oft einfacher und weniger auf Betriebssystem-Aufgaben angewiesen sind, wenn sie erklärt werden.