Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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 
35 namespace 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  };
137  class Deleter : public Runnable {
138  protected:
141  public:
143  Deleter(Master* m);
145  virtual void run(void);
146  };
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  }
298  GECODE_NEVER;
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>
326  : Runnable(true), master(m) {}
327 
328  template<class Jobs, class RetType>
329  void
331  delete master;
332  }
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
362  Thread::run(new Deleter(master));
363  }
364 
365 
366 }}
367 
368 // STATISTICS: support-any
369 
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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
void release(void)
Release the mutex.
Definition: none.hpp:48
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:42
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
Parallel iterator that runs jobs with a given number of threads.
Definition: run-jobs.hpp:76
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
An interface for objects that can be run by a thread.
Definition: thread.hpp:264
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
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56