CURS 1

TIPURI DE SISTEME DE CALCUL SI CARACTERISTICILE LOR:

Sistemele de calcul se impart in: MICROCALCULATOARE, accesibile d.p.d.v al pretului,

dimensiunii reduse, portabile, pot fi folosite in orice domeniu, lucreaza in retea, putand realize

schimburi de date; MINICALCULATOARELE au dimensiuni medii, mai scumpe decat PC-urile, au fost create pentru executarea unor functii specializate: aplicatii multiutilizator, masini cu control

numeric, automatizari industrial, au putere si capacitate de stocare mai mare, UCP complexa, system

de I/O foarte dezvoltat in sensul comunicarii prin retea de periferice in sistem multi-utilizator; MAIN-

FRAME-uri situate intre supercalc. Si minicalc. procesor foarte complex, volum mare de stocare in

UM, sistem de I/O complex, orientat pe gestionare de statii de lucru, permite acces multi-utilizator,

functioneaza de regula fara intrerupere, ceea ce presupune accesul controlat la date si un sistem de

protectii adecvat; SUPERCALCULATOARELE cele mai puternice, complexe si scumpe, au procesorul format dintr-un numar mare de microprocesoare, proiectate pentru calcul paralel.

FUNCTIILE SO:

Functiile de baza ale unui SO sunt extinderea masinii si gestionarea resurselor din perspectiva

multiplexarii intre timp si spatiu.

CE TIP DE MEMORIE SE CITESTE INITIAL LA RESTARTAREA UNUI SISTEM DE

CALCUL?

Memoria ROM se citeste initial.

CE REPREZINTA ISA?

Industry Set Architecture este o magistrala de date inventata de IBM.

LA CE SE REFERA TERMENUL DE MULTIPLEXARE

Multiplexarea este mijlocul prin care gradul de utilizare al unei resurse este imbunatatit ca urmare a

deservirii simultane a mai multor utilizatori.

DEFINITI TERMENUL DE MULTIPROGRAMARE

Multiprogramarea este tehnica de exploatare a SO care permite existenta simultana in memoria interna

a mai multor programe care se executa concurent, in alte parti fixe de memorie.

DEFINITI TERMENUL DE SPOOLING

Spooling reprezinta un mod eficient de exploatare a sistemelor de calcul seriale, bazat pe principiul

separarii operatiilor de intrare de op. de iesire si de restul operatiilor.

CE REPREZINTA GUI?

Graphical User Interface.- este numit sistemul de afiaj grafic-vizual pe un ecran, situat funcional ntre utilizator i dispozitive electronice cum ar fi computere, dispozitive personale de tip hand-held (playere MP3, playere media portabile, dispozitive de jucat), aparate electrocasnice i unele echipamente de birou. Pentru a prezenta toate informaile i aciunile disponibile, un GUI ofer pictograme i indicatori vizuali, n contrast cu interfeele bazate pe text, care ofer doar nume de comenzi (care trebuie tastate) sau navigaia text.

CARE ESTE DIFERENTA DINTRE SO PENTRU RETEA SI SO PENTRU OPERARE

DISTRIBUITE?

Diferenta este ca intr-un sistem distribuit existenta mai multor calculatoare autonome este transparenta

pentru utilizator. Utilizatorul unui sistem obisnuit nu este constient ca exista mai multe procesoare, in

schimb intr-un sistem central, utilizatorii trebuie sa se conecteze explicit la o anumita masina.

TIPURI DE SISTEME DE OPERARE

Main-frame, Server, Multiprocesor,Pc,Real-Time, Sensor mode, Smart card.

AVANTAJELE SISTEMELOR PARALELE:

Avantajele unui sistem paralel sunt: executarea simultana a doua sau a mai multor preocese,

castigandu-se astfel timp.

DESCRIETI MULTIPROCESAREA ASIMETRICA/SIMETRICA

In multi-procesarea asimetrica(slaba conectare) procesoarele sunt dedicate unui anumit tip de sarcini;

de accea un procesor poate fi neutilizat daca sarcinile sale nu sunt necesare. In multi procesarea

simetrica(conectare stransa) fiecare procesor este disponibil pentru orice task.

DESCRIETI SISTEMELE CLUSTER

Sunt sisteme multiprocesor, compuse din doua sau mai multe sisteme, individuale. Definitia acceptata

in general este ca sistemele cluster impartasesc depozitarea si sunt legate via LAN.

CLASIFICATI SO DUPA DESTINATIA LOR

In functie de sistemul de calcul pe care vor fi utilizate SO sunt: Main-frame(SO), Server(SO),

Multiprocesor(SO), PC SO, Real-Time SO, Embedded SO, Smart card So, Sensor mode SO.

CICLUL DE BAZA AL FUNCTIONARII UNUI PROCESOR

Faza de pregatire/Extragere instructiune Decodificarea Executarea instructiunii

DEFINITII

PSW program status word

IP Instruction pointer

SP stack pointer

RAM- Random acces memory

ROM read only memory

EEPROM electrically erasable programable read only memory

CMOS complimentary metal oxide semiconductor

APEL DE SISTEM

Apelul de sisteme inseamna de fapt apel de Kernel, deci invocarea SO

TIPURI DE MEMORIE

Memorie temporara Cache si RAM

Memorie Permanenta ROM,HDD, CD-ROM, FLASH MEMORY.

MODALITATEA DE FUNCTIONARE A MEMORIEI CACHE

Pentru a se recupera din timpul necesar la memorie se apeleaza la memoria CACHE care retine date

necesare pentru rularea programelor active.

STRUCTURA UNUI HDD

D.p.d.v constructiv, HDD-ul contine unul sau mai multe suporturi magnetice(platane) fixate pe un ax

vertical, care are rolul sa imprime miscarea de rotatie a acestora. Pentru stocarea informatieieste

necesara formatarea si eventual partitionarea

MMU

Memory Management Unit = Translatarea un proces de atribuire si organizare(mopare) a adreselor logice si adrese fizice de memorie

PLUG & PLAY

Sistemul PLUG & PLAY faciliteaza folosirea unei componente hardware intr-un sistem fara a fi

nevoie de configurarea dispozitivului sau interventia utilizatorului in rezolvarea conflictelor de

resurse.

MULTI-TASKING capacitatea de a executa mai multe task-uri concomitent

PROCESOARELE MULTITHREADING SI MULTI-CARE

Firele de executie aduc noutatea pentru modelul proceselor, ca permit executiile multiple,

independente in interiorul unui proces. Deoarece firele de executie au proprietati asemanatoare cu ale

proceselor, acestea sunt numite procese usoare. Termenul MULTITHREADING este folosit pentru a

descrie situatia in care esre permisa alocarea fiecarui fir, catre un CPU separat. Procesoarele MULTI-

CARE sunt cele care au mai mult de un nucleu.

CE REPREZINTA O INTRERUPERE?

De fiecare data cand un proces isi incepe felia de timp, executoru initializeaza un circuit de

temporizare care va masura urmatoarea cuanta. La sfarsitul cuantei , circuitul de temporizare

genereaza un semnal care poarta numele de intrerupere.

CUM FUNCTIONEAZA O INTRERUPERE?

UCP reactioneaza la acest seamnal foarte asemanator ca atunci cand este intrerupt in timpul

desfasurarii unei activitati: opreste activitatea, memoreaza unde anume se afla in operatia respectiva, si

acorda apoi atentia cuvenita sursei intreruperii. La primirea unui semnal de intrerupere UCP

completeaza ciclul curent de extragere-decodificare-executare, salveaza pozitia din procesul curent si

incepe executia unui program de tratare a intreruperilor.

DMA- direct memory acces este un proces prin care un dispozitiv extern preia controlul magistralei, in locul procesorului. Ideea fundamentala este de a transfera blocuri de date in mod direct intre

memorie si periferice, fara interventia UCP.

PCI perifheral component interconnect. Componentele PCI fac legatura intre dispozitivele hardware si computer

SCSI small component system interface. Controloarele SCSI sunt folosite in special in sistemele care au nevoie de performanta si stabilitate ridicata.

USB universal serial bus

IDE integrated drive electronics

IEEE 1934 (firewire) defineste o interfata seriala de viteza inalta care se poate utiliza pentru conectarea la PC a dispozitivelor periferice.

BIOS basic imput/output system

DIFERENTA DINTRE MODELUL DE FUNCTIONARE PIPELINE SI MODELUL DE

FUNCTIONARE AL UNEI UCP SUPER SCALARE.

In cazul in PIPELINE - UCP are unitati separate pentru extragere, decodare si executare, deci in timp

ce se executa instructiunea n, se decodeaza instructiunea n+1 si se extrage instructiunea n+2. In cazul

modelului super scalar sunt mai multe unitati de executare, deci doua sau mai multe operatii sunt

prelucrate in acelasi timp, decodate si descarcate intr-un buffer de asteptare pana pot fi executate.

SENSOR NODE OPERATING SYSTEM

Este un SO constituit dintr-o retea de senzori. Acesti senzori comunica intre ei si cu o statie de baza,

folosind o conexiune wireless. Acesti senzori reprezinta de fapt mici calculatoare bazate pe o baterie

cu un radio incorporat. Au putere limitata si nu pot functiona pe perioade lungi de timp. Fiecare senzor

este un calculator cu CPU, RAM, ROM. Sistemul de operare trebuie sa fie mic si simplu, deoarece

senzorii au putin RAM si baterii. Un sistem de operare cunoscut este TINY OS.

Curs 2

Ce reprezinta un proces?

Executia unui program se defineste ca o succesiune de procese care se realizeaza sub controlul

sistemului de operare. Procesul reprezinta o secventa de activitati care se executa la un moment dat in

sistemul de calcul si care se caracterizeaza prin:

- prelucrarile care se realizeaza, determinate de secventa de instructiuni care controleaza procesul;

- prelucrarile care se realizeaza, determinate de secventa de instructiuni care controleaza procesul;

- contextul de lucru asupra caruia actioneaza procesul, prin intermediul prelucrarilor, si care include resursele alocate procesului.

De ce avem nevoie de o memorie virtuala?

Atunci cand spatiul de adresare este prea mic este necesara memoria virtuala.

Sistemul de protectie al fisierelor (directoare si fisiere obisnuite) in Unix.

~ este destinat controlului accesului la fisiere. Sistemul Unix realizeaza o buna separare a

contextelor de executie. Exista trei tipuri de acces la fisiere:

R (read) dreptul la citire, ce permite vizualizarea continutului;

W (write) dreptul de sccriere, ce permite modificarea fisierului;

X (execute) dreptul la executie, ce permite incarcarea fisierului in memorie si lansarea lui in executie sau citirea si executia unui fisier de comenzi Shell.

In cazul directoarelor, drepturile R, W, X sunt interpretate astfel:

R permite utilizatorului sa deschida si sa citeasca fisierul director cu comanda ls;

W permite utilizatorului sa creeze si sa stearga fisiere in directorul respectiv;

X permite ca sistemul sa caute in directorul respectiv in cursul prelucrarii unei cai de acces.

Pentru sistemul Unix exista trei categorii de utilizatori:

U (user) proprietar;

G (group) grup;

O (other) alti utilizatori;

A (all) pentru toate cele trei categorii.

Sistemul Unix este astfel conceput si elaborat incat fiecare fisier are un proprietar, de obicei

