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

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 原语）静止就绪 - （激活） -> 活动就绪静止阻塞 - （激活） -> 活动阻塞中的信息： P41PCB组织方式：线性方式、链接方式、索引方式（三）内核：常驻内存OS 状态 :系统态（管态、内核态） 用户态

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

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

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

7、业（外存 -> 内存），只用于多道批 处理系统低级调度（进程调度） ：调度进程（就绪 -> 获得 CPU） 中级调度（内存调度） ：挂起（内存 -> 外存 -> 重入内存） 利用率： CPU 有效工作时间 /（CPU 有效工作时间 +CPU 空闲等待时间 ） （二）1. 作业：包含程序和数据，还有作业说明书。 批处理系统中，是以作业为基本单位从外存调入内存的。2. 作业控制块（ JCB） :作业在系统中存在的标志。 包含：作业标识、 .P883. 作业进入系统时 -> “作业注册”程序为其建立作业控制块 -> 放到作业后备队 列（外存） -> 调度作业

8、进入内存4. 作业的 4 种状态：提交状态、后备状态、 运行状态（对应的进程有 3 种状态）、 完成状态5. 作业调度的任务：（ 1）接纳多少个作业：取决于 多道程序度（2）接纳哪些作业：取决于 调度算法 调度时机：内存中的进程数小于多道度6. 进程的响应时间（作业的周转时间） ：完成时间 -到达时间 或 服务时间 +等待 时间平均周转时间： N 个的和除以 N带权周转时间：（服务时间 +等待时间） /服务时间 或 1+等待时间 /服务时间 平均带权周转时间： N 个的和除以 N7. 调度算法 （4 种都可用于作业调度或进程调度 ） （ 1）先来先服务（ FCFS） 只能非抢占式（2）短进程优

9、先（SJF）:有效降低作业的平均周转时间；对长作业不利（ 3）优先级调度算法 （PSA）（ 4）高响应比优先调度算法（ HRRN ） :优先级随等待时间延长而增加优先权= （服务时间 +等待时间） /服务时间 或 1+等待时间/服务时间 必须等某个进程完成时，才重新计算优先权，即运行某进程过程中有新进 程到达也不会重新调度后面 3 个对于作业只能非抢占式；对于进程，可抢占式或非抢占式8. 题目未说明时，默认是非抢占式。（三）1. 非抢占式：调度时机为 （1 ）进程运行完毕（ 2）进程 I/O 请求（3 ）执行 Block 原语抢占式：抢占原则（ 1）优先权（ 2 ）短进程优先（ 3）时间片2.

10、 调度算法（ 1）轮转调度算法：基于时间片（2）优先级调度算法（ 3）多队列调度算法：多个 就绪队列 ，不同队列采用不同的调度算法（4）多级反馈队列调度算法：对于长作业，往后时间片越长，得到的处理时间 越长（5）最低松弛度优先算法：松弛度 =必须完成时间 -需要服务时间（四）1.可重用性资源（打印机） ：请求资源 -> 获得资源-> 释放资源 可消耗性资源（通信中的消息） ：进程运行期间动态创建和消耗的，不再返回 可抢占性资源（CPU、内存）不可抢占性资源（打印机） ：可能引起死锁2.引起死锁的 3 个原因：（1）竞争不可抢占性资源（ 2）竞争可消耗性资源（ 3）进程推进顺序不当（

11、不 安全区 D ）3. 产生死锁的必要条件 ： （1）互斥条件（2）请求和保持条件（ 3）不可抢占条件（4）循环等待条件（产 生回路）4. 处理死锁的方法 ：（1）预防死锁（ 2）避免死锁（ 3）检测死锁（ 4 ）解除死锁5. 预防死锁：破坏其中一个条件（1）互斥条件不能破坏还应保持（2）破坏请求和保持条件：A. 一次性申请所需全部资源B.申请部分资源，用完释放，然后继续申请 （资源静态分配 ）（ 3）破坏不可抢占条件：提出新的资源请求时，必须释放自己已保持的所有资 源（好像被抢占了）（ 4）破坏循环等待条件： 每个进程按序号递增的顺序请求资源 （资源有序分配）6. 避免死锁：防止系统进入不安

12、全状态（ 1）系统安全状态：分配资源后，系统能按一 安全序列 推进（ 2）银行家算法 ：二维数组 A. 表示每个进程对每个资源的最大需求量B. 表示每个进程对每个资源已分配到的C. 表示每个进程对每个资源还需要的一维数组A.表示每类资源的可分配数 availableB. 表示每个资源当前可分配数（即加上某个进程运行完，释放后的资源数） workC. 表示每个进程能否获得足够资源而运行finish算法思路： P112-1147. 检测死锁：（ 1）资源分配图（2）死锁定理： S 为死锁的充分条件 :当且仅当 S 状态的资源分配图是 不可完全 简化的8. 解除死锁：（1）抢占资源（2）终止（撤销）

