Unit 4 File Management System.ppt (File Services)

This is for learning purpose.

1. Sanjivani Rural Education Society’s
Sanjivani College of Engineering, Kopargaon-423 603
(An Autonomous Institute, Affiliated to Savitribai Phule Pune University, Pune)
NAAC ‘A’ Grade Accredited, ISO 9001:2015 Certified
Department of Computer Engineering
(NBA Accredited)
Prof. A. V. Brahmane
Assistant Professor
E-mail : [email protected]
Contact No: 91301 91301 Ext :145, 9922827812
Subject-Operating System and Administration (CO2013)
Unit IV-Introduction to the File System

2. Content
•Internal representation of the files,
•i-node,
•structure of regular files,
•directories,
•conversion of pathnames to i-node, Superblock,
•i-node assignments to new files,
•Allocation of disk blocks
•Pathnames,
•File system,
•Mounting and unmounting,
•The organization of the File Tree, File Types, File Attributes, Access Control lists.
•Case Study –Open Source Automation Red Hat Ansible, Introduction, Overview and setup, How
Ansible works, Playbooks, Variables, Advanced execution.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

3. Internal Representation of Files
•EveryfileaUNIXsystemhasauniqueinode.Processesinteractwithfilesusing
welldefinedsystemcalls.Theusersspecifyafilewithacharacterstringwhichis
thefile'spathandthenthesystemgettheinodewhichismappedtothefile
whichcorrespondstothepath.
•Thealgorithmsdescribedbelowareabovethelayerofbuffercache.
Diagrammatically,itcanbeshownlikethis:
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

4. File system Algorithms
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

5. Inodes
•Inodes exist in a static form on the disk. The kernel reads them into
in-core inodes and modifies them.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

6. Disk inodes consists of the following fields:
•Ownerinformation:ownershipisdividedintoauserandagroupofusers.Root
userhasaccesstoallthefiles.
•Filetype:itstateswhetherafileisanormalfile,adirectory,ablockorcharacter
specialfile,oradevicefile.
•Fileaccesspermissions:thereare3typesofaccesspermissions:owner,group
andothers.Thereareseparatepermissionsforreading,writingandexecuting.
Sinceexecutepermissionisnotapplicabletoadirectory,executepermissionfora
directorygivestherighttosearchinsidethedirectory.
•Accesstimes:thetimesatwhichthefilewaslastaccessedandlastmodified,and
thetimeatwhichtheinodeswaslastmodified
•Numberoflinks:numberofplacesfromwhichthefileisbeingreferred.
•.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

7. •Arrayofdiskblocks:eveniftheusersgetalogicallysequentialrepresentationof
datainfiles,theactualdataisscatteredacrossthedisk.Thisarraykeepsthe
addressesofthediskblocksonwhichthedataisscattered.
•Filesize:theaddressingofthefilebeginsfromlocation0fromrelativetothe
startinglocationandthesizeofthefileisthemaximumoffsetofthefile+1.For
example,ifausercreatesafileandwritesabyteatoffset999,thesizeofthefile
is1000
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

8. Sample Disk Inode
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

9. The in-core inodes
•Thein-coreinodescontainthefollowingfieldsinadditionaltothefieldsofthe
diskinode:
•Statusoftheinode
•Locked.
•Aprocessis(ormanyprocessesare)waitingforittobeunlocked.
•Thedataintheinodediffersfromthediskinodeduetochangeintheinode
data.
•Thedataintheinodediffersfromthediskinodeduetochangeinthefile
data.
•Thefileisamountpoint(discussedlater).
•Thedevicenumberofthelogicaldeviceofthefilesystemonwhichthefile
resides.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

10. •Inodenumber:thediskinodesareplacedinanarray.Sothenumberoftheinode
isnothingbuttheindexoftheinodeinthearray.Thatiswhythediskcopydoes
notneedtostoretheinodenumber.
•Pointstoinodes:justlikethebuffercache,thein-coreinodesarenothingbuta
cachefordiskinodes(butwithsomeextrainformationwhichisdeterministic).In-
coreinodesalsohavehashqueuesandafreelistandthelistsbehaveinavery
similarwaytothebufferlists.Theinodehasnextandpreviouspointerstothe
inodesinthehashqueueandfreelists.Thehashqueueshaveahashfunction
basedonthedevicenumberandinodenumber.
•Referencecount:itgivesthenumberofinstancesoffilesthatareactivecurrently.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