persoana care l-a creat. Mai multi utilizatori care fac parte dintr-un compartiment de lucru (teme

comune, domeniu comun etc) formeaza un grup.

Sistemul de protectie a accesului la un fisier se bazeaza pe confruntarea cererilor utilizatorului

(r, w, x) cu drepturile asociate categoriei din care acesta face parte (u, g, o). Pentru precizarea

completa a drepturilor de acces la un fisier sunt necesari 9 biti, 3 biti pentru fiecare categorie de

utilizator.

Ce este file descriptor?

Pentru a putea actiona asupra unui fisier, este nevoie inainte de toate de o metoda de a

identifica in mod unic fisierul. In cazul functiilor discutate, identificarea fisierului se face printr-un

asa-numit descriptor de fisier acesta este un numar intreg care este asociat fisierului in momentul deschiderii acestuia.

Tipuri de fisiere Unix.

In Unix se deosebesc 4 tipuri de fisiere: ordinare (obisnuite), pipe, speciale si directoare. Unele

documentatii considera fisierele pipe in categoria fisierelor speciale.

Un fisier obisnuit este creat de un proces. El poate contine o sursa (text) sau un fisier

executabil (binar). Doua sau mai multe procese pot sa citeasca si sa scrie concurent in acelasi fisier.

Rezultatul depinde de ordinea in care cererile individuale de I/E apar si sunt in general

imprevizibile.Pana nu demult Unix-ul nu avea mecanisme eficiente pentru controlul accesului

concurent. Versiunile mai noi de Unix detin un control al concurentei prin semafoare.

Un fisier pipe este un fisier care este citit de un proces o singura data si este de natura

temporara. Daca data a fost citita din pipe o citire ulterioara este posibila doar daca procesul care a

creat fisierul pipe recreeaza datele intr-un nou fisier pipe. Fisierele pipe sunt cunoscute ca fisiere FIFO

(first in first out).

Fisierele speciale sunt fisiere atasate dispozitivelor de I/E. De exemplu, pentru fiecare partitie

a unui hard disc se gaseste cate un fisier special detine un i-node, care insa nu refera un bloc de date pe disc; in schimb, acest i-node contine un numar de dispozitiv care este folosit ca index intr-o tabela

kernel de proceduri pentru dispozitive periferice. Pentru identificarea fiecarui dispozitiv se folosesc 2

numere: minor (identifica numarul dispozitivului de tipul dat) si major (identifica tipul dispozitivului).

Un director face legatura intre numele fisierelor si locul unde acestea sunt memorate pe disc.

El nu contine efectiv fisierele care ii apartin, ci doar referintele la acestea, sub forma unei succesiuni

neordonate de intrari de 16 biti.

Memoria tampon =>un tampon este o locatie temporara de memorie, care este utilizata in mod

traditional, deoarece instructiunile UCP-ului pur si simplu nu pot referi in mod direct date stocate in

dispozitivele periferice. Astfel, memoria adresabila este utilizata ca stadiu intermediar. In plus, astfel

de tampoane pot fi viabile cand un bloc mare de date este asamblat sau dezasamblat (ca cerinta intr-un

dispozitiv de stocare a datelor), sau cand datele trebuie trimise in alta ordine decat cea in care sunt

produse. Castiful este prezent chiar daca datele tamponate sunt scrise in memoria tampon o singura

data si citite din acesta o singura data.

Caracterizati o conducta.

Shell permite comunicarea intre procese prin conducte (pipes). Conductele sunt canale de date

ce conduc la iesirea unui program catre intrarea altui program, fara crearea unor fisiere intermediare.

Ce inseamna a monta un sistem de fisiere?

Un disc fizic poate contine mai multe partitii logice, realizate de catre driverul de disc. Fiecare

partitie are un nume de fisier dispozitiv. Un proces poate accesa datele unei partitii deschizand fisierul

asociat acesteia, fisier tratat ca o succesiune de blocuri disc in care se poate scrie sau citi. O astfel de

partitie disc poate contine un sistem logic de fisiere ce consta din: un bloc de boot, superblocul, lista

de inoduri si blocuri de date. Un sistem de fisiere poate fi conectat logic (montat) intr-unul din

nodurile arborelui unui alt sistem de fisiere prin intermediul apelului sistem mount. Demontarea se face folosind apelul sistem umount.

Ce reprezinta lseek?

Operatia lseek repozitioneaza cursorul de fisier, astfel incat o operatie read/write va lucra

incepand cu aceasta noua pozitie.

Win32API o interfata destinata programarii aplicatiilor pentru sistemul de operare Microsoft Windows; prin el, programatorul are acces direct la o mare parte a functiilor de nivel de baza ale

sistemului de operare, putand crea aplicatii intr-un mod foarte flexibil.

Structura unui sistem de operare monolitic:

- un program principal care invoca procedurile de servicii necesare; - un set de proceduri de servicii care duc la indeplinire apelurile sistem; - un set de utilitare care vin in ajutorul procedurilor de servicii.

Sistemele stratificare ofera o constructie mai clara si o administrare mai facila a sistemului de

operare, cu anumite neajunsuri: definirea diferitelor nivele trebuie realizata cat mai clar inaintea

conceperii efective a sistemului de operare, iar realizarea de apleuri sistem din nivelele superioare

necesita un overhead mare pentru a putea identifica nivelul tinta si nivelul de origine al apelului

sistem.

Masina virtuala face posibila rularea unui alt sistem de operare intr-o fereastra a sistemului de operare principal, fara a repartitiona hard-disc-ul.

Structura unui microkernel structura modulara, uniformitate a functiilor oferite de drivere, lejeritate in scrierea driverelor, mod unificat de acces la functiile similare a h/w-ului facut de

producatori diferiti.

Structura unui sistem de operare bazat pe modelul client server:

~ este o structura sau arhitectura aplicatie distribuita care partajeaza procesarea intre furnizorii

de servicii numiti servere si elementele care solicita servicii numite clienti. Clientii si serverele

comunica printr-o retea de calculatoare, de obicei prin internet, avand suporturi hardware diferite, dar

pot rula si pe acelasi sistem fizic.Un server (fizic) ruleaza unul sau mai multe programe server, care

partajeaza resursele existente cu clientii. Clientul nu partajeaza niciuna dintre resursele proprii, ci

apeleaza la resursele serverului prin functiile server.Clientii initiaza comunicatia cu serverele si

asteapta mesajele acestora. Pentru mentinearea legaturii intre cei doi, indiferent de pauzele care

intervin, se foloseste conceptul de sesiune, care de obicei este limitata in timp.

Curs 3:

Definiti procesul.

Un proces este un program secvential in executie, impreuna cu zona sa de date, stiva si

numaratorul de instructiuni (program counter).

Orice proces este executat secvential, iar mai multe processe pot sa ruleze in paralel. De cele

mai multe ori, executia in paralel se realizeaza alocand pe rand procesorul cate unui proces. Desi la un

moment dat se executa un singur proces, in decurs de o secunda de exemplu, pot fi executate portiuni

din mai multe procese. Din aceasta schema rezulta ca un process se poate gasi, la un moment dat, in

una din urmatoarele stari:

- in executie (RUNNING) procesul se gaseste in executie atunci cand procesorul ii executa instructiunile;

- pregatit pentru executie (READY) este un proces care, desi ar fi gata sa isi continue executia, este lasat in asteptare din cauza ca un alt proces este in executie in mod voit sau

procesul efectureaza o operatie in afara procesorului, mare consumatoare de timp (cum e

cazul operatiilor de intrare iesire acestea sunt mai lente si intre timp procesorul ar putea executa parti din alte procese);

- blocat (BLOCKED).

Cum se creaza un proces?

Sunt patru pasi principali care duc la crearea unui proces:

- initializarea sistemului; - executarea unui sistem de apel pentru crearea unui proces de catre un proces aflat deja in

rulare;

- o cerere de creare proces a utilizatorului; - initializarea unui set de batch jobs (secventa de comenzi care se executa fara interventie

din afara).

Cum se incheie executia unui proces?

Un proces se poate incheia din cauza unuia din patru motive:

- iesire normala (voluntara); - iesire pricinuita de eroare (voluntara); - eroare fatala (involuntara); - incheiere pricinuita de alt process (involuntar).

Caracterizati ierarhia de procese.

In unele sisteme, cand un proces creaza un altul, procesul parinte contiua sa fie asociet cu cel

copil. Procesul copil poate si el sa creeze unul sau mai multe procese, astfel creandu-se o ierarhie.

Ce reprezinta un thread?

Threadul este cea mai mica unitate de procesare care poate fi programata de un sistem de

operare.

Ce inseamna multithreading?

Termenul multithread se poate referi la faptul ca mai multe threaduri exista in acelasi proces

sau rularea in paralel a mai multor threaduri, echivalentul mai multor procese rulate pe acelasi

calculator.

Modele:

Kernel-level threading threaduri create de utilizator care au corespondenta 1-1 cu entitati din kernel. Este cea mai simpla implementare de threaduri.

User-level threading (many to one)- toate threadurile de la nivel de aplicatie ajung intr-o

singura entitate de la nivel kernel. Singurul dezavantaj major este ca nu poate beneficia de accelerare

hardware pe procesoarele multithread sau pe sistemele multi-procesor.

Hybrid threading (many to many) un numar de threaduri de aplicatii ajung la un numar de entitati kernel (procesoare virtuale). Acesta este un compromis intre ULT si KLT. Este mai complex de implementat decat celelalte doua.

Justificati necesitatea threadurilor.

Principalul motiv pentru existenta threadurilor este ca in multe aplicatii au loc mai multe

activitati in acelasi timp,care se pot bloca ocazional. Prin descompunerea unor astfel de aplicatii in

secvente thread care ruleaza cvasi paralel, modelul de programare devine mai simplu.

Un alt motiv este ca sunt mai usor de creat si distrus decat procesele dat fiind faptul ca nu au

resurse atasate.

Ce reprezinta o masina cu stari finite?

Masinile cu stari finite reprezinta o metoda foarte eficienta pentru modelarea circuitelor

secventiale. Prin modelarea masinilor cu stari finite intr-un limbaj de descriere hardware si utilizarea

programelor, programatorul se poate concentra asupra modelarii secventei dorite de operatii fara a-si

pune problema in privinta implementarii circuitului (aceasta operatie este lasata programului).

Care sunt avantajele si dezavantajele thread-urilor?

Ele partajeaza acelasi spatiu de adrese si sunt mai rapide decat procesele (la task-switch, nu se

mai schimba si spatial de adrese).

Marele dezavantaj este problema la sincronizare.

Fiecare thread are propriul context, format din registri CPU si stiva.

Descrieti thread-urile pop-up.

Sunt threaduri create de sistem la aparitia unui mesaj, pentru a se ocupa de mesajul respectiv.

Caracterizati notiunea de concurenta intre doua procese. Concurena reprezinta situaia n care mai multe procese citesc sau scriu pe un set de date partajate i rezultatul final depinde de care proces ruleaza si cnd anume.

