Sisteme de operare

Sisteme de operare

Structura si incarcarea unui sistem de operare

Asa dupa am prezentat la inceputul acestui capitol, uin sistem de operare reprezinta un set de proceduri (subprograme sau rutine) manuale si automate, care joaca rolul de interfata intre programele utilizator si calculator, avand ca obiectiv optimizarea utilizarii resurselor fizice si logice ale sistemului de calcul. Resursele fizice sunt reprezentate de unitatea centrala de prelucrare, memorii si dispozitivele periferice. Cele logice sunt reprezentate de sistemul de gestiune al fisierelor pe suportii de memorii externe si de gestiunea si executia proceselor.

Componenta sistemului de operare care defineste modul de interactiune dintre sistemul de operare si utilizator poarta numele de interfata.

Nucleul unui sistem de operare contine acele module software care efectueaza operatiile primare necesare gestiunii resurselor fizice si logice si deci functionarii calculatorului. In general, aceste module sunt:

administratorul de fisiere (resurse logice) - stocheaza informatii referitoare la toate fisierele memorate pe un suport de stocare de masa (pozitiile fisierelor, spatiul ocupat, utilizatorii cu drept de acces la ele) si ce portiune din memoria de masa este disponibila pentru stocarea de noi fisiere sau extinderea celor existente. Acest modul administreaza toata componenta de organizare logica a informatiei pe suportii de memorie externa;

administratorul de memorie (resursa fizica) - are sarcina de a coordona utilizarea memoriei interne (principale) a unui sistem de calcul;

administratorul de procese (procesul - resursa logica), cu cele doua componente ale sale:

secventiatorul (scheduler)- are rolul de gestiune a proceselor active;

executorul (dispatcher) - are rolul de coordonare a derularii proceselor active;

driver-ele pentru dispozitivele periferice (resurse fizice) - comunica cu controlerele (placile de extensie) pentru efectuarea operatiilor de catre dispozitivele periferice ale sistemului de calcul. Fiecare driver este proiectat in mod specific, pentru un anumit tip de placa de extensie si traduce cererile formulate in termeni generali, de alte componente ale sistemului de operare, intr-o secventa de instructiuni specifice dispozitivului periferic atasat. De exemplu, pentru un disc, un driver poate converti o cerere generala de scriere a unei portiuni dintr-un fisier, in instructiuni care se refera la pistele si sectoarele discului (utilizand informatii furnizate de administratorul de fisiere), transmitandu-le apoi controler-ului corespunzator discului;

Sistemele de operare sunt rezidente pe un suport de memorie externe (in general, disc), atunci cand calculatorul nu este alimentat cu tensiune. In exploatare curenta, majoritatea componentelor sale trebuie sa fie in memoria interna. Procesul de aducerea in memoria interna a componentelor unui sistem de operare poarta numele de incarcare (booting) a sistemului de operare si se realizeaza imediat dupa ce calculatorul este alimentat cu tensiune.

Unitatea Centrala de Prelucrare (CPU) este astfel realizata incat, la pornirea calculatorului, registrul PC (Program Counter) contine intotdeauna adresa unui program numit de incarcare (program de bootstrap) care se afla inscriptionat intr-o zona de memorie ROM, din memoria interna a calculatorului. Acest program, prin lansarea sa in executie, citeste din blocul de incarcare (blocul de boot) de pe discul sistem (disc ce contine un sistem de operare), adresa de pe disc la care se gasesc componentele sistemului de operare, acestea urmand sa fie incarcate in memoria interna.

Blocul de incarcare, este un bloc (sector) de date cu regim special ce se afla pe orice disc, avand o adresa prestabilita. Acest bloc contine adresa de pe disc a sistemului de operare, in cazul in care acesta exista.

3.3.2. Evolutia sistemelor de operare

In acest paragraf vom parcurge pe scurt evolutia sistemelor de operare din punctul de vedere al utilizatorului, evolutie legata de cele doua componente de baza ale unui sistem de operare interfata si nucleul.

Initial sistemele de operare impuneau o activitate laborioasa de executie a programalor: exista o prima faza de pregatire a echipamentelor (incarcare benzi magnetice, plasarea cartelelor perforate in cititorul de cartele, etc), dupa care urma executia propriu-zisa a unui program. Din aceasta cauza executia fiecarui program era tratata ca o activitate izolata, denumita job. Utilizatorul era in acest caz chiar programatorul. De asemenea, exista o lista de utilizatori in asteptare. Etapa poate fi caracterizata prin interfata: limbaj de comanda simplificat, nucleu: utilizare secvential a calculatorului (monoprogramare).

O noua etapa este marcata de introducerea unui operator interpus intre utilizatorul prupriu-zis si calculator. Operatorul preia toate operatiunile pregatitoare realizate de utilizator in faza anterioara. Acesta a fost inceputul prelucrarii in loturi (batch processing - executarea lucrarilor prin plasarea lor intr-un grup unic si apoi reluarea lor fara o alat interactiune cu utilizatorul). Etapa este caracterizata prin dezvoltarea interfetei sistemului de operare si o utilizare tot secventiala a calculatorului prin prelucrare in loturi.

Urmatoarea faza de dezvoltare a sistemelor de opeare isi propune o mai eficienta utilizare a unitatii centrale de prelucrare (CPU). Pentru aceasta se trece la utilizarea CPU simultan de catre mai multe programe, aparand asa-numita multiprogramare. In aceste conditii apar mai multi utilizatori, aparent simultani, ai aceluiasi calculator. Pentru a se obtine timpi de executie relativ un 12312y2411m iform distribuiti pentru toti utilizatorii, multiprogramarea este insotita de partajarea timpului de ocupare a CPU.

Un dezavantaj al metodei clasice de prelucrare in loturi este acela ca o lucrare o data introdusa intr-un lot de job-uri, utilizatorul nu mai poate interveni asupra ei. Acest fapt a determinat dezvoltarea sistemelor de operare in directia creerii facilitatilor de prelucrare interactiva a lucrarilor. Aceste sisteme de operare permit realizarea unui dialog intre utilizatorul propriu-zis si program in timpul executiei acestuia. Prelucrarea interactiva permite aparitia in timp a conceptului de prelucrare in timp real. In acest caz, activitatile ce se desfasoara in calculator sunt corelate strict cu activitatile din mediul caruia apartine calculatorul.

In etapele de evolutie a sistemelor de operare prezentate, modificarile aparute au fost legate in special de nucleul sistemelor de operare. Trebuie precizat faptul ca si componenta reprezentand interfata a evoluat. In prima faza limbajul de comanda corespunzator interfetelor a devenit tot mai complex. Ulterior, majoritatea interfetelor sistemelor de operare au devenit interfete de tip Graphical User Interface (GUI), in care obiectele care trebuie manipulate, cum ar fi fisierele sau programele, sunt reprezentate grafic pe ecranul calculatorului prin pictograme. Unele sisteme de operare pot avea mai multe tipuri de interfete (limbaj de comanda sau grafice). Este cazul sistemelor de operare UNIX sau DOS. De exemplu, sistemul de operare DOS avea la un moment dat trei tipuri de interfete: cea standard - limbaj de comanda, Norton-ul interfata semigrafica si Windows-ul interfata grafica. Referitor la interfetele grafice, trebuie precizat faptul ca exista o tendinta de uniformizare a acestora (standardizare este prea mult spus). Astfel, tipul de ferestre utilizate in Windows si impuse de Microsoft, tind sa se impuna cel putin din punctul de vedere al functionalitatii (micsorare/marire, inchidere fereastra, scroll vertical si orizontal).

