Descriptive

Question 1

(a) The following table refers to search times for a key in B-trees and B+-trees.

A successful search means that the key exists in the database and unsuccessful means that it is not present in the database. Each of the entries X1, X2, X3 and X4 can have a value of either Constant or Variable. Constant means that the search time is the same, independent of the specific key value, where Variable means that it is dependent on the specific key value chosen for the search.

Give the correct values for the entries X1, X2, X3 and X4 (for example X1 = Constant, X2 = Constant, X3 = Constant, X4 = Constant).

(b) Relation R(A,B) has the following view defined on it:

 CREATE VIEW V AS
 (SELECT R1.A, R2.B
 FROM R AS R1, R AS R2
 WHERE R1.B = R2.A)

(i) The current contents of relation R are shown below. What are the contents of the view V?

(ii) The tuples (2,11) and (11,6) are now inserted into R. What are the additional tuples that are inserted in V?

A
Theory Explanation is given below.
Question 2

(a) Draw the process state transition diagram of an OS in which (i) each process is in one of the five states: created, ready, running, blocked (i.e. sleep or wait), or terminated, and (ii) only non-preemptive scheduling is used by the OS. Label the transitions appropriately.

(b) The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C function.

 int TEST-AND-SET (int *x)
 {
    int y;
    A1:y=*x;
    A2:*x=1;
    A3:return y;
 } 

(i) Complete the following C functions for implementing code for entering and leaving critical sections based on the above TEST-AND-SET instruction.

 int mutex=0;
 void enter-cs()
 {
 while (…………………………………);
 }
void leave-cs()
 {
 …………………………………..;
 } 

(ii) Is the above solution to the critical section problem deadlock free and starvation-free?

(iii) For the above solution, show by an example that mutual exclusion is not ensured if TEST-AND-SET instruction is not atomic.

A
Theory Explanation is given below.
Question 3

A computer system uses 32-bit virtual address, and 32-bit physical address. The physical memory is byte addressable, and the page size is 4 kbytes. It is decided to use two level page tables to translate from virtual address to physical address. Equal number of bits should be used for indexing first level and second level page table, and the size of each page table entry is 4 bytes.

    (a) Give a diagram showing how a virtual address would be translated to a physical address.
    (b) What is the number of page table entries that can be contained in each page?
    (c) How many bits are available for storing protection and other information in each page table entry?
A
Theory Explanation is given below.
Question 4

The following solution to the single producer single consumer problem uses semaphores for synchronization.

 #define BUFFSIZE 100
 buffer buf[BUFFSIZE];
 int first=last=0;
 semaphore b_full=0;
 semaphore b_empty=BUFFSIZE;
 
void producer()
 {
 while (1) {
     produce an item;
     p1: …………………..;
     put the item into buff (first);
     first=(first+1)%BUFFSIZE;
     p2: …………………..;
        }
 }
 void consumer()
 { 
while (1) {
             c1:……………………..
             take the item from buf[last];
             last=(last+1)%BUFFSIZE;
             c2: ……………………..;
             consume the item;
          }
 } 
    (a) Complete the dotted part of the above solution.
    (b) Using another semaphore variable, insert one line statement each immediately after p1, immediately before p2, immediately after c1, and immediately before c2 so that the program works correctly for multiple procedures and consumers.
A
Theory Explanation is given below.
Question 5

(a) Construct all the parse trees corresponding to i + j * k for the grammar

      E → E+E
      E → E*E
      E → id  
    (b) In this grammar, what is the precedence of the two operators * and +?
    (c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?
A
Theory Explanation is given below.
There are 5 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access