13、进程方法：A.终止所有进程B.逐个终止进程：付出代价最小的死锁解除算法 P117-118第四章 存储器管理均称为传统存储器管理方式，具有 2 个特点：一次性和驻留性 P153（一）1. 存储系统至少 3 级：最高层为 CPU 寄存器，内存，最底层为辅存。2. 可执行存储器：寄存器和内存 。3. 进程访问可执行存储器：使用一条 load 或 store 指令即可访问辅存：需通过 I/O 设备4. 程序的装入方式（ 1 ）绝对装入方式 ：单道环境 程序的相对地址（逻辑地址）与内存地址完全 相同（ 2） 静态可重定位装入方式 ：多道环境 在装入时对目标程序中指令和数据地 址进行修改，以后不再改变。（

14、3）动态运行时的装入方式 ：程序运行过程在内存的位置经常会改变 装入内 存，地址转换推迟到程序运行时才进行。A. 工作原理：增设一个 重定位寄存器，存放程序在内存中的起始地址-> 真正访问内存地址 =相对地址 +寄存器中的地址-> 程序移动时，只需修改寄存器中的起始地址B. 在“紧凑（拼接）”时，要用到。(二) 连续分配存储管理方式1. 单一连续分配 ：单道环境 内存分为系统区(多放在低址)和用户区2. 固定分区分配 ：多道环境 内存划分为若干个固定大小的区域，一个区域装入 一道作业(1) a.分区大小相等 b.分区大小不等( 2 )地址映射：采用静态重定位( 3)缺点：造成大量的

15、内部碎片( 4) 数据结构：分区使用表包括分区号、大小、起址、状态。3. 动态分区分配(可变分区分配) ：( 1 )分区分配：按需划分 分区回收：合并回收( 2) 数据结构：空闲分区表 包括分区号、大小、起址、状态(全都是未分配)空闲分区链 双向的( 3)分配： P128 下面回收： P1 29 注意不同合并方式会对空闲分区表的修改不同( 4)基于顺序搜索的动态分区分配算法A. 首次适应算法：每次分配从头顺序查找，找到大小可以满足为止特点：优先利用内存地址空闲区，保留了高址的大空闲区缺点：低址不断被划分，产生许多碎片；查找效率低对固定分区：整体分配，易形成内碎片对可变分区：按需划分，易形成外碎

16、片B. 循环首次适应算法：循环的，从上次找到的位置往下查找特点：使内存的空闲分区分布得更均匀缺点：缺乏大的空闲分区C.最佳适应算法：所有空闲分区从小到大形成空闲分区链缺点：留下许多碎片对固定分区：内碎片小对可变分区：易形成外碎片D. 最坏适应算法：所有空闲分区从大到小形成空闲分区链优点： 产生碎片的可能性最小 ；查找效率高对固定分区：内碎片大对可变分区：剩余分区可再次利用（5）基于索引搜索的动态分区分配算法A. 快速适应算法：相同容量的空闲分区形成一个空闲分区链设置索引表查找特点：不会对任何分区产生分割， 不会产生内存碎片优点：查找效率高在分配分区时，以进程为单位，一个分区只属于一个进程，或多

17、或少存在浪 费B. 伙伴系统：原理、分配、回收、计算伙伴地址P132C. 哈希算法：建立哈希函数，构造哈希表4. 动态重定位分区分配算法：与 3（3）基本相同，差别仅在于增加了紧凑的功 能（三）对换1. 对换：进程或程序和数据：内存 <-> 外存2. 对换的类型 ：（ 1 ）整体对换（进程对换） ：整个进程为单位对换（2）页面 /分段对换（部分对换）：以进程的一个页面或分段为单位对换目的：支持虚拟存储系统3. 磁盘空间分为文件区和对换区（对换空间）文件区：离散分配对换区：按需分配（分配算法上面 4 种都可以）、合并回收4. 进程的换进换出的选择标准 P137换出：换到 无阻塞进程为

