Given a 6gb file identify the number of index level needed when using indirect pointer

inode = 1 pointer to a data block + 1 pointer to indirect block

indirect block = 2 pointers to data blocks

directory = a regular file containing zero or more pairs of integers; the first integer of each pair is a file name and the second is the file's inumber

I have the following question from my professor but I am not understanding certain concepts:

Suppose a multi-level indexing scheme in which each file has 10 direct pointers,1 pointer for single indirection, 1 for double indirection and 1 for tripled indirection. Assume that the pointers are 64 bit and each block is 256 bytes

Each block will include 256/8 = 32 pointers
The superblock(inode) will point to:
10 direct pointers
32 Single indirect
32 * 32 double indirect
32*32*32 Triple Indirect pointers
This = 10+32+1024 = 32678 pointers = 33834 blocks
33834* 256 = 8.7 mb file size

My Question relates to two items. One why are we dividing 256 by 8 to get the number of pointers per block. Two where does 33834 blocks come from? Any help would be appreciated. I have read the textbook and still I do not understand this question.

asked Apr 15, 2017 at 16:22

The 8 is the size of the address. (It assumes 64 bit adresses.)

33834 = 10 + 32 + (32 * 32) + (32 * 32 * 32) as the count of the pointers in the multiple indexing scheme.

answered Apr 15, 2017 at 16:37

Imre PillerImre Piller

1431 silver badge10 bronze badges

3

	UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
CS 537 Spring 2001		A. Arpaci-Dusseau
	Quiz #9: May 2nd -- EOF :)

Name: Solutions

Student ID #: Solutions

Problem 1: Familiar Files (20 points)

Consider a UNIX file system with 12 direct pointers, 1 indirect pointer, 1 double-indirect pointer, and 1 triple-indirect pointer in the i-node. Assume that disk blocks are 8K bytes and that each pointer to a disk block requires 4 bytes.

A)What is the largest possible file that can be supported with this design? Show the expression to get full credit (i.e., you shouldn't calculate the final numeric answer!).

Number of ptrs/block = 8K/4 = 2048

(12 * 8KB) + (2048 * 8KB) + (2048 * 2048 * 8KB) + (2048 * 2048 * 2048 * 8KB)

B) How many disk reads will this file system require to read block 14 of the file named /a? Assume that nothing relevant is in the file-cache (e.g., no i-nodes and no data blocks); you can assume that the root directory contains very few entries (i.e., is one block long). To assure full credit, describe each disk read.

Block 14 of the file will be in the indirect block (there are only 12 direct pointers).

A total of 5 reads are required, as follows:

1 - Read i-node 2 and get the first data pointer
2 - Read the data associated with the root directory; find file "a" and its inode number
3 - Read a's i-node and get the address of the indirect block 
4 - Read the indirect block to get its 2nd pointer (ptr for block 14)
5 - Read block 14

Problem 2: Disk Scheduling (25 Points)

A) Rank the disk scheduling algorithms (FCFS, SSTF, SCAN, and C-SCAN) in terms of their fairness in servicing a continuous stream of disk requests; order them from the most fair to the least fair. Consider a general stream of random disk requests, not a particular workload.

Fairness implies that requests are serviced roughly in the order they enter the system. 

FCFS - services requests in strict order
C-SCAN - after reaching the end of the disk, services requests at the beginning of the disk next,
         which are likely the oldest ones
SCAN - services requests again at the same end of the disk
SSTF - can starve requests that are far away from the current disk head

B) List the order in which the following requests for a given cylinder number will be serviced for each of the different disk scheduling algorithms: 11, 15, 18, 6, 13, 7, 5, and 8. For those algorithms that require assumptions about the initial position of the disk head, assume that the disk head begins at position 9 and is moving in an upwards direction. Also assume that the SCAN and C-SCAN algorithms do not travel to the edge of the disk if there are no requests there.

SSTF: 8,7,6,5,11,13,15,18

SCAN: 11,13,15,18,8,7,6,5

C-SCAN: 11,13,15,18,5,6,7,8

Problem 3: Workloads and FFS (37 Points)

A) Consider modern workloads and access patterns. Circle the word that best completes each sentence.

1.  Most files created by users are ( small / large ).

2.  Most of the file data created by users is allocated to ( small / large ) files.

3.  Within the filesystem, it is important to optimize the bandwidth of 
    ( sequential / random ) access patterns.

B) When is FFS likely to switch to a new cylinder group? Circle ALL that apply.

a.  When allocating a new file.

b.  When allocating the first data block of a file.

c.  After allocating the first 48KB of a file.

d.  When allocating a new directory.

C) How did FFS solve the problem of an unorganized freelist? Circle the ONE best answer.

a.  Periodically reorganizes the free list so that it is sorted.

b.  Inserts each data block in the correct sorted order in the free list
    when the block is freed.

c.  Organizes the free list as a bitmap of free blocks.

d.  Uses a b-tree to point to contiguous regions of free blocks.

D) FFS introduced the concept of a disk fragment (i.e., a partial disk block) to support small files while still maintaining good bandwidth. Given the allocation policy in FFS, which statements are guaranteed to be true when an existing file is extended? Circle ALL that apply.

a.  A file does not span multiple fragments.

b.  A file does not span multiple disk blocks.

c.  A file does not use a partial disk block.

d.  A file does not use more than one partial disk block.

e.  A file does not share a partial disk block with another file.

f.  A file does not use a partial disk block for the middle portion of
    its data.

Problem 4: RAID and LFS (18 Points)

A) Match each RAID level with its primary disadvantage. Each disadvantage should be used only once. Choose the best option for each.

_c_ RAID-0        a.  Wastes disk capacity

_a_ RAID-1        b.  Complicated calculation of data and parity location

_d_ RAID-4        c.  Failure of one disk causes loss of data

_b_ RAID-5        d.  Parity disk is performance bottleneck

B) What is the purpose of the i-node map in LFS? Circle the ONE best answer.

a.  To speed up finding contiguous free disk blocks.

b.  To speed up finding contiguous free i-nodes.

c.  To help locate the position of an i-node on disk.

d.  To help compact i-nodes when the disk becomes full.

How many blocks can an indirect block directly point to?

What is 11th pointer of inode used for?

What is the data size of a file which uses 1 direct data block and 1 indirect block of 1kb file sizes There are total 256 blocks in the system?

What is the size of the bit vector of a 1TB disk with 512 byte blocks for free space management?