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