aboutsummaryrefslogtreecommitdiff
path: root/lru.py
blob: 76af4c4139af35c97686ebecaf5939f2f1f02502 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#!/usr/bin/env python3

# UPEM / System programming / Project: Memory paging simulator
# Pacien TRAN-GIRARD, Adam NAILI

from mem import Memory
from pageexception import *


class LruPaginator:
  def __init__(self, mem):
    self.mem = mem
    self._global_counter = 1
    self._check_table = [0 for _ in range(len(mem.main) + len(mem.virt))]
    self._main_cursor = 0

  def _update_check_table(self, page):
    """
    >>> lru = LruPaginator(Memory(3,5))
    >>> page = 3
    >>> lru._update_check_table(page)
    >>> print(lru._check_table[page])
    1
    >>> print(lru._global_counter)
    2
    """
    self._check_table[page] = self._global_counter
    self._global_counter += 1

  def _check_where_to_replace(self):
    """
    >>> lru = LruPaginator(Memory(3, 5))
    >>> lru._check_where_to_replace()
    >>> print(lru._main_cursor)
    0
    >>> lru.mem.main = [3, 4, 2]
    >>> lru._check_table = [1, 3, 6, 4, 5, 0, 0, 0]
    >>> lru._check_where_to_replace()
    >>> print(lru._main_cursor)
    0
    """
    for page in self.mem.main:
      if page is None:
        self._main_cursor = self.mem.main.index(page)
        return

    min = self._check_table[self.mem.main[0]]
    self._main_cursor = 0

    for page in self.mem.main:
      if min > self._check_table[page]:
        min = self._check_table[page]
        self._main_cursor = self.mem.main.index(page)

  def _put_main(self, page):
    self._check_where_to_replace()
    overwritten = self.mem.main[self._main_cursor]
    self.mem.main[self._main_cursor] = page
    self._update_check_table(page)
    return overwritten

  def load(self, page):
    if not self.mem.page_in_range(page): raise PageException
    if page in self.mem.main:
      self._update_check_table(page)
      return

    if page in self.mem.virt: self.mem.remove_virt(page)
    overwritten = self._put_main(page)
    if overwritten is not None: self.mem.put_virt(overwritten)


if __name__ == "__main__":
  import doctest
  doctest.testmod()