Gestiunea resurselor logice. sistemul de fisiere.

GESTIUNEA RESURSELOR LOGICE. SISTEMUL DE FISIERE

1. NOTIUNI INTRODUCTIVE

Pentru aplicatiile soft sunt necesare doua conditii esentiale:

stocarea informatiei;

regasirea informatiei.

Pana acum, singura entitate pe care am studiat-o a fost procesul. Acesta, insa, nu beneficiaza de aceste doua conditii, un proces neputand fi stocat intr-un mediu de memorare extern si, implicit, nu se poate apela la informatiile detinute de el dupa o anumita perioada. De aceea se impunea introducerea unei noi entitati care sa satisfaca cele doua conditii. Aceasta entitate a fost denumita fisier iar sistemul ce gestioneaza fisierele se numeste sistemul de fisiere.

Fisierul este o resursa logica a sistemului de operare si este memorat intr-un mediu extern de memorare. Prin definitie, fisierul este:

-unitatea logica de stocare a informatiei;

-o colectie de informatii definita de creatorul ei;

-o colectie de informatii mapate pe perifericile fizice.

Pentru a furniza un mod de pastrare a fisierelor, multe sisteme de operare au si conceptul de director ca o cale de a grupa mai multe fisiere.

Sistemul de fisiere dintr-un SO trebuie sa realizeze urmatoarele operatii:

-Crearea si stergerea fisierelor/directoarelor.

-Denumirea si manipularea fisierelor; fiecare fisier ar trebui sa aiba un nume care sa fie  reprezentativ pentru continutul sau; manipularea fisierelor consta in operatiile ce se pot efectua cu ele, ca scriere , citire, cautare.

-Asigurarea persistentei datelor. Acest lucru inseamna satisfacerea conditiei de regasire a datelor stocate, chiar si dupa perioade de timp foarte mari. De asemenea trebuie sa existe posibilitatea de refacere a continutului unui fisier in caz de accident, posibilitate pe care sistemul de fisiere trebuie sa o puna la dispozitie.

-Asigurarea mecanismelor de acces concurent al proceselor din sistem la informatiile stocate in fisier.

2. CLASIFICAREA FISIERELOR

2.1. Clasificarea fisierelor dupa structura

2.1.1. Secventa de octeti

Fisierul este alcatuit dintr-un sir de octeti. Interpretarea lor este facuta de catre programele utilizator, conferindu-se astfel acestui tip de structura o maxima flexibilitate. Marea majoritatea a sistemelor de operare actuale, printre care UNIX si WINDOWS, prezinta acest tip de structura.

2.1.2. Secventa de inregistrari

Un fisier este alcatuit dintr-o secventa de inregistrari, de obicei specifica unui anumit dispozitiv periferic. Astfel, pentru imprimanta, era linia de tiparit formata din 132 de caractere, pentru lectorul de cartele era o coloana s.a.m.d. Acest tip de structura tine deja de domeniul istoriei.

2.1.3. Structura arborescenta

Structura interna a unui fisier este organizata ca un arbore de cautare. Un arbore de cautare este un arbore binar ale carui noduri au o cheie de identificare. Cheia asociata unui anumit no este mai mare decat cheia asociata unui nod din sub-arborele drept. Cheia asociata unui anumit nod este mai mica decat cheia asociata uni nod din sub-arborele stang.

O astfel de structura este utilizata in calculatoarele de mare capacitate.

2.2.Clasificarea fisierelor dupa tip

2.2.1. Fisiere normale

Aceste fisiere contin informatie utilizator si pot fi de doua feluri:

-fisiere text;

-fisiere binare.

Fisierul text este format din linii de text; fiecare linie este terminata cu caracterele CR (carriage return) sau LF (line feed).

Fisierul binar este organizat ca secvente de octeti dar sistemul de operare ii poate asocia o anumita structura interna, cazul tipic fiind al fisierelor executabile.

2.2.2. Directoare

Sunt niste fisiere sistem destinate gestionarii structurii sistemului de fisiere.

2.2.3. Fisiere speciale de tip caracter/bloc

