/*    CSC 145 Assignment: Java Concurrency

1.  The first problem will deal with multi-threaded matrix
    multiplication.  A rXc matrix can be multiplied by a cXr matrix.
    Here, a matrix will be represented as a double[][].  Given
    double[][] M, M.length is the number of rows of the matrix, and
    M[0].length is the number of columns of the matrix. (Java only
    uses dynamically allocated arrays).

    Assume we have arrays M, N, and R (pre-allocated).  M has dimensions
    rowsXcols, N has dimensions colsXrows, and R has dimensions
    rowsXrows.  The following code will multiply M and N and store
    the result in R:

	int i, j, k;
	for(i=0;i<rows;i++);
	 for(j=0;j<rows;j++)
	 {  R[i][j] = 0;
	    for(k=0;k<cols;k++)
		R[i][j] += M[i][k] * N[k][j];
	 } 

    It is possible, however, to have multiple threads be responsible for
    computing separate rows of the result.  That is, instead of one thread
    with a triple-loop, we can have rows number of threads, each running
    a double-loop.  Furthermore, this arrangement would require no
    critical section, since the threads will be writing to different
    parts of R.  

    Please implement this, and demonstrate your program.  I'm providing
    you with a class with some utilities.

    Watch out:
    When creating a thread, you should pass it pointers to all three
    matrices.  The matrices should be created outside of the threads
    (probably in main).  Make sure you call "join" on the threads, for
    otherwise you would not know when all the threads have finished.
    Demonstrate that your algorithm computes the same values as the
    conventional solution.
*/

public class javaasn1
{

    // returns randomized matrix:
    public static double[][] makerandom(int rows, int cols)
    {
	double[][] M;
	M = new double[rows][cols];
	for (int i=0;i<rows;i++)
	    for (int j=0;j<cols;j++)
		M[i][j] = Math.random() * 1000;   // fill with random values
	return M;
    }

    // prints matrix
    public static void printmatrix(double[][] M)
    {
	int rows = M.length;
	int cols = M[0].length;
	for (int i=0;i<rows;i++)
	  {
	    for (int j=0;j<cols;j++)
		System.out.print(M[i][j]+"\t");
	    System.out.print("\n");
	  }
    } // printmatrix

} // matrix

/////////////////////////////////////////////////

/*
2.  Thread Pools.

    In the above problem, if you had a matrix with 1000 rows you will
    need 1000 threads.  It is unlikely that your hardware can execute
    them all simultaneously.  Furthermore, the overhead of setting up
    the threads can be substantial.  More likely, you will have the
    hardward resources to run only 2, 4 or 8 threads simultaneously
    (on multi-core and multi-processor systems for example).  To take
    maximum advantage of such capabilities, you will still need multiple
    threads, and each thread will need to be responsible for mulitiple
    rows of the matrix.  An elegant way to structure such a scenario
    is the use of "thread pools".  

    We now make a distinction between a "thread" and "job".  A job
    is just piece of code that needs to be executed.  Multiple jobs
    can be allocated to the same thread.  For an array of 1000 rows,
    we will still have 1000 jobs, but only a "pool" of 2 or 4 threads 
    to execute all of them.

    The Java API has built-in support for thread pools.  Go to the
    class homepage, click on the "java threads" link and read the
    tutorial and example on how to use thread pools.  Here's my own
    little example:

        import java.util.concurrent.*;

        ...
        class myjob implements Runnable
        {
	   int jobid;
           public myjob(int id) {jobid=id;}
	   public void run()
           {
	     System.out.println("doing job "+jobid);
             ...
           }
        } 
         
        ...
        try 
        {
          ExecutorService pool = Executors.newFixedThreadPool(4);
          for (i=0;i<16;i++) 
              pool.execute(new myjob(i))
          pool.shutdown();   // join on all jobs (not just threads!)
          pool.awaitTermination(1000,TimeUnit.SECONDS);
        }
        catch(Exception e) {System.out.println(e);}


   The class "myjob" implements the run() method, but is not to be
   confused with a thread class.  The Executors.newFixedThreadPool(4)
   call creates a pool of 4 threads.  The for-loop then submits 16
   myjobs to the thread pool.  All 16 jobs are to be executed by the 4
   threads.  The call to shutdown() closes the pool from accepting new
   jobs, and awaitTermination, with a time out, is like "join" on all the
   jobs - that's all the JOBS, not just all the THREADS!.

   Please modify your parallel matrix multication program to use
   fixed-size thread pools.


2b. (do this last)  
     Using Java's built-in thread pools is relatively easy.
     It is also possible to implement such a mechanism yourself, using
     the primitive "synchronized", "wait" and "notify" mechanisms.  Your
     thread pool must maximize thread utilization.  That is: no thread
     should be idle when there are jobs waiting to be executed.
     If you have 16 jobs and 4 threads, you might think: just allocate
     four jobs to each thread.  But that won't work because some jobs will
     take longer than others.  Thread 1 could finish all four of its jobs
     before thread 2 can even finish 2.  At this point, thread 1 should not
     be idle, because there are jobs waiting to be executed.

     The exact implementation details are up to you, but here is a suggested
     layout of the structure:

     interface Job
     {
        public void run();
     }

     // you have to implement concrete classes to implment Job

     class workerthread implements Runnable (an actual thread class)
     
     class ThreadPool

 The ThreadPool class should maintain the following data structures:

 * A list/array of all submitted jobs and their current status.  The
   status value is either READY, RUNNING or COMPLETE.  When a job is
   first submitted, it will be in the READY state.

 * An array of a fixed number of workthreads

The ThreadPool class also need to implement the following methods:

  synchronized int submit(Job newjob);  // called by an application 
       calls notifyAll(); to indicate new jobs has arrived

  synchronized Job getJob(workthread id); // called by a workerthread
       calls wait() if no jobs available 
  
  synchronized void setComplete(int jobid); // called by workerthread
       calls notifyAll() to wake up jjoin calls
       
  synchronized void jjoin(int jobid);        // called by application 
       calls wait() until setComplete called on jobid


The workerthread class will basically implement the following loop:
  loop:
  {
    calls getJob on the ThreadPool object to get a job
    calls the run() method of the job 
  }     

submit returns to the calling application an integer representing the
job id, which is needed by the application when it calls jjoin. 
getJob is called by a workerthread to obtain a READY job to execute.
getJob must also set the status of the job to RUNNING.
setComplete is also called by a workerthread, to change the status of
a job to COMPLETE.  jjoin is called by an application to wait for a
submitted job to complete. Synchronization is required by these methods.
When a workerthread calls getJob but no jobs are in the READY state,
it must wait().  When submit is called by an application to submit a 
new job, these workerthreads must wake up.  Similarly, an application
thread waits if it calls jjoin(), and wakes when a workerthread calls
setComplete.  Note that there are different conditions under which a 
thread waits or notifies, so you'll have to use notifyAll() together
with while loops (as opposed to if).

Here's sample code that should work with your implementation:

/* testing thread pool implementation */
class myjob implements Job  // a concrete job class
{
    public static int fact(int n)  // some work to be done
    {if (n<2) return 1; else return n*fact(n-1); }

