ICS 332 Spring 2026

Sample Homework Assignment #2

Overview

This is a sample assignment with questions that are more involved than the provided sample problems.

Solutions

Solutions are available as a plain ASCII file.

Exercise #1

Consider the following C program (assume there are not compilation of execution errors of any kind):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int count;

    if ((argc != 2) || (sscanf(argv[1],"%d",&count) != 1)) {
        fprintf(stderr,"Usage: %s <integer>\n", argv[0]);
        exit(1);
    }

    pid_t pid1, pid2;
    while (count > 1) {
        pid1 = fork();
        if (pid1 > 0) {
            count = count / 2; // INTEGER DIVISION
        } else if (pid1 == 0) {
            pid2 = fork();
            count = count - 1;
        }
    }
    exit(0);
}

Assume that this program executes successfully on some system.

Let T(n) be the number of processes this program creates (i.e., not counting the original process) when its input is n.

Question #1

It’s easy to see that T(0) = T(1) = 0. What is T(2)?

Question #2

What is T(3)?

Question #3

Write a recursive formula (i.e., a recurrence relation) that gives T(i) as a function of one or more values of T for smaller input (i.e., smaller i). Explain your reasoning.

Feel free to double-check your formula by actually running the program and counting the number of running processes (you will have to make it so that processes don’t immediately exit at the end so that you can count them).

Question #4

Say the maximum number of processes that can be created on your machine is 10,000 (you can find out the actual number of your machine with ulimit -u).

What is the smallest value of the command-line argument for which the above program would experience failed fork() calls? (hint: no need to solve the induction, just write a program)

Exercise #2

Consider the following C program (assuming that there are no compilation or execution errors):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

int main(int argc, char **argv) {
        pid_t pid;
							    
        // Main process's PID=66
        pid = fork(); // creates process with PID=23
        if (pid > 0) {
                pid_t pid2 = fork(); // creates process with PID=101
                if (pid2 == 0) {
                        sleep(10);
                        exit(0);
                }
		sleep(20);
                exit(0);
        } else {
                pid_t pid3 = fork(); // creates process with PID=89
                if (pid3 == 0) {
                        sleep(40);
                        printf("** ONE **\n");
                        exit(0);
                }
                pid_t pid4 = fork(); // creates process with PID=200
                if (pid4 == 0) {
                        sleep(50);
                        exit(0);
                }
                waitpid(pid3, NULL, 0);
        }
	sleep(20);
        printf("** TWO **\n");
        exit(0);
}

Assume that the PID of the main process is 66. Each call to fork() in the code is commented to show the PID of the newly created process (In practice this would all be consecutive integers, but to avoid one-off mistakes they are picked to be very different integers).

In this exercise we assume that all operations take zero time but for sleep() (which sleeps a prescribed number of seconds) and waitpid(), which obviously might block for a while. We also assume that the execution starts at time zero. Therefore, in all the questions below, whenever time is mentioned/needed, it’s always a perfect multiple of 10 (since all calls to sleep in the above program are for numbers of seconds that are multiples of 10).

Answer the following questions: