Homework 10

22C:116, Fall 1997

Due Monday Nov. 17, 1997, in class

Background A user-level thread package for UNIX might begin with a call to the following routine:

	(void) thsetup(int n; (void) *p(); int s)
	{
		int i;
		thheapinit();
		thschedinit();
		thcreate(p, s);
		for (i = 1; i < n; i++) {
			if (fork() != 0) { /* child */
				thdispatch();
			}
		}
		thdispatch();
	}

This converts the parent process into n parallel processes all running thdispatch9(), a routine that takes ready threads off the thread ready list and runs them. Prior to this, this routine initializes the shared heap (the only memory area shared by the n parallel processes) and initializes the thread ready list before creating a single thread running the function p, with a stack of size s. New threads are created by the following routine:

	(void) thcreate((void) *p(); int s);

This creates and schedules one thread in the thread ready list. This thread will execute the code in function p, using a stack of size s bytes to execute that code.

The following additional thread scheduling and synchronization operations are in our elementary UNIX-based user-level thread package:

	(thsem *) thseminit();
		-- create and return a pointer to a thread-semaphore
		-- in the shared heap
	(void) thwait(thesem s);
		-- wait on a thread-semaphore
	(void) thsignal(thesem s);
		-- signal on a thread-semaphore
	(void) thexit(thesem s);
		-- exit on a thread-semaphore
	(void *) thmalloc(n);
		-- allocate n bytes of shared heap
	(void *) thfree(void * p);
		-- deallocate a block of shared heap

Explain why thmalloc() and thfree() must be used instead of the standard C malloc() and free() primitives or the standard C++ object creation primitives.
Explain why thheapinit() was called prior to thcreate() inside thsetup().
Explain why the initial thread created by thsetup could not simply be the original main program started by the user? That is, why couldn't the thread package have been written to allow a main program like this:
```
	...
	thsetup(4);  -- 4-processes will execute my threads
	thseminit(s);
	thcreate(x);
	thcreate(y);
	thcreate(z);
	...
	thwait(s)
	...
```
What scope rules apply to our system? That is, what variables are useful inside code running in the thread package. Is it safe to use global variables for anything? How can threads communicate?
Hint: There is an extremely serious problem with this proposed thread package that makes it entirely useless, as proposed here!
Propose (without pseudocode) an implementation of the following routines for use within the thread package:
- The type thfd (a thread file descriptor)
- The routine thopen (opens a thread file descriptor)
- The routine thclose (closes a thread file descriptor)
- The routine thread (read using a thread file descriptor)
Hint: This is hard!
Consider a system with 16 CPUs sharing access to a single main memory and running a UNIX-like operating system that supports threads at either the user or kernel level. Explain why many observers of such systems would not consider load balancing to be a problem on such systems, while others would say that this system has a very active and effective load balancing algorithm.