CS620 New York University Assignment 8 Inodes Questions

Question Description

EX: 7.(2) Suppose the inode number of a file is 100005. How does the OS know where this inode is stored on disk? What data structures are accessed by the OS to compute the inode’s location on disk.

8.(10) Suppose that an inode is 256 bytes, pointers are 10 bytes long, and the status information takes up 56 bytes. Assume a block size of 4000 bytes.

    • How much room is there for direct pointers in the inode?

(b)How big a file can be represented with direct pointers?

(c)How big a file can be represented with single Indirect pointers?

(d)How big a file can be represented with Double Indirect pointers?

(e)How big a file can be represented with Triple Indirect pointers?

Unformatted Attachment Preview

CS 620 Assignment 8 12/2/2019 Due date 12/9/2019 Instructions: 1. You can either hand in a hard-copy in class or you can electronically submit the assignment. 2. Electronic submission: You assignment is due by 9:00 AM, 12/9/2019. Type in the following command from your agate account. ∼cs620/submit 8 hw8.pdf . 8 is the assignment number. Note that if you want to resubmit, then you need to use 8a, 8b, 8c, for assignment number (not 8). 3. Hard-copy submission: You assignment is due in class on 12/9/2019. 4. Late assignments will not be graded. 5. The relevant reading material is from Chapter 9: 9.1-9.6; 9.9 and file systems/storage systems 6. Show all work. If you just write down an answer without explanation, you will get no credit. 1. (4) Assume we have a demand-paged memory. The page table is held in registers. It takes 10 milliseconds to service a page fault if the replaced page is not modified, and 25 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds. Assume that the page to be replaced is modified 60 percent of the time. If the page fault rate is 1%, what is the effective page access time? 2. (8) For the following reference string: < A, E, F, B, C, E, B, B, F, D, A, F, F, F, B > How many page hits would occur with the Working set model and the FIFO page replacement algorithm when MM has (a) four frames and window size of three; (b) three frames and window size of three. All frames are initially empty, so your first unique pages will all cost one fault each. Show both the working set and the replacement queue (stack) when each page is accessed. 3. (16) Consider the following page reference string: < A, B, C, D, A, F, C, D, B, C, G, F, B, A, B > How many page hits would occur for the following replacement algorithms, assuming that MM has four frames? All frames are initially empty, so your first unique pages will all cost one fault each. Show the replacement queue (or MM frames) at every access. 1 (a) Least Recently Used (LRU). (b) Not Used Recently (NUR)/Second Chance. Assume that after pages A, B, C, D are loaded, the pointer is at A and the reference bit for each page is set to 1. (c) Most Recently Used (MRU). (d) Optimum replacement (OPT). 4. (3) What is Belady’s anomaly? Why does FIFO display this anomaly? 5. (4) Give an example of a specific page reference string and a specific memory size where the page fault ratio of using FIFO is smaller than for LRU, or argue that no such example can exist. 6. Compaction is the process by which fragmentation in file systems is removed. In compaction, files are all written contiguously and a large hole remains. Performance improves since reading a file requires a single seek and a single rotation followed by the transfer at full speed. Writing the file back requires the same work. Assume a seek time of 10ms, a rotational delay of 4ms, a transfer rate of 5MB/sec and an average file size of 10KB, Suppose the file system is fragmented, so compaction is started. (a) (3) How long does it take to read a file into main memory prior to compaction? Assume that prior to compaction, each file, on average, is fragmented into 5 portions (i.e., 5 portions of the file are randomly distributed on the disk, but the data within each portion are contiguous.) (b) (3) How long does it take to write the file contiguously into a new location. (Note that a file has to be read before it can be written contiguously to a new location.) (c) (2) Using these numbers, how long would it take to compact a 10GB disk? (d) (1) By what percentage does the performance of reading a file improve after compaction? 7. (2) Suppose the inode number of a file is 100005. How does the OS know where this inode is stored on disk? What data structures are accessed by the OS to compute the inode’s location on disk. 8. (10) Suppose that an inode is 256 bytes, pointers are 10 bytes long, and the status information takes up 56 bytes. Assume a block size of 4000 bytes. (a) How much room is there for direct pointers in the inode? (b) How big a file can be represented with direct pointers? (c) How big a file can be represented with single Indirect pointers? (d) How big a file can be represented with Double Indirect pointers? (e) How big a file can be represented with Triple Indirect pointers? 2 9. Suppose a file currently consists of 10 blocks. Assume that the file control block (i.e., inode) is already in memory. Assume that there are free disk blocks available after block 10 of the file. Each block read or write takes 1 disk 1/O operation. Calculate how many disk I/O operations are required for contiguous allocation scheme if a new block is (a) (3) inserted in the middle (i.e., after block 5) of the file. (b) (3) inserted at the end of the file (i.e., after block 10) of the file. 10. (4) Solve the above problem with the linked allocation scheme. 11. (4) Solve the above problem with the indexed allocation scheme. Assume that the index block is already loaded in MM. 3 …
Purchase answer to see full attachment