sisteme de fisiere

7/26/2019 Sisteme de Fisiere

1/26

6Sisteme de fiiere

Toate aplicaiile de pe un calculator trebuie ssalveze i srecupereze informaii. n timp ce un proceseste n execuie, acesta poate reine o cantitate limitatde informaii n spaiul propriu de adrese ioricum, capacitatea de stocare este limitatla dimensiunea spaiului de adrese virtual. Pentru anumiteaplicaii aceastdimensiune este potrivit, dar pentru altele, cum ar fi rezervrile companiilor aeriene,industria bancar, sau a corporaiilor de stocare a nregistrrilor, este mult prea mic.

O a doua problemn meninerea informaiei n cadrul spaiului de adrese al procesului este catuncicnd procesul se termin, informaia este pierdut. Pentru multe aplicaii, (spre exemplu bazele dedate), informaia trebuie reinut timp de sptmni, luni, sau chiar pentru totdeauna. Este

inacceptabil sdispardupce procesul care o folosete se termin. n plus, nu trebuie sse piardatunci cnd o cdere a sistemului distruge procesul.

O a treia problemeste cse ntlnete frecvent situaia ca mai multe procese sacceseze informaia(pri ale informaiei) n acelai timp. Dac avem un catalog virtual de telefonie stocat n cadrulspaiului de adrese al unui singur proces, numai acel proces l poate accesa. Solu ia acestei problemeeste sse facinformaia independentde orice proces.

Deci, avem nevoie de trei componente eseniale pentru stocarea pe termen lung a informaiei:1. Trebuie sfie posibil sse stocheze o cantitate mare de informaie.2. Informaia trebuie spersiste dupterminarea procesului care o folosete.3. Mai multe procese trebuie spoataccesa informaia n mod concurent.

Soluia uzuala acestor probleme este stocarea informaiilor pe discuri sau pe alte medii externe, nuniti numite fiiere (files). Procesele pot mai apoi s le citeasc i s scrie altele noi dac estenevoie. Informaia stocatn fiiere trebuie sfie persistent, adic, snu fie afectatde crearea sauterminarea proceselor. Un f iier trebuie sdisparnumai atunci cnd proprietarul l terge explicit.

Fiierele sunt administrate de sistemul de operare acesta ocupndu-se de structurarea, numirea,accesarea, folosirea, protejarea i implementarea acestora. Ca ntreg, acea parte a sistemului deoperare care se ocupcu fiiere este cunoscutsub numele de sistem de fiiere (file system).

6.1 Fiiere

6.1.1 Numirea fiierelor

Fiierele reprezintun mecanism de abstractizare. Ele asiguro modalitate de a stoca informaie peun suport extern, de exemplu disc, i de a o citi napoi mai trziu. Acest lucru trebuie fcut ntr-unasemenea mod astfel nct s se ascund de utilizator detaliile despre cum i unde este stocatinformaia i cum funcioneazdiscul n realitate.

Probabil cea mai important caracteristic a unui mecanism de abstractizare este modul n careobiectele administrate sunt denumite. Cnd un proces creeazun fiier, i dacestuia un nume. Cndprocesul se termin, fiierul continu s existe i poate fi accesat de alte procese folosindu-se denumele su.


2/26

Regulile exacte de numire a fiierelor diferntructva de la sistem la sistem, dar toate sistemele deoperare curente permit ca iruri valide, iruri de unu pn la opt caractere. Deci, referat, carteiagenda, sunt nume posibile de fiiere. De obicei cifrele i caracterele speciale sunt de asemeneapermise, deci nume ca 2, sau urgent!sunt valide. Multe dintre sistemele de fiiere permit nume depnla 255 de caractere.

Unele sisteme de fiiere fac distincie ntre literele mici i cele mari (case sensitive), n timp ce altelenu. UNIX face parte din prima categorie, n timp de MS-DOS face parte din a doua. Deci un sistem deoperare UNIX poate avea urmtoarele trei fiiere distincte: carte, Cartei CARTE. In MS-DOS toateaceste nume se referla acelai fiier.

O parantez la sistemele de fiiere este potrivitaici. Att Windows 95 ct i Windows 98 folosescsistemul de fiiere MS-DOS (FAT16) i deci motenesc multe din proprietile sale, cum ar ficonstrucia fiierelor. n plus, Windows NT i Windows 2000 suport sistemul de fiiere MS-DOS (iextensia acestuia FAT32) i deci i motenesc de asemenea proprietile. Oricum aceste ultime dousisteme au de asemenea un sistem nativ de fiiere (NTFS) care are proprieti diferite (cum ar fi numede fiiere n Unicode).

Multe sisteme de operare suport nume de fiiere formate din dou pri, cele dou pri fiindseparate de un punct, cum ar fi prog.c. Partea care urmeaz dup punct se numete tipul sauextensia f iierului i de obicei indicceva despre fiier. n MS-DOS, de exemplu, numele de fiiere au1 pn la 8 caractere, plus opional o extensie de 1 pn la 3 caractere. n UNIX, dimensiuneaextensiei, dac exist, este la latitudinea utilizatorului i un fiier poate avea dou sau mai multeextensii, ca la prog.c.Z, unde .Z este cel mai adesea folosit pentru a indica faptul cfiierul (prog.c)a fost comprimat folosind algoritmul de compresie Ziv-Lempel.

n anumite sisteme (de exemplu UNIX), extensiile fiierelor sunt doar convenii i nu sunt impuse desistemul de operare. Un fiier numit file.txtpoate fi un fiier ce conine text, dar numele are maimult rolul de a aminti proprietarului dect de a transmite vreo informaie calculatorului. Pe de altparte, un compilator de C poate insista ca fiierele pe care le compileazsse termine cu .ci altfel,este posibil srefuze sle compileze.

Convenii ca acestea sunt folositoare ndeosebi atunci cnd acelai program poate manevra mai multetipuri diferite de fiiere. Compilatorului de C, de exemplu, i poate fi dato listde fiiere pe care slecompileze i s le lege mpreun, unele dintre ele fiiere C i unele dintre ele fiiere n limbaj deasamblare. n acest caz extensia devine esenial pentru a spune compilatorului care este fiier C,care este fiier n limbaj de asamblare i care sunt fiiere de alt tip.

Prin comparaie, Windows, este contient de extensii i le atribuie semnificaii. Utilizatorii (sauprocesele) pot nregistra extensii cu sistemul de operare i pot specifica pentru fiecare ce program

deine" acea extensie. Cnd un utilizator face dublu click pe numele unui fiier, programul asociatextensiei sale este pornit cu fiierul ca parametru. De exemplu, fcnd dublu clic pe file.doc sepornete Microsoft Word cu file.docca fiier iniial de editat.

6.1.2 Structura fiierelor

Fiierele pot fi structurate n mai multe moduri. Trei posibiliti uzuale sunt prezentate n figuraurmtoare. Fiierul din figura urmtoare (a) este o secven nestructurat de octei. Prin urmaresistemul de operare nu tie i nu e interesat de ceea ce se afln fiier. Tot ceea ce vede sunt octei.Eventualul sens trebuie s fie impus de programe de la nivelul utilizator. Att UNIX ct i Windowsfolosesc aceastabordare. La un sistem de operare care privete fiierele ca o secvende octei seasiguro flexibilitate maxim. Programele utilizator pot pune ceea ce doresc n cmpurile lor i le potnumi ntr-un mod convenabil. Sistemul de operare nu ne ajut, dar nici nu ne stn cale.

Primul pas spre structurare este artat n (b). n acest model, un fiier este o secvende nregistrride lungime fix, fiecare cu o structur internproprie. Ceea ce st la baza ideii de fiier privit ca o


3/26

secvende nregistrri este faptul coperaia de citire ntoarce o nregistrare i operaia de scrieresuprascrie sau adaugo nregistrare.

Al treilea tip de structurde fiier este artat n (c). n aceastorganizare, un fiier este alctuit dintr-un arbore de nregistrri, nu neaprat toate de aceeai lungime, fiecare coninnd un cmp cheie la opoziie fixdin nregistrare. Arborele este sortat dupcmpul cheie, pentru a permite cutare rapidaunei chei. Operaia de baz n acest caz, nu este s obinem urmtoarea" nregistrare, dei acestlucru este de asemenea posibil, ci sobinem nregistrarea cu o anumitcheie. Pentru fiierul zoodin(c) cineva poate cere nregistrarea care are cheia ponei, de exemplu, fr stie poziia exact nfiier. Mai mult, nregistrrile noi pot fi adugate la fiier, sistemul de operare hotrnd unde s leplaseze, i nu utilizatorul.

6.1.3 Tipuri de fiiere

Multe din sistemele de fiiere suportmai multe tipuri de fiiere. UNIX i Windows de exemplu aufiiere normale i cataloage. UNIX are de asemenea fiiere speciale de tip bloc sau caracter. Fiierelenormale sunt cele care conin informaia utilizatorului. Toate fiierele din figura de mai sus sunt fiierenormale. Cataloagele sunt fiiere de sistem folosite pentru meninerea structurii sistemului de fiiere.Fiierele speciale de tip caracter sunt legate de intrare/ieire i sunt folosite pentru a modelaechipamentele seriale I/O cum ar fi terminalele, imprimantele sau reelele. Fiierele speciale de tipbloc (block special files) sunt folosite pentru a modela discuri.

Fiierele normale sunt n general fiiere ASCII sau fiiere binare. Fiierele ASCII constau n linii detext. Liniile nu trebuie saibtoate aceeai lungime. Marele avantaj al fiierelor ASCII este cpot fiafiate i imprimate aa cum sunt i pot fi modificate cu orice editor de text.

