This assignment is Due on:

		Day:	Wednesday, May 6, 1998
		Time:	before 6:00 PM

WARNINGS: TURN IN THIS ASSIGNMENT ELECTRONICALLY USING "turnin".  LATE 
ASSIGNMENTS WILL NOT BE ACCEPTED.
----------------------------------------------------------------------

The purpose of this homework is to reinforce explanation of the
following concurrency concepts:

			threads
			atomic instructions
			mutual exclusion
			race conditions
			critical section

Check 

    http://www.sun.com/workshop/threads/Berg-Lewis/examples.html

for examples on threads.

The man pages on acme also contain information.

We will be using Solaris threads, as opposed to POSIX threads which are
very similar.

To compile a program threads.c that uses the thread library, you need to
do: cc -lthread -o threads threads.c,
just as you do cc -lm foo foo.c for a program needing math libraries.

Read Bacon for the concurrency issues.


Use the following program:

    /*************************************************/
    /* to compile: cc -o threads threads.c -lthread  */
    /* to run:  threads                              */
    /*************************************************/

    #define _REENTRANT
    #include <stdio.h>
    #include <thread.h>
    #include <stdlib.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <unistd.h>
    #include <errno.h>

    #define THR_NUM	4

    void *thread( void * );	/* Prototyping the thread function */

    int counter = 0;

    mutex_t counterlock;

    /* We will use the above two later */

    int 
    main( void )
    {

	thread_t        thr[ THR_NUM ];
	int             i;

	/*
	 * set the thread concurrency to THR_NUM+1 so the threads (main too)
	 * can run concurrently
	 */

	thr_setconcurrency( THR_NUM + 1 );

	/* create the threads */
	for( i = 0; i < THR_NUM; i++ )
	    if(thr_create( NULL, 0, thread, ( void * )i, NULL, thr + i ) != 0)
	    {
		fprintf( stderr, "Error: can't create thread.\n" );
		exit( EXIT_FAILURE );
	    }
	/* check for error if can't create */

	/* wait for the threads to finish */
	for( i = 0; i < THR_NUM; i++ )
	    thr_join( thr[ i ], 0, NULL );

	printf( "Value of counter: %d\n", counter );
	/* ignore this for right now */

	/* exit the program */
	return EXIT_SUCCESS;
    }


    /* The thread */
    void *
    thread( void *arg )
    {
	int id = ( int )arg;
	int i;

	printf( "Thread #%d, PID=%d\n", id, getpid( ) );
	/* Print the thread's PID */

	thr_yield( );

	for( i = 0; i < 10; i++ )
	{
	    printf( "%d\n", i * THR_NUM + id );
	    thr_yield( );
	}

	/* exit the thread */
	thr_exit( NULL );
    }

     -----------------------Start Answer Here-----------------------
[p0]
5.0 points

	Discuss the difference between forking processes and creating
	threads.  What does the getpid() in the above program tell you?

     ------------------------End Answer Here------------------------
Here is some rough pseudocode.

    int foo;

    int
    main( void )
    {
	...

	fork()
	if child then
	    foo = 10
	else
	if parent then
	    foo = 20

	print foo
    }

The resulting output is that 10 and 20 are printed, in whatever order.

Now suppose we have the following pseudocode:

    int foo;

    void
    thread1( void * )
    {
	foo = 10;
	print foo;
    }

    void
    thread2( void * )
    {
	foo = 20;
	print foo;
    }

    int
    main( void )
    { 
	...
	thrcreate( thread1 );
	thrcreate( thread2 );
	...
    }

Sometimes we will print 10, 10.  Other times 10, 20.  Other times 20,
10.  Other times 20, 20.

     -----------------------Start Answer Here-----------------------
[p1]
8.0 points

	Discuss why the printing happens as such in the above two
	examples.

     ------------------------End Answer Here------------------------
In the above program we use thr_yield() to have one thread
voluntarily yield its execution to another thread.  This is in
contrast to preemptive scheduling, in which a process might be forced
to stop running, due to end of time slice, etc.

     -----------------------Start Answer Here-----------------------
