bogosort (was Re: Re: [RFC][PATCH -mm 5/6] Freezer: Use freezing timeout more efficiently)

Pavel Machek
2007-07-10T21:13:20Z

Hi!

> > > No, we can't do that:
> > >
> > > Imagine we have single uninterruptible task that waits for disk. It
> > > would exit uninterruptible state in 10msec, *but* you give up and
> > > unfreeze all. Now, another task goes uninterruptible waiting for
> > > disk and situation repeats. Livelock.
> >
> > For how many times would that have to repeat before 30s of timeout expires?
> >
> > Sorry, but I don't buy this argument. :-)
> >
> > > Yes, this might play with races in interresting ways and help fuse,
> > > but we do not want the livelock in the first place.
> >
> > I think that the "livelock" will never happen.
> >
> > Besides, we can add another timeout for breaking the loop from a "locked up"
> > state.
>
> Actually I like this idea. :-)
>
> I have updated the patch to use the additional timeout, please have a look
> (below).

Yes, this one could actually work... _really_ inefficiently.

Task here is to sort the tasks, and freeze them in such order that
freezing works, right? Yep, we do not know the dependencies
explicitely... but what you invented is bogosort.

Yes, it does increase chance that freezing succeeds, but I do not
think increase of chance is worth having bogosort in tree :-).

Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html