Procesele concurente numitei procese paralele, presupun c la un moment dat, mai multe programe pot fi urmrite ntre punctul de nceperei terminare a execuiei; n acest caz procesele interacioneaz n dou moduri: - indirect, prin concurarea la aceiai resurs a sistemului; - direct, prin utilizarea simultan a acelorai resurse. Se constat situaia n care procesele i afecteaz reciproc, ntr-un mod nedorit, execuia activitailor critice ( s presupunem ca dou procese ncearc n acelai timp s aloce ultimul 1MB de memorie). Dificultatea apare pentru c un proces B ncepe sa foloseasc una din variabilele partajate nainte ca un proces A s se termine. Acest situaie poate fi evitat dac se interzice citirea si scrierea de ctre mai multe procese simultan a datelor partajate.

Pentru a fi evitat concurena i a avea o soluie buna trebuiesc ndeplinite patru condiii: i. Oricare dou procese nu se afla simultan n regiunile lor critice. ii. Nici un fel de presupunere nu se poate face asupra vitezelor sau numarului de UCP-uri.

iii. Nici un proces care ruleaz n afara regiunii lui critice nu poate bloca alte procese. iv. Nici un proces nu trebuie s atepte la infinit pentru a intra n regiunea lui critic. (Tanembaum, 2001)

Caracterizati notiunea de sincronizare intre doua procese. Sincronizarea proceselor include mecanisme prin care anumite procese vor fi oprite la un moment dat,

pn ce apar anumite evenimente ce se afl sub controlul altei activiti. Problema sincronizrii apare datorit partajrii resurselor n legtur cu alocarea proceselor pentru execuia i comunicaia ntre procese .

Sincronizarea este necesar la uniprocesoare, multiprocesoare i in reelele de calculatoare.

Un program paralel const din mai multe procese independente ce coopereaz pentru a rezolva o problem. Cooperarea se poate realiza prin intermediul unei memorii partajate.Sistemul de operare trebuie s ofere cel putin un mecanism de baz care s permit comunicarea i sincronizarea n cadrul unui set de procese.

n sistemele multiprogramate, aceste operaii de comunicaie se pot realiza prin intermediul fiierelor.Un proces poate oferi unui proces informaii scriind date ntr-un fiier astfel nct cellalt proces s poat deschide fiierul i s poat citi informaiile respective. n general,comunicarea i sincronizarea prin intermediul fiierelor partajate este greoaie, iar procesele trebuie s fie capabile s se sincronizeze pe baza unui mecanism mai simplu dect acela de a partaja accesul la un fiier. Sistemele de tip timesharing stimuleaz nevoia unei metode mai facile de comunicare i sincronizare ntre procese. n astfel de sisteme, un singur utilizator poate s creeeze dou procese, rezultatul primului proces putnd fi rutat spre intrarea celui de-al doilea proces. Conductele (pipe) UNIX

implementeaz o astfel de facilitate. Programele bazate pe conlucrare trebuie s fie construite astfel nct procesele s poat accesa informaiile comune, totui far a interfera unul cu altul pe parcursul unor poriuni critice ale execuiei lor. Aceast condiie introduce o problem de sincronizare numit problema seciunii critice. O a doua problem este existena unui punct de blocare ( deadlock) n cadrul proceselor cooperante. Acest lucru nseamna c dou sau mai multe procese pot fi n situia n care fiecare deine resursele necesare celuilalt proces i nici unul nu poate continua executia fr ca s i cedeze celuilalt resursele. (Dodescu, 2003)

Dati un exemplu de situatie in care doua procese se gasesc n conditii de competitie. Considerm existenta a doua procese A i B a cror scop este tiprirea unui fiier la imprimant. Cnd un proces vrea s tipareasc un fiier, introduce numele fiierului ntr-un catalog de tiprire special (spooler directory). Alt proces, care se ocup de tiprirea documentelor (printer daemon), verific periodic dac exist fiiere de tiprit i, dac exist, le tiparete i apoi terge numele lor din catalog. Acest catalog de tiprire are un numr foarte mare de locaii, identificate prin 0,1,2... fiecare fiind capabil s memoreze numele unui fiier n fiecare lot. De asemenea exist dou variabile partajate, out, care indic urmtorul fiier care trebuie tiparit i in, care indic urmtorul loc liber n catalog.Aceste doua variabile pot fi pstrate foarte bine ntr-un fiier de doua cuvinte, disponibil tuturor proceselor.

n figur se constat c loturile de la 0 pana la 3 sunt libere (fiierele au fost deja tiprite) i loturile de la 4 pna la 6 sunt ncarcate (cu numele fiierelor care ateapt s fie tiprite). Situaia care o discutm este urmtoarea: mai mult sau mai puin simultan, procesele A i B solicit s nscrie un fiier pentru tiprire. Poate aprea situaia n care procesul A citete variabila in i salveaz valoarea 7, ntr-o variabil local numit urmtorul_loc_liber. Chiar atunci apare o ntrerupere de ceas i UCP decide c procesul A s-a executat suficient, aa c va comuta la procesul B. Procesul B citete i el in i primete tot un 7. i el o va salva n variabila sa local urmtorul_loc_liber. n acest moment ambele procese consider c urmtorul loc disponibil este 7. Procesul B continu sa se execute. Salveaz numele fiierului lui n locul cu numrul 7 i actualizeaz in la valoarea 8.Apoi, se execut mai departe. La un moment dat, procesul A i va relua execuia. Verific urmtorul_loc_liber, gsete valoarea 7 acolo i scrie numele fiierului lui n locul cu numrul 7, tergnd numele pe care procesul B tocmai l scrisese acolo.Apoi calculeaza urmatotul_loc_liber +1, adica 8 i seteaz in la valoarea 8. Catalogul de tiprire are acum o stare intern consistent, aa c procesul care se ocup de imprimare nu va observa nimic n neregul, dar procesul B nu va primi niciodata un rezultat. Utilizatorul B va atepta lnga imprimant ani de zile, tnjind dup rezultatul care nu va veni niciodata. Situaii ca acestea, n care dou sau mai multe procese citesc sau scriu date partajate i rezultatul final depinde de care proces ruleaz i cnd anume sunt numite condiii de cursa (race conditions). (Tanembaum, 2001)

Doua procese sunt mutual exclusive.Explicati. Pentru a preveni efectele generate de condiiile de competiie este necesar ca procesele s fie mutual exclusive.Dac un proces ruleaz i partajeaz resurse cu alt proces, acesta din urm nu se poate lansa n execuie pn la finalizarea execuiei primului.Zona n care dou procese acceseaz memoria partajat de ambele se numete seciune critic. Dac reuim ca dou procese s nu se afle n seciunea critic simultan putem evita competiian sine. Condiiile obinerii exclusivitii mutuale sunt: i. Dou procese nu se pot afla simultan n zona critic. ii. Nu ne raportm la numrul i viteza de prelucrare a procesoarelor.

iii. Niciun proces, care ruleaz n afara seciunii sale critice nu poate bloca un alt proces. iv. Un proces nu poate fi blocat la infinit la intrarea sa n seciunea critic. Exemplu: Situaia pe care o discutm este urmtoarea:

ltan tiprirea unui fiier.Procesul A citete variabila In i o stocheza 7.Procesorul blocheaz execuia Procesului A i red controlul Procesului B. Procesul B se execut i plaseaz numele fiierului de tiprit n 7 i seteaza In=8.

blocheaz Procesul B i transfer controlul Procesului A.

e procese citesc sau scriu pe un set de date partajate i rezultatul final depinde de care proces ruleaz i cnd anume, se numesc condiii de cursa .

Ce reprezinta o sectiune critica? Seciunea crtitic reprezint zona n care dou procese acceseaz memoria partajat de ambele procese.

Problema evitrii condiiilor de curs poate fi de asemenea formulat ntr-o manier abstract. O parte din timp un proces este ocpuat cu execuia calculelor interne i a altor lucruri care nu conduc la condiii de curs. Totui, un proces trebuie uneori s eceseze memoria sau fiierele partajate, sau s execute alte activiti critice care pot conduce la curse. Partea de program n care memoria partajat este accesat se numete regiune critic (critical region) sau seciune critic (critical section). Daca s-ar putea aranja lucrurile astfel nct oricare din dou procese s nu fie niciodat n acelai timp n regiunile lor critice, am putea evita cursele. (Tanembaum, 2001)

Doua procese obtin exclusivitate mutuala prin metoda de dezactivare a intreruperilor.

Prezentati dezavantajele metodei. Exclusivitatea mutual utiliznd busz waiting-ul are ca prim soluie dezactivarea ntreruperilor. Aceast abordare prezint urmtoarele dezavantaje: a) Dac dou procese pot dezactiva ntreruperile exist posibilitatea ca acestea s blocheze activarea ulterioar a ntreruperilor.

b) Dac lucrm pe un sistem multiprocesor exist posibilitatea ca un proces s dezactiveze ntreruperile doar pentru unu din procesoare , metoda devenind astfel ineficient. c) Deoarece sistemul de operare pentru buna sa operare realizeaz periodic apeluri de sistem, dezactivarea ntreruperilor la un moment inoportun poate afecta funcionalitatea sistemului de operare.

Concluzia este : O astfel de metod poate fi folosit cu succes doar de procese care opereaza la nivel Kernel.

Ce reprezinta un bit de atentie? Un mecanism de sincronizare pentru coordonarea i comunicarea ntre procese este :biul de atenie. Prin aceast modalitate, orice resurs partajat de "n" procese va dispune de un bit de atenie "lock-bit" folosindu-se convenia:

-bit = 0 - resursa este disponibil; -bit =1 - resursa este n folosin.

nainte ca un proces s aib acces la un procesor, acesta va verifica starea lock-b it-ului: dac lock-bit = 0 atunci este permis acestui proces s aib acces la procesor, iar la terminarea execuiei va trece lock-bit-ul n starea iniial 0; dac pe parcursul execuiei un alt proces va solicita procesorul, acesta va gsi lock-bit-ul n starea 1, el fiind trecut n starea de ateptare pn cnd lock-bit-ul devine 0.

Prezentati metoda de alternare stricta a executiei proceselor si dezavantajele ei. Presupunem dou procese A i B. Aceast soluie este o soluie care impune celor dou procese Ai B s alterneze accesul in regiunile lor critice, de exemplu in inregistrarea fiierelor pentru tiprire. Nici unul dintre procese nu va avea voie s zicem s inregistreze consecutiv dou fiiere. Astfel spus un proces care nu se afl in zona critic poate s blocheze un alt proces. tiind de cele patru condiii de cooperare ne dm seama c aceast soluie incalc condiia de eficien care spune c nici un proces care ruleaz in afara zonei critice s nu blocheze alte procese. Dei acest algoritm evit cursele nu este eficient.

n secvena de mai jos, variabila de tip ntreg turn, iniial cu valoarea 0, determin al cui rnd este s intre n regiunea critic i s verifice sau s actualizeze memoria partajat.Iniial, procesul 0 verific turn, observ c are valoarea 0 i intr in regiunea critic.Procesul 1 gasete tot valoarea 0 i de aceea cicleaz ntr-o bucla mic, verificnd mereu turn pn devine 1.Verificarea n continuu a unei variabile pn cnd are o anumit valoare se numete ateptare opcupat (busy waiting).Aceasta trebuie evitata ntotdeauna, deoarece irosete timp pe procesor. Ateptarea ocupat este folosit doar atunci cnd probabilitatea ca ateptarea s fie scurt esterezonabil.Un zvor care folosete ateptarea ocupat se numete spin lock while(TRUE) { while(TRUE) {

while(turn!=0) /*loop*/ ; while(turn!=1) /*loop*/ ;

critical_region(); critical region();

turn=1; turn=0;

noncritical_region(); noncritical_region;

} }