In ultimii ani ideea de a partaja informatiile si resursele unui sistem de calcul a condus la ideea conectarii calculatoarelor. Apar astfel retelele de calculatoare, calculatorul central de putere care deserveste mai multi utilizatori cadand locul conceptului in care mai multe calculatoare mici sunt conectate intr-o retea prin care utilizatorii partajeaza resursele si informatiile. Se poate spune ca software-ul de retea reprezinta o extensie naturala a domeniului sistemelor de operare.

O alta etapade dezvoltare a sistemelor de operare a fost impusa de aparitia CPU multiprocesor. Un sistem de operare corespunzator unui astfel de CPU trebuie sa coordoneze nu numai competitia dintre diferitele activitati concurente, ci sa controleze si alocarea activitatilor catre procesoarele din sistem. Aceasta activitate implica probleme de echilibrarea incarcarii (asigurarea utilizarii eficiente a tuturor procesoarelor) precum si de scalare (spargerea activitailor intr-un numar de operatii corspunzator numarului de procesoare din sistem).

Majoritatea caracteristicilor nucleelor sistemelor de operare, care au marcat etape importante in evolutia acestora vor fi prezentate detaliat in paragrafele urmatoare.

Procese gestionate de sistemul de operare

Pentru intelegerea functionarii unui sistem de operare este importanta intelegrea diferentei intre un program si un proces (sau altfel spuns, trebuie inteles ce este un proces). In timp ce un program reprezinta o secventa statica de instructiuni, un proces reprezinta starea la un moment dat a unui program aflat in executie. De exemplu, intr-un sistem multiutilizator cu partajarea timpului, doi utilizatori pot sa editeze simultan documente diferite. Ambele activitati pot utiliza acelasi program, dar fiecare dintre ele va constitui un proces distinct, avand propriile seturi de date.

Atributele unui proces sunt constituite de coordonatele ce caracterizeaza starea unui program la un moment dat. Acestea sunt reprezentate de:

registrul special PC (program counter) - caracterizeaza starea de evolutie a unui proces;

continutul registrilor generali;

adresa zonei de date specifice procesului, in memoria interna (valoare constanta);

adresa zonei de cod specifice procesului, in memoria interna (valoare constanta);

prioritatea procesului (valoarea constanta - in general);

starea curenta a procesului, etc.

Procesele sunt gestionate de administratorul de procese prin cele doua componente ale sale secventiatorul (scheduler-ul) si executorul (dispatcher-ul).

Secventiatorul gestioneaza lista cu toate procesele, in aceasta lista fiind evidentiate si atributele specifice fiecarui proces activ. Un proces activ este declansat de lansarea in executie a unui program.

Executorul asigura executia proceselor active si asigura trecerea de la un proces activ la un altul, prin salvarea contextului specific procesului intrerupt/blocat, si respectiv restaurarea contextului specific procesului reluat in executie din intrerupere/blocare. Contextul unui proces estereprezentat de atributele sale care nu sunt constante (de ex. valoarea registrului special PC, continutul registrilor generali, starea procesului).

Un proces poate avea patru stari distincte:

in executie - procesul se executa;

blocat - procesul lanseaza o cerere, de exemplu o operatie de intrare/iesire si se blocheaza pana la terminarea ei;

gata de executie - procesul este gata pentru a fi luat sau reluat in executie. Reluarea survine dupa o blocare sau intrerupere a sa;

executat complet - procesul este executat in intregime, urmand a fi scos din evidentele administratorului de procese;

In figura de mai sus sunt prezentate cele patru stari distincte ale unui proces (prin cercuri) si actiunile ce determina trecerea unui proces dintr-o stare in alta (prin dreptunghiuri).

Exista doua modalitati de planificare a proceselor:

planificare secventiala - acest mod determina de procese secventiale. In aceasta situatie, im momentul blocarii unui procesului astfel planificat, CPU-ul care-l realizeaza estenefolosit pana la deblocarea procesului, ceea ce implica o utilizare ineficienta a CPU. Utilizarea planificarii secventiale a programelor la nivelul CPU, s-a ,aterializat im monoprogramare;

planificare concurenta - acest mod determina aparitia de procese paralele (concurente), avand ca efect cresterea substantiala a coeficientului de utilizare al CPU (nu mai apar timpi morti in cazul blocarii unui proces in urma lansarii unei cereri). Utilizarea proceselor concurente la nivelul CPU a determinat aparitia multiprogramarii.

Avand ca obiect principal optimizarea randamentului CPU, multiprogramarea nu amelioreaza in orice situatie serviciile aduse utilizatorilor. Astfel, daca un program necesita un numar redus de operatii de intrare/iesire, din momentul in care acesta castiga CPU - procesul intra in starea de executie, celelalte procese active intr in starea de blocare pana la terminarea procesului aflat in stare activa. La nivelul utilizatorilor acest mod de lucru lasa impresia ca numai unul dintre ei este "servit" de calculator. Acest neajuns se inlatura prin tehnica partajarii timpului time-sharing): fiecare proces poate fi in stare de "executie" cel mult o cuanta de timp, dupa care este intrerupt si trecut in stare de "gata de executie", alt proces din lista de procese active trecand in starea de "executie". Cuantele de timp acordate proceselor pentru starea de "executie" sunt egale, in conditiile in care procesele au aceeasi prioritate.

In paragraful urmator vom prezenta numai problematica ridicata de procesele concurente, planificarea secventiala a acestora nemaiprezentand interes.

Procese concurente

Trecerea de la un proces la altul (Intreruperi)

In cazul planificarii concurente a proceselor, este esential de inteles modul de functionare in intreruperi al unui calculator si implicit al CPU, care coordoneaza intraga activitate.

Ce sunt intreruperile? In functionarea unui calculator pot apare evenimente de genul terminarea cuantei de timp pentru un proces care a fost in starea de "executie", lansarea unei cereri de catre un proces si intrarea sa in "blocare" sau terminarea executarii cererii lansate de un proces, care trebuie sa se materializeze in trecerea procesului din starea de "blocare", in cea de "gata de executie". Pe langa aceste evenimente mai sunt evident si altele (trecerea unui proces in stare "executie completa", aparitia unui nou proces, etc). In concluzie, se poate spune ca intreruperile sunt evenimente din activitatea unui calculator, care trebuie cunoscute de unitatea de comanda din CPU.

Intreruperile sunt administrate de CPU care contine, pe langa cele doua componente prezentate in paragraful 3.5 si alte componente printre care unitatea de control intreruperi (UCI). Aceasta componenta contine circuitele necesare pentru gestiunea si memorarea temporara a semnalelor de intreruperi generate la producerea unor evenimente de genul celor mentionate anterior. Fiecarui tip de intrerupere, ii corespunde o rutina de tratare. Existand mai multe tipuri de intreruperi, rezulta ca un calculator contine intr-o zona a memoriei sale interne un setul de rutine de tratare intreruperi. De exmplu la un PC, asocierea intre tipul intreruperii si rutina de tratare a acesteia, se face prin tabelul de vectori de intreruperi, care contine pentru fiecare tip de intrerupere adresa rutinei de tratare corespunzatoare.

