From: Robert Dober <robert.dober@...>
Date: 2006-07-19T06:56:10+09:00
Subject: Re: [QUIZ] Negative Sleep (#87)

------=_Part_75357_3799978.1153259766438
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

I just checked rubyquiz.com for some submissions and realized that sending
my submission as tar.bz2 was, errr, not the best idea.
Maybe it would be a good idea to add a warning about it somewhere or did I
overlook it?
Anyway here is my submission again. I was doing some rather havy
synchronisation stuff which is probably unneccessary, I would appreciate any
suggestions. I have the feeling that just using Thread.critical might be
enough,otoh I would interfere with threading libraries which want to use my
sleep-.

Here ya go

Definition
==========

While sleep(n) [n > 0] assures that the calling Thread sleeps for at least n
seconds,
unless awoken by #run, sleep(m) [m < 0] assures that the calling Thread will
suffer from
insomnia for at least -m seconds, unless resting with #stop or #sleep(n) [n
> 0]

As we know sleep(n) [n > 0] returns the time really slept, sleep(m) [m < 0]
cannot easily do
such a thing as it returns immediately. But when we put ourselves out of
insomnia with Thread#stop
we can return the time we were in insomnia. Thread#stop will still return
nil if the calling thread
was not in insomnia.

Implementation
==============
Instead of rewriting the scheduler I will try to give an implementation by
using Thread
priorities.
A thread that calls sleep(m) [m < 0] will be assigned the highest priority
of all threads. It also starts
another thread, called supervisor with even higher priority. But the
supervisor just sleeps for -m
seconds before reassigning the normal priority to the calling thread.

The Thread  is in "insomnia" mode during this time span. As mentioned above
there are only two
ways to get out of this "insomnia" mode. By the timeout -m, or if the
calling thread calls sleep(n)
[n > 0] or stop.

In order to do that we have to intercept all calls to Kernel#sleep and to
methods
adjusting a Thread's priority, which are:
    * Thread#new
    * Thread#fork
    * Thread#priority=
    * Thread#stop
to get out of insomnia ourselves.

I will ignore Thread#new and Thread#fork assuming that they initialize a
Thread with priority 0.

Testing
=======

running test.rb with a parameter of >> 10**5 should give a first insight of
how it works, depending
on the speed of your machine.


Shortcomings
============
* The naming is quite trivial and might conflict with subclasses of Thread.
* The implementation is minimal, an insomnia Thread does not get back into
insomnia mode after
    a sleep(n) [n > 0] as one might assume. An insomnia thread cannot call
sleep(m) [m < 0] again
    as might be useful.
* When calling sleep before synchronizing the Thread might be interrupted
and thus the effect
    of sleep(m) [m < 0] might not be immideate (as can be seen in test2.rb).
*Synchronization is done with big guns and without optimization, the former
because
    I do not know ruby Threads well, the later because of clarity of code.

* And hopefully *you* tell me about the other ones ;).

----------------------- 8< --------------------------------------
#!/usr/bin/ruby

require 'thread'

class IllegalMonitorState < RuntimeError ; end

class BusyFlag # taken from Scott Oak's and Henry Wong's "Java Threads"
    # allows to be called again for a Thread
    # already in possession of the Flag
    def initialize
        @count     = 0
        @possessor = nil
        @mutex     = Mutex.new
        @cv        = ConditionVariable.new
    end

    def get
        @mutex.synchronize do
            while not try_get do
                @cv.wait( @mutex )
            end
        end
    end

    def free
        @mutex.synchronize do
            return unless possessing?
            @count -= 1
            return unless @count.zero?
            @possessor = nil
            @cv.signal
        end
    end

    private
    def possessing?
        Thread.current == @possessor
    end

    def try_get
        if @possessor.nil? then
            @possessor = Thread.current
            @count = 1
            return true
        end
        return false unless possessing?
        @count += 1
        true
    end

end


class Thread
    ### keep track if there is a thread in insomnia by means of a supervisor
    ### control the insomnia with a supervisor
    @@supervisor = nil
    ### time the supervisor slept
    @@time       = 0
    ### keep track of the maximum prioriy
    @@max_prio = Thread.current.priority + 1
    ### synchronizing management data
    @@lock = BusyFlag.new

    alias_method :orig_priority=, :priority=
    def priority= np
        # I do not think this needs to be protected, if a thread is
interrupted while setting the priority
        # it cannot yet run with that priority and well not interfere with
the insomnia process.
        @@max_prio = np if np > @@max_prio
        self.orig_priority = np
    end

    class << self

        alias_method :orig_stop, :stop

        def insomnia?; @@supervisor end
        def max_prio; @@max_prio end
        def last_time; @@time end

        def lock; @@lock; end

        def set_insomnia n
            synchronize do
                old_prio = Thread.current.priority
                Thread.current.orig_priority = @@max_prio + 1
                @@supervisor = Thread.new( Thread.current ) {
                    |t|
                    Thread.current.orig_priority = @@max_prio + 2
                    @@time = orig_sleep n
                    t.orig_priority = old_prio
                }
                @@supervisor = nil
            end
        end

        def stop_insomnia
            @@supervisor.run if @@supervisor
        end

        def stop
            synchronize do
                stop_insomnia
                orig_stop
                @@time
            end
        end

        def synchronize( &block )
            begin
                @@lock.get
                block.call
            ensure
                @@lock.free
            end
        end
    end
end

module Kernel
    alias_method :orig_sleep, :sleep

    def sleep n
        Thread.synchronize do
            if n < 0 then
                raise IllegalMonitorState, "Already in insommnia mode" if
Thread.insomnia?
                return Thread.set_insomnia( -n )
            end
            Thread.lock.free
            ### if we are in Thread insomnia we might be interrupted by the
supervisor which gets us out of it
            ### but even if we call Thread.stop_insomnia then that has no
effect. So no sync needed :)
            Thread.stop_insomnia if Thread.insomnia?
            orig_sleep n
        end
    end
end

------=_Part_75357_3799978.1153259766438--