Sunt destinate utilizarii in conjunctie cu dispozitivele periferice.

2.3. Clasificarea fisierelor dupa suportul pe

care sunt rezidente

Din acest punct de vedere fisierele pot fi:

-fisiere pe disc magnetic;

-fisiere pe banda magnetica;

-fisiere pe imprimanta;

-fisiere pe ecran;

-fisiere pe tastatura.

2.4. Clasificarea fisierelor dupa acces

2.4.1. Fisiere cu acces secvential

In aceste fisiere, pentru a ajunge la informatie, trebuie mai intai sa se parcurga niste structuri. Este cazul tipic al benzii magnetice. In accesul secvential nu se pot face citiri si scrieri in acelasi timp.

2.4.2. Fisiere cu acces direct

Accesul se face direct intr-o structura data, existand posibilitati de a se face citiri si scrieri in acelasi timp. Este cazul tipic al hard discului.

2.4.3. Fisiere cu acces indexat

Se face acces direct prin continut, folosind o serie de tehnici ca fisiere de index, fisiere multi lista, B-arbori, hashing etc.

3. ATRIBUTE SI OPERATII CU FISIERE

3.1. Atribute

Nume numele fisierului este, pentru toate sistemele de operatii, pastrat in forma uman inteligibila.

Tip - acest atribut este absolut necesar deoarece SO cuprinde mai multe tipuri de fisiere(binar, text..).

Locatie - este un pointer la locatia fisierului pe perifericul de stocare.

Protectie - in legatura cu protectia fisierului, cele mai multe atribute se refera la posesorul sau si la drepturile de acces ale utilizatorilor sai.

Timp, data si identificatorul de utilizator - informatii pentru protectia, securitatea si monitorizarea utilizarii.

3.2. Operatii cu fisiere

Prezentam, in continuare, principalele operatii cu fisiere .

-Crearea unui fisier, creat().

-Citirea unui fisier; read();se citesc din fisier un numar specificat de octeti de la o pozitie curenta.

-Scrierea intr-un fisier, write(); se scrie intr-un fisier un numar specificat de octeti, incepand de la pozitia curenta.

-Deschiderea unui fisier, open(); cautarea in structura de directoare de pe disc a intrarii fisierului si copierea continutului intrarii in memorie.

-Descriptorul de fisier, fd; in urma operatiei de deschidere a unui fisier, se returneaza un intreg, numit descriptor de fisier, care va fi utilizat de procesul care a initiat operatia open() pentru toate operatiile ulterioare asupra fisierului respectiv. Descriptorul de fisier este folosit de SO ca un index intr-o tabela de descriptori asociata fiecarui proces, in care se regasesc si alti descriptori asociati altor fisiere folosite de procesul respectiv.

-Stergerea unui fisier, delete(), unlink().

-Trunchierea unui fisier, trunc(), inseamna stergerea unei zone contigue, de obicei la inceputul sau sfarsitul fisierului.

-Inchiderea unui fisier, close(), este mutarea continutului unui fisier din memorie in structura de directoare de pe disc.

-Adaugarea de date la sfarsitul unui fisier, append().

-Setarea pozitiei in fisier, seek().

-Repozitioanrea in fisier, lseek().

-Redenumirea unui fisier, rename().

-Operatia de setare si citire a atributelor unui fisier,setattributes().

Aceste operatii prezentate au echivalent in functiile biblioteca pe care utilizatorul le poate apela din program. La randul lor, aceste functii initiaza apeluri sistem.

In sistemele de operatii actuale accesarea unui fisier se face aleatoriu si nu secvential ca in sistemele mai vechi. Aceasta inseamna ca se pot face operatii de scriere/citire in orice pozitie din cadrul fisierului, adica orice octet din fisier este adresabil.

marker de accesare a unui octet

Fig. 1. Fisier cu secventa de octeti.

4. IMPLEMENTAREA SISTEMULUI DE FISIERE

4.1. Alocarea fisierelor pe disc

Un SOlucreaza la nivel logic cu blocuri. Un bloc este format din doua sau mai multe sectoare fizice. Una din problemele esentiale ale implementarii sistemului de fisiere este modul in care blocurile din disc sunt alocate pentru fisiere. Exista, la ora actuala, trei posibilitati de alocare:

