Computer Systems

The idea

Explore

Worked example

unsigned short u = s;     /* same 16 bits, unsigned reading   */
int  i = u;               /* widen an unsigned value          */
int  j = s;               /* widen a signed value             */
signed char k = (signed char) s;   /* keep the low 8 bits     */

1. What are the 16 bits of s?

   $300 = 256+32+8+4$ is 0x012C. Its negation in 16 bits is $2^{16}-300 = 65236$, which is 0xFED4. (Check: flip the bits of 0x012C to get 0xFED3, then add 1.)

2. What value does u hold?

   The same bits read as unsigned: $-300+2^{16}=65236$.

3. Widening to 32 bits: what are i and j?

   An unsigned value is zero-extended: i is 0x0000FED4 $=65236$. A signed value is sign-extended (the top bit is copied into the new bits): j is 0xFFFFFED4 $=-300$. Each extension keeps the value of its own reading.

4. What is k?

   Truncation keeps the low byte 0xD4 $=212$. Its top bit is 1, so as a signed char it is $212-256=-44$. Truncation is reduction mod $2^8$: $-300 \equiv -44 \pmod{256}$.

Check your understanding

Practice

The idea

Explore

Worked example

1. Write $6.75$ in binary and normalize it.

   $6.75 = 4+2+\tfrac12+\tfrac14 = 110.11_2 = 1.1011_2\times 2^2$. So $E=2$ and the digits after the point are 1011.

2. What goes in the exponent field?

   $e = E + B = 2+7 = 9$ = 1001. It is neither 0 nor 15, so the number is normalized.

3. There are four fraction digits but only three bits. Round.

   1.101|1: the dropped part is exactly half of the last kept place, a tie. Round to even: 1.101 ends in 1, so round up to 1.110. The stored value is $-1.75\times 2^2=-7$.

4. Give the bit pattern, then check it in the explorer.

   1 1001 110 = 0xCE. Type -6.75 above: the explorer shows the same bits, stored value $-7$, and an error of $0.25$, half the gap of $0.5$ between neighbours in $[4,8)$.

5. What are the smallest positive value and the largest finite value of this format?

   Smallest: the denormal 0 0000 001 $=\tfrac18\times2^{1-7}=2^{-9}\approx0.00195$. Largest: 0 1110 111 $=1.875\times2^{14-7}=240$.

Check your understanding

Practice

The idea

long fact(long n) {
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}

Explore

Worked example

void incr(long *p, long d) { *p += d; }

long twice(long x) {
    long v = x;
    incr(&v, 10);
    return v * 2;
}

1. Why can't v stay in a register?

   incr needs a memory address for it: &v. Registers have no addresses, so twice must reserve a stack slot for v.

2. Write plausible x86-64 code for twice.

   twice:
       subq   $24, %rsp        # room for v (plus padding)
       movq   %rdi, 8(%rsp)    # v = x
       leaq   8(%rsp), %rdi    # 1st argument: &v
       movl   $10, %esi        # 2nd argument: 10
       call   incr
       movq   8(%rsp), %rax    # reload v: incr changed it
       addq   %rax, %rax       # v * 2
       addq   $24, %rsp        # free the frame
       ret

3. Why 24 bytes, when v needs only 8?

   The x86-64 ABI requires %rsp to be a multiple of 16 at every call. On entry to twice, the caller's call has just pushed 8 bytes, so %rsp is 8 more than a multiple of 16. Subtracting 24 restores the alignment and leaves room for v.

4. What does incr compile to? Does it need a frame?

   addq %rsi, (%rdi) followed by ret. It calls nothing and keeps nothing, so beyond the return address it needs no stack at all.

5. What goes wrong if twice returned &v instead?

   The slot is freed by addq $24, %rsp. The next call made by the caller reuses those bytes for its own frame, so the returned pointer would point at whatever that call stores there.

Check your understanding

Practice

The idea

Explore

Worked example

1. What is the throughput without pipelining?

   One register at the end: period $240+15=255$ ps, so $1000/255\approx 3.92$ GIPS, and latency 255 ps.

2. Split into three equal stages of 80 ps. Throughput and latency?

   Period $80+15=95$ ps: $10.53$ GIPS, about 2.7 times faster. Latency grows to $3\times95=285$ ps.

