Smartphone Operating System (779883), страница 39
Текст из файла (страница 39)
It is, rather, more prudent toplace pieces of a file wherever they may fit and link the pieces togethersomehow so the file-system implementation can put them together whilereading data from the pieces.Working with linked file space requires having access to the linkageinformation. In some systems, the linkage information can be kept withthe file table.
Other systems store link information with each piece of afile on a storage medium. In these cases, the file looks like a linked list,and working through the contents of a file means traversing a linked listfrom front to back.Sometimes a compromise is made between contiguous allocation andlinked allocation. File blocks can be put contiguously together in clustersand the clusters can be strung together to allow flexibility in file growthand allocation.
A cluster is usually a group of disk sectors, which containthe file blocks. The size of a cluster is determined when the file system iscreated and remains constant over that file system.A slight variation on the method of keeping link information in a fileis the indexed approach. In the indexed approach, the address of thefirst pieces of a file is stored in the file table.
The address on the storagemedium of each piece of a file is stored in the file table as an index, anaddress relative to the base address of the file. Sometimes, if the file islarge, the index entries are stored as the first file block on the storagemedium and the entry in the FCB points to this block.We must deal with fragmentation issues when we split the storage into fixed-size blocks. All the above schemes suffer from internal182FILE SYSTEMS AND STORAGEfragmentation: files are seldom exactly the size that fits into a specificnumber of fixed blocks.
There is usually space within a block that iswasted. External fragmentation is the space wasted outside the collection of blocks. If a fixed-block scheme is used, external fragmentation iseliminated as the storage medium is carved up into blocks that fit exactly.From time to time, it is a good idea to defragment storage media.Defragmenting has nothing to do with internal or external fragmentation;it is focused on the wide dispersion of the blocks belonging to filecontent across a storage medium. The closer a file’s blocks are, the lessmechanical wear occurs from trying to move all over a medium to readthe blocks.
Defragmentation moves the blocks of all files so that they areas close to each other as possible, hopefully adjacent to one another.Free space and bad blocksIn addition to file content, there are two other types of blocks on astorage medium. Free space is space available for allocation to files andis made available when files are deleted.
Because of block-allocationpatterns, free space comes available in blocks that are scattered all overthe medium. These blocks must be accessible when space is needed andtherefore are usually linked together using the same methods used to linkfile blocks together. Contiguous or linked methods apply to free blocksas well.Occasionally, a block ‘goes bad’ – becomes damaged in some wayso that it is unusable. A bad block can simply be avoided on a storagemedium. As with file blocks and free space, bad blocks are usually linkedtogether so they can be found and avoided.FAT and VFAT File SystemsWhen Microsoft developed the first operating system to run on IBMhardware, it needed to invent a file system for the computer’s hard drives.In 1977, the FAT file system debuted on IBM PCs using the MicrosoftDisk Basic system.
This first file system – called the FAT file system forits use of a file-allocation table – is still in use, in more evolved forms, inmodern versions of Microsoft Windows. The FAT file system is also usefor most mobile media storage (for example, compact flash or multimediacards).The initial version of the FAT file system is called FAT12. This firstversion was very simple and restricted: no support for hierarchical directories, disk addresses were 12 bits long and the disk size was stored asIMPLEMENTATION OF A FILE SYSTEM183a 16-bit count of disk sectors, which limited the size to 32 MB.
Themaximum size of a partition was 32 MB.The release of MS-DOS 2.0 occurred at the beginning of 1983.This version of FAT12 introduced hierarchical directories. The use ofdirectories allowed FAT12 to store many more files on the hard disk,as the maximum number of files was no longer constrained by the rootdirectory size. This number could now be equal to the number of clusters(or even greater, using zero-sized files).
The format of the FAT itself didnot change. The 10 MB hard disk on the PC XT had 4 KB clusters. If a20 MB hard disk was later installed and formatted with MS-DOS 2.0, theresultant cluster size would be 8 KB, the boundary at 15.9 MB.In 1988, with the release of MS-DOS 4.0, the FAT16 file system wasfinalized. In this file system, the disk address was now 16 bits and themaximum partition size jumped to 2 GB. The maximum cluster size in aFAT16 file system is 32 KB.FAT12 and FAT16 file systems had what is known as the 8.3 limitation.Filenames on the system were limited to eight characters with a threecharacter suffix.
A variant of the FAT16 file system allowed longerfilenames to be used. This variant was known as the VFAT file systemafter the Microsoft Windows 95 VxD device driver.The FAT32 file system was introduced in 1996 and is still in usetoday. The FAT32 file system uses 32 bits for disk addressing and forclusters. Only 28 of the 32 bits are used to address clusters, but even thisallows for 228 clusters, which allows FAT32 to support media sizes up to2 TB.
Unfortunately, limitations in other Microsoft utilities mean that thefile-allocation table is not allowed to grow beyond 222 clusters, whichsupports media sizes up to 124 GB. Because of the 32-bit disk address,files can grow to a maximum size of 4 GB. Also the long filenames fromVFAT were implemented.Each of the FAT file-system variants shares common characteristics.They are implemented using a file-allocation table with file pieces puttogether using a linked list of clusters.
There is one file-allocationtable per disk volume. The FAT has a common structure, illustratedby Figure 8.4.Boot sectorOptional extraboot sectorspaceFigure 8.4FileallocationtableDuplicatefileallocationtableRoot filedirectoryThe generic format of a FAT file systemFile blockstorage184FILE SYSTEMS AND STORAGEThe first section of the FAT is known as the boot sector. This section ofthe file system contains the operating system’s boot-loader implementation. This is the place that the computer goes to retrieve code that bootsthe operating system.
In some implementations, this is code that initializesthe system for operating system execution. In others, the operating systemcode is stored elsewhere on the disk and the boot sector only contains anaddress where this code can be found.There is a section of this format that is made up of optional reservedsectors. This section of the file system is usually used by extensionsof the basic boot-sector format. Other versions of the operating systemthat expand upon Microsoft Windows but are compatible with it usethis optional section for an expanded boot sector. The boot sector forMicrosoft Windows NT is bigger than that for FAT16, for instance, butsince it uses this optional section, the rest of the format can be the same.The next two areas are identical copies of the file-allocation table forthe partition.
These tables are maps of the file-block storage areas of thestorage medium. They contain one table entry per disk block and eachentry holds the address of the next disk block of the file. This chain isstarted by a directory entry, which indexes filenames and the blocks theystart at. The chain is terminated with a special end-of-file value. Freeblocks have a 0 value in the table.
File-allocation tables also use specialvalues to indicate bad or reserved clusters.The next area was used by FAT12 and FAT16 file systems and containedthe root directory, used as starting point for all traversals through the filesystem. In FAT32, this directory was located on the disk and an addressto it was stored in the FAT.Finally, the rest of the storage medium is used for file block storage.Blocks are simply laid next to each other and adjacent blocks couldeasily be from different files. The only way to connect blocks is throughthe FAT.Let’s take an example.
A user wants to open a file and read the first1000 bytes from a file called \book\readme.txt. If we were using aFAT16 file system, we would start our journey by accessing the rootdirectory, which is stored in the boot sector, and we would look upthe directory name book. This entry would have the block number inthe block-storage region of the disk. We would read that block andassume it contained directory information.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
