​

Module V

FILE SYSTEM

OBCA104

Presented by

Latharani T R

Assistant Professor

Dept. of Computer Science and Engineering

Jain Institute of Technology

Davanagere.

​

​

1

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

Introduction

File Concepts

• A file is a named collection of related information on secondary-storage.
• Commonly, file represents
• program and
• data.
• Data in file may be
• numeric
• alphabetic or
• binary.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

2

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

File Types

Four types of file

• Text File
• Source file
• Object file
• Executable file

​

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

3

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

1. Text file:
1. Simplest kind of file.
2. Non-executable, digital file having only text (letters, digits and symbols)
3. In the human readable form.
4. Identifies with the .txt file extension

​

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

4

2) Source file:

• Human-readable version of a computer program like, C or Java or Python.
• Sequence of subroutines & functions.
• They are then used as an input to compile or interpreter which translates the code into machine-readable instructions that can be executed by a computer.
• Identifies with the extensions .py, .c, .java etc.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

5

3) Object file:

• Sequence of bytes organized into blocks
• Intermediate form between source and executable.
• Generated after compiling or assembling the source code.
• Object file is the intermediate form between source and executable.
• Identifies with the .obj extension

​

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

6

4) Executable file:

• Holds a program that is ready to execute in the machine understandable form. .
• Series of code sections generated after linking a set of object files together using a linker.
• Identifies with the .exe extension

​

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

7

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

8

File Attributes

1) Name: The only information kept in human-readable form.

2) Identifier: It is a unique number which identifies the file within file-system.

It is in non-human-readable form.

3) Type: It is used to identify different types of files.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

9

• Location: It is a pointer to
• Device and
• Location of file.
• Size:
• Current-size of file in terms of bytes, words, or blocks.
• It also includes maximum allowed size.
• Protection
• Access-control info. determines who can do
• reading
• writing and
• executing

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

10

Time, date, & user identification

• These information can be kept for
• Creation
• Last modification and
• last use.
• These data can be useful for
• Protection
• Security and
• Usage monitoring.
• Information about files are kept in the directory-structure, which is maintained on the disk

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

11

File Operations

1) Creating a file

• Two steps are:

i) Find the space in the file-system for the file.

ii) An entry for the new file is made in the directory.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

12

2) Writing a file

• Make a system-call specifying both
• File-name and
• Info. to be written to the file.
• The system searches the directory to find the file's location.
• The system keeps a writepointer(wp) to the location in the file where the next write is to take place.
• The write-pointer must be updated whenever a write-operation occurs.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

13

3) Reading a file

• Make a system-call specifying both
• File-name and
• Location of the next block of the file in the memory.
• The system searches the directory to find the file's location.
• The system keeps a readpointer(rp) to the location in the file where the next read is to take place.
• The read-pointer must be updated whenever a read-operation occurs.
• Same pointer (rp & wp) is used for both read- & write-operations. This results in
• Saving space and
• Reducing system-complexity

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

14

4) Repositioning within a file

• Two steps are:
• Search the directory for the appropriate entry.
• Set the current-file-position to a given value.
• This file-operation is also known as file seek.

5) Deleting a file

• Two steps are:
• Search the directory for the named-file.
• Release all file-space and erase the directory-entry

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

15

6) Truncating a file

• The contents of a file are erased but its attributes remain unchanged.
• Only file-length attribute is set to zero

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

16

• The OS keeps a small table which contains info. about all open files (called open-file table).
• If a file-operation is requested, then
• File is specified via an index into open-file table
• So no searching is required.
• If the file is no longer actively used, then
• Process closes the file and
• OS removes its entry in the open-file table

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

17

• Two levels of internal tables:
• Per-process Table
• Tracks all files that a process had opened.
• Includes access-rights to
• File and
• Accounting information
• Each entry in the table in turn points to a system-wide table

2) System-wide Table

• Contains process-independent information, such as
• file-location on the disk
• file-size and
• access-dates

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

18

• Information associated with an open file:

1) File-pointer

• Used by the system to keep track of last read-write location.