(a) Procesul 0 (b) Procesul 1

Cnd procesul 0 prsete regiunea critic, va seta turn pe 1, pentru a permiteprocesului 1 s intre n regiunea lui critic.S presupunem c procesul 1 termin execuia regiunii lui critice repede, astfel c ambele procese sunt n afara regiunii lor critice, cu turn avnd valoarea 0.Acum, procesul 0 execut rapid intreaga bucl, ieind din regiunea lui critic i modificnd turn la valoarea 1.n acest moment turn are valoarea 1 i ambele procese se execut n afara regiunilor lor critice. Brusc, procesul 0 termin i execuia regiunii sale necritice i reia bucla.Din pcate, acum nu i este permis s intre n regiunea critic, deoarece turn are valoarea 1, iar procesul 1 este ocupat cu execuia regiunii sale necritice.Procesul 0 va rmne agat n bucla while pn cnd procesul 1 va seta turn pe 0.Cu alte cuvinte, alternarea nu este o ide bun atunci cnd unul dintre procese este mult mai lent dect cellalt. Aceast situaie nu respect condiia 3 stabilit mai sus: procesul 0 este blocat de un proces care nu se afl n regiunea sa critic.ntorcndu-ne la catalogul de tipariredespre care am vorbit mai sus, procesul 0 nu ar putea tipri alt fisier pentru c procesul 1 execut altceva. De fapt, acest soluie impune celor 2 procese s alterneze stict in regiunile lor critice, de exemplu n nregistrarea fisierelor pentru tiprire.Niciunuia dintre procese nu i se va permite s nregistreze consecutive 2 fisiere.Dei acest algoritm evit cursele, nu este candidat serios pentru o soluie deoarece nu respect condiia 3. {pentru a avea o soluie bun trebuie ndeplinite 4 conditii: 1.oricare 2 procese nu se pot afla simultan n regiunile lor critice

2.niciun fel de presupunere nu se poate face asupra vitezelor sau numrului de UCP-uri 3.niciun proces care ruleaz n afar regiunii lui critice nu poate bloca alte procese 4.niciun proces nu trebuie s atepte la infinit pentru a intra n regiunea lui critic.}

Descrieti solutia lui Peterson. Prin combinarea ideii de alternare cu ideea variabilelor zvor si a variabilelor de avertizare, un matematician olandez T.Dekker. a fost primul care a nascocit o solutie de tipul sistemelor de programe

pentru problema excluderii mutuale, care nu impunea alternarea stricta.

In 1981, G.L. Peterson a descoperit un mod mai simplu de obtinere a excluderii mutuale umbrind

Solutia lui Dekker. Algoritmul lui Peterson este prezentat in figura 2-201. Acest algoritm este format

din 2 proceduri scrise ANSI C, ceea ce inseam c trebuie menionate prototipurile tuturor funciilor.

Solutia lui Peterson pentru obinerea excluderii mutuale. nainte de a folosi variabilele partajate (adica nainte de a intra in regiunea lui critica), fiecare proces

apeleaz enter_region cu numrul su de ordine, 0 sau 1, drept parametru. Acest apel l va face s atepte dac este cazul, pn cnd este n regul s intre. Dup ce a terminat de utilizat variabilele partajate, procesul apeleaz leave_region pentru a indica faptul c a terminat pentru a permite altui proces s intre, dac doreste. S vedem cum functioneaz aceasta soluie.Iniial, niciun proces nu se afl n regiunea lui critic.n acest moment procesul 0 apeleaza enter_region. si arat interesul prin setarea elementului din vector corespunztor lui i seteaz turn pe 0. Din moment ce procesul 1 nu este interesat, enter_region se termin de executat imediat. Dac procesul 1 apeleaz acum enter_region, va rmne agat acolo pn cnd interested[0] devine FALSE, eveniment care se ntmpl doar cnd procesul 0 apeleaz leave_region pentru a prasi regiunea sa critic. S considerm acum cazul n care ambele procese apeleaz enter_region aproape simultan.Ambele vor salva numrul propriu de ordine turn. Salvarea care se face ultima va conta: prima va fi suprascrisa i pierdut. (Tanembaum, 2001)

Ce reprezinta TSL? Multe calculatoare, mai ales cele proiectate innd cont de un numr mai mare de procesoare, au o instruciune (TSL RX, LOCK) (Teste and Set Lock) care funcioneaz dup cum urmeaz. Citete coninutul lui Lock n registrul RX i apoi salveaya o valoare diferit de zero la adresa de memorie a lui Lock. Operaiile de citire a cuvntului i salvrii n el sunt garantat indivizibile nici un alt proces nu poate accesa cuvntul de memorie pn cnd instruciunile nu s-au terminat. Procesorul care execut instruciunea TSL blocheaz magistrala memeoriei pentru a interzice altor procesoare s acceseze memoria pn ce nu a terminat de executat instruciunea. Pentru a utiliza TSL, se va folosi o variabil partajat, Lock, pentru a coordona accesul la memoria partajat. Cnd Lock are valoarea 0, orice proces o poate seta la 1 folosind instruciunea TSL i apoi s citeasc sau s scrie n memoria partajat. Dup ce termin, procesulreseteaz Lock napoi la 0 folosind instruciunea Move.

Pentru a mpiedica dou procese s intre n acelai timp n regiunile lor critice, soluia este prezentat mai jos:

Ceea ce este prezentat mai sus este o subrutin de patru instruciuni, ntr-un limbaj de asamblare fictiv (dar tipic). Prima instruciune copiaz vechea valoare a lui Lock n registru i seteaya apoi Lock la 1. Apoi, vechea valoare este comparat cu 0. Dac nu este 0, nseamn c LOCK esra deja setat, astfel c programul reia codul de la nceput i testeaz din nou condiia. Mai devreme sau mai trziu va deveni 0 (atunci cnd procesorul se afla n regiunea lui critic va termina cu aceasta), iar subrutina se va termina, cu LOCK setat. Eliberarea lui LOCK este simpl. Programul salveaz pur i simplu un 0 n lock. Nu sunt necesare instruciuni speciale. O soluie la problema regiunii critiice este clar. nainte de a intra n regiune critic proprie, un proces apeleaz enter_region, care execut ateptare ocupat pn cnd LOCK este liber: apoi, preia LOCKuli se intoarce din apelul enter?region. Dup regiunea critic, procesul apeleaz leave_region, care salveaz un 0 n zvor. La fel ca n cazul tuturor soluiilor bazate pe regiuni critice, procesele trebuie s apeleze enter_region i leave_region la momentele de timp corecte pentru ca mecanismul s funcioneze. Dac un proces trieaz, excluderea mutual va eua. (Tanembaum, 2001)

De ce avem nevoie de metoda sleep/wakeup? Datorit faptului c soluia lui Peterson nu poate gestiona problema inversrii prioritii s-a propus metoda Sleep and Wakeup.S presupunem c dou procese partajeaz un buffer de dimensiune fix. Un proces adaug date, cellalt extrage date.Aceast problem se mai numete problema productor-consumator, unde p. care adaug date n buffer este productor, iar cel care extrage date este consumator.Dac se ntmpl ca procesorul s ntrerup execuia procesului consumatorului i din punct de vedere logic consumatorul se afl nc n starea wakeup, productorul va genera un semnal de wakeup, care se va pierde datorit faptului ca nu exist o structur care s rein cte apeluri wakeup au fost realizate.

Tratati problema producator consumator utilizand metoda sleep/wakeup. Metoda cu apeluri sleep/wake-up este o metod simplu de implementat unde folosim apelul de sistem sleep care are ca efect blocarea apelantului, adic suspendarea execuiei acestuia i apelul de sistem wake/up pentru a trezi un proces.

Funcionarea acestei metode este urmtoarea: Fiecare dintre procese va verifica dac este cazul s l trezeasc pe cellalt i dac da, l va trezi. Condiia de curs apare pentru c accesul la condiia Memoria tampon plin? este nerestricionat. Poate aprea urmtoarea situaie- zona tampon este goal i consumatorul tocmai a verificat condiia Memoria tampon goal? pentru a verifica dac este DA. n acest moment planificatorul de procese decide s suspende execuia consumatorului i ncepe s execute productorul. Productorul introduce un element n memorie i observ c acum condiia Memoria tampon plin? este acum DA. Deoarece condiia tocmai a fost NU i deci consumatorul este suspendat, productorul apeleaz wakeup pentru a trezi consumatorul. Consumatorul nu este i logic suspendat i semnalul de trezire se va pierde i astfel data urmtoare cnd consumatorul se va executa acesta va verifica condiia

Memoria tampon goal? Citit anterior, va gsi DA i i va suspenda execuia. Dup ctva timp productorul i va suspenda i el execuia. Ambele procese vor fi suspendate. (stst.elia.pub.ro)

Prezentati cazul in care metoda sleep/wakeup devine ineficienta pentru rezolvarea problemei

producator consumator. Problema acestei metode este pierderea suspendrii consumatorului. Din pcate, consumatorul nu este i logic suspendat, astfel c semnalul de trezire este pierdut. Data urmtoare cnd se va executa consumatorul, acesta va verifica valoarea lui count citit anterior, va gsi 0 i i va suspenda execuia. Dup ctva timp, productorul va umple zona tampon i i va suspenda i el execuia. Ambele procese vor fi suspendate pentru totdeauna.

Soluie : memorarea bitului de trezire, dac se trimite unui proces treaz. Ulterior, dac acesta vrea s se autoblocheze, nu o va face, dar va terge bitul de memorare a trezirii. Fiecare proces care poate trezi un proces nc treaz va trebui s i aib bitul memorat, mpreuna cu adresa procesului la care se refer.

Curs 5:

Motivatia planificarii proceselor. n cazul folosirii multiprogramrii pe un calculator, acesta conine frecvent mai multe procese care concureaz simultan pt controlul UCP. Aceast situatie apare ori de cate ori doua sau mai multe procese se afl simultan n starea gata de execuie.Dac este disponibil o singura UCP, trebuie facuta o alegere cu privire la procesul care va rula n continuare. Componenta sistemului de operare care face

aceast alegere se numete planificator(scheduler) i algoritmul folosit de aceasta se numeste algoritm de planificare.

Definitia algoritmului de planificare preemtiv. Un algoritm de planificare preemtiv alege un proces i l las s se execute o durat maxim fixat. n caz c procesul este nc n execuie la sfritul intervalului de timp, este suspendat i planificatorul alege alt proces (daca exist un proces disponibil). Efectuarea unei planificri preemtive necesit o intrerupere de ceas la sfritul intervalului menionat pentru a muta controlul asupra UCP inapoi la planificator.Dac nu exist un ceas, singura opiune este planificarea non-preemtiv.

Definitia algoritmului de planificare nonpreemtiv. Un algoritm nonpreemtiv alege un proces pentru execuie i apoi l las s ruleze pn se blocheaz (fie la o operaie I/E sau n ateptarea altui proces) sau pn cnd procesul renunt voluntar la UCP. Chiar daca ruleaz ore intregi, procesul nu va fi suspendat forat. De fapt, nu se ia nicio decizie in timpul ntreruperilor de ceas. Dupa ce s-a terminat procesarea ntreruperii, procesul care rula nainte de

