STRUCTURI DE FISIERE

Fisierele secventiale

Notiuni de baza

Organizarea secventiala este, desigur, una conceptuala. Functie de caracteristicile fizice ale dispozitivului periferic utilizat se poate stoca fisierul respectiv in alt format si sa fie prezentat utilizatorului ca un fisier secvential. Notiunea de organizare secventiala - aici a inregistrarilor intr-un fisier - este legata de dispozitivul periferic si de suportul fizic utilizat (ex. banda magnetica este, prin natura sa, secventiala). Desigur, fisiere secventiale se pot stoca si pe suportul disc magnetic dispersand inregistrarile in diferite locatii disponibile (care nu sunt una dupa alta ca adresare). Sistemele de operare pastreaza evidenta locatiilor (sectoarelor) ocupate de inregistrari si fisiere si a ordinii in care trebuie citite.

Sfarsitul fiecarui fisier secvential este indicat de un marcaj de sfarsit de fisier - EDF (end of file).

Organizarea secventiala a fisierului

Inreg. nr.1 Inreg. nr.2

Inreg. nr. i  E O F

. . .

Fig. 3.1.1. Fisier secvential

Utilizatorul unui fisier secvential poate sa vada inregistrarile numai in ordine secventiala.

Singurul mod de a gasi o inregistrare este acela de a incepe cautarea de la inceputul fisierului si de a le gasi si extrage in ordinea in care se afla in fisier.

Structura secventiala a unui fisier este convenabila pentru generarea unor rapoarte (ex. statele de salarii), dar aceeasi structura secventiala este totala nefavorabila la actualizarea inregistrarilor. (De exemplu, pentru actualizarea orelor lucrate de un angajat se citeste cartela sa de pontaj si apoi se cauta in tot fisierul inregistrarea angajatului respectiv pentru actualizare, iar pentru urmatorul angajat trebuie reluat procesul de la inceput. Procesul poate fi simplificat daca ordinea cartelelor de pontaj corespunde cu ordinea inregistrarilor din fisierul angajatilor).

Din aceste motive fisierele secventiale sunt de regula stocate in ordine alfabetica sau numerica, in functie de continutul unui camp, numit camp-cheie (key field).

Avand in vedere avantajele oferite de o ordine bine stabilita in prelucrarea fisierelor secventiale, sortarea ocupa un loc important.

Pentru actualizarea unui fisier secvential, noile informatii (in cazul nostru colectia de cartele de pontaj) sunt inregistrate sub forma unui fisier secvential independent, cunoscut sub numele de fisier tranzactional. Acest fisier tranzactional este sortat in ordinea in care este sortat fisierul care trebuie actualizat si inregistrarile fisierului initial sunt actualizate in ordinea lor de aparitie.

Aspecte legate de programare

In ceea ce priveste manipularea fisierelor secventiale din punct de vedere al programatorului, tendinta in cadrul limbajelor de nivel inalt este ca operatiile cu fisiere sa se realizeze prin proceduri care sunt fie definite ca parte a limbajului formal, fie furnizate de extensii ale acestuia, sub forma de biblioteci. In ambele situatii, parametrii procedurilor indica fisierul-tinta si zona de memorie principala in care se scrie sau din care se citesc inregistrarile manipulate.

De exemplu, in Pascal se pot folosi instructiuni de forma:

read (Lista postala, Inregistrare postala)

si

write (Lista postala, Inregistrare postala)

pentru a citi, respectiv a scrie (salva) informatii dintr-un/intr-un fisier secvential identificat ca Lista postala. Alaturi de identificatorul de fisier, in lista de parametri apare si numele Inregistrare postala, utilizat in cadrul programului pentru identificarea blocului de date care se transfera.

Observati ca aceste instructiuni nu contin nici o informatie explicita cu privire la pozitia pe care o au in fisier inregistrarile manipulate.

Fisierul fiind secvential, inregistrarea citita este cea care urmeaza pozitiei curente in cadrul fisierului, iar inregistrarea care se scrie in fisier este plasata imediat dupa pozitia curenta.

Pe langa subrutine care permit manipularea inregistrarilor dintr-un fisier secvential, majoritatea limbajelor de nivel inalt furnizeaza si instrumente pentru detectarea marcajului de sfarsit de fisier.

Fisiere de text

Daca inregistrarea logica dintr-un fisier secvential se rastrange la un singur octet, se considera ca avem un fisier de text (text file). Denumirea fisierului reflecta faptul ca aceste fisiere sunt utilizate de obicei pentru stocarea unor documente care contin text.

Altfel spus, un fisier de text poate fi considerat compus din secvente de randuri separate prin marcaje de sfarsit de rand.

Manipularea fisierelor de text

