Pianificazione delle prenotazioni (non ristorante) con python

Question

Sto scrivendo un'applicazione python che utilizza OpenStack per fornire agli studenti l'accesso a un numero limitato di macchine virtuali.

Gli studenti possono effettuare prenotazioni, ora o in futuro.

Devo limitare il numero di macchine virtuali pianificate in qualsiasi momento a X, consentendo comunque agli studenti di prenotare vms se sono disponibili slot/prenotazioni.

Gli oggetti di prenotazione hanno il seguente aspetto (sqlalchemy). Vorrei sapere l'ora di inizio e la durata della prenotazione richiesta, a quel punto ho bisogno di passare attraverso le prenotazioni esistenti e vedere se ci sono troppe prenotazioni nel periodo di tempo richiesto. I campi * _job sono i nomi dei lavori di APScheduler.

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) 

Qualsiasi indicazione su dove cercare esempi di algoritmi di pianificazione o qualcosa del genere? Non ho ancora chiaro cosa cercare ...

Grazie.

Answer 1

È necessario cercare Scheduler basati su griglia. Normalmente gli scheduler non conoscono il vero tempo di esecuzione (o il tempo di utilizzo delle risorse) e vengono utilizzate complesse euristiche per indovinare quanto tempo impiegherà un problema (vedere tale euristica su un pianificatore di griglia su: PDF download Describing Scheduling on Grid basis). Un approccio più semplice con una griglia di base per rappresentare il carico di lavoro nel tempo soddisferà molto probabilmente le vostre esigenze. Python non ha librerie di oggetti di griglia fantastiche che io conosca (ne ho già implementate alcune in C++ e Python e non sono troppo difficili). Dovresti considerare il pacchetto numpy per la più semplice interpretazione di oggetti multidimensionali, che possono emulare o implementare le griglie abbastanza facilmente.

Msw ha menzionato l'algoritmo di Dijkstra's Banker che è una forma di pianificazione del lavoro, tuttavia il problema riguarda lo stato futuro più dello stato corrente e è possibile prevedere con precisione (conoscere il valore reale di) i tempi di attività. Quindi un T (timesteps) per N (numero di risorse - potrebbe essere solo 1) per M (riserva di risorse massime) griglia che si compila come posti di lavoro sono registrati sarebbe sufficiente. Determinare se un particolare lavoro può essere programmato in un particolare periodo di applicazione è un O (task_length * M) controlla su una sottosezione della griglia (start, stop) x (required_resources) x (1, M) per uno slot vuoto.

Trovare un luogo adeguato per un particolare lavoro (scegliere l'ora di inizio) è un compito più difficile e sarebbe raggiunto con un algoritmo di Dijkstra modificato, o da qualsiasi programmatore standard (il commento di msw è più utile per questo compito che per un controllo della capacità temporale). Si noti che gran parte del contenuto dello scheduler online è specifico per la pianificazione dei processi del sistema operativo, che si preoccupa maggiormente del tipo di operazione (I/O o meno) e delle penalità per impiegare più tempo del previsto rispetto all'uso di risorse astratte. Pertanto, le ricerche su google per gli scheduler ti forniranno spesso implementazioni dello scheduler Linux piuttosto che tecniche per dati arbitrari. Prova a cercare Scheduler di lavoro più brevi, che sono spesso più semplici e meno dipendenti dalle attività del sistema operativo quando vengono spiegati.