Proiectarea Si Analiza Sistemelor de Operare
1.Introducere
2. Funcțiile unui SGBD. Organizarea-tip a SGBD
2.1. Funcțiile principale ale unui SGBD
2.1.1. Administrarea explicită (directă) a datelor în memoria externă
2.1.2. Administrarea tampoanelor (buferelor) din memoria operativă
2.1.3. Administrarea tranzacțiilor
2.1.4. Jurnalizarea
2.1.5. Susținerea limbajelor BD
2.2. Organizarea tipică a unui SGBD concurent
3. Despre calculul relațional
3.1. Relații și proprietățile lor
3.2. Operații și algebre. Proprietățile operațiilor
3.3. Modele si sisteme algebrice. Algebra relațiilor
4. Proiectarea bazelor de date relaționale
4.1. Proiectarea logică
4.1.1. A doua formă normală
4.1.2. A treia formă normală
4.1.3. Forma normală Boyce-Codd
4.1.4. A patra formă normală
4.1.5. A cincea formă normală
Pagini 37
=== l ===
Proiectarea și analiza sistemelor de operare
1. Introducere
Scopul lucrării este expunerea bazelor contemporane ale metodelor și mijloacelor de elaborare a resurselor program de sistem (inclusiv, operații asincrone, tratarea întreruperilor, interfețele sistemelor de operare, compromisele dintre dispozitivele tehnice și resursele program) și pregătirea cititorului pentru proiectarea și analiza sistemelor de operare (S.O.).
Resursele fizice ale sistemelor de calcul contemporane posedă caracteristici tehnice extraordinare și pot fi utilizate în cele mai diverse scopuri. Însă aceste resurse fără compartimentul logic de sistem (software de sistem) întâmpină dificultăți majore în relațiile cu mediul în care trebuie să funcționeze. Acesta este motivul principal al creării sistemelor de operare, destinația cărora este administrarea (gestiunea, controlul) resurselor tehnice principale și asigurarea unei interfețe comode (plăcute, prietenești) între utilizator și calculator (fig.1.1) [1].
Fig.1.1. Relația dintre un sistem de operare și componentele unui calculator
Există mai multe motivații ale necesității studierii sistemelor de operare, cele mai importante fiind următoarele:
pentru utilizarea resurselor hardware în scopuri speciale poate fi necesar să se creeze un sistem de operare propriu sau să se introducă modificări în sistemul existent;
de alegerea corectă a sistemului de operare și a versiunii concrete poate depinde viabilitatea și eficacitatea sistemului de calcul;
este ideal ca utilizatorul să interacționeze cu sistemul de operare cunoscând toate subtilitățile ultimului, deoarece sistemul de operare este un intermediar între calculator și utilizator;
multe metode și concepte, utilizate în domeniul sistemelor de operare, pot fi implementate cu succes și în alte domenii (ultima motivație conform ordinii de expunere, dar nu și ultima ca importanță).
Prin noțiunea sistem de operare înțelegem modulele program ale unui sistem de calcul, care administrează resursele tehnice (procesoare, memoria operativă și secundară, dispozitive de intrare/ieșire, fișiere). Modulele în cauză soluționează situațiile de conflict, optimizează productivitatea sistemului, sporesc eficiența utilizării lui. Ele sunt un fel de intermediar (interfață) între programele utilizatorului și componentele tehnice ale calculatorului. Alte denumiri istorice: program de administrare, monitor, supervizor.
Modulele destinate unor domenii anume, cum ar fi translatoarele, depanatoarele, bibliotecile, mediile integrate (Visual) etc. nu sunt incluse în definiția unui sistem de operare, fiind considerate și ele utilizatori ai sistemului de operare.
Noțiuni de bază și clasificări
Un calculator constă dintr-un ansamblu de componente funcționale fizice și logice, care cooperează în satisfacerea cerințelor utilizatorilor privind introducerea, stocarea, prelucrarea, transmisia și regăsirea informațiilor. Aceste componente funcționale sunt structurate pe niveluri, care interacționează prin interfețe bine definite. Suportul fizic (resurse tehnice, hardware) constituie nivelul inferior al sistemului de calcul construit pe baza unor componente electronice, magnetice, optice, mecanice etc., mai mult sau mai puțin sofisticate în funcție de stadiul de dezvoltare a tehnologiilor respective.
Noțiuni și termeni din domeniul resurselor tehnice
Pentru a trece la noțiunile principale, legate de hardware, vom face cunoștință mai întâi cu funcțiile de bază ale unui calculator. Pot fi evidențiate cinci funcții esențiale [2]: inițializarea (bootup), introducerea datelor, procesarea datelor, stocarea datelor și extragerea rezultatelor:
Inițializarea implică testarea părților importante ale calculatorului, rularea fișierelor de pornire și încărcarea altor fișiere necesare, cum ar fi driverele de dispozitive;
Introducerea reprezintă transferul datelor dintr-o sursă externă în calculator. Surse externe pot fi dischetele, tastatura, mouse-ul etc.;
Procesarea se referă la manipularea datelor introduse, în scopul producerii unui rezultat (ieșirea);
Stocarea constituie procesul salvării informațiilor (date sau programe) într-un dispozitiv de păstrare, de exemplu discul fix, pentru recuperarea ulterioară.
Prin structura unui calculator vom subînțelege componentele (dispozitivele) care formează calculatorul și legăturile dintre ele. Componentele principale sunt: procesorul, memoria, unitățile de stocare pe termen lung, dispozitivele de intrare-ieșire (tastatura, display-ul, mouse-ul etc.). Relațiile (legăturile) dintre aceste componente pot fi foarte variate, dar, istoric prima și, devenită mai apoi clasică, este structura John von Neumann, prezentată în fig.1.2.
Fig.1.2. Structura unui calculator
Componentele principale se conectează la placa de bază (motherboard) direct sau prin conectoare speciale, numite plăci de extensie (daughterboards). Unitatea centrală de procesare – procesorul (CPU) se găsește într-un singur circuit integrat (cip) incorporând unitatea de comandă (Control Unit, CU) și unitatea logico-aritmetică (Arithmetic Logical Unit, ALU). Unitatea de comandă controlează funcționarea unității logico-aritmetice. Memoria este o zonă de lucru de mare viteză, unde CPU stochează datele și programele pentru a le consulta în mod rapid. Memoria poate fi organizată în mod ierarhic, caz în care există cel puțin două nivele de ierarhie – memoria centrală (operativă) și memoria secundară (externă, de lungă durată). Memoria operativă este electronică sub formă de cipuri, de obicei cu acces aleator (RAM – Random Access Memory) și trebuie să fie alimentată cu tensiune pentru a păstra datele. Pentru salvarea datelor atunci când se întrerupe alimentarea sau pentru păstrare de lungă durată, datele sunt stocate în memoria secundară, care le reține oricât de mult timp. Dispozitivele cele mai obișnuite de introducere a datelor sunt tastatura și mouse-ul, iar dispozitivul de ieșire cel mai utilizat este monitorul. Procesorul și memoria operativă formează nucleul calculatorului, toate celelalte dispozitive fiind cunoscute sub denumirea de periferie (dispozitive periferice).
Instrucțiunile care vor fi îndeplinite de calculator sunt stocate în memorie sub formă de programe. Unitatea de comandă ține evidența și interpretează instrucțiunile dintr-un program, fiind responsabilă cu transmiterea de sarcini specifice diferitelor elemente ale calculatorului. CU controlează în principal funcțiile I/O, de memorie și stocare, colaborează cu ALU, care răspunde de efectuarea operațiilor de calcul. Mai menționăm noțiunile: mărimea magistralelor interne și externe de date, mărimea adresei de memorie, frecvența ceasului.
Mărimea magistralei interne de date – procesoarele păstrează datele în locații temporare, numite registre. Datele sunt transferate оntre registre, CU, ALU și alte componente ale procesorului prin intermediul unei magistrale realizate în circuitele procesorului. Numărul de linii în această magistrală oferă o măsură a cantității de date pe care procesorul o poate transfera într-o singură operație. Valoarea ei poate varia între 8 și 32 de biți (în scopuri speciale 64 sau 128).
Mărimea magistralei externe de date măsoară câte date pot fi transferate între procesor și dispozitivele periferice într-o singură operație. Magistrala este un sistem de conectări și cablări ce distribuie datele prin calculator. Cu cât magistrala de date e mai mare, cu atât performanțele calculatorului se îmbunătățesc. Numărul de linii și aici variază între 8 și 32 de biți.
Mărimea adresei de memorie determină volumul de memorie care poate fi gestionat de către calculator fără eforturi speciale.
Un ceas electronic asigură coordonarea corespunzătoare a numeroaselor elemente ale calculatorului. Componentele calculatoarelor cu performanțe superioare pot opera la frecvențe de ceas mai mari. Frecvența ceasului indică viteza de operare a CPU. Ea se măsoară în milioane de impulsuri de ceas pe secundă, adică în megahertzi (MHz).
Noțiuni și termeni din domeniul sistemelor de operare
Un sistem de operare este un ansamblu de programe de control și de serviciu care ghidează un calculator în executarea sarcinilor sale și asistă programele de aplicație și utilizatorul prin intermediul anumitor funcțiuni. Natura funcțiilor și modul în care acestea sunt realizate determină atributele care caracterizează un sistem de operare: timpul de răspuns, simultaneitatea utilizării, eficiența, partajarea și protecția, generalitatea, flexibilitatea, extensibilitatea, fiabilitatea și disponibilitatea, transparența și vizibilitatea [3].
Timpul de răspuns exprimă durata intervalului delimitat de lansarea unei cereri de serviciu și achitarea acesteia de către sistem. Are două componente: timpul de așteptare pentru ca cererea respectivă să fie luată în considerație și timpul de execuție a acestei cereri.
Simultaneitatea utilizării măsoară gradul în care un sistem poate să execute în același timp mai multe lucrări.
Eficiența măsoară proprietatea unui sistem de a folosi оn mod optim resursele de care dispune.
Partajarea și protecția caracterizează nivelul la care utilizatorii au posibilitatea să utilizeze în comun informația prezentă în sistem și nivelul la care pot să comunice între ei, în deplină siguranță (în sensul evitării accesului neautorizat și/sau alterării intenționate sau accidentale a informației).
Fig.1.3. Relația dintre utilizator, sarcină, pas de task, proces și spațiu de adrese
Generalitatea, flexibilitatea, extensibilitatea măsoară gradul în care un sistem poate fi folositor și adaptabil unui context specific (exprimat prin nivelul de limitare impus programelor utilizatorului), precum și gradul în care se pot include în sistem noi componente hardware și software fără eforturi de proiectare și programare suplimentare.
Fiabilitatea și disponibilitatea exprimă proprietatea unui sistem de a cădea foarte rar în pană și de a evita goluri în funcționare din cauza defectării uneia sau mai multor componente ale sale.
Transparența și vizibilitatea exprimă pe de o parte proprietatea unui sistem de a face invizibil utilizatorului ceea ce se află sub interfața de utilizare care i se oferă și, pe de altă parte, capacitatea de a permite utilizatorilor săi să obțină anumite informații despre modul cum el lucrează, informații de care în mod teoretic ei nu au nevoie pentru a beneficia de o utilizare completă, însă care ar putea să-i ajute la obținerea unei utilizări mai eficiente [3].
Resursele program reprezintă seturi de programe și date utilizate pentru soluționarea anumitor probleme. Programul este transcrierea оntr-un limbaj de programare a unui algoritm, altfel – programul este o secvență de instrucțiuni sau simplu cod. Utilizatorul (user) este oricare doritor să îndeplinească anumite lucrări la calculator. Prin lucrare (sarcină, task) vom subînțelege un set de acțiuni, necesare pentru îndeplinirea unui lucru anume. Sarcina poate conține mai mulți pași. Pași de task sunt unități de lucru, care vor fi îndeplinite consecutiv, de exemplu trei pași – compilare, încărcare și executare. Primind un task de la utilizator, sistemul de operare poate crea câteva procese. Până la tehnologia Win32 prin proces se considerau calculele care puteau fi efectuate paralel cu alte calcule. Relația dintre un user, task, proces și spațiu de adrese este prezentată în fig.1.3.
Procesul mai poate fi definit drept traiectoria procesorului, atunci când ultimul îndeplinește un set oarecare de programe. Ansamblul programelor și datelor accesate în timpul procesului, formează spațiul de adrese. În fig.1.3 sunt aduse două exemple de spații de adrese – unul pentru procesul de intrare/ieșire (input/output, I/O) și altul pentru procesul unității centrale.
Una din destinațiile sistemului de operare este de a asigura proiectarea spațiului de adrese a unui proces în memoria fizică. Pentru rezolvarea acestei probleme sunt utilizate atât resurse tehnice (sisteme cu organizarea memoriei pe segmente sau pe pagini), cât și resurse program speciale.
Multiprogramarea este un termen utilizat în cazul unui sistem în care pot exista simultan câteva procese în stare de execuție. Un proces se consideră în stare de execuție, dacă calculele au început, dar la momentul considerat nu au fost terminate sau întrerupte (terminare din cauza unei erori sau din alte motive). Nu este obligatoriu ca un proces care se află оn starea de execuție să fie și executat de procesor la un moment dat.
Resursele hardware de protecție sunt utilizate cel mai des pentru controlul accesării memoriei. Resursele hardware de оntrerupere permit sistemului de operare să coordoneze operațiile care au loc în același timp; pot fi utilizate și pentru a schimba ordinea de execuție a programelor. Оntreruperea este un mecanism care impune procesorul să observe anumite evenimente. Pot exista mecanisme care permit să nu se acorde atenție unei anume întreruperi – întrerupere mascată.
Tipuri de sisteme de operare, obiective și funcții
Valorile concrete ale atributelor sistemelor de operare și combinații ale acestora determină diverse tipuri de sisteme și restricțiile de implementare. Conform acestor atribute pot fi evidențiate sisteme de operare [3]:
secvențiale
cu multiprogramare
cu prelucrare multiplă
în timp real, etc.
Majoritatea sistemelor de operare recunosc programul ca cea mai mică unitate de prelucrare, căreia i se atribuie o identitate și pe care un utilizator o poate prezenta spre execuție. Unele sisteme permit ca un program să fie considerat ca un ansamblu de sarcini ale căror execuții (inclusiv în paralel) contribuie la atingerea obiectivului urmărit de acest program.
Un sistem secvențial (tratare pe loturi, batch processing, traitement par lots) execută la un moment dat un singur program, care trebuie terminat înainte de a lua un alt program în considerație.
Sistemele cu multiprogramare acceptă la un moment dat mai multe programe în memoria centrală, acestea aflându-se în diverse stadii de execuție.
Un sistem de calcul cu prelucrare multiplă dispune de mai multe procesoare, care pot să execute simultan unul sau mai multe programe. Utilizarea efectivă a prelucrării multiple necesită atributul de multiprogramare. Execuția simultană a unui singur program de către mai multe unități presupune existența posibilității de a descompune acest program în mai multe sarcini (multitasking) sau mai multe procese.
Sistemele оn timp real sunt dedicate, de obicei, funcționării în cadrul unor sisteme de comandă și este necesar ca valorile anumitor atribute să se încadreze în limite destul de restrictive, dictate de dinamica proceselor comandate.
Tipurile de sisteme de operare enumerate mai sus nu sunt nici disjuncte și nici exhaustive. Majoritatea sistemelor existente pot fi încadrate în mai multe clase, atunci când se face o analiză prin prisma obiectivelor pe care le urmăresc. La capitolul obiective vom aminti оn primul rвnd maximizarea eficienței sistemului de calcul și a satisfacției utilizatorilor. Tot la obiective poate fi trecută și cererea de minimizare a posibilității de apariție a unor erori și de maximizare a transparenței sistemului de operare, garantarea securității datelor, optimizarea controlului comunicațiilor în cazul unei rețele de calculatoare. Un obiectiv foarte important este necesitatea de minimizare a efortului concepție-realizare a sistemului, ultim оn enumerare, dar poate cel mai important pentru specialiști.
Toate aceste obiective sunt consecințe ale dezideratului principal: un sistem de operare este destinat să administreze resursele sistemului de calcul și anume memoria, procesorul (procesoarele), dispozitivele și informația.
Un sistem de operare este obligat:
să păstreze informația despre starea fiecărei resurse
să ia decizia cărui proces să i se aloce resursa, în ce cantitate și când
să aloce resursa și
la momentul respectiv să o retragă.
Exemple de sisteme de operare
Exemplele care urmează [6] vor ilustra diversitatea funcțiilor îndeplinite de către un sistem de operare, fără pretenții de exhaustivitate. Pentru fiecare exemplu vom indica funcțiile puse în șarja sistemului de operare și caracteristicile principale ale acestuia.
Cazul calculatoarelor personale
Configurația cea mai simplă a unui calculator personal (PC) include o unitate centrală, o memorie principală, un display, o tastatură și un mouse. Această configurație de obicei este completată de o memorie secundară și o imprimantă (fig.1.4).
Utilizatorul unui atare sistem va cere minimum următoarele două tipuri de servicii:
identificarea și crearea unor fișiere sau mulțimi structurate de informații; stocarea acestor fișiere în memoria secundară; transferarea informațiilor între fișiere și dispozitivele de intrare/ieșire;
executarea unor programe existente în PC sau introduse sub formă de fișiere; introducerea datelor necesare executării programului (de la tastatură, din fișier sau de la alte surse); listarea rezultatelor la display, imprimantă sau copierea lor într-un fișier.
Sistemul de operare va acorda aceste servicii prin intermediul unui limbaj special, numit limbaj de comandă, introducându-se de la tastatură instrucțiuni de forma <acțiune> <parametri>, sau utilizând mouse-ul și o interfață grafică a utilizatorului (GUI – graphical user interface), acționările mouse-lui fiind imediat interpretate de sistem.
Iată două exemple de secvențe tipice de activități în cazul unui PC:
elaborarea unui program;
introducerea programului cu ajutorul tastaturii și a unui editor de texte;
executarea programului introducându-se datele necesare de la tastatură și extrăgând rezultatele la display sau imprimantă;
modificarea programului, dacă rezultatele nu sunt satisfăcătoare și repetarea execuției;
perfectarea versiunii finale a programului, inclusiv documentarea la necesitate a acestuia;
exploatarea unui program;
cererea de executare a unui program deja existent. Vor fi pregătite în prealabil date de intrare sau vor fi introduse in mod interactiv aceste date la cerere cu ajutorul tastaturii;
afișarea rezultatelor pe ecran, listarea la imprimantă sau copierea lor într-un fișier pentru o utilizare ulterioară.
Într-un atare sistem funcția partajare a resurselor este lipsă, or PC este folosit de un singur utilizator care are controlul total asupra acestuia. Alocarea resurselor este legată de gestionarea memoriei și administrarea fișierelor. Funcțiile principale vizibile ale sistemului de operare constau în administrarea fișierelor, realizarea operațiilor de intrare/ieșire și interpretarea comenzilor provenite de la interfața utilizator-sistem de operare.
Pentru acest tip de sisteme cele mai importante caracteristice sunt:
fiabilitatea;
eficacitatea;
simplitatea utilizării;
facilitatea extensibilității prin adăugarea unor utilite noi sau adaptarea la periferice noi.
Ultimele două aspecte pun în evidență importanța interfețelor oferite de sistem (limbajul de comandă sau GUI).
Comanda unor procese industriale
La o uzină chimică sunt utilizate doua produse inițiale A și B pentru sinteza produsului C conform fig.1.5.
Procesul de fabricație este comandat de un calculator care îndeplinește următoarele funcții:
Reglare. Pentru o derulare bună a procesului de fabricație parametrii de funcționare (temperatura, presiunea, concentrația, etc.) trebuie să se afle într-o plajă de valori predefinite. Pentru aceasta va fi acționat debitul de intrare a materiilor prime A sau B. Parametrii de funcționare sunt măsurați cu ajutorul unor captoare. Calculatorul preia aceste măsurări și, în dependență de algoritmul de comandă, acționează robinetele de intrare.
Înregistrare. Rezultatele măsurărilor sunt periodic înregistrate; valorile lor sunt afișate pe un tablou de bord și recopiate într-un fișier ("jurnal de bord") în scopul unor prelucrări ulterioare (date statistice).
Securitate. În cazul în care unul dintre parametrii măsurați depășește o valoare critică predefinită reactorul trebuie oprit imediat.
Acest mod de funcționare introduce unele restricții, descrise mai jos.
Măsurările sunt făcute periodic; fie T valoarea intervalului de timp dintre două măsurări consecutive (perioada de eșantionare), iar t – timpul total de prelucrare a datelor de către calculator (măsurarea propriu-zisă a semnalelor observate, înregistrarea, calcularea semnalelor de comandă și comanda robinetelor). Sistemul va funcționa doar în cazul respectării relației de restricționare t T.
Securitatea sistemului are prioritate maximă. Depășirea unor valori critice trebuie să fie detectată în orice moment și tratarea acestor accidente va întrerupe toate operațiile în curs de execuție.
Funcțiile principale ale sistemului de operare sunt:
acționarea organelor externe (citirea semnalelor captoarelor, comanda robinetelor);
evidența timpului real (declanșarea periodică a ciclului de calculare a semnalelor de comandă);
reacția la evenimentele exterioare (oprire de urgență);
gestiunea informațiilor (păstrarea și întreținerea fișierului jurnalului de bord).
Existența unor restricții stricte a duratei de prelucrare a informațiilor, noțiunea de tratare prioritară, conectarea la niște dispozitive exterioare de măsurare și acționare, sunt caracteristice aplicațiilor informatice "оn timp real". Pot fi menționate și alte domenii cu comandă în timp real: centralele telefonice, comanda aparatelor de zbor, robotica, monitoringul medical, etc.
Оn cazul acestor sisteme caracteristica principală este fiabilitatea, or rezultatele unei funcționări neadecvate pot fi catastrofale. Sistemul trebuie să garanteze un serviciu minim în cazul unor căderi în pană a dispozitivelor tehnice, unor evenimente accidentale sau erori umane.
Sisteme tranzacționale
Caracteristicile principale ale sistemelor cu tranzacții sau tranzacționale sunt următoarele:
sistemul gestionează un set de informații sau baze de date, care pot atinge volume importante;
asupra acestor informații pot fi executate un anumit număr de operații predefinite, sau tranzacții, adesea interactive;
sistemul este dotat cu un mare număr de puncte de acces și un mare număr de tranzacții se pot derula simultan.
Ca exemplu pot fi menționate sistemele de rezervare a biletelor de tren sau avion, de gestionare a conturilor bancare, de arhivare și consultare a documentelor.
Restricțiile sunt în primul rând legate de integritatea și coerența internă a informațiilor, care formează bazele de date. Aceste restricții depind, evident de aplicație. De exemplu, numărul de locuri rezervate într-un avion nu poate depăși numărul locurilor disponibile, un loc distinct poate fi atribuit unei singure persoane, etc.
Calitățile obligatorii ale unui sistem tranzacțional sunt disponibilitatea și fiabilitatea; pentru unele sisteme poate fi importantă și toleranța la defecțiuni. O caracteristică importantă ale sistemelor tranzacționale este multitudinea activităților paralele, iar în multe cazuri și repartizarea geografică a componentelor.
Sisteme оn timp partajat
Destinația principală a unor astfel de sisteme este furnizarea serviciilor necesare unei mulțimi de utilizatori, fiecare dintre ei beneficiind:
de servicii echivalente serviciilor unui calculator individual;
de servicii legate de existența unei comunități de utilizatori: partajarea informațiilor, comunicații între utilizatori.
Problemele care apar datorită conceptului de partajare a timpului sunt o combinație a problemelor existente în cazul unui calculator individual cu cele din sistemele tranzacționale și pot fi clasificate după cum urmează:
definirea mașinii virtuale oferite fiecărui utilizator;
partajarea și alocarea resurselor fizice comune: procesoare, memorii, organe de comunicație;
gestionarea informațiilor partajate și a comunicațiilor.
Caracteristicile obligatorii unui atare sistem combină în egală măsură calitățile unui sistem de operare al unui calculator individual și al unui sistem tranzacțional: disponibilitatea, fiabilitatea, securitatea, exploatarea optimă a caracteristicilor resurselor fizice, calitatea interfeței și serviciilor utilizatorului, facilitatea adaptării și extensibilității.
Sistemul de operare și procesele
Noțiunea de proces, introdusă mai sus, este asociată conceptului de lucrare (pentru a lua în considerare aspectele dinamice) și poate fi definită altfel ca o suită temporală de execuții de instrucțiuni, fiind o entitate de bază în descrierea sau analiza funcționării unui sistem. Evoluția în timp a unui proces presupune un consum de resurse, dictat de natura și complexitatea instrucțiunilor de executat. Orice utilizare a unei resurse este asociată, la un moment dat, unui proces și procesul respectiv își asumă răspunderea utilizării acestei resurse. În particular, rezultă că ori de câte ori se execută procedurile de sistem, resursele pe care le utilizează acesta intră în administrarea procesului (fie el și al utilizatorului), care a cerut serviciul. Resursele (procesorul, memoria centrală, informația, dispozitivele) alocate unui proces variază în timp (dinamica procesului).
Anterior un sistem de operare a fost definit ca un set de programe destinat să administreze resursele. Care sunt relațiile dintre programele sistemului de operare? Atunci când un proces este creat, care este ordinea de utilizare a unui program anume? Pentru a răspunde la aceste întrebări (și la altele) vom face cunoștință cu ciclul de viață a unui proces. În fig.1.6 sunt prezentate trei procese (trei sarcini ale utilizatorilor) existente оntr-un sistem cu multiprogramare.
Fig.1.6. Trei procese оntr-un sistem cu multiprogramare
Ciclul de viață a unui proces poate fi reprezentat printr-un set de stări ale procesului și trecerea de la o stare la alta. Vom evidenția trei stări elementare ale unui proces: proces ales (sau exe) – procesului i s-a alocat un procesor, este în curs de execuție, proces blocat – procesul așteaptă să se producă un anumit eveniment, a cărui apariție este indispensabilă, proces eligibil – procesul are la dispoziție toate resursele necesare lipsă fiind doar procesorul, adică este pregătit să se execute din momentul alocării unității centrale (fig.1.7).
Fig.1.7. Ciclul de viață a unui proces
Ciclul de viață a unui proces, prezentat în fig.1.7 sugerează existența “veșnică” a proceselor. Mai aproape de realitate un proces este reprezentat în fig.1.8. Aici norii semnifică componentele sistemului de operare, care tratează evenimentele respective, iar pentru modelarea procesului real au fost adăugate trei stări suplimentare:
prezentare – utilizatorul prezintă sistemului sarcina, sistemul trebuie să reacționeze la cererea utilizatorului,
păstrare – sarcina este reprezentată în formă internă, dar resursele nu sunt încă alocate,
terminare – calculele corespunzătoare procesului au luat sfârșit, toate resursele alocate procesului pot fi eliberate și întoarse sistemului.
Sistemul de operare este acea componentă, care va ghida procesul prin toate aceste stări. În fig.1.8 este prezentată una din variantele posibile ale ciclului de viață a procesului. Pot exista abateri de la acest model atât în sensul complexității, cât și în direcție opusă. Oricum, acest model este foarte util pentru rezolvarea problemei proiectării sistemelor de operare.
Mașină ierarhică și mașină extinsă
Astăzi este greu de închipuit că doar cu câteva decenii în urmă un utilizator era nevoit să programeze în zerouri și unități, utilizând un calculator fără “hainele program” (mașina goală). Chiar și specialiștii nu prea iubesc să scrie programe într-un limbaj de asamblare sau (și mai evident) utilizând doar instrucțiuni din setul, garantat de hardware. Un program elaborat de un specialist poate fi de forma [1]:
1 Transferă C, B Stabilește C=B
2 Găsește zona 80, X Să se găsească 80 de octeți de memorie liberi
și să se plaseze adresa zonei în X
3 Introdu date оn X Să se citească datele indicate în zona X
4 Compară X(2), ‘/*’ Coincide conținutul primilor 2 octeți ai zonei
X cu ‘/*’?
5 Dacă da, stop Dacă coincid, salt la STOP
Fig.1.8. Schimbarea stărilor unui proces și componentele SO responsabile de aceste schimbări
Instrucțiunile 1, 4 și 5 sunt instrucțiuni standard în multe calculatoare contemporane. Însă execuția corectă și eficientă a instrucțiunilor 2 și 3 poate necesita îndeplinirea a zeci, sute sau chiar mii de comenzi din setul standard, deoarece aceste instrucțiuni cer interacțiunea cu unele resurse cheie, cum ar fi memoria operativă și dispozitivele de intrare-ieșire. Sistemul de operare asigură instrucțiuni pentru realizarea unor astfel de funcții de administrare a resurselor. Din această cauză, instrucțiunile 2 și 3 sunt instrucțiuni ale mașinii extinse, ele neavând echivalenți în setul de instrucțiuni hardware. Sistemul de operare completează setul standard, realizat hardware, cu instrucțiuni de acest gen.
Setul de instrucțiuni realizat hardware împreună cu instrucțiunile suplimentare ale sistemului de operare formează sistemul de comenzi al mașinii extinse. Grafic conceptul de mașină extinsă poate fi reprezentat conform fig.1.9.
Nucleul sistemului de operare va fi executat pe mașina “goală”, iar programele utilizatorului – pe mașina extinsă. Să facem cunoștință acum cu modul în care sunt organizate оntr-un tot оntreg componentele sistemelor de operare.
Primele sisteme de operare erau formate dintr-un singur program mare. Dar, odată cu sporirea complexității sistemelor, această abordare liniară conducea la dificultăți serioase și s-a propus să se utilizeze și în acest domeniu conceptul de mașină extinsă. Acest concept, оn cazul sistemelor de operare, poate fi utilizat în două nivele (fig.1.10.) și conduce la noțiunea de mașină ierarhică [4]:
Primul nivel – funcțiile cheie, utilizate de majoritatea modulelor de sistem, pot fi realizate оn cadrul unei mașini extinse interne și
Nivelul doi – unele module pot fi executate оn cadrul unei mașini extinse externe, analogic proceselor utilizatorului.
Оn această abordare ierarhică apare imediat problema alegerii corecte a nivelului de ierarhie pentru fiecare modul al sistemului de operare (în mașina extinsă internă, externă sau va fi prezent în calitate de proces extern). Pot fi evidențiate subnivele ale celor două mașini extinse, iar interacțiunea proceselor sistemului de operare ne conduce la necesitatea introducerii mai multor straturi ale proceselor. Modulele sistemului, plasate în cadrul mașinii extinse, spre deosebire de modulele care aparțin straturilor proceselor, formează nucleul sistemului de operare. Concepția mașinii ierarhice este pe larg utilizată în proiectarea programelor mari utilizвnd metodele, cunoscute sub denumirea programare modulară sau programare structurală. Nu există reguli stricte în privința numărului de nivele, amplasării modulelor pe nivele, componența nucleului. De obicei, nucleul conține doar cele mai necesare și evidente funcții, celelalte, atunci când este posibil, vor fi prezente ca procese de sistem separate. O detalizare a conceptului de mașină ierarhică este adusă în fig.1.11. Procesele (incluse în dreptunghiuri) se adresează către funcțiile nucleului și utilizează împreună toate resursele sistemului. Unele procese generează sau comandă alte procese (granița dintre ele este prezentată de liniile în zig-zag, care separă diferite straturi ale proceselor). Într-o realizare strict ierarhică modulele, situate оntr-un nivel oarecare, pot accesa (se pot adresa) numai resursele nivelelor inferioare.
La nivelul 1 (nivelul cel mai inferior) sunt situate funcțiile de care au nevoie toate componentele administrării resurselor. Una dintre acestea este funcția care urmărește repartizarea resurselor, funcție, care la rândul său, necesită anumite mijloace de sincronizare. Aceste operații elementare sunt numite P-operator (ocuparea resursei sau cererea de acces) și V-operator (eliberarea resursei). Sincronizarea se face printr-o tehnică de programare, numită semafor. Pot fi semafoare simple (binare) sau polivalente (care pot avea mai multe valori). Fiecărei resurse îi este atașat un semafor. Atunci când în sistem apare o cerere pentru o resursă oarecare, pentru testarea semaforului respectiv este utilizat P-operatorul; dacă semaforul este “pe verde” (resursa este liberă), P-operatorul îl trece “pe roșu” (îl închide) și returnează comanda. În caz contrar, procesul care a generat cererea este trecut în stare de așteptare, pentru ca mai târziu, atunci când V-operatorul va elibera resursa și va trece semaforul “pe verde”, să acceseze resursa.
Amplasarea funcțiilor elementare pe nivele poate fi făcută în felul următor:
Nivelul 1. Administrarea procesoarelor (nivelul inferior)
P-operatorii de sincronizare
V-operatorii de sincronizare
planificarea proceselor (aparatul de multiprogramare)
Nivelul 2. Administrarea memoriei
alocarea memoriei
eliberarea memoriei
Nivelul 3. Administrarea procesoarelor (nivelul superior)
crearea și distrugerea unui proces
transmiterea și recepționarea mesajelor între procese
lansarea unui proces
oprirea unui proces
Nivelul 4. Administrarea dispozitivelor
urmărirea stărilor tuturor dispozitivelor periferice
planificarea intrărilor/ieșirilor
inițierea operațiilor de intrare/ieșire
Nivelul 5. Administrarea informației
crearea și distrugerea unui fișier
deschiderea și închiderea unui fișier
citirea și înscrierea unui fișier.
Nucleul sistemului de operare este format de subprogramele, care asistă execuția proceselor. Pentru a decide care funcții pot fi realizate în formă de procese separate este necesar să se stabilească funcțiile care pot fi executate independent și în mod paralel cu procesele utilizatorului (nu se va câștiga nimic evidențiind în procese separate funcții care trebuie să fie îndeplinite secvențial). Sistemele avansate permit crearea oricărui număr de procese, ceea ce este foarte comod pentru organizarea calculelor paralele sau a regimurilor de timp real. În cadrul tehnologiilor noi (Win32, de exemplu) noțiunea de proces a fost substanțial modificată, introducându-se alte concepte (thread-uri), care exploatează într-un mod mai eficient ideile multitasking-ului și multiprogramării.
Alte puncte de vedere asupra sistemelor de operare
Оn compartimentele precedente au fost tratate sistemele de operare din diferite puncte de vedere, cum ar fi SO și procesele, SO și mașina extinsă sau SO și mașina ierarhică. Există și alte puncte de vedere asupra sistemelor de operare pe care un specialist ar trebui să le cunoască.
Abordare funcțională
Pentru un utilizator obișnuit, convins că un calculator este doar un instrument care îl ajută în rezolvarea unor probleme din domeniul său de activitate, noțiuni cum ar fi administrarea memoriei cu paginație sau driverele dispozitivelor nu semnifică prea multe. Destinația principală a unui sistem de operare pentru această categorie de utilizatori este punerea la dispoziție a unui set de programe care ar ajuta în formularea și rezolvarea problemelor concrete. Abordarea sistemelor de operare din acest punct de vedere (abordare funcțională) poate conduce la confundarea lor cu unele programe, utile și foarte importante (translatoare, biblioteci, medii integrate, etc.). Pentru a evita posibilitatea apariției unei astfel de probleme aceste programe, de obicei, nu sunt considerate componente ale sistemului de operare.
Abordare din punctul de vedere al interfeței cu utilizatorul
Interfața sistemului de operare cu utilizatorul prezintă un interes aparte. Progresul în acest domeniu este spectaculos, dacă vom lua în considerație că în primele sisteme utilizatorul era obligat să indice în mod explicit și manual fiecare pas, oricât de nesemnificativ ar fi părut. Formularea pașilor cu ajutorul Job Control Language (JCL) nu a schimbat substanțial situația. Acest limbaj, nefiind agreat de utilizatorii simpli, care l-au denumit limbaj păsăresc, așa și nu a fost acceptat în cunoștință de cauză de către aceștia.
Conform JCL utilizatorul trebuie să încorporeze programul propriu într-un set de instrucțiuni, care indicau începutul, sfârșitul programului și al datelor de intrare, pașii și conținutul concret al pașilor. JCL în principiu era un metalimbaj de programare (programare la nivel macro). Pentru mijloacele tehnice de la acea perioadă JCL a sporit substanțial eficiența sistemelor de calcul, deși au existat multe inconveniente, principala fiind lipsa posibilității lucrului interactiv.
Microprocesoarele și memoriile anilor ’70 au pus problema lansării pe piață a calculatoarelor personale (PC) cu toate consecințele respective. Una din consecințe este și interfața utilizator-calculator, sistemul de operare devenind până la urmă responsabil de aceasta. Interfața grafica a utilizatorului (Graphical User Interface – GUI) a apărut mai întâi ca un complement al sistemului de operare (pentru MS DOS – Windows 1, Windows 2 sau chiar Windows 3, de exemplu), pentru ca mai apoi să fie integrată în cadrul sistemului (Windows 95, Windows NT, etc.). Un sistem de operare nu este, în principiu, obligat să posede o interfață sofisticată, totul este determinat de baza tehnică utilizată și de necesitățile concrete. Oricum, un specialist trebuie să distingă aceste două noțiuni – sistemul de operare și interfața utilizatorului.
Evoluția sistemelor de operare
O analiză cronologică a dezvoltării sistemelor de operare este greu de realizat, deoarece multe din principiile foarte importante au fost realizate pentru prima dată cu mult înainte de a deveni unanim acceptate. De exemplu, conceptele de memorie paginată și memorie virtuală au fost realizate pentru prima dată în 1959 în cadrul sistemului “Atlas” [5], fiind utilizate la mijlocul anilor ’60 în unele sisteme cu destinație specială, pentru ca în 1972 să fie preluate de firma IBM în cadrul familiei de calculatoare mari.
Primele sisteme erau caracterizate prin prelucrarea secvențială a taskurilor. Timpul de execuție a programelor era relativ mare, instrumentele de depanare – primitive, fiecare programator își încărca în mod individual programul (pachetul de cartele perforate), apăsa butoane, controla conținutul locațiunilor de memorie, etc. (1950 – 1956).
Sporirea vitezei de calcul, dar și a prețului calculatoarelor cerea o utilizare mai eficientă a timpului de calculator. Nu putea fi tolerată situația ca un calculator să “nu facă nimic”, atunci când utilizatorul își încarcă în mod manual programul. Au fost propuse programe de monitorizare (monitoare), care treceau de la o lucrare la alta în mod automat, utilizatorul fiind responsabil de organizarea corectă a programelor în cadrul unui pachet – primele încercări de prelucrare pe loturi (1956 – 1959).
Odată cu creșterea complexității calculatoarelor, îndeosebi în ceea ce consta administrarea dispozitivelor periferice, au fost propuse sisteme supervizoare (executive), care se aflau în memoria calculatorului în mod constant și acordau utilizatorilor servicii în gestiunea operațiilor de intrare/ieșire (1959 – 1963). În aceste sisteme mai erau realizate și o serie de facilități noi, cum ar fi controlul unor posibile încercări din partea programului de a încălca restricțiile existente în sistem, culegerea informațiilor de evidență, etc.
Au urmat apoi sistemele cu multiprogramare, menite la început să rezolve problema concordării vitezei de calcul a unității centrale și a perifericelor. Drept consecință, au apărut o mulțime de limbaje de control a lucrărilor, a fost realizată o standardizare substanțială a operațiilor de intrare-ieșire.
După 1965 au apărut primele sisteme cu partajare a timpului (time sharing), au fost propuse sisteme sofisticate de administrare a informației (sisteme de gestiune a datelor sau sisteme de fișiere, File Systems). Principiul time sharing oferea posibilitatea lucrului interactiv a mai multor utilizatori pe un singur calculator, fiecărui utilizator în mod ciclic acordându-i-se un interval anume de timp (cuantă de timp) și, datorită vitezei mari de calcul a unității centrale, creându-i-se impresia posesiei tuturor resurselor calculatorului.
Memoria virtuală și mașinile virtuale sunt niște principii care nici până astăzi nu au fost exploatate până la capăt. Progresele ultimilor ani în domeniul resurselor tehnice au permis implementarea acestor principii nu numai în cadrul sistemelor de calcul mari, ci și pentru calculatoarele personale. Specificațiile sistemelor de operare au fost în mare măsură standardizate, diversitatea SO devine tot mai mică, mulți specialiști exprimându-și îngrijorarea de o posibilă monopolizare a domeniului în viitorul apropiat. Evident, aceasta nu poate să sugereze nici într-un caz ideea că studierea principiilor de bază (mai vechi și mai noi) ale sistemelor de operare ar fi de prisos, ca și familiarizarea sau chiar cercetarea minuțioasă a unor sisteme existente, nicidecum nu poate însemna, în special pentru un specialist, pierderea interesului față de analiza și concepția sistemelor de operare.
O prezentare succintă a evoluției sistemelor de operare facilitează înțelegerea caracteristicilor actuale ale acestora și a termenilor deja introduși.
De la "poartă deschisă " la tratarea pe loturi
Primele calculatoare nu dispuneau de sisteme de operare. Fiecărui utilizator i se rezerva pentru un timp determinat calculatorul cu toate resursele acestuia. Interacțiunea era directă, programul și datele fiind introduse în mod manual sub formă de zerouri și unități. Utilitele care au apărut aveau destinația de a asista elaborarea programelor (asambloare, compilatoare, etc.) sau de a facilitata operațiile de intrare-ieșire.
Acest mod de exploatare, numit "poartă deschisă" [6], era de o eficacitate minimă, dispozitive foarte costisitoare fiind utilizate ineficient. Din această cauză la sfârșitul anilor '50 au apărut primele "monitoare de înlănțuire" – programe care permiteau executarea secvențială a unui set de lucrări, pregătite anticipat, trecerea de la o lucrare la alta fiind automatizată.
Funcția principală a unui atare sistem era gestiunea resurselor: memoria, procesorul, intrarea-ieșirea. Automatismul acestei gestionări implică o funcție de protecție a setului de lucrări contra unor riscuri perturbatorii in caz de eroare:
limitarea timpului de ocupare a procesorului pentru a evita blocarea sistemului atunci când un program conține o buclă infinită;
administrarea corectă a intrărilor-ieșirilor pentru a evita buclele în utilizarea perifericelor;
protecția zonei de memorie rezervate monitorului pentru a împiedica modificarea accidentală a acestuia.
Deși utilizarea monitoarelor de înlănțuire a ameliorat notabil randamentul utilizării procesorului, acest randament rămânea foarte scăzut din cauza că procesorul nu era eliberat în timpul operațiilor de intrare-ieșire. O soluționare ar fi constat în utilizarea a două calculatoare – unul (principal) pentru executarea programelor și altul (auxiliar) pentru operațiile de intrare-ieșire. O planificare adecvată a executării lucrărilor permitea utilizarea celor două calculatoare în paralel, dând posibilitatea sporirii la maximum a randamentului calculatorului principal.
Multiprogramarea și partajarea timpului
Progresul tehnologic și conceptual al anilor '60 – '70 a permis excluderea unor limitări caracteristice sistemelor de prelucrare pe loturi. Astfel, au fost introduse procesoare specializate pentru operațiile de intrare-ieșire (unitățile de schimb sau canalele), care permitea eliberarea procesorului central de gestionarea dispozitivelor de intrare-ieșire. Utilizarea principiului multiprogramării sau partajarea memoriei între mai mulți utilizatori a permis o utilizare și mai bună a procesorului central. Exploatarea unui calculator conform principiului timpului partajat oferă utilizatorilor posibilități analogice unui calculator individual, permițând beneficiul unor servicii comune la un preț redus.
Organizarea intrărilor – ieșirilor în memorii tampon
Un canal este un procesor specializat în executarea autonomă a operațiilor de intrare-ieșire, paralel cu procesul de prelucrare a informațiilor. Viteza de lucru a organelor periferice este relativ mică din cauza unor dispozitive mecanice care intră în componența acestora. Pentru excluderea influenței perifericelor asupra vitezei de lucru a sistemului de calcul s-a propus să se păstreze în memorie în anumite zone tampon datele de intrare (care vor fi utilizate la necesitate) și rezultatele (care vor fi imprimate în mod autonom) mai multor lucrări. Această situație este prezentată în fig.1.12.
Pentru a exclude utilizarea ineficientă a memoriei operative prin formarea zonelor-tampon, acestea erau organizate în memoria secundară de capacitate înaltă, transferurile între aceste două nuvele ale memorie fiind de asemenea comandate de un canal.
Deși utilizarea memoriilor tampon prezintă o serie de avantaje în vederea sporirii randamentului dispozitivelor calculatorului, totuși două momente negative pot fi menționate:
atunci când lucrarea în curs de execuție are nevoie de niște date unitatea centrală rămâne inactivă pe toată perioada citirii acestora;
o lucrare de scurtă durată, sosită în timpul execuției unei lucrări "lungi", trebuie să aștepte terminarea acesteia din urmă.
Multiprogramarea
Ultimele două momente au condus la ideea utilizării unui mod de funcționare a SO în care:
o lucrare aflată în starea blocat ar putea folosi unitatea centrală, eliberată de o lucrare care este în așteptarea datelor,
unitatea centrală ar putea schimba timpul său de alocare înainte de terminarea unei lucrări în scopul satisfacerii cerințelor legate de timpul de răspuns.
Оn acest caz este necesar ca valoarea timpului de realocare a unității centrale să fie mai mică în raport cu durata unui transfer între nivelele memoriei. Aceasta implică prezența simultană în memoria operativă a mai multor programe sau părți de programe. Acest mod de funcționare este numit multiprogramare [6] și este prezentat în fig.1.13.
Această schemă evidențiază două momente importante: rolul principal al memoriei operative (în sistemele anterioare acest rol era deținut de către unitatea centrală) și fluxul informațional între memoria operativă și cea secundară. Drept consecință, volumul memoriei operative și viteza de transfer între aceste două nivele ale memoriei devin caracteristici determinante ale performanței sistemului.
Principalele avantaje și restricții ale multiprogramării pot fi prezentate în rezumat după cum urmează:
un sistem cu multiprogramare este mai complicat pentru că el trebuie să asigure partajarea memoriei și protecția reciprocă a programelor;
multiprogramarea necesită dispozitive speciale pentru reactivarea programelor și protecția memoriei;
un sistem cu multiprogramare asigură o utilizare mai uniformă a diferitor resurse: unitatea centrală, memoria, organele de intrare-ieșire;
multiprogramarea permite reducerea timpului de răspuns în cazul lucrărilor de durată mică într-un sistem cu prelucrare secvențială.
Sisteme cu timp partajat
Un sistem de operare cu partajarea timpului trebuie să garanteze fiecărui utilizator un timp acceptabil de răspuns. Acest rezultat este obținut prin alocarea succesivă a procesorului pentru tranșe de timp foarte mici (cuante) programelor utilizatorilor.
Viabilitatea unei asemenea tehnici este legată de caracteristicile lucrului interactiv. Activitatea unui utilizator conține două componente: timpul de reflecție (gândire), în care utilizatorul elaborează, propune subiecte de lucru, introducând în calculator informații și timpul de așteptare, când așteaptă executarea de către sistem a serviciului cerut. Prima componentă este de o durată medie mult mai mare decât a doua și sistemul poate să servească simultan mai mulți utilizatori, folosind timpul mort, datorat perioadei de reflecție.
Ca exemplu, fie un sistem cu partajarea timpului, care deservește 1000 utilizatori cu un comportament mediu identic. Admitem că durata timpului de gândire este în medie de 9 ori mai mare decât a timpului de așteptare, acesta din urmă reprezentând 10% din timpul total. Avem, deci, în medie 100 utilizatori activi (care se află în așteptarea unui răspuns la un serviciu cerut). Presupunem că valoarea cuantei este de 5 ms. Dacă executarea unei cereri durează o cuantă, timpul de răspuns va fi de ordinul unei jumătăți de secundă.
Am admis în acest exemplu că toate programele utilizatorilor activi se află în memoria principală: timpul de comutare între programele a doi utilizatori se reduce la timpul de realocare a unității centrale, care este neglijabil în comparație cu valoarea cuantei. Multiprogramarea devine obligatorie, dacă ținem cont de raportul dintre acest timp și timpul necesar pentru încărcarea unui program din memoria secundară. Situația este de fapt și mai complicată: volumul memoriei principale nu permite aflarea aici a tuturor programelor utilizatorilor activi. Este posibil ca o informație să fie lipsă în memoria operativă atunci când unitatea centrală are nevoie de ea. Rolul sistemului de operare este de a minimiza pe cât este posibil probabilitatea apariției unui atare eveniment.
Dezvoltarea sistemelor de operare cu partajarea timpului a pus în evidență importanța interacțiunii om-calculator. Acest aspect a fost mult timp neglijat, dar cei care nu au făcut acest lucru au avut doar de câștigat.
Apariția microprocesoarelor cu posibilități mari de calcul și de prețuri tot mai mici a permis pe de o parte utilizarea la scară largă a calculatoarelor personale, iar pe de altă parte, satisfacerea cerințelor utilizatorilor sistemelor informatice de partajare a resurselor fizice și logice distribuite geografic. Au apărut noi tipuri de sisteme informatice: calculatoarele personale, rețelele locale și rețelele globale.
Conceptele și tehnicile elaborate pentru sistemele centralizate au rămas valabile și în cazul serverelor sau sistemelor de operare pentru calculatoarele personale. Repartizarea distribuită a informației, precum și transmiterea ei la distanțe mai mari sau mai mici a ridicat probleme noi, cum ar fi coordonarea activităților la distanță sau menținerea coerenței informațiilor distribuite. Toate acestea au trebuit să fie luate în considerație la elaborarea sistemelor de operare pentru sistemele informatice ale anilor care au urmat.
Realizări conceptuale
Paralel cu evoluția tehnică și funcțională a sistemelor de operare a avut loc și o importantă evoluție conceptuală, care a permis o mai bună înțelegere a funcționării sistemelor de operare și a condus la elaborarea unor metode proprii de concepere.
Debutul unei cercetări științifice a sistemelor de operare poate fi considerat anul 1964, care a succedat o etapă importantă de dezvoltare tehnică: primele sisteme cu partajare a timpului (Thor, CTSS), anunțarea seriei IBM 360 și introducerea canalelor de intrare-ieșire, prima memorie paginată (Atlas), etc.
Оn perioada 1965-1968 au fost elaborate noțiunile necesare conștientizării gestionării activităților fizice sau conceptuale paralele: proces secvențial, formularea și soluționarea unor probleme de excludere mutuală, sincronizarea și inventarea semaforului. Acestea au fost aplicate cu succes în elaborarea sistemelor de operare: sistemul THE (1967) utilizează semafoarele, sistemul Multics (1964-1970) conține un nucleu de gestionare a proceselor. Metode și utilitare destinate sistemelor distribuite sunt propuse la sfârșitul anilor '70. Utilite de sincronizare încep să fie introduse în limbajele de programare. Sunt propuse primele metode de specificare și control al validității sincronizărilor.
Problema definirii informației a fost pusă inițial în seama limbajelor de programare: fiecare limbaj definea universul său de obiecte accesibile și mijloacele efective de accesare. Sistemul de operare trebuia doar să implementeze obiectele definite de limbajul de programare in memoria fizică, direct adresabilă.
Restricțiile de capacitate și preț a memoriei principale a condus foarte repede la apariția necesității unei memorii secundare și a unor mecanisme de schimb de informații între aceste două nivele ale memoriei. Prima memorie paginată apare în 1962 (Atlas), tot atunci compilatoarele limbajului Algol 60 folosesc paginația virtuală pentru gestionarea programelor în curs de execuție. În 1965 este fundamentată noțiunea de segmentare, deși încă în 1962 sistemul Burroughs B5000 utiliza un mecanism de adresare logică prin unități de volum variabil sau segmente.
În 1966 este propus un model de arhitectură pentru calculatoare cu partajare a timpului, implementat în IBM 360/67. În acest calculator segmentele sunt doar simulate printr-o dublă paginație, din care cauză noțiunea de segmentare va rămâne pentru mult timp puțin înțeleasă de comunitatea informatică.
Problemele partajării și protecției informației, alocării resurselor conduc la noțiunea de memorie virtuală, care permite izolarea mecanismelor de gestionare a ansamblului “memorie principală – memorie secundară”, lăsând utilizatorilor simpli impresia unui spațiu de adresare uniform (contiguu). Au fost introduse noțiunile de modularitate și structurare ierarhică, obiect, etc.
Windows, Unix și alte sisteme
Paralel cu evoluția tehnică și funcțională a sistemelor de operare a avut loc și o importantă evoluție conceptuală, care a permis o mai bună înțelegere a funcționării sistemelor de operare și a condus la elaborarea unor metode proprii de concepere.
Debutul unei cercetări științifice a sistemelor de operare poate fi considerat anul 1964, care a succedat o etapă importantă de dezvoltare tehnică: primele sisteme cu partajare a timpului (Thor, CTSS), anunțarea seriei IBM 360 și introducerea canalelor de intrare-ieșire, prima memorie paginată (Atlas), etc.
În perioada 1965-1968 au fost elaborate noțiunile necesare conștientizării gestionării activităților fizice sau conceptuale paralele: proces secvențial, formularea și soluționarea unor probleme de excludere mutuală, sincronizarea și inventarea semaforului. Acestea au fost aplicate cu succes în elaborarea sistemelor de operare: sistemul THE (1967) utilizează semafoarele, sistemul Multics (1964-1970) conține un nucleu de gestionare a proceselor. Metode și utilitare destinate sistemelor distribuite sunt propuse la sfârșitul anilor '70. Utilite de sincronizare încep să fie introduse în limbajele de programare. Sunt propuse primele metode de specificare și control al validității sincronizărilor.
Problema definirii informației a fost pusă inițial în seama limbajelor de programare: fiecare limbaj definea universul său de obiecte accesibile și mijloacele efective de accesare. Sistemul de operare trebuia doar să implementeze obiectele definite de limbajul de programare in memoria fizică, direct adresabilă.
Restricțiile de capacitate și preț a memoriei principale a condus foarte repede la apariția necesității unei memorii secundare și a unor mecanisme de schimb de informații între aceste două nivele ale memoriei. Prima memorie paginată apare în 1962 (Atlas), tot atunci compilatoarele limbajului Algol 60 folosesc paginația virtuală pentru gestionarea programelor în curs de execuție. În 1965 este fundamentată noțiunea de segmentare, deși încă în 1962 sistemul Burroughs B5000 utiliza un mecanism de adresare logică prin unități de volum variabil sau segmente.
În 1966 este propus un model de arhitectură pentru calculatoare cu partajare a timpului, implementat în IBM 360/67. În acest calculator segmentele sunt doar simulate printr-o dublă paginație, din care cauză noțiunea de segmentare va rămâne pentru mult timp puțin înțeleasă de comunitatea informatică.
Problemele partajării și protecției informației, alocării resurselor conduc la noțiunea de memorie virtuală, care permite izolarea mecanismelor de gestionare a ansamblului “memorie principală – memorie secundară”, lăsând utilizatorilor simpli impresia unui spațiu de adresare uniform (contiguu). Au fost introduse noțiunile de modularitate și structurare ierarhică, obiect, etc.
Astăzi sistemele de operare în sensul tradițional de concepere sunt obiectul unor elaborări industriale, decât de cercetare. Chiar și lucrările care au avut loc sau mai derulează în SUA capătă tot mai multe trăsături de lucrări semiindustriale. Aceasta este datorat atât de achiziționării unei rezerve extraordinare de metode și algoritmi, cât și standardizării stricte a funcțiilor și interfețelor sistemelor de operare. Au totuși loc unele activități de cercetare, ca de exemplu cercetările din domeniul mediilor operaționale obiect-orientate.
SО UNIX și standardele sistemelor deschise
Sistemul de operare UNIX, primul sistem mobil care asigură un mediu fiabil de dezvoltare și utilizare a softului de aplicație, este fundamentul practic de elaborare a sistemelor fizico-logice deschise. Implementarea largă a sistemului de operare UNIX a permis trecerea de la declararea sistemelor deschise la dezvoltarea practică a acestui concept. Este greu de supraestimat și influența activităților de standardizare a interfețelor SO UNIX asupra dezvoltării domeniului sistemelor deschise. Cu toate acestea, pot fi evidențiate câteva versiuni ale SO UNIX, care diferă atât prin realizare, cât și prin interfețe și semantică (deși, odată cu dezvoltarea procesului de standardizare, aceste diferențe devin tot mai nesemnificative).
Modulele sursă ale SO UNIX au fost scrise de către colaboratorii companiei AT&T și timp îndelungat drepturile de autor, ca și drepturile de licențiere, au aparținut acestei companii. Mai târziu, din mai multe motive (complexitate tehnică în elaborarea și întreținerea acestui produs program complicat, unele dificultăți juridice, etc.), compania AT&T a creat compania USL (UNIX System Laboratories), care avea în șarjă exclusivă dezvoltarea și susținerea modulelor sursă ale SO UNIX.
Compania USL a propus versiunea UNIX System V 4.0, care a devenit standardul de-facto și baza mai multor versiuni UNIX, create de producătorii de stații de lucru și servere. În ultimul succes al USL în calitate de filială a firmei AT&T, versiunea SVR 4.2, pentru prima oară în istoria sistemelor de operare UNIX a fost realizat mecanismul proceselor “legere” (thread, fire), care erau executate în baza unei memorii virtuale comune și permitea utilizarea posibilităților dispozitivelor fizice, numite “arhitectura multiprocesorală simetrică” în care mai multe procesoare au drepturi egale de accesare a memoriei centrale comune.
Оn 1993 compania USL a fost absorbită de compania Novell, astăzi departament al acesteia, marca înregistrată UNIX fiind cedată consorțiumului X/Open. La începutul anului 1995 compania Novell a anunțat o variantă nouă a SO UixWare 2.0 bazată pe System V 4.2. Era un sistem de operare cu un sistem de fișiere foarte fiabil, fiind admis accesul la fișierele păstrate pe serverele NetWare, administratorul avea la dispoziție o interfață grafică bine pusă la punct, etc.
Pe parcursul a mai multor ani sistemul de operare de bază al companiei Sun a fost UNIX BSD. Însă, începând cu SunOS 4.0, s-a trecut la System V 4.0, firma Sun introducând o serie de modificații și extensii în această versiune. Ca exemplu, Sun a implementat paralelizarea programelor pentru sistemele multiprocesorale simetrice. Solaris este un mediu de interfațare a lui SunOS cu mijloace suplimentare GUI și resurse de nivel înalt pentru organizarea lucrului în rețea (de exemplu, apelarea procedurilor la distanță – RPC).
Și la baza SO HP/UX, DG/UX și AIX se află SVR 4.x din care cauză setul de bază al funcțiilor de sistem și biblioteci este același. Variantele SO UNIX, propuse de compania SCO și destinate exclusiv platformelor Intel, sunt bazate pe modulele inițiale ale System V 3.2, fiind total compatibile cu toate standardele de bază
OSF-1 și alte variante UNIX
Open Software Foundation (OSF) a fost prima companie comercială, care a încercat elaborarea SO UNIX în baza micronucleului Mach. A fost creat sistemul de operare OSF-1, care nu era în sens de licențiere „curat”, deoarece folosea o parte a modulelor inițiale din SVR 4.0.
Variantele SO UNIX, propuse de Universitatea din California, sunt o alternativă reală pentru UNIX AT&T. De exemplu, UNIX BSD 4.2 era pus la dispoziție în module inițiale și folosită chiar în fosta URSS pe calculatoarele de tip DEC. Grupul BSD a influențat enorm dezvoltarea sistemelor de operare UNIX, printre realizări amintim mult controversatul SO UNIX BSD 4.4, construit în baza principiilor „micronucleare”, sistemul FreeBSD și altele.
Nu putem să nu amintim aici și de realizarea originală a SO UNIX pentru platformele Intel, propusă de Torvald Linus – LINUX. Este un sistem de operare foarte popular în mediul studențesc, care are și una din cele mai populare teleconferințe în Internet.
Odată cu ieșirea SO UNIX pe piață și creșterea substanțială nu numai a numărului de utilizatori, ci și a numărului de specialiști din toate colțurile lumii, care propuneau modificări și chiar variante proprii, a apărut necesitate elaborării unor standarde, care ar conduce la sisteme compatibile. Prin standard al unei interfețe al SO subînțelegem un set de proprietăți, mai mult sau mai puțin formale, sintactice sau semantice ale componentelor sistemului de operare. Activitatea de standardizare a început cu mai mult de 10 ani în urmă, dar este puțin probabil să se ajungă la finiș într-un viitor apropiat. Totuși rezultatele sunt mai mult decât vizibile, permițând elaborarea unor sisteme de operare mobile.
Standarde UNIX
Unul dintre primele standarde de-facto a fost cel publicat de USL pentru versiunea SO UNIX System V Release 4 – System V Interface Definition (SVID). Majoritatea variantelor comerciale respectau standardul SVID. Evident, SVID fiind un document de firmă, publicat fără discuții publice nu putea fi adoptat standard oficial.
Paralel exista direcția BSD (Berkeley Standard Distribution), susținută de comunitatea universitară. Deși majoritatea realizărilor comerciale se baza pe Sistem V, UNIX BSD era foarte popular în universități din care cauză a fost elaborat un standard, care a unit practic AT&T cu BSD. Acest lucru a fost început de asociația programatorilor profesionali din cadrul UniForum (Sistemele Deschise) și continuat de grupurile de lucru POSIX (Portable Operating System Interface). Cel mai popular standard, adoptat de ISO la recomandarea IEEE, POSIX 1003.1 definește cerințele minime pentru componentele unui sistem de operare.
Organizația internațională X/Open, care activează în domeniul elaborării și propagării ideilor sistemelor deschise, culege și sistematizează standardele de-jure și de-facto de importanță industrială în așa numitul X/Open Common Application Environment (CAE). Specificațiile interfețelor resurselor, care formează CAE, sunt publicate în X/Open Portability Guide (XPG).
Pentru lumea UNIX este foarte important și standardul limbajului de programare C, adoptat mai întâi de ANSI și apoi de ISO. În acest standard sunt specificate, în afara limbajului C, bibliotecile necesare într-o realizare standard. Deoarece chiar de la apariție limbajul C și sistemele de programare respective erau strвns legate de UNIX, componentele bibliotecilor standard corespundeau exact mediului standard al SO UNIX.
Mai menționăm standardul de-facto SPARC Complience Definition, propus de organizația SPARC International, propunerea organizației 88/Open pentru procesoarele RISC Motorola, standardul sistemului de ferestre, susținut de X Consorțium (Institutul de Tehnologie din Massachussets) și OSF/Motif, elaborat de Open Software Foundation.
Sisteme de operare cu micronucleu
Micronucleul este partea minimă principală a unui sistem de operare, folosită pentru asigurarea modularității și transportabilității. Noțiunea de micronucleu a fost introdusă de compania Next prin sistemul de operare cu micronucleul Mach. Nucleul acestui sistem de operare, de dimensiuni mici, în jurul căruia se situau subsistemele executate în regim user, trebuia să asigure o flexibilitate și modularitate foarte înaltă. Dar în realitate acestea au fost umbrite de prezența serverului monolit, care realiza sistemul de operare UNIX BSD 4.3, ales de compania Next în calitate de nivel superior pentru micronucleul Mach. Totuși, utilizarea micronucleului Mach a permis introducerea administrării mesajelor și a unei serii de funcții de serviciu orientate pe obiecte, în baza cărora a fost creată o interfață grafică elegantă a utilizatorului cu mijloace simple de configurare, administrare și dezvoltare program.
Următorul SO cu micronucleu a fost MS Windows NT, în care momentul principal era declarat, în afara modularității, transportabilitatea. Acest sistem de operare poate fi utilizat în sistemele mono- și miltiprocesor, bazate pe procesoarele Intel, Mips, și Alpha. Mai mult, deoarece NT trebuia să execute și programele scrise pentru DOS, Windows, OS/2 și SO, compatibile cu standardele Posix, compania Microsoft a folosit modularitatea abordării „micronucleare” pentru crearea unei structuri generalizate, care nu repetă sistemele de operare existente, fiecare SO fiind emulat printr-un modul separat sau printr-un subsistem.
Au aderat la tehnologia „micronucleară” și companiile Novell/USL, Open Software Foundation (OSF), IBM, Apple și altele. Unul din concurenții principali ai lui NT în domeniul SO cu micronucleu sunt Mach 3.0, creat în Universitatea Carnegy-Mellon, și Chorus 3.0 al companiei Chorus Systems.
Baze de date
Sistemele informaționale sunt orientate, în linii mari, spre păstrarea, accesarea și modificarea informațiilor existente. Structura informațiilor este adesea foarte complicată, și, deși structurile datelor diferă de la sistem la sistem, ele au foarte multe momente comune. La etapa inițială de folosire a tenicii de calcul în gestiunea informației problemele structurării datelor erau rezolvate în mod individual pentru fiecare sistem informațional. Erau elaborate aplicații speciale pentru sistemele de gestiune a fișierelor (biblioteci de programe), la fel cum se procedează în cazul compilatoarelor, editoarelor, etc. Dar, fiindcă sistemele informaționale necesită structuri de date complicate, aceste resurse suplimentare de gestiune a datelor formau partea principală a sistemelor, repetându-se de la un sistem la altul. Tendința de evidențiere și generalizare a acestei părți comune a sistemelor informaționale, responsabile de gestiunea datelor structurate, a fost prima cauză de creare a sistemelor de gestiune a bazelor de date (SGBD). Foarte repede a devenit clară imposibilitatea rezolvării problemei doar cu ajutorul unei biblioteci de programe, care ar realiza metode mai complicate de manipulare a datelor prin intermediul SGF.
Vom exemplifica prin următoarea situație. Presupunem că dorim să realizăm un sistem informațional simplu, care ar duce evidența colaboratorilor unei organizații. Sistemul va îndeplini următoarele funcții:
să formeze lista colaboratorilor unei secții,
să permită transferul unui colaborator dintr-o secție în alta,
să asigure primirea la lucru a colaboratorilor și eliberarea acestora.
Pentru fiecare secție trebuie susținută posibilitatea aflării numelui șefului acestei secții, numărului total de colaboratori din secție, valoarea ultimului salariu total, etc. Pentru fiecare colaborator trebuie să existe posibilitatea aflării numărului legitimației de serviciu folosind numele și prenumele colaboratorului și invers, să se obțină informații despre faptul dacă colaboratorul dat corespunde postului ocupat, nivelul salariului, etc.
Presupunem că am hotărât să bazăm acest sistem informațional pe Sistemul de Gestiune a Fișierelor (SGF) și să utilzăm pentru aceasta un singur fișier, extinzând posibilitățile de bază ale SGF, creând o bibliotecă specială de funcții. Unitatea informațională minimală în acest caz este colaboratorul din care cauză vom cere ca în acest fișier să existe o înregistrare pentru fiecare coalborator. Care vor fi câmpurile acestei înscrieri? Numele complet al colaboratorului (COL_NUME), numărul legitimației (COL_NR_LEGIT), informația depsre corepunderea postului ocupat ((COL_STARE), pentru simplitate, “da” sau “nu”), mărimea salariului (COL_SAL), numărul secției (COL_NR_SEC). Deoarece dorim să avem un singur fișier, aceeași înregistrare trebuie să conțină și numele șefului secției (COL_SEF_SEC).
Reieșind din funcțiile sistemului nostru informațional, trebuie să fie asigurat accesul multicriterial la acest fișier utilizând cheile unice (care nu sunt repetate în diferite înregistrări) COL_NUME și COL_NR_LEGIT. În afară de aceasta mai este necesar să putem selecta toate înregistrările, care conțin aceeași valoare COL_NR_SEC (colaboratorii unei secții), adică să existe acces conform unei chei multiple. Mai mult, pentru a obține numărul de colaboratori dintr-o secție sau salariul total, sistemul informațional va trebui de fiecare dată să acceseze fiecare colaborator al secției și să calculeze valorile respective.
Observăm, că chiar penru un astfel de sistem simplu, realizarea în baza SGF cere (1) – crearea unei infrastructuri complicate pentru accesul multicriterial, și (2) – generează o metodă de păstrare evident redundantă (repetarea numelui șefului secției pentru fiecare colaborator) și executarea selectării și calculelor masive pentru obținerea informațiilor sumare despre secții. În afară de aceasta, dacă dorim, de exemplu, să tipărim lista colaboratorilor, care au un salariu dat, va trebui să cercetăm tot fișierul sau să-l restructurăm în așa mod încât câmpul COL_SAL să devină cheie.
Prima propunere ar fi să creăm două fișiere cu chei multiple: COLABORATORI și SECȚII. Primul fișier va conține câmpurile COL_NUME, COL_NR_LEGIT, COL_STARE, COL_SAL și COL_NR_SEC, iar al doilea – SEC_NR, SEC_SEF, SEC_SAL (slariul total) și SEC_NR_COL (numărul de colaboratori dintr-o secție). Majoritatea inconveniențelor de mai sus vor fi depășite. Fiecare fișier va conține doar informații nedublate, nu sunt necesare calcule suplimentare pentru a afla informații de tipul salariului total. Dar în acest caz sistemul nostru capătă proprietăți noi, care îl apropie de un Sistem de Gestiune a Bazelor de Date (SGBD).
Mai întâi de toate, sistemul trebuie în acest caz să știe că lucrează cu două fișiere legate (este primul pas în direcția schemei bazelor de date), să cunoască structura și sensul fiecărui câmp (de exemplu, că COL_NR_SEC în fișierul COLABORATORI și SEC_NR în fișierul SECȚII înseamnă același lucru), și să înțeleagă că în unele cazuri modificarea informației într-un fișier trebuie să genereze modificarea automată în celălalt fișier, pentru ca să fie coordonat (nu sunt sigur că este corect spus românește, am făcut facultatea în limba rusă) conținutul lor. De exemplu, dacă la lucru este primit un nou colaborator, se va adăuga o înregistrare în fișierul COLABORATORI, vor fi schimbate și câmpurile SEC_SAL și SEC_NR_COL în înregistrarea din fișierul SECȚII, care descrie secția colaboratorului dat.
Noțiunea de coordonare(?) a datelor este o noțiune cheie a bazelor de date. De fapt, dacă un sistem informațional (chiar la fel de simplu ca și în exemplul nostru) susține modul coordonat de păstrare a informațiilor în câteva fișiere, putem afirma că sistemul susține o bază de date. Iar dacă un sistem auxiliar de gestiune a datelor permite lucrul cu mai multe fișiere, asigurând coordonarea lor, acesta poate fi numit sistem de gestiune a bazelor de date. Deja singură cererea de susținere a coordonării datelor în câteva fișiere nu ne mai permite să ieșim din situație doar cu ajutoul unei biblioteci de funcții: un atare sistem trebuie să posede și unele date proprii (metadate) și chiar valori, care definesc integritatea datelor.
Dar aceasta încă nu este totul ce este cerut de la un SGBD. În primul rând, chiar și în exemplul nostru este incomodă îndeplinirea unor interpelări de tipul “să se pună la dispoziție numărul de colaboratori din secția în care lucrează Maria Mirabela Popescu”. Ar fi mult mai simplu dacă SGBD ar permite formularea unor astfel de interpelări într-un limbaj apropiat de cel natural. Astfel de limbaje se numesc limbaje de interpelare a bazelor de date. De exemplu, în limbajul SQL interpelarea noastră poate fi exprimată astfel:
SELECT SEC_NR_COL
FROM COLABORATORI, SECȚII
WHERE COL_NUME = "Maria Mirabela Popescu"
AND COL_NR_SEC = SEC_NR
Formularea unei interpelări în SQL permite să nu ne deranjeze modul cum va fi îndeplinită această interpelare. Printre metadatele acesteia va fi prezentă informația conform căreia câmpul COL_NUME este câmp cheie pentru fișierul COLABORATORI, iar SEC_NR – pentru fișierul SECȚII și sistemul se va folosi de aceasta.
Dacă va fi necesar să obținem lista colaboratorilor, care nu corespund postului ocupat vom proceda astfel:
SELECT COL_NUME, COL_NR_LEGIT
FROM COLABORATORI
WHERE COL_STARE = "nu",
și sistemul va îndeplini căutarea necesară în fișierul COLABORATORI, deoarece câmpul COL_STARE nu este câmp cheie.
Acum să ne închipuim, că în prima realizare a sistemului informațional, bazată pe utilizarea unor biblioteci de extensii a metodelor de accesare a fișierelor, are loc operația de înregistrare a unui nou colaborator. Conform proprietății de modificare coordonată, sistemul a introdus o nouă înregistrare în fițirerul COLABORATORI și trebuia să treacă la modificarea înregistrării fișierului SECȚII, dar anume în acest moment a avut loc decontectarea accidentală a alimentării cu curent electric. Evident, după relansarea sistemului baza de date se va afla într-o stare necoordonată. Va fi necesar să controlăm în mod explicit fișierele noastre și să introducem modificările necesare. O aplicație poate su nu-și facă griji în acest sens, dar SGBD-urile adevărate au în șarjă astfel de funcții. Mai mult, sistemele de gestiune a bazelor de date rezolvă o serie de probleme, care nu pot fi în principiu rezolvate cu ajutorul sistemelor de gestiune a fișierelor (accesarea paralelă a informațiilor, de ex.).
Ca și concluzie: există aplicații pentru care sunt suficiente fișierele, aplicații pentru care trebuie să hotărâm care este nivelul necesar de lucru cu datele în memoria externă, și aplicații care au evident nevoie de baze de date.
2. Funcțiile unui SGBD. Organizarea-tip a SGBD
După cum am observat, posibilitățile tradiționale ale sistemelor de gestiune a fișierelor sunt insuficiente pentru construirea unor sisteme informaționale, chiar foarte simple. Aceasta este cauza principală a apariției SGBD.
2.1. Funcțiile principale ale unui SGBD
2.1.1. Administrarea explicită (directă) a datelor în memoria externă
Această funcție presupune susținerea structurilor necesare în memoria externă atât pentru păstrarea datelor care sunt parte componentă a BD, cât și pentru scopuri de service, de exemplu, pentru accelerarea accesului la date (de obicei sunt utilizați idicii în acest scop). În unele realizări ale SGBD pentru aceasta sunt utilizate posibilitățile SGF, altele pot lucra chiar și cu dispoziltivele de memorie externă. Utilzatorii nu sunt obligați să cunoască dacă un SGBD utilizează SGF și, în caz afirmativ, cum sunt organizate fișierele. SGBD susține un sistem propriu de desemnare a obiectelor BD.
2.1.2. Administrarea tampoanelor (buferelor) din memoria operativă
SGBD lucrează cu BD de dimensiuni semnificative, de obicei cel puțin aceste dimensiuni sunt mult mai mari decât volumul memoriei operative prezente. Evident, dacă la accesarea fiecărui element de date va fi nevoie de schimb de informații cu memoria externă, tot sistemul va lucra cu viteza suportului extern de memorie. Unica posibilitate de sporire a acestei viteze este buferizarea datelor în memoria operativă. Chiar dacă SO execută buferizarea de sistem (cum este în cazul SO UNIX), aceasta nu este suficient pentru scopurile SGBD. Din această cauză SGBD concurente susțin un set propriu de bufere în memoria operativă cu propriul algoritm de dispecerizare.
Notăm, că există o direcție întreagă în domeniul SGBD, dedicată prezenței constante a întregii BD în memoria operativă (cazul sistemelor de căutare, tranzacționale în Internet, de exemplu). Aici presupunem că capacitatea memoriei operative poate fi suficient de mare și nu trebuie să ne facem probleme cu buferizarea.
2.1.3. Administrarea tranzacțiilor
Tranzacțiile sunt o succesiune de operații asupra BD, considerate de SGBD un tot întreg. Dacă tranzacția este executată în totalitate SGBD fixează (COMMIT) modificările în BD, în caz contrar nu are loc nici o modificare. Noțiunea de tranzacție este necesară pentru asigurarea integrității logice a BD. În exemplul precedent atunci când este îndeplinită operația de primire la lucru a unui colaborator nou, această operație este uniunea operațiilor elementare asupra fișierelor COLABORATORI și SECȚII într-o tranzacție. Noțiunea dată este și mai importantă pentru SGBD multiuser. Proprietatea că fiecare tranzacție începe atunci când starea BD este consistentă și lasă această stare la fel consistentă după terminarea sa, face folosirea noțiunii tranzacție оn calitate de unitate de activitate a user-ului. Dacă tranzacțiile sunt gestionate corect de către SGBD, fiecare utilizator are impresia că este singurul care folosește baza de date (dacă nu-s prea mulți, evident!).
Străns legate de administrarea tranzacțiilor în SGBD multiuser sunt noțiunile de serializare a tranzacțiilor și planul secvențial (serializat) de îndeplinire a tranzacțiilor. Prin serializarea unor tranzacții care ar trebui să fie îndeplinite în mod paralel înțelegem o astfel de planificare a executării lor, în care efectul final este același, deși tranzacțiile nu sunt îndeplinite paralel, ci secvențial (din cauza resurselor limitate, de exemplu).
2.1.4. Jurnalizarea
Una din proprietățile de bază ale SGBD este fiabilitatea păstrării datelor în memoria externă, prin aceasta înțelegându-se că, dacă a avut loc orice cădere hardware sau software, SGBD-ul trebuie să fie în stare să restabilească ultima stare coordonată a BD. Evident, pentru a restabili BD trebuie să existe niște informații suplimentare. Altfel spus, susținerea fiabilității păstrării datelor în BD necesită o redundanță a informațiilor, iar aceea parte a informațiilor, care este folosită pentru restabilire trebuie păstrată extrem (strașnic!) de fiabil. Cea mai răspândită metodă de susținere a unei astfel de redundanțe este întreținerea unui jurnal de bord în care să fie fixate schimbările BD. Jurnalul este o parte specială a BD, inaccesibilă utilizatorilor BD și întreținută în mod foarte pedant (adesea există două copii ale jurnalului, care se află pe discuri fizice diferite), în care vin informațiile despre toate înscrierile în BD (partea principală, fără Jurnal, adică). În dependență de SGBD și înscrierile în jurnal se fac în mod diferit. În unele cazuri înscrierea în jurnal corespunde unei operații logice oarecare (eliminarea unei linii, de ex.), în alte cazuri unei operații interne minime de modificare a unei pagini de memorie externă, sau combinația acestora.
Оn toate cazurlie este utilizată strategia înscrierii “profilactice” în jurnal (protocolul Write Ahead Log – WAL). În linii mari asta ar însemna, că înscrierea despre modificarea oricărui obiect al BD trebuie să nimerească în memoria externă a jurnalului înainte ca obiectul modificat să ajungă în memoria externă a părții principale a BD. Dacă SGBD-ul respectă protocolul WAL, jurnalul permite rezolvarea tuturor problemelor de restabilire a BD după oricare tip de cădere.
2.1.5. Susținerea limbajelor BD
Pentru lucrul cu bazele de date sunt utilizate limbaje speciale, numite limbaje ale bazelor de date. Оn SGBD-urile timpurii erau susținute câteva limbaje specializate funcțional. Cel mai frecvent importante erau două limbaje – limbajul de definire a schemei BD (SDL – Schema Definition Language) și limbajul de manipulare a datelor (DML – Data Manipulation Language). Primul era utilizat pentru determinarea structurii logice a BD (cum își închipuie utilizatorul baza de date). DML conținea instrucțiuni de manipulare a datelor (introducerea datelor în BD, eliminarea, modificarea sau selecatarea datelor existente). În SGBD contemporane este susținut un limbaj integrat unic. Cel mai răspândit este limajul SQL (Structured Query Language). Acest limbaj combină posibiltățile SDL și DML. Desemnarea obiectelor BD (desemnarea tabelelor și coloanelor lor, în cazul unor BD de tip relațional) este susținută la nivelul limbajului în sens că compilatorul SQL transformă numele externe ale obiectelor în identificatori interni în baza unor tabele-catalog de serviciu. Nucleul SGBD în genere nu are “treabă” cu numele tabelelor și coloanelor acestora. Limbajul SQL conține resurse speciale pentru determinarea resticțiilor de consistență a BD. Aceste restricții sunt păstrate în tabele-catalog speciale, iar garantarea consistenței are loc la nivel de limbaj, adică la compilarea instrucțiunilor de modificare a BD compilatorul SQL în baza restricțiilor de consistență generează codul respectiv.
Autorizarea accesului la BD la fel se realizează cu ajutorul unui set de instrucțiuni SQL, fiind posibil accesul diferențiat în dependență de statutul utilizatorului.
2.2. Organizarea tipică a unui SGBD concurent
Organizarea unui SGBD tip și setul de componente ale acestuia corespunde funcțiillor stabilite mai sus. Noi am stabilit următoarele funcții de bază:
administrarea datelor în memoria externă,
administrarea buferelor în memoria externă,
adminstrarea tranzacțiilor,
jurnalizarea și restabilirea BD după căderi,
susținerea limbajelor BD.
La nivel logic оn cadrul unui SGBD concurent putem evidenția nivelul cel mai intern – nucleul SGBD (numit adesea Data Base Engine), compilatorul SGBD (de obicei SQL), subsistemul Run-Time și un set de utilitare.
Nucleul SGBD este responsabil de administrarea datelor în memoria externă, gestiunea buferelor memoriei operatve, adminstrarea tranzacțiilor și jurnalizare. Respectiv, pot fi evidențiate astfel de componente ale nucleului cum ar fi managerul datelor, managerul buferelor, managerul tranzacțiilor și managerul jurnalului. Funcțiile acestor componente sunt interdependente din care cauză ele trebuie să funcționeze și să interacționeze conform unor protocoale bine gândite și strict validate. Nucleul SGBD posedă o interfață proprie, dar care este utilizată doar de programele SQL și utilitarele BD. Nucleul SGBD este partea rezidentă principală a sistemului de gestiune a BD. În arhitectura “client-server” nucleul este componenta principală a părții server a sistemului.
Destinația principală a compilatorului este translatarea instrucțiunilor scrise în limbajul BD în cod executabil. Problema principală constă în faptul că aceste limbaje (de obicei SQL) sunt neprocedurale, adică în operatorul unui atare limbaj sunt specificate niște acțiuni asupra BD, dar această specificare nu este procedură, ci doar descrie într-o formă oarecare condițiile de îndeplinire a acțiunii dorite. Compilatorul trebuie să hotărască cum să execute operatorul limbajului înaintea generării codului executabil. În rezultatul compilării se obține un program executabil, reprezentat de obicei în cod intern independent de mașină. În acest caz executarea reală a operatorului are loc utilizând un subsistem de susținerea a regimului run-time, care nu este altceva decât un interpretor al acestui limbaj intern.
Din categoria utilitarelor BD fac parte unele proceduri, îndeplinirea cărora nu este binevenită utilizând limbajul BD. Dintre acestea aminitim încărcarea și unload-ul unei BD, culegere date statistice, controlul global al consistenței BD, etc.
3. Despre calculul relațional
Presupunem că lucrăm cu BD care are schema COLABORATORI(NR_COL, NUME_COL, SAL_COL, NR_SEC_COL) (aici NR_COL este numărul legitimației colaboratorului, NUME_COL – numele colaboratorului, SAL_COL – salariul, iar NR_SEC_COL – numărul secției în care colaboratorul concret lucrează) și SECȚII(NUMĂRUL_SEC, NR_COL_IN_SECȚIE, SEF_SECȚIE). Dorim să aflăm numele și numerele colaboratorilor, care sunt șefii secțiilor cu numărul total de colaboratori mai mare ca 50. În sensul algebrei relaționale am fi obținut expresia, care ar fi citită aproximativ astfel:
Să se unească relațiile COLABORATORI și SECȚII cu condiția NR_COL= SEF_SECȚIE;
Relația obținută să fie restricționată cu condiția NR_COL_IN_SECȚIE > 50;
Rezultatul să fie proiectat pe atributul NR_COL, NUME_COL.
Fiecare pas corespunde unei operații relaționale. Dacă vom formula aceeași interpelare cu ajutorul calculului relațional (ceea ce va urma în continuare), vom obține o formulă, care ar putea fi citită astfel: să se determine NR_COL, NUME_COL pentru colaboratorii pentru care există secție cu aceeași valoare SEF_SECȚIE (ca și NUME_COL (sau NR_COL)) și cu valoarea NR_COL_IN_SECȚIE mai mare decât 50.
Aici am arătat numai caracteristicile relației rezultante, nu am spus nimic despre modalitatea de formare a acesteea. Sistemul va trebui singur să decidă, care operații și în care ordine să fie îndeplinite peste relațiile COLABORATORI și SECȚII. Spunem că formularea algebrică este procedurală, adică definește regulile de îndeplinire a interpelării, iar formularea logică (a doua) este descriptivă sau declarativă, deoarece ea doar descrie proprietățile rezultatului dorit. Aceste două mecanisme sunt echivalente și există reguli, relativ simple, care permit transformarea unui formalism în celălalt.
3.1. Relații și proprietățile lor
Se numește relație n-ară pe M submulțimea R Mn. Vom zice că a1,…, an, sunt în relația R dacă (a1,…,an)R. O relație unară este o parte a mulțimii M și determină o proprietate a elementelor unei submulțimi a mulțimii M din care cauză pentru n = 1 denumirea de relație practic nu se utilizează. Un interes mai mare prezintă cazul când n = 2 – relațiile binare. Dacă a și b se află în relația R, aceasta se va scrie aRb.
Exemplul 3.1. Pentru mulțimea N: relația "<" are loc pentru perechea (3,9) și nu are loc pentru (6,4). Relația "a fi divizor" are loc pentru perechea (7,35) și nu are loc pentru (18,2) sau (4,9). Pentru o mulțime de oameni pot fi relații de tipul "a fi prieteni", "a locui in același oraș", "a fi fiu", etc. <
Restricția lui R pe M1M este R1 = RM12.
Pentru definirea unei relații pot fi utilizate oricare din metodele de definire a mulțimilor. O posibilitate suplimentară este matricea de relație. Pentru mulțimea M = {a1, a2,…, am} aceasta este o matrice mxm оn care
1 dacă aiRaj,
a(i,j) =
0 оn caz contrar.
Deoarece relația este în ultimă instanță o mulțime, pot fi executate aceleași operații (reuniune, intersecție etc.) și cu relațiile.
O relație se numește inversa relației R (se va nota R-1) dacă aiRaj are loc atunci și numai atunci cвnd are loc ajR-1ai.
Relația poate poseda o serie de proprietăți dintre care vom menționa reflexivitatea, simetria și tranzitivitatea. Dacă pentru aM are loc aRa relația R se numește reflexivă. Diagonala principală a matricei relației R conține numai unități. Relația R se numește antireflexivă dacă nu există aM pentru care ar avea loc aRa. Diagonala principală a matricei unei astfel de relații conține numai zerouri. Relațiile "", "a avea un divizor comun" sunt reflexive. Relațiile "a fi fiu", ">" – sunt antireflexive.
Dacă pentru o pereche (a,b)M2 din aRb rezultă bRa (relația are loc în ambele părți sau nu are loc de fel), relația R se numește simetrică. Pentru astfel de relații c(i,j) = c(j,i): matricea este simetrică față de diagonala principală. Relația se va numi antisimetrică, dacă din aiRaj și ajRai rezultă că ai=aj . Relația "" este antisimetrică, iar "a locui în același oraș" – simetrică.
Relația R se numește tranzitivă dacă pentru oricare a, b și c din aRb și bRc rezultă aRc. Relațiile "a locui în același oraș", "egal", "<" sunt tranzitive, iar "a fi fiu" nu este tranzitivă.
Pentru oricare relație R poate fi definită noțiunea de închidere tranzitivă R*: aR*b (a se află în relația R* cu b), dacă în M există o secvență de n elemente a=a1,…, an-1, an = b оn care pentru elementele vecine are loc R: aRa2, a2Ra3,…, an-1Rb. Dacă R este tranzitivă, atunci R*=R. Pentru relația "a fi fiu" relația "a fi descendent direct" este închidere tranzitivă (este reuniunea relațiilor "a fi fiu", "a fi nepot", "a fi strănepot" s.a.m.d.).
O relație care posedă proprietățile reflexivitate, simetrie și tranzitivitate se numește relație de echivalență.
Se numește relație de ordine oricare relație care posedă proprietățile reflexivitate, antisimetrie și tranzitivitate. O relație antireflexivă, antisimetrică și tranzitivă se numește relație de ordine strictă. Două elemente a și b se numesc comparabile conform relației de ordine R dacă are loc aRb sau bRa. O mulțime M cu o relație de ordine definită pe M se numește total ordonată dacă oricare două elemente din M sunt comparabile și parțial ordonată, оn caz contrar.
Exemplul 3.2. Relațiile "", "" pentru o mulțime de numere sunt relații de ordine, iar "<", ">" – de ordine strictă. Relația de subordonare în cadrul unei întreprinderi definește o ordine strictă (dar parțială – nu pot fi comparați colaboratorii diferitor departamente).
În alfabetul latin literele sunt aranjate într-o ordine binecunoscută: se află în relația de precedare a literelor. Conform acestei relații poate fi stabilită relația de precedare a cuvintelor – ordinea lexicografică a cuvintelor (utilizată de exemplu în dicționare). Relația de ordine lexicografică poate fi definită și pentru informații numerice. De exemplu, în calculator data și anul sunt memorizate sub forma "anul, luna, ziua" pentru ca ordinea de creștere a datei totale să coincidă cu ordinea lexicografică. <
Exemplul 3.3. B este mulțimea tuturor cuvintelor binare de orice lungime și desemnează unicul cuvânt binar de lungime 0. Dacă m este un cuvвnt binar de lungime p, vom nota biții acestuia m1, m2,…, mp. Relația de ordine , definită peste B, se numește de ordine lexicografică, dacă:
m, m
pentru m de lungime p și n de lungime q cu proprietatea 0 < p q
m n, dacă m1=n1, m2=n2,…, mp=np,
m n, dacă m1=n1, m2=n2,…, ms-1=nsi1, ms < ns, pentru 1 s p,
n m, dacă m1=n1, m2=n2,…, ms-1=nsi1, ms > ns, pentru 1 s p. <
3.2. Operații și algebre. Proprietățile operațiilor
Funcția de tipul : MnM se va numi operație n-ară pe M. Setul A = <M, >, оn care este o mulțime de operații definite pe M, se numește algebră. Mulțimea M se va numi mulțime de bază sau suportul, iar = {1, 2,…, m,…} – signatura algebrei A. Vectorul, componentele căruia sunt aritățile operațiilor 1, 2,… se numește tipul algebrei A.
Operația se numește:
comutativă, dacă ab = ba,
asociativă, dacă pentru oricare a, b, c are loc (ab)c = a(bc),
idempotentă, dacă aa = a,
distributivă stânga față de operația g, dacă pentru oricare a, b, c are loc relația
a(bgc) = (ab)g(ac), și distributivă dreapta dacă (agb)c = (ac)g(bc).
Dacă există un element e pentru care are loc ae = ea = a, atunci acest element se numește neutru (sau unitate).
Exemplul 3.4. a) Pentru o mulțime arbitrară U și mulțimea tuturor părților B(U), algebra A = {B(U), , , } se numește algebră booleana a mulțimilor. Tipul ei este (2,2,1).
b) Algebra A = {R,+,x} se numește câmp al numerelor reale. Ambele operații sunt binare, deci tipul este (2,2).<
Algebrele L = {M,,} (cu două operații binare – reuniunea și intersecția) se numesc latice, dacă au loc axiomele:
P1: ab = ba, ab = ba – comutativitate,
P2: a(bc) = (ab)c, a(bc) = (ab)c – asociativitate,
P3: a(ba) = a, a(ba) = a – absorbție,
pentru oricare a, b, cM.
3.3. Modele si sisteme algebrice. Algebra relațiilor
Noțiunea de model este una din noțiunile de bază în matematica discretă. Se va numi model M setul care constă din mulțimea D – suportul modelului, și o mulțime de relații S definite pe D:
M = <D, S>.
Aici S = {R11, R12,…, R1n1, R21, R22,…, R2n2,…, Rm1, Rm2,…, Rmnm} este signatura modelului, RijMi. Exponenta suportului determină aritatea relației. Două relații Ri și Rj care au aceeași aritate se numesc compatibile.
Setul care conține mulțimea D, operațiile și relațiile definite pe D
A = <D, F, S>.
se numește sistem algebric.
Modelul este un caz particular al sistemului algebric, când mulțimea F este vidă, iar pentru o algebră mulțimea S este vidă.
Un alt caz particular al sistemelor algebrice оl constituie algebra relațiilor și extensia acesteea – algebra relațională. Pentru o algebră a relațiilor drept suport servește mulțimea relațiilor considerate, iar signatura o formează operațiile de reuniune, intersecție, diferență și produsul cartezian extins al relațiilor. Să facem cunoștință cu aceste operații.
Reuniunea RiRj a două relații compatibile Ri și Rj este mulțimea tuturor cortejurilor, fiecare dintre care aparține cel puțin uneia din relații.
Intersecția RiRj a două relații compatibile Ri și Rj se va numi mulțimea tuturor cortejurilor care aparțin ambelor relații în același timp.
Diferența Ri\Rj a două relații compatibile Ri și Rj se numește mulțimea tuturor cortejurilor care aparțin lui Ri și nu aparțin relației Rj .
Produs cartezian extins RixRj a două relații Ri și Rj se va numi mulțimea tuturor cortejurilor formate prin concatenarea lui aRi și a lui bRj.
Exemplu: dacă Ri ={(a,b),(a,c),(a,e)}, iar Rj = ((a,b,c),(c,d,e)}, atunci
RixRj = {(a,b,a,b,c), (a,b,c,d,e), (a,c,a,b,c), (a,c,c,d,e), (a,e,a,b,c), (a,e,c,d,e)}.
Algebra relațiilor și modelele sunt utilizate pentru formalizarea unor obiecte reale. Vom exemplifica prin folosirea algebrei relațiilor în cazul bazelor relaționale de date.
O bază de date de tip relațional este un tablou bidimensional în care coloanele determină așa numitele domene (atribute), iar liniile sunt cortejuri de valori concrete ale atributelor, care se află în relația R.
Exemplul 3.5. Relația R5 – "examene" (v.tab. 3.1). Relația R5 este o submulțime a produsului cartezian D1xD2xD3xD4xD5. Elemente ale domenului Di sunt valorile atributelor:
D1 = {3-101, 3-501, 3-502, 3-310} – numerele auditoriilor unde au loc examenele;
D2 = {Matematica discretă în inginerie, Microelectronica, Fizica, Circuite integrate, Electrotehnica} – denumirea disciplinelor;
D3 = {conf.V.Beșliu, conf. V.Negură, conf.A.Diligul, conf.V.Șontea, prof.I.Samusi} -examinatorii;
D4 = {3 iunie, 4 iunie, 8 iunie, 13 iunie} – data examenului;
D5 = {TI-961, TI-962, TI-963, C-941, C-942, C-951, C-952} – denumirea grupei.
Tabelul 3.1. Relația “examene”.
Numerele 1, 2,…, 10 din prima coloană identifică elemente ale relației R5. <
Algebra relațională este o extensie a algebrei relațiilor în sens că signatura S în afară de cele 4 operații descrise anterior mai conține câteva operații speciale, de exemplu proiecția, selecția și joncțiunea.
Operația selecție permite evidențierea unei submulțimi de cortejuri care posedă o proprietate dată. De exemplu, operația selecție permite evidențierea relației orarul conf. V.Beșliu – liniile оn care valoarea domenului D3 este conf. V.Beșliu:
Tabelul 3.2. Rezultatul operației selecție pentru valoarea “conf. V.Beșliu”
Operația proiecție se definește introducând pentru suportul D al algebrei relaționale o partiție de n submulțimi (n este aritatea relației) RnDn.
Proiecția relației binare R2AxB pe A (PrR2/A) se numește mulțimea {ai | (ai,bi)R2}.
Proiecția PrRn/Ai1,…,Aim a relației n-are RnA1xA2x…xAn, m n, pe Ai1, Ai2,…, Aim se numește mulțimea cortejurilor (ai1, ai2,…, aim), оn care ai1Ai1, ai2Ai2,…, aimAim și fiecare cortej este parte a unui element al relației n-are Rn. Cu alte cuvinte, operația proiecție permite construirea unei submulțimi verticale a relației (a unei mulțimi de submulțimi de atribute care se obține prin alegerea unor domene concrete). De exemplu, Pr(R5/D2,D3) determină denumirea examenelor și numele examinatorilor (liniile care coincid se scriu o singură dată, v.tab. 3.3).
Tabelul 3.3. Rezultatul operației “proiecție”.
Operația joncțiune (join) a două tabele care au un domen comun permite construirea unui tabel nou în care fiecare linie se va obține din unirea a două linii din tabelele inițiale. Aceste linii corespund aceluiași atribut din domenul comun. Domenul comun se va scrie o singură dată.
De exemplu, pentru tabele 3.4 și 3.5 domenul comun este D5, rezultatul operației de joncțiune este prezentat în tabelul 3.6.
Tabelul 3.4.
Tabelul 3.5.
Tabelul 3.6. Rezultatul operației “join”.
Operația join este definită nu numai pentru condiția de egalitate a două domene, ci pot fi și alte condiții de comparare, de exemplu, >, , <, , etc.
4. Proiectarea bazelor de date relaționale
Proiectarea bazelor de date rezolvă două probleme:
Cum să fie reprezentate obiectele domeniului obiectiv în obiecte abstracte ale modelului datelor astfel ca această reprezentare să nu contrazică semantica domeniului obiectiv și să fie, în măsura posibilităților, cea mai bună (eficientă, comodă, etc.)? Adesea această problemă este numită proiectarea logică a BD.
Cum să se asigure executarea eficientă a interpelărilor BD? Altfel, luând în considerație specificul unui SGBD concret, cum vor fi plasate datele în memoria externă, care structuri vor fi create suplimentar (de ex., indici), etc. Această problemă este numită proiectarea fizică a BD.
Este dificil să fie propuse niște rețete de ordin general pentru rezolvarea problemei proiectării fizice. Prea multe depind de SGBD folosit. De exemplu, cu ajutorul SGBD Ingres poate fi aleasă una dintre metodele de organizare fizică a relațiilor, iar lucrând cu System R ar trebui să ne gândim în primul rând la clasterizarea relațiilor și la setul necesar de indici, etc. Din această cauză vom cerceta mai departe doar momentele, legate de proiectarea logică a BDR, care au importanță mare atunci când utilizăm orice SGBDR. Mai mult, nu vom discuta un aspect foarte important al proiectării – determinarea cererilor de consistență (cu excepția restricției cheii primare). Aceasta din cauza, că atunci când este utilizat un SGBD cu mecanisme de asigurare a consistenței datelor (de ex., sistemele SQL orientate) este foarte dificil să fie propusă o abordare generală de determinare a cererilor de consistență. Aceste cereri (restricții) pot fi de ordin foarte general, iar formularea lor ține mai repede de artă, decât de măiestria inginerească. În literatură în această direcție este propus cel mult controlul automat al necontradicției setului de restricții al consistenței.
Vom considera, deci, că problema proiectarii unei baze de date de tip relațional constă în luarea unei decizii motivate în vederea obținerii unor răspunsuri la următoarele întrebări:
Care sunt relațiile din care este formată baza de date?
Care vor fi atributele acestor relații?
4.1. Proiectarea logică
Vom face cunoștință mai întâi cu abordarea clasică, când întreg procesul de proiectare are loc în termeni din domeniul modelului relațional de date, folosind metoda determinării consecvente a setului satisfăcător de relații. Punctul de plecare este reprezentarea domeniului obiectiv sub forma uneia sau mai multor relații și la fiecare pas al procesului de proiectare se va produce un set oarecare de scheme ale relațiilor, care posedă proprietăți mai bune decât la pasul precedent. Procesul de proiectare se transformă într-un proces de normalizare a schemelor relațiilor, iar fiecare formă normală care urmează posedă proprietăți mai bune decât forma precedentă.
Fiecărei forme normale îi corespunde un set anumit de cerințe, iar relația se află într-o formă normală, dacă satisface setul de cerințe caracteristic ei. Ca exemplu de set de cerințe poate fi considerată restricția primei forme normale – valorile tuturor atributelor relației sunt atomare. Deoarece restricția primei forme normale este o cerință fundamentală a modelului de date relațional clasic, vom considera că setul inițial de relații deja corespunde acestei cerințe. În teoria bazelor de date relaționale este evidențiat următorul șir de forme normale:
Prima formă normală (1FN);
A doua formă normală (2FN);
A treia formă normală (3FN);
Forma normală Boyce-Codde (BCNF);
A patra formă normală (4FN);
A cincea formă normală sau forma normală proiecție-reuniune (5FN sau PJ/NF).
Proprietățile principale ale formelor normale:
Fiecare următoare formă normală este într-un anumit sens mai bună decât precedenta;
Trecerea la următoarea formă normală păstrează proprietățile formelor normale precedente.
La baza procesului de proiectare se află metoda normalizării – decompoziția relației, care se află în forma normală precedentă în două sau mai multe relații, care vor respecta cerințele următoarei forme normale.
În practică, cele mai importante forme normale ale relațiilor sunt bazate pe noțiunea fundamentală, numită în teoria BDR dependență (relație) funcțională.
Definiția 1. Dependență funcțională. În relația R atributul y depinde funcțional de atributul x (x și y pot fi compuse) dacă și numai dacă fiecărei valori a lui x îi corespunde exact o valoare a lui y: x R y.
Definiția 2. Dependență funcțională totală. Dependență funcțională x R y se numește totală, dacă atributul y nu depinde funcțional de nici o submulțime proprie a lui x.
Definiția 3. Dependență funcțională tranzitivă. Dependență funcțională x R y se numește tranzitivă, dacă există un atribut z, astfel încât au loc dependențele funcționale totale x R z și z R y și lipsește dependența funcțională R.z R.x. (Dacă ultima cerință nu va fi îndeplinită vom avea în orice relație, care posedă mai multe chei, dependențe tranzitive “neinteresante”).
Definiția 4. Atribut simplu. Numim atribut simplu orice atribut al relației, care nu intră în componența cheii primare.
Definiția 5. Atribute reciproc independente. Două și mai multe atribute sunt reciproc independente dacă nici unul dintre aceste atribute nu este dependent funcțional de altele.
4.1.1. A doua formă normală
Considerăm următoarea schemă a relației:
COLABORATORI–SECȚII-PROIECTE(Nr_COL, Salariu_COL, SECȚIA_Nr, Nr_PROIECT, SARCINA_COL).
Cheie primară: Nr_COL, Nr_PROIECT.
Dependențe funcționale:
Nr_COL Salariu_COL
Nr_COL SECȚIA_Nr
SECȚIA_Nr Salariu_COL
Nr_COL, Nr_PROIECT SARCINA_COL.
Observăm, că deși în calitate de cheie primară a fost luat atributul compus Nr_COL, Nr_PROIECT, atributele Salariu_COL și SECȚIA_Nr depind funcțional de o parte a cheii primare, atributul Nr_COL. Drept rezultat, nu vom putea introduce în relația COLABORATORI-SECȚII-PROIECTE cortejul, care descrie un colaborator, care nu este încă implicat în realizarea vreunui proiect (cheia primară nu poate conține valori indefinite). Atunci când acest cortej va fi eliminat va fi distrusă nu numai legătura colaboratorului cu proiectul dat, dar va fi pierdută și informația, că acest colaborator lucrează într-o secție oarecare. Dacă colaboratorul este transferat într-o altă secție vom fi nevoiți să modificăm toate cortejurile, care descriu acest colaborator, în caz contrar vom obține rezultate necoordonate. Aceste fenomene neplăcute se numesc anomalii ale schemei relației. Ele sunt eliminate prin normalizare.
Definița 6. A doua formă normală (aici vom considera, că unica cheie a relației este cheia primară). Relația R se află în a doua forma normală (2FN) atunci și numai atunci, când aflându-se în prima formă normală, fiecare atribut simplu depinde total de cheia primară.
Ca exemplu va fi următoarea decompoziție a relației COLABORATORI-SECȚII-PROIECTE în două relații COLABORATORI-SECȚII și COLABORATORI-PROIECTE:
COLABORATORI-SECȚII(Nr_COL, Salariu_COL, SECȚIA_Nr)
Cheia primară: Nr_COL.
Dependențe funcționale:
Nr_COL Salariu_COL
Nr_COL SECȚIA_Nr
SECȚIA_NR Salariu_COL
COLABORATORI-PROIECTE(Nr_COL, Nr_PROIECT, SARCINA_COL)
Cheia primară: Nr_COL, Nr_PROIECT
Dependențe funcționale:
Nr_COL, Nr_PROIECT SARCINA_COL
Fiecare dintre aceste relații se află în a doua formă normală și în ele sunt eliminate anomaliile evidențiate mai sus.
Dacă se va permite prezența mai multor chei, definiția 6 va avea următoarea formulare:
Relația R se află în a doua forma normală (2FN) atunci și numai atunci, când ea se află în prima formă normală și fiecare atribut simplu depinde total de fiecare cheie a relației R. Nu ne vom opri la exemple de relații cu mai multe chei, acestea fiind prea complicate și rar întâlnite în practică.
4.1.2. A treia formă normală
Fie relația COLABORATORI-SECȚII, care se află în forma a doua normală. Observăm, că dependența funcțională Nr_COL Salariu_COL este tranzitivă, fiind consecința dependențelor funcționale Nr_COL SECȚIA_Nr și SECȚIA_Nr Salariu_COL. Altfel spus, salariul unui colaborator nu este o caracteristică a colaboratorului, ci a secției în care acesta lucrează (presupunere poate nu chiar corectă, dar acceptabilă pentru exemplu).
Drept rezultat, nu vom putea introduce în BD informații despre salariul unei secții până când în această secție nu va apare cel puțin un colaborator (cheia primară nu poate conține valori indefinite). Eliminând cortejul, care descrie ultimul colaborator al secției date se va pierde informație despre salariul secției. Pentru a modifica în mod coordonat salariul secției vom fi nevoiți să găsim mai înrâi toate cortejurile, care descriu colaboratorii secției date. Asta înseamă, că în relația COLABORATORI-SECȚII există în continuare anomalii. Acestea pot fi eliminate prin aceeași procedură de normalizare.
Definița 7. A treia formă normală. (Din nou vom defini presupunând existența unei chei unice). Relația R se află în a treia forma normală (3FN) atunci și numai atunci, când se află în a doua formă normală, și fiecare atribut simplu depinde netranzitiv de cheia primară.
Iată decompoziția relației COLABORATORI-SECȚII în două relații COLABORATORI și SECȚII:
COLABORATORI(Nr_COL, SECȚIA_Nr)
Cheia primară: Nr_COL
Dependențe funcționale: Nr_COL SECȚIA_Nr
SECȚII(SECȚIA_Nr, Salariu_COL)
Cheia primară: SECȚIA_Nr
Dependențe funcționale: SECȚIA_Nr Salariu_COL
Fiecare dintre aceste două relații se află în a treia formă normală și nu are anomaliile de mai sus.
Dacă vrem să omitem restricția, că fiecare relație are o singură cheie, atunci definiția 3FN va fi următoarea:
Definiția 71 . Relația R se află în a treia forma normală (3FN) atunci și numai atunci, când se află în a doua formă normală, și fiecare atribut simplu depinde netranzitiv de o cheie oarecare a relației R.
În practică, forma a treia normală în marea majoritate a cazurilor este cea finală și cu determinarea acestei forme, de obicei, procesul de proiectare a BDR ia sfârșit. Dar câteodată, totuși, procesul de normalizare trebuie continuat.
4.1.3. Forma normală Boyce-Codd
Considerăm următoarea schemă a relației:
COLABORATORI-PROIECTE (Nr_COL, Nume_COL, Nr_PROIECT, SARCINA_COL)
Chei posibile:
Nr_COL, Nr_PROIECT
Nume_COL, Nr_PROIECT
Dependențe funcționale:
Nr_COL Nume_COL
Nr_COL Nr_PROIECT
Nume_COL Nr_COL
Nume_COL Nr_PROIECT
Nr_COL, Nr_PROIECT SARCINA_COL
Nume_COL, Nr_PROIECT SARCINA_PROIECT
Am presupus în acest exemplu, că persoana colaboratorului este definită în totalitate atât de numărul acestuia, cât și de numele lui (nu оntotdeauna are loc оn realitate).
În conformitate cu definiția 71 relația COLABORATORI-PROIECTE se află în forma normală 3. Însă, deoarece există dependențe funcționale ale atributelor relației de un atribut, care este parte a cheii primare, apar anomalii. De exemplu, pentru a schimba în mod consistent numele colaboratorului cu numărul dat va fi necesar să modificăm toate cortejurile, care conțin numărul lui.
Definiția 8. Determinant. Numim determinant orice atribut de care deăpinde funcțional în totalitate un oarecare alt atribut.
Definița 9. Forma normală Boyce-Codde. Relația R se află în forma normală Boyce-Codde atunci și numai atunci când determinantul ei este o cheie posibilă.
Este evident, că această cerință nu este îndeplinită pentru relația COLABORATORI-PROIECTE. Putem realiza decompoziția ei în relațiile COLABORATORI și COLABORATORI-PROIECTE:
COLABORATORI(Nr_COL, Nume_COL)
Chei posibile:
Nr_COL
Nume_COL
Dpendențe funcționale:
Nr_COL Nume_COL
Nume_COL Nr_COL
COLABORATORI_PROIECTE(Nr_COL, Nr_PROIECT, SARCINA_COL)
Cheie posibilă: Nr_COL, Nr_COL
Dependențe funcționale: Nr_COL, Nr_PROIECT Sarcina_COL
Este posibilă și o altă decompoziție, dacă am lua la bază Nume_COL. În ambele cazuri relațiile obținute COLABORATORI și COLABORATORI-PROIECTE se află în BCNF cu anomaliile evidențiate.
4.1.4. A patra formă normală
Fie următorul exemplu de schemă a relației:
PROIECTE(Nr_PROIECT, COL_PROIECT, PROIECT_SARCINĂ)
Relația PROIECTE conține numerele proiectelor, lista colaboratorilor fiecărui proiect și lista lucrărilor prevăzute în proiect. Colaboratorii pot participa în mai multe proiecte, iar proiecte diferite pot avea lucrări de același fel.
Fiecare cortej al relației legă un proiect oarecare de colaboratorul care participă în acest proiect și de lucrarea pe care colaboratorul o îndeplinește în cadrul proiectului dat (presupunem că orice colaborator participant la proiect îndeplinește toate lucrările prevăzute de proiect). Din această cauză unica cheie posibilă a relației este atributul compus Nr_PROIECT, COL_PROIECT, PROIECT_SARCINĂ și nu există alți determinanți. Relația PROIECTE se află, deci, în BCNF. Ea are un șir de neajunsuri. De exemplu, dacă un colaborator oarecare este delegat la un proiect dat, va fi necesar să inserăm în relația PROIECTE atâtea cortejuri, câte lucrări sunt în proiect.
Definiția 10. Dependențe multiple. În relația R(A, B, C) există o dependență multiplă R.A > > R.B dacă și numai dacă mulțimea valorilor lui B, care corespunde unei perechi de valori A și C depinde numai de A și nu depinde de C.
În relația PROIECTE există două dependențe multiple
Nr_PROIECT > > COL_PROIECT
Nr_PROIECT > > PROIECT_SARCINĂ.
În caz general, în relația R(A, B, C) există o dependență multiplă R.A > > R.B dacă și numai dacă există o dependență multiplă R.A > > R.C.
Normalizarea relațiilr asemănătoare relației PROIECTE se bazaează pe următoarea teoremă:
Relația R(A, B, C) poate fi proiectată fără pierderi în relațiile R1(A,B) și R2(A,C) atunci și numai atunci când există MVD A > > B|C.
Prin proiectare fără pierderi se consideră decompoziția uei relații, când relația inițială poate fi restabilită integral și fără redundanță prin joncțiunea simplă a relațiilor obținute prin decompoziție.
Definiția 11. A patra formă normală. Relația R se consideră în a patra formă normală atunci și numai atunci când în cazul existenței dependenței multiple A> > B toate celelalte atribute ale R depind funcțional de A.
În exemplul nostru putem propune decompoziția relației PROIECTE în două relații PROIECTE_COLABORATORI și PROIECTE_SARCINI:
PROIECTE_COLABORATORI(Nr_PROIECT, COL_PROIECT)
PROIECTE_SARCINI(Nr_PROIECT, PROIECT_SARCINĂ).
Ambele relații sunt în a patra formă normală și nu au anomaliile de mai sus.
4.1.5. A cincea formă normală
În toate operațiile de normalizare petrecute până acum o relație a fost descompusă în două. Nu întotdeauna este posibil acest lucru, dar este posibilă decompoziția în mai multe relații, fiecare având proprietăți mai bune. Considerăm relația COLABORATORI_SECȚII_PROIECTE(Nr_COL, Nr_SECȚIE, Nr_PROIECT).
Presupunem că un colaborator poate lucra în mai multe secții, iar în fiecare secție – cu mai multe proiecte. Cheie primară pentru această relație este întreaga totalitate a atributelor, lipsind dependențe funcționale și multiple. Din această cauză relația se află în 4NF. Însă pot exista anomalii, care pot fi eliminate prin decompoziția relației inițiale în trei relații.
Definiția 12. Dependența joncțiunii. Relația R(X, Y,…, Z) satisface dependențele joncțiunii *(X, Y,…, Z) atunci și numai atunci când R poate fi restabilită fără pierderi prin joncțiunea proiecțiilor sale pe X, Y,…, Z.
Definiția 13. A cincea formă normală. Relația R se află în a cincea formă normală (proiecție-joncțiune – PJ/NF) atunci și numai atunci când orice dependență a joncțiunii în R rezultă din existența unei oarecare chei posibile în R.
Introducem următoarele nume pentru atributele compuse:
CS = {Nr_COL, Nr_SECȚIE}
CP = {Nr_COL, Nr_PROIECT}
SP = {Nr_SECȚIE, Nr_PROIECT}
Presupunem că în relația COLABORATORI_SECȚII_PROIECTE există dependența joncțiunii *(CS, CP, SP): Prin exemple poate fi arătat, că la inserarea și eliminarea cortejurilor pot să apară probleme. Acestea pot fi evitate prin decompoziția relației inițiale în trei relații noi:
COLABORATORI_SECȚII(Nr_COL, Nr_SECȚIE)
COLABORATORI_PROIECTE(Nr_COL, Nr_PROIECT)
SECȚII_PROIECTE(Nr_SECȚIE, Nr_PROIECT)
A cincea formă normală este ultima, care poate fi obținută prin decompoziție. Condițiile acestei forme sunt departe de a fi triviale din care cauză 5NF în practică se folosește relativ rar.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Proiectarea Si Analiza Sistemelor de Operare (ID: 149266)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.