Din motive legate de stocare, fisierele de text sunt impartite in secvente de octeti care formeaza inregistrari fizice a caror dimensiune e compatibila cu sistemul de stocare utilizat. Manipularea acestor inregistrari fizice este realizata in mod transparent de program.

In realitate, la solicitarea preluarii din fisier a primului octet/primul rand de text, programul citeste una sau mai multe inregistrari fizice si le memoreaza intr-un buffer (zona de tampon) din memoria principala.

Pe masura ce programul transfera continutul buffer-ului catre utilizator, in buffer sunt aduse noi inregistrari si asa mai departe, pana la atingerea sfarsitului de fisier.

La scriere in fisier, programul colecteaza octetii intr-un buffer, pana cand se acumuleaza acolo o inregistrare fizica intreaga - sau s-a ajuns la capatul fisierului si apoi se trece la transferarea efectiva a inregistrarii fizice pe dispozitivul de stocare.

Aspecte legate de programare

Manevrarea fisierelor de text se face cu ajutorul procedurilor predefinite, incluse in definitia formala a limbajului sau in biblioteci oferite ca extensii ale acestuia.

Consideram Symbol o variabila de tip caracter implicata in instructiunea:

read (Vechiul manuscris, Symbol).

Instructiunea de mai sus citeste un octet din fisierul de text identificat ca Vechiul manuscris si atribuie acea valoare variabilei Symbol.

Similar, instructiunea:

write (Noul manuscris, Symbol)

plaseaza octetul atribuit variabilei Symbol la pozitia curenta in fisierul Noul manuscris.

Fisiere indexate

Ideea de indexare este preluata din modul de lucru cu o carte, unde se utilizeaza un index care permite localizarea unui subiect mult mai repede decat prin parcurgerea secventiala a cartii.

Notiuni de baza

Indexul fisierului consta dintr-o lista a valorilor care apar in campurile-cheie ale fisierului, la care se adauga pozitia inregistrarii respective in cadrul dispozitivului de stocare masiva a informatiilor.

Acest mod de organizare presupune sa cunoastem valoarea campului-cheie corespunzator inregistrarii cautate.

Organizarea indexului

Pentru a cauta ceva in inregistrarea identificata prin index este necesar ca indexul sa fie transferat in memoria principala si in acest sens dimensiunea lui trebuie sa se incadreze in limite rezonabile.

O metoda de rezolvare a problemei indecsilor de mari dimensiuni este utilizarea unui index al indexului initial. Astfel indexul general va lua o forma stratificata sau arborescenta.

Aspecte legate de programare

Foarte putine dintre limbajele actuale de programare de nivel inalt contin comenzi specifice pentru manipularea fisierelor prin intermediul unui index. Sistemele de gestiunea bazelor de date furnizeaza instrumente care scutesc programatorul de sarcina de a-si intretine propriile sisteme de fisiere indexate.

Totusi exista si la nivelul limbajelor de programare "caramizile elementare" pentru construirea unui fisier indexat.

De exemplu: Intr-un program scris in limbajul C se poate utiliza functia fsetpos pentru a stabili pozitia curenta in cadrul unui fisier.

Astfel, instructiunea:

fsetpos (Personal, & Pozitie)

solicita ca pozitia curenta in cadrul fisierului Personal sa fie stabilita la locatia identificata prin valoarea variabilei Pozitie.

Daca imediat dupa aceasta instructiune se scrie:

fscanf (Personal, "%s", Nume)

vom obtine numele situat la respectiva pozitie din fisier.

Fisiere dispersate (hashed files)

Sistemul de stocare reprezentat prin fisiere dispersate permite doar accesul direct, fara a utiliza un mod de indexare. Ideea de baza este calcularea pozitiei fiecarei inregistrari in memorie prin aplicarea unui algoritm (algoritmul de dispersie) asupra valorii campului-cheie.

Altfel spus, fiind dat campul-cheie cautat, se poate determina rapid pozitia inregistrarii respective, fara a utiliza o tabela speciala (cazul fisierelor indexate).

Exemplu de tehnica de dispersie

Se imparte zona de memorie de masa alocata pentru fisierul respectiv in mai multe sectiuni, pe care le vom numi containere.

Sa presupunem ca zona de stocare se imparte in 20 de containere. De asemenea, presupunem ca inregistrarile din fisier vor fi cautate dupa numarul de identificare si vom stabili acest camp drept camp-cheie.

Obiectivul nostru urmator este sa convertim orice valoare a campului-cheie intr-o valoare numerica. Acest lucru este oarecum simplu, deoarece vom putea scrie forma binara a fiecarei valori din campul-cheie. Apoi utilizand aceasta interpretare numerica, se va imparti aceasta valoare binara a campului-cheie la numarul de containere, obtinandu-se catul si restul. Aceste resturi vor fi intotdeauna un numar intre 0 si 1

