Return to course pageReturn to index


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)


  • 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.

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?

Question 4 (see above)

Which of the following is concurrent but not 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?

Question 6 (see above)

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

Question 7 (see above)

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

The following discuss caches

Question 8 (see above)

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

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.

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

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

Question 13 (see above)

Large cache blocks improve cache performance when the code exhibits

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,

Question 15 (see above)

How is process memory reclaimed?

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

Question 16 (see above)

Inverting a private-key encryption requires

Question 17 (see above)

Inverting a symmetric-key encryption requires

Question 18 (see above)

Inverting a cryptographically secure hash requires

Question 19 (see above)

Inverting a public-key encryption requires

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

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

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


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?

Question 24 (see above)

When running in user mode,

Question 25 (see above)

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

Question 26 (2 points)

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

Return to course pageReturn to index