Un alt tip de fiiere sunt fiierele binare, care sunt diferite de fiierele ASCII. Prin imprimarea lorrezultun ir neinteligibil care seamncu un ir de caractere i simboluri aleatoare. De obicei au ostructurinternpe care o cunosc programele care le folosesc.

De exemplu, n figura urmtoare (a) avem un executabil binar simplu extras dintr-o versiune de UNIX.Dei fiierul este practic doar o secvende octei, sistemul de operare va executa fiierul doar dacare un format corect. Acesta are 5 seciuni: antet, text, date, biii de relocare i tabela de simboluri.

Antetul ncepe cu aa numitul numr magic (magic number), care identific fiierul ca executabil(pentru a preveni executarea accidental a unui fiier care nu este n acest format). Urmeazdimensiunile diferitelor seciuni din program, adresa de la care ncepe execuia i civa bii indicatori.Dupantet urmeazseciunile de text i date ale programului propriu-zis. Acestea sunt ncrcate n

memorie i relocate folosind biii de relocare. Tabela de simboluri e folositpentru depanare.


4/26

(a) (b)

Al doilea exemplu de fiier binar este o arhiv, de asemenea din UNIX. Ea constdintr-o colecie deproceduri (module) de bibliotec, compilate dar nelegate nc. Fiecare este prefaatde un antet carei spune numele, data crerii, proprietarul, codul de protecie i dimensiunea. La fel ca la executabile,antetele modulelor sunt pline de numere binare. Copierea lor pe o imprimant, ar produce o secvenneinteligibil.

Fiecare sistem de operare trebuie srecunoasccel puin un tip de fiiere, propriile executabile, darunele recunosc mai multe.

6.1.4 Accesarea fiierelor

Sistemele de operare mai vechi asigurau doar un singur tip de accesare a fiierelor: acces secvenial.n aceste sisteme, un proces putea citi toii octeii sau nregistrrile dintr-un fiier n ordine, ncepndde la nceput, dar nu putea ssaraleator i si citeascntr-o altordine. Fiierele secveniale erauconvenabile atunci cnd se folosea pentru stocare banda magnetici nu discul. Cnd discurile unintrat n folosin pentru stocarea fiierelor, a devenit posibil s se citeasc octeii nregistrrilor norice ordine sau sse acceseze nregistrrile dupcheie i nu duppoziie. Fiierele ale cror octeisau ale cror nregistrri pot fi citite n orice ordine sunt numite fiiere cu acces aleator.

Fiierele cu acces aleator sunt eseniale pentru multe aplicaii, de exemplu, sistemele de baze de date.Dac un client al unor linii aeriene suni vrea s rezerve un loc la un zbor anume, programul derezervri trebuie s fie capabil s acceseze nregistrarea despre acel zbor fr a trebui s citeasc

nregistrrile altor mii de zboruri mai nainte.

Se folosesc doumetode pentru a se specifica de unde se ncepe citirea. n prima dintre ele, fiecareoperaie de citire dpoziia din fiier de unde sse nceapcitirea. n a doua, o operaie specialde


5/26

cutare este oferit pentru a seta poziia curent. Dup o operaie de cutare fiierele pot fi cititesecvenial de la noua poziie curent.

6.1.5 Atributele fiierelor

Fiecare fiier are numele su i datele sale. n plus, sistemele de operare asociaz alte informaiipentru fiecare fiier, de exemplu, data i ora la care fiierul a fost creat i dimensiunea fiierului. Vomnumi aceste informaii suplimentare atributele fiierelor. Lista atributelor variaz considerabil de lasistem la sistem. Tabelul din figura urmtoare aratunele din posibiliti, dar existi altele. Nici unuldin sistemele de operare existente nu le are pe toate, dar fiecare dintre ele exist ntr-un sistem.

Atribut SemnificaieProtecie Cine poate accesa fiierul i n ce felParol Parola necesarpentru a accesa fiierulCreator Identificatorul persoanei care a creat fiierulProprietar Proprietarul curent

Indicator numai-citire 0 pentru citire/scriere; 1 pentru numai citireIndicator ascuns 0 pentru normal; 1 pentru cele ce nu sunt artate la listareIndicator sistem 0 pentru fiiere normale; 1 pentru fiiere sistemIndicator arhiv 0 pentru a fost salvat; 1 pentru trebuie sfie salvatIndicator ASCII/binar 0 pentru fiier ASCII; 1 pentru fiier binarIndicator acces aleator 0 pentru acces numai secvenial; 1 pentru acces aleatoriuIndicator temporar 0 pentru normal; 1 pentru terge fiier la terminare procesIndicator de ncuiere 0 pentru descuiat; 1 pentru ncuiatLungimea nregistrrii Numrul de octei dintr-o nregistrarePoziia cheii Deplasarea cheii n cadrul nregistrriiLungimea cheii Numrul de octei din cheieData crerii Data i ora cnd fiierul a fost creat

Timpul ultimei accesri Data i ora cnd fiierul a fost accesat ultima oarTimpul ultimei modificri Data i ora cnd fiierul a fost modificat ultima oarDimensiunea curent Numrul de octei din fiier

Primele patru atribute se referla protecia fiierului i spun cine l poate accesa i cine nu. n unelesisteme utilizatorul trebuie sprezinte o parolpentru a accesa un fiier, caz n care parola trebuie sfie unul din atribute.

Indicatorii sunt bii sau cmpuri scurte care controleaz sau permit anumite proprieti specifice.Fiierele ascunse, spre exemplu, nu apar n listarea tuturor fiierelor. Indicatorul de arhiveste un bitcare reine dacf iierului i-a fost fcuto copie de siguran. Programul de fcut copii de siguranlterge, iar sistemul de operare l seteaz de fiecare dat cnd fiierul este modificat. n acest fel

programul de fcut copii de sigurantie ce fiiere au nevoie de copii de siguran. Indicatorul detemporar permite ca un fiier s fie marcat pentru tergere automatatunci cnd procesul care l-acreat se termin.

Cmpurile lungimea nregistrrii, poziia cheii i lungimea cheii sunt prezente doar n fiierele n carelocalizarea nregistrrii se poate face dup o cheie. Ele asigur informaia necesar pentru a gsicheile.

Momentele de timp referitoare la data crerii fiierului, data ultimei accesri, data ultimei modificrisunt utile pentru o varietate de scopuri. De exemplu, un fiier sursce are data de modificare dupdata crerii fiierului executabil corespunztor trebuie sfie recompilat.

Dimensiunea curent ne arat ct de mare este fiierul n acest moment. Unele sisteme vechi de

operare ale calculatoarelor mari cereau ca dimensiunea maximsfie specificatla crearea fiierului,pentru ca sistemul de operare s rezerve maximul de spaiu n avans. Sistemele de operare ale


6/26

staiilor de lucru i calculatoarelor personale sunt suficient de inteligente pentru a se descurca fraceastinformaie.

6.1.6 Operaiile fiierelor

Fiierele existpentru a stoca informaie i a permite sfie recuperatmai trziu. Diferite sisteme deoperare oferdiferite operaii care permit salvarea i recuperarea. Mai jos este o discuie despre celmai folosite apeluri de sistem legate de fiiere:

1. Creare (create). Fiierul este creat gol. Scopul acestui apel este anunarea apariieifiierului i setarea anumitor atribute.

2. tergere (delete). Cnd nu mai este nevoie de acesta, fiierul va fi ters pentru aelibera spaiul de pe disc. ntotdeauna existun apel de sistem n acest scop.

3. Deschidere (open). nainte de folosirea unui fiier, un proces trebuie s l deschid.Scopul apelului de deschidere este de a permite sistemului saducatributele i lista deadrese de pe disc n memoria principal, pentru accesul rapid la acestea n urma unorapeluri ulterioare.

4. nchidere (close). Cnd toate accesele s-au terminat i atributele, adresele de pe discnu mai sunt necesare, fiierul ar trebui nchis pentru a elibera spaiul intern de adrese.Multe sisteme de operare ncurajeazacest lucru prin impunerea unui numr maxim defiiere deschise per proces. Un disc este scris n blocuri i nchiderea unui fiier foreazscrierea ultimului bloc din fiier, chiar dacacel bloc s-ar putea sa nu fie complet nc.

5.

Citire (Read). Datele sunt citite din fiier. De obicei, octeii ncep de la poziia curent.Cel care face apelul trebuie sspecifice ct de mult informaie este necesari trebuiede asemenea sasigure o zontampon n care so stocheze.

6. Scriere (write). Datele sunt scrise n fiier, din nou de la poziia curent. Dacpoziiacurent se afl la sfritul fiierului, dimensiunea fiierului se mrete. Dac poziiacurent este n mijlocul fiierului, datele existente sunt suprascrise i pierdute pentrutotdeauna

7. Adugare (append). Acest apel este o forma restrictiv de scriere. Poate doar s

adauge date la sfritul fiierului. Sistemele ce asigurun set minim de apeluri de sistemnu au n general adugarea, dar multe sisteme asigurmetode multiple de a face acelailucru.

8. Cutare (seek). Pentru fiierele cu acces aleatoriu, este necesar o metod care sspecifice de unde s se ia datele. Una din cele mai comune abordri este un apel desistem, cutare, care repoziioneazcursorul fiierului la un punct specific din fiier. Dupce apelul se termin, datele pot fi citite de la sau scrise la acea poziie.

