Operating-Systems
Question 1 |
A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when
A | LRU page replacement algorithm is used |
B | FIFO page replacement algorithm is used |
C | LFU page replacement algorithm is used |
D | None of the above |
In LRU which can eliminate (or) removed which is least recently used.
In LFU the frequency of the page is more. So it is in constant use so cannot be replaced.
Question 2 |
Consider the following heap (figure) in which blank regions are not in use and hatched region are in use.
The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if we use
A | either first fit or best fit policy (any one) |
B | first fit but not best fit policy |
C | best fit but first fit policy |
D | None of the above |
So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 125 size block, reducing it to 125.
Request for 125 satisfied by the 125 size block.
And request for 50 satisfied by 50 size block.
So, all requests can be satisfied.
In best fit strategy, a block request is satisfied by the smallest block in which can fit it. So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 50 size block as its the smallest size that fits 25, reducing it to 25.
Request for 125, satisfied by 150 size block, reducing it to 25.
Now, request for 50 cannot be satisfied as the two 25 size blocks are not contiguous.
Question 3 |
Consider the resource allocation graph given in the figure.
(a) Find if the system is in a deadlock state. (b) Otherwise, find a safe sequence.
A | Theory Explanation. |
Question 4 |
Which of the following statements is true?
A | ROM is a Read/Write memory |
B | PC points to the last instruction that was executed |
C | Stack works on the principle of LIFO |
D | All instructions affect the flags |
Question 5 |
In a paged segmented scheme of memory management, the segment table itself must have a page table because
A | the segment table is often too large to fit in one page |
B | each segment is spread over a number of pages |
C | segment tables point to page table and not to the physical locations of the segment |
D | the processor’s description base register points to a page table |
E | Both A and B |
Segment paging is different from paged segmentation.
Question 6 |
Which of the following page replacement algorithms suffers from Belady’s anamoly?
A | Optimal replacement |
B | LRU |
C | FIFO |
D | Both (A) and (C) |
Question 7 |
Which scheduling policy is most suitable for a time shared operating system?
A | Shortest Job First |
B | Round Robin |
C | First Come First Serve |
D | Elevator |
Question 8 |
The sequence …………… is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for …………… unit(s) of time.
A | {3,2,1),1 |
B | (2,1,3},0 |
C | {3,2,1),0 |
D | {1,2,3},5 |
So, (B) and (C) will be eliminated.
Now in (A) and (D):
For r(A),
So, idle time is between 0 to 1 which in case of option (A).
For option(D),
We can see there is no idle time at all, but in option given idle time is 5, which is not matching with our chart. So option (D) is eliminated.
Therefore, the correct sequence is option (A).
Question 9 |
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page with 1 free main memory frame is recorded as follows. What is the number of page faults?
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370
A | 13 |
B | 8 |
C | 7 |
D | 10 |
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
Question 10 |
In a virtual memory system the address space specified by the address lines of the CUP must be __________ than the physical memory size and _______ than the secondary storage size.
A | smaller, smaller |
B | smaller, larger |
C | larger, smaller |
D | larger, larger |
Question 11 |
A computer installation has 1000k of main memory. The jobs arrive and finish in the following sequences.
Job 1 requiring 200k arrives Job 2 requiring 350k arrives Job 3 requiring 300k arrives Job 1 finishes Job 4 requiring 120k arrives Job 5 requiring 150k arrives Job 6 requiring 80k arrives
(a) Draw the memory allocation table using Best Fit and First fit algorithms.
(b) Which algorithm performs better for this sequence?
A | Theory Explanation. |
Question 12 |
Consider the following program segment for concurrent processing using semaphore operators P and V for synchronization. Draw the precedence graph for the statements S1 to S9.
var a, b, c, d, e, f, g, h, i, j, k : semaphore; begin cobegin begin S1; V(a); V(b) end; begin P(a); S2; V(c); V(d) end; begin P(c); S4; V(c) end; begin P(d); S5; V(f) end; begin P(e); P(f); S7; V(k) end; begin P(b); S3;V(g);V(h) end; begin P(g); S6; V(i) end; begin P(h); P(i); S8; V(j) end; begin P(j); P(j); P(k); S9 end; coend end;
A | Theory Explanation. |
Question 13 |
The head of a moving head disk with 100 tracks numbered 0 to 99 is currently serving a request at tract 55. If the queue of requests kept in FIFO order is
10, 70, 75, 23, 65
Which of the two disk scheduling algorithms FCFS (First Come First Served) and SSTF (Shortest Seek Time First) will require less head movement? Find the head movement for each of the algorithms.
A | Theory Explanation. |
Question 14 |
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?
A | The hole created by worst fit is always larger than the hole created by first fit. |
B | The hole created by best fit is never larger than the hole created by first fit.
|
C | The hole created by first fit is always larger than the hole created by next fit. |
D | The hole created by next fit is never larger than the hole created by best fit. |
Question 15 |
Consider the following statements about process state transitions for a system using preemptive scheduling.
- I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.
Which of the above statements are TRUE?
A | II and III only |
B | I, II and III only
|
C | I, II, III and IV
|
D | I, II and IV only
|
Question 16 |
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1,P2,P3,P4.
If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is _____.
A | 5.25 |
Turn Around Time = (21 – 0) + (13 – 0) + (2 – 0) + (6 – 0), Average = 42/4 = 10.50
Turn Around Time (TAT) = (18 – 0) + (21 – 0) + (10 – 0) + (14 – 0), Average = 63/4 = 15.75
Absolute difference = |10.50-15.75| = 5.25
Question 17 |
Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.
wait (a); count = count+1; if (count==n) signal (b); signal (a); wait (b); signal (b);
What does the code achieve?
A | It ensures that all processes execute CODE SECTION P mutually exclusively. |
B | It ensures that at most two processes are in CODE SECTION Q at any time. |
C | It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
|
D | It ensures that at most n-1 processes are in CODE SECTION P at any time.
|
Question 18 |
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.
(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)
Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.
Which one of the following statements is FALSE?
A | The head reverses its direction of movement between servicing of Q and P. |
B | T is serviced before P. |
C | R is serviced before P. |
D | Q is serviced after S, but before T.
|
Question 19 |
Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ______.
A | 154.5 ns |
T=20ns
D=5000ns
h=0.95
p=0.1, 1-p=0.9
d=0.2, 1-d=0.8
EMAT = h×(T+M)+(1-h)[(1-p)×2M+p[(1-d)[D+M]+d(2D+M)]+T]
= 0.95×(20+100)+(1-0.95)[(1-0.1)×200+(0.1)[(1-0.2)[5000+100]+(0.2)(10000+100)]+20]
= 154.5 ns
Question 20 |
The process state transition diagram in below figure is representative of
A | a batch operating system |
B | an operating system with a preemptive scheduler |
C | an operating system with a non-preemptive scheduler |
D | a uni-programmed operating system |
So this is preemptive.
Question 21 |
A critical section is a program segment
A | which should run in a certain specified amount of time |
B | which avoids deadlocks |
C | where shared resources are accessed |
D | which must be enclosed by a pair of semaphore operations, P and V |
Question 22 |
Which of the following is an example of spooled device?
A | A line printer used to print the output of a number of jobs. |
B | A terminal used to enter input data to a running program. |
C | A secondary storage device in a virtual memory system. |
D | A graphic display device. |
Question 23 |
The correct matching for the following pairs is
A. Activation record 1. Linking loader B. Location counter 2. Garbage collection C. Reference counts 3. Subroutine call D. Address relocation 4. Assembler
A | A – 3 B – 4 C – 1 D – 2 |
B | A – 4 B – 3 C – 1 D – 2 |
C | A – 4 B – 3 C – 2 D – 1 |
D | A – 3 B – 4 C – 2 D – 1 |
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
Question 24 |
A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for
A | 151 |
B | 181 |
C | 231 |
D | 541 |
So, smallest allocation request which can be denied is 181 KB.
Question 25 |
A solution to the Dining Philosophers Problem which avoids deadlock is
A | ensure that all philosophers pick up the left fork before the right fork |
B | ensure that all philosophers pick up the right fork before the left fork |
C | ensure that one particular philosopher picks up the left fork before the right fork, and that all other philosophers pick up the right fork before the left fork |
D | None of the above |
To avoid this, atleast one philosopher should choose its first chopstick in different way so that circular loop is not formed.
Question 26 |
Four jobs to be executed on a single processor system arrive at time 0+ in the order A, B, C, D. their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is
A | 10 |
B | 4 |
C | 8 |
D | 9 |
∴ Completion time of A is 9 unit.
Question 27 |
A demand paged virtual memory system uses 16 bit virtual address, page size of 256 bytes, and has 1 Kbyte of main memory. LRU page replacement is implemented using a list whose current status (page number in decimal) is
For each hexadecimal address in the address sequence given below
00FF, 010D, 10FF, 11B0
indicate
(i) the new status of the list
(ii) page faults, if any, and
(iii) page replacements, if any
A | Theory Explanation. |
Question 28 |
The concurrent programming constructs fork and join are as below:
fork
N = 2 M = 2 fork L3 fork L4 S1 L1:join N S3 L2:join M S5 L3:S2 goto L1 L4:S4 goto L2 next:
A | Theory Explanation. |
Question 29 |
A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where P0, P1, P2 are processes, and R0, R1, R2 are resources types.
(a) Show that the system can be in this state.
(b) What will the system do on a request by process P0 for one unit of resource type R1?
A | Theory Explanation. |
Question 30 |
A file system with a one-level directory structure is implemented on a disk with disk block size of 4K bytes. The disk is used as follows:
Disk-block 0: File Allocation Table, consisting of one 8-bit entry per date block, representing the data block address of the next date block in the file Disk block 1: Directory, with one 32 bit entry per file: Disk block 2: Data block 1; Disk block 3: Data block 2; etc.
(a) What is the maximum possible number of files?
(b) What is the maximum possible file size in blocks?
A | Theory Explanation. |
Question 31 |
Locality of reference implies that the page reference being made by a process
A | will always be to the page used in the previous page reference |
B | is likely to be to one of the pages used in the last few page references |
C | will always be to one of the pages existing in memory |
D | will always lead to a page fault |
(1) Temporal locality
(2) Spatial locality
(3) Sequential locality
→ In programs related data are stored in consecutive locations and loops in same locations are used repeatedly.
Question 32 |
The correct matching for the following pairs is
(A) Disk Scheduling (1) Round robin (B) Batch Processing (2) SCAN (C) Time sharing (3) LIFO (D) Interrupt processing (4) FIFO
A | A – 3 B – 4 C – 2 D – 1 |
B | A – 4 B – 3 C – 2 D – 1 |
C | A – 2 B – 4 C – 1 D – 3 |
D | A – 3 B – 4 C – 3 D – 2 |
Batch processing - FIFO
Time sharing - Round Robin
Interrupt processing - LIFO
Question 33 |
I/O redirection
A | implies changing the name of a file |
B | can be employed to use an existing file as input file for a program |
C | implies connection 2 programs through a pipe |
D | None of the above
|
Question 34 |
Thrashing
A | reduces page I/O |
B | decreases the degree of multiprogramming |
C | implies excessive page I/O |
D | improve the system performance |
Question 35 |
Dirty bit for a page in a page table
A | helps avoid unnecessary writes on a paging device |
B | helps maintain LRU information |
C | allows only read on a page |
D | None of the above |
Question 36 |
An operating system contains 3 user processes each requiring 2 units of resource R. The minimum number of units of r such that no deadlocks will ever arise is
A | 3 |
B | 5 |
C | 4 |
D | 6 |
Question 37 |
Each Process Pi, i = 1.......9 is coded as follows
repeat P(mutex) {Critical section} V(mutex) forever
The code for P10 is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?
A | 1 |
B | 2 |
C | 3 |
D | None of the above |
repeat
{
V(mutex)
C.S.
V(mutex)
}
forever
Now, let me say P1 is in CS then P1 is in CS
then P10 comes and executes CS (upon mutex).
Now, P2 comes (down on mutex).
Now P10 moves out of CS (again binary semaphore will be 1).
Now P3 comes (down on mutex).
Now P10 comes (upon mutex).
Now P4 comes (down mutex).
⁞
So, if we take P10 'in' and 'out' of CS recursively, all 10 processes can be in CS at same time using binary semaphore only.
Question 38 |
A linker reads four modules whose lengths are 200, 800, 600 and 500 words, respectively. If they are loaded in that order, what are the relocation constants?
A | 0, 200, 500, 600 |
B | 0, 200, 1000, 1600 |
C | 200, 500, 600, 800 |
D | 200, 700, 1300, 2100 |
Now 2nd will start loading at 200, since size is 800, so last address is 999.
Now 3rd module will start loading at 1000, since size is 600. So last address is 1599.
Now 4th module will start loading at 1600 and go till 2099.
Question 39 |
Which of the following is an example of a spooled device?
A | The terminal used to enter the input data for the C program being executed |
B | An output device used to print the output of a number of jobs |
C | The secondary memory device in a virtual storage system |
D | The swapping area on a disk used by the swapper |
For example in printer if a process attempt to print a document but printer is busy printing another document, the process, instead of waiting for printer to become available, write its output to disk. When the printer becomes available the data on disk is printed.
Spooling allows process to request operation from peripheral device without requiring that the device is ready to service the request.
Question 40 |
When the result of a computation depends on the speed of the processes involved there is said to be
A | cycle stealing |
B | rare condition |
C | a time lock |
D | a deadlock |
Speed of processes corresponds to ordering of processes.
Question 41 |
A counting semaphore was initialized to 10. Then 6P (wait) operations and 4V (signal) operations were completed on this semaphore. The resulting value of the semaphore is
A | 0 |
B | 8 |
C | 10 |
D | 12 |
S = 10
Now 6P operations and uv operations were completed on this semaphore. So final value of S will be
S = 10 - 6 + 4 = 8
Question 42 |
A computer has six tape drives, with n processes competing for them. Each process may need two drives. What is the maximum value of n for the system to be deadlock free?
A | 6 |
B | 5 |
C | 4 |
D | 3 |
So maximum no. of process for the system to be deadlock free is 5.
Question 43 |
The overlay tree for a program is as shown below:
What will be the size of the partition (in physical memory) required to load (and run) this program?
A | 12 KB |
B | 14 KB |
C | 10 KB |
D | 8 KB |
For the above program, maximum memory will be required when running code portion present at leaves.
Maximum requirement
= MAX(12, 14, 10, 14)
= 14
Question 44 |
Consider n processes sharing the CPU in a round-robin fashion. Assuming that each process switch takes s seconds, what must be the quantum size q such that the overhead resulting from process switching is minimized but at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?
A | q ≤ t-ns/n-1 |
B | q ≥ t-ns/n-1 |
C | q ≤ t-ns/n+1 |
D | q ≥ t-ns/n+1 |
Question 45 |
If an instruction takes i microseconds and a page fault takes an additional j microseconds, the effective instruction time if on the average a page fault occurs every k instruction is:
A | i + (j/k) |
B | i + (j*k) |
C | (i+j)/ k |
D | (i+j)*k |
= service time + page fault rate * page fault service time
= i + 1/k * j
= i + j/k
or
The effective instruction time, if on the average a page fault occurs every k instructions, is:
i + (j / k)
This formula accounts for the normal instruction time (i) and the additional time for a page fault (j), considering the average frequency of page faults (k instructions between page faults).
Question 46 |
(a) Free disk space can be kept track of using a free list or a bit map. Disk addresses require d bits. For a disk with 13 blocks, F of which is free, state the condition under which the free list uses less space than the bit map.
(b) Consider a disk with C cylinders, t tracks per cylinder, s sectors per track and a sector length sl. A logical file dl with fixed record length rl is stored continuously on this disk starting at location (cL,tL,sL), where cL, tL and SL are the cylinder, track and sector numbers, respectively. Derive the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that rl=sl.
A | Theory Explanation. |
Question 47 |
Listed below are some operating system abstractions (in the left column) and the hardware components or mechanism (in the right column) that they are abstractions of. Which of the following matching of pairs is correct?
A. Thread 1. Interrupt B. Virtual address space 2. Memory C. File system 3. CPU D. Signal 4. Disk
A | (A) – 2 (B) – 4 (C) – 3 (D) - 1 |
B | (A) – 1 (B) – 2 (C) – 3 (D) – 4 |
C | (A) – 3 (B) – 2 (C) – 4 (D) - 1 |
D | (A) – 4 (B) – 1 (C) – 2 (D) – 3 |
⇒ Threads are handled by CPU.
⇒ Virtual address is a memory type.
⇒ File system is used to manage the disk.
⇒ Interrupt is a signal.
Question 48 |
Which of the following disk scheduling strategies is likely to give the best through put?
A | Farthest cylinder next |
B | Nearest cylinder next |
C | First come first served |
D | Elevator algorithm |
Nearest cylinder next - SSTF
First come first served - FCFS
Elevator - SCAN
SSTF always serves the request of nearest cylinder first. Due to which the necessary movement gets reduced.
Question 49 |
System calls are usually invoked by using
A | a software interrupt |
B | polling |
C | an indirect jump |
D | a privileged instruction |
Question 50 |
A multi-user, multi-processing operating system cannot be implemented on hardware that does not support
A | Address translation |
B | DMA for disk transfer |
C | At least two modes of CPU execution (privileged and non-privileged) |
D | Demand paging |
E | Both A and C |