In raport cu procesul aflat in stare de "executie", intreruperile se clasifica in:

intreruperi externe - aparitia lor este independenta de procesul aflat in stare de "executie" si sunt luate in evidenta de UCI. Aceste intreruperi pot fi mascabile sau nemascabile (in cazul unei intreruperi mascabile, se poate forta functie de context, sa nu se tina cont de ea). Intreruperi nemascabile sunt de obicei cele care semnaleaza probleme in hardware-ul sistemului de calcul;

intreruperi interne - aparitia lor este determinata de procesul aflat in stare de "executie" si nu sunt luate in evidenta de UCI, ele aplicandu-se direct de catre unitatea de control (UC) din CPU. Ele pot fi generate automat de UC in conditii predefinite (erori de program, executia pas cu pas a programului cu ajutorul depanatorului de programe) sau pot fi generate de programator prin instructiuni speciale de intreruperi.

Prelucrarea unei intreruperi inseamna suspendarea executiei procesului aflat in stare de "executie" si salvarea contextului acestuia, in vederea reluarii executiei sale. Atentie, intreruperea procesului nu inseamna intreruperea ciclului masina in care se afla procesul la momentul respectiv. Intreruperea se va produce numai dupa terminarea ciclului extragere-decodificare-executie aflat in derulare. Dupa realizarea intreruperii si salvarea contextului procesului, se executa rutina corespunzatoare intreruperii respective si in final, daca este cazul se reia executia procesului intrerupt, reluarea fiind precedata de restaurarea contextului corespunzator acestuia. In prelucrarea intreruperilor este implicat administratorul de procese prin executor (dispatcher). Activitatea acestuia determina si actualizarea tabelelor de gestiune procese ale secventiatorului.

Urmatorul desen isi propune sa prezinte componentele unui proces aflate la un moment dat in memoria interna a calculatorului. In acest scop, mai sunt necesare cateva notiuni. CPU din punct de vedere software poate avea doua stari distincte:

starea sistem (numita si Kernel) - caz in care procesul aflat in executie are acces la baza de date a sistemului de operare pentru consultare si modificare;

starea utilizator - caz in care accesul anterior mentionat nu este permis.

Probleme cauzate de procese concurente

Problemele sunt cauzate de faptul ca procesele folosesc aceleasi resurse fizice si logice, pentru care concura in a si le aloca.

O astfel de problema poate fi intalnita cand o resursa este solicitata de mai multe procese. De exemplu, mai multe procese doresc sa scrie in acelasi fisier sau mai multe procese solicita scrierea la imprimanta. O solutie pentru rezolvarea problemei este excludere mutuala intre procese - atat timp cat o resursa este alocata unui proces, aceasta nu mai poate fi alocata altuia. Pentru implementarea solutiei se poate utiliza un indicator (un bit sau o variabila booleana) care se mentine setat cat resursa e ocupata. Implementarea unui astfel de indicator trebuie facuta cu atentie, intrucat se poate ajunge usor in situatii in care excluderea mutuala sa nu functioneze. De exemplu, in cazul unei implementari extrem de simpliste a acestei solutii, se poate ajunge la situatia in care un proces P1 solicitant al resursei, sa fie intrerupt exact dupa momentul in care acesta a constatat ca resursa este disponibila. Intra in executie procesul P2 care solicita si el aceasi resursa, o gaseste nealocata si si-o aloca. In momentul in care procesul P1 reintra in executia isi aloca si el resursa, intrucat tocmai inainte de intrerupere constatatse ca aceasta nu este alocata. Rezulta, ca P1 si P2 nu s-au exclus reciproc.

Exista mai multe tehnici utilizate la implementarea corecta a indicatorului pentru excluderea mutuala a alocarii unei resurse:

Existenta unei instructiuni complexe de testare-setare indicator in setul de instructiuni cod masina;

Existenta unor instructiuni de invalidare/validare intreruperi care sa fie utilizate cat dureaza zona critica a codului (zona de cod critica este in acest caz de la testarea alocarii resursei si pana la instructiunea de alocare a acesteia);

O implementare mai complexa a acestui indicator este mecanismul de semafor. Un semafor este un ansamblu format dintr-o variabila "s", cu valori intregi, o lista de procese Q(s) si doua operatii primitive P si V. V(s) mareste valoarea argumentului "s" cu o unitate, iar P(s) micsoreaza valoarea argumentului "s" cu o unitate, numai daca valoarea argumentului ramane pozitiva, altfel operatia fiind intarziata pana cand conditia este indeplinita:

P(s) => s = s - 1

s < 0  => procesul se blocheaza si este introdus in Q(s);

s >= 0 => procesul se executa;

V(s) => s = s + 1

s < 0 => alege un proces din Q(s) si il activeaza;

s >= 0 => nu face nimic

Pentru a intelege mai bine titulatura mecanismului, primitiva P(s) poate fi echivalata cu sosirea la semafor. Daca acesta este rosu (s < 0), se asteapta culoarea verde in coada Q(s), daca se poate trece. Primitiva V(s) este echivalenta cu punerea pe culoarea verde a semaforului. Daca exista procese in coada Q(s), acestea pot trecem insa numai cate unul.

Se mai poate face o analogie intre acest mecanism de semafor si relatie producator - consumator. Consumatorul este reprezentat de primitiva P(s), iar producatorul de primitiva V(s).

Chiar daca excluderea mutuala a resurselor este corect implementata, in conditiile in care mai multe resurse sunt solicitate de mai multe procese la momente diferite de timp, pot apare interblocari fara iesire (asa-numitul deadlock). De exemplu, procesul P1 are alocata resursa R1 de la momentul T1 si are nevoie de ea pana la momentul T5. Similar, procesul P2 are alocata resursa R2 de la momentul T2 si are nevoie de ea pana la momentul T6. Pe parcursul de rularii proceselor, presupunem ca procesul P1 are nevoie de resursa R2 la momentul T3, iar procesul P2 are nevoie de resursa R1 la momentul T4. Rezulta o situatie fara iesire, ambele procese asteptand eliberarea resursei necesare, care este alocata celuilalt proces.

Situatia de interblocare a proceselor poate apare in una din urmatoarele conditii:

a - competitia este pentru resurse ce nu pot fi partajate;

b - resursele sunt solicitate la momente diferite de timp de catre procese;

c - o resursa odata alocata nu se poate forta dezalocarea sa;

Situatia de interblocare se evita prin eliminarea celor trei conditii anterior mentionate:

Eliminarea conditiei c: nu se fac eforturi pentru a se evita deadlock-ul, ci doar pentru a se constata. La constatare se omoara procesele cel mai putin evoluate;

Eliminare conditii a si b - evitare interblocare:

o modalitate este reprezentata de alocarea odata a tuturor resurselor de catre un proces (aceasta metoda poate crea uneori complicatii in programarea procesului sau chiar nu se poate folosi);