9. Obinerea atributelor (get attributes). De multe ori procesele trebuie s citeascatributele f iierelor pentru a-i ndeplini sarcina. De exemplu, programul UNIX, makeestede multe ori folosit pentru a ntreine dezvoltarea proiectelor software ce conin multefiiere surs. Atunci cnd se apeleaz make, acesta examineaz timpul de modificarepentru toate fiierele surs i fiierele obiect i determin numrul minim de compilri

pentru a aduce totul la zi. Pentru a face acest lucru, trebuie s se uite la atribute, maiexact la timpul de modificare.10. Setarea atributelor (set attributes). Unele din atribute pot fi setate de utilizatori i

pot fi modificate dup ce fiierul a fost creat. Acest apel de sistem face posibilmodificarea. Modul de protecie este un exemplu evident. Majoritatea indicatorilor intrdeasemenea n aceastcategorie.

11. Redenumire (Rename). Se ntmplfrecvent ca un utilizator strebuiascsschimbenumele unui fiier existent. Acest apel de sistem face schimbarea posibil. Nu este mereustrict necesar, deoarece de obicei fiierul poate fi copiat ntr-un fiier nou cu un numenou, iar fiierul vechi poate fi ters.


7/26

6.1.7 Un exemplu de program care folosete apeluri de sistem

n aceastseciune vom examina un program UNIX simplu care copiazun fiier sursntr-un fiier

destinaie. Programul este listat mai jos. Programul are funcionalitate minim i n plus are oraportare de erori i mai redus, dar ne ilustreazmodul de funcionare pentru unele din apelurile desistem legate de fiiere. Programul copyfile, poate fi apelat, de exemplu, prin linia de comand:

copyfile abc xyz

pentru a copia fiierul abcn xyz. Dacxyz existdeja, va fi suprascris. Altfel, va fi creat. Programultrebuie apelat cu exact douargumente, ambele nume valide de fiier.

Cele patru directive #include de la nceputul programului fac ca un numr mare de definiii iprototipuri de funcii s fie incluse n program. Acestea sunt necesare pentru a face programulconform cu standardele internaionale, dar nu ne vom preocupa de acest lucru n continuare.Urmtoarea linie este prototipul funciei main, ceva cerut de ANSI C, dar de asemenea neimportantpentru scopurile noastre.

Prima directiv#define este definirea unui macro care face ca irul de caractere BUF_SIZE s seexpandeze n memorie n numrul 4096. Programul va scrie i va citi din memorie n buci de 4096 deoctei. Se consider un bun exemplu de programare dac se dau nume simbolice constantelor caaceasta i s se foloseasc numele lor n loc de constante. Nu doar c aceast convenie faceprogramul mai uor de citit, dar l i face mai uor de ntreinut. A doua directiv#define determincine poate accesa fiierul de ieire.

Programul principal se numete main i are douargumente, argci argv. Acestea sunt furnizate desistemul de operare atunci cnd programul este apelat. Primul spune cte iruri de caractere au fostprezente la linia de comandcu care a fost invocat programul, inclusiv numele programului. Ar trebui

sfie 3. Al doilea argument este un vector de pointeri la argumente. n apelul exemplificat mai sus,elementele acestui vector ar conine poineri ctre urmtoarele valori:argv[0] = "copyfile"argv[1] = "abc"argv[2] = "xyz"

Prin acest vector programul i acceseazargumentele. Sunt declarate cinci variabile. Primele dou,in_fd i out_fd, vor reine descriptorii de fiier, nite ntregi mici ntori atunci cnd fiierul sedeschide. Urmtoarele dou, rd_counti wt_count sunt variabilele care numr octeii ntori deapelurile de sistem citire readi scriere write. Ultima variabil, buffer, este zona tampon folositpentru a reine datele citite i a asigura datele ce urmeaza f i scrise.

/* Program de copiere a fiierelor.

Verificarea i raportarea erorilor este minim.*/#include /*include fiierele antet necesare*/#include#include#include

int main(int argc, char *argv[]); /*prototip ANSI*/#define BUF_SIZE 4096 /*folosete o zon tampon de 4096 octei*/#define OUTPUT_MODE 0700 /*biii de protecie pentru fiierul de ieire*/int main(int argc, char *argv[]) {

int in_fd, out_fd, rd_count,wt_count;char buffer[BUF_SIZE];

if (argc != 3) exit(1); /*eroare de sintaxdacargc nu e 3*/


8/26

/*Deschide fiierul de intrare i creeazfiierul de ieire*/in_fd = open(argv[1], O_RDONLY); /*deschide fiierul surs*/if (in_fd < 0) exit(2); /*dacnu poate fi deschis, ieire*/out_fd= creat(argv[2], OUTPUT_MODE); /*creeazfiierul destinaie*/if (out_fd< 0) exit(3); /*dacnu poate fi creat, ieire*/

