Why can two-phase commit block?

A participant that has voted YES must preserve its prepared state until it learns the decision. If the coordinator fails and no accessible participant can establish that decision, it may have to wait for recovery, retaining resources such as locks. Blocking is possible, not inevitable after every coordinator failure.

How does a mutex differ from a counting semaphore?

A mutex provides ownership-based mutual exclusion: its owning thread must release it. A counting semaphore has no such ownership rule; waiting consumes a permit and posting adds one. With N initial permits and balanced acquisition/release, it can limit simultaneous resource users to N.

What does the PACELC framework add to CAP?

If a partition occurs (P), consider the availability-versus-consistency tradeoff (A/C). Else (E), consider latency versus consistency (L/C), especially when replicas coordinate. PACELC is a framework for discussing design choices, not a claim that every operation has one fixed universal tradeoff.

What does CAP require a replicated data service to trade off during a network partition?

It cannot guarantee both linearizable reads/writes and successful completion of every request to a nonfailed node. To preserve linearizability, some requests may have to wait or fail; to keep serving across the partition, some consistency guarantee must be weakened. CAP is not an unrestricted “choose any two” rule for normal operation.

Why can a page fault occur, and how may the operating system handle it?

A memory access faults when its translation is not present or its permissions do not allow the access. A valid access may need lazy allocation, copy-on-write, or a page read from a file or swap; the OS updates the mapping and retries the instruction. An invalid access instead raises an error, often a process signal. Not every fault requires disk I/O.

How can a global lock order prevent circular-wait deadlock?

Assign locks a consistent strict order and require every thread to acquire them only in increasing order while holding other locks. A cycle would require an order to increase and return to its starting point, which is impossible. Every relevant acquisition path must follow the rule.

How do a process and a thread differ in a typical operating system?

A process is a resource and protection container with its own virtual address space. Threads within it share that address space and resources such as open files, but each has its own execution state, including registers, program counter and stack. Separate processes can explicitly share memory.

What is a cache stampede, and how can it be mitigated?

Many requests miss the same expired or absent cache item and recompute or fetch it simultaneously, overloading the backing service. Per-key request coalescing, correctly managed locks, or early/probabilistic refresh can reduce the burst. Their effectiveness depends on timing and failure handling.

How do TCP and UDP differ in the service they provide?

TCP provides a connection-oriented, reliable, ordered byte stream with retransmission, flow control and congestion control; a connection can still fail. UDP preserves datagram boundaries but provides no built-in delivery, ordering or retransmission guarantee. An application using UDP may add those mechanisms itself.

What is a race condition, and why does a critical section need synchronization?

A race condition occurs when correctness depends on the timing or interleaving of concurrent operations. A critical section accesses shared state whose invariants must be protected. Mutual exclusion is a common way to ensure that only one thread executes the relevant section at a time.

What are the messages in an ordinary TCP three-way handshake with no data?

The client sends SYN with initial sequence number x. The server sends SYN+ACK with sequence number y and acknowledgment x+1. The client sends ACK acknowledging y+1. Each SYN consumes one sequence number; a pure ACK does not.

How does HTTP/2 multiplex requests, and what head-of-line blocking can remain?

HTTP/2 interleaves binary frames from separate streams on one TCP connection and compresses field sections with HPACK. This avoids the ordered-response constraint of HTTP/1.1 pipelining. TCP still delivers bytes in order, so a lost TCP segment can delay data for several streams.

What are the seven OSI layers and the common four TCP/IP layers, from bottom to top?

OSI: Physical, Data Link, Network, Transport, Session, Presentation, Application. The common four-layer TCP/IP model: Link, Internet, Transport, Application. These are different architectural models, so their layers do not correspond exactly one for one.

What do the closed, open and half-open states of a circuit breaker do?

Closed allows calls and tracks failures. Open rejects calls quickly after the configured failure threshold is reached. After a delay, half-open permits limited probe calls: recovery closes the breaker, while renewed failures reopen it. The pattern limits repeated calls to a failing service; it does not repair that service.

