操作系统讲稿内存管理学习教案

1、会计学1操作系统操作系统(co zu x tn)讲稿内存管理讲稿内存管理第一页，共101页。第1页/共100页第二页，共101页。实用系统实用系统(xtng)中的存储管理方法中的存储管理方法第2页/共100页第三页，共101页。 主存储器被限制为主存储器被限制为1MB的内存空间。的内存空间。 低端的低端的640KB的基的基本内存。本内存。高端的扩展内存。高端的扩展内存。 系统启动后将操作系统系统启动后将操作系统调入基本内存调入基本内存(ni cn)的的低端位置，大概占几十低端位置，大概占几十KB的空间。的空间。 基 本 内 存 的 剩 余基 本 内 存 的 剩 余(shngy)部分便是用来部分

2、便是用来存放用户程序的用户区存放用户程序的用户区。在在DOS发展的后期，已发展的后期，已经可以利用扩展内存来经可以利用扩展内存来存放系统的数据结构、存放系统的数据结构、驱动程序以及某些库文驱动程序以及某些库文件等内容，但用户不能件等内容，但用户不能对扩展存储器中的内容对扩展存储器中的内容进行修改。进行修改。 程序和数据不能突程序和数据不能突破基本内存的限制，因破基本内存的限制，因此，用户程序的大小必此，用户程序的大小必须低于须低于640KB。 用户区内只能存放用户区内只能存放一个用户程序，因此，一个用户程序，因此，DOS系统只支持单道程系统只支持单道程序。序。 第3页/共100页第四页，共10

3、1页。Windows xp要求存储器最低为要求存储器最低为64MB。内存被划分为大小为内存被划分为大小为4KB的页面。内存中可以存放多个的页面。内存中可以存放多个(du )用户用户任务的页面，因此，任务的页面，因此，Windows支持多任务同时运行。支持多任务同时运行。用户在编制程序时，其大小最高可达用户在编制程序时，其大小最高可达4GB，但在程序运行时，并不是，但在程序运行时，并不是全部程序都装入内存，而是只装入程序的部分页面来运行。全部程序都装入内存，而是只装入程序的部分页面来运行。当需要装入新的程序页面而内存中又没有足够的空闲区域时，操作系当需要装入新的程序页面而内存中又没有足够的空闲区

4、域时，操作系统将内存中长期未使用的页面换出到辅助存储器上早已安排的页面（统将内存中长期未使用的页面换出到辅助存储器上早已安排的页面（paging file）文件中，腾出空间后再将需要换进的页面调入。）文件中，腾出空间后再将需要换进的页面调入。Windows 支持虚拟存储器。支持虚拟存储器。 第4页/共100页第五页，共101页。页页面面(y min)在在内内存存中中换换出出换换进进 Page Faults/sec 是每秒钟发生是每秒钟发生页面缺失的平均数量。页面缺页面缺失的平均数量。页面缺失将直接失将直接(zhji)导致页面换进导致页面换进。 Pages Input/sec 是从磁盘换是从磁盘

5、换进页面进页面(y min)的速度。的速度。当一个进程引用一个虚拟当一个进程引用一个虚拟内存的页面内存的页面(y min)，而，而此页面此页面(y min)不存在于不存在于内存，就会发生页面内存，就会发生页面(y min)缺失。缺失。 Pages Output/sec 是指为了是指为了释放物理内存空间而将页释放物理内存空间而将页面写入磁盘的速度。面写入磁盘的速度。当 物 理 内 存 不 足 时 ，当 物 理 内 存 不 足 时 ，Windows 会将页面写回到磁会将页面写回到磁盘以便释放空间。盘以便释放空间。 出页的峰值往往与进页出页的峰值往往与进页峰值接近。峰值接近。说明出页多是因为有进页需

6、说明出页多是因为有进页需求，即只有当内存中没有可求，即只有当内存中没有可分配空间，同时又必须调入分配空间，同时又必须调入内存新的页面时，才需要换内存新的页面时，才需要换出页面。出页面。 第5页/共100页第六页，共101页。可可用用物物理理(wl)内内存存Available MBytes 是计是计算机上运行的进程的可算机上运行的进程的可用物理内存大小。它是用物理内存大小。它是将零的、空闲的和备用将零的、空闲的和备用内存列表的空间添加内存列表的空间添加(tin ji)在一起来计算在一起来计算的。的。 第6页/共100页第七页，共101页。 Linux系统也是将存储器空间划分成页面系统也是将存储器

7、空间划分成页面(y min)，根据进，根据进程运行时的需要来对页面程运行时的需要来对页面(y min)进行换进、换出的。进行换进、换出的。 同样在磁盘上也安排了交换区来与内存协调工作，以达到扩同样在磁盘上也安排了交换区来与内存协调工作，以达到扩大内存的目的。大内存的目的。 但是但是Linux系统的交换区多采用在硬盘上划分出一个指定区系统的交换区多采用在硬盘上划分出一个指定区域来作为交换区，因此，交换区的大小不可变化。域来作为交换区，因此，交换区的大小不可变化。第7页/共100页第八页，共101页。第8页/共100页第九页，共101页。n任务在被激活之前存放在辅助存储器上。任务在被激活之前存放在

