Which of the following is true about the below code for a reader-writer lock that allows multiple readers in a critical section, but never more than one writer and never a writer and readers at the same time.

typedef struct {
	sem_t rw_mutex;
	sem_t rcount_mutex;
	sem_t writer_waiting;
	int reader_count;
} rw_lock_t;
void rw_lock_init(rw_lock_t *lock) {
	sem_init(&lock->rw_mutex, 0, 1);
	sem_init(&lock->rcount_mutex, 0, 1);
	sem_init(&lock->writer_waiting, 0, 1);
	lock->reader_count = 0;
}
void reader_lock(rw_lock_t *lock) {
	sem_wait(&lock->writer_waiting);
	sem_wait(&lock->rcount_mutex);
	lock->reader_count++;
	if (lock->reader_count == 1) {
		sem_wait(&lock->rw_mutex);
	}
	sem_post(&lock->rcount_mutex);
	sem_post(&lock->writer_waiting);
}
void reader_unlock(rw_lock_t *lock) {
	sem_wait(&lock->rcount_mutex);
	lock->reader_count--;
	if (lock->reader_count == 0) {
		sem_post(&lock->rw_mutex);
	}
	sem_post(&lock->rcount_mutex);
}
void writer_lock(rw_lock_t *lock) {
    sem_wait(&lock->writer_waiting);
    sem_wait(&lock->rw_mutex);
}
void writer_unlock(rw_lock_t *lock) {
    sem_post(&lock->rw_mutex);
    sem_post(&lock->writer_waiting);
}

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);

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);

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?