CSC374 Sample Exam Questions

Consider the C program below. (For space reasons, we are not checking error return codes, so assume that all functions return normally.)
```
int main () 
{
  if (fork() == 0) {
    if (fork() == 0) {
      printf("3");
    }
    else {
      pid_t pid; int status;
      if ((pid = wait(&status)) > 0) {
	printf("4");
      }
    }
  }
  else {
    printf("2");
    exit(0);
  }
  printf("0");
  return 0;
}
```
For each of the following strings, answer whether (Y) or not (N) this string is a possible output of the program.
1. 32040
2. 34002
3. 30402
4. 23040
5. 40302
Consider the following C program:
```
#include <sys/wait.h>
int main() 
{
  int status;
  printf("%s\n", "Hello");
  printf("%d\n", !fork());
  if(waitpid(-1, &status, 0) != -1) {
    printf("%d\n", WEXITSTATUS(status));
  }
  printf("%s\n", "Bye");
  exit(2);
}
	    
```
Recall the following:
- Function fork returns 0 to the child process and the child.s process id to the parent.
- Function wait returns -1 when there is an error, e.g., when the executing process has no child.
- The macro WEXITSTATUS extracts the exit status of the terminating process.
What is a valid output of this program? Hint: there are several correct solutions.

Answer:

This problem tests your understanding of exceptional control flow in C programs. For problems A-C, indicate how many "hello" output lines the program would print. For D, indicate the value the program would print for the variable counter.

Caution: Don't overlook the printf function in main.

void doit() {
  fork();
  fork();
  printf("hello\n");
  return;
}
int main() {
  doit();
  printf("hello\n");
  exit(0);
}

Answer: output lines.

void doit() {
  if (fork() == 0) {
    fork();
    printf("hello\n");
    exit(0);
  }
  return;
}
int main() {
  doit();
  printf("hello\n");
  exit(0);
}

Answer: output lines.

void doit() {
  if (fork() == 0) {
    fork();
    printf("hello\n");
    return;
  }
  return;
}
int main() {
  doit();
  printf("hello\n");
  exit(0);
}

Answer: output lines.

int counter = 1;
int main() {
  if (fork() == 0) {
    counter--;
    exit(0);
  }
  else {
    wait(NULL);
    counter++;
    printf("counter = %d\n", counter);
  }
  exit(0);
}

Answer: counter =

This problem tests your understanding of exceptional control flow in C programs. Assume we are running code on a Unix machine. The following 3 parts all concern the value of the variable counter.

Part I

int counter = 0;
int main()
{
  int i;
  for (i = 0; i < 2; i ++){
    fork();
    counter++;
    printf("counter = %d\n", counter);
  }
  printf("counter = %d\n", counter);
  return 0;
}

How many times would the value of counter be printed?
What is the value of counter printed in the first output line?
What is the value of counter printed in the last output line?

Part II

pid_t pid;
int counter = 0;
void handler1(int sig)
{
  counter ++;
  printf("counter = %d\n", counter);
  fflush(stdout); /* Flushes the printed string to stdout */
  kill(pid, SIGUSR1);
}
void handler2(int sig)
{
  counter += 3;
  printf("counter = %d\n", counter);
  exit(0);
}
main() {
  signal(SIGUSR1, handler1);
  if ((pid = fork()) == 0) {
    signal(SIGUSR1, handler2);
    sleep(1); // Let parent execute
    kill(getppid(), SIGUSR1);
    while(1) {};
  }
  else {
    pid_t p; int status;
    if ((p = wait(&status)) > 0) {
      counter += 2;
      printf("counter = %d\n", counter);
    }
  }
}

What is the output of this program?

Part III

int counter = 0;
void handler(int sig)
{
  counter ++;
}
int main()
{
  int i;
  signal(SIGCHLD, handler);
  for (i = 0; i < 5; i ++){
    if (fork() == 0){
      exit(0);
    }
  }
  /* wait for all children to die */
  while (wait(NULL) != -1);
  printf("counter = %d\n", counter);
  return 0;
}

Does the program output the same value of counter every time we run it? Yes/No:
If the answer to is Yes, indicate the value of the counter variable. Otherwise, list all possible values of the counter variable.

Answer:
1,2,3,4,5 (may need to insert various sleep calls to see these different values on a particular machine)

