精华内容
下载资源
问答
  • 分页式存储空间的分配
    千次阅读
    2018-03-11 16:39:27

    4.3 知识点3:基本分页存储管理方式

    4.3.1 要点归纳

    1. 基本分页存储管理的原理

    在分区存储管理中,要求把作业放在一个连续的存储区中,因而会产生许多碎片,固定分区会产生内部碎片,动态分区会产生外部碎片。尽管通过拼接技术可以解决碎片问题,但代价较高。分页存储管理允许将作业存放到许多不相邻接的内存区域中,从而有效地解决了存储器碎片问题(尽管会产生内部碎片,但相对进程来说是很小的)。

    在基本分页存储管理(又称简单分页、纯分页)中,用户作业的地址空间被划分成若干大小相等的区域,称为页或页面。页面大小应该是2的整数幂,这样方便地址变换。由于作业大小不会刚好都是页面大小的整数倍,所以最后一个页面往往会有空间浪费,称为页内碎片,属于内部碎片。

    相应地,将内存的存储空间也分成与页大小相等的区域,称为块或物理块。在为作业分配存储空间时,总是以块为单位来分配,可以将作业中的任意一页放到内存中的任意一个空闲块中。在调度作业运行时,必须将它的所有页面一次调入内存;若内存中没有足够的物理块,则作业等待。

    单词Page Frame在国内操作系统教材中的翻译方式很多,有物理块(块)、页框、页架、页帧和帧等,读者应加以注意,但它表示的都是与一个逻辑页相对应的一个物理块。

    基本分页存储管理系统中的逻辑地址结构如图4.22所示。它包含两部分,前一部分为页号P,后一部分为页内偏移量W。如果逻辑地址空间是2m,页面大小是2^n(字节),那么逻辑地址的高m–n位是页号,低n位是页内偏移量。

    在基本分页存储管理中,逻辑地址空间以页为单位划分,而内存的分配是以内存块为单位分配的,页面大小正好等于一个物理块的大小。

    图4.22 分页系统中的逻辑地址结构

    上述地址结构中,两部分的地址长度为32位。其中0~11位(计12位)为页内偏移量,即每页大小=2^12=4×2^10=4KB;12~31位(计20位)为页号,即最多的页数=2^20= 1×2^10×2^10=1MB。页内偏移量也称为页内位移、页偏移或页内地址等。

    为了便于在内存中找到进程的每个页面所对应的物理块,系统为每个进程建立一张页面映像表,简称页表,记录页面在内存中对应的物理块号。页表一般存放在内存中,图4.23说明了页表的作用。

    页面大小由机器的地址结构决定。在确定地址结构时,若选择的页面较小,一方面可以使页内碎片较小并减少内存碎片的总空间量,有利于提高内存利用率;另一方面也会使每个进程要求较多的页面,从而导致页表过长,占用大量内存,还会降低页面调入/调出的效率。若选择的页面较大,虽然可以减少页表长度,提高页面调入/调出的效率,但又使页内碎片增大。因此,页面的大小应该选择适中,一般在512B~8KB之间。

    图4.23 页表的作用

    2. 基本分页存储管理的存储空间管理

    可用位示图构成主存分配表,位示图的每一行用一个字来表示,其中每一位(其位置用字号和位号确定,假设字号和位号从0开始编号)与一个主存块(其编号为块号)对应,0表示空闲,1表示已占用,最后一个字节为当前剩余的空闲块数。

    主存分配时,计算块号公式为:

    块号=字号×字长+位号

    主存第i块归还时,在位示图中对应位置可按如下公式确定:

    字号=块号i DIV 字长,位号=块号i MOD 字长

    其中,DIV表示整除,MOD表示求余数。

    3. 基本分页存储管理的地址变换机构

    如图4.24所示,给出了分页存储管理系统中的地址变换机构,其中逻辑地址到物理地址的变换要借助页表来实现,页表通常存放在内存中。

    为了实现上的方便,系统中设置了一个页表寄存器(PTR),其中存放页表在内存的起始地址F和页表的长度M。进程未执行时,页表的起始地址和长度存放在进程控制块中。当进程执行时,才将页表起始地址和长度存入页表寄存器中。

    假设页面大小为L,页表长度为M,逻辑地址A通过地址变换得到物理地址E的过程如下:

    计算页号P=(int)(A/L);页内偏移量W=A % L(W也称为页内地址)。

    比较页号P和页表长度M,若P≥M,则产生越界中断,否则转到下一步执行。

    页表中页号P对应的页表项地址=页表起始地址F+页号P×页表项大小,取出该页表项内容b,即为物理块号。

    计算E=b×L+W。

    用得到的物理地址E去访问内存。

    以上整个地址变换过程都是由硬件自动完成的。

    图4.24 分页存储管理系统的地址变换机构

    例如,若页面大小L为1KB,页号2对应的物理块为b=8,计算逻辑地址A=2500的物理地址E的过程如下:P=(int)(2500/1KB)=2,W=2500 % 1KB=452,查找得到页号2对应的物理块的块号为8,E=8*1024+452=8644。

    【例4.2】在分页存储管理系统中,逻辑地址的结构长度为18位,其中11~17位表示页号,0~10位表示页内偏移量。若有一个作业的各页依次放入2、3、7号物理块中,试问:

    (1)进程逻辑地址空间最大可为多少KB?分为多少页?每页有多大?

    (2)逻辑地址1500应在几号页内?对应的物理地址是多少?

    解:在该页表中,有3个页表项,分别为(0,2)、(1,3)、(2,7)。

    (1)由于逻辑地址共有18位,所以最大的逻辑地址空间为218B=256KB。采用0~10位表示页内偏移量,所以页面大小L=211B,每块大小=页面大小=211B,则页面总数=218/211=128页。

    (2)逻辑地址A=1500,对应页号=(int)(1500/211)=0,页内偏移量W=1500。查找页表可知对应的物理块号为2,所以,对应的物理地址E=2×211+1500=5596。

    4. 具有快表的地址变换机构

    从上面介绍的地址变换过程可知,若页表全部放在内存中,则要存取一个数据或一条指令至少要访问两次内存,一次是访问页表,确定所存取的数据或指令的物理地址,第二次才根据该地址存取数据或指令。显然,这种方法比通常执行指令的速度慢了一倍。

    为了提高内存访问的速度,可以在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器(又称联想存储器TLB、快表),通常是在快表中存放正在运行作业当前访问的那些页表项,以加速地址变换过程,主存中的页表有时也称为慢表。配有快表的地址变换机构,如图4.25所示。

    引入快表以后的地址变换过程如下:

    当CPU给出逻辑地址后,地址变换机构自动地将逻辑地址分为页号和页内偏移量两部分。

    将页号与联想存储器中的所有页号进行并行比较,若其中有与此匹配的页号,则表示所要访问的页表项在联想存储器中,于是取出该页对应的块号,与页内偏移量拼接形成物理地址。若联想存储器中的所有页号与所查找页号不匹配,则还需要再访问内存中的页表,从页表中取出物理块号,与页内偏移量拼接形成物理地址,还应将这次所查到的页表项存入快表中。

    用物理地址访问内存。

    在分页系统中增加了快表后,在快表中找出所需页表项的概率称为平均命中率。据统计,快表中如含有8个页表项时,平均命中率为85%,含有16个页表项时,平均命中率为97%,因此在配备快表的分页存储管理系统中,多一级地址变换不会明显减慢程序的执行速度。

    图4.25 配有快表的地址变换机构

    ━━━━━━━求解方法提示:基本分页管理方式中有效访问时间的计算法━━━━━━

    所谓有效访问时间(Effective Access Time,简称EAT),是指给定逻辑地址找到内存中对应物理地址单元中的数据所花的总时间。

    在基本分页系统中,如果没有快表,访问内存一次需要的时间为t,有效访问时间分为:查页表找到对应的页表项所花时间t、通过对应的物理地址访问一次内存所花时间t,所以:EAT=t+t=2t。

    若有快表,设快表TLB的查找需要时间为e,访问内存一次需要的时间为t,命中率为a,则有效访问时间分为:查页表项的平均时间为ea+(t+e)(1-a)、通过对应的物理地址访问一次内存所花时间为t,所以:EAT=ea+(t+e)(1-a)+t=2t+e-ta。

    例如,若有快表,且命中率为80%,查找TLB需要20ns,访问内存一次需要100ns,则:EAT=2×100+20-100×80%=140ns。这样,比内存访问时间慢了40%(从100ns上升到了140ns)。又例如,若命中率为98%,其他条件不变,则:EAT=2×100+20-100×98%=122ns。这个命中率仅产生了22%(从100ns上升到了122ns)的访问时间延迟。

    ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

    【例4.3】假设一个分页存储管理系统中具有快表,多数活动页表项都可以存在其中。如果页表放在内存中,内存访问时间是1?s,若快表的命中率为85%,则有效访问时间是多少?若快表的命中率为50%,则有效访问时间是多少?

    解:有效访问时间是指通过逻辑地址访问对应物理地址中的数据所花的时间。有快表时,先查找快表(由于速度很快,所花时间忽略不计),若找到了对应的页表项,取出物理块号并拼成物理地址,再访问内存,只须访问内存1次;若在快表中没有找到,再在页表中查找,需要访问内存2次。

    若快表的命中率为85%,则有效访问时间=2×1μs+0-1μs×85%=1.15μs。

    若快表的命中率为50%,则有效访问时间=2×1μs+0-1μs×50%=1.5μs。

    由于快表的访问时间相对很短,若题目中没有给出快表访问时间,通常可以看成快表访问时间为0。

    5. 两级和多级页表

    当页表很大时,可以采用多级页表形式,即构建两级或多级页表。两级页表是将基本分页存储管理中的逻辑地址结构由(页号P,页内偏移量W)改为如下形式:

    外层页号P1 外层页内地址P2(或内层页号) 页内偏移量W

    如图4.26所示是两级页表的示意图。

    图4.26 两级页表示意图

    在进行地址变换时,先用外层页号P1在外部页表上查找,找出的单元内容是对应二级页表的首地址,该首地址加上外层页内地址P2就是对应二级页表项的地址,取出该页表项的内容就是物理块号,该物理块号拼接页内偏移量W就得到了物理地址。

    两级页表解决了大页表占用大的连续存储空间的问题。多级页表依次类推,不再介绍。

    【例4.4】为满足264地址空间的作业运行,采用多级分页存储管理方式,假设页面大小为4KB,在页表中的每个页表项需要占8个字节,则为了满足系统的分页管理至少应采用多少级页表?

    解:页面大小=4KB=2^12字节,每个页表项为8字节=2^3字节,所以一个页面中可以存放2^12/2^3=29个页表项。设有n层分页,则64位逻辑地址形式为:

    第1层页号 第2层页号 … 第n层页号 页内偏移量

    其中,页面大小为212字节,所以页内偏移量占12位。剩下64-12=52位,由于每层指向一个物理块,其中可放下29个表项,所以?52/9?=6(向上取整数)。

    4KB的块可以存2^12/2^3=2^9即512个页表项,
    64位,4kb的页内编址需要12位。其余给多级页表,剩余52位,每级页表9位。52/9取上得6.所以是6级页表。
    实际上不管win还是linux,都只开放一部分寻址空间,所以实际上不会用到6级页表这种变态又耗时间的方法。

    6. 基本分页存储管理的内存保护

    分页环境下的内存保护由关联到每个物理块的保护位完成。这些位通常保存在页表中。一个位可以定义一个页是读写还是只读属性。每次引用内存都要通过页表来找到正确的物理块号,同时也要计算物理地址。可以检查保护位来确定有没有对一个只读页进行写操作,对只读页的写操作将产生操作系统的硬件自陷或内存保护错误。

    通常页表的每项还附属一个位:有效/无效(valid/invalid)位。当这个位被设为valid时,它指明相关联的页处于该进程的地址空间中;如果这个位是invalid,它指明这个页不在进程的逻辑地址空间中。利用有效/无效位可以使对非法地址的访问产生自陷。

    进程很少会使用它所有的地址空间,许多进程仅仅使用自己的很小一部分地址空间。在这种情况下,在页表中为地址空间中的每一页都创建一个表项是很浪费的。这个表的大部分都不会被用到,但却占用了宝贵的内存空间。有些系统提供了硬件,以页表长度寄存器的形式指明页表的大小。将这个值与每个逻辑地址进行检查以验证这个地址是否在进程的有限地址空间内。如果这个测试失败,就将向操作系统产生一个错误中断。

    7. 基本分页存储管理方式的优缺点

    优点如下:

    存在页内碎片,但碎片相对较小,内存利用率较高。

    实现了离散分配,消除了程序浮动。

    便于存储访问控制,有利于代码共享。

    无外部碎片。

    缺点如下:

    需要专门的硬件支持,尤其是快表。

    内存访问的效率下降。

    不支持动态链接,不能实现真正的共享。

    有内部碎片。

    4.3.2 例题解析

    1. 单项选择题

    【例4-3-1】在分页存储管理中,主存的分配是 。

    A. 以块为单位进行 B. 以作业的大小分配

    C. 以物理段进行分配 D. 以逻辑记录大小进行分配

    解:在分页存储管理中,将内存划分与页大小相等的区域,即物理块,在为作业分配存储空间时,总是以块为单位来分配,可以将作业中任一页分配到内存任意空闲块中。本题答案为A。

    【例4-3-2】分页式存储管理的主要特点是 。

    A. 要求处理缺页中断 B. 要求扩充主存容量

    C. 不要求作业装入到主存的连续区域 D. 不要求作业全部同时装入主存

    解:分页式存储管理是一种离散分配方法,作业的每个页面装入到一个主存块中,主存块之间不一定是连续区域。本题答案为C。

    【例4-3-3】在分页式存储管理中用作存储保护的是 。

    A. 页表长度 B. 页表始址 C. 页长 D. 重定位寄存器

    解:A。

    【例4-3-4】 存储管理方式提供一维地址结构。

    A. 分段 B. 分页 C. 分段和段页式 D. 都不是

    解:分页存储管理方式中所有地址都是一致的,而分段存储管理方式中每个段都有自已的地址,段之间是独立的,通过段号和段内地址实现地址变换。所以将分页存储管理方式中的地址结构看成是一维地址结构,分段存储管理方式中的地址结构看成是二维地址结构。本题答案为B。

    【例4-3-5】下列 存储管理方式能使存储碎片尽可能少,而且使内存利用率较高。

    A. 固定分区 B. 可变分区 C. 分页管理 D. 段页式管理

    解:分页管理方式页内碎片相对较小,内存利用率高。本题答案为C。

    【例4-3-6】以下解决主存碎片问题较好的存储器管理方式是 。

    A. 可变式分区 B. 分页管理 C. 分段管理 D. 单一连续区管理

    解:分页管理方式中没有外部碎片,内存利用率高,而分段管理方式中难以找到连续的空闲区放入整段,相对内存利用率不高。本题答案为B。

    【例4-3-7】 存储管理支持多道程序设计,算法简单,但存储碎片多。

    A. 段式 B. 页式 C. 固定分区 D. 段页式

    解:固定分区可用于多道程序系统,相对于其他选项算法简单,没有外部碎片,但不能实现多进程共享一个主存区,主存利用率低,存在较多的内部碎片。本题答案为C。

    【例4-3-8】操作系统采用分页存储管理方式,要求 。

    A. 每个进程拥有一张页表,且进程的页表驻留在内存中

    B. 每个进程拥有一张页表,但只有执行进程的页表驻留在内存中

    C. 所有进程共享一张页表,以节约有限的内存空间,但页表必须驻留在内存中

    D. 所有进程共享一张页表,只有页表中当前使用的页面必须驻留在内存中,以最大限度地节省有限的内存空间

    解:在多个进程并发执行时,所有进程的页表大多数驻留在内存中,在系统中只设置一个页表寄存器PTR,在其中存放页表在内存的起始地址和页表的长度。平时,进程未执行时,页表的起始地址和页表长度存放在本进程的PCB中,当调度到某进程时,才将这两个数据装入页表寄存器中。本题答案为A。

    【例4-3-9】在一个分页存储管理系统中,页表内容如表4.2所示。若页的大小为4KB,则地址转换机构将逻辑地址0转换成的物理地址为 。

    A. 8192 B. 4096 C. 2048 D. 1024

    解:在分页存储管理系统中,物理地址为页面对应的物理块号与页内地址拼接的结果,逻辑地址0的页号为0,页内位移也为0,故物理地址为2?4KB=8192B。本题答案为A。

    表4.2 一个页表

    页号 块号

    0 2

    1 1

    2 6

    3 3

    4 7

    【例4-3-10】在分页管理系统中,分页是由 完成的。

    A. 程序员 B. 硬件 C. 编译软件 D. 都不对

    解:在分页管理系统中,分页和地址转换过程都是由硬件完成的。本题答案为B。

    【例4-3-11】分页系统中的页面是 。

    A. 用户感知的 B. 操作系统感知的

    C. 编译程序感知的 D. 链接装配程序感知的

    解:在分页管理系统中,分页是由操作系统指挥硬件完成的,页面是由操作系感知的。本题答案为B。

    【例4-3-12】位示图法可用于 。

    A. 页式虚拟存储管理中页面置换

    B. 可变式分区存储管理中空闲区的管理

    C. 分页式存储管理中主存空闲块的管理

    D. 文件目录的查找

    解:位示图是一种存储空间管理方法,可用于主存和磁盘空间的管理,要求管理的基本单位大小是固定的,所以可用于分页式存储管理中主存空闲块的管理。本题答案为C。

    【例4-3-13】以下有关外层页表的叙述中错误的是 。

    A. 反映在磁盘上页面存放的物理位置

    B. 外层页表是指向页表的页表

    C. 为不连续(离散)分配的页表再建立一个页表

    D. 有了外层页表则需要一个外层页表寄存器就能实现地址变换

    解:外层页表并不是反应磁盘上页面存放的物理位置,而是在页表较大时将页表进行分页,再建立的页表的页表。本题答案为A。

    【例4-3-14】在基本分页存储管理中,设有8页的逻辑空间,每页有1024个字节,它们被映射到32块的物理存储区中,则逻辑地址的有效位是 ① 位,物理地址至少是 ② 位。

    A. 10 B. 13 C. 14 D. 15

    解:对于逻辑地址结构,8页=23页,每页1024个字节=210个字节,所以逻辑地址有效位数=3+10=13位。对于物理地址结构,每块大小=每页大小=210,共有32块=25个块,所以物理地址有效位数至少=5+10=15位。本题答案为:①B ②D。

    2. 填空题

    【例4-3-15】在分页存储管理中,要求程序中的逻辑地址可以分页,页的大小与 大小一致。

    解:本题答案为:物理块。

    【例4-3-16】作业的页表中包含逻辑地址中的 ① 与主存中 ② 的对应关系。

    解:本题答案为:①页号 ②块号。

    【例4-3-17】分页系统中信息的逻辑地址到物理地址的变换由 决定。

    解:本题答案为:页表。

    【例4-3-18】在基本分页存储管理中,地址变换公式为:物理地址= ① ×块长+ ② 。

    解:本题答案为:①块号 ②页内地址。

    【例4-3-19】在基本分页存储管理中主存分配情况可用一个 表示,其中某位为0表示对应块为空闲。

    解:本题答案为:位示图。

    【例4-3-20】在基本分页存储管理中,按给定的逻辑地址读写时,要访问两次主存,第1次是 ① ,第2次是 ② 。

    解:本题答案为:①查页表按页号读出对应的块号 ②按计算出来的物理地址进行读写。

    【例4-3-21】分页存储管理做重定位时,实际上是把 ① 作为物理地址的高位地址,而 ② 作为它的低地址部分。

    解:本题答案为:①块号 ②页内地址。

    【例4-3-22】在某基本分页存储管理中,逻辑地址为24位,其中8位表示页号,则允许的最大页面大小是 字节。

    解:逻辑地址由页号和页内地址两部分组成,页内地址的位数=24-8=16,页面大小为216字节。本题答案为:216。

    【例4-3-23】在基本分页存储管理系统中,把一段时间内总是经常访问的某页表项存放在 中,可实现快速查找并提高指令执行速度。

    解:本题答案为:快表。

    【例4-3-24】某分页存储管理中,页表如表4.3所示,页长为4KB,则地址转换机构将逻辑地址12293转换成物理地址 。

    表4.3 一个页表

    页号 块号

    0 2

    1 5

    2 6

    3 8

    4 3

    5 11

    解:12293=3×4KB+5,对应3号页的物理块块号为8,所以物理地址=8×4KB+5=32773。本题答案为:32773。

    【例4-3-25】某分页存储管理中,页面大小为4KB,某进程的页号0~8对应的物理块号分别为8、9、10、15、18、20、21、22、23。则该进程的逻辑地址05AF8H对应的物理地址是 。

    解:页面大小4KB=212B,05AF8H对应的二进制为0000 0101 1010 1111 1000(后12位为页内地址),对应5号页的物理块块号为20(对应的二进制数10100),所以物理地址=10100||1010 1111 1000=10100||1010 1111 1000=14AF8H(||表示地址拼接)。本题答案为:14AF8H。

    3. 判断题

    【例4-3-26】判断以下叙述的正确性。

    (1)在分页存储管理中,用户应将自己的程序划分成若干相等的页。

    (2)在分页存储管理中,页的大小是可以不相等的。

    (3)在分页存储管理中,作业装入主存后,其地址是连续的。

    (4)在分页存储管理中,作业的页面大小和内存物理块大小可以不相同。

    (5)在基本分页存储管理中,一个作业必须全部装入内存才能运行。

    (6)在基本分页存储管理中,一个作业的逻辑地址为12位,则逻辑地址空间的容量为212B。

    (7)在基本分页存储管理中,一个作业的逻辑地址由页号和页内地址两部分组成。

    (8)快表位于内存的一个特殊区域中。

    解:(1)错误。分页存储管理中,分页过程是由操作系统完成的,用户不能干预。

    (2)错误。在分页存储管理中,所有页的大小是相等的。

    (3)错误。在分页存储管理中,作业装入主存后,分配在不同的页面中,页之间不一定连续,所以作业的地址不一定是连续的。

    (4)错误。在在分页存储管理中,为了便于实现,通常作业的页面大小和内存物理块大小相等。

    (5)正确。

    (6)正确。

    (7)正确。

    (8)错误。快表是一种特殊的相联存储器,不属于内存,其存取速度比内存快。

    4. 问答题

    【例4-3-27】某分页系统的逻辑地址为16位,其中高6位为页号,低10位为页内偏移量,则在这样的地址结构中,请回答:

    (1)一页有多少个字节?

    (2)逻辑地址可有多少页?

    (3)一个作业最大的地址空间是多少字节?

    解:(1)由于逻辑地址中低10位为页内偏移量,所以每页的大小=210字节。

    (2)由于逻辑地址中高6位为页号,所以共有26个页面。

    (3)由于逻辑地址共有16位,所以一个作业最大的地址空间是216字节。

    【例4-3-28】在某个分页管理系统中,某一个作业有4个页面,被分别装入到主存的第3、4、6、8块中,假定页面和块大小均为1024字节,当作业在CPU上运行时,执行到其地址空间第500号处遇到一条传送命令:

    MOV 2100,3100

    请计算出MOV指令中两个操作数的物理地址。

    解:在页表中,逻辑页(0,1,2,3)对应物理块(3,4,6,8),页面大小L为1024字节。

    逻辑地址A1=2100,页号P1=(int)(2100/1024)=2,页内偏移量W1=2100-2×1024=52,对应的物理块号为6,则A1对应的物理地址E1=6×1024+52=6196。

    逻辑地址A2=3100,页号P2=(int)(3100/1024)=3,页内偏移量W2=3100-3×1024=28,对应的物理块号为8,则A2对应的物理地址E2=8×1024+28=8220。

    【例4-3-29】对一个将页表存放在内存中的分页系统,请回答:

    (1)如果访问内存需要0.2?s,一个数据的有效访问时间是多少?

    (2)如果加一个快表,且假定在快表中找到页表项的命中率为90%,则访问一个数据的有效访问时间又是多少(假定查快表需要花费的时间为0)?

    解:(1)在分页系统中,访问一个数据需要2次内存访问,所以有效访问时间为:2×0.2=0.4us。

    (2)在增加快表后,访问一个数据时先在快表中查找,若未找到再在页表中查找。快表命中只需0.2us,快表未命中需0.4us,则有效访问时间为90%×0.2us +10%×0.4us=0.22us。

    【例4-3-30】已知某分页系统,主存容量为64KB,页面大小为1KB,对于一个4页的作业,其0、1、2、3页分别被分配到主存的2、4、6、7块中。

    (1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。

    (2)以十进制的逻辑地址1023为例,画出地址变换过程图。

    解:(1)对上述逻辑地址,可先计算出它们的页号和页内偏移量(逻辑地址除以页面大小,得到的商为页号,余数为页内偏移量),然后通过页表转换成对应的物理地址。

    对于逻辑地址1023:计算(int)1023/1KB,得到页号P1=0,页内偏移量W1=1023,查页表找到对应的物理块号为2,故物理地址E1=2×1KB+1023=3071。

    对于逻辑地址2500:计算(int)2500/1KB,得到页号P2=2,页内偏移量W2=452,查页表找到对应的物理块号为6,故物理地址E2=6×1KB+452=6596。

    对于逻辑地址3500:计算(int)3500/1KB,得到页号P3=3,页内偏移量W3=428,查页表找到对应的物理块号为7,故物理地址E3=7×1KB+428=7596。

    对于逻辑地址4500:计算(int)4500/1KB,得到页号P4=4,页内偏移量W4=404,因页号不小于页表长度,故产生越界中断。

    (2)逻辑地址1023的地址变换过程如图4.27所示。

    图4.27 逻辑地址1023的地址变换过程

    【例4-3-31】某系统采用分页存储管理方式,设计如下:页面大小为4KB,允许用户虚地址空间最大为16页,允许系统物理内存最多为512个内存块。试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位?

    解:页面大小L=4KB=212字节,即页内偏移量占12位。由于物理块大小等于页面大小,所以物理块大小为212字节,物理块位数占12位。

    允许用户虚地址空间最大为16页=24页,即页号占4位。

    允许系统物理内存最多为512个内存块=29个内存块,即内存块位数占9位。

    虚地址寄存器位数=页号位数+页内偏移量位数=4+12=16位。

    物理地址寄存器位数=物理块位数+内存块位数=12+9=21位。

    【例4-3-32】在一个分页存储管理系统中,页的大小为2KB。设主存容量为512KB,描述主存分配的位示图如图4.28所示,0表示未分配,1表示已分配,此时系统要将一个9KB的作业装入内存,回答以下问题:

    (1)为作业分配内存后,请给出该作业的页表(分配内存时首先分配内存的低地址端)。

    (2)分页存储管理有无碎片存在?若有,会存在什么碎片?为该作业分配内存后,会产生零头吗?如果产生,碎片大小为多少?

    (3)若某系统采用分页存储管理,内存容量为64MB,也采用位示图管理内存,页面大小为4KB,该位示图占用多大内存?

    解:(1)因作业大小为9KB,所以需要5(9KB/2KB上取整=5)个物理块,查位示图,从上向下、从左向右找值为0的块的块号,依次分配给0~4页,对应的页表如表4.4所示。

    1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1

    物理块

    装入时刻

    1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0

    21

    250

    0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1

    9

    140

    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    11

    300

    1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0

    5

    160

    ...

    32

    270

    图4.28 内存位示图

    表4.4 一个页表

    页号 块号

    0 6

    1 18

    2 22

    3 23

    4 27

    (2)分页存储管理有碎片存在,分页存储管理存在内部碎片,为该作业分配内存会产生大小为1KB的内部碎片。

    (3)64MB的内存中有64MB/4KB=16KB个物理块,每块使用1位二进制,所以位示图大小为16K位,即16K位/8=2KB。

    【例4-3-33】为何引入多级页表?多级页表是否影响速度?

    解:早期的内存空间和进程空间都比较小,一个进程的页表长度也较小,可以在内存分配一个连续的存储区域保存进程的页表。但随着内存空间和进程空间的快速增长,页表越来越大,单级页表的存放遇到困难。例如,对于长度为232B的逻辑地址空间,页面长度定义为212(4KB),则一个进程最多可以拥有220个页面,也就是说系统需要提供长度为220项的连续页表存储区,这是很困难的。为此常将页表分为多级进行存放,例如对于上述例子,将220分为210×210两级,一级称为外页表,另一级称为内页表,此时外页表和内页表的长度都在210以内。可以很自然地把二级页表扩展为多级页表.显然,多级页表会降低地址映射的速度,但通过快表仍可以将效率保持在合理的范围内。

    例如对于4级页表,假定快表的命中率为98%,快表与内存的访问时间分别为20ns和100ns,那么,当快表命中时,需访问一次快表,得到主存地址后再访问一次主存得到该地址的数据,有效访问时间为20ns+100ns;当快表未命中时,需访问一次快表,未命中,然后访问4级页表(4次访问主存)得到主存地址,最后访问一次主存得到该地址的数据,有效访问时间为20ns+500ns。所以在这样的页表组织中平均有效访问时间为:EAT=98%×(20+100)+2%×(20+500)=128ns,额外的开销是128-100=28ns。


    更多相关内容
  • 2、输入块(页)的大小,通过模拟位示图为本作业分配内存空间建立相应的页表(长度不定); 3、录入逻辑地址转换成相应的物理地址 4、扩充页表,变成请求的二维页表(增加存在位等)完成地址转换。 5、输入分配给...
  • 要求实现:页表的数据结构、分页式内存空间分配及回收(建议采用位图法)、地址重定位、页面置换算法(从FIFO,LRU,NRU中任选一种)。 提示:可先用动态申请的方式申请一大块空间,然后假设该空间为内存区域,对该...
  • 分页式存储管理

    2012-06-07 17:11:18
    (1) 给出初态(页表、存储分块表等);...分配时,参数为进程名及请求分配的内存空间大小----字节数或页数。 回收时,参数为进程名。 (3) 每次分配或回收后,显示页表、存储分块表等的内容, 无法分配时,给出回应信息。
  • 分页式、分段式和段页式存储2.1 分页式存储2.2 分段式存储2.3 段页式存储 1. 进程虚拟空间 在32位的操作系统下,总共有32根地址线(32字节),而每根地址线只能表示两种电信号,即0:低电频,1:高电频,因此对应到...


    1. 进程虚拟空间

    在32位的操作系统下,总共有32根地址线(32字节),而每根地址线只能表示两种电信号,即0:低电频,1:高电频,因此对应到内存中,每个程序在运行时会分配4G的空间(1G = 210MB = 220KB=230B)。可画出对应的程序虚拟空间如下图:

    在这里插入图片描述
    数据段中存的是初始化的数据、未初始化的数据和一些静态的数据

    虽说,从刚学C开始,老师就经常讲这个,但是我们真的对他了解吗?

    1.1 探索进程虚拟空间

    我们首先用一段代码,来看一下进程创建后,父进程和子进程的进程虚拟空间是怎么样的,我们可以给一个全局变量,然后调用fork函数创建出子进程,在子进程中查看全局变量的地址,和父进程进行比较。

    代码如下:
    在这里插入图片描述
    运行结果如下:
    在这里插入图片描述
    可以发现父子进程中g_val的值都为0,且地址相等

    值都为0都可以理解,因为之前说过创建出的子进程会拷贝父进程大部分的PCB,其中包括了内存指针,内存指针指向的是进程的虚拟空间,因此子进程也拷贝了父进程的进程虚拟空间,所以g_val的值相等是可以理解的,但是为什么地址会相等呢?按理说,如果地址相等的话,在子进程中对g_val 进行修改的话,父进程中g_val的值也会改变,那创建出的子进程就没多大意义了。话不多说,我们实际验证一下。

    1.2 疑惑验证

    还是上面的代码,这次我们直接在子进程中修改g_val的值,看看父进程中会发生什么变化,按照之前来说的,地址一样,在子进程中对其进行修改,父进程也会进行相应的修改。

    代码如下:
    在这里插入图片描述
    运行结果如下:
    在这里插入图片描述

    !!,奇怪奇怪,很是奇怪,地址是相同的,在子进程中进行了修改,但是父进程却没有随预想的那样发生改变,那为什么会这样呢?接着向下看。

    关于进程的相关概念,可以看我之前写的详解进程的相关概念

    2.分页式、分段式和段页式存储

    在上面的探索中,我们发现父子进程,输出地址是一致的,但是变量内容不一样,由此可引出以下结论:

    • 变量内容不一样,所以父子进程输出的变量绝对不是同一个变量
    • 但地址值是一样的,说明,该地址绝对不是物理地址!
    • 在Linux地址下,这种地址叫做 虚拟地址
    • 我们在用C/C++语言所看到的地址,全部都是虚拟地址!物理地址,用户一概看不到,由OS统一管理

    因此,程序员在代码中看到的地址并不是真正的物理内存地址,而是OS内核虚拟出来的地址,虚拟地址并不能直接的保存数据,保存数据是在物理内存中进行保存。那么问题来了:进程是如何通过虚拟地址找到物理内存的地址呢?

    这里就用到了页表,它是一种映射关系,OS用它来通过虚拟地址来找到物理内存中它所映射的那块空间地址。

    在这里插入图片描述
    此图也说明了程序在物理内存中的存储时离散的。

    疑惑解答

    • 子进程在被创建时,子进程会拷贝父进程的大量的PCB内容,其中就有内存指针,而内存指针对应着进程虚拟地址,进程虚拟地址中又保留有页表的信息,凭借着和父进程相同的页表,子进程可以访问到和父进程相同的值,由于虚拟地址都一样,因此,我们看到的打印出的父子进程的地址就是一样的,对应的物理地址其实也是一样的。
    • 当然,这只是基于子进程只是单纯的访问,并不做修改的情况,如果当子进程中修改了某个值,那么OS会立即在物理内存中划分出一段空间,用来表示子进程的空间

    不想看话语?直接看图
    如图:

    初始时:
    在这里插入图片描述
    子进程发生修改,修改为100
    在这里插入图片描述

    这种方式也被称为写时拷贝

    碎片知识:进程虚拟地址空间构成了进程的独立性,即一个进程修改数据,不会影响另一个进程

    2.1 分页式存储

    分页式存储:将虚拟地址空间分成了一页一页的小块,将物理地址分成了一块一块的小块,一块的大小是4096字节。

    通过虚拟地址查找物理地址的方法:页号+页内偏移

    • 页号:虚拟地址 / 块大小
    • 页内偏移:虚拟地址 % 块大小

    在这里插入图片描述

    2.2 分段式存储

    分段式:和分页式一样,只不过是将物理地址分成了一段一段的小段(这一个小段通常都是大于一个小块的)

    通过虚拟地址查找物理地址的方法:段号+页内偏移

    • 段号:虚拟地址 / 段大小
    • 页内偏移:虚拟地址 % 段大小

    在这里插入图片描述

    2.3 段页式存储

    段页式:将一个页表分为了两个,一个为页表,一个为段表,物理空间和分页式一样,被分为一块一块的

    通过虚拟地址查找物理地址的方法:段号+页号+页内偏移

    • 段号:虚拟地址 / 段大小
    • 页号:虚拟地址 / 块大小
    • 页内偏移:虚拟地址 % 块大小

    在这里插入图片描述

    展开全文
  • 模拟请求分页式存储管理(OS实验)

    千次阅读 2021-05-17 16:46:00
    模拟请求分页式存储管理(操作系统实验) 1. 实验要求 内存总容量4MB,页面大小4KB。 用户自定义创建进程(进程名和所需存储空间),随机生成该进程的页面访问序列。 实现页面序列的访问过程,记录页面状态、访问...

    1. 实验要求

    • 内存总容量4MB,页面大小4KB。
    • 用户自定义创建进程(进程名和所需存储空间),随机生成该进程的页面访问序列。
    • 实现页面序列的访问过程,记录页面状态、访问次数和加载入内存的时间。
    • 内存空间满时,可通过LRU、FIFO和OPT中的任意调度算法实现页面的置换,要求只能置换当前页面所在进程的的其他页面。
    • 页面序列加载完毕后,输出当前进程的页面内容
    • 实现查看内存分配状况的功能

    2. 语言技巧总结(待完善)

    ①vector容器

    ②iterator迭代器

    ③结构体变量的初始化

    ④rand和srand生成随机数

    ⑤休眠函数Sleep()

    ⑥计时函数clock()

    ⑦取整函数floor()和ceil()

    3. 源代码

    #include <iostream>
    #include <string>
    #include <vector>
    #include <cstring>
    #include <ctime>
    #include <cmath>
    #include <iterator>
    #include <cstdlib>
    #include <windows.h>
    using namespace std;
    
    //页表项
    typedef struct Page_item
    {
        bool status;            //页面所在位置,true为内存,false为外存
        int block_num;          //内存块号
        int visit_num;          //访问次数
        bool change;            //内容是否更改
        double into_time;       //首次访问时间
        double last_visit_time; //最后访问时间
    } Page_item;
    
    //页表
    typedef vector<Page_item> Page;
    
    //进程控制块
    typedef struct P
    {
        string name; //进程名
        int size;    //页数
        Page page;   //页表
    } P;
    
    vector<P> all;               //所有进程信息表
    bool M[1000];                //总内存4M,内存块大小4k
    int occupy;                  //当前内存块占用状态
    int list[100];               //访问序列
    clock_t startTime, tempTime; //时间记录
    int note[1000];//用OPT置换时记录页面的预访问次数
    
    //LRU页面置换
    void LRU(Page &page, Page_item &page_item)
    {
        vector<Page_item>::iterator it = page.begin();  //遍历迭代器
        vector<Page_item>::iterator earliest_it = page.begin(); //上次最早访问迭代器
        for (; it != page.end(); it++)
            if (it->status && it->last_visit_time < earliest_it->last_visit_time)
                earliest_it = it;
        //新页面换入
        page_item.status = true;
        page_item.block_num = earliest_it->block_num;
        tempTime = clock();
        page_item.into_time = page_item.last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
        page_item.visit_num = 1;
        //旧页面换出
        earliest_it->status = false;
    }
    
    //FIFO置换策略,与LRU相似,找出最早加载到内存的页面来置换
    void FIFO(Page &page, Page_item &page_item)
    {
        vector<Page_item>::iterator it = page.begin();
        vector<Page_item>::iterator earliest_it = page.begin();
        for (; it != page.end(); it++)
            if (it->status && it->into_time < earliest_it->last_visit_time)
                earliest_it = it;
        page_item.status = true;
        page_item.block_num = earliest_it->block_num;
        tempTime = clock();
        page_item.into_time = page_item.last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
        page_item.visit_num = 1;
        earliest_it->status = false;
    }
    
    //OPT置换策略
    void OPT(Page &page, Page_item &page_item, int temp_pos, int list_length, int p_size)
    {
        //记录数组初始化
        for (int i = 0; i < p_size; i++)
            note[i] = -1;
        //当前已处于内存中的进程页面记录初始化
        vector<Page_item>::iterator it = page.begin();
        for (int i = 0; it != page.end(); it++, i++)
            if (it->status)
                note[i] = 0;
        //遍历待访问序列,记录到note中
        for (int i = temp_pos; i < list_length; i++)
            if (note[i] != -1)
                note[list[i]]++;
        //置换出将来最少用到的页面
        int will_least;
        int minVal = 99999;
        for (int i = 0; i < p_size; i++)
            if (note[i] != -1 && note[i] < minVal)
            {
                minVal = note[i];
                will_least = i;
            }
        //新页面换入
        page_item.status = true;
        page_item.block_num = page[will_least].block_num;
        tempTime = clock();
        page_item.into_time = page_item.last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
        page_item.visit_num = 1;
        //旧页面换出
        page[will_least].status = false;
    }
    
    //创建并加载进程到内存
    void createProcess()
    {
        //创建进程
        string temp_name;
        int temp_size, count;
        cout << "请依次输入进程的名称和大小(k):" << endl;
        cin >> temp_name >> temp_size;
        P process = {
            .name = temp_name,
            .size = ceil(temp_size / 4.0)};
        cout << "进程" + process.name + "已经创建成功,共" << process.size << "页" << endl;
    
        //生成访问序列
        srand((unsigned)time(NULL)); //每次生成随机数前,更换随机数种子为当前时间
        count = rand() % 20 + 5;    //访问序列长度为5——25,可根据需要更改
        for (int i = 0; i < count; i++)
            list[i] = rand() % process.size;
        cout << "随机产生的页面访问序列为:";
        for (int i = 0; i < count; i++)
            cout << list[i] << ' ';
        cout << endl;
    
        //初始化页表
        Page page;
        for (int i = 0; i < process.size; i++)
        {
            Page_item temp = {
                .status = false};
            page.push_back(temp);
        }
        process.page = page;
    
        //遍历访问序列
        for (int i = 0; i < count; i++)
        {
            tempTime = clock();
            if (!process.page[list[i]].status) //页面未加载
            {
                if (occupy == 1000) //内存已满
                {
                    cout << "内存已满!" << endl;
                    if (i == 0)
                    {
                        cout << "当前进程无可调出页面,只能调出其他进程的页面,本程序暂不支持此操作!" << endl;
                        break;
                    }
                    cout << "请选择页面置换的调度方式:" << endl
                         << "1.LRU(优先调出最久未使用的页面)" << endl
                         << "2.FIFO(优先调出最早进入内存的页面)" << endl
                         << "3.OPT(优先调出以后最不经常使用的页面)" << endl;
                    char choice;
                    cin >> choice;
                    switch (choice)
                    {
                    case '1':
                        LRU(process.page, process.page[list[i]]);
                        cout << "置换成功!" << endl;
                        break;
                    case '2':
                        FIFO(process.page, process.page[list[i]]);
                        cout << "置换成功!" << endl;
                        break;
                    case '3':
                        OPT(process.page, process.page[list[i]], i, count, process.size);
                        cout << "置换成功!" << endl;
                        break;
                    default:
                        cout << "输入有误,本页面调入失败" << endl;
                        break;
                    }
                }
                else
                {
                    int pos = rand() % 1000;
                    int next_pos;
                    for (int j = 0; j < 1000; j++)
                    {
                        next_pos = (pos + j) % 1000;
                        if (M[next_pos])
                        {
                            M[next_pos] = false;
                            occupy++;
                            process.page[list[i]].status = true;
                            process.page[list[i]].visit_num = 1;
                            process.page[list[i]].block_num = next_pos;
                            process.page[list[i]].into_time = process.page[list[i]].last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
                            break;
                        }
                    }
                }
            }
            else    //页面已加载
            {
                process.page[list[i]].visit_num++;
                process.page[list[i]].last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
            }
            Sleep(100); //每次加载页面休眠100ms
        }
    
        //输出当前进程的页表
        vector<Page_item>::iterator it = process.page.begin();
        cout << endl;
        cout << "进程" << process.name << "的页表如下" << endl;
        for (int i = 0; it != process.page.end(); it++, i++)
        {
            cout << "页号:" << i << "  ";
            if (it->status)
                cout << "主存块号:" << it->block_num << "  "
                     << "访问次数:" << it->visit_num << "  "
                     << "首次访问时间:" << it->into_time << "ms"
                     << "  "
                     << "最后访问时间:" << it->last_visit_time << "ms"
                     << "  "
                     << endl;
            else
                cout << "未调入主存" << endl;
        }
        cout << endl;
        all.push_back(process);
    }
    
    //打印当前内存使用情况
    void showStorage()
    {
        vector<P>::iterator it = all.begin();
        cout << "内存占用情况如下:" << endl;
        cout << "进程名"
             << "  "
             << "占据内存块数" << endl;
        for (; it != all.end(); it++)
            cout << it->name << "      " << it->size << endl;
    }
    
    int main()
    {
        memset(M, 1, sizeof(M));
        occupy = 0;
        char choice;
        bool flag = true;
        startTime = clock();
        while (flag)
        {
            cout << "请输入要进行的操作:" << endl
                 << "1.查看当前内存中进程占用情况" << endl
                 << "2.创建新进程" << endl
                 << "3.退出" << endl;
            cin >> choice;
            switch (choice)
            {
            case '1':
                showStorage();
                break;
            case '2':
                createProcess();
                break;
            case '3':
                flag = false;
                break;
            default:
                cout << "输入有误" << endl;
                break;
            }
        }
        return 0;
    }
    
    展开全文
  • 分页式存储(C语言实现)

    千次阅读 2020-11-30 19:18:29
    分页式存储(C语言实现) 分段允许进程的物理地址空间是非连续的。分页是提供这种优势的另一种内存管理方案。然而,分页避免了外部碎片和紧缩,而分段不可以。 不仅如此,分页还避免了将不同大小的内存块匹配到交换...

    分页式存储(C语言实现)

    分段允许进程的物理地址空间是非连续的。分页是提供这种优势的另一种内存管理方案。然而,分页避免了外部碎片和紧缩,而分段不可以。

    不仅如此,分页还避免了将不同大小的内存块匹配到交换空间的问题,在分页引入之前采用的内存管理方案都有这个问题。由于比早期方法更加优越,各种形式的分页为大多数操作系统采用,包括大型机的和智能手机的操作系统。实现分页需要操作系统和计算机硬件的协作。

    基本方法

    分页存储管理是将一个进程逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从0开始,如第0页、第1页等。相应地,也把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或页框存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。将每个进程的页面号和相应的内存块号的对应关系存储在页面变换表中,这样就可以通过地址变换机构寻找到某个逻辑地址在内存中的实际物理地址。

    代码实现

    #include <stdio.h>
    #include <stdlib.h>
    #define BLOCKSIZE  200//定义块的大小
    #define COUNT 100  // 定义内存块总数 
    
    enum STATUS {OCCUPIED,FREE//内存块的状态
    		} block[COUNT]; //建立内存块数组 记录内存信息 
    
    //进程链表
    typedef struct ProcessInfo {
    	int PId;  //记录进程ID 
    	int pages; //记录页数 
    	int * addr; //定义一个整形指针指向由动态数组构成的页面变换表 
    	struct ProcessInfo * next;//链表指针指向下一个结点 
    }P;
    struct ProcessInfo *head;//定义链表头指针
    void run();//程序菜单 
    void Allocate(int id,int size);//为进程分配内存:参数(进程ID 和所需内存大小size) 
    void Releace(int id);//释放一个进程所占的内存:参数(进程ID) 
    void Locate(int id,int log);//查看进程的逻辑地址对应的物理地址:参数(进程ID,逻辑地址) 
    void dispaly();//显示 进程单链表 
    void mem(); //显示内存未被分配的块 
    //看进程的逻辑地址对应的物理地址
    void Locate(int id,int log){ 
    	struct ProcessInfo *p_move;//定义一个结构体指针 用于遍历链表 
    	int page,j;//page记录所在页数,j记录页内地址 
    	p_move=head;
    	j=log%BLOCKSIZE;
    	while(p_move->PId!=id&&p_move->next!=NULL){//遍历链表 直到找到该进程或遍历整个链表后结束 
    		p_move=p_move->next;
    		} 
    	if(p_move->PId==id){//判断是否找到 
    		if(j==0) {//计算逻辑页号 
    		page=log/BLOCKSIZE;
    	}else	{
    		page=log/BLOCKSIZE+1;
    	}
    		printf("物理地址为:%d\n",(p_move->addr[page-1])*BLOCKSIZE+j);//page-1是因为数组下标从零开始 而页号是从1开始 
    	}
    	else{
    		printf("没有找到!!!\n");
    	}
    }
    //遍历进程表 
    void display() {
    	P* p_move;
    	p_move=head;
    	printf("ID\tPages\n");
    	while(p_move!=NULL) {//遍历整个单链表 
    		printf("%d\t%d\n",p_move->PId,p_move->pages);
    		p_move=p_move->next;
    	}
    }
    //为进程分配内存 
    void Allocate(int id,int size) {
    	int pages,num=0,i,j;
    	struct ProcessInfo *p_move,*p_new;//p_move 用于遍历数组 ,p_new用于保存进程信息 
    	p_move=head;//将头指针的值传给p_move 
    	while(p_move!=NULL) {//遍历整个链表判断ID是否有重复  
    		if(p_move->PId==id) {
    			printf("分配失败,进程ID相同!!!\n");
    			return;//存在ID相同 退出插入 
    		}
    		p_move=p_move->next;//p_move指向下一个结点 
    	}//计算分页的页数 
    	if(size%BLOCKSIZE==0) {
    		pages=size/BLOCKSIZE;
    	}else
    		pages=size/BLOCKSIZE+1; 
    	for(i=0; i<COUNT; i++) {//遍历内存状态表查看空闲区是否足够 
    		if(block[i]==FREE) {
    			num++;
    		}
    		if(num>=pages)
    			break;//若足够跳出循环 
    	}
    
    	if(num<pages) {//不够则退出插入 
    		free(p_new); 
    		printf("分配失败,空间不足!!\n");
    		return;
    	}
    	p_new=(P *)malloc(sizeof(P));//对p_new进行初始化 
    	p_new->PId=id;//将进程ID保存到p_new中 
    	p_new->pages=pages;//将页面个数存入到p_new中 
    	p_new->addr=(int *)malloc( sizeof(int)*pages );//申请pages个整形存储空间并将首地址传到addr中 
    	for(i=0; i<pages; i++) {//为进程分配内存空间 
    		for(j=0; j<COUNT; j++) {
    			if(block[j]==FREE) {
    				p_new->addr[i]=j;//将第i页对应内存块好存到addr[]中 
    				block[j]=OCCUPIED;
    				break;
    			}
    		}
    	}
    	p_move=head;//重新将链表首地址传给p_move 
    	if(head==NULL) {//判断链表是否为空 
    		head=p_new;// 将P_new的地址传给head 
    		p_new->next=NULL;//p_new指向空 
    	} else {
    		while(p_move->next!=NULL) {//链表不为空则 找到最后一个节点 
    			p_move=p_move->next;
    		}
    		p_move->next=p_new;//将p_new插入到最后一个节点后 
    		p_new->next=NULL;//让p_new指向空 
    	}
    	printf("分配成功!!\n");
    	return ;
    }
    //释放一个进程 
    void Releace(int id) {
    	struct ProcessInfo *p_move,*p_d;//p_move遍历链表 p_d保存被删除节点的前一个节点 
    	int i;
    	p_move=head;
    	while(p_move->PId!=id&&p_move->next!=NULL){//遍历链表找到相应的进程 
    		p_d=p_move;//p_d记录被删节点的前一个节点 
    		p_move=p_d->next;
    	} 
    	if(p_move->PId==id){//判断是否找到 
    		for(i=0;i<p_move->pages;i++){//遍历页面变换表释放相应的内存 
    				block[p_move->addr[i]]=FREE;
    		}
    		free(p_move->addr);//释放页面变换表 
    		if(p_move==head){//删除对应的节点 
    			head=p_move->next;
    			
    		}else{
    			p_d->next=p_move->next;
    		}
    		free(p_move);//释放被删除进程的节点 
    		printf("删除成功!!!\n");
    	}
    	else{
    		printf("没有找到!!!\n");
    	}
    }
    //遍历内存块 查找未被分配的内存块 
    void mem(){
    	int i;
    	printf("内存分区:");
    	for(i=0;i<COUNT;i++){
    		if(block[i]==FREE)
    		printf("%d\t",i);
    	}
    	printf("\n"); 
    }
    void run() {
    	int num,id,size;
    	while(1) {
    		display();
    		size=0;
    		id=-1;
    		printf("**********************\n");
    		printf("1:分配进程\t2:释放进程\t3:查看物理地址\t4:查看内存空闲内存块\t5:退出\n");
    		scanf("%d",&num);
    		switch(num) {
    			case 1:
    				printf("输入进程ID和所需内存空间大小:");
    			 	scanf("%d %d",&id,&size);
    				Allocate(id,size);
    				break;
    			case 2:
    				printf("请输入进程ID:");
    				scanf("%d",&id);
    				Releace(id);
    				break;
    			case 3: 
    			 	printf("输入进程ID和逻辑地址:");
    			 	scanf("%d %d",&id,&size);
    				Locate(id,size);
    				break; 
    			case 4: 
    				mem();
    				break;
    			case 5:
    				return ;
    		}
    		printf("**********************\n");
    		
    	}
    }
    
    void main() {
    	int i;
    	head=NULL;//初始化进程表 
    	for(i=0; i< COUNT; i++) {//初始化内存块 
    		block[i]=FREE;
    	}
    	run();
    }
    

    结果

    为进程分配内存
    在这里插入图片描述
    查看物理地址
    在这里插入图片描述
    释放进程
    在这里插入图片描述

    展开全文
  • 2、输入块(页)的大小,通过模拟位示图为本作业分配内存空间建立相应的页表(长度不定); 3、录入逻辑地址转换成相应的物理地址 4、扩充页表,变成请求的二维页表(增加存在位等)完成地址转换。 5、输入分配给...
  • 操作系统实验——分页式存储管理

    千次阅读 2021-10-11 18:33:37
    熟练掌握分页式管理基本原理,并在实验过程中体现内存空间分配回收、地址转换过程。 掌握利用位示图管理内存与置换空间分配与回收。 掌握基本的位运算 掌握请求式分页存储管理基本原理,并在试验过程中体会...
  • 基本分页存储管理方式

    千次阅读 2022-03-11 13:46:40
    基本分页存储管理方式~
  • 操作系统 请求分页式存储管理 实验要求 通过编写分页式存储管理的模拟程序,加深对页式存储管理方式的理解,熟悉逻辑地址到物理地址的转换过程,掌握虚拟存储管理中的页面调度算法,认识分页式虚拟存储系统中缺页...
  • 注:本文讨论的是适合多道程序的内存分配...2.1 基本分页式内存分配管理 2.1.1 基本分页式内存思想与方法 2.1.2 进程逻辑地址与内存物理地址如何转换? 2.1.3 页面在内存中的起始地址——页表 操作...
  • 非连续分配管理方式分页存储管理...但是如果使用非连续分配管理方式,作业要求的1G内存空间可以分散的分配在内存各个区域,当然,这需要额外的空间存储分散区域的索引。 根据分区大小是否固定分为分页存储管理方式和
  • 2.能够模拟内存的分页式分配和回收过程,可查看内存分配位示图和进程页表; 3.可根据内存分配状态进行地址转换。 4.能够模拟基于虚拟存储器的内存分配和回收过程,可查看交换空间位示图和扩 展的页表; 5.在虚拟...
  • 【操作系统】分页式存储管理习题

    千次阅读 2020-12-30 10:51:31
    操作系统——分页式存储管理习题习题一习题二参考链接 习题一 在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096字节,现有一逻辑地址为2F6A(H),且第0,1,2页依次存放在物理块5,10,11中,问相应的...
  • 通过实现一个操作系统的内存管理的模拟系统,观察内存空闲分区管理、内存分配和回收过程,了解内存管理技术等特点,掌握内存管理中的分配、回收和置换算法,加深对请求调页系统的原理和实现过程的理解。
  • 【操作系统——内存基本分页存储管理】

    多人点赞 热门讨论 2022-08-10 00:08:32
    非连续分配方式有根据分区的大小是否固定,分为页式存储管理和段式存储管理,而在页式存储管理当中又将作业运行是否需要将全部的页面都调入内存分为基本分页式存储管理和请求分页式存储管理。...
  • 这样就以页的方式来管理存储块,就叫分页式存储管理。 在分配存储块时,会根据作业的逻辑地址的大小计算所需要多少个存储块,然后查找空闲块并更新空闲块的状态为占用;回收存储块时,会将作业关联的所有空闲块的...
  • 2020/4/27 在家的网课,无聊,记录一下分页,分段,段页式存储笔记 昨天刚学了分页存储,听得我一脸懵逼,好在课下花了很长时间才弄懂。 1 分页存储管理 1.分页存储管理方式 分页存储管理是解决存储碎片的一种方法...
  • 分页存储管理方式

    千次阅读 2020-04-08 12:40:48
    原理 分页式存储管理的原理: 假设一个进程大小1KB,我们把1KB分成若干个大小相同的块,叫做一个页面或一页;...基本分页式存储管理(简单分页式存储管理)的原理: 当一个作业需要被调入内存...
  • 概括的挺详细的,然后我加上了纯分页系统和请求式分页系统的基本概念,也对有些部分稍作修改 一、分页存储管理 1、基本概念(页面和物理块) 将一个进程的逻辑地址空间划分成若干大小相等的部分,每一部分称为页或...
  • 分页存储存储管理方式详解

    万次阅读 多人点赞 2020-04-22 21:38:18
    分页存储存储管理方式详解离散分配方式分页储存管理方式页面与页表页面物理块逻辑地址结构页表快表(TLB,Translation Look aside Buffer)一级页表的缺陷两级多级页表反置页表反置页表的提出基于反置页表的地址转换...
  • 分区式存储管理最大的缺点是碎片问题严重,内存利用率低。究其原因,主要在于连续分配的限制,即它要求每个作用在内存中必须占一个连续的分区。 如果允许将一个进程分散地装入到许多不相邻的分区中,便可充分地利用...
  • 段页式存储管理方式 连续存储会产生许多的“碎片”,虽然“紧凑”方法可以将许多碎片拼接可以的大块空间,但需为之很大的开销。如果允许将一个进程直接分散的装入到许多不相邻的分区中,便可以充分利用内存空间。...
  • 结束否是没有模拟页式存储管理 8模拟页式存储管理9模拟页式存储管理2、核心部分(1)、 先进先出算法(FIFO)10模拟页式存储管理2、最近最少用算法(LRU)11模拟页式存储管理3、最佳置换算法(OPT)12模拟页式存储管理...
  • 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从0开始,如第0页、第1页等。相应地,也把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或页框(frame)...
  • 首先分配一片较大的内存空间,作为程序运行的可用存储空间; 建立应用程序的模型; 建立进程的基本数据结构及相应算法 建立管理存储空间的基本存储结构。 建立管理分页的基本数据结构与算法。 设计存储空间分配与...
  • 要求实现:页表的数据结构、分页式内存空间分配及回收(建议采用位图法)、地址重定位、页面置换算法(从FIFO,LRU,NRU中任选一种)。 提示:可先用动态申请的方式申请一大块空间,然后假设该空间为内存区域,对该...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,629
精华内容 9,451
热门标签
关键字:

分页式存储空间的分配