se cauta o cale de transformare a resurselor nepartajabile in resurse partajabile. Un exemplu in acest sens il constituie tehnica spooling folosita la scrierea la imprimanta. De exemplu, cand imprimanta este alocata unui proces care o foloseste efectiv, celelalte procese care cer atasarea resursei in acest interval, vor lista pe o imprimanta virtuala, reprezentata practic de un fisier pe disc. In momentul in care imprimanta devine disponibila fisierele continand liste, sunt scoase la imprimanta.

Comunicarea intre procese

Comunicarea intre procese reprezinta o necesitate pentru sistemele informatice evoluate. Exista mai multe modalitati de realizare:

Sincronizarea prin indicatoare -a fost deja discutata ca modalitate de excliudere mutuala a proceselor. Reprezinta cea mai simpla forma de comunicare intre procese, comunicarea facandu-se fara schimb de informatie;

Comunicarea prin fisiere - reprezinta o modalitate simpla de comunicare, dar periculoasa datorita problemelor ce apar la scrierea concurenta in fisiere. In general sistemele de operare (componenta de administrare fisiere) nu ofera un mecanism de protectie in acest sens. Utilizatorul poate sa-si creeze unul, dar e foarte complicat. Un mecanism simplu care rezolva aceasta problema, fara prea mare eficienta insa, este utilizarea fisierelor de tip pipeline (conducta). Sunt fisiere in care scrierea si citirea se fac FIFO;

Comunicarea prin zone de memorie comuna - permite utilizarea in comun de catre mai multe procese a unei zone de memorie interna, prin maparea (proiectarea) in acest spatiu comun a unei zone din spatiul de adresa propriu fiecarui proces. De obicei accesul la aceasta zona nu e controlat de sistemul de operare, violarea spatiului afectat zonei comune de memorie intrand in responsabilitatea utilizatorului. Zonele de memorie partajate intre procese pot fi de date sau de cod. Ex biblioteci partajate de cod, asa-numitele dll-uri din Windows (dynamic library link);

Comunicarea prin cozi de mesaje - principiul consta in comunicarea prin intermediul unei cozi circulare de mesaje, gestionata de SO. Mesajele au fie un proces fixat explicit drept destinatar, fie respecta o structura de tipuri de mesaje, selectia pentru destiantie facandu-se in baza tipului (ex Windows);

Proliferarea proceselor prin generarea de procese fiu de catre un proces tata - aceasta proliferare e specifica SO evoluate Transferul de informatii are loc in urmatorul sens: fiul primeste informatii de la tata la crearea sa si la randul sau, fiul returneaza informatii tatului la incheiere. Evolutia procesului fiu poate fi cu sau fara blocare procesului tata.

La incheierea acestui paragraf consideram ca trebuie subliniat faptul ca procesele sunt gestionate administratorul de procese din nucleul sistemului de operare, prin componentele sale secventiator si executor, care de fapt gestioneaza soft resursa fizica CPU.

Tehnici de alocare a memoriei interne

Alocarea continua

Este cea mai simpla forma de gestiune a memoriei interne (MI), fiind utilizata la sistemele de operare cu monoprogramare la nivelul CPU.

Avantajele metodei constau in simplitate, care aduce dupa sine intelegerea si utilizarea usoara a unui astfel de sistem de operare. Tot la avantaje intra si faptul ca sistemul de operare este foarte restrans, ocupand un spatiu de memorie mic.

Dezavantajele constau in cele implicate de utilizarea monoprogramarii, la care se adauga si utilizarea ineficienta a memoriei interne, datorita zonei libere ramase dupa programul utilizator.

Alocarea partitionata

Este cea mai simpla tehnica de gestiune a memoriei interne pentru sistemele de operare ce permit multiprogramare la nivelul CPU. Memoria interna este divizata in zone separate de memorie, numite si partitii, fiecare dintre ele putand gazdui un program utilizator distinct.

Cei mai cunoscuti algoritmi software pentru realizarea alocarii partitiilor catre programele utilizator sunt:

partitionarea statica - consta in divizarea MI in partitii fixe ca dimensiune, inaintea lansarii in executie a programelor. Principalul avantaj al algoritmului consta in faptul ca permite o implementare simpla a multiprogramarii. Dezavantajele sunt insa mai mari:

utilizare ineficienta a memoriei interne;

inainte de alegerea dimensiunilor partitiilor trebuie facuta o analiza a dimesiunilor programelor ce urmeaza a fi rulate pentru a dimensiona corect partitiile fixe. Acest dezavantaj determina un imobilism in utilizarea acestui algoritm de alocare a MI, deoarece este putin probabil ca la un numar mai mare de programe ce urmeaza a fi rulate in timp, sa nu fie nevoie de o redimensionare a partitiilor fixe.

partitionarea dinamica - consta in crearea partitiei afectate unui program in timpul incarcarii pentru executie a acestuia, astfel incat dimensiunea partitiei sa corespunda dimensiunilor programului.

Avantajele acetui algoritm de alocare a partitiilor constau in:

utilizare mai eficienta a memoriei interne, comparativ cu partitionarea statica;

mobilitate mare din punctul de vedere al numarului de programe active, partitiile de incarcare corespunzatoare netrebuind sa aiba o dimensiune prestabilita;

Dezavantajul principal consta in faptul ca utilizarea metodei atrage dupa sine o fragmentare a memoriei interne, dupa o perioada de timp sufient de mare, in care s-au incarcat pentru executie diverse programe. Din cauza fragmentarii memoriei, se poate ajunge la situatia in care un program ce trebuie executat, nu poate fi incarcat, in ciuda faptului ca fragmentele de memorie libere, existente la momentul respectiv, insumate depasesc dimensiunea programului in cauza.

Avand in vedere aceasta posibila fragmentare a memoriei interne, dupa o perioada de functionare, partitia de memorie ce trebuie alocata programului ce urmeaza a fi incarcat, poate fi determinata prin doua metode:

se cauta secvential de la inceputul memoriei interne, un spatiu de memorie liber in care sa poata fi incarcat programul ce urmeaza a fi executat. Prima zona de memorie libera continua, care are dimensiunea mai mare decat cea a programului in cauza, va constitui partitia dinamica de incarcare. Metoda se numeste first-fit;

se baleiaza toata memoria interna, inventariindu-se dimensiunile tuturor zonelor de memorie libera. In final, se va alege dintre toate zonele de memorie libera determinate, acea zona a carei dimensiune este cea mai mare apropiata de dimensiunea programului ce urmeaza a fi incarcat si evident, mai mare ca aceasta. In felul acesta se pierde cat mai putina memorie la incarcarea unui program. Metoda se numeste best-fit.

Ambele tehnici descrise anterior nu rezolva integral problema fragmentarii in timp a memoriei interne. O alta metoda suplimentara utilizata pentru a indeparta acest dezavantaj, este defragmentarea periodica a memoriei interne. Aceasta implica descarcarea tuturor programelor incarcate in memoria interna la un moment dat si reincarcarea secventiala a lor, astfel incat intre partitiile dinamice astfel create, sa nu mai existe spatii de memorie libera (evacuarea unui program din memorie pentru a fi incarcat la alta adresa poarta numele de relocare program). Aceasta tehnica rezolva problema defragmentarii pentru moment, utilizarea ei determinand si o incetinire a executiei programelor, datorata relocarii acestora.

Alocarea prin tehnica paginarii

