FOUNDATIONS · PART 0533 MIN READPREFACE · ~33 MIN LEFT+60 XP
Part 5: Operating System Concepts for System Design.
Every distributed system runs on operating systems. When you say "the server handles 10,000 requests per second," you're relying on OS concepts you might not consciously think about.
5 stages26 code
stages
5
code blocks
26
5 stages · save a checkpoint to resume by stage on any device
Every distributed system runs on operating systems. When you say "the server handles 10,000 requests per second," you're relying on OS concepts you might not consciously think about.
Your application code sits on top of
Layer (top to bottom)
Includes
Your application
Runtime
Python, JVM, Go, Node.js
System libraries
libc
Operating system kernel
Process Management · Memory Management · File Systems · I/O Subsystem · Networking Stack · Device Drivers
Hardware
Understanding OS concepts helps you
Tune your systems for performance
Debug production issues
Make informed architecture decisions
Answer interview questions confidently
This document covers everything about operating systems you need for system design interviews.
ExplainerThe whole lesson: operating system concepts
Processes isolate memory while threads share it, which brings race conditions and deadlocks. Virtual memory maps pages through a page table, page faults and the memory hierarchy set the speed, and cache lines reward sequential access. Event loops on epoll replace thread-per-connection, while the page cache, fsync, write-ahead logs, file descriptor limits and container cgroups decide what survives a crash and what scales.
%% title: Fork and exec (Unix/Linux)
sequenceDiagram
autonumber
participant P as Parent Process
participant C as Child Process
P->>C: fork()
Note right of C: Created as copy of parent<br/>Gets new PID<br/>Shares open file descriptors
Note left of P: (continues)
C->>C: exec("/bin/program")
Note right of C: Replaces memory with new program
P->>P: wait() ...
Note right of C: (runs program)
C-->>P: exit status · exit(0)
fork() return values:
In parent: Returns child's PID (positive number)
In child: Returns 0
On error: Returns -1
Copy-on-write (COW):
Child doesn't immediately copy parent's memory
Pages marked read-only, shared between parent/child
Two threads access shared data, at least one writes. Result depends on timing (non-deterministic).
Thread A
Thread B
read counter (0)
read counter (0)
counter = 0 + 1
counter = 0 + 1
write counter (1)
write counter (1)
Expected: 2 · Actual: 1 ← BUG!
2. Deadlock
Two threads each hold a lock the other needs
Thread A
Thread B
lock(A)
lock(B)
waiting for B
waiting for A
Both stuck forever!
Prevention:
Lock ordering (always acquire in same order)
Lock timeout
Deadlock detection
3. Livelock
Threads keep responding to each other but make no progress. Like two people in hallway both stepping aside.
4. Starvation
One thread never gets resources (always preempted)
Your turn · checkpoint 1not answered
50 threads, 10 database connections
A service has 50 worker threads but only 10 database connections. You want at most 10 threads talking to the database at once, and the rest should wait their turn. Is a mutex the right tool? If not, what is?
Think it through, or jot it down. Then compare.
One strong answer
A mutex isn't enough. It lets exactly one thread in at a time, so 9 connections would sit idle.
Use a semaphore with a count of 10. Each thread calls acquire() before taking a connection, and the count drops. The 11th thread blocks until someone calls release().
Mutexes protect shared data, one thread at a time. Semaphores count a limited resource, N at a time.
bool CAS(address, expected, new_value): // This is atomic (hardware instruction) if *address == expected: *address = new_value return true return false
Lock-free counter example
pythonLockFreeCounter · 11 lines
class LockFreeCounter: def __init__(self): self.value = AtomicInt(0) def increment(self): while True: old = self.value.get() new = old + 1 if self.value.compare_and_swap(old, new): return new # CAS failed, another thread changed it, retry
Why lock-free?
No deadlocks
No priority inversion
Progress guarantee (someone always makes progress)
All CPU registers (general purpose, program counter, stack pointer)
Memory management info (page table pointer)
Floating point state
→ Saved to Process A's Process Control Block (PCB)
Update scheduler
Mark Process A as READY (or WAITING)
Select Process B to run
Mark Process B as RUNNING
Restore state of Process B
Load registers from Process B's PCB
Load page table pointer (TLB flush!)
Jump to Process B's program counter
Time costs
Direct costs:
Register save/restore: ~100-1000 cycles
Page table switch: ~1000+ cycles
Indirect costs (often bigger!):
TLB flush: Cache misses for a while
CPU cache pollution: Process B's data not in L1/L2
Pipeline flush: Branch prediction invalid
Total: 1-10 μs for threads, 10-100 μs for processes
Your turn · checkpoint 2not answered
2,000 threads on 8 cores
A server gives each request its own thread: 2,000 threads on an 8-core machine, mostly waiting on I/O. The CPU is busy, but much of that time isn't spent on application code. Where is the time going, and what would you change?
Think it through, or jot it down. Then compare.
One strong answer
Context switches. Only 8 threads can run at once, so the OS keeps swapping threads in and out. Each switch costs ~1–10 μs directly, plus cold caches afterwards.
What to change: don't block a thread per request. An event loop handles many connections on one thread, and a thread pool sized to the cores handles CPU work.
The trade-off: fewer switches, but async code is harder to write than plain blocking calls.
One thread handles many connections. No blocking = no forced context switch.
Examples: Node.js, nginx, Redis
2. Thread pools
Fixed number of threads, reused. Avoid thread creation/destruction overhead.
text2 lines
pool = ThreadPool(num_cores * 2)pool.submit(task)
3. CPU affinity
Pin threads to specific CPU cores. Better cache utilization.
bash1 line
taskset -c 0,1 ./myprogram
4. Batch processing
Process multiple items per wake-up. Amortize context switch cost.
text2 lines
while items = queue.get_batch(100): process(items)
5. Cooperative scheduling
Coroutines yield voluntarily. No preemptive switches.
Examples: Python asyncio, JavaScript async/await (Go goroutines are mostly cooperative but preemptible since Go 1.14)
Quick check4 questions · +5 XP each
Processes, threads and context switching
Q1/4 Two threads each run counter += 1 1,000 times on a shared counter. The final value is often below 2,000. Why?
Answer & explanation
Answer: B
Both threads can read the same old value and both write old + 1, losing one increment: a race condition. Use an atomic increment or a mutex. A deadlock would hang the threads, not lose updates.
Q2/4 Thread A locks accounts then audit; thread B locks audit then accounts. The service hangs now and then. What is the standard fix?
Answer & explanation
Answer: A
Each thread holds the lock the other needs: a deadlock. A single lock order makes that cycle impossible. Spinlocks still deadlock, just while burning CPU.
Q3/4 You must run untrusted plugin code that sometimes crashes. Why run it as separate processes rather than threads?
Answer & explanation
Answer: C
Threads share one address space, so one fatal fault kills every thread. Processes are isolated. Processes cost more to create and switch between; you pay that for the isolation.
Q4/4 Why is a switch between two processes more expensive than one between two threads of the same process?
Answer & explanation
Answer: C
Threads share an address space, so the page tables and TLB entries stay valid. A process switch loads new page tables, and the indirect cost of lost translations and cache lines is often the bigger part. Both kinds of switch save and restore registers.
Isolation — Each process thinks it has entire address space. Can't accidentally (or maliciously) access other process's memory
Simplification — Programmers use simple linear addresses. OS handles mapping to physical memory
Overcommit — Can allocate more virtual memory than physical RAM. Pages stored on disk when not in use (swap)
Shared memory — Multiple processes can map same physical page. Used for: shared libraries, IPC
Virtual address space (64-bit Linux)
Address
Region
Notes
0xFFFFFFFFFFFFFFFF – 0xFFFF800000000000
Kernel space (not accessible from user mode)
Top 128 TB
0xFFFF800000000000 – 0x00007FFFFFFFFFFF
(huge gap)
Non-canonical addresses
0x00007FFFFFFFFFFF – 0x0000000000000000
User space: Stack (grows ↓) · ... · Heap (grows ↑) · Data · Text
Bottom 128 TB
Your turn · checkpoint 3not answered
Estimate it: page table entries for 4 GB
A process maps 4 GB of memory. How many page translations does that take with normal 4 KB pages? How many with 2 MB huge pages? Why would a database care?
The TLB holds only tens to a few thousand entries. With huge pages, far more of a database's memory is covered by cached translations, so fewer accesses pay for a slow page table walk.
// Array stored: [0][1][2][3][4][5][6][7]for (int i = 0; i < N; i++) sum += array[i]; // Sequential, cache-friendly
Each cache line (64B) loads ~16 integers. Next iteration hits cache (spatial locality).
2. Strided access (Bad)
c11 lines
// 2D array stored row-major: [0,0][0,1][0,2]...[1,0][1,1]...// BAD: Column-major traversalfor (int j = 0; j < cols; j++) for (int i = 0; i < rows; i++) sum += matrix[i][j]; // Jumping around, cache misses!// GOOD: Row-major traversalfor (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) sum += matrix[i][j]; // Sequential, cache-friendly
3. Structure of Arrays (SoA) vs Array of Structures (AoS)
cEntity · 16 lines
// AoS (Array of Structures) - common but often slowerstruct Entity { float x, y, z; int health; bool active; };Entity entities[1000];// To sum all x values: loads entire struct but only uses xfor (i = 0..999) sum += entities[i].x; // Cache pollution!// SoA (Structure of Arrays) - cache-friendlystruct Entities { float x[1000], y[1000], z[1000]; int health[1000]; bool active[1000];};// To sum all x values: only loads x arrayfor (i = 0..999) sum += entities.x[i]; // Cache-friendly!
Allocate memory on local node — numactl --membind=0 ./myprogram
Bind threads to cores on same node as their data — numactl --cpunodebind=0 ./myprogram
Database optimization
Partition data by NUMA node
Pin worker threads to nodes
Quick check2 questions · +5 XP each
Virtual memory and the memory hierarchy
Q1/2 A service's p99 jumps from 2ms to 40ms once its memory use exceeds physical RAM. What is the most likely cause?
Answer & explanation
Answer: B
A major fault means disk I/O, about 1-10ms each, roughly 1000x a minor fault. Swapping turns memory accesses into disk reads. Minor faults only update the page table (microseconds), so they cannot explain jumps of tens of milliseconds.
Q2/2 Summing a large row-major 2D array column by column is several times slower than row by row. Why?
Answer & explanation
Answer: A
A 64-byte cache line brings in about 16 adjacent ints. Row order uses them all (spatial locality); column order uses one and moves on. The arithmetic is identical; the gap is memory access pattern.
%% title: Blocking vs non-blocking I/O
sequenceDiagram
participant T as Thread
participant K as Kernel
Note over T,K: BLOCKING I/O
T->>K: read(fd, buf, size)
Note left of T: Thread blocked/sleeping<br/>Cannot do other work
Note right of K: Waiting for data<br/>from disk/network
K-->>T: Data returned
Note left of T: Thread continues
Note over T,K: Problem: Thread is idle while waiting<br/>Solution: More threads (but threads are expensive)
Note over T,K: NON-BLOCKING I/O
T->>K: read(fd, buf, size)
K-->>T: EAGAIN (would block)
Note right of K: No data yet
Note left of T: Do other work
T->>K: read(fd, buf, size)
K-->>T: EAGAIN
Note right of K: Still no data
Note left of T: Do other work
T->>K: read(fd, buf, size)
K-->>T: Data
Note right of K: Data ready!
Note over T,K: Problem: Busy polling wastes CPU<br/>Solution: Event notification (select/poll/epoll)
Your turn · checkpoint 4not answered
10,000 sockets, one of them ready
A server watches 10,000 open sockets, and at any moment only a few have data. Picture a call that hands the kernel the full list every time and checks every socket. Why does that get slower as connections grow? What would you want instead?
Think it through, or jot it down. Then compare.
One strong answer
Each call is O(n): the kernel scans all 10,000 sockets to find the one that's ready, and the list is copied and rebuilt every time. Double the connections and you double the wasted work.
What you want: register each socket once and have the kernel return only the ready ones.
That's the move from select/poll to epoll (kqueue on BSD/macOS), and it's why one event loop can handle tens of thousands of connections.
while (running): events = epoll_wait(epfd, timeout) # ◀── Block until ready for event in events: if event.type == READABLE: data = read(event.fd) process(data) if event.type == WRITABLE: write(event.fd, pending_data) run_timers() run_callbacks()
DiagramReactor pattern
%% title: Reactor pattern
flowchart TD
subgraph CL["Clients"]
c1@{ icon: "sd:user", label: "Client 1" }
c2@{ icon: "sd:user", label: "Client 2" }
c3@{ icon: "sd:user", label: "Client 3" }
end
c1 & c2 & c3 --> R["Reactor (Event Loop)<br/>Demultiplexer (epoll)"]:::core
R --> H1@{ icon: "sd:api", label: "HTTP Handler" }
R --> H2@{ icon: "tech:websocket", label: "WS Handler" }
R --> H3@{ icon: "sd:file", label: "File Handler" }
subgraph HD["Handlers"]
H1
H2
H3
end
class c1,c2,c3 client
class H1,H2,H3 service
Pros: Simple programming model Cons: Threads expensive, doesn't scale past ~10K connections Used: Traditional web servers (Apache worker MPM; prefork uses a process per connection)
2. Thread pool
Main Thread: accept() → queue task. Worker Pool: threads pull from queue.
Single Thread: epoll_wait → handle ready events → repeat
Pros: Massive concurrency, no thread overhead Cons: Can't use multiple cores, callback hell Used: Node.js, Redis
4. Hybrid (event loop + thread pool)
Event Loop: handles I/O, delegates CPU work
Thread Pool: handles CPU-intensive tasks
Event Loop (I/O bound) ⇄ Thread Pool (CPU bound)
Pros: Best of both worlds Cons: More complex Used: Node.js (libuv workers), nginx
5. Multi-threaded event loops
Multiple event loops, one per core
Core
Event loop
Handles connections
Core 0
Event Loop 0
0, 4, 8, ...
Core 1
Event Loop 1
1, 5, 9, ...
Core 2
Event Loop 2
2, 6, 10, ...
Core 3
Event Loop 3
3, 7, 11, ...
Pros: Scales to multiple cores Cons: Cross-thread communication needed Used: nginx (worker processes), Go runtime
ExplainerThread per connection vs an epoll event loop
With a thread per connection, each thread blocks in read() and sits idle until its data arrives, which doesn't scale past about 10K connections. An event loop registers every connection with epoll once; one thread blocks in epoll_wait, gets back only the ready connections, handles them in turn and loops.
Cache MISS: Read from disk, cache, return (~10ms for HDD)
Write behavior
Write-back (default): Write to cache → return immediately → flush later. Fast but data loss risk on crash
Write-through (O_SYNC/O_DSYNC): Write to cache AND disk → return. Slower but safer
O_DIRECT: Bypass cache entirely. Used by databases that manage own cache
fsync(): Force flush to disk. Ensures durability
System design impact
Situation
Response
Reading same file twice?
→ Second read from cache (fast)
Too many dirty pages / write stalls?
→ Tune vm.dirty_ratio, vm.dirty_background_ratio
Database doing own caching?
→ Use O_DIRECT to avoid double caching
Need durability?
→ fsync() after writes (databases do this)
Your turn · checkpoint 5not answered
What breaks if the power fails mid-update?
A database applies a commit by overwriting the changed pages in its data files. The power fails halfway through writing one of them. What state is that data in after reboot? How would you design commits so they survive this?
Think it through, or jot it down. Then compare.
One strong answer
The page is half old, half new: corrupted. Updating in place isn't atomic, and nothing records what the write was meant to be.
The fix: first append the change to a log and fsync() it, then update the data files. After a crash, replay the committed entries from the log.
Appending to the log is sequential, so it's fast enough to do on every commit. The slow random writes to the data files can happen later.
Q1/4 A push-notification gateway must hold 50,000 mostly idle connections open. Which I/O model fits?
Answer & explanation
Answer: A
epoll returns only ready sockets, so one thread can watch tens of thousands of idle connections cheaply. Thread-per-connection stops scaling around 10K connections, and a 50-thread blocking pool can only serve 50 sockets at a time.
Q2/4 In a single-threaded Node.js server, one request handler runs a 2-second CPU-heavy computation. What happens to the other connections?
Answer & explanation
Answer: B
The event loop only switches tasks when a handler yields. CPU work never yields, so everything waits; that is why the hybrid model offloads it. Event loops are great for I/O-bound work, not long CPU-bound work.
Q3/4write() returns success, then the machine loses power and the data is gone. What did the application skip?
Answer & explanation
Answer: C
By default writes land in the page cache and return immediately; the flush to disk happens later. fsync() forces it. O_DIRECT is for avoiding double caching. The durability guarantee comes from fsync, which is why databases fsync the WAL.
Q4/4 Why does a database append to a write-ahead log and fsync it, instead of fsyncing changed data pages in place on each commit?
Answer & explanation
Answer: C
Sequential I/O is much faster than random, about 100 MB/s vs 1 MB/s on HDD. The log makes commits durable, and the data files catch up later. Compression is not the point; append-only access is.
WorksheetOne server, 1 million connections (assumptions labelled)
Value
Concurrent connections (the interview question in Chapter 10)
1,000,000
Thread-per-connection: stack per thread (assumed ~1 MB default)
1,000,000 × 1 MB ≈ 1 TB of stacks
Event loops: state per connection (assumed under 1 KB)
1,000,000 × 1 KB ≈ 1 GB
Cores, one event loop each (assumed)
32 → ~31,000 connections per loop
File descriptors needed
1 per connection → 1,000,000, against a common default ulimit -n of 1,024
Conclusion: memory per connection decides the model. A thread per connection needs about a terabyte of stacks, and event loops need about a gigabyte. Either way, the default file descriptor limit stops the server at about 1,000 clients until it's raised.
Q1/2 A new server rejects connections with "Too many open files" at about 1,000 concurrent clients, though CPU and memory are fine. What should you check first?
Answer & explanation
Answer: A
Every TCP connection is a file descriptor, and the default limit is often 1,024, so it runs out around 1,000 clients. Swappiness and CPU quotas affect performance, not the count of open sockets.
Q2/2 A Kubernetes pod has limits of cpu: 500m and memory: 512Mi. What happens when it tries to exceed each?
Answer & explanation
Answer: B
CPU is compressible, so the cgroup just gives you fewer time slices. Memory is not, so going over the hard limit triggers the OOM killer. That difference matters: a memory leak restarts pods, while a CPU spike just slows them down.
Q: "What's the difference between a process and a thread?"
Great answer:
"A process is an independent execution unit with its own memory space,
file descriptors, and system resources. Processes are isolated from each
other — one crashing doesn't affect others.
A thread is a lightweight execution unit within a process. Multiple threads
share the same memory space, heap, and file descriptors, but each has its
own stack and registers.
Key differences:
Memory: Processes isolated, threads share
Creation cost: Process ~0.1-1 ms, thread ~10μs
Communication: Processes need IPC, threads share memory directly
Crash impact: Process crash is isolated, thread crash kills whole process
I'd use multiple processes when I need isolation (like running untrusted
code) or want to leverage multiple machines. I'd use threads when I need
shared state and low-latency communication within a single machine.
Modern systems often combine both — like nginx using multiple worker
processes, each with async I/O handling many connections."
Q: "How would you handle 1 million concurrent connections?"
Great answer:
"This is the C10K problem scaled up 100x (C10M is the 10-million version).
The key is minimizing overhead per connection.
First, avoid thread-per-connection. At 1M connections, that's 1M threads,
each using memory for stack (~1MB default). That's 1TB just for stacks!
Instead, I'd use:
Event-driven architecture: epoll/kqueue with non-blocking I/O. One thread
can handle thousands of connections by only processing when data is ready.
Multiple event loops: One per CPU core. With 32 cores, each handles ~30K
connections.
System tuning:
File descriptor limits: at least 1M
Ephemeral port range expanded
TCP buffer sizes optimized
somaxconn increased for accept queue
Memory efficiency:
Connection state < 1KB per connection
Zero-copy I/O where possible
Object pooling to avoid allocation overhead
Consider io_uring on modern Linux for even better performance — it
reduces syscall overhead significantly.
Companies like Discord and WhatsApp handle millions of connections using
these techniques."
Q: "Explain virtual memory and why it's important."
Great answer:
"Virtual memory gives each process the illusion of having its own
contiguous address space, even though physical memory is shared and
fragmented.
How it works:
Each process has a page table mapping virtual to physical addresses
CPU's MMU translates addresses on every memory access
TLB caches recent translations for performance
Key benefits:
Isolation: Process A can't access Process B's memory. Even if both use
virtual address 0x1000, they map to different physical frames.
Simplification: Programmer doesn't worry about where memory physically
is. malloc() returns an address that just works.
Overcommit: Can allocate more virtual memory than physical RAM. Pages
not actively used can be swapped to disk.
Shared memory: Same physical page can appear in multiple address spaces.
Used for shared libraries (libc loaded once, shared by all).
Memory-mapped files: Map files into address space, let OS handle I/O.
The cost is the page table walk on TLB miss (~100 cycles). That's why TLB
hit rate matters, and why huge pages (2MB instead of 4KB) can help —
fewer TLB entries needed to cover same memory."
Q: "What happens when a process accesses memory that's not in RAM?"
Great answer:
"That triggers a page fault. There are three types:
Minor page fault: The page exists in memory but isn't mapped in the
page table. Common after fork() with copy-on-write, or first access
to newly allocated memory. OS just updates the page table. Cost: ~1μs.
Major page fault: The page isn't in memory at all. Either it was
swapped out, or it's a memory-mapped file being accessed. OS must
read from disk. Cost: ~10ms for HDD, ~100μs for SSD.
Invalid fault: The address isn't valid — null pointer, stack overflow,
or permission violation. Results in SIGSEGV (segmentation fault).
For high-performance systems, you want to minimize major page faults:
Disable swap for databases (or use fast NVMe for swap)
Pre-fault memory on startup (touch all pages)
Use mlock() to prevent critical pages from swapping
Monitor page fault rates (vmstat, perf)
Latency-sensitive stores like Elasticsearch recommend disabling swap —
an OOM is better than unpredictable latency from page faults."
"There are five main I/O models, each with different tradeoffs:
Blocking I/O:
read() blocks until data available. Simple but wastes thread while
waiting. One thread per connection doesn't scale.
Non-blocking I/O:
read() returns immediately with EAGAIN if no data. Application must
poll repeatedly. Wastes CPU cycles polling.
I/O Multiplexing (select/poll/epoll):
One syscall monitors many file descriptors. epoll_wait() blocks until
ANY descriptor is ready, then returns which ones. Efficient for many
connections. This is what nginx, Node.js, Redis use.
Signal-driven I/O:
Kernel sends signal when I/O is ready. Application handles in signal
handler. Rarely used — signals are tricky.
Async I/O (aio, io_uring):
Submit I/O operations, kernel completes them in background. io_uring
on modern Linux is the most efficient — submissions and completions
via shared memory rings, minimal syscalls.
For a high-performance server, I'd use epoll (or kqueue on BSD) for
network I/O. For disk I/O where async matters (like databases), I'd
consider io_uring on Linux 5.1+.
The key insight: match I/O model to workload. CPU-bound work needs
threads. I/O-bound work with many connections needs event-driven."
Q: "How does epoll differ from select?"
Great answer:
"Both monitor multiple file descriptors, but epoll is far more efficient
at scale.
select() problems:
Limited to 1024 fds (FD_SETSIZE)
O(n) kernel scan of ALL fds each call
Must rebuild fd_set after each call
Returns all fds, you check which are ready
epoll() solutions:
No fd limit (just system resources)
O(1) monitoring — kernel maintains interest list
Register once with epoll_ctl(), monitor forever
Only returns READY fds, not all fds
Performance comparison with 10,000 connections:
select: Scan 10,000 fds per call, even if only 1 is ready
epoll: Return immediately with just the 1 ready fd
epoll also supports edge-triggered mode: only notifies on state CHANGE,
not while state IS ready. More efficient but requires draining the buffer
completely each notification.
For any serious server handling more than a few hundred connections,
epoll (or kqueue on macOS/BSD) is essential."
Q: "What is a deadlock and how do you prevent it?"
Great answer:
"A deadlock is when two or more threads are waiting for each other to
release resources, creating a cycle where none can proceed.
Four conditions must ALL be true for deadlock:
Mutual exclusion: Resources can't be shared
Hold and wait: Thread holds one resource while waiting for another
No preemption: Resources can't be forcibly taken
Circular wait: A cycle exists in the wait graph
Prevention strategies break one condition:
Lock ordering: Always acquire locks in the same order globally.
If everyone acquires A before B, no cycle is possible.
Lock timeout: Don't wait forever. Try to acquire, timeout, release
all locks, retry with backoff. Breaks 'no preemption' (the thread
gives up what it holds).
Single lock: Use one coarse-grained lock instead of many fine-grained
ones. Simpler but reduces parallelism.
Lock-free algorithms: Use atomic operations (CAS) instead of locks.
No locks = no deadlock. But complex to implement correctly.
Deadlock detection: Build wait-for graph, detect cycles, abort one
transaction. Used by databases.
In practice, I use a combination:
Lock ordering for related locks
Timeouts for external resources
Careful design to minimize lock scope"
Q: "What's the difference between a mutex and a semaphore?"
Great answer:
"Both are synchronization primitives, but with different semantics:
Mutex (Mutual Exclusion):
Binary: locked or unlocked
Ownership: Thread that locks must unlock
Purpose: Protect critical sections (one thread at a time)
Use case: Protecting shared data structure
Semaphore:
Counting: Can allow N threads (not just 1)
No ownership: Any thread can signal (increment)
Purpose: Control access to limited resources
Use case: Connection pool with max 10 connections
Example differences:
Mutex for protecting a map:
text3 lines
mutex.lock()map[key] = value // Only one thread heremutex.unlock()
Semaphore for connection pool:
text6 lines
sem = Semaphore(10) // Allow 10 concurrentsem.acquire() // Blocks if 10 are already heldconn = pool.get()// use connectionpool.release(conn)sem.release() // Allow another thread in
Binary semaphore (count=1) looks like a mutex but lacks ownership —
any thread can release it. This makes it suitable for signaling between
threads (producer signals consumer) but a poorer fit for protecting critical
sections (no ownership checks, no priority inheritance).
I prefer mutex for protection, semaphore for resource counting."