[p2]
4.0 points

	In the above program, explain why the numbers 0 to 39 are
	printed out, and explain why the order is somewhat scrambled.

     ------------------------End Answer Here------------------------
Now use the following function instead in your program:

    /* The thread */
    void *
    thread( void *arg )
    {
	int             id = ( int )arg;
	int             i;

	for( i = 0; i < 10000; i++ )
	{
	    /*
	     * Note that we have two "odd" threads and
	     * two even threads, so it seems that each 
	     * even thread is adding a total of 10000, 
	     * and each odd thread is subtracting that
	     * much.  So it seems that we should break 
	     * even....
	     * But we shall see....
	     */ 
	    if (id % 2 == 0)
		counter++;
	    else
		counter--;
	}

	/* exit the thread */
	thr_exit( NULL );
    }

Read through the above code and try to understand what it does.
After replacing the old thread function with this one, recompile and
run your program several times.  Note that counter is a different
value after each time you run it.


     -----------------------Start Answer Here-----------------------
[p3]
5.0 points

	A statement such as foo = foo + 1 is equivalent to the
	following operations at the machine level:

			get	old_foo
			add	1
			save	new_foo

	Using this information, explain why we were getting all the
	different numbers from running the program multiple times.
	(Hint - what if two threads are executing the above instructions
	 at nearly the same time?)

     ------------------------End Answer Here------------------------
Now use the following function instead:

    /* The thread */
    void *
    thread( void *arg )
    {
	int             id = ( int )arg;
	int             i;

	for( i = 0; i < 10000; i++ )
	{
	    mutex_lock( &counterlock );
	    if( id % 2 == 0 ) 
		counter++;
	    else
		counter--;
	    mutex_unlock( &counterlock );
	}
	/* exit the thread */
	thr_exit( NULL );
    }


     -----------------------Start Answer Here-----------------------
[p4]
5.0 points

	Compile the program and run it several times.  What is the
	output?  Explain why the output is consistently 0.

     ------------------------End Answer Here------------------------
Now consider this:

    /* The thread */
    void  *
    thread( void *arg )
    {
        int             id = ( int )arg;
        int             i, j;

	for( i = 0; i < 10000; i++ )
	{

	    while( id % 4 != flag )
		/* empty loop */;

	    /*  Critical Section goes here */

	    flag = ( flag + 1 ) % 4;
	}
    }  

     -----------------------Start Answer Here-----------------------
[p5]
6.0 points

	Does this solve the critical section problem (i.e. are the
	following conditions met)?

	(Assume flag is initialized to 0 and only 4 threads)

	(a) Mutual exclusion in critical section is insured.

	(b) If no threads are in critical section, then choosing a
	    new thread to enter critical section can not be postponed
	    indefinitely.

	(c) There must be a bound for the number of times other
	    threads can enter their critical sections before a given
	    thread can enter its critical section.

	Explain your answer.

     ------------------------End Answer Here------------------------

Entering a critical section can be controlled safely by the following:
(for the sake of this problem, it may help to think in terms of a 
 client/server configuration)

You can assume that mutex_lock/unlock will be handled through the server.

    mutex_lock();
    if (server says resources available) 
    {
	tell server resources are in use
	use resources;
	tell server resources are available
    }
    mutex_unlock();

An alternative is the following:

    while (last update says resources not available)
	wait;
    mutex_lock();
    while (last update says resources not available)
	wait;
    broadcast to all clients that resources are in use;  
    mutex_unlock();
    use resources;
    broadcast to all clients that resources are available;


     -----------------------Start Answer Here-----------------------
[p6]
8.0 points

Compare and contrast these two different methods.  Do they both guarrantee
mutual exclusion?  How efficient are they?

     ------------------------End Answer Here------------------------

Now let's analyze a concurrency problem.

Imagine a system of single-lane one-way streets (no passing) looking like
the following:

     |  |  |      |  A  |
     |  V  |      |  |  |
------     --------     -------
<-          <---          <-
------  |  --------  A  -------
     |  |  |      |  |  |
