Operating Systems Assignment-

Question 1 - There are four processes P1, P2, P3 and P4 that enter the ready queue of a uni-processor system in the order above at the same time. Their service time requirements are listed below, in CPU time units:

a. Show how the processes are scheduled if FCFS scheduling is employed, using the timing diagram format found in our in class examples). What are the waiting times of the four processes in the ready queue? What is the average waiting time?

b. Show how the processes are scheduled if Round Robin scheduling is employed (use a time slice length of 2 time units). What are the waiting times of the four processes in the ready queue (i.e. how long does each process spend in total waiting to run)? What is the average waiting time?

Question 2 - Consider a paged virtual memory system with 32-bit virtual addresses and 1K byte pages. A hierarchical page table structure is to be employed. It is desired to limit the size of each part of the page table to one page. Each page table entry requires 32 bits.

a. How many levels of page tables are required? Explain.

b. What is the size of the page table at each level? Hint: One page table size is smaller.

c. The smaller page size could be used at the top level or the bottom level of the page table hierarchy. Which strategy consumes the least number of pages?

Question 3 - Consider the organization of a UNIX file as represented by the inode. Assume that there are 12 direct block pointers and a singly, doubly, and triply indirect pointer in each inode. Further, assume that the system block size and the disk sector size are both 512 bytes. If the disk block pointer is 4 bytes, then:

a. What is the maximum file size supported by this system? Give your answer as four separate values; the number of bytes that can be accessed directly, the number of bytes accessed using a single indirect reference, double indirect reference, and triple indirect reference.

b. Assuming no information other than that the file inode is already in main memory, how many disk accesses are required to access the byte in position 13,423,956?

Question 4 - A process contains seven virtual pages on disk and is assigned a fixed allocation of three page frames in memory. The following page trace occurs:

3, 2, 4, 3, 4, 2, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 5, 6, 7, 2, 1

a. Show the successive pages residing in the three frames using the LRU replacement policy. Compute the hit ratio in main memory (i.e. the number of page references found in main memory divided by the total number of references). Assume that the frames are initially empty.

b. Repeat part (a) for the FIFO replacement policy.