GATE CSE 2005
Q21.
We are given 9 tasks T1, T2... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time. Are all tasks completed in the schedule that gives maximum profit?Q22.
We are given 9 tasks T1, T2... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time. What is the maximum profit earned?Q23.
A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred byte-wise. Let the interrupt overhead be 4 \musec. The byte transfer time between the device interfaces register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under program-controlled mode?Q24.
Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?Q25.
Consider a disk drive with the following specifications: 16 surfaces, 512 tracks/surface, 512 sectors/track, 1 KB/sector, rotation speed 3000 rpm. The disk is operated in cycle stealing mode whereby whenever one 4 byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a 4 byte word from the memory in each DMA cycle. Memory cycle time is 40 nsec. The maximum percentage of time that the CPU gets blocked during DMA operation is:Q26.
Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?Q27.
Suppose there are \left \lceil log n \right \rceil sorted lists of \left \lfloor n/log n \right \rfloor elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)Q28.
Consider line number 3 of the following C-program. int min ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I =0, I < N, I++); /* Line 3 */ } Identify the compiler's response about this line while creating the object-module:Q29.
The following is the Hasse diagram of the poset [{a,b,c,d,e}, \prec ] The poset is:Q30.
In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is: