-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path912.html
70 lines (70 loc) · 32.8 KB
/
912.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
<html><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=2.0, minimum-scale=0.1"><title>文字大纲</title></head><link href="res/icon.png" rel="icon"><body><div style="font-weight:bold">912</div><ul><li>数据结构<ul><li>一、绪论</li><li>二、向量</li><li>三、列表</li><li>四、栈与队列</li><li>五、二叉树</li><li>六、二叉搜索树</li><li>七、高级搜索树</li><li>八、词典</li><li>九、图</li><li>十、优先级队列</li><li>十一、串</li><li>十二、排序</li></ul></li><li>操作系统<ul><li>一、绪论
⭐<ul><li>操作系统概述
⭐<ul><li>OS与OS内核<ul><li>OS是管理硬件资源，控制程序执行，改善人机界面和为应用软件提供支持的一种系统软件</li><li>操作系统中的
软件分类<ul><li>应用软件</li><li>系统软件<ul><li>系统应用</li><li>操作系统<ul><li>命令行（交互界面）</li><li>内核：一些核心的功能，编译器、系统库之类的并非必不可少，并不属于内核</li></ul></li></ul></li></ul></li><li>操作系统内核<ul><li>抽象<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/5EI3B1JA64.png" width="486px" height="404.7652173913043px"/><br></li></ul></li><li>特征<ul><li>并发：计算机系统中同时存在多个运行程序</li><li>共享：程序间“同时”访问互斥共享各种资源</li><li>虚拟：每个程序“独占”一台完整计算机</li><li>异步：服务完成的时间不确定，也可能失效</li></ul></li></ul></li></ul></li><li>OS演化<ul><li>单用户系统：手动连线/纸带传输<ul><li>OS = 装载器+程序库</li></ul></li><li>批处理系统：磁带/磁盘传输<ul><li>OS = 装载器 + 程序控制器 + 输出处理器</li></ul></li><li>多道程序系统：多个程序驻留在内存中，轮流使用CPU<ul><li>OS = 装载器 + 程序调度 + 内存管理 + 输出管理</li></ul></li><li>分时系统：有中断处理，与外界交互延时缩短（交互性）</li></ul></li><li>操作系统结构<ul><li>简单结构<ul><li>没有拆分成模块</li></ul></li><li>单体分层结构<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/X2OHJCB258.png" width="486px" height="217.08259823576586px"/><br></li><li>将单体操作系统划分为多层，每层建立在低层之上，最底层 (layer 0), 是硬件驱动，最高层 (layer N) 是用户界面，每一层仅使用更低一层的功能和服务</li></ul></li><li>微内核结构<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/YC6PWSN854.png" width="313px" height="249.76767676767676px"/><br></li><li>尽可能把内核功能移动到用户空间，用户模块间的通信使用消息传递；
好处：灵活、安全；缺点：性能</li></ul></li><li>外核结构<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/1J4YFQ1VN6.png" width="409px" height="265.3352402745995px"/><br></li><li>让内核分配物理资源给多个应用程序，并让每个程序决定如何处理这些资源。
保护和控制分离</li></ul></li><li>虚拟机结构<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/45YI8G4D3J.png" width="436px" height="244.2563535911602px"/><br></li><li>虚拟机管理器将单独的机器接口转换成很多虚拟机，每个虚拟机都是一个原始计算机系统的有效副本，并能完成所有的机器指令</li></ul></li></ul></li></ul></li><li>中断、异常与系统调用
⭐⭐⭐⭐<ul><li>补充（考过一道小题）：QEMU模拟器：使用软件qemu-system-riscv64来模拟一台64位RISC-V架构的计算机，它包含：一个CPU（可调整为多核）、一块物理内存、若干IO外设</li><li>OS与硬件的关系
（软硬件接口）<ul><li> 硬件\stackrel{ 支持}{\longrightarrow}OS\stackrel{支持}{\longrightarrow}应用</li><li>硬件与OS的边界：指令集 + 寄存器</li><li>OS是对硬件的虚拟与抽象</li></ul></li><li>OS与应用程序的关系
（系统调用）<ul><li>OS通过系统调用来向应用程序提供服务</li><li>进程的地址空间：界定了OS/APP的边界</li><li>引入系统调用的目的是增加安全性和可靠性</li><li>系统调用大致类型<ul><li>进程控制、文件管理、设备管理、信息维护、通信</li></ul></li></ul></li><li>系统调用和CPU运行模型<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/82JW38ABC3.png" width="508px" height="187.36333699231614px"/><br></li></ul></li><li>隔离机制<ul><li>隔离<ul><li>定义：操作系统的应用程序不会影响（或破坏）其它应用或操作系统的正常执行或信息泄露</li><li>本质：在需要交换信息或共享资源的情况下才会出现（隔离并不意味着不要共享）</li><li>隔离的单位<ul><li>通常是运行的应用程序</li></ul></li><li>方法<ul><li>基于软件的隔离</li><li>基于硬件的隔离</li><li>基于网络的隔离</li></ul></li></ul></li><li>OS隔离APP的分类<ul><li>数据隔离：虚拟内存<ul><li>地址空间：若无许可，每个程序无法访问不属于自己的内存</li></ul></li><li>控制隔离：特权模式<ul><li>OS内核运行在内核态</li><li>应用程序运行在用户态</li></ul></li><li>时间隔离：
中断/异常机制<ul><li>中断：打断一直占用
CPU的应用程序<ul><li>结果：恢复中断前下一条指令</li></ul></li><li>异常：及时响应和处
理应用的异常行为<ul><li>结果：杀死产生异常的程序
或重新执行异常指令</li></ul></li></ul></li></ul></li></ul></li><li>对比<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/DG5RUXC96V.png" width="591px" height="207.15136876006437px"/><br></li><li>同步/异步<ul><li>中断是异步的：异步意味着中断的发生与当前程序执行无关，它们随时可以发生，通常是由硬件事件触发的，如I/O操作完成时钟中断等</li><li>异常是同步的：同步意味着异常是程序执行过程中由指令自身引起的，比如执行了一个除以零的操作，访问了非零内存地址等</li><li>系统调用可以是同步的，也可以是异步的：取决于是否需要等待系统调用完成</li></ul></li></ul></li></ul></li></ul></li><li>二、进程管理1
⭐⭐⭐⭐<ul><li>计算机系统的发展主线
⭐<ul><li>多道程序与协作式调度<ul><li>多道程序<ul><li>在内存中存在多个可执行程序，各个执行程序共享处理器</li><li>作业（job）：应用的一次执行过程</li></ul></li><li>协作式调度<ul><li>可执行程序主动放弃处理器使用</li><li>操作系统不会打断正在执行的程序</li><li>操作系统选择下一个执行程序使用处理器</li></ul></li></ul></li><li>分时多任务与
抢占式调度<ul><li>分时多任务<ul><li>用户视角<ul><li>在内存中存在多个可执行程序</li><li>各个可执行程序分时共享处理器</li><li>操作系统按时间片来给各个可执行程序分配CPU时间</li><li>进程（Process）：应用的一次执行过程</li></ul></li><li>OS视角<ul><li>进程（Process）：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，也成为任务（Task）</li><li>从一个应用程序对应的进程切换到另一个应用程序对应的进程，称为进程切换</li></ul></li></ul></li><li>抢占式调度<ul><li>进程被动地放弃处理器使用</li><li>进程按时间片轮流使用处理器，是一种“暂停—继续”组合的执行过程</li><li>基于时钟硬件中断机制，操作系统可随时打断正在执行的程序</li><li>操作系统选择下一个执行程序使用处理器</li></ul></li></ul></li><li>实时事务系统<ul><li>很多用户都在对数据库进行查询和修改，例如航空公司的预订系统</li><li>局限于一个或几个应用</li></ul></li></ul></li><li>进程
⭐⭐⭐⭐<ul><li>特点<ul><li>动态性：开始执行 → 暂停 → 继续 → 结束执行的过程</li><li>并发性：一段时间内多个进程在执行</li><li>有限度的独立性：进程之间不用感知对方存在</li></ul></li><li>进程与程序
⭐<ul><li>对应<ul><li>进程是操作系统处于执行状态的程序的抽象<ul><li>程序 = 文件（静态的可执行文件）</li><li>进程 = 执行中的程序 = 程序 + 执行状态</li></ul></li><li>同一程序的多次执行过程对应为不同进程</li><li>进程执行需要的资源：内存（保存代码和数据）、CPU（执行指令）</li></ul></li><li>区别<ul><li>进程是动态的，是程序的执行；程序是静态的，是有序代码的集合</li><li>进程是暂时的，是一个状态变化的过程；程序是永久的，可长久保存</li><li>组成不同，进程的组成包括程序、数据和进程控制块（PCB）</li></ul></li></ul></li><li>进程控制块（PCB）
⭐⭐⭐⭐<ul><li>操作系统管理进程的核心数据结构</li><li>功能<ul><li>OS管理控制进程执行所用的信息集合</li><li>OS用PCB描述进程的基本情况以及运行变化的过程</li><li>PCB是进程存在的唯一标志</li><li>每个进程都在OS中有一个对应的PCB<span style="color:blue;font-size:12px"> (注:进程与PCB的关系：一一对应)</span></li></ul></li><li>进程控制信息<ul><li>调度和状态信息：调度进程和处理机使用情况</li><li>进程间通信信息：进程间通信相关的各种标识</li><li>存储管理信息：指向进程映像存储空间的数据结构</li><li>进程所用资源：进程使用的系统资源，如打开文件等</li><li>有关数据结构连接信息：与PCB相关的进程队列</li></ul></li><li>组织方式<ul><li>链表：同一状态的进程其PCB成一链表，多个状态对用多个不同的链表，如：就绪链表、阻塞链表</li><li>索引表：同一状态的进程归入一个索引表，由索引指向PCB，多个状态对用多个不同的索引表，如：就绪索引表、阻塞索引表</li></ul></li></ul></li><li>进程模型
⭐⭐⭐⭐⭐<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/57RTQ1OZ6A.png" width="374px" height="325.1539961013645px"/><br><ul><li><img src="http://mindline-image2.qiniu.mindline.cn/F15Q36N41I.png" width="412px" height="322.13519163763067px"/><br></li></ul></li></ul></li><li>进程切换<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/DX5B4MJYP4.png" width="566px" height="294.62153163152055px"/><br></li></ul></li></ul></li></ul></li><li>三、内存管理
⭐⭐⭐⭐⭐<ul><li>内存分配<ul><li>地址空间
⭐<ul><li>术语<ul><li>物理地址<ul><li>用于内存芯片级的单元寻址，与处理器和CPU连接的地址总线相对应</li></ul></li><li>逻辑地址<ul><li>CPU执行机器指令时，用来指定一个操作数或是一条指令的地址。也是用户编程时使用的地址</li></ul></li><li>线性地址/虚拟地址<ul><li>与逻辑地址类似，是一个不真实的地址</li></ul></li></ul></li><li>内存管理<ul><li>内存管理方式<ul><li>重定位</li><li>分段</li><li>分页</li><li>虚拟存储</li></ul></li><li>操作系统的内存管理高度依赖硬件<ul><li>MMU（内存管理单元）：
处理CPU存储访问请求的硬件</li></ul></li></ul></li><li>地址空间的定义<ul><li>物理地址空间<ul><li>物理内存的地址空间</li></ul></li><li>虚拟地址空间<ul><li>虚拟内存的地址空间</li></ul></li><li>逻辑地址空间<ul><li>程序执行的地址空间</li></ul></li></ul></li><li>逻辑地址生成<ul><li>地址生成时机<ul><li>编译时<ul><li>假设起始地址已知</li><li>如果起始地址改变，必须重新编译</li></ul></li><li>加载时<ul><li>编译时起始地址未知，编译器需生成可重定位的代码</li><li>加载时位置可以不固定，生成绝对（虚拟）地址</li></ul></li><li>执行时<ul><li>执行时代码不可修改</li><li>需要地址转换（映射）硬件支持</li></ul></li></ul></li><li>虚拟内存可作为外存的缓存<ul><li>常用数据放在物理内存中</li><li>不常用数据放在外存</li><li>运行的程序直接用虚存地址，不用关注具体放在物理内存还是外存</li></ul></li><li>地址生成过程<ul><li>CPU<ul><li>ALU：需要逻辑地址的内存内容</li><li>MMU：进行逻辑地址和物理地址的转换</li><li>CPU控制逻辑：给总线发送物理地址请求</li></ul></li><li>内存<ul><li>发送物理地址的内容给CPU</li><li>接收CPU数据到物理地址</li></ul></li><li>操作系统<ul><li>建立逻辑地址LA和物理地址PA的映射</li></ul></li></ul></li></ul></li></ul></li><li>静态内存分配<ul><li>编译时的内存分配<ul><li>包括全局、静态变量和代码</li><li>位于全局/静态数据段、常量数据段、代码段</li></ul></li></ul></li><li>动态内存分配<ul><li>是指运行时的内存分配<ul><li>栈：局部变量</li><li>堆：malloc，free</li></ul></li><li>内存管理技术对比<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/U5SE6Q2O2L.png" width="840px" height="425.1905252317199px"/><br></li></ul></li><li>分类<ul><li>连续内存分配
⭐⭐⭐⭐⭐<ul><li>概念<ul><li>给应用分配一块不小于指定大小的连续的内存区域</li><li>内存碎片：不能被利用的空闲内存<ul><li>外碎片：分配单元间未被使用的内存</li><li>内碎片：分配单元內部未被使用的内存</li></ul></li></ul></li><li>分配
方式<ul><li>固定分区分配<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/2IY0UWGU1C.png" width="514.3333333333334px" height="826.6071428571428px"/><br></li><li>系统生成阶段，内存被划分成许多静态分区，进程可装入大于等于自身大小的分区中</li><li>程序可能放不下、内存利用率非常低、内部碎片</li></ul></li><li>动态分区分配
⭐⭐⭐⭐⭐<ul><li>当程序被加载运行时或运行中数据存储时，分配一个进程指定大小可变的连续分区（内存块）</li><li>名称区分：动态内存分配与动态分区分配。
动态分区分配是动态内存分配中的连续内存分配的分配方式中的一种</li><li>用户库/操作系统需要维护的数据结构<ul><li>已分配分区</li><li>空闲分区</li></ul></li><li>策略<span style="color:blue;font-size:12px"> (注:注意对比
不同的算法
以及优缺点)</span><ul><li>最先匹配
(First-fit)<ul><li>从低地址开始查找，使用最先匹配（不小于申请大小）的分区</li><li>优点：简单，在高地址空间有大块的空闲分区</li><li>缺点：外碎片，分配大块时较慢</li></ul></li><li>最佳匹配
(Best-fit)<ul><li>查找并使用不小于申请大小的最小空闲分区</li><li>优点：多数申请分配的尺寸较小时，效果很好</li><li>缺点：外碎片，释放分区较慢，容易产生很多无用的小碎片
通常性能是最差的</li></ul></li><li>最差匹配
(Worst-fit)<ul><li>使用尺寸大于n的最大空闲分区</li><li>优点：中等大小的分配较多时，效果最好</li><li>外碎片，释放分区较慢，容易破坏大的空闲分区</li></ul></li><li>下次匹配
(Next-fit)<ul><li>从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块</li></ul></li></ul></li><li>碎片整理
⭐⭐⭐<ul><li>碎片整理：通过调整进程占用的分区位置来减少或避免分区碎片</li><li>碎片紧凑：通过移动分配给进程的内存分区，以合并外部碎片</li><li>考虑到开销，移动也不能过于频繁</li><li>分区对换：通过抢占并回收处于等待状态进程的分区，以增大可用的内存空间<span style="color:blue;font-size:12px"> (注:换到外存去，变成挂起的状态)</span></li></ul></li></ul></li><li>伙伴系统
(Buddy System)
⭐⭐⭐<ul><li>分配<ul><li>数据结构：空闲块按大小和起始地址组织成一个二维数组，初始时只有一个大小为2^U的空闲块</li><li>过程：从小到大在空闲块中找最小可用块，如空闲块过大，对可用空闲块进行二等分，直到得到合适可用空闲块</li></ul></li><li>释放<ul><li>过程：把块放入空闲块数组，合并满足条件的空闲块</li><li>合并条件：在二叉树中是兄弟</li></ul></li><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/P4RQX1W5IK.png" width="569px" height="316.354006586169px"/><br></li></ul></li><li>优点：快速，无外部碎片</li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/ZWS4B3L6W6.png" width="723px" height="344.5089141004862px"/><br></li></ul></li></ul></li></ul></li></ul></li><li>非连续内存分配
⭐⭐⭐⭐⭐<ul><li>背景<ul><li>需求背景<ul><li>内核通过页表能够把多个地址不连续的物理页转换为地址连续的多个虚拟页</li><li>解决内存的外碎片的问题</li><li>创建运行的程序时需要分配让其真正运行所需的比较大的内存空间</li></ul></li><li>设计目标<ul><li>允许一个程序使用非连续的物理地址空间</li><li>允许共享代码和数据</li><li>支持动态加载和动态链接</li></ul></li><li>需解决<ul><li>虚拟地址到物理地址的地址转换</li><li>非连续分配的硬件辅助机制</li></ul></li></ul></li><li>段式存储管理
⭐⭐<ul><li>程序运行的段地址空间由多个段组成<ul><li>主代码段、子模块代码段、公共库代码段、栈段、堆数据……</li></ul></li><li>逻辑视图<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/680QRQ45FG.png" width="558px" height="393.19534883720934px"/><br></li></ul></li><li>实现方式<ul><li>段基址寄存器 + 段界寄存器（每段对应一个）</li><li>在内存中保存段表，段表项包括段基址和段长</li><li><img src="http://mindline-image2.qiniu.mindline.cn/5PG66WWFMY.png" width="726px" height="348.1800295130349px"/><br></li></ul></li></ul></li><li>页式存储管理
⭐⭐⭐⭐⭐<ul><li>将物理页面和逻辑页面都划分为大小相同的基本分配单位，二者的基本单位大小也是相同的</li><li>页表<ul><li>与段表类似，但无需记录长度，因为一个页大小是固定的</li><li><img src="http://mindline-image2.qiniu.mindline.cn/S3C33V29A7.png" width="721px" height="348.1797919762259px"/><br></li><li>每个进程都有一个，例外：反置页表</li></ul></li><li>与段式对比<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/277WGL41K2.png" width="1081px" height="549.8189655172413px"/><br></li><li>简单：所有页/段都在内存里</li></ul></li><li>性能
改进<ul><li>TLB<ul><li>提高页式存储管理性能的办法，缓存、间接访问</li><li>硬件管理，硬件全权处理TLB未命中</li><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/YN4IVV9O26.png" width="664px" height="423.11671924290215px"/><br></li><li>若未命中，更新TLB后重新执行该指令</li></ul></li><li>上下文切换
对TLB的处理<ul><li>TLB中的映射只对当前进程有效，进程切换时会出现问题</li><li>解决<ul><li>清空操作：全部有效位置0</li><li>有些系统添加了地址空间标识符（ASID），可看作进程标识符，但通常比PID位数少</li></ul></li></ul></li></ul></li><li>多级页表<ul><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/17K5HC8E41.png" width="588px" height="355.6207881210737px"/><br></li></ul></li><li>第一级页表的页号叫做页目录号</li><li>类似于树形结构，若一个二级页表中所有页都不是有效的，那页目录表可以直接存储“这个页表不包含有效位”，这样就不用在内存中留空间来存储无效的页表了，从而解决页表太大，消耗内存太多的问题，减少页表所占的连续页表空间</li><li>TLB未命中时，需要加载更多次内存，例如，使用二级页表，TLB未命中，则需访存两次（页表）得到物理地址，再访存数据一次</li><li>考试时一般情况二级页表占一个页面</li></ul></li><li>反置页表<span style="color:blue;font-size:12px"> (注:也叫反向页表、倒排页表)</span><ul><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/XSX5JE5W73.png" width="637px" height="371.67345783814375px"/><br></li></ul></li><li>思路：所有进程共享一个反置页表，不让页表与逻辑地址空间的大小相对应，而是与物理地址空间大小相对应，倒排页表的第i项就对应第i个物理页框</li><li>页表的
每个表
项包含<ul><li>页号：虚拟地址的页号部分</li><li>进程标识符：使用该页的进程。页号和进程标识符共同标志一个特定进程的虚拟地址空间中的一页</li><li>控制位：该域包含一些标记，比如有效、访问、修改，以及保护和锁定信息</li><li>链指针：空，或下一项的索引值</li></ul></li><li>优缺点<ul><li>优点<ul><li>所有进程共享一个反置页表，省空间</li><li>不需要多级页表的转换，简化管理</li></ul></li><li>缺点：需要额外的数据结构，实现复杂</li></ul></li></ul></li></ul></li></ul></li><li>段页式存储
⭐⭐<ul><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/27B150E5S2.png" width="628px" height="373.66534316505954px"/><br></li></ul></li><li>内存共享<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/NM7N235ALY.png" width="630px" height="394.40625px"/><br></li></ul></li></ul></li></ul></li></ul></li></ul></li></ul></li><li>虚拟存储<ul><li>覆盖和
交换<ul><li>覆盖技术<ul><li>程序员手动控制在较小的可用内存中运行较大的内存</li><li>不同时间段内执行的函数或模块共享一块有限的空间</li><li>图例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/39KVS41JE3.png" width="512px" height="306.4970251716247px"/><br>另一种调用方法只需共100K的内存</li></ul></li><li>不足：编程困难、增加执行时间</li></ul></li><li>交换技术<ul><li>操作系统以程序为单位自动换入换出内存<ul><li>换出：把一个执行程序的整个地址空间内容保存到外存<span style="color:blue;font-size:12px"> (注:挂起)</span></li><li>换入：将外存中某执行程序的地址空间内容读入内存</li></ul></li></ul></li><li>比较<ul><li>覆盖：发生在模块/函数间，程序员需给出模块/函数间的逻辑覆盖结构</li><li>交换：发生在运行的程序间，不需要模块间的逻辑覆盖结构</li></ul></li></ul></li><li>虚拟存储<ul><li>操作系统将不常用的部分内存暂存到外存，将要处理器访问的数据从外存装入内存
前提：程序具有局部性（使虚存有效果）</li><li>规则<ul><li>装载程序时：只将当前指令需要的部分页面或段装入内存</li><li>指令执行中需要的指令或数据不在内存（称为缺页或缺段）时：处理器通知操作系统将相应的页面或段调入内存</li><li>操作系统将内存中暂时不用的页面或段保存到外存</li></ul></li><li>特点<ul><li>不连续性<ul><li>物理内存分配非连续、虚拟地址空间使用非连续</li></ul></li><li>大用户空间<ul><li>虚拟内存大于实际的物理内存</li></ul></li><li>部分交换<ul><li>只对部分虚拟地址空间进行调入调出</li></ul></li></ul></li><li>在页式存储管理
的基础上增加<ul><li>请求调页：也称按需分页，在处理器需要访问数据时，才把数据从外存调入内存</li><li>页面置换：把不常用的页换出，要使用的页换入</li><li>缺页异常：
软硬件协同支持<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/JMFOG25A83.png" width="460px" height="377.6405274115198px"/><br></li><li>1.CPU读内存单元，在TLB中根据其虚拟地址匹配物理地址，未命中，读页表
2.由于页表项的存在位为0，CPU产生缺页异常
3.OS查找到保存在外存中对应的应用的页面的内容
4-1.如果有空闲物理页帧，把外存中的页面内容换入到某空闲物理页帧中
4-2.如无空闲物理页帧，通过置换算法释放/换出某物理页帧到外存，再把外存中的页面内容换入到某空闲物理页帧中
5.修改页表项，建立虚拟页到物理页的映射，存在位置为1
6.OS返回到应用程序，让处理器重新执行产生缺页异常的读内存单元指令</li><li>在何处保存未映射的页？<ul><li>交换空间<ul><li>磁盘分区：一般是扇区地址</li><li>在存在位为0的页表项中保存外存的页地址</li></ul></li><li>磁盘上的文件
（代码或数据）<ul><li>地址空间的逻辑段表示中有对应的文件位置</li><li>代码段：可执行二进制文件</li><li>动态加载的共享库程序段：动态调用的库文件</li></ul></li></ul></li></ul></li></ul></li><li>性能<ul><li>有效存储访问时间
EAT = 内存访问时间*(1-p) + 缺页异常处理时间</li><li>缺页异常处理时间 = 磁盘访问时间 * p(1+q)<ul><li>p：缺页率</li><li>q：写回概率（淘汰一个页面到磁盘）</li></ul></li></ul></li></ul></li></ul></li><li>页面置换算法<ul><li>概念<ul><li>时机：空闲内存数量设置上限和下限，到达下限开始回收内存，到达上限暂停回收</li><li> 页面锁定/常驻内存
（必须常驻内存的逻辑页面）<ul><li>操作系统的关键部分</li><li>要求响应速度的代码和数据</li><li>页表中的锁定标志位</li></ul></li><li>评价方法：缺页率</li><li>强制性未命中（冷启动未命中）：最初页面都不在内存中，一定产生未命中</li></ul></li><li>分类<ul><li>局部页面置换算法<span style="color:blue;font-size:12px"> (注:置换页面的选择范围仅限于
当前进程占用的物理页面)</span><ul><li>最优页面置换算法
OPT（理想化）<ul><li>置换未来最长时间不访问的页面，是一种理想化的算法，实际系统中无法实现</li><li><img src="http://mindline-image2.qiniu.mindline.cn/WB0041K7S2.png" width="478px" height="279.6663498098859px"/><br></li></ul></li><li>先进先出算法
FIFO<ul><li>选择在内存中驻留时间最久的页面进行置换，通过链表记录，把链头换出，新换进来的加入链尾</li><li>实现简单，性能较差，Belady现象</li><li><img src="http://mindline-image2.qiniu.mindline.cn/95RC15S83R.png" width="453px" height="177.3435251798561px"/><br></li></ul></li><li>最近最久未使用
LRU<ul><li>选择最长时间没有被引用的页面进行置换</li><li>实现<ul><li>页面链表<ul><li>类似于页面栈，访问到的拉到链表头，换出时选择链表尾</li></ul></li><li>页面栈<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/X4Y82152XJ.png" width="536px" height="359.38590078328986px"/><br></li></ul></li></ul></li></ul></li><li>时钟置换算法
CLOCK<ul><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/9DNM02E5X5.png" width="553px" height="262.26999208234366px"/><br></li><li><img src="http://mindline-image2.qiniu.mindline.cn/786BAPPH3P.png" width="579px" height="272.92775365179625px"/><br></li></ul></li><li>实现过程<ul><li>页面装入内存时，访问位初始化为1</li><li>访问页面时，访问位置1</li><li>缺页时，指针从当前位置开始顺序检查，若访问位1，则置0，转向下一个，否则替换之，然后指向下一个</li></ul></li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/S85L718QYH.png" width="598px" height="355.9673684210527px"/><br>初始顺序是1a、1b、1c、1d，指针在a</li></ul></li></ul></li><li>改进的时钟置换算法
改进CLOCK<ul><li>并非改进了缺页率，改进的是修改页的缺页处理开销</li><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/S58KFMJZN5.png" width="549px" height="269.1733505821475px"/><br></li></ul></li><li>实现过程<ul><li>类比于CLOCK算法，CLOCK算法找0，改进CLOCK找00（访问、修改）</li><li>访问页面时，访问位置1；修改页面时，修改位置1</li><li>缺页时，指针从当前位置开始顺序检查，若访问位1，则置0，转向下一个，否则看修改位，若修改位1，则置零，如果均为0（00），则替换之，置10或11（取决于是否修改），然后指向下一个<span style="color:blue;font-size:12px"> (注:访问位、修改位是1的时候都相当于一层复活甲，先用访问位)</span></li></ul></li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/R0814FURAF.png" width="453px" height="261.3461538461538px"/><br>最后把b换走</li></ul></li></ul></li><li>最不常用算法
LFU<ul><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/K6WU6W8U26.png" width="509px" height="240.2098930481283px"/><br></li></ul></li><li>特征<ul><li>开销大</li><li>开始时频繁使用，但以后不常使用的页面难以替换
解决方法：计数定期右移（减半）</li><li>也会产生Belady现象</li></ul></li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/W6IN438KLP.png" width="509px" height="260.65903197925667px"/><br></li></ul></li></ul></li><li>Belady现象<ul><li>采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象</li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/K41G691UQS.png" width="481px" height="447.0383729854183px"/><br>FIFO的123412512345，直接背下来
三个的时候缺页9次，四个的时候缺页10次</li></ul></li><li>哪些算法有Belady现象<ul><li>FIFO、时钟置换、改进时钟、LFU有</li><li>LRU没有</li></ul></li></ul></li><li>FIFO、CLOCK、LRU的比较<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/433934VAR8.png" width="593px" height="222.2388242498469px"/><br></li><li><img src="http://mindline-image2.qiniu.mindline.cn/7D458ITW4F.png" width="562px" height="152.92517006802723px"/><br></li><li><img src="http://mindline-image2.qiniu.mindline.cn/I614LQR1H6.png" width="560px" height="240.23952095808383px"/><br></li></ul></li></ul></li><li>全局页面置换算法<span style="color:blue;font-size:12px"> (注:置换页面的选择范围是所有
可换出的物理页面)</span><ul><li>为进程分配可变数目的物理页面</li><li>工作集页面置换算法<ul><li>工作集<span style="color:blue;font-size:12px"> (注:独立的，进程的固有性质)</span><ul><li><img src="http://mindline-image2.qiniu.mindline.cn/CC7RU42Z9G.png" width="486px" height="258.2255639097744px"/><br></li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/V4X8QT3Q37.png" width="423px" height="196.02439024390242px"/><br></li><li><img src="http://mindline-image2.qiniu.mindline.cn/U045HCVK87.png" width="418px" height="198.2680591818973px"/><br></li></ul></li></ul></li><li>常驻集<span style="color:blue;font-size:12px"> (注:取决于具体算法)</span><ul><li><img src="http://mindline-image2.qiniu.mindline.cn/34483O4QX8.png" width="569px" height="301.8614699331848px"/><br></li></ul></li><li>算法<ul><li>指定一个工作集窗口大小，换出不在工作集中的页面</li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/M1G5T2T1QH.png" width="609px" height="314.475px"/><br></li></ul></li></ul></li></ul></li><li>缺页率置换算法<ul><li>缺页率<ul><li>缺页次数/内存访问次数
或
缺页平均时间间隔的倒数</li><li>影响缺页率的因素<ul><li>页面置换算法</li><li>分配给进程的物理页面数目</li><li>页面大小</li><li>程序的编写方法</li></ul></li></ul></li><li>工作原理<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/S51TN8NRSL.png" width="594px" height="261.7231441048035px"/><br>一旦产生缺页，进行判断：如果距离上次缺页超过了设置的窗口时间，就把从上次缺页到现在访问过的页面留下，剩下的都踢出去，否则直接把缺失的页面加进来即可</li></ul></li><li>示例<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/6HG34ELJL2.png" width="516px" height="271.19064124783364px"/><br></li></ul></li></ul></li><li>抖动<ul><li><img src="http://mindline-image2.qiniu.mindline.cn/UJ8G5M555W.png" width="656px" height="349.3734335839599px"/><br></li></ul></li></ul></li></ul></li></ul></li></ul></li><li>四、进程管理2<span style="color:blue;font-size:12px"> (注:2天)</span></li><li>五、进程管理3<span style="color:blue;font-size:12px"> (注:2天)</span></li><li>六、设备管理<span style="color:blue;font-size:12px"> (注:0.5天)</span></li><li>七、文件系统<span style="color:blue;font-size:12px"> (注:0.5天)</span></li></ul></li><li>计算机组成<ul><li>一、计算机系统概述</li><li>二、数据的机器级表示</li><li>三、运算方法和运算部件</li><li>四、指令系统</li><li>五、中央处理器</li><li>六、指令流水线</li><li>七、存储器层次结构</li><li>八、总线与IO</li></ul></li><li>计算机网络<ul><li>一、计算机网络与因特网<span style="color:blue;font-size:12px"> (注:根据自顶向下整理，对网络的宏观理解)</span></li><li>二、物理层</li><li>三、链路层</li><li>四、网络层</li><li>五、传输层</li><li>六、应用层</li></ul></li></ul></body></html>