tmp2rv4ngki

Semaphore Assignment

For this assignment you will add a semaphore to fix a race condition in an existing program.

Since this program is using fork() you will need to run it in either macOS or your Linux VM. If you are using your VM, you should give the VM 2 processor cores to work with by going to the settings for the VM, clicking on the System tab, selecting the Processor subtab, and increasing the processors to 2. Your VM needs to be shut down to change this setting.

The Program

The program in find_divisors.c takes a list of positive integers from the command line and prints the divisors of each integer using a naive algorithm. The program forks a child process, and the parent and the child work in parallel to go through the list of numbers.

The list of numbers is placed in an array before forking, so each process has a copy of the array after forking. Currently the only shared resource between the two processes is the index of the next number to process.

Each process calls get_next_number() in a loop to figure out what number to process next. get_next_number() returns 0 when the end of the list is reached, and the loop terminates when that is the case.

Try compiling the program as it is:

$ gcc find_divisors.c -o find_divisors

And then run it with a small list of numbers:

$ ./find_divisors 1 2 3 4
1: 1
2: 1 2
3: 1 3
4: 1 2 4

This is too few numbers for the race condition to present itself. The command seq can generate a list of numbers for you. You can embed a command line command within another command using backticks. So to pass the numbers 1 through 1000 to the program, run it like this:

$ ./find_divisors `seq 1000`

This should be enough arguments to expose the race condition, but it is probably hard to see through inspection. Pipe the output through wc -l to see how many lines are printed:

$ ./find_divisors `seq 1000` | wc -l
1024

Like we saw in class, the processes are occasionally doing duplicate work due to the race condition.

Adding a Semaphore

The critical region here is in get_next_number():

    if(*index >= size) {
        number = 0;
    }
    else {
        number = numbers[*index];
        *index = *index + 1;
    }

See the file shared_memory_semaphore.c from the class code to see the version of the code from class that fixed the race condition with a semaphore. Like in that program, you will need to do the following:

Come up with a name for the semaphore
Delete the semaphore in case it already exists
Open a new semaphore
Enclose the critical region with calls to sem_wait() and sem_post()
Have the parent process delete the semaphore after the child has terminated

Since you will need to set up the semaphore in main() but use the semaphore in get_next_number() you will either need to declare the semaphore pointer as a global variable, or add a parameter to get_next_number() so you can pass the pointer to the function.

In Linux you need to add the -pthread option to the compile command for the program to compile with the semaphore functions. This is not required in macOS, but it does not hurt. So the compile command becomes this:

$ gcc -pthread find_divisors.c -o find_divisors

Testing your Code

If your semaphore is working correctly, you should always see 1000 lines when running the program with the integers 1 through 1000.

You can see the parallelism in action by running the program with much larger integers.

Now try giving it the numbers 6,000,000,000 and 6,000,000,001:

$ ./find_divisors 6000000000 6000000001

Both processes will chug away for a little while (about a minute on my macbook), then you should see the first two numbers’ divisors printed at about the same time. Note that the first number has many divisors but the second is prime.

If you run the command top in another terminal you should see both processes using 100% of a CPU core while it is running.

Submission

Push your code back to git-keeper.

CS 210

Semaphore Assignment

The Program

Adding a Semaphore

Testing your Code

Submission