File Access & File System & File Allocation Table

File Access & File System & File Allocation Table

1. FileSystem&
Fileallocationtable(FAT)
PREPAREDBY:
DAVESUSHILKUMAR A.
PABARISHASHIKANTC.
PAMBHARVISHALG.

2. FileSystem
Thecollectionofalgorithmsanddatastructures
whichperformthetranslationfromlogicalfile
operations(systemcalls)toactualphysical
storageofinformation.
2

3. WhatDoesaFileSystemDo?
▶Responsibilities
Creating, manipulating, renaming, copying, and removing
files to and from a storage device
Organizing files into common storage units
Called directories
Keeping track of file and directory locations
Assisting users
Relate files and folders to the physical structure of the
storage medium
3

4. ▶Filesusedbyoperatingsystemsandapplications
Word-processing documents
Source code for programs you have written
Music files
Movie files
Spreadsheets
Photos
▶Operating systems use a file folder icon to
represent a directory
4

5. LayeredFileSystem
▶Logical File System
 Maintains file structure via
FCB (file control block)
▶File organization module
Translates logical block to
physical block
▶Basic File system
Converts physical block to disk
parameters (drive 1, cylinder 73, track
2, sector 10 etc)
▶I/O Control
Transfers data between memory and
disk
5

6. PhysicalDiskStructure
▶Parameterstoreadfrom disk:
cylinder(=track)#
platter(=surface)#
sector#
transfersize
Tracks
Sectors
within a
Track
Cluster
6

7. FilesystemUnits
▶Sector –the smallest unit that can be accessed on
a disk (typically 512 bytes)
▶Block(or Cluster) –the smallest unit that can be
allocated to construct a file
▶What’s the actual size of 1 byte file on disk?
takes at least one cluster,
which may consist of 1~8 sectors,
thus 1byte file may require ~4KB disk space.
7

8. Sector~Cluster~Filelayout
8

9. FCB–FileControlBlock
▶Containsfileattributes+blocklocations
Permissions
Dates(create,access,write)
Owner,group,ACL(AccessControlList)
Filesize
Locationoffilecontents
▶UNIXFileSystemI-node
▶FAT/FAT32partof FAT(FileAlloc.Table)
▶NTFSpartofMFT(MasterFileTable)
9

10. FileSystemImplementation
Contiguousallocation
Linkedlistallocation
Linkedlistallocationusinganindex(DOSfileallocationtable-FAT)
10

11. ContiguousAllocation
▶The file is stored as a contiguous block of data
allocated at file creation
(a)Contiguousallocationofdiskspacefor7files
(b)Stateof thediskafterfilesDandE havebeenremoved
11

12. ContiguousAllocation(Cont.)
▶FAT(fileallocationtable)containsfilename,startblock,length
▶Advantages
Simpletoimplement(startblock&lengthisenoughto defineafile)
Fastaccessasblocksfolloweachother
▶Disadvantages
Fragmentation
Re-allocation(compaction)
12

13. LinkedListAllocation
▶Thefileisstoredas alinkedlistofblocks
13

14. LinkedListAllocation(Cont.)
▶Eachblockcontainsapointertothenextblock
▶FAT(fileallocationtable)containsfilename, first blockaddress
▶Advantages
Fragmentationiseliminated
Blocksize isnotapowerof 2becauseofpointerspace
▶Disadvantages
Randomaccessisveryslow as linkshave tobefollowed
14

15. IndexedBlockAllocation
▶Indexedallocation
Eachfile hasits ownindexblock(s)of pointersto itsdatablocks
Logicalview
indextable
15

16. IndexedAllocation(Cont.)
Needindextable
Randomaccess
Dynamicaccesswithoutexternalfragmentation,buthaveoverheadof
indexblock
Mappingfromlogicaltophysicalinafileofmaximumsizeof256K
bytesandblocksizeof512bytes.Weneedonly1blockforindex
table
Q
LA/512
R
Q = displacement into index table R = displacement into block
16

17. IndexedAllocation–Mapping(Cont.)
Mapping from logical to physical in a file of unbounded length
(block size of 512 words)
Linked scheme –Link blocks of index table (no limit on size)
Q
1
LA / (512 x 511)
R
1
Q
1 = block of index table
R
1 is used as follows:
Q
2
R
1 / 512
R
2
Q
2 = displacement into block of index table
R
2 displacement into block of file:
17

