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.

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

Question 1 (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:

Question 2 (dropped) (see above)

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

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

Question 3 (see above)

Which of the following is parallel but not concurrent?

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

Question 4 (see above)

Which of the following is concurrent but not parallel?

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

The following ask about several synchronization primitives

Question 5 (see above)

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

monitor
barrier
atomic compare-and-set
reader-writer lock

Question 6 (see above)

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

barrier
monitor
reader-writer lock
atomic compare-and-set

Question 7 (see above)

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

atomic compare-and-set
reader-writer lock
monitor
barrier

The following discuss caches

Question 8 (see above)

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

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

Question 9 (see above)

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

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

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

Question 10 (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.

Question 11 (see above)

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

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

Question 12 (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

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

Question 13 (see above)

Large cache blocks improve cache performance when the code exhibits

low spatial locality
low temporal locality
high spatial locality
high temporal locality

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 14 (see above)

If a thread has a memory leak,

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

Question 15 (see above)

How is process memory reclaimed?

The process's page table is deleted when the process terminates
The loader which launched the process follows frees its memory after it terminates
The malloc library keeps track of allocated memory and frees it before the process terminates

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 16 (see above)

Inverting a private-key encryption requires

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

Question 17 (see above)

Inverting a symmetric-key encryption requires

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

Question 18 (see above)

Inverting a cryptographically secure hash requires

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

Question 19 (see above)

Inverting a public-key encryption requires

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

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

Question 20 (see above)

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

Answer:

Question 21 (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:

Question 22 (see above)

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

Answer:

The following ask about threading

Question 23 (2 points) (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?

```
mov (%rax), %rbx
mov %rbx, %rcx
```
```
mov %rax, (%rbx)
mov (%rbx), %rcx
```
```
mov %rax, %rbx
mov %rbx, (%rcx)
```
```
mov (%rax), %rbx
mov %rbx, (%rcx)
```
```
mov %rax, %rbx;
mov %rbx, %rcx;
```

Question 24 (see above)

When running in user mode,

Some, but not all, threads belong to a process
Some, but not all, processes belong to a thread
Every thread belongs to a process
Every process belongs to a thread

Question 25 (see above)

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

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

Question 26 (2 points)

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

Each resource is used by at most one thread at a time
Each thread uses at most one resource at a time
I've numbered the resources from 1 to n; all threads always request lower-numbered resources before higher-numbered resources
I used a message-passing API instead of directly using synchronization primitives

Return to course page

Return to index