Consider the following C snippet running on a system with 8-byte pointers and 8-byte longs:

long A[4] = {10, 20, 30, 40};
long B[4] = {50, 60, 70, 80};
long *C[2] = {&A[1], &B[2]};
long *D[2] = {&A[1], &B[2]};
B[2] = *C[1];
C[1] = &A[3];
*C[0] = B[0];

The arrays C and D contains addresses. Depending on where the arrays are stored in memory the values of the addresses in C and D will vary. For example, if A is located at address 0x1000 and B at 0x2000, then D[0] could contain 0x1008 and D[1] will contain 0x2010, but these values would be different if A and B were at different locations.

For some placement of the arrays in memory, which of the following are possible values for the array C at the end of the code snippet above? Select all that apply.

The kill command-line utility invokes the kill system call, which can be used, among other things, to make another process terminate. When a user runs kill to terminate another process using its process ID, at what point(s) does the processor switch into kernel (privileged) mode? Select all that apply.

Consider the following C function:

int count = 0; pid_t pid;
pid_t mystery() {
    for (int i = 0; i < 4; ++i) {
        count += 1;
        pid = fork();
        if (pid != 0) {
            return pid;
        }
    }
    return 0;
}

Which of the following is true about the above function? Select all that apply.

Which of these items are copied into the child process on a fork()? Assume copy-on-write is NOT implemented. Choose all that apply.

Now imagine the following pseudocode in some process that starts out with default stdout (pointing to the screen):

 fd1 = open(file1, ...)
 close(STDOUT_FILENO)
 fd2 = open(file2, ...)
 fd3 = dup2(fd2,STDOUT_FILENO)
 write(STDOUT_FILENO, ...)

Where will the write appear?

Consider the following code snippets:

program1:

int x = 0; pid_t childpid = -1, mypid; 

childpid = fork();
if (childpid > 0) {
  x=500;
  printf(“%d forked,”, childpid);
  waitpid(childpid, etc);
  printf(“%d done,”, childpid);
}
else if (childpid == 0) {
  mypid = getpid();
  x=100;
  printf(“%d exec’ing,”, mypid);
  char *args[] = {"program2", "0", NULL};
  exec(program2, args);
  printf(“%d post-exec,”, mypid);
}

program2:

int x; 

int main(int argc, char**argv) {
  x = strtoi(argv[1]);
  if (x == 0) {
    x++;
    char *args[] = {"program2", itoa(x), NULL};
    exec(program2, args);
  }
  printf(“x=%d,”, x);
  return 0;
}

Which, if any, of the following outputs sequences are valid, assuming the child pid is 23 and the fork and execs do not fail? Select all that apply.

The following process operates on a file that contains the following lines:

LINE1
LINE2
LINE3

Consider the following code snippet (the read consumes 6 characters because of the newline at the end of each line):

int retval;

pid_t childpid = fork();
if (childpid > 0) {
  char buf[1024];
  fd1 = open("file", O_RDWR);
  retval = read(fd1, buf, 6);
  write(STDOUT, buf, 6);
} else if (childpid == 0) {
  char buf[1024];
  fd1 = open("file", O_RDWR);
  fd2 = dup(fd1);
  retval = read(fd1, buf, 6);
  retval = read(fd2, buf+6, 6);
  write(STDOUT, buf, 12);
}

Assume the file exists and the fork and the reads and writes succeed.

Which of the following outputs, if any, are possible (newlines are omitted to make the options easier to read)? Choose all that apply.

Consider a system with

• single-level page tables
• 1024 (2 to the 10) byte pages (and therefore 10-bit page offsets).
• 4-byte page table entries, containing, starting with the least significant bits
  • a 1 valid bit
  • a writeable bit
  • an executable bit
  • a user-mode bit
  • a 6 unused bits
  • a 22-bit physical page number
• a page-table base register set to the physical address 0x12000

