Homework 7 Solutions

22C:116, Fall 1998

1. Consider the following little C program:

   	int a;
   
   	void t( int * p, void (*f) (void *, void *) )
   	{
   		if (0 == *p) {
   			printf( "some output\n" ); /* stop here */
   		} else {
   			(*p)--;
   			(*f)( p, f );
   		}
   	}
   
   	void main()
   	{
   		a = 1;
   		t( &a, t );
   	}
   

   To work out the access matrix at the moment the output "some output" appears, we need to know what users exist. I will take the users to be the function activations, so we have the following:
   1. main() suspended at the call t( &a, t ).
   2. t1, t() called by main and suspended at the call (*f)( p, f ).
   3. t2, t() called by t and suspended at the call printf().
   The objects we will consider are the variables and functions:
   1. the global variable a.
   2. the function t().
   3. for each activation of t, t.p, the parameter p.
   4. for each activation of t, t.f, the parameter f.
   5. the function main().
   The operations allowed are the right to Call a function and the right to Access a variable or parameter. The resulting access matrix is:

      objects    a    t()  t1.p  t1.f  t2.p  t2.f  main()
              |     |     |     |     |     |     |     |
    users ____|_____|_____|_____|_____|_____|_____|_____|
              |     |     |     |     |     |     |     |
    main()    |  A  |  C  |     |     |     |     |  C  |
          ____|_____|_____|_____|_____|_____|_____|_____|
              |     |     |     |     |     |     |     |
    t1        |  A  |  C  |  A  |  A  |     |     |  C  |
          ____|_____|_____|_____|_____|_____|_____|_____|
              |     |     |     |     |     |     |     |
    t2        |  A  |  C  |     |     |  A  |  A  |  C  |
          ____|_____|_____|_____|_____|_____|_____|_____|
   

   Note that this particular solution ignores the fact that the parameter f is a pointer to a function while the parameter p is a pointer to an integer. These parameters convey no new rights in the context of this program! If, however, a pointer to a local variable was passed from one function to another, a new access right would be conveyed, and if C had local functions, so it was not the case that all functions are legally callable from all other functions, this added complexity would have to be addressed.

2. A unix kernel call uses a gate crossing mechanism to move from the user's protection domain to the kernel's domain. The return from a kernel call crosses back from the kernel to user domains, and therefore involves a second example of gate crossing. In contrast, calls to routines in the standard library involve no change of protection domain, so no gate crossing is involved.

3. Recently, two new tools have become available, one is a chip that can directly read a fingerprint when a person touches it, and the other is a software system that can scan the distinctive patterns in the iris of a person's eyes using a TV camera. These mechanisms are both potentially useful user authentication mechanisms. Neither solves any other security problem.

4. For our example thread package, why the error message "Possible deadlock" does not mean that there is certainly a deadlock because it only means that an empty ready list resulted from a thread_wait operation. It may be that the other threads have all terminated, so one thread has just blocked itself when no other thread exists to signal the blocked thread. This programming error is not a deadlock!

5. It would be desirable to add code to our thread package (with semaphores) to automatically detect all deadlocks when they occur, but this is not possible because the semaphore abstraction gives no hint about what thread might signal a particular semaphore. Therefore, it is impossible to determine what thread(s) a blocked thread is waiting for, and as a result, no deadlock graph can be constructed, except the trivial one, where we assume that each thread could potentially singal all semaphores, and therfore, if any thread is not blocked, we declare, uselessly, that it is not a deadlock.