Difference between revisions of "Language Reference/Monitors"

From wiki.visual-prolog.com
m (geshi update)
(→‎Queue: correct syntax)
Line 316: Line 316:


     clauses
     clauses
        dequeue guard { value_fact(_), ! }.
         dequeue() = V :-
         dequeue() = V :-
             value_fact(V),
             value_fact(V),
Line 321: Line 322:
         dequeue() = V :-
         dequeue() = V :-
             common_exception::raise_error(....).
             common_exception::raise_error(....).
    clauses
        dequeue_guard() :-
            value_fact(_),
            !.
end implement queue</vip>
end implement queue</vip>


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


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

Revision as of 14:36, 15 March 2010

Template:Preliminary Documentation


A monitor is an 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 leave 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 are similar, except that the mutex object is owned by the object.

Guard Predicates

Consider a monitor protected queue: some threads (producers) inserts elements in the queue and others (consumers) pick-out elements. However, you can not 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 quard 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.
    predicates
        classInfo : core::classInfo.
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)),
            !;
            common_exception::raise_error(common_exception::classInfo, predicate_name(),
                "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. The queue example is effectively the same as this "monitor-free" code:

class queue
    predicates
        insert : (integer Element).
    predicates
        remove : () -> integer Element.
    predicates
        classInfo : core::classInfo.
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())).
    clauses
 
    clauses
        classInfo("queue", "1.0").
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 ohter 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 opeations, 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 :-
            value_fact(V),
            !.
        dequeue() = V :-
            common_exception::raise_error(....).
end implement queue

References