| 1 | <?xml version="1.0" encoding="utf-8"?> |
|---|
| 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" |
|---|
| 3 | "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> |
|---|
| 4 | |
|---|
| 5 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> |
|---|
| 6 | |
|---|
| 7 | <head> |
|---|
| 8 | <meta http-equiv="content-type" content="application/xml+xhtml; charset=utf-8" /> |
|---|
| 9 | <title>Logtalk user manual: multi-threading programming</title> |
|---|
| 10 | <link rel="stylesheet" href="../screen.css" type="text/css" media="screen"/> |
|---|
| 11 | <link rel="stylesheet" href="../print.css" type="text/css" media="print"/> |
|---|
| 12 | </head> |
|---|
| 13 | |
|---|
| 14 | <body> |
|---|
| 15 | |
|---|
| 16 | <div class="top-left">Logtalk user manual</div> |
|---|
| 17 | <div class="top-right">Multi-threading programming</div> |
|---|
| 18 | <div class="bottom-left"><span class="page"/></div> |
|---|
| 19 | <div class="bottom-right"><span class="page"/></div> |
|---|
| 20 | <div class="navtop"><a href="../index.html">Contents</a> > <a href="index.html">User Manual</a> > Threads</div> |
|---|
| 21 | |
|---|
| 22 | <h1 id="threads_threads">Multi-threading programming</h1> |
|---|
| 23 | |
|---|
| 24 | <p> |
|---|
| 25 | Logtalk provides <strong>experimental</strong> support for multi-threading programming on selected Prolog compilers. Logtalk makes use of the low-level Prolog built-in predicates that interface with POSIX threads (or a suitable emulation), providing a small set of high-level predicates and directives that allows programmers to easily take advantage of modern multi-processor and multi-core computers without worrying about the details of creating, synchronizing, or communicating with threads. Logtalk multi-threading programming integrates with object-oriented programming by enabling objects and categories to prove goals concurrently and to send both synchronous and asynchronous messages. |
|---|
| 26 | </p> |
|---|
| 27 | |
|---|
| 28 | <h2 id="threads_enabling">Enabling multi-threading support</h2> |
|---|
| 29 | |
|---|
| 30 | <p> |
|---|
| 31 | Multi-threading support may be disabled by default. It can be enabled on the Prolog configuration files of supported compilers by setting the read-only compiler flag <code>threads</code> to <code>on</code>. |
|---|
| 32 | </p> |
|---|
| 33 | |
|---|
| 34 | <h2 id="threads_directive">Enabling objects to make multi-threading calls</h2> |
|---|
| 35 | |
|---|
| 36 | <p> |
|---|
| 37 | The <a title="Consult reference manual" href="../refman/directives/threaded0.html"><code>threaded/0</code></a> object directive is used to enable an object to make multi-threading calls: |
|---|
| 38 | </p> |
|---|
| 39 | <pre>:- threaded.</pre> |
|---|
| 40 | <p> |
|---|
| 41 | This directive results in the automatic creation and set up an object message queue when the object is loaded or created at runtime. Object message queues are used for exchanging thread notifications and for storing concurrent goal solutions and replies to the <em>multi-threading calls</em> made within the object. The message queue for the pseudo-object <code>user</code> is automatically created when Logtalk is loaded (provided that multi-threading programming is supported and enabled for the chosen Prolog compiler). |
|---|
| 42 | </p> |
|---|
| 43 | |
|---|
| 44 | <h2 id="threads_builtins">Multi-threading built-in predicates</h2> |
|---|
| 45 | |
|---|
| 46 | <p> |
|---|
| 47 | Logtalk provides a small set of built-in predicates for multi-threading programming. For simple tasks where you simply want to prove a set of goals, each one in its own thread, Logtalk provides a <a title="Consult reference manual" href="../refman/builtins/threaded1.html"><code>threaded/1</code></a> built-in predicate. The remaining predicates allow for fine-grained control, including postponing retrieving of thread goal results at a later time, supporting non-deterministic thread goals, and making <em>one-way</em> asynchronous calls. Together, these predicates provide high-level support for multi-threading programming, covering most common use cases. |
|---|
| 48 | </p> |
|---|
| 49 | |
|---|
| 50 | <h3 id="threads_threaded">Proving goals concurrently using threads</h3> |
|---|
| 51 | |
|---|
| 52 | <p> |
|---|
| 53 | A set of goals may be proved concurrently by calling the Logtalk built-in predicate <a title="Consult reference manual" href="../refman/builtins/threaded1.html"><code>threaded/1</code></a>. Each goal in the set runs in its own thread. |
|---|
| 54 | </p> |
|---|
| 55 | <p> |
|---|
| 56 | When the <code>threaded/1</code> predicate argument is a conjunction of goals, the predicate call is akin to <em>and-parallelism</em>. For example, assume that we want to find all the prime numbers in a given interval, <code>[N, M]</code>. We can split the interval in two parts and then span two threads to compute the primes numbers in each sub-interval: |
|---|
| 57 | </p> |
|---|
| 58 | <pre>prime_numbers(N, M, Primes) :- |
|---|
| 59 | M > N, |
|---|
| 60 | N1 is N + (M - N) // 2, |
|---|
| 61 | N2 is N1 + 1, |
|---|
| 62 | threaded(( |
|---|
| 63 | prime_numbers(N2, M, [], Acc), |
|---|
| 64 | prime_numbers(N, N1, Acc, Primes) |
|---|
| 65 | )). |
|---|
| 66 | |
|---|
| 67 | prime_numbers(N, M, Acc, Primes) :- |
|---|
| 68 | ... |
|---|
| 69 | </pre> |
|---|
| 70 | <p> |
|---|
| 71 | The <code>threaded/1</code> call terminates when the two implicit threads terminate. In a computer with two or more processors (or with a processor with two or more cores) the code above can be expected to provide better computation times when compared with single-threaded code for sufficiently large intervals. |
|---|
| 72 | </p> |
|---|
| 73 | <p> |
|---|
| 74 | When the <code>threaded/1</code> predicate argument is a disjunction of goals, the predicate call is akin to <em>or-parallelism</em>, here reinterpreted as a set of goal <em>competing</em> for providing a solution. For example, assume that we have several different methods to find the roots of real functions. Depending on the real function, some methods will faster than others. Some methods will converge into the solution while others may diverge and never find it. We can try all the methods at one by writing: |
|---|
| 75 | </p> |
|---|
| 76 | <pre>find_root(Function, A, B, Error, Zero, Algorithm) :- |
|---|
| 77 | threaded(( |
|---|
| 78 | (bisection::find_root(Function, A, B, Error, Zero), Algorithm = bisection) |
|---|
| 79 | ; (newton::find_root(Function, A, B, Error, Zero), Algorithm = newton) |
|---|
| 80 | ; (muller::find_root(Function, A, B, Error, Zero), Algorithm = muller) |
|---|
| 81 | )). |
|---|
| 82 | </pre> |
|---|
| 83 | <p> |
|---|
| 84 | The <code>threaded/1</code> call succeeds when one of the implicit threads succeeds in finding the function root, leading to the termination of all the remaining competing threads. |
|---|
| 85 | </p> |
|---|
| 86 | <p> |
|---|
| 87 | The <code>threaded/1</code> built-in predicate is most useful for lengthy, independent deterministic computations where the computational costs of each goal outweigh the overhead of the implicit thread creation and management. |
|---|
| 88 | </p> |
|---|
| 89 | |
|---|
| 90 | <h3 id="threads_call">Proving goals asynchronously using threads</h3> |
|---|
| 91 | |
|---|
| 92 | <p> |
|---|
| 93 | A goal may be proved asynchronously using a new thread by calling the Logtalk built-in predicate <a title="Consult reference manual" href="../refman/builtins/threaded_call1_2.html"><code>threaded_call/1</code></a>. Calls to this predicate are always true and return immediately (assuming a callable argument). The term representing the goal is copied, not shared with the thread. |
|---|
| 94 | </p> |
|---|
| 95 | <p> |
|---|
| 96 | The results of proving a goal asynchronously in a new thread may be later retrieved by calling the Logtalk built-in predicate <a title="Consult reference manual" href="../refman/builtins/threaded_exit1_2.html"><code>threaded_exit/1</code></a> within the same object where the call to the <code>threaded_call/1</code> predicate was made. The <code>threaded_exit/1</code> calls block execution until the results of the <code>threaded_call/1</code> calls are sent back to the object message queue. |
|---|
| 97 | </p> |
|---|
| 98 | <p> |
|---|
| 99 | The <code>threaded_exit/1</code> predicate allow us to retrieve alternative solutions through backtracking (if you want to commit to the first solution, you may use the <a title="Consult reference manual" href="../refman/builtins/threaded_once1_2.html"><code>threaded_once/1</code></a> predicate instead of the <code>threaded_call/1</code> predicate). For example, assuming a <code>lists</code> object implementing the usual <code>member/2</code> predicate, we could write: |
|---|
| 100 | </p> |
|---|
| 101 | <pre>| ?- threaded_call(lists::member(X, [1,2,3])). |
|---|
| 102 | |
|---|
| 103 | X = _G189 |
|---|
| 104 | yes |
|---|
| 105 | |
|---|
| 106 | | ?- threaded_exit(lists::member(X, [1,2,3])). |
|---|
| 107 | |
|---|
| 108 | X = 1 ; |
|---|
| 109 | X = 2 ; |
|---|
| 110 | X = 3 ; |
|---|
| 111 | no |
|---|
| 112 | </pre> |
|---|
| 113 | <p> |
|---|
| 114 | In this case, the <code>threaded_call/1</code> and the <code>threaded_exit/1</code> calls are made within the pseudo-object <em>user</em>. The implicit thread running the <code>lists::member/2</code> goal suspends itself after providing a solution, waiting for a request to an alternative solution; the thread is automatically terminated when the runtime engine detects that backtracking to the <code>threaded_exit/1</code> call is no longer possible. |
|---|
| 115 | </p> |
|---|
| 116 | <p> |
|---|
| 117 | Calls to the <code>threaded_exit/1</code> predicate block the caller until the object message queue receives the reply to the asynchronous call. The predicate <a title="Consult reference manual" href="../refman/builtins/threaded_peek1_2.html"><code>threaded_peek/1</code></a> may be used to check if a reply is already available without removing it from the thread queue. The <code>threaded_peek/1</code> predicate call succeeds or fails immediately without blocking the caller. However, keep in mind that repeated use of this predicate is equivalent to polling a message queue, which may severely hurt performance. |
|---|
| 118 | </p> |
|---|
| 119 | <p> |
|---|
| 120 | Be careful when using the <code>threaded_exit/1</code> predicate inside failure-driven loops. When all the solutions have been found (and the thread generating them is therefore terminated), re-calling the predicate will generate an exception. Note that failing instead of throwing an exception is not an acceptable solution as it could be misinterpreted as a failure of the <code>threaded_exit/1</code> argument. |
|---|
| 121 | </p> |
|---|
| 122 | <p> |
|---|
| 123 | The example on the previous section with prime numbers could be rewritten using the <code>threaded_call/1</code> and <code>threaded_exit/1</code> predicates: |
|---|
| 124 | </p> |
|---|
| 125 | <pre>prime_numbers(N, M, Primes) :- |
|---|
| 126 | M > N, |
|---|
| 127 | N1 is N + (M - N) // 2, |
|---|
| 128 | N2 is N1 + 1, |
|---|
| 129 | threaded_call(prime_numbers(N2, M, [], Acc)), |
|---|
| 130 | threaded_call(prime_numbers(N, N1, Acc, Primes)), |
|---|
| 131 | threaded_exit(prime_numbers(N2, M, [], Acc)), |
|---|
| 132 | threaded_exit(prime_numbers(N, N1, Acc, Primes)). |
|---|
| 133 | |
|---|
| 134 | prime_numbers(N, M, Acc, Primes) :- |
|---|
| 135 | ... |
|---|
| 136 | </pre> |
|---|
| 137 | <p> |
|---|
| 138 | When using asynchronous calls, the link between a <code>threaded_exit/1</code> call and the corresponding <code>threaded_call/1</code> call is made using unification. If there are several <code>threaded_call/1</code> calls for a matching <code>threaded_exit/1</code> call, the connection can potentially be established with any of them. Nevertheless, you can easily use a tag the calls by using the extended <a title="Consult reference manual" href="../refman/builtins/threaded_call1_2.html"><code>threaded_call/2</code></a> and <a title="Consult reference manual" href="../refman/builtins/threaded_exit1_2.html"><code>threaded_exit/2</code></a> built-in predicates. For example: |
|---|
| 139 | </p> |
|---|
| 140 | <pre> |
|---|
| 141 | ?- threaded_call(member(X, [1,2,3]), Tag). |
|---|
| 142 | |
|---|
| 143 | Tag = 1 |
|---|
| 144 | yes |
|---|
| 145 | |
|---|
| 146 | ?- threaded_call(member(X, [1,2,3]), Tag). |
|---|
| 147 | |
|---|
| 148 | Tag = 2 |
|---|
| 149 | yes |
|---|
| 150 | |
|---|
| 151 | ?- threaded_exit(member(X, [1,2,3]), 2). |
|---|
| 152 | |
|---|
| 153 | X = 1 ; |
|---|
| 154 | X = 2 ; |
|---|
| 155 | X = 3 |
|---|
| 156 | yes |
|---|
| 157 | </pre> |
|---|
| 158 | <p> |
|---|
| 159 | When using these predicates, the tags shall be considered as an opaque term; users shall not rely on its type. |
|---|
| 160 | </p> |
|---|
| 161 | |
|---|
| 162 | <h2 id="threads_ignore">One-way asynchronous calls</h2> |
|---|
| 163 | |
|---|
| 164 | <p> |
|---|
| 165 | Sometimes we want to prove a goal in a new thread without caring about the results. This may be accomplished by using the built-in predicate <a title="Consult reference manual" href="../refman/builtins/threaded_ignore1.html"><code>threaded_ignore/1</code></a>. For example, assume that we are developing a multi-agent application where an agent may send an "happy birthday" message to another agent. We could write: |
|---|
| 166 | </p> |
|---|
| 167 | <pre>threaded_ignore(agent::happy_birthday), ... |
|---|
| 168 | </pre> |
|---|
| 169 | <p> |
|---|
| 170 | The call succeeds with no reply of the goal success, failure, or even exception ever being sent back to the object making the call. Note that this predicate implicitly performs a deterministic call of its argument. |
|---|
| 171 | </p> |
|---|
| 172 | |
|---|
| 173 | <h2 id="threads_synchronized_predicates">Asynchronous calls and synchronized predicates</h2> |
|---|
| 174 | |
|---|
| 175 | <p> |
|---|
| 176 | Proving a goal asynchronously using a new thread may lead to problems when the goal results in side-effects such as input/output operations or modifications to an object database. For example, if a new thread is started with the same goal before the first one finished its job, we may end up with mixed output, a corrupted database, or unexpected goal failures. In order to solve this problem, predicates (and grammar rule non-terminals) with side-effects can be declared as <em>synchronized</em> by using the <a title="Consult reference manual" href="../refman/directives/synchronized1.html"><code>synchronized/1</code></a> predicate directive. Proving a query to a synchronized predicate (or synchronized non-terminal) is internally protected by a mutex, thus allowing for easy thread synchronization. For example: |
|---|
| 177 | </p> |
|---|
| 178 | <pre>:- synchronized(db_update/1). % ensure thread synchronization |
|---|
| 179 | |
|---|
| 180 | db_update(Update) :- % predicate with side-effects |
|---|
| 181 | ... |
|---|
| 182 | </pre> |
|---|
| 183 | <p> |
|---|
| 184 | A second example: assume an object defining two predicates for writing, respectively, even and odd numbers in a given interval to the standard output. Given a large interval, a goal such as: |
|---|
| 185 | </p> |
|---|
| 186 | <pre>| ?- threaded_call(obj::odd_numbers(1,1000)), threaded_call(obj::even_numbers(1,1000)). |
|---|
| 187 | |
|---|
| 188 | 1 3 2 4 6 8 5 7 10 ... |
|---|
| 189 | ... |
|---|
| 190 | </pre> |
|---|
| 191 | <p> |
|---|
| 192 | will most likely result in a mixed up output. By declaring the <code>odd_numbers/2</code> and <code>even_numbers/2</code> predicates synchronized: |
|---|
| 193 | </p> |
|---|
| 194 | <pre>:- synchronized([ |
|---|
| 195 | odd_numbers/2, |
|---|
| 196 | even_numbers/2]). |
|---|
| 197 | </pre> |
|---|
| 198 | <p> |
|---|
| 199 | one goal will only start after the other one finished: |
|---|
| 200 | </p> |
|---|
| 201 | <pre>| ?- threaded_ignore(obj::odd_numbers(1,1000)), threaded_ignore(obj::even_numbers(1,1000)). |
|---|
| 202 | |
|---|
| 203 | 1 3 5 7 9 11 ... |
|---|
| 204 | ... |
|---|
| 205 | 2 4 6 8 10 12 ... |
|---|
| 206 | ... |
|---|
| 207 | </pre> |
|---|
| 208 | <p> |
|---|
| 209 | Note that, in a more realistic scenario, the two <code>threaded_ignore/1</code> calls would be made concurrently from different objects. Using the same synchronized directive for a set of predicates imply that they all use the same mutex, as required for this example. |
|---|
| 210 | </p> |
|---|
| 211 | |
|---|
| 212 | <p> |
|---|
| 213 | The <code>synchronized/1</code> directive must precede any local calls to the synchronized predicate (or synchronized non-terminal) in order to ensure proper compilation. In addition, as each Logtalk entity is independently compiled, this directive must be included in every object or category that contains a definition for the described predicate, even if the predicate declaration is inherited from another entity, in order to ensure proper compilation. Note that a synchronized predicate cannot be declared dynamic. To ensure atomic updates of a dynamic predicate, declare as synchronized the predicate performing the update. |
|---|
| 214 | </p> |
|---|
| 215 | <p> |
|---|
| 216 | Logtalk supports both deterministic and non-deterministic synchronized predicates (and synchronized non-terminals). However, whenever possible, synchronized predicates should be coded as deterministic predicates in order to avoid deadlocks. In those cases where the predicate (or grammar rule) is defined in the same object (or category) where the predicate is declared synchronized, Logtalk takes advantage of any existing <a title="Consult reference manual" href="../refman/directives/mode2.html"><code>mode/2</code></a> directives in order to generate the most appropriated mutex handling code. When no <code>mode/2</code> predicate directives are presented, Logtalk assumes a deterministic predicate when generating the mutex handling code. |
|---|
| 217 | </p> |
|---|
| 218 | <p> |
|---|
| 219 | We may declare all predicates of an object (or a category) as synchronized by using the entity directive <a title="Consult reference manual" href="../refman/directives/synchronized0.html"><code>synchronized/0</code></a>. In this case, the <code>synchronized/1</code> predicate directive is not necessary and should not be used. |
|---|
| 220 | </p> |
|---|
| 221 | <p> |
|---|
| 222 | Synchronized predicates may be used as wrappers to messages sent to objects that are not multi-threading aware. For example, assume a <code>random</code> object defining a <code>random/1</code> predicate that generates random numbers, using side-effects on its implementation (e.g. for storing the generator seed). We can specify and define e.g. a <code>sync_random/1</code> predicate as follows: |
|---|
| 223 | </p> |
|---|
| 224 | <pre> |
|---|
| 225 | :- synchronized(sync_random/1). |
|---|
| 226 | |
|---|
| 227 | sync_random(Random) :- |
|---|
| 228 | random::random(Random). |
|---|
| 229 | </pre> |
|---|
| 230 | <p> |
|---|
| 231 | and then always use the <code>sync_random/1</code> predicate instead of the predicate <code>random/1</code> from multi-threaded code. |
|---|
| 232 | </p> |
|---|
| 233 | <p> |
|---|
| 234 | The synchronization entity and predicate directives may be used when defining objects that may be reused in both single-threaded and multi-threaded Logtalk applications. The directives are simply ignored (i.e. the synchronized predicates are interpreted as normal predicates) when the objects are used in a single-threaded application. |
|---|
| 235 | </p> |
|---|
| 236 | |
|---|
| 237 | <h2 id="threads_notifications">Synchronizing threads through notifications</h2> |
|---|
| 238 | |
|---|
| 239 | <p> |
|---|
| 240 | Declaring a set of predicates as synchronized can only ensure that they are not executed at the same time by different threads. Sometimes we need to suspend a thread not on a synchronization lock but on some condition that must hold true for a thread goal to proceed. I.e. we want a thread goal to be suspended until a condition becomes true instead of simply failing. The built-in predicate <a title="Consult reference manual" href="../refman/builtins/threaded_wait1.html"><code>threaded_wait/1</code></a> allows us to suspend a predicate execution (running in its own thread) until a notification is received. Notifications are posted using the built-in predicate |
|---|
| 241 | <a title="Consult reference manual" href="../refman/builtins/threaded_notify1.html"><code>threaded_notify/1</code></a>. A notification is a Prolog term that a programmer chooses to represent some condition becoming true. Any Prolog term can be used as a notification argument for these predicates. Related calls to the <code>threaded_wait/1</code> and <code>threaded_notify/1</code> must be made within the same object, <em>this</em>, as the object message queue is used internally for posting and retrieving notifications. |
|---|
| 242 | </p> |
|---|
| 243 | <p> |
|---|
| 244 | Each notification posted by a call to the <code>threaded_notify/1</code> predicate is consumed by a single <code>threaded_wait/1</code> predicate call (i.e. these predicates implement a peer-to-peer mechanism). Care should be taken to avoid deadlocks when two (or more) threads both wait and post notifications to each other. |
|---|
| 245 | </p> |
|---|
| 246 | |
|---|
| 247 | <h2 id="threads_performance">Multi-threading performance</h2> |
|---|
| 248 | |
|---|
| 249 | <p> |
|---|
| 250 | The performance of multi-threading applications is highly dependent on the back-end Prolog compiler, on the operating-system, and on the use of dynamic binding and dynamic predicates. All compatible back-end Prolog compilers that support multi-threading features make use of POSIX threads or <em>pthreads</em>. The performance of the underlying pthreads implementation can exhibit significant differences between operating systems. An important point is synchronized access to dynamic predicates. As different threads may try to simultaneously access and update dynamic predicates, these operations must be protected by a lock, usually implemented using a mutex. Poor mutex lock operating-system performance, combined with a large number of collisions by several threads trying to acquire the same lock, often result in severe performance penalties. Thus, whenever possible, avoid using dynamic predicates and dynamic binding. |
|---|
| 251 | </p> |
|---|
| 252 | |
|---|
| 253 | <div class="footer"> |
|---|
| 254 | <div class="copyright"> |
|---|
| 255 | <span>Copyright © <a href="mailto:pmoura@logtalk.org">Paulo Moura</a> — <a href="http://logtalk.org">Logtalk.org</a></span><br/> |
|---|
| 256 | <span>Last updated on: October 20, 2008</span> |
|---|
| 257 | </div> |
|---|
| 258 | <div class="navbottom"> |
|---|
| 259 | <span><a href="events.html">previous</a> | <a href="../glossary.html">glossary</a> | <a href="errors.html">next</a></span><br/> |
|---|
| 260 | <span><a href="http://validator.w3.org/check/referer">XHTML</a> + <a href="http://jigsaw.w3.org/css-validator/check/referer">CSS</a></span> |
|---|
| 261 | </div> |
|---|
| 262 | </div> |
|---|
| 263 | |
|---|
| 264 | </body> |
|---|
| 265 | |
|---|
| 266 | </html> |
|---|