How does HTTP/3 over QUIC reduce transport head-of-line blocking?

QUIC carries independent reliable streams over UDP, so missing data in one stream need not block delivery on another. Loss recovery and congestion control still operate across the connection. QUIC supports a one-round-trip handshake and, for eligible resumed connections, optional replay-sensitive 0-RTT data.

How does Raft elect a leader, and what do randomized election timeouts accomplish?

After an election timeout, a follower becomes a candidate, advances its term, votes for itself and requests votes. A candidate needs a majority; each server grants at most one vote per term and checks log freshness. Randomized timeouts reduce repeated split votes, but do not guarantee that every election succeeds.

Which four Coffman conditions are necessary for resource deadlock?

Mutual exclusion, hold-and-wait, no preemption, and circular wait. In the classical reusable-resource model, breaking any one prevents this kind of deadlock. Allowing these conditions does not mean that every execution must deadlock.

How do TCP’s receive window rwnd and congestion window cwnd constrain sending?

The receiver advertises rwnd to limit data it is ready to accept; the sender maintains cwnd to limit network load. In normal operation, outstanding unacknowledged data is bounded by min(rwnd, cwnd). They address receiver capacity and network congestion, respectively.

What is Raft’s log-matching property, and how are conflicting follower logs repaired?

If two logs have entries with the same index and term, their prefixes through that index are identical. AppendEntries checks the preceding index and term; the leader retries until it finds a matching prefix, then conflicting follower entries are replaced by the leader’s entries. Correct Raft never discards committed entries.

What mechanisms secure a typical certificate-authenticated TLS 1.3 connection?

Certificate validation and handshake signatures authenticate the peer; ephemeral (EC)DHE establishes shared key material; AEAD protects application data’s confidentiality and integrity. TLS 1.3 also supports pre-shared-key modes, so certificates and forward secrecy must not be assumed for every mode or for 0-RTT data.

What does eventual consistency promise, and what role do conflict mechanisms play?

If updates stop and updates or repairs can eventually reach the replicas, they should converge under the system’s reconciliation rules. Vector clocks detect causal ordering and concurrent versions; they do not resolve conflicts by themselves. Compatible CRDT merges or deterministic policies such as last-write-wins can reconcile state, though last-write-wins can discard updates.

What are the prepare and decision phases of two-phase commit (2PC)?

Each participant votes YES only after durably preparing, or votes NO if it cannot commit. The coordinator durably records COMMIT only after all vote YES; otherwise it may decide ABORT before any commit decision. It then communicates the decision. A timeout after a participant has prepared is not permission for that participant to abort unilaterally.

How does ring-based consistent hashing reduce remapping when nodes change?

Hash keys and nodes onto a ring and assign each key to its next node clockwise. Adding a node splits an interval; removing one transfers its interval to its successor. With reasonably uniform placement, changing one of N nodes remaps an expected O(K/N) of K keys, not a worst-case guarantee; virtual nodes improve balance.

Why does the active closer normally enter TCP TIME-WAIT for twice the maximum segment lifetime?

TIME-WAIT lets it acknowledge a retransmitted FIN if the final ACK was lost, and lets old segments expire before the same connection identifiers are reused. The usual interval is 2×MSL. This supports safe connection closure; it is not a guarantee that an ACK can never be lost.

What is Belady’s anomaly, and why does LRU avoid it?

For the same page-reference sequence, some replacement policies such as FIFO can incur more page faults when given more frames. LRU has the stack property: the pages held with N frames are a subset of those held with N+1 frames. Increasing its frame allocation therefore cannot increase faults for that sequence.

How does round-robin scheduling use a time quantum, and what is the tradeoff?

Each runnable task gets up to one quantum before moving to the back of the ready queue; it may block, yield or finish earlier. Short quanta improve responsiveness but increase switching overhead. If quanta exceed CPU bursts, behavior approaches first-come, first-served scheduling.