ntrerupere este executat n continuare.

Definitia compute-bound process. Anumite procese petrec majoritatea timpului efectund calcule, acestea se numesc procese limitate de

calcule (compute-bound). Ele au n mod obinuit rafale de utilizare a UCP mai lungi si ca atare perioade de ateptare a operaiilor I/E rare.

Definitia I/O-bound process. Exist de asemenea anumite procese care ii petrec majoritatea timpului ateptnd completarea operaiilor de I/E, acestea se numesc procese limitate de I/E (I/O- bound). Procesele limitate de I/E au rafale UCP scurte i perioade( frecvente) de asteptare a operaiilor de I/E. S observam c factorul cheie este lungimea rafalei UCP i nu lungimea rafalei I/E. Procesele limitate de I/E sunt de acest tip pentru c nu efectueaz multe calcule ntre cererile de I/E, pentru c nu au cereri I/E deosebit de lungi.

Care sunt obiectivele generale ale unui algoritm de planificare. 1. Corectitudine: fiecare proces primete o capacitate egal de UCP.

2. Respectarea politicilor: politica declarat trebuie respectat.

3. Echilibrul: meninerea tuturor prilor sistemului n operare.

Care sunt obiectivele generale ale unui algoritm de planificare pentru un sistem batch. 1. Productivitate: maximizarea numrului de sarcini pe or.

2. Timpul de rspuns: minimizarea timpului ntre introducerea sarcinii i terminare.

3. Gradul de utilizare a UCP: meninerea UCP ocupat tot timpul.

Care sunt obiectivele generale ale unui algoritm de planificare pentru un sistem interactiv. 1. Timpul de raspuns: rspuns rapid la cereri.

2. Proporionalitate: ndeplinirea ateptrilor utilizatorului.

Care sunt obiectivele generale ale unui algoritm de planificare pentru un sistem n timp real. 1. Respectarea termenelor: evitarea pierderii datelor.

2. Predictibilitate evitarea degradrii calitii sistemelor multimedia.

Sistemele n timp real sunt acele sisteme pentru care timpul joac un rol esenial. Astfel de calculatoare sunt conectate de regul la un dispozitiv extern care trimite anumite semnale ctre calculator, iar calculatorul trebuie s raspund la aceste semnale intr-un interval de timp bine stabilit. Exemple de astfel de sisteme sunt pilotul automat ntr-un avion sau un sistem de monotorizare a unui

reactor nuclear.

Algoritmi de planificare utilizati pentru sistemele batch. 1. Primul venit-primul servit (first-come first-served). n cazul acestui algoritm, procesele primesc

UCP n ordinea n car cer.n principiu, exist o singur coad de procese gata de execuie. Atunci cnd este introdus prima sarcin din exterior, dimineaa, este pornit imediat i i se permite s ruleze ct timp dorete. Pe msur ce sosesc celelalte sarcini, ele sunt plasate la sfritul cozii. Atunci cnd procesul n execuie se blocheaz este plasat la sfaritul cozii, ca i n cazul unei sarcini nou sosite.

2. Cea mai scurt lucrare la nceput(shortest job first). Atunci cnd mai multe sarcini, la fel de importante, ateapt n coada de intrare pentru a fi pornite, planificatorul alege cea mai scurt lucrare la nceput.

3. Urmatorul timp minim rmas(shortest remaining time next). n cazul acestui algoritm, planificatorul alege mereu procesul al crui timp de executie rmas este cel mai scurt. Timpul de rulare trebuie cunoscut a priori, atunci cnd sosete o nou lucrare, durata sa total este comparat cu timpul rmas pentru procesul curent. Dac noua lucrare necesit mai puin timp dect procesul curent, acesta este suspendat i se pornete noua lucrare. Aceast schem permite sarcinilor noi i scurte s obin un serviciu de calitate.

4. Planificare pe trei nivele. Pe masur ce sosesc noi sarcini n sistem, ele sunt iniial plasate ntr o coad de intrare situat pe disc. Planificatorul de primire decide ce sarcini va admite n sistem. Celelalte sunt inute n coada de intrare pn cnd sunt selectate. Al doilea nivel de planificare const n a decide care procese ar trebui pstrate in memorie i care ar trebui inute pe disc, aceast sarcin este ndeplinit de planificatorul de memorie. Iar al treilea nivel de planificare consta de fapt n a alege unul din procesele gata de execuie din memoria principal pentru a rula. Aceast component este numit planificatorul UCP.

Algoritmi de planificare utilizati pentru sistemele interactive. 1. Planificare Round Robin. Fiecrui process i se atribuie un interval de timp numit cuant n care i se permite s ruleze. Dac procesul este nc n execuie la sfritul cuantei, UCP se ia forat de la

respectivul proces i se atribuie altui proces. Dac procesul s-a blocat sau s-a terminat nainte de terminarea cuantei de timp, comutarea UCP se face n momentul blocrii procesului.

2. Planificarea bazat pe prioriti. Fiecare process are o prioritate i se permite rularea procesului gata de execuie cu cea mai mare prioritate. Pentru a prentmpina cazurile n care procesele cu prioritate mare ruleaz la infinit, planificatorul poate decrete prioritatea procesului curent la fiecare semnal de ceas (adic la fiecare ntrerupere de ceas). Daca aceast aciune determin prioritatea respectivului proces s scad sub a urmatorului din ierarhie, acest ultim proces are posibilitatea s se execute.

3. Cozi multiple. Poiectanii creeaz clase de prioritate. Procesele din cea mai mare clas erau rulate pentru o cuant de timp. Procesele din urmatorarea clas se rulau pe trei cuante de timp, urmatoarele pe patru cuante de timp .a.m.d. Cnd un proces folosea n ntregime cuanta alocat, era mutat n jos o clasa.

4. Shortest process next. Procesele interactive urmeaz de obicei modelul n care se asteapt o comand, se execut comanda, se asteapt comanda, se execut comanda .a.m.d. Dac privim execuia fiecrei comenzi ca pe o lucrare separat, atunci putem minimiza ntreg timpul de rspuns executnd n continuare cea mai scurt lucrare. Singura problem const n a realiza care din procesele executabile este cel mai scurt. O abordare const n a face estimri bazate pe comportamentul anterior i a rula procesul cu cel mai mic timp de execuie estimate. Tehnica prin care se estimeaz urmtoarea valoare ntr o serie prin considerarea sumei ponderate a ntregii valori curente msurate i a valorii estimate anterioare se numete mbtrnire (aging). 5. Planificarea garantat. O abordare complet diferit la problema planificrii const n a face promisiuni reale utilizatorilor referitoare la performan i de a le respecta. Dac exist n utilizatori conectai n sistem n timp ce noi lucrm, vom primi aproximativ 1/n din puterea de calcul; n mod similar, pe un sistem cu un singur utilizator pe care ruleaz n procese, toate fiind egale, fiecare ar trebui s beneficieze de 1/n din ciclurile procesorului. Pentru a respecta aceast promisiune, sistemul trebuie s in evidena capacitii de calcul consumate de fiecare proces de la crearea sa. Se calculeaz apoi capacitatea la care are dreptul fiecare, mai precis intervalul de la creare este mpartit la n.

6. Planificarea n sistem de loterie. Ideea fundamental este de a atribui proceselor bilete de loterie pentru diferite resurse ale sistemului, cum ar fi timpul alocat pe UCP. Atunci cnd trebuie luat o decizie de planificare se alege un bilet de loterie la ntamplare i procesul care deine biletul primete resursa. Aplicat planificrii proceselor pe UCP, acest sistem poate desfura o loterie de 50 de ori pe secunda, fiecare ctigtor primind ca premiu 20 msec de timp alocat pe UCP.

7. Planificare cu pri egale(Fair-Share Scheduling). Unele sisteme iau n considerare i posesorul procesului inainte de planificare. n acest model, fiecare utilizator are alocat o anumit proporie a capacitii UCP, iar planificatorul alege procesele astfel nct s se respecte aceast regula. Astfel dac 2 utilizatori au primit promisiunea c li se va aloca aproximativ 50 % din capacitatea UCP, fiecare va primi exact atat , indiferent de cte procese are.

Algoritmi de planificare utilizati pentru sistemele n timp real. Algoritmii de planificare pentru sistemele de timp real pot fi statici sau dinamici. Primii iau deciziile

de planificare nainte de inceperea rulrii sistemului. Cei din urm iau deciziile in timpul rulrii, adica chiar n momentul apariiei evenimentelor externe. Planificarea statistic funcioneaz numai dac sunt disponibile informaii perfecte apriori despre operaiile ce trebuie efectuate i termenele care trebuie respectate. Algoritmii de planificare dinamic nu au aceste restricii. (Tanembaum, 2001)

Unul dintre algoritmii de planificare n timp real foarte utilizai este algoritmul monotonic. Acesta acord prioriti proceselor proportional cu frecvena de apariie a evenimentului ce declaneaz procesul respectiv. De exemplu, un proces ce este declanat de un eveniment ce apare cu o perioad de 25 ms va primi prioritatea 40, n timp ce un proces ce este declanat cu o perioada de 125 ms va primi prioritatea 8.

Un al doilea algoritm este cel al timpului de rezerva minim. De exemplu, dac un proces are nevoie de 100 ms pentru a fi rulat, iar el trebuie terminat n cel mult 200 ms, atunci sistemul calculeaz timpul de rezerv pe care l are la dispoziie pentru acest proces: 200-100=100 ms. Planificatorul menine o lista a proceselor ordonat dupa acest timp de rezerv si atribuie UCP procesului cu timpul de rezerv cel mai mic.

Alt algoritm de planificare n timp real este algoritmul termenului limita cel mai scurt . Atunci cnd

apare un eveniment extern, procesul care trateaz acel eveniment va fi adaugat la o lista cu procese gata de execuie. Aceast lista este meninut sortat dup termenul limit n care trebuie tratat evenimentul. Procesul cu termenul limita cel mai apropiat va fi primul rulat.

(Dodescu, 2003)

Planificarea user-thread-urilor. n cazul n care mai multe procese au fiecare fire de execuie multiple, exist doua nivele de paralelism: procese si fire. Planificarea n astfel de sisteme este substanial diferit, depinznd de tipul de implementare suportat (n spaiul user, n spaiul kernel, sau ambele). n cazul firelor de execuie implementate n spaiul utilizator, nucleul nu este contient de existena firelor i opereaz n modul obinuit alegnd un proces , pe care l numim A si d procesului controlul pe parcursul cuantei sale de timp. Planificatorul de fire de execuie din interiorul procesului A decide ce fir sa ruleze, s spunem A1. Deoarece nu exist vreo ntrerupere de ceas pentru a multiprograma firele, acest fir poate continua s se execute ct timp doreste. Dac foloseste toata cuanta procesului, nucleul va selecta un alt proces spre execuie. Atunci cnd procesul A ruleaz din nou, firul A1 va rencepe s se execute. Firul ca continua s consume timpul procesului A pna cnd termin. n orice caz, comportamentul su antisocial nu va afecta celelalte procese. Acestea vor obine cuanta considerat potrivit de planificator, indiferent de ce se intampl n interiorul procesului A. Considernd cazul n care firele de execuie ale lui A au relative puin de procesat ntr-o rafal de utilizare a UCP, s spunem 5 msec de lucru ntr-o cuant de 50 msec. n consecin, fiecare ruleaz o perioad scurt de timp, apoi cedeaz UCP planificatorului de fire. Aceast comportare poate duce la secvena A1, A2, A3, A1, A2, A3 ,A1, A2, A3, A1, nainte ca nucleul s comute la procesul B. Aceast situaie este ilustrat n figura urmatoare:

