Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 8 (Operating Systems)

A computer bus conventionally has address, data and control components. Address information selects a memory location or device register; data carries the value being transferred; control identifies operations and coordinates timing, direction, completion and arbitration. A clock, request/grant and acknowledge signals are examples of control information. These are logical roles, not a requirement for three physically separate wire groups: implementations may multiplex address and data on the same wires.

The processor selects the device's data or control register by presenting its address, either in memory-mapped input-output space or in a distinct port-address space. For a write, it places data on the computer bus and asserts the appropriate write control. For a read, it asserts read control and samples the data supplied by the addressed device. The device recognizes the address and uses the bus timing or acknowledge protocol to indicate completion, including wait states if needed.

The processor uses status registers to determine readiness and control registers to request operations. This register-level communication can be arranged using polled input-output or interrupt-driven input-output; the bus transaction itself and the policy for waiting on a device are separate issues.

With direct memory access, a device can initiate memory transfers, so the processor is no longer the only computer bus master. Requests must be arbitrated to prevent conflicting transfers, and the processor may have to wait while the device owns a shared bus. The operating system must supply valid stable buffers and arrange safe completion before reusing them. On a noncoherent system, cached processor copies must be flushed or invalidated as appropriate so processor and device agree on data. These extra initiators also need suitable address and protection controls.

Separate buses match different bandwidth, latency and electrical requirements. Processor-memory traffic needs high bandwidth and short delays, whereas many peripheral devices are slower or use different signaling protocols. Bridges let them communicate without making every memory transfer obey the slowest peripheral's timing. Separating traffic also reduces contention and electrical loading, and permits expansion or compatibility with older device interfaces. Thus a hierarchical computer bus organization is useful even though all devices are ultimately reachable from the processor.

Add profiling to the timer-interrupt handler. When the target operating-system process is interrupted while running, record its saved instruction pointer, map that address to a code region in the executable, and increment an address histogram. Addresses with many samples identify regions consuming a large fraction of execution time. The executable's code can then be disassembled around these addresses even when source and symbolic names are absent.

This is statistical program profiling: uniform samples of running time estimate time spent in code, not exact execution counts. Restrict samples to the desired process and distinguish application execution from unrelated kernel work. A sufficiently fine address histogram and many samples reveal hot loops; varying the sample interval reduces synchronization bias. If exact visit counts rather than time hotspots are needed, arrange breakpoint or single-step traps, or rewrite the binary to add counters, accepting their much larger overhead. Source code is not required to associate sampled execution with instruction addresses.

Use strength reduction on the disassembled hot instructions. In a fixed-width wrapping integer model,The first replacement is a single left bit shift. For the second, preserve the original operand in a register, shift a copy left by four and subtract the original:This avoids a general multiplication if shifts and subtraction are cheaper on the target processor. The two identities hold for positive and negative two's complement operands when only the low $w$ result bits are required.

Because only a binary is available, patch the machine instructions and adjust displaced branches or use a jump to a replacement code block if the new sequence does not fit. Preserve live registers and the calling convention. If later instructions consume overflow or other condition flags, or the original multiplication produces a double-width result or traps on overflow, matching only the low-word arithmetic is insufficient: those effects must be reproduced or the transformation rejected. Finally, measure the modified program; a fast hardware multiply need not be slower than several replacement instructions.