/*Bucla de copiere*/while(TRUE) {

rd_count = read(in_fd, buffer, BUF_SIZE); /*citete un bloc de date*/if (rd_count


9/26

6.1.8 Fiiere direct n memorie

Muli programatori sunt de prere c accesarea fiierelor n modul descris mai sus este greoaie i

neconvenabil, n special dacse face comparaia cu accesarea memoriei obinuite. Din acest motiv,anumite sisteme de operare, au pus la dispoziie o metodde a pune n corespondenun fiier cuspaiul de adrese al unui proces care ruleaz. n mod conceptual, ne putem imagina existena a douapeluri noi de sistem, map (pune n coresponden) i unmap (anuleaz corespondena). Primulofer un nume fiierului i o adres virtual, ceea ce face ca sistemul de operare s pun ncorespondenfiierul cu zona de la adresa virtualdin spaiul de adrese.

De exemplu, spresupunem un fiier f, cu lungimea de 64KO, este pus n corespondencu adresavirtual ce ncepe la adresa 512K. n continuare orice instruciune n cod main care citeteconinutul octetului de la adresa 512K, va primi octetul 0 al fiierului i aa mai departe. n modsimilar, o scriere la adresa 512K+21000 modificoctetul 21000 al fiierului. Atunci cnd procesul setermin, fiierul modificat este lsat pe disc ca i cum ar fi fost schimbat de o combinaie de apeluride sistem seek i write.

Ceea ce se ntmplde fapt este ctabelele interne ale sistemului sunt schimbate sfacf iierul sdevin locul de stocare al zonei de memorie de la 512K la 576K. Prin urmare, o citire de la 512Kcauzeazun defect de pagin, care aduce pagina 0 a fiierului. n mod similar, o scriere la 512K+1100cauzeaz un defect de pagin, aducnd pagina ce conine acea adres, dup care poate avea locscrierea n memorie. n cazul n care pagina este evacuatde algoritmul de nlocuire a paginilor, estescris napoi, la locul potrivit din fiier. Atunci cnd procesul se termin, toate paginile cucorespondenn memorie care au fost modificate sunt scrise la loc n fiierele lor.

Punerea n corespondena fiierelor n memorie funcioneazcel mai bine n sistemele ce suportsegmentare. ntr-un asemenea sistem, fiecare fiier poate fi pus n coresponden cu un segmentpropriu, astfel nct octetul k din fiier este octetul k din segment. n figura de mai jos (a) avem un

proces care are dousegmente, text i date. Spresupunem cacest proces copiazf iiere, la fel caprogramul anterior. Mai nti pune n coresponden fiierul surs, s spunem abc, n unul dinsegmente. Apoi creaz un segment nou i l pune n coresponden cu fiierul destinaie, xyz, nexemplul nostru. Aceste operaii ne aduc la situaia din figura de mai jos (b).

n acest moment procesul poate copia segmentul surs n segmentul destinaie folosind o bucl decopiere obinuit. Nu e nevoie de nici un apel de sistem read sau write. Atunci cnd totul se termin ,se poate executa apelul de sistem unmap pentru a terge fiierele din spaiul de adrese i apoi seiese. Fiierul de ieire, xyz, va exista acum, ca i cum ar fi fost creat n modul convenional.

Dei punerea fiierelor direct n memorie eliminnevoia de I/O, deci face programarea mai uoar,introduce cteva probleme proprii. Este greu ca sistemul de operare s tie dimensiunea exact afiierului de ieire, xyz, n exemplul nostru. Poate spune cu uurin numrul celei mai mari paginiscrise, dar nu poate s tie ci octei au fost scrii n acea pagin. S presupunem c programul

folosete doar pagina 0 i dupexecuie toi octeii sunt n continuare 0 (valoarea iniial). Poate cxyz este un fiier care constn 10 de zero. Poate ce un fiier care constn 100 de zero. Poate ce


10/26

un fiier care constn 1000 de zero. Sistemul de operare nu poate spune. Tot ce poate sfacestescreeze un fiier de lungime egalcu dimensiunea paginii.

O a doua problempoate aprea (eventual) dacun fiier este pus direct n memorie de un proces ideschis n mod convenional pentru citire de un altul. Dac primul proces modific o pagin,schimbarea nu va fi reflectat n fiierul de pe disc pn cnd pagina nu este evacuat. Sistemul

trebuie saibfoarte mare grijpentru a fi sigur ccele douprocese nu vd versiuni inconsistenteale fiierului.

O a treia problem cu punerea direct n memorie este c un fiier poate fi mai mare dect unsegment, sau chiar mai mare dect ntregul spaiu de adrese. Singura cale de ieire este de a aranjaca apelul de sistem map sf ie capabil cpunmai degrabn memorie o poriune din fiier, dect totfiierul. Dei acest lucru funcioneaz, este evident mai puin satisfctor dect punerea n memorie a

ntregului fiier.

6.2 Cataloage

Pentru a organiza i a ine evidena fiierelor, sistemele de fiiere folosesc aa-numitele cataloage(catalogues) sau mape (folders), care n multe sisteme, sunt chiar ele nsele fiiere.

6.2.1 Sisteme cu un singur nivel de cataloage

Cea mai simplformde sistem de cataloage este savem un catalog care sconintoate fiierele,denumit de cele mai multe ori catalog rdcin(root directory). Pe calculatoarele personale mai vechi,acest sistem era des ntlnit, n mare parte din cauz c exista un singur utilizator. Ins trebuieremarcat c i primul super-calculator din lume, CDC 600 avea tot un singur catalog pentru toatefiierele, dei era folosit de mai muli utilizatori n acelai timp, pentru a menine simpldezvoltarea

programelor.Un exemplu de sistem cu un catalog este dat n figura de mai jos. Aici catalogul conine patru fiiere.In figur sunt artai proprietarii fiierelor i nu numele acestora (pentru c proprietarii suntimportani pentru ceea ce urmeaz). Avantajele acestei scheme sunt simplitatea i posibilitatea de alocaliza f iierele repede, n fond este doar un loc unde trebuie cutat.

Problema care apare la un sistem cu un singur catalog i cu mai muli utilizatori este c utilizatoridiferii pot folosi n mod accidental aceleai nume pentru fiierele lor. De exemplu, dacutilizatorul Acreeaz un fiier care se numete mailbox i mai apoi utilizatorul B creeaz i el un fiier care senumete mailbox, fiierul lui B n va suprascrie pe cel al lui A. Prin urmare, aceastschemnu maieste folositpe sistemele multiutilizator.

6.2.2 Sisteme de cataloage cu dounivele

Pentru a evita conflictele cauzate de alegerea identica numelor de fiiere proprii pentru mai muli

utilizatori, urmtorul pas a fost s se dea fiecrui utilizator cte un catalog. n acest mod, numelealese de un utilizator nu interfereaz cu numele alese de alt utilizator i nu e nici o problemdac


11/26

exist fiiere cu acelai nume n dou sau mai multe cataloage. Aceast implementare duce la unsistem ca n figura urmtoare.

n mod implicit n aceast implementare cnd un utilizator ncearc s deschid un fiier, sistemultrebuie stie despre ce utilizator e vorba, pentru a ti n ce catalog scaute. n consecin, e nevoiede o procedurde autentificare, n care fiecare utilizator specificun nume sau un identificator, ceeace nu era necesar la sistemele cu un singur nivel de cataloage.

Dacacest sistem este implementat n forma cea mai simpl, utilizatorii pot accesa doar fiierele dincataloagele lor. n orice caz, o mic extensie permite unui utilizator s acceseze fiierele altorutilizatori atunci cnd se furnizeazo informaie despre proprietarul fiierului care va fi deschis. Deexemplu,

open("x")

ar putea fi apelul pentru deschidea fiierului numit x din catalogul utilizatorului i

open("nancy/x")

ar putea fi apelul pentru deschiderea fiierului numit x din catalogul altui utilizator, Nancy.

Una din situaiile n care utilizatorii au nevoie sacceseze alte fiiere dect ale lor este cea n care seruleazprogramele executabile ale sistemului. Existena unor copii ale tuturor programelor utilitare nfiecare catalog este n mod cert ineficient. La o adic e nevoie de un catalog de sistem care sconinprogramele executabile.

6.2.3 Sisteme de cataloage ierarhice

Sistemul cu dou nivele de cataloage elimin conflictele de nume dintre utilizatori, dar nu estesatisfctor pentru utilizatorii cu un numr mare de fiiere. Chiar i pe un singur calculator personaleste neconvenabil. Este destul de ntlnitsituaia n care un utilizator vrea s i grupeze fiiereledup un model logic. Un profesor de exemplu, poate avea o colecie de fiiere, care mpreunformeazo carte, pe care el o scrie pentru un curs, o a doua colecie de fiiere coninnd programelestudenilor trimise pentru un alt curs, un al treilea grup de fiiere, coninnd codul unui sistem avansatde scris compilatoare pe care el l construiete, un al patrulea grup de fiiere coninnd propunerile decontracte de cercetare i de asemenea alte fiiere pentru pota electronic, amnunte despre ntlniri,lucrri pe care le scrie i aa mai departe. Este necesaro metodde a grupa aceste fiiere n moduriflexibile, alese de utilizator.

Astfel ajungem la nevoia de a avea o ierarhie general(de ex., un arbore de cataloage). Prin aceast

abordare, fiecare utilizator are attea cataloage cte are nevoie, astfel nct fiierele sfie grupate nmoduri ct mai naturale. Aceastabordare este exemplificatn f igura urmtoare. Aici, cataloagele A,


12/26

B i C, fiecare coninute n catalogul rdcin, aparin unor utilizatori diferii, dintre care doi au creatsubcataloage pentru proiectele la care lucreaz.

Abilitatea ca utilizatorii screeze un numr arbitrar de subcataloage ofero unealtfoarte puternicde structurare pentru utilizatori s-i organizeze munca. Din acest motiv, majoritatea sistemelor deoperare moderne sunt organizate n acest scop.

6.2.4 Numele cilor

Atunci cnd sistemul de fiiere e organizat ca un arbore de cataloage, este nevoie de o metodde aspecifica numele. Existdoumetode diferite care se folosesc. n prima metodse dun nume decale absolut (absolut path name) constnd n calea de la catalogul rdcin pn la fiier. Spreexemplu, calea /usr/ast/mailboxnseamncn catalogul rdcinavem un subcatalog usr, care

la rndul lui conine un subcatalog ast, care conine fiierul mailbox. Numele de ci absolute ncepntotdeauna de la catalogul rdcini sunt unice. n UNIX, componentele cii sunt separate de /. nWindows separatorul este \. Prin urmare aceeai cale n cele dousisteme s-ar fi scris aa:

Windows: \usr\ast\mailboxUNIX: /usr/ast/mailbox

Indiferent ce caracter separator se utilizeaz, dac primul caracter al numelui cii este chiarseparatorul, atunci este vorba de o cale absolut.

Cellalt tip de nume este nume de cale relativ(relative path name). Acesta este folosit n conjunciecu conceptul de catalog de lucru (working directory), numit de asemenea i catalog curent (current

directory). Utilizatorul poate desemna un catalog ca i catalog de lucru, caz n care toate cile care nuncep de la catalogul rdcin sunt considerate relative la catalogul curent. De exemplu, daccatalogul curent este: /usr/ast, atunci fiierul a crui cale absoluteste /usr/ast/mailboxpoate fireferit simplu ca mailbox. Cu alte cuvinte, comanda UNIX,

cp /usr/ast/mailbox /usr/ast/mailbox.bak

i comanda

cp mailbox mailbox.bak

fac exact acelai lucru dac/usr/asteste catalogul de lucru. Forma relativeste de multe ori maiconvenabil, dar face exact acelai lucru ca forma absolut. Unele programe trebuie sacceseze unanume fiier indiferent de catalogul de lucru. n acest caz, trebuie folosite ntotdeauna nume de ciabsolute.


13/26

Majoritatea sistemelor ce suport un sistem de fiiere ierarhic au dou intrri speciale n fiecarecatalog, notate cu "." i "..", pronunate de obicei punct" respectiv punct punct". "." se referlacatalogul curent n vreme ce ".." se refer la catalogul printe. Pentru a vedea cum sunt acesteafolosite, sconsiderm arborele UNIX din figura urmtoare.

Un anume proces are ca i catalog de lucru /usr/ast. Poate folosi ".." pentru a merge n sus n arbore.De exemplu poate copia fiierul /usr/lib/dictionary n catalogul propriu folosind comanda:

cp ../lib/dictionary .

Prima cale anunsistemul smeargn sus (n catalogul usr), apoi smeargn jos spre catalogul libpentru a gsi fiierul dictionary. Al doilea argument, "." indiccatalogul curent. Atunci cnd comandacp primete un nume de catalog (inclusiv punct) ca ultim argument, copiaz toate fiierele acolo.Bineneles, o metodmai normalde a copia ar fi:

cp /usr/lib/dictionary .

Aici, folosirea punctului l scutete pe utilizator de tastarea cuvntului dictionary a doua oar. Daroricum, tastarea comenzii:

cp /usr/lib/dictionary dictionary

funcioneaz, la fel cum funcioneazi

cp /usr/lib/dictionary /usr/ast/dictionary

Toate aceste comenzi fac exact acelai lucru.


14/26

6.2.5 Operaiile cataloagelor

Apelurile de sistem permise pentru administrarea cataloagelor au o variaie foarte mare de la sistem lasistem, spre deosebire de cele de la fiiere. Pentru a v face o impresie asupra lor i cumfuncioneaz, vom da un exemplu (specific UNIX).

1.

Creare (create). Se creazun catalog. Este gol, excepie fcnd "." i "..", care sunt puseacolo automat de sistem (sau n anumite cazuri de programul mkdir).2. tergere (delete). Se terge un catalog. Se poate terge numai un catalog gol. Un catalog

care conine doar "." i ".." se considergol i acestea nu pot fi terse n mod normal.3. Deschidere catalog (opendir). Cataloagele pot fi citite. Spre exemplu, pentru afiarea

tuturor fiierelor dintr-un catalog, un program deschide catalogul pentru a citi numele tuturorfiierelor pe care le conine. nainte ca un catalog s fie citit, trebuie deschis, analog cudeschiderea si citirea fiierelor.

4. nchiderea cataloagelor (closedir). Cnd un catalog a fost citit, ar trebui s fie nchis,pentru a elibera spaiul din tabela intern.

5. Citirea cataloagelor (readdir). Acest apel ntoarce urmtoarea intrare ntr-un catalogdeschis. La nceputuri, era posibil sse citeasccataloagele folosind apelul de sistem obinuitde read (citire), dar aceastabordare are dezavantajul cforeazprogramatorul scunoasci s se descurce cu structura intern a cataloagelor. Prin contrast, readdir ntoarce

ntotdeauna o intrare n formatul standard, indiferent care din structurile posibile de cataloagese folosete.

6. Redenumirea (rename). n multe privine, cataloagele sunt la fel ca fiierele i pot firedenumite la fel ca fiierele.

7. Legarea (link). Legarea este o tehnic ce permite unui fiier s apar n mai mult de uncatalog. Acest apel de sistem specific un fiier existent i un nume de cale i creeaz olegturde la fiierul existent la numele specificat prin cale. n acest mod, acelai fiier poateaprea n mai multe cataloage.

8. Dezlegarea (unlink). Se terge o intrare dintr-un catalog. Dac fiierul care se dezleageste prezent ntr-un catalog, (cazul normal), este ters din sistemul de fiiere. Dace prezent

n mai multe cataloage, doar numele specificat prin cale este ters. Celelalte rmn. n UNIX,

apelul de sistem folosit pentru tergerea fiierelor i prezentat mai devreme este de faptunlink.

Lista de mai sus ne aratcele mai importante apeluri de sistem, dar mai sunt i altele, spre exemplu,pentru administrarea informaiilor legate de protecia cataloagelor.

6.3 Implementarea sistemului de fiiere

6.3.1 Planul sistemului de fiiere

Sistemele de f iiere sunt stocate pe discuri. Majoritatea discurilor pot fi mprite n una sau mai multepartiii, cu sisteme de fiiere independente pe fiecare dintre partiii. Sectorul 0 al discului se numeteMBR (Master Boot Record Inregistrarea principal de pornire) i este folosit pentru a startacalculatorul. La sfritul MBR-ului se afltabela de partiii. Aceasttabeloferinformaii cu privire la

nceputul i sfritul tuturor partiiilor. Numai una din partiiile din tabeleste marcatca activ. Lapornirea calculatorului este executat informaia din MBR. Primul lucru pe care l face programul dinMBR este slocalizeze partiia activ, sciteascprimul ei bloc, numit bloc de iniializare (boot block)i s l execute. Programul din blocul de iniializare ncarc sistemul de operare coninut n partiiarespectiv. Pentru uniformitate fiecare partiie ncepe cu un bloc de iniializare, chiar dacnu conineun sistem de operare. Oricum, partiia poate sconinn viitor un astfel de sistem de operare i decipstrarea unui bloc de iniializare devine o idee potrivit.

n afarde faptul c ncep cu un bloc de iniializare, planul partiiei este foarte variabil n funcie desistemul de fiiere. De multe ori sistemul de fiiere va conine unele din elementele prezentate n


15/26

figura urmtoare. Primul element este superblocul (superblock). Coninnd toi parametrii principalilegai de sistemul de fiiere, el este citit n memorie cnd calculatorul este iniializat sau cnd sistemulde fiiere este creat pentru prima dat. Informaia tipicdin superbloc conine un numr ce identifictipul de sistem, numrul de blocuri din sistemul de fiiere i alte informaii administrative importante.

Apoi pot urma informaii despre blocurile libere din sistemul de fiiere, spre exemplu sub form dehartde bii sau listde pointeri. Aceasta poate fi urmatde i-noduri, care este un vector de structuride date, cu cte un i-nod pentru fiecare fiier, coninnd informaii exhaustive cu privire la acesta.Dupaceasta poate urma catalogul rdcin, ce reprezint vrful arborelui sistemului de fiiere. ncele din urm, restul discului este n general ocupat de toate celelalte cataloage i fiiere.

6.3.2 Implementarea fiierelor

Probabil c cea mai important discuie legat de implementarea stocrii de fiiere este pstrarealegturii ntre fiiere i blocurile alocate acestora. n funcie de sistemul de operare sunt folositediferite metode.

Alocarea continu

Cea mai simplschemde alocare este de a stoca fiecare fiier ca o niruire continude blocuri. nacest fel pe un disc cu blocuri de 1KB, un fiier de 50KB ar avea alocate 50 de blocuri consecutive. Totpentru un astfel de fiier, pentru un disc cu blocuri de 2KB, ar fi necesare 25 de blocuri consecutive.

Figura urmtoare (a) prezintun exemplu de alocare continude spaiu de stocare. n acest caz sunt

evideniate primele 40 de blocuri, ncepnd cu blocul 0 din partea stng. Un fiier A, cu lungimea depatru blocuri, este scris pe disc ncepnd de la blocul 0. Urmeazun fiier B, de ase blocuri lungime,acesta este scris imediat dupsfritul fiierului A. De notat faptul cfiecare dintre fiiere ncepe cuun nou bloc, astfel, dac fiierul A are ca dimensiune 3.5 blocuri, o parte din spaiu va fi irosit lasfritul ultimului bloc. n figur sunt reprezentate apte fiiere, fiecare ncepnd cu blocul imediaturmtor ultimului bloc al fiierului anterior. Haurarea este folositdoar pentru a diferenia fiierele.

Alocarea continude spaiu are douavantaje principale. Primul avantaj este implementarea simpl,aceasta doarece a ine minte locaia blocurilor unui fiier se reduce la a reine dounumere: adresaprimului bloc i numrul blocurilor ce aparin fiierului. Dndu-se numrul primului bloc, numrulblocului urmtor poate fi obinut printr-o simpladunare.

Al doilea avantaj este performana crescut, ntregul fiier putnd fi citit de pe disc ntr-o singuroperaie. Este necesar o singur operaie de localizare (pn la primul bloc). Apoi, nu mai sunt


16/26

necesare alte operaii de localizare sau ntrzieri de rotaie pentru ca datele s fie citite la vitezamaxim de pe disc. Astfel alocarea continu este simplu de implementat i are o performancrescut.

Din pcate, alocarea continuare i un mare dezavantaj: n timp discul devine fragmentat. Pentru anelege aceasta mai bine, surmrim (b). Aici doufiiere, D i F au fost terse. Cnd un fiier a fostters, blocurile sale sunt eliberate, lsnd o serie de blocuri libere pe disc. Discul nu este comprimat nacest caz pentu a elimina aceste goluri, deoarece aceasta ar nsemna copierea tuturor blocurilor ceurmeaz, posibil milioane de astfel de blocuri. Ca rezultat, discul este n cele din urm format dinfiiere i goluri, cum este ilustrat n figur.

Iniial, fragmentarea nu este o problemdeoarece fiecare fiier nou poate fi scris la sfritul discului,dupterminarea tuturor celorlalte fiiere. Totui, n cele din urm, discul va fi complet ocupat i atunciva fi necesarfie compactarea, care este o operaie neoptim, sau refolosirea spaiului liber din goluri.Folosirea acestui spaiu nseamnpstrarea unei liste de goluri, lucru realizabil n practic. Totui, cndun fiier nou este creat, este necesar cunoaterea apriori a dimensiunii finale a acestuia pentru aalege golul de dimensiunile potrivite pentru stocare.

Imaginai-vconsecinele unui astfel de design. Un utilizator folosete un editor de texte pentru a creaun nou fiier. Primul lucru pe care programul l ntreabeste care va fi dimensiunea finala acestuidocument. ntrebarea este obligatorie, altfel editorul nu va putea fi folosit. n cele din urm, dacdimensiunea se dovedete prea mic, programul va trebui s i ncheie funcionarea prematur,deoarece golul folosit este complet utilizat i nu mai exist loc n continuare pentru a scrie i restulfiierului. Dacutilizatorul ncearcsocoleascaceastproblemintroducnd o valoare exagerat demare ca dimensiune finala fiierului, sspunem 100 MB, este posibil ca editorul snu gseascungol de o astfel de dimensiune i sanune faptul cfiierul nu poate fi creat. Desigur utilizatorul vaavea opiunea de a ncerca cu o dimensiune mai mic, sspunem 50MB de aceasta dati tot aapncnd un gol de dimensiunile potrivite este gsit. Un astfel de design este nsinacceptabil.

Exist ns o situaie n care alocarea continu de spaiu este fezabil i, n fapt, utilizat pe scarlarg: la CD-ROM-uri. Aici dimensiunile tuturor fiierelor sunt cunoscute apriori i nu se vor modifica lautilizri diferite ale sistemului de fiiere de pe CD-ROM. Alocarea continua fost n fapt folositpentrudiscurile magnetice, cu muli ani nainte, datorit simplitii i performanelor ridicate (pe atunci nuconta foarte mult prerea utilizatorilor). Apoi ideea a fost abandonatdatoritabsurditii de a declaradimensiunea finalla crearea unui nou fiier. Totui cu lansarea CD-ROM-urilor, a DVD-urilor i a altorsuporturi de date optice cu o singurscriere, din nou alocarea continupare o idee foarte bun. De

aceea este utilstudierea sistemelor vechi i ideilor ce sunt simple i clare conceptual, deoarece pot fiutile n viitor n situaii surprinztoare.


17/26

Alocarea cu liste nlnuite

A doua metod pentru stocarea fiierelor este de a pstra pe fiecare dintre acestea ntr-o listnlnuit de blocuri, aa cum arat figura urmtoare. Primul cuvnt al fiecrui bloc este folosit capointer la urmtorul. Restul blocului este destinat datelor.

Fiier A

Spre diferende alocarea continu, n aceastmetodpot fi folosite toate blocurile. Spaiul nu estepierdut din cauza fragmentrii (cu excepia fragmentrii interne din ultimul bloc). De asemenea, estesuficient ca intrarea catalogului s pstreze adresa primului bloc. Urmtoarele blocuri pot fi aflatepornind de la acesta. Pe de altparte, dei citirea unui fiier este pur secvenial, accesul aleator esteextrem de ncet. Pentru a ajunge la blocul n, sistemul de operare trebuie snceapcu nceputul i sciteasccele n-1 blocuri dinaintea sa, cte unul pe rnd. Evident c, realiznd attea operaii de citire,procesul va fi dureros de ncet.

De asemenea, cantitatea de date ce pot fi stocate ntr-un bloc nu mai este o putere a lui doi, deoarecepointerul ocup el nsui civa octei. Dei nu imposibil de realizat, avnd o astfel de dimensiunespecificeste mai ineficient deoarece multe programe executoperaii de citire i scriere pe blocuri acror dimensiuni este o putere a lui doi. Avnd primii octei ocupai de pointerul la blocul urmtor,citirea ntregului bloc necesit preluarea i concatenarea informaiilor din dou blocuri, ceea cegenereazo ntrziere din cauza copierii.

Ambele dezavantaje ale alocrii folosind liste nlnuite pot fi eliminate prin preluarea pointerului dinfiecare bloc i pstrarea acestuia ntr-o tabel n memorie. Figura urmtoare prezint o astfel detabelpentru exemplul anterior. n ambele figuri avem douf iiere. Fiierul A folosete blocurile 4, 7,2, 10 i 12 n aceastordine, iar fiierul B folosete n ordine blocurile 6, 3, 11 i 14. Folosind tabela

din figura urmtoare, putem ncepe cu blocul 4 i surmm lanul pnla sfritul fiierului. Acelailucru poate fi obinut pornind de la blocul 6. Ambele lanuri sunt terminate cu un marcator special (nexemplul nostru -1) ce nu este un numr de bloc valid. O astfel de tabel pstrat n memoriaprincipaleste numitFAT (File Allocation Table - Tabelde alocare a fiierelor).

Folosind aceastorganizare, ntregul bloc este destinat pstrrii datelor. Mai mult dect att, accesulaleator este mult uurat. Dei lanul trebuie n continuare s fie urmat pentru a gsi o locaie dat

ntr-un fiier, lanul este n ntregime n memorie i poate fi astfel urmat nct snu se fac nici oreferire la disc. Ca i n cazul metodei anterioare, este suficient ca intrarea catalogului spstreze unsingur ntreg (numrul blocului de start) i pornind de la acesta slocalizam toate blocurile, indiferentct de mare este fiierul.

Dezavantajul principal al acestei metode este cntreaga tabeltrebuie pstratn memorie tot timpulpentru ca sistemul sfuncioneze. Cu un disc de 20GB i o dimensiune a blocurilor de 1KB, o tabel


18/26

are nevoie de 20 de miloane de intrri, cte una pentru fiecare dintre cele 20 de milioane de blocuri.Fiecare intrare trebuie saibcel puin 3 octei. Pentru o vitezcrescut la regsirea informaiei artrebui sfie 4 octei. n acest fel tabela va ocupa tot timpul pn la 60 MB sau 80MB din memoriaprincipal, depinznd de optimizrile sistemului n timp i spaiu. Conceptual, tabela poate fi stocati

n memoria paginat, totui ar ocupa n continuare o cantitate mare de memorie virtuali spaiu pedisc, n timp ce ar genera un trafic crescut de paginare.

I-noduri

Ultima metodprezentat, pentru a pstra corespondena ntre fiiere i blocurile alocate, este de aasocia cu fiecare fiier o structurde date numiti-nod(prescurtare de la index-node - nod-index),ce pstreazatributele i adresele pe disc ale blocurilor ce aparin fiierului. Un exemplu simplu esteprezentat n figura urmtoare.


19/26

Dndu-se un i-nod, este posibil s gsim apoi toate blocurile fiierului. Marele avantaj al acesteimetode, fade fiierele nlnuite folosind o tabeln memorie, este aceea cun i-nod trebuie sfie

n memorie doar cnd fiierul corespunztor este accesat. Dac fiecare i-nod ocup n octei i unmaxim de k fiiere pot fi accesate simultan, memoria totalocupatde un vector coninnd i-nodurileacestor f iiere este de doar kn octei. Doar acest spaiu trebuie alocat n avans.

Acest vector este n general mult mai mic dect spaiul ocupat de tabela de fiiere descris nseciunea anterioar. Motivul este simplu. Tabela ce pstreazlista nlnuita tuturor blocurilor esteproporional n dimensiuni cu ntregul disc. Dacdiscul are n blocuri, tabela are nevoie de n intrri.Pe msurce discul crete n dimensiuni, tabela crete n dependen liniar. Prin contrast, metodafolosind i-noduri necesit un vector n memorie cu dimensiuni proporionale cu numrul maxim defiiere ce pot fi accesate simultan. Nu are relevanfaptul cdiscul poate avea 1 GB sau 10 GB sau100 GB.

O problemcu i-nodurile este aceea c fiecare dintre ele are un spaiu pentru un numr limitat deadrese de disc, ce se ntmplcnd un fiier crete peste aceast limit? O soluie este rezervareaultimei adrese de disc nu pentru un bloc de date, ci pentru adresa unui bloc ce con ine mai multe

adrese de blocuri de disc, aa cum se observn figura de anterioar. O metodchiar i mai avansateste pstrarea a dousau mai multe astfel de blocuri ce conin adrese de disc sau chiar blocuri cepstreazblocuri de disc pline de adrese.

6.3.3 Implementarea cataloagelor

nainte ca un fiier spoatfi citit, el trebuie deschis. Cnd un fiier este deschis, sistemul de operarefolosete calea indicat de utilizator pentru localizarea intrrii catalogului. Intrarea catalogului oferinformaia necesar pentru localizarea blocurilor de disc. Depinznd de sistem, aceast informaiepoate s fie adresa pe disc a ntregului fiier (alocare continu), numrul primului bloc (amndouschemele folosind liste nlnuite), sau numrul i-nodului. n toate cazurile, funcia principal a

sistemului de cataloage este s pun n coresponden numele ASCII al fiierului cu informaianecesarlocalizrii datelor.

O problem asemntoare este aceea a pstrrii atributelor. Toate sistemele de fiiere pstreazatribute pentru acestea, de exemplu creatorul fiierului i momentul de timp al crerii, care trebuie iele stocate undeva. O posibilitate evident este pstrarea lor direct n intrarea catalogului. Multesisteme fac exact acest lucru. Aceastopiune este reprezentatn figura urmtoare (a).

n acestproiectare imediat, un catalog este reprezentat de o listde intrri de dimensiune fix, cteuna pentru fiecare fiier, coninnd un nume de fiier (de lungime fix), o structurpentru atributelefiierului i una sau mai multe adrese de disc (pn la o dimensiune maxim) indicnd locaiablocurilor de disc asociate.

Pentru sistemele ce folosesc i-noduri, o altposibilitate pentru pstrarea atributelor este chiar n i-nod,dect n intrrile cataloagelor. n acest caz, intrarea de catalog poate sf ie mai scurt: doar un nume


20/26

de fiier i un numr de i-nod. Aceastabordare este reprezentat n (b). Aa cum vom vedea maitrziu, aceastmetodare anumite avantaje prin comparaie cu pstrarea n intrarea de catalog. Celedou abordri prezentate n figura de mai sus corespund sistemelor MS-DOS/Windows i respectivUNIX.

Pnacum am presupus cf iierele au nume scurte de lungime fix. n MS-DOS fiierele au ntre 1-8

caractere pentru numele de baz i o extensie opional de 1-3 caractere. n UNIX Versiunea 7,numele de fiiere erau de 1-14 caractere, incluznd orice extensie. Totui, aproape toate sistemele deoperare moderne suportnume de fiiere mai mari i de lungimi variabile. Cea mai simplabordarepentru a implementa acest lucru este sfixm o limitpentru lungimea numelui fiierului, tipic 255caractere i apoi folosirea uneia din posibilitile ilustrate n figura de mai sus, cu 255 caractererezervate pentru fiecare nume de fiier. Aceastabordare este simpl, nsirosete un spaiu mare destocare din catalog, deoarece doar un numr limitat de fiiere au denumiri att de lungi. Din motivede eficien, o structurdiferiteste necesar.

O idee este s renunm la ideea c toate cataloagele au aceeai dimensiune. n aceastmetod,fiecare intrare de catalog are o poriune fix, tipic ncepnd cu lungimea intrrii, apoi urmndinformaii cu un format fix, n general coninnd proprietarul, timpul crerii, o informaie de protejare

i alte atribute. Aceastprim informaie de lungime fixeste urmatde numele fiierului, orict delung ar fi acesta, aa cum este ilustrat n figura de mai jos (a).

ZONANume

n acest exemplu avem trei fiiere: project-budget, personnel i foo. Fiecare nume de fiier estencheiat de un caracter special (n general 0), ce este reprezentat n f igurde un ptrat cu o cruciulin interior. Pentru a permite fiecrui catalog s nceap aliniat la dimensiunea unui cuvnt, fiecarenume de fiier este completat cu un numr ntreg de cuvinte, reprezentat n figur prin csuehaurate.

Un dezavantaj al acestei metode este cla tergerea unui fiier, un spaiu liber de dimensiuni variabileeste introdus n catalog, n care urmtorul fiier poate snu aibsuficient loc. Aceastproblemammai ntlnit-o la alocarea continua fiierelor pe disc, numai cacum compactarea catalogului este

fezabil, ntruct el este n ntregime n memorie. O alt problem este c o intrare de catalog se


21/26

poate ntinde pe mai multe pagini, astfel nct pot aprea erori de paginare la citirea numelui unuifiier.

O alt posibilitate de a trata problema numelor de dimensiune variabil este de a face intrrile decataloage de lungime fixi de a pstra numele de fiiere mpreunntr-o zonla sfritul catalogului,aa cum este reprezentat n figura anterioar(b). Aceastmetodare avantajul cla tergerea unei

intrri, urmtorul fiier va ncpea mereu n locul liber. Desigur zona de nume trebuie ntre inutierori de paginare pot sapar n continuare n timpul procesrii numelor de fiiere. O micvictorieaici este lipsa necesitii ca numele de fiiere snceapaliniate la nivel de cuvnt, aa cnu mai suntnecesare caracterele de umplere dupnumele de fiiere (b), n timp ce ele sunt necesare n (a).

n toate abordrile de pnacum, cataloagele sunt parcurse liniar de la nceput i pnla sfritul lorpentru regsirea unui fiier. Pentru cataloage extrem de mari, cutarea liniarpoate s fie lent. Omodalitate de cretere a vitezei de cutare este folosirea unei tabele de dispersie n fiecare catalog. Oalt modalitate pentru creterea vitezei este pstrarea rezultatelor cutrilor anterioare. naintea

nceperii unei proceduri de cutare, se verific nti printre rezultatele operaiilor anterioare dincatalog. Dac este prezent printre acestea, atunci fiierul poate fi localizat imediat, eliminndnecesitatea unei cutri greoaie. Desigur aceastvariantfuncioneazcu succes doar dacun numr

mic dintre fiiere este apelat n marea majoritate a cazurilor.

6.3.4 Fiiere partajate

Cnd un numr de utilizatori lucreazmpreunla un proiect, apare necesitatea de a partaja accesulla aceleai f iiere. n consecin, este de preferat ca un fiier partajat saparsimultan n cataloagediferite, aparinnd de utilizatori diferii. Figura urmtoare prezintun sistem de fiiere, cu doar unuldintre fiierele lui C prezent i n cataloagele lui B. Lanul ntre catalogul lui B i fiierul partajat senumete legtura. nsui sistemul de fiiere n acest caz este un graf orientat fr cicluri i nu unarbore.

Partajarea fiierelor este folositoare, totui introduce anumite probleme. Pentru nceput, daccataloagele conin adrese de disc, atunci o copie a adreselor de disc va trebui fcutn catalogul lui B,la crearea unei legturi. DacB sau C deschid fiierul, noile blocuri vor fi prezente doar n catalogulutilizatorului ce execut operaiile. Schimbrile nu vor fi vizibile celuilalt utilizator, n acest felpierzndu-se scopul principal al partajrii.


22/26

Aceasta problem poate fi rezolvat n dou moduri. n prima soluie, blocurile de disc nu suntprezente n cataloage, ci doar o mic structur de date asociat fiierului nsui. In acest cazcataloagele indicdoar spre aceaststructur. Aceasta este abordarea folositn UNIX (unde aceaststructurde date este i-nodul).

n a doua soluie, B are o legtur ctre fiierele lui C lsnd sistemul s creeze pentru el un nou

fiier, de tipul LEGTURi pstrnd acest fiier n catalogul lui B. Acest nou fiier conine doar caleacomplet ctre fiierul spre care se creaz legtura. Cnd B citete din fiierul legat, sistemul deoperare vede cf iierul citit este de tipul LEGTUR, cautapoi fiierul respectiv i ncarcoriginalul.

Aceastabordare se numete legtursimbolic.

Fiecare dintre metode are i dezavantaje. n cazul primei metode, cnd B creeazo legturla fiierulpartajat, i-nodul l pstreaz pe creator ca fiind C. Crearea unei legturi nu schimb proprietarulfiierului (vezi figura urmtoare), dar crete contorul de legturi din i-nod, n acest fel sistemul tiecte intrri de cataloage indicspre fiierul respectiv.

Catalogul lui C Catalogul lui B Catalogul lui C Catalogul lui B

Dac C ncearc apoi s tearg fiierul, sistemul este pus n faa unei situaii delicate. Dacndeprteazfiierul i terge i-nodul, B va avea o intrare de catalog indicnd spre un i-nod invalid.Daci-nodul este refolosit apoi de un alt fiier, legtura lui B va indica ctre un fiier greit. Sistemulpoate svaddin contorul din i-nod cfiierul este ncn uz, dar nu existnici o modalitate pentru els localizeze toate intrrile de catalog pentru acest fiier, ca s le tearg. Indicatori ctre cataloagenu pot fi pstrai n i-nod deoarece pot exista un numr nelimitat de cataloage.

Singura variant viabileste tergerea intrrii de catalog a lui C, dar lsarea intacta i-nodului, cucontorul avnd valoarea 1, ca n figura de mai sus (c). Acum avem o situa ie n care B este singurulutilizator ce are o intrare de catalog ctre un fiier din proprietatea lui C. Dac sistemul permite

interogri, C va fi n continuare rspunztor pentru fiier, pncnd B decide srenune la legtur.n acest caz contorul ajunge la valoarea 0 i fiierul este ters.

Cu legturi simbolice aceast problem nu apare deoarece doar creatorul fiierului are un indicatorctre i-nod. Utilizatorii, ce au creat legturi la fiier, au doar calea ctre fiier i nu indicatori i-nod.Cnd proprietarul terge fiierul, acesta este complet distrus. ncercri ulterioare de acces la fiier voreua, deoarece sistemul este incapabil s localizeze fiierul. tergerea unei legturi simbolice nuafecteazfiierul n nici o msur.

Problema cu legturile simbolice este timpul suplimentar necesitat de ctre acestea. Fiierul coninndcalea trebuie citit, apoi aceasta trebuie parcurstreptat i urmat, componentcu component, pncnd i-nodul este regsit. Toataceastactivitate poate implica un numr suplimentar de accese ladisc. Mai mult dect att, este nevoie de cte un i-nod suplimentar pentru fiecare legtursimbolicpentru a pstra calea ctre fiier; ca i optimizare, dac dimensiunile cii sunt reduse, sistemul arputea pstra aceast informaie chiar n i-nod. Legturile simbolice au avantajul c pot fi folosite


23/26

pentru a indica spre fiiere ale unor maini aflate oriunde, prin simpla pstrare a adresei de reea aacesteia n plus fade informaia legatde calea fiierului.

6.3.5 Gestiunea spaiului pe disc

Fiierele sunt n mod uzual pstrate pe disc, de aceea administrarea spaiului de disc este crucialpentru proiectanii sistemelor de fiiere. Doustrategii sunt posibile pentru pstrarea unui fiier de noctei: n octei consecutivi sunt alocai pe disc, sau fiierul este mprit ntr-un numr de blocuricontinue (dar nu obligatoriu). Aceeai alegere este prezent i la sistemele de administrare amemoriei, unde apar segmentarea puri paginarea.

Aa cum am vzut, pstrarea unui fiier ca o secven continude octei are o problemevident:dacfiierul crete n dimensiuni, probabil cva trebui sfie repoziionat pe disc. Aceeai problemrmne valabili pentru segmentele de memorie, cu observaia c repoziionarea unui segment nmemorie este o operaie relativ rapidprin comparaie cu mutarea unui fiier de la o anumitpoziiepe disc la alta. Din acest motiv, majoritatea sistemelor mpart fiierele n blocuri de dimensiune fixcenu trebuie neaprat sfie adiacente.

Dimensiunea blocurilor

n momentul n care s-a decis pstrarea fiierelor n blocuri de dimensiune fix, problema imediatceapare este alegerea dimensiunii acestor blocuri. Dacinem cont de organizarea discurilor, sectoarele,pistele i cilindrii sunt candidai evideni pentru unitatea de alocare (cu toate cele sunt dependentede dispozitivul fizic, ceea ce evident este un minus). n sistemul de paginare, dimensiunea paginii esteo problematicmajor.

Avnd o unitate de alocare mare precum cilindrul, nseamncfiecare fiier, chiar i unul de 1 octet,va ocupa n ntregime cilindrul. Cercetri efectuate au demonstrat cdimensiunea medie a fiierelor nmediul UNIX este de aproximativ 1KB, aa calocarea de blocuri de 32KB pentru fiecare fiier ar duce

la pierderea a 31/32 sau 97% din capacitatea totala discului. Pe de altparte folosirea unei unitide alocare mici, nseamn cpentru fiecare fiier vor fi necesare mai multe blocuri. Citirea fiecruibloc implic n principiu o operaie de cutare i o ntrziere datorat rotaiei discului, aadar citireaunui fiier format din mai multe blocuri mici va fi nceat. Spre exemplu sconsiderm cazul unui discavnd 131072 de octei per pist, un timp de rotaie de 8.33 msec i un timp mediu de cutare de 10msec. Timpul n milisecunde necesar citirii unui bloc de k octei este suma cutrii, ntrzierii de rotaiei a timpului de transfer: 10 + 4.165 + (k /131072) x 8.33. Curba din figura urmtoare descrie vitezade transfer a unui astfel de disc ca o funcie de dimensiunea blocului.

Pentru a calcula spaiul n mod eficient, trebuie sfacem o presupunere n legturcu dimensiuneamedie a fiierelor. Pentru exemplif icare considerm msurtorile efectuate ntr-un departament, ce are1000 de utilizatori i peste 1 milion de fiiere UNIX, i care au surprins o mediande 1680 octei,


24/26

nsemnnd prin aceasta c jumtate dintre fiiere sunt mai mici i jumtate sunt mai mari dectaceastvaloare. Pentru simplitate, spresupunem ctoate fiierele sunt de 2 KB, ceea ce formeazcurba punctatdin figura prezentati care reprezinteficiena folosirii spaiului de disc.

Cele dou curbe pot fi nelese n modul urmtor. Timpul de acces pentru un bloc este completdeterminat de timpul de cutare i ntrzierea de rotaie, n consecinvor fi necesare 14 msec pentru

accesul unui bloc, cu ct mai multe date sunt citite o dat, cu att mai bine. n consecin rata detransfer crete cu dimensiunea blocurilor (pn cnd transferul va ocupa att de mult timp nct eldevine dominant). Cu blocuri mici, ce sunt puterea lui doi i f iiere de 2 KB, nu este irosit spaiul dinblocuri. Totui, pentru fiiere cu blocuri de 2 KB i 4 KB sau mai mari, o parte din spaiu este nefolosit.n realitate puine fiiere au dimensiunea multiplu de mrimea blocurilor, n consecin n generaloricum se pierde o anumitparte din ultimul bloc.

Ce arataceste curbe este coricum performanele i utilizarea spaiului de disc sunt n mod inerentn conflict. O dimensiune de compromis este necesar. Pentru aceasta, 4 KB ar putea reprezenta oalternativ bun, ns unele sisteme de operare i-au fcut alegerea acum muli ani n urm, pevremea cnd parametrii de disc i dimensiunile f iierelor erau diferite. De exemplu, pentru UNIX, 1 KBeste o dimensiune folositn mod curent, iar pentru FAT16 dimensiunea blocurilor poate sfie orice

putere a lui doi de la 512 octei la 32 KB, dar este determinatde dimensiunea discului i de numrulmaxim de blocuri pe o partiie de disc care este 216=65536, ceea ce foreazfolosirea blocurilor maripentru discuri de capacitate ridicat.

Administrarea blocurilor libere

Pentru administrarea blocurilor libere sunt utilizate dou metode aa cum este prezentat n figuraurmtoare.

Prima folosete o listnlnuitde blocuri de disc, fiecare bloc pstrnd un numr maxim de blocurilibere. Cu un bloc de 1KB, avnd o valoare unicasociatreprezentatpe 32 bii, fiecare dintre blocuripstreaz n lista sa 255 de astfel de identificatori (este necesar cte o poziie pentru referireaurmtorului bloc). Un disc de 16GB are nevoie de o listde maximum 16794 de blocuri de cte 1KB,pentru a pstra toate cele 224identificatoare de blocuri.

Cealalttehnicfolositeste imaginea de bii. Un disc cu n blocuri are nevoie de o imagine cu n bii.Blocurile libere sunt reprezentate cu 1 n imagine, n timp ce blocurile alocate sunt reprezentate de


25/26

valoarea 0 (sau vice versa). Un disc de 16 GB are 224blocuri de 1KB i de aceea el are nevoie de 224bii pentru imagine, ceea ce necesita 2048 blocuri. Nu este surprinztor c imaginea necesitmaipuin spaiu, deoarece folosete 1 bit pentru fiecare bloc, n locul a 32 bii cum este cazul listei

nlnuite. Doar dac discul este aproape plin (adic are un numr mic de blocuri libere) atuncimetoda folosind o listnlnuita va avea nevoie de mai puin spaiu dect imaginea de bii. Pe de altparte, dacsunt multe blocuri libere, cteva dintre ele pot fi mprumutate pentru a pstra lista, fr

pierderi legate de capacitatea discului.

Cnd este folosit metoda listelor nlnuite, doar un bloc de referine trebuie inut n memoriaprincipal. Cnd un fiier este creat, blocurile necesare sunt luate din blocul de referin e. Cnd bloculnu mai are referine, un nou bloc este citit de pe disc. n mod similar, cnd un fiier este ters,blocurile sale sunt eliberate i adugate la lista de referine din memoria principal. Cnd acest bloceste plin n totalitate, el va fi scris pe disc.

n anumite situaii, aceastmetodduce la un trafic I/O nejustificat. Surmrim situaia din figuraurmtoare (a), n care blocul din memorie mai are spaiu doar pentru ncdouintrri. Dacun fiierde trei blocuri este eliberat, blocul de referine nu va mai avea spaiu suficient i atunci el va trebuiscris pe disc, ducnd la situaia din (b). Dacun fiier de trei blocuri este scris n acest moment, un

ntreg bloc de referine trebuie s fie iari citit de pe disc, ceea ce ne duce iar situa ia (a). Dacfiierul de trei blocuri nou creat era un fiier temporar, cnd este eliberat, un alt acces de scriere va finecesar pentru a trece blocul plin de referine napoi pe disc. Pe scurt, cnd blocul de referine esteaproape liber, o serie de fiiere temporare de scurtduratpot cauza o multitudine de accese de I/O.

O abordare alternativ, ce evitmajoritatea accesurilor I/O, este mprirea blocului de referine. nacest mod, n loc de a trece din situaia (a) ctre cea din (b), vom trece din (a) n (c) cnd cele treiblocuri sunt eliberate. Acum sistemul poate s suporte o serie de fiiere temporare fr a cretenumrul de apeluri I/O. Dacblocul din memorie se umple complet, el este scris pe disc i un bloc pe

jumtate plin de referine este adus n memorie. Ideea este, n acest caz, s pstrm majoritateablocurilor de referine pe disc (pentru a minimiza accesul la disc), dar n acelai timp s avem n

memorie un bloc plin doar pe jumtate, n acest fel suportnd att crearea ct i tergerea de fiiere,fraccese suplimentare de I/O la disc.

Cu o hartde bii, este iari posibil spstrm doar un bloc n memorie, fcnd schimburi cu disculdoar cnd blocul devine plin sau complet gol. Un beneficiu adiional al acestei metode este c, fcndtoate alocrile dintr-un singur bloc al imaginii de bii, blocurile vor fi extrem de apropiate, n acest felminimiznd timpul de acces la disc.

Cotpe disc (Quote)

Pentru a preveni posibilitatea ca utilizatorii s foloseasc prea mult spaiu pe disc, sistemele deoperare multiutilizator, de cele mai multe ori, pun la dispoziie un mecanism de forare a cotelor

admise. Ideea este cadministratorul sistemului rezervfiecrui utilizator un maximum de fiiere iblocuri, iar sistemul de operare are grijca utilizatorul snu depeascaceste limite. Un mecanismtipic este descris mai jos.


26/26

Cnd un utilizator acceseaz un fiier, atributele i adresele de disc sunt localizate i plasate ntr-otabelde fiiere deschise n memoria principal. Printre atribute existo intrare care spune cine esteproprietarul fiierului. Toate adugrile la dimensiunea fiierului vor fi sczute din cota proprietarului.O a doua tabelpstreazinformaia de cotpentru fiecare utilizator ce are la momentul respectiv unfiier deschis, chiar dacfiierul a fost deschis de ctre un alt utilizator. Acest tabel este reprezentat n

figura urmtoare. Aici este parial figurat cota fiierelor pe disc pentru toi utilizatorii ce au fiieredeschise n acest moment de timp. Cnd toate fiierele sunt nchise, nregistrrile sunt nscrise napoi

n fiierul de cote.

Cnd o intrarea nou este creat n tabela de fiiere deschise, o referin la nregistrarea de cotpentru proprietar este adugataici. n acest mod sunt accesibile foarte uor diferitele limite impusede administrator. De fiecare dat cnd un bloc este adugat la un fiier, numrul total de blocuriaparinnd de proprietar este mrit cu o unitate i se efectueaz o verificare n legtur cu limitele

fizice i logice. Limitele logice pot fi depite, acest lucru nu este valabil i n cazul limitelor fizice. Oncercare de a face adugri la un fiier, atunci cnd limita fizic este depit, va rezulta ntr-oeroare. Verificri similare existi pentru numrul de fiiere.

Cnd un utilizator ncearc s se autentifice, sistemul verific dac a fost depit cota fizic saulogic a fiierelor sau numrul de blocuri de disc folosite. Dac oricare dintre limite a fost atins,sistemul iniiaz un avertisment utilizatorului i numrul de avertismente rmase este sczut cu ounitate. Dacacest contor atinge valoarea zero, nseamncutilizatorul a ignorat de prea multe oriavertismentul i n consecinlui nu i se va permite autentificarea n sistem. Pentru a recpta dreptulde a avea acces iar la sistem, utilizatorul va trebui s discute personal cu administratorul. Aceastmetod are proprietatea c utilizatorii pot s treac de limitele logice n timpul sesiunii curente, cuobligaia de a terge toatinformaia suplimentarnainte de a ncheia sesiunea. Limitele fizice nu pot

fi niciodatdepite.

sisteme de fisiere

Documents