Exam practice

Start R0 at 1. In the loop: show R0, add 1, compare with 6 (or 5), and branch back while it is still less.

It shows 1 2 3 4 5: after 5 is shown, R0 becomes 6, the compare says equal, BLT isn’t taken, and it halts. (CMP R0, #5 with BLT would stop after 4: check the last time round.) Other correct programs are fine; check yours in the widget.

• 0: 2006 = LOAD R0, 6
• 1: 2107 = LOAD R1, 7
• 2: 6001 = SUB R0, R1
• 3: F003 = OUT R0
• 4: 0000 = HALT
• 5: 0000 (not used)
• 6: 0050 = the number 80 (hex 50)
• 7: 001E = the number 30 (hex 1E)

It loads 80 and 30, works out 80 − 30, and shows 50. Words 6 and 7 are data, not instructions: the processor never reaches them, because HALT stops it first. (If HALT were missing, it would carry on into address 5, which also reads as HALT; a program that runs into its data may do nonsense.)

A branch may name a label that comes later in the program: BGT show is at address 3, but the line labeled show is at address 6. When the assembler reaches BGT show, it hasn’t yet seen show, so it can’t write its address.
On the first pass it gives every line an address (one word for each instruction or DATA) and records each label with its address in a symbol table: show 6, mina 8, bikash 9. On the second pass it turns every line into machine code, looking up each label in the table: BGT show becomes C006.

• a.Bits 1 and 3 are 1: the battery is charging and there is an overload. Bit 0 is 0, so it is on mains power, and bit 2 is 0, so the battery isn’t low.
• b.Test overload: AND 0000 1000 gives 0000 1000, not 0, so there is an overload. Clear charging: AND 1111 1101 gives 0000 1000. Flip bit 0: XOR 0000 0001 gives 0000 1011.

c.

d. Left 2: 0010 1000 = 40 (10 × 4). Right 1: 0000 0101 = 5 (10 ÷ 2).

• a.Distributive: $A \cdot (B + \overline{B})$. Complement: $A \cdot 1$. Identity: $A$.
• b.De Morgan (break the bar, change the sign): $\overline{A} \cdot \overline{\overline{B}}$. Double negation: $\overline{A} \cdot B$.
• c.Distributive, OR form ($A + B \cdot C = (A + B) \cdot (A + C)$, read from right to left): $A + B \cdot \overline{B}$. Complement: $A + 0$. Identity: $A$.

Truth table for a.:

The last column is the same as A in every row.

a. Q is 1 in rows 3 (011), 5 (101), 6 (110) and 7 (111):
$$Q = \overline{A}\,B\,C + A\,\overline{B}\,C + A\,B\,\overline{C} + A\,B\,C$$
b. On the map (rows A, columns BC in the order 00, 01, 11, 10) the 1s are cell 3 (row 0, column 11) and cells 5, 7, 6 (row 1, columns 01, 11, 10). Three loops of two, all through cell 7: cells 3 and 7 (B and C stay 1): BC; cells 5 and 7 (A and C stay 1): AC; cells 7 and 6 (A and B stay 1): AB.
$$Q = A \cdot B + A \cdot C + B \cdot C$$
Three 2-input AND gates and an OR of three (two 2-input OR gates): five gates, against four 3-input ANDs, an OR of four and NOT gates for the long form.
c. Rows 1, 3, 5, 7 are 0001, 0011, 0101, 0111: A = 0 and D = 1 in all four, B and C change. On the map they are the middle two columns (CD = 01 and 11) of the top two rows (AB = 00 and 01): a loop of four, $\overline{A} \cdot D$. Rows 12 and 13 are 1100 and 1101: A = 1, B = 1, C = 0, D changes: a loop of two, $A \cdot B \cdot \overline{C}$. So $Q = \overline{A} \cdot D + A \cdot B \cdot \overline{C}$. (Row 13 could also be looped with row 5 above it, but that loop would be no bigger and isn’t needed.)

a. A D flip-flop copies its input D to its output Q only at the clock’s rising edge (a tick). At every other moment it ignores D, so Q holds the bit it took at the last tick until the next one.
b.

c. The PC’s next value, PC + 1, is worked out from the PC itself and fed back into it. With latches, the new PC would at once go round through the adder and make another new value, and the PC would race on with no control. With D flip-flops on a clock, all the PC’s bits take in the next address together at one tick and then hold it steady for a whole tick, while the processor fetches the instruction at that address and the next address settles.

• a.Von Neumann has one memory for instructions and data and one bus, so instructions and data take turns (the Von Neumann bottleneck); Harvard has two memories, each with its own bus, so an instruction can be fetched while data is read or written. Von Neumann’s memory can be shared out between program and data as needed; Harvard’s two memories have fixed sizes. Von Neumann is used for the main memory of general-purpose computers (laptops, phones); Harvard in small controllers (a rice cooker, a micro:bit), signal processors, and inside each core, where the cache is split into an instruction cache and a data cache.
• b.Any three: RISC has fewer, simpler instructions, CISC more, some doing several steps; RISC instructions are all one length, CISC’s vary; in RISC only LOAD and STORE reach memory, in CISC many instructions can; RISC instructions take about one tick each and pipeline easily, some CISC ones take many ticks; RISC programs have more instructions, CISC programs fewer; RISC chips decode more simply with fewer transistors. Our model is RISC: a short list of simple instructions, each exactly one word, and only LOAD and STORE reach memory (a load/store design).
• c.Phones run on batteries: RISC’s simple decoding needs fewer transistors and less power. Many laptops use CISC so that the huge number of programs already written for that instruction set still run; inside, they break each complex instruction into simple micro-operations.

Training is mostly multiplying inputs by weights and adding them up, the same step done to a huge number of numbers, and none of these multiplications needs another’s answer. In Unit 8’s network, one digit through the hidden layer alone is 196 × 32 = 6,272 multiplications. A GPU has thousands of simple cores, which work in groups doing the same instruction on different numbers at once: SIMD, single instruction, multiple data. So it does tens of thousands of multiplications in a tick, where a CPU, with a few fast cores, does perhaps a hundred or so.
A CPU is better at a program that must go step by step, each step needing the answer of the one before, or one full of different choices (if and else), such as a word processor, a compiler, or the rules of a game: its few cores are each far faster and cleverer than a GPU’s, and a GPU’s many cores can’t help when there is only one thing to do at a time.

Python uses both: it compiles the program into bytecode, and its virtual machine, an interpreter, carries out the bytecode one instruction at a time. Imported modules’ bytecode is kept in .pyc files in __pycache__.

def f(r):    return r * r * 3

(Any name for the function will do; the first line shows where its body starts.) RESUME starts the function. LOAD_FAST_BORROW puts r on the stack, twice. BINARY_OP 5 (*) takes both off and puts r × r back. LOAD_SMALL_INT puts 3 on the stack. The second BINARY_OP multiplies r × r by 3, leaving the answer on the stack, and RETURN_VALUE gives it back.

From the top (high addresses) down:

• Stack: a frame for each function call not yet finished, holding its local variables and its return address. It grows down with each call and shrinks with each return.
• (free space between them)
• Heap: objects made while the program runs (lists, text, objects of classes), kept until they are freed. It grows up as more is needed.
• Global data: variables that last as long as the program.
• Code: the program’s machine code, which doesn’t change.

The stack and the heap grow, towards each other.

The first CALL quad (address 1) pushed 2. Inside quad, the second CALL double (address 8) pushed 9. The first double’s return address, 8, was popped when it returned. So the stack holds 9 on top and 2 under it.
A fixed place would hold only one return address. When quad calls double, double’s return address would overwrite quad’s, and quad could never get back to the main program. A stack keeps every unfinished call’s address, and the last one pushed is the first one needed: last in, first out, exactly the order in which calls finish.

• Ready → running: the scheduler picks it for a core.
• Running → ready: its time slice is over (a timer interrupt), and another process gets the core.
• Running → waiting: it asks for something slow, a file, a key, the network, with a system call.
• Waiting → ready: the device is done, and its interrupt tells the kernel, which marks the process ready.

A waiting process couldn’t do anything with a time slice: it has nothing to work on until its data arrives. Giving it turns would only waste the core, so the scheduler gives them to the ready processes, and the interrupt brings the waiting one back when its data comes.

FCFS: P1 0–5, P2 5–8, P3 8–16, P4 16–18. Waits: P1 0, P2 4, P3 6, P4 13. Average 5.75 ms.
SJF: P1 0–5 (the only one there at 0); then the shortest ready, P4 5–7, P2 7–10, P3 10–18. Waits: P1 0, P2 6, P3 8, P4 2. Average 4 ms.
Round robin (2 ms): P1 0–2, P2 2–4, P3 4–6, P1 6–8, P4 8–10 (done), P2 10–11 (done), P3 11–13, P1 13–14 (done), P3 14–18 (done). Waits (finish − arrival − needed): P1 14 − 0 − 5 = 9, P2 11 − 1 − 3 = 7, P3 18 − 2 − 8 = 8, P4 10 − 3 − 2 = 5. Average 7.25 ms.
c. SJF gives the shortest average here. Under SJF (and SRT) a long process such as P3 could starve if short processes kept arriving. A scheduler prevents it by aging: raising a process’s priority the longer it waits, until it must run. (Round robin, which gives every process a turn, can’t starve one.)

5,000 ÷ 4,096 = 1, remainder 904: page 1, offset 904. Page 1 is in frame 2, which starts at 2 × 4,096 = 8,192. Physical address = 8,192 + 904 = 9,096.
20,000 is in page 4 (20,000 ÷ 4,096 = 4, remainder 3,616), and the table has no page 4. The hardware stops the process and calls the kernel, which ends it (a segmentation fault). That is good: a buggy or harmful program can’t read or spoil memory that isn’t its own, so it can crash only itself, not other programs or the operating system.

• a.Pages are all the same size; segments are as long as the part of the program they hold. Paging divides memory without regard to what is in it; segmentation divides it by the program’s own parts (code, data, stack). Segments leave odd-sized gaps in memory as programs come and go; any free page fits any page.
• b.Thrashing is when a computer spends nearly all its time moving pages between RAM and storage, and hardly any running programs. It happens when the processes in use need much more memory than there is RAM, so the pages they need are out on storage almost every step, and storage is thousands of times slower than RAM. To stop it: close programs (or run fewer at once), or add more RAM.

Both threads read 20 before either wrote, so both wrote 21: one sale is lost. This is a race condition.
With a lock around the three instructions (the critical section), a thread must take the lock before its LOAD and let go after its STORE. If A holds it, B must wait at the lock until A has stored 21; then B loads 21 and stores 22. The three steps of one thread can no longer be mixed with the other’s.

0.75 = 0.11 in binary = 1.1 × 2⁻¹. Sign 0; exponent −1 + 7 = 6 = 0110; mantissa 100. So 0 0110 100.
9 = 1001 in binary = 1.001 × 2³. Sign 0; exponent 3 + 7 = 10 = 1010; mantissa 001. So 0 1010 001.
0.2: multiplying by 2 gives the bits 0.0011 0011 0011…, repeating for ever, because 0.2 = 1/5 can’t be made from halves, quarters, eighths and so on. Any format keeps only a fixed number of mantissa bits, so it must cut the pattern off and round: what is kept is only the nearest number it can hold.

It never prints “done”: the loop never ends. 0.3 can’t be stored exactly, and each addition is rounded, so after ten additions total is very close to 3.0 but not exactly 3.0 (it is 2.9999999999999996), and != stays true; after that it keeps growing past 3.
Two fixes:

total = 0.0while total < 3.0 - 1e-9:     # stop once it is (almost) 3    total = total + 0.3print(round(total, 2))

3.0

count = 0                     # count tenths as whole numberswhile count != 30:    count = count + 3print(count / 10)

3.0

The first compares with a tolerance instead of ==/!=; the second keeps whole numbers, which are exact, and makes a float only to show it.

The first: NumPy keeps the count in 16 bits, so 32,767 + 1 overflows and wraps round to −32,768, as in our model processor. Python’s own int joins as many pieces as it needs, so 2 ** 100 is exact.
The second: a double keeps about 16 significant digits. Near 2⁵³ the gap between one double and the next is 2, so adding 1 changes nothing. The largest double is about 1.8 × 10³⁰⁸; anything bigger becomes infinity, inf.
The third: 10⁴⁰⁰ is a perfectly good Python int, but it is beyond the largest double, so it can’t be turned into a float: an OverflowError.

Any one, done and explained. For example: in the model processor, again called itself with no way to stop. It showed 1 to 28 and then stopped with a stack overflow: every call pushed a return address, and after 27 the stack had grown down to the end of the program, in a memory of only 32 words. A programmer avoids it by making sure every chain of calls ends (a base case), or by using a loop; in Python, the recursion limit stops such a program with a RecursionError before the real stack runs out.
Other good answers: 32,767 + 1 in a 16-bit integer gives −32,768 (overflow: 16 bits; check sizes, or use more bits); 0.1 + 0.2 printing 0.30000000000000004 (binary fractions; compare with a tolerance, count paisa); 2.0 ** 53 + 1 equals 2.0 ** 53 (a double keeps about 16 digits; use ints for big whole numbers); long time slices making the music stutter in the scheduler (one core shared; shorter slices and priorities).