Difference between revisions of "Language Reference/Monitors"

From wiki.visual-prolog.com
(→‎Semantics: code indentation)
(→‎Queue: bug missing retract)
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{Preliminary Documentation}}
{{languageReferenceNavbar|Monitors}}
{{languageReferenceNavbar|Monitors}}


Line 138: Line 136:
{{Example| Here is a queue class that solves the pick-out problem using a guard predicate on the '''remove''' operation:
{{Example| Here is a queue class that solves the pick-out problem using a guard predicate on the '''remove''' operation:
<vip>monitor class queue
<vip>monitor class queue
    predicates
predicates
        insert : (integer Element).
    insert : (integer Element).
    predicates
predicates
        remove : () -> integer Element.
    remove : () -> integer Element.
end class queue
end class queue


%-----------------------------------------
implement queue
implement queue
    class facts
class facts
        element_fact : (integer Element) nondeterm.
    element_fact : (integer Element) nondeterm.


    clauses
clauses
        insert(Element) :-
    insert(Element) :-
            assert(element_fact(Element)).
        assert(element_fact(Element)).


    clauses
clauses
        remove guard remove_guard.
    remove guard remove_guard.
        remove() = Element :-
    remove() = Element :-
            retract(element_fact(Element)),
        retract(element_fact(Element)),
            !;
        !;
            common_exception::raise_error(common_exception::classInfo, predicate_name(),
        exception::raise_error("The guard should have ensured that the queue is not empty").
                "The guard should have ensured that the queue is not empty").


    predicates
predicates
        remove_quard : () determ.
    remove_quard : () determ.
    clauses
clauses
        remove_guard() :-
    remove_guard() :-
            element_fact(_),
        element_fact(_),
            !.
        !.
end implement queue</vip>
end implement queue</vip>
Notice that '''remove''' is a procedure, because threads that call remove will '''''wait''''' until there is an element for them.  The guard predicate '''remove_guard''' succeeds if there is an element in the queue.
Notice that '''remove''' is a procedure, because threads that call remove will '''''wait''''' until there is an element for them.  The guard predicate '''remove_guard''' succeeds if there is an element in the queue.
Line 172: Line 170:
}}
}}


Guard predicates are handled in the transformation mentioned above. The queue example is effectively the same as this "monitor-free" code:
Guard predicates are handled in the transformation mentioned above.
 
{{Example|The queue example is effectively the same as this "monitor-free" code:
<vip>class queue
<vip>class queue
    predicates
predicates
        insert : (integer Element).
    insert : (integer Element).
    predicates
predicates
        remove : () -> integer Element.
    remove : () -> integer Element.
end class queue
end class queue


%-----------------------------------------
implement queue
implement queue
    class facts
class facts
        monitorRegion : mutex := mutex::create(false).
    monitorRegion : mutex := mutex::create(false).
        remove_guard_event : event := event::create(true, toBoolean(remove_guard())).
    remove_guard_event : event := event::create(true, toBoolean(remove_guard())).
        element_fact : (integer Element) nondeterm.
    element_fact : (integer Element) nondeterm.


    clauses
clauses
        insert(Element) :-
    insert(Element) :-
            _W = monitorRegion:wait(),
        _W = monitorRegion:wait(),
            try
        try
                assert(element_fact(Element))
            assert(element_fact(Element))
            finally
        finally
                setGuardEvents(),
            setGuardEvents(),
                monitorRegion:release()
            monitorRegion:release()
            end try.
        end try.


    clauses
clauses
        remove() = Element :-
    remove() = Element :-
            _W = syncObject::waitAll([monitorRegion, remove_guard_event]),
        _W = syncObject::waitAll([monitorRegion, remove_guard_event]),
            try
        try
                retract(element_fact(Element)),
            retract(element_fact(Element)),
                !;
            !;
                common_exception::raise_error(common_exception::classInfo, predicate_name(),
            common_exception::raise_error(common_exception::classInfo, predicate_name(),
                    "The guard should have ensured that the queue is not empty")
                "The guard should have ensured that the queue is not empty")
            finally
        finally
                setGuardEvents(),
            setGuardEvents(),
                monitorRegion:release()
            monitorRegion:release()
            end try.
        end try.


    class predicates
class predicates
        remove_guard : () determ.
    remove_guard : () determ.
    clauses
clauses
        remove_guard() :-
    remove_guard() :-
            element_fact(_),
        element_fact(_),
            !.
        !.
 
class predicates
    setGuardEvents : ().
clauses
    setGuardEvents() :-
        remove_guard_event:setSignaled(toBoolean(remove_guard())).
end implement queue</vip>}}


    class predicates
        setGuardEvents : ().
    clauses
        setGuardEvents() :-
            remove_guard_event:setSignaled(toBoolean(remove_guard())).