11. Accessing Inodes
•Thealgorithmigetallocatesanin-corecopyofaninode.
•Iftheinodeisnotfoundonahashqueue,itallocatesaninodefromthefreelist
andreadsthediskcopyintothein-coreinode.
•Italreadyknowstheinodenumberanddevicenumber.
•Itcalculatesthelogicalblocknumberonwhichthediskinoderesidesaccording
tohowmanyinodesfitintoonediskblock.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

12. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

13. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

14. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

15. Important Calculation
•Theformulaforcalculatingthelogicalblocknumberis:
•blocknumber=((inodenumber-1)/numberofinodesperblock)+startblockof
inodelist
•wherethedivisionoperationreturnstheintegerpartofthequotient.
•Tofindthebyteoffsetoftheinodeinthatblock,thisfollowingformulaisused:
•byteoffset=((inodenumber-1)%numberofinodesperblock)*sizeofdisk
inode
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

16. Algorithm for allocation of incore inode -iget
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

17. Releasing Inodes –iput
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

18. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

19. Structure of a Regular File
•InUNIX,thedatainfilesisnotstoredsequentiallyondisk.
•Ifitwastobestoredsequentially,thefilesizewouldnotbeflexiblewithoutlarge
fragmentation.
•Incaseofsequentialstorage,theinodewouldonlyneedtostorethestarting
addressandsize.
•Instead,theinodestoresthediskblocknumbersonwhichthedataispresent.
•Butforsuchstrategy,ifafilehaddataacross1000blocks,theinodewouldneed
tostorethenumbersof1000blocksandthesizeoftheinodewoulddiffer
accordingtothesizeofthefile.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

20. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

21. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

22. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

23. Direct and Indirect Blocks in Inode
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

24. •Tobeabletohaveconstantsizeandyetallowlargefiles,indirectaddressingisused.
•Theinodeshavearrayofsize13whichforstoringtheblocknumbers,although,the
numberofelementsinarrayisindependentofthestoragestrategy.
•Thefirst10membersofthearrayare"directaddresses",meaningthattheystorethe
blocknumbersofactualdata.
•The11thmemberis"singleindirect",itstorestheblocknumberoftheblockwhichhas
"directaddresses".
•The12thmemberis"doubleindirect",itstoresblocknumberofa"singleindirect"block.
•Andthe13thmemberis"tripleindirect",itstoresblocknumberofa"doubleindirect"
block.
•Thisstrategycanbeextendedto"quadruple"or"quintuple"indirectaddressing.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

25. •Ifalogicalblockonthefilesystemholds1Kbytesandthatablocknumberis
addressablebya32bitinteger,thenablockcanholdupto256blocknumbers.
Themaximumfilesizewith13memberdataarrayis:
•10directblockswith1Kbyteseach = 10Kbytes
•1indirectblockwith256directblocks = 256Kbytes
•1doubleindirectblockwith256indirectblocks = 64Mbytes
•1tripleindirectblockwith256doubleindirectblocks= 16Gbytes
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

26. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

27. •Toaccessbyteoffset9000:Thefirst10blockscontain10Kbytes.So9000shouldbein
thefirst10block.9000/1024=8soitisinthe8thblock(startingfrom0).And9000%
1024=808sothebyteoffsetintothe8thblockis808bytes(startingfrom0).(Block367
inthefigure.)
•Toaccessbyteoffset350000:Thefirst10blockscontain10Kbytes(350000-10240=
339760).Asingleindirectblockcontains256Kbytes.(339760-(256*1024)=77616).So
adoubleindirectblock(block9156inthefigure)mustbeused.Everysingleindirect
blockinthedoubleindirectblockcontains256K,sodatamustbeinthe0thsingle
indirectblock(block331inthefigure).Everydirectblockinthesingleindirectblock
addresses10Kbytes(77616/10240=7).Sothedatamustbein7th(startingfrom0)
directblock(blocknumber3333inthefigure).Andthebyteoffsetwillbe77616%1024
=816.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

28. bmap Algorithm
•The algorithmbmapis used to convert logical byte offset of a file to a physical
disk block:
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

