OS File Systems: Mapping Logical to Physical

Question

There's a homework question I need to answer and I can't make heads or tails of it. I've looked over what I think are the pertinent sections in the book (Operating Systems Concepts 9th edition) a couple of times, and I'm not sure where this comes from.

The Question:

Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions:

a. How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)

b. If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?

The homework is slightly modified (starting at logical block 12, and wanting to access logical block 3 rather than 10 and 4, respectively).

The answers:

Answer: Let Z be the starting file address (block number).

a. Contiguous.

Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.

i. Add X to Z to obtain the physical block number. Y is the displacement into that block.

ii. 1

b. Linked.

Divide the logical physical address by 511 with X and Y the resulting quo-tient and remainder respectively.

i. Chase down the linked list (getting X + 1 blocks). Y + 1 is the displacement into the last physical block.

ii. 4

c.Indexed.

Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.

i. Get the index block into memory. Physical block address is contained in the index block at location X. Y is the displacement into the desired physical block.

ii. 2

I have no idea where these answers come from, and every online resource simply regurgitates these over and over. Can anyone provide a more thorough explanation?

Answer 1

The book in question is pure fecal waste matter. No source creates greater confusion resulting in SO questions than that book. I can see from what you have copied why you are so confused.

As the risk of confusing you further, typically operating systems do physical, logical, and virtual I/O to disks.

For physical I/O you have specify the (ta-ta) physical location of the block on the disk. That's the platter, track, and sector.

In logical I/O the disk is treated as an array of blocks. Each block on the disk has a sequential number. Most disks these days do logical I/O in hardware. Operating systems rarely have to do physical I/O these days.

Virtual I/O is used for file access. Disk virtual I/O is similar to disk logical I/O. The difference is that in virtual I/O the blocks making up a file are treated as an array as opposed to the blocks of the disk.

If you can do logical I/O to a disk you can own the system.

The first bit of confusion from your book is that normally when we are dealing with file systems, we only work in blocks (or block clusters). You question is asking to use byte offsets.

The next bit of added confusion from the book is that it is calling the virtual block of the file a "logical block"

In your first question, you are dealing with contiguous files. In a contiguous file, there will be a simple matching between the virtual blocks of the file and the logical blocks of the disk. If the first (or zeroth) logical block of the file is Z, then the mapping from any virtual block to logical block N is N-Z.

In your contiguous file question, if I want to locate an arbitrary byte at offset B in a file then B DIV 512 is the virtual block containing the byte. B MOD 512 is the offset within the block containing the byte.

Thus the logical block being sought is B DIV 512 + Z.

In part 2, of this question, you want to move from virtual block 10 to virtual block 4. Because you are at logical block 10 + Z and the file is contiguous, block four is accessed by reading logical block 4 + Z. That can be done directly with no intervening

From there, your question descends into the realm of total bovine fecal waste matter.

It appears from the question and answer that the "book" is presuming a linked structure where each block contains 511 bytes of data and one byte consisting of an offset to the next block (something totally unrealistic).

If you want to access the 4th block, you have to read the first block, find the offset to the 2d block, read the second block, ..... find the offset to the 4th block, read the forth block.

Another bit of confusion is that the questions seem to switch between block numbers starting at 0 and block numbers starting at 1. "4" is only correct if blocks are numbered starting at 1. However, the division to get offsets in the rest of the answers presume that block numbering starts at 0.

For the indexed method of file allocation, the "book" apparently presumes the existence of a contiguous index. Again, it presumes that the size of the offsets in the index are one-byte.

Let's assume Z is the starting point of the index. Then the entry for block 4 (numbered 1 to 4) is the byte at block Z + 3 DIV 512 and the offset at 3 MOD 512 (3 = 4 - 1).

To find the block, you have to read the index and read the data block (2 reads).

What you are reading has no relation to reality and I understand why you are confused.