UTSA CS 3733 Operating Systems Assignment 4 Fall 2011

CS 3733 Operating Systems, Fall 2011 Assignment 4

Due Monday, November 21

In this assignment you will write several versions of a program to find the first few prime numbers greater than a given number. We will use a fairly stupid algorithm. The purpose of the assignment is not to solve the problem, but to show how you might use concurrency to speed up the execution.

In each part you are asked to modify the program from the previous part. In doing so, make a new file containing the new program. You may want to name the programs part0, part1, etc. Save the programs for each part, as you may need to run them again. Put them all in a directory called assign4.

Each program should start by outputting (to standard error) which part of the assignment this is, your name and the command line parameters. It should then give the answer or answers. Only the answers should go to standard output and all output should be to standard error. Eventually we will redirect standard output to a file and do a checksum on the result.

At the end of the assignment, the requirements for turning in your program are described. Run all of the tests on the same machine, if possible.

Basic algorithm:
An an integer, n, is prime if it is at least 2 and the only positive factors it has are 1 and itself. If n has a factor that is greater than 1 and less than n, at least one such factor is at most sqrt(n). You will test each value of k between 2 and sqrt(n), to see if k is a factor of n. If none are factors, then n is a prime number. k is a factor of n if n%k is 0.

For each value of k in this range we test whether n%k is 0. If it is, we have found a factor and the number is not prime.

Do not modify the algorithm to make it more efficient. For example, we know that other than 2, the smallest factor must be odd. Do not use this fact.

Part 0
Write a function isPrimeInt that takes one integer parameter and returns true if that parameter is prime and false otherwise. Use the algorithm described above. Put the function in a file called primelib.c. Test this by writing a program, part0.c that takes one command line parameter, an integer n, and prints a message indicating whether or not n is prime.

Notes:

You may use atoi to convert the command line parameter to an int.
Exit the program with an appropriate message if it does not have exactly one command line parameter.
Test your program with some big numbers. It should be pretty quick no matter which number you use. It will take the longest when the number is prime or the product of two large primes, but it should produce the results in well under a second.
All of the output from this program should go to standard error.

Here are some good int values to try:

12347
12349
1493749
1493748
2147483647
2147483645

Part 1
Write a function called isPrimeLongLong in primelib.c. This program will take a single long long parameter and return true if the parameter is a prime, and false otherwise. Use the same algorithm as before. This function should be similar to isPrimeInt. Write a program called part1.c to test this function. Very little of your program needs to be changed, except for replacing int by long long in the appropriate places. Only use long long where necessary. You can use atoll to convert the command line string to a long long. All output should go to standard error.

Try your program with the same values for Part 0, plus some additional larger values below.

Here are some larger values for you to test.

439366540651
38743898310620761
426182928722265301
2305843009213693951
9223371873002223329
9223372036854775807

You can tell whether each of these is a prime by using the factor program that is available on our machines in the lab.

After you think your isPrimeLongLong function is correct, download this program. Compile it with:
cc -o testpart1 testpart1.c primelib.c -lm
and run the program, redirecting standard output to a file called part1.out.
Execute:
ls -l part1.out
wc part1.out
md5sum part1.out
and save the result. Turn this in.

Part 2
Now have the program find the first prime number that is at least as great as the command line parameter. Make a program called part2.c that is similar to part1.c, but includes a loop. If the given number is not prime, try the next value and continue until you find a prime. When the correct number is found, output the original number and then the prime found to standard output, each on a separate line with no additional characters. The only output to standard output should be these two lines and they should not contain any blanks or letters. Run your program on the first 11 of the test cases above and create a single file containing what was printed to standard output. The file should contain exactly 22 lines. Why shouldn't you run the program on the last test case? If your program is named appropriately, you can use this script to run your program. After running this program execute:
ls -l part2.out
wc part2.out
md5sum part2.out
and save the result. Turn this in.

Part 3
Here we will address the problem described in the introduction. Write a program called part3.c that will now take two command line parameters: n and m, where n is the the starting value as before, m is the number of primes to find. This second number, m, should be an int (not a long long). Check the command line parameters, and print an appropriate message (to standard error) if necessary. Then add an additional loop to solve the problem in part 2 m times. Do not print the results until all m values have been found. Then print the value of n and each of the primes found to standard output, one per line with only the digits and the newline being output. Do not output any blanks. The primes found should be in numerical order and exactly m+1 lines should be produced (even if n is prime, in which case n will appear twice). After you are sure your program is working, run the program using test number 9 and 20 as parameters. Redirect standard output to the file part3.out, execute:
ls -l part3.out
wc part3.out
md5sum part3.out
and save the result. Turn this in.
Note that this may take a long time to run, on the order of several minutes. To get an idea of how long it will take, run the program with the second parameter of 2 and see how long it takes to find 2 primes. It should take about 10 times as long to find 20 of them. If your program is very inefficient and it looks like finding 20 primes will take more than 5 minutes, run this on test number 8 instead. This should take about one fourth the time as running on test number 9.

Part 4
The program your wrote in part 3 is very CPU intensive and can be speeded up by taking advantage of a multicore CPU. Most of the machines in our lab have 4 cores, so in theory we can speed up the calculation by a factor of 4 by using all of the cores. This program should produce exactly the same output as the program in Part 3 (assuming the parameters are the same). Think about how an algorithm that will implement Part 3 using thread to take advantage of the multiple CPUs. We will discuss this in class and you will then implement the algorithm we develop. Here are some things to think about:

How will each thread know which numbers to test for primes?
Where will the threads store the primes they find?
How will each thread communicate its results back to a common thread?
Remember, that nothing is printed until all calculations are complete.
The results should be output in numerical order, independent of the order in which the threads complete. How can this be done?
What synchronization needs to be done to protect critical sections?
How will a thread know when to terminate?

Do the following on the same machine, one with at least 2 cores:

Time the test you did in part 3 with test number 9 finding 20 primes.
You will generate the file part3.out.
Time part 4 with the same test but with 1, 2, 3, 4, 5, 8, and 20 threads.
For each one, create a file called part4-k.out, where k is the number of threads.
Put all of these files in a common directory in which these are the only files with the extension .out. Then run:
```
      ls -l *.out
      wc *.out
      md5sum *.out
```
and turn in the results. If you did this correctly, all of the files should be identical. Each of the files should contain exactly 21 lines.
Run the timing tests when no other processes are putting a significant load on the CPU.
Make a table giving your timing results. One column of the table should give the number of threads and another should give the time. The time we are interested in is the elapsed time, also called real time or wall clock time. This is the same time you would get if you used to stopwatch to time the code from start to finish. Be sure to state the units of time used (minutes, seconds, milliseconds, or microseconds). The units should be appropriate for the values given in the table.

Additional questions for Part 4, added 11/13/11:
Answer the following questions:

Describe in words what the shared buffer does. Indicate how you did the synchronization and the algorithm for adding to the buffer, e.g. what to do if you add to a full buffer.
Describe the conditions under which a thread will exit.
Can you tell how many cores the machine has from the results of your table? Explain.

If you used a method other than the one described in the assignment, you need to describe in detail what you did including a discussion of the synchronization you used and how the threads terminated.

Handing in your assignment
You will hand in the source code for each of the 5 parts of the assignment. In addition, you will run specific tests for each part. You will time each test using the time command. Make sure the time command you are using displays the user time, the system time and the elapsed time. We are interested in the elapsed time.

Use this cover sheet.