18. IndexedAllocation–Mapping(Cont.)
Two-level index (4K blocks could store 1,024 four-byte pointers in outer
index -> 1,048,567 data blocks and file size of up to 4GB)
Q
1
LA/(512x512)
R
1
Q
1=displacementintoouter-index
R
1isusedasfollows:
Q
2
R
1/512
R
2
Q
2=displacementintoblockof indextable
R
2displacementintoblockoffile:
18

19. File Allocation
Table FAT File
SystemFAT File System
•The File Allocation Table (FAT) file system is a simple file system originally designed for
small disks and simple folder structures.
•TheFATfilesystemisnamedforitsmethodoforganization,thefileallocationtable,which
residesatthebeginningofthevolume.
•Toprotectthevolume,twocopiesofthetablearekept,incaseonebecomesdamaged.In
addition,thefileallocationtablesandtherootfoldermustbestoredinafixedlocationsothat
thefilesneededtostartthesystemcanbecorrectlylocated.
•A volume formatted with the FAT file system is allocated into clusters.
•The default cluster size is determined by the size of the volume.
•For the FAT file system, the cluster number must fit in 16 bits and be a power of2.
19

20. •ThewayFATworksisthatitkeepsarecordatthestartofthedriveofall
thefiles,andtopointtothefiles,itpointstotheclustersthatcontainthe
files.
•Themainruleofclustersisthattherecannotbemorethan1fileper
cluster;otherwise,pointingtothatclusterwouldcauseproblems,asit
wouldbepointinganddoingread/writeoperationsontwofilesatonce,
whichwouldcauseWindowstocrash.
•Depending on the size and FAT version of the partition, the cluster size
can vary.
•AlsokeepinmindthatasectionofthepartitionisreservedfortheFAT,
whichistherecordofeachfileandwhereitcanbefound.Thischanges
insizedependingonthesizeofthepartitionandclusters.
HowFATWorks
The FAT Family
▶ FAT12, FAT16, FAT32
12, 16, and 32 are the number of bits
used in the FAT for cluster addresses
20

21. FAT32isaderivativeoftheFileAllocationTable(FAT)
filesystemthatsupportsdriveswithover2GBofstorage.
BecauseFAT32drivescancontainmorethan65,526
clusters,smallerclustersareusedthanonlargeFAT16
drives.Thismethodresultsinmoreefficientspace
allocationontheFAT32drive.
The largest possible file for a FAT32 drive is 4GB minus
2 bytes.
TheFAT32filesystemincludesfourbytespercluster
withinthefileallocationtable.Notethatthehigh4bitsof
the32-bitvaluesintheFAT32fileallocationtableare
reservedandarenotpartoftheclusternumber.
FAT32FileSystem
21

22. CreatingaFAT FileSystem
▶High-level formattingcreatesfilesystemdatastructures
▶Boot sector
▶Clusterallocation
▶FileAllocation Table(FAT)
▶$BitmapintheMasterFile Table(MFT)forNTFS
▶Exactdetailsdependon operatingsystem
▶Root Directory
22

23. EachFATtypehasitslimits; thistabledisplaystheselimits:
FAT type Max Clusters Cluster sizes Max volume size
FAT12 4,086 0.5 to 4KB
16,736,256 bytes
(16MB)
FAT16 65,526 2KB to 32KB
2,147,483,648 bytes
(2GB)
FAT32 268,435,456 4KB to 32KB
8,796,093,022,208 bytes
(8TB)
FATLimitations
23

24. DeletedFileRecovery
AllClusterPointersintheFATaregone!
▶Option 1
Grab the next n-1 consecutive clusters.
Call it the file.
May have allocated or unallocated
clusters from other files.
WinHex uses this option.
▶Option 2
Grab the next n-1 unallocated clusters
using the FAT.
Call it the file.
May have unallocated clusters from
other deleted files.
EnCase uses this option.
•Get the first cluster from the directory entry
•Get size from directory entry
•Calculate the number of clusters allocated
to the file, n.
24

25. 25