Memo has been implemented in C in several versions on an Encore shared-memory multiprocessor using the Encore's parallel programming library and using a package that simulates conventional distributed memory parallel programming.
The two shared memory versions both allocate memos in shared memory and both use a hash table to look up folders. One version locks the entire memo package to achieve mutual exclusion; the other locks individual hash table buckets.
A memo_get is handled by linking a "get structure" in a folder telling which process to deliver the memo to. Memo_get will wait for one to be delivered. Memo_get_skip will check to see if a memo was found while the get structure was being installed. Memo_alt is handled like memo_get: it simply installs get structures in the listed folders. Memo_alt_skip and memo_strict_alt_skip are identical; they install get structures in all named folders and check if a memo was latched during the installation.
All the three distributed memory versions have used servers to handle the directory of folders. The simplest distributed implementation uses a single server; the Memo procedures are replaced with stubs that pass messages to the server to invoke the operations.
Two distributed memory implementations use multiple servers. Folder names are hashed to determine which server is handling the folder. For both, the implementation of the varieties of memo_alt is difficult. For memo_alt itself, messages are sent to all servers containing any of the folders listed. Servers that find memos must latch one of the memos and respond. It must not remove the memo from its folder unless its memo is the one chosen - other servers can also have memos. A latched memo may delay other get_skip operations: if it is not chosen, the memo will be logically present to a get_skip or alt_skip, even though it cannot be immediately returned.
The implementation of memo_strict_alt_skip is particularly problematic; before it can return NULL, the system has to guarantee that there is an instant of time across the entire machine during which no memos are present in any of the folders. In one implementation, the process executing the strict_alt_skip potentially communicates with the servers three times: the first time to install the get structures; the second time, after the servers respond, to remove the get structures; and the third time to accept one latched memo and unlatch the others. (It can communicate only twice if the first communication finds and latches a memo immediately.)
In the other multi-server distributed memory implementation, the servers involved chain together, locking out other operations, until the strict_alt_skip is complete.
This page last updated 09/30/97