17. COMP1521 Revision

COMP1521 Revision#

COMP1521 is really one long story about what a running program looks like once the comfortable abstractions of C are peeled back.

flowchart TD
    C["C source"] --> MIPS["instructions<br/>and calling conventions"]
    C --> DATA["integer, float,<br/>text and memory representations"]
    C --> OS["system calls<br/>and files"]
    OS --> PROC["processes and IPC"]
    PROC --> THREAD["threads and<br/>synchronisation"]

This note is a map, not a substitute for the topic notes. Start with Preamble for the course's overall machine model, then use this map to find gaps and decide what to practise next.

The Core Story#

You should be able to explain each of these transitions:

1. C constructs become sequences of MIPS instructions.
2. Instructions operate on finite bit patterns in registers and memory.
3. Those bits represent integers, floating-point values, addresses, instructions and encoded text according to context.
4. User programs request privileged operations through system calls and library wrappers.
5. The OS gives each process an execution environment and virtualised resources.
6. Processes communicate through inherited and redirected file descriptors.
7. Threads share an address space, introducing efficient communication and synchronisation problems.

Operating Systems joins the two halves of this story: it explains how a program running ordinary instructions crosses a controlled boundary to request files, processes and other protected services.

MIPS#

Revise Using MIPS, MIPS Control, MIPS Data and Memory and MIPS Functions until you can translate small C programs without guessing. Use Running MIPS to make tracing and debugging part of that translation process rather than an afterthought.

You should be able to:

• choose registers according to the calling convention;
• construct if, if/else, loops and short-circuit logic using branches and labels;
• calculate array and struct addresses;
• use lb, lbu, lh, lw, sb, sh and sw with correct sizes and alignment;
• write a function prologue, body and epilogue;
• save $ra when a function calls another function;
• preserve every $s register your function changes;
• pass the first arguments in $a0 to $a3 and return through $v0;
• trace memory and registers by hand.

A translation routine#

When translating C to MIPS:

1. simplify the C into explicit assignments, conditions, labels and gotos;
2. decide where each long-lived C value lives;
3. translate one simple statement at a time;
4. preserve the original control-flow structure;
5. test boundaries: zero iterations, first element, last element and negative values.

Do not optimise while the program is still wrong. A boring, literal translation is much easier to verify.

Bit Representations#

From Integers and Bitwise Operations, revise:

• binary and hexadecimal conversion;
• unsigned ranges;
• two's-complement signed ranges and negation;
• sign extension versus zero extension;
• overflow and truncation;
• bit masks, shifts, setting, clearing and toggling bits.

From Floating Point, revise:

• sign, biased exponent and fraction fields;
• normalised values and the implicit leading one;
• zero, subnormal, infinity and NaN encodings;
• why many decimal fractions cannot be represented exactly.

For every bit question, write the width beside the value. 0xFF can mean 255, -1, a byte of a UTF-8 sequence or part of a larger word; the representation and operation determine its meaning.

Files and File Systems#

From File Systems and Files and Streams, know both interfaces:

Be able to explain short reads/writes, EOF (read() == 0 vs EOF), errno, binary-safe copying, and stdio buffering modes. fgetc() returning int and text functions failing on embedded null bytes are favourite exam traps.

From File System Metadata and Directories, practise:

• decoding octal permissions;
• distinguishing file and directory permission meanings;
• using stat(), lstat() and the S_IS... macros;
• explaining inodes, directory entries, hard links and symlinks;
• iterating with opendir(), readdir() and closedir();
• safely constructing full paths during traversal.

Unicode#

From Unicode and UTF-8, be able to move in both directions:

code point -> payload bits -> UTF-8 byte templates -> hexadecimal bytes
hexadecimal bytes -> validate prefixes -> payload bits -> code point

Know the one-to-four-byte prefix table without needing to rediscover it. Practise identifying leading and continuation bytes with bit masks. Keep bytes, code points and user-perceived characters separate.

Processes#

From Processes, distinguish these operations precisely:

Draw a process tree for every non-trivial fork() question. Trace both return values. For waitpid(), use the status macros rather than treating the status word as a raw exit code.

Pipes and Redirection#

From Pipes and File Redirection, remember:

pipefd[0] = read end
pipefd[1] = write end

Be able to explain why the pipe is created before the children, why dup2() occurs before exec(), and why every process must close unused ends. A pipeline should start its connected programs before waiting for them, otherwise a full pipe can deadlock.

The 26T2 final-exam guidance places complex process/thread creation and pipes towards the challenge end of the paper. That changes the order in which you should spend revision time, not the semantics you need to understand.

Threads#

From Concurrency and Threads, know:

• what threads share and what remains per-thread;
• the signatures of pthread_create() and pthread_join();
• how to give every thread a stable argument object;
• why an apparently single C expression can be several machine operations;
• the definition of a data race and critical section;
• how a mutex establishes mutual exclusion;
• how inconsistent lock order causes deadlock;
• which atomic compound operations are indivisible.

When diagnosing concurrent code, ask:

1. Which memory locations are shared?
2. Can two threads access one at overlapping times?
3. Can either access write?
4. What establishes the required ordering or exclusion?
5. Does every path obey the same rule?

How to Practise#

Reading produces familiarity; writing and tracing produce exam skill. For each topic:

1. solve one small question without notes;
2. compile and test it;
3. add boundary cases beyond the supplied examples;
4. explain the bug in each failed attempt;
5. rewrite the solution once, cleanly, from memory.

Use man while practising. The 26T2 course guidance explicitly makes the command-line manual available in the restricted exam environment, while the course website and personal files are unavailable. Useful queries include:

man 2 open
man 3 fopen
man 2 stat
man 2 waitpid
man 3 pthread_create
man -k "process wait"

Exam Strategy#

The Week 10 slides describe a programming exam with separate C or MIPS files, examples, autotests and question-specific restrictions. The details are term-specific, so verify the current course announcement before relying on dates or logistics. The durable strategy is:

• read every restriction before coding;
• create the exact requested filename;
• match the input/output format exactly;
• use examples as evidence, not as the entire specification;
• write your own boundary tests;
• leave time to submit every substantial attempt;
• keep code readable enough that you can debug it under pressure.

Passing supplied autotests does not prove the program is correct. Hidden tests target assumptions which the examples did not expose.

Final Checklist#

• [ ] I can write and trace MIPS control flow.
• [ ] I can write a correct non-leaf MIPS function.
• [ ] I can compute addresses for arrays and structs.
• [ ] I can convert and reason about fixed-width bit patterns.
• [ ] I can decode a simple IEEE 754 value.
• [ ] I can copy a binary file safely.
• [ ] I can inspect permissions and directory entries.
• [ ] I can encode and decode UTF-8 by hand.
• [ ] I can trace fork(), exec() and waitpid().
• [ ] I can wire a pipe using dup2() and close the correct ends.
• [ ] I can create/join threads and spot lifetime bugs.
• [ ] I can identify a data race or deadlock and explain the fix.