end implement queue</vip>
An '''event''' is created for each guard predicate; this event is set to ''signaled'' if the guard predicate succeeds.  As mentioned it is set during the creation of the monitor and each time a predicate leaves the monitor (before it leaves the critical region).
An '''event''' is created for each guard predicate; this event is set to ''signaled'' if the guard predicate succeeds.  As mentioned it is set during the creation of the monitor and each time a predicate leaves the monitor (before it leaves the critical region).


Line 237: Line 239:


<vip>monitor class log
<vip>monitor class log
    properties
properties
        logStream : outputStream.
    logStream : outputStream.
    predicates
predicates
        write : (...).
    write : (...).
end class log
end class log


%-----------------------------------------
implement log
implement log
    class facts
class facts
        logStream : outputStream := erroneous.
    logStream : outputStream := erroneous.
    clauses
clauses
        write(...) :-
    write(...) :-
            logStream:write(time::new():formatShortDate(), ": "),
        logStream:write(time::new():formatShortDate(), ": "),
            logStream:write(...),
        logStream:write(...),
            logStream:nl().
        logStream:nl().
  end implement log</vip>
  end implement log</vip>


Line 262: Line 265:
end interface outputStream_sync
end interface outputStream_sync


%-----------------------------------------
class outputStream_sync : outputStream_sync
class outputStream_sync : outputStream_sync
    constructors
constructors
        new : (outputStream Stream).
    new : (outputStream Stream).
end class outputStream_sync  
end class outputStream_sync  


%-----------------------------------------
implement outputStream_sync
implement outputStream_sync
     delegate interface outputStream to stream
     delegate interface outputStream to stream


    facts
facts
        stream : outputStream.
    stream : outputStream.


    clauses
clauses
        new(Stream) :- stream := Stream.
    new(Stream) :- stream := Stream.
end implement outputStream_sync</vip>
end implement outputStream_sync</vip>


You should realize however that with code like this:
You should realize however that with code like this:


<vip>   clauses
<vip>clauses
        write(...) :-
    write(...) :-
            logStream:write(time::new():formatShortDate(), ": "),
        logStream:write(time::new():formatShortDate(), ": "),
            logStream:write(...),
        logStream:write(...),
            logStream:nl().</vip>
        logStream:nl().</vip>


consists of '''''three separate''''' operations, so it can still be the case (fx) that two threads first write the time and then one writes the "...", etc.
consists of '''''three separate''''' operations, so it can still be the case (fx) that two threads first write the time and then one writes the "...", etc.
Line 292: Line 297:


<vip>monitor interface queue{@Elem}
<vip>monitor interface queue{@Elem}
    predicates
predicates
        enqueue : (@Elem Value).
    enqueue : (@Elem Value).
    predicates
predicates
        dequeue : () -> @Elem Value.
    dequeue : () -> @Elem Value.
end interface queue
end interface queue


%-----------------------------------------
class queue{@Elem} : queue{@Elem}
class queue{@Elem} : queue{@Elem}
end class queue
end class queue


%-----------------------------------------
implement queue{@Elem}
implement queue{@Elem}
    facts
facts
        value_fact : (@Elem Value).
    value_fact : (@Elem Value).


    clauses
clauses
        enqueue(V) :-
    enqueue(V) :-
            assert(value_fact(V)).
        assert(value_fact(V)).


    clauses
clauses
        dequeue guard { value_fact(_), ! }.
    dequeue guard { value_fact(_), ! }.
        dequeue() = V :-
    dequeue() = V :-
            value_fact(V),
        retract(value_fact(V)),
            !.
        !.
        dequeue() = V :-
    dequeue() = V :-
            common_exception::raise_error(....).
        common_exception::raise_error(....).
end implement queue</vip>
end implement queue</vip>
'''Notice''' that [[PFC]] contains a similar class <vp>monitorQueue</vp> already.


=== References ===
=== References ===


*[[wikipedia:Monitor (synchronization)]]
*[[wikipedia:Monitor (synchronization)]]

Latest revision as of 09:11, 7 April 2014