-alocare contigua;

-alocare inlantuita;

-alocare secventiala.

4.1.1. Alocare contigua

In acest mod de alocare fiecare fisier ocupa o multime contigua de blocuri pe disc, adica o multime in care elementele se ating.

Avantajele acestei alocari sunt:

-este un tip de alocare foarte simplu, fiind necesare doar numarul blocului de inceput si numarul de blocuri ale fisierului; de exemplu, un fisier cu 8 blocuri , cu adresa blocului de inceput 1234, va fi reprezentat pe disc astfel:

-sunt permise accese directe.

Dezavantaje:

-exista o risipa de spatiu foarte mare, adica o mare fragmentare a discului datorata conditiei de contiguitate a blocurilor din fisier;

-fisierele nu pot creste in dimensiune ceea ce constituie un impediment important.

Alocarea contigua a fost folosita in primele sisteme de operare, in prezent aproape nu mai este utilizata.

4.1.2. Alocarea inlantuita

Fiecare fisier este o lista liniara inlantuita de blocuri pe disc.

Fiecare bloc contine partea de informatie, care este blocul propriu zis, si o legatura spre blocul urmator, de tip pointer.

In figura 3. este data o astfel de reprezentare pentru un fisier format din 4 blocuri.

Avantaje:

-blocurile unui fisier pot fi imprastiate oriunde in disc caci nu mai exista conditia de contiguitate;

-fisierul poate creste in dimensiuni pentru ca oricand i se pot aloca blocuri libere de pe disc;

-accesul secvential se face relativ usor.

Dezavantaje:

- accesul direct se face destul de greu, datorita numeroaselor legaturi ce pot sa apara la un moment dat;

o corupere a lantului de pointere, duce la distrugerea fisierului sau chiar a intregului sistem de fisiere.

Fig. 3. Reprezentarea unui fisier cu 4 blocuri. Alocare inlantuita.

Acest tip de alocare este specific sistemelor de operare ce folosesc tabela FAT (File Alocation Table). In tabela FAT un fisier este  reprezentat ca in exemplul din figura 4.

Fig. 4. Reprezentarea unui fisier in tabele FAT.

Sisteme de operare ce utilizeaza alocarea inlantuita, deci tabela FAT, sunt: MS DOS, WINDOWS 95, WINDOWS 98, OS/2(versiunea 1 si 2).

4.1.3. Alocarea indexata

In acest tip de alocare se pun la un loc toti pointerii, intr-un bloc de index.

Alocarea indexata grupeaza referintele si le asociaza cu un fisier particular.

Avantaje:

-se realizeaza un acces direct;

-aproape dispare fragmentarea externa:

-este o situatie avantajoasa in cazul in care sistemul de operare are multe fisiere de dimensiune mica.

Dezavantaje:

-implica un cost suplimentar prin accesul la blocul de index.

Alocarea indexata este utilizata in sistemele UNIX, in sistemul cu i-noduri.

Un i-nod (index nod) contine un camp de date in care sunt stocate atributele fisierului respectiv si o legatura spre alt bloc. Fiecarui fisier ii corespunde un i-nod.

Structura unui nod de indexare este data in figura 4.

Aceasta implementare permite o indirectare pana la nivel de trei blocuri.

Adresa indexata unde se gasesc informatiile din fisier poate fi:

-blocul initial, daca adresa este mai mica decat 10 blocuri;

-blocul urmator indexat, pentru bloc de indirectare simpla;

-al doilea bloc, dat de blocul urmator, pentru bloc de indirectare dubla;

-al treilea bloc, dupa indirectarea data de primele 2 blocuri, pentru bloc de indirectare tripla.

Fig. 4 Structura unui i-nod ( nod de indexare)

4.2. Evidenta blocurilor libere

Operatiile de creare, stergere, scriere , efectuate asupra fisierelor, sunt operatii dinamice, ceea ce necesita, in orice moment, alocare/dealocare de blocuri pentru fisiere.

Cum se aloca, firesc, blocuri libere in acel moment,  este necesar ca sistemul de fisiere sa aiba o evidenta a blocurilor libere in orice moment. Cele mai utilizate metode de evidenta sunt:

-metoda listei inlantuite;

-metoda hartii de biti;

-gruparea.

In prima metoda, blocurile libere din disc sunt organizate intr-o structura de lista simplu inlantuita. Operatiile efectuate asupra acestei liste sunt: inserarea de noi noduri, pentru blocurile libere nou aparute, si stergerea de noduri pentru blocurile ce au fost ocupate. Aceasta lista este implementata la o adresa dintr-un bloc dinainte stabilita.

Fig. 5. Lista simplu inlantuita a blocurilor libere din disc.

In metoda hartilor de biti, se utilizeaza o structura de harta de biti in care fiecare bit corespunde unui bloc de pe disc. Un bit 0 inseamna ca blocul este liber iar un bit 1 inseamna ca blocul este ocupat.

Aceasta metoda are avantajul, fata de prima, ca harta de biti are o dimensiune constanta, relativ mica. In plus, localizarea unei zone libere de blocuri cu dimensiune prestabilita se face usor, prin cautarea in harta a unei secvente de biti 0.

Fig. 6.Harta de biti pentru evidenta blocurilor libere pe disc.

In metoda gruparii se foloseste o structura care memoreaza zonele libere din disc, fiecare zona fiind caracterizata prin adresa primului bloc din zona libera si prin numarul de blocuri.

4.3. Eficienta si performanta sistemului de

fisiere

Eficienta unui sistem de fisiere depinde in primul rand de doi factori:

-de algoritmii de alocare a discului, discutati anterior;

- de tipurile de date pastrate in intrarea fisierului din director.

Performanta unui sistem de fisiere poate fi imbunatatita prin trei factori:

-disc cache; aceasta inseamna o sectiune bine determinata a memoriei principale, utilizata ca memorie cache a blocurilor de disc cele mai des utilizate;

-free-behind si read ahead care sunt tehnici de optimizare a accesului secvential;

-RAM disc care inseamna declararea unei portiuni de memorie principala ca un disc virtual.

4.4. Fiabilitatea sistemelor de fisiere

Este necesar ca sistemele de fisiere sa ofere instrumente care sa permita urmatoarele lucruri:

a)-Evitarea distrugerii informatiei pe disc.

b)-Recuperarea informatiilor in urma unor erori hard sau soft.

c)-Asigurarea consistentei sistemului de fisiere.

4.4.1. Evitarea distrugerii informatiei pe disc

In acest context, una dintre cele mai importante probleme este evidenta blocurilor defecte (bad blocks). Aceasta problema este rezolvata atat la nivel hard cat si la nivel soft.

La nivel hard, pana in anul 1993, era permis unui producator de hard discuri ca acestea sa aiba un numar limitat de sectoare defecte, sectoare ce erau stantate pe hard disc. Dupa 1993, standardele internationale nu au mai permis producatorilor sa scoata pe poarta fabricii discuri cu sectoare defecte.

La nivel soft, sistemul de operare, prin intermediul sistemului de fisiere, are incorporat un fisier bad bloc in care sunt trecute toate blocurile defecte ale hard discului. Un bloc situat in acest fisier nu va fi utilizat de sistemul de fisiere, fiind ignorat. Exista doua tipuri de metode pentru a determina daca un bloc este defect si pentru a-l trece in fisierul de bad-bloc:

-metode offline;

-metode online.

Metodele offline constau in a rula programe fara ca sistemul de operare sa fie incarcat, deci a efectua teste independent de sistemul de operare. La sistemele mai noi acest lucru se face, de obicei, prin formatarea lowlevel, cand se determina blocurile defecte, se trec intr-o memorie locala a discului si apoi , la incarcarea SO, ele vor fi trecute in fisierul bad block. La sistemele mai vechi, cand nu exista notiunea de formatare a discului, se treceau teste, se determinau sectoarele defecte si se derutau aceste sectoare, in sensul ca se treceau pe pista de rezerva a discului si nu mai erau considerate blocuri defecte. Metodele online se desfasoara atat timp cat sistemul de operare este activ. De obicei, sistemul de fisiere are inglobat un program care testeaza blocurile unui disc si le declara defecte daca este cazul.

4.4.2. Recuperarea informatiei in urma unor erori

soft sau hard

Recuperarea unui fisier poate fi facuta prin urmatoarele metode:

-prin mecanisme de back-up;

-prin sisteme jurnalizate.

Un mecanism de back-up inseamna copierea intregului sistem de fisiere pe alt periferic decat discul, adica pe banda magnetica sau, mai adesea, pe streamer. Aceasta operatie de salvare se face periodic, perioada fiind hotarata de inginerul de sistem, si se numeste massive dump sau periodic dump. Principalul ei dezavantaj consta in timpul lung ce necesita. Exista si o varianta ce necesita timp mai scurt, numita incremental dump, care consta in salvarea pe banda sau pe streamer numai a fisierelor ce au fost modificate de la ultima operatie de salvare.

Sistemele jurnalizate inregistreaza fiecare actualizare a sistemului de fisiere ca pe o tranzactie. Toate tranzactiile sunt scrise intr-un jurnal. O tranzactie este considerata comisa atunci cand este scrisa in jurnal. Tranzactiile din jurnal sunt operate asincron in sistemul de fisiere. Dupa ce sistemul de fisiere este modificat, tranzactie este stearsa din jurnal. In momentul in care sistemul de fisiere a cazut dintr-o eroare de hard sau soft, se reporneste sistemul de operare si tranzactiile din jurnal vor fi, toate, actualizate.

4.4.3, Asigurarea consistentei sistemului de fisiere

Probleme de consistenta a sistemului de fisiere apar in cazul in care unele modificari facute sistemului de fisiere nu au fost actualizate pe disc. Verificarea consistentei sistemului de fisiere se face, atat la nivel de bloc cat si la nivel de fisiere, cu ajutorul unor programe utilitare.

Un exemplu de program care verifica consistenta la nivel de bloc, din sistemul UNIX, este cel dat in continuare.

C1- indica numarul de aparitii ale blocului respectiv in toate i- nodurile.

C2- indica numarul aparitiilor blocului in lista de blocuri libere.

In mod normal trebuie sa avem C1+C2=1

Tabelul 1. Situatiile anormale care pot sa apara in asigurarea consistentei sistemului de fisiere.

Pentru verificarea consistentei la nivel de fisier se folosesc doua contoare, CF1 si CF2. CF1 contorizeaza aparitiile fisierului in directorul de sistem si CF2 contorizeaza numarul de legaturi stocat in i-nodul asociat fisierului respectiv. In mod normal CF1=CF2. Situatiile anormale sunt:

Cf1< CF2, fisierul va figura ca fiind adresat chiar daca el a fost sters din toate directoarele unde figura si iroseste un i-nod;

CF1>CF2, se aloca acelasi i-nod pentru doua fisiere diferite.

4.5. Protectia fisierelor

Este foarte important ca fiecare utilizator sa-si defineasca drepturile de acces asupra propriilor fisiere, precizand cine le poate accesa si ce operatie poate efectua asupra lor.

Sistemul UNIX are unul din cele mai eficiente sisteme de protectie a fisierelor. In acest sistem sunt trei tipuri de utilizatori si proprietari :

-proprietarul fisierului;

-utilizatori, membri ai grupului din care face parte posesorul fisierului;

-alti utilizatori.

si trei tipuri de operatii:        citire, scriere si executie.

Implementarea se face cu un grup de 9 biti, 3 biti de fiecare operatie, pentru fiecare tip de utilizator. Acest grup de 9 biti este continut in unul dintre atributele care se gasesc in i-nodul asociat.

Fig.  Implementarea sistemului de protectie in UNIX.

In acest caz proprietarul are toate drepturile asupra sistemului, utilizatorii membri ai grupului au drept de citire si executie iar ceilalti utilizatori au doar dreptul de citire.