3. Suppose the logic only splits as 60, 120, 60 ps. Now?

   The slowest stage sets the clock: period $120+15=135$ ps, $7.41$ GIPS. The two short stages sit idle for half of every cycle.

4. Go deeper: six equal stages of 40 ps.

   Period $55$ ps, $18.18$ GIPS, latency $330$ ps. Doubling the stages from three to six gave only a 1.73 times speedup, because the 15 ps of register delay is now $15/55\approx27\%$ of every cycle.

Check your understanding

Practice

irmovl $1, %eax
addl   %eax, %ecx
mrmovl 8(%ecx), %edx
addl   %edx, %eax

The idea

long prod(long *a, long n) {
    long acc = 1;
    for (long i = 0; i < n; i++)
        acc = acc * a[i];        /* needs the previous acc */
    return acc;
}

long prod2(long *a, long n) {     /* k = 2 accumulators */
    long acc0 = 1, acc1 = 1, i;
    for (i = 0; i + 1 < n; i += 2) {
        acc0 = acc0 * a[i];
        acc1 = acc1 * a[i+1];       /* independent of acc0 */
    }
    for (; i < n; i++)
        acc0 = acc0 * a[i];
    return acc0 * acc1;
}

Explore

Worked example

1. What CPE do you expect, and why?

   One chain of dependent multiplies: each starts only when the previous result is ready, so $\mathrm{CPE}=L=4$.

2. With $k$ accumulators and one unit, what is the CPE?

   $\max(4/k,\ 1)$. It improves until $k=4$, where a new multiply starts every cycle; more accumulators cannot help a single unit.

3. With $u$ units, how many accumulators are needed to reach the throughput bound?

   We need $L/k\le 1/u$, so $k\ge L\cdot u$. Enough chains have to be in flight to keep $u$ units each busy for $L$ cycles: with $u=2$, $k=8$. Try L = 3, u = 2 in the explorer: the CPE stops improving at $k=6$.

4. Is the rewrite allowed?

   Only if a slightly different rounding is acceptable. The products are mathematically equal, but floating-point multiplication is not associative, so the last bits can differ.

5. The loop speeds up from CPE 4 to CPE 1. How much faster is the whole program?

   Amdahl with $\alpha=0.3$, $k=4$: $S=1/(0.7+0.075)=1/0.775\approx1.29$. Even an infinitely fast loop would give only $1/0.7\approx1.43$.

Check your understanding

void scale(long *a, long n, long *f) {
    for (long i = 0; i < n; i++)
        a[i] = a[i] * *f;
}

Practice

The idea

int a[8][8];        /* row i starts 32 bytes after row i-1 */
for (i = 0; i < 8; i++)            /* row by row: stride 1 */
    for (j = 0; j < 8; j++)  s += a[i][j];
for (j = 0; j < 8; j++)            /* column by column: stride 8 */
    for (i = 0; i < 8; i++)  s += a[i][j];

Explore

Worked example

1. Find $S$, $s$, $b$, $t$, and split the address 0x1A4.

   $S=128/16=8$, so $s=3$, $b=4$, $t=12-3-4=5$. 0x1A4 = 00011 010 0100: tag 3, set 2, offset 4. Check: $3\cdot128+2\cdot16+4=420=$0x1A4.

2. What is the miss rate of the first pass?

   A block holds 4 ints. The first access to each block misses and the next three hit: 25% misses, all of them cold.

3. And of the second pass?

   The array is 256 bytes, twice the cache. By the end of the first pass, v[32..63] has replaced v[0..31] in every set ($v[i]$ and $v[i+32]$ are 128 bytes apart, so they share a set). The second pass starts on evicted blocks and again misses 25%, now capacity misses.

4. Reorganize the work: do both passes over v[0..31], then both over v[32..63]. Miss rate?

   Each half is exactly 128 bytes, so it stays in the cache during its second pass, which now hits every time. Overall: 16 misses in 128 accesses, 12.5%. Working on a cache-sized piece at a time is the idea behind blocking.

Check your understanding

Practice

The idea

Explore

Worked example

