[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: On hierarchy
Jonathan S. Shapiro
Re: On hierarchy
Fri, 21 Oct 2005 16:26:06 -0400
On Fri, 2005-10-21 at 20:22 +0200, Udo A. Steinberg wrote:
> On Fri, 21 Oct 2005 10:43:33 -0400 Jonathan S. Shapiro (JSS) wrote:
> JSS> 1. System calls are only preemptable between well-defined "units of
> JSS> operation".
> In order to use compatible terminology, please write "preemptible" ;)
Happily. My splling is terribull. Actually, I believe that the correct
spelling in this case is with an "a".
> JSS> 2. Because they are non-preemptable, units of operation must complete in
> JSS> a small *constant* number of steps.
> JSS> => In my *opinion*, the L4 string bound is too large to satisfy
> JSS> this requirement, but this is definitely a matter of opinion
> JSS> and preference. In effect, I want a smaller constant bound.
> Note that there exist at least one fully preemptible L4 microkernel, namely
> Fiasco, where your concern is a non-issue.
Yes. I was aware of this. There are two cases in the API that I do not
understand how to implement correctly if operations are preemptable. Can
you explain them:
1. Two threads exist in a task. One performs an unmap from a location
while the other (simultaneously) executes a loop performing a map. Is
the unmap guaranteed to terminate in any predictable amount of time?
[You may have already answered this below]
2. One thread performs a long unmap that is preempted after making
partial progress. Because it is preempted, the scheduler permits other
threads to run. In particular, a debugger thread performs a "stop"
operation on the thread that is performing the UNMAP. I do not see any
outcome in which this is possible within the requirements I have stated
without leaving the system overall in an inconsistent state.
> JSS> 4. Locks may not be held across preemptions. This is necessary to avoid
> JSS> priority inversion.
> Not quite. Priority inversion can also be avoided by using helping mechanisms
> such that higher-priority threads help a low-priority lock holder out of its
> critical section. There's a whole set of formulas for such things in common
> real-time literature.
Unfortunately, none of these mechanisms work in the general case -- a
discussion we should take up separately. The problem is that there is no
way in general to know which thread to escalate if the IPC mechanism is
general-purpose. Both the L4 and EROS IPC mechanisms are general
Setting this aside, long-held locks also create opportunities for kernel
deadlock that we would prefer to avoid, and they make analysis of kernel
correctness about two orders of magnitude harder. I don't know if formal
analysis is an active objective for L4.sec, but for Coyotos this is
definitely a concern.
> JSS> 2. The UNMAP operation requires an "all children" visit. The question
> JSS> is: can this operation be divided successfully into constant-bounded
> JSS> units of operation? The answer appears to me to be "no".
> You can descend down the mapping tree starting at the root node, marking each
> node "unmapped" as you come across it. Such marked nodes don't allow creation
> of any subnodes underneath them, which ensures the mapping tree does not grow
> in such branches. For each leaf node reached, you remove the node, remove the
> PTE and flush the relevant TLB entry. The per-node time overhead is bounded
> and you can be preempted in between such node operations.
> Granted, unmap operations can take a long time to complete for the unmapper,
> depending on the size of the mapping tree for the unmapped page frame.
If I understand you, this is the case where the unmap is a total unmap:
the PTE's are going to invalid. I had in mind a different algorithm, but
I agree that yours works. Also, I *think* that your solution resolves my
"map during unmap" question.
The case that I do not currently understand how to do is the *partial*
unmap -- e.g. taking away write permission while leaving read
permission. For this case, I think you will need to add some form of
index to keep track of progress. Is there a way around this?
Do the performance measurements that have been published for the map
operation include this locking, or are they measuring an incorrect
Finally this strategy violates the long-held locks requirement. I
recognize that this requirement needs further discussion, and that other
design rules may be feasible here.
Re: On hierarchy, Espen Skoglund, 2005/10/21
Re: On hierarchy, ness, 2005/10/21
Re: On hierarchy, Jonathan S. Shapiro, 2005/10/23