Study Guide 6

Code Jams are open book. 40 minutes in lab.

Topics:

Everything from Study Guide 5, plus

  • POSIX threads

  • mutex, barrier

  • deadlock, thread safety

Practice questions

Short answers

  • What is a thread?

  • What is a mutex? When do we need to use mutex?

  • What is a race condition?

  • What is deadlock?

  • What does it mean for a function to be thread safe?

  • Why and when might we want to use multiple threads?

  • When might we want to use multiple processes versus multiple threads?

1) Write a multi-threaded program (4 threads) that computes the average of a list of numbers. You can assume that the size of the list can be evenly divided by 4.

2) The following multi-threaded program simulates two bank accounts. But it’s not working correctly. What is going on and how can we fix it?

struct account {
  pthread_mutex_t lock;
  int balance;
};

void *Transfer(void *args){
  struct account** accounts = (struct account**) args;
  struct account* fromAcct = accounts[FROM];
  struct account* toAcct = accounts[TO];

  for (int i = 0; i < 10000; i++) {
    pthread_mutex_lock(&fromAcct->lock);
    pthread_mutex_lock(&toAcct->lock);

    fromAcct->balance -= 25;
    toAcct->balance += 25;

    pthread_mutex_unlock(&fromAcct->lock);
    pthread_mutex_unlock(&toAcct->lock);
  }

  return NULL;
}

int main() {

  // create accounts for A and B
  struct account accountA;
  struct account accountB;
  accountA.balance = 100;
  accountB.balance = 50;
  pthread_mutex_init(&accountA.lock, NULL);
  pthread_mutex_init(&accountB.lock, NULL);
  printf("Starting balances:\n");
  printf("\tA: %d\n", accountA.balance);
  printf("\tB: %d\n", accountB.balance);

  // create threads
  struct account* transformA2B[2];
  transformA2B[0] = &accountA;
  transformA2B[1] = &accountB;

  struct account* transformB2A[2];
  transformB2A[0] = &accountB;
  transformB2A[1] = &accountA;

  pthread_t A2B, B2A;
  pthread_create(&A2B, NULL, Transfer, &transformA2B);
  pthread_create(&B2A, NULL, Transfer, &transformB2A);

  // wait for threads to finish
  pthread_join(A2B, NULL);
  pthread_join(B2A, NULL);

  printf("Ending balances:\n");
  printf("\tA: %d\n", accountA.balance);
  printf("\tB: %d\n", accountB.balance);

  // cleanup
  pthread_mutex_destroy(&accountA.lock);
  pthread_mutex_destroy(&accountB.lock);

  return 0;
}

3) The following multi-threaded program attempts to count the numbers in a list that are greater than 1000 but isn’t working correctly. What is going on and how can we fix it?

#define SIZE 100000

static unsigned long long count = 0;
struct thread_data {
  int start_index;
  int end_index;
  int* array;
};

void *countOver1000(void *userdata) {
  struct thread_data *data = (struct thread_data *) userdata;

  for (int i = data->start_index; i < data->end_index; i++) {
    if (data->array[i] > 1000) {
      count++;
    }
  }
  return (void*) NULL;
}

int main(int argc, char *argv[]) {
  srand(time(0));

  int values[SIZE];
  unsigned long long test = 0;
  for (int i = 0; i < SIZE; i++) {
    values[i] = rand() % SIZE;
    if (values[i] > 1000) test++;
  }

  printf("Test with 4 threads\n");
  pthread_t threads[4];
  struct thread_data data[4];
  int subsize = SIZE/4; // assume multiple of 4
  for (int i = 0; i < 4; i++) {
    data[i].array = values;
    data[i].start_index = subsize*i;
    data[i].end_index = subsize*(i+1);
    pthread_create(&threads[i], NULL, countOver1000, (void*) &data[i]);
  }

  for (int i = 0; i < 4; i++) {
    pthread_join(threads[i], NULL);
  }

  printf("Answer with threads: %llu\n", count);
  printf("Correct answer: %llu\n", test);

  return 0;
}

4) Ann-marie has the following errors when she tries to build. What type of error is it (compile, link, runtime, or logical)? How can she fix it?

thread-argv.c: In function ‘main’:
thread-argv.c:71:7: warning: implicit declaration of function ‘pthread_attr_init’ [-Wimplicit-function-declaration]
   71 |   s = pthread_attr_init(&attr);
      |       ^~~~~~~~~~~~~~~~~
thread-argv.c:76:9: warning: implicit declaration of function ‘pthread_attr_setstacksize’ [-Wimplicit-function-declaration]
   76 |     s = pthread_attr_setstacksize(&attr, stack_size);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~
thread-argv.c:96:9: warning: implicit declaration of function ‘pthread_create’ [-Wimplicit-function-declaration]
   96 |     s = pthread_create(&tinfo[tnum].thread_id, &attr,
      |         ^~~~~~~~~~~~~~
thread-argv.c:105:7: warning: implicit declaration of function ‘pthread_attr_destroy’ [-Wimplicit-function-declaration]
  105 |   s = pthread_attr_destroy(&attr);
      |       ^~~~~~~~~~~~~~~~~~~~
thread-argv.c:112:9: warning: implicit declaration of function ‘pthread_join’ [-Wimplicit-function-declaration]
  112 |     s = pthread_join(tinfo[tnum].thread_id, &res);
      |         ^~~~~~~~~~~~