Pianificadore (informàtica)

Artìculu in LSC

Su pianificadore (fintzas manigiadore de protzessos, connotu comente a scheduler puru, dae s'inglesu to schedule literalmente "pònnere in lista"), in informàtica, est unu cumponente de unu sistema operativu, unu programma chi ativat un'algoritmu de pianificatzione chi òrdinat in su tempus s'esecutzione de unu grupu de rechestas de atzessu a su protzessore dae unu protzessu de esecutare), donende prioridade a is chi respetant unos cantos paràmetros segundu una tzerta polìtica, a manera de perfetzionare s'atzessu a cussa risursa e permìtere de aici s'acumprimentu de su servìtziu/istrutzione o protzessu bòlidu.

S'atentu postu in carchi paràmetru masaprestu chi subra àteros diferèntziat sa polìtica de pianificatzione a s'àmbitu de su manìgiu de sos protzessos ponende in òpera coas de prioridades: a esèmpiu su pianificadore podet esecutare sas rechertas in base a s'òrdine issoro de arribu (FIFO), opuru donare pretzedèntzia a sas chi impinnant pro prus pagu tempus sa risursa (SNPF); podent esìstere polìticas chi si basant subra printzìpios istatìsticos o subra sa preditzione pro individuare un'ordinamentu de rechertas chi s'acùrtziet su prus possìbile a su mègius.

A parusu s'obietivu de sa pianificatzione est cuddu de:

• massimizare su throughput, overas sa produtividade de totu su sistema, minimende su tempus chi sa risursa no est impreada;
• chircare s'ordinamentu de rechestas chi mìnimat su raportu tra tempus de servìtziu (su tempus chi una recherta impreat pro èssere elaborada) e tempus de "turnaround" (su tempus chi passat tra s'istante in ue sa recherta est generada e cudda in ue sa recherta est satisfata);
• evitare fenòmenos malos comente a sa starvation overas "s'isetu eternu" de carchi recherta;
• donare a s'impitadore sa pertzetzione chi su sistema elàboret sas rechertas a manera contemporànea.

Esistent in realidade medas recuisidos chi podent èssere cunsiderados, chi dipendent fintzas dae su problema dislindadu chi su pianificadore depet risòlvere.

Pianificatzione a curtzu

De sòlitu, elaboradores cun unu protzessore non podent esecutare prus che unu programma isceti in su pròpiu tempus, e fintzas in is elaboradores cun prus protzessores ddoe sunt agiumai semper prus protzessos prontos che protzessores pro ddos elaborare, tando pro pòdere esecutare prus protzessos est netzessàriu impreare unu pianificadore. A su programma chi faghet custu traballu calicunu autore ddi narat dispatcher.

A sa minuda, su pianificadore si òcupat de fàghere esecutare unu protzessu interrumpende·nde in manera temporale unu àteru, realizende gai su chi est mutidu "càmbiu de cuntestu" a s'internu de su tziclu de su protzessore. Esistent vàrios algoritmos de pianificatzione chi permitint de seberare in sa manera prus efitziente possìbile cale protzessu depet sighire: a esèmpiu su nùcleu Linux in sa versione 2.4 tenet unu pianificadore O(n), mentras de sa versione 2.6 tenet un'algoritmu de cumplessidade O(1), est a nàrrere capassu de determinare in unu tempus costante cale protzessu depat èssere esecutadu, in manera indipendente dae su nùmeru de protzessos isetende.

Pianificatzione de s'unidade tzentrale de càrculu

Sa pianificatzione est un'operatzione de importu mannu pro su funtzionamentu curretu e efitziente de su carculadore. Difatis non permitit isceti de esecutare prus programmas a manera cuncurrente, ma cunsentit fintzas de megiorare s'impreu de su protzessore. A esèmpiu, cando est netzessàriu esecutare un'operatzione de I/E, su protzessore non podet sighire s'elaboratzione de su protzessu atualmente in esecutzione finas s'acabbu de s'operatzione. Sende chi sas operatziones de I/E sunt meda prus lentas de su protzessore, diat èssere un'isprecu de risursas si su protzessore abarraret blocadu finas cando acabbant. Pro evitare custu sas operatziones de I/E benint manigiadas dae su Sistema operativu chi, in s'ìnteri, assignat s'impreu de su protzessore a un'àteru protzessu. Custu massimizat s'impreu de sas risursas de su sistema.