Pentru inceput sunt necesare doua notiuni noi:

spatiul de adrese utilizator - reprezinta spatiul logic de adresa aflat la dispozitia utilizatorului pentru realizarea programului;

spatiul fizic de adrese - reprezinta spatiul de memorie fizica alocat unui program.

Aceste spatii de adrese sunt limitate de posibilitatea de adresare operanzi sau instructiuni in cadrul programului, impusa de lungimea cuvantului calculator.

In cadrul acestei tehnici spatiul de adresa utilizator al fiecarui program este divizat in arii egale numite pagini si in mod asemanator, memoria fizica este divizata in arii de aceeasi dimensiune. La incarcarea programului in memorie, fiecare pagina din spatiul de adrese utilizator este plasata intr-o pagina din spatiul fizic de adrese. Paginile apartinand spatiului de adresa utilizator nu trebuie sa ocupe un spatiu continuu in sirul de pagini in care este impartit spatiul fizic de adrese. Continuitatea lor logica este asigurata de sistemul de operare. Aceasta tehnica de alocare a memoriei interne, inlatura complet dezavantajul defragmentarii memoriei, asigurand si o utilizare eficienta a acesteia.

Facem observatia ca foarte multe programe, in executie nu utilizeaza toate instructiunile si deci tot spatiul fizic de adresa in care a fost incarcat. Elementele care conduc la situatii de acest gen pot fi:

rutinele de manipulare eroriscrise de utilizator sunt executate numai daca apar situatiile de eroare respective;

anumite parti (rutine) ale programului se exclud reciproc sau nu sunt necesare pentru orice rulare, etc.

Rezulta ca in timpul rularii, un program poate avea incarcate in memoria interna, din spatiul de adrese utilizator, numai paginile necesare executiei, restul existand pe un suport de memorie externa (disc). In timpul executiei unui astfel de program, paginile care nu exista in memoria interna, sunt incarcate de pe suportul de memorie externa, doar in momentul referirii lor dintr-o alta pagina a programului respectiv, incarcata deja in memoria interna.

Aceasta tehnica de alocare este numita alocare prin cerere de pagina si poate fi implementata la nivel de pagina sau de segment (segmentul este o alta unitate de divizare a unui program in arii). Traficul de pagini intre memoria interna si memoria externa pe care se afla pagini din programele aflate in executie, intra in responsabilitatea sistemului de operare.

Deci, nu este strict necesar ca spatiul de adrese utilizator sa fie in corespondenta biunivoca cu spatiul fizic de adrese, acesta din urma putand fi mai mic. Apare astfel ideea ca suma spatiilor de adrese utilizator corespunzatoare unor programe aflate in executie, poate fi mai mare chiar decat limita maxima a spatiului fizic de adrese, ceea ce face ca spatiul de adrese utilizator sa devina un spatiu virtual in raport cu cel fizic. Aceasta idee da nastere notiunii de memorie virtuala.

Notiunea semnifica utilizarea unui spatiu de adrese utilizator, mai mare decat spatiul fizic de adrese. In cazul memoriei virtuale utilizatorul are iluzia ca memoria interna are o capacitate mult mai mare decat cea reala, dar ca este si mai lenta. Sistemul de calcul este considerat cu un singur nivel de memorie (memoriile interna si externa reunite), organizat la nivel de pagina, traficul de pagini dintre cele doua tipuri de memorii neimplicand programatorul.

Alte tehnici de lucru cu memoria interna

Mecanismul de swapping (de evacuare) - este un mecanism care a prefigurat notiunea de memorie virtuala. Necesitatea aparitie lui a rezultat din faptul ca memoria interna reprezinta o resursa fizica limitata. Mecanismul permite partajarea memoriei interne intre mai multe programe ale caror spatii de adrese utilizator insumate, ar necesita un spatiu fizic de adrese mai mare decat cel existent in memoria interna respectiva.

Mecanismul propriu-zis consta in evacuarea pe disc a programelor incarcate in memoria interna conform unei discipline prestabilite, in situatia in care programele curente incarcate in memoria interna, nu permit incarcarea altor programe. Dupa o cuanta de timp programele evacuate pe disc, sunt reincarcate pt continuarea executiei (time-sharing la nivelul memorie interne). Deci, mecanismul este foarte asemanator cu cel practicat in cadrul memoriei virtuale, deosebirea constand in faptul ca nu se lucreaza la nivel de pagina.

Acest mecanism de gestiune a memoriei interne a fost utilizat inca de la alocarea memoriei interne prin partitii dinamice.

Stiva - este un mecanism de utilizare a memoriei. Zona de memorie utilizata in acest scop poate fi gestionata de sistemul de operare (stiva sistem) sau de catre utilizator (stiva utilizator). Aceasta zona de memorie este folosita pentru diverse manevre ca de exemplu:

salvare/restaurare proces intrerupt;

pasare de parametrii in diverse situatii.

Stiva reprezinta un depozit de diverse elemente memorate, la care accesul este bazat de disciplina LIFO (Last In First Out). Figurativ stiva poate fi asimilata unei tevi inchise la un capat, in care se introduc si extrag elemente, de diametrul egal cu cel al tevi, pe la capatul ramas liber.

Din cele doua exemple de utilizare a stivei date anterior, vom insista in cele ce urmeaza asupra pasarii parametrilor catre proceduri si functii. Dupa cum este cunoscut, acestea reprezinta zone de cod (subprograme), care identifica printr-un nume o secventa de instructiuni specializate in a executa anumite actiuni, cu grad mare de repetabilitate in cadru unui program de mari dimensiuni. Pentru a fi executata secventa de instructiuni specifica unui subprogam acesta trebuie apelat prin identificator. Apelul inseamna un salt la secventa de instructiuni, sintaxa de apel permitand pasarea unor parametrii catre zona de cod reprezentand subprogramul.

Exista doua moduri de pasare a parametrilor:

prin valoare - cand pe stiva este transmisa valoarea efectiva a parametrului, acesta fiind echivalent cu o variabila interna a subprogramului;

prin variabila (referinta) - cand pe stiva este transmisa adresa la care se gaseste valoarea efectiva a parametrului, acesta fiind echivalent cu o variabila externa a subprogramului;

Alt element important la pasarea parametrilor este reprezentat de ordinea de asezare a parametrilor in stiva, existand in acest sens doua conventii:

parametrii sunt asezati in stiva de la stanga la dreapta (conventia Pascal);

parametrii sunt asezati in stiva de la dreapta la stanga (conventia C);

Primul element care se aseaza in stiva este reprezentat de adresa de intoarcere, PC-ul programului apelant. Urmatoarele elemenete asezate in stiva sunt reprezentate de parametrii de tip valoare sau referinta. Dupa executarea zonei de cod corespunzatoare subprogramului apelat, parametrii pasati prin stiva sunt eliberati (stersi), pentru a se putea ajunge la adresa de intoarcere in programul apelant. Avand in vedere cele prezentate pana acum, se poate concluziona ca rezultatul prelucrarilor unui subprogram, nu poate fi facut cunoscut programului apelant prin intermediul parametrilor de tip valoare, ci doar prin cel al parametrilor de tip referinta.

(desen cu explicatii, exemplu de pasare)

Exemple de alocare memorie la diverse sisteme de operare

