CS 3214 Final: CS3214 FinalCS3214F09
CS 3214 Sample Final Exam (Fall 2009)
1/10
Sample Final Exam (Fall 2009)
Solutions are shown in this style. This exam was given Fall 2009
1. System Calls (16 pts)
a) (12 pts) Consider the following interaction of a user running bash in a terminal. In the
table below, list the following events: (1) process-related system calls (fork, exec, exit,
kill, wait/waitpid) and (2) signals delivered to a process (such as SIGCHLD, SIGINT,
SIGTSTP, SIGTERM).
User input shown in bold, terminal
output in italics
Shell Process Child Process1 Child Process2
$ ls fork()
exec(“ls”)
exit()
waitpid()/
SIGCHLD
$ sleep 100 &
[1] 29598
fork()
exec(“sleep”)
$ sleep 200 &
[2] 29599
fork()
exec(“sleep”)
$ jobs
[1]- Running sleep 100 &
[2]+ Running sleep 200 &
$ fg %2
sleep 200
waitpid()
User types ^C
SIGINT
SIGCHLD
+waitpid()
waitpid()
$ fg %1
sleep 100
waitpid()
User types ^Z SIGTSTP
SIGCHLD
+waitpid()
[1]+ Stopped sleep 100
$ kill %1 kill()
SIGTERM
SIGCHLD
+waitpid()
$ jobs
CS 3214 Sample Final Exam (Fall 2009)
2/10
[1]+ Terminated sleep 100
Use different rows to express if events are synchronized, i.e., if it is guaranteed that event n
occurs after event m, then event n should be listed in a row below event m. Note that not all
rows/columns will have entries.
b) (4 pts) Explain briefly the key difference between the terms “background process” and
“stopped process”!
A background process is one whose process group is not currently the foreground
process group of its controlling terminal (or a process that has been detached from its
controlling terminal). A background process can perform computation, consume CPU
time, or be blocked while doing I/O or engaging in synchronization with other processes.
A stopped process is a background process that is in the stopped state – it is not
scheduled by the OS onto any CPU, cannot perform computation or I/O until it is moved
out of the stopped state via a SIGCONT signal or terminated.
2. Multithreading (18 pts)
a) (10 pts) Consider a fixed thread pool such as the one you implemented in exercise 11.
Such a thread pool creates a fixed number of threads that process submitted tasks in
FIFO order. Each task (or “callable”) is represented by a C function that receives a
pointer to a custom argument.
/* Data to be passed to callable. */
struct callable_data {
int number;
sem_t *next, *previous;
};
/* A callable. */
void *
callable_task(struct callable_data *
callable)
{
sem_wait(callable->previous);
printf("Task %d ran.\n",
callable->number);
sem_post(callable->next);
return NULL;
}
int
main(…) {
…
const int N = ntasks;
sem_t s[N + 1];
// …. main continued
// create N callable tasks
struct callable_data * callable_data[N];
for (i = 0; i < N; i++) {
callable_data[i] = malloc(
sizeof *callable_data[i]);
callable_data[i]->number = i;
callable_data[i]->next = &s[i + 1];
callable_data[i]->previous = &s[i];
}
// submit tasks to thread pool
for (i = N - 1; i >= 0; i--) {
printf("Submitting task %d:
next=%d, previous=%d\n",
callable_data[i]->number,
callable_data[i]->next - s,
callable_data[i]->previous - s
);
thread_pool_submit(ex,
(thread_pool_callable_func_t)
callable_task,
callable_data[i]);
}
CS 3214 Sample Final Exam (Fall 2009)
3/10
// initialize N + 1 semaphores
for (i = 0; i < N + 1; i++)
sem_init(&s[i], 0, 0);
printf("Posting first semaphore\n");
sem_post(&s[0]);
sem_wait(&s[N]);
printf("Done.\n");
}
As in exercise 11, the number of threads and tasks can be varied.
i. (5 pts) Suppose this program is run with 4 threads and 2 tasks. The first three lines
the program outputs are shown below. Describe what output, if any, the program will
produce next. If no output is produced or if the output is not deterministic, state that!
$ ./threadpool_test 4 2
Submitting task 1: next=2, previous=1
Submitting task 0: next=1, previous=0
Posting first semaphore
Task 0 ran.
Task 1 ran.
Done.
In this example, each task N waits for task N-1 to signal a shared semaphore (“previous”), then
signals a semaphore that is shared with task N+1 (“next”). The main thread signals the
semaphore on which task 0 is waiting, then waits for the last semaphore to be signaled. This is
a classic example of using semaphores to express precedence constraints.
ii. (5 pts) Now suppose the program is run with 4 threads and 5 tasks. Describe what
output, if any, the program will produce next. If no output is produced or if the output
is not deterministic, state that!
$ ./threadpool_test 4 5
Submitting task 4: next=5, previous=4
Submitting task 3: next=4, previous=3
Submitting task 2: next=3, previous=2
Submitting task 1: next=2, previous=1
Submitting task 0: next=1, previous=0
Posting first semaphore
In this example, deadlock will occur because the tasks are inserted in decreasing order (first
task 4, then task 3, etc.) Task 4 waits for 3, task 3 waits for 2, task 2 for task 1, and task 1
waits for task 0. Since the thread pool, as stated, will handle tasks in FIFO order and since it is
limited to handling 4 tasks simultaneously, task 0 cannot be run until at least one of tasks 1-4
completed. Since these tasks depend on task 0, a deadlock occurs.
b) (8 pts) What output do the following 2 programs produce and why?
#include <pthread.h> #include <pthread.h>
Document Summary
This exam was given fall 2009: system calls (16 pts, (12 pts) consider the following interaction of a user running bash in a terminal. In the table below, list the following events: (1) process-related system calls (fork, exec, exit, kill, wait/waitpid) and (2) signals delivered to a process (such as sigchld, sigint, User input shown in bold, terminal output in italics. A background process is one whose process group is not currently the foreground process group of its controlling terminal (or a process that has been detached from its controlling terminal). A background process can perform computation, consume cpu time, or be blocked while doing i/o or engaging in synchronization with other processes. Such a thread pool creates a fixed number of threads that process submitted tasks in. Each task (or callable ) is represented by a c function that receives a pointer to a custom argument.
