Show the route.
Collect the marks.

The OS is a trusted runtime between apps and hardware

As a full-stack developer, imagine the machine as a server whose database is CPU time, memory, devices, and files. Applications are untrusted tenants. The operating system is both the API that gives them useful abstractions and the control plane that stops one tenant from corrupting another.

Program, process, thread: do not merge them

A program is passive code and data in a file. A process is one execution instance with an address space, open-file table, credentials, registers, program counter, and scheduling state. A thread is one execution path inside a process: threads normally share the process address space and files but have their own registers, program counter, and stack.

This distinction explains the process-state diagram. Ready means it has everything except a CPU. Running means a CPU currently executes one of its threads. Blocked means scheduling it would be pointless because it awaits an event such as I/O completion. The event moves it to ready; the scheduler—not the device—later moves it to running.

Three transfers that exam questions deliberately confuse

A mode switch changes privilege level. A context switch changes the executing thread/process and therefore saves/restores registers and scheduler state. A system call can perform only a mode switch; it becomes a context switch if the caller blocks or the scheduler chooses someone else.

Architecture in one causal chain

Von Neumann hardware stores instructions and data behind a shared path. That shared path is the bottleneck. Harvard-style separation permits an instruction fetch and a data access concurrently; modern CPUs commonly present one programmer-visible address space while splitting instruction/data caches close to the core. The memory hierarchy exists because small fast storage is expensive: registers → caches → RAM → SSD/HDD. A miss moves the request down the hierarchy and adds latency.

Time-sharing combines multiprogramming with preemption: a timer interrupt periodically gives the kernel control so it can rotate among ready processes. To a programmer this creates responsive, apparently concurrent processes and prevents a CPU-bound loop from owning the machine forever.

Scheduling is a deterministic simulation, not a picture-guessing task

The scheduler sees a stream of events: a process arrives, a CPU burst finishes, a quantum expires, or a process blocks/unblocks. Its state is the current time, the running process, every remaining burst, and the ready queue. The Gantt chart is merely a log produced from those state transitions.

The paper algorithm that prevents almost every error

1. Write time | running | ready queue | remaining.
2. If the queue is empty, jump time to the next arrival and enqueue it.
3. Choose by the algorithm. Run only until the next event the algorithm cares about.
4. Subtract executed time. Add all arrivals at the event timestamp.
5. For RR, requeue the unfinished process after same-time arrivals under the course convention.
6. Copy the interval to the Gantt chart; repeat until every remaining burst is zero.

FCFS is non-preemptive and preserves arrival order. It is simple but a long job can create a convoy. SPN/SJF chooses the shortest burst among processes already ready and then runs it to completion; it minimizes average waiting time when burst estimates are known, but a long job can wait behind repeated short arrivals. RR limits each visit to quantum q; small q improves responsiveness but increases context-switch overhead.

How variants change the trace

For SRTN, a new arrival can preempt if its remaining time is shorter. For priority scheduling, first state whether a larger or smaller number means higher priority and whether equal priorities use FCFS or RR. For CFS, the conceptual rule is “run the eligible task with the smallest virtual runtime,” not “fixed quantum round robin.”

Linux files make sense when you separate names, objects, and open handles

A directory is not the file object; it is a mapping from a name to an inode number. The inode stores object metadata and block pointers. A path is a sequence of directory lookups. After open(), the process receives a file descriptor: a small integer indexing its table of open handles. That is why deleting or renaming a pathname does not magically invalidate every already-open descriptor.

Permission checks are a decision tree

1. Identify the acting user and supplementary groups.
2. Select exactly one triad: owner if UID matches; otherwise group if any owning group matches; otherwise other. Linux does not combine triads.
3. For every parent directory in a path, require x to traverse it.
4. For the final operation, check the right on the relevant object: file content rights for reading/writing a file; directory w+x for creating, deleting, or renaming entries.