Consider the following C program. (For space reasons, we are not checking error return codes. You can assume that all functions return normally.)


int val = 10;
void handler(sig)
{
  val += 5;
  return;
}
int main()
{
  int pid;
  signal(SIGCHLD, handler);
  if ((pid = fork()) == 0) {
    val -= 3;
    exit(0);
  }
  waitpid(pid, NULL, 0);
  printf("val = %d\n", val);
  exit(0);
}

What is the output of this program? val =

This problem concerns the following four versions of the tfgets routine, a timeout version of the Unix fgets routine.

The tfgets routine waits for the user to type in a string and hit the return key. If the user enters the string within 5 seconds, the tfgets returns normally with a pointer to the string. Otherwise, the routine "times out' and returns NULL.

For each version (a - d) indicate (Y/N) whether it will correctly implement this description of tfgets.

Y/N

void handler(int sig) {
  siglongjmp(env, 1);
}
char *tfgets(char *s, int size, FILE *stream) {
  pid_t pid;
  signal(SIGCHLD, handler);
  if (!sigsetjmp(env, 1)) {
    pid = fork();
    if (pid == 0) {
      return fgets(s, size, stream);
    }
    else {
      sleep(5);
      kill(pid, SIGKILL);
      wait(NULL);
      return NULL;
    }
  }
  else {
    wait(NULL);
    exit(0);
  }
}

Y/N

void handler(int sig) {
  wait(NULL);
  siglongjmp(env,1);
}
char *tfgets(char *s, int size, FILE *stream) {
  pid_t pid;
  signal(SIGUSR2, handler);
  if (sigsetjmp(env, 1) != 0)
    return NULL;
  if ((pid = fork()) == 0) {
    sleep(5);
    kill(getppid(), SIGUSR2);
    exit(0);
  }
  fgets(s, size, stream);
  kill(pid, SIGKILL);
  wait(NULL);
  return s;
}

Y/N

void handler(int sig) {
  wait(NULL);
  siglongjmp(env, 1);
}
char *
tfgets(char *s, int size, FILE *stream) {
  pid_t pid;
  str = NULL;
  signal(SIGCHLD, handler);
  if ((pid = fork()) == 0) {
    sleep(5);
    exit(0);
  }
  else {
    if (sigsetjmp(env, 1) == 0) {
      str = fgets(s, size, stream);
      kill(pid, SIGKILL);
      pause();
    }
    return str;
  }
}

Y/N

void handler(int sig) {
  wait(NULL);
  siglongjmp(env, 1);
}
char *
tfgets(char *s, int size, FILE *stream) {
  pid_t pid;
  str = NULL;
  signal(SIGCHLD, handler);
  if ((pid = fork()) == 0) {
    sleep(5);
    return NULL;
  }
  else {
    if (sigsetjmp(env, 1) == 0) {
      str = fgets(s, size, stream);
      kill(pid, SIGKILL);
      pause();
    }
    return str;
  }
}

The following problem concerns the way virtual addresses are translated into physical addresses.

The memory is byte addressable.
Memory accesses are to 1-byte words (not 4-byte words).
Virtual addresses are 16 bits wide.
Physical addresses are 14 bits wide.
The page size is 1024 bytes.
The TLB is 4-way set associative with 16 total entries.

In the following tables, all numbers are given in hexadecimal. The contents of the TLB and the page table for the first 32 pages are as follows:

TLB:

Set	Tag	PPN	Valid	Tag	PPN	Valid	Tag	PPN	Valid	Tag	PPN	Valid
0	8	7	1	F	6	1	0	3	0	1	F	1
1	1	E	1	2	7	0	7	3	0	B	1	1
2	0	0	0	C	1	0	F	8	1	7	6	1
3	8	4	0	3	5	0	0	D	1	2	9	0

