Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Total

5 5 10 5 10 5 5 10 10 5 5 5 5 15 100

DO NOT WRITE ANYTHING ABOVE THIS LINE

UMC 102 Final Exam 24 Apr 2024

Maximum marks: 100 Duration: 3 hrs
hours

Name: __________________________________________ SR No: ____________________

Instructions to students

1. Students must report 10 mins prior to the commencement of the exam & sit in their assigned seats only.

2. Students are not allowed to leave the examination hall within 1 hr after the commencement of exam

3. Mobile phones/any form of communication devices are strictly prohibited in the exam rooms. It is best to
leave the mobile phone in the hostel itself before coming for the exam.

4. Mere possession of a mobile phone/communication device inside the examination hall or during the exam
will be treated as a case of cheating (absolutely no excuses). In such cases, suitable action will be taken.

5. No form of unfair means (including talking to another student, copying from another student's paper,
copying from any books, notes, cheat sheets, etc., use of mobile phone/communication devices) during the
examination will be tolerated. A student found resorting to any form of unfair means during the examination,
will be given 'F' grade in that course as a minimum punishment. No appeals will be accepted.

6. Abetting a student to resort to any form of unfair means will also be considered as an unfair practice. In
this instance as well, the student abetting another student will be given 'F' grade in that course. No appeals
will be accepted. In case the student who is abetting another student is from a different class/batch, suitable
action will be taken on such a student.

7. Before answering the questions, the student must write his/her name and student registration number on
the answer script.

8. When an additional sheet is taken by the student, the student must write his/her name and serial number,
sign the additional sheet and must get it countersigned by the invigilator.

9/11. DURING THE UMC 102 EXAMINATIONS, POSSESSION OR USE OF CALCULATING

DEVICES OF ANY KIND IS PROHIBITED.

11. If a student is found with a mobile phone/communication device/calculating device while taking a
break to use the washroom when the exam is in progress, it will be treated as a case of
cheating. Irrespective of whether the student is using the mobile phone/communication
device/calculating device or not, the same penalty as in item 4 will be applicable

1/14
UMC 102 Final Exam Instructions

1. Answer all parts of all the questions in the space provided for each. Pages devoted for rough
work will not be evaluated.

2. Assume the following sizes in Bytes for different types of data

char int unsigned int float double pointer

1 4 4 4 8 8

3. Assume that all numerical values shown in the questions are in decimal unless explicitly
indicated otherwise (e.g., 0x37, 1358)

[Q1] Consider two n-bit values: A= an-1an-2 ... ai ... a2a1a0 and B=bn-1bn-2 ... bi ... b2b1b0
Suppose that we perform two operations:
• We first treat A and B as unsigned integers and multiply them to obtain the n-bit bitstring
C.
• Next, we treat A and B as signed, 2s complement integers and multiply them to obtain
the n-bit bitstring D.

Give example with n=4-bit strings in which the numerical values of C (an unsigned value) and D (a
2s complement value) are same. By numerical value, we mean the value of the bitstring interpreted
as an integer.

[Q2] Now give an example with n=4-bit strings in which the numerical values of C (an unsigned
value) and D (a 2s complement value) are different.

2/14
[Q3] Prove the result that there is bit-level equivalence of unsigned and two’s complement
multiplication, i.e., that the bit-level representation of C and D are the same.

3/14
[Q4] Using the same design principles as the IEEE single and double precision data formats, a 13
bit float has been designed for the low precision needs of the Deep Learning community, using an
exponent bias of 7. Calculate the sizes (in bits) of the s, e and f fields of the 13 bit format.

4/14
[Q5] Assume that two-dimensional arrays are stored in memory in row-major order, and consider
the three variants shown below for computing the product of two matrices stored in two-dimensional
arrays. Assume each of the matrix elements are doubles and that the value of N (i.e., the dimension
of the matrix) is very large. Assume a cache block size of 32 bytes.

For each of the variant below, calculate the cache miss rate per iteration. Write your answers adjacent
to each code variant.

5/14
[Q6] Mention 2 ways in which the x86-64 control transfer instructions CALL and SYSCALL differ
from each other.

[Q7] Complete the drawing of the virtual address space of a program in execution by filling in the
names of the virtual address space regions. Treat Initalized Data and Uninitialized Data as a single
Data region.

6/14
[Q8] Given the following program skeleton, in which region of the virtual address space will each
of the 6 listed variable references be located?

#include <stdio.h>
#include <stdlib.h>

int N = 512;

struct TreeNode
{ struct TreeNode *left, *right;
float value;
} *Tree;

