Notes on Modern Operating Systems, Chapter 2, Part 2: Interprocess Communication

Notes on the second part of Chapter 2 of Modern Operating Systems, on interprocess communication. These sections cover the basic ideas of mutual exclusion and coordination of concurrent processes. There wasn’t a ton in this section I hadn’t seen before, but it was a good refresher and a good chance to nail down some of the terminology.


2.3 Interprocess Communication

Three issues to consider in interprocess communication:

  1. Passing information between processes
  2. Preventing concurrent processes from interfering with each other
  3. Sequencing of dependency acquisition

2) and 3) also apply to threads. 1) less so because threads can share memory.

2.3.1 Race Conditions

  • A race condition occurs when two processes are reading or writing shared data and the result depends on the order of execution.
  • The shared data can be in memory, a file, a directory, whatever.

2.3.2 Critical Regions

  • Need mutual exclusion to lock other processes out of shared data when it’s being used.
  • The part of the program that uses the shared data, requiring mutual exclusion, is called the critical region.
  • If you ensure that two processes are never executing the critical region at the same time, you can avoid race conditions.

Four conditions must hold for a good solution to this:

  1. No two processes are simultaneously in the critical region.
  2. No assumptions may be made about speed of processes or the number of CPUs.
  3. No process outside its critical region should be able to block other processes.
  4. No process should have to wait forever to enter its critical region.

2.3.3 Mutual Exclusion with Busy Waiting

In practice busy waiting is rarely useful, so I’m not going to write down any notes about it, but the book lists several bad solutions for mutual exclusion using busy waiting and goes over how they introduce race conditions and other badness.

A loop that runs doing nothing to implement busy waiting is called a spin lock.

The one useful thing the section covers is the TSL (test-and-set-lock) instruction, which is a CPU instruction that atomically sets and checks a lock variable. This instruction is useful in other, less terrible kinds of mutual exclusion.

2.3.4 Sleep and Wakeup

Want to get rid of busy waiting.

Producer-Consumer Problem

  • We’ll use this problem as an example for the mutual exclusion techniques we’re about to discuss.
  • Two processes share a fixed-size buffer
  • One process produces things and puts them on the buffer.
  • The other consumes things from the buffer and does something with them.
  • Access to the shared buffer must be carefully managed.
  • Conceptually, we want the producer to sleep when the buffer is full and wake up and add things to it when there is space. Conversely, we want the consumer to sleep when the buffer is empty and wake up and take things from it when it is not empty.

2.3.5 Sempahores

  • One way to achieve sleep and wakeup is with semaphores.
  • A semaphore is an integer variable that supports two operations: up and down.
  • down decrements the semaphore. If the semaphore is zero, the process that called down blocks until the semaphore is no longer zero.
  • up increments the semaphore.
  • Semaphores can represent “tickets” or “passes” to do a specific operation.
  • You can use them like this to synchronize two processes, imposing a certain ordering on their actions.
  • For example, in the producer-consumer problem, you can use empty and full semaphores to track how many spaces are empty and full in the buffer.
  • Then you can force the consumer to do a down on full so that it blocks when there’s on the buffer to take, and force the producer to do a down on empty so that it blocks when there’s no space for it to add to the buffer.
  • This assures that consumption only happens after production and production only proceeds to a certain point before some consumption happens.

2.3.6 Mutexes

  • A mutex is another way of using a semaphore. It only has the values 0 and 1.
  • If the value is 1, processes can enter the critical region. If 0, they block on trying to enter the critical region.
  • If your processor has a TSL instruction, you can implement mutex locking and unlocking in user space.
  • Importantly, this means you can implement mutexes so that when a thread blocks on a mutex, the thread can yield the CPU before blocking.
  • Most modern OSes allow limited sharing of memory between processes, which allows mutex sharing.

2.3.7 Monitors

  • A collection of variables and functions that guarantee only a single thread at once can access them.
  • Monitors are a programming language-specific feature. The compiler handles mutual exclusion, often using a mutex or semaphore under the hood.
  • Monitors still need a way to block processes that can’t proceed anymore so that another process can start using the monitor. They do this with…

