Suppose we have a file that needs to be moved to a different place on the disk (
ID: 3772762 • Letter: S
Question
Suppose we have a file that needs to be moved to a different place on the disk (that happens to be non-fragmented). For each of the allocation methods: Contiguous, Linked, and Indexed answer the following questions: What structures need to be changed to that we can accurately find all of the blocks of the file in the new location (For example, suppose right after the moving, we want to access a block that is exactly halfway through the file.) What needs to be updated to make sure we access it correctly, and not the block halfway through the old file locationExplanation / Answer
The structures to be changed so that we can accurately find all blocks of the file are:
1)Contiguous: For this we will use arrays as elements are stored in contigous memory locations.
Contiguous Allocationrequires that all blocks of a file be kept together contiguously.
Performance is very fast, because reading successive blocks of the same file generally requires no movement of the disk heads, or at most one small step to the next adjacent cylinder.
Storage allocation involves for the allocation of contiguous blocks of memory ( first fit, best fit, fragmentation problems, etc. ) The distinction is that the high time penalty required for moving the disk heads from spot to spot may now justify the benefits of keeping files contiguously when possible.
2)Linked: we will used a linked list to find the blocks of the file.
Disk files can be stored as linked lists, with the expense of the storage space consumed by each link. ( E.g. a block may be 508 bytes instead of 512. )
Linked allocation involves no external fragmentation, does not require pre-known file sizes, and allows files to grow dynamically at any time.
Unfortunately linked allocation is only efficient for sequential access files, as random access requires starting at the beginning of the list for each new location access.
3)Indexed: for this we can use arrays or linked list or both of them . we can use a stack to insert nd delete from one end.
Indexed Allocation combines all of the indexes for accessing each file into a common block ( for that file ), as opposed to spreading them all over the disk or storing them in a FAT table.
The following needs to be changed to access them correctly:
1)Contiguous:Extents need to be changed:A variation is to allocate file space in large contiguous chunks, called extents. When a file outgrows its original extent, then an additional one is allocated. ( For example an extent may be the size of a complete track or even cylinder, aligned on an appropriate track or cylinder boundary. ) The high-performance files system Veritas uses extents to optimize performance.
2)Linked:Clusters need to be changed and allocated.Allocating clusters of blocks reduces the space wasted by pointers, at the cost of internal fragmentation.
3)Indexed:change and use a combined scheme:his is the scheme used in UNIX inodes, in which the first 12 or so data block pointers are stored directly in the inode, and then singly, doubly, and triply indirect pointers provide access to more data blocks as needed. ( See below. ) The advantage of this scheme is that for small files ( which many are ), the data blocks are readily accessible ( up to 48K with 4K block sizes ); files up to about 4144K ( using 4K blocks ) are accessible with only a single indirect block ( which can be cached ), and huge files are still accessible using a relatively small number of disk accesses ( larger in theory than can be addressed by a 32-bit address, which is why some systems have moved to 64-bit file pointers. )