18、止 换入：第一个换“就绪”且换出时间最久的进程，继续换到 无处于“就绪且换出”状态的进程为止（四）分页存储管理方式：提高内存利用率1. 程序分为若干固定大小的页面，内存同样称为物理块（页框）2. 页面大小应为 2 的幂，通常为 1KB-8KB3. 地址结构：页号 P+ 页内地址 W （一维的）若页面的大小为L,则逻辑地址LA=P*L+W4. 每个进程一张 页面映像表（页表） ：存放在内存里，实现从页号到物理块号的地址映射页表大小 = 表项数 *表项大小 P1395. 地址变换机构：实现从逻辑地址到物理地址的转换6. 页表寄存器：存放页表始址 + 页表长度进程未执行时，页表始址 + 页表长度放在

19、 本进程 PCB 中-> 执行时，装入页表 寄存器7. 查找过程（ 2 次访问内存）：页表寄存器 -> 页表（内存里） -> 得到内存物理 地址，到内存取指令8. 具有快表（联想寄存器） ：先查快表看能否命中，未能命中则 查完页表后还要 修改快表9. 查快表 t1, 查页表和取指令 t2:若同时查块表和页表：命中： t1+t2未命中： t2+t1（ 修改快表 ）+t2若命中率为 h, 可得有效访问内存的时间 :h*t1+（1-h）*（t2+t1）+t2（五）分段存储管理方式：满足用户编程和使用的要求1. 作业分为若干个大小不同的段2. 一个作业最多 64K 个段，每个段最大长

20、度为 64KB3. 地址结构：段号 + 段内地址（二维的）段号太大， 段表中找不到则表示 越界 ；段内地址太大， 超过段表中目的段的大 小，则表示 段内越界 。4. 每个进程一张段映射表（段表） ：存放在内存里，每个表项包含一个 段的起始 地址（基址） + 该段的长度5. 地址变换机构：段表寄存器，存放段表始址 + 段表长度6. 查找过程（ 2 次访问内存）：段表寄存器 -> 段表（内存里） -> 得到内存物理 地址，到内存取指令7. 具有联想寄存器的：与分页式相同8. 分页与分段的区别： P148（ 重）（六）段页式存储管理方式1. 程序分成若干段，每个段再分成若干页2. 地址结

21、构：段号 + 段内页号 + 页内地址（二维的）3. 需要段表寄存器、段表、页表：每个进程一张段表，段表包含页表始址 + 页表大小4. 查找过程（ 3 次访问内存）：段表寄存器 -> 找段表（内存里），得到该段对应 的页表起始地址 -> 找页表（内存里） ，得到该页的物里块号 -> 形成物理地址， 到内存取指令5. 具有联想寄存器的：与分页式相同第五章 虚拟储存器原理：局部性原理（时间局部性、空间局部性）（一）概述1.虚拟储存器：具有 请求调入 功能和置换功能，从逻辑上对内存容量扩充2.特征：多次性、对换性、虚拟性3. 实现虚拟储存器的基础：离散存放、多次装入（二）请求分页存储

22、管理方式1.页表增加 4 个字段：状态位（该页是否已调入内存） 、访问位（访问次数或多 久未访问）、修改位（有被修改的置换时要写回外存） 、外存地址2.缺页中断机构 ：指令执行期间，发现要访问的指令或数据不在内存，马上发出 中断这种属于陷进（软中断） ，之前打印机那些是硬中断3. 地址变换过程 P158（ 重） 注意最后必有“修改访问位和修改位”这一步骤4. 最小物理块数：进程能正常运行的最小物理块数5. 内存分配策略 ：（1）固定分配局部置换 固定分配：为每个进程分配固定数目的物理块，不再改变 局部置换：只能从分配给该进程的页面中选一页换出（ 2）可变分配全局置换（3）可变分配局部置换 一进

23、程运行时缺页率很低，可以减少分配给该进程的物理块数6. 物理块分配算法（1）平均分配算法：平均分配给各个进程（2）按比例分配算法：按进程大小3）考虑优先级的分配算法7. 页面调入策略（1）何时调入A. 预调页策略：将预计不久后会被访问的页面预先调入内存，可用于首次 调入时B. 请求调页策略：缺页请求时再调入，一次只调入一页（2）何处调入UNIX 方式：从未运行过的，从文件区调入置换在对换区的，从对换区调入8缺页率：访问页面失败的次数 F/访问页面总次数A（三）页面置换算法1. 最佳置换算法（无法实现的） ：换出未来最迟被访问的页面2. 先进先出置换算法： 可能产生 Belady 异常，即分配的