Condition Variables

  • Two operations: wait and signal.
  • If a process can’t continue, it waits on a condition variable and blocks.
  • Then another process can enter the monitor and wake up the sleeping process by doing a signal on the condition variable.
  • You can either immediately suspend the signaling process, resuming it later, and let the awakened process run; or you can require a signal to be the last thing in a function.
  • Without the monitor’s guarantee of only one process running the code at once, wait and signal are subject to race conditions where signals cross and wakeup signals disappear into the void just as a process is about to go to sleep, causing them to never wake up.

Java objects can also be used as monitors with the synchronized keyword and the wait and notifyAll methods. This combined with threads is the basis for all Java concurrency.

2.3.8 Message Passing

  • Semaphores and monitors require shared memory, so they can’t be used in distributed systems.
  • Message passing, on the other hand, is more general and works even across machines.
  • Uses two operations: send and receive. These are implemented as system calls.
  • send gets a process ID and a message.
  • receive also gets a process ID and in C implementations it gets passed an empty message to hydrate.
  • A receiver can block until a message arrives, or return immediately with an error code.

Message passing raises several design challenges.

  • Messages can be lost by the network. You can have receivers send back an acknowledgment signal, and have senders retry the message if they don’t get it after a certain timeout.
  • Local message passing is slower than semaphores or monitors.
  • You can implement message passing with a mailbox that buffers received messages, or you can have threads block and wait on each other. The latter is called a rendezvous.

2.3.9 Barriers

  • Block a group of processes all at the same point in the program to coordinate their start on the next phase.

2.4 Classical IPC Problems

These are all well-known and there’s a ton of information out there on them, so I didn’t take detailed notes about them.

2.4.1 Dining Philosophers

Models a situation where there is possible contention for a set of shared resources, which can lead to possible deadlocks or starvation.

2.4.2 Readers and Writers

A simplistic model of a database, where multiple concurrent processes can read but only one can write at a time.

2.4.3 Sleeping Barber

Models a situation where a bounded size queue of tasks is being serviced by a single process but filled by multiple processes.

Notes on Modern Operating Systems, Chapter 2, Part 1: Processes and Threads

These are my notes on Chapter 2, Sections 2.1 and 2.2 of Modern Operating Systems, Second Edition, by Andrew Tanenbaum. The chapter is quite long, and dense with text, so I’m splitting my notes into three parts. Part 1, this part, is the basics of processes and threads. Part 2 will be Sections 2.3 and 2.4 on interprocess communication and concurrency control. Part 3 will be Section 2.5 on scheduling.

As with Computer Networking: A Top-Down Approach, I bought an old edition of this book for cheap about six years ago and happened to have it laying around. The second edition is from the year 2000, so it’s now twenty years old and somewhat out of date. But operating systems haven’t changed as much in twenty years as the Internet has, so although some of the chapters talk as if single-core processors are still the status quo, and the Case Studies section in the back talks about Windows 2000, I’ve yet to stumble on anything that makes me suspicious.

The writing style is clear, but the sections aren’t always the best organized and sometimes make references to material that hasn’t been covered yet. Partly that’s just inherent to the way operating system concepts all connect into a whole, so although it does bother me a little, it was a reasonable choice. If you can find a newer edition for under fifty dollars it might be worth picking up. There are a couple sections towards the end of the book where Tanenbaum talks about his work on MINIX and his opinions on Linux and Linus Torvalds that read like aggrieved Usenet posts cleaned up for publication, and he also constantly dunks on other people’s research, writing in Chapter 3 that research on distributed deadlock detection is not “even remotely practical in real systems” and that its “main function seems to be keeping otherwise unemployed graph theorists off the streets”. I find it highly amusing, not least because Tanenbaum must have known that the undergraduate students who would mostly be reading this book didn’t care.

Section 2.1 Processes

  • Processes pretend to run sequentially, but behind they scenes they run discontinuously as the CPU swaps between them.
  • Each process maintains its own logical program counter which is loaded into the real program counter when the CPU picks it up to run.
  • Run order and run time of processes might be non-deterministic, so you cannot make any assumptions about when processes will run or how long they will run for.

