restart.cpp
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, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2009-08-11 15:05:41 +0200 (Tue, 11 Aug 2009) $ by $Author: schulte $ 00011 * $Revision: 9585 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/support.hh> 00039 00040 #ifdef GECODE_HAS_THREADS 00041 00042 #include <gecode/search/parallel/restart.hh> 00043 00044 namespace Gecode { namespace Search { namespace Parallel { 00045 00046 Space* 00047 Restart::next(void) { 00048 // Invariant: the worker holds the wait mutex 00049 m_search.acquire(); 00050 // Check whether root space is already failed 00051 if (root == NULL) { 00052 m_search.release(); 00053 return NULL; 00054 } 00055 while (!solutions.empty()) { 00056 // No search needs to be done, try to take leftover solution 00057 Space* s = solutions.pop(); 00058 if (best == NULL) { 00059 best = s->clone(); 00060 reset_needed = true; 00061 m_search.release(); 00062 return s; 00063 } else { 00064 s->constrain(*best); 00065 if (s->status() == SS_FAILED) { 00066 delete s; 00067 } else { 00068 delete best; 00069 best = s->clone(); 00070 reset_needed = true; 00071 m_search.release(); 00072 return s; 00073 } 00074 } 00075 } 00076 // We ignore stopped (it will be reported again if needed) 00077 has_stopped = false; 00078 // No more solutions? 00079 if (n_busy == 0) { 00080 m_search.release(); 00081 return NULL; 00082 } 00083 if (reset_needed) { 00084 reset_needed = false; 00085 root->constrain(*best); 00086 // Leave lock 00087 m_search.release(); 00088 // Grab wait lock for reset 00089 m_wait_reset.acquire(); 00090 // Release workers for reset 00091 release(C_RESET); 00092 // Wait for reset cycle started 00093 e_reset_ack_start.wait(); 00094 // Perform reset 00095 root = reset(root); 00096 // Block workers again to ensure invariant 00097 block(); 00098 // Release reset lock 00099 m_wait_reset.release(); 00100 // Wait for reset cycle stopped 00101 e_reset_ack_stop.wait(); 00102 if (root == NULL) 00103 return NULL; 00104 } else { 00105 m_search.release(); 00106 } 00107 00108 // Okay, now search has to continue, make the guys work 00109 release(C_WORK); 00110 00111 /* 00112 * Wait until a search related event has happened. It might be that 00113 * the event has already been signalled in the last run, but the 00114 * solution has been removed. So we have to try until there has 00115 * something new happened. 00116 */ 00117 while (true) { 00118 e_search.wait(); 00119 m_search.acquire(); 00120 while (!solutions.empty()) { 00121 // Check solution 00122 Space* s = solutions.pop(); 00123 if (best == NULL) { 00124 best = s->clone(); 00125 reset_needed = true; 00126 m_search.release(); 00127 // Make workers wait again 00128 block(); 00129 return s; 00130 } else { 00131 s->constrain(*best); 00132 if (s->status() == SS_FAILED) { 00133 delete s; 00134 } else { 00135 delete best; 00136 best = s->clone(); 00137 reset_needed = true; 00138 m_search.release(); 00139 // Make workers wait again 00140 block(); 00141 return s; 00142 } 00143 } 00144 } 00145 // No more solutions or stopped? 00146 if ((n_busy == 0) || has_stopped) { 00147 m_search.release(); 00148 // Make workers wait again 00149 block(); 00150 return NULL; 00151 } 00152 m_search.release(); 00153 } 00154 GECODE_NEVER; 00155 return NULL; 00156 } 00157 00158 Restart::~Restart(void) { 00159 delete best; 00160 delete root; 00161 } 00162 00163 }}} 00164 00165 #endif 00166 00167 // STATISTICS: search-parallel