File Systems
Operating Systems Lab Class 10&11
In this lab session (and the following one) you will write a program that implements the basic i-node based file system.
Disk Space Management Methods
Operating system maintains a list of free disk space to keep track of all disk blocks which are not being used by any file. Whenever a file has to be created, the list of free disk space is searched for and then allocated to the new file. The amount of space allocated to this file is then removed from the free space list. When a file is deleted, its disk space is added to the free space list. But the problem is how to allocate space to files for effective disk space utilisation and quick access. There are three major methods of storing files on disks: contiguous, linked, and indexed, as shown in Figure 1.
Figure 1: Disk Space Management Methods
UNIX i-nodes
The inode block numbers work in a group of 13, which can be explained as follows (see Figure 2),
1. The first 10 (A0-A9) point directly to a data block which contain the actual file data – this is called direct addressing = 10 KB (1 KB each).
2. Then the 11th block (A10) points to a data block that contains 256 pointers, each of those pointers point to a single address block as above. This is called single indirect block addressing = 256 x 1 KB = 256 KB .
3. The 12th block points to a data block that has 256 pointers and each of those pointers point to a data block with 256 pointers, and each of those pointers to a data block as per point 1 above. This is called double indirect block addressing = 256 x 256 x 1 KB = 64 Mb.
1
4. The 13th point has a triple indirect setup where the 256 pointers each point to 256 pointers that each point to 256 pointers that each point to a data block as per point 1 above = 256 x 256 x 256 x 1 KB = 16 GB.
So the max size is actually 16 GB, but this is limited by the inode sizing not by the structure of the operating system.
Figure 2: Datablock addressing in the inode The file system has the following layout (see the example in Appendix 1):
1 Getting Started
1. Download the os-lab10.zip archive from Canvas and unzip into your workspace.
2. Start NetBeans and open the project. The project should contain six files in the src directory: BasicFSMain.java (contains the main method), FileSystem.java, Volume.java, SuperBlock.java, Inode.java and Util.java.
3. Before you begin, read through the code and then compile it before making any modifications. This should work without problems.
2 Implementation
The class Volume implements a partition on a disk and is entirely given. the file Util.java contains auxiliary functions for (de)serialising integers into/from byte arrays.
1. The class SuperBlock implements the superblock (block 0) of the filesystem that contains important information such as block size and a bitmap to manage free blocks. Your task is to implement three methods for finding a free block, freeing a block and computing the number of free blocks.
2. The class Inode implements an i-node data structure. Your task is to implement methods for writing the data structure into the block and parsing it from a block. Note that the SIZE of the i-node may be smaller than the block size. The pos parameter gives you the position within the block where the i-node starts. Moreover, you are asked to implemented a method that computes the number of blocks used by that file.
3. The class FileSystem shall implement five file system functions:
• format() formats the volume by writing an appropriate superblock. A sufficient number of
blocks following the superblock must be allocated to hold the i-nodes.
• mount() mounts the volume by loading the superblock and i-nodes into main memory.
• unmount() unmounts the volume.
• create() creates a new file by adding an i-node and allocating an appropriate number of
blocks.
• delete() deletes a file by removing the i-node.
The code provided already contains print functions that dump the content of the data structures to the terminal when you run the program.
4. Last but not least, we implement the main program. The program takes the size of the volume followed by a sequence of commands that you are going to interpret and run. Running
java BasicFSMain 7 f 4 4 m c 18 c 5 d 0 u
• args[0]=7: the size of the volume is 27 = 128 bytes.
• args[1]=’f’: indicates that the format command should be executed with the following two
parameters:
• args[2]=4: block size 24 = 16 bytes and
• args[3]=4: maximum number of i-nodes 4.
• args[4]=’m’: executes the mount command next.
• args[5]=’c’: executes the create command with the following parameter
• args[6]=18: file size 18 bytes.
• args[7]=’c’: executes the create command with the following parameter
• args[8]=5: file size 5 bytes.
• args[9]=’d’: executes the delete command with the following parameter
• args[10]=0: i-number 0.
• args[11]=’u’: executes the unmount command.
This means that we have a 128 bytes volume that we will format with a file system that uses 16-bytes blocks. We reserve space for 4 i-nodes. Then we mount the volume and create two files. At last, we delete the first file we created (which will have i-number 0), and unmount the volume.
The appendix shows the output of running the program with these arguments.
3 Reflection
Look at the bitwidths of the datatypes used in the program and the restrictions defined in the usage() message. Explain which elements cause the following limitations.
5. What is the maximum 6. What is the maximum 7. What is the maximum 8. What is the maximum 9. What is the maximum
4 References
https://goo.gl/lWMCWi
size of a volume that we allow? size of a block?
number of i-nodes?
number of blocks per i-nodes? file size?
Appendix 1
Appendix 2
Call Util.testUtil() to run some examples that explain the Util class methods: toBinaryString, shortToByteArray, shortFromByteArray, longToByteArray and longFromByteArray.
*************************************************
|| testUtil ||
/**
* byte: the byte data type is an 8-bit signed two’s complement integer. It
* has a minimum value of -128 and a maximum value of 127 (inclusive).
* short: the short data type is a 16-bit signed two’s complement integer.
* int: the int data type is a 32-bit signed two’s complement integer.
* long: the long data type is a 64-bit two’s complement integer.
*/
(byte) (200) = -56
(byte) (255) = -1
(byte) (512) = 0
(1023 >> 8) = 3 // 1023 = 00000011 11111111
toBinaryString(7, 8)= 00000111
shortToByteArray(array, 4, 1023)
// (byte) 1023 = (byte) [00000011 11111111] = [(byte) 3 (byte) 255 ]= [3 -1]
0 0 0 0 3 -1 0 0 0 0 0 0 0 0 0 0
shortFromByteArray(array, 4)= 1023
longToByteArray(array2, 4, 13110592)
// 13110592 = 00000000 00000000 00000000 00000000 00000000 11001000 00001101 01000000
0 0 0 0 0 0 0 0 0 -56 13 64 0 0 0 0
longFromByteArray(array2, 4)= 13110592
*************************************************
Appendix 1 Cont…
Runningjava BasicFSMain 7 f 4 4 m c 18 c 5 d 0 ugives: Volume created with size 128
Format volume with blockSize 16 and max. 4 inodes
————
| SuperBlock |
————
block size: 16
number of blocks: 8
number of inodes: 4
next free inode: 0
number of free blocks: 5
free blocks bitmap: 0000000000000000000000000000000000000000000000000000000000000111
Write block 0 successful
————
| Volume |
————
block 0
00010000 (0)
00001000 (1)
00000100 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000111 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 1
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 2
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 3
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 4
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 5
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 6
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 7
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
Volume formatted successfully with blockSize 16 and max. 4 inodes
Mount volume
Read block 0 successful
————
| SuperBlock |
————
block size: 16
number of blocks: 8
number of inodes: 4
next free inode: 0
number of free blocks: 5
free blocks bitmap: 0000000000000000000000000000000000000000000000000000000000000111
Read block 1 successful
————
| Inode 0 |
————
file size: 0
blocks used: 0
direct block[0]: 0
direct block[1]: 0
direct block[2]: 0
direct block[3]: 0
direct block[4]: 0
direct block[5]: 0
————
| Inode 1 |
————
file size: 0
blocks used: 0
direct block[0]: 0
direct block[1]: 0
direct block[2]: 0
direct block[3]: 0
direct block[4]: 0
direct block[5]: 0
Read block 2 successful
————
| Inode 0 |
————
file size: 0
blocks used: 0
direct block[0]: 0
direct block[1]: 0
direct block[2]: 0
direct block[3]: 0
direct block[4]: 0
direct block[5]: 0
————
| Inode 1 |
————
file size: 0
blocks used: 0
direct block[0]: 0
direct block[1]: 0
direct block[2]: 0
direct block[3]: 0
direct block[4]: 0
direct block[5]: 0
Volume mounted successfully
Create file with file size 18
————
| Inode 0 |
————
file size: 18
blocks used: 2
direct block[0]: 3
direct block[1]: 4
direct block[2]: 0
direct block[3]: 0
direct block[4]: 0
direct block[5]: 0
Write block 1 successful
Write block 0 successful
————
| SuperBlock |
————
block size: 16
number of blocks: 8
number of inodes: 4
next free inode: 1
number of free blocks: 3
free blocks bitmap:
————
| Volume |
————
block 0
00010000 (0)
00001000 (1)
00000100 (2)
00000001 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00011111 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 1
00000011 (0)
00000100 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
0000000000000000000000000000000000000000000000000000000000011111
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 2
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 3
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 4
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 5
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 6
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 7
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
File created with i-number 0
Create file with file size 5
————
| Inode 1 |
————
file size: 5
blocks used: 1
direct block[0]: 5
direct block[1]: 0
direct block[2]: 0
direct block[3]: 0
direct block[4]: 0
direct block[5]: 0
Write block 1 successful
Write block 0 successful
————
| SuperBlock |
————
block size: 16
number of blocks: 8
number of inodes: 4
next free inode: 2
number of free blocks: 2
free blocks bitmap:
————
| Volume |
————
block 0
00010000 (0)
00001000 (1)
00000100 (2)
00000010 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00111111 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 1
00000011 (0)
00000100 (1)
00000000 (2)
0000000000000000000000000000000000000000000000000000000000111111
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000101 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 2
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 3
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 4
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 5
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 6
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 7
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
File created with i-number 1
Delete file with i-number 0
————
| SuperBlock |
————
block size: 16
number of blocks: 8
number of inodes: 4
next free inode: 0
number of free blocks: 4
free blocks bitmap: 0000000000000000000000000000000000000000000000000000000000100111
Write block 0 successful
————
| Volume |
————
block 0
00010000 (0)
00001000 (1)
00000100 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00100111 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 1
00000011 (0)
00000100 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000101 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 2
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 3
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 4
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 5
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 6
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
block 7
00000000 (0)
00000000 (1)
00000000 (2)
00000000 (3)
00000000 (4)
00000000 (5)
00000000 (6)
00000000 (7)
00000000 (8)
00000000 (9)
00000000 (10)
00000000 (11)
00000000 (12)
00000000 (13)
00000000 (14)
00000000 (15)
File deleted with i-number 0
Unmount volume
Volume unmounted successfully