计算机操作系统 李翠霞

第四章存储器管理,主讲：李翠霞办公室：水环楼306电话-mail:qyliying,2,Review,单一连续分配方式内存分为两个区域：系统区，用户区。用户区一次只能装入一道程序。固定分区分配方式将内存用户空间划分成若干个固定大小的区域，在每个分区中只装入一道作业，这样，用户空间分成了几个分区，便允许有几道作业并发运行。有大小相等和大小不等两种分区方式。可以使用分区说明表对存储空间进行管理动态分区分配方式,3,Review,动态分区分配方式根据进程的实际需要，动态地为之分配内存空间。数据结构空闲分区表：每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区大小等数据项。空闲区（块）链表：将所有的空闲区链成一个链表。,空闲分区表,空闲链结构,4,【动态分区分配算法分类】,顺序搜索法,分类搜索法快速适应算法,分区分配算法,首次适应算法,循环首次适应算法,最佳适应算法,最坏适应算法,分区分配操作,从头开始查表,检索完否?,m.sizeu.size,m.size-u.sizesize?,从该分区中划出u.size大小的分区,将该分区分配给请求者修改相关的数据结构,返回,返回,继续检索下一个表项,将该分区从链中移出,Y,N,Y,m.size表示空闲分区大小,u.size表示请求分区大小,size表示事先规定的不可再分割的剩余分区大小,图4-7内存分配流程,Y,N,N,6,回收内存,7,4.3连续分配方式,8,固定分区限制了活动进程的数目，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统是两者之间的折衷。,思想：无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，1km，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配分区的大小。,系统开始运行时，是一个大小为2m的空闲分区。在系统运行过程中，由于不断地划分，可能会形成若干个不连续的空闲分区。将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k（1km）个空闲分区链表。,9,2KB,4KB,32KB,分配时，如果需要16KB,32KB,16KB,回收时，过程相反,10,2KB,4KB,32KB,分配时，如果需要8KB,32KB,16KB,8KB,回收时，过程相反,11,分配时：当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1n2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的分区已经耗尽，则在分区大小为2i+1的分区链表中寻找。若存在2i+1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i+1的分区也不存在，则需要查找大小为2i+2的空闲分区。若找到则对其进行两次分割：第一次，将其分割为2i+1的两个分区，一个用于分配，一个加入到大小为2i+1的空闲链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲链表中。依此类推。,回收时：一次回收可能需要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i+1的分区，若事先已存在2i+1的空闲分区时，又应继续与其伙伴分区合并为大小为2i+2的空闲分区，依此类推。,12,在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。回收空闲分区时需要合并，时间性能比分类搜索算法差，但比顺序搜索算法好。空间性能优于分类搜索法，比顺序搜索法略差。,常用于多处理机系统。,13,哈希算法利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一表项记录了一个对应的空闲分区链表表头指针。分配时，根据所需空闲分区大小，通过哈希函数计算，即可得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。,01234567,哈希函数为：Hash(x)=xmod8,14,在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。？紧凑或拼接碎片整理,15,若想把作业装入，可采用：将内存中所有的作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。这种将多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改，则程序必将无法执行。为此，每次紧凑后，都必须对移动了的程序和数据进行重定位。,紧凑,紧凑前,紧凑后,紧凑前,紧凑后,动态重定位的实现,J6大小为10K,1、硬件支持：增加动态重定位寄存器RR（或基地址寄存器BA）,紧凑前：BA=64k,紧凑后：BA=28k,动态重定位示意图,LOADR1,2500,365,0,100,2500,5000,2500,10000,LOADR1,2500,365,10000,12500,15000,10100,相对地址,重定位寄存器,处理机一侧,存储器一侧,主存,+,请求分配u.Size分区,检索空闲分区链（表）,空闲分区总和u.size？,按动态分区方式进行分配,修改有关的数据结构,进行紧凑形成连续空闲区,修改有关的数据结构,无法分配返回,返回分区号及首址,找到大于u.size的可用区否？,否,否,是,P128图4-11动态分区分配算法流程图,20,2、软件处理：,需要时再移动,优缺点：解决碎片问题，以便运行大作业。紧凑系统开销大。,3、多重可重定位分区举例,DOS采用了四重可重定位分区,重定位寄存器：CS、DS、SS、ES,四重分区在内存中的位置可以不连续,每个分区（段），在内存中可以移动,回收一个分区马上移动,21,矛盾：一方面：在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面：却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。,解决的办法：引入Swapping(对换)技术。对换：把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。,22,23,对换单位：进程、页面、段进程（地址空间）整体的换进/换出进程地址空间分为页，暂不用的页面可以淘汰出内存，需要时由缺页中断处理程序调入内存。进程地址空间分为段，暂不用的段可以淘汰出内存，需要时由缺段中断处理程序调入内存。,24,【对换空间管理的目标和空间分配方法】追求对换的速度而非空间利用率，文件系统往往追求外存空间的利用率。采用以物理块为单位的连续分配策略（对换时磁头尽量少移动），数据结构和算法类似内存管理中的动态分区算法。二者差异：动态分区管理的是内存空间，对换技术管理的是外存的对换区。动态分区是以字节或内存块作为分配单位，对换技术是以对换区中物理块为单位。,2对换区空间的管理,采用动态分区算法,25,4.优点：增加并发运行的进程数5.问题：程序换入时要重定位，要有动态重定位硬件支持,3.进程的换出与换入（1）进程的换出每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。（2）进程的换入系统应定时地查看所有进程的状态，从中找出“就绪”状态但已被换出的进程，将其中换出时间最久（换出到磁盘上）的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,26,本章主要内容,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,27,4.4基本分页存储管理方式,产生的原因：连续分配方式会产生很多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。,如果允许一个进程直接分散地装入到许多不连续的分区中，则无须“紧凑”。如果离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式；如果没有页面对换功能，则称为基本的分页存储管理；如果有页面对换功能，则称为请求分页存储管理；,28,4.4基本分页存储管理方式,目的:避开连续分配,解决碎片问题(采用离散分配),将进程的逻辑地址空间划分为若干大小相等的页(page)，对各页加以编号，从0开始；物理内存划分为与页面相同大小的若干存储块，或称之页框（帧）(pageframe)，同样对它们编号，如0#块等；页的大小=块的大小；地址空间装入时，各页面可装入不连续的块中；需要CPU的硬件支持。,页表,用户程序含七个页面,30,4.4基本分页存储管理方式,页面大小如何设定？页面大小应适中。若太小：可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率；但另一方面每个进程会占用较多的页面，从而导致进程的页表过长，占用大量内存；降低页面换进换出的效率。若太大：可以减少页表的长度；提高页面换进换出的速度；页内碎片增大。页面大小应为2的幂次，通常为512B8KB。,31,4.4基本分页存储管理方式,页号P,位移量W,31,12,11,0,图中的地址长度为32位，其中011位为页内地址，即每页的大小为4KB（212）；1231位为页号，地址空间最多允许有1M（220）页。,地址结构,32,若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,D=AMODL,其中，INT是整除函数，MOD是取余函数。,例：某系统的页面大小为1KB，A=2170B，则可求出：,页号为2，位移量为122。,4.4基本分页存储管理方式,地址结构,33,4.4基本分页存储管理方式,页表,页表的定义：在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，但系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映像表，简称页表。页表的组成：进程地址空间中的所有页（0n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。页表的作用：进程执行时，通过查找该表，即可找到每页在内存中的物理块号。保护的实现：通过在页表的表项中增加一存取控制字段，即可实现对该页的存取控制。,页表,用户程序含七个页面,35,4.4.2地址变换机构,分页存储管理方式的地址变换：实质是将逻辑地址中的页号，转换为内存中的物理块号。可借助于页表实现。若页表驻留在内存中，则在系统中设置一个页表寄存器来存放页表在内存中的首地址和页表的长度。这时的地址变换称为基本的地址变换。若为了提高地址变换速度，引入了快表，则此时的地址变换称为具有快表的地址变换。,36,4.4.2地址变换机构,页表寄存器PTR（Page-TableRegister）：其中存放页表在内存的始址和页表长度。进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器。地址变换过程：分页地址变换机构将有效地址（相对地址）分为页号和页内地址两部分，以页号为索引去检索页表。将页号与页表长度相比，若页号页表长度，则越界中断，否则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，得到物理块号，将之装入物理地址寄存器。与此同时，将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。,37,4.4.2地址变换机构,1000H,如图例子中，页表的首地址为1000H，每一页表项占用1个字节，则3号页的页表项地址为多少？,3号页的页表项地址为页表首址+（页号*页表项长度）,3号页的页表项地址=1000+3*1=1003H,根据该地址可得3号页的物理块号为9。,若每页表项占用2个字节，则3号页的页表项地址为1000+3*2=1006H,OS,分页系统的地址变换机构,一.实现原理,1.地址空间分页,内存分块,页长=块长,(进程地址空间),2.通过页表把作业映射到内存,3.地址变换机构（P132图4-13）:,以执行loadR1,2500为例说明:指令要取的数在地址空间位于2页,页内偏移地址=452.指令要取的数在内存空间位于8644=10248+452,进程的执行过程如下:(1)页表长度，页表地址送页表控制寄存器后，开始执行(2)执行load指令,CPU把2500送VA,分离出P=2,W=452.(3)根据页表查得2页位于内存第8块.,(4)块号8、W(452)送入MA，拼接成物理地址：8644（5）8644送地址总线，完成取数操作。,页长=1k，划分位置左面为第10位，右面为第9位（右面占10个比特位）；页长=2k，右面占11个比特位；页长=4k，右面占12个比特位；,问题：如何把虚地址分离为（P，W）？,42,m-1,0,页号P,页内偏移量W,VA,划分位置取决页面大小。,