大学操作系统课本操作系统知识点

1、第一章（一）1. 未配置操作系统的计算机系统（1）人工操作方式（人机矛盾）（ 2）脱机输入 / 输出方式2. 单道批处理系统内存里一道作业3. 多道批处理系统优点：（1）资源利用率高（CPU、内存、I/O设备）（ 2 ）系统吞吐量大缺点： （1）平均周转时间长（ 2 ） 无交互能力3. 分时系统（解决人机交互）及时接收：多个用户（配置多路卡） 、为每个用户配置一个缓冲区及时处理： （1） 作业直接进入内存（ 2）采用轮转运行方式（时间片）响应时间=时间片X终端数4. 实时系统周期性实时任务和非 . 硬实时任务和软 .（二）操作系统的基本特性1. 并发（进程才能）实现并发执行的前提是：多道程序环

2、境2. 共享J, /、互斥共享方式、同时访问方式3. 虚拟（ 1）时空复用技术（虚拟处理机技术、虚拟设备技术）（2）空分复用技术（虚拟磁盘技术、虚拟储存器技术）4. 异步5. 操作系统两个最基本的特征：并发和共享第二章（一）1. 前趋图（有向无环图）：描述进程之间执行的先后顺序2. 顺序执行：顺序性、封闭性、可再现性并发执行：间断性、失去封闭性、不可再现性（与时间有关的错误）Bernstein 条件（二）1. 进程实体：包括程序段、数据的和 PCB2. 进程的特征：动态性、并发性、独立性、异步性（按各自速度推进）3. 进程的三种基本状态：就绪、执行、阻塞相互之间的转换注意：执行 - （时间片完

3、） - 就绪4. 进程的创建（状态） ：申请空白 PCB- 分配资源 - 挂到就绪队列进程的终止（状态） ：保存记录 -PCB 返还系统5. 进程的挂起（不再被调度不在内存了、 suspend 原语）活动就绪 - （挂起） - 静止就绪活动阻塞 - （挂起） - 静止阻塞执行 - （挂起） - 静止就绪进程的激活（ active 原语）静止就绪 -（激活）- 活动就绪静止阻塞 -（激活）- 活动阻塞6.PCB 中的信息：P41PCB 组织方式：线性方式、链接方式、索引方式（三）1.OS 内核：常驻内存OS 状态:系统态（管态、内核态） 用户态（目态）2. 父进程创建子进程： 3 种返回值进程图

4、:描述进程家族关系的一棵树3. 进程的创建（ Creat 原语）引起进程创建的事件：用户登录、作业调度、提供服务（创建打印进程） 、应用请求 （用户创建）创建过程： 申请空白 PCB- 分配资源（从系统或父进程） - 初始化进程控制块 （初 始化内容见 P45） - 插入就绪队列4. 进程的终止引起进程终止的事件：正常结束、异常结束、外界干预终止过程： P465. 进程的阻塞（ block 原语）引起事件：请求共享资源失败、 等待某种操作的完成 （I/O 操作）、新数据未到达 （合 作进程中）、等待新任务的到来（发送进程，没有信息可发送）阻塞过程：状态：执行变为阻塞 -PCB 挂到阻塞队列 -

5、 调度其他进程6. 进程的唤醒（ wakeup 原语）唤醒过程：移除阻塞队列 - 挂到就绪队列四）1. 进程的同步（1）同步 :即某件事要等待另一件事完成才可以开始（ 2）2 种相互制约关系 ：间接相互制约关系（进程互斥访问资源） 、直接相互制约关系 （进程合作）2. 临界资源、临界区（进入区、退出区、剩余区）3. 同步机制遵循的规则 :空闲让进、忙则等待、有限等待、让权等待（请求资源失败应 释放 CPU ）4.3 种信号量：互斥信号量（初值为 1 ）、资源信号量（初值可为 n ）、同步信号量 （初值 为 0）P（ wait ）原语：减 1 V（signal） 原语：加 1（五）1. 进程的互