How do slow start and congestion avoidance grow cwnd in the classic RFC 5681 TCP model?

Below the slow-start threshold, ACK-driven growth is roughly exponential and can approximately double cwnd per round trip. In congestion avoidance, growth is roughly one maximum-sized segment per round trip. ACK behavior affects growth; other TCP congestion-control algorithms need not follow this exact pattern.

What are paging and a translation lookaside buffer (TLB)?

Paging maps virtual memory pages to physical page frames using page tables. A TLB caches recent address translations and associated access information, reducing page-table lookups. Systems may support several page sizes; the TLB caches translations, not the pages’ data.

What state is saved and restored during a CPU context switch?

The operating system preserves the outgoing task’s execution state, such as registers, program counter and stack pointer, and restores the incoming task’s state. Address-space state is changed when needed; switching between threads of one process need not change the page-table root. Exact saved state depends on the architecture and implementation.

How does the cache-aside pattern handle a read?

The application checks the cache. On a hit it returns the cached value; on a miss it reads the backing store, populates the cache and returns the value. Expiration and invalidation policies are still needed because cached data can become stale.

How do write-through and write-behind caching differ?

Write-through completes the backing-store write as part of the write operation before acknowledging success. Write-behind acknowledges a cache update and writes to the store later, reducing immediate write latency. Pending writes can be lost on failure unless protected durably; durability depends on the system, not just the pattern’s name.

How is an ordinary uncached DNS name lookup resolved?

A client asks a recursive resolver. If needed, that resolver follows referrals from a root server to a top-level-domain server and then an authoritative server, obtaining records such as A or AAAA. It returns the answer and may cache it for its TTL; cached referrals or answers can skip some steps.

Operating Systems, Concurrency, Networking Protocols & Distributed Systems

Review 32 university-level systems concepts: processes, concurrency and virtual memory; TCP, DNS, HTTP and TLS; and distributed consensus, transactions and caching. Assumes basic programming and computer-network knowledge. Protocol versions and failure assumptions are explained where relevant.

Level: advanced
Languages: en → en
Cards: 32
Markdown: Operating Systems, Concurrency, Networking Protocols & Distributed Systems (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Why can two-phase commit block?	A participant that has voted YES must preserve its prepared state until it learns the decision. If the coordinator fails and no accessible participant can establish that decision, it may have to wait for recovery, retaining resources such as locks. Blocking is possible, not inevitable after every coordinator failure.
2	How does a mutex differ from a counting semaphore?	A mutex provides ownership-based mutual exclusion: its owning thread must release it. A counting semaphore has no such ownership rule; waiting consumes a permit and posting adds one. With N initial permits and balanced acquisition/release, it can limit simultaneous resource users to N.
3	What does the PACELC framework add to CAP?	If a partition occurs (P), consider the availability-versus-consistency tradeoff (A/C). Else (E), consider latency versus consistency (L/C), especially when replicas coordinate. PACELC is a framework for discussing design choices, not a claim that every operation has one fixed universal tradeoff.
4	What does CAP require a replicated data service to trade off during a network partition?	It cannot guarantee both linearizable reads/writes and successful completion of every request to a nonfailed node. To preserve linearizability, some requests may have to wait or fail; to keep serving across the partition, some consistency guarantee must be weakened. CAP is not an unrestricted “choose any two” rule for normal operation.
5	Why can a page fault occur, and how may the operating system handle it?	A memory access faults when its translation is not present or its permissions do not allow the access. A valid access may need lazy allocation, copy-on-write, or a page read from a file or swap; the OS updates the mapping and retries the instruction. An invalid access instead raises an error, often a process signal. Not every fault requires disk I/O.
6	How can a global lock order prevent circular-wait deadlock?	Assign locks a consistent strict order and require every thread to acquire them only in increasing order while holding other locks. A cycle would require an order to increase and return to its starting point, which is impossible. Every relevant acquisition path must follow the rule.
7	How do a process and a thread differ in a typical operating system?	A process is a resource and protection container with its own virtual address space. Threads within it share that address space and resources such as open files, but each has its own execution state, including registers, program counter and stack. Separate processes can explicitly share memory.
8	What is a cache stampede, and how can it be mitigated?	Many requests miss the same expired or absent cache item and recompute or fetch it simultaneously, overloading the backing service. Per-key request coalescing, correctly managed locks, or early/probabilistic refresh can reduce the burst. Their effectiveness depends on timing and failure handling.
9	How do TCP and UDP differ in the service they provide?	TCP provides a connection-oriented, reliable, ordered byte stream with retransmission, flow control and congestion control; a connection can still fail. UDP preserves datagram boundaries but provides no built-in delivery, ordering or retransmission guarantee. An application using UDP may add those mechanisms itself.
10	What is a race condition, and why does a critical section need synchronization?	A race condition occurs when correctness depends on the timing or interleaving of concurrent operations. A critical section accesses shared state whose invariants must be protected. Mutual exclusion is a common way to ensure that only one thread executes the relevant section at a time.
11	What are the messages in an ordinary TCP three-way handshake with no data?	The client sends SYN with initial sequence number x. The server sends SYN+ACK with sequence number y and acknowledgment x+1. The client sends ACK acknowledging y+1. Each SYN consumes one sequence number; a pure ACK does not.
12	How does HTTP/2 multiplex requests, and what head-of-line blocking can remain?	HTTP/2 interleaves binary frames from separate streams on one TCP connection and compresses field sections with HPACK. This avoids the ordered-response constraint of HTTP/1.1 pipelining. TCP still delivers bytes in order, so a lost TCP segment can delay data for several streams.
13	What are the seven OSI layers and the common four TCP/IP layers, from bottom to top?	OSI: Physical, Data Link, Network, Transport, Session, Presentation, Application. The common four-layer TCP/IP model: Link, Internet, Transport, Application. These are different architectural models, so their layers do not correspond exactly one for one.
14	What do the closed, open and half-open states of a circuit breaker do?	Closed allows calls and tracks failures. Open rejects calls quickly after the configured failure threshold is reached. After a delay, half-open permits limited probe calls: recovery closes the breaker, while renewed failures reopen it. The pattern limits repeated calls to a failing service; it does not repair that service.
15	How does HTTP/3 over QUIC reduce transport head-of-line blocking?	QUIC carries independent reliable streams over UDP, so missing data in one stream need not block delivery on another. Loss recovery and congestion control still operate across the connection. QUIC supports a one-round-trip handshake and, for eligible resumed connections, optional replay-sensitive 0-RTT data.
16	How does Raft elect a leader, and what do randomized election timeouts accomplish?	After an election timeout, a follower becomes a candidate, advances its term, votes for itself and requests votes. A candidate needs a majority; each server grants at most one vote per term and checks log freshness. Randomized timeouts reduce repeated split votes, but do not guarantee that every election succeeds.
17	Which four Coffman conditions are necessary for resource deadlock?	Mutual exclusion, hold-and-wait, no preemption, and circular wait. In the classical reusable-resource model, breaking any one prevents this kind of deadlock. Allowing these conditions does not mean that every execution must deadlock.
18	How do TCP’s receive window rwnd and congestion window cwnd constrain sending?	The receiver advertises rwnd to limit data it is ready to accept; the sender maintains cwnd to limit network load. In normal operation, outstanding unacknowledged data is bounded by min(rwnd, cwnd). They address receiver capacity and network congestion, respectively.
19	What is Raft’s log-matching property, and how are conflicting follower logs repaired?	If two logs have entries with the same index and term, their prefixes through that index are identical. AppendEntries checks the preceding index and term; the leader retries until it finds a matching prefix, then conflicting follower entries are replaced by the leader’s entries. Correct Raft never discards committed entries.
20	What mechanisms secure a typical certificate-authenticated TLS 1.3 connection?	Certificate validation and handshake signatures authenticate the peer; ephemeral (EC)DHE establishes shared key material; AEAD protects application data’s confidentiality and integrity. TLS 1.3 also supports pre-shared-key modes, so certificates and forward secrecy must not be assumed for every mode or for 0-RTT data.
21	What does eventual consistency promise, and what role do conflict mechanisms play?	If updates stop and updates or repairs can eventually reach the replicas, they should converge under the system’s reconciliation rules. Vector clocks detect causal ordering and concurrent versions; they do not resolve conflicts by themselves. Compatible CRDT merges or deterministic policies such as last-write-wins can reconcile state, though last-write-wins can discard updates.
22	What are the prepare and decision phases of two-phase commit (2PC)?	Each participant votes YES only after durably preparing, or votes NO if it cannot commit. The coordinator durably records COMMIT only after all vote YES; otherwise it may decide ABORT before any commit decision. It then communicates the decision. A timeout after a participant has prepared is not permission for that participant to abort unilaterally.
23	How does ring-based consistent hashing reduce remapping when nodes change?	Hash keys and nodes onto a ring and assign each key to its next node clockwise. Adding a node splits an interval; removing one transfers its interval to its successor. With reasonably uniform placement, changing one of N nodes remaps an expected O(K/N) of K keys, not a worst-case guarantee; virtual nodes improve balance.
24	Why does the active closer normally enter TCP TIME-WAIT for twice the maximum segment lifetime?	TIME-WAIT lets it acknowledge a retransmitted FIN if the final ACK was lost, and lets old segments expire before the same connection identifiers are reused. The usual interval is 2×MSL. This supports safe connection closure; it is not a guarantee that an ACK can never be lost.
25	What is Belady’s anomaly, and why does LRU avoid it?	For the same page-reference sequence, some replacement policies such as FIFO can incur more page faults when given more frames. LRU has the stack property: the pages held with N frames are a subset of those held with N+1 frames. Increasing its frame allocation therefore cannot increase faults for that sequence.
26	How does round-robin scheduling use a time quantum, and what is the tradeoff?	Each runnable task gets up to one quantum before moving to the back of the ready queue; it may block, yield or finish earlier. Short quanta improve responsiveness but increase switching overhead. If quanta exceed CPU bursts, behavior approaches first-come, first-served scheduling.
27	How do slow start and congestion avoidance grow cwnd in the classic RFC 5681 TCP model?	Below the slow-start threshold, ACK-driven growth is roughly exponential and can approximately double cwnd per round trip. In congestion avoidance, growth is roughly one maximum-sized segment per round trip. ACK behavior affects growth; other TCP congestion-control algorithms need not follow this exact pattern.
28	What are paging and a translation lookaside buffer (TLB)?	Paging maps virtual memory pages to physical page frames using page tables. A TLB caches recent address translations and associated access information, reducing page-table lookups. Systems may support several page sizes; the TLB caches translations, not the pages’ data.
29	What state is saved and restored during a CPU context switch?	The operating system preserves the outgoing task’s execution state, such as registers, program counter and stack pointer, and restores the incoming task’s state. Address-space state is changed when needed; switching between threads of one process need not change the page-table root. Exact saved state depends on the architecture and implementation.
30	How does the cache-aside pattern handle a read?	The application checks the cache. On a hit it returns the cached value; on a miss it reads the backing store, populates the cache and returns the value. Expiration and invalidation policies are still needed because cached data can become stale.
31	How do write-through and write-behind caching differ?	Write-through completes the backing-store write as part of the write operation before acknowledging success. Write-behind acknowledges a cache update and writes to the store later, reducing immediate write latency. Pending writes can be lost on failure unless protected durably; durability depends on the system, not just the pattern’s name.
32	How is an ordinary uncached DNS name lookup resolved?	A client asks a recursive resolver. If needed, that resolver follows referrals from a root server to a top-level-domain server and then an authoritative server, obtaining records such as A or AAAA. It returns the answer and may cache it for its TTL; cached referrals or answers can skip some steps.