Jan Kończak

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
Tentative weight for the question types:
  * 4<small>pts</small> for explain a code and/or point a bug in the code.
  * 3<small>pts</small> for write code or fill gaps in the code.
  * 2<small>pts</small> set correct initial value for semaphores.
  * 3<small>pts</small> for short, rather theoretical, questions.
The weights of the topics in the test will be scaled to the number of lab
classes for the topic, i.e., questions worth about half of the points will
deal with course materials from classes 7-9 covering threads, mutexes and
condition variables (that is three classes out of six total).
  
The questions provided below are example questions, not an exhaustive list of
possible questions, and the example questions do not cover all course material.

<html><div style="line-height:1em"></html>

--------------------------------

**~~#~~.**
Say that you need to pass a ''double'' and two ''int''s to a thread routine.
Explain how can you do this in pthreads.

**~~#~~.**
Explain what is the difference between joining a thread and detaching it.

**~~#~~.**
Explain why one has to use mutexes in concurrent programs. Provide a scenario
where omitting a mutex causes trouble.

**~~#~~.**
Tell what are the two differences between a binary semaphore and a recursive
mutex.

**~~#~~.**
Provide a scenario in which two threads deadlock so that no other thread can
wake them.

**~~#~~.**
The method ''pthread_cond_wait'' takes as an argument a condition variable and
a locked mutex. Explain why one must pass it a locked mutex.
You can provide a scenario that would cause trouble if ''pthread_cond_wait''
would not require the mutex.

**~~#~~.**
Waiting on condition variable is typically called in a ''while'' loop. Explain
why.

--------------------------------

**~~#~~.**
Explain how can you learn that a function from POSIX API failed.

**~~#~~.**
Provide two ways of telling why a function from POSIX API has failed.

**~~#~~.**
List and explain the possible return values of ''read'' function in the
following code:
<html><div style="margin-top:-1em"></html>
<code c>
int filedes = open("file", O_RDWR);
char letter;
int x = read(filedes, &letter, 1);
</code>

**~~#~~.**
Explain what happens when you write from several threads to the same file, and
explain how the result of the write depend on flags used upon opening the file.

**~~#~~.**
Explain the lines below do and what is difference between the two lines:
<html><div style="margin-top:-1em"></html>
<code c>
open( "first", O_RDWR|O_CREAT,        0644);
open("second", O_RDWR|O_CREAT|O_EXCL, 0644);
</code>

**~~#~~.**
Explain how can you add to a C program custom code to be executed when the
program gets interrupted by //Ctrl+C//.

**~~#~~.**
Write how can you tell whether you are in the parent or the child process when you
fork.

**~~#~~.**
Explain what happens to:
<html><div style="margin-top:-1em"></html>
  - open files
  - mutexes
  - threads
  - memory allocated by ''malloc''
  - memory mapped by ''mmap'' with ''MAP_SHARED'' flag
<html><div style="margin-top:-1em"></html>
upon a call to ''fork()'' function.

**~~#~~.**
Tell why ''"ls"'' appears twice in the following code:
<html><div style="margin-top:-1em"></html>
<code c>
execlp("ls", "ls", "-xls", 0);
</code>

**~~#~~.**
Name a function that you can use (prior to ''fork'') to create an
unidirectional channel for passing data to child processes.

**~~#~~.**
Explain how can you learn that a child process finished.

**~~#~~.**
What is the difference between opening a file twice and opening it once and then
duplicating the descriptor.

**~~#~~.**
What are the limitations of using MAP_ANONYMOUS flag in mmap when creating a
shared memory block.

**~~#~~.**
Write a line of code that creates a new named semaphore and sets its value to 1.


--------------------------------


**~~#~~.**
Write two snippets of code and a function. The first snipped of code must run
the function in a new thread and pass one ''double'' and one ''int'' to it.
The function must multiply the numbers and make a string (null-terminated char
array) out of the result. The second snippet must collect the result string.

