Aritoni Ovidiu Sisteme de operare 1 Introducere

C. Randuri multiple

Unul dintre primele temporizatoare prioritare a existat in CTSS (Corbato si al. 1962). Problema intampinata de CTSS a fost aceea ca schimbarea proceselor era foarte inceata din cauza ca 7094 nu putea memora decat un singur process o data. Fiecare comutare insemna trecerea pe discheta a procesului curent si citirea de pe disk a unui nou proces. Cei care au proiectat CTSS si-au dat repede seama ca era mai eficient sa se dea proceselor legate de procesor un quantum mai mare din cand in cand decat quantumuri mici si frecvente (pentru a reduce numarul schimbarilor). Pe de alta parte, un quantum mare pentru toate procesele ar duce la cresterea timpului de raspuns, dupa cum am vazut deja. Solutia lor a fost formarea claselor de prioritati. Procesele din clasele superioare erau rulate un quantum. Procesele din clasele urmatoare - doua quantumuri, urmatoarele, patru quantumuri, si asa mai departe. De fiecare data cand un proces isi epuiza quantumurile alocate era mutat o clasa mai jos.

De exemplu, ganditi-va la un proces care avea nevoie sa calculeze 100 de quantumuri fara intrerupere. Initial ii era acordat un quantum, apoi era schimbat. Data urmatoare ii erau acordate doua quantumuri inainte de a fi schimbat. La rulari succesive ar fi obtinut 4,8,16,32 apoi 64 de quantumuri, desi ar fi folosit pentru a-si termina sarcina doar 37 de quantumuri din cele 64 finale. In acest caz ar fi nevoie numai de 7 schimbari (incluzand si incarcarea initiala) in loc de 100 in cazul unui algoritm circular pur. In plus, pe masura ce procesul se adancea tot mai mult in randuri prioritare, ar fi rulat din ce in ce mai rar, pastrand procesorul pentru procese scurte, interactive.

Urmatoarea tactica a fost folosita pentru a evita uitarea proceselor care initial necesitau o rulare indelungata, dar care ulterior, au devenit interactive. De fiecare data cand la un terminal se cerea finalizarea, procesul apartinand terminalului respectiv era mutat in clasa cu cea mai mare importanta, presupunandu-se ca procesul este pe cale sa devina interactiv. Intr-o zi un utilizator cu un proces solicitant pentru procesor a descoperit ca simpla apasare a tastei ENTER aleatoriu, o data la cateva secunde scurta foarte mult timpul de raspuns. Le-a spus tuturor prietenilor lui. Morala povestii: e mult mai usor sa faci un lucru bine teoretic decat in practica.

Multi alti algoritmi au fost utilizati pentru impartirea proceselor in clase de prioritati. De exemplu, sistemul XDS 940 (Lampson, 1968), construit in Berkeley, avea 4 clase de prioritati numite terminal, I/O, quantum scurt si quantum lung. Cand un proces care astepta pentru intrare de terminal era in cele din urma initiat, acesta intra in clasa cu cea mai mare imprtanta (terminal). Cand un proces care astepta pentru disk era pregatit, intra in cea de-a doua clasa. Cand un proces rula inca in momentul terminarii quantumului, acesta era initial plasat in cea de-a treia clasa. In orice caz, daca un proces isi epuiza integral quantumul de prea multe ori consecutiv, fara sa se fi blocat pentru terminal sau alt I/O, era mutat in capatul randului. Multe alte sisteme folosesc ceva similar pentru a favoriza utilizatorii si procesele interactive fata de cele de fond.

D. Intai sarcinile cele mai scurte

Majoritatea algoritmilor de mai sus au fost conceputi pentru sisteme interactive. Haideti sa analizam acum unul care este potrivit in special pentru sarcini de incarcare a caror timp de rulare este cunoscut dinainte. Intr-o companie de asigurari de exemplu, oamenii pot sa prevada destul de exact cat timp va fi necesar pentru a rula o incarcare de 1000 de cereri, de vreme ce o munca similara se face in fiecare zi. Atunci cand mai multe sarcini la fel de importante formeaza un rand la intrare asteptand sa fie incepute, temporizatorul ar trebui sa foloseasca algoritmul "intii sarcinile cele mai scurte". Priviti figura 2-24. Vom vedea 4 sarcini A,B,C si D cu timpuri de rulare de 8,4,4 si respectiv 4 minute. Rulandu-le in aceasta ordine, raspunsul pentru A va veni in 8 min, pentru B in 12, pentru C in 16, iar pentru D in 20 de minute, deci o medie de 14 minute.

