run-jobs.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2017
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Support {
template<class RetType>
class Job {
public:
virtual RetType run(int i) = 0;
virtual ~Job(void) {}
};
template<class RetType>
class JobStop {
protected:
RetType r;
public:
JobStop(RetType r0);
RetType result(void) const;
};
template<class Jobs, class RetType>
class RunJobs {
protected:
class Master;
class Worker : public Runnable {
protected:
Job<RetType>* job;
Master* master;
int idx;
public:
Worker(Job<RetType>* j, Master* m, int i);
virtual void run(void);
virtual ~Worker(void);
};
class Master {
protected:
Mutex m;
Event e;
unsigned int n_threads;
Jobs& jobs;
int idx;
RetType sres;
int sidx;
DynamicQueue<RetType,Heap> rs;
public:
Job<RetType>* next(int& i);
void report(RetType r);
void stop(RetType r, int i);
bool done(void) const;
Master(Jobs& j, unsigned int m);
bool run(RetType& r);
bool stopped(void) const;
int stoppedjob(RetType& r) const;
bool needthread(void);
~Master(void);
};
class Deleter : public Runnable {
protected:
Master* master;
public:
Deleter(Master* m);
virtual void run(void);
};
Master* master;
public:
RunJobs(Jobs& j, unsigned int m);
bool run(RetType& r);
bool stopped(int& i, RetType& r) const;
~RunJobs(void);
};
template<class RetType>
forceinline
JobStop<RetType>::JobStop(RetType r0) : r(r0) {}
template<class RetType>
forceinline RetType
JobStop<RetType>::result(void) const {
return r;
}
template<class Jobs, class RetType>
forceinline
RunJobs<Jobs,RetType>::Worker::Worker(Job<RetType>* j,
Master* m,
int i)
: Runnable(true), job(j), master(m), idx(i) {}
template<class Jobs, class RetType>
RunJobs<Jobs,RetType>::Worker::~Worker(void) {}
template<class Jobs, class RetType>
inline int
RunJobs<Jobs,RetType>::Master::stoppedjob(RetType& r) const {
r = sres;
return sidx;
}
template<class Jobs, class RetType>
inline bool
RunJobs<Jobs,RetType>::Master::stopped(void) const {
return sidx >= 0;
}
template<class Jobs, class RetType>
forceinline Job<RetType>*
RunJobs<Jobs,RetType>::Master::next(int& i) {
m.acquire();
Job<RetType>* j;
if (jobs() && !stopped()) {
j = jobs.job(); i=idx++;
} else {
j = NULL;
n_threads--;
e.signal();
}
m.release();
return j;
}
template<class Jobs, class RetType>
forceinline void
RunJobs<Jobs,RetType>::Master::report(RetType r) {
m.acquire();
rs.push(r);
e.signal();
m.release();
}
template<class Jobs, class RetType>
forceinline void
RunJobs<Jobs,RetType>::Master::stop(RetType r, int i) {
m.acquire();
if (!stopped()) {
sres=r; sidx = i;
}
rs.push(r);
e.signal();
m.release();
}
template<class Jobs, class RetType>
void
RunJobs<Jobs,RetType>::Worker::run(void) {
do {
try {
RetType r = job->run(idx);
master->report(r);
} catch (JobStop<RetType>& js) {
master->stop(js.result(),idx);
}
delete job;
job = master->next(idx);
} while (job != NULL);
}
template<class Jobs, class RetType>
forceinline bool
RunJobs<Jobs,RetType>::Master::done(void) const {
return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
}
template<class Jobs, class RetType>
inline
RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads)
: n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
m.acquire();
while ((n_threads < m_threads) && jobs()) {
if (stopped())
break;
Thread::run(new Worker(jobs.job(),this,idx));
n_threads++; idx++;
}
m.release();
}
template<class Jobs, class RetType>
inline bool
RunJobs<Jobs,RetType>::Master::run(RetType& r) {
m.acquire();
if (done()) {
m.release();
return false;
}
if (!rs.empty()) {
r = rs.pop();
m.release();
return true;
}
m.release();
while (true) {
e.wait();
m.acquire();
if (done()) {
m.release();
return false;
}
if (!rs.empty()) {
r = rs.pop();
m.release();
return true;
}
m.release();
}
GECODE_NEVER;
}
template<class Jobs, class RetType>
inline bool
RunJobs<Jobs,RetType>::Master::needthread(void) {
bool n;
m.acquire();
while (!rs.empty())
rs.pop().~RetType();
sidx = 0;
n = !done();
m.release();
return n;
}
template<class Jobs, class RetType>
inline
RunJobs<Jobs,RetType>::Master::~Master(void) {
sidx = 0;
RetType r;
while (run(r))
r.~RetType();
}
template<class Jobs, class RetType>
forceinline
RunJobs<Jobs,RetType>::Deleter::Deleter(Master* m)
: Runnable(true), master(m) {}
template<class Jobs, class RetType>
void
RunJobs<Jobs,RetType>::Deleter::run(void) {
delete master;
}
template<class Jobs, class RetType>
inline bool
RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
i = master->stoppedjob(r);
return i >= 0;
}
template<class Jobs, class RetType>
inline
RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m)
: master(new Master(j,m)) {}
template<class Jobs, class RetType>
inline bool
RunJobs<Jobs,RetType>::run(RetType& r) {
return master->run(r);
}
template<class Jobs, class RetType>
inline
RunJobs<Jobs,RetType>::~RunJobs(void) {
if (!master->needthread())
delete master;
else
Thread::run(new Deleter(master));
}
}}
// STATISTICS: support-any
Gecode::Support::DynamicQueue
Queue with arbitrary number of elements.
Definition dynamic-queue.hpp:42
Gecode::Support::Event
An event for synchronization.
Definition thread.hpp:215
Gecode::Support::JobStop
Class to throw an exception to stop new jobs from being started.
Definition run-jobs.hpp:49
Gecode::Support::JobStop::r
RetType r
The result stored.
Definition run-jobs.hpp:52
Gecode::Support::JobStop::JobStop
JobStop(RetType r0)
Constructor.
Definition run-jobs.hpp:164
Gecode::Support::JobStop::result
RetType result(void) const
Return the passed result.
Definition run-jobs.hpp:168
Gecode::Support::Job
Baseclass for jobs with return type RetType.
Definition run-jobs.hpp:39
Gecode::Support::Job::~Job
virtual ~Job(void)
Destructor.
Definition run-jobs.hpp:44
Gecode::Support::Job::run
virtual RetType run(int i)=0
Run a job with iterator index i.
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Gecode::Support::RunJobs::Deleter
A class to delete the master (running in parallel).
Definition run-jobs.hpp:137
Gecode::Support::RunJobs::Deleter::run
virtual void run(void)
Perform deletion.
Definition run-jobs.hpp:330
Gecode::Support::RunJobs::Deleter::master
Master * master
The master to be deleted.
Definition run-jobs.hpp:140
Gecode::Support::RunJobs::Deleter::Deleter
Deleter(Master *m)
Initialize with master m.
Definition run-jobs.hpp:325
Gecode::Support::RunJobs::Master
Definition run-jobs.hpp:96
Gecode::Support::RunJobs::Master::~Master
~Master(void)
Destructor.
Definition run-jobs.hpp:316
Gecode::Support::RunJobs::Master::stop
void stop(RetType r, int i)
Report that a job with index i has been stopped.
Definition run-jobs.hpp:225
Gecode::Support::RunJobs::Master::idx
int idx
Index of next job to be created.
Definition run-jobs.hpp:107
Gecode::Support::RunJobs::Master::sres
RetType sres
Result from a the first stopped job (passed in exception).
Definition run-jobs.hpp:109
Gecode::Support::RunJobs::Master::next
Job< RetType > * next(int &i)
Get next job witth index i, if possible.
Definition run-jobs.hpp:200
Gecode::Support::RunJobs::Master::sidx
int sidx
Index of the first stop that has been stopped (-1 if none).
Definition run-jobs.hpp:111
Gecode::Support::RunJobs::Master::stopped
bool stopped(void) const
Whether a job has thrown a JobStop exception.
Definition run-jobs.hpp:194
Gecode::Support::RunJobs::Master::e
Event e
Event is triggered if a the first job is added to queue.
Definition run-jobs.hpp:101
Gecode::Support::RunJobs::Master::rs
DynamicQueue< RetType, Heap > rs
Queue of not yet requested results.
Definition run-jobs.hpp:113
Gecode::Support::RunJobs::Master::needthread
bool needthread(void)
Whether a new thread is needed for deletion.
Definition run-jobs.hpp:303
Gecode::Support::RunJobs::Master::m
Mutex m
Mutex for synchronizing access.
Definition run-jobs.hpp:99
Gecode::Support::RunJobs::Master::n_threads
unsigned int n_threads
Number of threads currently not in use.
Definition run-jobs.hpp:103
Gecode::Support::RunJobs::Master::report
void report(RetType r)
Report result r by a worker.
Definition run-jobs.hpp:216
Gecode::Support::RunJobs::Master::run
bool run(RetType &r)
Run next job and return true if succesful and assign r to its result.
Definition run-jobs.hpp:272
Gecode::Support::RunJobs::Master::stoppedjob
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
Gecode::Support::RunJobs::Master::Master
Master(Jobs &j, unsigned int m)
Initialize with job iterator j and maximal number of threads m.
Definition run-jobs.hpp:258
Gecode::Support::RunJobs::Master::jobs
Jobs & jobs
Input jobs.
Definition run-jobs.hpp:105
Gecode::Support::RunJobs::Master::done
bool done(void) const
Test whether all jobs are done.
Definition run-jobs.hpp:252
Gecode::Support::RunJobs::Worker
The actual worker using a thread to run a job.
Definition run-jobs.hpp:80
Gecode::Support::RunJobs::Worker::idx
int idx
Original iterator index of job.
Definition run-jobs.hpp:87
Gecode::Support::RunJobs::Worker::run
virtual void run(void)
Run jobs.
Definition run-jobs.hpp:237
Gecode::Support::RunJobs::Worker::Worker
Worker(Job< RetType > *j, Master *m, int i)
Initialize worker.
Definition run-jobs.hpp:176
Gecode::Support::RunJobs::Worker::master
Master * master
The master to communicate with.
Definition run-jobs.hpp:85
Gecode::Support::RunJobs::Worker::~Worker
virtual ~Worker(void)
Nothing to delete (done in run).
Definition run-jobs.hpp:182
Gecode::Support::RunJobs::Worker::job
Job< RetType > * job
The job to run.
Definition run-jobs.hpp:83
Gecode::Support::RunJobs::master
Master * master
The actual master.
Definition run-jobs.hpp:148
Gecode::Support::RunJobs::RunJobs
RunJobs(Jobs &j, unsigned int m)
Initialize with job iterator j and maximal number of threads m.
Definition run-jobs.hpp:347
Gecode::Support::RunJobs::run
bool run(RetType &r)
Run next job and return true if succesful and assign r to its result.
Definition run-jobs.hpp:352
Gecode::Support::RunJobs::stopped
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
Gecode::Support::RunJobs::~RunJobs
~RunJobs(void)
Destructor.
Definition run-jobs.hpp:358
Gecode::Support::Runnable::Runnable
Runnable(bool d=true)
Initialize, d defines whether object is deleted when terminated.
Definition thread.hpp:40
Gecode::Support::Thread::run
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Support
Support algorithms and datastructures
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56