AAPCS32 2026-10-24
View more
The 32-bit calling convention for the ARM architecture family. Its base variant passes initial arguments in r0–r3, returns a word in r0, preserves r4–r8, r10, r11, and sp, and requires eight-byte stack pointer alignment at public calls.[ref]
Read the full article
Context switch 2026-10-13
View more
A context switch transfers CPU execution from one operating-system process or software thread to another while preserving enough execution context for the suspended task to resume. The operating-system kernel saves the outgoing task's processor registers, including its resume program counter and stack pointer, and restores the incoming task's saved state. Hardware entry and software switching divide this work differently across architectures; the diagram groups them into logical save and load steps. During the transition the same CPU executes the operating-system kernel's scheduler and switching code. [ref]
For a schematic switch from A to B, let A's resume program counter be , its stack pointer , and one illustrative data processor register contain 7. B's saved values are . Saving A retains in A's execution context; loading B establishes before B resumes. These are selected fields, not a complete architecture-specific execution context. Later restoring A recovers its 7 even though B has used the same physical processor register for 42.
Figure 1.
One CPU over time: save A's execution context, run the scheduler, and restore B's execution context
. Details.
The useful invariant is that each suspended task retains its own resume state, so another task's use of the processor registers does not erase it. This is what makes repeated turns under round-robin scheduling possible. Saving an execution context does not copy the entire address space. Switching between software threads of one operating-system process can retain the same address space; switching between operating-system processes with different address spaces may also require changing the memory management unit's translation context, such as the active page table and associated address space identifier, depending on the architecture. Their contents remain in computer memory. [ref]
Entering the operating-system kernel through an interrupt, synchronous processor exception or system call does not automatically imply a context switch to another task. The handler may return to the same task; process scheduling determines whether another runnable task should take over. A context switch consumes time, and a changed memory cache or translation lookaside buffer working environment can add subsequent costs. Those costs are excluded from the toy process scheduling timelines, which are calculations rather than operating system benchmarks. [ref][ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 3 / a / Solution 2026-10-31
View more
The calling convention passes the integer argument in $a0, returns the result in $v0, and uses jal with $ra for a call and its return address. The callee returns using jr $ra. Its stack frame grows downwards from $sp and must be removed before returning, restoring the caller's stack pointer.
The $s processor registers are callee-saved registers: a callee that uses $s0 or $s1 must restore their incoming values. The $a, $v, and $t processor registers are caller-saved registers; a caller must preserve any of their values that it needs after a call. Consequently foo keeps its own argument in $s0 and the first call's result in $s1, where nested calls preserve them. Because a nested jal overwrites $ra, foo also saves its incoming return address. Every recursive activation has its own stack frame.
The supplied MIPS instructions use the paper's simplified convention: pseudoinstructions such as subi are accepted, and control transfers have no branch delay slot. The completed code below follows that convention. A hardware implementation with delayed control transfers requires suitable scheduling or nop instructions throughout the supplied code as well.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 3 / c / Solution 2026-10-25
View more
SP-relative addressing forms an effective memory address by adding an offset to the stack pointer. It accesses local variables, saved processor registers or other stack-frame data without dedicating a separate base processor register for each object. The supplied reference gives word-aligned SP-relative offsets from to , which corresponds to an eight-bit nonnegative field scaled by four.
In the modified datapath, select the stack pointer for the unshifted ALU input, the instruction immediate operand for the barrel shifter input, and ALU addition. The effective address can then be . Scaling the immediate operand changes the reachable displacement range without storing a larger immediate operand. For example, an eight-bit field shifted by two reaches offsets through ; shifting it by four reaches through , but only on a sixteen-byte grid. Larger range and finer address granularity are different properties, so the extra reach is not free arbitrary-byte addressing.
The parallel layout cannot feed a shifted immediate operand directly into its address-producing ALU in the same pass. The serial layout can. The actual immediate operand width and permitted shift encodings of a new instruction must be specified; the question does not fix them, so no particular enlarged instruction encoding is implied.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Digital systems, linear algebra, introduction to formal proof / 2 / b / Solution 2026-10-25
View more
Use the conventional integer calling convention: $a0 holds the argument and $v0 holds the result. The function is recursive, so every call must preserve its own return address and original argument. The first recursive result must also survive the second call; a caller-saved register alone would not protect it.
This implementation reserves a 32-byte stack frame, keeping the stack pointer eight-byte aligned. Offsets 0–15 are available as the outgoing argument area, 16 stores the original argument, 20 stores the first result, 24 is padding, and 28 stores the return address. It changes no callee-saved register. Assemble in classic MIPS delayed-branch mode with instruction reordering disabled, such as .set noreorder.
foo:
addiu $sp,$sp,-32  # allocate 32-byte aligned frame
sw $ra,28($sp)  # save caller return address
sw $a0,16($sp)  # save original n
beq $a0,$zero,foo_base
sll $zero,$zero,0
addiu $t0,$zero,1
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $t0,$zero,2
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $a0,$a0,-1
jal foo
sll $zero,$zero,0
sw $v0,20($sp)  # preserve foo(n-1) across next call
lw $a0,16($sp)  # recover original n
sll $zero,$zero,0
addiu $a0,$a0,-3
jal foo
sll $zero,$zero,0
lw $t0,20($sp)
sll $zero,$zero,0
addu $v0,$v0,$t0  # combine the two recursive results
beq $zero,$zero,foo_return
sll $zero,$zero,0
foo_base:
addu $v0,$a0,$zero  # base case result is n
foo_return:
lw $ra,28($sp)
sll $zero,$zero,0
addiu $sp,$sp,32  # release the frame
jr $ra
sll $zero,$zero,0
All displayed operation mnemonics denote single machine instructions. In particular, sll $zero,$zero,0 is the actual harmless shift encoding often abbreviated by the pseudoinstruction nop; addu $v0,$a0,$zero performs a copy without the move pseudoinstruction. Each branch or jump has an explicit harmless branch delay slot, and harmless shifts also separate loads from their subsequent uses. The base cases return the original argument; other calls return the sum of the two recursive values. Every return restores the saved return address and exactly undoes the stack allocation.[ref]
The stated domain is nonnegative integer , with sufficient stack space and a result representable in the intended integer type. The non-trapping additions implement that mathematical result within range; beyond it, machine wraparound would require a separately specified integer semantics.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 2 / c / Solution 2026-10-25
View more
Keep total in the callee-saved register r4, and the first returned sum in the callee-saved register r5. Suppose the surrounding function has made an aligned stack frame with the local seven-halfword array at the current sp, occupying fourteen bytes in a sixteen-byte slot. One possible frame setup is push {r4,r5,r6,lr} followed by sub sp,sp,#16; the earlier code initializes total, regular, and special before this fragment.
    ldr  r0, =regular       @ assembler literal load of the global array address
    movs r1, #7
    bl   sum16
    movs r5, r0             @ first sum must survive the next call

    add  r0, sp, #0         @ current frame's local special array
    movs r1, #7
    bl   sum16
    muls r0, r5, r0         @ second sum times first sum
    adds r4, r4, r0         @ update total
The AAPCS32 permits each call to overwrite r0–r3, r12, and condition flags, but requires preservation of r4–r8, r10, r11, and sp. Thus both r4 and r5 remain valid even if sum16 is replaced by another conforming implementation. bl changes the link processor register lr, so the enclosing function saves its own return address in its prologue. Its epilogue can use add sp,sp,#16 and pop {r4,r5,r6,pc}. The frame uses thirty-two bytes in total, preserving the required eight-byte stack pointer alignment at both calls.[ref]
The two calls may be evaluated in this order. Assume the product and final addition fit the signed 32-bit result expected by the source program; unlike each individual seven-element sum, their product need not fit. The assembly language operations retain their low 32 bits if this assumption fails, whereas signed integer overflow in the C programming language has different semantics.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 1 / b / Solution 2026-10-25
View more
Use an explicit-stack depth-first tree traversal. Descend the left branch immediately and put each nonempty right subtree on a stack for later. For the same node declarations as in the paper, an original C programming language implementation is:
int sum_iter(tree t)
{
    tree pending[32];
    unsigned top = 0;
    int total = 0;
    while (t != NULL || top != 0) {
        if (t == NULL) {
            t = pending[--top];
        } else {
            total += t->data;
            if (t->right != NULL)
                pending[top++] = t->right;
            t = t->left;
        }
    }
    return total;
}
The loop invariant says that the accumulated labels plus the sums of the current subtree and all pending subtrees equal the original tree sum, with the unvisited subtrees disjoint. Visiting a node adds its label and replaces its subtree by its two children. Popping merely changes which pending subtree is current. When both current and pending subtrees are absent, the invariant proves the result.
At most one unvisited right sibling is pending at each level of the current ancestor path. If depth means the number of nonempty nodes on a longest root-to-leaf path, depth at most 32 requires at most 31 pending right siblings. A 32-word array is therefore sufficient; it also covers the convention that depth counts at most 32 edges. The depth promise makes unchecked pushes valid here. For arbitrary input, a production implementation should check capacity rather than overwrite its frame.
A corresponding Thumb instruction set implementation keeps the total in r4, the array base in r5, and its next-free address in r6:
.global sum_iter_asm
.thumb_func
sum_iter_asm:
    push {r4, r5, r6, lr}
    sub  sp, sp, #128        @ 32 pending pointers
    mov  r5, sp              @ base of pending array
    mov  r6, sp              @ empty stack: next-free equals base
    movs r4, #0
.Lvisit:
    cmp  r0, #0
    beq  .Ltake_pending
    ldr  r1, [r0, #0]
    adds r4, r4, r1          @ consume this node's label
    ldr  r1, [r0, #8]
    cmp  r1, #0
    beq  .Lleft
    str  r1, [r6, #0]        @ defer the nonempty right subtree
    adds r6, r6, #4
.Lleft:
    ldr  r0, [r0, #4]        @ continue down the left branch
    b    .Lvisit
.Ltake_pending:
    cmp  r6, r5
    beq  .Ldone
    subs r6, r6, #4
    ldr  r0, [r6, #0]
    b    .Lvisit
.Ldone:
    movs r0, r4
    add  sp, sp, #128
    pop  {r4, r5, r6, pc}
The stack pointer stays fixed while the array is used; r6 is a separate cursor inside that array. All callee-saved registers touched by the function are restored. Each nonempty node contributes its label exactly once. As in part (a), require that every partial total fits the signed result type; a representable final answer alone does not prevent overflow in a different summation order.
Read the full article
Processor register Created 2026-10-13 Updated 2026-10-24
View more
A small storage location within a CPU used by its instructions. Some hold data; others describe control state, such as the program counter or stack pointer. Saving and restoring processor registers lets different software threads reuse the same CPU while retaining separate execution contexts.
Read the full article
SP-relative addressing 2026-10-24
View more
SP-relative addressing adds an encoded displacement to the stack pointer. Scaling an immediate operand by a power of two reaches farther with the same field width but restricts the address grid. An eight-bit nonnegative field scaled by four reaches , whereas scaling it by sixteen reaches ; it does not provide every intervening byte address.
Read the full article
Stack alignment Created 2026-10-24 Updated 2026-10-31
View more
Stack alignment constrains the stack pointer to a multiple of a specified byte boundary. AAPCS32 requires word alignment generally and eight-byte alignment at public interfaces. Saving four 32-bit words preserves eight-byte alignment; saving three would change it by four bytes and may require padding before another call. Frame size and the alignment of local objects must be considered together.[ref]
Read the full article
Stack pointer Created 2026-10-13 Updated 2026-10-24
View more
A processor register identifying the current position in a stack, commonly a call stack; the exact convention depends on the architecture. Restoring a stack pointer selects the saved stack position, rather than copying the whole call stack.
Read the full article
Thread (computing) 2026-10-13
View more
A software thread is an execution stream within a operating-system process. Each software thread has its own execution context, including processor registers, an instruction pointer, and a call stack selected by its stack pointer. Software threads in the same operating-system process share its address space, global variables, dynamically allocated storage (the memory heap), and resources such as file descriptors. Separate register states let two software threads pause at different instructions and later resume correctly. A context switch saves and restores those states; it does not copy the entire shared address space. [ref][ref]
In the right half of the diagram under operating-system process, T1 and T2 access the same counter x at virtual address 0x1234. Their call stacks occupy separate regions of the same address space, and their saved processor registers can contain different values. A software thread's own call stack means the stack used for its calls, not a hardware protection boundary against another software thread. Another software thread with a suitable address can access that stack's live data, subject to the program's lifetime and synchronization rules. Sharing an address space enables easy communication and makes accidental interference possible.
Concurrency means that several activities can make progress over overlapping intervals; parallel execution means that several activities execute at the same instant. On one CPU execution slot, process scheduling can interleave software threads without simultaneous execution. Multiple processor cores can run eligible software threads in parallel, but merely creating software threads does not ensure parallel execution or a speedup.
Consider an explicitly abstract interleaving model: shared x starts at , and each of T1 and T2 performs three indivisible logical steps in its own order: load x into its own register r, add to r, then store r into x. Each load sees the latest preceding store in the displayed order. These model assumptions specify the example; they do not describe every programming language or every hardware memory model. In serial order T1 finishes all three steps before T2 starts, so T2 loads and stores .
An overlapping order instead gives T1 load , T2 load , T1 add to get r1 = 1, T2 add to get r2 = 1, T1 store , and T2 store . The load/store subsequence is therefore T1 load , T2 load , T1 store , T2 store : final , although each software thread incremented its register correctly. The second store replaces the first with the same value, losing one intended update. This race condition is possible even with interleaving on a single CPU.
Figure 1.
Two abstract load/add/store increments retain separate registers but can leave the shared counter at instead of the serial result
. Details.
This is not an unprotected C implementation example. Conflicting unsynchronized accesses to an ordinary non-atomic C object from different software threads can constitute a data race, which has undefined behavior; the abstract trace is not a prediction of that program's allowed outcomes. [ref]
The repair explains why synchronization matters: mutual exclusion around the whole load/add/store sequence prevents the other software thread from starting an increment halfway through it. Alternatively, an appropriate atomic operation can make the complete increment one indivisible read-modify-write. In the toy model, either repair makes the two increments take effect in an order, producing . Making only each load and each store an atomic operation still permits the displayed lost update. [ref]
The attraction is independently progressing activities with direct access to shared data: a user-interface software thread can handle input while another waits for input-output, and workers can divide independent pieces of a large calculation among available cores. The first benefit can exist on one CPU; the second requires suitable work and execution resources. Context switches, synchronization, register-state records and extra call stacks consume time or computer memory, so the useful partition depends on the workload. [ref]
Read the full article