root / trunk / libraries / libRaster / src / org / gvsig / raster / buffer / cache / LRUAlgorithm.java @ 11074
History | View | Annotate | Download (8.96 KB)
| 1 | 11074 | nacho | /* gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana
|
|---|---|---|---|
| 2 | *
|
||
| 3 | * Copyright (C) 2006 IVER T.I. and Generalitat Valenciana.
|
||
| 4 | *
|
||
| 5 | * This program is free software; you can redistribute it and/or
|
||
| 6 | * modify it under the terms of the GNU General Public License
|
||
| 7 | * as published by the Free Software Foundation; either version 2
|
||
| 8 | * of the License, or (at your option) any later version.
|
||
| 9 | *
|
||
| 10 | * This program is distributed in the hope that it will be useful,
|
||
| 11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
| 12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
| 13 | * GNU General Public License for more details.
|
||
| 14 | *
|
||
| 15 | * You should have received a copy of the GNU General Public License
|
||
| 16 | * along with this program; if not, write to the Free Software
|
||
| 17 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
||
| 18 | */
|
||
| 19 | |||
| 20 | package org.gvsig.raster.buffer.cache; |
||
| 21 | |||
| 22 | import java.io.IOException; |
||
| 23 | |||
| 24 | import org.gvsig.raster.buffer.IBand; |
||
| 25 | import org.gvsig.raster.buffer.RasterBand; |
||
| 26 | import org.gvsig.raster.buffer.RasterBuffer; |
||
| 27 | import org.gvsig.raster.dataset.IBuffer; |
||
| 28 | |||
| 29 | /*
|
||
| 30 | * TODO: OPTIMIZACION: Trabajo de optimizaci?n en la velocidad e acceso a cach?.
|
||
| 31 | * TODO: FUNCIONALIDAD: Acabar de implementar los m?todos de acceso a datos, intercambio de bandas, etc...
|
||
| 32 | */
|
||
| 33 | /**
|
||
| 34 | * Esta clase contiene el algoritmo de reemplazo de trozos de cach? LRU
|
||
| 35 | *
|
||
| 36 | * @author Nacho Brodin (nachobrodin@gmail.com)
|
||
| 37 | *
|
||
| 38 | */
|
||
| 39 | public class LRUAlgorithm { |
||
| 40 | |||
| 41 | private Cache cache = null; |
||
| 42 | |||
| 43 | /**
|
||
| 44 | * Constructor. Asigna la cach? para poder aplicar el algoritmo.
|
||
| 45 | * @param cache
|
||
| 46 | */
|
||
| 47 | public LRUAlgorithm(Cache cache){
|
||
| 48 | this.cache = cache;
|
||
| 49 | } |
||
| 50 | |||
| 51 | /**
|
||
| 52 | * Asigna el objeto cach?.
|
||
| 53 | * @param cache
|
||
| 54 | */
|
||
| 55 | public void setCache(Cache cache) { |
||
| 56 | this.cache = cache;
|
||
| 57 | } |
||
| 58 | |||
| 59 | /**
|
||
| 60 | * Funci?n que controla para cada l?nea si la p?gina a la que accede est? cacheada o no
|
||
| 61 | * . Es la encargada de realizar los reemplazos o cargar la p?gina en el buffer de "p?gina
|
||
| 62 | * actualmente accedida" (accessPage de la clase Cache)
|
||
| 63 | * @param line L?nea del raster a la que se est? accediendo
|
||
| 64 | * @param readOnly ser? true si el acceso que se est? realizando es de lectura y false si se
|
||
| 65 | * est? escribiendo alg?n dato
|
||
| 66 | */
|
||
| 67 | public void cacheAccess(int line, boolean readOnly)throws InvalidPageNumberException{ |
||
| 68 | int pag = line >> cache.getBitsPag();
|
||
| 69 | if(cache.isInCache(pag)){
|
||
| 70 | if(cache.getNumberInAccessPage() != pag)
|
||
| 71 | loadPage(pag, readOnly); |
||
| 72 | }else{
|
||
| 73 | replacePage(pag + 1, readOnly, false); |
||
| 74 | replacePage(pag, readOnly, true);
|
||
| 75 | } |
||
| 76 | } |
||
| 77 | |||
| 78 | /**
|
||
| 79 | * Carga la p?gina desde cach? al buffer actualmente en uso. Esta operaci?n no lleva
|
||
| 80 | * cambio de datos sino que solo es un cambio de punteros. La secuencia de operaciones es:
|
||
| 81 | * <UL>
|
||
| 82 | * <LI>Cargar la p?gina como accedida</LI>
|
||
| 83 | * <LI>Asignar n?mero a la p?gina accedida</LI>
|
||
| 84 | * <LI>Actualizar la antig?edad de accesos.Se incrementar? uno en todas las p?ginas del
|
||
| 85 | * conjunto y se pondr? a 0 la p?gina accedida.</LI>
|
||
| 86 | * <LI>Poner a 0 el valor de lastAccess de la p?gina cargada. Esto hace que tenga m?nima
|
||
| 87 | * prioridad en la politica de reemplazamiento.</LI>
|
||
| 88 | * <LI>Poner a false el flag de p?gina modificada si el par?metro readOnly es false.</LI>
|
||
| 89 | * </UL>
|
||
| 90 | * @param nPag N?mero de p?gina del raster a la que se intenta acceder.
|
||
| 91 | * @param readOnly ser? true si el acceso que se est? realizando es de lectura y false si se
|
||
| 92 | * est? escribiendo alg?n dato.
|
||
| 93 | */
|
||
| 94 | private void loadPage(int nPag, boolean readOnly)throws InvalidPageNumberException{ |
||
| 95 | PageBuffer buf = cache.getPageBufferFromNumberRasterPage(nPag); |
||
| 96 | int[] cacheGroupPage = cache.getNumberGroupFromNumberRasterPage(nPag); |
||
| 97 | if(buf != null && cacheGroupPage != null){ //Comprueba que el n?mero de p?gina sea correcto para la cach?. |
||
| 98 | cache.setAccessPage(buf, nPag); |
||
| 99 | cache.updateLastAccess(cacheGroupPage[0]);
|
||
| 100 | cache.setZeroInLastAccess(cacheGroupPage[0], cacheGroupPage[1]); |
||
| 101 | if(!readOnly)
|
||
| 102 | cache.setModify(cacheGroupPage[0], cacheGroupPage[1]); |
||
| 103 | }else
|
||
| 104 | throw new InvalidPageNumberException(""); |
||
| 105 | //System.out.println("LOAD: "+nPag);
|
||
| 106 | } |
||
| 107 | |||
| 108 | /**
|
||
| 109 | * <P>
|
||
| 110 | * Cuando se accede a una p?gina que no est? cacheada necesitamos cargarla en cach? antes de
|
||
| 111 | * acceder a ella. Si hay un hueco libre en su conjunto se meter? en este pero sino habr?
|
||
| 112 | * que reemplazar una ocupada. Para esto habr? que localizar el conjunto donde va
|
||
| 113 | * destinada y luego la posici?n del conjunto donde se cargar? localizando cual es el
|
||
| 114 | * elemento del conjunto que hace m?s tiempo que se accedi?.
|
||
| 115 | * </P>
|
||
| 116 | * <P>
|
||
| 117 | * Si el elemento es insertado en un hueco la secuencia es la siguiente:
|
||
| 118 | * </P>
|
||
| 119 | * <UL>
|
||
| 120 | * <LI>Obtenemos la siguiente p?gina vacia.</LI>
|
||
| 121 | * <LI>La cargamos de datos.</LI>
|
||
| 122 | * <LI>Se asigna como p?gina accedida</LI>
|
||
| 123 | * <LI>Ponemos true en su posici?n en el vector cacheada</LI>
|
||
| 124 | * <LI>Asignamos el n?mero de p?gina de raster que hemos cargado en esa posici?n de la cach?.</LI>
|
||
| 125 | * <LI>Incrementamos en 1 todos los valores de ?ltimo acceso de las p?ginas del grupo.</LI>
|
||
| 126 | * <LI>Ponemos a 0 su ?ltimo acceso</LI>
|
||
| 127 | * <LI>Si el acceso es para escritura ponemos el flag de p?gina modificada a true.</LI>
|
||
| 128 | * </UL>
|
||
| 129 | * <P>
|
||
| 130 | * Si se reemplaza una p?gina la secuencia es la siguiente:
|
||
| 131 | * </P>
|
||
| 132 | * <UL>
|
||
| 133 | * <LI>Incrementamos en 1 todos los valores de ?ltimo acceso de las p?ginas del grupo y
|
||
| 134 | * obtenemos la posici?n de la p?gina de reemplazo.</LI>
|
||
| 135 | * <LI>Ponemos a false la p?gina que va a sacarse de cach?</LI>
|
||
| 136 | * <LI>Si ha sido modificada la p?gina que va a sacarse de cach? se vuelca a disco</LI>
|
||
| 137 | * <LI>Ponemos el flag de modificada para la p?gina sacada a disco a false.</LI>
|
||
| 138 | * <LI>Cargamos la p?gina de cach? de datos.</LI>
|
||
| 139 | * <LI>Asignamos el n?mero de p?gina de raster que hemos cargado en esa posici?n de la cach?.</LI>
|
||
| 140 | * <LI>Se asigna como p?gina accedida</LI>
|
||
| 141 | * <LI>Ponemos true en su posici?n en el vector cacheada</LI>
|
||
| 142 | * <LI>Ponemos a 0 su ?ltimo acceso</LI>
|
||
| 143 | * <LI>Si el acceso es para escritura ponemos el flag de p?gina modificada a true.</LI>
|
||
| 144 | * </UL>
|
||
| 145 | * @param nPag N?mero de p?gina que est? siendo accedida
|
||
| 146 | * @param readOnly ser? true si el acceso que se est? realizando es de lectura y false si se
|
||
| 147 | * est? escribiendo alg?n dato.
|
||
| 148 | * @param n ser? true si el acceso se est? haciendo a la p?gina n y false si se est? haciendo a
|
||
| 149 | * la n+1.
|
||
| 150 | */
|
||
| 151 | private void replacePage(int nPag, boolean readOnly, boolean n){ |
||
| 152 | int group = nPag % cache.getNGroups();
|
||
| 153 | |||
| 154 | if(nPag >= cache.getNTotalPags())
|
||
| 155 | return;
|
||
| 156 | |||
| 157 | //Insertamos en un hueco
|
||
| 158 | |||
| 159 | if(insertInAHole(group, readOnly, nPag, n))
|
||
| 160 | return;
|
||
| 161 | |||
| 162 | //Reemplazamos una existente
|
||
| 163 | |||
| 164 | int posInGroupPageToReplace = cache.updateLastAccess(group); //Se actualizan los indices y se obtiene la p?gina a reemplazar |
||
| 165 | |||
| 166 | cache.setZeroInLastAccess(group, posInGroupPageToReplace); |
||
| 167 | int rasterPageToReplace = cache.getRasterPageNumberInPosition(group, posInGroupPageToReplace);
|
||
| 168 | |||
| 169 | //Sacamos la antigua
|
||
| 170 | cache.setPageAsNotLoadInCache(rasterPageToReplace); |
||
| 171 | if(cache.isModified(group, posInGroupPageToReplace)){
|
||
| 172 | try {
|
||
| 173 | cache.savePage(group, posInGroupPageToReplace, rasterPageToReplace); //Volcamos disco
|
||
| 174 | cache.unsetModify(group, posInGroupPageToReplace); |
||
| 175 | } catch (IOException e) { |
||
| 176 | System.err.println("No se ha podido salvar la p?gina de cach?."); |
||
| 177 | e.printStackTrace(); |
||
| 178 | } |
||
| 179 | } |
||
| 180 | |||
| 181 | //Insertamos la nueva
|
||
| 182 | cache.loadPage(group, posInGroupPageToReplace, nPag); //Cargamos de nuevo el buffer
|
||
| 183 | cache.setRasterPageNumberInPosition(group, posInGroupPageToReplace, nPag); |
||
| 184 | cache.setPageAsLoadInCache(nPag); //Pone true en su posici?n en el vector cacheada
|
||
| 185 | PageBuffer pb = cache.getPageBuffer(group, posInGroupPageToReplace); |
||
| 186 | |||
| 187 | if(n){
|
||
| 188 | if(!readOnly)
|
||
| 189 | cache.setModify(group, posInGroupPageToReplace); |
||
| 190 | cache.setAccessPage(pb, nPag); //Asigna como accedida
|
||
| 191 | } |
||
| 192 | //System.out.println("REPLACE: "+nPag);
|
||
| 193 | } |
||
| 194 | |||
| 195 | /**
|
||
| 196 | * Comprueba si hay alg?n hueco en el que insertar y si es as? se inserta en el y devuelve
|
||
| 197 | * true.
|
||
| 198 | * @param group conjunto donde hay que buscar para la inserci?n
|
||
| 199 | * @param readOnly si es true la operaci?n es de solo consulta y si es false la operaci?n
|
||
| 200 | * est? modificando alg?n valor de la p?gina a insertar
|
||
| 201 | * @param nPag N?mero de p?gina a cargar
|
||
| 202 | * @return true si se ha insertado en un hueco y false si no se ha insertado
|
||
| 203 | */
|
||
| 204 | private boolean insertInAHole(int group, boolean readOnly, int nPag, boolean n){ |
||
| 205 | PageBuffer pb = null;
|
||
| 206 | for(int i = 0; i < cache.getPagsPerGroup(); i++){ |
||
| 207 | if(cache.getLastAccess()[group][i] == -1){ |
||
| 208 | |||
| 209 | //Pone true en su posici?n en el vector cacheada
|
||
| 210 | pb = cache.getPageBuffer(group, i); |
||
| 211 | cache.loadPage(group, i, nPag); //Sube la p?gina a cach?
|
||
| 212 | cache.setRasterPageNumberInPosition(group, i, nPag);//Asigna el n?mero de p?g a una posici?n de cach?
|
||
| 213 | cache.setPageAsLoadInCache(nPag); |
||
| 214 | cache.updateLastAccess(group); |
||
| 215 | cache.setZeroInLastAccess(group, i); |
||
| 216 | if(n){ //La n+1 no se carga como accedida ni se pone a 0 su contador de ?ltima accedida |
||
| 217 | if(!readOnly)
|
||
| 218 | cache.setModify(group, i); |
||
| 219 | cache.setAccessPage(pb, nPag); //Asigna como accedida
|
||
| 220 | } |
||
| 221 | //System.out.println("INSERT: "+nPag);
|
||
| 222 | return true; |
||
| 223 | } |
||
| 224 | } |
||
| 225 | return false; |
||
| 226 | } |
||
| 227 | |||
| 228 | } |