OS Minor 2 Model Answers

 

Question 1)

 

Logical Address & Physical Address: Logical address space versus the Physical address space. The mapping used to map one to another. Size of one space versus the other should be mentioned. Contiguous nature should also be mentioned as a discriminating factor.

 

Allocated and unused memory block

 

i.                    First-fit

100k (free) – 290k - 110k - 100k (free) - 200k (free) - 300k (free)- 420k - 180k (free). No space left for the 350k Block.

 

ii.                  Best-fit

100k (free) – 420k -80k (free) - 110k - 90k (free)- 290k - 10k (free) – 350k – 250k (free)

 

iii.        Worst-fit 

100k (free) – 420k - 80k (free) - 200k (free) - 300k (free)- 290k - 110k – 200k (free). No space left for the 350k Block.

 

Q 2

 

a)        Virtual address consists of m bits of page no. and n bits of offset. Using page number, get the frame number from page table.  Physical address = 2^n*(frame no)+ offset

 

b)        A page fault occurs when the ‘present bit’  is 0

 

c)        When page fault occurs following steps occur

 

a.       A trap is generated to the hardware

b.      The system stores the present state of registers and program counter

c.       It checks if the requested page is in valid space of process or not

d.      Looks for a free frame

e.       If no free frame is available, use some page replacement scheme and choose a victim frame

f.       The requested page is brought into system

 

d)       When modified bit is set to 0 and the page is to be replaced, we don’t write back the contents of the page as 0 indicates that the page was not modified.

e)        Reference bit is used for page replacement policy.  

 

 

Q3

 

The instruction can be used to implement the lock as follows -:

 

while (true) 

{

         key = TRUE;

         while ( key == TRUE)

         Swap (&lock, &key );

 

         // critical section

 

         lock = FALSE;

 

         //      remainder section

}               

 

The lock will lead to busy waiting. It can be removed by the use of a waiting queue which will implement two operations:

–         lock: Place the process invoking the operation on the  appropriate waiting queue

–         wakeup: Remove one of processes in the waiting queue and place it in the ready queue                 

 

 

Q4

a)      x=1 x=1

x=1 x=2

x=1 x=3

x=2 x=1

x=2 x=2

x=2 x=3

x=3 x=1

 

b)      1, 2 or 3

c)      Yes, this is an example of a race condition, because the output depends upon the order of execution of the processes. The code can be changed in the following way -:

 

ProcessA()

{

            int i;

           

            wait(mutex);

            i = x;

            i = i + 2;

            x = i;

            atomicprintf(“x = %d\n”, x);

            signal(mutex)

}

 

 

ProcessB()

{

            int i;

           

            wait(mutex);

            i = x;

            i = i + 1;

            x = i;

            atomicprintf(“x = %d\n”, x);

            signal(mutex)

}

 

 

 

Question 5

 

 

i.          Block Size = 64 KB = 216 B

            No. of Blocks per program of 1 GB = 1 GB / 64 KB = 230 B / 216 B = 214

            Overhead per cache block = 16 bits address tag + Dirty and other status bits.

                                                            = 32 bits (word size for efficient performance)

[note 20 or 24 bits is also acceptable choice though accessing entries may require some bit operations]

 

            Total overhead per program is No. of Blocks * Overhead per cache block

                                                                        = 214 * 4 B

                                                                        = 64 KB

 

 

ii.         Time taken to transfer 128 B of data from memory to cache is 50 ns

[Note cache operates on a per line basis, so only one line is transferred not entire page]

            Time taken to access data:

            TLB/CACHE HIT                   TLB/CACHE MISS

            1 ns                                          50ns + 1 ns

 

            Time taken to access data assuming no page faults. There are four cases:    

TLB

CACHE

Time

Probability

HIT

HIT

1 + 1 = 2 ns

0.995 * 0.995

HIT

MISS

1 + 50 ns=51

0.995 * 0.005

MISS

HIT

50 + 1 = 51 ns

0.005 * 0.995

MISS

MISS

51 + 51 = 102 ns

0.005 * 0.005

 

            Average Time to access memory is

                        0.995 * 0.995 * 2 ns + 0.995 * 0.005 * 51 ns

                                    + 0.005 * 0.995 * 51 ns + 0.005 * 0.005 * 102 ns

                        = 2.49005ns

 

 

iii.        Data transfer rate of hard disk drive = 128 MB/s

            Time taken to transfer a block of data, 64 KB is 64 KB / 128 MB/s

                                                                                                = 0.5 ms

            Time to access and transfer a data block is seek time +rotational latency + transfer time = 5.5 ms [check]

 

            Probability of page fault is 1 in 10 million = 10-7

 

            Assuming that there are no dirty bits set, average time to access memory with page faults is

 

                        page fault probability * page transfer time

                        + ( 1 - page fault probability) *  memory access time without fault

 

            = 10-7 * 5.5 ms + ( 1 - 10-7 ) * 2.49 ns

            =

 

            Assuming that there always the dirty bit s set, average time to access memory with page faults is

 

                        page fault probability * 2 * page transfer time

                        + ( 1 - page fault probability) *  memory access time without fault

 

            = 10-7 * 2 * 5.5 ms + ( 1 - 10-7 ) * 2.49 ns

            =