A monitor is a language construction to synchronize two or more threads that use a shared resource, usually a hardware device or a set of variables. The compiler transparently inserts locking and unlocking code to appropriately designated procedures, instead of the programmer having to access concurrency primitives explicitly.

Visual Prolog monitor entrances can be controlled by guard predicates (conditions).

Syntax

Monitor interfaces and monitor classes are scopes:

Scope : one of
    ...
    MonitorInterface
    MonitorClass
    ...

A monitor interface is defined by writing the keyword monitor in front of a regular interface definition:

MonitorInterface :
    monitor IntertfaceDefinition

A monitor class is declared by writing the keyword monitor in front of a regular class declaration:

MonitorClass :
    monitor ClassDeclaration

Monitor classes and interfaces cannot declare multi and nondeterm predicate members.

Restrictions

  • A regular interface cannot support a monitor interface
  • A monitor class cannot construct objects.
  • It is not legal to inherit from a monitor (i.e. from a class that implements a monitor interface).

Semantics

The predicates and properties declared in a monitor are the entrances to the monitor. A thread enters the monitor through an entrance and is in the monitor until it leaves that entrance again. Only one thread is allowed to be in the monitor at the time. So each entry is protected as a critical region.

The semantics is simplest to understand as a program transformation (which is how it is implemented). Consider this academic example:

monitor class mmmm
predicates
    e1 : (a1 A1).
    e2 : (a2 A2).
    ...
    en : (an An).
end class mmmm
 
%-----------------------------------------
implement mmmm
clauses
    e1(A1) :- <B1>.
 
clauses
    e2(A2) :- <B2>.
 
...
clauses
    en(An) :- <Bn>.
end implement mmmm

Where <B1>, <B2>, ..., <Bn> are clause bodies. This code corresponds to the following "normal" code:

class mmmm
predicates
    e1 : (a1 A1).
    e2 : (a2 A2).
    ...
    en : (an An).
end class mmmm
 
%-----------------------------------------
implement mmmm
class facts
    monitorRegion : mutex := mutex::create(false).
 
clauses
    e1(A1) :-
        _W = monitorRegion:wait(),
        try
           <B1>
        finally
           monitorRegion:release()
        end try.
 
clauses
    e2(A2) :-
        _W = monitorRegion:wait(),
        try
            <B2>
        finally
            monitorRegion:release()
        end try.
...
clauses
    en(An) :-
        _W = monitorRegion:wait(),
        try
            <Bn>
        finally
            monitorRegion:release()
        end try.
end implement mmmm

So each monitor class is extended with a mutex, which is used to create a critical region around each entry body.

The code for monitor objects is similar, except that the mutex object is owned by the object.

Guards

Consider a monitor protected queue: some threads (producers) inserts elements in the queue and others (consumers) pick-out elements. However, you cannot pick-out elements if the queue is empty.

If we implement the queue using a monitor, the "pick-out" entry could be determ, failing if the queue is empty. But then the consumers would have to "poll" the queue until an element can be obtained. Such polling uses system resources, and normally it is desirable to avoid polling. This problem can be solved by guard predicates.

Each entry can have a guard associated in the implementation. The guard is added as a special guard-clause before the other clauses of the entry.

Clause : one of
    ...
    GuardClause.
GuardClause : one of
    LowerCaseIdentifier guard LowerCaseIdentifier .
    LowerCaseIdentifier guard AnonymousPredicate .
Example The guard can be the name of a predicate
clauses
    remove guard remove_guard.
    remove() = ...
Example The guard can also be an anonymous predicate
clauses
    remove guard { :- element_fact(_), ! }.
    remove() = ...


The guard predicates are evaluated when the monitor is created. For monitor classes this means at program start, for object predicates this is immediately after the construction of the object. The guard predicates are also evaluated whenever a tread leaves the monitor. But they are not evaluated at any other time.

If a certain guard succeeds the corresponding entry is open, if it fails the entry is closed.

It is only possible to enter open entries.

Example Here is a queue class that solves the pick-out problem using a guard predicate on the remove operation:
monitor class queue
predicates
    insert : (integer Element).
predicates
    remove : () -> integer Element.
end class queue
 
%-----------------------------------------
implement queue
class facts
    element_fact : (integer Element) nondeterm.
 
clauses
    insert(Element) :-
        assert(element_fact(Element)).
 
clauses
    remove guard remove_guard.
    remove() = Element :-
        retract(element_fact(Element)),
        !;
        exception::raise_error("The guard should have ensured that the queue is not empty").
 
