001 /*
002 * $RCSfile: FileAssignment.java,v $
003 *
004 * Created on April 2, 2006, 11:48 AM
005 *
006 * This file is part of the STAR Scheduler.
007 * Copyright (c) 2002-2006 STAR Collaboration - Brookhaven National Laboratory
008 *
009 * STAR Scheduler is free software; you can redistribute it and/or modify
010 * it under the terms of the GNU General Public License as published by
011 * the Free Software Foundation; either version 2 of the License, or
012 * (at your option) any later version.
013 *
014 * STAR Scheduler is distributed in the hope that it will be useful,
015 * but WITHOUT ANY WARRANTY; without even the implied warranty of
016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
017 * GNU General Public License for more details.
018 *
019 * You should have received a copy of the GNU General Public License
020 * along with STAR Scheduler; if not, write to the Free Software
021 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
022 */
023 package gov.bnl.star.offline.scheduler.policy;
024
025 import gov.bnl.star.offline.scheduler.catalog.PhysicalFile;
026
027 import java.util.*;
028
029 public class FileAssignment {
030 private ListMap filemap = new ListMap();
031 private int minFiles;
032 private int maxFiles;
033 private boolean noMin;
034 private boolean noMax;
035
036 /** Create a new empty distribution, specifying the limits on how many files
037 * to assign to a single process
038 * @param minFiles minimum number of files to assign to a process
039 * @param maxFiles maximum number of files to assign to a process
040 */
041 public FileAssignment(int minFiles, int maxFiles) {
042 this.minFiles = minFiles;
043 this.maxFiles = maxFiles;
044
045 if (minFiles == -1) {
046 noMin = true;
047 }
048
049 if (maxFiles == -1) {
050 noMax = true;
051 }
052 }
053
054 /** True if the correct assignment can be divided into processes and
055 * dispatched correctly.
056 * @return false if the filse on any location can't be divided correctly
057 */
058 public boolean isValid() {
059 if (noMin) {
060 return true;
061 }
062
063 Iterator iter = getLocations().iterator();
064
065 while (iter.hasNext()) {
066 Location location = (Location) iter.next();
067
068 if (isValid(location) == false) {
069 return false;
070 }
071 }
072
073 return true;
074 }
075
076 /** True if the files assigned to the location can be divided in to a valid
077 * process.
078 * @param location location to check
079 * @return false if the filse on the location can't be divided correctly
080 */
081 public boolean isValid(Location location) {
082 return needsMoreFiles(location) == 0;
083 }
084
085 /** Returns the list of locations on which the files can't be divided in
086 * valid processes.
087 * @return a list of Location objects
088 */
089 public List getInvalidLocations() {
090 List invalids = new ArrayList();
091 Iterator iter = getLocations().iterator();
092
093 while (iter.hasNext()) {
094 Location location = (Location) iter.next();
095
096 if (isValid(location) == false) {
097 invalids.add(location);
098 }
099 }
100
101 return invalids;
102 }
103
104 /** Returns a printable summary of the current assignment, stating the
105 * total number of locations, and the number of invalid locations.
106 * @return a short summary of the locations
107 */
108 public String getSummary() {
109 StringBuffer summary = new StringBuffer();
110 summary.append(getLocations().size()).append(" location, of which ");
111 summary.append(getInvalidLocations().size()).append(" invalid: ")
112 .append(getInvalidLocations());
113
114 return summary.toString();
115 }
116
117 /** A full description of the current assignment, in a human readable
118 * form, contaning the number of files and processes for all the locations.
119 * @return a full report of the file distribution
120 */
121 public String getReport() {
122 StringBuffer report = new StringBuffer();
123
124 List invalids = new ArrayList();
125 Iterator iter = getLocations().iterator();
126
127 while (iter.hasNext()) {
128 Location location = (Location) iter.next();
129
130 if (isValid(location) == false) {
131 invalids.add(location);
132 }
133
134 report.append(location);
135 report.append(": nFiles ").append(getFiles(location).size());
136 report.append(" - nProc ").append(minProcs(location));
137
138 if (isValid(location)) {
139 report.append(" - valid");
140 } else {
141 report.append(" - INVALID");
142 }
143
144 report.append("\n");
145 }
146
147 return report.toString();
148 }
149
150 /** Returns the minimum number of process to dispatch on the location to
151 * cover all the files. It is the number of files divided by maxFiles, rounded
152 * up to the next integer. This number might not satisfy the minFiles
153 * requirements.
154 * @param location the location in the assignment
155 * @return the number of processes on which the list will be split
156 */
157 public int minProcs(Location location) {
158
159
160 if (noMax) return 1;
161 /*
162 if (noMax || (maxFiles == 0)) return 1;
163 */
164
165 int nFiles = getFiles(location).size();
166 int nProc = nFiles / maxFiles;
167 int mod = nFiles % maxFiles;
168
169 if (mod > 0) {
170 nProc++;
171 }
172
173 return nProc;
174 }
175
176 /** Returns how many are to be assigned to the location to make the assignment
177 * valid.
178 * @param location the location to check
179 * @return the number of files needed to meet the min requirement; 0 if the
180 * requirements are met
181 */
182 public int needsMoreFiles(Location location) {
183 if (noMin) {
184 return 0;
185 }
186
187 int minTotalFiles = minProcs(location) * minFiles;
188 int nFiles = getFiles(location).size();
189 int needed = minTotalFiles - nFiles;
190
191 if (needed > 0) {
192 return needed;
193 }
194
195 return 0;
196 }
197
198 /** Returns how many files are to be deassigned from the location to
199 * make the assignment valid.
200 * @param location the location to check
201 * @return the number of files to remove to meet the max files requirements;
202 * 0 if the requirements are met
203 */
204 public int needsLessFiles(Location location) {
205
206 //if (noMax) { //this is could be a bug. More testing is needed
207 // return 0;
208 //}
209
210 if (isValid()) {
211 return 0;
212 }
213
214 int nFiles = getFiles(location).size();
215 int maxTotalFiles = (minProcs(location) - 1) * maxFiles;
216 int needed = nFiles - maxTotalFiles;
217
218 System.out.println("maxTotalFiles = " + maxTotalFiles + " nFiles = " + nFiles);
219
220 return needed;
221 }
222
223 /** Returns how many files can be assigned to the location without changing
224 * the number of processes.
225 * @param location location to check
226 * @return max number of files that can be added
227 */
228 public int canAdd(Location location) {
229 if (noMax) {
230 // No maximum: can add everything
231 return Integer.MAX_VALUE;
232 }
233
234 int maxTotalFiles = (minProcs(location)) * maxFiles;
235
236 return maxTotalFiles - getFiles(location).size();
237 }
238
239 /** Returns how many files can be deassigned to the location without changing
240 * the number of processes.
241 * @param location location to check
242 * @return max number of files that be removed
243 */
244 public int canRemove(Location location) {
245 // TODO This is not quite right
246 if (noMin) {
247 return getFiles(location).size();
248 }
249
250 int minTotalFiles = (minProcs(location)) * minFiles;
251 int remove = minTotalFiles - getFiles(location).size();
252
253 if (remove > 0) {
254 return remove;
255 }
256
257 return 0;
258 }
259
260 /** Returns the locations to which something was assigned.
261 * @return a Set of Location objects
262 */
263 public Set getLocations() {
264 return filemap.getKeys();
265 }
266
267 /** Returns a list of URL of the files assigned to that location (a location
268 * can be a set of nodes).
269 * @param location the location to check
270 * @return a List of URL objects
271 */
272 public List getFiles(Location location) {
273 return filemap.getList(location);
274 }
275
276 /** Returns the list of files assigned to a particular process of one
277 * location.
278 * @param location the location to check
279 * @param processIndex the process number
280 * @return a List of URL objects
281 */
282 public List getFiles(Location location, int processIndex) {
283 int nProc = minProcs(location);
284 List total = getFiles(location);
285
286 if (nProc <= processIndex) {
287 throw new ArrayIndexOutOfBoundsException(
288 "Process index requested is too high");
289 }
290
291 // Calculating how many files. The modulus tells us how many processes
292 // are going to have one process more than the others
293 int filesPerProcess = total.size() / nProc;
294 int mod = total.size() % nProc;
295 int nFiles = filesPerProcess;
296
297 if (processIndex < mod) {
298 nFiles++;
299 }
300
301 // Calculating the offset on the list. Again, the modulus is used to
302 // know how many preeceding processes had one file more
303 int index = (filesPerProcess * processIndex) +
304 Math.min(processIndex, mod);
305
306 return total.subList(index, index + nFiles);
307 }
308
309 /** Adds the file to the assignment, the host is used as location
310 * @param file the URL of the file
311 */
312 public void add(PhysicalFile file) {
313 filemap.add(Location.getLocation(file), file);
314 }
315
316 /** Assigns the file to the location.
317 * @param location the location to which to assign the file
318 * @param file the URL of the file
319 */
320 public void add(Location location, PhysicalFile file) {
321 filemap.add(location, file);
322 }
323
324 /** Adds a collection of files to the assignment. It will use the
325 * add(URL) method iteratively.
326 * @param coll a Collection of URL objects
327 */
328 /*public void add(Collection coll) {
329 Iterator iter = coll.iterator();
330
331 while (iter.hasNext()) {
332 PhysicalFile file = (PhysicalFile) iter.next();
333 add(file);
334 }
335 }*/
336
337 /** Adds an entire FileAssignment to the present.
338 * @param assignment the assignment to add to this
339 */
340 public void addAll(FileAssignment assignment) {
341 filemap.addAll(assignment.filemap);
342 }
343
344 /** Adds a list of files to the assignment.
345 * @param col a Collection of PhysicalFile objects
346 */
347 public void addAllPhysical(Collection col) {
348 Iterator iter = col.iterator();
349
350 while (iter.hasNext()) {
351 add(((PhysicalFile) iter.next()));
352 }
353 }
354
355 /** Adds a list of files to the specified location.
356 * @param location the location to which to add to
357 * @param col a Collection of PhysicalFile objects
358 */
359 public void addAllPhysical(Location location, Collection col) {
360 Iterator iter = col.iterator();
361
362 while (iter.hasNext()) {
363 add(location, ((PhysicalFile) iter.next()));
364 }
365 }
366
367 /** Removes the file from the location.
368 * @param location the location from which to remove the file
369 * @param file the file to remove
370 */
371 public void remove(Location location, PhysicalFile file) {
372 filemap.remove(location, file);
373 }
374
375 /** Removes a set of file a location.
376 */
377 public void removeAllPhysical(Location location, Collection col) {
378 Iterator iter = col.iterator();
379
380 while (iter.hasNext()) {
381 remove(location, ((PhysicalFile) iter.next()));
382 }
383 }
384
385 public void orderFiles(Comparator comp) {
386 Set location = getLocations();
387 Iterator iter = location.iterator();
388
389 while (iter.hasNext()) {
390 List files = getFiles((Location)iter.next());
391 Collections.sort(files, comp);
392 }
393 }
394
395 }