A program accesses virtual address 0x98765 which corresponds to physical address 0xa8765 and is writeable, not executable, and user-mode accessible. As part of this access, the processor accesses a pagetable entry at address ____. Write your answer as a hexadecimal number. If not enough information is given, write "unknown".

Suppose a process running on a system with 4096-byte pages has the following memory layout:

• 0x0--0x0ffff (virtual pages 0x0 through 0x0f): inaccessible
• 0x10000--0x1ffff (virtual pages 0x10 through 0x1f): code and constants, read-only + executable
• 0x20000--0x3ffff (virtual pages 0x20 through 0x3f): global variables, read/write + non-executable
• 0x40000--0x5ffff (virtual pages 0x40 through 0x5f): heap, read/write + non-executalbe
• 0x60000--0x9ffff (virtual pages 0x60 through 0x9f): inaccessible
• 0xa0000--0xa8fff (virtual apges 0xa0 through 0xa8): stack
• 0xa8fff--(maximum possible): inaccessible

Assume the system running the program uses copy-on-write in a way which copies as few pages as possible. Initially, the program is running with all pages mapped in its memory so it can access any of its memory without an exception occuring (including writing).

Then the following happens in this order:

• the program calls fork()
• the parent process runs first, and copies the byte at address at 0x14300 into its stack at address 0xa63000
• then the parent process copies the byte at address at 0x14301 into its stack at address 0xa63001
• then the child process expands its heap to include 0x60000-0x67fff, and writes to all of those bytes (sequentially, one at a time)

As a result of these events, how many additional pages of memory will be allocated to store the program's memory? (Do not include space for page tables, operating system bookkeeping, etc.)

If one doubles the size of pages and also doubles number of entries in each page table on a system with five-level page tables, this will add ___ bits to the size of virtual addresses supported.

If the address size supported will increase, write a positive number; if it will descrease, write a negative number; if it will stay the same write "0". If not enough information is provided, write "unknown" and explain in the comments.

Suppose we modify the dining philosophers to put all chopsticks in the center of the table where each of the philosophers takes the first of those chopsticks that is available.

We can represent that using the following psuedocode:

    Lock chopsticks[NUM_CHOPSTICKS];

    int GetChopstick() {
        for (int i = 0; i < NUM_CHOPSTICKS; i++) {
           if (trylock(chopsticks[i]))
               return i;
           /* in version as posted: 
           else
               return -1;
            */
        }
        /* not version as posted: */ return -1; 
    }

    void PutDown(x) {
       Unlock(chopsticks[x]);
    }

    void Eat() {
        left = right = -1;

        while (left == -1)
            left = GetChopstick();

        while (right == -1)
            right = GetChopstick();

       // use chopsticks and eat

       PutDown(left)
       PutDown(right)
    }

In the above psuedocode:

• the Lock type represents a lock, and all locks are appropriately initialized
• TryLock(x) attempts to acquire the lock without waiting. If successful, it returns 1. Otherwise, it returns 0 without waiting.
• Unlock(x) releases a lock.
• NUM_CHOPSTICKS represents the number of chopsticks available, which may vary.

For each of the following scenarios, is deadlock possible? Select all that apply.

Consider the following psuedocode:

mutex_t mutex;
cond_t cv;
int locked[NUM_ACCOUNT] = {0, 0, 0, ... 0};

// assume withdraw() and deposit() do what the function names say
/*line 1*/ void transfer(acct1, acct2, amt) { // transfer amt from acct1 to acct2
/*line 2*/   mutex_lock(&mutex)
/*line 3*/   while (locked[acct1]) cv_wait(&cv, &mutex);
/*line 4*/   locked[acct1]=1;
/*line 5*/   while (locked[acct2]) cv_wait(&cv, &mutex);
/*line 6*/   locked[acct2]=1;
/*line 7*/   withdraw(amt, acct1);
/*line 8*/   deposit(amt, acct2);
/*line 9*/   locked[acct1]=0;
/*line 10*/  locked[acct2]=0;
/*line 11*/  mutex_release(&mutex);
/*line 12*/  signal(&cv);
/*line 13*/}

