Study Guide 5

Code Jams are open book. 40 minutes in lab.

Topics:

Everything from Study Guide 4, plus

Compiling and linking
Memory hierarchy, primary and secondary storage, caches, temporal and spatial locality
Advanced pointers, pointer arithmetic, void*, function pointers, pass by pointer
Implementations of malloc and free. sbrk()
The operating system, interrupts, traps, processes, virtual memory, zombies
fork(), wait(), pid, ps
Interprocess communication: signals, sockets, pipes, shared memory
Threads

You will not be asked to write a program that uses sockets, pipes, or shared memory but you should understand what they are and how/when they are used.

Practice questions

Compiling and linking

1) Short answers

What is the difference between compiling and linking?
What is a library? When would you use one?
What are differences between an application and a library?
What is the difference between static and dynamic libraries? Why might you want to use one over the other?
What does the pre-processor do?
What is the purpose of compiling and linking?

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

/usr/bin/ld: /tmp/ccH1QHw0.o: in function `main':
thread-argv.c:(.text+0x1c4): undefined reference to `pthread_attr_setstacksize'
/usr/bin/ld: thread-argv.c:(.text+0x2e4): undefined reference to `pthread_create'
/usr/bin/ld: thread-argv.c:(.text+0x38d): undefined reference to `pthread_join'
collect2: error: ld returned 1 exit status

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

4) Tymothy would like to create a library for creating color pallettes. The functions in their library would have the following APIs.

struct ppm_pixel {
  union {
    struct {
      unsigned char red;
      unsigned char green;
      unsigned char blue;
    };
    unsigned char colors[3];
  };
};

// Creates and initializes a pallet with the given number of random colors
struct ppm_pixel* create_pallette(int size);

// Frees the memory associated with the given pallette
void delete_pallette(struct ppm_pixel* pallette);

How can Tymothy use ar to create a static library?
How can Tymothy use gcc to create a shared library?
How might Tymothy implement the given functions?
Are the commands for building a library different
What is the difference between a header file (.h) and an implementation file (*.c)?
How can Tymothy use the functions in their library? Write a program that tests the pallet function.

Advanced pointers

1) Draw a stack diagram for the following program. Show all intermediate values.

#include <stdio.h>

int main() {
  int vals[4] = {1,2,3,4};

  printf("-------\n");
  for (int* ptr = vals; ptr < vals+4; ptr++) {
    printf("%p %d\n", ptr, *ptr);
  }

  return 0;
}

2) Fix the error in the following program. Then draw the function stack and heap for the working program.

#include <stdio.h>

int main() {
  void *gen_ptr;
  int x = 3;
  char ch = 'a';

  gen_ptr = &x;  // gen_ptr can be assigned the address of an int
  gen_ptr = &ch; // or the address of a char (or the address of any type)

  int* int_ptr;
  int_ptr = &x;

  printf("The int value is %d\n", *int_ptr);
  printf("The char value is %c\n", *gen_ptr);
  return 0;
}

3) Fix the error in the following program. Then draw the function stack and heap for the working program.

#include <stdio.h>

int main() {
  int* value = NULL;
  printf("value is %d\n", *value);

  int a = 4;
  value = &a;
  printf("value is %d\n", *value);
}

Memory

1) Short answers

What is the memory hierarchy?
Why do computers have a memory hierachy?
What is a cache hit? A cache miss?
What are some examples of primary storage?
What are some examples of secondary storage?
What is locality and what impact does it have on performance?
What is sbrk()? Why do we use functions such as malloc and free, rather than call sbrk() directly from our programs?
What is memory fragmentation and how can it occur?

2) In the following code, which variables have temporal locality? spatial locality?

#include <stdio.h>

int main() {
    int i, size = 0;

    // declare array of 10 ints
    int my_arr[10];

    // set the value of each array element
    for (i = 0; i < 10; i++) {
        my_arr[i] = i;
        size++;
    }

    // set value at position 3 to 100
    my_arr[3] = 100;

    // print the number of array elements
    printf("array of %d items:\n", size);

    // print each element of the array
    for (i = 0; i < 10; i++) {
        printf("%d\n", my_arr[i]);
    }

    return 0;
}

3) Is the following program guaranteed to have good spatial locality? Why or why not?

#include <stdio.h>
#include <stdlib.h>

void init_matrix(int** m, int rows, int cols) {
  int i, j;
  for (i = 0; i < rows; i++) {  // for each row i
    for (j = 0; j < cols; j++) { // iterate over each column in row i
        m[i][j] = 0;
    }
  }
}

int main() {
  int nrows = 50;
  int ncols = 100;

  int** matrix = malloc(sizeof(int*) * nrows);
  for (int i = 0; i < nrows; i++) {
    matrix[i] = malloc(sizeof(int) * ncols);
  }

  init_matrix(matrix, nrows, ncols);

  for (int i = 0; i < nrows; i++) {
    free(matrix[i]);
  }
  free(matrix);
  matrix = NULL;
  return 0;
}

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?
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 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;
}