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