This yields the famous deletion result: deleting dir/file is primarily permission on dir, because deletion removes a directory entry. Conversely, writing the file contents depends on the file’s write bit. The sticky bit can add an ownership restriction in shared directories.

The shell performs a parse-and-wire phase before commands run

For sudo echo hi > protected, the current shell opens protected before launching sudo. Therefore sudo elevates echo, not the redirection. Use echo hi | sudo tee protected when the privileged process must open the file. A pipeline connects stdout of the left command to stdin of the right; each stage has its own exit status, and $? is only the status of the most recently completed command.

Expansion order matters in traces: parse operators → expand variables/quotes/globs → set up redirections and pipes → execute. Single quotes preserve text literally; double quotes allow variables but prevent word splitting and glob expansion of the resulting value.

Hard links and symbolic links

A hard link is another directory entry for the same inode; it normally cannot cross filesystems and survives deletion of another name. A symlink is a distinct inode containing a pathname; it can cross filesystems but can dangle. The object is reclaimed only when its hard-link count is zero and no process still has it open.

A filesystem is an indexing structure plus a crash-consistency policy

Start with the logical question “which object does this pathname name?” The superblock provides filesystem-wide metadata and the root inode. Each directory block maps the next component name to an inode. The final inode supplies metadata and pointers to data blocks. Only then ask what the storage device pays to fetch those blocks.

Allocation strategies express the same trade-off as data structures

Free-space bitmaps spend one bit per block and make runs searchable with word operations. A free list is simple but less convenient for finding a long contiguous run. Internal fragmentation is unused space inside allocated blocks; external fragmentation is free space split into separate gaps.

HDD and SSD formulas represent different physics

Charge a new HDD seek/rotation only when the physical run changes under the problem’s model. Consecutive sectors in one run share the positioning cost. SSDs have no mechanical seek, but separate requests still pay controller/flash latency. Convert kB/MB consistently with the convention supplied by the exercise.

Journaling is not a backup

A journal records intended metadata or data changes before the main structures are committed. After a crash the filesystem replays or rolls back incomplete transactions to restore structural consistency. It does not guarantee that the newest user data survived, and it does not protect against deletion or device failure.

Every memory question follows address → translation → residency → permission

A process behaves as if it owns a private contiguous address space. The MMU translates each virtual address to physical memory under rules installed by the kernel. That indirection gives isolation, relocation, sparse allocation, sharing, and the ability to keep only part of the address space in RAM.

Address translation by hand

1. From page size, determine offset bits. For 4 KiB, offset = 12 bits = last three hexadecimal digits.
2. Split virtual address into virtual page number and offset.
3. Index the page table; inspect present/valid and access permissions.
4. If resident and permitted, replace the page number with the frame number and preserve the offset unchanged.
5. If absent, report page fault; if prohibited, report protection fault. Do not invent a physical address.

Dynamic base/limit relocation is the simpler version: first require 0 ≤ VA < limit, then compute PA = base + VA. The limit is a size/bound, not the largest valid physical address.

Effective access time is a probability tree

Write mutually exclusive paths and make their probabilities sum to one. Conditional miss rates multiply: an L2 cost is paid only on an L1 miss; a memory cost only on all preceding misses. Every request pays the first lookup, which is why the nested form is safer than listing vague “hit times.”

Replacement algorithms differ only in victim policy

On a hit, update policy state but do not replace a frame. On a fault with a free frame, fill it. Otherwise choose a victim: FIFO evicts oldest load; LRU evicts least recently used; OPT evicts the page used farthest in the future; NFU evicts the lowest accumulated reference count; aging right-shifts history and inserts the latest reference bit at the most significant position; clock gives referenced pages a second chance by clearing R=1 until it finds R=0.

OPT is a benchmark because it needs future knowledge. NFU can remember ancient popularity forever; aging fixes this by discounting old references. More frames do not guarantee fewer FIFO faults (Belady’s anomaly), while stack algorithms such as LRU and OPT do not show that anomaly.

Separate “push bits” from “move the signal”

