Study Guide 5

Code Jams are open book. 40 minutes in lab.

Topics:

Everything from Study Guide 4, plus

  • The operating system, interrupts, traps, processes, virtual memory, zombies

  • fork(), wait(), pid, ps

  • Interprocess communication: signals, shared memory, pipes, sockets

  • POSIX threads

  • mutex, barrier

  • deadlock, thread safety

We skipped signals this semester (Spring 2023). You do not need to study this topic

Practice questions

OS, Processes

1) Short answer

  • What is the operating system?

  • What is the BIOS or UEFI for?

  • What is virtual address space (VAS)? Why is it useful?

  • What is a process?

  • What is the difference between an interrupt and a trap?

  • Why do we need interrupts and traps?

  • Why do we need special mechanisms, such as pipes or sockets, to communicate between processes?

  • How can you kill a process using ps ?

  • What states can a process be in?

  • What is a zombie process?

  • What are the different states that a process can be in?

  • Why might we want to register a signal handler for the SIGKILL or SIGSEGV signal?

  • When does the OS send the SIGSEGV signal?

  • What are the differences between shared memory, signals and pipes?

2) The following program creates a zombie process. Why?

void main() {
  if (fork() == 0) { /*child */
    printf("Child, PID = %d\n", getpid());
    exit(0);
  } else { /*parent */
    printf("Parent, PID = %d\n", getpid());
    while(1) {
    }
  }
}

3) Draw the process hierarchy created by executing the following program. For each process in the hierarchy, list its output (e.g. what does each process print)?

int main() {
  pid_t ret;

  printf("A\n");

  ret = fork();
  if(ret == 0) {
    printf("B\n");

    ret = fork();
    if(ret == 0) {
      printf("C\n");
    }
    printf("D\n");
  } else {
    printf("E\n");

    ret = fork();
    printf("F\n");
  }

  printf("G\n");
  return 0;
}

4) What type of event does SIGINT represent? Write a program that registers a signal handler for SIGINT?

Threads

Short answer

  • 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 (2 threads) that computes the average of a list of numbers. You can assume that the size of the list can be evenly divided by 2. Sketch a stack diagram for this program using a list of 4 numbers.

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