Notice: Exam Form BE IV/II & BAR V/II (Back) for 2076 Magh
Routine: BE IV/II & BAR V/II - 2076 Magh
Result: BCE I/II exam held on 2076 Bhadra
Result: All (except BCE & BEI) I/II exam held on 2076 Bhadra
Notice: Exam Center for Barrier Exam (2076 Poush), 1st Part
View All
View Old Questions
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All
View Syllabus
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All

Notes of Operating System [CT 656]

File Systems

File Naming: Structure, Type, Access, Attribute and Operation

Files are the units to store information on external storage media that satisfies the following requirements.
a) It must store large volume of information.
b) It must be process independent i.e termination of process using the file should not affect the existence of information within it.
c) Multiple processes must be able to access information within it at the same instant of time.

The part of OS dealing with files, its structure, naming, implementation, security and so on is called file system

File Naming

- On creation of a file by any process, it provides a name.
- When process terminates, the file continues to exist.
- The rules for file naming caries from system to system.
- Generally, files are named with two parts separated by a period sign: filename and extension.
- Extension indicates some information about the file
- For eg: file. c
Here, the filename is ‘file’ and extension is ‘c’. The extension indicates that the file is a C file which can be compiled by C compiler.

File Structure

- File can be structured as byte sequence, record sequence and tree.
- In byte sequence, file is an unstructured sequence of bytes. The OS only sees bytes and the meaning should be provided by user level programs.
- In record sequence, a file is a sequence of fixed length records, each with same internal structure.
- In tree a file consists of a tree of records, may be of varying length, each containing key field in fixed position in the record. The key field is used for sorting tree.


File Types

- Regular files contain user information and data bytes.
- Regular files may be ASC II/ text file or binary file.
- ASCII files consist of lines of text, each line terminated by carriage return or line feed. Each line may have variable length. These files are easy to edit and display.
- Binary files usually have some internal structure with sections: header, text, data, relocation bits and symbol table for executable file, and header, object module for archive file.

File Access

- Sequential access: a process reads file starting at the beginning without skipping around.
- Random access: a process reads file out of order by key. The staring position can be specified using READ operation or SEEK position

File Attributes

- The additional information except filename and its data associated with each file is known as file attributes.
- The attributes varies form system to system.
- Protection, password, creator, owner, flags (hidden. Read only, archive, ASCII / binary, random access, lock), record length, key length, creation time. Time of last access, current size, maximum size, etc.

File Operations

- Different operation are used to allow storage and retrieval of information.

Directory and File Paths

- Directory is the structure in file system that keeps track of the files.
- A directory contains a number of entries, one per file


- The number of directories varies from system to system.
- When file system is organized as a directory tree, a way is needed to specify file names. The way is by is by specifying path name for each file.
- Each file is given an absolute path name consisting of the path form root directory to the file
Eg: /user/ ast/ mailbox
- If first character of path name is separator, It is absolute,
- Relative path name is the path for the file beginning from the current working directory
- Eg: if current directory is /user/ast, then relative path can be mailbox.

- The operations allowed for managing directories are: -

- Linking is the technique that allows a file to appear in more than one directory.

File System Implementation - Block Size Selection and its Impact

File System Layout

File system are stored on disks. The disks are separated into partitions. The sector 0 is Master Boot Record (MBR), used to boot the computer. BIOS reads in and executes MBR, MBR locates the active partition, reads in the boot block and execute. The boot block reads in the OS contained in the partition. The superblock contains key parameters about a file system.

A possible file system layout is shown in figure below: -


Selecting Block Size

- Data are accessed as fixed size block.
- Each block is of fixed size in which files are stored.
- The block size should neither be low nor large.
- Having large block size amy result in single file with many blocks causing high seek time and rotational delay.

Impact of block size selection

- Higher block size indicates higher data rate
- Higher block size indicates lower space utilization
- Eg: consider a disk with 32768 bytes per track, totation time of 16.67 ms and average seek time of 30ms. - For block size of K bytes’ time to read a block is:
30+16.67+(K/32768) * 16.67


Keeping Track of Blocks of Each file

- Consecutive blocks
# Problem when file grows
- Linked list
# Slow random access

File Implementation (File Allocation Technique)

It is the mechanism of keeping track of which disk blocks go which files

Contiguous Allocation

- Store each file as a contiguous block of data on the disk.
- Disk address is assigned in liner order.
- It is easy to implement.
- The entire file can be read from disk in a single operation.
- It is not feasible if maximum file size is unknown during creation
- It may result in disk fragmentation.


Linked Listed Allocation

- Store each file as a linked list of disk blocks.
- The first word of each block is used as a pointer to next one and the rest of the block is for data.
- Space is not last to disk fragmentation except for internal fragmentation.
- The directory entry can store disk address of first lock only.
- Random access is very slow.
- Extra overhead while copying due to a pointer at the head of block.


Linked List Allocation Using on Index

- File allocation table (FAT) keeps track of pointers as a table in memory.
- A table has one entry for each disk block with all file blocks linked together.
- The directory, stores the first block number of each file.
- The entire block is available for data.
- Random access is easier.
- The entire table must be in memory all the time.
- Growth of table size is liner with grow of disk size.


I – nodes

- Each file is associated with a table called index-nodes (i-node) which lists the attributes and disk addresses of the file’s blocks.
- Directory contains addresses of index blocks of files.
- Keep data structure in memory only for active files.
- Solves the growth problem.
- Each i-node is of fixed size.


Directory Implementation

Directory specifies block address by providing
a) Address of first block
b) No. of first block
c) No. pf i-node

Mapping File Blocks on Disk Platter (Free Disk Space Management)

Files are stored in disk. Whenever a file needs space for allocation, it is necessary to know which blocks on the disk are necessary. For this purpose, the OS maintains disk allocation table (DAT) to keep track of a list of free disk spaces. Whenever a file is created, the list of free disks is searched and then allocated. Then, the space allocated is removed from free space list, then a file is deleted, its space is added to free space list

Linked Free Space List

- All the free blocks are linked together using a linked list of disk blocks, each holding max. number of for free blocks that can fit.
- Free blocks are used to store free list.
- During allocation, the OS allocate the first block in free space list.
- No disk fragmentation.
- Must read each block that waste time.
- Pointer used also consume disk space.

Eg: consider a 20M disk with of size 1k.
Here, the block number is of 16-bits and blocks is 20k hence, total blocks needed to hold all block number is:
= 16 & 20000 bits
=320000 bits
= 40000 bytes
= 40 k
= 40 blocks
Each block can hold 500 block numbers.


Bitmap or Bit Vector

- Every block is represented by a single bit. ‘1’ is marked as free block while ‘o’ as allocated block.
- A disk with n blocks requires bitmap with n bits.
- It requires less space.
- Simple and efficient
- May require hardware support to do bit operation.

Eg. For above example:
Total blocks needed is:
= 1 * 20000 bits
= 2000bits
= 2500 byte
= 2.5 k
= 3 blocks

File System Performance

- Because of seek time and latency time, disk access is slower than memory access.
- Disk performance is worst than memory performance.
- Disk performance can be improved by:
a) Block caching
b) Block read ahead
c) Reduce disk arm motion.



Sponsored Ads