Utilizand acest sistem se poate converti orice valoare din campul cheie intr-un intreg care identifica unul dintre containerele din memoria de masa, unde vom stoca inregistrarea respectiva.

Rezolvarea situatiilor de depasire superioara

Un fisier dispersat trebuie implementat in ideea ca se va ajunge la depasirea capacitatii containerelor. In acest sens trebuie gasita o metoda de solutionare a situatiei.

Metoda tipica de rezolvare a problemei este rezervarea unei zone suplimentare de memorie de masa, unde sa fie inmagazinate inregistrarile care depasesc capacitatea containerelor.

Aceasta zona suplimentara a memoriei de masa se numeste zona de depasire.

In concluzie, daca numarul depasirilor este foarte mare, eficienta acestui tip de fisier scade considerabil.

Din acest motiv, proiectarea unui fisier dispersat presupune o atenta alegere a algoritmului de dispersie, a numarului si a dimensiunilor containerelor , precum si a marimii si structurii zonei de depasire.

Aspecte legate de programare

Limbajele procedurale de nivel inalt folosite in prezent nu ofera o implementare directa a fisierelor dispersate. Acest fapt se datoreaza atat aparitiei unor sisteme de gestiunea bazelor de date performante, cat si dependentei de aplicatie a detaliilor de proiectare (algoritmul de dispersie, numarul si dimensiunea containerelor).

In limbajul C va fi nevoie doar sa se memoreze pozitiile de stocare ale containerelor si sa se utilizeze functia fsetpos pentru localizarea containerului indicat de functia de dispersie.

Tehnicile de dispersie sunt folosite cu mare succes si in distributia datelor in zone ale memoriei interne principale.

Rolul sistemului de operare

Mediul de lucru, in cazul limbajelor de nivel inalt, ofera rutine predefinite pentru manipularea fisierelor componente, care nu intra in sarcina programatorului.

Pentru utilizarea operatiilor de regasire si inserare a inregistrarilor, rutinele comunica cu sistemul de operare, deci acestuia ii revine sarcina manipularii fisierelor.

Sistemul de operare trebuie sa cunoasca structura fisierului, campul-cheie si daca fisierul trebuie salvat.

Functie de tipul fisierului se pot prelua: pozitia curenta in cadrul fisierului, inregistrarea fizica care se afla in buffer-ul din memoria principala.

Pentru gestionarea acestor informatii, sistemul de operare foloseste cate o tabela - numita descriptor de fisier sau bloc de control - pentru fiecare fisier utilizat.

Daca un program lucreaza cu trei fisiere, sistemul de operare va trebui sa construiasca trei descriptori de fisier care sa permita gestionarea acestora. In limbajele de nivel inalt, construirea descriptorului de fisier se initializeaza printr-o rutina numita Open.

In FORTRAN, instructiunea tipica are urmatoarea forma:

OPEN (UNIT = 10, FILE = ,Test File', STATUS = OLD,

ACCESS = SEQUENTIAL)

si solicita sistemului de operare sa construiasca un descriptor de fisier pentru fisierul cu numele Test File.

Parametrii precizati specifica ca:

fisierul va fi indicat ulterior in program ca unitatea logica numarul 10 (UNIT = 10);

numele fisierului este Test File (File = ,Test File');

sistemul de operare ar trebui sa gaseasca deja fisierul in memoria de masa (STATUS = OLD);

structura fisierului este secventiala (ACCESS = SEQUENTIAL).

Din exemplul furnizat se observa ca un fisier poate fi desemnat ulterior in program prin alt nume decat numele lui propriu-zis.

Aceasta distinctie care se face intre numele extern al fisierului si identificatorul utilizat in program reflecta diferenta intre regulile sintactice ale sistemului de operare si cele ale limbajului de programare. Aceasta distinctie intre identificatorii externi si interni de fisier permite, de altfel, un grad mai mare de flexibilitate in sensul ca o procedura proiectata sa manipuleze fisierul prin intermediul identificatorului intern poate fi utilizata ca rutina generica pentru prelucrarea a diferite fisiere.

Dupa prelucrarea fisierului, multe limbaje de programare cer sa fie apelata o rutina numita Close. Aceasta rutina informeaza sistemul de operare ca spatiul de memorie rezervat pentru descriptorul de fisier poate fi folosit in alte scopuri. Pentru anumite fisiere (ex. fisierele txt), rutina Close are si rolul de a comunica sistemului de operare necesitatea transferarii ultimei inregistrari fizice pe dispozitivul de stocare.