1. Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

(a) Smaller sizes of executable files

(b) Lesser overall page fault rate in the system

(c) Faster program startup

(d) Existing programs need not be re-linked to take advantage of newer versions of libraries

2. A uni-processor computer system only has two processes, both of which alternate 10ms CPU bursts with 90ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?

• First come first served scheduling
• Shortest remaining time first scheduling
• Static priority scheduling with different priorities for the two processes
• Round robin scheduling with a time quantum of 5 ms.

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.

3. Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)

• 1.5 ns
• 2 ns
• 3 ns
• 4 ns

4. Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address OxO0400000, and a stack page starting at virtual address 0xFFFFF000. The amount of memory required for storing the page tables of this process is

• 8 KB
• 12 KB
• 16 KB
• 20 KB

THE FOLLOWING INFORMATION TO Q. 80-81

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P: Process Q:

while (1) { while (1) {

W: Y:

print '0’; print '1'

print '0'; print '1'

X: z:

} }

Synchronization statements can be inserted only at points W, X, Y and Z

5. Which of the following will always lead to an output staring with '001100110011' ?

• P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
• P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially I, and T initially 0
• p(S) at W, V(T) at X, p(T) at Y, V(S) at Z, S and T initially 1
• P(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S initially 1, and T initially 0

6. Which of the following will ensure that the output string never contains a substring of the form 0.1"0 or 10"1 where n is odd?

• p(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S and T initially 1
• P(S) at W, V(T) at X, p(T) at Y, V(S) at Z, Sand T initially 1
• P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
• V(S) at W, V(T) at X, P(S) at Y, P(T) at Z,S and T initially 1

7. The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?

(a) 172.57.88.62 and 172.56.87.233

(b) 10.35.28.2 and 10.35.29.4

(c) 191.203.31.87 and 191.234.31.88

(d) 128.8.129.43 and 128.8.161.55

8. A 2km long broadcast LAN has 10 7 bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2 x 10 8 m/s. What is the minimum packet size that can be used on this network?

• 50 bytes
• 100 bytes
• 200 bytes
• None of the above

9. Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 m s. Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 m S. What is the maximum achievable throughput in this communication?

(a) 7.69 x 10 6 bps (b) 11.11 x 10 6 bps

(c) 12.33 x 10 6 bps (d) 15.00 x 10 6 bps

10. Consider the following functional dependencies in a database:

Date _ of _ Birth ® Age Age ® Eligibility

Name ® Roll _number Roll _number ® Name

Course _number ® Course _name Course _ number ® Instructor

(Roll_ number, Course _number) ® Grade

The relation (Roll _ number, Name, Date_of_birth, Age) is

(a) in second normal form but not in third normal form

(b) in third normal form but not in BCNF

(c) in BCNF

(d) in none of the above

11. Consider the set of relations shown below and the SQL query that follows:

Students: (Roll _ number, Name, Date _ of _birth)

Courses: (Course _ number, Course _name, Instructor)

Grades: (Roll _ number, Course _ number, Grade)

select distinct Name

from Students, Courses, Grades

where Students. Roll _number = Grades. Roll _number

and Courses. Instructor = Korth

and Courses. Course _number = Grades. Course _number

and Grades. grade = A

Which of the following sets is computed by the above query ?

(a) Names of students who have got an A grade in all courses taught by Korth

(b) Names of students who have got an A grade in all courses

(c) Name of students who have got an A grade in at least one of the courses taught by

Korth

(d) None of the above

12. Consider three data items D1, D2, and D3, and the following execution schedule

of transactions T1, T2, and T3. In the diagram, R(D) and W(D) denote the actions

reading and writing the data item D respectively.

  T1 T2 T3

R (D3);

R (D2);

W (D2);

R (D2);

R (D3);

Time R(D1);

W(Dl);

W(D2);

W(D3);

R(Dl);

R(D2);

W(D2);

W(Dl);

• The schedule is serializable as T2; T3; T1
• The schedule is serializable as T2; T1; T3
• The schedule is serializable as T3; T2; T1
• The schedule is not serializable

13. In the following C program fragment, j, k n and TwoLog_n are integer variables, and A is an array of integers. The variable n is intialized to an integer ³ 3, and TwoLog _n is initialized to the value of2* é iog 2(n) ù

for (k = 3; k < = n; k++)

A [k} = 0;

for (k=2; k <= TwoLog_n; k++)

for (j=k + 1; j <= n; j++)

A [j] = A (j] || (j%k);

for (j=3; j <= n; j++)

if (!A[j]) print f ("%d ",j);

The set of numbers printed by this program fragment is

(a) {m | m £ n, ( $ i) [m = i!]} (b) {m | m £ n, ( $ i) [m = i 2]}

(c) {m I m £ n, m is prime} (d) {}

14. Consider the C program shown below.

# include <stdio.h>

#define print (x) print f ("%d", x)

intx;

void Q (int z) {

z + = x; print (z);

}

void p (int *y) {

int x = *y+2;

Q (x); *y = x-1;

print (x)

}

main (void) {

x=5;

p (&x);

print (x);

}

The output of this program is

• 1276
• 22 12 11
• 14 6 6
• 766

15. Consider the function f defined below.

struct item {

int data;

struct item * next;

};

int, f(struct item *p) {

return ((p = = NULL) | | (p - > next = = NULL) ||

(( P-> data < = p - > next - > data) &&

f (p - > next)));

}

For a given linked list p, the function f returns 1 if and only if

• the list is empty or has exactly one element
• the elements in the list are sorted in non-decreasing order of data value
• the elements in the list are sorted in non-increasing order of data value
• not all elements in the list have the same data value.