File Structure - I/O SYSTEMS

1.File Structure

· All disk I/O is performed in units of one block (physical record) size which will exactly match the length of the desired logical record.

· Logical records may even vary in length. Packing a number of logical records into physical blocks is a common solution to this problem.

· For example, the UNIX operating system defines all files to be simply a stream of bytes. Each byte is individually addressable by its offset from the beginning (or end) of the file. In this case, the logical records are 1 byte. The file system automatically packs and unpacks bytes into physical disk blocks – say, 512 bytes per block – as necessary.

· The logical record size, physical block size, and packing technique determine how many logical records are in each physical block. The packing can be done either by the user’s application program or by the operating system.

2.Directory Structure

There are five directory structures. They are

1. Single-level directory

2. Two-level directory

3. Tree-Structured directory

4. Acyclic Graph directory

5. General Graph directory

3.Allocation Methods

· The main problem is how to allocate space to these files so that disk space is utilized effectively and files can be accessed quickly .

· There are there major methods of allocating disk space:

1. Contiguous Allocation

2. Linked Allocation www.Vidyarthiplus.com

3. Indexed Allocation

1. Contiguous Allocation

· The contiguous – allocation method requires each file to occupy a set of contiguous blocks on the disk.

2. Linked Allocation

· Linked allocation solves all problems of contiguous allocation.

· With linked allocation, each file is a linked list of disk blocks, the disk blocks may be scattered anywhere on the disk.

· Each block contains a pointer to the next block. These pointers are not made available to the user.

· There is no external fragmentation with linked allocation, and any free block on the free space list can be used to satisfy a request.

· The size of a file does not need to the declared when that file is created. A file can continue to grow as long as free blocks are available consequently, it is never necessary to compacts disk space.

3. Indexed Allocation

· Linked allocation solves the external – fragmentation and size- declaration problems of contiguous allocation.

· Linked allocation cannot support efficient direct access since the pointers to the blocks are scattered with the blocks themselves all over the disk and need to be retrieved in order.

· Indexed allocation solves this problem by bringing all the pointers together into one location: the index block.

· Each file has its own index block, which is an array of disk – block addresses.

· The ith entry in the index block points to the ith block of the file.

· The directory contains the address of the index block .

· To read the ith block, we use the pointer in the ith index – block entry to find and read the desired block this scheme is similar to the paging scheme .

4.Free-space Management

· Since disk space is limited, we need to reuse the space from deleted files for new files, if possible.

· To keep track of free disk space, the system maintains a free-space list.

· The free-space list records all free disk blocks – those not allocated to some file or directory.

· To create a file, we search the free-space list for the required amount of space and allocate that space to the new file.

· This space is then removed from the free-space list.

· When a file is deleted, its disk space is added to the free-space list.

5.Disk scheduling:

One of the responsibilities of the operating system is to use the hardware efficiently.

For the disk drives,

1. A fast access time and

2. High disk bandwidth.

· The access time has two major components;

· The seek time is the time for the disk arm to move the heads to the cylinder containing the desired sector.

· The rotational latency is the additional time waiting for the disk to rotate the desired sector to the disk head. www.Vidyarthiplus.com

· The disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.

FCFS Scheduling

SSTF (shortest-seek-time-first)Scheduling

SCAN Scheduling

C-SCAN Scheduling

LOOK Scheduling