2.1.1 Process Creation

Four events cause process creation:

  1. System initialization
  2. System call by a running process (fork on Unix).
  3. User request to create a process (e.g. running a terminal command, clicking an icon).
  4. Batch job initialization (on mainframes, submitted by users).
  • fork on Unix creates new processes.
    • The child process starts with the same memory, environment strings, and open files as its parent.
    • Then it runs execve or some similar system call to change the memory image and run a new program.
    • The child’s memory image is a copy of the parent’s into a new address space. Children do not share address spaces with their parents, so the parent and child cannot access each other’s memory.

2.1.3 Process Destruction

Processes can terminate for the following reasons:

  1. Normal exit (voluntary), triggered on Unix by the exit system call
  2. Error exit (voluntary), e.g. program cannot finish, such as compiler called on nonexistent file
  3. Fatal error (involuntary), e.g. divide by zero error, attempt to access protected memory (null pointer dereference in C)
  4. Murder by another process (involuntary), e.g. someone calls kill on it.

2.1.4 Process Hierarchies

  • Do not exist on Windows.
  • On Unix a process and its descendants form a group. Process groups share some signals and other things.
  • Since all processes on Unix are children of the init process, there is also a global process group.

2.1.5 Process States

Three basic states:

  1. Running (using the CPU)
  2. Ready (stopped, but could be picked up and run at any time)
  3. Blocked (unable to run until some event happens)
  • Running ⬌ blocked can happen due to a system call made by the running process, or automatically if the process reads from a pipe or a special file like a terminal or socket when there’s no input available.
  • Running ⬌ Ready is managed by the process scheduler, which decides what process to run next.

2.1.6 Implementation of Processes

  • The operating system has a process table that stores the following data for each process:
    • Process state (running, ready, blocked)
    • Program counter (i.e. address of the next instruction to execute)
    • Stack pointer (i.e. address of the top of the runtime stack)
    • Memory allocation
    • Status of open files
    • Accounting and scheduling information
    • Anything else that needs to be saved between process switches

The process table enables interrupt execution. (i.e. hardware interrupts, which “interrupt” the currently running process to deliver something from a hardware device)
1. Hardware pushes the program counter, registers, state, etc. to the stack
2. Hardware loads a new program counter from the interrupt vector, a special location in memory assigned to each class of IO device (e.g. hard disk, timer, terminal devices in mainframes).
3. Assembly language procedure saves the current values of the registers in the process table.
4. Assembly language procedure sets up a new stack.
5. Interrupt service written in C runs. It reads input from the IO device and buffers it into memory.
6. Now that the input from the hardware has been pulled in, the scheduler runs and decides which process to run next.
7. The C procedure returns control to assembly
8. Assembly starts the new current process; it loads up the registers, resets the program counter and stack pointer, etc.

2.2 Threads

2.2.1 The Thread Model

  • A process can have multiple threads of execution
  • Processes group resources together; threads are the thing that actually runs on the CPU.
  • Each thread has its own:
    • Program counter
    • Registers
    • Runtime stack with execution history
  • All the threads in a process share:
    • An address space (so they can access each other’s memory)
    • Global variables
    • Open files
    • Child processes
    • Pending alarms
    • Signals and signal handlers
  • All threads in a process share memory so they can read and write each other’s variables and even stacks. This is part of the benefit of threads; it allows more efficient cooperation between concurrent entities (compared to processes, which can’t read each other’s memory and thus must use other means of communicating).
  • Threads have four states:
    1. Running
    2. Blocked
    3. Ready
    4. Terminated
  • Processes start with one thread and create more using library calls.
  • Threads can exit by calling another library procedure, e.g. thread_exit.
  • In some systems threads can wait for other threads to exit by calling thread_wait.
  • thread_yield gives up the CPU for another thread. The CPU won’t actually stop a thread until a process switch occurs, so threads in the same process have to yield to each other.
  • Threads introduce many complications, including synchronizing their shared memory and coordinating the yields so you don’t waste time running blocked threads.

