Il tempo di esecuzione di ogni task \u00e8 noto.<\/li>\n<\/ol>\nMetriche del pianificatore<\/h3>\n \n Oltre ad alcune assunzioni sul carico, \u00e8 necessario anche uno strumento di confronto per le varie 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
Come esempio utilizzeremo la metrica chiamata tempo di turnaround<\/b> (turnaround time). Il tempo di turnaround di un task viene definito come la differenza tra il tempo di completamento del task e il tempo di arrivo del task nel sistema.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Poich\u00e9 abbiamo assunto che tutti i task siano arrivati nello stesso momento, allora Ta=0 e quindi Tt=Tc. Questo valore cambier\u00e0 naturalmente quando modificheremo le assunzioni sopra menzionate.<\/p>\n
Un'altra metrica \u00e8 fairness<\/b> (equit\u00e0). Prestazioni e equit\u00e0 sono spesso caratteristiche contrapposte nella pianificazione. Ad esempio, un pianificatore pu\u00f2 ottimizzare le prestazioni, ma a scapito del tempo di attesa di altri task, riducendo cos\u00ec l'equit\u00e0.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n L'algoritmo pi\u00f9 semplice che possiamo implementare si chiama FIFO o first come (in), first served (out)<\/b>. Questo algoritmo ha diversi vantaggi: \u00e8 molto semplice da implementare e si adatta a tutte le nostre ipotesi, svolgendo il compito piuttosto bene.<\/p>\n
Consideriamo un semplice esempio. Supponiamo che 3 task siano stati assegnati contemporaneamente. Ma supponiamo che il task A sia arrivato un po' prima degli altri, quindi nella lista di esecuzione apparir\u00e0 prima degli altri, proprio come B rispetto a V. Supponiamo che ognuno di essi venga eseguito per 10 secondi. Quale sar\u00e0 quindi il tempo medio di esecuzione di questi task?<\/p>\n
Come si pu\u00f2 vedere, tempi di esecuzione differenti dei task influenzano negativamente la produttivit\u00e0 dell'algoritmo FIFO. Supponiamo che il task A venga eseguito per 100 secondi, mentre B e V continuano a richiedere 10 secondi ciascuno.<\/p>\n
effetto convoglio<\/b>, quando alcuni consumatori a breve termine di una risorsa si trovano in coda dietro a un consumatore pesante. \u00c8 simile a una fila al supermercato, quando davanti a te c'\u00e8 un cliente con un carrello pieno. La soluzione migliore al problema \u00e8 cercare di cambiare cassa o rilassarsi e respirare profondamente.<\/p>\nShortest Job First<\/h3>\n
\n C'\u00e8 un modo per risolvere situazioni simili con processi pesanti? Certo. Un altro tipo di pianificazione si chiamaShortest Job First<\/b> (SJF). Il suo algoritmo \u00e8 anch'esso piuttosto primitivo \u2014 come suggerisce il nome, le prime a essere eseguite saranno le task pi\u00f9 brevi, una dopo l'altra.<\/p>\n
50 invece di 110<\/b>, il che \u00e8 praticamente il doppio migliore.<\/p>\n
Pertanto, dato il presupposto che tutti i compiti arrivino contemporaneamente, l'algoritmo SJF sembra essere l'algoritmo pi\u00f9 ottimale. Tuttavia, le nostre assunzioni non sembrano ancora realistiche. Questa volta cambiamo l'assunzione 2 e consideriamo che i compiti possano arrivare in qualsiasi momento, e non tutti insieme. A quali problemi potrebbe portare questo?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Per migliorare la situazione, ignoreremo l'assunzione 3 che afferma che il programma viene avviato e funziona fino al completamento. Inoltre, avremo bisogno del supporto dell'hardware e, come potreste immaginare, utilizzeremo un timer<\/b> per interrompere il compito in esecuzione e eseguire il cambio di contesto<\/b>. In questo modo, il pianificatore pu\u00f2 intervenire al momento dell'arrivo dei compiti B e C \u2014 interrompere l'esecuzione del compito A e avviare l'elaborazione dei compiti B e C e, al termine di questi, riprendere l'esecuzione del processo A. Questo tipo di 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 compiti e che questi compiti utilizzano solo la CPU, lo STCF sar\u00e0 la soluzione migliore. In passato, questi algoritmi funzionavano e piuttosto bene. Tuttavia, ora l'utente trascorre la maggior parte del tempo al terminale e si aspetta un'interazione interattiva produttiva. Cos\u00ec \u00e8 nata una nuova metrica \u2014 tempo di risposta<\/b> (response).<\/p>\n
Il tempo di risposta viene calcolato come segue:<\/p>\n
Tresponse = Tfirstrun \u2212 Tarrival<\/u><\/p>\n
Pertanto, per l'esempio precedente, il tempo di risposta sar\u00e0 il seguente: A=0, B=0, C=10 (abg=3,33).<\/p>\n
E si scopre che l'algoritmo STCF non \u00e8 poi cos\u00ec buono in situazioni in cui 3 compiti arrivano contemporaneamente: deve aspettare che i compiti pi\u00f9 piccoli siano completamente completati. Cos\u00ec, l'algoritmo \u00e8 buono per la metrica del tempo di turnaround, ma scarso per la metrica dell'interattivit\u00e0. Immaginate di essere seduti a un terminale e di dover aspettare pi\u00f9 di 10 secondi per digitare simboli in un editor, perch\u00e9 un'altra attivit\u00e0 occupa il processore. Non \u00e8 affatto piacevole.<\/p>\n
Round Robin<\/h3>\n \n Per risolvere questo problema \u00e8 stato sviluppato l'algoritmo Round Robin<\/b> (RR). L'idea principale \u00e8 piuttosto semplice: invece di eseguire i compiti fino al completamento, eseguiremo un compito per un intervallo di tempo (chiamato quantum di tempo) e poi passeremo a un altro compito in coda. L'algoritmo ripete il suo lavoro fino a quando tutti i compiti non sono completati. Di conseguenza, il tempo di esecuzione del programma deve essere multiplo del tempo dopo il quale il timer interromper\u00e0 il processo. Ad esempio, se il timer interrompe il processo ogni x=10ms, 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 lavorare per 5 secondi. L'algoritmo SJF eseguir\u00e0 ciascun compito fino alla fine, prima di avviare un altro. Al contrario, l'algoritmo RR con una finestra di esecuzione di 1s eseguir\u00e0 i 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 di tempo sia un parametro molto importante per il RR; minore \u00e8, maggiore sar\u00e0 il tempo di risposta. Tuttavia, non si pu\u00f2 renderla eccessivamente piccola, poich\u00e9 il tempo di commutazione del contesto giocher\u00e0 anch'esso un ruolo nelle prestazioni complessive. Pertanto, la selezione del tempo di finestra di esecuzione \u00e8 determinata dall'architetto del sistema operativo e dipende dai compiti che si prevede di eseguire. La commutazione del contesto non \u00e8 l'unica operazione di servizio che richiede tempo; un programma in esecuzione deve gestire anche altre cose, come vari cache, e a ogni commutazione \u00e8 necessario salvare e ripristinare questo ambiente, il che pu\u00f2 richiedere anche molto tempo.<\/p>\n
Il RR \u00e8 un ottimo pianificatore se parliamo solo della metrica del tempo di risposta. Ma come si comporter\u00e0 la metrica del tempo di turnaround delle attivit\u00e0 con questo algoritmo? Consideriamo l'esempio sopra, in cui i tempi di esecuzione A, B, C = 5s e arrivano allo stesso tempo. Il compito A terminer\u00e0 alle 13, B alle 14, C alle 15s e il tempo medio di turnaround sar\u00e0 di 14s. Pertanto, il RR \u00e8 l\u2019algoritmo peggiore per la metrica del turnaround.<\/p>\n
Parlando pi\u00f9 in generale, qualsiasi algoritmo di tipo RR \u00e8 equo; divide il tempo di CPU equamente tra tutti i processi. E cos\u00ec, queste metriche sono costantemente in conflitto tra loro.<\/p>\n
Cos\u00ec, abbiamo diversi algoritmi opposti e rimangono anche alcune ipotesi: che il tempo del compito sia noto e che il compito utilizzi solo la CPU.<\/p>\n
Mescolamento con I\/O<\/h3>\n \n Iniziamo rimuovendo l'ipotesi 4, che il processo utilizzi solo la CPU; naturalmente non \u00e8 cos\u00ec e i processi possono accedere anche ad altre attrezzature.<\/p>\n
Nel momento in cui un processo richiede un'operazione di input\/output, il processo passa allo stato di blocked, in attesa di completare l'I\/O. Se l'I\/O \u00e8 diretto a un disco rigido, tale operazione pu\u00f2 occupare fino a diversi ms o pi\u00f9 a lungo, e la CPU in quel momento sar\u00e0 inattiva. Durante questo tempo, il pianificatore pu\u00f2 assegnare la CPU a un altro processo. La successiva decisione che dovr\u00e0 prendere il pianificatore \u00e8 quando il processo terminer\u00e0 il suo I\/O. Quando accade, si verifica un'interruzione e il sistema operativo passer\u00e0 il processo che ha richiesto l'I\/O allo stato di ready.<\/p>\n
Consideriamo un esempio con diverse attivit\u00e0. Ognuna di esse ha bisogno di 50 ms di tempo di CPU. Tuttavia, la prima richieder\u00e0 ogni 10 ms l'accesso all'I\/O (che verr\u00e0 eseguito anche ogni 10 ms). Mentre il processo B utilizza semplicemente 50 ms di CPU senza I\/O.<\/p>\n
L'oracolo non c'\u00e8 pi\u00f9.<\/h3>\n \n Ora cerchiamo di liberarci dell'idea che il tempo di esecuzione di un'attivit\u00e0 sia noto. Questa \u00e8, in generale, l'ipotesi peggiore e pi\u00f9 poco realistica dell'intero elenco. Infatti, nelle normali OS medie, il sistema operativo sa generalmente molto poco sul tempo di esecuzione dei task; come possiamo quindi costruire un piano senza sapere quanto tempo impiegher\u00e0 un'attivit\u00e0? 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 task e considerato due famiglie di pianificatori. La prima avvia l'attivit\u00e0 pi\u00f9 breve all'inizio, migliorando in tal modo il tempo di turnaround, mentre la seconda interrompe equamente tutte le attivit\u00e0, migliorando il tempo di risposta. Entrambi gli algoritmi hanno dei difetti dove gli altri algoritmi eccellono. Abbiamo anche visto come l'uso parallelo di CPU e I\/O possa migliorare le prestazioni, ma non abbiamo ancora risolto il problema della visione del sistema operativo. Alla prossima lezione, esamineremo un pianificatore che guarda al passato recente e cerca di prevedere il futuro. 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