Past exam of the year 1 of the computer science course of the University of Oxford / 2017

Solutions to the 15 June 2017 preliminary examination, with all 46 printed subparts answered. Source: released examination archive, member a10101w1-1.pdf.

Use four request bits $r_0,r_1,r_2,r_3$ and four grant bits $g_0,g_1,g_2,g_3$. A high $r_i$ requests service for the coming allocation period, and a high $g_i$ identifies the requester granted the resource during the current period. At most one grant may be high. An all-zero grant vector means idle. The synchronous sequential circuit also has a clock and an initialization signal.

Requests are sampled at a clock edge; the resulting allocation appears during the following cycle. This fixes the Moore machine timing convention: current grants depend on the stored state, rather than combinationally on requests that can change within the cycle.

Store three state bits: a two-bit index $L\in \{0,1,2,3\}$ identifying the most recent recipient, and a valid bit $V$ indicating whether that recipient is receiving service in the current cycle. ThenWhen no requests are present at a decision edge, clear $V$ but preserve $L$. Preserving $L$ implements round-robin arbitration with idle memory. Four possible last recipients each have an active and an idle state, giving eight states. The four idle states have equal outputs but different future priorities, so they cannot all be merged. One valid reset is $L=3,V=0$, which gives requester zero first priority at startup.

All requester indices in the following expressions are interpreted modulo four. Let $h_{\ell ,j}$ mean that requester $j$ is the first asserted request after last recipient $\ell$:An empty logical conjunction is true. Decode the remembered index and combine the four priority orders:Exactly one $w_j$ is high when any request is high. Write $L$ as bits $L_1{L}_0$. The next-state function and Moore machine outputs areThus an idle step preserves the priority memory. The $w_j$ are combinational selection signals, not the current-cycle grants: exposing them directly as outputs would change the design into a Mealy machine. If a requester remains continuously asserted, each intervening successful grant advances the circular order, so it receives service after at most four grant decisions.

For a single read-only memory implementing both the next-state and output equations, the address has four request bits plus three present-state bits. Each word contains three next-state bits and four grant bits. HenceThree D flip-flops store the state outside this combinational ROM. This is the direct truth-table implementation for the encoding above. A smaller factored implementation exploits the independence of the next-state equations from $V$: a $64\times 3$ next-state ROM and an $8\times 4$ output ROM use $224$ stored bits in total, or the output decoder can be ordinary logic. These are different implementation organizations, not different state counts.

An input-output-bound process spends much of its time waiting for input-output, often with short CPU bursts between waits. A CPU-bound process spends most of its time doing useful CPU computation, with comparatively little blocking. These descriptions concern the bottleneck in the workload; an I/O-bound process still needs CPU time.

With nonpreemptive scheduling, a running process retains the processor until it finishes its current CPU burst, blocks or voluntarily yields. With preemptive scheduling, the operating system may suspend a runnable process and select another one.

Time-slice preemption needs a hardware timer delivering an interrupt after bounded execution time, so control returns to the scheduler even if the running program never yields. Saving and restoring the execution context then lets the interrupted process resume later. The timer mechanism should remain under operating-system control.

Assume both processes are available at time zero and run the listed order, A followed by B, with no overlap even during input-output. A takes $12+4=16$ ms; B then takes $3+4=7$ ms. ThusThe scheduling turnaround time includes the time waiting before a process first runs. Reversing the serial order would leave the total at 23 ms but change completion times to 7 and 23 ms, with mean 15 ms. If arrivals were instead delayed until each serial launch, that would define a different turnaround measurement; the simultaneous-arrival convention is used for comparing the schedulers below.

With the given ready-order rule and A first, the CPU timeline in milliseconds isA performs input-output during $[4,6)$ and $[10,12)$; B does so during $[5,7)$ and $[11,13)$. In particular, B becoming ready at time 7 does not interrupt A's ongoing nonpreemptive burst. The completion times are $C_A=16$ and $C_B=17$, givingThere are 15 ms of useful CPU execution and 2 ms of idle time on this particular timeline.

Use round-robin scheduling with scheduling quantum 2 ms. A's first burst is split by B, and A's second burst is also interrupted once. The resulting CPU intervals areA blocks for input-output during $[5,7)$ and $[12,14)$; B blocks during $[3,5)$ and $[6,8)$. At time 8, B joins the ready queue while A uses the remainder of its current quantum; B runs at time 9. No other process is runnable during A's final four milliseconds, so A can continue across the time-16 quantum boundary. Consequently

The preemptive policy improves B's scheduling turnaround time from 17 to 10 ms and the mean from 16.5 to 14 ms. A finishes later, at 18 rather than 16 ms, and the total completion time rises from 17 to 18 ms. Thus preemption improves mean turnaround here; nonpreemption gives the shorter makespan here.

The result illustrates different scheduling objectives, not a universal winner. These calculations assume negligible context switch overhead; charging for the additional switches could change the comparison. Both policies perform the same 15 ms of useful CPU work.

Use $k$ clocked processor registers, each storing an $n$-bit word, two independent combinational read ports and one synchronous write port. Each address requires $a=\lceil {\log }_{2}k\rceil$ bits. The read addresses select two $k$-to-one multiplexers, each $n$ bits wide. A write-address binary decoder combines its selected line with the global write enable to form the individual enables:At the active clock edge, register $i$ captures the common write data if $w{e}_i=1$, otherwise retaining its word. Reads return the currently stored words selected by their respective addresses. For non-power-of-two $k$, unused address codes need a specified harmless implementation. A simultaneous read and write of one address follows the chosen edge/read timing; an additional forwarding circuit would be needed if a different bypass convention were required.