29. Algorithm -bmap
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

30. Directories
•Directoryfileshaveentriesofsubdirectoriesandfilesthatresideinsidethem.
•Directoryfileshavethemappingofafilenameanditsinodenumber.
•Onedirectoryentrytakes16bytes.
•14bytesaregivenforthenameofthefileand2bytesforinodenumber.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

31. Directory layout for /etc
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

32. •Theentry.hastheinodenumberofthethedirectoryfileitself.
•And..hastheinodenumberoftheparentdirectory..and..fortherootdirectory
arenothingbutinodenumbersoftherootdirectoryitself.
•Entriesthathavetheinodenumber0areempty(i.e.deletedfiles).
•Thekernelhasexclusivewritestowritetoadirectory.
•Theaccesspermissionfordirectoriesmeandifferentthings.
•Readpermissionisforreadingthecontentsofthedirectory,writepermission
giventhepermissiontocreatefilesanddirectoriesinthatdirectory,andthe
executepermissiongivestherighttosearchinthatdirectory.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

33. Conversion of Path Name to an Inode
•Algorithmnamei(nametoinode)isusedforconvertingapathtoaninode
number.
•Thekernelparsesthepathbyaccessingeachinodeinthepathandfinally
returningtheinodeoftherequiredfile.
•Everyprocesshasacurrentdirectory.Thecurrentdirectoryofprocess0isthe
rootdirectory.
•Foreveryotherprocess,itisthecurrentdirectoryofitsparentprocess.Laterthe
processcanchangethecurrentdirectorywiththesystemcallchdir.
•Theinodeofthecurrentdirectoryisstoredintheu-area.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

34. •Searchesstartwithrespecttothecurrentdirectoryunlessthepathbeginswith
the/component,statingthatthesearchshouldstartwiththerootdirectory.
•Inodenumberoftherootispresentastheglobalvariable.Evenifthecurrent
rootischangedbyusingchroot(moreonthislater),thecurrentrootinode
numberisstoredintheu-area.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

35. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

36. Algorithmnamei
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

37. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

38. Superblock
•Thecontentsofthesuperblockare:
•sizeofthefilesystem.
•numberoffreeblocksinthefilesystem.
•listoffreeblocksinthefilesystem.
•pointertothenextfreeblockinthefreeblockslist
•sizeoftheinodeslist.
•numberoffreeinodesinthefilesystem.
•listoffreeinodesinthefilesystem.
•pointertothenextfreeinodeinthefreeinodeslist.
•lockfieldsforthefreeblocksandfreeinodeslist.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

39. Superblock cont….
•afieldindicatingwhetherthesuperblockhaschanged.
•Thekernelperiodicallywritesthesuperblocktothediskifithadbeenmodified
sothatitisconsistentwiththedataonthedisk.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

40. Inode Assignment to a New File
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

41. ialloc
•Ifthelistofinodesnumbersinthesuperblockisnotempty,thekernelassigns
thenextinodenumber,allocatesafreein-coreinodeforthenewlyassigneddisk
inodeusingalgorithmiget,copiesthediskinodetothein-corecopy,initializes
thefieldsintheinodeandreturnsthelockedinode.Itupdatestheinodeondisk
toindicatethattheinodeisinuse.
•Ifthesuperblocklistoffreeinodesisempty,thekernelsearchesthediskand
placesasmanyfreeinodenumbersaspossibleintothesuperblock.Thekernel
readstheinodelistondisk,blockbyblock,andfillsthesuperblocklistofinode
numberstocapacity,rememberingthehighest-numberedinodethatitfinds
("remembered"inode).Itisthelastonesavedinthesuperblock.Thenexttime
thekernelsearchesthediskforfreeinodes,itusestherememberedinodeasits
startingpoint,therebyassuringthatitwastesnotimereadingdiskblockswhere
nofreeinodesshouldexist.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

42. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

43. Two Arrays of Free Inode Numbers
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

44. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

45. Algorithm for freeing inodes (ifree)
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

