Engineer Computer System flashcards

33 cards. Read the term and the definition here. The deck at the top of this page is optional.

Amdahl's Law

Speedup equals 1 divided by ((1 - f) + f/s), where f is the enhanced fraction and s the improvement. The serial portion caps total gain no matter how large s becomes.

CPI

Cycles per instruction, the average number of clock cycles each instruction takes. Execution time equals instruction count times CPI times clock cycle time.

Cache Miss Penalty

The extra time to fetch a block from a lower memory level after a cache miss. Average access time equals hit time plus miss rate times miss penalty.

Write-Back Cache

A policy where writes update only the cache line and set a dirty bit, deferring memory writes until eviction. It lowers memory traffic but needs coherence handling.

Two's Complement Range

For n bits the representable range is -2^(n-1) through 2^(n-1) - 1. Negation inverts every bit and then adds one to the result.

IEEE 754 Single Precision

A 32-bit format with one sign bit, eight exponent bits biased by 127, and 23 fraction bits. Normalized value is (-1)^s times 1.f times 2^(e-127).

De Morgan's Laws

The complement of A AND B equals A' OR B', and the complement of A OR B equals A' AND B'. These identities convert between sum-of-products and product-of-sums forms.

Setup and Hold Time

Setup time requires data stable before a clock edge; hold time requires it stable afterward. Violations cause metastability, and the longest path sets maximum clock frequency.

Belady's Anomaly

A counterintuitive case where adding more page frames increases the number of page faults, observed with FIFO replacement but not with stack algorithms such as LRU.

Thrashing

A condition where processes spend most time paging because their combined working sets exceed physical memory. The remedy is reducing the degree of multiprogramming.

Translation Lookaside Buffer

A small associative cache holding recent virtual-to-physical page translations. A TLB hit avoids a page-table walk; a miss costs one or more memory references.

Coffman Conditions

Four necessary deadlock conditions: mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any single condition prevents deadlock from occurring.

Quicksort Worst Case

Quicksort degrades to O(n^2) when partitions are maximally unbalanced, such as sorted input with a first-element pivot. Randomized or median-of-three pivots avoid this.

Dijkstra's Algorithm

A single-source shortest-path algorithm that repeatedly settles the closest unvisited vertex using a priority queue. It requires non-negative edge weights to remain correct.

Dynamic Programming Conditions

Applicable when a problem has optimal substructure and overlapping subproblems. Memoization solves top-down with caching; tabulation solves bottom-up by filling a table.

Union-Find

A disjoint-set structure supporting near-constant find and union through path compression and union by rank. It underpins Kruskal's minimum spanning tree algorithm.

Dependency Inversion Principle

High-level modules should depend on abstractions rather than concrete implementations, and abstractions should not depend on details. This decouples policy from mechanism.

Test-Driven Development

A cycle of writing a failing test, writing minimal code to pass it, then refactoring. Tests drive design and must be deterministic and independent of execution order.

Git Rebase Versus Merge

Merge joins histories with a merge commit and preserves both branches. Rebase replays commits onto a new base, producing linear history but rewriting commit identifiers.

Third Normal Form

A relation in second normal form with no transitive dependency of a non-key attribute on the key. Every non-key attribute depends only on candidate keys.

ACID Properties

Atomicity makes transactions all-or-nothing, consistency preserves constraints, isolation makes concurrent execution appear serial, and durability keeps committed data after failures.

Covering Index

An index containing every column a query references, so the engine returns results from the index alone without reading table rows, enabling an index-only scan.

CAP Theorem

A distributed data store cannot simultaneously guarantee consistency, availability, and partition tolerance. When a partition occurs, the system must choose consistency or availability.

TCP Three-Way Handshake

The connection opens with SYN, then SYN-ACK, then ACK, synchronizing sequence numbers in both directions. Teardown uses FIN and ACK exchanges for each direction.

TLS Handshake Purpose

It authenticates the server via certificate, negotiates cipher suites, and establishes shared session keys. The result provides confidentiality and integrity for application data.

SQL Injection Defense

Use parameterized queries or prepared statements so user input is bound as data, never concatenated into SQL text. Input validation and least-privilege accounts add defense in depth.

Subnet Host Count

An IPv4 /n prefix leaves 32 minus n host bits, giving 2^(32-n) total addresses and 2^(32-n) minus 2 usable hosts after network and broadcast addresses.

Availability in Nines

99.9 percent availability allows about 8.77 hours downtime yearly, 99.99 percent about 52.6 minutes, and 99.999 percent about 5.26 minutes.

Consistent Hashing

A partitioning scheme placing nodes and keys on a hash ring so that adding or removing a node remaps only a small fraction of keys, unlike modulo hashing.

Token Bucket

A rate limiter holding tokens that refill at a fixed rate. Each request consumes a token, permitting bursts up to bucket capacity while enforcing an average rate.

Idempotent HTTP Methods

Methods whose repeated application yields the same server state: GET, PUT, and DELETE. POST is not idempotent unless a client-supplied request key deduplicates retries.

Copyleft License

A license such as the GPL requiring derivative works distributed publicly to carry the same terms. Permissive licenses like MIT and Apache-2.0 impose no such reciprocity.

GDPR Data Minimization

A principle requiring collection of only personal data adequate and relevant to a stated purpose. It pairs with purpose limitation, storage limitation, and accountability obligations.