Loading...
Loading...
Loading...
Core CS and SQL interview guide
Processes, threads, scheduling, memory management and deadlocks. Every answer is short enough to say aloud, and every question links to the lesson that teaches it.
60 questionsLast updated
A semaphore is an integer variable accessed only through two atomic operations: wait (P), which decrements and blocks if no permit is available, and signal (V), which increments and wakes a waiting process.
Follow-up: What happens when wait is called and the value is zero? The caller blocks on the semaphore's queue until another thread calls signal, which moves it back to ready. No CPU is wasted spinning.
Common mistake: Describing it only as a lock. It is a counter: a binary one acts like a lock, a counting one controls N resources.
Lesson: Synchronisation, critical sections and semaphoresProducers add to a bounded buffer and consumers remove from it. Use empty = N for free slots, full = 0 for filled slots, and mutex = 1 for the buffer; the producer waits on empty then mutex, and the consumer waits on full then mutex.
Follow-up: What is each of the three semaphores for? empty counts free slots (starts at N), full counts filled slots (starts at 0), and mutex protects the buffer (starts at 1).
Common mistake: Using only a mutex. Then the producer cannot sleep when the buffer is full, and the consumer cannot sleep when it is empty, so both spin.
Lesson: Synchronisation, critical sections and semaphoresA binary semaphore has only values 0 and 1, so it lets one process in at a time. A counting semaphore starts at N and lets up to N processes use a resource with N identical copies.
Follow-up: Give a real example of each. Binary: guarding one shared account. Counting: a pool of 3 printers, 30 software licences or 10 database connections.
Lesson: Synchronisation, critical sections and semaphoresvolatile enough to make count++ thread-safe in Java?No. volatile makes writes visible to other threads, but count++ is still three steps that can interleave. Use a lock or AtomicInteger.
Follow-up: What does volatile guarantee, then? Visibility: a write is seen by other threads, and reads and writes of that variable are not reordered around it. It does not make compound steps like count++ atomic.
Common mistake: Believing volatile replaces synchronized. It gives visibility only, not mutual exclusion.
Lesson: Synchronisation, critical sections and semaphoresThe entry section is the code that asks permission to enter the critical section, the exit section releases it, and the remainder section is the rest of the code that does not touch shared data.
Lesson: Synchronisation, critical sections and semaphoresA classic software solution for two processes using a flag array ("I want to enter") and a turn variable ("you go first"). It meets all three requirements in theory, but on modern CPUs that reorder memory operations it needs memory barriers to work.
Atomic instructions such as test-and-set and compare-and-swap, which read and update a memory word in one indivisible step. Locks and Java's atomic classes are built on them.
Lesson: Synchronisation, critical sections and semaphoresThey come from Dijkstra's Dutch terms, usually explained as proberen (to test) and verhogen (to increase). In practice P is wait or down, and V is signal or up.
Lesson: Synchronisation, critical sections and semaphoresFunctionally it can give mutual exclusion, but it lacks ownership, so a buggy thread could release a lock it never took. Mutexes can also support features such as re-entrancy and priority inheritance that plain semaphores do not.
Lesson: Synchronisation, critical sections and semaphoresIn the blocking implementation, a process that cannot proceed is put on the semaphore's waiting queue and blocked. A later signal moves one waiting process back to ready.
Lesson: Synchronisation, critical sections and semaphoresIn the textbook blocking implementation, a value of −k means k processes are blocked waiting on that semaphore.
Lesson: Synchronisation, critical sections and semaphoresFive philosophers share five forks and each needs two to eat. If all pick up their left fork at once, each waits for the right one forever, which shows deadlock; fixes include picking forks in a global order or allowing only four to sit.
Lesson: Synchronisation, critical sections and semaphoresA high-priority task waits for a lock held by a low-priority task, while a medium-priority task keeps the low one from running, so the high one is effectively blocked by the medium one. Priority inheritance fixes it by temporarily raising the lock holder's priority.
Lesson: Synchronisation, critical sections and semaphoresA monitor is a language-level construct that bundles shared data with the methods that use it and guarantees only one thread runs inside at a time, with condition variables for waiting. Java's synchronized methods with wait and notify are monitor-style.
synchronized and ReentrantLock are mutex-style locks, java.util.concurrent.Semaphore is a counting semaphore, ReentrantReadWriteLock is readers-writers, and AtomicInteger uses compare-and-swap.
synchronized (new Object()) not protect anything?Each call locks a brand-new object that no other thread uses, so there is no mutual exclusion. All threads must synchronise on the same shared lock object.
Lesson: Synchronisation, critical sections and semaphoresA deadlock is a situation where each process in a set is waiting for a resource held by another process in the same set, so none of them can ever proceed without outside help.
Follow-up: Can you give a Java example? Thread A locks account X and then account Y, while thread B locks Y and then X. Each waits for the lock the other holds.
Common mistake: Calling it a very slow program. Nothing is slow: the threads are blocked for ever and the program makes no progress.
Lesson: Deadlock: conditions, prevention and avoidanceMutual exclusion, hold and wait, no preemption and circular wait. All four must hold at the same time for a deadlock to occur.
Follow-up: Which one is the easiest to break in code? Circular wait: give every lock a number and always take locks in increasing order.
Common mistake: Naming only three conditions or adding starvation. All four must hold together; remove one and deadlock cannot happen.
Lesson: Deadlock: conditions, prevention and avoidancePrevention, which breaks one of the four conditions; avoidance, which grants requests only if the system stays safe; detection and recovery; and ignoring the problem, which many desktop OSs do for user programs.
Follow-up: Which approach do real systems use? Operating systems mostly ignore it for user programs, because it is rare and prevention is costly. Databases use detection and roll back one victim transaction.
Common mistake: Listing only prevention. Name all four: prevention, avoidance, detection with recovery, and ignoring the problem.
Lesson: Deadlock: conditions, prevention and avoidanceBy breaking one condition: request all resources at once (no hold and wait), release held resources when a request fails (allow preemption), or number resources and always request them in increasing order (no circular wait).
Follow-up: Which condition does lock ordering break? Circular wait. If everyone takes lock 1 before lock 2, nobody can hold lock 2 while waiting for lock 1.
Common mistake: Saying you can remove mutual exclusion. Exclusive resources such as a printer or a write lock need it, so we break another condition.
Lesson: Deadlock: conditions, prevention and avoidanceEach process declares its maximum need. The OS tracks Available, Allocation and Need = Max − Allocation. For each request it pretends to grant it and runs the safety check; it grants only if a safe sequence still exists, otherwise the process waits.
Follow-up: What does the safety check do, step by step? It computes Need = Max - Allocation, finds a process whose Need fits in Available, pretends it finishes and takes back its Allocation, and repeats. If all finish, the state is safe.
Common mistake: Granting a request just because the resources are free. First pretend to grant it and run the safety check.
Lesson: Deadlock: conditions, prevention and avoidanceIn deadlock, every process in the cycle is stuck forever. In starvation, a process is ready but keeps being passed over while others make progress, for example a low-priority job.
Follow-up: Can starvation happen without a deadlock? Yes. A low-priority process can starve while everything else runs normally. No cycle of waits is needed.
Common mistake: Treating them as the same thing. In deadlock all processes in the cycle are stuck; in starvation the system still makes progress.
Lesson: Deadlock: conditions, prevention and avoidanceTwo threads lock the same two monitors in opposite orders. A thread dump from jstack or jcmd <pid> Thread.print shows "Found one Java-level deadlock" with the threads and locks involved.
Follow-up: How do you confirm it in a running JVM? Take a thread dump with jstack or jcmd Thread.print. It prints "Found one Java-level deadlock" with the threads and the locks involved.
Common mistake: Restarting the app as the only fix. Find and fix the lock order, or the deadlock returns.
Lesson: Deadlock: conditions, prevention and avoidanceA process holds at least one resource and is waiting to acquire more that other processes hold. If processes had to get everything at once, this condition could not occur.
Lesson: Deadlock: conditions, prevention and avoidanceThere is a chain of processes P1 to Pn where each waits for a resource held by the next and Pn waits for P1. It is the condition that turns waiting into a deadlock.
Lesson: Deadlock: conditions, prevention and avoidanceLock ordering: give every lock a global order and always acquire locks in that order. It breaks circular wait with almost no runtime cost.
Lesson: Deadlock: conditions, prevention and avoidanceResources sit idle for a long time while the process does not use them yet, so utilisation is low, and a process needing many popular resources may starve.
Lesson: Deadlock: conditions, prevention and avoidancePrevention removes a condition by design, so deadlock can never arise, often at the cost of utilisation. Avoidance keeps all conditions possible but checks each request at runtime and grants it only if the resulting state is safe.
Lesson: Deadlock: conditions, prevention and avoidanceBecause it works like a bank that never lends out cash in a way that leaves it unable to meet all its customers' maximum credit limits in some order.
Lesson: Deadlock: conditions, prevention and avoidanceProcesses must declare their maximum need in advance, the number of processes and resources must be fixed, and the check runs on every request, which costs time. That is why general-purpose OSs rarely use it.
Lesson: Deadlock: conditions, prevention and avoidanceOnly if each resource has a single instance. With multiple instances, a cycle means deadlock is possible but another holder may release an instance and break it.
Common mistake: Saying any cycle is a deadlock. It is certain only when every resource has a single instance.
Lesson: Deadlock: conditions, prevention and avoidanceIt is a resource allocation graph with the resource nodes removed, valid for single-instance resources. An edge P → Q means P waits for a resource that Q holds, and a cycle means deadlock.
Lesson: Deadlock: conditions, prevention and avoidanceIt is a trade-off: running on every request finds deadlocks immediately but costs a lot, so systems run it periodically or when CPU utilisation drops, which is a sign that processes are stuck.
Lesson: Deadlock: conditions, prevention and avoidanceBy terminating processes, either all deadlocked ones or one at a time until the cycle breaks, or by preempting resources from a victim and rolling it back to a safe point. Victims are chosen by cost, such as priority and work done.
Lesson: Deadlock: conditions, prevention and avoidanceIt means ignoring deadlocks and assuming they are rare, then restarting if one happens. Most desktop OSs, including Linux and Windows, take this approach for user programs because prevention or avoidance would cost more.
Lesson: Deadlock: conditions, prevention and avoidanceAt least n × (m − 1) + 1. Then, even if every process holds m − 1 units, one unit is free and some process can finish.
Lesson: Deadlock: conditions, prevention and avoidancetryLock timeouts help with deadlock?A thread that cannot get the second lock within the timeout gives up and releases the first, which breaks the no-preemption condition. It must then retry, ideally after a random delay to avoid livelock.
Common mistake: Using tryLock without retrying later. Add a random delay, or both threads may retry together and fall into a livelock.
Lesson: Deadlock: conditions, prevention and avoidancePaging splits logical memory into fixed-size pages and physical memory into frames of the same size, and loads any page into any free frame. A per-process page table records which frame holds each page.
Follow-up: Why does paging remove external fragmentation? All frames are the same size, so any page fits any free frame. No odd-sized holes are left over.
Common mistake: Saying paging has no fragmentation at all. The last page of a process is usually partly empty: that is internal fragmentation.
Lesson: Memory management: paging and segmentationA page is a fixed-size block of a process's logical memory; a frame is a block of physical memory of the same size. Pages are loaded into frames.
Follow-up: Is the page size the same as the frame size? Yes, always, so a page fits exactly into a frame.
Common mistake: Mixing the two up. Pages are logical, in the process; frames are physical, in RAM.
Lesson: Memory management: paging and segmentationThe translation look-aside buffer is a small, fast hardware cache of recent page-to-frame translations. On a hit the translation is immediate; on a miss the page table in memory is read and the TLB is updated.
Follow-up: What happens on a TLB miss? The page table in memory is read to find the frame, and the entry is usually loaded into the TLB for next time.
Common mistake: Calling the TLB part of main memory. It is a small, fast hardware cache next to the CPU.
Lesson: Memory management: paging and segmentationEAT = hit ratio × (TLB time + memory time) + miss ratio × (TLB time + 2 × memory time). With 20 ns TLB, 100 ns memory and 80% hits, EAT is 140 ns.
Follow-up: Give EAT for hit ratio 80%, TLB 20 ns and memory 100 ns. 0.8 x (20 + 100) + 0.2 x (20 + 200) = 96 + 44 = 140 ns.
Common mistake: Forgetting that a miss costs two memory reads: first the page-table entry, then the data.
Lesson: Memory management: paging and segmentationWasted space inside an allocated block, because the block is larger than requested. With 4 KB pages, a process needing 9 KB gets 12 KB and wastes 3 KB in its last page.
Follow-up: How much is wasted on average? About half a page per process. Smaller pages waste less but need bigger page tables.
Common mistake: Mixing it up with external fragmentation. Internal is inside an allocated block; external is the gaps between blocks.
Lesson: Memory management: paging and segmentationPaging uses fixed-size blocks that are invisible to the programmer and causes only internal fragmentation. Segmentation uses variable-size logical units that match the program's structure and causes external fragmentation.
Follow-up: Can the two be combined? Yes. Segmentation with paging splits each segment into pages: logical segments for protection, and no external fragmentation.
Common mistake: Saying segmentation has no fragmentation. Variable-size segments leave external fragmentation.
Lesson: Memory management: paging and segmentationNumber of pages × entry size. With 32-bit addresses, 4 KB pages and 4-byte entries: 2³² ÷ 2¹² = 2²⁰ entries × 4 bytes = 4 MB per process.
Follow-up: What is it for a 32-bit address space, 4 KB pages and 4-byte entries? 2^20 pages x 4 bytes = 4 MB per process.
Common mistake: Forgetting the entry size. Size = number of pages x bytes per entry.
Lesson: Memory management: paging and segmentationIt is how the OS tracks which parts of RAM are used and by whom, decides where to place processes, translates their addresses and frees memory when they finish, while keeping processes from touching each other's memory.
Lesson: Memory management: paging and segmentationA logical (virtual) address is what the program uses; a physical address is the real location in RAM. The memory management unit (MMU) translates logical to physical at runtime.
Lesson: Memory management: paging and segmentationMoving a whole process out of memory to disk (the swap area) and back later, to free memory for others. Modern systems mostly swap individual pages rather than whole processes.
Lesson: Memory management: paging and segmentationIn simple contiguous allocation, the base register holds the process's starting physical address and the limit register its size. Every address is checked against the limit and then added to the base.
Lesson: Memory management: paging and segmentationEach process gets one continuous block of physical memory. It is simple, but as processes come and go, free memory breaks into scattered holes.
Lesson: Memory management: paging and segmentationBy compaction, which moves processes together to form one large hole but is slow and needs relocatable addresses, or by non-contiguous schemes such as paging that let a process use scattered frames.
Lesson: Memory management: paging and segmentationSo the split into page number and offset is just taking the high and low bits, with no division. For 4 KB pages the low 12 bits are the offset.
Follow-up: What is the trade-off in choosing a page size? Large pages mean smaller page tables and fewer faults but more wasted space. Small pages waste less but need bigger tables.
Lesson: Memory management: paging and segmentationNo external fragmentation, but some internal fragmentation in the last page of each process, on average about half a page.
Lesson: Memory management: paging and segmentationOne table for the whole system with one entry per physical frame, saying which process and page occupies it. It saves memory but makes lookup slower, so it is usually combined with hashing.
Lesson: Memory management: paging and segmentationIts entries belong to the old process, so they are flushed, or each entry carries an address-space identifier (ASID) so entries from several processes can live together safely.
Lesson: Memory management: paging and segmentationSegmentation divides a program into variable-size logical segments, such as code, data, heap and stack. An address is (segment, offset), and a segment table holds each segment's base and limit.
Lesson: Memory management: paging and segmentationLook up the segment's base and limit, check that offset < limit, and if so the physical address is base + offset. Otherwise the hardware traps with an addressing error.
Lesson: Memory management: paging and segmentationEach segment is itself divided into pages, so the logical structure of segments is kept while memory is allocated in frames, avoiding external fragmentation. Classic x86 used this combination.
Lesson: Memory management: paging and segmentationIt needs 3 pages, 12,288 bytes, so 12,288 − 10,300 = 1,988 bytes are lost to internal fragmentation.
Lesson: Memory management: paging and segmentationVirtual memory gives each process a large logical address space and keeps only the pages it is using in RAM, with the rest on disk. Programs can be larger than physical memory, and more programs can run at once.
Follow-up: Does virtual memory make the computer faster? No. It lets programs bigger than RAM run and more of them fit at once. Touching pages that sit on disk is slow, which is why page faults must be rare.
Common mistake: Saying virtual memory is the swap file or the hard disk. It is the mechanism that gives every process a large address space; the disk is only its backing store.
Lesson: Virtual memory and page replacement algorithmsA trap raised when a process accesses a page that is not currently in a physical frame. The OS loads the page from disk, updates the page table and restarts the instruction.
Follow-up: Who handles a page fault, the hardware or the OS? The hardware raises the trap when the valid bit is not set. The OS fault handler loads the page and restarts the instruction.
Common mistake: Calling every page fault an error or a crash. It is a normal event in demand paging; only an illegal address ends the process.
Lesson: Virtual memory and page replacement algorithmsEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson