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

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

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

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

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

5、的同步（ 1）同步:即某件事要等待另一件事完成才可以开始2 2） 2 种相互制约关系：间接相互制约关系（进程互斥访问资源）、直接相互制约关系（进程合作）3 .临界资源、临界区（进入区、退出区、剩余区）4 .同步机制遵循的规则:空闲让进、忙则等待、有限等待、让权等待（请求资源失败应释放CPU）种信号量：互斥信号量（初值为1 ） 、资源信号量（初值可为n） 、同步信号量（初值为 0）P（ wait ）原语：减1 V（signal） 原语：加1（五）1 .进程的互斥和同步称为低级进程通信，还有基于共享数据结构的通信方式也是2 .进程通信方式（ 1）直接通信方式（基于共享存储区）申请一个缓冲区- 将进

6、程 A 发送区的内容复制给缓冲区- 将缓冲区挂到进程 B 的消息队列- 进程 B 将缓冲区复制到自己的接收区（ 2）管道通信方式（对管道的write 和 read ）管道是一个pipe 文件，作为一个中介（ 3）消息传递方式（封装）：直接和间接（有中间实体：邮箱）（六）进程和线程的区别重第三章1. 三大调度：高级调度（作业调度）：调度作业（外存- 内存） ，只用于多道批处理系统低级调度（进程调度）：调度进程（就绪- 获得 CPU）中级调度（内存调度）：挂起（内存- 外存- 重入内存）利用率：CPU 有效工作时间/（CPU 有效工作时间+CPU 空闲等待时间）（二）1 .作业：包含程序和数据，还

7、有作业说明书。批处理系统中，是以作业为基本单位从外存调入内存的。2 .作业控制块（JCB） :作业在系统中存在的标志。包含：作业标识、.P883 .作业进入系统时- “作业注册”程序为其建立作业控制块- 放到 作业后备队列（外存）- 调度作业进入内存4 .作业的4 种状态： 提交状态、后备状态、运行状态 （对应的进程有3 种状态） 、完成状态5 .作业调度的任务：（ 1）接纳多少个作业：取决于多道程序度（ 2）接纳哪些作业：取决于调度算法调度时机：内存中的进程数小于多道度6 .进程的响应时间（作业的周转时间）：完成时间-到达时间或 服务时间 + 等待时间平均周转时间：N 个的和除以N带权周转时

8、间：（服务时间+等待时间）/服务时间或 1+ 等待时间/服务时间平均带权周转时间：N 个的和除以N7 .调度算法（4 种都可用于作业调度或进程调度）（ 1）先来先服务（FCFS）只能非抢占式（ 2）短进程优先（SJF） ：有效降低作业的平均周转时间；对长作业不利（ 3）优先级调度算法（PSA）4）高响应比优先调度算法（HRRN ） :优先级随等待时间延长而增加优先权 =（服务时间+等待时间）/服务时间或 1+ 等待时间 /服务时间必须等某个进程完成时，才重新计算优先权，即运行某进程过程中有新进程到达也不会重新调度后面 3 个对于作业只能非抢占式；对于进程，可抢占式或非抢占式8 .题目未说明时，

9、默认是非抢占式。（三）1 .非抢占式：调度时机为（ 1 ）进程运行完毕（2） 进程 I/O 请求 （ 3）执行 Block原语抢占式：抢占原则（1 ）优先权（2）短进程优先（3）时间片2 .调度算法（ 1）轮转调度算法：基于时间片（ 2）优先级调度算法（ 3）多队列调度算法：多个就绪队列 ，不同队列采用不同的调度算法（ 4）多级反馈队列调度算法：对于长作业，往后时间片越长，得到的处理时间越长（ 5）最低松弛度优先算法：松弛度= 必须完成时间-需要服务时间（四）1 .可重用性资源（打印机）：请求资源- 获得资源- 释放资源可消耗性资源（通信中的消息）：进程运行期间动态创建和消耗的，不再返回可抢占

10、性资源（CPU、内存）不可抢占性资源（打印机）：可能引起死锁2 .引起死锁的3 个原因：（ 1）竞争不可抢占性资源（2 ）竞争可消耗性资源（3）进程推进顺序不当（不安全区 D）3 .产生死锁的必要条件：（ 1）互斥条件（2 ）请求和保持条件（3 ）不可抢占条件（4 ）循环等待条件（产生回路）4 .处理死锁的方法：（ 1）预防死锁（2 ）避免死锁（3）检测死锁（4）解除死锁5.预防死锁：破坏其中一个条件（ 1）互斥条件不能破坏还应保持（2）破坏请求和保持条件：A.一次性申请所需全部资源B.申请部分资源，用完释放，然后继续申请（资源静态分配）（ 3）破坏不可抢占条件：提出新的资源请求时，必须释放自

11、己已保持的所有资 源（好像被抢占了）（ 4） 破坏循环等待条件：每个进程按序号递增的顺序请求资源（资源有序分配）6 .避免死锁：防止系统进入不安全状态（ 1）系统安全状态：分配资源后，系统能按一安全序列 推进（ 2）银行家算法：二维数组A. 表示每个进程对每个资源的最大需求量B.表示每个进程对每个资源已分配到的C.表示每个进程对每个资源还需要的一维数组A.表示每类资源的可分配数availableB.表示每个资源当前可分配数（即加上某个进程运 行完，释放后的资源数）workC.表示每个进程能否获得足够资源而运行finish算法思路：P112-1147 .检测死锁：（ 1）资源分配图（ 2）死锁定

12、理：S 为死锁的充分条件:当且仅当S 状态的资源分配图是不可完全简化的8 .解除死锁：（ 1）抢占资源（ 2）终止（撤销）进程方法：A.终止所有进程B.逐个终止进程：付出代价最小的死锁解除算法 P117-118第四章 存储器管理均称为传统存储器管理方式，具有2 个特点：一次性和驻留性P153（一）1 .存储系统至少3 级：最高层为CPU 寄存器，内存，最底层为辅存。2 .可执行存储器：寄存器和内存。3 .进程访问可执行存储器：使用一条load 或 store 指令即可访问辅存：需通过I/O 设备4 .程序的装入方式（ 1） 绝对装入方式：单道环境程序的相对地址（逻辑地址）与内存地址完全相同（

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

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

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

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

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

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

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

20、）：段表寄存器- 找段表（内存里），得到该段对应的页表起始地址- 找页表（内存里），得到该页的物里块号- 形成物理地址，到内存取指令5 .具有联想寄存器的：与分页式相同第五章 虚拟储存器原理：局部性原理（时间局部性、空间局部性）（一）概述1 .虚拟储存器：具有请求调入 功能和 置换 功能，从逻辑上对内存容量扩充2 .特征：多次性、对换性、虚拟性3 .实现虚拟储存器的基础：离散存放、多次装入（二）请求分页存储管理方式1 .页表增加4 个字段：状态位（该页是否已调入内存）、访问位（访问次数或多久未访问）、修改位（有被修改的置换时要写回外存）、 外存地址2 .缺页中断机构：指令执行期间，发现要访问的

21、指令或数据不在内存，马上发出中断这种属于陷进（软中断），之前打印机那些是硬中断3 .地址变换过程P158（重）注意最后必有“修改访问位和修改位”这一步骤4 .最小物理块数：进程能正常运行的最小物理块数5 .内存分配策略：（ 1）固定分配局部置换固定分配：为每个进程分配固定数目的物理块，不再改变局部置换：只能从分配给该进程的页面中选一页换出（ 2）可变分配全局置换（ 3）可变分配局部置换一进程运行时缺页率很低，可以减少分配给该进程的物理块数6.物理块分配算法（ 1）平均分配算法：平均分配给各个进程（ 2）按比例分配算法：按进程大小3）考虑优先级的分配算法 7.页面调入策略（ 1）何时调入A.预调

22、页策略：将预计不久后会被访问的页面预先调入内存，可用于首次 调入时B.请求调页策略：缺页请求时再调入，一次只调入一页（ 2）何处调入UNIX 方式：从未运行过的，从文件区调入置换在对换区的，从对换区调入8.缺页率：访问页面失败的次数 F/访问页面总次数A（三）页面置换算法1 .最佳置换算法（无法实现的）：换出未来最迟被访问的页面2 .先进先出置换算法：可能产生Belady 异常 ，即分配的页面数越多，缺页率反而越多原因：先进的一般都是经常被访问的3 .最近最久未使用置换算法（LRU） :需要移位寄存器或栈两个硬件之一的支持移位寄存器：每个在内存的页面配置一个R=Rn-1Rn-2.R1R0进程访

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

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

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

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

27、（磁盘、光盘）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）设备-DR: 数据准备；DR- 内存

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

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