Interview Q&A / Operating Systems

1. A system has 32-bit logical addresses and 4 KB pages. How many bits are the page number and offset, and how large is the page table?

   4 KB = 2^12, so the offset is 12 bits and the page number is 32 - 12 = 20 bits. That gives 2^20 entries; at 4 bytes each, the page table is 4 MB per process.

   IntermediateQuick answer1 min read
2. Burst times 24, 3 and 3, all arriving at time 0, with a time quantum of 4 ms. What is the average waiting time under Round Robin?

   P1 runs 0-4, P2 4-7, P3 7-10, then P1 alone finishes at 30. Waiting times are P1 6, P2 4, P3 7, so the average is 17 / 3, about 5.67 ms.

   IntermediateQuick answer1 min read
3. Five processes arrive together with bursts 10, 1, 2, 1, 5 and priorities 3, 1, 4, 5, 2 (lower number is higher priority). What is the average waiting time under non-preemptive priority scheduling?

   The order is P2, P5, P1, P3, P4. Waiting times are 0, 1, 6, 16 and 18, a total of 41, so the average is 41 / 5 = 8.2 ms.

   IntermediateQuick answer1 min read
4. Four processes arrive at 0, 1, 2 and 3 with bursts 8, 4, 9 and 5. What is the average waiting time under preemptive SJF (SRTF)?

   Run order by remaining time: P1 0-1, P2 1-5, P4 5-10, P1 10-17, P3 17-26. Waiting times are P1 9, P2 0, P3 15, P4 2, so the average is 26 / 4 = 6.5 ms.

   IntermediateQuick answer1 min read
5. Given a segment table, how do you translate the logical address (1, 500)?

   Look up segment 1, compare the offset with its limit, and add the offset to its base. If the offset is not below the limit the hardware traps. With limit 400 here, (1, 500) is invalid; (0, 500) maps to 1900.

   IntermediateQuick answer1 min read
6. How can you detect a deadlock using a resource allocation graph?

   Draw processes and resources as nodes, with request and assignment edges. A cycle means deadlock if every resource has a single instance; with multiple instances a cycle is necessary but not enough.

   IntermediateQuick answer1 min read
7. How do you solve the producer-consumer problem using semaphores?

   Use three semaphores: empty (counts free slots, starts at N), full (counts filled slots, starts at 0) and mutex (starts at 1). Producers wait on empty, consumers wait on full, and mutex guards the buffer.

   IntermediateQuick answer1 min read
8. How does the time quantum affect Round Robin performance?

   A very large quantum makes Round Robin behave like FCFS. A very small one wastes time on context switches. A good quantum is longer than most CPU bursts, often cited as 80% of bursts finishing within one quantum.

   IntermediateQuick answer1 min read
9. If a program calls fork() three times in a row, how many processes run in total?

   Each unconditional fork() doubles the number of processes, so n sequential calls give 2^n processes in total: 8 for three calls, meaning 7 new children plus the original.

   IntermediateQuick answer1 min read
10. If a TLB lookup takes 10 ns, memory access 100 ns and the hit ratio is 90%, what is the effective access time?

    EAT = 0.9 x (10 + 100) + 0.1 x (10 + 100 + 100) = 99 + 21 = 120 ns. A TLB hit needs one memory access; a miss needs two, one for the page table and one for the data.

    IntermediateQuick answer1 min read
11. What does a page table entry contain besides the frame number?

    Besides the frame number, an entry holds control bits: valid/present, read/write/execute permissions, a user/supervisor bit, a dirty (modified) bit and an accessed (reference) bit.

    IntermediateQuick answer2 min read
12. What is a condition variable and why does wait() release the lock?

    A condition variable lets a thread sleep until some condition becomes true. wait() atomically releases the lock and sleeps so other threads can change the state; on wakeup the thread reacquires the lock and rechecks.

    IntermediateQuick answer1 min read
13. What is a monitor in operating systems, and how is it different from a semaphore?

    A monitor bundles shared data with the procedures that access it, and the language guarantees only one thread is inside at a time. A semaphore is a bare counter that the programmer must use correctly everywhere.

    IntermediateQuick answer1 min read
14. What is a spinlock, and when is it better than a lock that puts the thread to sleep?

    A spinlock makes a waiting thread loop on the CPU until the lock is free. It is better when the lock is held for a very short time, because sleeping and waking cost more than a brief spin.

    IntermediateQuick answer1 min read
15. What is livelock, and how is it different from deadlock?

    In deadlock, processes are blocked and make no progress. In livelock they keep running and changing state in response to each other, but still make no progress, like two people repeatedly stepping aside in a corridor.

    IntermediateQuick answer1 min read
16. What is the convoy effect in FCFS scheduling?

    The convoy effect is when many short processes queue behind one long CPU-bound process, so the CPU and I/O devices sit idle in turns and average waiting time rises sharply.

    IntermediateQuick answer1 min read
17. What is the difference between fork() and exec()?

    fork() creates a new process that is a copy of the caller. exec() replaces the current process's program with a new one, keeping the same PID. Shells combine them: fork a child, then exec the command in it.

    IntermediateQuick answer1 min read
18. What is the difference between user-level threads and kernel-level threads?

    User-level threads are managed by a library in user space, and the kernel sees only one process. Kernel-level threads are managed by the OS itself, so they can run on several cores and block independently.

    IntermediateQuick answer1 min read
19. What is the dining philosophers problem and how can it be solved?

    Five philosophers sit round a table with five forks, and each needs two adjacent forks to eat. If all pick up their left fork together, everyone waits forever. Solutions include a fork ordering, a limit of four seated, or an asymmetric pickup.

    IntermediateQuick answer1 min read
20. Why do operating systems use multi-level page tables?

    A single flat page table needs an entry for every possible page, even unused ones. A multi-level table splits it into pieces and only allocates the pieces for regions actually in use, saving a large amount of memory.

    IntermediateQuick answer1 min read