存储管理

• 虚拟存储器
  内存有限，不能保证要运行的程序都能装入
  程序中的地址与实际物理地址不同
         ▲编译程序不知道实际运行机器的内存使用状况
         ▲动态连接的程序编译时不知道它将被连接到怎样的程序中 
         …  …
  虚拟地址空间——以0为起始地址的线性或多维地址空间
  虚地址——虚拟地址空间中的地址
  虚拟存储器——将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器
  程序中的地址——虚地址
  程序执行需要进行虚地址到实际物理地址的地址变换
• 存储管理的任务
  内存空间的管理、分配与回收
  内存共享
  存储保护与安全
  内存“扩充”
  地址变换
  
• 分区存储管理
  系统预先把内存用户区划分为若干个连续区域，每个区域称为一个分区。分区大小可以相等，也可以不等。一个进程占据一个分区
  优点：分配回收方便，适用于用户不多的小型系统；
  缺点：内存使用不充分，每一分区剩余部分无法利用
• 分区存储管理内存分配
  首先适配算法
  当接到内存申请时，查空闲块表，找到第一个不小于请求的空块，将其分割并分配
  特点：简单、快速分配
  最佳适配算法
  接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配
  特点：用最小空间满足要求
  最坏适配算法
  接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配
  特点：当分割后空闲块仍为较大空块

    三种分配方案比较：最佳分配适用于请求分配的内存范围较广的系统。因为按照最佳分配的原来进行分配时，总是找大小最接近请求的空间，因此系统中可能产生存储量很小而每次都无法利用的小空间，同时也保留那些空间很大的片段，这样，不同的空闲片段将差别巨大，大片区域非常大，小片区域非常小而无法利用。最差适配则与之相反，将会使整个区域的空闲片段的大小趋于均匀，因此其适用于请求内存大小差别不是很大的系统。而首次适配是随机的，因此介于两者之间。

 

    碎片问题
    经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。
   回收：进程结束后，将使用的空间释放放并插入到可用分区表/链中。

•  页式存储管理
  基本思想（工作原理）
  把进程的虚拟地址空间划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址。进程的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址
  内存空间
  按页的大小划分为大小相等的区域，称为页面（内存块，物理页面，页框）
  内存分配
  以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻
  虚地址：页号+页内地址

   

     静态页式管理
        页表：系统为每个进程建立一个页表，页表给出逻辑页和具体内存页面之间的对应关系；页表放在内存，属于进程的现场信息
       请求表：系统通过请求表来管理每个进程/作业的内存请求和内存分配情况
       存储页面表：系统通过该表识别内存页面的分配情况

    预调入页式管理
        系统对外存中的页面进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们调入和调出内存

 

    请求页式存储管理
         请求页存储管理只让进程或作业的部分程序和数据驻留在内存中，因此，在执行过程中需要动态地将外存中的页调入内存
        两个基本问题是
           怎样发现这些不在内存中的虚页：通过在页表中设置中断位及虚页在外存中的始址
           怎样处理这种情况（采用何种方法把所缺的页调入内存，以及当内存中没有空闲页面时怎么办）：淘汰换页算法

 

• 先进先出算法（first input first output,FIFO）
  先进入内存的页面先淘汰。实现是在页表中登记进入的次序，并将各个已分配的页面按分配时间顺序连接起来，组成FIFO队列。优点是实现简单，缺点是遇到常用的页效率低下，并可能产生Belady现象
  Belady：现象是指分配的页面数增多，缺也次数反而增加的现象。
• 
  循环检测法
  让循环多的页面留驻内存，计算机采用记录页面住留内存期间对该页的访问时间，t为该页上一次访问时间，T为该页第二次访问时间，选用相对时间（t-T）最大的淘汰。优点是适合循环多的大程序；缺点是系统开销大。
• 最近最少使用页面先淘汰（least recently useed,LRU）
  该算法的基本思想是：当要淘汰某页时，选择离当时时间最近的一段时间内最久没有使用过的页面先淘汰。该算法的出发点是，如果某页被访问了，则可能它马上还要被访问，或者反过来说，如果某页面很长时间未被访问，则它在最近一段时间也不会被访问。LRU的实现是一件十分困难的事情，我们一般采用它的近似算法。
• 最不经常使用的页面先淘汰（least frequent used,LFU）
  该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。
• 最近没有使用的页面先淘汰（not used recently,NUR）
  它是上述算法的一种简化，利用在页表中设置一个访问位即可实现，当某页被访问时，访问位置“1”，否则访问位置“0”当需要淘汰一页时，从那些访问位为“0”的页中选一页进行淘汰。系统周期性地对所有访问位清零。
• 随机数淘汰页面算法（random replacement algorithm）
  在系统设计人员无法确定那些页的访问概率较低时，随机地选择某个用户的页面进行淘汰也是一种方法。
• 最优淘汰算法（optimal replacement algorithm,OPT）
  它是一种理想的淘汰算法，系统预测作业今后要访问的页面，淘汰页是将来不被访问的页面或者最长时间后才能被访问的页面。这种算法是无法实现的，因为它要求必须预先知道每个进程的访问串。

     页式存储管理的优点: 虚存量大，适合多道程序运行，用户不必担心内存不够的调度操作。动态页式管理提供了内存与外存统一管理的虚存实现方式；内存利用率高，不常用的页面尽量不留在内存; 不要求作业连续存放，有效地解决了内存碎片问题。
     页式存储管理的缺点: 要进行页面中断，缺页中断等处理，系统开销较大；有可能产生“抖动”现象；地址变换机构复杂，一般采用硬件实现，增加了机器成本

• 
  段式存储管理
  段式存储管理的基本思想
  页式存储管理的不足
  由于页的划分固定，每页的内容无完整的意义，因此页式存储管理在不同作业或进程之间共享公用子程序和数

    据段变得非常困难——为什么？
     段式存储管理的基本思想
     把程序按内容或过程（函数）关系分成段，每段有自己的名字。
     一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。以段为单位分配内存，然后通过地址映射机构把段式虚拟存储地址转化为内存中的实际地址。经常访问的段驻留内存，在将来一段时间内不被访问的段放在外存，待需要时自动调入内存——实现二维虚拟存储器

    内存分配
    以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多 少），但各段之间可以不连续存放
内存的分配算法: 首先适配；最佳适配；最坏适配
管理用数据结构：段表，请求表，空闲表
虚地址：段号+段内地址

• 
  段页式存储管理

基本思想
页式管理的装入不收进程大小限制仅与页有关，但共享难于实现；段式管理受段的长度限制，但易于共享
结合段式与页式的优点——段页式管理
内存划分成页；虚存以段为单位划分为页
装入按页，调用按段
管理用数据结构
段表：（段号/名，页数，页表起始地址，访问位，存取方式）
页表：（页号，页面号，内/外存）
空闲页表：与页式管理类似
请求表：（进程号，段表起始地址）
问题：系统中有多少个段表？页表？空闲页表？请求表？

虚地址：（段号，页号，页内地址）

内存分配与回收
与页式管理相同
共享
利用段表实现共享——与段式管理一致
优缺点
页式与段式管理的折衷，系统开销大

• 
  程序局部性原理
  在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面
  时间局部性
  一条指令被执行了，则在不久的将来它可能再被执行
  空间局部性
  若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用

 

• 工作集（Working Set）模型
  基本思想
  根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断
  如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数 

–

    工作集
        •对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集

分享到：

很牛的求职经历(转) | 字符串匹配算法

• 2008-08-29 14:37
• 浏览 1252
• 评论(0)
• 查看更多