[coyotos-dev] Sleep for interval

[William Leslie]

On 10/18/07, Pierre THIERRY <nowhere.man at levallois.eu.org> wrote:
>
> Scribit William Leslie dies 05/10/2007 hora 01:19:
> > assume you have two lists, ordered in time. One is for relative waits,
> > the other for absolute. Check the absolute list- if something is
> > expired, take it off the sleep queue. Place the previously running
> > process at the end of the (relative) list [O(1) if you maintain a
> > pointer there], and pop a process of the bottom of the list. That
> > whole thing is O(1) in time.
>
> Only if you assume that only one element can be expired. But in the
> worst case, the whole absolute list is expired, and dealing with this is
> O(n) WRT the number of elements in the list.


Can you think of any time this will actually happen?  The only cases I
have thought of for mass-expiry are multiprocessing and killing a
large number of processes. If the list is implemented using the per-
process state, ie, the pointer to the next process, the latter is cleaned
up by killing anyway. The former becomes a bit of a problem with APIC
as far as I understand it, and would welcome more insight on that.

Also, inserting in a simple ordered list is O(n) also, O(log n) if you
> use something more fit to the job, like a heap.


Which is what Jonathan suggested, more or less. I bought up the
problem of insertion on #Hurd. fmg eventually got me thinking that
it is a bad idea to have rt and regular processes in the same list
anyway, as they really need to be treated separately when deciding
where to insert.

In other words, we can't have processes that are neither sleeping
nor real-time getting in the way of scheduling real time processes
or sticking waiting processes back into the scheduling queue.
Also, we need to insert in these cases. Both of these should be in
a heap.

For regular waiting processes, however, insertion might not be a
problem. But this is algorithm-specific, and getting the rt and
short-sleep processes out of that list makes the whole implemen-
tation simpler. We can even keep O(1) process dispatch for most
cases if we keep data on the first element in the heap.

-William Leslie
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/coyotos-dev/attachments/20071019/3aa897c0/attachment.html