Assignment 2, Solutions

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

Advance Warning: You will have to add features to this thread package in next week's assignment. The code you will need to write is small, but time spent studying the thread package this week will be important preparation for next week's assignment.

Part A: What changes to the the external interface to the thread package (not the source code) would be required in order to allow code running in one thread to force the termination of another thread (the thread_kill operator)? These changes will, if implemented, result in changes and additions to the header file of the package. For this week, focus on describing the nature of the change to the specification.

Note: This question does not ask for implementation, it asks for interface specifications! This is not the place to discuss implemtation options!

First, we need to export a new type so that we can deal with thread handles. We could do this with a declaration like this:

struct thread { ... }

Second, we need to modify thread launch so it returns a thread handle. Given a declaration such as the above, the new version would be:

struct thread * thread_launch ( int size, ... );

Finally, we need the thread_kill function itself:

void thread_kill( struct thread * t );
/* given t, a thread handle, kill that thread */

Part B: If a running thread forces the termination of some other thread, this implies that the thread being killed must be either ready or waiting. What decisions made in designing the internal data structures of the thread manager, as it is currently written, make the kill operation difficult to implement. What changes would you suggest to simplify the kill operation?

As currently written, the ready list is a thread-queue object, and so is the queue of threads waiting on each semaphore. Thus, to kill a thread, we must delete it from the associated thread queue. Unfortunately, these queues are singly linked lists, so the operation of deleting an arbitrary element requires a search of the queue. Furthermore, the thread object, itself, does not contain any record of the thread manager's state of the thread, so we do not know what queue to search when given a thread to kill. Finally, there is no global record of all the queues we might want to search, so as it stands, there is insufficient information to implement the kill operation.

We can fix this by making changing the implementation of thread queues, so that queues are doubly linked. Deletion from a doubly linked list is straightforward. Alternatively, we could fix this by including, in each thread, a pointer to the thread queue in which that thread has been enqueued. This allows deletion from that queue without changing the list structure.

Part C: In examining the source code and header files for the thread package, note that the header file threads.h is not included by the implementation threads.c, and furthermore, some of the declarations in threads.h do not match the corresponding declarations in threads.c. These oddities are deliberate, and taken together, they accomplish something very useful. Explain this!

The public definition of the semaphore type hides the implementation from the user, while the private declaration, in the thread package implementaiton, shows all the details of the implementation. Because these differ, the header file cannot be included in the thread package.

Consider a system where process description records are randomly allocated in some kind of system heap, and where the process handle given to the user is simply a pointer to the process description record. If the user makes a mistake and passes a corrupted pointer to the system, the system will have great difficulty detecting this error and previnting accidental or malicious damage to system data structures when this occurs.

If the process handle given to users is an integer index into the process table, then each integer value corresponds to exactly one process description, and there is no way to deliberately or accidentally construct a handle that refers to anything that is not a process description. This protects the system from a large number of potential vulnerabilities at the cost of a fixed limit on the number of processes determined by the size of the process table.

Interrupts are requested asynchronously by devices outside the central processor, for example, by I/O completion. Traps occur as a direct consequence of instructions executed on the processor, for example, when an an illegal instruction code is encountered.