6、斥和同步称为低级进程通信，还有基于共享数据结构的通信方式也是2. 进程通信方式（ 1）直接通信方式（基于共享存储区）申请一个缓冲区 - 将进程 A 发送区的内容复制给缓冲区 - 将缓冲区挂到进程 B 的消息队列 - 进程 B 将缓冲区复制到自己的接收区（ 2）管道通信方式（对管道的 write 和 read ）管道是一个 pipe 文件，作为一个中介（3）消息传递方式（封装） ：直接和间接（有中间实体：邮箱）（六）进程和线程的区别 重第三章1. 三大调度：高级调度（作业调度） ：调度作业（外存 - 内存），只用于多道批处理系 统低级调度（进程调度） ：调度进程（就绪 - 获得 CPU）中级调度

7、（内存调度） ：挂起（内存 - 外存 - 重入内存）2. CPU 利用率： CPU 有效工作时间 /（CPU 有效工作时间 +CPU 空闲等待时间 ）（二）1. 作业：包含程序和数据，还有作业说明书。批处理系统中，是以作业为基本单位从外存调入内存的。2. 作业控制块（ JCB） :作业在系统中存在的标志。 包含：作业标识、 .P883. 作业进入系统时 - “作业注册”程序为其建立作业控制块 - 放到作业后备队列（外 存） - 调度作业进入内存4. 作业的 4 种状态：提交状态、后备状态、运行状态（对应的进程有 3 种状态）、完成 状态5. 作业调度的任务：（1）接纳多少个作业：取决于 多道程

8、序度（2）接纳哪些作业：取决于 调度算法调度时机：内存中的进程数小于多道度6. 进程的响应时间（作业的周转时间） ：完成时间 -到达时间 或 服务时间 + 等待时间 平均周转时间： N 个的和除以 N带权周转时间：（服务时间 +等待时间） /服务时间 或 1+等待时间 /服务时间 平均带权周转时间： N 个的和除以 N7. 调度算法 （4 种都可用于作业调度或进程调度 ）（ 1）先来先服务（ FCFS） 只能非抢占式（2）短进程优先（SJF）:有效降低作业的平均周转时间；对长作业不利（ 3）优先级调度算法 （PSA）（4）高响应比优先调度算法（ HRRN ）:优先级随等待时间延长而增加 优先权

9、= （服务时间 +等待时间） /服务时间 或 1+等待时间/服务时间 必须等某个进程完成时，才重新计算优先权，即运行某进程过程中有新进程到达也不会重新调度后面 3 个对于作业只能非抢占式；对于进程，可抢占式或非抢占式8. 题目未说明时，默认是非抢占式。（三）1. 非抢占式：调度时机为（ 1）进程运行完毕（ 2）进程 I/O 请求（ 3）执行 Block 原语抢占式：抢占原则（ 1）优先权（ 2）短进程优先（ 3）时间片2. 调度算法（ 1）轮转调度算法：基于时间片（2）优先级调度算法（ 3）多队列调度算法：多个 就绪队列 ，不同队列采用不同的调度算法（4）多级反馈队列调度算法：对于长作业，往后

10、时间片越长，得到的处理时间越长（5）最低松弛度优先算法：松弛度 =必须完成时间 -需要服务时间（四）1.可重用性资源（打印机） ：请求资源- 获得资源- 释放资源 可消耗性资源（通信中的消息） ：进程运行期间动态创建和消耗的，不再返回 可抢占性资源（CPU、内存） 不可抢占性资源（打印机） ：可能引起死锁2.引起死锁的 3 个原因：（1）竞争不可抢占性资源（ 2）竞争可消耗性资源（ 3）进程推进顺序不当（不安全区D）3. 产生死锁的必要条件 ：（ 1）互斥条件（ 2 ）请求和保持条件（ 3）不可抢占条件（ 4 ）循环等待条件（产生回 路）4. 处理死锁的方法 ：（1）预防死锁（ 2）避免死锁（

11、 3）检测死锁（ 4 ）解除死锁5. 预防死锁：破坏其中一个条件（1）互斥条件不能破坏还应保持（2）破坏请求和保持条件：A.一次性申请所需全部资源B.申请部分资源，用完释放,然后继续申请 （资源静态分配 ）（ 3）破坏不可抢占条件：提出新的资源请求时，必须释放自己已保持的所有资源（好 像被抢占了）（ 4）破坏循环等待条件：每个进程按序号递增的顺序请求资源（资源有序分配）6. 避免死锁：防止系统进入不安全状态（ 1）系统安全状态：分配资源后，系统能按一 安全序列 推进（ 2）银行家算法 ：二维数组 A. 表示每个进程对每个资源的最大需求量B. 表示每个进程对每个资源已分配到的C. 表示每个进程对

12、每个资源还需要的一维数组 A. 表示每类资源的可分配数 availableB. 表示每个资源当前可分配数（即加上某个进程运行完， 释放后的资源数） workC. 表示每个进程能否获得足够资源而运行finish算法思路： P112-1147. 检测死锁：（ 1）资源分配图（2）死锁定理：S为死锁的充分条件：当且仅当S状态的资源分配图是不可完全简化的8. 解除死锁：（1）抢占资源（2）终止（撤销）进程方法：A.终止所有进程B.逐个终止进程：付出代价最小的死锁解除算法 P117-118第四章 存储器管理均称为传统存储器管理方式，具有 2 个特点：一次性和驻留性 P153（一）1. 存储系统至少 3

13、级：最高层为 CPU 寄存器，内存，最底层为辅存。2. 可执行存储器：寄存器和内存 。3. 进程访问可执行存储器：使用一条load或store指令即可访问辅存：需通过 I/O 设备4. 程序的装入方式（ 1 ）绝对装入方式 ：单道环境 程序的相对地址（逻辑地址）与内存地址完全相同（ 2） 静态可重定位装入方式 ：多道环境 在装入时对目标程序中指令和数据地址进行 修改，以后不再改变。（3）动态运行时的装入方式 ：程序运行过程在内存的位置经常会改变 装入内存，地 址转换推迟到程序运行时才进行。A. 工作原理：增设一个重定位寄存器，存放程序在内存中的起始地址- 真正访问 内存地址 =相对地址 +寄存

14、器中的地址- 程序移动时，只需修改寄存器中的起始地址B. 在“紧凑（拼接）”时，要用到。（二）连续分配存储管理方式1 .单一连续分配 ：单道环境 内存分为系统区（多放在低址）和用户区2. 固定分区分配 ：多道环境 内存划分为若干个固定大小的区域，一个区域装入一道作 业(1) a.分区大小相等 b.分区大小不等( 2 )地址映射：采用静态重定位( 3)缺点：造成大量的内部碎片( 4) 数据结构：分区使用表 包括分区号、大小、起址、状态。3. 动态分区分配(可变分区分配) ：( 1 )分区分配：按需划分 分区回收：合并回收( 2) 数据结构：空闲分区表 包括分区号、大小、起址、状态(全都是未分配)

15、空闲分区链 双向的( 3)分配： P128 下面回收： P1 29 注意不同合并方式会对空闲分区表的修改不同( 4)基于顺序搜索的动态分区分配算法A. 首次适应算法：每次分配从头顺序查找，找到大小可以满足为止特点：优先利用内存地址空闲区，保留了高址的大空闲区缺点：低址不断被划分，产生许多碎片；查找效率低对固定分区：整体分配，易形成内碎片对可变分区：按需划分，易形成外碎片B. 循环首次适应算法：循环的，从上次找到的位置往下查找特点：使内存的空闲分区分布得更均匀缺点：缺乏大的空闲分区C. 最佳适应算法：所有空闲分区从小到大形成空闲分区链缺点：留下许多碎片对固定分区：内碎片小对可变分区：易形成外碎片

16、D. 最坏适应算法：所有空闲分区从大到小形成空闲分区链优点： 产生碎片的可能性最小 ；查找效率高对固定分区：内碎片大对可变分区：剩余分区可再次利用（5）基于索引搜索的动态分区分配算法A. 快速适应算法：相同容量的空闲分区形成一个空闲分区链设置索引表查找特点：不会对任何分区产生分割， 不会产生内存碎片 优点：查找效率高在分配分区时，以进程为单位，一个分区只属于一个进程，或多或少存在浪费B. 伙伴系统：原理、分配、回收、计算伙伴地址 P132C. 哈希算法：建立哈希函数，构造哈希表4. 动态重定位分区分配算法：与 3（3）基本相同，差别仅在于增加了紧凑的功能（三）对换1. 对换：进程或程序和数据：

