Description
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
A B C D A B C D
P0 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.
a) If a physical memory access takes 150 ns, what is the effective access time to
memory (EAT) without TLB?
b) 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?
c) 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 firstlevel table. Offset is 12 bits. Assume each page table entry (any level) is 8
bytes.
a) How many bits in a page table entry are used to store a frame number?
b) 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).
c) 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
2
0x0f0000000000. Assume for this question that stack segment also grows
upward (towards higher addresses).
Q4. Consider the following page reference string of a process.
2 4 1 3 4 6 3 6 1 2 1 5 2 5 4 1 2 4 3
Assume the process has 3 frames that it can use, all empty initially.
a) 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.
b) 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.
a) 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).
b) 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.
a) What is the maximum size of a file that can be stored in this file system?
b) How many second level index blocks are required for a file X of size 8 GB.
c) 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?
