# Operating System |Gate-2013| Previous year question|Set-8 Operating System |Gate-2013|

1. A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3), Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes. What is the size of a page in KB in this computer? [GATE – 2013]

a. 2
b. 4
c. 8
d. 16

2. A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i]=g(a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.

Process X:                         Process Y:

private i;                         private i;

for (i=0; i < n; i++) {            for (i=0; i < n; i++) {

a[i] = f(i);                       EntryY(R, S);

ExitX(R, S);                       b[i]=g(a[i]);

}                                 }

Which one of the following represents the CORRECT implementations of ExitX and EntryY? [GATE – 2013]

a. ExitX(R,S) {
P(R);
V(S);
}
EntryY(R,S) {
P(S);
V(R);
}

b. ExitX(R,S) {
P(S);
V(R);
}
EntryY(R,S) {
V(S);
P(R);
}

c. ExitX(R,S) {
V(R);
P(S);
}
EntryY(R,S) {
V(S);
P(R);
}

d. ExitX(R,S) {
V(R);
V(S);
}
EntryY(R,S) {
P(R);
P(S);
}

1. A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates , Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution? [GATE – 2013]

a. -2
b. -1
c. 1
d. 2

1. Consider a hard disk with 16 recording surfaces (0-15) having 16384 cylinders (0-16383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512 bytes. Data are organized cylinder-wise and the addressing format is <cylinder no., surface no., sector no.>. A file of size 42797 KB is stored in the disk and the starting disk location of the file is <1200, 9, 40>. What is the cylinder number of the last sector of the file, if it is stored in a contiguous manner? [GATE – 2013]

a. 1281
b. 1282
c. 1283
d. 1284

Operating System |Gate-2013|

1. Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d, process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes? [GATE – 2013]

a. X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)
b. X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)
c. X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)
d. X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a

1. A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero? [GATE – 2013]

a. This algorithm is equivalent to the first-come-first-serve algorithm.
b. This algorithm is equivalent to the round-robin algorithm.
c. This algorithm is equivalent to the shortest-job-first algorithm
d. This algorithm is equivalent to the shortest-remaining-time-first algorithm.