What is wrong, if anything, with this code? (If nothing is wrong, select no options below.)

Consider the following potentially buggy code that is intended to allow multiple reader threads to be reading concurrently in a shared buffer and intended to ensure that a thread writing to the shared buffer must have exclusive access.

pthread_mutex_t lock;
pthread_cond_t proceed;
//initialization not shown

int reading = 0;
int writing = 0;

void reader(void) {
    pthread_mutex_lock(&lock);
    while (writing) pthread_cond_wait(&proceed, &lock);
    reading++;
    pthread_mutex_unlock(&lock);

   //reading code here

    pthread_mutex_lock(&lock);
    reading--;
    pthread_cond_signal(&proceed);
    pthread_mutex_unlock(&lock);
}

void writer(void) {
    pthread_mutex_lock(&lock);
    while (reading) pthread_cond_wait(&proceed, &lock);
    writing++;
    pthread_mutex_unlock(&lock);

   //writing code here

    pthread_mutex_lock(&lock);
    writing--;
    pthread_cond_signal(&proceed);
    pthread_mutex_unlock(&lock);
}

Assume that all appropriate header files are included and that code that accesses the shared buffer is included where //reading code here and //writing code here are.

Which of the following are bugs in this code or otherwise true about the code? Select all that apply.

Consider the following code:

int partial_mins[n];  //assume we initialize this to all MAX_INT in main()
int data[SIZE]; //filled with data for which we will find the min value
int chunk_size;
// SIZE and NUM_THREADS are defined elsewhere

void *find_min(void *raw_thread_num) {
  int thread_num = (int)raw_thread_num;
  int chunk_size = (SIZE / NUM_THREADS);
  for (int i = chunk_size * thread_num; i < chunk_size * (thread_num +1); i++) {
    if (data[i] < partial_mins[thread_num])
      partial_mins[i] = data[i]
  }
}

This function can be run by multiple instances of pthread_create to obtain a "partial minimum" of a subset of the shared array data. Later, other code can take the minimum of these minimums to find the overall minimum of the array. Which variables are likely to exhibit false sharing when the code is run? Select all that apply.

Suppose we use a scheme with acknowledgments and sequence numbers like described in lecture to send data from machine A to machine B over a network that follows the mailbox model.

In this scheme, machine A does not send a data message until after it receives an acknowledgment message for its previous data message, so that it can handle cases where the network fails to deliver its data network.

Suppose while a particular data transfer occurs, the network is reliable for sending messages from A to B, but very unreliable for sending messages from B to A. So, all the messages from A to B are received correctly and not delayed, but every third message (starting with the third one) from B to A is lost.

If the data transfer sends data from A to B that is split across 1000 data messages, how many messages, including lost acknowledgment messages, will be sent across the network in total?

Suppose we have a network of networks setup as follows:

• machine A is connected to network 1
• a router B is connected to network 1 and network 2
• a router C is connected to network 2 and network 3
• machine D is connected to network 3

Router B's routing table will have an entry that corresponds to the IP address for machine D which indicates to send packets addressed to machine D to ______.

Consider a communication scenario with participants A, B, C, an active "machine-in-the-middle" attacker M, and an eavesdropper E.

In advance, the following sets of symmetric keys are shared as follows:

• one set between all of A, B, and C
• one set between A and B
• one set between A and C
• one set between B and C

(Assume that symmetric key shared are only available to those who it is shared with.)

Suppose A sends a sequence of text lines to both B and C, by doing the following for each line of text:

• A increments a counter's value
• A generates a message containing that line of text, and the value of the counter, encrypts that message with a key shared between A, B, and C, and generates a message authentication code for that message using a key shared between A, B, and C,
• A generates a message containing the counter's value and generates two message authentication codes for that message:
  • one for the set between A and B
  • one for the set between A and C
