精华内容
下载资源
问答
  • 操作系统 请求分页存储管理

    千次阅读 2020-12-22 13:06:04
    请求分页存储管理优缺点 请求分页存储管理中的页表机制 系统需要解决的问题 系统如何获知进程当前所需页面不在主存 当发现缺页时,如何把所缺页面调入主存 当主存中没有空闲的页框时,为了要接受一个新页,需要...

    目录

    • 请求分页存储管理中的页表机制
    • 缺页中断机构
    • 地址转换
    • 页置换算法
    • 页分配和页置换策略
    • 工作集及抖动现象的消除
    • 请求分页存储管理的优缺点

    请求分页存储管理中的页表机制

    系统需要解决的问题

    • 系统如何获知进程当前所需页面不在主存
      当发现缺页时,如何把所缺页面调入主存
      当主存中没有空闲的页框时,为了要接受一个新页,需要把老的一页淘汰出去,根据什么策略选择欲淘汰的页面

    页表机制

    页描述子的扩充(页表机制 )

    • 状态位P(中断位)指示该页是在内存还是在外存
    • 访问位A 用于记录本页在一段时间内被访问的次数或记录本页在最近多长时间未被访问
    • 修改位M 表示该页在内存中是否被修改过
    • 外存地址 该页在外存上的地址,通常是物理块号

    在这里插入图片描述

    缺页中断机构

    • 在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断。相应的中断处理程序把控制转向缺页中断子程序,执行此子程序,即把所缺页面装入主存,然后处理机重新执行缺页时打断的指令。这时,就将顺利形成物理地址。
    • 缺页中断与一般中断的区别
      • 在指令执行期间产生和处理中断信号
      • 一条指令在执行期间可能产生多次缺页中断,例如:在请求分页存储管理中,当中断位反映出进程当前欲访问的页不在内存时(1表示该页在内存,0表示该页不在内存),就产生一次缺页中断。系统收到缺页中断信号后就立即执行相应的缺页中断处理程序。
      • 特点:
        (1)缺页中断的产生和处
        理(中断的响应)出现在一条指令的
        执行期内。
        (2)程序运行过程中,一条指令的执行
        期间内可能会产生多次缺页中断。
        在这里插入图片描述

    地址变换机构

    • 如果在快表中未找到该页的页表项,则应再到内存中去查找页表,再从找到的页表项中的状态位P,该页是否调入内存。其结果可能是:
      (1)该页已经调入内存,这是应将此页的页表项写入快表,当快表已满时,应先调出按某种算法所确定的页的页表项,然后再写入该页的页表项。
      (2)该页尚未调入内存,这时便应产生缺页中断,请求OS从外存中把该页调入内存。

    请求分页中的地址变换过程
    在这里插入图片描述
    页面调入过程

    在这里插入图片描述

    页置换算法

    缺页率

    • 假设一个进程的逻辑空间为n页,系统为其分配的内存物理块数为m(m≤n)
    • 如果在进程的运行过程中,访问页面成功(即所访问页面在内存中)的次数为S,访问页面失败(即所访问页面不在内存中,需要从外存调入)的次数为F,则该进程总的页面访问次数为A=S+F,那么该进程在其运行过程中的缺页率即为
      在这里插入图片描述

    影响缺页率的因素

    • 分配给进程的物理页面数
    • 页面本身的大小
    • 程序的编制方法
    • 页面淘汰算法

    最佳(Optimal)置换算法

    • 最佳置换算法是由Belady于1966年提出的一种理论上的算法
    • 其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面
    • 采用最佳置换算法,通常可保证获得最低的缺页率
    • 采用最佳置换算法可保证获得最低的缺页率。
    • 由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法也是无法实现的,但是可利用该算法去评价其它算法。

    利用最佳页面置换算法时的置换图

    在这里插入图片描述

    先进先出(FIFO)页面置换算法

    • 该算法总是淘汰最先进入内存的页面,即选择在内存中的驻留时间最久的页面予以淘汰。
    • 该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老页面。
    • 但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,含有全局变量、常用函数、例程等的页面,FIFO置换算法并不能保证这些页面不被淘汰。

    利用FIFO置换算法时的置换图

    在这里插入图片描述

    最近最久未使用(LRU)置换算法

    • 最近最久未使用(LRU)的页面置换算法,是根据页面调入内存后的使用情况。
    • 由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似。
    • LRU置换算法是选择最近最久未使用的页面予以淘汰。

    LRU页面置换算法
    在这里插入图片描述

    LRU置换算法的硬件支持
    • 把LRU算法作为页面置换算法是比较好的,它对于各种类型的程序都能适用,但实现起来有相当大的难度,因为它要求系统具有较多的支持硬件。所要解决的问题有:

      • 一个进程在内存中的各个页面各有多久时间未被进程访问;
        如何快速地知道哪一页最近最久未使用的页面。
        为此,须利用以下两类支持硬件:
      1. 移位寄存器:
        定时右移
      2. 栈:
        当进程访问某页时,将其移出压入“栈顶”,“栈底”换出。
    • 寄存器

      • 为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为
        在这里插入图片描述

      • 访问时将Rn-1位置成1,定时信号每隔一时间间隔右移一位,则具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面
        在这里插入图片描述
        某进程具有8个页面时的LRU访问情况
        在这里插入图片描述

      • 进程访问某页时,将该页面的页号从栈中移出,再压入栈顶
      • 用栈保存当前使用页面时栈的变化情况
        在这里插入图片描述

    最少使用(LFU: Least Frequently Used)置换算法

    • 为内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率

    • 该算法选择在最近使用最少的页面作为淘汰页
      在这里插入图片描述

    • 与最近最少用算法LRU的区别

      • 只考虑一段时间内使用的次数,而不管其使用的

    注意:这种算法并不能真正反映出页面的使用情况,因在每一时间间隔内只是用寄存器的一位来记录页的使用情况,因此访问1次和10000次是等效的

    简单的Clock置换算法

    • 利用Clock算法时,只须为每页设置一位访问位,在将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时,其访问位被置1。置换算法在选择一页淘汰时,只须检查其访问位。
      在这里插入图片描述
    • 各字段说明如下
      (1)状态位(存在位)P。用于指示该页是否调入内存,供程序访问时参考。
      (2)访问字段A。用于记录本页在一段时间内被访问的次数,或最近已有多长时间未被访问,提供给置换算法选择换出页面时参考
      (3)修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本,因此,若未被修改,在置换该页时就不须将该写回到外存上,以减少系统的开销和启动磁盘的次数;若已被修改,则必须将该页重写到外存上,以保证外存中所保留的始终是最新副本。
      (4)外存地址。用于指出该页在外存上的地址,通常是物理块号,供调入该页时使用。

    简单的CLOCK置换算法(近似的LRU算法)

    • 当采用简单的CLOCK算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列
    • 当某页被访问时,其访问位被置1
    • 置换算法在选择一页淘汰时,只需检查页的访问位,是0换出,是1重新置0且暂不换出,再按FIFO检查下一个页面。检查到最后一个页面,若其访问位仍为1,则再返到队首检查
    • 由于该算法是循环地检查各页面的访问情况,故称为CLOCK算法,置换的是未使用过的页,又称为最近未用算法NRU(Not Recently Used)

    简单Clock置换算法的流程和示例
    在这里插入图片描述

    改进型Clock置换算法

    • 在将一个页面换出时,如果该页已被修改过,便须将它重新写到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。同时满足两条件的页面作为首选淘汰的页。

    在这里插入图片描述

    • 各字段说明如下:
      (1)状态位(存在位)P。用于指示该页是否调入内存,供程序访问时参考。
      (2)访问字段A。用于记录本页在一段时间内被访问的次数,或最近已有多长时间未被访问,提供给置换算法选择换出页面时参考。
      (3)修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本,因此,若未被修改,在置换该页时就不须将该写回到外存上,以减少系统的开销和启动磁盘的次数;若已被修改,则必须将该页重写到外存上,以保证外存中所保留的始终是最新副本。

      (4)外存地址。用于指出该页在外存上的地址,通常是物理块号,供调入该页时使用。

    改进型Clock置换算法说明

    • 考虑使用情况和置换代价,换出的最好是未使用且未被修改过的
    • 由访问位A和修改位M组合:
      • 1类**(A=0, M=0)**:表示该页最近既未被访问,又未被修改,是最佳淘汰页
      • 2类**(A=0, M=1)**:表示该页最近未被访问,但已被修改,并不是很好的淘汰页
      • 3类**(A=1, M=0)**:最近已被访问,但未被修改, 该页有可能再被访问
      • 4类**(A=1, M=1)**:最近已被访问且被修改,该页可能再被访问
        在这里插入图片描述
    • 其执行过程可分成以下三步
    1. 从指针所指示的当前位置开始, 扫描循环队列, 寻找A=0且M=0的第一类页面, 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A
    2. 如果第一步失败,即查找一周后未遇到第一类页面, 则开始第二轮扫描,寻找A=0且M=1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位A都置0
    3. 如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所有的访问位A复0。 然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页

    改进型Clock置换算法-示例

    在这里插入图片描述

    未完待续。。。

    展开全文
  • 1 基本分页存储管理 连续分配:为用户进程分配的必须是一个连续的内存空间。 非连续分配:为用户进程分配的可以是一些分散的内存空间。 1.1 什么是分页存储 将内存空间分为一个个大小相等的分区(比如:每个分区4KB...

    1 基本分页存储管理

    连续分配:为用户进程分配的必须是一个连续的内存空间。
    非连续分配:为用户进程分配的可以是一些分散的内存空间。

    1.1 什么是分页存储

    1. 内存空间分为一个个大小相等的分区(比如:每个分区4KB),每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面)。每个页框有一个编号,即“页框号”(页框号=页帧号=内存块号=物理块号=物理页号),页框号从 0 开始 。
      在这里插入图片描述
    1. 进程的逻辑地址空间也分为与页框大小相等的一个个部分, 每个部分称为一个“”或“页面” 。每个页面也有一个编号, 即“页号”,页号也是从 0 开始 。
      在这里插入图片描述
    1. 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说,进程的页面与内存的页框有一一对应的关系。 各个页面不必连续存放,可以放到不相邻的各个页框中。
      (注意:进程的最后一个页面可能没有一个页框那么大。也就是说,分页存储有可能产生内部碎片,因此页框不能太大,否则可能产生过大的内部碎片造成浪费

    1.2 重要的数据结构——页表

    为了能知道进程的每个页面在内存中存放的位置,操作系统要为每个进程建立一张页表。

    注:页表通常存在PCB(进程控制块)中
    1. 一个进程对应一张页表
    2. 进程的每个页面对应一个页表项
    3. 每个页表项由“页号”和“块号”组成
    4. 页表记录进程页面实际存放的内存块之间的映射关系
    5. 每个页表项的长度是相同的
      在这里插入图片描述

    核心问题:

    1. 每个页表项多大?占几个字节?
    2. 如何通过页表实现逻辑地址到物理地址的转换?
    1. 已知计算机中内存块的数量页表项中块号至少占多少字节?

    假设某系统物理内存大小为4GB,页面大小为4KB,则每个页表项至少应该为多少字节?

    1. 内存块大小=页面大小=4KB=212 B
    2. 4GB的内存总共会被分为 232/212 =220个内存块
    3. 内存块号的范围应该是0~ 220-1
    4. 内存块号至少要用20bit来表示 →至少要用3B来表示块号(3*8=24bit

    页表项连续存放,因此页号可以是隐含的,不占存储空间(类比数组)

    引出问题:假设页表中的各页表项从内存地址为X的地方开始连续存放…
    如何找到页号为i的页表项?
    i号页表项的存放地址=X+3*I因此,页表中的页号可以是隐含的,即页号不占用存储空间
    在这里插入图片描述
    假设某系统物理内存大小为4GB,页面大小为4KB,则每个页表项至少应该为多少字节?

    1. 内存块大小=页面大小=4KB=212 B
    2. 4GB的内存总共会被分为 232/212 =220个内存块
    3. 内存块号的范围应该是0~ 220-1
    4. 内存块号至少要用20bit来表示 →至少要用3B来表示块号3*8=24bit
    5. 由于页号是隐含的,因此每个页表项占3B,存储整个页表至少需要3*(n+1)B
    1. 如何实现地址的转换

    进程在内存中连续存放时 , 操作系统是如何实现逻辑地址到物理地址的转换的?
    过程如下:
    在这里插入图片描述
    思考:将进程地址空间分页之后 ,操作系统该如何实现逻辑地址到物理地址的转换 ?

    特点:虽然进程的各个页面是离散存放的,但是页面内部是连续存放的

    如果要访问逻辑地址A,则 :

    1. 确定逻辑地址A对应的“页号”P
    2. 找到P号页面在内存中的起始地址(需要查页表)
    3. 确定逻辑地址A的“页内偏移量”W
      逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W

    子问题:如何确定一个逻辑地址对应的页号、页内偏移量?

    Eg:在某计算机系统中,页面大小是50B。某进程逻辑地址空间大小为200B,则逻辑地址110对应的页号、页内偏移量是多少?
    在这里插入图片描述
    如何计算:
    页号=逻辑地址/页面长度 (取除法的整数部分)
    页内偏移量=逻辑地址%页面长度(取除法的余数部分)

    本例中页号=110/50=2
    页内偏移量=110%50=10

    逻辑地址可以拆分为(页号,页内偏移量
    通过页号查询页表,可知页面在内存中的起始地址
    页面在内存中的起始地址+页内偏移量=实际的物理地址
    在这里插入图片描述

    逻辑地址→物理地址,二进制转化

    在计算机内部,地址是用二进制表示的, 如果页面大小刚好是2的整数幂,则计算机硬件可以很快速的把逻辑地址拆分成(页号,页内偏移量)

    假设某计算机用32个二进制位表示逻辑地址,页面大小为4KB =212 B=4096B

    1. 0号页的逻辑地址范围应该是0-4595,用二进制表示应该是: 00000000000000000000000000000000~00000000000000000000111111111111
    2. 1号页的逻辑地址范围应该是4096~8191,用二进制表示应该是: 00000000000000000001000000000000~00000000000000000001111111111111
    3. 2号页的逻辑地址范围应该是8192~12287,用二进制表示应该是: 00000000000000000010000000000000~00000000000000000010111111111111
    1. Eg:逻辑地址2,用二进制表示应该是00000000000000000000000000000010
      页号=2/4096=0=00000000000000000000
      页内偏移量=2%4096=2=000000000010
    2. Eg:逻辑地址4097,用二进制表示应该是00000000000000000001000000000001
      页号=4097/4096=1=00000000000000000001
      页内偏移量=4097%4096=1=000000000001

    如果每个页面大小为2KB,用二进制数表示逻辑地址, 则末尾K位即为页内偏移量,其余部分就是页号

    假设物理地址也用32个二进制位表示,则由于内存块的大小=页面大小,因此:

    1. 0号内存块的起始物理地址是00000000000000000000000000000000
    2. 1号内存块的起始物理地址是00000000000000000001000000000000
    3. 2号内存块的起始物理地址是00000000000000000010000000000000
    4. 3号内存块的起始物理地址是00000000000000000011000000000000

    根据页号可以查询页表,而页表中记录的只是内存块号,而不是内存块的起始地址!
    起始地址计算: J号内存块的起始地址=J*内存块大小

    假设通过查询页表得知1号页面存放的内存块号是9(1001),
    则9号内存块的起始地址=9X4096=00000000000000001001000000000000
    则逻辑地址4097对应的物理地址=页面在内存中存放的起始地址+页内偏移量 =(00000000000000000011000000000001

    结论:如果页面大小刚好是2 的整数幂,则只需把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址

    1.3 基本地址变换机构

    1. 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
    2. 通常会在系统中设置一个页表寄存器(PTR),存放页表在内存中的起始地址F和页表长度M
    3. 进程未执行时,页表的始址和页表长度放在进程控制块PCB)中,当进程被调度时,操作系统内核会把它们放到页表寄存器中。

    注意:页面大小是2的整数幂

    设页面大小为L,逻辑地址A到物理地址E的变换过程如下:
    在这里插入图片描述

    变换过程说明:

    1. 计算页号P和页内偏移量W(十进制手算:P=A/LW=A%L;但是在计算机实际运行时,逻辑地址结构固定不变,因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)
    2. 比较页号P和页表长度M,若P>=M,则产生越界中断,否则继续执行
      (注意:页号从0开始,而页表长度至少是1,因此P=M时也会越界)
    3. 页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度,取出改页表项内容b,即为内存块号。
      注意区分页表项长度、页表长度、页面大小的区别、页表长度指的是这个页表中总共有几个页表项,即总共有几个页;页表项长度指的是每个页表项占多大存储空间页面大小指的是一个页面占多大的存储空间
    4. 计算E=b*L+W,用得到的物理地址E去访存。(如果内存块号、页面偏移量是用二进制表示的,那么把二者拼接起来就是最终的物理地址了)

    例:若页面大小L为1K字节,页号2对应的内存块号b=8,将逻辑地址A=2500转换为物理地址E。

    题目等价描述:某系统按字节寻址,逻辑地址结构中,页内偏移量占10位,页号2对应的内存块号b=8,将逻辑地址A=2500转换为物理地址E
    页内偏移量占10位,说明一个页面的大小L为210B=1KB

    1. 计算页号、页内偏移量
      页号P=A/L=2500/1024=2;页内偏移量W=A%L=2500%1024=452
    2. 根据题中条件可知,页号2没有越界,其存放的内存块号b=8
    3. 物理地址E=b*L+W=8X1024+452=8644

    在分页存储管理(页式管理)的系统中,只要确定了每个页面的大小,逻辑地址结构就确定了。因此,页式管理中地址是一维的。即只要给出一个逻辑地址,系统就可以自动地算出页号、页内偏移量两个部分,并不需要显式地告诉系统这个逻辑地址中,页内偏移量占多少位。

    1.4 具有快表的地址变换机构

    快表的地址变换机构:是基本地址变换机构的改进版本

    1.4.1 什么是快表(TLB)

    快表,又称联想寄存器(TLBtranslation lookaside buffer ),是一种访问速度比内存快很多的高速缓存(TLB不是内存!),用来存放近访问的页表项的副本,可以加速地址变换的速度。 与此对应,内存中的页表常称为慢表。
    在这里插入图片描述
    在这里插入图片描述

    1.4.2 引入快表后,地址的变换过程
    1. CPU给出逻辑地址,由某个硬件算得页号、页内偏移量,将页号与快表中的所有页号进行比较。
    2. 如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,再将内存块号与页内偏移量拼接形成物理地址,然后访问该物理地址对应的内存单元。因此, 若快表命中,则访问某个逻辑地址仅需一次访问内存即可
    3. 如果没有找到匹配的页号,则需要访问内存中的页表,找到对应页表项,得到页面存放的内存块号,再将内存块号与页内偏移量拼接形成物理地址,然后访问该物理地址对应的内存单元。因此, 若快表未命中,则访问某个逻辑地址需要两次访存
      (注意:在找到页表项后,应同时将其存入快表, 以便后面可能的再次访问。但若快表已满,则必须按照一定的算法对旧的页表项进行替换)

    由于查询快表的速度比查询页表的速度快很多,因此只要快表命中,就可以节省很多时间。 因为局部性原理,一般来说快表的命中率可以达到90%以上。

    • 例:某系统使用基本分页存储管理,并采用了具有快表的地址变换机构。访问一次快表耗时1us,访问一次内存耗时100us。若快表的命中率为90%,那么访问一个逻辑地址的平均耗时是多少?
    (1+100)* 0.9+(1+100+100)* 0.1=111us

    说明:

    1. (1+100)* 0.9 访问逻辑地址,首先优先根据页号查询快表,耗时1us,若快表命中,就可以得到逻辑地址对应的最终的物理地址,再访问一次内存,就是访问我们最终要访问的物理单元,所以命中耗时101us;
    2. 若快表未命中,需要访问内存,查询慢表,最后就可以得到逻辑地址对应的最终的物理地址,再访问一次内存,就是访问我们最终要访问的物理单元,所以未命中耗时201us;
    3. 不管命中否,首先都得访问一次快表;
    4. 本题是优先查询快表。
    • 有的系统支持快表和慢表同时查找,如果是这样,平均耗时应该是(1+100)* 0.9+(100+100)* 0.1= 110.9us 若未采用快表机制,则访问一个逻辑地址需要100+100=200us 显然,引入快表机制后,访问一个逻辑地址的速度快多了。
    1.4.3 地址变换过程小结

    在这里插入图片描述
    TLB和普通Cache的区别:

    TLB中只有页表项的副本,而普通Cache中可能会有其他各种数据的副本

    1.5 两级页表

    1.5.1 单级页表存在的问题,为啥引入两极页表

    单级页表:
    在这里插入图片描述

    某计算机系统按字节寻址,支持32位的逻辑地址,采用分页存储管理,页面大小为4KB,页表项长度为4B
    4KB=212B,因此页内地址要用12位表示,剩余20位表示页号。
    因此,该系统中用户进程最多有220 页。相应的,一个进程的页表中,最多会有220 =1M=1048576个页表项,所以一个页表最大需要 220 * 4B=222 B,共需要222 /212 =210 个页框存储该页表。
    根据页号查询页表的方法:K号页对应的页表项存放位置=页表始址+K* 4
    要在所有的页表项都连续存放的基础上才能用这种方法找到页表项

    根据局部性原理可知,很多时候,进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

    思考:我们是如何解决进程在内存中必须连续存储的问题的?
    将进程地址空间分页,并为其建立一张页表,记录各页面的存放位置同样的思路也可用于解决“页表必须连续存放”的问题,把必须连续存放的页表再分页,从而将页表拆开

    把页表再分页并离散存储,然后再建立一张页表记录页表各个部分的存放位置,称为页目录表,或称外层页表,或称顶层页表

    1.5.2 两级页表的原理、地址结构
    1. 32位逻辑地址空间,页表项大小为4B,页面大小为4KB,则页内地址占12位 ,采用单级页表:
      在这里插入图片描述
      因此,该系统中用户进程最多有220 页。相应的,一个进程的页表中,最多会有220 =1M=1048576个页表项,所以一个页表最大需要 220 * 4B=222 B,共需要222 /212 =210 个页框存储该页表。
      在这里插入图片描述
    1. 现在把页表再分页并离散存储,然后再建立一张页表记录页表各个部分的存放位置,称为页目录表,或称外层页表,或称顶层页表
      在这里插入图片描述

    10位一级页号刚好可表示0~1023
    在这里插入图片描述

    1.5.3 二级页表如何实现地址变换

    在这里插入图片描述
    例:将逻辑地址(0000000000,0000000001,111111111111)转换为物理地址(用十进制表示)。

    1. 按照地址结构将逻辑地址拆分成三部分
    2. 从PCB中读出页目录表始址,再根据一级页号查页目录表,找到下一级页表在内存中的存放位置
    3. 根据二级页号查二级页表,找到最终想访问的内存块号
    4. 结合页内偏移量得到物理地址
      在这里插入图片描述

    最终要访问的内存块号为4
    该内存块的起始地址为4*4096=16384
    页内偏移量为4095
    最终的物理地址为 16384+4095=20479

    没有必要让整个页表常驻内存,因为进程在一段时间内可能只需要访问某几个特定的页面。

    可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以 在页表项中增加一个标志位,用于表示该页面是否已经调入内存
    在这里插入图片描述

    1. 若分为两级页表后,页表依然很长,则可以采用更多级页表,一般来说各级页表的大小不能超过一个页面
      例:某系统按字节编址,采用40位逻辑地址,页面大小为4KB,页表项大小为4B,假设采用纯页式 存储,则要采用()级页表,页内偏移量为()位?

    页面大小= 4KB =212B,按字节编址,因此页内偏移量为12位
    页号= 40-12 = 28位
    页面大小= 212B,页表项大小= 4B ,则每个页面可存放212 / 4 = 210个页表项
    因此各级页表最多包含210个页表项,需要10 位二进制位才能映射到210个页表项,因此每一级的页表对应页号应为10位。总共28位的页号至少要分为三级
    在这里插入图片描述
    如果只分为两级页表,则一级页号占18位, 也就是说页目录表中最多可能有218个页表项,超过了一个页面, 显然,一个页面是放不下这么多页表项的

    1. 两级页表的访存次数分析(假设没有快表机构)

    第一次访存:访问内存中的页目录表
    第二次访存:访问内存中的二级页表
    第三次访存:访问目标内存单元

    N级页表访问一个逻辑地址,需要N+1次访存

    1.5.4 二级页表小结

    在这里插入图片描述

    2 基本分段存储管理方式

    “分段”与“分页”最大的区别就是——离散分配时所分配地址空间的基本单位不同

    2.1 分段

    1. 进程的地址空间:按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言中,程序员使用段名来编程),每段从0开始编址
    2. 内存分配规则:以段为单位进行分配,每个段在内存中占据连续空间,但各段之间可以不相邻。

    在这里插入图片描述
    编译程序会 将段名转换为段号
    由于是按逻辑功能模块划分,用户编程更方便,程序的可读性更高

    LOAD1,[D]|<A>; //将分段D中A单元内的值读入寄存器1 
    STORE1,[X]|<B>; //将寄存器1的内容存入X分段的B单元中
    

    上述汇编指令,写程序时使用的段名[D]、[X]会被编译程序翻译成对应段号
    <A>单元、<B>单元会被编译程序 翻译成段内地址
    在这里插入图片描述

    分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成。如:
    在这里插入图片描述
    段号的位数决定了每个进程最多可以分几个段
    段内地址位数决定了每个段的最大长度是多少

    在上述例子中,若系统是按字节寻址的,则段号占16位,因此在该系统中,每个进程最多有216 =64K个段; 段内地址占16位,因此每个段的最大长度是216 =64KB。

    2.2 段表

    问题:程序分多个段,各段离散地装入内存,为了保证程序能正常运行,就必须能从物理内存中找到各个逻辑段的存放位置。为此,需为每个进程建立一张段映射表,简称“段表”。
    在这里插入图片描述

    1. 每个段对应一个段表项,其中记录了该段在内存中的起始位置(又称 “基址”)和段的长度。
    2. 各个段表项的长度是相同的。

    例如:某系统按字节寻址,采用分段存储管理,逻辑地址结构为(段号16位,段内地址16位),因此用16位即可表示最大段长。物理内存大小为4GB(可用32位表示整个物理内存地址空间)。
    因此,可以让每个段表项占16+32=48位,即6B。由于段表项长度相同,因此段号可以是隐含的,不占存储空间。
    若段表存放的起始地址为M,则K号段对应的段表项存放的地址为M+K*6

    2.3 地址变换

    在这里插入图片描述

    2.4 分段、分页管理的对比

    1. 是信息的物理单位。分页的主要目的是为了实现离散分配,提高内存利用率。分页仅仅是系统管理上的需要,完全是系统行为,对用户是不可见的
      是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的,用户编程时需要显式地给出段名。
    1. 页的大小固定且由系统决定。
      段的长度却不固定,决定于用户编写的程序。
    1. 分页的用户进程地址空间是一维的,程序员只需给出一个记忆符即可表示一个地址。
      分段的用户进程地址空间是二维的,程序员在标识一个地址时,既要给出段名,也要给出段内地址。

    在这里插入图片描述

    1. 分段比分页更容易实现信息的共享和保护。
      不能被修改的代码称为纯代码或可重入代码(不属于临界资源),这样的代码是可以共享的。可修改的代码是不能共享的(比如,有一个代码段中有很多变量,各进程并发地同时访问可能造成数据不一致)

    只需让各进程的段表项指向同一个段即可实现共享
    在这里插入图片描述
    在这里插入图片描述

    1. 访问一个逻辑地址需要几次访存?
      (1)分页(单级页表):第一次访存——查内存中的页表,第二次访存——访问目标内存单元。总共两次访存
      (2)分段:第一次访存——查内存中的段表,第二次访存——访问目标内存单元。总共两次访存
      (3)与分页系统类似,分段系统中也可以引入快表机构,将近期访问过的段表项放到快表中,这样可以少一次访问,加快地址变换速度。

    2.5 分段存储管理小结

    在这里插入图片描述

    3 段页式存储管理

    3.1 分页、分段优缺点分析

    在这里插入图片描述

    分段管理中产生的外部碎片也可以用“紧凑”来解决,只是需要付出较大的时间代价

    3.2 分段+分页=段页式管理

    在这里插入图片描述

    3.3 段页式管理的逻辑地址结构

    在这里插入图片描述
    即把段内地址再拆分为页号+页面偏移量
    段号的位数决定了每个进程最多可以分几个段
    页号位数决定了每个段最大有多少页
    页内偏移量决定了页面大小、内存块大小是多少

    在上述例子中,若系统是按字节寻址,则

    • 段号占16位,因此在该系统中,每个进程最多有216=64K个字段
    • 页号占4位,因此每个段最多有24=16页
    • 页内偏移量占12位,因此每个页面\每个内存块大小为212=4096=4KB

    “分段”对用户是可见的,程序员编程时需要显式地给出段号、段内地址。
    而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。
    因此段页式管理的地址结构是二维的。

    简记:页式一维、段式二维、段页式二维

    3.4 段表、页表

    在这里插入图片描述

    每个段对应一个段表项,每个段表项由段号、页表长度、页表存放块号(页表起始地址)组成。每个段表项长度相等,段号是隐含的。

    每个页面对应一个页表项,每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等,页号是隐含的。

    3.5 段页式管理地址变换过程

    在这里插入图片描述

    也可引入快表机构,用段号和页号作为查询快表的关键字。若快表命中则仅需一次访存

    3.6 段页式管理小结

    在这里插入图片描述

    展开全文
  • 操作系统中的内存管理习题,请分析和比较连续分配、分页和分段三种存储分配机制的优缺点
  • 分段分页方式的比较各自优缺点

    千次阅读 2018-06-19 14:23:56
    或者说,分页仅仅是由于系统管理的需要,而不是用户的需要(也是对用户透明的)。段是信息的逻辑单位,它含有一组其意义相对完整的信息(比如数据段、代码段和堆栈段等)。分段的目的是为了能更好的满足用户的需要...

    分段和分页其实都是一种对地址的划分或者映射的方式。 两者的区别主要有以下几点:

    1)页是信息的物理单位,分页是为实现离散分配方式,以消减内存的外零头,提高内存的利用率;或者说,分页仅仅是由于系统管理的需要,而不是用户的需要(也是对用户透明的)。段是信息的逻辑单位,它含有一组其意义相对完整的信息(比如数据段、代码段和堆栈段等)。分段的目的是为了能更好的满足用户的需要(用户也是可以使用的)。

    2)页的大小固定且由系统确定,把逻辑地址划分为页号和页内地址两部分,是由机器硬件实现的,因而一个系统只能有一种大小的页面。段的长度却不固定,决定于用户所编写的程序,通常由编辑程序在对源程序进行编辑时,根据信息的性质来划分。

    3)分页的作业地址空间是维一的,即单一的线性空间,程序员只须利用一个记忆符(线性地址的16进制表示),即可表示一地址。分段的作业地址空间是二维的,程序员在标识一个地址时,既需给出段名(比如数据段、代码段和堆栈段等),又需给出段内地址。

    4)页和段都有存储保护机制。但存取权限不同:段有读、写和执行三种权限;而页只有读和写两种权限

    展开全文
  • 2.详述分段管理分页管理的区别。 3.P249 习题11 1.采用相联存储器后地址转换过程,用图表示出来CPU对存储器的访问,通常是一次读写一个字单元。当CPU访Cache不命中时,需将存储在主存中的字单元连同其后若干个字...

    1.采用相联存储器后地址转换过程,用图表示出来

    2.详述分段管理和分页管理的区别。 

    3.P249 习题11

    1.采用相联存储器后地址转换过程,用图表示出来CPU对存储器的访问,通常是一次读写一个字单元。当CPU访Cache不命中时,需将存储在主存中的字单元连同 其后若干个字一同调入Cache中,之所以这样做,是为了使其后的访存能在Cache中命中。因此,主存和Cache之间一次交换的数据单位应该是一个数 据块。数据块的大小是固定的,由若干个字组成,且主存和Cache的数据块大小是相同的。

     从Cache-主存层次实现的目标看,一方面既要使CPU的访存速度接近于访Cache的速度,另一方面为用户程 序提供的运行空间应保持为主存容量大小的存储空间。在采用Cache-主存层次的系统中,Cache对用户程序而言是透明的,也就是说,用户程序可以不需 要知道Cache的存在。因此,CPU每次访存时,依然和未使用Cache的情况一样,给出的是一个主存地址。但在Cache-主存层次中,CPU首先访 问的是Cache,并不是主存。为此,需要一种机制将CPU的访主存地址转换成访Cache地址。而主存地址与Cache地址之间的转换是与主存块与 Cache块之间的映射关系紧密联系的,也就是说,当CPU访Cache未命中时,需要将欲访问的字所在主存中的块调入Cache中,按什么样的策略调 入,直接影响到主存地址与Cache地址的对应关系,这也就是本小节要解决的主存与Cache的地址映射问题。

     主要有三种地址映射方式,分别为全相联映射、直接相联映射和组相联映射。

     1. 全相联映射

     全相联映射是指主存中任一块都可以映射到Cache中任一块的方式,也就是说,当主存中的一块需调入Cache时,可根据当时Cache的块占用或分配情况,选择一个块给主存块存储,所选的Cache块可以是Cache中的任意一块。例如,设Cache共有2C块,主存共有2M块,当主存的某一块j需调进Cache中时,它可以存入Cache的块0、块1、…、块i、… 或块2C -1的任意一块上。如图4-28所示。

    主存与Cache的地址映射 - zjfzjf - zjfzjf

      

    图4-28全相联映射方式

     在全相联映射方式下,CPU的访主存地址为如下形式:

    主存与Cache的地址映射 - zjfzjf - zjfzjf

      

     其中,M为主存的块号,W为块内的字号。而CPU访Cache的地址形式为:

    主存与Cache的地址映射 - zjfzjf - zjfzjf

      

     其中,C为Cache的块号,W为块内的字号。

     主存地址到Cache地址的转换是通过查找一个由相联存储器实现的块表来完成的,其形成过程如图4-29示。

     

    主存与Cache的地址映射 - zjfzjf - zjfzjf

     

    图4-29全相联映射的地址转换

     当 一个主存块调入Cache中时,会同时在一个存储主存块号和Cache块号映射表的相联存储器中进行登记。CPU访存时,首先,根据主存地址中的主存块号 M在相联存储器中查找Cache块号,若找到,则本次访Cache命中,于是将对应的Cache块号取出,并送访Cache地址的块号C字段;紧接着将主 存地址的块内字号W直接送Cache地址的块内字号W字段,从而形成一个访Cache的地址;最后根据该地址完成对Cache单元的访问.

     全相联映射方式的优点是Cache的空间利用率高,但缺点是相联存储器庞大,比较电路复杂,因此只适合于小容量的Cache之用。 

    2.详述分段管理和分页管理的区别。

    分页系统的缺点
      缺点的改进:
    ①页表太大?这个缺点用多级页表来克服了。
    ②多级页表速度慢?这个问题用TLB解决了大部分。页面的来回更换?这个问题用页面更换算法解决了。

     
    缺点③:共享困难,虽然理论上我们可以按页面进行共享,似乎可以!但是呢这根本就是不现实的,因为一个页面的内容很可能存在代码和数据,即很难使得一个页面里面只包含可共享的内容 或者 不可共享的内容缺点④:一个进程只能占用一个虚拟地址空间,这也是分页系统无法克服的。所以一个程序的大小最大只能和虚拟地址空间的大小一样,其所有的内容都必须在这个虚拟地址空间中分布。

    但是很多人觉得一个程序不必要分配多个虚拟地址空间!


    那么我们来看一个例子:编译器的工作过程。我们知道在编译器工作时需要保持多个数据结构:词法分析树,常数表,代码段,符合表 ,调用栈。使用保持多个数据结构并没有任何问题,
    问题出现在:这些数据结构可以独立的增长和缩小,从而造成了该数据结构所需的内存空间的变化。


    那么我们来想怎么实现在一个虚拟地址空间内,实现各个数据段的空间的增加和减少???


    解决方法:那一个程序占用一个虚拟空间不能解决我们各个数据结构段增长的需求!那么就使用多个虚拟地址空间来解决。

     

    分段管理系统
      定义:分段管理是将一个程序按照逻辑单元分成多个程序段,每个段使用自己单独的虚拟地址空间。
    5个段占用5个虚拟地址空间。这样一个段占用一个虚拟地址空间,就不会发生空间增长时碰撞到另一个段的问题。

     

     

     
    分段原理:一个程序占据多个虚拟地址空间,那么不通过的段有可能有同样的虚拟地址空间。在分段情况下,一个虚拟地址空间又段号和段内偏差。段号找相应的段地址空间!

      实现手段:由于分段内存管理 和 基本内存管理有着类似之处,所以分段也是使用 基址---极限管理模式。
    不过这里使用的是一组 基址—极限对。而对每一对基址极限用于其中一段的管理。

     

    分段管理的一个重要数据结构就是段表。该表存放的是虚拟的段号到该段所在内存基址的映射。如果一个段不存在,则段号对应的基址将不存在。


    分段的优缺点
     
    优点:

    1.每个逻辑单元可以独占一个虚拟地址空间,这样所写程序的空间大为增长。


    2.共享性强。


    3.相比于分页,当对于空间稀疏的程序,分页仍然需要分配虚拟页面。而分段不给他分配任何的虚拟空间。


    缺点:既然是分段,就存在前面基本内存管理的缺点-----外部碎片化 和 一个段必须全部加载到内存上。

    3.P249 习题11

      答:(1)649

      (2)1727

      (3)2301

      (4)140

      (5)1956

     

    转载于:https://www.cnblogs.com/songwanli/p/10955381.html

    展开全文
  • 前叙除“多重分区”的分配方法外,都属于连续分区...纯分页系统 1.页面与页框 *1.把作业的地址空间划分为大小相等的片,称为页面/页,Page。 *2.把内存的物理空间划分为同页大小的片,称为页框/存储块,PageFrame。
  • 文章目录非连续分配管理基本分页存储管理如何实现地址转换页表总结基本地址变换机构(页表寄存器)总结具有快表的地址变换机构局部性原理快表引入快表后, 地址变换过程总结两级页表单级页表存在的问题两级页表 (解决...
  • 一. 存储管理(一) 存储体系(二) 地址重定位1. 绝对装入2. 可重定位装入(三) 链接1. 静态链接2. 动态链接二. 分区存储管理方案(一) 概述(二) 单一连续分区(三) 固定分区(四) 可变分区1. 概述2. 分区...
  • 连续,设计简单,直接寻址,效率高。...一、分区存储管理 1、固定分区: 优点:易于实现、开销小 缺点:存在内部碎片(分区内未被利用空间)、分区总数固定,限制了并发执行的程序数量。 2、动...
  • 连续,设计简单,直接寻址,效率高。缺点:内存利用效率最低,有内部碎片。 分页,缓解内存压力,设计最复杂(粒度最小...一、分区存储管理  1、固定分区:  优点:易于实现、开销小  缺点:存在内部碎片(分区...
  • 存储管理之页式、段式、段页式存储 以及 优缺点

    万次阅读 多人点赞 2018-09-14 18:08:44
    内存管理方式主要分为:页式管理、段式管理和段页式管理。 页式管理的基本原理是将各进程的虚拟空间划分为若干个长度相等的页。把内存空间按页的大小划分为片或者页面,然后把页式虚拟地址与内存地址建立一一对应的...
  • 分页、分段和段页式存储管理方式

    千次阅读 2018-04-10 20:56:44
     分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从0开始,如第0页、第1页等。相应地,也把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或页框...
  • 一、基本分段存储管理方式 (一)分段 进程的地址空间:按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言中,程序员使用段名来编程),每段从0开始编址 内存分配规则:以段为单位进行分配,...
  • 内存管理
  • 分页存储管理基本思想: 用户程序的地址空间被划分成若干固定大小的区域,称为“页”,相应地,内存空间分成若干个物理块,页和块的大小相等。可将用户程序的任一页放在内存的任一块中,实现了离散分配。 分段存储...
  • 分页内存管理

    千次阅读 2019-03-18 16:31:41
    3、虚拟地址的构成与地址翻译4、页表5、分页内存管理优缺点二、分页内存管理例子解析三、缺页中断和页面置换的目标1、缺页中断2、页面置换的目标四、页面置换算法1、最佳置换算法(OPT)2、最近最久未使用(LRU)3...
  • 请求分页与请求分段管理方式

    千次阅读 2020-05-12 11:56:45
    请求分页与请求分段管理方式 请求分页管理方式 1 概述 请求分页系统建立在基本分页系统基础之上,为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。...
  • 分页与分段存储

    2020-12-29 20:11:41
    分页与分段存储1 分页存储管理方式1.1 分页存储管理的基本方法 1 分页存储管理方式 分页存储管理方式 : 将用户程序的地址空间分为若干个固定大小的区域,称为“页”或“页面”。相应的,也将内存空间分为若干个物理...
  • 内存管理的三个离散方式:页式(分页)、段式(分段)、段页式(页段联动) 目录页式基本原理实现优点缺点段式管理基本原理实现优点缺点段页式管理基本原理实现优点缺点 页式 基本原理 将各进程的虚拟空间划分为若干...
  • 段页式管理方式

    2020-12-18 15:02:53
    在前面文章基本分页存储管理方式和分段存储管理方式中介绍了非连续分配管理方式的基本分页存储管理方式。 接下来,本文将介绍非连续分配管理的第三种方式——段页式存储管理方式 分页、分段的优缺点 分页 优点:...
  • 段页式存储管理方式详解

    千次阅读 2020-05-12 15:34:32
    段页式存储管理方式详解分段存储方式引入目的:基本原理分段段表地址变换机构信息保护信息共享分页与分段的主要区别:段页式存储管理方式引入原因:基本原理段表与页表地址变换机构 分段存储方式 引入目的: 满足用户在...
  •  分页存储管理 1.基本思想 用户程序的地址空间被划分成若干固定大小的区域,称为“页”,相应地,内存空间分成若干个物理块,页和块的大小相等。可将用户程序的任一页放在内存的任一块中,实现了离散分配。 1) ...
  • 八种架构设计模式及其优缺点概述

    千次阅读 2017-04-11 09:15:31
    八种架构设计模式及其优缺点概述, 单库单应用模式:最简单的,可能大家都见过 内容分发模式:目前用的比较多 查询分离模式:对于大并发的查询、业务 微服务模式:适用于复杂的业务模式的拆解 多级缓存...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,133
精华内容 4,853
关键字:

分页存储管理方式的优缺点