After working through multiple incorrect solutions to the single-buffer-slot producer/consumer problem, we have finally settled on the following code with some key new insights including: using condition variables to signal when the buffer is filled and when it has been emptied, and using a while loop instead of an if statement when checking if there is something in the buffer (i.e., the value of count).

int loops;
cond_t cond;
mutex_t mutex;
void *producer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex);
    while (count == 1)
      Pthread_cond_wait(&cond, &mutex);
    put(i);
    Pthread_cond_signal(&cond);
    Pthread_mutex_unlock(&mutex);
  }
}
void *consumer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex);
    while (count < 2)
      Pthread_cond_wait(&cond, &mutex);
    int tmp = get();
    Pthread_cond_signal(&cond);
    Pthread_mutex_unlock(&mutex);
    printf("%d\n", tmp);
  }
}

Which of the following is true about our code?

Recall that demand paging is when we bring a page into memory when it is accessed, and prefetching brings extra pages into memory according to some policy. An example of a prefetching policy is when we need page P, we also bring in pages P+1 and P+2 into memory since they are likely to be accessed as well.

When traversing a large linked list, which prefetching policy is most likely to improve performance by reducing page faults?

Suppose we want to implement a concurrent hash table that uses open addressing to resolve collisions. Recall the following:

• Open addressing checks the array index at the hash function and if it is not available, moves ahead according to some rule until it finds an empty spot in the array.

• Recall also that two commonly used rules for finding the empty array slot are:

  1. Linear probing: First check the hashed index i and if it is occupied, then move to index i+1 modulo the size of the array and so on recursively until an open spot is found.
  2. Quadratic probing: First check the hashed index i and if it is occupied, then move to index i^2 modulo the size of the array and so on recursively until an open spot is found.

• Linear probing makes it easy to implement a search, but increases clustering, whereas quadratic probing increases the difficulty of implementing a search, but reduces clustering.

With all of this in mind, which of the following approaches to implementing the concurrent hash table do you expect will perform best in terms of turnaround time?

What does the absolute value of a negative semaphore represent?

Consider the following lock and unlock functions from class that puts threads to sleep instead of spin-waiting. Identify the bug(s) in the code. Assume TestAndSet runs atomically.

void lock(lock_t *m) {
   while (TestAndSet(&m->guard, 1) == 1)
      ; // acquire guard lock by spinning
   if (m->flag == 0){
      m->flag = 1; // lock is acquired 
      m->guard = 0; 
   } else {
      queue_add(m->q, gettid()); 
      m->guard = 0; 
      park(); 
    } 
} 
void unlock(lock_t *m) { 
   while (TestAndSet(&m->guard, 1) == 1) 
      ; // acquire guard lock by spinning 
   if (queue_empty(m->q)) 
      m->flag = 0; // let go of lock; no one wants it 
   else 
      unpark(queue_remove(m->q)); // hold lock (for next thread!)
   m->guard = 0; 
}

lock_t mutex;
.
.
.
lock(&mutex);
while(1){
myFunc();
}
unlock(&mutex);

Suppose three (3) threads each increment a shared variable 5 times that is initialized to 0 (so, the expected result then is 15). After all threads have finished, the main prints the value of the shared variable. Without locks (or any other way of enforcing mutual exclusion), which of the following will/could be printed by the main?

What will be printed by the following code snippet that creates two (2) threads to execute the function mythread and joins them to ensure they both finish?

void *mythread(void *arg) {
   int result = 0;
   result = result + 100;
   printf("result %d\n", result);
}
thread_t p1, p2;
thread_create(&p1, mythread, NULL);
thread_create(&p2, mythread, NULL);
thread_join(p1);
thread_join(p2);