Study Guide 5

Code Jams are open book. 40 minutes in lab.


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

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


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;

    // 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++) {
  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());
  } 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;


  ret = fork();
  if(ret == 0) {

    ret = fork();
    if(ret == 0) {
  } else {

    ret = fork();

  return 0;

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


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++) {

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


  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

  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) {
  return (void*) NULL;

int main(int argc, char *argv[]) {

  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;