Shemaforos

6.16 Algoritmos de ubicación., Algoritmos de remoción de páginas: Optimo, FIFO, LRU (LFU y MFU)
Algoritmo de reemplazo de páginas óptimo Este algoritmo debe de tener el menor índice de fallos de página de todos los algoritmos. En teoría, este algoritmo debe de reemplazar la página que no va a ser usada por el periodo más largo de tiempo. Desafortunadamente, el algoritmo de reemplazo óptimo esfácil en teoría, pero prácticamente imposible de implementar, dado que requiere conocer a futuro las necesidades del sistema. Tal algoritmo existe y ha sido llamado OPT o MIN, pero se usa únicamente para estudios de comparaciones. Por ejemplo, puede resultar muy útil saber que aunque algún nuevo algoritmo no sea óptimo, está entre el 12.3% del óptimo y entre el 4.7% en promedio. OPTIMAL Thisalgorithm should have the lowest rate of page faults for all algorithms. In theory, this algorithm must replace the page will not be used for the longest period of time. Unfortunately, the optimal replacement algorithm is easy in theory, but practically impossible to implement, as it requires to meet future system needs. Such an algorithm exists and has been called OPT or MIN, but is only used forcomparison studies. For example, it can be very helpful to know that although some new algorithm is not optimal, is among the 12.3% of the optimal and between 4.7% on average. Algoritmo de reemplazo "Primero en entrar, primero en salir" (FIFO) El algoritmo más sencillo para remplazo de páginas es el FIFO (First In – First Out). Este algoritmo asocia a cada página el momento en que ésta fue traída amemoria. Cuando una página debe ser reemplazada se selecciona a la más antigua. No es estrictamente necesario registrar el momento de entrada de la página a memoria, sino que se puede crear una cola en la que se van agregando las páginas conforme van llegando a la memoria. Cuando se debe eliminar una página, se selecciona la que está al frente de la lista (o sea, la más antigua de la lista). Cuandollega una página nueva, se inserta en la parte trasera de la cola. Al igual que el algoritmo aleatorio, este algoritmo es fácil de comprender y de programar. Sin embargo, su desempeño no siempre es del todo bueno. La página reemplazada puede ser un módulo de inicialización que fue usado hace mucho tiempo y ya no se tiene necesidad de él. Por otro lado, puede contener una variable de uso muy frecuenteque fue inicializada de manera temprana y está en uso constante. FIFO The simplest algorithm for page replacement is the FIFO (First In - First Out). This algorithm associates with each page the time it was brought to memory. When a page is selected to be replaced at the earliest. It is not strictly necessary to record the time of entry to memory page, but you can create a queue in which pagesare being added as they come to mind. When to delete a page, select the one at the front of the list (ie, the oldest of the list). When it reaches a new page is inserted at the rear of the queue. Like the random algorithm, this algorithm is easy to understand and to program. However, its performance is not always all good. The page can be replaced with a module initialization was used long ago andno longer have need of it. On the other hand, can contain a very frequent use variable that was initialized early and is in constant use. Algoritmo de reemplazo de páginas "la de menor uso reciente" (LRU) Este algoritmo es una buena aproximación al óptimo y se basa en al observación de que las páginas de uso frecuente en las últimas instrucciones se utilizan con cierta probabilidad en lassiguientes. De la misma manera, es probable que las páginas que no hayan sido utilizadas durante mucho tiempo permanezcan sin uso por bastante tiempo. Implementando el algoritmo con esta base, al ocurrir un fallo de página, se elimina la página que no haya sido utilizada durante el tiempo más grande. De ahí su denominación: menor uso reciente (LRU - Least Recent Use). A diferencia de los algoritmos...