**~~#~~.**
The code below looks up a number that, when appended to a provided text, will
produce a MD5 sum starting with a provided prefix.
Fill the gaps to make the code produce exactly 10 results instead of one.
<html><div style="margin-top:-1em"></html>
<code c>
#include <md5.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// To compile this code, add '-lmd' to compile options.

const char *text;
const char *prefix;
#define NO_THREADS 8

// writes MD5 sum of 'text' with 'nonce' appended to 'md5'
// returns if MD5 sum starts with 'prefix'
int try(long nonce, char md5[]) {
  char *data;
  int len = asprintf(&data, "%s %lx\n", text, nonce);
  MD5Data((uint8_t *)data, len, md5);
  free(data);
  return !strncmp(prefix, md5, strlen(prefix));
}

┌───────────────────────┐
│                       │
└───────────────────────┘

void *lookup(void *arg) {
  long i = (intptr_t)arg;
  char md5[MD5_DIGEST_STRING_LENGTH];
  while (1) {
    if (try(i, md5)) {
      ┌───────────────────────┐
      │                       │
      └───────────────────────┘
      printf("%s %lx\n%s\n", text, i, md5);
      ┌───────────────────────┐
      │exit(0);               │
      └───────────────────────┘
    }
    if ((((i += NO_THREADS) / NO_THREADS) % 4096) == 0) {
      ┌───────────────────────┐
      │                       │
      └───────────────────────┘
    }
  }
}

int main(int argc, char *argv[]) {
  prefix = argv[1];
  text = argv[2];
  pthread_t t[NO_THREADS];
  for (intptr_t i = 1; i < NO_THREADS; ++i) {
    pthread_create(t + i, NULL, lookup, (void *)i);
  }
  lookup((void *)0);
}
</code>

**~~#~~.**
The code below produces an incorrect result. Explain why, and propose how to
fix the issue.
<html><div style="margin-top:-1em"></html>
<code c>
  │ #include <pthread.h>
  │ #include <stdint.h>
  │ #include <stdio.h>
  │ 
 1│ void *thread(void *rawArg) {
 2│   uint64_t arg1 = ((uint64_t *)rawArg)[0];
 3│   uint64_t arg2 = ((uint64_t *)rawArg)[1];
 4│   return (void *)(arg1 * arg2);
  │ }
  │ 
  │ int main() {
  │   pthread_t threads[18];
 5│   for (int i = 1; i < 19; ++i) {
 6│     uint64_t args[] = {i, i + 1};
 7│     pthread_create(&threads[i - 1], NULL, thread, args);
  │   }
 8│   uint64_t sum = 0;
 9│   for (int i = 1; i < 19; ++i) {
10│     uint64_t result;
11│     pthread_join(threads[i - 1], (void **)&result);
12│     sum += result;
  │   }
13│   printf("∑ᵢ₌₁¹⁸ i·(i+1) = %ld\n", sum);
  │   return 0;
  │ }
</code>