Est de importu sa distintzione tra pianificatzione cun deretu de prelatzione (preemptive scheduling) e pianificatzione sena prelatzione o cooperativa (nonpreemptive scheduling o cooperative scheduling). In su primu casu su pianificadore podet leare su protzessore a su protzessu fintzas cando custu potet sighire in sa pròpia esecutzione. In su segundu casu, imbetzes, su pianificadore depet abetare chi su protzessu lasset lìberu su protzessore de èssere torradu a assignare.

Esistent vàrios algoritmos de pianificatzione chi tenent contu de vàrios bisòngios e chi podent èssere prus indicados in carchi cuntestu chi no in àteros. Su sèberu de s'algoritmu de impreare dipendet de chimbe critèrios printzipales:

• Impreu de su protzessore: sa CPU depet èssere ativa su prus possìbile, duncas depent èssere reduidos a su mìnimu sos tempos mortos.
• Throughput: su nùmeru de protzessos cumpletados in una determinada cantidade de tempus.
• Tempus de cumprimentu: su tempus chi passat tra s'incumentzu de unu protzessu e su cumprimentu de s'esecutzione sua.
• Tempus de isetu: su tempus chi unu protzessu prontu pro s'esecutzione abarrat in isetu de sa CPU.
• Tempus de risposta: su tempus chi colat tra s'incumentzu de su protzessu e s'arribu de sa prima risposta.

Pro analizare sos algoritmos chi ant a èssere posca presentados at a èssere impreadu su critèriu de su tempus de isetu mèdiu de sos protzessos cunsiderados.

Obietivos de sa pianificatzione

Un'algoritmu de pianificatzione tenet is obietivos sighentes:

• Ecuidade: protzessos de su matessi tipu depent tènnere tratamentos prètzisos
• Bilantzu: totu sas alas de su sistema depent èssere isfrutadas

Annotamala bisòngiat fàghere unu distinghimentu tra sos sistemas batch e sos sistemas interativos. In sos primos su throughput depet èssere massimizadu e su tempus de cumprimentu depet èssere redùsidu a su mìnimu. In sos sistemas interativos, su tempus de risposta depet èssere su mìnimu possìbile pro dare s'idea de continuidade a s'impitadore e sa proportzionalidade depet èssere respetada, est a nàrrere su tempus de risposta depet èssere proportzionale a sa cumplessidade de s'atzione.

Modello Màchina Sìngula (mollu de Karg e Thompson)

Passos de s'algoritmu:

1. Isseberare duos traballos a manera casuale.
2. Isseberare unu traballu nou e proare a lu dispònnere in sa secuèntzia currente
3. Pro ogni positzione proada contare su tempus de assètiu complessivu
4. Allogare su traballu in sa positzione chi garantit su tempus prus bàsciu de assètiu
5. Si ddoe at traballos de allogare, bae a su passu 2. Si no, fine.

FCFS

S'algoritmu FCFS (First Come First Served) est unu tipu de algoritmu FIFO: esecutat sos protzessos in su matessi òrdine chi arribant a su sistema. Duncas, su primu protzessu chi su protzessore esecutat, est su primu chi ddu recheret. Is imbenientes benint serbidos cando custu at acabadu s'esecutzione sua, e aici acontesset pro totu sos àteros in coa. Custu tipu de algoritmu est simpre meda de pònnere in òpera ma a parusu est pagu efitziente, a su mancu cunsiderende su tempus mèdiu de isetu.

Difatis, pighemus comente a esèmpiu s'arribu in s'òrdine de sos protzessos sighentes cun sa durada espressada in millisecundos:

• p1: 10ms
• p2: 4ms
• p3: 2ms

Ant a èssere esecutados in su matessi òrdine: p1 → p2 → p3

Su protzessu p1 no abetat nudda, pro ite intrat deretu in esecutzione. Su protzessu p2 abetat 10 millisecundos, e p3 14. Su tempus mèdiu de isetu tando est (0+10+14)/3=8 millisecundos. Ddoe at tando un'efetu acumpangiamentu, caraterizadu dae su fatu chi prus protzessos curtzos abetant s'agabbu de un'ùnicu protzessu prus grae. Unu resurtadu meda diferente de su chi si podet otènnere, in manera teòrica, de s'algoritmu primorosu SJF (Shortest Job First) aguale a (0+2+6)/3=8/3 millisecundos isceti.

