Assignment 11, Solutions

Part of the homework for 22C:50, Summer 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Background: Consider a progamming language that is basically like Java, C or C++, except that it supports coroutines with explicit coroutine instantiation and calls. Each coroutine instance may call functions, or methods on its local stack. The syntax for resuming a coroutine instance is similar to the syntax for a function call. Every time you resume an instance of a coroutine that was declared with parameters, you must pass those parameters. Here is an example of this language:
```
	coroutine A( instance i, instance j )
	{
		output( "-" );
		i( j, self );
		output( "|" );
		j( i, i );
		exit()
	}
	instance x = instantiate(A);
	instance y = instantiate(A);
	instance z = instantiate(A);
	x( y, z );
```
A Question: What output would you expect from this program up to the point it calls exit()?

---|||
Background: Here is a fragment of the code for the scheduler of a thread package written in C (this is lifted from a real thread package!):
```
	void thread_relinquish()
	/* call this within a thread to allow scheduling of a new thread */
	{
		if (_setjmp( current->state ) == 0) {
			thread_enqueue( current, &readylist );
			current = thread_dequeue( &readylist );
			_longjmp( current->state, 1 );
		}
	}

	void thread_exit()
	/* call this within a thread to terminate that thread */
	{
		free( current );

		/* ? */

		/* now, get the next thread to run */
		current = thread_dequeue( &readylist );
		_longjmp( current->state, 1 );
	}

	void thread_signal( struct thread_semaphore * s )
	/* call this within a thread to signal a semaphore */
	{
		struct thread * t = thread_dequeue( &s->queue );
		if (t == thread_null) {
			s->count++;
		} else {
			thread_enqueue( t, &readylist );
		}
	}
```
Part a) The above code is incorrect! Specifically, it does nothing to handle the termination of the final thread in an application. Suggest an appropriate rewrite to the above code to deal with this situation.

The problem is, it doesn't check for null being returned by thread_dequeue in thread_exit().
```
	void thread_exit()
	/* call this within a thread to terminate that thread */
	{
		free( current );

		/* ? */

		/* now, get the next thread to run */
		current = thread_dequeue( >readylist );
		if ( current == thread_null ) exit();
		_longjmp( current->state, 1 );
	}
```
Part b) The above code fragment contains enough pieces that you should be able to construct the correct code for the thread_wait operation on a thread_semaphore without really understanding that awful stuff about setjmp and longjmp. Give your best guess of the code for the thread_signal function.
```
	thread_wait( struct thread_semaphore * s )
	{
		if (s->count > 0) {
			s->count--;
		} else {
			if (_setjmp( current->state ) == 0) {
				thread_enqueue( current, &s->queue );
				current = thread_dequeue( &readylist );
				_longjmp( current->state, 1 );
			}
		}
	}
```
Part c) There is interesting problem in the code for thread_relinquish() at the point marked with a question mark comment. Where is the current activaton record at that time? Suppose you ran this code on a computer where the heap manager promptly filled the deallocated block of memory with zeros as part of the free() function. What would happen? (this asks you to combine everything you know about calling sequences, activation records and threads! Fun?)

The question mark is in thread_exit(). At that point, the current stack has been passed to free() and the heap manager might have written zeros over that entire area, including the current activation record. Our only hope is that all the information we need to continue was stored in registers that were restored by the return from the heap manager. If that wasn't done, entirely unpredictable execution will follow at this point.
Indeed, it did on some machines, while the code worked perfectly well on others. Fixing this was an interesting programming exercise!