2) File-open Count

• The counter
• Tracks the no. of opens & closes and
• Reaches zero on the last close

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

19

3) Disk Location of the File

• Location-info is kept in memory to avoid having to read it from disk for each operation.

4) Access Rights

• Each process opens a file in an access-mode (read, write or execute).

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

20

File Types

• Common technique for implementing file-types:
• Include the type as part of the file-name.
• Two parts of file-name

1) Name and

2) Extension (.doc, .txt, .exe etc.)

• The system uses the extension to indicate
• Type of file and
• Type of operations (read or write).

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

21

File Structure

• File types can be used to indicate the internal structure of the file.
• Disadvantage of supporting multiple file structures: Large size.
• All OSs must support at least one structure: an executable file

• Too few structures make programming inconvenient.

• Too many structures make programmer confusion.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

22

Internal File Structure

• Locating an offset within a file can be complicated for the OS.
• Disk-systems typically have a well-defined block-size.
• All disk I/0 is performed in units of one block (physical record), and all blocks are the same size

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

23

• Problem: It is unlikely that physical-record size will exactly match length of desired logical-record.
• Solution: Packing a number of logical-records into physical-blocks.
• Following things determine how many logical-records are in each physical-block:
• Logical-record size
• Physical-block size and
• Packing technique

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

24

• The packing can be done either by
• User's application program or
• OS.
• Disadvantage of packing:
• All file-systems suffer from internal fragmentation
• The larger the block size, the greater the internal fragmentation.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

25

Access Methods �

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

26

Sequential Access

• This is based on a tape model of a file.
• This works both on
• Sequential-access devices and
• Random-access devices.
• Information in the file is processed in order
• For ex: editors and compilers

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

27

File-operations

1) Read next

• This is used to
• Read the next portion of the file and
• Advance a file-pointer, which tracks the I/O location.

2) Write next

• This is used to
• Append to the end of the file and
• Advance to the new end of file

3) Rewind

• Read the previous contents

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

28

Sequential-access file

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

29

Direct Access (Random/Relative Access)

• A file is made up of fixed length logical records.
• Programs can read and write records rapidly in no particular order.
• Jump to any record and read that record.
• Operations supported include:
• Read n - read record number n.
• Write n - write record number n.
• Jump to record n - could be 0 or the end of file.
• Query current record - used to return back to this record later.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

30

Simulation of sequential access on a direct-access file.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

31

​

• Sequential access can be easily emulated using direct access.
• The inverse is complicated and inefficient.

�

Other Access Methods

• These methods generally involve constructing a file-index.
• The index contains pointers to the various blocks (like an index in a book).
• To find a record in the file.
• First, search the index and
• Then, use the pointer to
• Access the file directly and
• Find the desired record.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

32

Example of index and relative files

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

33

Problem: With large files, the index-file itself may become too large to be kept in memory. Solution: Create an index for the index-file.

Directory Structure�

Storage Structure

• A disk can be used in its entirety for a file system.
• Physical disk can be broken up into multiple partitions, slices, or mini-disks.
• Each of which becomes a virtual disk and can have its own filesystem.
• Or, multiple physical disks can be combined into one volume.
• i.e. a larger virtual disk, with its own filesystem spanning the physical disks.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

34

A typical file-system organization��

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

35

Directory Overview

• Directory operations to be supported include:
• Search for a file
• Create a file - add to the directory
• Delete a file - erase from the directory
• List a directory - possibly ordered in different ways.
• Rename a file - may change sorting order
• Traverse the file system.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

36

Single-Level Directory

• Simple to implement, but each file must have a unique name.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

37

• All files are contained in the same directory.

Disadvantages (Limitations):

1) Naming problem: All files must have unique names.

2) Grouping problem: Difficult to remember names of all files, as number of files increases.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

38

Two-Level Directory

• Each user gets their own directory space (UFD).
• File names only need to be unique within a given user's directory.
• A master file directory(MFD) is used to keep track of each users directory.
• Must be maintained when users are added to or removed from the system.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

39

