Study Guide 5

Quizzes are closed book. 30 minutes in lab.

Topics:

Everything from Study Guide 4, plus

The operating system, processes, signals, virtual memory
fork(), wait(), pid, ps
Basic POSIX threads

Practice questions

OS, Processes, Threads

1) Example short answer questions

What is the operating system?
What is the BIOS or UEFI for?
What is virtual address space (VAS)?
Why do we need a virtual address space (VAS)?
Why might a processed be in a blocked state?
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 is a zombie process?
What are the different states that a process can be in?
What is a signal handler?
Why might we want to register a signal handler?
When does the OS send the SIGSEGV signal?
When does the OS send the SIGINT signal?
When does the OS send the SIGCHD signal?
What happens when a process calls fork?
What is a thread?
What are the differences between threads and processes?
Why and when might we want to use multiple threads?
When might we want to use multiple processes versus multiple threads?
What is a function pointer?
What is a void* pointer?

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 timeline created by executing the following program. For each created process, 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) Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)? How many processes are created?

int main() {
  pid_t ret;

  printf("A\n");

  for (int i = 0; i < 3; i++)
  {
     ret = fork();
     if (ret == 0) // child
     {
        printf("B%d\n", i);
     }
  }

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

5) Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)? How many processes are created?

int main() {
  pid_t ret;

  printf("A\n");

  for (int i = 0; i < 3; i++)
  {
     ret = fork();
     if (ret == 0) // child
     {
        printf("B%d\n", i);
        exit(0);
     }
  }

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

6) Draw the process timeline created by executing the following program. For each created process, list its output (e.g. what does each process print)? How many processes are created?

int main() {
  pid_t ret;

  int value = 10;
  printf("A%d\n", value);

  ret = fork();
  if (ret == 0) // child
  {
     value--;
  }
  else
  {
     value++;
  }

  printf("Z%d\n", value);
  return 0;
}

Threads

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

2) Draw the stack diagram for the following program with two threads.

struct thread_data {
  float s;
  int start_index;
  int end_index;
  float* array;
};

void *scalar_multiply(void *userdata) {
  struct thread_data *data = (struct thread_data *) userdata;
  for (int i = data->start_index; i < data->end_index; i++) {
    data->array[i] = sqrt(i)* data->s;
  }
  return NULL;
}

int main(int argc, char **argv) {
  int i;
  int nthreads;
  pthread_t *thread_array;
  long *thread_ids;
  struct thread_data *tdata;
  float data[100000];

  if (argc !=2) {
    fprintf(stderr, "usage: %s <n>\n", argv[0]);
    fprintf(stderr, "where <n> is the number of threads\n");
    return 1;
  }
  nthreads = strtol(argv[1], NULL, 10);

  // Allocate space for thread structs and identifiers.
  thread_array = malloc(nthreads * sizeof(pthread_t));
  thread_ids = malloc(nthreads * sizeof(long));
  tdata = malloc(nthreads * sizeof(struct thread_data));

  struct timeval tstart, tend;
  gettimeofday(&tstart, NULL);
  // Assign each thread an ID and create all the threads.
  int subsize = (int) (100000 / nthreads);
  for (i = 0; i < nthreads; i++) {
    thread_ids[i] = i;
    tdata[i].s = 3.14;
    tdata[i].start_index = i*subsize;
    tdata[i].end_index = (i+1)*subsize;
    tdata[i].array = data;
    pthread_create(&thread_array[i], NULL, scalar_multiply, &tdata[i]);
  }

  /* Join all the threads. Main will pause in this loop until all threads
   * have returned from the thread function. */
  for (i = 0; i < nthreads; i++) {
    pthread_join(thread_array[i], NULL);
  }
  gettimeofday(&tend, NULL);

  float timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
  printf("scalar_multiply time is %g\n", timer);

  free(thread_array);
  free(thread_ids);
  free(tdata);

  return 0;
}

3) Draw the stack diagram for the following program with two threads.

struct foo {
   long id;
   char message[16];
};

void *HelloWorld(void *id) {
  struct foo *holder = (struct foo *) id;
  printf("%s world! I am thread %ld\n", holder->message, holder->id);
  return NULL;
}

int main(int argc, char **argv) {
  struct foo holder1, holder2;
  holder1.id = 1;
  strcpy(holder1.message, "caio");

  holder2.id = 2;
  strcpy(holder2.message, "aloha");

  long* retval1 = NULL, *retval2 = NULL;
  pthread_t thread1, thread2;
  pthread_create(&thread1, NULL, HelloWorld, &holder1);
  pthread_create(&thread2, NULL, HelloWorld, &holder2);
  pthread_join(thread1, NULL);
  pthread_join(thread2, NULL);
  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);
      |         ^~~~~~~~~~~~

5) What is the output of the following program? Draw the stack diagram.

#include <stdio.h>

typedef void (*functionType)(int a, int b);

void example(int a, int b) {
  printf("This is a function stored as data! %d %d\n", a, b);
}

int main() {
  functionType myFunction = example;
  (*myFunction)(10, 3);
}

6) Indicate which of the following dereferences are safe.

#include <stdio.h>

int main()
{
  void* generic = NULL;
  int a = 3;
  double b = 4.5;
  generic = &a;
  generic = &b;

  printf("test %f\n", *generic);

  double* double_ptr = (double *) generic;
  printf("test %f\n", *double_ptr);

  int* int_ptr = (int *) generic;
  printf("test %d\n", *int_ptr);

  generic = &a;

  double* double_ptr = (double *) generic;
  printf("test %f\n", *double_ptr);

  int* int_ptr = (int *) generic;
  printf("test %d\n", *int_ptr);

  return 0;
}