8、辅助存储器上。n当任务被激活时，它成为进程进入主存储器。当任务被激活时，它成为进程进入主存储器。n进程的描述部分及主程序部分始终存放于主存储器，其他进程的描述部分及主程序部分始终存放于主存储器，其他程序和数据部分视需要由操作系统在内存与外存之间交换。程序和数据部分视需要由操作系统在内存与外存之间交换。n当用户向计算机提交自己的任务时，存储管理是以一种逻当用户向计算机提交自己的任务时，存储管理是以一种逻辑形式来进行描述。辑形式来进行描述。n而当操作系统处理用户的任务时，是对具体的存储器地址而当操作系统处理用户的任务时，是对具体的存储器地址进行操作。进行操作。n存储管理的工作就是圆满地处理发生在衔

9、接逻辑和物理存存储管理的工作就是圆满地处理发生在衔接逻辑和物理存储时所产生的各种储时所产生的各种( zhn)问题。问题。第9页/共100页第十页，共101页。用户的每一条程序指令要访问的数据都用户的每一条程序指令要访问的数据都有一个对应的地址，这个地址被称为有一个对应的地址，这个地址被称为逻逻辑地址辑地址。由于它是相对于由于它是相对于0的地址，因此又被称的地址，因此又被称为为相对地址相对地址。当用户程序被编译为当用户程序被编译为目标代码目标代码时也使用时也使用的是相对地址。的是相对地址。原则上讲，因此用户可以无限制地加长原则上讲，因此用户可以无限制地加长自己的程序。自己的程序。在具体应用中在具

10、体应用中相对地址的大小受相对地相对地址的大小受相对地址寄存器位数的限制址寄存器位数的限制，如在，如在Windows 中中相对地址寄存器为相对地址寄存器为32位，表示相对地址位，表示相对地址最大可达最大可达4GB。逻辑地址空间可以逻辑地址空间可以定义定义为：实体（用户为：实体（用户、作业、任务、进程或程序）所用的所、作业、任务、进程或程序）所用的所有有逻辑地址的集合逻辑地址的集合。不同的操作系统赋予逻辑地址空间不同不同的操作系统赋予逻辑地址空间不同的表现形式，它的大小也是可以确定的的表现形式，它的大小也是可以确定的。用户可以直接对逻辑地址和逻辑地址空用户可以直接对逻辑地址和逻辑地址空间进行访问和

11、操作间进行访问和操作。逻辑地址空间又称为逻辑地址空间又称为相对地址空间相对地址空间，有，有时候也被简称为用户空间或者作业空间时候也被简称为用户空间或者作业空间。逻辑地址空间的大小被限制在。逻辑地址空间的大小被限制在0到相对到相对地址最大值之间。地址最大值之间。内存中的实际地址被称为物理地址。内存中的实际地址被称为物理地址。由于它并不和任何相对地址相关，因由于它并不和任何相对地址相关，因此，物理地址又称为绝对地址。此，物理地址又称为绝对地址。物理地址的最小值为物理地址的最小值为0，最大值取决，最大值取决于内存的大小和内存地址寄存器的所于内存的大小和内存地址寄存器的所能表现的最大值，二者中较小的那

12、一能表现的最大值，二者中较小的那一个值为物理地址的最大值。个值为物理地址的最大值。 物理地址空间可以定义为：当逻辑地物理地址空间可以定义为：当逻辑地址空间址空间被映射到内存被映射到内存时所对应的物理时所对应的物理地址的集合。地址的集合。物理地址空间又称为物理地址空间又称为绝对地址空间绝对地址空间。物理地址空间并不是指物理内存，只物理地址空间并不是指物理内存，只有当逻辑地址空间存在时，才会有物有当逻辑地址空间存在时，才会有物理地址空间。理地址空间。物理地址空间受存储器大小的限制，物理地址空间受存储器大小的限制，也就是说物理地址空间最大只能达到也就是说物理地址空间最大只能达到内存的大小。内存的大小

13、。第10页/共100页第十一页，共101页。装入后的作业并不能立即运行，因为作装入后的作业并不能立即运行，因为作业中每一个指令要访问业中每一个指令要访问(fngwn)的地的地址依然是相对地址，相对地址是逻辑地址依然是相对地址，相对地址是逻辑地址空间中的地址，并不是内存中的实际址空间中的地址，并不是内存中的实际地址，因此不能够访问地址，因此不能够访问(fngwn)。 装入是指将逻辑地址空间安装入是指将逻辑地址空间安排到内存中具体的物理位置上排到内存中具体的物理位置上。 装入针对的是整个逻辑地址空装入针对的是整个逻辑地址空间。间。1.装入装入2.地址映射地址映射对于指令要访问的地址进行相对对于指令