predicates
    remove_quard : () determ.
clauses
    remove_guard() :-
        element_fact(_),
        !.
end implement queue

Notice that remove is a procedure, because threads that call remove will wait until there is an element for them. The guard predicate remove_guard succeeds if there is an element in the queue.

So remove_guard is evaluated each time a thread leaves the monitor, and the element_fact fact database can only be changed by a thread that is inside the monitor. Therefore the guard value stays sensible all the time (i.e. when there are no threads in the monitor). It is important to ensure such "stays sensible" condition for guards.

Guard predicates are handled in the transformation mentioned above.

Example The queue example is effectively the same as this "monitor-free" code:
class queue
predicates
    insert : (integer Element).
predicates
    remove : () -> integer Element.
end class queue
 
%-----------------------------------------
implement queue
class facts
    monitorRegion : mutex := mutex::create(false).
    remove_guard_event : event := event::create(true, toBoolean(remove_guard())).
    element_fact : (integer Element) nondeterm.
 
clauses
    insert(Element) :-
        _W = monitorRegion:wait(),
        try
            assert(element_fact(Element))
        finally
            setGuardEvents(),
            monitorRegion:release()
        end try.
 
clauses
    remove() = Element :-
        _W = syncObject::waitAll([monitorRegion, remove_guard_event]),
        try
            retract(element_fact(Element)),
            !;
            common_exception::raise_error(common_exception::classInfo, predicate_name(),
                "The guard should have ensured that the queue is not empty")
        finally
            setGuardEvents(),
            monitorRegion:release()
        end try.
 
class predicates
    remove_guard : () determ.
clauses
    remove_guard() :-
        element_fact(_),
        !.
 
class predicates
    setGuardEvents : ().
clauses
    setGuardEvents() :-
        remove_guard_event:setSignaled(toBoolean(remove_guard())).
end implement queue

An event is created for each guard predicate; this event is set to signaled if the guard predicate succeeds. As mentioned it is set during the creation of the monitor and each time a predicate leaves the monitor (before it leaves the critical region).

When entering an entry the threads waits both for the monitorRegion and for the guard event to be in signalled state.

In the code above the initialization of the class itself and the guard events are done in an undetermined order. But actually it is ensured that the guard events are initialized after all other class/object initialization is performed.

Examples of practical usage

This section shows a few cases where monitors are handy.

Writing to a log file

Several threads needs to log information to a single log file.

monitor class log
properties
    logStream : outputStream.
predicates
    write : (...).
end class log
 
%-----------------------------------------
implement log
class facts
    logStream : outputStream := erroneous.
clauses
    write(...) :-
        logStream:write(time::new():formatShortDate(), ": "),
        logStream:write(...),
        logStream:nl().
 end implement log

The monitor ensures that writing of a log lines are not mixed with each other, and that stream changes only takes place between writing of log lines.

Shared output streams

This monitor can be used to thread protect the operations of an output stream:

monitor interface outputStream_sync
    supports outputStream
end interface outputStream_sync
 
%-----------------------------------------
class outputStream_sync : outputStream_sync
constructors
    new : (outputStream Stream).
end class outputStream_sync 
 
%-----------------------------------------
implement outputStream_sync
    delegate interface outputStream to stream
 
facts
    stream : outputStream.
 
clauses
    new(Stream) :- stream := Stream.
end implement outputStream_sync

You should realize however that with code like this:

clauses
    write(...) :-
        logStream:write(time::new():formatShortDate(), ": "),
        logStream:write(...),
        logStream:nl().

consists of three separate operations, so it can still be the case (fx) that two threads first write the time and then one writes the "...", etc.

Queue

The queue above is fine, but actually it may be better to create queue objects. Using generic interfaces we can create a very general queue:

monitor interface queue{@Elem}
predicates
    enqueue : (@Elem Value).
predicates
    dequeue : () -> @Elem Value.
end interface queue
 
%-----------------------------------------
class queue{@Elem} : queue{@Elem}
end class queue
 
%-----------------------------------------
implement queue{@Elem}
facts
    value_fact : (@Elem Value).
 
clauses
    enqueue(V) :-
        assert(value_fact(V)).
 
clauses
    dequeue guard { value_fact(_), ! }.
    dequeue() = V :-
        retract(value_fact(V)),
        !.
    dequeue() = V :-
        common_exception::raise_error(....).
end implement queue

Notice that PFC contains a similar class monitorQueue already.

References