Generated on Tue Mar 5 2013 22:37:29 for Gecode by doxygen 1.8.3.1
restart.cpp
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, 2009
8  *
9  * Last modified:
10  * $Date: 2009-08-11 23:05:41 +1000 (Tue, 11 Aug 2009) $ by $Author: schulte $
11  * $Revision: 9585 $
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 #include <gecode/support.hh>
39 
40 #ifdef GECODE_HAS_THREADS
41 
43 
44 namespace Gecode { namespace Search { namespace Parallel {
45 
46  Space*
47  Restart::next(void) {
48  // Invariant: the worker holds the wait mutex
49  m_search.acquire();
50  // Check whether root space is already failed
51  if (root == NULL) {
52  m_search.release();
53  return NULL;
54  }
55  while (!solutions.empty()) {
56  // No search needs to be done, try to take leftover solution
57  Space* s = solutions.pop();
58  if (best == NULL) {
59  best = s->clone();
60  reset_needed = true;
61  m_search.release();
62  return s;
63  } else {
64  s->constrain(*best);
65  if (s->status() == SS_FAILED) {
66  delete s;
67  } else {
68  delete best;
69  best = s->clone();
70  reset_needed = true;
71  m_search.release();
72  return s;
73  }
74  }
75  }
76  // We ignore stopped (it will be reported again if needed)
77  has_stopped = false;
78  // No more solutions?
79  if (n_busy == 0) {
80  m_search.release();
81  return NULL;
82  }
83  if (reset_needed) {
84  reset_needed = false;
85  root->constrain(*best);
86  // Leave lock
87  m_search.release();
88  // Grab wait lock for reset
90  // Release workers for reset
92  // Wait for reset cycle started
94  // Perform reset
95  root = reset(root);
96  // Block workers again to ensure invariant
97  block();
98  // Release reset lock
100  // Wait for reset cycle stopped
102  if (root == NULL)
103  return NULL;
104  } else {
105  m_search.release();
106  }
107 
108  // Okay, now search has to continue, make the guys work
109  release(C_WORK);
110 
111  /*
112  * Wait until a search related event has happened. It might be that
113  * the event has already been signalled in the last run, but the
114  * solution has been removed. So we have to try until there has
115  * something new happened.
116  */
117  while (true) {
118  e_search.wait();
119  m_search.acquire();
120  while (!solutions.empty()) {
121  // Check solution
122  Space* s = solutions.pop();
123  if (best == NULL) {
124  best = s->clone();
125  reset_needed = true;
126  m_search.release();
127  // Make workers wait again
128  block();
129  return s;
130  } else {
131  s->constrain(*best);
132  if (s->status() == SS_FAILED) {
133  delete s;
134  } else {
135  delete best;
136  best = s->clone();
137  reset_needed = true;
138  m_search.release();
139  // Make workers wait again
140  block();
141  return s;
142  }
143  }
144  }
145  // No more solutions or stopped?
146  if ((n_busy == 0) || has_stopped) {
147  m_search.release();
148  // Make workers wait again
149  block();
150  return NULL;
151  }
152  m_search.release();
153  }
154  GECODE_NEVER;
155  return NULL;
156  }
157 
159  delete best;
160  delete root;
161  }
162 
163 }}}
164 
165 #endif
166 
167 // STATISTICS: search-parallel