2.2.2 Thread Usage

  • Threads let a single application do multiple things, modeled as sequential jobs running side by side instead of as a mess of interrupts and signals.
  • On multiprocessor systems or multi-core CPUs, multiple threads can actually run simultaneously. On single-core systems threads will switch on and off the one core.
  • Threads can start up faster than processes since they require fewer resources to get going.
  • Threads can block and cooperatively switch off since they can signal each other using their shared memory.

2.2.3 Threads in User Space

  • Processes manage their own threads in user space.
  • The kernel knows nothing of threads.
  • Each process has a thread table with the threads’ program counters, stack pointers, registers, etc.
  • The threads run on a run-time system, a library of thread-managing procedures

Advantages:

  • Thread switching is very fast since applications don’t need to trap to the kernel to switch.
  • Applications can implement custom thread scheduling.
  • User-space threads scale better since they don’t require space in the kernel.

Drawbacks:

  • If a user-space thread makes a blocking system call, it will block without giving you a chance to switch threads before handing off control to the kernel, because the kernel knows nothing of threads and cannot give you that chance. This means the whole process is blocked.
  • If a thread causes a page fault, e.g. because it needs to run some code that isn’t loaded into memory yet, it gets blocked, again without allowing any chance to switch threads.

Possible solutions to the drawbacks (that all suck):

  • The select system call can detect when a system call will block. You can use it before making a possibly blocking system call, and if it detects that the system call will block, you can switch to another thread and make the system call later. E.g. if the current thread needs to read some data, but the read call will block on a disk read, you can switch threads until the interrupt executes later and the data is buffered in memory, and then switch back to that thread.
  • Using select sucks because you have to wrap all your blocking system calls to do the select check, so you have to modify the kernel, and it’s also annoying and tedious logic to implement.
  • You can also use a clock interrupt to stop the currently running thread every so often and check if it’s been blocked and should be swapped for another thread.
  • Using a clock interrupt sucks because it’s an ugly hack (you might still let the blocked thread have the CPU for a while before the clock interrupt stops it), and apparently each process only gets one clock so if you use it to manage thread swapping you can’t use it for anything else.
  • System calls can all be rewritten to be non-blocking. E.g. rather than waiting for input to be available, a read call would just return 0 (for 0 bytes read) and you could try again later.
  • Rewriting system calls sucks because you have to rewrite a bunch of system calls around threads and that’s not cool.

2.2.4 Threads in the Kernel

  • You can instead put threads in the kernel. The kernel then manages the thread table and thread swapping instead of the user program.
  • All blocking calls are system calls and when a thread blocks, the kernel can choose another thread to run. If there is no suitable thread in the same process, the kernel can choose to let a different process run for a while.
  • Creating, destroying, waiting, etc. are all more expensive since they are system calls.

2.2.5 Hybrid Implementations

  • The idea is to combine the lightweight nature of user-space threads with the ease of swapping out blocked threads that comes with kernel threads.

2.2.6 Scheduler Activations

  • The kernel assigns each process some virtual CPUs (or they can request and release them). [It’s not actually clear to me from the text how the virtual CPUs play into this process.]
  • The kernel can detect when a thread blocks and notify the process through a mechanism called upcalls.
  • Upcalls work by activating the process’s runtime system at a known starting address, similar to a Unix signal. Once activated, the runtime system can choose to run another thread instead of the blocked one.
  • When a hardware interrupt runs, the process will be resumed and the runtime system can decide which thread to run. It can run the thread that was interrupted, or, if the hardware interrupt completed something that a blocked thread cares about (like reading in some data and buffering it in memory), it can choose to run the blocked thread, or it can just choose to run a completely different thread.
  • This system isn’t great because you now have two-way calls between the kernel and user space, whereas a normal operating system has a nice layered model where user space calls the kernel but not the reverse.

To be continued next time with interprocess communication. And then…in the epic final part of Chapter 2…SCHEDULING!!!

Notes on Computer Networking: A Top-Down Approach Chapter 2

These are my notes on Computer Networking: A Top-Down Approach (4th Edition) Chapter 2, Application Layer.

