Generated on Tue May 22 09:40:17 2018 for Gecode by doxygen 1.6.3

run-jobs.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2017
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 
00035 namespace Gecode { namespace Support {
00036 
00038   template<class RetType>
00039   class Job {
00040   public:
00042     virtual RetType run(int i) = 0;
00044     virtual ~Job(void) {}
00045   };
00046 
00048   template<class RetType>
00049   class JobStop {
00050   protected:
00052     RetType r;
00053   public:
00055     JobStop(RetType r0);
00057     RetType result(void) const;
00058   };
00059 
00060   template<class Jobs, class RetType>
00076   class RunJobs {
00077   protected:
00078     class Master;
00080     class Worker : public Runnable {
00081     protected:
00083       Job<RetType>* job;
00085       Master* master;
00087       int idx;
00088     public:
00090       Worker(Job<RetType>* j, Master* m, int i);
00092       virtual void run(void);
00094       virtual ~Worker(void);
00095     };
00096     class Master {
00097     protected:
00099       Mutex m;
00101       Event e;
00103       unsigned int n_threads;
00105       Jobs& jobs;
00107       int idx;
00109       RetType sres; 
00111       int sidx;
00113       DynamicQueue<RetType,Heap> rs;
00114     public:
00116       Job<RetType>* next(int& i);
00118       void report(RetType r);
00120       void stop(RetType r, int i);
00122       bool done(void) const;
00124       Master(Jobs& j, unsigned int m);
00126       bool run(RetType& r);
00128       bool stopped(void) const;
00130       int stoppedjob(RetType& r) const;
00132       bool needthread(void);
00134       ~Master(void);
00135     };
00137     class Deleter : public Runnable {
00138     protected:
00140       Master* master;
00141     public:
00143       Deleter(Master* m);
00145       virtual void run(void);
00146     };
00148     Master* master;
00149   public:
00151     RunJobs(Jobs& j, unsigned int m);
00153     bool run(RetType& r);
00155     bool stopped(int& i, RetType& r) const;
00157     ~RunJobs(void);
00158   };
00159 
00160 
00161 
00162   template<class RetType>
00163   forceinline
00164   JobStop<RetType>::JobStop(RetType r0) : r(r0) {}
00165 
00166   template<class RetType>
00167   forceinline RetType
00168   JobStop<RetType>::result(void) const {
00169     return r;
00170   }
00171 
00172 
00173 
00174   template<class Jobs, class RetType>
00175   forceinline
00176   RunJobs<Jobs,RetType>::Worker::Worker(Job<RetType>* j, 
00177                                         Master* m,
00178                                         int i) 
00179     : Runnable(true), job(j), master(m), idx(i) {}
00180   
00181   template<class Jobs, class RetType>
00182   RunJobs<Jobs,RetType>::Worker::~Worker(void) {}
00183 
00184 
00185   template<class Jobs, class RetType>
00186   inline int
00187   RunJobs<Jobs,RetType>::Master::stoppedjob(RetType& r) const {
00188     r = sres;
00189     return sidx;
00190   }
00191 
00192   template<class Jobs, class RetType>
00193   inline bool
00194   RunJobs<Jobs,RetType>::Master::stopped(void) const {
00195     return sidx >= 0;
00196   }
00197 
00198   template<class Jobs, class RetType>
00199   forceinline Job<RetType>*
00200   RunJobs<Jobs,RetType>::Master::next(int& i) {
00201     m.acquire();
00202     Job<RetType>* j;
00203     if (jobs() && !stopped()) {
00204       j = jobs.job(); i=idx++;
00205     } else {
00206       j = NULL;
00207       n_threads--;
00208       e.signal();
00209     }
00210     m.release();
00211     return j;
00212   }
00213 
00214   template<class Jobs, class RetType>
00215   forceinline void
00216   RunJobs<Jobs,RetType>::Master::report(RetType r) {
00217     m.acquire();
00218     rs.push(r); 
00219     e.signal();
00220     m.release();
00221   }
00222 
00223   template<class Jobs, class RetType>
00224   forceinline void
00225   RunJobs<Jobs,RetType>::Master::stop(RetType r, int i) {
00226     m.acquire();
00227     if (!stopped()) {
00228       sres=r; sidx = i;
00229     }
00230     rs.push(r); 
00231     e.signal();
00232     m.release();
00233   }
00234 
00235   template<class Jobs, class RetType>
00236   void
00237   RunJobs<Jobs,RetType>::Worker::run(void) {
00238     do {
00239       try {
00240         RetType r = job->run(idx);
00241         master->report(r);
00242       } catch (JobStop<RetType>& js) {
00243         master->stop(js.result(),idx);
00244       }
00245       delete job;
00246       job = master->next(idx);
00247     } while (job != NULL);
00248   }
00249 
00250   template<class Jobs, class RetType>
00251   forceinline bool
00252   RunJobs<Jobs,RetType>::Master::done(void) const {
00253     return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
00254   }
00255 
00256   template<class Jobs, class RetType>
00257   inline
00258   RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads) 
00259     : n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
00260     m.acquire();
00261     while ((n_threads < m_threads) && jobs()) {
00262       if (stopped())
00263         break;
00264       Thread::run(new Worker(jobs.job(),this,idx));
00265       n_threads++; idx++;
00266     }
00267     m.release();
00268   }
00269 
00270   template<class Jobs, class RetType>
00271   inline bool
00272   RunJobs<Jobs,RetType>::Master::run(RetType& r) {
00273     m.acquire();
00274     if (done()) {
00275       m.release();
00276       return false;
00277     }
00278     if (!rs.empty()) {
00279       r = rs.pop();
00280       m.release();
00281       return true;
00282     }
00283     m.release();
00284     while (true) {
00285       e.wait();
00286       m.acquire();
00287       if (done()) {
00288         m.release();
00289         return false;
00290       }
00291       if (!rs.empty()) {
00292         r = rs.pop();
00293         m.release();
00294         return true;
00295       }
00296       m.release();
00297     }
00298     GECODE_NEVER;
00299   }
00300 
00301   template<class Jobs, class RetType>
00302   inline bool
00303   RunJobs<Jobs,RetType>::Master::needthread(void) {
00304     bool n;
00305     m.acquire();
00306     while (!rs.empty())
00307       rs.pop().~RetType();
00308     sidx = 0;
00309     n = !done();
00310     m.release();
00311     return n;
00312   }
00313 
00314   template<class Jobs, class RetType>
00315   inline
00316   RunJobs<Jobs,RetType>::Master::~Master(void) {
00317     sidx = 0;
00318     RetType r;
00319     while (run(r))
00320       r.~RetType();
00321   }
00322 
00323   template<class Jobs, class RetType>
00324   forceinline
00325   RunJobs<Jobs,RetType>::Deleter::Deleter(Master* m) 
00326     : Runnable(true), master(m) {}
00327 
00328   template<class Jobs, class RetType>
00329   void
00330   RunJobs<Jobs,RetType>::Deleter::run(void) {
00331     delete master;
00332   }
00333 
00334 
00335 
00336 
00337 
00338   template<class Jobs, class RetType>
00339   inline bool
00340   RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
00341     i = master->stoppedjob(r);
00342     return i >= 0;
00343   }
00344 
00345   template<class Jobs, class RetType>
00346   inline
00347   RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m) 
00348     : master(new Master(j,m)) {}
00349 
00350   template<class Jobs, class RetType>
00351   inline bool
00352   RunJobs<Jobs,RetType>::run(RetType& r) {
00353     return master->run(r);
00354   }
00355 
00356   template<class Jobs, class RetType>
00357   inline
00358   RunJobs<Jobs,RetType>::~RunJobs(void) {
00359     if (!master->needthread())
00360       delete master;
00361     else
00362       Thread::run(new Deleter(master));
00363   }
00364 
00365 
00366 }}
00367 
00368 // STATISTICS: support-any
00369