Objects which Block

This note broaches whether more than one CPU should be allowed to obey code from the behavior of one object at the same time. Fundamental mechanisms prevent this when the answer is no. It proposes a biased answer ‘no’. The bias is from Keykos with this restriction. I consider here the ramifications for one sort of object with which I have experience. This sort is complex, yet perhaps not complex enough.

This is the exemplar code. As I go thru the ramifications I will of necessity be describing the multiprocess solution within Keykos. There may be other ways to exclude MP within an OB with other advantages. I don’t know.

The B-Tree algorithm, as coded, is not suitable for MP. Even the external semantics are unsuitable. If we had a large number of elements to add to the empty set and simple arithmetic suggested that N processors should apply themselves to this we could create N empty sets, launch N tasks. Each task creates an empty set, adds its portion of elements and when they are finished we take the union of the N resulting abstract sets. This imposes a log(n) cost which may be tolerable. This leaves the semantics of Set unchanged!