sistemul RSX: partitionare dinamica;

sistemul Unix: alocare prin cerere de pagina;

sistemul DOS: combinatie intre alocare continua si tehnica paginarii memoriei;

sistemul Windows: alocare prin cerere de pagina;

cum este administrata zona de memorie afectata unui program in Pascal, sub sistemele de operare DOS sau Windows:

zona Heap (libera);

segment stiva (contine variabile locale rezultate crearea unui nou bloc sau din pasarea parametrilor catre un subprogram, adrese retur etc.);

segment date (variabile globale, variabile pt editor si compilator daca e activ si mediul Pascal);

segment cod (unit-ul system, unit-uri diverse, cod program, cod editor, cod compilator, evident daca e activ si mediul Pascal) - toate sunt paginate separat.

Gestiunea sistemului de fisiere

Structura organizatorica a sistemului de fisiere pe discuri

Scopul existentei acestei structuri organizatorice, materializata in sistemului de gestiune fisiere pe un suport digital de informatie, este stabilirea unui algoritm de alocare spatiu liber in vederea scrierii informatiilor si regasirii lor, precum si in vederea gestiunii spatiului liber pe un suport extern de informatie.

Intrucat pentru benzile magnetice, structura organizatoriza a sistemului de fisiere este foarte apropiata de organizarea fizica a informatiei pe acest tip de suport extern de memorie, in cele ce urmeaza vom face referiri doar la structura organizatorica a sistemului de fisiere pe discuri.

Sistemul de fisiere sistem si de aplicatie stocate pe un disc, trebuie structurat logic. Cele doua categorii de fisiere - sistem si aplicatie - pot fi interpretate ca fisiere apartinand celor doua grupari primare aflate la baza software-ului, prezentate in paragraful 4.1.1. In general, la sistemele de operare actuale continutul acestei structuri logice este descris in mai multe cataloage numite directoare, care alcatuiesc o structura arborescenta, elementul de structura fiind directorul. Exista 2 tipuri de directoare:

radacina (principal) - este unic pentru un disc, pozitia sa pe disc este cunoscuta de la faza de formatare a discului;

ordinare, numite si subdirectoare, functie de context. - acestea pot fi pe mai multe niveluri, alcatuind impreuna cu directorul radacina structura arborescenta amintita anterior.

Un director poate contine fisiere si alte subdirectoare direct subordonate. Informatiile continute de un director, se refera la toate elementele continute de acesta si constau in nume fisier/subdirector, extensie - pentru fisiere, dimensiune - pentru fisiere, data creerii, data ultimei modificari si zona de pe disc in care este stocata informatia propriu-zisa corespunzatoare fisierului/subdirectorului respectiv.

SD_IJ - subdirectorul "j" de pe nivelul "i";

FU_IJ - fisierul utilizator "j" dintr-un director de pe nivelul "i".

In figura de mai sus, alaturi de structura arborescenta de directoare, apare si modulul de gestiune a sistemului de fisiere, specific fiecarui disc. Acest modul are o strcutura specifica fiecarui sistem de operare si ofera, in general, informatii asupra modului de regasire a informatiilor pe disc. In cazul sistemelor de operare DOS si Windows, modulul contine doua componente de baza:

blocul de incarcare - din prezentarea facuta in partea introductiva a acestui capitol am cunosc utilitatea acestuia. La informatiile continute de acest bloc, utile din punctul de vedere al incarcarii sistemului de operare, adaugam si informatia referitoare la pozitia directorului radacina si a tabelelor de alocare a spatiului pe disc;

tabelele de alocare a spatiului pe disc - FAT (File Alocation Table). Aceste tabele de alocare spatiu exista in dublu exemplar (FAT1 si FAT2) si reprezinta o insiruire a cluster-elor existente pe disc. Un cluster este o unitate de alocare a spatiului pe disc, reprezentand un grup de blocuri fizice (sectoare) ale discului. Un cluster poate contine 1, 2, 4, 8, 16 blcouri fizice. Spatiul alocat pe disc unui fisier este de fapt, o lista simplu inlantuita de cluster-e, FAT-ul folosind la a marca inlantuirile corespunzatoare tuturor listelor inlantuite specifice fiecarui fisier de pe un disc. Figura urmatoare ilustreaza acest lucru:

In exemplul dat sunt desenate primele 11 cluster-e ale FAT-ului. In desen apare ca exemplu un director, care contine 3 subdirectoare (SD₁, SD₂ si SD₃) si 3 fisiere utilizator (FU₁, FU₂ si FU₃). In informatiile referitoare la un fisier, existente intr-un director, se afla si numarul primului cluster din FAT, alocat fisierului in cauza. Astfel pentru FU₂, primul cluster alocat este chiar cluster-ul 1. In desen este reprezentata si lista simplu inlantuita a cluster-elor alocate fisierului FU₂. Rezulta ca fisierului precizat ii mai sunt alocate cluster-ele 4, 5, 6, 7 si 10.

Pentru localizarea fisierelor pe disc se utilizeaza identificatorul de fisier. Acesta este compus din: device, cale (succesiune de directoare), nume fisier si extensie fisier.

Cautarea unui fisier presupune mai multe accesari ale discului. Sa luam de exemplu identificatorul de fisier: "e:\SubD1\SubD2\FisUt1". Pentru localizarea acestui fisier se parcurg urmatorii pasi:

se cauta in directorul radacina (a carui pozitie este cunoscuta) cluster-ul de inceput al directorului "SubD1";

se parcurge lista inlantuita de cluster-e, pentru a se determina blocurile fizice in care este inscriptionata informatia corespunzatoare directorului "SubD1";

se cauta in datele corespunzatoare directorului, partea de informatii referitoare la directorul "SubD2", pt a determina cluster-ul de inceput;

se parcurge lista inlantuita de cluster-e, pentru a se determina blocurile fizice in care este inscriptionata informatia corespunzatoare fisierului "FisUt1";

Organizarea si accesarea fisierelor

Din punctul de vedere al organizarii informatiilor apartinand unui fisier, se poate discuta despre o structura fizica si una logica:

Structura fizica se refera la modul de stocare a informatiei proprie unui fisier, cu ajutorul entitatilor specifice organizarii fizice a informatiei pe suporti externi de memorie. Din acest punst de vedere un fisier este alcatuit dintr-o succesiune de  blocuri de date (sectoare), acestea fiind unitatea de transfer informatie intre ME si MI. Ideal este ca aceste blcouri sa fie asexate continuu.

Din punctul de vedere al alocarii spatiului fizic pe un suport magnetic fisierele pot fi:

cu alocare statica - fisierul ramane pe perioada utilizarii la dimensiunea initiala;

cu alocare dinamica - fisierul se extinde automat functie de necesitati pe parcursul exploatarii;

Structura logica se refera la modul de stocare a informatiei proprie unui fisier, din punctul de vedere al programatorului. Astfel, un fisier este alcatuit din articole sau inregistrari, acestea reprezentand unitatea logica de informatie ce poate fi manipulata intre program si suportul fizic. Aceasta entitate structurala, este descrisa in Pascal cu ajutorul tipului structurat "record".

O inregistrare este alcatuita la randul ei din componente elementare numite campuri, care pot fi manipulate la nivel de program (elementele din structura articolului).

