Suppose a process wish to open a file named test.txt. So it issues a system call requesting Operating system to find the file on disk,and to grab the handle of file to operate on it. My question is how does the operating system actually locates file on disk(Particularly sequence of actions the operating system performs to do this)? How partitions,file systems,directory structures used to accomplish this? (If possible kindly explain with an example)
I'll outline a fictional simplified filesystem for you. There are a few more details, but they are not needed to understand what's going on.
The operating system uses a module called a filesystem.
The filesystem is software that knows how the disk is organized.
It talks to the disk-driver which is software that tells the disk to read of write a particular sector on the disk.
The top down structure goes like this:
string s = ReadTextFileIntoString('c:\documents\test.txt'); //Translates to the following calls. Disk = GotoDisk('c:'); //The root directory is always at sector 512. Dir = Disk.ReadDirectoryFromDisk(512); Sector = Dir.SearchForFileName('documents'); if (Sector = -1) then StopWithError; Dir2 = Disk.ReadDirectoryFromDisk(Sector); Sector = Dir2.SearchForFileName('test.txt'); if Sector = -1 then StopWithError; File = Disk.GetFile(Sector); s = File.ReadToString; /see above.
A disk is made up of sectors, The first sector is 0 and the last is sector how ever many sectors there are on the disk. Say 1.999.999.999 for a 1 terabyte disk. Every sector is 512 bytes large. There are no missing numbers or gaps.
The very first sector, sector 0 holds the master boot record. Which is a small program in 512 bytes that starts up the operating system.
This tiny program knows how to read a sector from the disk and little else.
The disk driver is software that knows how to read and write a sector. That's it.
It has two methods.
ReadSector(sectornumber: integer, Buffer: 512bytes); WriteSector(sectornumber: integer, Buffer: 512bytes);
Above the disk driver sits the filesystem,
It knows about:
- File Allocation Table - FAT
A directory is a text file with the following structure:
filename1.1024.characters filesize starting-sector DirectoryYN filename2....
As you can see we know where a file starts. The directory tells us.
But a sector is only 512 bytes. How do we know where the rest of the file is?
Files on disks are not continuous so if the first sector is 5 the rest of the file need not be on sectors 6,7,8 etc. In fact they can be anywhere at all.
To solve this problem there is the FAT The File allocation table.
This is structure to tell which sectors belong to a file.
It looks like this:
0 2 3 3 8 10 -1 -1 -1 -1
Every entry corresponds to a sector.
The 1 first entry is sector 0 (we start counting at 0 in computing).
The second entry is sector 1 etc.
Inside the entry is a reference to the next sector.
If a file has no next sector the entry references itself.
The first entry (in our fictional example) is the boot sector, which is a file 512 bytes long. It has no next sector, so the next sector is itself: 0. The second entry is the FAT itself. It is a little larger, so it starts at sector 1->2->3->3 the entry for sector 3 points to itself, so there the file ends.
This is how the filesystem knows how to locate a file.
It knows where the file starts and it uses a little table to see where the different sectors after the first are located.
For those sectors that are empty it works the same way, but negative numbers are used. All the writer has to do is locate negative numbers in the file allocation table and write data into those sectors, then update the relevant entries in the FAT and the file is stored.
Note that there are two pieces of information stored a single entry in the table.
The first the the number of the entry, this corresponds with the sector, second it the data inside that entry, this corresponds with where the next sector in the chain is, or whether that sector is free.
An entry in the directory can be another directory (which is really a text file) or a normal file.
The filesystem will load one directory at a time, until it finds the entry for the file, then it will do whatever is requested (read, write, delete).