CS 3733 Operating Systems, Spring 2008 Assignment 5

Due Friday, April 11

Put all of the code for this assignment in a fresh directory. For each part, perform the following tests from Assignment 4: tests 9, 10, 17, 18, 19. Since our starting point is Part 2 of Assignment 4, incorrect results may be obtained for some of the tests on some of the parts of this assignment.

Part 0
Start with your program from Part 2 of Assignment 4. Modify findFactors1 and findFactors2 so that they can be called as threads. This means that each needs to have one pointer parameter and return a pointer. We will not use the return value, so they can return NULL. Instead of taking a parameter that is a long long, have them each take one parameter that is a pointer to a long long. Call the functions without creating any threads. Modify findFactors2 so that it terminates after saving its first factor.

We will have to handle errors differently if we are not going to use the return value of findFactors1 or findFactors2. Have saveValue set a global error number (not errno) in case an error occurs. Check this value each time findFactors1 or findFactors2 returns. Terminate the program with an appropriate error message if an error occurs.

Answer the following questions:

1. How should the global error number be declared and why?
   Hint: Look at USP: Program 8.9, page 280.
2. This program is based on Part 2 of Assignment 4 which can give incorrect results under some circumstances.
   Does this implementation have the same problem?
   What were your results for test number 10?

In this case we have two concurrent threads looking for primes and storing the results using saveValue. Answer the following questions:

3. Suppose one of the threads calls saveValue and loses the CPU just at the wrong place in saveValue.
   Where this place is will depend on your implementation, but there will always be such a place.
   Now the other thread calls saveValue.
   What can go wrong?
4. Did you experience the above problem when running your program? If you did, what were the results?
   If not, why do you think it did not occur?

Part 2
Add appropriate synchronization to saveValue so that the program does not have any synchronization issues. The simplest method is to use a pthread_mutex_lock as in USP Program 13.2, on page 454, but other methods are available. Answer the following question:

5. What synchronization method did you use?

Part 3
If findFactors1 finds a factor, findFactors2 will not find a new prime factor. Have findFactors1 kill off the findFactors2 thread if it finds a factor.

We cannot do this using pthread_cancel since findFactors2 does not have any cancellation points. Consider using the following method. Have a global variable which is initially false and set to true when findFactors1 finds a factor. Have findFactors2 examine this value in its loop and terminate if the value it true.

6. How should this global variable be declared?
7. Are there any synchronization issues involved in having two threads access this global variable concurrently?
8. Did this solve the problem with the tests that were giving incorrect results?
9. The program still has a possibility of producing non-prime factors.
   How can this occur even if the second thread is killed?

Part 4
In this part we will fix the problem of factors that are not prime. You may use any method you like to do this. Here are two suggestions.

• When both threads have completed, your list of factors will contain all prime factors less than sqrt(n).
  It may contain at most one number that is not a prime factor (since findFactors2 cannot find more than one factor).
  For each number in the list, see if it is divisible by one of the others.
• If one of the numbers in the list is less than sqrt(n)/2, remove any other ones from the list (there will be at most one) greater than sqrt(n)/2.

10. Write a short paragraph describing the method you used to implement this part.
11. If all of your tests were giving correct results in Part 3, how did you test that this really solved the problem?

Part 5
One problem still remains. It is possible for findFactors2 to find a factor that findFactors1 has already found.

12. Find an example of a small integer, n, that has three prime factors, p, q, and r, such that p < sqrt(n)/2 and sqrt(n)/2 < q < sqrt(n).
    Hint: you can find an example with three small distinct prime factors.
13. Try Part 4 on this example. Did it give the correct results?

Fix the problem by having saveValue reject multiple factors. Now when all threads have completed, check each factor to see how many times it divides the original value.

Part 6
In Parts 3 and 4, if findFactors1 finds a factor and kills the findFactors2 thread, only one CPU will be working on this problem. Find a way to do what we did in Part 5 of Assignment 4 by having the program use 2 threads on the reduced problem whenever a factor is found.

14. Write a short paragraph describing the method you used to implement this.
15. Did you have to modify the fix from Part 4 or any other part of the program? Explain.
    This is a question about whether your program is correct, not about whether it gave the right answers for the tests you tried.

Part 7
What if we were to utilize 3 threads by breaking the problem into 3 parts:
     2 to sqrt(n)/3
     sqrt(n)/3 to 2*sqrt(n)/3
     2*sqrt(n)/3 to sqrt(n)
If the first one found a factor, would it be possible for one of the others to find a prime factor? In other words,

16. Is it possible for n to have a prime factor between 2 and sqrt(n)/3 and one between sqrt(n)/3 and sqrt(n)?
    Give an example involving small numbers.
17. How would you have to modify the program to handle this? Will only prime factors be found?
    Note: you do not need to implement this.

Handing in your assignment
You will hand in the source code for each of the programming parts of the assignment.

In addition, run the tests listed above (with timing) for each part of the assignment. Do all of the tests on the same type of machine, all at home, or all in the lab. If you do the tests on UTSA machines, try to do all of them on main2xx machines which are mostly identical. Check the load average before running your tests. (You can do this with the w command.) If the load average is high, note this with your output.

Answer the questions for each part of the assignment. Please type your answers and make sure each is labeled with the appropriate number.

Use this cover sheet.