46. •Ifthesuperblockislocked,thealgorithmreturns,theinodenumberisnot
updatedinthefreelistofinodenumbers.
•Buttheinodecanbefoundwhensearchingthediskblocks.Ifthediskblockslist
isfullandtheinodenumberislessthantherememberedinodenumber,the
replacetherememberedinodenumberwiththeinputinodenumber,sothatthe
searchwillstartfromthatinode.
•Ideally,thereshouldneverbefreeinodeswhoseinodenumberislessthanthe
rememberedinodenumber,butexceptionsarepossible.
•Ifaninodeisbeingfreedandthesuperblockislocked,insuchsituation,theitis
possibletohaveaninodenumberthatisfreeandislessthantheremembered
inodenumber.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

47. Placing Free Inode Numbers into Super Block
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

48. Allocation of Disk Blocks
•Whendataiswrittenonafile,thekernelmustallocatediskblocksfromthefile
system(fordirectdatablocksorsometimes,indirectdatablocks).
•Thefilesystemsuperblockcontainsanarraythatisusedtocachethenumbersof
freediskblocksinthefilesystem.
•Theutilityprogrammkfs(makefilesystem)organizesthedatablocksofafile
systeminalinkedlist,suchthateachlinkofthelistisadiskblockthatcontainsan
arrayoffreediskblocknumbers,andonearrayentryisthenumberofthenext
blockofthelinkedlist.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

49. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

50. Linked List of Free Disk Block Numbers
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

51. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

52. Algorithm for allocation of disk blocks (alloc)
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

53. •Theprogrammkfstriestoorganizetheoriginallinkedlistoffreeblocknumberssothat
blocknumbersdispensedtoafileareneareachother.
•Thishelpsperformance,becauseitreducesdiskseektimeandlatencywhenaprocess
readsafilesequentially.
•Thekernelmakesnoattempttosortblocknumbersonthefreelist.
•Thealgorithmfreeforfreeingablockisthereverseoftheoneforallocatingablock.
•Ifthesuperblocklistisnotfull,theblocknumberofthenewlyfreedblockisplacedon
thesuperblocklist.
•If,however,thesuperblocklistisfull,thenewlyfreedblockbecomesalinkblock;the
kernelwritesthesuperblocklistintotheblockandwritestheblocktodisk.
•Itthenplacestheblocknumberofthenewlyfreedblockinthesuperblocklist:That
blocknumberistheonlymemberofthelist.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

54. An example of how the super block free data blocks list works
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

55. •Thereisadifferenceishowfreeinodenumbersaremanagedandhowfreedisk
blocknumbersaremanaged.
•Allthefreediskblocknumbersarestoredasalinkedlistofarraysbutincaseof
freeinodenumbers,allthefreeinodenumbersarenotstored.
•Afterthecapacityofthefreeinodenumbersexceeds,theotherfreeinode
numbersarenotstoredanywhere.
•Thereare3reasonsforthisdifferenttreatment:
•Thekernelcandeterminewhetheraninodeisfreebyinspectingitsfiletype.However,thereisno
waytoknowwhetheradiskblockisfreebylookingatthedatainit.
•Diskblocklendthemselvestotheuseoflinkedlist:adiskblockeasilyholdslargelistsoffree
blocknumbers.Butinodeshavenoconvenientplaceforbulkstorageoflargelistoffreeinode
numbers.
•Userstendtousefreediskblocksmorethanfreeinodes,sotheperformancelaginsearching
wouldbemorenoticeableincaseofdiskblocksthaninodes.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

56. Other File Types
•TheUNIXsystemsupportstwootherfiletypes:pipesandspecialfiles.Apipe,
sometimescalledafifo(first-in-first-out),differsfromaregularfileinthatitsdata
istransient;oncedataisreadfromapipe,itcannotbereadagain.Also,thedata
isreadintheorderthatitwaswrittentothepipe,andthesystemallowsno
deviationfromthatorder.Thekernelstoresdatainapipethesamewayitstores
datainanordinaryfile,exceptthatitusesonlythedirectblocks,nottheindirect
blocks.Pipesaredescribedlater.
•OthertypesinUNIXsystemarespecialfiles,includingblockdevicespecialfiles
andcharacterdevicespecialfiles.Bothtypesspecifydevices,andthereforethe
fileinodesdonotreferenceanydata.Instead,theinodecontainstwonumbers
knownasthemajorandminordevicenumbers.Themajornumberindicatesa
devicetypesuchasterminalordisk,andtheminornumberindicatestheunit
numberofthedevice
•
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon

57. •Thank you …..
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon