My homework for ComS 352, Extra assignment 11

Assignment-11-anderson.txt

Brian Anderson
Com S 352 - Assignment 11
April 25, 2013
=====================================================================================

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

Block Size: 1024 bytes.
File Information already in memory.
At: block 8, access logical block 4.

Allocation Stragegies
======================
|   Contiguous  |       Blocks Read: 1
+---------------+----------------------------------------+
   | "requires that each file occupy a set of contiguous |
   |  blocks on the disk. Disk addresses define a linear |
   |  ordering on the disk."                             |
   +-----------------------------------------------------+

It can move from 8 to 4 with 1 read. 
From the text book (page 518):
"For any type of access, contiguous allocation requires only one 
 access to get a disk block. Since we can easily keep the initial 
 address of the file in memory, we can calculate immediately the 
 disk address of the ith block (or the next block) and read it directly."

+--------------+
|   Linked     |           Blocks Read: 4
+--------------+------------------------------------------+
"...for direct access, however, an access to the ith block 
 might require i disk reads. This problem indicates why 
 linked allocation should not be used for an application 
 requiring direct access." (text page 518)

The last block was logical block 8, to move back to block 4
(assuming the same file, and doubly linked list), it would take
at most 4 reads. Logical read of pointer to previous block from 8,
same for 7,6,5 and finally it would be at block 4.

+--------------+
|   Indexed    |           Blocks Read: 1
+--------------+------------------------------------------+
"...If the index block is already in memory, then the access 
 can be made directly" (text page 518)

Given the information that it is in memory, then only 1 block
read is needed since the index table is loaded into memory.


=====================================================================================
2. UNIX i-node.

Direct Blocks: 12
Index Blocks:  256 pointers

1. What is the largest size (in the unit of “block”) that a file is allowed to have? 
   (List the formula for computing the largest size is acceptable if you do not show 
   the final result in number.)

    16,842,764 "blocks"
   
             Single      Double       Triple
    Direct   Indirect    Indirect     Indirect
    ------   ---------   ---------    -----------
    12     + 256       + (256*256) + (256*256*256)

2. Suppose the control block is already in main memory but none of other blocks of 
   the file is in the memory, and each I/O access can only read one block. 
   If a user process wants to read the following blocks: 10 and 600. 
   How many I/O accesses are needed in total?
   

+-----------+------------------+
| Block 10  |  1   I/O Access  |
+-----------+------------------+---------------------------------------------
It is contained in the direct block, and because the control block
is already in memory we just need to look up the pointer in the
direct block and do a single read of that data block.

+-----------+------------------+
| Block 600 |  3  I/O Accesses |
+-----------+------------------+---------------------------------------------
Block 600 is located in the double indirect section.
It would require a read of the first level pointer-indexes, then the second 
level of pointers and then finally the data-block.

gistfile1.txt

...