CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Count the polls (20 minutes)

A device is ready 2 ms after the command and each poll takes 50 ns. How many polls does the loop make?

Done when: 40,000.

Hint

divide the wait by the time of one poll, in the same unit.

Easy 2: Words in a buffer (20 minutes)

How many 4-byte words are there in 64 KiB?

Done when: 16,384.

Hint

64 KiB is 65,536 bytes. Divide by 4.

Easy 3: Interrupt share (20 minutes)

A disk raises 1,000 interrupts per second and each costs 5 microseconds. What share of one processor does it use?

Done when: 5 ms per second, which is 0.5%.

Hint

multiply 1,000 by 5 microseconds and compare it with one second.

Medium

Medium 1: Programmed I/O against DMA (45 minutes)

Move 64 KiB. Programmed I/O costs 20 ns per 4-byte word. DMA costs 10 microseconds for set-up and the final interrupt. Find both times and the ratio.

Done when: 327.68 microseconds, 10 microseconds, and a ratio of about 32.8.

Hint

programmed I/O is 16,384 x 20 ns. Divide by 10 microseconds.

Medium 2: Batching (45 minutes)

A network card receives 100,000 packets per second and an interrupt costs 5 microseconds. Find the processor share with one interrupt per packet, and with one per 32 packets.

Done when: 50% and about 1.56%.

Hint

100,000 / 32 = 3,125 interrupts per second.

Medium 3: Interrupts per byte (45 minutes)

Compile the program of section 5 and run it with request sizes of 4 KiB, 64 KiB and 1 MiB on a file of at least 256 MiB. Report bytes per interrupt for each.

Done when: three values that rise with request size, and a note that the counts include other interrupts.

Hint

bytes per interrupt is 256 MiB divided by the interrupt count.

Hard

Hard 1: Poll, interrupt or hybrid (90 minutes)

An interrupt costs 5 microseconds of processor time. For device latencies of 1, 5 and 100 microseconds, compute the processor time of three methods: pure polling, pure interrupt, and a hybrid that polls for up to 5 microseconds and then sleeps and takes an interrupt.

Done when: polling 1, 5 and 100; interrupt 5, 5 and 5; hybrid 1, 5 and 10 microseconds; and a sentence on why the hybrid never costs much more than the better of the other two.

Hint

hybrid cost is L if L is at most 5, else 5 plus 5.

Hard 2: Bus share (90 minutes)

A memory bus carries 1,000 MB/s. Two DMA devices move data at 100 MB/s and 400 MB/s. How much bus bandwidth is left for the processor, and how long does the faster device need for 1 MiB?

Done when: 500 MB/s (50%) and 2.62 ms for 1 MiB at 400 MB/s.

Hint

the bandwidth left is 1,000 - 100 - 400. The time is 1,048,576 bytes divided by 400,000,000 bytes per second.

Hard 3: Find your disk's interrupts (90 minutes)

On your machine, run cat /proc/interrupts before and after reading a large file with dd if=FILE of=/dev/null bs=1M. Name the row that grew most, and compute the interrupts per MiB.

Done when: the name of the row, the two counts, and an interrupts-per-MiB figure, with a sentence on whether the value fits the idea that large requests need fewer interrupts.

Hint

if the disk is virtual, the row may be a virtio entry. Use the largest increase.