1、,二、链接方式3、运行时动态链接-由于程序在每次运行时，可能运行的程序模块可能不同，在程序得到运行时才将用到的目标模块链接成完整的可执行的目标模块。,三、重定位-完成相对（逻辑）地址转换成内存物理（绝对）地址的工作。分为静态重定位和动态重定位。,5.2 连续空间分配 方式：单道连续、多道固定、多道可变5.2.1 单道连续分配,单道:指任一时刻内存只有一道作业，该作业连续存放于内存中。特点：易于理解，访问效率高、空间利用率低。,（1）内存空间安排：内存除存在OS外，余下的空间只供一个用户程序使用。,一、管理方法,（2）设置越界检查机构：用户程序每访问一次主存，越界检查机构将访问的地址与界地址寄存
2、器中的值比较。若越界，则终止其执行。,（3）覆盖（overlap）技术,引入原因：因内存小于作业的程序空间而引入覆盖。方法：将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用函数，由用户编程序时考虑调用。,例:下图的调用关系中,B不会调用C,C也不会调用B,所以过程B,C不必同时调入主存,同样D、E之间，D、E与F之间也有同样的关系。,多道：任一时刻内存可有多道作业，每道作业连续存放于内存.,5.2.2 多道固定划分法,一、固定划分管理方法,（1）将用户内存空间分成长度固定的若干块。每块分区的大小不一定相等。,例如:某存储系统共
3、256KB采用固定分区法，0-50K为OS使用。50K-80K为分区1，80K-130K为分区2，130K-190K为分区3，190K-256K为分区4。见图示,这样，内存就可以同时装入四个作业，分区1可装入小于30KB的作业，分区2可装入小于50KB的作业，分区3可装入小于60KB的作业，分区4可装入小于66KB的作业。,1.上下界寄存器的地址检查机构。当作业被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次内存访问时，地址检查机构作越界检查。,（2）地址访问保护技术的第一种方式,（1）上下界寄存器和地址检查机构。,例如：CPU访问上例中作业2的地址A，则检查过程如下：,静态重定位：
4、指用户代码中使用的相对地址,连接程序将其装配成绝对地址。（即：在装入一个作业时，把该作业中的程序和数据地址一次全部转换成绝对地址。）,（2）上下界寄存器和地址检查机构要求作业采用静态重定位技术。,例：程序A的逻辑地址空间如图，将其装入内存。内存起始地址为5000号单元。用静态重定位法画出其装入内存后的情况。MOV R1，（500）表示：将500号单元（地址）的数据12345送入1号寄存器。,静态重定位装入内存后的情况：,5100,5500,5700,5000,逻辑地址,2.基址寄存器、长度寄存器的动态地址转换机构。当作业被调度运行时，将作业所占内存基址及长度送基址、长度寄存器，每次内存访问时，
5、先看访问地址是否小于长度，然后+基址进行访存。见下图。,（2）地址访问保护技术的第二种方式,例：CPU要访问上例作业2的A地址时的检查过程,动态重定位：指用户代码中的相对地址先原封不动地装入内存指定地址，在执行期间才被动态地转换成绝对地址.,（2）基址寄存器、长度寄存器和动态地址转换机构要求作业采用动态重定位技术,又例动态重定位的实现过程。指令MOV R1,（3000）（即把相对地址为3000的单元中的123取到1号寄存器）,（3）多道固定划分法的作业调度技术,（4）固定分区法存在碎片问题 内部碎片：内存某存储区间大于其存放作 业空间的部分。如：作业只有3KB时，而某内存固定分区有4KB。有1
6、KB内部碎片。,外部碎片：内存某存储区间容不下要运行 的作业时。作业长度为：5KB，8KB，12KB时，若内存固定分区只剩下4KB，则存在外部碎片。,一、管理方法,5.2.3 多道连续可变划分法,特点：多道、连续、但不固定划分内存。,系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业到达后，作业有多大就分配多大的空间。作业撤离时，将释放的空间加入空闲队列。,例题1：有以下4个作业，采用多道连续分配技术,例题2：有以下5个作业，假设任一时间段内，内存中每一作业的运行时间相等，采用FCFS作业调度方法。,作业到来次序 所需存储量 运行时间,1 60KB 10s,2 100KB 5s
7、,3 30KB 20s,4 70KB 8s,5 50KB 15s,OS,0 40 256,J1,J2,J3,J4,J5,二、可变分区中的数据结构 常用的数据结构有两种：空闲分区表和空闲分区链。（1）空闲分区表。为内存中每个尚未分配出去的分区设置一个表项，每个表项包含分区序号、分区起始地址和分区的大小。根据右图的内存使用情况填写空闲分区表。,（2）空闲分区链。在每个空闲分区中设置用于控制分区分配的信息及用于链接各个分区的指针，将内存中的空闲分区链接成一个链表。不同的分配算法链表的组织方式不同。,三、可变分区分配算法,（一）首次适应（First Fit）算法。该算法要求空闲分区以地址递增的次序排序
8、。如果采用的是链表结构，分配时则从链表的开始顺序进行查找，直到找到一个能够满足进程大小要求的空闲分区为止。然后，按进程的大小，从分区中“切出”一块内存空间分配给请求者，余下的空闲分区仍然留在链表中。,例1：根据右图的内存使用情况画出首次适应算法的链表组织形式及分配一个10k的作业后的情况。,1解：（1）分配一个10k的作业前的链表组织形式。,（2）分配一个10k的作业后的链表组织形式。,表头指针,表头指针,三、可变分区分配算法,（二）下次适应（Next Fit）算法。该算法从首次适应算法演变而来。为了避免低地址部分小空闲分区的不断增加，在给进程分配内存空间时，不再每次从链首开始查找，而是从上次
9、找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，并从中“切出”一块与请求的大小相等的内存空间分配出去。,例2：根据右图的内存使用情况画出下次适应算法的链表组织形式及分配一个10k的作业后的情况。假设上次找到的空闲分区是空闲区1。,2解：,表头指针,表头指针,三、可变分区分配算法,（三）最佳适应（Best Fit）算法。最佳的含义是指每次为进程分配内存时，总是把与进程大小最匹配的空闲分区分配出去。该算法若采用的数据结构是空闲分区链，首先要求将空闲分区，按分区大小递增的顺序形成一空闲分区链。当进程要求分配内存时，第一次找到的满足要求的空闲区，必然是最优的。,例3：根据右图
10、的内存使用情况画出最佳适应算法的链表组织形式及分配一个10k的作业后的情况。,3解：,表头指针,表头指针,三、可变分区分配算法,（四）最坏适应（Worst Fit）算法。该算法与最佳适应算法相反，要求空闲分区按分区大小递减的顺序排序，每次分配时，从链首找到最大的空闲分区“切出”一块进行分配。该算法的特点是基本上不会留下小空闲分区，不易形成碎片。缺点是大的空闲分区被切割，当有较大的进程需要运行时，系统往往不能满足要求。,例4：,4解：,表头指针,表头指针,四、可变分区的作业分配过程在找到合适的空闲块后，从其中将作业大小的空间分给作业，而剩余部分挂入空闲队列。下面F 是空闲块集合;size（k）为块k 的大小;size（v）为用户所需空间。分配共需5步：,（1）如果所有属于F 的k，均有size（k）size（v）（3）F=F k;,（4）如果size（k）-size（v）基本单位，则将k分给用户。（5）否则将k分成k1,k2，其中 size（k1）=size（v），F=F+k2,2、空间回收过程：当作业结束时，收回作业所占空间，将此块链入空闲队列。若空闲队列中原来有与此块的相邻块，则把这些块合并成一个大连续块。,五、紧致技术通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。如下列：一个应用紧致（紧缩）技术的例子。,连续空间分配法小结：,
