[coyotos-dev] Sleep for interval

[Pierre THIERRY]

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.

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.

Slowly,
Pierre
-- 
nowhere.man at levallois.eu.org
OpenPGP 0xD9D50D8A
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.coyotos.org/pipermail/coyotos-dev/attachments/20071017/de8d2629/attachment.bin