CS342 Operating Systems Homework #2

Q1. Suppose we have 4 resource types, A, B, C, D, and 6 processes, P0...P5, in a system. The current Allocation and Maximum Demand matrices are shown below. We have, in total, 15 instances of A, 6 instances of B, 9 instances of C, 10 instances of D. Prove that the current state is safe. If, at this state, a request from P5 (3,2,3,3) is made, should it be granted or not? Prove your answer.

     

Alloc


MaxDemand
P0
ABCD
ABCD
2
0 2
1
9 5 5
5
P1
0
1 1
1
2 2 3
3
P2
4
1 0
2
7 5 4
4
P3
1
0 0
1
3 3 3
2
P4
1
1 0
0
5 2 2
1
P5
1
0 1
1
4 4 4
4



Q2. Assume we have system that is using single-level paging. Assume page table for a process is always in the memory.

If a physical memory access takes 150 ns, what is the effective access time to memory (EAT) without TLB?



Assume we have a TLB used. The TLB search takes 10 ns, no matter it is a hit or miss. If hit rate is 85%, what is the effective access time to memory?



If two level paging would be used, what would be your answer for questions a) and b)?



Q3. Assume a system is using four-level paging, 48-bit virtual addresses and 48-bit physical addresses. A virtual address is divided into five pieces as follows: [9, 9, 9, 9, 12]. That means, the first 9 bits are index to the first-level table. Offset is 12 bits. Assume each page table entry (any level) is 8 bytes.

How many bits in a page table entry are used to store a frame number?
How much memory is consumed by 1st, 2nd, 3rd, and 4th level page tables for a process that has 6 MB of virtual memory used, starting at address 0x000000300000. That means the process has one virtual memory area used, starting at virtual address 0x000000300000 (included), and ending at virtual address 0x0000000900000 (not included). In other words, the range of legal addresses is [0x000000300000, 0x0000000900000).



How much memory is consumed by 1st, 2nd, 3rd, and 4th level page tables for a process that has a code segment of 128 KB at virtual address 0x000001000000, a data segment of 2 GB starting at virtual address 0x000800000000 and a stack segment of 4 MB starting at virtual address












1

 0x0f0000000000. Assume for this question that stack segment also grows upward (towards higher addresses).




Q4. Consider the following page reference string of a process.




2413463612 15254 1243

Assume the process has 3 frames that it can use, all empty initially.




Assume second chance (i.e., clock) algorithm is used as page replacement algorithm. Assume reference bits (R bits) are cleared after every 5 references (i.e., some time between every 5th and 6th reference). Show the memory state (the pages in memory and their R bit values) after each page reference. Also indicate which reference causes a page fault. Assume after a page fault, when the new page is loaded, its R bit is set to 1.



Solve the same question for Optimal algorithm.



Q5. Suppose that a disk drive has 10,000 cylinders, numbered 0 to 9,999. The drive is currently serving a request at cylinder (track) 4500, and the previous request was at cylinder 3900. The queue of pending requests, in FIFO order, is as follows: 5200 2000 9500 4300 1500 5100 9600 4000 4600




Starting from the current head position, what is the total distance (in cylinders/tracks) that the disk arm moves to satisfy all the pending requests for each of the following disk-scheduling algorithms: FCFS, SCAN , SSTF.




Q6. A disk has the following parameters:




Size: 512 GB

RPM: 3600

avg seek time: 4 ms

max transfer rate: 30 MB/s.

Assume block size 4 KB. What is the I/O time to read one random block from this disk? How many such transfers can we complete per second? What is the I/O data rate (i.e., throughput).
Assume we will read 512 blocks (each 4 KB), that are contiguous on the disk, sequentially. How many such transfers can we complete per second? What is the I/O data rate (i.e., throughput).



Q7. Consider a file system that uses inodes to represent files. Disk blocks are 4 KB in size, and a pointer to a disk block requires 8 bytes. Assume in an inode we have 10 direct disk block pointers, one single indirect pointer, one double indirect pointer, and one triple indirect pointer. That means, combined index allocation scheme is used to keep track of the blocks allocated to a file.

What is the maximum size of a file that can be stored in this file system?
How many second level index blocks are required for a file X of size 8 GB.
If nothing, except the inodes, is cached in memory, how many disk block accesses are required to access a byte i) at offset 2^15, ii) at offset 2^23, iii) at offset 2^32 of the file X?
























2