1. Trace gcc main.o libutil.a libfmt.a.

   After main.o: $U=\{\texttt{fmt\_time}\}$. Scanning libutil.a: no member defines fmt_time, so nothing is taken. Scanning libfmt.a: its member defining fmt_time is added, and $U=\{\texttt{pad}\}$. End of the command line with $U\neq\varnothing$: undefined reference to `pad'.

2. Fix the order.

   gcc main.o libfmt.a libutil.a. When libutil.a is scanned, pad is already in $U$. The rule: a library must come after every file that uses it.

3. Now pad also calls fmt_num, which lives in libfmt.a. What happens with the fixed command?

   The member with pad adds fmt_num to $U$, but libfmt.a was already scanned: undefined reference to fmt_num. (Unless fmt_num happens to sit in the same member as fmt_time, which was already taken in whole.)

4. How do you link two libraries that depend on each other?

   Name one of them twice: gcc main.o libfmt.a libutil.a libfmt.a. (Alternatively, merge them into one library.)

Check your understanding

Practice

The idea

Explore

Worked example

int main(void) {
    int x = 5;
    pid_t pid = fork();
    if (pid == 0) {            /* child */
        x = x * 2;
        printf("child: %d\n", x);
        exit(0);
    }
    waitpid(pid, NULL, 0);     /* parent */
    x = x + 1;
    printf("parent: %d\n", x);
    return 0;
}

1. What does this print?

   child: 10 then parent: 6.

2. Why doesn't the child's x = 10 show up in the parent?

   After fork, each process has its own copy of x at the same virtual address. Changes in one are invisible to the other. (The kernel shares the physical pages until one side writes, but that's an implementation detail.)

3. Is the order of the two lines guaranteed?

   Yes. The parent's printf comes after waitpid, which returns only after the child has exited, and the child prints before it exits.

4. Delete the waitpid line. Now?

   Both orders are possible. Nothing connects the parent's print to the child's.

5. Restore waitpid but delete the child's exit(0). Now?

   The child falls through. It calls waitpid(0, NULL, 0), which waits for any child in its process group; it has no children, so the call fails at once. It prints parent: 11 and exits. The real parent then reaps it and prints parent: 6. Output: child: 10, parent: 11, parent: 6, in that order.

Check your understanding

Practice

printf("A\n");
if (fork() == 0)
    printf("B\n");
else
    printf("C\n");
printf("D\n");

The idea

Explore

Worked example

1. How big is a single flat page table per process?

   $p=12$, so the VPN has 20 bits: $2^{20}$ PTEs $\times$ 4 bytes = 4 MB, for every process, even one that uses a few pages.

2. Use two levels instead: the VPN splits into 10 + 10 bits. What does each level hold?

   The level-1 table has $2^{10}$ entries (4 KB); each points to a level-2 table, also 4 KB, that maps $2^{10}$ pages $= 4$ MB of virtual memory. Level-2 tables exist only for regions in use.

3. A process uses 8 MB at the bottom of its address space and 1 MB of stack at the top. How much page-table memory does it need now?

   Two level-2 tables for the 8 MB, one for the stack, plus the level-1 table: $4\times4$ KB = 16 KB instead of 4 MB.

4. Split the virtual address 0x00403A1C into VPN1, VPN2 and VPO.

   VPO is the low 12 bits: 0xA1C. The VPN is 0x00403A1C >> 12 = 0x403; VPN1 $=$0x403 >> 10$= 1$ and VPN2 $=$0x403 & 0x3FF$= 3$. So: entry 1 of the level-1 table, entry 3 of that level-2 table, byte 0xA1C of the page.

Check your understanding

Practice

The idea

Explore

Worked example

1. What size is p's block, and what is its header?

   $10+8=18$, rounded up to 24. Header $24\,|\,1=$0x19. Splitting leaves a free block of 40 bytes, header 0x28.

2. What happens for q = malloc(20)?

   It needs $20+8=28\to32$ bytes. The leftover would be $40-32=8$ bytes, too small for a block, so q gets the whole 40-byte block: header 0x29.

3. How much internal fragmentation does q's block have?

   The program asked for 20 bytes in a 40-byte block: 20 bytes are overhead (8 for header and footer, 12 unused).

4. free(p): does it coalesce?

   No. Its only neighbour, q, is allocated. The header becomes 0x18.

5. free(q): what is the heap now?

   Its previous neighbour is free: the footer just before q's header says "24, free". The two merge into one free 64-byte block, header 0x40. Check it in the explorer starting from an empty heap: the steps look the same, only in a larger heap.

Check your understanding

Practice

The idea

Explore

Worked example

1. Which process should open in.txt: the shell or a child?

   A child. The shell calls fork, and the child changes its own standard input. The shell's descriptor 0 must stay connected to the terminal.

2. The child calls fd = open("in.txt", O_RDONLY). Which descriptor does it get?

   The smallest unused one: 3, since 0, 1 and 2 are open.

3. How does it make descriptor 0 refer to the file?

   dup2(fd, 0) closes the child's old descriptor 0 (the terminal's open file entry loses one reference; the shell still holds it) and points 0 at in.txt's entry. Then close(fd), since descriptor 3 is no longer needed.

4. The child calls execve("/usr/bin/sort", ...). Why does sort read from the file?

   execve replaces the code and data but keeps the descriptor table. sort reads descriptor 0 like always and has no idea it is a file.

Check your understanding

Practice

The idea

int listenfd = open_listenfd(port);   /* socket + bind + listen */
while (1) {
    int connfd = accept(listenfd, NULL, NULL);   /* waits for a client */
    handle(connfd);                   /* read request, write reply */
    close(connfd);
}

Worked example

1. Write the server's address as a 32-bit hex number.

   One byte per field: $198=$C6, $51=$33, $100=$64, $7=$07. The address is 0xC6336407.

2. In network byte order, in what order do those bytes sit in memory? What value would the x86 client see if it read them as a uint32_t without ntohl?

   Big-endian, so most significant first: C6 33 64 07. Read little-endian, those bytes are 0x076433C6. ntohl swaps them back.

3. The port: what bytes does htons(80) put in memory, and what port would a server listen on if you stored plain 80 on x86?

   $80=$0x0050. htons(80) gives the bytes 00 50. Stored without conversion on x86, the bytes are 50 00, which the network reads as 0x5000 = port 20480.

4. The client's kernel picks port 50123. What is the socket pair? Could a second tab in the same browser use the same pair?

   (192.0.2.10:50123, 198.51.100.7:80). No: a second connection gets a different ephemeral port, and the differing pair is how both kernels tell the two connections apart.

5. On the server, which calls block, and which descriptors exist after accept returns?

   accept blocks until a connection arrives (and read blocks until data does). Afterwards there are two: listenfd, still open for the next client, and connfd, connected to this client only.

6. The client sends the request below in one write. How does the server know the headers have ended?

   GET /index.html HTTP/1.1\r\n
   Host: www.example.com\r\n
   \r\n

   By the empty line: \r\n right after a \r\n. Since a read may return only part of the request, the server keeps reading, line by line, until it sees that empty line. That is the short-count lesson from the previous module.

Check your understanding

Practice

The idea

volatile long cnt = 0;              /* shared */
void *worker(void *arg) {
    for (long i = 0; i < NITERS; i++)
        cnt++;    /* load cnt into %rdx; add 1; store %rdx to cnt */
    return NULL;
}

Explore

Worked example

void transfer(struct account *from, struct account *to, long amt) {
    P(&from->lock);
    P(&to->lock);
    from->balance -= amt;
    to->balance   += amt;
    V(&to->lock);
    V(&from->lock);
}

1. Find a schedule that never finishes.

   Thread 1 does P(&A.lock), then thread 2 does P(&B.lock). Now thread 1 waits for B's lock, which thread 2 holds, and thread 2 waits for A's lock, which thread 1 holds. Neither can proceed: deadlock.

2. In a progress graph, where is the trouble?

   There are two forbidden regions, one per lock, and they overlap in a way that leaves a pocket below and to the left of their overlap. A path that enters the pocket can only move right into one forbidden region or up into the other: it is stuck. That pocket is the deadlock region.

3. Fix transfer without a global lock.

   Lock in a fixed order, for example by account number: lock min(from, to) first, then max(from, to); unlock in either order. Both threads now try A first, so whichever gets A will also get B.

4. Does the fix still work with many threads and many accounts?

   Yes. If everyone acquires locks in increasing order, a cycle of waiting threads is impossible: the thread holding the highest-numbered lock in such a cycle could only be waiting for an even higher lock, which no one in the cycle holds.

Check your understanding

Practice