（2）保护键法：为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段。
（3）界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。 6.分区存储管理
分区管理：把内存划分成若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。
分区管理基本原理：给每一个内存中的进程划分一块适当大小的存储区，以连续存储各进程的数据和程序，使各进程得以并发执行。 按分区的时机，分区管理可以分为固定分区、动态分区。 （1）固定分区
把内存空间分成若干个大小不等的区域，称为分区。每个用户程序（作业、进程）调入内存后，占用其中一个分区，程序运行完成后释放该分区。 （2）动态分区
系统生成后，操作系统占用内存的一部分，剩下的部分作为一个空闲区，当一个用户程序（作业、进程）调入内存时，把这个空闲区的低地址部分的区域分配给它，当有作业完成后释放所占用的存储区。 在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称主空闲。
分区的分配与回收
（1）固定分区时的分配和回收
当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。当进程执行完毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用即可。 （2）动态分区时的分配和回收
动态分区时的分配与回收主要解决三个问题：分配空闲区、更新可用表、合并空闲区
动态分区时的分配方法从可用表或自由链中寻找空闲区的方法：首次适应算法、最佳适应算法、最坏适应算法 ①首次适应算法
首次适应算法的表是按空闲区首址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。
分配时从表首开始，以请求内存区的大小逐个与空闲区进行比较，找到第一个满足要求的空闲后，若空闲区大小与请求区的大小相等，则将该空闲区分配给请求者，并撤消该空闲区所在表目；若大于请求区，就将该空闲区的一部分分配给请求者，然后，修改空闲区的大小和首址。
②最佳适应算法
最佳适应算法是将申请者放入与其大小最接近的空闲区中。切割后的空闲区最小，若系统中有与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者。（首次适应法则不一定）这种算法最大的缺点是分割后的空闲区将会很小，直至无法使用，而造成浪费。 ③最坏适应算法
为了克服最佳适应算法把空闲区切割得大小的缺点，人们提出了一种最坏适应算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题。 （3）动态分区的分配与回收
分配算法中切割空闲区是从低地址开始的，剩下的部分仍作为一个空闲区，门限值是切割空闲区后剩下的区域若小于门限值，就不切割该空闲区，统统分给申请者。
这三种放置算法的优劣很难区分，要具体情况具体分析。
例如：某时刻系统中有三个空闲区，其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)。有一作业系列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)
从搜索速度上看，最先适应算法具有最佳性能。从回收过程来看，最先适应算法也是最佳的。最先适应法尽可能地利用了地地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的作业或进程。
最佳适应法找到的空闲区是最佳的，最坏适应法是基于不留下碎片空闲区这一点出发的，它选择最大的空闲区来满足用户的需求，以期分配后的剩余部分仍能进行再分配。 分区存储管理的优缺点： 优点：
（1） 实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率 （2） 该方法要求的硬件支持少，管理算法简单，因而容易实现 缺点：
（1） 内存利用率仍然不高
（2） 作业或进程的大小受分区大小控制，除非配合采用覆盖技术和交换技术 （3） 无法实现各分区之间的信息共享 覆盖与交换技术
7.覆盖与交换技术是在多道环境下用来扩充内存的两种方法。
覆盖技术要求程序员提供一个清楚地覆盖结构。即程序员必须完成把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序的工作。操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。
交换技术是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。
交换技术不要求程序员给出程序段之间的覆盖结构，交换主要是在进程或作业之间进行，覆盖则主要是在同一个作业或进程内执行，覆盖只能覆盖那些与覆盖程序段无关的程序段。 交换进程由换入和换出两个过程组成。 8.页式管理
页式管理的基本原理
首先，进程虚拟地址空间分成大小相等的页面，进程的虚拟地址变为页号P与页内地址W组成。内存空间也按页的大小划分称片或页面，这些页面为系统中的任一进程所共享（除去操作系统以外），分页管理时，用户进程在内存空间内除了在每个页面内地址连续之外，每个页面之间不再连续）。采用请求调页或预调页技术实现内外存存储器的统一管理。
页式虚拟地址变为内存页面物理地址：页式管理把页式虚拟地址与内存页面物理地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。 页式存储管理要解决如下问题： （1）页式存储管理系统的地址映射； （2）调入策略； （3）淘汰策略； （4）放置策略。 静态页面管理
静态页面管理方法是在作业或进程开始执行之前，把该作业或进程的程序段或数据全部装入内存的各个页面中，并通过页表和硬件变换地址机构实现虚拟地址到内存物理地址的地址映射。 ①内存页面分配和回收
静态页面管理的第一步是为要求内存的作业或进程分配足够的页面。系统依靠存储页面表、请求表以及页表来完成内存的分配工作。 页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。
最简单的页表是由页号和页面号组成，页表在内存中占有一块固定的存储区，大小由进程或作业的长度来决定。页式管理时每个进程至少拥有一个页表。
请求表用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。系统应该知道每个作业或进程的页表起始地址和长度，以进行内存分配和地址变换。请求表中还应该包括每个进程或作业所请求的页面数。
存储页表指出内存各页面是否已被分配出去，以及未分配页面的总数。通常有两种记录空闲存储块的方法：位图法和链表法。 位图法：在内存中划分一块固定区域，每个单元的每个比特代表一个页面，如果该页面已被分配，则对应比特位置1，否则置0。 链表法：在空闲页面链中，对首页面的第一个单元和第二个单元分别放入空闲页面总数与指向下一个空闲页面的指针。其他页面的第一个单元中则分别放入指向下一个页面的指针。链表法由于使用了空闲页面本身的单元存放指针，因此不占据额外的内存空间。
分配算法：请求表给出进程或作业要求的页面数，然后，由存储页面数表检查是否有足够的空闲页面，如果没有，则本次无法分配，如果有则首先分配设置页表，并填写请求表中的相应表项后，按一定的查找算法，搜索出所要求的空闲页面，并将对应的页面号填入页表中。 静态页式管理的页面回收方法：当进程执行完毕时拆除对应的页表，并把页表中的各页面插入存储页面表即可。 动态页式管理
动态页式管理分为请求页式管理和预调入页式管理。
请求式分页存储管理与静态页式管理在内存块的分配与回收，存储保护某方面都十分相似，不同之处在于地址重定位问题。在请求式分页存储管理的地址重定位时，可能会出现所需页面不在主存的情况，此时，系统必须解决以下两个问题： （1）当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？ （2）当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？
怎样发现不在内存中虚页的问题可以用扩充页表的方法解决。增设缺页中断位和该页在外存的首址。缺页中断位：该位为“1”，表示此页已在内存；为“0”，表示该页不在内存。当此位为0时，会发出“缺页”中断信号，以求得系统的处理。
抖动现象：置换算法选择不当，有可能产生刚被调出内存的页又马上被调回内存，调回内存不久又马上被调出内存，如此反复的局面。这使得整个系统的页面调度非常频繁，以致大部分时间花费在主存和辅存之间的来回调入调出上的现象。
改变位：该位为“0”时，表示此页面在内存时数据未被修改过；为“1”时，表示被修改过。当此页面被选中为淘汰对象时，根据此位的取值来确定是否要将该页的内容进行磁盘回写操作。 页号 页面号 中断位 外存首址 改变位 请求页式管理中的置换算法
置换算法在内存中没有空闲页面时被调用。它的目的是选出一个被淘汰的页面。
把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率最低的页，将它们移出内存。
比较常用的置换算法有：随机淘汰算法（在系统设计人员无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出）、轮转法RR（轮转法循回换出内存可用去内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间）和先进先出法FIFO（选择内存驻留时间最长的一页将其淘汰）。最近最久未用页面淘汰算法（最近最久未用（LRU）页面淘汰算法的着眼点是在要进行页面淘汰时，检查这些淘汰对象的被访问时间，总是把最长时间未被访问过的页面淘汰出去。这是一种基于程序局部性原理的淘汰算法。也就是说，该算法认为如果一个页面刚被访问过，那么不久的将来被访问的可能性就大；否则被访问的可能性就小。）最近最少用页面淘汰算法（最近最少用（LFU）页面淘汰算法的着眼点是考虑内存块中页面的使用频率，它认为在一段时间里使用得最多的页面，将来用到的可能性就大。因此，当要进行页面淘汰时，总是把当前使用得最少的页面淘汰出去。要实现LFU页面淘汰算法，应该为每个内存中的页面设置一个计数器。对某个页面访问一次，它的计数器就加1。经过一个时间间隔，把所有计数器都清0。产生缺页中断时，比较每个页面计数器的值，把计数器取值最小的那个页面淘汰出去。）最优页面淘汰算法（如果已知一个作业的页面走向，那么要进行页面淘汰时，应该把以后不再使用的或在最长时间内不会用到的页面淘汰出去，这样所引起的缺页中断次数肯定最小，这就是所谓的“最优（OPT）页面淘汰算法”。遗
憾的是，OPT的前提是要已知作业运行时的页面走向，这是根本不可能做到的，所以OPT页面淘汰算法没有实用价值，它只能用来做为一个标杆（或尺度），与别的淘汰算法进行比较。如果在相同页面走向的前提下，某个淘汰算法产生的缺页中断次数是否接近它。） Belady现象：一般来说，对于任一作业或进程，如果给它的页面数越接近于它所要求的页面数，则发生缺页的次数会越小。但是，使用FIFO算法时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。 存储保护
页式管理可以为内存提供两种方式的保护。一种是地址越界保护，另一种是通过页表控制对内存信息的存取操作方式以提供保护。 地址越界保护可由地址变换机构中的控制寄存器的值——页表长度和所要访问的虚地址相比较来完成。 存取控制保护的实现则是在页表中增加相应的保护位即可。 ★页式管理的优缺点 优点
（1）由于它不要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题；
（2）动态页式管理提供了内存和外存统一管理的虚存实现方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用率，又有利于组织多道程序执行。 缺点
（1）要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本。 （2）增加了系统开销，例如缺页中断处理。
（3）请求调页的算法如选择不当，有可能产生抖动现象。
（4）虽然消除了碎片，但每个作业和进程的最后一页总有一部分空间得不到利用。如果页面较大，则这一部分的损失仍然较大。 9.段式管理
段式存储管理的基本思想：把程序按内容或过程（函数）关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟存储地址转化为内存中的实际地址。和页式管理一样，段式管理也采用只把那些经常访问的段驻留内存，而把那些在将来一段时间内不被访问的段放在外存，待需要时自动调入内存的方法实现二维虚拟存储器。 段式与页式的比较 段 式 页 式 分段由用户设计自己划分，每段对应的程序模块，有完整的逻辑意义 分页用户看不见，由操作系统为内存管理划分 段面是信息的逻辑单位 便于段的共享，执行时按需动态链接装入 段长不等，可动态装入，有利于新数据的增长 二维地址空间：段名、段中地址；段号、段内单元号 管理形式上象页式，但概念不同 段式管理的实现原理
段式管理把一个进程的虚地址空间设计成二维结构，即段号S与段内相对地址W。段号与段号之间无顺序关系，段的长度是不固定的。每个段定义一组逻辑上完整的程序或数据。例如，一个进程中的程序和数据可被划分为主程序段、子程序段、数据段与工作区段。每个段是一个首地址为零、连续的一维线性空间。 段式管理的内存分配与释放
段式管理中以段为单位分配内存，每段分配一个连续的内存区。由于各段长度不等，所以这些存储区的大小不一。而且，同一进程所包含的各段之间不要求连续。段式管理的内存分配和释放是动态进行的，与分区式管理一样可以采用最先适应法、最佳适应法、最坏适应法等进行空闲区分配。内存回收法也同分区式管理。当内存中没有足够的空闲区时，需要淘汰算法。 ★段式管理的地址变换
由于段式管理只存放部分信息副本在内存，而大部分信息在外存中，这必然引起CPU访问时发生所要访问的段不在内存现象。那么CPU如何感知到所要访问的段不在内存而启动中断处理程序呢？还有，段式虚拟地址属于一个二维的虚拟空间，怎样变换到一个一维线性物理地址呢？这些都由段式地址变换机构解决。
段式管理程序在进行初始内存分配之前，首先根据用户要求的内存大小为一个作业或进程建立一个段表，以实现动态地址变换和缺段中断处理及存储保护等。
段式管理的地址变换：一般在内存中给出一块固定的区域放置段表。当某进程开始执行时，管理程序首先把该进程的段表始地址放入段表地址寄存器中。通过访问段表寄存器，管理程序得到该进程的段表始地址从而可开始访问段表。然后，由虚拟地址中的段号s为索引，查段表。若该段在内存，则判断其存取控制方式是否有错。如果存取控制方式正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对应地址w相加，从而得到实际内存地址。若该段不存在，则产生缺段中断将CPU控制权交给内存分配程序。内存分配程序首先检查空闲区链，以找到足够长度的空闲区来装入所需的段。如果内存中的可用空闲区总数小于所要求的段长时，则检查段表中访问位，
页面是信息的物理单位 页一般不能共享 页面大小相同，位置不能动态增加 一维地址空间 往往需要多次缺页中断才能把所需的信息完整地调入内存 以淘汰那些访问概率低的段并将需要段调入。 段的共享与保护
段式存储管理可以方便地实现内存信息共享和进行有效地内存保护。这是因为段是按逻辑意义来划分的，可以按名访问的缘故。 段的共享：在多道环境下，常常有许多子程序和应用程序是被多个用户所使用的。特别是在多窗口系统、支持工具等广泛流行的今天，被共享的程序和数据的个数和体积都在急剧增加，有时往往超过用户程序长度的许多倍。 内存只保留一个副本，供多个用户使用，称为共享。
在多道环境下，由于进程的并发执行，一段程序为多个进程共享时，有可能出现多次同时重复执行该段程序的情况。这就要求它在执行过程中，该段程序的指令和数据不能被修改。
共享段进行内外存交换时，应该设置一个共享位。显然，一个正在被某进程使用或即将被某进程使用的共享段是不应该调出内存的。 段的保护：（1）地址越界保护法（2）存取方式控制保护法 ★段式管理的优缺点 优点
提供了内外存统一管理的虚存实现。 段长可根据需要动态增长。
便于对具有完整逻辑功能的信息段进行共享。 便于实现动态链接。 缺点
需要更多的硬件支持。 处理碎片比较麻烦。
给系统管理带来一定的难度和开销。 每个段的长度受内存可用区大小的限制。 选择不恰当的淘汰算法，可能会产生抖动现象。 10.段页式管理 段页式管理的基本思想
段式管理为用户提供了一个二维的虚地址空间，反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护等，这大大方便了用户。而分页管理系统则有效地克服了碎片，提高了存储器的利用率。从存储管理的目的来讲，主要是方便用户的程序设计和提高内存的利用率。那么把段式管理和页式管理结合起来让其互取长补短不是更好吗？于是，段页式管理方式便被提了出来。一般仅用于大型机。 段页式管理的实现原理
段页式管理时的进程的虚拟地址空间中的虚拟地址由三部分组成：即段号S，页号P和页内相对地址D。
由于虚拟空间的最小单位是页而不是段，从而内存可用区也就被划分成为若干个大小相等的页面，且每段所拥有的程序和数据在内存中可以分开存放。分段的大小也不再受内存可用区的限制。
为了实现段页式管理，系统必须为每个作业或进程建立一张段表，管理内存分配与释放、缺段处理、存储保护和地址变换等。另外，由于一个段又被划分成了若干页，每个又必须建立一张页表，把段中的虚页变换成内存中实际页面。显然，与页式管理时相同，页表中也要有实现缺页中断处理和页面保护等功能的表项。
另外，由于在段页式管理中，页表不再属于进程而属于段，因此，段表中应有页表首址和长度的项。 ★动态地址变换过程
在一般使用段页式存储管理的计算机系统中，都在内存中开辟出一块固定的区域存放进程的段表和页表。因此，在段页式管理系统中，要对内存中指令或数据进行一次存取的话，至少需要访问三次以上的内存。显然，CPU的执行指令速度大大降低。
为了提高地址转换速度，设置快速联想寄存器。它用于存放当前最常用的段号、页号和对应的内存页面与其它控制用栏目。 ★局部性原理和抖动问题
程序设计常识告诉我们，一个作业往往含有许多循环和子程序的结构。因此，在作业运行期间，在一小段时间内，访问的地址空间往往只涉及整个程序的一小部分。在另一小段数据内，又只涉及另外的一小部分。这种现象称为局部性特征。 反映在页面综迹里，这种特征表现为，在任何一小段时间里，作业只集中于访问某几页。 所谓工作集，就是一个作业在某一小段时间内访问页面的集合。
如用W(t,△t)表示在(t-△t)到t之间所访问的不同的页面，那么，这个W就称之为作业在时间t的工作集。工作集长度是W (t,△t)中的页面数。工作集长度越短，局部性越突出。
一般来说，一个作业的工作集，在运行的不同时刻是不同的，工作集大小亦不相等。而且，工作集大小与△t有关。 △t大小很难确定，过小，就不能体现一个工作集过渡到另一个工作集一般是缓慢的这一局部性特征。
一个进程执行过程中缺页的发生有两种可能。一种是并发进程所要求的工作集总和大于内存可提供的可用区。这时，系统将无法正常工作，因为缺乏足够的空间装入需要的程序和数据。
另一种可能性是，虽然存储管理程序为每个并发进程分配了足够的工作集，但系统无法在开始执行前选择适当的程序和数据进入内存。这种情况下，只能依靠执行过程中，当CPU发现所要访问的指令或数据不在内存时，由硬件中断后转入中断处理程序，将需要的程序和数据调入。
系统抖动：当给进程分配的内存小于所要求的工作集时，由于内存外存之间交换频繁，访问外存时间和输入输出处理时间大大增加，反而造成CPU因等待数据空转，使得整个系统性能大大下降，这就造成了系统抖动。 解决抖动问题 1、增加工作集大小；
2、选择不同的淘汰算法，尽量保持工作集页面在内存中。
实际上，为了使系统获得高效率，暂停一个作业，当其有足够数量的页面在主存时才恢复运行；而在调度一个新作业时，必须有足够多的空闲存储块，才让其进入主存。
计算机操作系统知识点整理
