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

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

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

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

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

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

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

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

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

9、抢占式；对于进程，可抢占式或非抢占式8.题目未说明时，默认是非抢占式。（三）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个特点：一次性和驻留性 P1531存储系统至少3级：最高层为CPU寄存器，内存，最底层为辅存 2可执行存储器：寄存器和内存。3. 进程访问可执行存储器：使用一条load或store指令即可访问辅存：需通过I/O设备4. 程序的装入方式(1)绝对装入方式：单道环境 程序的相对地址(逻辑地址)与内存地址完全相同（2）静态可重定位装入方式：多道

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

14、：采用静态重定位（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,查页表和取指令t2:若同时查块表和页表：命中：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=R n-1R n-2. .R1R0进程访问某物理块时，将相

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

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

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

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

28、串行（2）CPU启动一个设备的过程：启动命令-> 设备控制器地址（即要选哪个设备）-地址线-> 设备控制器->1/0 逻辑进行译码-> 选中设备（3）设备->DR:数据准备；DR->内存：数据传送（4）设备控制器的功能：A. 接收和识别命令B. 数据交换C. 标识和报告设备的状态D. 地址识别（设备控制器可连接多个设备、其里面也有很大寄存器，都需 要地址）E. 数据缓冲区F差错控制3.I/0通道（特殊处理机）（1） 在CPU与设备控制器之间目的：建立独立的I/O操作（2）过程：CPU发I/O指令-> 通道-> 内存中取对应的通道程序并执行->

29、; 完 成后，向CPU发中断信号（3）通道与CPU共享内存（其通道程序放在内存）（4）通道的类型：A. 字节多路通道：每个字通道连接一个设备，按时间片轮转共享主通道 适合低速设备B. 数组选择通道：每次只允许一个设备传输数据C. 数组多路通道（二）设备驱动程序1设备驱动程序的功能：A. 将命令中的抽象要求转换为与设备相关的底层操作B. 检查I/O请求的合法性，设置设备的工作方式C. 启动I/O设备D. 及时响应设备控制器发来的中断请求，调用相应的中断处理程序2. 设备驱动程序的特点：A. 用汇编语言编写B. 允许可重入3. 设备处理方式：A. 每类设备一个进程来控制B. 整个系统一个进程或一个

30、输入一个输出共 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. 以数据块为单位、直接从设备到内存、在控制器的控制下不用经过CPUB. DMA控制器：三部分组成：DMA控制器与主机的接口、与设备的接口、 I/O控制逻辑含有4个寄存器：数据寄存器 DR、控制/状态寄存器CR、数据计数器 DC、内存地址