地址映象和变换（一）之主存虚存

地址映象：是将每个虚存单元按某种规则装入实存，即建立多用户虚地址与实存地址之间的对应关系。
地址变换：是程序按照这种映象关系装入实存后，在执行时，多用户虚地址如何变换成对应的实存地址。

页面争用（实页冲突）：发生两个以上的虚页想要进入主存中同一个页面位置的现象。

由于虚存空间远远大于实存空间，因此页式虚拟存储器常采用全相联映像。

替换算法

当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。

• 随机算法（RAND）：用软的或硬的随机数产生器来形成主存重要被替换页的页号。
  简单，易于实现
  没有利用历史信息
  命中率低，很少使用
• 先进先出（FIFO）：选择最早装入主存的页作为被替换的页。
  配置计数器字段
  虽然利用历史信息，但不一定反映出程序的局部性
• 近期最少使用（LRU）：选择近期最少访问的页作为被替换的页。
  配有计数器字段
  比较正确反映程序的局部性
• 优化替换算法（OPT）：在时刻t找出主存中每个页将要用到时刻ti，然后选择其中ti-t最大的那一页作为替换页。
  理想化算法

例子：设有一道程序，有1至5共5页，执行时的地址流为：
2，3，2，1，5，2，4，5，3，2，5，2

主存页为3。分别采用FIFO、LRU、OPT算法。

其中LRU是以历史信息为判断依据，而OPT则建立在对未来使用页的预知（故称理想算法）。