Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
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: 2017-01-24 21:23:36 +0100 (Tue, 24 Jan 2017) $ by $Author: schulte $
11  * $Revision: 15372 $
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;
47  };
48 
50  template<class RetType>
51  class JobStop {
52  protected:
54  RetType r;
55  public:
57  JobStop(RetType r0);
59  RetType result(void) const;
60  };
61 
62  template<class Jobs, class RetType>
78  class RunJobs {
79  protected:
80  class Master;
82  class Worker : public Runnable {
83  protected:
89  int idx;
90  public:
92  Worker(Job<RetType>* j, Master* m, int i);
94  virtual void run(void);
96  virtual ~Worker(void);
97  };
98  class Master {
99  protected:
105  unsigned int n_threads;
107  Jobs& jobs;
109  int idx;
111  RetType sres;
113  int sidx;
116  public:
118  Job<RetType>* next(int& i);
120  void report(RetType r);
122  void stop(RetType r, int i);
124  bool done(void) const;
126  Master(Jobs& j, unsigned int m);
128  bool run(RetType& r);
130  bool stopped(void) const;
132  int stoppedjob(RetType& r) const;
134  bool needthread(void);
136  ~Master(void);
137  };
139  class Deleter : public Runnable {
140  protected:
143  public:
145  Deleter(Master* m);
147  virtual void run(void);
148  };
151  public:
153  RunJobs(Jobs& j, unsigned int m);
155  bool run(RetType& r);
157  bool stopped(int& i, RetType& r) const;
159  ~RunJobs(void);
160  };
161 
162 
163 
164  template<class RetType>
166  JobStop<RetType>::JobStop(RetType r0) : r(r0) {}
167 
168  template<class RetType>
169  forceinline RetType
171  return r;
172  }
173 
174 
175 
176  template<class Jobs, class RetType>
179  Master* m,
180  int i)
181  : Runnable(true), job(j), master(m), idx(i) {}
182 
183  template<class Jobs, class RetType>
185 
186 
187  template<class Jobs, class RetType>
188  inline int
190  r = sres;
191  return sidx;
192  }
193 
194  template<class Jobs, class RetType>
195  inline bool
197  return sidx >= 0;
198  }
199 
200  template<class Jobs, class RetType>
203  m.acquire();
204  Job<RetType>* j;
205  if (jobs() && !stopped()) {
206  j = jobs.job(); i=idx++;
207  } else {
208  j = NULL;
209  n_threads--;
210  e.signal();
211  }
212  m.release();
213  return j;
214  }
215 
216  template<class Jobs, class RetType>
217  forceinline void
219  m.acquire();
220  rs.push(r);
221  e.signal();
222  m.release();
223  }
224 
225  template<class Jobs, class RetType>
226  forceinline void
228  m.acquire();
229  if (!stopped()) {
230  sres=r; sidx = i;
231  }
232  rs.push(r);
233  e.signal();
234  m.release();
235  }
236 
237  template<class Jobs, class RetType>
238  void
240  do {
241  try {
242  RetType r = job->run(idx);
243  master->report(r);
244  } catch (JobStop<RetType>& js) {
245  master->stop(js.result(),idx);
246  }
247  delete job;
248  job = master->next(idx);
249  } while (job != NULL);
250  }
251 
252  template<class Jobs, class RetType>
253  forceinline bool
255  return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
256  }
257 
258  template<class Jobs, class RetType>
259  inline
260  RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads)
261  : n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
262  m.acquire();
263  while ((n_threads < m_threads) && jobs()) {
264  if (stopped())
265  break;
266  Thread::run(new Worker(jobs.job(),this,idx));
267  n_threads++; idx++;
268  }
269  m.release();
270  }
271 
272  template<class Jobs, class RetType>
273  inline bool
275  m.acquire();
276  if (done()) {
277  m.release();
278  return false;
279  }
280  if (!rs.empty()) {
281  r = rs.pop();
282  m.release();
283  return true;
284  }
285  m.release();
286  while (true) {
287  e.wait();
288  m.acquire();
289  if (done()) {
290  m.release();
291  return false;
292  }
293  if (!rs.empty()) {
294  r = rs.pop();
295  m.release();
296  return true;
297  }
298  m.release();
299  }
300  GECODE_NEVER;
301  }
302 
303  template<class Jobs, class RetType>
304  inline bool
306  bool n;
307  m.acquire();
308  while (!rs.empty())
309  rs.pop().~RetType();
310  sidx = 0;
311  n = !done();
312  m.release();
313  return n;
314  }
315 
316  template<class Jobs, class RetType>
317  inline
319  sidx = 0;
320  RetType r;
321  while (run(r))
322  r.~RetType();
323  }
324 
325  template<class Jobs, class RetType>
328  : Runnable(true), master(m) {}
329 
330  template<class Jobs, class RetType>
331  void
333  delete master;
334  }
335 
336 
337 
338 
339 
340  template<class Jobs, class RetType>
341  inline bool
342  RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
343  i = master->stoppedjob(r);
344  return i >= 0;
345  }
346 
347  template<class Jobs, class RetType>
348  inline
349  RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m)
350  : master(new Master(j,m)) {}
351 
352  template<class Jobs, class RetType>
353  inline bool
355  return master->run(r);
356  }
357 
358  template<class Jobs, class RetType>
359  inline
361  if (!master->needthread())
362  delete master;
363  else
364  Thread::run(new Deleter(master));
365  }
366 
367 
368 }}
369 
370 // STATISTICS: support-any
371 
Definition: run-jobs.hpp:98
An event for synchronization.
Definition: thread.hpp:223
Job< RetType > * job
The job to run.
Definition: run-jobs.hpp:85
#define forceinline
Definition: config.hpp:173
Job< RetType > * next(int &i)
Get next job witth index i, if possible.
Definition: run-jobs.hpp:202
int sidx
Index of the first stop that has been stopped (-1 if none)
Definition: run-jobs.hpp:113
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
A class to delete the master (running in parallel)
Definition: run-jobs.hpp:139
Mutex m
Mutex for synchronizing access.
Definition: run-jobs.hpp:101
~RunJobs(void)
Destructor.
Definition: run-jobs.hpp:360
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool run(RetType &r)
Run next job and return true if succesful and assign r to its result.
Definition: run-jobs.hpp:354
Master * master
The actual master.
Definition: run-jobs.hpp:150
~Master(void)
Destructor.
Definition: run-jobs.hpp:318
The actual worker using a thread to run a job.
Definition: run-jobs.hpp:82
Parallel iterator that runs jobs with a given number of threads.
Definition: run-jobs.hpp:78
virtual void run(void)
Perform deletion.
Definition: run-jobs.hpp:332
Deleter(Master *m)
Initialize with master m.
Definition: run-jobs.hpp:327
Gecode toplevel namespace
RetType result(void) const
Return the passed result.
Definition: run-jobs.hpp:170
int idx
Original iterator index of job.
Definition: run-jobs.hpp:89
Event e
Event is triggered if a the first job is added to queue.
Definition: run-jobs.hpp:103
bool needthread(void)
Whether a new thread is needed for deletion.
Definition: run-jobs.hpp:305
Worker(Job< RetType > *j, Master *m, int i)
Initialize worker.
Definition: run-jobs.hpp:178
Baseclass for jobs with return type RetType.
Definition: run-jobs.hpp:43
Class to throw an exception to stop new jobs from being started.
Definition: run-jobs.hpp:51
RetType sres
Result from a the first stopped job (passed in exception)
Definition: run-jobs.hpp:111
virtual ~Worker(void)
Nothing to delete (done in run)
Definition: run-jobs.hpp:184
static void run(Runnable *r)
Construct a new thread and run r.
Definition: thread.hpp:120
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
unsigned int n_threads
Number of threads currently not in use.
Definition: run-jobs.hpp:105
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:189
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Heap heap
The single global heap.
Definition: heap.cpp:48
JobStop(RetType r0)
Constructor.
Definition: run-jobs.hpp:166
RetType r
The result stored.
Definition: run-jobs.hpp:54
DynamicQueue< RetType, Heap > rs
Queue of not yet requested results.
Definition: run-jobs.hpp:115
void stop(RetType r, int i)
Report that a job with index i has been stopped.
Definition: run-jobs.hpp:227
Queue with arbitrary number of elements.
An interface for objects that can be run by a thread.
Definition: thread.hpp:258
int idx
Index of next job to be created.
Definition: run-jobs.hpp:109
bool done(void) const
Test whether all jobs are done.
Definition: run-jobs.hpp:254
virtual RetType run(int i)=0
Run a job with iterator index i.
virtual void run(void)
Run jobs.
Definition: run-jobs.hpp:239
bool stopped(void) const
Whether a job has thrown a JobStop exception.
Definition: run-jobs.hpp:196
void report(RetType r)
Report result r by a worker.
Definition: run-jobs.hpp:218
void release(void)
Release the mutex.
Definition: none.hpp:52
bool run(RetType &r)
Run next job and return true if succesful and assign r to its result.
Definition: run-jobs.hpp:274
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Jobs & jobs
Input jobs.
Definition: run-jobs.hpp:107
RunJobs(Jobs &j, unsigned int m)
Initialize with job iterator j and maximal number of threads m.
Definition: run-jobs.hpp:349
Master * master
The master to communicate with.
Definition: run-jobs.hpp:87
Master * master
The master to be deleted.
Definition: run-jobs.hpp:142
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:342
Master(Jobs &j, unsigned int m)
Initialize with job iterator j and maximal number of threads m.
Definition: run-jobs.hpp:260