14、要访问的地址进行相对地址到绝对地址的变换，就是地地址到绝对地址的变换，就是地址映射。址映射。地址映射就是将逻辑地址空间中地址映射就是将逻辑地址空间中的地址映射到物理地址空间中去的地址映射到物理地址空间中去。采用的办法为重定位。采用的办法为重定位。 1.装入程装入程序序(chngx) 在装入过程完成后，根据装入的起始位置来修改在装入过程完成后，根据装入的起始位置来修改程序中指令要访问的地址，将相对地址改为绝对程序中指令要访问的地址，将相对地址改为绝对地址就是重定位。地址就是重定位。绝对地址绝对地址 （BR）相对地址）相对地址 根据不同的根据不同的地址修改时间地址修改时间可将可将重定位划分为重定位

15、划分为静态静态重定位和重定位和动态动态重定位。重定位。第11页/共100页第十二页，共101页。2.重定位重定位(dngwi)：静态重定位静态重定位(dngwi)动态重定位动态重定位(dngwi) mov AL, nn mov AL, nn+m 逻辑空间 0 内存 m nn L nn+m L+m 静态重定位是在装入过程完成后在静态重定位是在装入过程完成后在程序运行程序运行前前，一次一次将所有的指令要访问的地址全部修改将所有的指令要访问的地址全部修改为绝对地址，在程序运行过程中不再修改。为绝对地址，在程序运行过程中不再修改。静态重定位要求程序一旦装入其静态重定位要求程序一旦装入其绝对地址空间绝对

16、地址空间就就不能发生变化不能发生变化了。了。 mov AL, nn m nn+m nn + mov AL, nn m L+m 0 L nn 逻辑空间 L 基址寄存器 L 地址寄存器 内存 L 动态重定位是在程序的动态重定位是在程序的运行过程运行过程中，当指令需中，当指令需要执行时对将要访问的要执行时对将要访问的地址地址进行进行修改修改。 动态重定位动态重定位允许允许在在程序运行过程程序运行过程中，其中，其绝对地绝对地址址空间发生变化或被分割为不同的区域，空间发生变化或被分割为不同的区域，变化变化后后只需要将基地址寄存器中的内容作对应修改。只需要将基地址寄存器中的内容作对应修改。 采用静态重定位

17、采用静态重定位(dngwi)方式的主要优点是：方式的主要优点是：（1）可以在一般机器上全部用软件实现。）可以在一般机器上全部用软件实现。（2）装入程序可以实现静态连接。）装入程序可以实现静态连接。静态重定位静态重定位(dngwi)方式主要缺点是：方式主要缺点是：（1）执行期间程序不能在主存储器中移动，）执行期间程序不能在主存储器中移动，所以对提高主存储器的利用率不利。所以对提高主存储器的利用率不利。（2）若程序空间大于被分配的物理空间，由）若程序空间大于被分配的物理空间，由程序员自行采取某种手段来空间不足问题，如程序员自行采取某种手段来空间不足问题，如采用覆盖结构。采用覆盖结构。（3）用户不能

18、共享已经存放在主存中的同一）用户不能共享已经存放在主存中的同一个程序，如果几个用户要使用同一个程序，则个程序，如果几个用户要使用同一个程序，则每个用户必须在各自的主存空间中存放一个程每个用户必须在各自的主存空间中存放一个程序副本。序副本。 采用动态重定位方式的主要优点有：采用动态重定位方式的主要优点有：（1）在程序开始执行之前，不一定要把整）在程序开始执行之前，不一定要把整个个(zhngg)程序都调入到主存中。一个程序程序都调入到主存中。一个程序可以被分配在多个不连续的主存物理空间内可以被分配在多个不连续的主存物理空间内，以提高主存储器的利用率。，以提高主存储器的利用率。（2）几个程序可以共享

19、存放在主存中的同）几个程序可以共享存放在主存中的同一个程序段。一个程序段。（3）支持虚拟存储器。）支持虚拟存储器。动态重定位方式的主要缺点有：动态重定位方式的主要缺点有：（1）需要有硬件支持。）需要有硬件支持。（2）实现存储管理的软件算法比较复杂。）实现存储管理的软件算法比较复杂。第12页/共100页第十三页，共101页。1.存储存储(cn ch)分配分配 2.存储存储(cn ch)释放释放 3.分配原则分配原则 在设计分配程序时需要考虑诸多因素(yn s):(1)内存空间的划分(2)数据结构的确定 (3)作业空间的划分(4)淘汰算法 (5)分配算法 存储分配实际上是将作业存储分配实际上是将作

20、业的逻辑地址空间映射成为内的逻辑地址空间映射成为内存中的物理地址空间。存中的物理地址空间。 内存中有许多尚未使用的区内存中有许多尚未使用的区域即自由区都可以被分配，但域即自由区都可以被分配，但到底选择哪一自由区必须依据到底选择哪一自由区必须依据分配算法来确定。分配算法来确定。 存储释放实际上是解除存储释放实际上是解除逻辑地址空间与物理地址逻辑地址空间与物理地址空间的联系，并释放物理空间的联系，并释放物理空间。空间。 存储释放程序将回收的内存储释放程序将回收的内存区域重新设定为自由区，存区域重新设定为自由区，并将其安排进入自由区队列并将其安排进入自由区队列。进入自由区队列的具体位。进入自由区队列

