CS314 Operating System Spring 2018 Exercise Questions on March 15th, 2018 EXERCI

Question

CS314 Operating System Spring 2018 Exercise Questions on March 15th, 2018 EXERCISE #1 Compare the contiguous, linked-list, and index storage-space (sectors) allocation methods for the following three performance metrics: speed, reliability, and storage-space utilization. Contiguous Linked-List Index Speed (read an entire file) Reliability Space Utilization Note 1: Compare the three methods by: "best"', "almost best", "2nd best", and "worst" Note 2: It is possible for more than one method to have the same ranking EXERCISE #2 the overhead of reading an existing data bock, using the number of the necessary disk Estimate accesses, in a file using the contiguous, linked-list, and index allocation methods for the following cases: Contiguous Linked-List Index lst sector N-th sector Use the following assumptions: (1) One data block is the same size of a hard drive sector. (2) Reading a sector requires the OS one disk access. (3) The index has been loaded to the memory (4) The directory of the target file has been loaded to the memory (no disk (no disk access needed for accessing the index). access needed for target sector from the 1st accessing the file directory). (5) For contiguous allocation, the OS can "spot"("calculate) the sector of a target file.

Explanation / Answer

EXERCISE 1:   

Speed(read an entire file):

i) contiguous allocation: Best

It is very fast. Because no. of block accesses are very less. 1 access per file. Because we can directly access next blocks by using direct addressing.

ii) Linked allocation: Worst

Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.

iii) Indexed allocation: Best

This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.

Reliability

i) contiguous allocation: Best

All blocks of file are continuous. We will store first block address. Missing that block among some many will have very less probability.

ii) Linked allocation: Worst

Links may break at any time. Once they broke, there is no way to get to the link.

iii) Indexed allocation: Best

same as contiguous case.

Space utilization:

i) contiguous allocation: Worst

It suffers from internal and external fragmentation. It is not easy to find contiguous memory blocks for a file to allocate. Those are holes.

ii) Linked allocation: Best

This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.

iii) Indexed allocation: Best

Same as linked allocation.

EXERCISE 2:   

1st Sector:

i) contiguous allocation: Best

Overhead is acceptable. It will store first block address only, which is necessarily needed.

ii) Linked allocation: Best

Same as contiguous allocation.

iii) Indexed allocation: Best

Same as contiguous allocation. It will store index block address.

Nth Sector:

i) contiguous allocation: Best

No overhead here to access Nth sector.

ii) Linked allocation: Worst

We cannot directly access Nth sector or block. We need atleast N accesses. It is all overhead.

iii) Indexed allocation: Best

Same as contiguous allocation. It will store Nth block address as well.

Thumbs up, please :)

Thanks

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.