• A sends each of the encrypted messages and message authentication codes to B and C.

Given this scheme, which of the following are likely possible?

Consider a TLS handshake like the one we described in lecture. Suppose a client contacts a server which has a different name than the name of the server it expected to connect to. Then the connection would most likely fail because ___.

Consider the following assembly code:

subq %r9, %r8
xorq %rdx, %r9
imulq %r9, (%r13)
addq %r8, %r13
movq (%r9), %r11
orq %r11, %r12

If we had a processor with the following pipeline stages (following the names used in lecture):

• fetch
• decode
• execute combined with memory
• writeback

Then which of the following things in the code example are data hazards when the code is run on the pipelined processor?

Suppose a 5-stage pipelined processor, similar to the design discussed in lecture, executes a program with 100 million instructions.

If there were no hazards, this program would execute in about 100 million cycles.

Suppose there are not data hazards in the program on the pipelined processor, but there are control hazards in the form of conditional jumps.

Assume that when a conditional jump is mispredicted, incorrect instructions are fetched during the decode and execute stages of the conditional jump and the correct next instruction is fetched during the jump's memory stage. (By "correct next instruction", we mean the target of the jump (the address specified by its operand) if it is taken, or the instruction that follows it in memory if it is not.) When a jump is predicted correctly, the correct next destination of the jump fetched during its decode stage (and no incorrect instructions are fetched).

If 5% of the instructions are conditional jumps, and the processor can predict them with 80% accuracy, then we'd expect the program to execute around __% slower than if we predicted the jumps perfectly.

Consider the following assembly snippet:

movq (%r8), %r9
addq %r9, %r10
subq %r10, %r11
imulq %r10, %r12
movq %r12, (%r9)

On an out-of-order processor with sufficiently many functional units, the instruction subq %r10, %r11 in the above assembly snippet could be potentially be issued in the same cycle as ___. Select all that apply.

Consider the following loop:

begin:
    movq (%r8), %r9
    addq $512, %r8
    cmp %r9, %r10
    jmp begin

On an out-of-order processor with sufficiently many functional units, movq (%r8), %r9 could potentially be executing (reading a value from the data cache) ____. Select all that apply.

Consider the following C snippet

int i = 0; 
do {
    i += 1;
    if (i % 2 == 0) {
        A();
    } else {
        B();
    }
} while (i != 100);

Assume the above code is compiled such that there is one conditional jump implementing the if statement and one condtiional jump implementing the do-while loop condition.

Suppose we use a branch predictor with a lookup table that identifies for each instruction whether it was taken the last time it ran.

Rounded to the nearest percent, we would expect a branch predictor accuracy of ___% if the above code is run repeatedly. Round your answer to the nearest integer number of precent.

Consider the following C code:

unsigned char array[10000];
...
array[200] += 10

If this is run on a system where: * array is located at address 0x100400 * chars are 1 byte * virtual memory is not enabled * there is a 131072 byte (2 to the 17th power byte) 2-way data cache with 128-byte blocks

Then the running the C code might evict a value from what set index in the data cache?

Consider the following C code:

struct Files all_files[NUM_FILES];
int GetLastByteOfFile(int index) {
    if (index >= 0 && index < all_files) {
        struct File *file = &all_files[index];
        if (file->type == MEMORY) {
            return file->data[file->size - 1];
        } else if (file->type == DISK) {
            return GetLastByteOfDiskFile(file)
        } else {
            return -1;
        }
    } else {
        return -1;
    }
}

If the above function runs in kernel mode, we might be able to use a Spectre-style attack where the cache evictions caused by memory access of file->data[file.size - 1] allows us learn about the value of an arbitrary memory location. To perform this attack, the attacker would prefer to choose an out-of-bounds index such that ___.