Können wir den Seitenersatz-Algorithmus für die LRU (zuletzt verwendete Seite) in O(1) (d. H. Konstante Zeit) erhalten?Können wir in O (1) den LRU-Seitenersetzungsalgorithmus erhalten?
Bitte geben Sie den Algorithmus wenn möglich.
Eine doppelt verknüpfte Liste kann eine LRU-Warteschlange mit O (1) -Operationen implementieren. Benutzte Knoten können von ihrem alten Standort getrennt und in konstanter Zeit wieder mit dem Kopf der Warteschlange verbunden werden.
Beachten Sie, dass Sie, wenn Sie es als Seitenersetzungsmethode verwenden möchten, immer noch herausfinden müssen, wie die MMU-Stats verwendet werden, um die Warteschlange effizient zu aktualisieren.
Schöne Antwort, aber wollte nur den Fragesteller darauf hinweisen, dass diese Methode wegen der Zeitbeschränkungen, die sie auferlegt, praktisch von keinem Betriebssystem verwendet wird. –
Ja, Sie kümmern sich nicht wirklich um die genaue Reihenfolge, in der die Seiten verwendet wurden. Was Sie wollen, ist eine Liste von "nicht kürzlich verwendeten" Seiten, die Sie bei Bedarf rausschmeißen können. Praktisch, Sie aktualisieren Ihre Seitenersetzungsstatistiken Batch-Stil, mit den Seitenzugriffsflags der MMU - aber beachten Sie, dass eine doppelt verknüpfte LRU-Warteschlange * eine praktische Datenstruktur für diesen Zweck ... – comingstorm
ist, aber um die verwendeten Knoten zu finden wir müssen die Liste durchqueren ... das wird O (n) Zeit brauchen ..... korrigiere mich, wenn ich falsch bin .. – Amnesiac
In Wikipedia gibt es references zu mehreren LRU-Seitenalgorithmen, einschließlich Links zu Implementierungen. Die Optionen sind:
Hausaufgaben? Was hast du bisher versucht? –