Page table: (Only the first 32 PTE's shown.)

Page Table

VPN	PPN	Valid
00	2	0
01	5	1
02	7	1
03	D	1
04	F	1
05	E	1
06	B	0
07	D	1
08	7	1
09	C	0
0A	3	0
0B	1	1
0C	0	1
0D	D	0
0E	0	0
0F	1	0

VPN	PPN	Valid
10	1	1
11	3	0
12	9	0
13	7	1
14	D	1
15	5	0
16	E	1
17	6	0
18	1	0
19	0	1
1A	8	1
1B	C	0
1C	0	0
1D	2	1
1E	7	0
1F	3	0

For the given virtual addresses, indicate the TLB entry accessed and the physical address. Indicate whether the TLB misses and whether a page fault occurs.

If there is a page fault, enter "-" for "PPN" and leave part C blank.

Virtual address: 0x027c

Virtual address format

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0

Address translation

Parameter	Value
VPN
TLB Index
TLB Tag
TLB Hit? (Y/N)
Page Fault? (Y/N)
PPN

Physical address format

13	12	11	10	9	8	7	6	5	4	3	2	1	0

Virtual address: 0x0C53

Virtual address format

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0

Address translation

Parameter	Value
VPN
TLB Index
TLB Tag
TLB Hit? (Y/N)
Page Fault? (Y/N)
PPN

Physical address format

13	12	11	10	9	8	7	6	5	4	3	2	1	0

This problem concerns dynamic storage allocation.

Consider an allocator that uses an implicit free list. The layout of each allocated and each free memory block is as follows:

	   31                           2 1 0
	   __________________________________
 Header	  |   Block Size (bytes)       |     |
	  |____________________________|_____|
	  |                                  |
	  |                                  |
	  |                                  |
	  |                                  |
	  |                                  |
	  |__________________________________|
 Footer	  |   Block Size (bytes)       |     |
	  |____________________________|_____|

Each memory block, either allocated or free, has a size that is a multiple of eight bytes. Thus, only the 29 higher order bits in the header and footer are needed to record block size, which includes the header and footer.

The usage of the remaining 3 lower order bits is as follows:

bit 0 indicates the use of the current block: 1 for allocated, 0 for free.
bit 1 indicates the use of the previous adjacent block: 1 for allocated, 0 for free.
bit 2 is unused and is always set to be 0.

Given the contents of the heap shown on the left, show the new contents of the heap (in the right table) after a call to free(0x400b010) is executed.

Your answers should be given as hex values. The contents of the payload of a free block is not used and can be any arbitrary hex value.

Note that the addresses grow from bottom up. So the previous block is below the block at 0x400b010.

Assume that the allocator uses immediate coalescing, that is, adjacent free blocks are merged immediately each time a block is freed.

Address		Address
0x400b028	0x00000013	0x400b028
0x400b024	0x400b611c	0x400b024	0x400b611c
0x400b020	0x400b512c	0x400b020	0x400b512c
0x400b01c	0x00000013	0x400b01c
0x400b018	0x00000011	0x400b018
0x400b014	0x400b511c	0x400b014	0x400b511c
0x400b010	0x400b601c	0x400b010	0x400b601c
0x400b00c	0x00000011	0x400b00c
0x400b008	0x00000012	0x400b008
0x400b004	0x400b601c	0x400b004	0x400b601c
0x400b000	0x400b511c	0x400b000	0x400b511c
0x400affc	0x00000012	0x400affc

Two threads execute the following function. The parameter passed to threadfnc for each thread is the same int array of size 1024. The threads are trying to cooperate to increment each array element by 1.

The array a is declared globally. The index i is also global and is initially equal to 0.
```
	      int a[1024];
	      int i = 0;
	      sem_t mutex; // initial value 1
	    
```
A semaphore, mutex, with initial value 1 is used to ensure that only one thread at a time increments a[i] and increments i.
```
void *threadfnc(void *p)
{

  while(i < 1024) {
    sem_wait(&mutex);
    a[i]++;
    i++;
    sem_post(&mutex);
  }
  return NULL;
}
```
When this code is tested, it almost works. Each element of the array is incremented just once, but it is discovered that on some executions an index out of bounds error occurs: one of the threads attempts to update a[1024]!

Briefly explain why this could occur.

Answer:

When i = 1023, this sequence would cause the error: (1) semaphore value of mutex is 0 and first thread executes a[1023]++ (2) second thread evaluates i < 1024 (still true, i is 1023) (3) second thread executes sem_wait(&mutex) and blocks (4) first thread evaluate i++ (now i is 1024) (5) first thread evaluates sem_post(&mutex) which unblocks second thread (6) first thread tests i < 1024 (false) (7) first thread returns (8) second thread increments a[1024] : error