• Efficient searching
• No filename-collision among different users.

Disadvantage

• Grouping Problem

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

40

Two-level directory structure

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

41

Tree-Structured Directories

• A tree is the most common directory-structure.
• The tree has a root directory.
• Every file in the system has a unique path-name.
• Each user / process has the concept of a current directory from which all ( relative ) searches take place.
• Files may be accessed using either
• Absolute pathnames ( relative to the root of the tree ) or
• Relative pathnames ( relative to the current directory. )

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

42

Tree-structured directory structure

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

43

• To delete an empty directory:
• → Just delete the directory.
• 2) To delete a non-empty directory:
• First, delete all files in the directory.
• If any subdirectories exist, this procedure must be applied recursively to them.

Advantage:

1) Users can be allowed to access the files of other users.

Disadvantages:

1) A path to a file can be longer than a path in a two-level directory.

2) Prohibits the sharing of files (or directories).

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

44

Acyclic-Graph Directories�

• Useful when same files need to be accessed by more than one user / process in more than one place in the directory structure.
• UNIX provides two types of links for  ) implementing the acyclic-graph structure.
• A hard link 
• A symbolic link
• Windows only supports symbolic links, termed shortcuts.
• Hard links require a reference count, or link count for each file to keep track of no. of directory entries currently referring to this file.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

45

Acyclic-graph directory structure

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

46

• The directories can share subdirectories and files
• An acyclic graph means a graph with no cycles.
• The same file (or subdirectory) may be in 2 different directories.
• Only one shared-file exists.
• Changes made by one person are immediately visible to the other.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

47

Two problems:

1) A file may have multiple absolute path-names.

2) Deletion may leave dangling-pointers to the non-existent file.

Solution to deletion problem:

1. Use backpointers: Preserve the file until all references to it are deleted.
2. With symbolic links, remove only the link, not the file. If the file itself is deleted, the link can be removed.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

48

General Graph Directory

Problem:

• If there are cycles, we want to avoid searching components twice.

Solution:

Limit the no. of directories accessed in a search.

Problem:

With cycles, the reference-count may be non-zero even when it is no longer possible to refer to a directory (or file).

• A value of 0 in the reference count means that there are no more references to the file or directory, and the file can be deleted.

Solution: Garbage-collection scheme can be used to determine when the last reference has been deleted.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

49

General Graph Directory

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

50

• Garbage collection involves

1) First pass

• Traverses the entire file-system and
• Marks everything that can be accessed.

2) A second pass

Collects everything that is not marked onto a list of free-space

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

51

File System Structure

• Disks provide the bulk of secondary-storage on which a file-system is maintained.
• It is a suitable medium for storing multiple files because

1) A disk can be rewritten in place.

• It is possible to read, write or modify a block on the disk.

2) A disk can access directly any block of information.

• Either sequentially or randomly.
• Switching from one file to another requires only moving the read-write heads and waiting for the disk to rotate.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

52

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

53

• To improve I/O efficiency, I/O transfers between memory and disk are performed in units of blocks.
• Each block has one or more sectors.
• Depending on the disk drive, sector-size varies from 32 bytes to 4096 bytes.
• The usual size is 512 bytes.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

54

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

55

• File-systems provide efficient and convenient access to the disk by allowing data to be stored, located, and retrieved easily
• Design problems of file-systems:
• 1) Defining how the file-system should look to the user.
• 2) Creating algorithms & data-structures to map the logical file-system onto the physical secondary-storage devices

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

56

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

57

Advantages of layered structure:

1) Duplication of code is minimized.

2) I/O control can be used by multiple file-systems.

Allocation Methods

• Many files are stored on the same disk.
• Main problem: How to allocate space to the files so that
• disk-space is utilized effectively and
• files can be accessed quickly.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

58

• Three methods of allocating disk-space:
• 1) Contiguous
• 2) Linked and
• 3) Indexed
• Each method has advantages and disadvantages.
• Some systems support all three.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

59

Contiguous allocation