I don’t particularly recommend this book. It came out in 2008, and a lot’s happened to the internet since then. It’s not that well organized; you’ll see if you read the notes that they take some bizarre leaps from topic to topic. And it tends to be extremely wordy; these notes condense almost 100 pages of information. Because of that, you’ll notice that I didn’t take notes on every section. But I happened to have this book laying around, so I read it. I’m putting up the notes for my own future reference and in case someone else someday finds them useful.


2.1.1 Application Architectures

  • Client-server: one process (client) initiates communication, another (server) responds.
  • P2P: No central server, any process can act as either a client or a server.
    (Note: “process” refers to an operating system process, i.e. a running program.)
  • Sockets are the interface between the transport layer (of the OSI layer model) and the application layer. A process listens to a socket for messages and can put messages into the socket to send them across the network to the other end.

2.1.3 Transport Services Available to Applications

  • Messages pushed into a socket are sent across the network using a transport layer protocol.
  • There are four services transport layer protocols could theoretically provide.
    • Reliable data transfer
    • Throughput guarantees (e.g. guaranteed delivery of bits at 50 kbps)
    • Timing (e.g. guaranteed receipt of messages within 100ms)
    • Security

2.1.4 Transport Services on the Internet

  • TCP
    • Uses handshaking to establish a connection between client and server
    • Guarantees lossless data transfer
    • Implements throttling to reduce congestion over the network; this means it provides no timing or throughput guarantees.
  • UDP
    • Does not use handshaking or establish connections; packets sent over UDP might just disappear and never reach their destination.
    • Does not throttle.
    • Theoretically, UDP would be good for loss-tolerant time-bound applications, since the lack of throttling often means more throughput and faster delivery. In practice, UDP is usually blocked by firewalls, so no one uses it.
  • Neither protocol provides throughput guarantees, timing guarantees, or security, and UDP does not provide reliable data transfer either, which makes it puzzling that we took the time to go over those four services above. Applications built on these protocols must cope with the lack of these services.
  • SSL is an application-layer add-on to TCP that provides encryption; other application layer protocols send their messages through SSL, which encrypts them and sends them into the socket, which uses TCP to send them to the other end, where the encrypted message is read from the socket by SSL on the other end and decrypted before being passed to the application layer protocol on that end.
  • The transport layer uses IP addresses and port numbers to find the correct destination machine and socket on that machine.

2.2 The Web and HTTP

  • HTTP is defined by RFCs 1945 and 2616.
  • An HTTP server stores no information about the clients, so HTTP is a stateless protocol.
  • HTTP uses persistent connections by default, i.e. after opening a TCP connection, it will keep that connection open and reuse it for a period of time for subsequent interactions. This increases performance; establishing a connection requires an extra network round trip to go through the handshaking process, and a single web page might require several requests to fully load (to get the HTML, Javascript, CSS, images, etc.), so reusing a connection reduces that overhead.

HTTP request message format:
– \<HTTP method, e.g. GET, POST> \<URL> \<version, e.g. HTTP/1.1>
– <header name>: <header value>
– <More headers>
– Empty line
– <Entity body, which can contain any data>

HTTP response message format:
– <version> <status code, e.g. 400> <explanation of status code, e.g. “Bad Request”>
– <header name>: <header value>
– <More headers>
– Empty line
– <Entity body>

2.2.4 Cookies

  • Defined in RFC 2965
  • Response header Set-cookie tells client to store something, such as a user id, in a cookie file, keyed by the host name.
  • Request header Cookie contains the value set by the host to which the request was made.
  • Cookies allow servers to maintain information about clients even over the stateless HTTP protocol.

2.2.5 Web Caching

  • Cache make go fast
  • The cache can send requests with an If-Modified-Since header; if the object being requested has not been updated, the server will return status 304 Not Modified, telling the cache it can return the version it has.
  • The book doesn’t mention this, but ETags are another mechanism used for cache validation.

