Quiz Viewer

Midterm

You may use any resource that existed prior to this exam opening, including websites, books, etc; but should not consult friends, tutors, forums, or other interactive help for this exam.

You must not share any information about this exam (even how you felt about it) with any party (even others who have taken it) until after it closes at 2020-04-06 23:59 EDT.

The following are all of the form "inverting ____ requires". To invert function f we mean, given f(m), compute m. Assume that

You do not have access to the original message (not even as private information)
You do not have the time to use brute-force approaches.

Question 1 (1 pt; mean 0.97) (see above)

Inverting a cryptographically secure hash requires

1%
private information, like a private key
public information, like a public key
1%
unrecorded information, like when I moved my mouse
97%
⊤
none of the above are sufficient

Question 2 (1 pt; mean 0.87) (see above)

Inverting a public-key encryption requires

82%
⊤
private information, like a private key
11%
½
public information, like a public key
unrecorded information, like when I moved my mouse
7%
none of the above are sufficient

Question 3 (1 pt; mean 0.76) (see above)

Inverting a private-key encryption requires

31%
½
private information, like a private key
61%
⊤
public information, like a public key
1%
unrecorded information, like when I moved my mouse
7%
none of the above are sufficient

Question 4 (1 pt; mean 0.88) (see above)

Inverting a symmetric-key encryption requires

86%
⊤
private information, like a private key
4%
public information, like a public key
unrecorded information, like when I moved my mouse
10%
none of the above are sufficient

Untrusted agent U sends me a message M and a message signature S created by agent A using public key K.

Question 5 (dropped) (see above)

Which of the following should I definitely not get from U?

This question has been dropped because of an ambiguity in its wording. The intent was to suggest that if U is my witness that K belongs to A, then U can simply give me U's public key instead of A's public key. Unfortunately, I failed to mention that K was not part of a certificate, and since certificates are commonly used to allow U to give me K in practice the question became too vague to measure learning.

Question 6 (1 pt; mean 0.55) (see above)

Assume

H(message) is the hash function
P(message, key) is the public/private encryption function
Y(message, key) is the symmetric encryption function

Give C-syntax Boolean expression, like M == Y(H(M),K), which is true if and only if the message was signed by A.

Answer:

Key: H(M) == P(S,K)

The following discuss caches

Question 7 (1 pt; mean 0.94) (see above)

Large cache blocks improve cache performance when the code exhibits

94%
⊤
high spatial locality
1%
high temporal locality
4%
low spatial locality
low temporal locality

Question 8 (1 pt; mean 0.82) (see above)

Set-associative caches are used instead of fully-associative caches because set-associative caches

1%
are conceptually simpler and easier to verify
11%
are less expensive to manufacture
6%
are more versatile, working well on all kinds of locality
82%
⊤
can perform cache lookups in less time
have lower miss-rates for real code

Question 9 (1 pt; mean 1) (see above)

Set-associative caches are used instead of direct-mapped caches because set-associative caches

are conceptually simpler and easier to verify
are less expensive to manufacture
24%
⊤
are more versatile, working well on all kinds of locality
can perform cache lookups in less time
76%
⊤
have lower miss-rates for real code

Question 10 (1 pt; mean 0.94) (see above)

Which code has better locality? Assume i and j are stored in registers and a is a 10,000-element array.

94%

⊤

for(i=0; i<100; i+=1)
    for(j=0; j<100; j+=1)
        a[i*100+j] = i*j;

for(j=0; j<100; j+=1)
    for(i=0; i<100; i+=1)
        a[i*100+j] = i*j;

Question 11 (1 pt; mean 0.28) (see above)

Because 1009 is prime, the following will set all 1009 elements of a to 0 as long as x is not a multiple of 1009:

for(int i=0; i<1009; i+=1)
    a[(i*x)%1009] = 0;

Consider x values 2, 31, and 505. Order these values from slowest to fastest assuming we have a

4-way set-associative cache with 32 sets
4 entries of a can fit in a single cache block

Assume that the (i*x)%1009 takes the same number of cycles regardless of the values of i and x.

For 2, we access items 0, 2, 4, 6, 8, .... That gives us 1 cold miss, then 1 hit, then 1 cold miss, etc: 50% hit rate.

For 31, we access items 0, 31, 62, 93, ...., 992, 43, 74, 85, ... That means every read is a miss, and even once we wrap around we'd on new blocks: 0% hit rate.

For 505, we access items 0, 505, 1, 506, 2, 507, .... Two misses, then size hits; 2 misses then 6 hits, etc: 75% hit rate.

Question 12 (1 pt; mean 0.42) (see above)

In your TLB code, you had no block offset because there was just one entry per block. We had just one entry per block because

38%
not having a block offset makes the TLB lookup times faster
11%
½
not having a block offset makes the TLB misses rarer
37%
⊤
TLB accesses do not show spatial locality
1%
TLB accesses do not show temporal locality
11%
we simplified the problem; real TLBs do have multi-entry blocks and block offsets

If you have 52-bit addresses cached in a 16MB 8-way set-associative L2 cache with 64-byte blocks

Question 13 (1 pt; mean 0.86) (see above)

