Dr. Volkmar Uhlig, Dr. Kevin Elphinstone

Abstract:

Recent implementations of the Recursive Virtual Address Space Model have shown problematic and undesired behavior such as:
- long interrupt latencies
- unbounded priority inversion, or
- the demand for complex helping schemes to avoid both.

We were able to show, that those problems were inherent to non-post-order traversal of the mapping database tree upon unmap. By combining:
- preemptable post-order traversal on unmap,
- roll forward in combination with scheduler-conscious locking techniques, and
- an efficient way to track the restart points of preempted operations: the token based preempted thread list
we were able to eliminate long interrupt latencies and unbounded priority inversion without having to rely on helping techniques. We were able to preserve performance for the mapping case and add an overhead of only 12.2% to the unmap case while achieving good preemptability.

BibTex:

@diplomathesis{voelp02recvirtaddrspace,
  author = {Marcus Voelp},
  title = {Design and Implementation of the Recursive Virtual Address Space Model for Small Scale Multiprocessor Systems},
  type = {Diploma Thesis},
  address = {System Architecture Group, University of Karlsruhe, Germany},
  month = sep,
  year = 2002,
  url = {http://i30www.ira.uka.de/teaching/theses/pasttheses/}
}