1、2022年6月1日星期三22时18分27秒计算机操作系统Principles of Operating System胡志刚胡志刚中南大学信息科学与工程学院中南大学信息科学与工程学院Central South UniversityCollege of Information Science and Engineering 2022年6月1日星期三22时18分28秒计算机操作系统REFERANCEREFERANCEREFERANCEREFERANCEREFERANCEREFERANCE第第第第第第1 1 1 1 1 1章章章章章章 第第第第第第2 2 2 2 2 2章章章章章章 第第第第第第3 3
2、 3 3 3 3章章章章章章 第第第第第第4 4 4 4 4 4章章章章章章 第第第第第第5 5 5 5 5 5章章章章章章 2022年6月1日星期三22时18分28秒计算机操作系统第第第第第第6 6 6 6 6 6章章章章章章 第第第第第第7 7 7 7 7 7章章章章章章 第第第第第第8 8 8 8 8 8章章章章章章 第第第第第第9 9 9 9 9 9章章章章章章 第第第第第第101010101010章章章章章章 2022年6月1日星期三22时18分28秒计算机操作系统6.16.16.16.26.26.26.36.36.3 6.46.46.46.56.56.56.66.66.6实验二实验
3、二实验二实验二实验二实验二2022年6月1日星期三22时18分28秒计算机操作系统l为多道程序的运行提供良好的环境和存储基础；为多道程序的运行提供良好的环境和存储基础；l方便用户使用存储器，提高存储器和方便用户使用存储器，提高存储器和CPU的利用率；的利用率；l从逻辑上来扩充主存储器从逻辑上来扩充主存储器l主存空间分配和管理主存空间分配和管理l地址转换和重定位地址转换和重定位l存储保护和共享存储保护和共享l存储扩充存储扩充 2022年6月1日星期三22时18分28秒计算机操作系统 用户编制的源程序成为可以在内存运行的程用户编制的源程序成为可以在内存运行的程序通常要经历三个步骤：序通常要经历三个
4、步骤：。源源程程序序Compiler系统源系统源语句库语句库私有源私有源语句库语句库目标目标模块模块Linker系统目标系统目标语句库语句库私有源私有源语句库语句库装入装入模块模块Loader重定位重定位重定位重定位重定位重定位2022年6月1日星期三22时18分29秒计算机操作系统重定位的重定位的重定位的重定位的重定位的重定位的2 2 2种方式种方式种方式种方式种方式种方式用户程序中使用的地址；用户程序中使用的地址；系统为主存单元分配的地址；系统为主存单元分配的地址；例：例： 0 LOAD AX,6 ；将将6号单元内容入号单元内容入AX 2 ADD AX,8 ；AX与与8号单元内容相加号单元
5、内容相加 4 SRORE AX,10 ；AX内容入内容入10号单元号单元 6 A 8 B 10 A+B修改程序中与地址相关的内容修改程序中与地址相关的内容-将相对地址变为将相对地址变为绝对地址的过程称为程序重定位。绝对地址的过程称为程序重定位。2022年6月1日星期三22时18分29秒计算机操作系统程序入主存之前由编译程序入主存之前由编译/链接程序完成重定链接程序完成重定位，入主存可立即执行。位，入主存可立即执行。例例例例例例程序入主存之前不进行重定位，入主存执程序入主存之前不进行重定位，入主存执行到与地址相关项时，再进行重定位。行到与地址相关项时，再进行重定位。例例例例例例装入的装入的装入的
6、装入的装入的装入的3 3 3种方式种方式种方式种方式种方式种方式2022年6月1日星期三22时18分29秒计算机操作系统 0 LOAD AX,6 2 ADD AX,8 4 SRORE AX,10 6 A 8 B 10 A+B1000 LOAD AX,10061002 ADD AX,10081004 SRORE AX,10101006 A1008 B1010 A+B静态静态入入10001000 LOAD AX,61002 ADD AX,81004 SRORE AX,101006 A1008 B1010 A+B动动 态态执行：绝对地址执行：绝对地址=R+相对地址相对地址2022年6月1日星期三22
7、时18分29秒计算机操作系统事先已经知道用户程序入主存后的位置，故编事先已经知道用户程序入主存后的位置，故编译程序在编译时即可将相对地址改为绝对地址。装入译程序在编译时即可将相对地址改为绝对地址。装入程序按照装入模块中的地址，将程序和数据装入内存。程序按照装入模块中的地址，将程序和数据装入内存。多道环境下，编译程序不能预知用户程序入主多道环境下，编译程序不能预知用户程序入主存后的位置，故编译后的目标模块的起始地址一般设存后的位置，故编译后的目标模块的起始地址一般设为从为从0开始。可重定位装入程序根据内存使用情况，将开始。可重定位装入程序根据内存使用情况，将装入模块重定位后装入内存。装入模块重定
8、位后装入内存。装入程序按照装入模块中的地址，将程序和数装入程序按照装入模块中的地址，将程序和数据装入内存，执行时重定位。据装入内存，执行时重定位。程序的链接程序的链接程序的链接程序的链接程序的链接程序的链接2022年6月1日星期三22时18分29秒计算机操作系统将编译后得到的一组目标模块将编译后得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装以及它们所需要的库函数，装配成一个完整的装入模块。有三种链接方法：入模块。有三种链接方法：1、修改相对地址；、修改相对地址； 2、将外部调用符号，变换为相对地址；、将外部调用符号，变换为相对地址；例例例例例例边装入，边链接；边装入，边链接；程序
9、执行时再链接；程序执行时再链接；2022年6月1日星期三22时18分29秒计算机操作系统 模块模块ACALL B；Return； 模块模块BCALL C；Return； 模块模块CReturn；000L-1M-1N-1目标模块目标模块链接链接 模块模块AJSR “L”Return； 模块模块BJSR “L+M”Return； 模块模块CReturn；装入模块装入模块0LL+ML+M+N-12022年6月1日星期三22时18分29秒计算机操作系统实存管理实存管理/虚存管理虚存管理 内存分为内存分为：系统区，用户区；：系统区，用户区； 存储保护存储保护：一般采用界限地址寄存器。：一般采用界限地址寄
10、存器。系统区系统区1用户区用户区上限地址寄存器上限地址寄存器系统区系统区2下限地址寄存器下限地址寄存器固定分区分配固定分区分配固定分区分配固定分区分配固定分区分配固定分区分配2022年6月1日星期三22时18分29秒计算机操作系统将内存地址空间划分为若干个固定大小的将内存地址空间划分为若干个固定大小的区域，每个分区装入一道作业运行。区域，每个分区装入一道作业运行。动态分区分配动态分区分配动态分区分配动态分区分配动态分区分配动态分区分配一、分区划分一、分区划分 1、大小相等；、大小相等； 2、大小不等；、大小不等；二、数据结构二、数据结构 例例例例例例 分区说明表：分区说明表：分区号，大小，起始
11、地址，状态；分区号，大小，起始地址，状态；三、分配三、分配/回收回收 例例例例例例四、优缺点四、优缺点： “内零头内零头”(Internal Fragmentation)OVER2022年6月1日星期三22时18分29秒计算机操作系统分区号分区号 大小（大小（KB）始址（始址（K）状态状态 1 15 30 已已/未未 2 30 45 已已/未未 3 50 75 已已/未未 4 100 125 已已/未未作业序列：作业序列：A(10),B(50),C(25),B,D(30).OS1/A2/C3/B4/30K45K75K125K225K0K2022年6月1日星期三22时18分29秒计算机操作系统主
12、存预先不划分分区，作业入主存执行时主存预先不划分分区，作业入主存执行时再根据作业大小划分等额分区分配。再根据作业大小划分等额分区分配。一、数据结构（一、数据结构（例例例例例例） ：空闲分区表：空闲分区表/空闲分区控制块；空闲分区控制块； 空闲分区表：空闲分区表：序号，大小，起始地址，状态；序号，大小，起始地址，状态； ：已分已分分区表分区表/已分分区控制块；已分分区控制块； 二、分区分配二、分区分配4算法算法 分配分配分配分配分配分配/ / /回收回收回收回收回收回收2022年6月1日星期三22时18分30秒计算机操作系统按照分区分配算法，选择一个合适的未分分区分按照分区分配算法，选择一个合适
13、的未分分区分配，并修改空闲配，并修改空闲/已分分区表。（已分分区表。（例例例例例例）“外零头外零头”：系统中存在但无法使用的分区。：系统中存在但无法使用的分区。克服外零头：设置不再分割的剩余区最小值克服外零头：设置不再分割的剩余区最小值Size回收分区应与空闲分区合并。回收分区应与空闲分区合并。共有四种情况（共有四种情况（P143图图5-10）（）（例例例例例例）动态重定位分区分配动态重定位分区分配动态重定位分区分配动态重定位分区分配动态重定位分区分配动态重定位分区分配2022年6月1日星期三22时18分30秒计算机操作系统进程序列：进程序列： A（10）B（50）C（25）B D（48）序号
14、序号 大小（大小（KB）始址（始址（K） 状态状态 1 610 30 未未 2 空表目空表目 3 空表目空表目 4 空表目空表目 .OS030640A（10） 600 40 B（50）4090 550 90 C（25）115 525 115 50 40 525 115 未未D（48） 2 88 525 115 ALLOCATION OVERC 552 88 空表目空表目OVER2022年6月1日星期三22时18分30秒计算机操作系统 移动内存中作业，将分散的多个可用分区合移动内存中作业，将分散的多个可用分区合并成一个大的分区，这种方法称为紧凑。并成一个大的分区，这种方法称为紧凑。要求：采用动态
15、重定位技术。要求：采用动态重定位技术。当作业需进入主存时，若主存每一个可用当作业需进入主存时，若主存每一个可用分区都不能满足要求，而可用分区总和又可满足分区都不能满足要求，而可用分区总和又可满足要求时，首先完成内存的要求时，首先完成内存的“紧凑紧凑”，然后调入。，然后调入。IBM-PCIBM-PCIBM-PC微机中的存储管理方式微机中的存储管理方式微机中的存储管理方式微机中的存储管理方式微机中的存储管理方式微机中的存储管理方式2022年6月1日星期三22时18分30秒计算机操作系统将进程当前不运行的指令和数据只在需要时装将进程当前不运行的指令和数据只在需要时装入到该进程不需再使用的指令和数据所
16、占用的内存入到该进程不需再使用的指令和数据所占用的内存空间中。空间中。使在较小的可用内存空间上运行较大的程序成使在较小的可用内存空间上运行较大的程序成为可能，该技术常与分区存储管理技术配合使用。为可能，该技术常与分区存储管理技术配合使用。 2022年6月1日星期三22时18分30秒计算机操作系统解决由于内存不足而无法同时调入解决由于内存不足而无法同时调入多个作业的问题。多个作业的问题。通过中级调度。通过中级调度。进程对换：进程对换： 以整个进程为单位；以整个进程为单位； 页页/段对换：虚存管理技术；段对换：虚存管理技术；将外存分为文件区和对换区，并设置数据将外存分为文件区和对换区，并设置数据结
17、构记录外存空间的使用情况，用于分配结构记录外存空间的使用情况，用于分配/回收。回收。2022年6月1日星期三22时18分30秒计算机操作系统例例例例例例内存物理地址空间按内存物理地址空间按2n等分成页框等分成页框/架，并从架，并从0连续连续编号：编号：0,1,2,.。作业的逻辑地址空间按页框大小等分成页，并从作业的逻辑地址空间按页框大小等分成页，并从0连续编号：连续编号：0,1,2,.。作业逻辑地址表示：作业逻辑地址表示：v=(P,d)作业连续的页，可以分配不连续的页框；作业连续的页，可以分配不连续的页框；系统设置页表系统设置页表PMT(Page Mapping Table)保存作业保存作业各
18、页入内存后的情况；各页入内存后的情况；主要有：页号、页框号主要有：页号、页框号设置设置一个一个页表地址寄存器，保存页表地址寄存器，保存当前执行进程当前执行进程页页表的起始地址和页表的长度。表的起始地址和页表的长度。地址变换地址变换地址变换地址变换地址变换地址变换2022年6月1日星期三22时18分30秒计算机操作系统.页框号页框号012345678910111201230 21 32 63 8 页号页号 页框号页框号作业作业AA0A1A2A3012作业作业B0 41 7 2 12 页号页号 页框号页框号B0B1B22022年6月1日星期三22时18分30秒计算机操作系统借助借助PMT表、页表寄
19、存器完成作业表、页表寄存器完成作业的逻辑地址（虚地址）到内存物理地址的的逻辑地址（虚地址）到内存物理地址的变换。变换。例例例例例例从虚地址转换为物理地址，然后再从虚地址转换为物理地址，然后再完成地址访问，共访问几次主存？效率为完成地址访问，共访问几次主存？效率为多少？多少？具有快表的地址变换具有快表的地址变换具有快表的地址变换具有快表的地址变换具有快表的地址变换具有快表的地址变换2022年6月1日星期三22时18分30秒计算机操作系统页框号页框号013456789101112A0A1A2A320 21 32 63 8 页号页号 页框号页框号作业作业A: V=(2,d)页表寄存器页表寄存器B L
20、 L(6，d)偏移偏移dOVER2022年6月1日星期三22时18分30秒计算机操作系统增设若干具有并行查询能力的特殊高速缓冲寄增设若干具有并行查询能力的特殊高速缓冲寄存器（联想寄存器存器（联想寄存器/快表），保存当前执行进程的部分快表），保存当前执行进程的部分/全部页表表目。全部页表表目。IBM：变换后备存储器变换后备存储器TLB （Translation Look-aside Buffer); NT:变换查找缓冲区；变换查找缓冲区；先查快表：先查快表： 找到：得出物理地址；找到：得出物理地址； 未找到：查页表。未找到：查页表。 例例例例例例由于联想寄存器较贵，系统配置数目有限，如由于联想寄
21、存器较贵，系统配置数目有限，如Inter 80486有有32个，个，如何提高从快表中找到的概率？如何提高从快表中找到的概率？程序的局部性特征程序的局部性特征程序的局部性特征程序的局部性特征程序的局部性特征程序的局部性特征有效访问时间示例有效访问时间示例有效访问时间示例有效访问时间示例有效访问时间示例有效访问时间示例2022年6月1日星期三22时18分30秒计算机操作系统P b 页号页号 页框号页框号V=(P,d)页表寄存器页表寄存器B L L(b，d)P b快表快表.OVER2022年6月1日星期三22时18分30秒计算机操作系统遵循结构化设计的程序具有如下两个特征：遵循结构化设计的程序具有如
22、下两个特征： 刚被访问的主存单元，不久会刚被访问的主存单元，不久会被访问。被访问。 刚被访问的主存单元，其刚被访问的主存单元，其不久会被访问不久会被访问。 For i= 1 To 100 Do A(i)=0; 2022年6月1日星期三22时18分31秒计算机操作系统联想寄存器的访问时间为联想寄存器的访问时间为20ns，内存访问时内存访问时间为间为100ns。 不使用联想寄存器的访问时间为：不使用联想寄存器的访问时间为： t=100*2 若从联想寄存器找到的概率为若从联想寄存器找到的概率为 ，则有，则有效访问时间为：效访问时间为： t=20%*(20+100*2)+80%(20+100) =14
23、0ns两级和多级页表两级和多级页表两级和多级页表两级和多级页表两级和多级页表两级和多级页表2022年6月1日星期三22时18分31秒计算机操作系统 现代大多数计算机系统都支持非常大的逻辑现代大多数计算机系统都支持非常大的逻辑地址空间。如地址空间。如Windows NT是是32位的位的OS，它为每它为每一个进程提供的逻辑地址空间为一个进程提供的逻辑地址空间为232，即，即4000MB。 对一个有对一个有32位逻辑地址空间的分页系统，若位逻辑地址空间的分页系统，若页面大小为页面大小为4KB（212B），），则每一个进程的页表则每一个进程的页表项可达项可达1兆个。设每一个表目占兆个。设每一个表目占4
24、个字节，则每个个字节，则每个进程页表需进程页表需4MB连续内存连续内存。为解决对内存高要求。为解决对内存高要求的问题，的问题， 1、页表采用离散分配方式；、页表采用离散分配方式； 2、部分页表表目入内存，其余仍在外存。、部分页表表目入内存，其余仍在外存。两级页表两级页表两级页表两级页表两级页表两级页表2022年6月1日星期三22时18分31秒计算机操作系统1、页表再按页框大小分页，、页表再按页框大小分页，0页、页、1页页.编号；编号； 2、为页表再建立一张页表（、为页表再建立一张页表（），每个），每个页表项记录页表页面的物理块号；页表项记录页表页面的物理块号； 3、设置外层页表寄存器，存放外层
25、页表的起址；、设置外层页表寄存器，存放外层页表的起址； 4、逻辑地址表示：、逻辑地址表示： 对于对于32位，页面大小为位，页面大小为4KB（212）的系统，则共有的系统，则共有220个表目。设每个表目占个表目。设每个表目占4字节，则：每页存放表目数字节，则：每页存放表目数为为210个，共需个，共需210个外层页表。个外层页表。逻辑地址如下：逻辑地址如下：P1P2d01112212231页内偏移页内偏移212外层页内地址外层页内地址210外层页号外层页号2102022年6月1日星期三22时18分31秒计算机操作系统一组逻辑信息的集合。如：主程序段、子一组逻辑信息的集合。如：主程序段、子程序段、数
26、据段、堆栈段等。程序段、数据段、堆栈段等。1、方便编程；、方便编程； 2、分段共享；、分段共享； 3、分段保护；、分段保护； 4、动态连接；、动态连接； 5、动态增长。、动态增长。分段的基本原理分段的基本原理分段的基本原理分段的基本原理分段的基本原理分段的基本原理2022年6月1日星期三22时18分31秒计算机操作系统作业的逻辑地址空间分段，每个段有自己的段名，作业的逻辑地址空间分段，每个段有自己的段名，并从并从0连续编号：连续编号：0,1,2,.。装入程序将分段装入时，为每一个分段分配一段装入程序将分段装入时，为每一个分段分配一段号；号；作业逻辑地址表示：作业逻辑地址表示：v=(S,w)以段
27、为单位分配主存，每一分段分配连续的分区；以段为单位分配主存，每一分段分配连续的分区；系统设置段保存作业各段入内存后的情况；系统设置段保存作业各段入内存后的情况； 主要有：段号、段长、主存起址主要有：段号、段长、主存起址设置设置一个一个段表地址寄存器，保存段表地址寄存器，保存当前执行进程当前执行进程段段表的起始地址和长度。（表的起始地址和长度。（F5-22,F5-23例例） 分页和分段的区别分页和分段的区别分页和分段的区别分页和分段的区别分页和分段的区别分页和分段的区别2022年6月1日星期三22时18分31秒计算机操作系统 可共享的代码应该是可共享的代码应该是可重入的可重入的（Reentran
28、t），），可重入代码又称可重入代码又称纯代码纯代码（Pure Code）。）。 为保证共享代码是纯代码，设计时可将作业为保证共享代码是纯代码，设计时可将作业分成两部分：纯段、杂段。分成两部分：纯段、杂段。 分段共享方便，分页共享较困难分段共享方便，分页共享较困难。 分页与分段都有较完善的保护机制。分页与分段都有较完善的保护机制。 分页系统，通过页表地址寄存器中的页表长度；分页系统，通过页表地址寄存器中的页表长度； 分段系统，通过段表地址寄存器中的段表长度分段系统，通过段表地址寄存器中的段表长度及段表中的段长项来实现存储保护。及段表中的段长项来实现存储保护。2022年6月1日星期三22时18分3
29、1秒计算机操作系统1、页是信息的物理单位，为实现离散存储，提、页是信息的物理单位，为实现离散存储，提高内存利用率而引入；段是信息的逻辑单位，为高内存利用率而引入；段是信息的逻辑单位，为满足用户要求而引入。满足用户要求而引入。2、页的大小固定且由系统确定；段长不定，取、页的大小固定且由系统确定；段长不定，取决于用户程序，并在编译时划分。决于用户程序，并在编译时划分。3、分页的作业地址空间是一维的；分段的作业、分页的作业地址空间是一维的；分段的作业地址空间是二维的。地址空间是二维的。共享与保护共享与保护共享与保护共享与保护共享与保护共享与保护2022年6月1日星期三22时18分31秒计算机操作系统
30、例例例例例例内存物理地址空间等分成页框，并从内存物理地址空间等分成页框，并从0连续编号；连续编号；作业的逻辑地址分段；作业的逻辑地址分段；作业各段按页框大小等分成页，并从作业各段按页框大小等分成页，并从0连续编号；连续编号；作业逻辑地址表示：作业逻辑地址表示：V=(S,P,d)作业各段连续的页，可以分配不连续的页框；作业各段连续的页，可以分配不连续的页框；系统为每个作业设置一个段表，每个分段再设置一个页表，系统为每个作业设置一个段表，每个分段再设置一个页表，分别保存作业各段及每段各页入内存后的情况；分别保存作业各段及每段各页入内存后的情况；段表：段号、段表：段号、该段页表起址、该段页表长度该段
31、页表起址、该段页表长度 页表：页号、页框号页表：页号、页框号设置设置一个一个段表地址寄存器，保存段表地址寄存器，保存当前执行进程当前执行进程段表的起始段表的起始地址和段表的长度。地址和段表的长度。2022年6月1日星期三22时18分31秒计算机操作系统.页框号页框号012345678910111201230 21 32 63 8 页号页号 页框号页框号作业作业AA00A01A02A030120 41 7 2 12 页号页号 页框号页框号A10A11A12主段主段0子段子段10 P0 L01 P1 L1段号段号 页表起址页表起址 长度长度2022年6月1日星期三22时18分31秒计算机操作系统
32、主存储器空间的分配和回收主存储器空间的分配和回收 帮助了解在不同的存储管理方式下，应怎帮助了解在不同的存储管理方式下，应怎样实现主存空间的分配和回收。样实现主存空间的分配和回收。 在在管理方式下，采用管理方式下，采用最先适应算最先适应算法法实现主存空间的分配和回收。实现主存空间的分配和回收。 提示及要求提示及要求提示及要求提示及要求提示及要求提示及要求2022年6月1日星期三22时18分31秒计算机操作系统自行假设主存空间大小，预设操作系统所自行假设主存空间大小，预设操作系统所占大小并构造未分分区表；占大小并构造未分分区表； 表目内容：表目内容：起址、长度、状态（未分起址、长度、状态（未分/空
33、表空表目）目）结合实验一，结合实验一，PCB增加为：增加为： PID，要求运行时间，优先权，状态，要求运行时间，优先权，状态，所需主存大小，主存起始位置所需主存大小，主存起始位置，PCB指针指针采用最先适应算法分配主存空间；采用最先适应算法分配主存空间；进程完成后，回收主存，进程完成后，回收主存，并与相邻空闲分并与相邻空闲分区合并。区合并。2022年6月1日星期三22时18分31秒计算机操作系统7.17.17.17.17.17.1 7.27.27.27.27.27.2 7.37.37.37.37.37.3 7.47.47.47.47.47.4 7.57.57.57.57.57.5 7.67.6
34、7.67.67.67.6 2022年6月1日星期三22时18分32秒计算机操作系统 作业一次全部入主存；作业一次全部入主存； 作业进入主存后一直驻留直到完成。作业进入主存后一直驻留直到完成。实存管理的不足：实存管理的不足： ，将系统可提供的比实际大很多，将系统可提供的比实际大很多的内存容量，称为虚拟存储器。的内存容量，称为虚拟存储器。 请求分页系统和请求分段系统。请求分页系统和请求分段系统。页页/ /段表扩充，缺页段表扩充，缺页/ /段中断，地址变换段中断，地址变换虚存的虚存的虚存的虚存的虚存的虚存的4 4 4个特征个特征个特征个特征个特征个特征2022年6月1日星期三22时18分32秒计算机
35、操作系统 采用离散分配方式；采用离散分配方式； 一个作业分成多次调入主存运行；一个作业分成多次调入主存运行； 将得不到运行的程序、数据调至外存将得不到运行的程序、数据调至外存盘交换区；盘交换区；2022年6月1日星期三22时18分32秒计算机操作系统 页号，页框号，状态位页号，页框号，状态位P，访问位访问位A，修改位修改位M，外存地址外存地址与一般中断的与一般中断的2点区别：点区别： 是在指令执行期间，发现指令是在指令执行期间，发现指令/数据不在主存时数据不在主存时产生并处理；产生并处理； 一条指令在执行期间，可能会产生多次缺页中一条指令在执行期间，可能会产生多次缺页中断。要求系统能保存多次中
36、断的状态。（断。要求系统能保存多次中断的状态。（例例例例例例）地址变换地址变换地址变换地址变换地址变换地址变换2022年6月1日星期三22时18分32秒计算机操作系统设：主存页框大小为设：主存页框大小为128字，有字，有128*128的数组；的数组；Var A:array1.128 of array1.128 of integer;for i:=1 to 128 for j:=1 to 128 Aij:=0;在在中，数组元素的存放中，数组元素的存放格式为格式为，问：执行，问：执行时缺页次数为多少？时缺页次数为多少？A1,1A1,2A1,3.A1,128.A128,1A128,2A128,3.A
37、128,128. 1页页 1页页2022年6月1日星期三22时18分32秒计算机操作系统存储保护检查：存储保护检查：页号页号页表长度？页表长度？是，越界是，越界中断；否则中断；否则2；查快表：查快表：找到找到，修改访问位对于写操作置，修改访问位对于写操作置修改位，并形成物理地址访问；修改位，并形成物理地址访问； 若未找到若未找到，查页表状态位：在主存，将表，查页表状态位：在主存，将表目写入快表；否则，缺页中断。目写入快表；否则，缺页中断。 页面分配页面分配页面分配页面分配页面分配页面分配2022年6月1日星期三22时18分32秒计算机操作系统预调预调/请调；请调；交换区交换区/文件区；文件区；
38、 保证进程正常运行所需最小的页框数，其保证进程正常运行所需最小的页框数，其值取决于指令的格式、功能和寻址方式。值取决于指令的格式、功能和寻址方式。 采用直接寻址：最小物理块数为采用直接寻址：最小物理块数为2；（存；（存放指令的页和存放数据的页）放指令的页和存放数据的页） 采用间接寻址：最小物理块数为采用间接寻址：最小物理块数为3； 页面分配和置换策略页面分配和置换策略页面分配和置换策略页面分配和置换策略页面分配和置换策略页面分配和置换策略2022年6月1日星期三22时18分32秒计算机操作系统分配：固定分配：固定/可变；可变； 置换：局部置换：局部/全局。全局。 固定分配局部置换；固定分配局部
39、置换； 可变分配全局置换；可变分配全局置换； 先分配一定数额，先分配一定数额，OS保留一个空闲页框队列。保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；进程缺页时，申请新页框：有，追加分配； 无，全局置换。无，全局置换。 可变分配局部置换；可变分配局部置换； 先分配一定数额，先分配一定数额，OS保留一个空闲页框队列。保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；进程缺页时，申请新页框：有，追加分配； 无，局部置换。无，局部置换。分配算法分配算法分配算法分配算法分配算法分配算法2022年6月1日星期三22时18分32秒计算机操作系统 每个进程分配的页框数为：每个进程分配
40、的页框数为： 系统的总页框数分为系统的总页框数分为：一部分一部分，按比例，按比例分配；分配；另一部分另一部分，按进程的优先权适当追加；，按进程的优先权适当追加；2022年6月1日星期三22时18分32秒计算机操作系统 “”(Thrashing)：刚刚被换出的页很快又被刚刚被换出的页很快又被访问，需再次调入。使进程花费大部分时间进行页访问，需再次调入。使进程花费大部分时间进行页面的置换，称进程发生了面的置换，称进程发生了“抖动抖动”。 为避免抖动的发生，应选择合适的置换算法。为避免抖动的发生，应选择合适的置换算法。1、最佳置换算法、最佳置换算法2、先进先出置换算法（、先进先出置换算法（FIFO）
41、（）（例例例例例例）3、最近最久未使用置换算法、最近最久未使用置换算法(Least Recently Used) 记录页面上次被访问的时间，选择最近记录页面上次被访问的时间，选择最近最久未使用的页面淘汰。（最久未使用的页面淘汰。（例例例例例例） 页面置换算法（续页面置换算法（续页面置换算法（续页面置换算法（续页面置换算法（续页面置换算法（续1 1 1 1 1 1）2022年6月1日星期三22时18分32秒计算机操作系统 设页面走向为：设页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。当分配。当分配的物理块数分别为的物理块数分别为3、4时时缺页次数缺页次数/缺页率缺页率各为各为多少多
42、少2022年6月1日星期三22时18分32秒计算机操作系统1+21+321+432+143+214+521+1 5221 5321+432+5 43+缺页次数缺页次数=10缺页率缺页率=10/12设页面走向为：设页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。当分配的。当分配的物理块数分别为物理块数分别为3、4时时缺页次数缺页次数/缺页率缺页率各为多少？各为多少？1+21+321+4321+1 43221 435214+152421543215+4321+5432+缺页次数缺页次数=8缺页率缺页率=8/122022年6月1日星期三22时18分33秒计算机操作系统（1）简单）简单Cl
43、ock 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页面置换算法（续页面置换算法（续页面置换算法（续页面置换算法（续页面置换算法（续页面置换算法
44、（续2 2 2 2 2 2）2022年6月1日星期三22时18分33秒计算机操作系统 选择近期使用次数最少的页面淘汰。选择近期使用次数最少的页面淘汰。 为每个页面设置一移位寄存器，记录该页被访问的频为每个页面设置一移位寄存器，记录该页被访问的频率。率。 采用可变分配、局部置换方式采用可变分配、局部置换方式。置换算法。置换算法FIFO，被置被置换的页按是否被修改过而入系统设置的两个链表队列：换的页按是否被修改过而入系统设置的两个链表队列：修改页修改页面链表、空闲页面链表。面链表、空闲页面链表。 如果再次产生缺页中断，首先检查链表队列：如果再次产生缺页中断，首先检查链表队列： 有有，恢复到进程驻留
45、集中；，恢复到进程驻留集中； 无无，取空闲页面链表中第一页分配。，取空闲页面链表中第一页分配。 修改页面链表中页面达到一定数量时，集中回写，减少修改页面链表中页面达到一定数量时，集中回写，减少I/O次数。次数。 2022年6月1日星期三22时18分33秒计算机操作系统缺页率对系统性能的影响；缺页率对系统性能的影响； 将缺页率保持在一个合理水平时应将缺页率保持在一个合理水平时应分配的页框数。分配的页框数。 T=(1-p)*ma+p*缺页中断时间缺页中断时间t =ma+(t-ma)*p (ma为存储访问时间为存储访问时间)1、缺页中断服务时间；、缺页中断服务时间； 2、缺页的读入时间；、缺页的读入
46、时间； 3、进程恢复执行时间。、进程恢复执行时间。由于由于tma，所以所以T直接比例于直接比例于p。 ()工作集工作集工作集工作集工作集工作集2022年6月1日星期三22时18分33秒计算机操作系统 进程缺页率高，不仅会使其运行进度减慢，进程缺页率高，不仅会使其运行进度减慢，而且增加了而且增加了CPU开销和通道及外设的负担。开销和通道及外设的负担。 1968年，年，Denning根据程序的局部性理论根据程序的局部性理论(进进程对页的访问不是均匀的，而是集中的。进程访程对页的访问不是均匀的，而是集中的。进程访问页面集合的变化，从一个时间段到另一个时间问页面集合的变化，从一个时间段到另一个时间段是
47、缓慢过渡的段是缓慢过渡的)，提出了工作集理论，提出了工作集理论(属属LRU算算法的发展法的发展)。 进程在某段时间内实际访问页的集进程在某段时间内实际访问页的集合。合。 具体表述具体表述具体表述具体表述具体表述具体表述2022年6月1日星期三22时18分33秒计算机操作系统 设进程在设进程在t- 到到t时间段内访问页的工作集记为：时间段内访问页的工作集记为：W(t, ) （ 为为工作集窗口尺寸工作集窗口尺寸）则：则：|W(t, )|为工作集中包含的为工作集中包含的页面数页面数 1、W是是t的函数，随时间不同，工作集不同；的函数，随时间不同，工作集不同； 2、W是是 的的非降函数。非降函数。 若
48、若 过过大，甚至将整个作业地址空间包含在内，大，甚至将整个作业地址空间包含在内，则失去虚存意义；则失去虚存意义； 过过小，会导致频繁缺页。小，会导致频繁缺页。 抖动的产生和预防抖动的产生和预防抖动的产生和预防抖动的产生和预防抖动的产生和预防抖动的产生和预防2022年6月1日星期三22时18分33秒计算机操作系统 随着多道程序度的提高，随着多道程序度的提高，CPU的利用率随之而提的利用率随之而提高，并在某时达到高，并在某时达到。此时，如果道数再增加，系。此时，如果道数再增加，系统缺页次数增加，产生抖动。统缺页次数增加，产生抖动。 采用局部置换策略，使抖动控制在局部范围；采用局部置换策略，使抖动控
49、制在局部范围； 在在CPU调度程序中引入工作集算法，控制道数；调度程序中引入工作集算法，控制道数； 采用采用准则：调整道数，使产生缺页频率的准则：调整道数，使产生缺页频率的平均时间平均时间 系统处理缺页的平均时间；系统处理缺页的平均时间； 挂起若干进程。挂起若干进程。2022年6月1日星期三22时18分33秒计算机操作系统 段名，段长，内存起址，状态位，存取方段名，段长，内存起址，状态位，存取方式，访问位，修改位，增补位，外存起址式，访问位，修改位，增补位，外存起址 在一条指令的执行期间，产生并处理中断，在一条指令的执行期间，产生并处理中断，且可能产生多次缺段中断。（且可能产生多次缺段中断。（
50、P185，F6-12） 分段的共享与保护分段的共享与保护分段的共享与保护分段的共享与保护分段的共享与保护分段的共享与保护2022年6月1日星期三22时18分33秒计算机操作系统 每个共享进程段表中，在相应共享段每个共享进程段表中，在相应共享段表目中，指向共享段在内存的起址即可。表目中，指向共享段在内存的起址即可。共享段表共享段表共享段表共享段表共享段表共享段表 越界检查：越界检查： 存取控制检查：存取控制检查： 环保护机构：类似于软件的层次结构，每层有环保护机构：类似于软件的层次结构，每层有不同的优先数，不同的优先数，0环为操作系统。环为操作系统。 个访问规则：个访问规则： 一个程序可以访问同
