《专升本操作系统第四章存储管理》由会员分享，可在线阅读，更多相关《专升本操作系统第四章存储管理（74页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章存存 储储 管管 理理操作系统 Operating System教学目的教学目的&存储器是作业驻留和活动的地方，和存储器是作业驻留和活动的地方，和cpucpu一样对系统性能影响很大的瓶颈资源一样对系统性能影响很大的瓶颈资源之一。如何让容量有限的内存被多任务之一。如何让容量有限的内存被多任务安全高效共享是现代操作系统内存管理安全高效共享是现代操作系统内存管理的核心任务的核心任务&因此，本章着重介绍多种存储管理的方因此，本章着重介绍多种存储管理的方式，如分区管理，分页管理等式，如分区管理，分页管理等教学难点教学难点&页式存储管理页式存储管理&段式存储管理段式存储管理存储管理4.1 存储
2、管理的概念4.2 分区管理4.3 分页管理4.4 分段管理4.5 段页式管理存储管理的基本概念存储管理的基本概念&物理内存：由系统实际提供的存储单元（通常为字节）所组成&物理内存是系统硬件（存储单元）支持的实实在在的内存，地址是一维的，存储容量受到实际存储单元的限制&虚拟内存只考虑互相关联的信息之间的相对位置，其容量只受到计算机的地址位数的限制，如处理器有32位地址，则它的虚拟地址空间为2（32），约4G虚拟地址到物理地址的映射虚拟地址到物理地址的映射&源程序经过编译链接后，形成一个以地址0位始地址的虚拟内存，每条指令或每个数据单元都在虚拟内存中拥有确定的地址，该地址称为虚拟地址。&当内存分配
3、区确定后，就要将虚拟地址变换为内存中的物理地址，该变换过程就称为地址映射或重定位静态映射静态映射&假设目标程序分配的内存起始地址为BA，每条指令或数据的虚拟地址为VA，则该指令或数据映射的内存地址就为MA=BA+VA&目标程序中的所有地址部分都以BA为基地址进行修改 动态映射动态映射&动态映射是在目标程序执行过程中，在CPU访问内存之前，由硬件地址映射机构来完成将要访问的指令或数据的虚拟地址映射为内存的物理地址&地址映射机构通常由一个或多个公用的基地址寄存器BR和一个或多个虚拟地址寄存器VR组成动态映射动态映射&BR存放当前程序分配的内存空间的起始地址，VR存放当前被映射的虚拟地址，映射得到的
4、物理地址MA=BR+VR&只要改变BR的内容，就可以改变程序的内存空间，实现程序在内存中的搬家，所以BR又称为重定位寄存器0 0 0 0100 100 + 1100+ 1100200 200 1200 1200 LOAD A 2003456VR 200BR 1000Load A 2003456存储管理&分区管理&分页管理&分段管理&段页式管理存储器的分区管理存储器的分区管理&基本思想基本思想：把内存划分为若干个大小不：把内存划分为若干个大小不等的区域，每个区域称为一个分区等的区域，每个区域称为一个分区&有可变分区和固定分区两种方案有可变分区和固定分区两种方案固定分区固定分区&固定分区固定分区就
5、是把内存划分为若干个大小就是把内存划分为若干个大小不等的分区，分区的大小和分区总数可不等的分区，分区的大小和分区总数可由操作员或操作系统在系统初启时建立由操作员或操作系统在系统初启时建立好，一旦建好，每个分区的大小和分区好，一旦建好，每个分区的大小和分区的总数都是固定不变的的总数都是固定不变的&固定分区管理通过数据结构固定分区管理通过数据结构分区说分区说明表来实现明表来实现固定分区示例固定分区示例区号区号分区大分区大小小起始地起始地址址使用状使用状态态0 032K32K0K0K1 11 18K8K32K32K1 12 216K16K40K40K0 03 332K 32K 56K56K1 14
6、464K64K88K88K0 0 OSOS作业作业A A（6K6K）作业作业B B（28K28K）1分区2分区3分区4分区032k40k56k 88k可变分区管理可变分区管理&与固定分区的与固定分区的3 3点不同：点不同： 1 1、可变分区的分区建立不是在系统、可变分区的分区建立不是在系统初启时，而是在系统运行中，在作业装初启时，而是在系统运行中，在作业装入时动态建立入时动态建立 2 2、分区的大小，不是事先设定的，、分区的大小，不是事先设定的，而是根据作业对内存的需求量而分配的而是根据作业对内存的需求量而分配的 3 3、分区的个数也是变换不定的、分区的个数也是变换不定的OS224kOSA（9
7、0k） 134KOs（90k）B 50k84kOSA（90KB（50K84k032256A 90kB 50kC 100k可变分区的数据结构可变分区的数据结构&位图位图&链表链表1110001111100011111110001111100011111000111110000000000000000000OSOS作业作业A A空空作业作业B B作业作业C C空空作业作业D D空空可变分区的管理分配策略可变分区的管理分配策略&最先适应法最先适应法FFFF&最佳适应法最佳适应法BFBF&最坏适应法最坏适应法WFWF三种策略比较三种策略比较&WF最快能找到要分配的空闲区，它总是查找空闲链表的第一个空闲
8、区，若能满足则分配&在内存分配上，FF最快，因为BF和WF均要把分配剩余的空闲区按其大小插入到空闲表的合适位置，而FF不改变分配剩余部分在空闲链表的位置&在内存回收上，FF最佳。FF很容易实现邻接空闲区的合并，并且不需要改变合并后的空闲区在空闲链表中的位置&FF尽可能的分配低地址空间，保留高地址的空闲区，用于大作业分配三种策略比较三种策略比较F1（100kF2 （50kA 30kB 70kC 50kA（30K ）B（70k）C（50K）B 70k30kA 30k20k分配前 WF BF FF存储管理&分区管理&分页管理&分段管理&段页式管理分页与分区的比较分区的缺点 1、当不存在能满足作业需求
9、量的连续区时，即使空闲空间总量大于作业需求量，也不能分配 2、导致了内存碎片问题，使得内存利用率不高 3、合并内存碎片也要耗费大量的CPU时间 4、各个作业对用于不同的分区，不利用程序段的共享&分页管理取消了存储分配连续性要求，使得一个作业的地址空间在内存中是若干个不一定连续的区域 静态分页存储管理&先来看一个饭店安排客房的例子 假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现又有一个旅游团要求入住。接待员统计了一下，说：“贵团全体都能住下，但是不能住同一楼层，更没有几个挨着的。”&对于饭店这样的安排，客人不会感到奇怪，因为旅游团的大多数团员都是两人一组；而饭店每天都有入
10、住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。分页的基本原理内存分配与饭店安排房间有所类似。&把作业的虚拟空间划分为若干个大小相等的块，成为页（Page），对所有的页从0依次编号，于是作业的虚拟地址可以用页号P和页内地址d来表示。&于此对应，内存空间也划分为与页大小相等的若干块，成为页帧（Page frame），系统以页为单位给作业分配帧，帧之间可以是不连续的，这样可以减少内存碎片，最多存在小于帧大小的内碎片，不会产生外碎片分页的基本原理&一个作业只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。同时为这个作业建立一个页号与块号的对照表，称为页表。这好像饭店的客户登记表
11、一样&每个块的大小是固定的，一般是0.5KB4KB之间的数值，而且必须是2的幂次分页的基本原理&一个作业只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。同时为这个作业建立一个页号与块号的对照表，称为页表。这好像饭店的客户登记表一样&每个块的大小是固定的，一般是0.5KB4KB之间的数值，而且必须是2的幂次思考：为什么大小要在这个范围内？分页存储管理示例地址转换&页式存储管理对作业的地址转换采用动态重定位技术。&设每页大小为aKB 物理地址=物理块首址+块内地址 =物理块号*a+页内地址 逻辑地址=逻辑页首址+页内地址 =逻辑页号*a+页内地址&从上述过程中可以看出，分页管理每取一
12、个数据时，都要访问两次内存，一次是访问内存中的页表，得到数据的物理地址，另一次是根据得到的物理地址，从内存中取得数据&为了提高地址变换的速度，在地址变换机构中，增加一个高速可并行查找的联想存储器，构成一张快表分页系统地址转换过程1.由指令产生逻辑地址2.若逻辑页号不小于页表长度寄存器的值，则产生越界中断，否则，转（3）3.由逻辑页号查快表，若成功，则读出物理块号，转（5） ，否则，转（4）4.由逻辑页号查页表，从相应页表目取出该页相应的物理块号，把逻辑页号与物理块号至于快表表目中，若此时快表已满，则先按淘汰算法淘汰一个快表表目5.把物理块号与页内地址写入物理地址寄存器的相应位置得物理地址地址变
13、换示例作业号作业号页表起页表起始始申请帧申请帧数数分配状分配状态态A A14000140005 5已分已分1、系统从作业申请表中，取出作业A的页表起址14000放入页表起址寄存器PAR中，把申请帧数放入PLR2、由PAR得到A的页表地址为140003、将虚地址5000转换为页号P和页内地址D，即P=4，d=9044、将页号与PLR比较，进行地址越界检查5、若为有效地址，则从相应的页号4中，取出帧号216、由块号*块长度+块内地址，即21*1024+904=22408，即为虚地址5000对应的物理地址设页的长度为1kb，作业A中有一条load 1，5000取数指令页的分配与回收&最简单的管理内存
14、的方法是：位示图&位示图中的每一位与一个主存块对应，其值为0时，表示对应的主存块空闲；其值为1时，表示对应的主存块已分配&位示图的优点是占用主存空间少，可常驻内存，加快分配进程；&不足之处：不太直观，要进行图中每个位元素的下标值到其所对应的主存块的块号的转换示例&设主存储器的可分配区域被分为256块，则只需要33B的位示图来作为主存分配表。其中8个字长32位的字可以描述全部256个块的分配使用情况，另有一个字节记录剩余的空闲块数。页的分配与回收&还有可以采用顺序分配算法 先查看空闲块数是否能满足作业要求。若不能满足，则不进行分配，作业不能装入主存：若能满足，则根据需求从位示图中找出一些为0的位
15、，把这些位置成1，从空闲块中减去本次占用的块数，按公式“块号=字号*字长+位号”计算出这些位所对应的主存块号，把作业装入到这些块，并为作业建一张页表动态分配存储管理&静态分页管理要求每个作业在分配到所申请的全部帧后才能装入运行。&静态缺点：当前可用帧数小于作业的需求量时，作业不能运行；作业的大小也受到了帧总数的限制&而动态分页的思想是：每次只装入一部分，其他部分在执行过程中动态装入动态分页管理的任务&调入策略：当作业需要的信息不在内存中时，系统才把所需的页调入内存&替换策略：解决当前内存中没有空闲帧时，如何淘汰内存中已占据的帧&地址变换：完成将虚地址变换为对应的物理地址主存页面分配策略&平均分
16、配：将内存中所以物理块等分给进入系统中的进程的做法，简单易行，但会导致“内碎片”增加和缺页率提高&按进程长度比例分配 设Si 为进程Pi逻辑空间页面数，定义S=Si；m为内存空间物理块总数，则分配给进程Pi的内存物理块数Ai为： Ai=Si/S*m&按进程优先级分配&按长度和优先级分配页面调度算法&调度算法的好坏，直接影响系统的效率&抖动：刚被调出的帧马上要访问，调入内存后不久又要被调出，如此反复的调入调出页面调度算法&最佳淘汰算法OPT淘汰算法 Belady于1966提出的一种理论上的算法。每次都淘汰以后永不使用的，或者最长时间后才会被访问的页面 虽然可以保证最低的缺页率，但无法实现，因为它
17、必须知道页面“将来”的访问情况页面调度算法&先进先出淘汰算法FIFO 总是淘汰最先进入内存的页面。 实现简单，只需把进程已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存最老的页面 效率不高，而且会造成Belady现象Belady现象&一般而言，内存帧数越多，一个作业发生缺页的次数越少&但Belady提出反例 一个作业有5个页，编号从0到4，页的引用顺序为012301401234，采用FIFO替换算法，当存储帧数为3的，缺页次数为9，内存帧数为4的缺页反而为10页面调度算法&最近最久未用淘汰算法LRU 总是淘汰内存中最长时间没有被访问的帧，即淘汰最后一次访问时
18、间距当前时间间隔最长的页面 LRU的开销很大，必须要有硬件的支持，完全由软件实现其速度至少会减少10倍，所以用LRU的近似算法更实用页面调度算法&二次机会淘汰算法SC 通过对FIFO进行简单的改造，结合页表中的访问位而得来一种淘汰算法。 该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链链尾。如此重复。页面调度算法&时钟淘汰算法&最近未用淘汰算法例题&已知某作业执行时页面访问次序为：70120304230321201701，该作业得到3个空闲内存块，开始时，前三页已装入内存。要求： （1）试计算采用FIFO淘汰算法和
19、LRU算法进行页面调度时产生的缺页中断次数 （2）求出各自的缺页中断率例题例题解：（解：（1）FIFO7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 777001例题例题解：（解：（1）FIFO7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 777222244400000007770000333222221111100111100033333222221例题例题解：（解：（1）FIFO7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 p p p p p p p p p p p p 一共产生一共产生12
20、次缺页次缺页777222244400000007770000333222221111100111100033333222221例题例题&LRU7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 111007例题例题&LRU7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 111203 0423032120170100120 304230321201707012 23042203312017例题例题&LRU7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 p p p p p p p p p 一共产生一共产生9
21、次缺页次缺页111203 0423032120170100120 304230321201707012 23042203312017例题&（2） FIFO缺页率为：12/20*100%=60% LRU缺页率为：9/20*100%=45%存储管理&分区管理&分页管理&分段管理&段页式管理分段式存储管理基本思想&分页和分区存储管理对用户提供的是一个线性的地址空间，即作业的地址都是从0开始顺序编址&但是，一个作业的地址空间都有一定的逻辑关系，例如可以划分为主程序、子程序和各种数据结构（数组、栈、文件等），因此，如果按照各个逻辑结构来申请作业的地址空间并进行管理，将非常有利于程序设计。&基本思想：将作
22、业按逻辑上有完整意义的段划分，每段都有自己的名字，以段为单位分配内存并进行内外存交换段式管理的基本原理&将程序的地址空间划分为若干个段(segment)，这样就使得每个进程都有一个二维的地址空间（段号+段内相对地址）&为每个段分配一个连续的分区，而进程中的各个段可以不连续的存放在内存的不同分区中。&程序加载时，操作系统为所有段分配其所需的内存，各段之间不必连续，物理内存的管理采用动态分区的管理方法。段式物理地址分配回收&分配：在为某个段分配物理内存时，可以采用最先适应法、最坏适应法和最佳适应法等&回收：回收某个段占用的空间时，要注意将回收的空间与其相邻的空间合并段式管理的数据结构&为了实现段式
23、管理，操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射，并跟踪物理内存的使用情况，以便在装入新的段的时候，合理的分配内存空间数据结构&进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段都有段基址（base address）&系统段表：系统所占用段&空闲段表：内存中所有空闲段，可以结合到系统段表中&系统段表和空闲段表通常是结合为一张表存储管理过程&分段式存储管理中以段为单位进行内存分配，每段分配一个连续的内存区，各段之间的内存区不一定连续，且各个内存区也不等长。&内存的分配和释放是需要动态进行的。当要求调入某段时，若内存中有的足够空闲区满足该段的长度，则
24、可以采用与分区式管理相同的几种分配和释放算结；&若内存中没有足够的空间，那采用几种的替换算法，多次替换直到换到能满足调入段的长度为止段表段号装入标志位段长内存始址0Y（表示某段已调入内存）2k2k1Y3k8k2N1k系统为每个运行的作业建立一个段表 段式管理的地址变换&在段式管理系统中，整个的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成&为了完成进程逻辑地址到物理地址的映射，处理器会查找内存中的段表，由段号得到段的首地址，加上段内地址，就得到实际的物理地址&这个过程也是由处理器的硬件直接完成的，操作系统只需在进程切换时，将进程段表的首地址装入处理器特定寄存器中。这个寄存器一般被称为
25、段表地址寄存器段式地址切换 段表地址寄存器 内存 段表 34c4 虚拟地址 段号 段内地址段表起始地址11c4段号 始地址0150013400&与页式系统类似，段表放在内存中，每访问一次数据都要两次访问内存，从而降低了计算机的速度。解决这个问题的方法也是在处理器增加一个高速关联处理器，用于保存经常使用的段表项&由于一般段表项的数目比页表项的数目少的多，其所需的关联存储器也相对小的多，因此可以显著减少存储数据的时间页式和段式的区别&相似之处：两者都采用离散分配方式，且都通过地址映射机构来实现地址变换&不同之处： 1、页是信息的物理单位，分页也是为了实现离散分配方式，以减少内存的碎片，提高内存的利
26、用率。可以这么说分页是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组相对完整的信息。分段的目的是为了更好的满足用户的需要页式和段式的区别 2、页的大小是固定的，且由系统决定。而段的长度是不固定的，且决定于用户所编写的程序，通常由编译系统在对源程序进行编译时根据信息的性质来划分 3、页的地址空间是一维的，即单一的线性地址空间，程序员只需要利用一个标识符，即可以表示一个地址。分段的地址是二维，程序员在标示一个地址时，即需要给出段名还有段内地址分段式管理的优点&没有内碎片，外碎片可以通过内存紧缩来消除；&便于实现内存共享和保护（可以分别编写和编译源程序的一个文件，并且可以针对不
27、同类型的段采用不同的保护，也可以按段位单位来进行共享）；&便于实现动态链接缺点&提高了硬件的成本&段的长度受到了内存可用大小的限制，因为段是管理也是一次性将进程装入内存&增加了系统的复杂性&有可以产生抖动现象。与动态分页式管理一样，若替换算法不恰当，则可能产生抖动现象存储管理&分区管理&分页管理&分段管理&段页式管理段页式的基本思想&由于分段式着眼于方便用户，为用户提供二维的虚拟地址空间，&分页式以提高内存利用率为动力，有效的克服了碎片，&因此，若将分段与分页结合起来，进行优势互补，这就是段页式存储管理段页式存储管理的地址空间&作用的地址空间也是二维的，是按段划分的。但是每个段再划分为若干个大
28、小相同的页，其地址结构由段号、段内页号和页内地址组成&程序员可见和使用的仍然是段号和段内相对地址，但是地址变换机构将会自动将段内相对地址的高几位解释为段内页号，将剩余的低位解释为页内相对地址&由于作用的地址空间最小单位不是段而是页，从而内存也可以按也划分，并按页为单位装入。这样一个段可以装入到若干个不连续的页内，段的大小也可以不受内存可用去的限制了 动态地址变换&系统为每个作业建立一张段表，每个段建立一张页表，段表中的地址是页表的起始地址，页表中的地址为页面号 内存空间 段表 寄存器 0段页表（上）1号段表（下） 段表始址段号页表长度页表始址0212页号 其他 页面01页号 其他页面01地址变换&寄存器 段表 段号 1号页表 页号 页内相对地址段表始址段号 页表长度页表始址0122spd页号其他页面01作业作业1. 1. 名词解释名词解释 静态重定位、覆盖技术静态重定位、覆盖技术2. 2. 简答简答（1 1）在可变分区管理下，采用移动技术有）在可变分区管理下，采用移动技术有什么优点？什么优点？ （2 2）分段式存储管理的优缺点是什么？）分段式存储管理的优缺点是什么？3. 3. 应用题应用题 课本课本P91P91页页 1 1，2 2，3 3