Nointames si sos protzessos sunt longos e tenent pagu rechertas de I/E, su FCFS abarrat su mègius algoritmu.

RR

S'algoritmu de pianificatzione RR (round-robin) est un'algoritmu cun prelatzione chi esecutat sos protzessos in s'òrdine de arribu, comente a su FCFS, ma esecutat sa prelatzione de su protzessu in esecutzione, ponende·ddu a sa fine de sa coa de sos protzessos in isetu, cando s'esecutzione durat prus de sa "cantidade de tempus" istabilida, e faghende sighire s'esecutzione a su protzessu imbeniente chi isetat.

A esèmpiu in s'ipòtesi chi ddoe siant sos protzessos sighentes in coa cun relativa durada in millisecundos, e sa cantidade de tempus istabilida de 20 ms:

• p1: 30ms
• p2: 15ms
• p3: 60ms
• p4: 45ms

Ant a èssere esecutados in s'òrdine sighente:

• p1 (interrùmpidu a pustis de 20 ms, nd'abarrant 10)
• p2 (acabat sa pròpia esecutzione pro ite durat prus pagu de 20 ms)
• p3 (interrùmpidu a pustis de 20 ms, nd'abarrant 40)
• p4 (interrùmpidu a pustis de 20 ms, nd'abarrant 25)
• p1 (acabat sa pròpia esecutzione pro ite netzessitaiat mancu de 20 ms)
• p3 (interrùmpidu a pustis de 20 ms, nd'abarrant 20)
• p4 (interrùmpidu a pustis de 20 ms, nd'abarrant 5)
• p3 (acabat sa pròpia esecutzione pro ite netzessitaiat 20 ms cabales)
• p4 (acabat sa pròpia esecutzione)

Sas prestatziones de custu algoritmu sunt duncas influentzadas dae su tempus mèdiu de isetu, mancari chi cunsentat a totus sos protzessos de otènnere su controllu de su protzessore e èvitat tando su problema de s'isetu indefinidu (starvation).

Est annotamala de tènnere in cunsideru s'impatu de totu is càmbios de cuntestu fatos. Est netzessàriu tando carculare bene sa durada primorosa de sa cantidade de tempus pro fàghere a manera chi su pesu de is càmbios de cuntestu e de is tempus de isetu siant limitados. Faghet a istabilire chi, pro unu funtzionamentu primorosu, sas secuèntzias de operatziones de CPU diant dèpere èssere prus curtzos de sa cantidade de tempus istabilida in belle su 80% de sos casos.

Cun custo algoritmu, sa mèdia andat contada summende sas 4 diferèntzias tra istante finale de esecutzione de su protzessu e relativu consumu. Andende tando a rapresentare in manera gràfica s'andanta de sos protzessos de p1 a p4, notemus chi p1 acabat a s'istante 85, p2 a s'istante 35, p3 a s'istante 145, p4 a s'istante 150. Summende sas diferèntzias amus a tènnere [(85-30)+(35-15)+(145-60)+(150-45)]/4. Sa mèdia risultante est 66,25 ms (Tempus de isetu).

SJF

Sos algoritmos SJF (shortest job first), podent èssere siat sena prelatzione (SNPF) siat cun prelatzione (SRTF).

Non podende connòschere su tempus chi su protzessu at a ocupare su protzessore (pro su problema de sa firmada), su sistema operativu at a impreare sos datos de elaboratziones pretzedentes. Pro fàghere custu, impreat sa fòrmula:

$\tau _{n+1}=\alpha t_{n}+(1-\alpha )\tau _{n}$

In ue (0<=α<=1).

Mescamente:

• $\alpha =0\Rightarrow \tau _{n+1}=\tau _{n}$ (s'istòria reghente non est cunsiderada)
• $\alpha =1\Rightarrow \tau _{n+1}=t_{n}$ (contat solu s'ùrtimu balore beru de su consumu de s'unidade de càrculu)

SNPF

S'algoritmu SNPF (Shortest Next Process First) previdet chi siat esecutadu semper su protzessu cun su tempus de esecutzione prus curtzu tra cussos in isetu. Pighemus a esèmpiu chi siant arribados in manera contemporànea sos sighentes protzessos, cadaunu cun sa durada de esecutzione sua in millisecundos:

• p1: 10
• p2: 2
• p3: 6
• p4: 4

Sos protzessos sunt esecutados in s'òrdine sighente: p2 → p4 → p3 → p1

Sena cunsiderare su tempus netzessàriu pro su càmbiu de cuntestu, su protzessu p2 no abetat nudda, pro ite intrat luego in esecutzione, p4 abetat 2 millisecundos, ca intrat in esecutzione a pustis de p2, tando p3 abetat 6 millisecundos e p1 nd'abetat 12. Su tempus mèdiu de isetu est paris a (0+2+6+12)/4= 5 millisecundos.

Faghet a dimustrare chi custu algoritmu est primorosu, ca cunsentit de otènnere semper su balore prus bassu de tempus de isetu mèdiu. A dolu mannu, no est possìbile a dd'aplicare, in cantu non si podet connòschere a in antis cantu at a durare s'esecutzione de su protzessu. Nointames faghet a proare ddu prevìdere, ca diat pòdere assimigiare a is esecutziones pretzedentes.

Una tècnica impreada est cussa de impreare sa mèdia mòbile esponentziale: $\tau _{n+1}=\alpha t_{n}+(1-\alpha )\tau _{n}$, in ue $\tau _{n}$ est s'istima de sa n-esima esecutzione de su protzessu, $\tau _{n+1}$ s'istima atuale e $\alpha$∈$[0,1]$ est su pesu chi depet èssere assignadu a su passadu de su protzessu e de sòlitu pro $\alpha =1/2$ ddoe at una discreta istima de su cumportamentu de su protzessu e unu resurtadu atzetàbile.

SRTF

S'algoritmu SRTF (Shortest Remaining Time First) si diferèntziat pro su fatu chi, cando arribat unu protzessu nou cun durada minore de su tempus netzessàriu a su protzessu in esecutzione pro acabbare sa sessione sua, su pianificadore faghet unu càmbiu de cuntestu e nde ddi assignat sa CPU.

HRRN

S'algoritmu HRRN (Higher Responsive Ratio Next) est impreadu pro prevènnere s'isetu esageradu de sos protzessos longos, ca cun SNPF e SRTF is chi sunt prus curtzos tenent prioridade, e si basat subra su tempus de isetu de unu protzessu impreende sa fòrmula $Ratio=(W+S)/S$ ue $W$ est su tempus de isetu e $S$ su consumu de sa CPU imbeniente istimadu.

Multilevel Feedback

Mancari chi su tempus de esecutzione de unu protzessu non potzat èssere istimadu cun pretzisione in su su momentu chi intrat in su sistema, ddoe at sa possibilidade de istimare su tempus coladu. Est introduidu su cuntzetu de Feedback segundu su cale si penalizant sos protzessos chi ant gastadu prus tempus in su sistema. Su Multilevel Feedback (o Feedback cun coas mùltiplas) est una pianificatzione basada subra cantos de tempus e impreat unu mecanismu de prioridade dinàmica. Cando unu protzessu intrat in su sistema, tenet una prioridade assignada segundu critèrios pre-definidos e est insertadu in una coa cun unu cantu de tempus fissadu. Si su protzessu chi s'agatat in istadu de esecutzione finit su cantu suo de tempus, est iscostiadu in una coa cun unu cantu de tempus prus mannu ma cun una prioridade minore.

Ogni coa est manigiada pro mèdiu de s'algoritmu de round-robin, totus tranne s'ùrtima chi est serbida tràmite FCFS. Caraterìsticas:

• Favorit protzessos prus curtzos;
• Cun carchi isbrigu est possìbile evitare cunditziones de starvation.

FSS

S'algoritmu FSS (Fair Share Scheduling) collit sos protzessos in grupos, gai est possìbile tènnere unu controllu prus mannu de sa distributzione de sas risursas computatzionales.

Bibliografia

• Sistemi operativi, concetti ed esempi (A. Silbershatz, P. Baer Galvin, G. Gagne, 2003, editore Pearson Educational, ISBN 8871921402).
• Architettura dei Sistemi di Elaborazione, volume 1 (F. Baiardi, A. Tomasi e Marco Vanneschi, 1988, Franco Angeli Edizioni, ISBN 882042746X).
• Architettura dei Sistemi di Elaborazione, volume 2 (F. Baiardi, A. Tomasi, Marco Vanneschi, 1987, Franco Angeli Edizioni, ISBN 882042746X)