Metoda utilizata in sistemul WINDOWS este ce a listelor de acces. Fiecarui fisier ii este asociata o lista de control de acces (acces control list= ACL). Lista contine mai multe intrari de control al accesului (acces control entries =ACE). Fiecare ACE specifica drepturile de acces pentru un utilizator sau grup de utilizatori, continand un identificator al acestora, o descriere a drepturilor si drepturile pe care le confera asupra fisierului, precum si alte optiuni cum ar fi cea legata de posibilitatea ca un fisier creat in cadrul unui director sa mosteneasca drepturile de acces ale acestuia.

In momentul in care un utilizator incearca sa acceseze fisierul, se verifica automat in cadrul listei de control asociate (ACL) daca este vorba de un acces permis sau nepermis.

4.6. Organizarea fisierelor pe disc

4.6.1. Organizarea in sistemul de operare UNIX

In UNIX exista urmatoarea organizare a sistemului de fisiere:

Blocul de boot contine proceduri si functii pentru initializarea sistemului.

Superblocul contine informatii despre starea sistemului de fisiere: dimensiunea, numarul de fisiere ce pot fi create, adresa spatiului liber de pe disc, numarul de i-noduri, numarul de blocuri.

Lista de i-noduri este lista tuturor nodurilor index continute in sistem, o lista lineara in care un nod este identificat printr-un indice. Dintre i-noduri, primul din lista este destinat gestiunii blocurilor diferite iar al doilea are directorul de radacini.

Blocurile de date contin atat date utilizator cat si date folosite de sistemul de fisiere.

4.6.2. Organizarea fisierelor in SO ce folosesc FAT

In SO care utilizeaza mecanisme de tip FAT, structura unei intrari de director este:

Principalul dezavantaj al mecanismelor FAT este absenta mecanismului de crearea legaturilor la fisiere. Pentru realizarea unor legaturi ar fi necesar ca o aceeasi intrare sa figureze in doua sau mai multe directoare, avand drept consecinta duplicarea unor date legate de pozitionarea pe disc, de timpul si dimensiunea fisierului respectiv, ceea ce poate genera inconsistente.

4.6.3. Organizarea in HPFS (High Performance File System)

Aceasta organizare utilizeaza pentru descrierea localizarii pe disc a fisierelor structuri de date de tip arbori B care au principala proprietate de a avea performante ridicate pentru operatiile de cautare.

In aceasta organizare discul arata astfel:

-Primele 18 sectoare contin blocul de boot, superblocul, blocul de rezerva. Aceste blocuri contin informatii despre initializarea sistemului de fisiere , gestiunea sistemului si refacerea sistemului dupa producerea de erori.

-Benzi de 8MB, fiecare banda avand asociata o harta de biti de dimensiunea 2kB in care un bit corespunde unui bloc de 4KB din cadrul benzii; daca bitul e zero bitul este liber, daca bitul e 1 blocul este alocat. Hartile de biti sunt situate in mod alternativ la sfarsitul si la inceputul benzilor asa incat sa se poata face alocari contigue de pana la 16MB. Se lasa spatiu intre fisierele existente si cele nou create in ideea obtinerii unor alocari de blocuri contigue.

........

Fig. 8. Organizarea benzilor cu harti de biti in sistemul HPFS.

Pentru descrierea fisierelor se utilizeaza F-noduri.

Director

F-nod

Fig. 9. Descrierea fisierelor cu F-noduri.

F-nodurile sunt structuri de date care contin atributele si informatiile legate de localizarea pe disc a fisierelor. Fiecare F-nod are cel mult 8 extensii. Extensiile sunt entitati distincte, fiecare din ele putand adresa blocuri de maxim 16MB.

5.6.4. Organizarea in NTFS (New Technology File System)

Fiecare volum NTFS contine un MFT (Master File System) care este un fisier cu informatii despre fisierele si directoarele de pe volumul respectiv. MFT este organizat ca o succesiune de inregistrari dintre care primele 16 sunt utilizate pentru descrierea MFT-ului insusi si pentru furnizarea informatiei necesare dupa situatii de avarie. Urmatoarele inregistrari din MFT descriu fisierele si directoarele.