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