Articolele unui fisier pot fi de lungime fixa sau variabila, in acest ultim caz lungimea articolului fiind precizata chiar in corpul articolului la inceput.

Prin cheie de acces la un articol se intelege un camp din structura acestuia, pe baza caruia se pot identifica articlolele. Se pot admite chei duble (articole cu chei egale) sau chei multiple (mai multe campuri din structura unui articol servesc la identificarea articolului).

Comunicarea suport fizic - MI afectata programului, se face prin asa numitele zone de memorie tampon, rezervate la nivelul programului. De obicei, aceste zone sunt mai mari decat dimensiunea unui articol (cuprind de obicei blocul de date din face parte articolul) si din acest motiv se poate lucra cu scrieri intarziate sau citiri in devans. Tehnica scrierilor intarziate se materializeaza in faptul ca un articol nu este scris pe disc in momentul in care se da comanda de propriu-zisa de scriere (deci la executia unei instructiuni "write" in Pascal). Scriere se face efectiv, dupa ce s-a strans un lot mai mare de articole, pentru a se reduce numarul de accese la disc. De obicei exista si instructiuni pentru realizarea efectiva a scrierii pe disc (exemplu instructiunea "flash" in Pascal). Modul de lucru in cazul citirii in avans este similar.

Subiectul acestui paragraf il constituie in continuare, modurile in care pot fi organizate inregistrarile apartinand unui fisier in memoria externa, astfel incat accesul la ele sa fie cat mai comod.

Organizarea secventiala a fisierelor

Inregistrarile fisierelor cu aceasta organizare pot fi accesate numai in ordinea secventiala in care au fost memorate, pentru identificarea unui articol folosindu-se cheia de acces. Deci, organizarea secventiala a fisierelor, permite numai un acces secvential la informatia dintr-un astfel de fisier.

In astfel de fisiere, in general nu se poate modifica continutul articolului, decat eventual, pentru fisierele cu articole de lungime fixa. Stergerea articolelor se poate face doar logic sau nu se poate face de loc. Stergerea logica a unui articol implica invalidarea sa ca articol ce poate fi accesat, neinsemnand si stergerea efectiva (fizica) a sa din fisierul respectiv. Daca se doreste si stergerea fizica a articolului din fisier, atunci intregul fisier trebuie rescris. Adaugarea unui nou articol nu se poate face decat la sfarsitul fisierului (append).

Fisierele organizate secvential sunt singurele fisiere care admit structuri compuse din articole de lungime variabila, lungimea fiind precizata la inceputul articolului, in astfel de cazuri.

Fisierele cu organizare secventiala, sunt utilizate in general in forma sortata, dupa criterii ce tin de cheia de acces a articolelor ce le compun. Avand in vedere particularitatea legata de adaugarea unor noi articole intalnita la aceasta organizare a fisierelor, actualizarea unui fisier sortat reprezinta o procedura greoaie. In general, aceasta consta din urmatorii pasi:

se construieste un fisier intermediar sortat, cu articolele ce se adauga;

cele doua fisiere (cel deja existent si cel nou creat) se interclaseaza pe baza criteriilor avute in vedere la sortarea fiecaruia. Este important de retinut ca fisierul rezultat, este rescris in totalitate.

Secventa clasica de instructiuni pentru parcurgerea unui fiser secvential este:

citeste prima inregistrare din fisier;

while not(eof(variabila_fisier)) do begin

- Prelucreaza inregistrarea citita;

- Citeste urmatoarea inregistrare din fisier;

end;

Fisierele text reprezinta un caz particular de fisiere secventiale. Fiecare inregistrare e compusa dintr-un caracter obisnuit sau dintr-un caracter de control al scrierii (retur de car, salt la linie noua sau indicator de font - tip, marime, aspect). Un fisier text poate fi vazut si ca o secventa de randuri, separate prin marcaje de sfarsit/inceput rand (implementat in Pascal). In acest sens, randul poate fi interpretat si ca un articol de lungime variabila, lungimea sa nefiind precizata explicit la inceputul articolului, ci indirect prin caracterele de control care separa doua randuri.

Organizarea indexata a fisierelor

Dupa cum s-a observat la organizarea secventiala, accesul la articolele unui fisier este lent. In ideea reducerii timpului de acces la articole, o solutie poate fi memorarea intr-o zona aparte, pe care o vom numi tabel de indecsi, a fiecarei chei de acces corespunzatoare articolelor continute intr-un fisier si adresa pe disc a articolelor corespunzatoare.

Aceasta organizare permite un acces relativ direct la articole, cautarile secventiale fiind reduse la tabela de indecsi si eventual la un grup mic de articole. Un astfel de fisier, pentru care se construieste o tabela cu adresele articolelor ce-l compun, poarta numele de fisier indexat. Comparativ cu organizarea secventiala, aceasta organizare, pe langa un acces relativ direct la articole, permite stergerea fizica a articlelor precum si adaugarea de noi articole fara proceduri atat de laborioase (se actualizeaza doar tabela de indecsi).

O tabela de indecsi se compune din doua elmente de baza:

cheia de acces a unui articol;

adresa pe disc a articolului respectiv.

Pentru cresterea vitezei de lucru, acest tabel de indecsi se va incarca integral in MI. De exemplu, directoarele element de baz in organizarea logica a informatiei pe discuri, pot fi privite ca tabele de indecsi pentru elementele continute: directoare sau fisiere. Celor doua elemente de baza ale unei tabele de indecsi , le corespund:

nume director sau fisier, pe post de cheie de acces;

cluster-ul de la care incepe lista simplu inlantuita de cluster-e afectate directorului sau fisierului, pe post de adresa articol.

Daca se doreste regasirea articolelor si dupa alte criterii (chei de acces), se mai creaza un tabel de indecsi pentru noile chei (indexare multipla). Existenta mai multor indecsi duce la timpi mai mari de prelucrare a fisierului indexat, deoarce trebuie actualizate mai multe tabele de indecsi la inserare sau stergerea articolelor.

In realitate, organizarea tabelei de indecsi este putin mai complicata. Nu se lucreaza, pastrand adresa fiecarei chei in parte (deci a fiecarui articol). Tabela de indecsi care se incarca in MI, ar ocupa dimensiuni mari. Ca atare, se ordoneaza secvential fisierul (se sorteaza dupa criterii rezultate din cheia de acces), apoi se imparte in segmente mai mici, care contin fiecare mai multe inregistrari. Fiecare segment astfel obtinut este apoi reprezentat in index printr-un singur articol.

Alta metoda de rezolvare a tabelelor de indecsi de mari dimensiuni, este ca tabela de indecsi sa fie divizata intr-un index de indecsi (este exact sistemul ierarhic de directoare utilizat de majoritatea sistemelor de operare).

Referitor la accesul la inregistrari oferit de organizarea indexata a unui fisier putem concluziona ca acesta este direct. Exista de asemenea si acces secvential, la partea de cautare in tabela de indecsi si la partea de cautare a unui articol intr-un segment de fisier. Ponderea acestor cautari secventiale este insa nesemnificativa.

Organizarea dispersata a fisierelor (directa)