fig.2-24. Un exemplu de temporizare de tipul "intii sarcinile cele mai scurte"

Acum haideti sa analizam cazul in care aceste patru sarcini sunt rulate cu ajutorul

algoritmului " intii sarcinile cele mai scurte", asa cum vedem in figura 2-24(b). Timpurile

de raspuns sunt acum de 4,8,12 si 20 de minute, deci o medie de 11 minute. S-a dovedit ca aceasta metoda este cea mai buna. Sa presupunem ca exista patru sarcini cu timpuri de rulare de a,b,c respectiv d. Prima sarcina este incheiata in intervalul de timp a, cea de-a doua in intervalul a+b si asa mai departe. Media de raspuns va fi de (4a+3b+2c+d)/4. Este clar ca a contribuie mai mult la medie decat in alte cazuri, deci a trebuie sa fie cea mai scurta sarcina, urmata de b, apoi de c si in cele din urma d deoarece ea fiind cea mai lunga sarcina va afecta doar timpul ei de raspuns.Acelasi argument este valabil pentru un numar oricat de mare de sarcini.

Dat fiind ca acest algoritm da cea mai mica medie a timpului de raspuns ar fi bine

daca ar putea fi folosit si pentru procesele interactive. Pana la un anumit punct pot fi folosite. In general, procesele interactive urmeaza modelul de asteptare a comenzii, executarea comenzii, si asa mai departe. Daca privim executarea fiecarei comenzi ca pe o sarcina separata, atunci, in ansamblu, putem sa micsoram timpul de raspuns daca rulam prima data cea mai scurta sarcina. Singura problema este sa ne dam seama care este cel mai scurt dintre procesele curente care pot fi rulate.

O abordare posibila ar fi sa facem estimari bazate pe fapte anterioare si sa rulam

procesul care are cel mai scurt timp estimat. Sa presupunem ca pentru un terminal timpul estimat pentru o comanda este T0. Acum sa presupunem ca urmatoarea rulare a sa este T1. Am putea actualiza estimarea noastra printr-o suma a acestor doua valori, adica aT0+(1-a)T1. Odata cu alegerea lui a putem sa decidem daca dorim ca procesul de estimare sa uite vechile rulari sau daca dorim sa le tina minte mult timp. Daca a=1/2, obtinem estimari succesive dupa cum urmeaza:

T0, T0/2+T1/2, T0/4+T1/4+T2/2, T0/8+T1/8+T2/4+T3/2

Dupa trei noi rulari, valoarea lui T0 in noua estimare a scazut la 1/8.Tehnica estimarii valorii urmatoare intr-o serie prin luarea mediei valorii curente masurate impreuna cu estimarea anterioara se mai numeste si "imbatranire". Se poate aplica in multe situatii in care este necesara o estimare bazata pe valorile anterioare. "Imbatranirea” este usor de implementat mai ales cand a=1/2. Singurul lucru care trebuie facut este adaugarea noii valori la estimarea curenta si impartirea sumei la 2.

Merita sa subliniem ca algoritmul "intai cea mai scurta sarcina" este potrivit doar

atunci cand sarcinile trebuie efectuate simultan. Un contra-exemplu in acest sens: exista cinci sarcini, de la A la E, cu timpuri de rulare de 2,4,1,1 si respectiv 1. Timpurile lor de sosire sunt 0,0,3,3 si 3.

Initial, doar A si B pot fi alese deoarece celelalte inca nu au ajuns. Utilizand

algoritmul in care cea mai scurta sarcina are prioritate vom rula sarcinile in ordinea A,B,C,D si E si vom avea o medie de asteptare de 4.6. Totusi, rulandu-le in ordinea B,C,D,E,A vom avea o medie de asteptare de 4.4.