CSC 209 extra problems regarding pthreads

1. At https://www.teach.cs.toronto.edu/~ajr/209/probs/pthreads/starter.c you will find code for a basic merge sort. This program also initializes an array with random numbers before invoking the sort, and does some checking after the sort to see if it worked.

You don't have to read all of the code, but do note the mysort() function and how it is recursive — see the initial call in main(), and see the two recursive calls in mysort() itself. (Ignore mysort()'s bizarre return type for now; this will save you time later.)

This problem is to make this into a parallel merge sort, by using threads.

One issue is that thread functions only take one argument, but we have two arguments to mysort(). So to make a threads version of this code, we need to change it to use a pointer to a struct. Add this struct type declaration at the top:

	struct args {
	    int *p;
	    int size;
	};

Then change the three mysort() calls (one in main(), two in mysort()) to create a "struct args" and pass a pointer to that instead. Example:

	struct args subarg1 = { p, midpoint };
	mysort(&subarg1);

	int *p = ((struct args *)arg)->p;
	int size = ((struct args *)arg)->size;

Then, make it create threads. Instead of recursively calling one mysort() and then the other, make it do the two mysort()s in parallel using threads. But you can't proceed to the merge until both of the sub-sorts have completed.

And, of course, test that it's still working.

(Unfortunately, in its current form this code is not amenable to timing tests, because acquiring the random numbers takes a significant amount of time in comparison to the sort, and, more importantly, takes a highly variable amount of time depending on the randomness pool in the OS kernel which is used for /dev/urandom, and furthermore running this program a lot will deplete the randomness pool so it will affect the timing even more. All this is to say that to do timing tests you'd want to split the randomization from the sort, and repeat only the sort many times.)

2. The "Sieve of Eratosthenes" is an ancient method of finding prime numbers attributed to Eratosthenes, born in 276 BCE.

Imagine a board of 100 numbers:

Remove the 1, since that is neither a prime number nor composite.

Start with the 2, and leave that alone, but punch out (remove from the board) the numbers 4, 6, 8, 10, and so on — all of the multiples of 2.

Next go to the 3. Leave that alone, but punch out the numbers 6 (already punched out), 9, 12 (already punched out), and so on — all of the multiples of 3.

When we get to the 4, we see that it is punched out, so we don't have to do anything.

Then we punch out all of the multiples of 5, excluding 5 itself; and so on.

When we're done, we have left a list of the prime numbers less than (or equal to) 100.

Write a program using threads to do these "punching out"s in parallel.

Create an array of type int from 2 to 100, to be considered as booleans. (The easiest way to do this is with "int sieve[101];" and ignore sieve[0] and sieve[1].)

Set all of the values to true (1).

Then create a thread for each of the numbers from 2 to 100 inclusive, which will do the "punching out" for that number. These threads must run in parallel.

After you "pthread_join" (wait for) all the threads, print the numbers corresponding to all of the 1 values left in the array.

Note that this evades any concurrency issues — if two threads set a particular int to zero simultaneously, no harm is done.

Unlike the real Sieve of Eratosthenes, you will not be doing the optimization of, for example, seeing that 4 is already punched out and not bothering to do the algorithm for 4. This would raise concurrency issues.

NOTE: In standard software tools fashion, your output should be just the prime numbers, no more and no less, with one number per line (like the output of "seq").