**~~#~~.**
Describe what the lines marked with ''<--'' do.
\\
Then, describe in a single short sentence functionality of the following
program.
<html><div style="margin-top:-1em"></html>
<code c>
  │ #include <fcntl.h>
  │ #include <pthread.h>
  │ #include <stdio.h>
  │ #include <stdlib.h>
  │ #include <string.h>
  │ #include <unistd.h>
  │ 
  │ void *process(void *arg) {
 1│   int fd = open((char *)arg, O_RDONLY);
 2│   if (fd == -1) return NULL;
  │   unsigned char c;
 3│   unsigned *buf = malloc(256 * sizeof(unsigned));
 4│   memset(buf, 0, 256 * sizeof(unsigned));
 5│   while (read(fd, &c, 1) == 1);                         // <--
 6│     buf[c]++;                                           // <--
 7│   close(fd);
 8│   return buf;
  │ }
  │ 
  │ void outputAndFree(char *name, unsigned *buf) {
 9│   printf("%10s:", name);
10│   if (!buf) {
11│     puts(" failed");
12│     return;
  │   }
13│   for (unsigned char i = 'a'; i <= 'z'; ++i)
14│     printf(" %4u", buf[i]);
15│   putchar('\n');
16│   free(buf);
  │ }
  │ 
  │ int main(int argc, char *argv[]) {
17│   if (argc < 2) return 1;
18│   pthread_t *tid = malloc(argc * sizeof(pthread_t));
19│   for (int i = 2; i < argc; ++i)
20│     pthread_create(tid + i, NULL, process, argv[i]);    // <--
21│   unsigned *buf = process(argv[1]);
22│   outputAndFree(argv[1], buf);
23│   for (int i = 2; i < argc; ++i) {
24│     pthread_join(tid[i], (void **)&buf);                // <--
25│     outputAndFree(argv[i], buf);
  │   }
  │   return 0;
  │ }
</code>


--------------------------------


**~~#~~.**
Provide a shell command that produces the same output as the following
//program// when invoked as ''//program// //filename//'', where //filename// is a
path to a text file.
\\
Then, describe how the program operates to produce the output.
<html><div style="margin-top:-1em"></html>
<code c>
  │ #include <fcntl.h>
  │ #include <unistd.h>
  │ #define MIN(a, b) (a < b ? a : b)
  │ int main(int argc, char *argv[]) {
 1│   if (argc != 2) return 1;
  │   int fd, cnt, pos;
 2│   if (( fd = open(argv[1], O_RDONLY)) == -1) return 1;
 3│   if ((pos = lseek(fd, -1, SEEK_END)) == -1) return 0;
  │   char buf[1024];
 4│   while (pos > 0) {
 5│     int i, bs = MIN(pos, 1024);
 6│     lseek(fd, pos - bs, SEEK_SET);
 7│     if (read(fd, buf, bs) != bs)
 8│       return 1;
 9│     for (i = bs; i > 0 && buf[--i] != '\n'; /**/)
  │       ;
10│     pos -= bs - i;
11│     if (buf[i] == '\n') {
12│       pos++;
13│       break;
  │     }
  │   }
14│   lseek(fd, pos, SEEK_SET);
15│   while ((cnt = read(fd, buf, 1024)) > 0)
16│     write(1, buf, cnt);
17│   close(fd);
  │   return 0;
  │ }
</code>


