[mkc2008] Fwd: Mapping - Mapping DB

Marcus Voelp voelp at os.inf.tu-dresden.de
Tue Apr 7 09:02:40 CEST 2009

Jan Bierbaum wrote:
>> Currently, Fiasco implements such a helping lock at the page frame in
>> Sigma0 (and when splitting large pages but don't worry). Both map and
>> unmap grab this lock to modify the mapping database.
> That means in Fiasco the locked "subtree" starts right at the frame and
> not at the root node of the respective map/unmap-operation?
> My point is rather that with atomic CPU instructions the maps would
> automatically be synchronized with each other and concurrent unmaps. 
On most modern architectures you cannot implement map with a single
atomic operation. This might change with transactional memory.

> If
> maps don't care about the helping locks but instead use their own
> locking scheme couldn't that lead to problems? 
Yes, to be more precise here any single node operation has to acquire a
respective lock to make it atomic towards other single node operations.
But locking nodes won't help you to synchronize concurrent preemptible
unmaps as one unmap could remove the node at which a concurrent unmap
has to resume its operation.
> A map could for example
> try to insert new nodes in a subtree currently being deleted by a
> concurrent unmap.
Yes, that's an issue and there are various possible solutions to this:
1) don't worry, unmap will catch it (proper synchronization provided)
2) remove rights in preorder pass => map can only establish nodes with
    rights; unmap may just skip the node in its postorder traversal.
3) prevent maps on a to be unmapped subtree

To be honest, we ourselves are not sure which alternative is the best
one. I personally favor for 2 but that's more an unsubstantiated guess.

The pros and cons are however, a nice question for the exam ;) Thx.



More information about the mkc2008 mailing list