Keep storage only for registers 1 through 31, return a hardwired all-zero word on either read port when its address is zero, and setThere is no enable for register zero and no global RegWrite input to this register file. The right-hand diagram above shows this change. Every clock edge may select a write address; choosing zero suppresses all physical register enables. Consequently the MIPS zero register acts as a write-suppression destination.

Move the no-write decision into the destination-address path. If the original destination selection produced $d$ and the original write-enable decision was $W$, drive the new register file withA five-bit two-input multiplexer after the existing destination selector implements this, or the decoder can directly select among zero, the instruction's destination fields and register 31. Its control still distinguishes writing and non-writing instructions: removing the register-file enable pin does not remove that logical decision.

Read-address selection and the result-data path can remain unchanged. Instructions that formerly disabled RegWrite now select destination zero; their write data is irrelevant. Instructions writing an actual destination preserve the same address and data. Since writes to the MIPS zero register were already discarded, the architectural behaviour is unchanged for that case as well.

For add, select rd and the arithmetic logic unit result. For sw, select destination zero while retaining the memory-store controls and source-register reads. For jal, select register 31 and the return-address data. These are the same actual register writes as before, with sw using destination zero in place of disabling RegWrite.

The link value is determined by the particular MIPS architecture datapath convention: $\mathrm{PC}+4$ for the usual teaching datapath without a delay slot, or $\mathrm{PC}+8$ for classic delayed-branch MIPS. This write-enable change does not alter whichever link convention the original machine implements.

No: the only solution is the zero vector. Subtract the fourth row equation from the first to get $2x_3=0$. Subtract the third from the fourth to get $2x_2=0$. With $x_2=x_3=0$, any row then gives $x_1=0$. Thus this homogeneous linear system has trivial null space.

The columns are linearly independent. A linear combination of them with coefficients $x_1,x_2,x_3$ is exactly $Ax$. Part (a) shows that this vanishes only when all three coefficients vanish, which is the definition of column independence. Hence $A$ has column rank three.

Writing the columns as $a_1,a_2,a_3$, matrix multiplication givesThe column space is the linear span of these columns, so this particular linear combination belongs to it. The assertion holds for every vector of coefficients $y$.

If $Ax=b$ has a solution, the multiplication identity from part (c) expresses $b$ as a linear combination of the columns, so $b\in \mathrm{Col}(A)$.

Conversely, if $b$ lies in that column space, its definition supplies scalars $x_1,x_2,x_3$ with $b=x_1{a}_1+x_2{a}_2+x_3{a}_3$. Put those scalars into the column vector $x$. Then $Ax=b$. This proves both directions of the claimed equivalence.

The Gram-Schmidt process first gives $u_1=a_1=(1,1,1,1{)}^T$, of norm two. Next $a_1^T{a}_2/(a_1^T{a}_1)=2$, soFor the third column, both coefficients onto $u_1,u_2$ equal one, givingThese three nonzero vectors are mutually orthogonal and each has norm two. The resulting orthonormal basis is

Collect the orthonormal vectors as columns and compute $R=Q^{T}A$. This gives the thin QR decompositionThe inner products in part (e) prove $Q^{T}Q=I_3$; the column identities $a_1=2q_1$, $a_2=4q_1+2q_2$, $a_3=2q_1+2q_2+2q_3$ prove $A=QR$.

Substitute the QR decomposition into the normal equations:The diagonal of $R$ is nonzero, so $R^T$ is invertible. Cancel it algebraically to obtainCompute the three inner products in $Q^{T}b$, then use back substitution in this upper triangular matrix. There is no need to form an inverse or explicitly construct $A^{T}A$. The orthogonal projection of $b$ onto the column space is $Q{Q}^{T}b$; its orthogonal residual proves that this solution minimizes $\Vert Ay-b{\Vert }_2$.

The required elementary matrix isLeft multiplication exchanges the two rows. Applying the same exchange twice restores every row, so $E^2=I_3$.

The elementary row operation and its reverse areThus $FA$ replaces row three by row three minus three times row two. The inverse adds those three copies back.

Use multiplicativity of the determinant and the determinant criterion for an invertible matrix:Neither factor can therefore be zero, so both matrices are nonsingular. The determinant of a triangular matrix is the product of its diagonal entries:Each product is nonzero, forcing every diagonal factor to be nonzero. These explicitly stated determinant properties justify both conclusions.

First subtract row one from row two, using $E_1$; then subtract four times the updated row two from row three, using $E_2$:The updated second row is $(0,1,2)$ and the final third row is $(0,0,-4)$. Hence $E_2{E}_{1}A=U$ and $L=E_1^{-1}{E}_2^{-1}$. The resulting LU decomposition isReversing the order when undoing the elementary operations is essential.

Introduce $z=Ux$. Solve $Lz=b$ by forward substitution and then $Ux=z$ by back substitution. For these factors, the recurrences arefollowed byThe nonzero diagonal entries make both triangular solves well-defined. No matrix inverse is calculated.