17、内存 外存2. 对换的类型 ：（ 1 ）整体对换（进程对换） ：整个进程为单位对换（2）页面 / 分段对换（部分对换）：以进程的一个页面或分段为单位对换 目的：支持虚拟存储系统3. 磁盘空间分为文件区和对换区（对换空间）文件区：离散分配对换区：按需分配（分配算法上面 4 种都可以）、合并回收4. 进程的换进换出的选择标准 P137换出：换到 无阻塞进程为止 换入：第一个换“就绪”且换出时间最久的进程， 继续换到 无处于“就绪且换出” 状态的进程为止（四）分页存储管理方式：提高内存利用率1. 程序分为若干固定大小的页面，内存同样称为物理块（页框）2. 页面大小应为 2 的幂，通常为 1KB-8K

18、B3. 地址结构：页号P+页内地址 W （一维的）若页面的大小为L,则逻辑地址LA=P*L+W4. 每个进程一张 页面映像表（页表） ：存放在内存里，实现从页号到物理块号的地址映 射页表大小 = 表项数 *表项大小 P1395. 地址变换机构：实现从逻辑地址到物理地址的转换6. 页表寄存器：存放页表始址 +页表长度进程未执行时，页表始址 +页表长度放在 本进程 PCB 中- 执行时，装入页表寄存器7. 查找过程（ 2 次访问内存）：页表寄存器-页表（内存里） - 得到内存物理地址， 到内存取指令8. 具有快表（联想寄存器） ：先查快表看能否命中，未能命中则 查完页表后还要修改快 表9. 查快表

19、t1,查页表和取指令t2:若同时查块表和页表：命中： t1+t2未命中：t2+t1（修改快表）+t2若命中率为h,可得有效访问内存的时间：h*t1+（1-h）*（t2+t1）+t2五）分段存储管理方式：满足用户编程和使用的要求1. 作业分为若干个大小不同的段2. 一个作业最多 64K 个段，每个段最大长度为 64KB3. 地址结构：段号 + 段内地址（二维的）段号太大，段表中找不到则表示 越界 ；段内地址太大，超过段表中目的段的大小，则 表示 段内越界 。4. 每个进程一张段映射表 （段表）：存放在内存里， 每个表项包含一个 段的起始地址（基 址）+ 该段的长度5. 地址变换机构：段表寄存器，

20、存放段表始址 + 段表长度6. 查找过程（ 2 次访问内存）：段表寄存器 - 段表（内存里） - 得到内存物理地址， 到内存取指令7. 具有联想寄存器的：与分页式相同8. 分页与分段的区别： P148（ 重）（六）段页式存储管理方式1. 程序分成若干段，每个段再分成若干页2. 地址结构：段号 +段内页号 +页内地址（二维的）3. 需要段表寄存器、段表、页表：每个进程一张段表，段表包含页表始址 + 页表大小4. 查找过程（ 3 次访问内存）：段表寄存器 - 找段表（内存里），得到该段对应的页表 起始地址 - 找页表（内存里），得到该页的物里块号 - 形成物理地址，到内存取指令5. 具有联想寄存器

21、的：与分页式相同第五章 虚拟储存器原理：局部性原理（时间局部性、空间局部性）（一）概述1.虚拟储存器：具有 请求调入 功能和置换功能，从逻辑上对内存容量扩充2.特征：多次性、对换性、虚拟性3. 实现虚拟储存器的基础：离散存放、多次装入（二）请求分页存储管理方式1. 页表增加 4 个字段：状态位（该页是否已调入内存） 、访问位（访问次数或多久未访 问）、修改位（有被修改的置换时要写回外存） 、外存地址2. 缺页中断机构 ：指令执行期间，发现要访问的指令或数据不在内存，马上发出中断 这种属于陷进（软中断） ，之前打印机那些是硬中断3. 地址变换过程 P158（ 重） 注意最后必有“修改访问位和修改

