Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
run-jobs.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2017
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34
35namespace Gecode { namespace Support {
36
38 template<class RetType>
39 class Job {
40 public:
42 virtual RetType run(int i) = 0;
44 virtual ~Job(void) {}
45 };
46
48 template<class RetType>
49 class JobStop {
50 protected:
52 RetType r;
53 public:
55 JobStop(RetType r0);
57 RetType result(void) const;
58 };
59
60 template<class Jobs, class RetType>
76 class RunJobs {
77 protected:
78 class Master;
80 class Worker : public Runnable {
81 protected:
87 int idx;
88 public:
90 Worker(Job<RetType>* j, Master* m, int i);
92 virtual void run(void);
94 virtual ~Worker(void);
95 };
96 class Master {
97 protected:
103 unsigned int n_threads;
105 Jobs& jobs;
107 int idx;
109 RetType sres;
111 int sidx;
114 public:
116 Job<RetType>* next(int& i);
118 void report(RetType r);
120 void stop(RetType r, int i);
122 bool done(void) const;
124 Master(Jobs& j, unsigned int m);
126 bool run(RetType& r);
128 bool stopped(void) const;
130 int stoppedjob(RetType& r) const;
132 bool needthread(void);
134 ~Master(void);
135 };
136
137 class Deleter : public Runnable {
138 protected:
141 public:
143 Deleter(Master* m);
145 virtual void run(void);
146 };
147
149 public:
151 RunJobs(Jobs& j, unsigned int m);
153 bool run(RetType& r);
155 bool stopped(int& i, RetType& r) const;
157 ~RunJobs(void);
158 };
159
160
161
162 template<class RetType>
164 JobStop<RetType>::JobStop(RetType r0) : r(r0) {}
165
166 template<class RetType>
167 forceinline RetType
169 return r;
170 }
171
172
173
174 template<class Jobs, class RetType>
177 Master* m,
178 int i)
179 : Runnable(true), job(j), master(m), idx(i) {}
180
181 template<class Jobs, class RetType>
183
184
185 template<class Jobs, class RetType>
186 inline int
188 r = sres;
189 return sidx;
190 }
191
192 template<class Jobs, class RetType>
193 inline bool
195 return sidx >= 0;
196 }
197
198 template<class Jobs, class RetType>
201 m.acquire();
202 Job<RetType>* j;
203 if (jobs() && !stopped()) {
204 j = jobs.job(); i=idx++;
205 } else {
206 j = NULL;
207 n_threads--;
208 e.signal();
209 }
210 m.release();
211 return j;
212 }
213
214 template<class Jobs, class RetType>
215 forceinline void
217 m.acquire();
218 rs.push(r);
219 e.signal();
220 m.release();
221 }
222
223 template<class Jobs, class RetType>
224 forceinline void
226 m.acquire();
227 if (!stopped()) {
228 sres=r; sidx = i;
229 }
230 rs.push(r);
231 e.signal();
232 m.release();
233 }
234
235 template<class Jobs, class RetType>
236 void
238 do {
239 try {
240 RetType r = job->run(idx);
241 master->report(r);
242 } catch (JobStop<RetType>& js) {
243 master->stop(js.result(),idx);
244 }
245 delete job;
246 job = master->next(idx);
247 } while (job != NULL);
248 }
249
250 template<class Jobs, class RetType>
251 forceinline bool
253 return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
254 }
255
256 template<class Jobs, class RetType>
257 inline
258 RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads)
259 : n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
260 m.acquire();
261 while ((n_threads < m_threads) && jobs()) {
262 if (stopped())
263 break;
264 Thread::run(new Worker(jobs.job(),this,idx));
265 n_threads++; idx++;
266 }
267 m.release();
268 }
269
270 template<class Jobs, class RetType>
271 inline bool
273 m.acquire();
274 if (done()) {
275 m.release();
276 return false;
277 }
278 if (!rs.empty()) {
279 r = rs.pop();
280 m.release();
281 return true;
282 }
283 m.release();
284 while (true) {
285 e.wait();
286 m.acquire();
287 if (done()) {
288 m.release();
289 return false;
290 }
291 if (!rs.empty()) {
292 r = rs.pop();
293 m.release();
294 return true;
295 }
296 m.release();
297 }
299 }
300
301 template<class Jobs, class RetType>
302 inline bool
304 bool n;
305 m.acquire();
306 while (!rs.empty())
307 rs.pop().~RetType();
308 sidx = 0;
309 n = !done();
310 m.release();
311 return n;
312 }
313
314 template<class Jobs, class RetType>
315 inline
317 sidx = 0;
318 RetType r;
319 while (run(r))
320 r.~RetType();
321 }
322
323 template<class Jobs, class RetType>
327
328 template<class Jobs, class RetType>
329 void
333
334
335
336
337
338 template<class Jobs, class RetType>
339 inline bool
340 RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
341 i = master->stoppedjob(r);
342 return i >= 0;
343 }
344
345 template<class Jobs, class RetType>
346 inline
347 RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m)
348 : master(new Master(j,m)) {}
349
350 template<class Jobs, class RetType>
351 inline bool
353 return master->run(r);
354 }
355
356 template<class Jobs, class RetType>
357 inline
359 if (!master->needthread())
360 delete master;
361 else
363 }
364
365
366}}
367
368// STATISTICS: support-any
369
Queue with arbitrary number of elements.
An event for synchronization.
Definition thread.hpp:215
Class to throw an exception to stop new jobs from being started.
Definition run-jobs.hpp:49
RetType r
The result stored.
Definition run-jobs.hpp:52
JobStop(RetType r0)
Constructor.
Definition run-jobs.hpp:164
RetType result(void) const
Return the passed result.
Definition run-jobs.hpp:168
Baseclass for jobs with return type RetType.
Definition run-jobs.hpp:39
virtual ~Job(void)
Destructor.
Definition run-jobs.hpp:44
virtual RetType run(int i)=0
Run a job with iterator index i.
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
A class to delete the master (running in parallel)
Definition run-jobs.hpp:137
virtual void run(void)
Perform deletion.
Definition run-jobs.hpp:330
Master * master
The master to be deleted.
Definition run-jobs.hpp:140
Deleter(Master *m)
Initialize with master m.
Definition run-jobs.hpp:325
void stop(RetType r, int i)
Report that a job with index i has been stopped.
Definition run-jobs.hpp:225
int idx
Index of next job to be created.
Definition run-jobs.hpp:107
RetType sres
Result from a the first stopped job (passed in exception)
Definition run-jobs.hpp:109
Job< RetType > * next(int &i)
Get next job witth index i, if possible.
Definition run-jobs.hpp:200
int sidx
Index of the first stop that has been stopped (-1 if none)
Definition run-jobs.hpp:111
bool stopped(void) const
Whether a job has thrown a JobStop exception.
Definition run-jobs.hpp:194
Event e
Event is triggered if a the first job is added to queue.
Definition run-jobs.hpp:101
DynamicQueue< RetType, Heap > rs
Queue of not yet requested results.
Definition run-jobs.hpp:113
bool needthread(void)
Whether a new thread is needed for deletion.
Definition run-jobs.hpp:303
Mutex m
Mutex for synchronizing access.
Definition run-jobs.hpp:99
unsigned int n_threads
Number of threads currently not in use.
Definition run-jobs.hpp:103
void report(RetType r)
Report result r by a worker.
Definition run-jobs.hpp:216
bool run(RetType &r)
Run next job and return true if succesful and assign r to its result.
Definition run-jobs.hpp:272
int stoppedjob(RetType &r) const
Return index of first job that has thrown a JobStop exception (-1 if none) with its result.
Definition run-jobs.hpp:187
Master(Jobs &j, unsigned int m)
Initialize with job iterator j and maximal number of threads m.
Definition run-jobs.hpp:258
bool done(void) const
Test whether all jobs are done.
Definition run-jobs.hpp:252
The actual worker using a thread to run a job.
Definition run-jobs.hpp:80
int idx
Original iterator index of job.
Definition run-jobs.hpp:87
virtual void run(void)
Run jobs.
Definition run-jobs.hpp:237
Worker(Job< RetType > *j, Master *m, int i)
Initialize worker.
Definition run-jobs.hpp:176
Master * master
The master to communicate with.
Definition run-jobs.hpp:85
virtual ~Worker(void)
Nothing to delete (done in run)
Definition run-jobs.hpp:182
Job< RetType > * job
The job to run.
Definition run-jobs.hpp:83
Master * master
The actual master.
Definition run-jobs.hpp:148
RunJobs(Jobs &j, unsigned int m)
Initialize with job iterator j and maximal number of threads m.
Definition run-jobs.hpp:347
bool run(RetType &r)
Run next job and return true if succesful and assign r to its result.
Definition run-jobs.hpp:352
bool stopped(int &i, RetType &r) const
Whether a job has thrown a JobStop exception with index i and result r.
Definition run-jobs.hpp:340
~RunJobs(void)
Destructor.
Definition run-jobs.hpp:358
Runnable(bool d=true)
Initialize, d defines whether object is deleted when terminated.
Definition thread.hpp:40
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
Heap heap
The single global heap.
Definition heap.cpp:44
Support algorithms and datastructures
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56