Algoritmul de planificare folosit de executive poate fi oricare din cele descrise mai sus.n practic, cele mai des folosite sunt round i planificarea bazat pe prioriti. Singura constrngere este lipsa unui ceas pentru a ntrerupe un fir de execuie care a rulat prea mult.

Planificarea kernel-thread-urilor. n cazul firelor implementate n nucleu, nucleul alege un anumit fir spre execuie. Nu este nevoie ca nucleul s in seam de procesul cruia i aparine firul, dar poate face acest lucru dac dorete. Firul primeste o cuanta de timp i este suspendat forat dac depaete aceast cuant. Cu o cuant de 50 msec, dar cu fire de execuie care se blocheaz dupa 5 msec, ordinea firelor pentru o perioad de 30 msec ar putea fi A1, B1, A2, B2, A3, B3, ceea ce nu era posibil cu aceeasi parametrii n cazul firelor

implementate n spaiul utilizator. Aceast situaie este ilustrat parial n urmatoarea figur:

Deoarece nucleul tie c a comuta de la un fir al procesului A la un fir al procesului B este mai costisitor dect s ruleze un al doilea fir al lui A ( datorit necesitii schimbrii harii de memorie i stricrii memoriei ascunse), poate lua aceast informaie n considerare atunci cnd ia o decizie. De exemplu, dac lum dou fire care sunt la fel de importante , dintre care unul aparine procesului al crui fir tocmai s-a blocat i cellalt aparinnd unui alt proces, preferinele se ndreapt spre primul fir de execuie.

Avantaje si dezavantaje ale planificrii user-thread-urilor comparativ cu kernel-thread-urilor Performana reprezint o diferen major ntre firele din spaiul utilizator i cele din nucleu.Efectuarea unei comutri de fire n spaiul utilizator este format din cteva instruciuni.n cazul firelor din nucleu, este necesar o comutare de context complet, schimbarea harii de memorie, invalidarea memoriei ascunse, operaia fiind mai lent cu cateva ordine de mrime. Pe de alt parte, n cazul firelor implementate n nucleu, blocarea unui fir la o operaie I/E nu cauzeaz blocarea procesului cum se ntampl n cazul implementrii n spaiul utilizator.

Un alt factor important este acela c firele din spaiul utilizator pot angaja un planificator specific aplicaiei. Dac am considera spre exemplu cazul serverului de web, presupunem c un fir de lucru tocmai s-a blocat i firul de dispecerizare i 2 fire de lucru sunt gata de execuie.Executivul tiind ce poate face fiecare thread, poate s aleag cu uurin firul de dispecerizare, pentru c acesta s porneasc execuia unui alt fir de execuie.Aceast strategie maximizeaz paralelismul ntr-un mediu n care firele de lucru se blocheaz frecvent n memorii de I/E. n cazul firelor implementate n nucleu, nucleul nu ar putea tii niciodata ce a facut fiecare fir (dei acestea ar putea avea prioritai diferite):

CURS 6

Definiti blocajul. deadlock

Un set de procese este blocat daca fiecare process din setul respective asteapta un eveniment care

poate fi cauzat doar de un alt process din acest set. Niciunul din procese nu poate rula, elibera resurse,

sau sa treaca in starea awake.

Ce este o resursa preemptibila?

O resursa care poate fi luata de la procesul care o detine fara efecte nedorite. Memoria este un exemplu

de resursa preemtibila.

Ce este o resurs nonpreemptibila?

Este o resursa care nu poate fi luata de la detinatorul ei fara ca executia acestuia sa esueze. Daca un

process a inceput sa inscriptioneze un cd-rom, de exemplu, si deodata I se ia accesul la unitatea de

inscriptionare si se da altui process, va rezulta un cd cu informative amestecata, fara sens. In general

blocajele sunt non-preemtibile.

Care sunt conditiile de aparitie a unui blocaj?

-excluziune mutual o resursa este fie ocupata de un process, fie este libera

-de detinere-asteptare a unei resurse : un process ce detine resurse poate solicita resurse noi

-nonpreemtivitatii: resursele ocupate nu pot fi retrase fortat unui process.

-de asteptare circular: lantul circular de asteptare este format din cel putin 2 procese, fiecare resursa

solicitata este detinuta de urmatorul process din lantul circular.

Cum se pot modela blocajele?

Cu ajutorul grafurilor orientate. Grafurile au doua tipuri de noduri : procesele, reprezentate prin

cercuri, si resursele, reprezentate prin patrate. Un arc de la un nod tip resursa catre un nod de tip

process arata ca acea resursa a fost ceruta, accesul la ea a fost acordat si ea este in present detinuta de

procesul respectiv.

Caracterizati algoritmul strutului.

Se bazeaza pe prezumtia ca nu exista blocaje. Prezumtia este rezonabila daca blocajele apar foarte rar

sau costul prevenirii blocajelor este mare.Unix si Windows utilizeaza aceasta abordare. Este un

compromise intre comoditate si corectitudine.

Cum se realizeaz detectia si rezolvarea blocajelor?

Cand se foloseste tehnica aceasta , sistemul nu incearca sa previna aparitia blocajelor. In schimb, le

lasa sa apara, incearca sa detecteze cand ele se intampla si apoi sa ia masuri pt recuperare. Poate fi

dentificat un ciclu care denota aparitia unui blocaj. In acest caz, se trece larezolvarea blocajelor :

1.prin preemtiune. Eliberarea unei resurse allocate unui alt process; metoda dependent de natura

resursei; 2. Prin rollback. Marcarea punctelor de executie ale uni process, salvarea starii unui process

si utilizarea ei; restartarea procesului din punctual de executie marcat daca se identifica blocaj. 3.

Oprirea proceselor. Sea mai simpla si eficienta metoda, pp. oprirea proceselor a caror executie poate fi

rulata de la inceput de exemplu nu se opreste un process de actualizare a unei baze de date.

Cum se evita blocajele?

Evitarea permite sistemului intrarea n starea de interblocare i rezolv apoi aceast situaie, reprezentnd de multe ori o soluie destul de dificila i de costisitoare,presupune folosirea de informaii suplimentare referitoare la modul n careprocesele vor formula cererile de acces la resurse.Cunoscnd toat secvena de cereri i eliberari de resurse pentru fiecaredintre procese se poate hotr pentru fiecare cerere n parte dacva fi sau nu satisfcut. n cazul fiecrei formulri de cerere se impune ca sistemul s

ia n considerare resursele disponibile n momentul respectiv, resurselealocate deja, precum

i viitoarele cereri i eliberari de resurse corespunztoare fiecrui proces, pentru a putea decide dac cererea curent poate fi satisfcutsau trebuie s atepte n vederea evitrii apariiei unei interblocri.Pentru implementarea acestei metode se folosesc n prezent mai muli algoritmi care difer ntre ei prin tipul i cantitatea de informaie necesar.

Caracterizati starea sigura si nesigura.

O stare este numita sigura-safe- daca sistemul nu se afla in interblocare in acel moment si exista o

ordine de planificare in care fiecare process poate rula pana la terminare, chiar daca procesele arc ere

deodata numarul lor maxim de resurse.

O stare nesigura nu este o stare in care sistemul se afla in interblocare. Dintr-o astefel de stare nu se

poate garanta faptul ca toate procesele se vor termina, pe cand la cea sigur avem aceasta garantie.

Caracterizati algoritmul bancherului pentru o singura resursa

Un algoritm de planificare care poate evita blocajele este o extensie a lgoritmului de detectare a

blocajelor. Algoritmul este modelat dupa felul in care un bancher dintr-un oras mic gestioneaza un

grup de client carora le-a deschis linii de credit. Acesta verifica daca acceptrea unei cereri va duce

la o stare nesigura.Daca da, cererea este respinsa. Daca cererea duce la o stare sigura, ea este

indeplinita. Algoritmul ia in considereare fiecare cerere pe masura aparitiei ei si se uita daca

acceptarea va duce la o stare sigura. Pentru a verifica asta, verifica daca are suficiente resurse

pentru a satisface cativ client. IN caz ca are, se presupune ca aceste imprumuturi vor fi returnate si

in continuare va fi verificat clientul cel mai apropiat de limita si asa mai departe. Daca toate

imprumuturile pot fi retunate, starea este sigura si cererea initiate va fi acceptata.

Caracterizati algoritmul bancherului pentru resurse multiple.

Cauta pe rand, un R, ale carui nevoi de resurse sunt mai mici sau egale cu A. Daca nu exista niciun

astfel de rand, sistemul se va bloca in cele din durma deoarece niciun process nu va putea relua pana la

terminare. Presupunem ca procesul ales cere toate resursele de care are nevoie si se termina.

Marcheaza acest proces ca fiind terminat si adauga toate resursele in vectorul A. Repeta acesti pasi fie

pana cand toate procesele sunt marcate ca fiind terminate, in acest caz starea initiala este sigura, fie

pana cand aparet un blocaj, caz in care starea initiala este nesigura. Acest algoritm este foarte bine

reliefat in teorie, dar practice este nefolositor deoarece rareori procesle stiu in avans care vor fi nevoile

lor maxime de resurse, iar numarul de procese variaz pe masura ce apar sau dispar utilizatori.

Cum se previn blocajele?

Blocajele se previn cu ajutorula patru conditii. Daca ne asiguram ca cel putin una dintre ele nu va fi

niciodata satisfacuta, atunci este imposibil sa apara blocaje.

1.Combaterea contidiei de excludere mutuala. Daca nicio resursa nu ar fi alocata exclusive pt un

rproces, nu am avea niciodata blocaje. Totusi, daca am permite ca doua procese sa scrie in acelasi timp

s-ar crea haos. Prin introducere in coasa de asteptare(spooling) mai multe rpocese pot genera simultan

date de iesire. Insa, nu toate dispozitivele pot face spooling. Procesele care gestioneaza o actiune, sunt

programate sa actioneze doar dup ace sunt disponibile doate datele de iesire. In acest caz avem doua

procese care au furnizat fiecare o parte din datele de iesire, dar nu toate si de acees nu se poate

continua. Niciunul dintre procese nu se va termina vreodata, asadar avem un blocaj. Totusi frecvent, se

evita alocarea unei resurse cand aceasta nu este absolute necesara si se incearca asigurarea ca vor

exista ca mai putine procese care ar putea cere resursa.

2. Combaterea conditiei de detinere si asteptare. Daca am putea impiedica procesele care detin resurse

sa mai astepte prolucrarea altor resurse, am pute alumina blocajele. Un mod de a face asta este sa le

cerem tuturor proceseloe sa ceara toate resursele inainte de inceperea executiei. Daca totul este

disponbil, procesului ii va fi alocat tot ceea ce ii trebuie si va putea rula pana se va termina. Daca una

sau mai multe resurse sunt ocupate, nu se va aloca nimic si procesul doar va astepta. Un alt mode de

