Final Preparation

22C:116, Spring 1995

Douglas W. Jones

The Question: Amoeba implements kernel threads. Why would user-level threads provide no benefit on Amoeba?
Background: Consider this piece of C code from the UNIX-hater's Web page:
```
#include 

main()
{
  printf("%d\n",
         foo() + (foo()<<1) + (foo()<<2) + (foo()<<3)
        );
}

foo()
{
  return(fork() ? 1 : 0);
}
```
Consider: the following questions, also from the UNIX-hater's Web page: ``Without using anything but the calculator hanging off your belt, your VI quick reference card, and the LCD alarm chronograph mechanical pencil in your plastic pocket reinforce-omatic, describe in minute detail the output of this program. Expound in depth on the cultural and historical traditions behind every race condition involved, including insightful commentary on the personality quirks and religious practices of the parties responsible for each kernel bug you refer to in your explanation. Make sure to mention every operating system release in which your comments apply. Be concise and to the point. You may not blame it on the compiler. For extra credit, replace the fork() with vfork().''
Hint: Consider violating the rules and compiling and running this code. From one run to the next, it produces wildly different outputs!
Background: Capability systems have been implemented in many ways, ranging from hardware support for capability based addressing to purely software based systems with capabilities used to address messages. While there has been fairly extensive study of systems that allow communication capabilties to be embedded as bit patterns in user data, little effort has been put into allowing memory capabilities, for example, capabilities for memory pages, to be freely embedded as bit patterns in user data.
Consider a system with a paged address space, where the operating system treats the virtual address translation map of each process as a capability list. Without loss of security, could the system turn over a capability for a page, as a bit pattern, to a user process?
For example, consider implementing the function getcap(va) that returns a safely protected bit pattern representing the capability for the page at virtual address va in the caller's address space, and putcap(va,cap) that takes a bit pattern cap and installs the corresponding page in the caller's virtual address space at va.
Finally, given that secure implementations of getcap and putcap are possible, what is the effect on the rest of the system of prividing them to users?
Background: Network protocols, particularly client-server protocols, play a central role in distributed system design. Mutual exclusion is a universal problem in systems that embody any form of parallelism.
Consider the problem of implementing locking in a distributed file system. Logically, a file lock is a semaphore associated with a file. When the file is locked, other users attempting to lock the file are blocked. When the file is later unlocked, one of the users blocked on that file is unblocked.
Background: Consider the problem of implementing a timed wait for a semaphore to be signalled. Conceptually, the user of such a service wants to wait for either a signal on the semaphore or for the passage of some time interval t. When one or the other occurs, the user process should continue, and the user process should receive an indication of which occurred.
Typically, semaphores offer the operations P(sem) and V(sem), and a timer service might be exposed to the user as a service delay(t,sem) that signals the indicated semaphore after the indicated time interval has passed.
Consider the problem of implementing a timed wait. What is wrong with the following implementation:
```
timed_wait(sem,t)
  begin
    delay(t,sem)
    P(sem)
  end
```
Can you fix the problem using the primitives provided? Can you fix it using multiple threads?