void InOrder (struct *T, int max)

{ int count;
struct TreeNode *tmp;
...
}

void main()
{ int limit;
...
}

Reference Virtual memory region

limit

Tree

*tmp

*Tree

tmp

7/14
[Q9] Consider the two program snippets P.c and Q.c as shown below. I have with me a uni-processor
machine (i.e., it has only one processor core).

You may assume for this question that the address 0x12345678h is a valid address and mapped
into the address space of both P.c and Q.c. Now suppose that I compile these programs and run them
concurrently on the machine as shown using the command line operations below:
$ gcc P.c -o P.out
$ gcc Q.c -o Q.out
$ ./P.out & ./Q.out

P.c -
Is there a situation in which the printf statement on line [P4] of the program P.c will print the value
2? Explain why or why not. If your answer is yes, please show a concrete execution of how the lines
o P.out
of P.c and Q.c interleave to produce 2 as the printed value. If your answer is no, explain why the value
2 cannot be printed by the printf statement.
$ gcc Q.
c -
o Q.out
$
./P.out
&
./Q.out

8/14
[Q10] Suppose that the physical page frame for a virtual page exists in memory, and that a valid
mapping exists in the page table. Does the process need to invoke the operating system to resolve
the virtual address to the physical address? Why or why not?

[Q11] Consider a machine with a two-level page table, where the page tables fit in main memory.
On this sytem, 75% of all page-table references are resolved by the TLB. Assume that accessing
main memory takes 200ns, and that accessing the TLB takes 4ns. The access time to resolve a page-
table reference is defined as the total time to obtain the virtual address to physical address transla-
tion, and access the relevant address from physical memory. On this system, calculate the average
access time to resolve a page-table reference.

9/14
[Q12] A computer system supports virtual memory that uses 48 bit virtual addresses and 52 bit
physical addresses with page size of 8 Kbyte. It uses a single level Page Table for each process.
Each Page Table Entry is of size 8 Bytes. What is the size (in bytes) of the page table in this
system?

[Q13] Explain what will happen on a Linux laptop when each of the 2 programs shown below is
executed.

void main( ) #include <stdlib.h>

{ void main( )
while (1); { void *p;
} while (1)
p = malloc ( 1 );
}

10/14
[Q14] The government of Elbonia decides that a bicycle bridge must be built across a deep canyon
running down the middle of the country. Unfortunately, severe budget cuts have forced the following
restrictions on the bridge:
• The bridge is single lane, i.e., traffic can only move in one direction at any given time.
• Due to weight restrictions, at most three riders can cross the bridge at once if they are
going in the same direction.
• If riders going in the opposite directions get on the bridge at the same time, there will be
a deadlock. Citizens of Elbonia are unbelievably stubborn and would never consider turn-
ing around.
Thus, the government wants to create a program that every citizen willing to use the bridge must use.
Here is how the program must work:
• There is a sign visible to everyone saying what direction the bridge can be used in right
now (e.g., it reads either “EAST" or “WEST").
• When a rider arrives, if the sign is in the opposite direction of where he wants to go (i.e.,
he wants to go EAST, but the sign reads WEST), but there is no one on the bridge, he is
allowed to change the sign to his
direction, and proceed across the bridge. However, he must wait in line if:
o the sign has the wrong direction and someone is on the bridge;
o the sign has the right direction, but there are already three riders on the bridge; or
o there is someone already in line.
• When a rider successfully crosses the bridge, say, from EAST to WEST, and someone is
waiting in line in the WEST, he sets the sign to EAST. If he is the last one off the
bridge,xa4 he can tell up to three people in line on the WEST side to use the bridge. On
the other hand, if no one is waiting on the WEST side, he can shout back across the bridge,
telling someone in line on the EAST that he can now use the bridge. A rider crossing from
WEST to EAST would follow a similar protocol.
Each rider calls the following routine, cross_bridge, which must implement the above set of
rules correctly. Write pseudocode for this routine using semaphores. The formal parameter, direction,
indicates the direction (EAST or WEST) that the caller intends to travel across the bridge. You can
assume that a shared global variable curr_direction stores the current direction that the bridge
is being used in.

cross_bridge(int direction) {
x // returns after caller has successfully crossed the bridge
}

P.c -o P.out
$ gcc Q.c -o Q.out
$ ./P.out & ./Q.out

11/14
Write down the code for cross_bridge:

------------------------------------------------ END OF EXAM ------------------------------------------------

FOR ROUGH WORK (WILL NOT BE GRADED)

12/14
FOR ROUGH WORK (WILL NOT BE GRADED)

13/14