Il tempo di esecuzione di ogni compito \u00e8 noto.<\/li>\n<\/ol>\nMetriche del Pianificatore<\/h3>\n \n Oltre ad alcune assunzioni sul carico, \u00e8 necessario avere anche uno strumento per confrontare diverse politiche di pianificazione: le metriche del pianificatore. Una metrica \u00e8 semplicemente una misura di qualcosa. Ci sono diverse metriche che possono essere utilizzate per confrontare i pianificatori.<\/p>\n
Per esempio, utilizzeremo una metrica chiamata tempo di turnaround<\/b> (turnaround time). Il tempo di turnaround di un compito \u00e8 definito come la differenza tra il tempo di completamento del compito e il tempo di arrivo del compito nel sistema.<\/p>\n
Tempo di completamento = Tempo di arrivo<\/u><\/p>\n
Poich\u00e9 abbiamo ipotizzato che tutte le attivit\u00e0 siano arrivate contemporaneamente, Ta = 0 e dunque Tt = Tc. Questo valore cambier\u00e0 naturalmente quando modificheremo le ipotesi sopra elencate.<\/p>\n
Un'altra metrica \u00e8 equit\u00e0<\/b> (equit\u00e0, giustizia). Le performance e l\u2019equit\u00e0 sono spesso caratteristiche contrastanti nella pianificazione. Ad esempio, un pianificatore pu\u00f2 ottimizzare le performance, ma a scapito dell'attesa dell'avvio di altre attivit\u00e0, riducendo cos\u00ec l'equit\u00e0.<\/p>\nPRIMO ARRIVATO, PRIMO SERVITO (FIFO)<\/h3>\n
\n L'algoritmo pi\u00f9 semplice che possiamo implementare si chiama FIFO o primo arrivato (in), primo servito (fuori)<\/b>. Questo algoritmo ha diversi vantaggi: \u00e8 molto semplice da implementare e si adatta a tutte le nostre ipotesi, svolgendo il lavoro piuttosto bene.<\/p>\n
Consideriamo un semplice esempio. Supponiamo che 3 compiti siano stati assegnati contemporaneamente. Ma supponiamo che il compito A sia arrivato leggermente prima degli altri, quindi sar\u00e0 prima nella lista di esecuzione, proprio come B rispetto a C. Supponiamo che ciascuno di essi richieda 10 secondi per essere completato. Quale sar\u00e0 quindi il tempo medio di esecuzione di questi compiti?<\/p>\n
Si rivela che tempi di esecuzione diversi per i compiti hanno un impatto estremamente negativo sulla produttivit\u00e0 dell'algoritmo FIFO. Supponiamo che il compito A richieda 100 secondi, mentre B e C continuano a richiedere 10 secondi ciascuno.<\/p>\n
effetto convoglio<\/b>, quando alcuni utenti temporanei di una risorsa si trovano in fila dietro a un utente pesante. \u00c8 simile a una coda in un supermercato, in cui davanti a te c'\u00e8 un cliente con un carrello pieno. La soluzione migliore a questo problema \u00e8 cercare di cambiare cassa o rilassarsi e respirare profondamente.<\/p>\nShortest Job First<\/h3>\n
\n \u00c8 possibile risolvere situazioni simili con processi pesanti? Certamente. Un altro tipo di pianificazione \u00e8 chiamatoShortest Job First<\/b> (SJF). Il suo algoritmo \u00e8 piuttosto semplice: come suggerisce il nome, verranno eseguiti per primi i compiti pi\u00f9 brevi uno dopo l'altro.<\/p>\n
50 invece di 110<\/b>, che \u00e8 praticamente il doppio migliore.<\/p>\n
In questo modo, data l'assunzione che tutti i compiti arrivino contemporaneamente, l'algoritmo SJF sembra essere il pi\u00f9 ottimale. Tuttavia, le nostre assunzioni non sembrano ancora realistiche. Questa volta modificheremo l'assunzione 2 e presumeremo che i compiti possano arrivare in qualsiasi momento, e non tutti insieme. A quali problemi potrebbe portare ci\u00f2?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Per migliorare la situazione, elimineremo l'assunzione 3 che prevede che il programma sia avviato e funzionante fino al completamento. Inoltre, avremo bisogno di supporto hardware e, come potreste immaginare, utilizzeremo un timer<\/b> per interrompere il compito in esecuzione e cambiare i contesti<\/b>. In questo modo, il pianificatore pu\u00f2 adottare delle misure non appena arrivano i task B e C \u2014 interrompere l'esecuzione del task A e iniziare a elaborare i task B e C, per poi continuare l'esecuzione del task A una volta completati. Tale pianificatore \u00e8 chiamato STCF<\/b>o Preemptive Job First<\/b>.<\/p>\n
Metrica Tempo di risposta (Response Time)<\/h3>\n \n Pertanto, se conosciamo i tempi di esecuzione dei task e sappiamo che questi task utilizzano solo la CPU, STCF sar\u00e0 la soluzione migliore. In tempi passati, questi algoritmi funzionavano piuttosto bene. Tuttavia, ora l'utente trascorre la maggior parte del suo tempo al terminale e si aspetta un'interazione interattiva performante. Cos\u00ec \u00e8 nata una nuova metrica \u2014 tempo di risposta<\/b> (response).<\/p>\n
Il tempo di risposta si calcola nel seguente modo:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Cos\u00ec, per l'esempio precedente, il tempo di risposta sar\u00e0: A=0, B=0, C=10 (abg=3,33).<\/p>\n
E si scopre che l'algoritmo STCF non \u00e8 cos\u00ec efficace quando 3 compiti arrivano contemporaneamente: dovr\u00e0 attendere che i compiti pi\u00f9 piccoli siano completati. Pertanto, l'algoritmo \u00e8 buono per la metrica del tempo di rotazione, ma scarso per la metrica dell'interattivit\u00e0. Immaginate di essere al terminale e di dover aspettare pi\u00f9 di 10 secondi per digitare caratteri in un editor, perch\u00e9 un'altra attivit\u00e0 occupa la CPU. Non \u00e8 affatto piacevole.<\/p>\n
Round Robin<\/h3>\n \n Per risolvere questo problema \u00e8 stato sviluppato un algoritmo Round Robin<\/b> (RR). L'idea principale \u00e8 piuttosto semplice: invece di avviare i compiti fino al loro completamento, avvieremo il compito per un certo intervallo di tempo (chiamato quantum di tempo) e poi passeremo a un altro compito in coda. L'algoritmo ripete il suo lavoro finch\u00e9 tutti i compiti non sono completati. Nel frattempo, il tempo di esecuzione del programma deve essere un multiplo del tempo dopo il quale il timer interromper\u00e0 il processo. Ad esempio, se il timer interrompe il processo ogni x=10ms, allora la dimensione della finestra di esecuzione del processo deve essere un multiplo di 10 e pu\u00f2 essere 10, 20 o x*10.<\/p>\n
Consideriamo un esempio: i compiti A, B e C arrivano contemporaneamente nel sistema e ciascuno di essi desidera funzionare per 5 secondi. L'algoritmo SJF eseguir\u00e0 ciascun compito fino alla fine prima di avviarne un altro. In contrasto, l'algoritmo RR con finestra di avvio=1s si occuper\u00e0 dei compiti nel seguente modo (fig. 4.3):<\/p>\n
Il tempo medio di risposta per l'algoritmo RR (0+1+2)\/3=1, mentre per SJF (0+5+10)\/3=5.<\/p>\n
\u00c8 logico supporre che la finestra temporale sia un parametro molto importante per il RR; pi\u00f9 \u00e8 piccola, pi\u00f9 veloce sar\u00e0 il tempo di risposta. Tuttavia, non pu\u00f2 essere troppo ridotta, poich\u00e9 il tempo di switching del contesto gioca anch'esso un ruolo nelle prestazioni generali. Pertanto, la scelta del tempo della finestra di esecuzione \u00e8 determinata dall'architetto del sistema operativo e dipende dalle attivit\u00e0 che si intendono eseguire. Il switching del contesto non \u00e8 l'unica operazione di servizio che richiede tempo; un programma in esecuzione gestisce anche vari cache, e ad ogni switching \u00e8 necessario salvare e ripristinare questo ambiente, il che pu\u00f2 richiedere molto tempo.<\/p>\n
Il RR \u00e8 un ottimo pianificatore, se consideriamo solo la metrica del tempo di risposta. Ma come si comporter\u00e0 la metrica del tempo di turnaround con questo algoritmo? Consideriamo l'esempio sopra, dove i tempi di esecuzione per A, B e C sono di 5 secondi e arrivano contemporaneamente. Il compito A si concluder\u00e0 a 13 secondi, B a 14 secondi, e C a 15 secondi, con una media di turnaround di 14 secondi. Cos\u00ec, il RR \u00e8 il peggior algoritmo per la metrica di turnaround.<\/p>\n
In altre parole, qualsiasi algoritmo del tipo RR \u00e8 equo, poich\u00e9 suddivide il tempo di utilizzo della CPU equamente tra tutti i processi. In questo modo, queste metriche confliggono costantemente tra loro.<\/p>\n
Pertanto, abbiamo diversi algoritmi contrapposti e rimangono alcune ipotesi \u2014 che il tempo di esecuzione sia noto e che il processo utilizzi esclusivamente la CPU.<\/p>\n
Integrazione con I\/O<\/h3>\n \n Innanzitutto, eliminiamo l'ipotesi 4, secondo cui il processo utilizza solo la CPU; naturalmente, non \u00e8 cos\u00ec e i processi possono accedere anche ad altre risorse hardware.<\/p>\n
Quando un processo richiede un'operazione di input-output, il processo passa allo stato di bloccato, in attesa che l'I\/O venga completato. Se l'I\/O \u00e8 diretto a un disco rigido, tale operazione pu\u00f2 richiedere anche diversi millisecondi o pi\u00f9 a lungo, e in quel momento la CPU rester\u00e0 inattiva. Durante questo tempo, il pianificatore pu\u00f2 assegnare la CPU a un altro processo. La prossima decisione che dovr\u00e0 prendere il pianificatore \u00e8 quando il processo completer\u00e0 il suo I\/O. Quando ci\u00f2 accade, si verifica un'interruzione e il sistema operativo ripristina il processo che ha richiesto l'I\/O nello stato di pronto.<\/p>\n
Consideriamo un esempio composto da pi\u00f9 compiti. Ognuno di essi necessita di 50 ms di tempo di CPU. Tuttavia, il primo acceder\u00e0 all'I\/O ogni 10 ms (che sar\u00e0 anch'esso eseguito ogni 10 ms). Il processo B, invece, utilizza semplicemente 50 ms di CPU senza I\/O.<\/p>\n
L'oracolo non c'\u00e8 pi\u00f9.<\/h3>\n \n Adesso proviamo a liberarci dell'ipotesi che il tempo di esecuzione di un compito sia noto. In generale, questa \u00e8 l'ipotesi pi\u00f9 pessima e irreale dell'intero elenco. Infatti, nei sistemi operativi mediamente comuni, il sistema operativo stesso conosce molto poco sul tempo di esecuzione dei compiti; come possiamo quindi costruire un pianificatore senza sapere quanto tempo impiegher\u00e0 un compito? Forse potremmo utilizzare alcuni principi del RR per risolvere questo problema?<\/p>\n
Risultato<\/h3>\n \n Abbiamo esaminato le idee di base della pianificazione dei compiti e considerato due famiglie di pianificatori. Il primo avvia il compito pi\u00f9 breve per primo, migliorando cos\u00ec il tempo di turnaround; il secondo, invece, suddivide equamente il tempo tra tutti i compiti, migliorando il tempo di risposta. Entrali algoritmi sono inefficaci nelle situazioni in cui le prestazioni degli altri algoritmi eccellono. Abbiamo anche esaminato come l'uso parallelo della CPU e dell'I\/O possa migliorare le prestazioni, ma non abbiamo risolto il problema della chiarezza da parte del sistema operativo. Nella prossima lezione, esamineremo un pianificatore che guarda al passato recente e cerca di prevedere il futuro, e si chiama multi-level feedback queue.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t