CH5-1连续分配存储管理

CH5存储器管理,5.1程序的装入和链接5.2连续存储空间管理5.3对换5.4分页式存储管理5.5分段式存储管理5.6虚拟存储管理,5.1程序的装入和链接,程序的装入程序的链接,程序的装入,绝对装入方式事先已知用户程序形成可执行模块后将驻留在内存的什么地方，编译程序在编译的时候直接产生实际存储地址的目标代码；,由绝对装入程序按照模块中提供的绝对地址，将程序和数据装入内存；,装入内存后，因为其中提供的均是绝对地址，因此调度到它运行时，不须再对其中的地址再作修改和变换；,程序中使用的绝对地址，既可由程序员直接给出，也可在编译或汇编时给出程序员给出：要求其熟悉内存的使用情况，并且程序一旦修改，可能会引起程序中所有绝对地址的改变；编译时产生：在编程时尽量采用符号地址，在编译或汇编时，再将这些符号地址转换成绝对地址；,可重定位装入方式,编译完成后，目标模块的起始地址通常都是从0开始，程序中的所有其它地址，也都是相对于起始地址0计算的；可重定位装入程序在将这些目标模块装入内存时，先要将目标模块中的相对地址全部转换成绝对地址，再装入内存;,例如：编制的程序编译完后，地址为00002020H，如果分给它的内存空间是从10000H开始的一段内存空间，那么在装入时，该目标程序的地址就从10000+0000H10000+2020H,如有一条语句：MOVA，2000H，则将转变成：MOVA，12000H,动态运行时装入方式,将装入模块装入内存后，并不立即进行地址转换，而是到程序真正要执行时才进行地址转换，因此装入内存后，装入模块中的地址依然是相对地址；,方便存储管理中的“对换”，以利于提高系统性能,程序的链接,指将经过编译后的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块可执行模块。,静态链接,A模块,B模块,C模块,CallBReturn,CallCReturn,Return,0,L-1,0,M-1,0,N-1,A模块JSR“L”Return,B模块JSR“L+M”Return,C模块Return,0,L-1,L,L+M-1,L+M,L+M+N-1,对各模块的相对地址进行修改为A、B、C最终要链接成一个模块，且执行的顺序为ABC，所以B应接在A的末尾，起始地址应为L-1+1，而C则因为接在B的末尾，所以起始地址应为L+M-1+1,换外部调用符号为具体地址将每个模块中所用的外部调用符号变成大的链接模块中的具体地址,装入时动态链接,用户源程序经编译后得到的目标模块，如A、B、C模块，是在装入时边装入边链接的,即：A模块在装入时，如需要调用B模块，就去外存找B模块，并将它装入内存，装入时修改其中的相对地址，B模块在装入时，又有调用C模块的语句，于是再找到C模块，将C模块调入内存，并修改其相对地址,运行时动态链接,将某些目标模块的链接，推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并将它链接至调用者模块上。,真正轮到A模块运行时，它要调用的可能只是B模块或C模块，如按装入时动态链接，则A模块在装入时也要将B、C模块一齐装入。如按运行时动态链接，则A模块在运行时，如满足条件1，则将B模块装入即可，如满足条件2，则将C模块装入即可。,5.2连续分配存储管理方式,指为一个用户程序分配一个连续的内存空间，有两种分配方式：单一连续分配方式分区式分配方式,单一连续分配方式,最早出现的一种存储器管理方式，在这种方式下，内存只驻留一道程序。,操作系统将内存分为两个分区：系统区：仅提供给OS用，一般驻留在内存的低址部分用户区：除系统区外的全部内存空间，提供给用户使用,单一连续分配方式,单一连续分配方式中的存储保护措施为了防止OS受到用户程序的破坏，较常用的方法是设一个基址寄存器（装有程序的最小物理地址）、一个界限寄存器（存放该程序的逻辑地址范围），由一个存储管理部件MMU来管理用户程序是否越界。,单一连续分配方式,方法是：每次执行一条指令，MMU都将程序中的逻辑地址映射为物理地址（相对地址+基址），然后将此物理地址与界限寄存器值比较，如果未超出，表示未越界，可以继续执行；如果超出，则产生一中断信号送至CPU，告诉它程序执行越界，终止。现代OS一般不用这种方法，重启即可。,单一连续分配的缺点,一个作业独占主存储空间，降低存储空间的利用率；处理器和外部设备串行工作；计算机的外围设备利用率不高,分区式分配方式,固定分区式分配动态分区式分配,固定分区式分配,实现思路将内存空间划分为若干个固定大小的分区，每个分区可装一道作业，当内存中划分成几个分区时，便允许几道作业并发运行；当某个分区的作业运行完毕，让出它所占有的这块内存时，系统便从外存的后备队列中挑选出另一个作业调入内存,划分分区的方法,分区大小相等：简单、不很合理，程序太大，分区不够用，无法正常运行，程序太小，分区利用率不够；分区大小不等：较合理。大程序放入大分区，小程序放入小分区；,固定分区式分配方式的内存分配,将这些分区根据大小进行排队，并为之建立一张分区使用表；,用户程序进入内存，首先由一个内存分配程序来查这张分区使用表，直到找到一个能满足要求、状态是“未分配”的一个分区，然后，将这个分区分配给它,固定分区式分配的缺点,每个分区的大小是固定的，必然造成空间的浪费,动态分区分配含义,根据用户程序的实际需要，动态地为之分配连续的内存空间，需要就分，再需要再分。实现多个作业对内存的共享，进一步提高内存资源利用率。,动态分区分配示例,操作系统,作业1,空闲区,作业2,空闲区,4K,10K,46K,52K,128K,操作系统,作业1,空闲区,作业2,空闲区,4K,10K,40K,46K,52K,128K,作业3,操作系统,作业1,空闲区,4K,10K,40K,128K,作业3,动态分区分配中用到的数据结构,空闲分区表空闲分区链,空闲分区表,用于为每个内存中尚未分配出去的分区设置一个表项，包括：分区序号、分区始址、分区大小、状态等等信息,空闲分区链,每个分区的起始部分：设置一些用于控制分区分配的信息，以及用于链接各分区的前向指针；分区尾部：则设置一后向指针，通过前后向指针将所有分区链接成一个双向链；每个分区的尾部还设有一状态位，当一个分区分配出去以后，该状态位由01，前后向指针无效，且前空闲分区与后空闲分区再相连；,动态分区分配算法,1）首次适应分配算法2）循环首次适应算法3）最优适应分配算法,首次适应分配算法,空闲分区按地址递增的次序排列；,在进行内存分配时，从空闲分区表（或空闲分区链）首开始顺序查找，直到找到一个能满足其大小要求的空闲分区；,按照分区分配请求的大小，从该分区中划出一块内存空间分配给请求者，余下的仍留在空闲分区表或空闲分区链中；,首次适应分配算法,低址部分不断被划分，留下许多难以利用的小的空闲分区，每次分区分配时都要检索小分区，浪费时间,循环首次适应算法,由首次适应算法演变而来,在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一空闲分区开始往下查找，直到找到第一个能满足要求的空闲分区为止,按照请求分配的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表或空闲分区链中,使内存中空闲分区分布更均匀，也减少了找空闲分区的开销，但是会导致缺乏大的空闲分区,最佳适应算法,要求空闲分区按大小递增的次序排列分配过程与首次分配算法相似,优点：每次为程序分配内存时，总是把既能满足要求，又是最小的空闲分区分给该程序，避免了大材小用；,缺点：每次划分完后剩下的往往是难以利用的、小的空闲分区。这样经多次请求划分后，系统中会剩下许多这样小的难以再利用的小空闲分区，即小碎片；,动态分区分配操作流程,m.sizeu.size,检索完否？,m.size-u.sizesize?,将该分区分配给请求者，修改有关数据结构,返回,Y,N,Y,继续检索,从表头开始查表,N,Y,将该分区从表或链中移出,返回,从该分区中划出与u.size大小相等的分区,请求分区大小：u.size；表中每个分区大小：m.size；系统认可的不可分割分区：size,N,动态分区分配的回收算法,AXB,AB,AX,A,XB,B,X,变为,变为,变为,变为,回收前,回收后,碎片问题所谓“碎片”，是指内存中无法被利用的小的空闲分区。,进行内存分配时可能会出现如下情况：,当一个作业申请一定数量的主存空间时，虽然此时空闲区的总和大于作业所申请的主存容量，但却没有单个空闲分区足够大，达到足以装下这个作业。,紧凑和拼接技术,指移动存储器中已分配作业到主存的一端，使本来分散的空闲区连成一个大的空闲区，以便能装入大的作业运行,0,300K,500K,600K,1000K,1200K,1500K,1900K,2100K,0,300K,500K,600K,800K,1200K,(a)初始分配,(b),例：,例：,(c),(d),0,300K,500K,600K,1000K,1200K,0,300K,500K,600K,1500K,1900K,2100K,注意的问题,移动会增加系统开销移动必须修改空闲分区表等信息，这些都增加了OS的工作量，所以应尽量减少移动的作业数和信息量,注意的问题,移动是有条件的不是任意一个作业都能随