2.3 FTP

  • FTP allows navigating a remote filesystem and transferring files to and from that filesystem.
  • FTP uses two TCP connections
    • A control connection on port 21 sends user id, password, and commands
    • A data connection on port 20 sends actual files.
  • Using the separate connection for control information is called sending control information out of band.
  • FTP is not stateless; it stores username, password, and current directory for clients.
  • Control connections are persistent; they are kept open for a period of time and reused.
  • Data connections are not persistent; they are opened by the server in response to user commands, used to send or receive a single file, and closed.

2.4 Email

  • Uses two types of protocols: mail send (SMTP) and mail read (POP3, IMAP).

2.4.1 SMTP

  • Uses TCP’s reliable data transfer.
  • Has both a client and server mode. Message senders are clients, message receivers are servers.
  • All text in an SMTP message must be 7-bit ASCII because the protocol is extremely old.
  • Uses port 25.
  • Handshakes to establish a connection.
  • Uses a single TCP connection to send all outgoing messages it has.
  • Is a push protocol—clients mainly send data to servers. By contrast, HTTP is mainly a pull protocol; clients typically receive data from servers.
  • RFC 822 defines SMTP and the headers for sending ASCII text.
  • MIME (Multipurpose Internet Mail Extensions) defines headers for sending non-ASCII text.
    • Defined in RFCs 2045 and 2046.
    • Uses the Content-type and Content-Transfer-Encoding headers.
    • Content-type tells the receiver what the data actually is, e.g. image/jpeg, audio/vorbis, text/csv.
    • Content-Transfer-Encoding tells the receiver how the data was converted to 7-bit ASCII text, e.g. base64.

2.4.4 Mail-Access Protocols

  • Since SMTP is push-based, it can’t really be used to retrieve mail by non-server clients like desktop PCs.
  • POP3 and IMAP are pull-based protocols for email clients to retrieve mail.
  • POP3 is very simple; it cannot manage email directories on a remote server. It has “read and delete” mode, where it downloads mail and deletes it from the remote server, as well as “read and keep”, where it leaves the mail on the server.
  • IMAP is much more complex.
    • It can manage mail directories.
    • It can obtain parts of messages, which can be useful when bandwidth is low; you can avoid downloading large video and audio files.
  • Web mail clients like Gmail just use HTTP to retrieve messages. POP3 and IMAP are useful for desktop clients like Thunderbird and Outlook, or for terminal clients like Mutt. Gmail and other web-based email services sometimes provide POP3 or IMAP access so you can use clients like Thunderbird and Mutt to read your mail. Information to access Gmail using SMTP and IMAP from an email client.