------  V  --------  |  -------
->          --->          ->
------     --------     -------
     |  |  |      |  A  |
     |  V  |      |  |  |

The following code simulates driving along these streets:




    /*************************************************/
    /* to compile: cc -o traffic traffic.c -lthread  */
    /*************************************************/

    #define _REENTRANT 
    #include <stdio.h>
    #include <thread.h>
    #include <stdlib.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <unistd.h>
    #include <errno.h>

    #define NUM_CARS	 100

    #define FIRST_INTER(dir) ( ((dir)+1) % 4 )

    #define SECOND_INTER(dir) (dir)	

    enum directions { NORTH, EAST, SOUTH, WEST };

    enum intersection_loc { NE, SE, SW, NW };

    enum state { VACANT, OCCUPIED };

    static char *dirstr[] = { "NORTH", "EAST", "SOUTH", "WEST" };

    static char *interstr[] = { "NE", "SE", "SW", "NW" };

    static int intersections[4];

    static int between_intersec[4];

    static void *car( void * );   /* Prototyping the thread function */

    static mutex_t lock, done; /* for critical sections */

    static int numdone;

    int 
    main( void )
    {

	thread_t        thr[ NUM_CARS ];
	int             i;

	/*
	 * set the thread concurrency to THR_NUM+1 so the threads (main too)
	 * can run concurrently
	 */

	thr_setconcurrency( 4 + 1 );

	/* create the threads */
	for( i = 0; i < NUM_CARS; i++ )
	    if( thr_create( NULL, 0, car, ( void * )( i % 4 ), 0, 
		thr + i) != 0)
	    {
		fprintf( stderr, "Error: can't create thread.\n" );
		exit( EXIT_FAILURE );
	    }
	/* check for error if can't create */


        /* This is kinda ugly.  I would prefer a nicer cleanup, 
	   but it is guarranteed to stop any deadlock... */	

        (void)sleep(10);

        if (numdone < NUM_CARS) {        
        printf("Probably deadlock.\n");
        raise(SIGKILL); /* kill itself */
	}
	/* exit the program */
	printf("NO DEADLOCK!\n");
       return EXIT_SUCCESS; 
    }


    /* The thread */
    static void *
    car( void *arg )
    {
	int dir = (int) arg;
        int inter;
        int i, cars;

	/* Trying to enter first intersection */

        inter = FIRST_INTER(dir);
	while(intersections[inter] == OCCUPIED)
          thr_yield(); /* let the other threads try to drive out */ 
	intersections[inter] = OCCUPIED;
	printf("Driving %s, reached %s intersection.\n", dirstr[dir],
		interstr[inter]);          
        thr_yield();   /* for fun */

	/* Trying to enter middle */

	while(between_intersec[dir] == OCCUPIED)
          thr_yield(); /* let the other threads try to drive out */ 
	intersections[inter] = VACANT;
	between_intersec[dir] = OCCUPIED;
        printf("Driving %s, in middle now.\n", dirstr[dir]);

	/* Trying to enter second intersection */

        inter = SECOND_INTER(dir);
	while(intersections[inter] == OCCUPIED)
          thr_yield(); /* let the other threads try to drive out */ 
	between_intersec[dir] = VACANT;
        intersections[inter] = OCCUPIED;
	printf("Driving %s, reached %s intersection.\n", dirstr[dir],
		interstr[inter]);          
	intersections[inter] = VACANT;
        thr_yield();   /* for fun */

	/* exit the thread */

	mutex_lock(&done);
        numdone++;
	printf("DONE: %d\n",numdone);
        mutex_unlock(&done);
	thr_exit( NULL );
    }



     -----------------------Start Answer Here-----------------------
[p7]
9.0 points

Now run the program.

a) Why is the simulation getting into deadlock?
   Explain the circumstances.

b) Is there any potential for a car collision?
   If so, give a circumstance.

c) The code in the thread can be summarized by:

When able to, enter first intersection.
When able to, exit first intersection and enter middle area.
When able to, exit middle area and enter second intersection.

What is the smallest subset of the above code that could be
placed in a critical section to eliminate deadlock?

     ------------------------End Answer Here------------------------