    public int result; // to be used by application
    int n;             // parameter to fact function
    int id;            // job id (assigned by submit call)
    public myjob(int x, int id) {n=x; this.id=id;}

    public void run()
    {
	// simulate 0-8 second delay:
	try {Thread.sleep((int)(Math.random()*8000));} catch (Exception e) {}
	result = fact(n); // do work
    }
} // myjob



public class pooltest
{
   public static void main(String[] args) throws Exception
   {
       int i;
       ThreadPool pool = new ThreadPool(4);  // make pool of 4 worker threads
       for(i=0;i<16;i++)  // submit 16 jobs to pool
	   pool.submit(new myjob(i,i));  
       pool.start();
       for(i=0;i<16;i++)
	   pool.join(i);
       System.out.println("All jobs complete");  System.out.flush();
       pool.submit(new myjob(17,17)); //submit a new job 
   }
}

You should adopt your matrix multiplication program to your version
of thread pools
/////////////////////////////////////////////////
*/


/*
3. This problem asks you to design and apply Java synchronization
   mechanisms.  You are required to sketch your code first.

Suppose you are working for a tv network on an election night and that
you are actually completely unbiased towards any party.  Your task is
to update the election results as the votes are being counted.  Each
precinct periodically submits the results of every 1000 new votes.
But some precinct will report their results much faster than others.
Since you want to be as balanced as possible in your projections, you
do not want to give any precinct more weight than any other.  For
example, if precinct A is heavily republican, but the votes are coming
in much slower than the votes from heavily democratic precinct B, then
simply updating the total results at regular intervals will not yield
an accurate projection.  That is, you do not want to update the
election results until you have heard from all precincts.

The following naive (unsynchronized) thread update its Dvotes and Rvotes
values at random intervals.
*/

class precinctPoll implements Runnable
{
    int maxvotes;
    public int Dvotes = 0;   // votes for democrat
    public int Rvotes = 0;   // votes for republican
    int interval;            // delay interval

    public precinctPoll(int m) 
     { maxvotes=m;
       interval = (int)(Math.random()*10)+1; // sleep 1-10secs.
     }

    public void run()
    {
      try 
      {
	  while (Dvotes+Rvotes < maxvotes)
	  {
	      Thread.sleep(interval);
	      int dv = (int)(Math.random()*1001);
	      Dvotes += dv;
	      Rvotes += (1000-dv);
	  }
      }
      catch (Exception e) {System.out.println(e);}
    }

}

/*
For this problem of the assignment, assume you have 10 precinctPolls:

for(int i=0;i<10;i++) new Thread(new precinctPoll(100000)).start();

You want to update the total votes from all precincts EVERY TIME ALL
TEN PRECINCTS HAVE UPDATED THEIR RESULTS.  Modify the program as
necessary.  Make a simulation that clearly demonstrates
synchronization.  Use the "plaingui" windows for output from different
threads (but don't overuse it).
*/