Transmission delay is the time to serialize L bits onto a link of rate R: L/R. Propagation delay is how long the signal travels distance d at speed v: d/v. A faster link reduces serialization but does not make the signal propagate faster. Processing is device work; queuing is waiting behind earlier traffic.

Use a delay ledger

For a simple symmetric request/response, RTT is twice the stated one-way path only if the return has the same components. If the problem already gives RTT, do not double it. For store-and-forward routers, a complete packet may need serialization on every link; for cut-through or idealized questions, follow the stated model.

Throughput is useful data divided by elapsed time

Bandwidth-delay product is the amount of data that fills the path, not a time. Its units are bits. To convert it to complete packets, divide by packet size in bits and floor. Do not multiply by two when RTT is already round-trip.

Jitter is variation in delay. The course exercise uses mean absolute deviation, so state that definition and follow it even though other sources use different jitter estimators. Loss is sent minus delivered over sent. Real-time voice usually values low jitter and delay; bulk transfer values throughput; safety/control traffic may prioritize loss/reliability.

Topology questions ask “what fails, how far, and at what cost?”

Replace the drawing with an undirected graph unless the problem says otherwise. Vertices are devices; edges are links. Degree counts incident links. Shortest path is the fewest links between two vertices. Diameter is the worst shortest-path length over all pairs. Connectivity is the smallest number of vertices or edges whose removal disconnects the graph—state which kind the question uses. A graph is regular if every vertex has the same degree.

Do not infer connectivity from degree alone unless you can prove it. The exam-safe method is constructive: show that fewer removals cannot disconnect, then exhibit a set of the claimed size that does.

Router versus switch in one precise contrast

A switch normally forwards frames inside a layer-2 broadcast domain using MAC addresses learned from source frames. A router forwards packets between IP networks using a routing table and decrements TTL/Hop Limit. A router replaces the link-layer frame at every hop; the destination IP normally remains end-to-end unless NAT rewrites it.

OSI questions are easier when you ask “which object owns this function?”

Flow control protects a receiver from a sender that is too fast. Congestion control protects the network from too much offered traffic. They can coexist in TCP but answer different questions.

The physical layer encodes symbols; the link layer frames a local conversation

A receiver does not see abstract 0s and 1s. It samples voltage, light, or radio symbols and must know when to sample. A line code maps bits to signal levels/transitions and can provide clock information. Mark bit-cell boundaries first; then apply the course convention mechanically.

NRZ-L uses a level per bit and can lose synchronization on long constant runs. Manchester forces a mid-bit transition, improving clock recovery at the cost of more signal changes/bandwidth. 4B/5B maps each four-bit nibble to a five-bit code chosen to limit long runs; it is block coding, not the final electrical waveform.

Frames add local addressing and error detection

Ethernet wraps payload in a frame containing destination/source MAC addresses, an EtherType/length interpretation, and a frame check sequence. A switch learns the source MAC → incoming port mapping and uses the destination MAC to forward or flood. The FCS detects corruption; ordinary Ethernet does not itself provide end-to-end retransmission.

The first 24 bits of a globally administered MAC address form the organizationally unique identifier (OUI). A MAC address identifies an interface on a local link; it is not a routable global path. ARP/neighbor discovery bridges the question “which local MAC currently owns this next-hop IP?”

Drawing recipe

1. Copy the bit string and draw equal-width cells.
2. Write the convention: e.g. Manchester 0 = low→high, 1 = high→low.
3. Draw the mid-cell transition for every Manchester bit and any boundary transition implied by adjacent cells.
4. For 4B/5B, split into nibbles, show each table lookup, concatenate, and label it encoded bits—not voltage.

A prefix fixes the left bits and leaves a power-of-two address block

In IPv4 a.b.c.d/p, the first p bits identify the network and the remaining 32−p bits vary inside the block. The network address has all host bits zero; the broadcast has all host bits one. Traditional usable-host exercises subtract those two endpoints.

The changing-octet shortcut