24、页面数越多，缺页率反 而越多原因：先进的一般都是经常被访问的3最近最久未使用置换算法（LRU）:需要移位寄存器或栈两个硬件之一的支持移位寄存器：每个在内存的页面配置一个R=Rn-1Rn-2.R1R0进程访问某物理块时，将相应的寄存器的 Rn-1 位置 1。每隔一 段时间寄存器右移一位。最小数值那个就是最近最久未使用的页面。栈：栈顶总是最近访问的页面号（命中时调到栈顶） ，栈低总是最久的（置换 时从栈底淘汰）4. 最少使用置换算法（ LFU） :即看访问次数最少的采用移位寄存器方式：每次访问某页，将该寄存器最高位置1，每隔一段时间右移一位。最小数值那个就是最少使用的页面。5. 简单的 Clock

25、 置换算法（最近未用算法 NRL ）：每页设置访问位 （A） ，将内存中所有页面构成循环队列。 某页被访问时， 访问位置 1置换时，若访问位为 0 则换出，为 1 则改为 0改进的 Clock 置换算法 ：多了修改位 （W） ，修改为为 1 表示修改过 第一步：优先置换“ A=0 ，W=0 ”的页面，不改变访问位 A 第二步：找“ A=0 ，W=1 ”的页面，同时将 A=1 的改为 A=0 第三步：重复第一步6. 页面缓冲算法（ PBA）：（1）影响页面换进换出效率的因素A. 页面置换算法 B.写回磁盘的频率 C.读入内存的频率（ 2）算法原理 :A. 空闲页面链表：用于分配给频繁缺页的进程、

26、一个 未被修改的页面（有 数据）要换出时，不换出，接到该链末尾B. 修改页面链表：一个 已修改的页面要换出时，不换出，接到该链末尾， 方便集中写回磁盘（四）抖动与工作集1. 工作集：某段时间内，进程实际所要访问页面的集合不同时间的工作集大小不同，所含的页面数也不同 P1712. 抖动（ 1）产生原因：进程太多，缺页频繁， CPU 效率急剧下降（进程处于“抖动” 状态）2）产生前提：采取可变分配 + 全局置换（3）预防方法：A.采取局部置换策略B. 把工作集算法融入到处理机调度中调入作业之前，检查每个进程在内存的驻留页面是否足够多。C. 利用“ L=S ”准则调节缺页率P172D. 选择暂停的进

27、程：挂起若干进程第六章（一） I/O 系统O系统的层次结构：从下往上：硬件-> 中断处理程序-> 设备驱动程序-> 设备 独立性软件 -> 用户层软件O 系统的上、下接口： I/O 系统接口、软件 / 硬件接口（下面就是硬件部分了）O 系统的分层：从下往上：中断处理程序 -> 设备驱动程序 -> 设备独立性软件O 系统接口：有 3 种（ 1 ）块设备接口A. 块设备：以数据块为单位（磁盘）特点：传输速率高；可寻址；磁盘设 备的 I/O 常采用 DMA 方式B. 块设备接口特征：隐藏了磁盘的二维结构（磁道号 +扇区）；将抽象的命 令映射为底层操作（ 2）流设备

28、接口A. 流设备：以字符为单位（键盘、打印机）特点：传输速率低；不可寻址； 流设备的 I/O 常采用中断驱动方式B. 程序用get和put操作，只能顺序存取C. 大多数流设备属于独占设备（互斥方式），要提供打开/关闭操作。（ 3）网络通信接口二）硬件部分O 设备的类型：存储设备和 I/O 设备、低速设备（键盘、鼠标）和中速设备（打 印机）和高速设备（磁盘、光盘）2. 设备控制器（控制一个或多个 I/O 设备）（1）三部分组成：A. 设备控制器与CPU的接口（并行）：数据总线 ->DR: 内存 <-> 设备->C/S: 状态：设备 ->CPU启动： CPU->

29、 设备地址总线：设备名 -> 译码电路（ I/O 逻辑） -> 接口控制总线：操作码 -> 译码电路 ->CRB. 设备控制器与设备的接口（串行）：数据线：设备 <->DR状态线：设备 ->C/S控制线： C/S-> 设备C. 译码电路（I/O逻辑）:实现对设备的控制上面 2 个译码功能 +并行-（分解） -><-（ 组装）- 串行（ 2） CPU 启动一个设备的过程：启动命令 -> 设备控制器地址（即要选哪个设备） -地址线->设备控制器->I/O 逻辑进行译码 -> 选中设备（ 3）设备 ->DR:

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

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

32、 传送必要的参数-> 启动 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.以数据块为单位、直接从设备到内存、在控制器的控制下不用经过 CPU 控制器：三部分组成： DMA 控制器与主机的接口、与设备的接口、 I/O 控 制逻辑含有4个寄存器：数据寄存器 DR、控制/状态寄存器CR、数据计