22、位”这一步骤4. 最小物理块数：进程能正常运行的最小物理块数5. 内存分配策略 ：（1）固定分配局部置换固定分配：为每个进程分配固定数目的物理块，不再改变局部置换：只能从分配给该进程的页面中选一页换出（ 2）可变分配全局置换（3）可变分配局部置换一进程运行时缺页率很低，可以减少分配给该进程的物理块数6. 物理块分配算法（1）平均分配算法：平均分配给各个进程（2）按比例分配算法：按进程大小（3）考虑优先级的分配算法7. 页面调入策略1）何时调入A. 预调页策略 ：将预计不久后会被访问的页面预先调入内存，可用于首次调入时B. 请求调页策略：缺页请求时再调入，一次只调入一页（2）何处调入UNIX 方

23、式：从未运行过的，从文件区调入置换在对换区的，从对换区调入8. 缺页率：访问页面失败的次数 F/访问页面总次数A（三）页面置换算法1. 最佳置换算法（无法实现的） ：换出未来最迟被访问的页面2. 先进先出置换算法： 可能产生 Belady 异常，即分配的页面数越多，缺页率反而越多原因：先进的一般都是经常被访问的3. 最近最久未使用置换算法（LRU）:需要移位寄存器或栈两个硬件之一的支持移位寄存器：每个在内存的页面配置一个R=Rn-1Rn-2.R1R0进程访问某物理块时，将相应的寄存器的 Rn-1 位置 1。每隔一段时间 寄存器右移一位。最小数值那个就是最近最久未使用的页面。栈：栈顶总是最近访问

24、的页面号（命中时调到栈顶） ，栈低总是最久的（置换时从栈 底淘汰）4. 最少使用置换算法（ LFU） :即看访问次数最少的采用移位寄存器方式：每次访问某页，将该寄存器最高位置 1，每隔一段时间右 移一位。最小数值那个就是最少使用的页面。5. 简单的 Clock 置换算法（最近未用算法 NRL）：某页被访问时，访问位每页设置访问位（A），将内存中所有页面构成循环队列 置1置换时，若访问位为 0 则换出，为 1 则改为 0改进的 Clock 置换算法 ：多了修改位 （W） ，修改为为 1 表示修改过 第一步： 优先置换“ A=0 ，W=0 ”的页面 ，不改变访问位 A 第二步：找“ A=0 ，W=

25、1 ”的页面，同时将 A=1 的改为 A=0 第三步：重复第一步6. 页面缓冲算法（ PBA ）：（1）影响页面换进换出效率的因素A. 页面置换算法 B.写回磁盘的频率 C.读入内存的频率（ 2）算法原理 :A. 空闲页面链表：用于分配给频繁缺页的进程、一个 未被修改的页面（有数据） 要换出时，不换出，接到该链末尾B. 修改页面链表：一个 已修改的页面要换出时，不换出，接到该链末尾，方便集 中写回磁盘（四）抖动与工作集1. 工作集：某段时间内，进程实际所要访问页面的集合不同时间的工作集大小不同，所含的页面数也不同 P1712. 抖动（ 1）产生原因：进程太多，缺页频繁， CPU 效率急剧下降（

26、进程处于“抖动”状态）（2）产生前提：采取可变分配 + 全局置换（3）预防方法：A.采取局部置换策略B. 把工作集算法融入到处理机调度中调入作业之前，检查每个进程在内存的驻留页面是否足够多。C. 利用“ L=S ”准则调节缺页率P172D. 选择暂停的进程：挂起若干进程第六章（一）I/O 系统1.I/O 系统的层次结构：从下往上：硬件 - 中断处理程序 - 设备驱动程序 - 设备独 立性软件 - 用户层软件2.I/O 系统的上、下接口： I/O 系统接口、软件 / 硬件接口（下面就是硬件部分了）3.I/O 系统的分层：从下往上：中断处理程序 - 设备驱动程序 - 设备独立性软件4.I/O 系统