2.5 DNS

  • DNS (Domain Name System) translates human-readable domain names to numeric IP addresses.
  • The term “DNS” actually refers to two things:
    • A distributed database implemented in a hierarchy of DNS servers.
    • An application-level protocol for querying this database.
  • DNS servers often run the Berkeley Internet Name Domain (BIND) software.
  • DNS runs on UDP and uses port 53.
  • Clients implementing other protocols (e.g. HTTP, FTP, SMTP) will include a step where they use DNS to translate user-supplied hostnames into IP addresses.
  • DNS can add a delay to requests, but the delay is minimized with caching in nearby servers.
  • DNS also provides:
    • Host aliasing: can translate a short alias into a longer canonical hostname
    • Mail server aliasing: can give a web server and mail server the same alias but different canonical hostnames
    • Load distribution: (proceed with caution; I have doubts that this is still a good idea. I asked a question on SE about this: https://softwareengineering.stackexchange.com/q/404590/212168) DNS can map a hostname to a set of IP addresses. You can map a hostname to a set of replica servers all running the same application. The DNS server will (according to the book) rotate the order of the IP addresses it returns, and clients will (according to the book) always take the first one, so requests will be distributed across your servers.

2.5.2 How DNS?

DNS uses four types of servers:
– Root DNS servers. There are 13 of these in the world, controlled by various institutions and entities. They are the first stop in a DNS lookup.
– TLD DNS servers. These each service a top-level domain (.com, .edu, .gov, .jp, .fr, .tv, etc.). Different companies own the different TLD servers.
– Authoritative DNS servers. The owner of a domain controls the authoritative DNS server for the domain.
– Local DNS servers. These act as brokers / caching centers for a local area.

A basic example of a DNS interaction.
1. A client requests an internet connection to an ISP. The ISP provides the address of one of its local DNS servers using the DHCP protocol. The local DNS server will be within a few routers of the client for speed.
2. The client will send requests for hostname lookups to its local DNS server. The local DNS server will forward them to a root DNS server.
3. The root DNS server will send back the identity of a TLD server that can handle the request. E.g. if the hostname is google.com, the root DNS server will send back a TLD server that can handle .com.
4. The local DNS server contacts the provided TLD server. The TLD server looks at the entire domain and returns an authoritative DNS server for that domain. E.g. if the hostname is google.com, the TLD server for .com will send back an authoritative DNS server for google.com.
5. The local DNS server contacts the provided authoritative DNS server. The authoritative DNS server will provide the IP address of a machine mapped to the hostname, possibly after communicating with other authoritative DNS servers to resolve subdomains. E.g. the authoritative DNS server for google.com might contact another authoritative DNS server to resolve docs.google.com to an IP address.
6. The local DNS server returns the IP address to the client. The client uses that IP address to send a request.

The local DNS server can cache a lot of the information it receives for later reuse. This allows it to skip a lot of the steps. For example if the local DNS server caches the IP of docs.google.com, it can immediately send that IP address back to any client who requests it. It can also cache the authoritative DNS server for google.com, so if a client requests any subdomain of google.com, it can go straight to that authoritative DNS server instead of going through the root and TLD servers again.

DNS cache is busted after a period of time, typically 24–48 hours.

2.5.3 DNS Messages and Resource Records

  • A resource record is a four-tuple: (Name, Value, Type, TTL)
  • The TTL is the time before the record should be evicted from cache.

Four types:
A: Name is host, Value is host’s IP address. Nowadays we also have AAAA for IPv6 addresses.
NS: Name is domain (e.g. google.com), Value is hostname of authoritative DNS server for that domain, e.g. ns2.google.com.
CNAME: Name is an alias, Value is the canonical hostname.
MX: Name is an alias, Value is the canonical hostname of a mail server. This exists so a mail server and another kind of server (such as a web server) can have the same alias but different canonical hostnames, so you can have bludengooden.com point to both the web server bludengooden-website.com and the mail server bludengooden-mail.com. Web clients will request the CNAME record for bludengooden.com and get back the value bludengood-website.com, while mail clients will request the MX record and get back the value bludengooden-mail.com.

Note1: There are actually an assload of DNS record types.
Note2: On MacOS and Linux (probably also through WSL on Windows) you can use the terminal command dig to do DNS lookups.

Format of a DNS message:

16 bit ID 12 bits of flags
number of questions number of answers
number of authority records number of additional records
Questions
Answers
Authority
Additional
  • The 16-bit ID links requests and responses together.
  • The flags indicate such things as whether the message is a query or reply, if the queried server is authoritative for the queried name, or whether to allow recursive queries (a DNS server receiving a query and querying another DNS server to fulfill it).
  • The numbers indicate the number of DNS records returned in the later sections.
  • Questions are queries with host names and types (A for host address, MX for mail server canonical name, etc.)
  • Answers are only in replies and are the answers for the queries (IP addresses for A queries, canonical names for CNAME and MX queries). You might get multiple answers when a hostname has multiple IPs.
  • Authority is the records of other authoritative servers.
  • Additional depends on the query but will contain other useful information. E.g. for an MX query, the answers section will contain the canonical hostname of the mail server, and the additional section will contain the A records mapping the canonical name to an IP address so you don’t have to query again for them. Similarly, for an NS query, the answers section will have the canonical names of the authoritative DNS servers, and the additional section will have the A records for the IP addresses. You can mess around with dig to see these.

Records are inserted to DNS by paying a registrar, which are authorized by ICANN, to get your hostname mapped to your authoritative DNS server in a TLD server for your top-level domain.


There were two more sections, one about P2P protocols and BitTorrent, another about implementing custom application-layer protocols in Java by using the various socket classes. I read the P2P section but chose not to take extensive notes on it. I skimmed the implementation section.