Assignment 3, Solutions

http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/

The Problem: As announced last week, you are to modify this thread package so that the code running in one thread can force the termination of another thread (the thread_kill operator). You will have to add some kind of thread handle to the interface, and the thread_launch operator will return such a handle.

Note that you may wish to seek a minimum effort path to a solution instead of a computationally optimal solution. If you examine the alternatives to the solution of this problem, you will find that some involve writing more code, or more code disbursed throughout the pre-existing thread package, while others involve less code or code that is concentrated in one part of the package.

For maximum credit: Your thread handle should be opaque, so that details of the thread implementation are not revealed to the user in the header file that gives the user interface. There are several ways to do this, varying in difficulty.

What to turn in: Turn in clearly written correct code. This should include the new header file for the thread package, plus those parts of the thread package you changed, with enough context to be easy to read, but without functions that remained unchanged. Your additions to the code should blend comfortably into the style of the existing code, yet should be easy to identify -- this may be done by embedded comments or by highlighting those parts you added or changed. Your code should work, but you'll only be asked to demonstrate this if it isn't obvious that your solution is correct. Note that this problem, in total, is worth 3 of the 5 points for this assignment.

	#### new declarations in header file ####

	/* no details are given here, thread handles are pointers to this */
	struct thread;

	void thread_kill( struct thread * t );
	/* call this to kill thread t, which must be ready or waiting */

	#### changes to header file ####

	struct thread * thread_launch( int size, void (* proc)(int), int param );
	/* call this to launch proc(param) as a thread */
	/* may be called from main or from any thread */
	/* returns hasndle for thread, useful as a parameter to thread_kill */
	{
		... -- body of thread_launch unchanged
		return t;
	}

	#### changes to thread implementation ####

	struct thread_queue {
		/* thread queues are doubly linked;
		   items in the queue must have a thread-queue as their
		   first component; the queue itself is represented by
		   a free standing thread_queue, where next points to the
		   head thread and back points to the tail thread */
		struct thread_queue * next;
		struct thread_queue * back;
	}

	struct thread {
		struct thread_queue links; /* used to link threads into queues */
		...
	}

	static void thread_queue_init( struct thread_queue * q )
	/* initialize q */
	{
		q->next = q;
		q->back = q;
	}
	
	static void thread_enqueue( struct thread * t, struct thread_queue * q )
	/* enqueue t on q */
	{
		t->links.next = q;
		t->links.back = q->back;

		/* the next two lines are type unsafe but they work
                   because the pointer to the thread also points to
                   the first field of the thread, the thread_queue element */
		q->back->next = (struct thread_queue *)t;
		q->back = (struct thread_queue *)t;
        }

	static struct thread * thread_dequeue( struct thread_queue * q )
	/* dequeue and return a thread from q */
	{
		if (q->next == q) { /* empty queue */
			return thread_null;
		} else {
			struct thread * t;
			/* the next line is type unsafe but it works because
			   the pointer to the thread also points to the first
			   field of the thread, the thread_queue element */
			t = (struct thread *)(q->next);
			q->next = q->next->next;
			q->next->back = q;
			return t;
		}
	}

	#### new private functions in thread implementation ####

	static void thread_unqueue( struct thread * t )
	/* remove t from the queue it is part of */
	/* illegal if t not enqueued somewhere, but no checking for this! */
	{
		struct thread_queue * nxt = t->links.next;
		struct thread_queue * bak = t->links.back;
		nxt->back = bak;
		bak->next = nxt;
	}

	#### new interface function in thread implementation ####

	void thread_kill( struct thread * t );
	/* call this to kill thread t, which must be ready or waiting */
	{
		thread_unqueue( t );
		mem_to_free = (void *)t;
		_longjmp( go_free_it, 1 );
	}

Note, we could have merged the code for thread_kill and thread_unqueue given above into one function, but as coded, the thread_unqueue function deals purely with the thread_queue abstraction, while the thread_kill routine deals with the semantics of the thread package; it seems better to keep these two issues separated.

Background: The Berkeley Timesharing System was implemented on the SDS 940 computer, made by Scientific Data Systems, a company that Xerox later bought, renamed Xerox Data Systems, and ran into the ground. The SDS 9x0 family of machines had 24-bit words with an 8-bit opcode, 2 bits of address mode, and 14 bits of physical address. The 940, introduced in 1966, was basically a 930 with an added memory management unit. This took the 14-bit address and broke it into a 3-bit page number and an 11-bit word-in-page field. Note that this machine had no byte addressing. Software could use either 3 8-bit bytes per word or 4 6-bit bytes per word, depending on the character set needed!

The Berkeley Timesharing System was, incidentally, commercialized by ComShare Inc and by Tymshare Inc. GTE bought the latter, which became the basis of GTE's network division. ComShare is still a thriving company.

In the notes describing the Berkeley Timesharing System, it is stated that this system allowed each user to have an address space of 64 pages, with any number of threads sharing this address space, where each thread could, at any instant, address only some subset of the user's pages.

A Problem: Explain why the hardware leads to this constraint!

Each thread can only address one of 8 pages because the virtual address only has a 3-bit page field.

Suggest the data structures appropriate inside the operating system for representing the address space of a user and the address spaces of that user's threads.

The virtual address space of a user would be represented by a 64-entry page table, and the virtual address space of each thread belonging to the user would be represented by an 8-entry page table. It would be reasonable to have each entry in this little table be a 6-bit index into the user's table. When the thread is scheduled, the 8-entry page table inside the MMU can be computed by extracting 8 of the 64 entries from the user's page table, as selected by the 8-entry table of the thread being scheduled.

Suggest how the user might go about specifying the shape of the address space to be used by a thread when that thread is launched. (None of this need be based on the real system as it was actually developed, it need only be plausable.)

The easiest solution, and incidentally, the one actually used, was to have the user pass the entire 8-entry by 6-bit page table for the thread as a parameter to the thread launch routine.

A Problem: Do problem 12 on page 154 of the text.

A single-threaded web server using the standard C or C++ interface to the file system will block whenever it reads a part of a web page from the disk, so it will never overlap network service with disk I/O. A multithreaded server could handle network interfacing to one or more clients during the time that disk I/O is being done on behalf of another client.

If the kernel offers a complete suite of nonblocking I/O primitives, it is possible, in theory, to construct a pure event-driven single-threaded finite-state server that equals the performance of the multithreaded server. Generally, programming for event-driven programs is far more difficult than programming for multithreaded applications!