27、接口：有 3 种（1）块设备接口A. 块设备：以数据块为单位（磁盘）特点：传输速率高；可寻址；磁盘设备的I/O 常采用 DMA 方式B. 块设备接口特征：隐藏了磁盘的二维结构（磁道号 + 扇区）；将抽象的命令映射 为底层操作（ 2）流设备接口A. 流设备：以字符为单位（键盘、打印机）特点：传输速率低；不可寻址；流设备的 I/O 常采用中断驱动方式B. 程序用get和put操作，只能顺序存取C. 大多数流设备属于独占设备（互斥方式），要提供打开/关闭操作。（ 3 ）网络通信接口（二）硬件部分1.I/O 设备的类型：存储设备和 I/O 设备、低速设备（键盘、鼠标）和中速设备（打印 机）和高速设备（

28、磁盘、光盘）2. 设备控制器（控制一个或多个 I/O 设备）（ 1 ）三部分组成：A. 设备控制器与CPU的接口（并行）：数据总线 -DR: 内存 设备-C/S: 状态：设备 -CPU 启动： CPU- 设备地址总线：设备名 - 译码电路（ I/O 逻辑） - 接口控制总线：操作码 - 译码电路 -CRB. 设备控制器与设备的接口（串行）：数据线：设备 DR 状态线：设备 -C/S 控制线： C/S- 设备C. 译码电路（I/O逻辑）:实现对设备的控制上面 2 个译码功能 +并行-（分解） - 设备控制器地址（即要选哪个设备） -地址线- 设备控制器-I/O 逻辑进行译码- 选中设备（ 3）设

29、备 -DR: 数据准备； DR- 内存：数据传送（ 4）设备控制器的功能：A. 接收和识别命令B. 数据交换C. 标识和报告设备的状态D. 地址识别（设备控制器可连接多个设备、其里面也有很大寄存器，都需要地址）E. 数据缓冲区F差错控制 3.I/O 通道（特殊处理机）1) 在 CPU 与设备控制器之间 目的：建立独立的 I/O 操作(2) 过程：CPU发I/O指令- 通道- 内存中取对应的通道程序并执行- 完成后, 向 CPU 发中断信号(3) 通道与 CPU 共享内存(其通道程序放在内存)( 4)通道的类型：A. 字节多路通道： 每个字通道连接一个设备, 按时间片轮转共享主通道 适合低 速设

30、备B. 数组选择通道：每次只允许一个设备传输数据C. 数组多路通道(三) 设备驱动程序1. 设备驱动程序的功能：A. 将命令中的抽象要求转换为与设备相关的底层操作B. 检查I/O请求的合法性，设置设备的工作方式C. 启动I/O设备D. 及时响应设备控制器发来的中断请求，调用相应的中断处理程序2. 设备驱动程序的特点：A. 用汇编语言编写B. 允许可重入3. 设备处理方式：A. 每类设备一个进程来控制B. 整个系统一个进程或一个输入一个输出共 2个进程C. 不设置进程(常用)4. 设备驱动程序的处理过程：将抽象要求转换为具体要求- 对服务请求进行校验 -检查设备的状态 - 传送必要的参数- 启动

31、 I/O 设备启动后，驱动程序把控制返回给 I/O 系统，自己阻塞起来，直到中断到来被唤醒I/O 操作是在设备控制器的控制下进行 ，实现处理机与 I/O 设备的并行操作5. 对 I/O 设备的控制方式（ 1）轮询的可编程 I/O 方式：数据传送过程中， CPU 一直查询CPU 与设备、设备之间只能串行工作（ 2）中断的可编程 I/O 方式（以 字节为单位 传送数据）：数据传送过程中， CPU 干别的事， 传送好控制器通过控制线发中断给 CPU ， CPU 取走数据写入内存能并行工作（ 3）直接储存器访问方式（ DMA 方式）：A. 以数据块为单位 、直接从设备到内存、在控制器的控制下不用经过 CPUB.DMA 控制器：三部分组成： DMA 控制器与主机的接口、与设备的接口、 I/O 控