15-410 HW2 solutions (Spring, 2012)

Question 1 - Public Key Practicum

If you did this problem correctly, in a couple of hours your hw2 directory should contain a $USER.message.decrypted file. If not, check to see if there is a $USER.ERROR file. If not, a popular problem is that you used file names other than the ones specified in the assignment, the grading script wasn't able to guess what you meant, and the grader hasn't yet had the time to manually intervene.

By the way, your encrypted messages to us were read and, generally, appreciated.

The best George R. R. Martin quote was provided by Kaili Li. We were rickrolled twice. Of course we're not going to reveal the messages--they're secret!

Question 2 - Producer/Consumer

In the IPC/RPC lecture, your instructor briefly claimed that IPC systems with blocking send() operations are "bad for the producer/consumer pattern". In this problem you will explore what that might mean.

Part A

Explain why a "strictly blocking send" is bad for the producer/consumer pattern.

First let's discuss the relative rates at which the producer and consumer run. If either one generally runs much faster than the other, buffering is of no real use. If the consumer runs much faster than the producer, the kernel's buffer will always be empty, no matter how big the kernel might have been willing for it to be. If the producer runs much faster than the consumer, the kernel's buffer will always be full (to whatever limit the kernel imposes). This case is particularly unhelpful, because some large amount of memory is being consumed with no benefit.

When is buffering useful? In general, it is useful when the producer and the consumer generally run at roughly the same speed, but not exactly in lock-step. For example, imagine that the time for the producer to produce 20 items is essentially always exactly the same amount of time as it takes for the consumer to consume 20 items, even though some individual items take three times as long to produce as others, and some individual items take three times as long to consume as others. In that case a 20-item buffer is great: any time the consumer is working on a "hard" item, the producer will run ahead for a while, and when the producer is working on a "hard" item, the consumer will catch up. Most of the time the buffer will be right around empty; sometimes it will fill up partially for a while before draining back to "around empty"; and once in a while it will fill up and the consumer will actually be blocked briefly. This is how buffers should theoretically work (and there is lots of theory—see 15-857A: Analytical Performance Modeling & Design of Computer Systems), but not how they always do (see Ars Technica's coverage of Understanding bufferbloat and the network buffer arms race by Iljitsch van Beijnum).

With that out of the way, why is a "strictly blocking send" bad for producer/consumer? At a high level of abstraction, it seems as if there shouldn't be any problem, especially not on a uni-processor machine: if we have two processes, a producer and a consumer, all we really care about is that the kernel's buffering approach doesn't do something so silly that there would be a period of time during which the processor would be idle, i.e., neither process could run.

Strictly-blocking send doesn't cause this problem on a uni-processor: if the producer runs for a while, produces something, tries to send it, and blocks because the consumer isn't waiting, that means that the consumer hasn't finished consuming the previous item yet. The kernel can block the sender and switch to running the consumer; when the consumer finishes and retrieves the item that the producer is trying to transmit, neither the producer nor the consumer will be blocked, and the kernel can choose to run either one completely productively. If the kernel runs the consumer until it finishes consuming, the consumer will block because the buffer is empty, and the kernel will be able to resume the sender. If instead the kernel runs the producer, we are back to the beginning of the scenario. Either way, or with any mixture, the system is always productive, so a strictly-blocking send is fine.

The situation is different on a multi-processor machine, however. What we want is for the producer and the consumer to keep two processors busy. Recall that we assume the producer and the consumer run at the same rate of speed, over an appropriate averaging interval—because if that isn't true then buffering is of little value (we might re-design our code, or, if we have enough processors, we might run multiple producers and multiple consumers in whatever ratio is necessary to bring their processing rate into balance). The problem is that if the kernel doesn't buffer when the producer sends then the producer can't temporarily get ahead of the consumer. This in turn means that the consumer can't ever run faster than the producer. The result is that both of them run at the speed of the slower one; since their speeds vary from time to time, the throughput of the system also varies, meaning that some of the time some processor must be idle.

Here is an example. When the application begins, the producer naturally starts working away to compute the first item, and the consumer naturally blocks in receive() because nothing has been produced yet.

The lack of buffering means that the system flips back and forth between 100% busy (good) and 50% busy (bad). Even a single-entry queue would help quite a bit!

Part B

Unix pipes (and also port-based IPC mechanisms) historically almost always ran on uni-processor machines, because historically almost all machines were uni-processors. However, Unix pipes (and also port-based IPC mechanisms) generally supported buffered send operations. Briefly speculate as to why send buffering was considered a good idea, even though, historically speaking, kernel memory for buffering was a limited resource.

In a sense this is a "trick question": except at the very beginning of computing history, "uni-processor" machines contain multiple processors; the obvious example of a "secret processor" is a disk controller, which accepts a read or write command from the main processor, "computes" for a while, and then either acknowledges completion of the write command or returns the result for the read command. If our chain is (as stated in the original problem) producer, then consumer, then log file, then buffering between the consumer and the disk controller helps us keep both the main CPU (alternating between the producer and the consumer) and the disk busy. If the disk runs slower than the consumer for a while, the consumer will stall; at this point, it's useful if the producer can keep running for a while while the consumer is stalled; this requires buffering between the producer and the consumer.

Another reason: so far our discussion has assumed that it is free for the kernel to switch between the producer and the consumer, though we know this isn't true. Switching back and forth requires distasteful things like TLB flushing. On a system with limited RAM, such as an older uni-processor system, switching between the producer and the consumer might even require swapping the address space of the blocked process out to disk and then swapping the address space of the unblocked process in from disk: this might take seconds, during which neither producer nor consumer would be running. CPU utilization would be vastly increased in such a scenario if the kernel were willing to buffer "a few" items: the producer would produce several items and then block; the kernel would swap out the producer and swap in the consumer; the consumer would consume the several items and then block; the kernel would swap out the consumer and swap in the producer; and this pattern would repeat.

For further reading...

Here is last semester's homework page.

[Last modified Saturday May 05, 2012]