Pianificatori di attività

Question

Ho avuto una discussione interessante con alcuni colleghi sulle migliori strategie di pianificazione per le attività in tempo reale, ma non tutti avevano una buona comprensione delle strategie di pianificazione comuni o utili.

Per la tua risposta, scegli una strategia ed esaminala in dettaglio, invece di fornire piccole informazioni su diverse strategie.Se hai qualcosa da aggiungere alla descrizione di qualcun altro ed è breve, aggiungi un commento anziché una nuova risposta (se è lunga o utile, o semplicemente una descrizione molto migliore, utilizza una risposta)

• Qual è la strategia: descrivi il caso generale (supponi che le persone sappiano cos'è una coda di attività, semafori, blocchi e altri fondamenti del sistema operativo al di fuori dello scheduler stesso)
• Per cosa è ottimizzata questa strategia (latenza delle attività, efficienza, tempo reale, jitter, condivisione delle risorse, ecc.)
• È in tempo reale o può essere reso in tempo reale

Strategie attuali:

• Prelazione basata sulla priorità
• Orologio più lento con potenza minima

-Adamo

Answer 1

Come descritto in un articolo intitolato Pianificazione delle attività in tempo reale per sistemi embedded attenti al consumo energetico, Swaminathan e Chakrabarty descrivono le sfide della pianificazione delle attività in tempo reale in dispositivi a basso consumo (incorporati) con più velocità del processore e profili di consumo energetico disponibili.L'algoritmo di pianificazione delineato (e dimostrato essere peggiore solo dell'1% circa rispetto a una soluzione ottimale nei test) ha un modo interessante di pianificare le attività che chiamano euristica LEDF.

Dal giornale:

La prima scadenza a bassa energia prima euristica, o semplicemente LEDF, è un'estensione del noto algoritmo di prima scadenza (EDF).Il funzionamento del LEDF è il seguente:LEDF mantiene un elenco di tutte le attività rilasciate, chiamata "Ready List".Quando vengono rilasciate attività, viene scelto l'attività con la scadenza più vicina per essere eseguita.Viene eseguito un controllo per vedere se la scadenza delle attività può essere soddisfatta eseguendolo alla tensione inferiore (velocità).Se la scadenza può essere rispettata, LEDF assegna la tensione inferiore all'attività e l'attività inizia l'esecuzione.Durante l'esecuzione dell'attività, altre attività possono inserire nel sistema.Si presume che questi compiti vengano inseriti automaticamente nella "lista pronta".LEDF seleziona nuovamente l'attività con la scadenza più vicina da eseguire.Finché ci sono compiti in attesa di essere eseguiti, LEDF non mantiene il processore inattivo.Questo processo viene ripetuto fino a quando non sono state programmate tutte le attività.

E in pseudo-codice:

Repeat forever {
    if tasks are waiting to be scheduled {
        Sort deadlines in ascending order
        Schedule task with earliest deadline
        Check if deadline can be met at lower speed (voltage)
        If deadline can be met,
            schedule task to execute at lower voltage (speed)
        If deadline cannot be met,
            check if deadline can be met at higher speed (voltage)
        If deadline can be met,
            schedule task to execute at higher voltage (speed)
        If deadline cannot be met,
            task cannot be scheduled: run the exception handler!
    }
}

Sembra che la pianificazione in tempo reale sia un problema interessante e in evoluzione man mano che i dispositivi piccoli e a basso consumo diventano sempre più onnipresenti.Penso che questa sia un'area in cui vedremo molte ulteriori ricerche e non vedo l'ora di restare al passo!

Answer 2

Uno schema comune di pianificazione in tempo reale consiste nell'utilizzare il multitasking preventivo basato sulle priorità.
A ciascuna attività viene assegnato un livello di priorità diverso.
L'attività con la priorità più alta nella coda pronta sarà l'attività in esecuzione.Funzionerà finché non rinuncerà alla CPU (ad es.ritardi, attese su un semaforo, ecc...) o un'attività con priorità più alta diventa pronta per essere eseguita.

Il vantaggio di questo schema è che il progettista del sistema ha il pieno controllo su quali attività verranno eseguite e con quale priorità.Anche l'algoritmo di pianificazione è semplice e dovrebbe essere deterministico.

D'altra parte, le attività a bassa priorità potrebbero essere affamate di CPU.Ciò indicherebbe un problema di progettazione.