combatere a cond de detinere si asteptare este ca fiecarui process care doreste o resursa sa I s e ceara

sa elibereze temporar toate resursele pe care le detine in present. Apoi va incerca sa ia dintr-o data tot

ce are nevoie.

3.Combaterea lipsei de preeemptie este destul de rar folosita . Daca uni process i-a fost alocata

imprimanta de ex, si se afla in mijlocul tiparirii datelor de iesire, faptul ca I s-ar lua fortat imprimanta

deoarece un trasator cerut nu este disponibil, ar fi derutant sau chiar imposibil.

4. Combaterea conditiei de asteptare circular. Asteptarea circular poate fi eliminate in mai multe

fe;luri. Un mod ar fi sa impunem regula ca orice process are dreptul la o singura resursa la un moment

dat. Daca are nevoie de o a doua, trebuie sa o elibereze pe prima. Pt un proces care are nevoie sa

scoata la imprimanta un fisier urias pe o banda magnetic, aceasta restrictive este inacceptabila. Un at

mod ar fi realizarea unei numerotari globale a resurselor. Regula este urmatoarea : procesele pot cere

resurse oricand vor, dar toate cererile rebuiesc facute in ordinea numerelor. Un process poate cere mai

intai o imprimanta si apoi o banda magnetic, dar nu va putea cere mai intai un trasator si apoi o

imprimanta.Cu aceasta regula, nu pot exista niciodata cilcuri. Desi ordonarea numerica a resurselor

elimiba problema blocajelor, ar putea fi indisponibila alegerea unei ordini in care sa satisfaca pe toata

lumea. Cand resursele include intrari in tabela de procese, spatial de pe disc alocat pt spooling,

intregistrari detinute din baza de date si alte surse, atat ele cat si diverse folosiri pot fi atat de

numeroase a.i. nicio abordare nu mai este posibila.

Explicati si dati exemplu de two-phase blocking.

Desi atat evitarea cat si prevenirea blocajelor nu sunt foarte promitatoare, in multe sisteme de date, o

operatie care apare frecvent este blocarea ccesului ca cateva inregistrari si avoi vizualizarea lor. In

momentul in care exista mai multe procese care ruleaza in acelasi timp exista un real risc de aparitie a

interblocarii. Abordarea folosita este denumita blocarea in doua faze. Aici, procesul incearca mai intai

sa blocheze accesul pe rand la toate inregistrarile de care are nevoie. Dca reusese, incepe faza a doua

in care realizeza actualizarile si apoi blocheaza accesul. In rima faza nu este realizata nicio

modificcare. Daca in prima faza este nevoie de o inregistrare care este dj blocata de altcineva,

procesul deblocheaza toate inregistrarile si reia aceasta etapa. Intr-un anumit sens aceasta abordare

este similara cu cereaza in avans a tuturor resurselor necesar, sau cel putin inainte de a se realize ceva

ireversibil. In ultimele versiuni ale blocarii in doaua faze nu are loc eliberarea si reluarea in cazul in

care prima faza este intalnita cu o resursa dj blocata. In aceste versiuni poate aparea un blocaj.

Algoritmul functioneaza doar in acele situatii in care programatorul are lucrurile aranjate foarte atent

astfel incat programul sa poata fi oprit in orice punct in timpul unei faze si reluat. Multe aplicatii nu

pot fi structurate in acest fel.

Explicati si dati exemplu de comunication deadlock.

Exemplificati notiunea de starvation.

Intr-un system dynamic, au tot timpul loc cereri de resurse. Este necesara o politica pt a stabili cine sa

ia o anumita resursa sic and. Aceasta politica, dei pare rezonabila, poate duce sa ramanerea in asteptare

a unor procee care nu vor fi niciodata luate in considerere, desi ele nu se afla in blocaj. Ca exemplu ,

sa luam alocarea imprimantei. Sa ne imaginam sa un system foloseste un anumit tip de algoritm pt a

se asigura ca alocarea imprmantei nu duce la interblocare. Sa presupunem ca acum exista cateva

procese cre o vor toate deosata. Care o va primii? Un posibil algoritm de alocare este ca ea sa fie data

asta procesului cu fisierul cel mai mic de tiparit . Aceasta abordare maximizeaza numarul clientilor

fericiti. Daca un system aglomerat are un fiesier urias de tiparit, de fiecare data cand imprimanta este

libera, se va uita in jur-sistemul- si va allege procesul cu fisierul cel mai mic. Dca nu exista un flux

constant de procese cu fisiere mici, imprimanta nu-I va fi alocata niciodata procesului cu fisierul

uriam. Pur si simplu acesta va muri de foame(amanat la nesfarsit, chair daca nu e blocat). Infometarea

poate fi evitata prin folosirea unor politici de locare a resurselor de tip primul sosit primul servit. In

aceasta abordare este servit procesul care a asteptat cel mai mult. In timp, fiecare process va devein in

cele din urma cel mai vechi si astfel isi va primi resursa de care are nevoie.

CURS 7

Caracterizati cazul in care utilizam tehnica de multiprogramare pe partitii fixate de memorie.

Cea mai simpla modalitate de a face multiprogramare este de a diviaza memoria in n partitii. Cand un

proces trebuie executat va fi pus in coada de intrare a celei mai mici partitii care este suficient de

mare pt a-l cuprinde. Deoarece partitiile sunt fixe, orice spatiu care nu este folosit de un proces va fi

pierdut. Dezavantajul sortarii proceselor executate in cozi de asteptare devine evident cand o coada pt

o partitie mare este goala iar una pt o partitie mica este plina

Cum se realizeaza translatarea adreselor logice n adrese fizice?

Alocarea spaiului din memoria interna se realizeazn funcie de disponibilitatea memoriein acel moment, fapt care nu permite cunoaterea adreselor reale ocupate de program la momentul execuiei (numite i adrese fizice) n etapele scrierii i translatrii programelor a cror adrese de memorie, sunt simbolice (numiteadrese logice). Translatarea adreselor logice n adrese fizice se realizeazprintr-o funcie de translatare care precede execuia instruciunii respective.Activitatea de gestiune a memoriei are la baz trei algoritmi :1) algoritmul detransfer care determin cnd un bloc trebuie transferat din memoria externn memoria intern- naintea execuiei sau n timpul execuiei;2) algoritmul de plasarecare determin ce zonnealocat din memoria intern este folosit pentru plasarea blocului ncrcat din memoria extern;3) algoritmul dereamplasarecare determin care blocuri i la ce moment trebuie rencrcate n memoria intern.

Cum se realizeaza swapping-ul ? Exista mai multe metode de gestiune a memoriei,dintre acestea metodele cu partitii.In sisteme

multiutilizator cu partajare a timpului, sau in computere care au de indeplinit sarcini consumatoare

de memorie apare problema ca memoria principala nu este suficienta.

Solutia in acest caz este ca o parte din procese sa fie stocate pe hard disk si adus in memoria

principala atunci cand este nevoie. Se folosesc doua strategii generale in acest caz:cea mai simpla,

numita swapping, consta in mutarea proceselor cu totul intre memorie si hard fixe pot fi utile in

cazul unui sistem cu prelucrare pe loturi.

Avantajul la swapping este practic ca partitiile memoriei sunt de marime variabila, in functie de

process si astfel memoria poate fi utilizata mai eficient, principalul dezavantaj insaeste ca se

complica algoritmul de alocare a memoriei.

Dupa folosirea swappingului un timp e posibil sa se creeze mai multe zone de

memorie libera care sa fie prea mici pentru a putea incarca un proces intreg in ele, pentru a rezolva

aceasta problema se poate compactata memoria astfel incat sa avem o singura zona de memorie

libera foarte mare si compacta.

Managementul memoriei utilizand bitmap(harta de biti)

O metoda de gestiune a memoriei in cazul swappingului este cu ajutorul hartilor de biti(bitmaps).

Metoda presupune creerea unei harti in care fiecare bit corespunde unei zone dememorie de

dimensiune fixa, bitul fiind 0 pentru o zona libera si 1 pentru o zona ocupata.

Memoria este impartita in unitati de alocare care pot fi de la cativa octeti pana la cativa KB. Fiecarei

unitati de alocare ii corespunde un bit in harta de biti. Bitul este 0 daca unitatea este libera si 1 daca

este ocupata; (AICI) avem 5 procese cu 3 regiuni libere. Cu cat unitatea de alocare este mai libera, cu

atat harta de biti este mai mare. Totusi, daca unitatea de alocare e de 4 octeti, atunci pentru 32 de biti

de memorie va fi necesar un singur bit in harta. O memorie de 32n biti va necesita o harta de n biti.

Asadar, harta de biti va ocupa doar 1\33 din memorie.

Descrieti cum se realizeaza managementul memoriei utiliznd liste. Utilizarea listelor inlantuite pentru gestiunea memoriei presupune creerea une

liste in care fiecare element se refera la o zona de memorie astfel: zona poate fi

ocupata sau libera, se retine adresa de inceput a zonei si adresa de sfarsit a zonei si un pointer catre

elementele vecine. Lista de obicei este ordonata dupa adrese astfel incat atunci cand trebuie

modificata aceasta sa se faca usor : atunci cand se dezaloca memorie dintr-o zona elementele

corespunzatoare zonelor vecine libere impreuna cu elmentul respectiv se combina formand un nou

element cu adresa de inceput a primului si adresa de final a ultimului si marcat ca liber.

Pentru a aduce un proces din memorie trebuie cautata o zona de memorie

adecvata, pentru aceasta exista mai multi algoritmi cum ar fi first fit (care alege prima zona suficient

de mare pentru a tine procesul respectiv, dupa care la urmatorul process cautarea se face din nou de la

inceput), next fit (alege prima zona suficient de mare, dupa care la urmatorul proces cautarea se face

incepand cu ultima zona unde s-a ajuns), best-fit (se cauta prin toata lista pana se gaseste cea mai mica

zona liberacapabila sa acomodeze procesul respectiv), worst fit (se cauta prin toata lista si se alege cea

mai mare zona libera).

Caracterizati memoria virtuala. Memoria virtual reprezint o metod de organizare a memoriei prin intermediul creia programatorul "vede" un spaiu virtual de adresare foarte mare care este mapat n memoria fizic disponibil, fr ca programatorul s "simt aceasta. Aceasta soluie a aparut din nevoia unui spatiu mare de memorie, pentru programe prea mari pentru a intra in memoria disponibila. Soluia folosit n mod uzual a fost mprireaprogramului respectiv n buci numite overlay. Overlay 0 ncepea s ruleze primul. Atuncicnd acesta termin, chem un alt overlay. Unele sisteme bazate pe overlay erau destul de

complexe permind mai multe overlay-uri n memorie, n acelai timp. Overalay-urile erau inute pe disc i erau schimbate ntre ele n memorie, n mod dinamic, conform cerinelor. Schimbarea efectiva a overlay-urilor si operaia de mprire a programului n buci este fcut de sistem, cu ajutorul memoriei virtuale. Ideea de baz a memoriei virtuale este aceea c mrimea total a programului, a datelor, poate depi mrimea memoriei fizice disponibile pentru acesta. Programul menine prile ce sunt folosite n memorie iar restul prilor sunt inute pe disc. De exemplu, un program de 16 MB poate rula pe un sistem cu 4MB alegnd cu grij care 4MB trebuie s fie meninui n memorie n orice moment, iar prile de care este nevoie se vor schimba ntre disc i memorie. Prin mecanismele de memorie virtual se mrete probabilitatea ca informaia ce se dorete a fi accesat de ctre CPU din spaiul virtual (disc), s se afle n memoria principal, reducndu-se astfel n mod semnificativ timpul de acces de la 10-15 ms (timp acces discuri), la 50-80