21、的具体位置也必须依据分配算法。置也必须依据分配算法。 第13页/共100页第十四页，共101页。第14页/共100页第十五页，共101页。 当进程之间需要共享当进程之间需要共享某些数据时，使用界地址某些数据时，使用界地址寄存器就表现得无能为力寄存器就表现得无能为力。 第15页/共100页第十六页，共101页。当进程访问某个区域时，若进程的访问权限大于等于被访当进程访问某个区域时，若进程的访问权限大于等于被访问区域的权限值，访问可以进行问区域的权限值，访问可以进行(jnxng)，否则视为非法，否则视为非法。系统系统(xtng)为每一个存储区为每一个存储区域都给定一个访问权限值。域都给定一个访问权

22、限值。同时也为每一个同时也为每一个进程进程赋予一个赋予一个访问权限值访问权限值。 一个进程可以对不同存储区域有一个进程可以对不同存储区域有不同的访问权限；不同的访问权限； 一个存储区域也可以被多个具有一个存储区域也可以被多个具有不同访问权限的进程按权限级别进不同访问权限的进程按权限级别进行访问。行访问。 访问授权保护还有一个好处是它访问授权保护还有一个好处是它允许存储区域的共享。允许存储区域的共享。 第16页/共100页第十七页，共101页。(1)实际内存实际内存(ni cn)空间空间 (2)辅助存储器上的内存辅助存储器上的内存(ni cn)交换交换区区 (3)虚拟地址虚拟地址 (4)换进、换

23、出机制换进、换出机制 目目前的操前的操作系统作系统几乎全几乎全部具备部具备虚拟存虚拟存储器功储器功能，虽能，虽然不同然不同的系统的系统其实现其实现虚拟存虚拟存储器的储器的基本条基本条件都相件都相似，但似，但在数据在数据(shj)的换进的换进、换出、换出策略上策略上是可以是可以不同的不同的。 第17页/共100页第十八页，共101页。第18页/共100页第十九页，共101页。第19页/共100页第二十页，共101页。第20页/共100页第二十一页，共101页。的低地址部分的单一的连续(linx)的区域。第21页/共100页第二十二页，共101页。第22页/共100页第二十三页，共101页。 采用

24、采用(ciyng)(ciyng)静态重定位的方式在作业静态重定位的方式在作业装入时一次性对所有指令将要访问的地址进装入时一次性对所有指令将要访问的地址进行修改。行修改。 由于作业的物理地址空间不会发生变化，由于作业的物理地址空间不会发生变化，因此，单一连续分区不适合使用动态重定位因此，单一连续分区不适合使用动态重定位。 第23页/共100页第二十四页，共101页。 使 用 界 地 址 寄 存 器 保 护 法 。 其 中(qzhng)，基址寄存器的内容是操作系统常驻内存部分以后的首地址，长度寄存器的内容便是用户可用区域的长度。 由于操作系统不会发生变化，甚至可以不使用界地址寄存器，而将基址和长度

25、用两个常量来代替 。第24页/共100页第二十五页，共101页。（1）管理简单。管理简单。（2）使用安全。）使用安全。（3）不需要任何附加的硬件设备。）不需要任何附加的硬件设备。（1）作业的大小受用户区大小的限制。作业的大小受用户区大小的限制。（2）不支持多用户。）不支持多用户。（3）容易造成系统资源的浪费。）容易造成系统资源的浪费。第25页/共100页第二十六页，共101页。 将内存空间由小到大将内存空间由小到大划分为若干个位置固定大划分为若干个位置固定大小不等的区域，每个区域小不等的区域，每个区域可以存放一个作业，存放可以存放一个作业，存放于不同区域的作业可以并于不同区域的作业可以并行。行