1. Convert the prefix to a dotted mask or identify the octet where network bits stop.
2. Block size = 256 − mask value in that octet.
3. Find the greatest block multiple not exceeding the IP octet: that is the network boundary.
4. Broadcast boundary = network + block − 1; earlier octets stay fixed and later octets become 255.
5. Write network, broadcast, and usable range separately.

VLSM is memory allocation with alignment

Sort host requirements largest first. For each, choose the smallest power-of-two block that fits the required usable hosts, convert it to a prefix, and allocate at an address divisible by that block size. Packing small blocks first can strand a large aligned region—exactly like heap fragmentation.

Longest-prefix routing

1. Include directly connected networks and a default route if supplied.
2. For the destination, test every row: (IP AND mask) == network.
3. Among all matches, choose the largest prefix length.
4. Report the next hop/interface; if directly connected, say so instead of inventing a gateway.

TTL/Hop Limit prevents loops. Each router decrements it; traceroute deliberately sends probes with values 1, 2, 3… and observes ICMP Time Exceeded replies. Path MTU discovery sets DF, reacts to “too big/fragmentation needed,” and reduces packet size.

IPv6: what changed and why

IPv6 expands addresses to 128 bits and uses a fixed 40-byte base header. It removes the base-header checksum and router fragmentation, moves optional features to extension headers, renames TTL to Hop Limit, and uses Next Header to identify an extension or upper-layer protocol. Intermediate routers do less per-packet work; sources handle fragmentation when necessary.

UDP sends messages; TCP maintains a byte-stream state machine

IP delivers packets to a host interface. A transport protocol and port identify the application endpoint. UDP preserves datagram boundaries and adds ports, length, and checksum with no connection setup or built-in ordering/retransmission. TCP exposes an ordered reliable byte stream, so it must establish state, number bytes, acknowledge progress, retransmit loss, and control how much data is in flight.

Handshake and sequence arithmetic

Each side chooses an initial sequence number. SYN x consumes sequence number x; the peer replies SYN+ACK y, ack x+1; the initiator acknowledges ack y+1. ACK always means the next byte expected. If 400 bytes begin at sequence 1001, the next expected byte is 1401. FIN also consumes one sequence number.

The three-way handshake proves both directions work and synchronizes both initial sequence spaces. Two messages cannot confirm that the responder received the initiator’s acknowledgement of the responder’s sequence number.

Sliding window: three regions, one invariant

At the sender, bytes left of ACK are acknowledged; bytes already sent but at or right of ACK are in flight; later bytes inside the advertised window may be sent now. The right edge is ACK + rwnd − 1. Usable capacity is advertised window minus in-flight bytes. Duplicate ACKs do not move the left edge.

Flow control uses the receiver-advertised window to protect receiver buffers. Congestion control separately estimates what the network can carry. The actual sending limit is constrained by both.

DNS resolves names through delegated authority

The client asks a recursive resolver. On a cache miss, the resolver follows referrals from a root server to a TLD server to the authoritative server, returns the record, and caches it for its TTL. Common records: A (IPv4), AAAA (IPv6), CNAME (alias), MX (mail exchanger), NS (authoritative server), PTR (reverse lookup). Reverse IPv4 lookup reverses octets under in-addr.arpa.

DHCP bootstraps configuration before the client has an address

DORA = Discover, Offer, Request, Acknowledge. Discover and Request are normally broadcast in the basic scenario because the client initially lacks usable IP configuration and wants all servers to see which offer it selected. The ACK supplies the lease plus options such as mask, router, and DNS server. Transaction ID and client hardware address correlate messages.

Encapsulation answers “which address changes where?”

Application data → TCP/UDP segment (ports) → IP packet (end-to-end logical addresses) → link frame (next-hop MAC addresses) → signal. At a router, the incoming frame ends; the router decrements TTL/Hop Limit, chooses the next hop, and creates a new outgoing frame. NAT may additionally rewrite IP addresses and ports while storing a translation-table entry.