Operating System Gate Previous Year Question

Which of the following CPU scheduling algorithm can potential cause starvation?

a) FCFS
b) SJF
c) Priority scheduling
d) Round Robin

Consider a computer system with 57 bit virtual address using multilevel page tables with L levels for virtual to physical address translation. The page size is 4 KB and page table entry at any of the levels occupy 8 bytes. What is the value of L?

Which one or more of the following option guarantee that a computer system transit from user mode to kernel mode

a) Page fault
b) System call
c) Malloc call
d) Function call

Which one of more of the following need to be saved on context switch form one thread (T1) of a process to another thread (T2) of the same process?

a) Program counter
b) Stack pointer
c) General purpose register
d) Page table base register

Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

a) P=4, Q=10, R=6, S=2
b) P=2, Q=9, R=5, S=1
c) P=4, Q=12, R=5, S=4
d) P=3, Q=7, R=7, S=3

Which of the following statements is/are TRUE with respect to deadlocks?

a) Circular wait is a necessary condition for the formation of deadlock.
b) In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
c) If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
d) In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Consider a demand paging system with four-page frames (initially empty) and an LRU page replacement policy. For the following page reference string 7, 2,7,3, 2,5,3, 4,6,7,7,1,5,6,1 the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.

A cache memory that has a hit rate of 0.8 has an access latency 10 ns and miss penalty 100 ns. Optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _____.

Consider the following five disk five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.

a) T is serviced before P.
b) Q is serviced after S, but before T.
c) The head reverses its direction of movement between servicing of Q and P.
d) R is serviced before P.

Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

CODE SECTION P
wait(a); count=count+1;
if (count==n) signal (b);
signal (a): wait (b) ; signal (b);
CODE SECTION Q

What does the code achieve ?

a) It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
b) It ensures that two processes are in CODE SECTION Q at any time.
c) It ensures that all processes execute CODE SECTION P mutually exclusively.
d) It ensures that at most n−1 processes are in CODE SECTION P at any time.

Consider the following statements about process state transitions for a system using preemptive scheduling.

I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.
Which of the above statements are TRUE ?

a) I, II, and III only
b) II and III only
c) I, II, and IV only
d) I, II, III and IV only

Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statement is TRUE ?

a) The hole created by first fit is always larger than the hole created by next fit.
b) The hole created by worst fit is always larger than the hole created by first fit.
c) The hole created by best fit is never larger than the hole created by first fit.
d) The hole created by next fit is never larger than the hole created by best fit.

Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ___________ .

A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60 MHz clock. To service a cache-miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is _________ × 10⁶ bytes/sec.

The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointer The disk block size is 4 kB and the disk block addresses 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) __________ GB.

The following C program is executed on a Unix / Linux system:
 

Consider the following snapshot of a system running n concurrent processes. Process i is holding X_i instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R arecurrently in use. Further, for all i, process i can place a request for at most Y_i additional instances of R while holding the X_t instances it already has. Of the n processes, there are exactly two processes p and q such that Y_p = Y_q = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?

a) X_p + X_q < Min {Y_k ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}
b) X_p + X_q < Min {Y_k ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}
c) Min (X_p , X_q ) ≤ Max {Y_k ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}
d) Min (X_p , X_q ) ≤ Max {Y_k ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8k Band the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

a) 16 x 2¹⁰
b) 8 x 2²⁰
c) 4 x 2²⁰
d) 256 x 2¹⁰

Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time: [120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3], [56, 116, 2], [118, 16, 1] Currently head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible. The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is ______

The size of the physical address space of a processor is 2^P bytes. The word length is 2^W bytes. The capacity of cache memory is 2^N bytes. The size of each cache block is 2^M words. For a K-way set-associative cache memory, the length (in number of bits) of the tag field is

a) P − N − log₂K
b) P − N + log₂K
c) P − N − M − W − log₂K
d) P − N − M − W + log₂K

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimental measured that the average time taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?

a) ^{(D - M)}/_{(X - M)}

b) ^{(X - M)}/_{(D - M)}

c) ^{(D - X)}/_{(D - M)}

d) ^{(X - M)}/_{(D - X)}

The read access times and the hit ratios for different caches in a memory hierarchy are as given below:

A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for 3 processes are shown below:

a) Safe, Deadlocked
b) Safe, Not Deadlocked
c) Not Safe, Deadlocked
d) Not Safe, Not Deadlocked

Which of the following is/are shared by all the threads in a process?

I. Program Counter
II. Stack
III. Address space
IV. Registers

a) III only
b) IV only
c) I and II only
d) III and IV only

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:

Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of allocated frames increases. Now consider the following statements:

a) S1 is true, S2 is true
b) S1 is true, S2 is false
c) S1 is false , S2 is true
d) S1 is false, S2 is false

A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

a) x = 1, y = 2
b) x = 2, y = 1
c) x = 2, y = 2
d) x = 1, y = 1

Threads of a process share

a) global variables but not heap
b) heap but not global variables.
c) neither global variables nor heap.
d) both heap and global variables.

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ________.

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first.

Consider the following two-process synchronization solution.

Process 0
---------
Entry: loop while (turn == 1);
(critical section)
Exit: turn = 1;

Process 1
----------
Entry: loop while (turn == 0);
(critical section)
Exit: turn = 0;

The shared variable turn is initialized to zero. Which one of the following is TRUE?

a) This is a correct two-process synchronization solution.
b) This solution violates mutual exclusion requirement.
c) This solution violates progress requirement.
d) This solution violates bounded wait requirement.

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

a) LRU (Least Recently Used)
b) OPT (Optimal Page Replacement)
c) MRU (Most Recently Used)
d) FIFO (First In First Out)

Consider a computer system with ten physical page frames. The system is provided with an access sequence a₁, a₂, ..., a₂₀, a₁, a₂, ..., a₂₀), where each ai number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is __________

Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63, moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is______

Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is _________megabytes.

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

a) Shortest remaining time first
b) Round-robin with time quantum less than the shortest CPU burst
c) Uniform random
d) Highest priority first with priority proportional to CPU burst length

The maximum number of processes that can be in Ready state for a computer system with n CPUs is

a) n
b) n²
c) 2n
d) Independent of n

Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution) is _________ tracks

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

Which one of the following statements is FALSE?

a) The TLB performs an associative search in parallel on all its valid entries using the page number of the incoming virtual addresses.
b) If the virtual address of a word given by the CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory
c) The memory access time using a given inverted page table is always the same for all incoming virtual addresses.
d) In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.