26、。 用户逻辑用户逻辑(lu j)(lu j)地地址空间依然是一个连续的址空间依然是一个连续的整体，在作业申请进入内整体，在作业申请进入内存时一次性装入。存时一次性装入。 描述内存中每一个描述内存中每一个(y (y )区域的情况区域的情况描述存放于区域中的作业描述存放于区域中的作业 第26页/共100页第二十七页，共101页。地址映射地址映射 由于作业被分配进入内存后位置不再由于作业被分配进入内存后位置不再发生变化，因此，地址映射可以采用静发生变化，因此，地址映射可以采用静态重定位态重定位(dngwi)(dngwi)方法。不过我们要注方法。不过我们要注意到每一个作业的物理地址空间的起始意到每一个

27、作业的物理地址空间的起始位置是不相同的，因此，对每一个作业位置是不相同的，因此，对每一个作业进行重定位进行重定位(dngwi)(dngwi)时要修正基址寄存时要修正基址寄存器的值。器的值。存储保护存储保护 存储保护可以采取界地址寄存器的存储保护可以采取界地址寄存器的方法和访问授权保护，由于作业在内存方法和访问授权保护，由于作业在内存中的位置保持不变，可以用两个常量替中的位置保持不变，可以用两个常量替代界地址寄存。代界地址寄存。 第27页/共100页第二十八页，共101页。优缺点：优缺点：（1）提高了）提高了CPU的利用率。的利用率。（2）作业大小受到最大分区大小）作业大小受到最大分区大小的限制

28、。的限制。（3）空间浪费。）空间浪费。（4）碎片）碎片(su pin)问题。问题。第28页/共100页第二十九页，共101页。根据作业对内存空间根据作业对内存空间的申请来划分主存区的申请来划分主存区域，区域的大小域，区域的大小(dxio)(dxio)可变、位置可变、位置可变、数量也可变可变、数量也可变 描述已被分配描述已被分配(fnpi)(fnpi)的的区域区域 描述内存中的自由区域描述内存中的自由区域 为每一个为每一个自由分区自由分区设置一设置一个个链接链接指针来指向下一个自指针来指向下一个自由分区，使所有的自由分由分区，使所有的自由分区形成一个链表区形成一个链表 第29页/共100页第三十

29、页，共101页。多重分区分配多重分区分配(fnpi)(fnpi)与释放与释放 将作业将作业(zuy)(zuy)分配到内存中分配到内存中第一个碰到的大于或等于作第一个碰到的大于或等于作业业(zuy)(zuy)申请空间的未分配申请空间的未分配区。区。将作业申请大小与内存中所将作业申请大小与内存中所有未分配区的大小进行比较有未分配区的大小进行比较(bjio)(bjio)，直到找到最小的，直到找到最小的大于或等于作业空间的区分大于或等于作业空间的区分配给作业。配给作业。 将作业申请大小与内存中所有未将作业申请大小与内存中所有未分配区的大小进行比较，直到找分配区的大小进行比较，直到找到到最大的最大的大于

30、或等于作业空大于或等于作业空间的区分配给作业。间的区分配给作业。算法简单但分配比较盲目，算法简单但分配比较盲目，可能造成较小的作业分割了可能造成较小的作业分割了较大的空间，使大作业无法较大的空间，使大作业无法被分配。被分配。 优先使用小的自由空间，但优先使用小的自由空间，但每次分配以后的剩余空间可每次分配以后的剩余空间可能变得过小而成为碎片。能变得过小而成为碎片。 使用大的自由空间，在进行分使用大的自由空间，在进行分割后剩余空间还可以被使用，割后剩余空间还可以被使用，但也使大的自由空间无法保留但也使大的自由空间无法保留给需要大空间的作业。给需要大空间的作业。 另外可以有：另外可以有：最佳适应算

31、法也是最先适应最佳适应算法也是最先适应算法算法最坏适应算法也是最先适应最坏适应算法也是最先适应算法算法如何实现？如何实现？几种方法比较几种方法比较第30页/共100页第三十一页，共101页。4.4.地址映射地址映射 动态分区采用动态重定位方式来实现地址映射动态分区采用动态重定位方式来实现地址映射，这样作业的基地址发生变化也不会影响执行。，这样作业的基地址发生变化也不会影响执行。 当作业被选择运行时，其物理空间起始地址被当作业被选择运行时，其物理空间起始地址被装入基地址寄存器中，装入基地址寄存器中，CPUCPU每执行一条指令之前重每执行一条指令之前重定位硬件对指令要访问的地址进行修改。定位硬件对

32、指令要访问的地址进行修改。5.5.存储保护存储保护 存储保护可以采用界地址寄存器的方法和访问存储保护可以采用界地址寄存器的方法和访问授权保护，不过由于作业被分配于内存一个连续的授权保护，不过由于作业被分配于内存一个连续的区域中，访问授权保护的作用似乎区域中，访问授权保护的作用似乎(s h)(s h)并不大并不大，因为作业并没有对其他作业空间的访问权力。，因为作业并没有对其他作业空间的访问权力。第31页/共100页第三十二页，共101页。6.6.存储区整理存储区整理经过不断地分配和释放后，内存中自由分区会变得经过不断地分配和释放后，内存中自由分区会变得越来越多和越来越小，这就使很多小自由分区成为

33、越来越多和越来越小，这就使很多小自由分区成为碎片。碎片。可以用紧缩的方法来解决碎片。紧缩是将内存中已可以用紧缩的方法来解决碎片。紧缩是将内存中已使用区域经过移动使用区域经过移动(ydng)(ydng)沉淀到低地址部分，从沉淀到低地址部分，从而使碎片浮动到内存的高地址部分合并成较大的可而使碎片浮动到内存的高地址部分合并成较大的可使用空间。使用空间。用紧缩方法来消除碎片需要占用大量的用紧缩方法来消除碎片需要占用大量的CPUCPU时间，时间，并且在移动并且在移动(ydng)(ydng)过程中稍有不慎就有可能破坏过程中稍有不慎就有可能破坏全部数据。全部数据。第32页/共100页第三十三页，共101页。

34、7.7.多重动态分区的优缺点多重动态分区的优缺点（1 1）多道程度得以提高。）多道程度得以提高。（2 2）提高了内存的利用率。）提高了内存的利用率。（3 3）作业大小）作业大小(dxio)(dxio)依然受内存容量的限制。依然受内存容量的限制。（4 4）对碎片问题的解决需要以增加系统开销为代价）对碎片问题的解决需要以增加系统开销为代价。（5 5）不便共享。）不便共享。第33页/共100页第三十四页，共101页。举例：举例： 作业作业A要求要求18KB；作业；作业B要求要求25KB；作业；作业C要求要求30KB。用首次适。用首次适应算法、最佳适应算法来处理应算法、最佳适应算法来处理(chl)该作

35、业序列，看哪种算法合该作业序列，看哪种算法合适。适。 os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1第34页/共100页第三十五页，共101页。 (1) 首次适应算法中的自由首次适应算法中的自由(zyu)主存主存队列队列 (a) 首次适应算法中的自由主存队首次适应算法中的自由主存队列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-

36、 -1第35页/共100页第三十六页，共101页。 (2) 最佳适应算法最佳适应算法(sun f)中的自由中的自由主存队列主存队列 (b) 最佳适应算法中的自由主存队列最佳适应算法中的自由主存队列 160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1第36页/共100页第三十七页，共101页。(a) 首次适应算法中的自由主存队列首次适应算法中的自由主存队列 20KB 0 30KB 100KB 0 20KB 160KB

37、 0 5KB 210KB 0 46KB (b) 最佳适应算法中的自由主存队列最佳适应算法中的自由主存队列 160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 作业作业(zuy)A要求要求18KB作业作业(zuy)B要求要求25KB作业作业(zuy)C要求要求30KB第37页/共100页第三十八页，共101页。 分页存储管理方式分页存储管理方式(fngsh)(fngsh) 页式系统应解决的问题页式系统应解决的问题 分区存储管理的主要问题是碎片问题分区存储管理的主要问题是碎片问题。 在采用分区存储管理的系统中，在采用分区存储管理的系统中，会形成一些非

38、常小的分区，最终这些会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用非常小的分区不能被系统中的任何用户（程序）利用而浪费。户（程序）利用而浪费。 造成这样问题的主要原因造成这样问题的主要原因(yunyn)是用户程序装入内存时是整是用户程序装入内存时是整体装入的，为解决这个问题，提出了体装入的，为解决这个问题，提出了分页存储管理技术。分页存储管理技术。第38页/共100页第三十九页，共101页。第39页/共100页第四十页，共101页。 一、一、 页式系统页式系统(xtng)的基的基本概念本概念 （1） 页面页面 程序的地址空间被等分程序的地址空间被等分成大小相等的片，称为页成大

39、小相等的片，称为页面，又称为虚页。面，又称为虚页。 （2） 主存块主存块 主存被等分成大小相等主存被等分成大小相等的片，称为主存块，又称的片，称为主存块，又称为实页。为实页。第40页/共100页第四十一页，共101页。（3 3） 页表页表 为了实现从地址空间到物理主存为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对的映象，系统建立的记录页与内存块之间对应关系应关系(gun x)(gun x)的地址变换的机构称为页面的地址变换的机构称为页面映像表，简称页表。映像表，简称页表。 第41页/共100页第四十二页，共101页。01 KB01KB2 KB3KB 1主存主存作业作业2地址

40、地址(dzh)空间空间2 KB3 KB4KB5KB6KB7KB8KB9 KB10KB 101KB2KB 1作业作业1地址地址(dzh)空空间间01KB 1作业作业(zuy)3地址地址空间空间0516页号页号块号块号02140827作业作业1页表页表作业作业2页表页表作业作业3页表页表osos 分页映像存储的例分页映像存储的例 第42页/共100页第四十三页，共101页。 （4 4）虚地址结构）虚地址结构( (程序字程序字) ) 虚地址是用户程序中的逻辑地址，它包括虚地址是用户程序中的逻辑地址，它包括(boku)(boku)页号和页内地址（页内位移）。页号和页内地址（页内位移）。 区分页号和页内

41、地址的依椐是页的大小，页内区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。地址占虚地址的低位部分，页号占虚地址的高位部分。 假定页面大小假定页面大小10241024字节，虚地址共占用字节，虚地址共占用2 2个字个字节节(16(16位位) ) 页号页号 页内地址（位移量）页内地址（位移量） P W P W 15 10 9 15 10 9 0 0第43页/共100页第四十四页，共101页。（5） 页式地址变换页式地址变换页式地址变换举例页式地址变换举例 作业作业(zuy)2地址空间中，设地址空间中，设100号单元处有号单元处有如下指令：如下指令： mov r

42、1,2500。当这条指令执行。当这条指令执行时，如何进行正确的地址变换。时，如何进行正确的地址变换。mov r1 ,250012301KB1 KB3KB 1作业作业(zuy)2地址地址空间空间 2500 2 2* *1024 + 452 1024 + 452 p=2 w=452 p=2 w=452第44页/共100页第四十五页，共101页。l 页式地址变换过程页式地址变换过程(guchng) 000111 011100010015 10 9 0页号页号P页内位移页内位移(wiy)W页表始址寄存器页表始址寄存器mov r1 ,250012301KB2KB3KB 1作业作业(zuy)2地址地址空间

43、空间+021427页表页表 000010 011100010015 10 9 0页号页号P页内位移页内位移W250001KB主存主存2 KB3KB4KB5KB6KB7 KB8KB9KB10KB 1ososmov r1 , 2500123第第1页页7*1024+452=7620第45页/共100页第四十六页，共101页。l 页式地址变换的步骤页式地址变换的步骤l CPU给出操作数地址给出操作数地址(为为2500) ；l 由分页机构自动地把逻辑地址分为由分页机构自动地把逻辑地址分为(fn wi)两部分，得到页号两部分，得到页号p和页内相对位移和页内相对位移w (p =2， w =452)； l 根

44、据页表始址寄存器指示的页表始地址，以根据页表始址寄存器指示的页表始地址，以页号为索引，找到第页号为索引，找到第2页所对应的块号页所对应的块号(为为7) ；l 最后，将块号最后，将块号b和页内位移量和页内位移量w拼接在一起，拼接在一起，就形成了访问主存的物理地址就形成了访问主存的物理地址l (7*1024+452=7620)。第46页/共100页第四十七页，共101页。第47页/共100页第四十八页，共101页。第48页/共100页第四十九页，共101页。 例：有一系统例：有一系统(xtng)(xtng)采用页式存储管理，有一作业大小采用页式存储管理，有一作业大小是是8KB8KB，页大小为，页大

45、小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9 9、1010、5 5块，试块，试将虚地址将虚地址71457145，34123412转换成内存地址。转换成内存地址。虚地址虚地址(dzh) 3412(dzh) 3412P P3412 3412 2048 2048 1 1W W 3412 mod 2048 3412 mod 2048 1364 1364MR=9MR=9* *2048+1364=197962048+1364=19796虚地址虚地址(dzh)3412(dzh)3412的内存的内存地址地址(dzh)(dzh)是：是：1979619796第49页/共100页第五十页，共101

46、页。与静态分页管理不同与静态分页管理不同 ：按需分配按需分配(n x fn pi)。将需要运行的页面存放于。将需要运行的页面存放于内存，暂时不需要运行的页内存，暂时不需要运行的页面存放于辅存，当需要运行面存放于辅存，当需要运行存放于辅存上的页面时，再存放于辅存上的页面时，再将对应的页面调入内存。将对应的页面调入内存。 注意页表变化注意页表变化第50页/共100页第五十一页，共101页。第51页/共100页第五十二页，共101页。衡量淘汰算法衡量淘汰算法(sun f)依据依据：所有页面访问次数淘汰页面数淘汰率 所有页面访问次数缺页次数缺页率 好的淘汰算法好的淘汰算法(sun f)(sun f)应

47、该有较低的缺页率和淘汰应该有较低的缺页率和淘汰率。率。 第52页/共100页第五十三页，共101页。选择在最远的将来才被访问的页面淘汰。选择在最远的将来才被访问的页面淘汰。 谁是最远的、将来才被访问的页面？选择最早进入内存的页面淘汰 这种方法包含一个假定：这种方法包含一个假定：最早进入内存的页面就是目前最不会被使最早进入内存的页面就是目前最不会被使用的页面。用的页面。 假定不成立？假定不成立？系统抖动！系统抖动！第53页/共100页第五十四页，共101页。选择最近一段时间内最长时间未被使用选择最近一段时间内最长时间未被使用的页面淘汰的页面淘汰 该算法的该算法的假定假定：长时间未使用的页面不会马

48、上被使用：长时间未使用的页面不会马上被使用。这正好符合内存这正好符合内存局部性原理局部性原理（内存中某个位置现在被（内存中某个位置现在被访问，很快将再次被访问；某个位置现在被访问，其访问，很快将再次被访问；某个位置现在被访问，其邻近位置也将被访问。）邻近位置也将被访问。） 问题：问题：需要确定一个需要确定一个比较时间段比较时间段来反映哪一个页面长期未被来反映哪一个页面长期未被使用，时间段使用，时间段过长过长时该算法将变为时该算法将变为先进先出先进先出算法，时算法，时间段间段过短过短又会使系统频繁地记录访问次数并进行比较又会使系统频繁地记录访问次数并进行比较，从而增加系统，从而增加系统开销开销。

49、第54页/共100页第五十五页，共101页。选择页面选择指针遇到的选择页面选择指针遇到的最近未被访问最近未被访问(fngwn)(fngwn)的的页面淘汰。页面淘汰。简化的方法是：简化的方法是：页面选择指针下移，只要遇到刚才页面选择指针下移，只要遇到刚才(gngci)(gngci)未使用的页面就可以淘汰未使用的页面就可以淘汰。 第55页/共100页第五十六页，共101页。例例: : 某作业有某作业有a,b,c,da,b,c,d四个页面四个页面, ,作业在运行作业在运行(ynxng)(ynxng)过过程中的访问次序为程中的访问次序为:a,b,c,a,d,a,:a,b,c,a,d,a,试计算采用试计

50、算采用FIFOFIFO和和LRULRU淘淘汰算法汰算法, ,各会产生几次缺页中断各会产生几次缺页中断?(?(注：系统为该作业分配注：系统为该作业分配个内存块个内存块) ) 缺页中断次数淘汰的页面进入主存的页面1-a2-B3-C4ad5ba缺页中断次数淘汰的页面进入主存的页面1-a2-b3-c4bd LRU LRUFIFOFIFO第56页/共100页第五十七页，共101页。第57页/共100页第五十八页，共101页。第58页/共100页第五十九页，共101页。第59页/共100页第六十页，共101页。第60页/共100页第六十一页，共101页。第61页/共100页第六十二页，共101页。第62页

51、/共100页第六十三页，共101页。第63页/共100页第六十四页，共101页。作业地址空间按逻辑意义划分成段，每段作业地址空间按逻辑意义划分成段，每段都有其对应的段号和段长，对分段数量都有其对应的段号和段长，对分段数量(shling)和分段的长度没有限制。和分段的长度没有限制。 内存空间采用多重动态内存空间采用多重动态(dngti)(dngti)分区的形式，分分区的形式，分区的长度和位置没有限制。区的长度和位置没有限制。 段表将作业中的段对应于内段表将作业中的段对应于内存存(ni cn)(ni cn)中的分区。有缺中的分区。有缺段机制。段机制。第64页/共100页第六十五页，共101页。段号

52、段号S S 段内位移段内位移(wiy)d (wiy)d 每个段的段内位移每个段的段内位移(wiy)(wiy)的范的范围是不同的。围是不同的。 分页管理分页管理中，逻辑地址是中，逻辑地址是线性地址线性地址。分段管理分段管理中，段号中，段号S和段内位移和段内位移d不能形成一个不能形成一个线性地址，因为它实际上是代表着段长和段内位移线性地址，因为它实际上是代表着段长和段内位移两个变两个变量量。由于这两个变量没有特定的限制范围而无法用一由于这两个变量没有特定的限制范围而无法用一个变量来替代，因此分段管理的个变量来替代，因此分段管理的逻辑地址是二维地址逻辑地址是二维地址，分段，分段管理的逻辑地址空间是管

53、理的逻辑地址空间是二维空间二维空间。 第65页/共100页第六十六页，共101页。段表段表段表寄存器段表寄存器内存分块表内存分块表OrOr已使用分区表已使用分区表自由自由(zyu)(zyu)分区表分区表自由自由(zyu)(zyu)分区块链分区块链作业表作业表第66页/共100页第六十七页，共101页。段表中段号为段表中段号为S S的表目地址的表目地址(dzh)(dzh)（段表寄存器）表目长度段表寄存器）表目长度S S 段表起始段表起始(q sh)(q sh)地址（段表寄存器地址（段表寄存器） 对应对应(duyng)(duyng)的内存分区地的内存分区地址址S S 绝对地址绝对地址SSd d 第

54、67页/共100页第六十八页，共101页。第68页/共100页第六十九页，共101页。首先为作业分配段表空间；首先为作业分配段表空间；分配主程序段：分配主程序段：按一定的分配算法（内存空间采用动态分区形式，按一定的分配算法（内存空间采用动态分区形式，因此因此(ync)分配算法可采用最先适应算法、最佳适应算法或分配算法可采用最先适应算法、最佳适应算法或者最坏适应算法。）者最坏适应算法。）填写段表：填写段表：填入对应段表表目中该段的内存地址，其他暂时不填入对应段表表目中该段的内存地址，其他暂时不在内存的段，缺段状态置为在内存的段，缺段状态置为1，在需要运行时再调入。，在需要运行时再调入。第69页/

55、共100页第七十页，共101页。当作业空间逻辑分段后，当作业空间逻辑分段后，用户用户(yngh)(yngh)是靠调用来是靠调用来实现段与段之间的关系，实现段与段之间的关系，而存储管理将其实现称为而存储管理将其实现称为连接连接 第70页/共100页第七十一页，共101页。连接连接(linji)(linji)也可以分为静态连接也可以分为静态连接(linji)(linji)与动态连接与动态连接(linji)(linji)。静态连接静态连接(linji)(linji)发生在发生在作业刚装入内存还没有被执作业刚装入内存还没有被执行前，行前，一次完成所有连接一次完成所有连接(linji)(linji)。动

56、态连接动态连接发生在发生在执行过程中执行过程中，每当作业段与段之间产生调，每当作业段与段之间产生调用要求时才进行连接。用要求时才进行连接。问题问题：作业段必须一次全部调：作业段必须一次全部调入内存，限制了作业的大小，入内存，限制了作业的大小，对内存的容量要求高。对内存的容量要求高。作业中的各段没有必要一次作业中的各段没有必要一次全部调入，这极大的提高了全部调入，这极大的提高了内存的利用率。内存的利用率。分段管理采用的是动态连接方式。分段管理采用的是动态连接方式。第71页/共100页第七十二页，共101页。第72页/共100页第七十三页，共101页。第73页/共100页第七十四页，共101页。第74页/共100页第七十五页，共101页。有没有同时有没有同时利用利用分页管理和分段管理分页管理和分段管理的的优点优点，克服克服它们的它们的弱点弱点管理方法？管理方法？第75