**~~#~~.**
The code below might work by chance, but it contains a fragment that makes the
behaviour of the code undefined. Point out which line is it, and describe a
scenario when the problem can manifest.
<html><div style="margin-top:-1em"></html>
<code c>
  │ #include <pthread.h>
  │ #include <signal.h>
  │ #include <stdio.h>
  │ #include <stdlib.h>
  │ #include <unistd.h>
  │ 
 1│ pthread_mutex_t stdOutMtx = PTHREAD_MUTEX_INITIALIZER;
  │ 
 2│ void ctrlc(int _) {
 3│   pthread_mutex_lock(&stdOutMtx);
 4│   printf("Quitting!\n");
 5│   pthread_mutex_unlock(&stdOutMtx);
 6│   exit(0);
  │ }
  │ 
  │ int mainPipe[2];
  │ int trianglePipe[2];
  │ int squarePipe[2];
  │ 
  │ void *triangle(void *_) {
 7│   pthread_detach(pthread_self());
 8│   while (1) {
  │     int n;
 9│     read(trianglePipe[0], &n, 4);
10│     pthread_mutex_lock(&stdOutMtx);
11│     for (int i = 0; i < n; i++) {
12│       for (int j = i; j < n; j++) {
13│         usleep(10000);
14│         putchar('*'); fflush(stdout);
  │       }
15│       putchar('\n');
  │     }
16│     pthread_mutex_unlock(&stdOutMtx);
17│     write(mainPipe[1], &n, 1);
  │   }
  │ }
  │ 
  │ // square is identical to triangle with an exception in line marked by '<--'
  │ void *square(void *_) { 
  │   pthread_detach(pthread_self());
  │   while (1) {
  │     int n;
  │     read(squarePipe[0], &n, 4);
  │     pthread_mutex_lock(&stdOutMtx);
  │     for (int i = 0; i < n; i++) {
  │       for (int j = 0; j < n; j++) {      // <--
  │         usleep(10000);
  │         putchar('*'); fflush(stdout);
  │       }
  │       putchar('\n');
  │     }
  │     pthread_mutex_unlock(&stdOutMtx);
  │     write(mainPipe[1], &n, 1);
  │   }
  │ }
  │
  │ int main() {
  │   int32_t n;
  │   char t;
  │   pthread_t tid;
18│   signal(SIGINT, ctrlc);
19│   pipe(mainPipe); pipe(trianglePipe); pipe(squarePipe);
20│   pthread_create(&tid, NULL, triangle, NULL);
21│   pthread_create(&tid, NULL, square, NULL);
22│   while (1) {
23│     printf("Provide a dimension: ");  fflush(stdout);
24│     scanf("%d", &n);
25│     printf("Provide a type [t/s]: "); fflush(stdout);
26│     scanf("%*[\n]%c", &t);
27│     switch (t) {
  │       case 't':
28│         write(trianglePipe[1], &n, 4);
29│         read(mainPipe[0], &t, 1);
  │         break;
  │       case 's':
30│         write(squarePipe[1], &n, 4);
31│         read(mainPipe[0], &t, 1);
  │         break;
  │     }
  │   }
  │   return 0;
  │ }
</code>

**~~#~~.**
Describe what this code does, and think up and provide one use case for it. 
<html><div style="margin-top:-1em"></html>
<code c>
  │ #include <unistd.h>
  │ #include <stdlib.h>
  │ #include <semaphore.h>
  │ #include <sys/wait.h>
  │ #include <fcntl.h>
  │ int main(int argc, char *argv[]){
 1│     sem_t * sem = sem_open (argv[1], O_RDWR|O_CREAT, 0600, atoi(argv[2]));
 2│     sem_wait(sem);
 3│     if(!fork()){
 4│         execvp(argv[3], argv+3);
 5│         return -1;
  │     }
 6│     close(0); close(1); close(2);
 7│     int rv;
 8│     wait(&rv);
 9│     sem_post(sem);
10│     return rv;
  │ }
</code>

**~~#~~.**
The code below is a simple implementation of a linked-list based queue with
a blocking get. Fill the gap with code that initializes the semaphores.
<html><div style="margin-top:-1em"></html>
<code c>
#include <semaphore.h>
#include <stdlib.h>

typedef int value_type;
struct llqueue {
  struct element {
    value_type value;
    struct element *next;
  } *head, *tail;
  sem_t count;
  sem_t excl;
};

void llqueue_put(struct llqueue *ll, value_type v) {
  struct element *e = malloc(sizeof(struct element));
  e->value = v;
  e->next = NULL;
  sem_wait(&ll->excl);
  if (ll->tail == NULL)
    ll->head = e;
  ll->tail = e;
  sem_post(&ll->excl);
  sem_post(&ll->count);
}

value_type llqueue_get(struct llqueue *ll) {
  sem_wait(&ll->count);
  sem_wait(&ll->excl);
  struct element *h = ll->head;
  value_type v = h->value;
  if (h->next == NULL)
    ll->tail = NULL;
  ll->head = h->next;
  sem_post(&ll->excl);
  free(h);
  return v;
}

void llqueue_init(struct llqueue *ll) {
  ll->head = ll->tail = NULL;
  ┌───────────────────────┐
  │                       │
  └───────────────────────┘
}
</code>


<html></div></html>


~~META:
language = en
~~