The set index is how many bits? Answer as a base-10 integer

Answer:

Key: 15

Question 14 (1 pt; mean 0.93) (see above)

The block offset is how many bits? Answer as a base-10 integer

Answer:

Key: 6

Question 15 (1 pt; mean 0.91) (see above)

The tag is how many bits? Answer as a C expression that evaluates to the correct number. You may use

constants like 52
the following variables
- bob (the number of block offset bits)
- sib (the number of set index bits)
the following function
- log2(n) the log-base-2 of n
the operators +, -, *, /, and <<

Answer:

Key: 52 - bob - sib

The following ask about threading

Question 16 (1 pt; mean 0.94) (see above)

When running in user mode,

3%
Every process belongs to a thread
94%
⊤
Every thread belongs to a process
Some, but not all, processes belong to a thread
3%
Some, but not all, threads belong to a process

Question 17 (1 pt; mean 0.66) (see above)

We often say that "each thread has its own stack memory"; we mean that each

7%
has its own page table, meaning each uses different physical addresses for the stack
66%
⊤
has its own %rsp hardware, meaning each uses different virtual addresses for the stack
6%
use the same stack addresses, but one thread finishes using it before the next begins using it
21%
use the same stack addresses, but when switching threads the contents are changed to match the scheduled thread

Question 18 (2 pt; mean 1.52) (see above)

In a multi-threaded environment, which of the following pairs of instructions always runs atomically; that is, that the result of running them is the same as if no other instructions were run in between them?

85%
⊤
```
mov %rax, %rbx;
mov %rbx, %rcx;
```
82%
⊤
```
mov (%rax), %rbx
mov %rbx, %rcx
```
17%
```
mov %rax, (%rbx)
mov (%rbx), %rcx
```
55%
⊤
```
mov %rax, %rbx
mov %rbx, (%rcx)
```
55%
```
mov (%rax), %rbx
mov %rbx, (%rcx)
```

I eat a meal consisting of a bowl of soup and a bowl of ice cream, using the same spoon for both.

Question 19 (1 pt; mean 0.79) (see above)

Which of the following is concurrent but not parallel?

3%
My digestion of the two if I eat all the soup, then all the ice cream.
4%
My digestion of the two if I eat some soup, then some ice cream, then some more soup, then some more ice cream, etc.
10%
The emptying of the bowls if I eat all the soup, then all the ice cream.
79%
⊤
The emptying of the bowls if I eat some soup, then some ice cream, then some more soup, then some more ice cream, etc.
4%
none of the above are concurrent without being parallel

Question 20 (1 pt; mean 0.85) (see above)

Which of the following is parallel but not concurrent?

3%
My digestion of the two if I eat all the soup, then all the ice cream.
10%
My digestion of the two if I eat some soup, then some ice cream, then some more soup, then some more ice cream, etc.
1%
The emptying of the bowls if I eat all the soup, then all the ice cream.
1%
The emptying of the bowls if I eat some soup, then some ice cream, then some more soup, then some more ice cream, etc.
85%
⊤
none of the above are parallel without being concurrent

A memory leak in a process is limited to that process: when the process terminates, all its allocated memory will be reclaimed (that is, deallocated and made available to other processes).

Question 21 (1 pt; mean 0.44) (see above)

How is process memory reclaimed?

44%
The loader which launched the process follows frees its memory after it terminates

The loader puts the process into memory. It does not do anything after that.
13%
The malloc library keeps track of allocated memory and frees it before the process terminates

If this was what happened, that crashing would cause a system-wide memory leak.
44%
⊤
The process's page table is deleted when the process terminates

Question 22 (1 pt; mean 0.48) (see above)

If a thread has a memory leak,

25%
its leaked memory is reclaimed when the thread exits, using the same mechanism as a process
27%
its leaked memory is reclaimed when the thread exits, but using a different mechanism than a process
48%
⊤
its leaked memory is not reclaimed

The following ask about several synchronization primitives

Question 23 (1 pt; mean 0.65) (see above)

Which of the following is commonly used to create a simple blocking mutex?

13%
atomic compare-and-set
6%
barrier
48%
⊤
monitor
34%
½
reader-writer lock

Question 24 (1 pt; mean 0.85) (see above)

Which of the following does not block: that is, it never suspends a thread?

85%
⊤
atomic compare-and-set
8%
barrier
monitor
7%
reader-writer lock

Question 25 (1 pt; mean 0.92) (see above)

The x86 instruction lock cmpxchg is a hardware implementation of which of the following?

92%
⊤
atomic compare-and-set
barrier
4%
monitor
4%
reader-writer lock

Question 26 (2 pt; mean 1.07)

Which of the following ensure that my code has no deadlocks?

31%
Each resource is used by at most one thread at a time
49%
⊤
Each thread uses at most one resource at a time
69%
I used a message-passing API instead of directly using synchronization primitives

I realize my writeup is vague, although I think lecture was clearer: message passing reduces the chance of, not prohibits possibility of, deadlock. This option was given half weight compared to the others to compensate for this partial ambiguity.
54%
⊤
I've numbered the resources from 1 to n; all threads always request lower-numbered resources before higher-numbered resources

Return to course page

Return to index