操作系统设计与实现(第四章)

操作系统设计与实现主讲教师：徐战亚Email：[e-mail]第四章存储器管理一、存储器在操作系统中的地位是计算机不可缺少的部分，存在的方式也多种多样。对于操作者、程序设计者、系统开发者都希望能拥有无穷大的、高速的、内容不发生变化的存储器，最根本的还是能以很低的成本来使用。由于技术的原因，我们无法满足我们的需求，因此，大部分的计算机都以一种层次结构来进行存储器的管理。高速、价格昂贵、易失信息的Cache一般单位几百KB；中速、中等价格、易变化的RAM，一般单位为几百M；低速、低廉价格、不易丢失信息的磁盘，一般单位为G；存储器层次结构对于操作系统，它本身提供一个存储管理模块来管理它本身的这个层次性的存储器系统。Memorymanager由操作系统协调这些存储器的使用重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。内存：是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。可以分为：系统区：用于存放操作系统用户区：用于装入并存放用户程序和数据。操作系统存储管理目的----用户对内存的使用要求1、充分利用内存，为多道程序并发执行提供存储基础；2、尽可能方便用户使用：自动装入用户程序；用户程序中不必考虑硬件细节；3、系统能够解决程序空间比实际内存空间大的问题；4、程序在执行时可以动态伸缩；5、内存存取速度快；6、存储保护与安全；7、共享与通信；8、了解有关资源的使用状况；9、实现的性能和代价。操作系统存储管理的任务前提:引入多道程序设计技术，满足用户要求1.内存空间的管理、分配与回收记录内存的使用情况——设置相应的内存分配表（见下页）（内存分配回收的依据）内存空间划分问题？静态或动态，等长或不等长内存分配表位示图表示法：用一位（bit）表示一个空闲页面（0：空闲，1：占用）；0…...110…...第0页第1页第i页第n-1页空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用；空闲块链表：将所有的空闲块链成一个链表。确定分配算法实施内存分配回收内存分配回收方式:静态分配与动态分配连续性；离散性驻留性；交换性一次性；多次性2.存储共享内存共享：两个或多个进程共用内存中相同区域目的：节省内存空间，提高内存利用率实现进程通信（数据共享）共享内容：代码共享，要求代码为纯代码数据共享3.存储保护与安全保护目的：为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时,不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）存储保护保护系统程序区不被用户侵犯;（有意或无意的）不允许用户程序读写不属于自己地址空间的数据;（系统区地址空间，其他用户程序的地址空间）保护过程----防止地址越界每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。一般由硬件提供一对寄存器：基址寄存器：存放起始地址限长寄存器：存放长度（上界寄存器/下界寄存器）保护过程----防止操作越权对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。即读写保护。4.内存“扩充”通过虚拟存储技术实现用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来扩充内存的容量，使用户得到比实际内存容量大的多的内存空间。内存“扩充”具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。5.地址映射（地址重定位，地址变换）(1)逻辑地址（相对地址，虚地址）(2)物理地址（绝对地址，实地址）(3)地址映射(1)逻辑地址（相对地址，虚地址）用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息。(2)物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址。(3)地址映射为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。地址映射BA=1000LoadA2003456。。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间0100200300.........LOADA2003456逻辑地址空间110012001300物理地址空间200VR+1000BR***重定位和保护多道程序导致了分区的产生，而分区也导致了新的问题，即程序的重新定位和保护。如果多个作业都是为某一个程序服务，当主程序调用这些作业的时候，就需要定位到这些作业，保证程序的运行（主函数和分别编译好的子函数）。这时，链接的时候，链接器按照我们的分区机制来定位程序。定位和保护的常见方法：原因:当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。静态重定位当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。动态重定位在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。硬件上需要一对寄存器的支持。4.1基本的内存管理在运行时进程可以在内存和磁盘之间进行移动（交换和分页技术）的系统；运行时进程不能够移动的系统，较为简单。交换和分页技术的目的是由于没有足够的主存来同时容纳所有的进程而被引入。随着硬件的发展，现有的良好的管理方案也会可能变成过时的技术而被淘汰。4.1.1无交换和分页的单道程序此方案是指同一个时刻和操作系统共享存储器。用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统0ABC对于A图，操作系统位于主存最底部的RAM，即随机存取存储器中，用户程序位于主存的上部。对于B图，操作系统位于主存最高端的只读存储器里（ROM）,（其实本身属于一种映像区域，映像了主板上的基本的输入输出系统）。对于C图，设备的驱动程序位于内存最高端的ROM中，操作系统的其余部分位于低端的RAM中，中间是用户的应用程序。如MS-DOS系统。对于IBM操作系统，系统位于ROM中的部分即为BIOS。对于这种方式，不管是哪一个图，操作系统每次把需要的程序从磁盘复制到存储器里并执行，当程序结束时，系统提示结束，当有新的命令时，系统加载新的程序到存储器中，覆盖原来的程序，继续新的执行。可以满足早期一般的小型的操作系统的需求，但随着硬件性能的提高，这种方式逐渐被淘汰。4.1.2固定分区的多道程序对于常见的系统，我们希望能够支持更多的程序，当某个程序处于等待I/O的时候，可以让CPU为别的程序服务，来提高系统整体的性能。因此可以用划分分区的方法来同时加载多个程序，可以把主存分为几个大小不同的分区，根据程序的不同，来把他们加载到不同的分区中。而同时，程序也可按照单个输入队列的方式进行输入，也可以按照多个输入队列的方式进行输入。分区4分区3分区2分区1操作系统多个输入队列单个输入队列分区4分区3分区2分区1操作系统700K400K100K0对于左图，由于作业的大小类似的时候，而且众多的作业大小都类似，而此时分区的大小固定，我们该选择合适大小的分区来运行这个作业，这样的话，类似的作业就被分到了一起，而那些与作业的大小不一致的分区，就必然会出现空闲状态，那些分到一起的进程却不得不等待，等待要分到内存空间。忙得忙，闲的闲。如分区一和分区三。对于右图，所有的作业都被放入一个队列，每次当有分区被释放的时候，就从等待队列中寻找，最适合这个分区大小的进程，这样做是为了避免把大的分区分给那小的作业，免得资源被浪费，但这样却常常把小的作业推到了后面；但对于操作系统，我们做普通的要求就是简单的操作能被最快的反馈给我们，即小的作业能够被最快的处理，因此，为了总能够满足用户的这个要求，一般要专门保证总有一个小的分区，专门来处理那些小的事件、作业，免得被大的作业抢去分区。或者通过加权来判断作业被推后的次数，到了一定的程度，就不再跳过而是立即执行。4.2交换固定分区的方案在批处理系统中是种简单高效的方案，每一个作业都在队列中一直到被分配到某个分区，然后被执行完毕。只要能够放入内存，能够使CPU繁忙，就能满足要求。但在分时系统中，或者个人的PC中，这种方案就不太实际，会常常由于主存不够，需要把进程保存到磁盘，同样的，也需要常常动态地把进程从磁盘调入内存。这时就需要有新的技术，即交换技术(swapping)和虚拟内存技术的引入。OSOSOSOSOSOSAAABBBBCCCCDDabcdefOSCDE进程依次进入，并获得到自己所需要的内存空间，当某个进程执行完毕后便离开，它原来的占用的内存资源便得到释放，当新的进程到来的时候，又可以从这个被释放的空间中划分新的空间，因此主存的利用变得很高效。（理想上的）g上图中的内存分配与固定分区的不同，它是一种可变分区的内存分配，这时内存中的分区的数目和大小都是在随时随着进程的变化而变化的。实际上，内存空间在不断划分的时候，本身的分布也在变化的越来越复杂，越来越不便于管理。迫切需要一个机制去整理这个零碎的空间。即空闲区域的合并---内存紧缩。(低效的操作，耗时)****新的问题如果根据进程需要给它分配内存，而且，进程运行的时候大小不再变化，那么分配就简单，根据需要的大小分配即可；如果进程运行时，该进程的数据段增长，就需要分配新的内存，那进程所需的空间就开始变大，上图中，如果相邻区域是空洞，则直接分配给它，但如果是进程时？交换，将某一进程移出，但此时内存满了，磁盘交换分区也满了，某进程则必须等待或杀死。****新问题的解决带来的矛盾：多数的进程都需要动态的空间，且申请新的内存空间，频繁的交换导致大量的进程等待和时间开销。****矛盾的解决在每个进程申请空间的时候分配一些多余的内存空间；（A）或者对于具有两个可增长数据部分的进程，采用在进程的分区内分开放置的方式管理。（B）OSABA为增长内存准备的内存实际使用的内存为增长内存准备的内存实际使用的内存OSA---PROGA---DATAA---STACKB---DATAB---STACKB---PROGB为增长内存准备的内存为增长内存准备的内存4.2.1使用位图的内存管理由于操作系统需要对内存进行分配管理和回收，所以，它必须很好地对内存进行跟踪，常用的是位图法和自由链表：ABCDE(a)对于位图方法，位图的大小与内存的大小和分配的单位的大小相关，内存不变时，被分配的单个单元越小，则位图就越大。位图的组织结构简单，便于管理，且占用的内存很小但也有缺陷：定位的速度受限，由于每个位图单元代表一个被分配的单元，所以连续性不强，对于某个需要几个分配单元大小的进程就很难快速在位图中找到这样连续的空间。故实际不很常用。4.2.2使用链表的内存管理这种方法是通过一个链表来管理已经分配的和尚未分配的内存段，通过对链表的维护达到对内存的管理。这里的内存段可以使被某个进程所占用，也可以是个空洞，即尚未分配的区域。表的内容包括段的性质、开始地址、长度、长度和指向下一个表项的指针。这是一般，链表的组织都按照地址来排列，这样的进程切换会很直观，更有效的方法是采用