ns (timp acces DRAM-uri) n tehnologiile actuale.

Ce reprezinta TLB ?

TLB-uri Translation Lookaside Buffers.

n majoritatea schemelor de paginare tabelele sunt inute n memorie din cauza mrimii lor.Din moment ce viteza de execuie este limitat de rata cu care CPU-ul poate lua instruciuni i date din memorie, faptul c este necesar s se fac referine la tabel pentru dou pagini duce la reducerea performanei.Soluia cu care s-a venit a fost echiparea calculatoarelor cu un dispozitiv hardware mic pentru maparea adreselor virtuale n adrese fizice fr a trece prin tabel. Dispozitivul se numete TLB sau uneori o memorie asociativ, este de obicei n interiorul MMU i este alctuit dintr-un numr mic de intrri, opt n acest exemplu, dar rareori sunt mai mult de 64. Fiecare intrare conine informaii cu privire la o pagin inclusiv numrul paginii virtuale, un bit ce este setat cnd pagina este modificat, codul de protecie (permisii decitire/scriere/executare), i cadrul de paginii fizice n care pagina este situat. Aceste cmpuri au o coresponden unu la unu cu cmpurile din tabelul de pagin.Un alt bit indic dac o intrare este valid sau nu. Atunci cnd o adres virtual este prezentat la MMU pentru translaie, hardware-ul verific mai nti s vad dac numrul paginii virtuale este presetat n TLB comparndu-l simultan cu toate intrrile (n paralel). Dac se gsete o pereche valid i accesul nu ncalc biii de protecie cadrul paginii este luat din TLB, fr a mai merge la tabel. Dac numrul paginii virtual este prezent n TLB dar instruciunea ncearc s scrie pe o pagin ce nu poate fi scris, o eroare de proteci este generat, la fel cum s-ar fi ntmplat i din tabel.

Prezentati algoritmii de inlocuire a paginilor.

OPTIMAL. Fiecare pagin se eticheteaz cu numrul de instruciuni ce se vor executa pn cnd este referit pagina pentru prima dat. Atunci cnd trebuie eliminat o pagin din memorie, se selecteaz pagina cu cea mai mare valoare a etichetei. Dei acest algoritm genereaz cea mai mic rat de pagini invalidate, el nu poate fi implementat, deoarece sistemul de operare nu poate determina cnd urmeaz s fie referit o pagin. Acest algoritm este utilizat doar pentru studii comparative. De exemplu, pentru un algoritm care nu este optimal, este util de tiut c are performane cu 12% mai slabe dect cele optimal.

NRU. Pentru fiecare pagin existent n memorie, intrarea corespunztoare din tabela paginilor conine doi bii de stare: R i M: bitul R este pus pe 1 ori de cte ori pagina este referit (n citire sau scriere), bitul M devine 1 atunci cnd pagina este modificat. Aceti biii trebuie actualizai la fiecare referire a memoriei. Dac un bit devine 1, el rmne pe aceeai valoare pn cnd este resetat explicit de ctre sistemul de operare. La prima intrarea n execuie a unui proces, biii R i M asociai paginilor ce aparin procesului sunt pui pe 0 de ctre sistemul de operare. Periodic (ex. la fiecare ntrerupere de ceas) bitul R este pus pe 0 pentru a putea face distincie ntre paginile care nu au fost referite recent i cele care au fost referite. n momentul generrii unei ntreruperi de pagin invalid de operare inspecteaz toate paginile i le mparte n 4 categorii pe baza valorilor biilor R i M. Clasa 0: nereferit, nemodificatClasa 1: nereferit, modificatClasa 2: referit, nemodificatClasa 3: referit, modificatPagina care va fi eliminat din memorie este selectat aleator din clasa nevid avnd cel mai mic indice.

FIFO.Acest algoritm asociaz fiecare pagini momentul la care a fost adus n memorie. Cnd se pune problema nlocuirii unei pagini se selecteaz pagina cea mai veche. Nu mai trebuie memorat momentul la care o pagin este adus n memorie dac sistemul de operare menine o list nlnuit a paginilor din memorie, pagina din capul listei fiind cea mai veche, iar cea de la sfritul listei fiind cea mai nou. Pagina eliminat din memorie va fi pagina din capul listei, iar atunci cnd se aduce n memorie o pagin ea va fi nserat la sfritul listei.

SECOND CHANCE ALGORITHM.Folosind algoritmul FIFO exist posibilitatea de a elimina din memoriei o pagin utilizat intens. Eliminarea unei astfel de pagini va conduce doar la creterea ratei de pagini invalide. Pentru a evita o astfel de problem se poate modifica algoritmi FIFO astfel nct s se verifice bitul R al celei mai vechi pagini. Dac R este 0 pagina este veche i neutilizat, deci va fi nlocuit imediat. Dac R este 1, se reseteaz bitul R, pagina este mutat la sfritul listei i procesul de cutare continu. Aceast variant modificat a algoritmului FIFO este denumit algoritmul celei de a doua anse. Acest algoritm caut o pagin veche care nu a fost referit n perioada anterioar de ceas.

LAST RECENTLY USED. Este o aproximare bun a algoritmului optimal i se bazeaz pe observaia c paginile care au fost utilizate intens n ultimele cteva instruciuni vor fi, probabil, utilizate intens i n urmtoarele cteva instruciuni. Aceste observaii sugereaz c atunci cnd se refer o pagin inexistent n memorie se va nlocui pagina care a fost neutilizat cel mai mult timp. Algoritmul LRU poate fi implementat n 2 moduri: a) cu ajutorul unei liste nlnuite a tuturor paginilor din memorie. n capul listei sunt plasate pagini referite recent, iar la sfritul listei se gsesc pagini nereferite de mult timp. La fiecare referire a unei pagini din memorie ea trebuie cutat n list i mutat n capul listei. n cazul n care trebuie eliminat o pagin din memorie se va alege ultima pagin din list. b) cu ajutorul unui contor C (contor hardware) care este incrementat dup fiecare instruciune. Fiecare intrare din tabela paginilor trebuie s dein un cmp n care s se poat stoca valoarea contorului C. Dup fiecare referire la memorie, valoarea curent a lui C se stocheaz n intrarea din tabela paginii corespunztoare paginii referite. La o ntrerupere de pagin invalid se va selecta pagina din memorie avnd cea mai micvaloare a contorului C (care a fost neutilizat cel mai mult timp).

Care este diferenta dintre o adresa fizica si una virtuala?

CURS 8

Probleme de proiectare a sistemelor cu paginare Alocare global vs alocare local. Cnd un proces declanseaz un page fault (pagina accesat nu se gsete n memoria principal), un algoritm de alocare local a paginilor seleceaz pentru nlocuire o pagin care aparine acelui proces (sau un grup de procese care mpart aceeai partiie de memorie). Algoritmul de alocare global a paginilor poate selecta orice pagin din memorie pentru nlocuire.

Alocarea local a paginilor presupune existena unei partiionri a memoriei care s determine cte pagini sunt alocate unui proces sau unui grup de procese. In general, algoritmii de alocare global sunt mai eficieni dect cei de alocare local, mai ales cnd dimensiunea setului n lucru variaz pe toat durata procesului. Daca se folosete un algoritm pentru alocare local, iar dimeniunea setului n lucru crete, va rezulta thrashing-ul. Daca dimeniunea setului scade, algoritmii locali folosesc memoria n mod

ineficient. Pentru un algoritm de alocare global, sistemul trebuie s decid mereu cte pagini s aloce pentru fiecare proces. O metod este de a monitoriza dimensiunea setului n lucru cu ajutorul biilor de vrst, dar n acest caz nu se poate spune cu certitudine dac nu va rezulta thrashing-ul. Dimeniunea setului se poate modifica n cteva microsecunde, pe cnd biii de vrst dureaz cteva tacturi de ceas. O alt metod este existena unui algoritm care s aloce pagini proceselor n lucru. Se determin numarul proceselor n lucru i se aloc pentru fiecare un numr egal de pagini. La folosirea unui algoritm de alocare global, este posibil s alocm pentru nceput un numr de pagini proporional cu dimensiunea procesului, dar alocarea trebuie updatat pe msur ce procesele se execut. Astfel se folosete algoritmul frecvenei page fault-urilor (PFF page fault frequency), care stabilete cnd s se mreasc sau s scad numrul de pagini alocate unui proces. Acest algoritm nu d nici o informaie asupra crei pagini sa fie nlocuit cnd apare un fault, ci doar controleaz dimensiunea setului alocat. Controlul alocrii paginilor Chiar dac se folosesc cei mai buni algoritmi de alocare a paginilor, se poate ntmpla s rezulte tharshing-ul. De fapt, de fiecare dat cnd suma tuturor seturile n lucru ale proceselor este mai mare dect capacitatea memoriei, rezulta thrashing-ul.

Acest lucru se poate observa atunci cnd algoritmul PFF indic existena unui proces care are nevoie de mai mult memorie, dar nici un proces nu are nevoie de mai puin memorie. Situaia n care se ajunge este destul de delicat: nu se poate aloca memorie n plus procesului care are nevoie, deoarece nu avem de unde. Trebuie s scpm temporar de anumite procese. Singura metod pentru a realiza acestu lucru, fr a termina forat procese, este s le mutm pe disc (swap). Astfel, paginile rmase libere de la procesle mutate vor fi acum alocate proceselor care au mai mult nevoie de memorie. Dimensiunea paginilor

Dimensiunea paginilor este de obicei determinat de arhitectura procesorului. Un sistem cu dimensiune mic a paginilor utilizeaz mai multe pagini, astfel c tabela de pagini (page table), care este utilizat pentru a face legtura ntre adresele virtuale i adresele fizice, va ocupa mai mult spaiu. Pentru a face legtura ntre adresele fizice si adresele virtuale, procesoarele au nevoie de o tabela speciala, numita Translation Lookaside Buffer, sau TLB, care este

consultata la fiecare acces de memorie. TLB nu are o dimensiune fix, iar cnd nu poate completa cerere de adres (TLB miss), tabelele de pagini trebuie cautate manual (hardware or software), pentru a se gasi adresa cautat. Daca dimensiunea paginilor este mare, atunci tabela TLB poate memora mai multe legturi ntre adresele virtuale si adresele fizice, evitndu-se astfel acele TLB misses, mari consumatoare de timp.

Rareori se ntmpl ca un proces sa aib nevoie de un numr fix (ntreg) de pagini.

Astfel, ultima pagin va fi parial ocupat, restul de memorie neocupat din acea pagin neputnd fi utilizat. Astfel, dimensiunea mare a paginilor va crete probabilitatea ca poriuni mari din memorie s nu poat fi utilizate. Dimensiunea mic a paginilor asigur o mai bun egalitate ntre dimensiunea memoriei si dimensiunea total a proceselor. Spaiul datelor i spaiul instruciunilor Instruciunile i datele ocup spaii de adrese dif