È possibile un OS multitasking preemptive sul DCPU-16 senza interruzioni?

Question

Sto esaminando vari progetti di sistemi operativi nella speranza di scrivere un semplice sistema operativo multitasking per il DCPU-16. Tuttavia, tutto ciò che ho letto sull'implementazione del multitasking preemptive è incentrato sugli interrupt. Sembra che nell'era dell'hardware e del software a 16 bit, il multitasking cooperativo fosse più comune, ma che richiede che tutti i programmi siano scritti pensando al multitasking.

Esiste un modo per implementare il multitasking preventivo su un'architettura senza interruzioni? Tutto ciò a cui riesco a pensare è un interprete che cambierà dinamicamente i compiti, ma ciò avrebbe un enorme impatto sulle prestazioni (forse dell'ordine di 10-20x + se dovesse analizzare ogni operazione e non lasciare che tutto funzioni in modo nativo, io sono immaginando).

Answer 1

Il multitasking di prelazione viene normalmente implementato mediante l'esecuzione di routine di interruzione in caso di modifiche dello stato/eventi interessanti a uno scheduler, che decide quali attività sospendere e quali nuove attività avviare/continuare in base alla priorità. Tuttavia, altri eventi interessanti possono verificarsi quando un'attività in esecuzione effettua una chiamata a una routine del sistema operativo, che può avere lo stesso effetto.

Ma tutto ciò che conta è che qualche evento venga annotato da qualche parte e lo scheduler decida chi eseguire. In questo modo è possibile effettuare tutte queste segnalazioni/pianificazioni degli eventi solo sulle chiamate del sistema operativo.

È possibile aggiungere chiamate all'unità di pianificazione in punti "convenienti" in vari codici dell'applicazione di attività per far sì che il sistema passi più spesso. Che si tratti solo di cambiare o di utilizzare alcune informazioni di background come il tempo trascorso dall'ultima chiamata è un dettaglio dello scheduler.

Il tuo sistema non sarà così reattivo come uno guidato da interrupt, ma hai già rinunciato scegliendo la CPU che hai fatto.

Answer 2

Penso che la vostra valutazione sia corretta. Il multitasking preventivo si verifica se lo scheduler può interrompere (in senso non inflesso, dizionario) un'attività in esecuzione e passare a un'altra autonomamente. Quindi ci deve essere una sorta di attore che richiede all'operatore di pianificazione di agire. Se non ci sono dispositivi di interruzione (nel senso tecnico incurvato) allora c'è poco che puoi fare in generale.

Tuttavia, anziché passare all'interprete completo, un'idea che si verifica è solo la riprogrammazione dinamica del codice di programma fornito. Quindi, prima di entrare in un processo, lo schedulatore conosce lo stato completo del processo, compreso il valore del contatore del programma in cui entrerà. Può quindi eseguire la scansione in avanti da lì, sostituendo, ad esempio, il ventesimo codice di istruzione o il successivo codice di istruzione di salto che non si trova immediatamente sul contatore del programma con un salto indietro nello scheduler. Quando il processo ritorna, lo scheduler reinserisce l'istruzione originale. Se si tratta di un salto (condizionale o meno), effettua anche il salto in modo appropriato.

Ovviamente, questo schema funziona solo se il codice del programma non si modifica in modo dinamico. E in questo caso puoi pre-elaborarlo in modo da sapere in anticipo dove i salti sono senza una ricerca lineare. Potresti tecnicamente consentire codice di auto-modifica ben scritto se fosse disposto a nominare tutti gli indirizzi che potrebbero essere modificati, permettendoti di evitare sicuramente quelli nelle modifiche dinamiche del tuo schedulatore.

Si finirebbe per eseguire un interprete, ma solo per i salti.

Answer 3

In realtà, sì. Il metodo più efficace consiste semplicemente nel patch dei tempi di esecuzione nel caricatore. Le cose del kernel/demone possono avere patch personalizzate per una migliore reattività. Ancora meglio, se si ha accesso a tutti i sorgenti, è possibile applicare patch al compilatore.

La patch può essere costituita da un programmatore distribuito di ordinamento.Ogni programma può essere aggiornato per avere un timer a latenza molto bassa; al caricamento, imposterà il timer, e ad ogni ritorno dallo scheduler, lo ripristinerà. Un metodo semplice permetterebbe di codice per fare semplicemente un

if (timer - start_timer) yield to scheduler; 

che non cede troppo grande un calo di prestazioni. Il problema principale è trovare dei buoni punti per farli scoppiare. Tra ogni chiamata di funzione è un inizio, e rilevare i loop e inserirli è primitivo ma efficace se hai davvero bisogno di anticipare in modo reattivo.

Non è perfetto, ma funzionerà.

Il problema principale è assicurarsi che il ritorno del timer sia a bassa latenza; in questo modo è solo un confronto e un ramo. Inoltre, gestendo le eccezioni - errori nel codice che causano, per esempio, cicli infiniti - in qualche modo. È possibile utilizzare tecnicamente un timer watchdog hardware abbastanza semplice e asserire un reset sulla CPU senza cancellare la RAM; una routine in-RAM sarebbe il punto in cui i punti di RESET vector, che ispezionerebbero e riposizionerebbero lo stack alla chiamata del programma (bloccando così il programma ma preservando tutto il resto). È un po 'come una bruta-forza se-tutto-altro-fallisce il crash del programma. Oppure potresti POTENZIALMENTE cambiarlo in multi-task in questo modo, RESET come interruzione, ma è molto più difficile.

Quindi ... sì. È possibile ma complicato; usando tecniche di compilatori JIT e di traduttori dinamici (gli emulatori li usano).

Questa è una spiegazione un po 'confusa, lo so, ma sono molto stanco. Se non è abbastanza chiaro, posso tornare a chiarirlo domani.

A proposito, affermare il ripristino su un mid-program della CPU sembra pazzesco, ma è una tecnica consolidata e consolidata. Le prime versioni di Windows lo facevano persino per attivare la modalità di compatibilità, penso 386, correttamente, perché non c'era modo di tornare a 32 bit dalla modalità a 16 bit. Anche altri processori e sistemi operativi hanno funzionato.

EDIT: Quindi ho fatto qualche ricerca su cosa sia la DCPU, haha. Non è una vera CPU. Non ho idea se tu possa affermare il reset nell'emulatore di Notch, vorrei chiederglielo. Tecnica pratica, cioè.

Answer 4

un altro modo è quello di mantenere a piccoli compiti sulla base di una coda di eventi (come applicazioni GUI correnti)

questo è anche cooperative, ma ha l'effetto di non aver bisogno di OS chiamate che appena torna dal compito e poi si passare al prossimo compito

se è quindi necessario continuare un'attività che deve passare la "funzione" accanto e un puntatore per i dati necessari alla coda compito