• Requires that each file occupy a set of contiguous blocks on the device.
• Accessing a file that has been allocated contiguously is easy.
• One difficulty is finding space for a new file.
• Determining how much space is needed for a file is difficult.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

60

Contiguous allocation of disk space

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

61

• If we allocate too little space to a file, we may find that the file cannot be extended.
• Even if the total space needed is known in advance, pre-allocation may be inefficient.
• This method suffers from both internal and external fragmentation.
• To minimize these drawbacks, can use a modified contiguous-allocation scheme.
• Here, a contiguous chunk of space is allocated initially.
• If that amount is not large enough, another chunk of contiguous space, known as an extent, is added.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

62

Linked allocation

• Solves all problems of contiguous allocation. With linked allocation,
• Each file is a linked list of storage blocks.
• Blocks may be scattered anywhere on the device.
• The directory contains a pointer to the first and last blocks of the file.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

63

Linked allocation of disk space.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

64

• To create a new file, just create a new entry in the directory
• Each directory-entry has a pointer to the disk-block of the file).

1) A write to the file causes a free block to be found,then written and linked to the eof (end of file).

2) A read to the file causes moving the pointers from block to block.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

65

Advantages

1. No external fragmentation
2. Any free block on the free-space list can be used to satisfy a request.
3. The size of the file doesn't need to be declared on creation.
4. Not necessary to compact disk-space

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

66

Disadvantages:

1) Can be used effectively only for sequential-access files.

2) Space required for the pointers.

• Solution: Collect blocks into multiples (called „clusters‟) & allocate clusters rather than blocks.

3) Reliability: Problem occurs if a pointer is lost( or damaged).

• Partial solutions:

i) Use doubly linked-lists.

ii) Store file name and relative block-number in each block.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

67

FAT (File Allocation Table)

• FAT is a variation on linked allocation.
• FAT has an entry for each disk block.
• Rather than blocks, FAT entries are linked.
• Example: MS-DOS and OS/2

Advantages:

• Save disk block space
• Faster direct access

Disadvantage:

• A significant number of disk head seeks.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

68

Indexed Allocation 

• Solves the problems of linked allocation (without a FAT) by bringing all the pointers together into an index block.
• Special block known as the Index block contains the pointers to all the blocks occupied by a file.
• Each file has its own index block. 
• It overcomes the problem of external fragmentation.

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

69

Indexed allocation of disk space

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

70

Disadvantages:

1) Suffer from wasted space

2) The pointer overhead of the index block is generally greater than the pointer overhead of linked allocation.

3) Suffer from performance problems.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

71

Free-Space Management

• Critical aspect of operating systems.
• Involves managing the available storage space on the hard disk or other secondary storage devices.
• When a new file is created, space need to be allocated for it by finding free space.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

72

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

73

Methods

The OS uses various techniques to manage free space and optimize the use of storage devices.

Bit Vector

• Free space is implemented using bit vector.
• Each block is represented by 1 bit
• 1 indicates free
• 0 indicates allocated

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

74

0 0 0

0 1 1

1 0 0

0 0 0

0 1 1

0

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

75

BIT VECTOR

Advantages

• Simple implementation
• Easy to find first free block
• Easy to find n consecutive free blocks

Disadvantages

• Entire vector is to be kept in main memory - not possible for larger disks.
• Bit vector need to be updated, as and when a block becomes free.
• The entire vector is written to disc occasionally for recovery

​

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

76

Linked List

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

77

Linked List

• Link all free blocks
• Point the pointer to first free block in disk

Disadvantage

• Traversal is laborious

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

78

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

79

Grouping

• Store addresses of n free blocks in the first free block
• First n-1 blocks are free while n^th block contains addresses of another set of n free blocks

Advantage:

• 1) Addresses of a large no of free blocks can be found quickly

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

80

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

81

Counting

1. Stores the address of the first free disk block and a number n of free contiguous disk blocks that follow the first block.
2. Every entry in the list would contain:
1. Address of first free disk block
2. A number n

Advantage:

• Easy to locate group of free blocks.

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

82

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

83

5

2

14

1

Counting list entry

​

Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davanagere

84