第6 7章 存储管理课件.ppt

2023年1月17日星期二12时8分17秒,计算机操作系统,操作系统原理 Principles of Operating System,胡志刚中南大学信息科学与工程学院Central South UniversityCollege of Information Science and Engineering,2023年1月17日星期二12时8分17秒,计算机操作系统,目 录,REFERANCE第1章 操作系统引论第2章 进程的描述与控制第3章 进程的通信与同步第4章 调度与死锁第5章 存储器管理,2023年1月17日星期二12时8分17秒,计算机操作系统,目 录,第6章 虚拟存储器第7章 设备管理第8章 文件系统第9章 磁盘存储器管理第10章 操作系统接口,2023年1月17日星期二12时8分17秒,计算机操作系统,第6章 存储器管理,6.1 存储管理功能 6.2 分区存储管理方式6.3 覆盖与交换技术6.4 分页存储管理方式6.5 分段存储管理方式6.6 段页式存储管理方式 实验二 主存空间的分配和回收,2023年1月17日星期二12时8分17秒,计算机操作系统,6.1 存储管理功能,1、存储管理的主要任务为多道程序的运行提供良好的环境和存储基础；方便用户使用存储器，提高存储器和CPU的利用率；从逻辑上来扩充主存储器2、存储管理功能主存空间分配和管理地址转换和重定位存储保护和共享存储扩充,2023年1月17日星期二12时8分17秒,计算机操作系统,一、程序的装入和链接,用户编制的源程序成为可以在内存运行的程序通常要经历三个步骤：编译、链接和装入。,源程序,Compiler,系统源语句库,私有源语句库,目标模块,Linker,系统目标语句库,私有源语句库,装入模块,Loader,重定位,2023年1月17日星期二12时8分17秒,计算机操作系统,重定位的2种方式,1、程序的装入,补充：重定位的概念：相对地址：用户程序中使用的地址；绝对地址：系统为主存单元分配的地址；相对地址空间：绝对地址空间：例：0 LOAD AX,6；将6号单元内容入AX 2 ADD AX,8；AX与8号单元内容相加 4 SRORE AX,10；AX内容入10号单元 6 A 8 B 10 A+B重定位：,修改程序中与地址相关的内容-将相对地址变为绝对地址的过程称为程序重定位。,2023年1月17日星期二12时8分17秒,计算机操作系统,1、静态重定位思想：程序入主存之前由编译/链接程序完成重定位，入主存可立即执行。例优缺点：,根据重定位的时机不同有2种方式,2、动态重定位思想：程序入主存之前不进行重定位，入主存执行到与地址相关项时，再进行重定位。例优缺点：,装入的3种方式,2023年1月17日星期二12时8分17秒,计算机操作系统,静/动态重定位示例,0 LOAD AX,6 2 ADD AX,8 4 SRORE AX,10 6 A 8 B 10 A+B,1000 LOAD AX,10061002 ADD AX,10081004 SRORE AX,10101006 A1008 B1010 A+B,静态入1000,1000 LOAD AX,61002 ADD AX,81004 SRORE AX,101006 A1008 B1010 A+B,动 态重定位R 1000,执行：绝对地址=R+相对地址,2023年1月17日星期二12时8分17秒,计算机操作系统,装入模块装入内存的三种方式：,1、绝对装入方式(Absolute Loading Mode)思想：事先已经知道用户程序入主存后的位置，故编译程序在编译时即可将相对地址改为绝对地址。装入程序按照装入模块中的地址，将程序和数据装入内存。,2、可重定位装入方式(Relocatable Loading Mode)思想：多道环境下，编译程序不能预知用户程序入主存后的位置，故编译后的目标模块的起始地址一般设为从0开始。可重定位装入程序根据内存使用情况，将装入模块重定位后装入内存。,3、动态运行时装入方式(Dynamic Run_time Loading)思想：装入程序按照装入模块中的地址，将程序和数据装入内存，执行时重定位。,程序的链接,2023年1月17日星期二12时8分17秒,计算机操作系统,链接程序的功能：将编译后得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。有三种链接方法：,2、程序的链接,一、静态链接(Static Linking)工作：1、修改相对地址；2、将外部调用符号，变换为相对地址；例,二、装入时动态链接(Load-Time Dynamic Linking)工作：边装入，边链接；,三、运行时动态链接(Run-Time Dynamic Linking)工作：程序执行时再链接；,2023年1月17日星期二12时8分17秒,计算机操作系统,程序的链接示例(P136 图5-4),模块ACALL B；Return；,模块BCALL C；Return；,模块CReturn；,0,0,0,L-1,M-1,N-1,目标模块,链接,模块AJSR“L”Return；,模块BJSR“L+M”Return；,模块CReturn；,装入模块,0,L,L+M,L+M+N-1,2023年1月17日星期二12时8分17秒,计算机操作系统,6.2 分区存储管理方式,区分：实存管理/虚存管理6.2.1单一连续分配(单用户、单任务的OS)内存分为：系统区，用户区；存储保护：一般采用界限地址寄存器。,系统区1,用户区,上限地址寄存器,系统区2,下限地址寄存器,固定分区分配,2023年1月17日星期二12时8分17秒,计算机操作系统,思想：将内存地址空间划分为若干个固定大小的区域，每个分区装入一道作业运行。,6.2.2固定分区分配,动态分区分配,一、分区划分 1、大小相等；2、大小不等；,二、数据结构 例 分区说明表：分区号，大小，起始地址，状态；,三、分配/回收 例,四、优缺点：“内零头”(Internal Fragmentation),OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,固定分区示例,分区号 大小（KB）始址（K）状态 1 15 30 已/未 2 30 45 已/未 3 50 75 已/未 4 100 125 已/未,作业序列：A(10),B(50),C(25),B,D(30).,OS,1/A,2/C,3/B,4/,30K,45K,75K,125K,225K,0K,2023年1月17日星期二12时8分17秒,计算机操作系统,6.2.3 动态分区分配,思想：主存预先不划分分区，作业入主存执行时再根据作业大小划分等额分区分配。,一、数据结构（例）1、空闲分区：空闲分区表/空闲分区控制块；空闲分区表：序号，大小，起始地址，状态；2、已分分区：已分分区表/已分分区控制块；,二、分区分配4算法 1、首次适应(First Fit)；2、循环首次适应(Next Fit)；3、最佳适应(Best Fit):4、最坏适应(Worst Fit);,分配/回收,2023年1月17日星期二12时8分17秒,计算机操作系统,1、分区分配按照分区分配算法，选择一个合适的未分分区分配，并修改空闲/已分分区表。（例）“外零头”：系统中存在但无法使用的分区。克服外零头：设置不再分割的剩余区最小值Size,三、分区的分配/回收,2、分区回收说明：回收分区应与空闲分区合并。共有四种情况（P143图5-10）（例）,动态重定位分区分配,2023年1月17日星期二12时8分17秒,计算机操作系统,动态分区分配示例（首次）,进程序列：,A（10）,B（50）,C（25）,B,D（48）,序号 大小（KB）始址（K）状态 1 610 30 未 2 空表目 3 空表目 4 空表目.,OS,0,30,640,A（10）,600 40,B（50）,40,90,550 90,C（25）,115,525 115,50 40 525 115,未,D（48）,2 88 525 115,ALLOCATION OVER,C,552 88,空表目,OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,6.2.4动态重定位分区分配,一、紧凑 移动内存中作业，将分散的多个可用分区合并成一个大的分区，这种方法称为紧凑。要求：采用动态重定位技术。二、动态重定位分区分配思想：当作业需进入主存时，若主存每一个可用分区都不能满足要求，而可用分区总和又可满足要求时，首先完成内存的“紧凑”，然后调入。书中算法流程,IBM-PC微机中的存储管理方式,2023年1月17日星期二12时8分17秒,计算机操作系统,6.3 覆盖与交换技术,6.3.1 覆盖技术基本思想：将进程当前不运行的指令和数据只在需要时装入到该进程不需再使用的指令和数据所占用的内存空间中。引入目的：使在较小的可用内存空间上运行较大的程序成为可能，该技术常与分区存储管理技术配合使用。优点：缺点：,2023年1月17日星期二12时8分17秒,计算机操作系统,6.3.2 交换(Swapping)技术,引入目的：解决由于内存不足而无法同时调入多个作业的问题。,1、多道程序环境下的对换实现：通过中级调度。分类：进程对换：以整个进程为单位；页/段对换：虚存管理技术；,2、对换空间管理实现：将外存分为文件区和对换区，并设置数据结构记录外存空间的使用情况，用于分配/回收。,2023年1月17日星期二12时8分17秒,计算机操作系统,6.4 分页存储管理方式,基本思想：（例）1、内存物理地址空间按2n等分成页框/架，并从0连续编号：0,1,2,.。2、作业的逻辑地址空间按页框大小等分成页，并从0连续编号：0,1,2,.。3、作业逻辑地址表示：v=(P,d)4、作业连续的页，可以分配不连续的页框；5、系统设置页表PMT(Page Mapping Table)保存作业各页入内存后的情况；主要有：页号、页框号6、设置一个页表地址寄存器，保存当前执行进程页表的起始地址和页表的长度。,地址变换,2023年1月17日星期二12时8分17秒,计算机操作系统,分页存储管理方式示例,.,页框号,0,1,2,3,4,5,6,7,8,9,10,11,12,0123,0 21 32 63 8,页号 页框号,作业A,A0,A1,A2,A3,012,作业B,0 41 7 2 12,页号 页框号,B0,B1,B2,OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,6.4.2地址变换,一、基本地址变换（直接地址映像）思想：借助PMT表、页表寄存器完成作业的逻辑地址（虚地址）到内存物理地址的变换。例问题：从虚地址转换为物理地址，然后再完成地址访问，共访问几次主存？效率为多少？,具有快表的地址变换,2023年1月17日星期二12时8分17秒,计算机操作系统,分页基本地址变换示例,页框号,0,1,3,4,5,6,7,8,9,10,11,12,A0,A1,A2,A3,2,0 21 32 63 8,页号 页框号,作业A:V=(2,d),页表寄存器,B L,L,(6，d),偏移d,OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,二、具有快表的地址变换（相关地址映像）,思想：增设若干具有并行查询能力的特殊高速缓冲寄存器（联想寄存器/快表），保存当前执行进程的部分/全部页表表目。例如：IBM：变换后备存储器TLB（Translation Look-aside Buffer);NT:变换查找缓冲区；地址变换：先查快表：找到：得出物理地址；未找到：查页表。例问题：由于联想寄存器较贵，系统配置数目有限，如Inter 80486有32个，如何提高从快表中找到的概率？,程序的局部性特征,有效访问时间示例,2023年1月17日星期二12时8分17秒,计算机操作系统,具有快表的地址变换示例,P b,页号 页框号,V=(P,d),页表寄存器,B L,L,(b，d),P b,快表,.,OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,程序的局部性特征,遵循结构化设计的程序具有如下两个特征：时间局部性：刚被访问的主存单元，不久会再次被访问。空间局部性：刚被访问的主存单元，其临近单元不久会被访问。例：For i=1 To 100 Do A(i)=0;,2023年1月17日星期二12时8分17秒,计算机操作系统,有效访问时间示例（P153）,设：联想寄存器的访问时间为20ns，内存访问时间为100ns。不使用联想寄存器的访问时间为：t=100*2 若从联想寄存器找到的概率为80%，则有效访问时间为：t=20%*(20+100*2)+80%(20+100)=140ns,两级和多级页表,2023年1月17日星期二12时8分17秒,计算机操作系统,6.4.3两级和多级页表,现代大多数计算机系统都支持非常大的逻辑地址空间。如Windows NT是32位的OS，它为每一个进程提供的逻辑地址空间为232，即4000MB。对一个有32位逻辑地址空间的分页系统，若页面大小为4KB（212B），则每一个进程的页表项可达1兆个。设每一个表目占4个字节，则每个进程页表需4MB连续内存。为解决对内存高要求的问题，有两种思路：1、页表采用离散分配方式；2、部分页表表目入内存，其余仍在外存。,两级页表,2023年1月17日星期二12时8分17秒,计算机操作系统,两级页表（其余自学）,思想：1、页表再按页框大小分页，0页、1页.编号；2、为页表再建立一张页表（外层页表），每个页表项记录页表页面的物理块号；3、设置外层页表寄存器，存放外层页表的起址；4、逻辑地址表示：V=（P1，P2，d）。例：对于32位，页面大小为4KB（212）的系统，则共有220个表目。设每个表目占4字节，则：每页存放表目数为210个，共需210个外层页表。逻辑地址如下：,P1,P2,d,0,11,12,21,22,31,页内偏移212,外层页内地址210,外层页号210,见F5-20，OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,6.5 分段存储管理,6.5.1分段存储管理方式的引入段：一组逻辑信息的集合。如：主程序段、子程序段、数据段、堆栈段等。目的：1、方便编程；2、分段共享；3、分段保护；4、动态连接；5、动态增长。,分段的基本原理,2023年1月17日星期二12时8分17秒,计算机操作系统,6.5.2分段的基本原理,1、作业的逻辑地址空间分段，每个段有自己的段名，并从0连续编号：0,1,2,.。2、装入程序将分段装入时，为每一个分段分配一段号；3、作业逻辑地址表示：v=(S,w)4、以段为单位分配主存，每一分段分配连续的分区；5、系统设置段保存作业各段入内存后的情况；主要有：段号、段长、主存起址6、设置一个段表地址寄存器，保存当前执行进程段表的起始地址和长度。（F5-22,F5-23例）地址映像同分页系统,分页和分段的区别,2023年1月17日星期二12时8分17秒,计算机操作系统,一、分页分段的共享 可共享的代码应该是可重入的（Reentrant），可重入代码又称纯代码（Pure Code）。为保证共享代码是纯代码，设计时可将作业分成两部分：纯段、杂段。分段共享方便，分页共享较困难。,6.5.3共享与保护,二、分页分段的保护 分页与分段都有较完善的保护机制。分页系统，通过页表地址寄存器中的页表长度；分段系统，通过段表地址寄存器中的段表长度及段表中的段长项来实现存储保护。,2023年1月17日星期二12时8分17秒,计算机操作系统,1、页是信息的物理单位，为实现离散存储，提高内存利用率而引入；段是信息的逻辑单位，为满足用户要求而引入。,分页和分段的3个主要区别,2、页的大小固定且由系统确定；段长不定，取决于用户程序，并在编译时划分。,3、分页的作业地址空间是一维的；分段的作业地址空间是二维的。,共享与保护,2023年1月17日星期二12时8分17秒,计算机操作系统,6.6段页式存储管理方式,基本思想：（例）1、内存物理地址空间等分成页框，并从0连续编号；2、作业的逻辑地址分段；3、作业各段按页框大小等分成页，并从0连续编号；4、作业逻辑地址表示：V=(S,P,d)5、作业各段连续的页，可以分配不连续的页框；6、系统为每个作业设置一个段表，每个分段再设置一个页表，分别保存作业各段及每段各页入内存后的情况；段表：段号、该段页表起址、该段页表长度 页表：页号、页框号7、设置一个段表地址寄存器，保存当前执行进程段表的起始地址和段表的长度。,2023年1月17日星期二12时8分17秒,计算机操作系统,段页式存储管理方式示例,.,页框号,0,1,2,3,4,5,6,7,8,9,10,11,12,0123,0 21 32 63 8,页号 页框号,作业A,A00,A01,A02,A03,012,0 41 7 2 12,页号 页框号,A10,A11,A12,主段0,子段1,0 P0 L01 P1 L1,段号 页表起址 长度,2023年1月17日星期二12时8分17秒,计算机操作系统,实验二 主存空间的分配和回收,一、实验内容 主存储器空间的分配和回收二、实验目的 帮助了解在不同的存储管理方式下，应怎样实现主存空间的分配和回收。三、实验题目 在可变分区管理方式下，采用最先适应算法实现主存空间的分配和回收。,提示及要求,2023年1月17日星期二12时8分17秒,计算机操作系统,1、自行假设主存空间大小，预设操作系统所占大小并构造未分分区表；表目内容：起址、长度、状态（未分/空表目）2、结合实验一，PCB增加为：PID，要求运行时间，优先权，状态，所需主存大小，主存起始位置，PCB指针3、采用最先适应算法分配主存空间；4、进程完成后，回收主存，并与相邻空闲分区合并。,提示及要求,2023年1月17日星期二12时8分17秒,计算机操作系统,第7章 虚拟存储器,7.1 虚拟存储器的基本概念7.2 请求分页存储器管理方式7.3 页面置换算法7.4 请求分页系统的性能分析7.5 请求分段存储器管理方式7.6 段的动态链接（补充）,2023年1月17日星期二12时8分17秒,计算机操作系统,7.1 虚拟存储器的基本概念,实存管理有两个明显的特性：一次性：作业一次全部入主存；驻留性：作业进入主存后一直驻留直到完成。实存管理的不足：一、虚拟存储器的定义 从用户角度，将系统可提供的比实际大很多的内存容量，称为虚拟存储器。二、虚存的2种实现方式 请求分页系统和请求分段系统。硬件支持：页/段表扩充，缺页/段中断，地址变换,虚存的4个特征,2023年1月17日星期二12时8分17秒,计算机操作系统,1、离散性：采用离散分配方式；2、多次性：一个作业分成多次调入主存运行；3、对换性：将得不到运行的程序、数据调至外存盘交换区；4、虚拟性：（OVER）,三、虚存的4个特征,2023年1月17日星期二12时8分17秒,计算机操作系统,7.2 请求分页存储器管理方式,7.2.1请求分页中的硬件支持一、页表机制 页号，页框号，状态位P，访问位A，修改位M，外存地址二、缺页中断机构与一般中断的2点区别：1、是在指令执行期间，发现指令/数据不在主存时产生并处理；2、一条指令在执行期间，可能会产生多次缺页中断。要求系统能保存多次中断的状态。（例）,地址变换,2023年1月17日星期二12时8分17秒,计算机操作系统,多次缺页中断示例,设：主存页框大小为128字，有128*128的数组；Var A:array1.128 of array1.128 of integer;程序段：for i:=1 to 128 for j:=1 to 128 Aij:=0;,在Pascal中，数组元素的存放格式为以行为主序，问：执行时缺页次数为多少？,A1,1A1,2A1,3.A1,128.A128,1A128,2A128,3.A128,128.,1页,1页,2023年1月17日星期二12时8分17秒,计算机操作系统,有快表的地址变换过程：(P170，F6-2)1、存储保护检查：页号页表长度？是，越界中断；否则2；2、查快表：找到，修改访问位对于写操作置修改位，并形成物理地址访问；若未找到，查页表状态位：在主存，将表目写入快表；否则，缺页中断。OVER,7.2.2 请求分页的地址变换机构,页面分配,2023年1月17日星期二12时8分17秒,计算机操作系统,一、页面调入3策略 1、何时调入：预调/请调；2、何处调入：交换区/文件区；3、调入过程：二、最小物理块数 保证进程正常运行所需最小的页框数，其值取决于指令的格式、功能和寻址方式。采用直接寻址：最小物理块数为2；（存放指令的页和存放数据的页）采用间接寻址：最小物理块数为3；,7.2.3 页面调度策略,页面分配和置换策略,2023年1月17日星期二12时8分17秒,计算机操作系统,三、页面分配和置换策略(三种),分配：固定/可变；置换：局部/全局。1、固定分配局部置换；2、可变分配全局置换；先分配一定数额，OS保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；无，全局置换。3、可变分配局部置换；先分配一定数额，OS保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；无，局部置换。,分配算法,2023年1月17日星期二12时8分17秒,计算机操作系统,1、平均分配算法2、按进程大小比例分配算法 每个进程分配的页框数为：Si/S*m3、考虑优先权的分配算法 系统的总页框数分为两部分：一部分，按比例分配；另一部分，按进程的优先权适当追加；,四、固定分配的分配算法,2023年1月17日星期二12时8分17秒,计算机操作系统,五、页面置换算法(Page-Replacement Algorithms),“抖动”(Thrashing)：刚刚被换出的页很快又被访问，需再次调入。使进程花费大部分时间进行页面的置换，称进程发生了“抖动”。为避免抖动的发生，应选择合适的置换算法。1、最佳置换算法2、先进先出置换算法（FIFO）（例）3、最近最久未使用置换算法(Least Recently Used)思想：记录页面上次被访问的时间，选择最近最久未使用的页面淘汰。（例）比较FIFO与LRU得出何结论？OVER,页面置换算法（续1）,2023年1月17日星期二12时8分17秒,计算机操作系统,FIFO置换算法示例,设页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。当分配的物理块数分别为3、4时缺页次数/缺页率各为多少,2023年1月17日星期二12时8分17秒,计算机操作系统,S=3标志,1+,21+,321+,432+,143+,214+,521+,1 52,21 5,321+,432+,5 43+,缺页次数=10缺页率=10/12,LRU置换算法示例,设页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。当分配的物理块数分别为3、4时缺页次数/缺页率各为多少？,S=4标志,1+,21+,321+,4321+,1 432,21 43,5214+,1524,2154,3215+,4321+,5432+,缺页次数=8缺页率=8/12,2023年1月17日星期二12时8分17秒,计算机操作系统,4、Clock置换算法(LRU的近似算法)（1）简单Clock NRU(Not Recently Used)思想：内存中所有页面组成循环队列，置换算法选择淘汰页面时，依次检查访问位：为0，换出；为1，重置为0，继续检查下一页面。（2）改进型Clock置换算法（算法见P179）通过访问位A、修改位M的组合值来确定。A 0 0 1 1 M 0 1 0 1 淘汰序号 0 1 2 3 OVER,页面置换算法（续1）,页面置换算法（续2）,2023年1月17日星期二12时8分17秒,计算机操作系统,页面置换算法（续2）,5、最少使用置换算法(Least Frequently Used)思想：选择近期使用次数最少的页面淘汰。实现：为每个页面设置一移位寄存器，记录该页被访问的频率。6、页面缓冲算法(Page Buffering Algorithm)思想：采用可变分配、局部置换方式。置换算法FIFO，被置换的页按是否被修改过而入系统设置的两个链表队列：修改页面链表、空闲页面链表。如果再次产生缺页中断，首先检查链表队列：有，恢复到进程驻留集中；无，取空闲页面链表中第一页分配。修改页面链表中页面达到一定数量时，集中回写，减少I/O次数。OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,7.2.4 请求分页系统的性能分析,分析内容：1、缺页率对系统性能的影响；2、将缺页率保持在一个合理水平时应分配的页框数。一、缺页率p对有效访问时间T的影响 T=(1-p)*ma+p*缺页中断时间t=ma+(t-ma)*p(ma为存储访问时间)t由三部分组成：1、缺页中断服务时间；2、缺页的读入时间；3、进程恢复执行时间。由于tma，所以T直接比例于p。(P180例,OVER),工作集,2023年1月17日星期二12时8分17秒,计算机操作系统,进程缺页率高，不仅会使其运行进度减慢，而且增加了CPU开销和通道及外设的负担。1968年，Denning根据程序的局部性理论(进程对页的访问不是均匀的，而是集中的。进程访问页面集合的变化，从一个时间段到另一个时间段是缓慢过渡的)，提出了工作集理论(属LRU算法的发展)。工作集：进程在某段时间内实际访问页的集合。OVER,二、工作集/驻留集(Working Set),具体表述,2023年1月17日星期二12时8分17秒,计算机操作系统,设进程在t-到t时间段内访问页的工作集记为：W(t,)（为工作集窗口尺寸）则：|W(t,)|为工作集中包含的页面数工作集W是二元函数：1、W是t的函数，随时间不同，工作集不同；2、W是的非降函数。若过大，甚至将整个作业地址空间包含在内，则失去虚存意义；过小，会导致频繁缺页。,工作集的具体表述,抖动的产生和预防,2023年1月17日星期二12时8分17秒,计算机操作系统,1、产生原因 随着多道程序度的提高，CPU的利用率随之而提高，并在某时达到峰值。此时，如果道数再增加，系统缺页次数增加，产生抖动。2、抖动预防的4种方法(1)、采用局部置换策略，使抖动控制在局部范围；(2)、在CPU调度程序中引入工作集算法，控制道数；(3)、采用L=S准则：调整道数，使产生缺页频率的平均时间=系统处理缺页的平均时间；(4)、挂起若干进程。,三、抖动的产生和预防,2023年1月17日星期二12时8分17秒,计算机操作系统,7.3 请求分段存储器管理方式,7.3.1 请求分段中的硬件支持一、段表机制 段名，段长，内存起址，状态位，存取方式，访问位，修改位，增补位，外存起址二、缺段中断 在一条指令的执行期间，产生并处理中断，且可能产生多次缺段中断。（P185，F6-12）三、地址变换机构(P186,F6-13)OVER,分段的共享与保护,2023年1月17日星期二12时8分17秒,计算机操作系统,共享方式：每个共享进程段表中，在相应共享段表目中，指向共享段在内存的起址即可。系统实现：一、设置共享段表/现行分段表二、建立共享段分配、回收操作过程三、完善分段保护机制，有3种常用措施：1、越界检查：2、存取控制检查：3、环保护机构：类似于软件的层次结构，每层有不同的优先数，0环为操作系统。2个访问规则：A、一个程序可以访问同环或低优先权环中数据；B、一个程序可以调用同环或高优先权环中的服务；,7.3.2 分段的共享与保护,2023年1月17日星期二12时8分17秒,计算机操作系统,共享段表,说明：1、共享段只有当所有共享进程都不再需要时(Count=0)，才会被释放；2、对同一个共享段，不同进程可以使用不同的段号来共享该段。,段名 段长 内存起址 状态 外存起址 共享进程计数Count状态 进程名 进程号 段号 存取控制.,2023年1月17日星期二12时8分17秒,计算机操作系统,共享段的分配、回收,分配：第一个请求使用共享段的进程申请内存分区，调入，修改共享段表相应内容；以后其它进程使用该共享段时，首先在本进程段表中填入该共享段的物理地址；然后在共享段表中增加一表目，填入进程名，存取控制等信息，并完成Count+1。回收：执行Count-1，取消共享段表中的表目 OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,7.4 UNIX存储管理,7.4.1 UNIX的交换策略一、数据结构映射图（map）1、在内存，用于管理交换设备的空闲资源；2、是一个数组，数组的内容包括可分配资源地址和该地址上可用资源的单位数；3、采用最先适配的算法分配一个资源上的连续“块”；,经过一段分配后为：,地址 单位数,地址 单位数,初始交换映射图：,例如：,2023年1月17日星期二12时8分17秒,计算机操作系统,1、引起进程换出的事件系统调用fork必须为子进程分配空间；系统调用brk扩大一个进程的大小；一个进程由于其栈的自然增长而变大；为了运行以前被换出、而现在又应被换入的进程；2、步骤确定换出的进程，使该进程中每个区的引用数减1，把那些引用数减为0的区换出；内核分配对换设备空间，将该进程锁在内存中；内核绕过高速缓冲，直接在对换设备和用户地址空间之间对换数据；一般若u区含有进程的地址转换表，则内核在实现上不能换出u区，同时在换出时还要决定是否一个进程能将其自身换出，还是必须由另一个进程将其换出；,二、进程的换出操作,2023年1月17日星期二12时8分17秒,计算机操作系统,由0进程完成，该程序也叫调度程序Sched或是交换程序swapper，负责进程调度和交换工作；内核定期唤醒交换进程，交换进程具有高优先权，在核心态下运行；时钟处理程序度量每一个进程在内存中或被换出的时间；换入操作是换出操作的逆过程。,三、进程的换入操作,2023年1月17日星期二12时8分17秒,计算机操作系统,7.4.2 UNIX的请求调页策略,一、数据结构1、页表（Page Table）：一个区对应一个页表，用来存取物理存储器。2、磁盘块描述项(disk block descriptors）：主要用于对虚拟页的磁盘副本进行说明。3、页面数据表pfdata(page frame data table)：用于描述每个物理页，以页号索引；4、对换使用表(swap-use table)：描述当前有多少页表项指向交换设备上的该页。,2023年1月17日星期二12时8分17秒,计算机操作系统,各数据结构之间的关系,页表,磁盘块描述字,物理页657,交换设备块4526,虚地址1695K,页号,657,交换设备号,1,块号,4526,2023年1月17日星期二12时8分17秒,计算机操作系统,二、偷页过程,是一个核心进程，它将不再是进程工作集的页偷偷地换出内存，又称为页面淘汰进程或页面窃取进程（Page Stealer Process）。在系统初启时创建，当空闲页低于某一个低水准表示时调用，使系统中可用的空闲存储维持在一个高水准标志上，以减少抖动；工作过程检查每个活动的、非上锁的区，跳过上锁区，期待下遍扫描区链表时再检查他们，并增加所有有效页的年龄字段；当遍数超过某个阈值，内核将该页置为可被换出的状态；当一个进程在一个区中出现有效性错，则内核锁住该区，偷页进程不能将出错页换出；,2023年1月17日星期二12时8分17秒,计算机操作系统,又称为页面故障（Page Faults）或页面错；有两种错，有效性错和保护错；有效性错：即进程企图存取一个有效位为0的页而产生的错误；内核调用有效性错处理程序；引起出错的页面状态有五种：在交换设备上，且不在内存；在内存中的空闲页链表上；在一个可执行文件中；标志为“请求清零”；标志为“请求填入”；保护错：进程试图存取一个许可位关闭的有效页面所产生的错误；,三、缺页,2023年1月17日星期二12时8分17秒,计算机操作系统,7.5 段的动态链接,静态链接方式，入内存之前完成：1、外部调用链接；2、重定位；缺点：由于被链接的分段可能不使用，造成内存和机时的浪费。为克服上述不足，分段存储管理中可采用动态链接方式。即在运行过程中，需要使用某分段时，再完成链接。,动态链接实现,2023年1月17日星期二12时8分17秒,计算机操作系统,一、设置连接间接字 寻址方式中，包含直接地址的字称为间接字。分段管理中，间接寻址使用较多，为标志直接地址的段是否已被链接，在进程间接字中设置标志位L(链接标志位)，将这样的间接字称为链接间接字。L=1/0，表示该分段未/已链接；当间接寻址时：若L=1，产生链接中断；若L=0，按链接间接字中的直接地址操作。,动态链接的实现,L 直接地址,编译的准备工作,2023年1月17日星期二12时8分17秒,计算机操作系统,编译原则：1、若被编译段中语句是访问本段单元，则将其编译成直接寻址格式；2、若被编译段中语句是访问外段单元，则将其编译成间接寻址格式。分3个步骤：（例）A、在本段中增设链接间接字，并设L=1；B、开辟另一个存储单元，保存被访问段的符号名、段内地址(S,w)；C、将间接链接字的地址场指向该符号名所在单元的地址。,编译的链接准备工作,链接中断,2023年1月17日星期二12时8分17秒,计算机操作系统,编译的链接准备工作示例,设：有一作业如下图所示：,.Call x|.,Y:,编译,.Call*main|100.,100,102,1 main|102,x|,Main分段入内存后0#,X分段3#,0 3|y,OVER,2023年1月17日星期二12时8分17秒,计算机操作系统,执行间接寻址指令时，硬件判断L=1，触发链接中断，转链接中断处理程序。经4步处理：1、通过链接间接字，找欲访问的段名|段内地址(x|)；(例)2、查共享段表、进程段表，判断该段是否在内存；3、是，查段号并修改链接间接字为段号及段内地址，并设置L=0，返回断点；4、否，分配内存，读入该分段，转第3步。,三、链接中断,