Fisierele dispersate (hashed files) reprezinta un sistem de stocare a informatiei ce permite accesul direct la articole, fara a utiliza o tabela de indecsi. Aceasta este substituita prin calcularea si determinarea pozitie fiecarei inregistrari pe suportul de memorie externa, cu ajutorul unui algoritm aplicat valorii campului reprezentand cheia de acces a fiecarui articol.

Ideea de baza consta in impartirea zonei de memorie externa alocata fisierului, in mai multe arii numite containere sau granule. Fiecare articol este repartizat intr-un container (granula) pe baza unui algoritm de calcul, care aplicat cheii de acces determina in mod unic containerul corespunzator. Pentru regasirea unui articol, acelasi algoritm de calcul se aplica cheii de acces a articolului, determinandu-se containerul in care se afla acesta. Intrucat, intr-un container pot exista mai multe articole, aici cautarea se face secvential.

Utilizarea acestui mod de organizare a unui fisier presupune o analiza prealabila a inregistrarilor ce urmeaza a fi stocate in fisierul respectiv. Mai exact, este necesara o analiza statistica a valorilor campului declarat drept cheie de acces in cadrul articolelor ce vor popula fisierul. De asemenea trebuia facuta si o estimare a numarului total de inregistrari. Pasii ce trebuie parcursi pentru stabilirea caracteristicilor unui fisier organizat astfel ar fi urmatorii:

estimarea numarului de inregistrari care vor popula fisierul;

determinarea granulatiei fisierului, aceasta implicand stabilirea numarului de containere (granule) din care va fi compus fisierul si capacitatea fiecarui container (granule);

stabilirea unui algoritm de calcul care aplicat valorii numerice reprezentate de cheia de acces a inregistrarilor, sa aibe ca rezultat numarul de ordine al unui container in care articolul respectiv va fi stocat;

incarcarea propriu-zisa a fisierului cu inregistrari reale si analiza gradului de umplere a containerelor.

Referitor la structura unui astfel de fisier, mai trebuie amintita si zona de depasire, care alaturi de containere acopera intregul spatiu de memorie externa afectat fisierului. Zona de depasire este necesara intrucat, intr-un container pot exista coliziuni care sa determine depasirea capacitatii containerului respectiv (repartizarea a doua sau mai multe inregistrari in acelasi container poarta numele de coliziune). Inregistrarile care au fost repartizate in acelasi container, sunt de regula, legate intre ele cu ajutorul unei liste simplu inlantuite. In cazul in care capacitatea containerului este depasita, lista simpla inlantuita se continua in zona de depasire, ea continand articolele suplimentare. Daca inregistrarile din container nu sunt inlantuite prin lista simpla amintita, containerul va contine doar adresa primului element din lista inlantuita corespunzatoare, din zona de depasire.

Problema reducerii la zero a utilizarii zonei de depasire si deci a inlaturarii ei din structura fisierului nu se pune. Se pune insa problema ca aceasta zona de depasire sa fie folosita cat mai putin, intrucat cautarea de spatiu liber in aceasta zone, in vederea alocarii unei inregistrari sau cautarea unei inregistrari deja existente in aceasta zona, se face parcurgand lista simplu inlantuita, deci secvential. Pentru a existenta cat mai putine inregistrari in zona de depasire, trebuie ales un algoritm de calcul care sa asigure o umplere cat mai uniforma a containerelor. In felul acesta daca dimensionarea fisierului a fost bine facuta, foarte putine inregistrari vor fi stocate in zona de depasire. Se identifica astfel ca problema majora calitatea algoritmului utilizat la repartizarea inregistrarilor in containere. In principiu acest algoritm trebuie sa fie un generator de numere aleatoare uniform repartizate intr-un interval, generator care sa aibe ca element de intrare valoarea numerica reprezentate de cheia de acces. Exemple de algoritmi:

deducerea containerului dedicat unei inregistrari prin aplicarea operatiei modulo N valorii numerice rezultate din cheia de acces a articolului, N reprezentand numarul de containere existente in fisierul respectiv. Este un algoritm simplu, care da rezultate bune pentru cazuri particulare. N este de preferat sa fie numar prim;

ridicarea la patrat a valorii numerice rezultate din cheia de acces a articolului si alegerea cifrelor din mijlocul numarului obtinut;

generatoare de numere aleatoare, care sa aibe ca elment de pornire valoarea numerica rezultata din cheia de acces a articolului: generatorul congruential aditiv, generatorul congruential multiplicativ sau generatorul congruential mixt.

Un grad de umplere mediu de 50-60% a containerelor, pana la aparitia primelor inregistrari in zona de depasire, reprezinta un procent multumitor si ca atare algoritmul de calcul utilizat este considerat bun.

Se pot desprinde urmatoarele concluzii legate de acest mod de organizare a unui fisier:

accesul la o inregistrare este direct, la care se adauga o eventuala cautare secventiala in container (daca articolele sunt pe o lista simplu inlantuita si in container) si o cautare secventiala in zona de depasire, daca exista articole stocate aici;

spatiul fizic alocat fisierului trebuie sa fie mai mare decat spatiul ocupat efectiv de inregistrarile fisierului (aproape dublu);

dimensiunea fisierului trebuind sa fie estimata la inceputul utilizarii sale, rezulta ca pentru fisierele organizate astfel, este suficienta alocarea statica a spatiului fizic pe suportul de memorie externa;

continand structuri mai sofisticate putine limbaje de programare implementeaza acest mod de organizare a fisierelor.

Figura urmatoare ilustreaza organizarea dispersata a fisierelor.

Cocluzie: rolul sistemului de operare in gestiunea sistemului de fisiere consta in:

stocarea si regasirea informatie pe disc - asigura organizarea logica a informatiei si legatura dintre aceasta si organizarea fizica a informatiei pe disc.

Pentru manipularea fisierelor pune la dispozitia utilizatorului un set de rutine specifice tipurilor de organizari fisiere implementate pe sistemul respectiv de operare. Aceste seturi de rutine isi fac simtita prezenta prin intermediul limbajelor de programare, care le implementeaza.

Dintre modurile de organizare a inregistrarilor in fisiere, organizarea secventiala este implementata de toate sistemele de operare. Celelalte moduri de organizare a inregistrarilor in fisiere, sunt implementate in forme particulare, de diversele limbaje de programare implementate, la randul lor pe un sistem de operare;

contine rutinele de tratare intreruperi pt lucrul cu fisiere. Acestea reprezinta o colectie de rutine ce asigura serviciile de baza pentru operatiile de intrare-iesire, constituind interfata dintre SO si periferia hardware a calculatorului. Pentru sistemele de operare Dos si Windows  aceste rutine constituie asa-numitul BIOS (Basic Input Output System), inscris in memorie ROM;

are sarcina de a manipula fisierele cu care se lucreaza. Pentru a face asta, trebuie sa aibe acces la atributele fisierului respectiv. Acestea sunt gestionate intr-o tabela de control fisier creata automat de sistemul de operare, la actiunea explicita de deschidere a fisierului de catre un program. Tabela de control fisier se poate aloca:

la nivel de program;

centralizat, la nivelul bazei de date a sistemului de operare.

Alocarea centralizata presupune activitati mai complexe, dar utilizarea ei permite construirea unor mecanisme de protectie intre utilizatori la folosirea aceluiasi fisier.