17. COMP1521 Revision

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.

Practice: The Boundary#

1. Why is a C library call not necessarily a system call, and why is a system call not necessarily a context switch?

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.

Practice: MIPS#

2. In the MIPS calling convention, which side of a call is responsible for preserving an $s register changed by the callee, and why must a non-leaf function normally preserve $ra?

3. An int32_t array begins at 0x10010000. What address contains element 5, and which MIPS load instruction retrieves the complete signed 32-bit element?

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.

Practice: Representations#

4. The byte pattern 0xFF is observed in memory. Give three distinct meanings it could have, and state what extra information chooses between them.

5. A binary32 value has bits 0 01111111 00000000000000000000000. Decode it. What category would the same fields have if the exponent became 11111111?

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.

Practice: Files#

6. A regular file offset starts at 4. read(fd, buf, 10) returns 6; lseek(fd, -3, SEEK_CUR) succeeds; then read(fd, buf, 2) returns 2. What is the final offset?

7. A file-copy loop calls write(out, buffer, n_read) once and assumes success whenever the result is not -1. Describe the missing control flow.

Unicode#

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

Encoding moves from a code point to payload bits, places those bits into the correct UTF-8 byte template, then writes the resulting bytes. Decoding reverses the path: validate the byte prefixes, recover the payload bits, then reconstruct the 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.

Practice: Unicode#

8. The bytes 41 E2 82 AC 80 are presented as UTF-8. Decode every complete valid code point from the beginning, then identify exactly where and why validation fails.

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.

Practice: Process Status#

9. waitpid() succeeds and stores a value in status. Why is printf("%d", status) not a reliable way to print the child's exit code? Give the correct decision sequence for normal exit and signal termination.

Pipes and Redirection#

From Pipes and File Redirection, remember:

Remember the direction by the operation each end permits: pipefd[0] is the read end and pipefd[1] is the 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.

Practice: Pipelines#

10. A shell-style pipeline waits for the producer before creating the consumer. Explain the deadlock and give the required process/descriptor ordering.

Synthesis Trace: Descriptors Survive fork() and exec()#

Suppose a process opens a regular file as descriptor 3, duplicates it onto standard input, then forks. Assume explicit synchronisation guarantees that the parent's two-byte read completes before the child executes and reads from its standard input.

Both processes' descriptor 0 entries refer to the same inherited open file description, so they share one current offset. If it began at 0, the trace is:

fork() duplicates descriptor-table entries, not independent copies of the underlying open file description. exec() replaces the program but preserves an open descriptor unless its close-on-exec flag is set. The explicit ordering above matters: without synchronisation, parent and child scheduling would make it unsafe to predict which process reads which bytes first.

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?

Practice: Shared State#

11. Two threads update total and count, and readers require them to describe the same snapshot. Why is protecting only total inadequate, even if count is atomic?

Common Mistakes#

The topic notes explain each rule where it is needed. This is the single course-wide checklist to use when reviewing a solution. Do not merely memorise the bullets: for each one, make sure you can construct a small failing example and explain the correction.

MIPS and Memory#

• Confusing an address with the value stored at that address. la obtains an address; a load such as lw follows an address and retrieves data.
• Treating array indexes as byte offsets. Multiply the index by the element size before adding it to the base address.
• Using the wrong transfer width, such as lw for a char, or choosing lb where an unsigned byte requires lbu.
• Assuming a pseudo-instruction must correspond to one real instruction, or assuming every immediate can hold an arbitrary 32-bit value.
• Reversing a branch condition while translating if, a loop, break, or continue.
• Assuming $t registers, argument registers, or $ra survive a function call.
• Modifying an $s register without restoring its incoming value, or restoring stack values from offsets calculated after $sp has already moved.
• Forgetting that a non-leaf function's own jal overwrites $ra.
• Allocating and deallocating different stack-frame sizes, so $sp does not return to its entry value.
• Ignoring alignment or struct padding when calculating an address by hand.

Representations#

• Reasoning about a bit pattern without first writing down its width and whether it is signed or unsigned.
• Assuming signed overflow wraps in C merely because unsigned arithmetic does.
• Confusing sign extension with zero extension, especially because the u in addiu does not select zero extension.
• Shifting a signed value when the intended operation is on raw bits, or shifting by an amount outside the type's valid range.
• Expecting every decimal fraction to have an exact binary floating-point representation, or comparing calculated floating-point values for exact equality without justification.
• Treating NaN like an ordinary number; even NaN == NaN is false.

Files, Streams, and Directories#

• Treating a file descriptor as a pointer or assuming the same descriptor number identifies the same object in another process.
• Assuming read() or write() transfers the entire requested count, or storing an ssize_t result in an unsigned type before checking for -1.
• Treating arbitrary bytes returned by read() as a NUL-terminated C string.
• Supplying O_CREAT without a mode, writing decimal 644 instead of octal 0644, or reading errno when no function has reported an error.
• Confusing a buffered FILE * stream with its underlying descriptor, including closing it with close(fileno(stream)) instead of fclose().
• Storing fgetc() in char before comparing it with EOF, or using text functions on binary data containing zero bytes.
• Forgetting that "w" truncates, that stdio buffers are duplicated by fork(), or that mixed stream/descriptor access requires coordination.
• Thinking a filename is stored in the inode, treating a hard link as a shortcut, or assuming removing a symbolic link removes its target.
• Applying regular-file permission intuition directly to directory traversal and entry creation.

Processes, Pipes, and Threads#

• Thinking fork() starts a different program or that exec() creates an additional process.
• Assuming the parent must run before the child, or reading the encoded waitpid() status as a raw exit code.
• Creating a pipe after the processes diverge, reversing its read and write ends, or forgetting to close every unused copy.
• Waiting for a producer before starting its consumer, allowing the finite pipe buffer to create a deadlock.
• Treating a pipe as a message or C-structure channel instead of a byte stream with an application-defined protocol.
• Assuming threads have separate globals or heaps, or assuming one line of C is automatically one atomic operation.
• Protecting writers but not readers, using different mutexes for one invariant, or acquiring multiple mutexes in inconsistent orders.
• Passing a thread a pointer to changing loop storage or returning a pointer to a worker's expired stack frame.

Unicode#

• Using “Unicode”, “code point”, “UTF-8 byte”, “glyph”, and “character” as though they were interchangeable.
• Using strlen() to count code points or user-perceived characters.
• Counting leading-byte shapes without checking continuation bytes, truncation, overlong forms, surrogates, and the U+10FFFF limit when validity matters.

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"

Practice: Cumulative Challenge#

12. A program reads a file containing UTF-8, passes the bytes through a pipe, and counts characters in a worker thread. Name one boundary or lifetime mistake possible at each layer: file I/O, pipe setup, UTF-8 decoding and thread communication.

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.