Failisüsteemi realiseeringud

Failisüsteemi disainil on kaks tahku:
1.	liidese disain: kuidas failisüsteem paistab kasutajale, millised on kasutaja võimalused, st loogilise struktuuri kavandamine
2.	algoritmide ja andmestruktuuride valimine loogiliste struktuuride realiseerimiseks.
Failisüsteemi realiseering on tavaliselt jaotatud erineva tasemete kihtideks, näiteks
•	I/O kontroll: seadmete draiverid ning katkestuste haldurid, sõltumatud loogilisest struktuurist. Draiverid tõlgivad kõrge taseme käsud (tüüpi “kirjutada kettale plokk nr. 158”) kettaseadme kontrollerile sobivaks masinkoodis käskude jadaks.
•	baasfailisüsteem – teab, kuidas leida igale seadmele sobiv draiver ning kuidas neile käske edastada. Sõltumatu loogilisest struktuurist.
•	Failide organiseerimise moodul – tegeleb vaba mälu haldamisega, loogiliste aadresside tõlkimisega füüsilisteks, samuti tegeleb kettale kirjutamise planeerimisega.
•	loogiline failisüsteem: tegeleb metaandmetega, milleks on kõik failidega seatud andmed väljaarvatud tegelik faili sisu. Haldab failiga seotud informatsiooni (tavaliselt faili kontrollplokis, FCB), tegeleb juurdepääsuõiguste kontrolliga. Tegeleb kasutajaprogrammide I/O käskude teisendamisega madalama taseme operatsioonideks.
Lisaks failisüsteemi realiseerivatele programmidele koosneb failisüsteem mitmetest andmestruktuuridest, millest osa paikneb välismälus ning osa põhimälus. Välismälus paiknevateks struktuurid sisaldavad tavaliselt iga kettasektsiooni jaoks
1.	alglaadimisplokki
2.	sektsiooni kontrollplokki (Unixi failisüsteemis superblock, NTFS süsteemis Master File Table). Sisaldab sektiooni andmeplokkide arvu ja asukohta, suurust, viiteid vabadele plokkidele, viiteid failide kontrollplokkidele ning vabadele failide kontrollplokkidele
3.	kataloogistruktuuri
4.	failide kontrollplokke, mis sisaldavad failiga seotud õigusi, suurust, andmeplokkide asukohta jne. NTFSis sisalduvad need andmed põhilises failitabelis (Master File Table)
Põhimälus hoitavateks struktuurideks on tavaliselt
1.	Tabel ühendatud sektsioonidest (partitions) koos sektsioonis paikneva failisüsteemi infoga
2.	tabel hiljuti kasutatud kataloogide infoga
3.	süsteemi avatud failide tabel
4.	protsesside avatud failide tabelid
Mälu eraldamise meetodid
Kolm põhilist meetodit: järjestikune eraldamine, lingitud eraldamine ja indekseeritud eraldamine.
1.	järjestikune eraldamine võimaldab kiiret andmevahetust (järjestikuste mälublokkide kirjutamine ja lugemine on kiire) ning arvepidamine on lihtne (vaja säilitada ainult algusaadress ning mäluplokkide arv), kuid probleemiks on välimine killustatus, täiendava mälu eraldamine faili suurenemisel ning ka sisemine killustatus, kui faili suurenemist ette nähes eraldatakse liiga suur mäluplokk. Modifikatsiooniks on süsteem, kus failile eraldatakse mälu suhteliselt suurte portsude kaupa, iga portsu jaoks salvestatakse alguskoha aadress ning plokkide arv (sellist süsteemi kasutab NTFS). Probleemiks võib olla sisemine killustatus.
2.	lingitud eraldamine: kataloogistruktuuris on kirjas iga faili esimese mäluploki aadress ning kettal on iga mäluploki lõpus kirjas järgmise mäluploki aadress või siis faili lõpu sümbol. Probleemiks on otsepöörduse raskus. Modifikatsiooniks failipaigutustabeli (file allocation table, FAT) kasutamine FAT ja FAT32 failisüsteemides. Fat on iga kettasektsiooni alguses paiknev tabel, kus on kirje iga selle sektsiooni andmeploki jaoks. Kui andmeplokk on kasutamata, siis tabelis on 0, kasutuse korral aga faililõpusümbol (-1) või järgmise selle faili mäluploki number.
3.	indekseeritud mälueraldus: iga faili jaoks on spetsiaalne indeksplokk, mis sisaldab selle faili jaoks eraldatud mäluplokkide numbreid. Kasutusel Unix ja Linux süsteemides.
Arvepidamine vaba mälu üle 
FAT süsteemides ei ole eraldi andmestikku vaja, kogu info on olemas FAT tabelis. Teistes süsteemides kasutatavatest meetoditest on lihtsaimad järgmised kaks:
1.	mälukasutus fikseeritakse nn bittide vektoris, kus iga mäluploki jaoks on vastavas positsioonis kas 0 (vaba) või 1 (kasutusel). Näiteks
0011101000000...
näitab, et esimesed kaks plokki on vabad, järgmised kolm plokki on kasutusel, kuues on vaba, seitsmes on kasutusel, kaheksas, üheksas, .jne on vabad.
2.	hoida vabade mäluplokkide nimekirja ahelloendina, kus viide esimesele vabale mäluplokile on fikseeritud kohal ning koos sellega on viide, kust leida järgmise vaba mäluploki aadressi.
Logifaili kasutamine failisüsteemi kooskõla tagamiseks
Failioperatsioonidega seoses võivad muutuda mitmed failisüsteemi andmed. Näiteks mingile failile mälu eraldamisel tuleb muutunud suurus ning uue mäluploki aadress kajastada failikontrollplokis ning modifitseerida vabade mäluplokkide nimekirja. Kui süsteem peaks hanguma nende tegevuste poole peal, võib tekkida tõsiseid probleeme. Selleks vältimiseks kasutab näiteks NTFS logifaili. Iga muudatus failisüsteemi metaandmestikus kirjutatakse kõigepealt logifaili (see on kiirem kui tegelike muudatuste tegemine, kuna logifailile eraldatakse järjestikune mälupiirkond). Seejärel jagab op süsteem aega protsessile, mis sooritab järjest logifailis olevad muudatused failisüsteemi andmestikus. Kui kõik muudatused on sooritatud, siis kustutatakse vastavad andmed logifailist.
NFS (Network File System)
Võimaldab failide jagamist üle LANi ja WANi. NFS protokoll kirjeldab käskude formaadid, mis võimaldavad
•	otsida faili kataloogist
•	kataloogi sisu lugemist
•	tööd kataloogidega
•	failide atribuutidele juurdepääsu
•	failide lugemist ja kirjutamist
Teises arvutis oleva failisüsteemi kasutamiseks peab selle kõigepealt olemasolevale failisüsteemile liitma. Võrguga seotud probleemide vältimiseks kasutatakse järgnevaid meetmeid:
1.	faili avamise ja sulgemise käsud puuduvad, st. server ei hoia mingisugust failide kasutamisega seotud infot. Iga failidega seotud käsk peab sisaldama loogilise mäluploki numbrit, kuhu andmed kirjutada.
2.	faili kirjutamine on sünkroonne
NFS ei võimalda ühe faili kasutamise sünkroniseerimist erinevate kasutajate poolt.
Kettaseadme planeerimine
Kettale kirjutamisel kulub aega kirjutuspea õigele kohale liigutamiseks ning andmete ülekandmiseks.
1.	FCFS planeerimine – kõige lihtsam, kuid ei arvesta mäluplokkide asukohta, seega kulub palju aega kirjutuspea liigutamisele.
2.	SSTF (shortest seek time first, lühim otsimisaeg ennem) planeerimine: järmisena kirjutatakse momendiasukohale lähim mäluplokk. Parem, kui FCFS, kuid on võimalik nälgimine (mingi mäluplokk jääbki kirjutamist ootama)
3.	SCAN planeerimine: kirjutuspea liigub ühes suunas ketta lõpuni ning seejärel terves ulatuses tagasi. Järgmisena kirjutatakse liikumise suunas paiknev lähim plokk. Ketta keskel väiksem ooteaeg kui servades
4.	C-SCAN planeerimine. Kirjutatakse ainult ühes suunas liikudes. Ketta lõppu jõudes liigub kirjutuspea algusesse tagasi ilma andmeid kirjutamata. Ooteaeg ühesugune tervel kettal.
5.	LOOK planeerimine – SCAN või C-SCAN modifikatsioon, kus ühes suunas liigutakse ainult kuni viimase selles suunas paikneva I/O nõudeni, seejärel pöördub kirjutuspea tagasi.
Kettaseadme formaatimine
Eristatakse toorest formaatimist ja loogilist formaatimist
1.	toores formaat –madalatasemeline (füüsiline) formaatimine, toimub tavaliselt tehaselt. Kettaseade viiakse kontrolleri poolt kasutatavale kujule, jaotades füüsilise ketta mälupesad sektoriteks, mis koosnevad päisest, andmepiirkonnast (tüüpiliselt 512 baiti) ning sabaosast. Päis ja sabaosa sisaldavad kontrolleri poolt kasutatavaid andmeid, nt. sektori number, ECC (error-correcting code)
2.	loogiline formaatimine – failisüsteemi tekitamine