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

第一章（一）1.未配置操作系统的计算机系统（1）人工操作方式（人机矛盾）（2）脱机输入/输出方式2.单道批处理系统 内存里一道作业3.多道批处理系统 优点：（1）资源利用率高（CPU、内存、I/0设备） （2）系统吞吐量大 缺点：（1）平均周转时间长 （2）无交互能力3.分时系统（解决人机交互） 及时接收：多个用户（配置多路卡）、为每个用户配置一个缓冲区 及时处理：（1）作业直接进入内存 （2）采用轮转运行方式（时间片） 响应时间=时间片×终端数4. 实时系统周期性实时任务和非. 硬实时任务和软.（二）操作系统的基本特性1. 并发（进程才能） 实现并发执行的前提是：多道程序环境2. 共享 互斥共享方式、同时访问方式3.虚拟（1）时空复用技术（虚拟处理机技术、虚拟设备技术） （2）空分复用技术（虚拟磁盘技术、虚拟储存器技术）4. 异步5. 操作系统两个最基本的特征：并发和共享第二章（一）1.前趋图（有向无环图）：描述进程之间执行的先后顺序2.顺序执行：顺序性、封闭性、可再现性 并发执行：间断性、失去封闭性、不可再现性（及时间有关的错误） Bernstein条件（二）1.进程实体：包括程序段、数据的和PCB2.进程的特征：动态性、并发性、独立性、异步性（按各自速度推进）3.进程的三种基本状态：就绪、执行、阻塞 相互之间的转换 注意：执行-（时间片完）->就绪4.进程的创建（状态）：申请空白PCB->分配资源->挂到就绪队列 进程的终止（状态）：保存记录->PCB返还系统5.进程的挂起（不再被调度不在内存了、suspend原语） 活动就绪-（挂起）->静止就绪 活动阻塞-（挂起）->静止阻塞 执行 -（挂起）->静止就绪 进程的激活（active原语） 静止就绪-（激活）->活动就绪 静止阻塞-（激活）->活动阻塞6.PCB中的信息：P41 PCB组织方式：线性方式、链接方式、索引方式(三)1.OS内核：常驻内存 OS状态:系统态（管态、内核态） 用户态（目态）2.父进程创建子进程：3种返回值 进程图:描述进程家族关系的一棵树3.进程的创建（Creat原语） 引起进程创建的事件：用户登录、作业调度、提供服务（创建打印进程）、应用请求（用户创建） 创建过程：申请空白PCB->分配资源（从系统或父进程）->初始化进程控制块（初始化内容见P45）->插入就绪队列4.进程的终止 引起进程终止的事件：正常结束、异常结束、外界干预 终止过程：P465.进程的阻塞（block原语） 引起事件：请求共享资源失败、等待某种操作的完成（I/O操作）、新数据未到达（合作进程中）、等待新任务的到来（发送进程，没有信息可发送） 阻塞过程：状态：执行变为阻塞->PCB挂到阻塞队列->调度其他进程6.进程的唤醒（wakeup原语） 唤醒过程：移除阻塞队列->挂到就绪队列（四）1.进程的同步（1）同步:即某件事要等待另一件事完成才可以开始（2）2种相互制约关系：间接相互制约关系（进程互斥访问资源）、直接相互制约关系（进程合作）2.临界资源、临界区（进入区、退出区、剩余区）3.同步机制遵循的规则:空闲让进、忙则等待、有限等待、让权等待（请求资源失败应释放CPU）4.3种信号量：互斥信号量（初值为1）、资源信号量（初值可为n）、同步信号量(初值为0) P（wait）原语：减1 V(signal)原语：加1（五）1.进程的互斥和同步称为低级进程通信，还有基于共享数据结构的通信方式也是2.进程通信方式（1）直接通信方式（基于共享存储区） 申请一个缓冲区->将进程A发送区的内容复制给缓冲区->将缓冲区挂到进程B的消息队列->进程B将缓冲区复制到自己的接收区（2）管道通信方式（对管道的write和read） 管道是一个pipe文件，作为一个中介（3） 消息传递方式（封装）：直接和间接（有中间实体：邮箱）（六）进程和线程的区别 重第三章（一）1.三大调度：高级调度（作业调度）：调度作业（外存->内存），只用于多道批处理系统 低级调度（进程调度）：调度进程（就绪->获得CPU） 中级调度（内存调度）：挂起（内存->外存->重入内存）2.CPU利用率：CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)（二）1.作业：包含程序和数据，还有作业说明书。 批处理系统中，是以作业为基本单位从外存调入内存的。2.作业控制块（JCB）:作业在系统中存在的标志。包含：作业标识、.P883.作业进入系统时->“作业注册”程序为其建立作业控制块->放到作业后备队列（外存）->调度作业进入内存4.作业的4种状态：提交状态、后备状态、运行状态（对应的进程有3种状态）、完成状态5.作业调度的任务：（1）接纳多少个作业：取决于多道程序度 （2）接纳哪些作业：取决于调度算法调度时机：内存中的进程数小于多道度6.进程的响应时间（作业的周转时间）：完成时间-到达时间 或 服务时间+等待时间 平均周转时间：N个的和除以N 带权周转时间：（服务时间+等待时间）/服务时间 或 1+等待时间/服务时间 平均带权周转时间：N个的和除以N7.调度算法(4种都可用于作业调度或进程调度)（1）先来先服务（FCFS） 只能非抢占式（2）短进程优先（SJF）：有效降低作业的平均周转时间；对长作业不利（3）优先级调度算法(PSA)（4）高响应比优先调度算法（HRRN）:优先级随等待时间延长而增加 优先权=（服务时间+等待时间）/服务时间 或 1+等待时间/服务时间 必须等某个进程完成时，才重新计算优先权，即运行某进程过程中有新进程到达也不会重新调度后面3个对于作业只能非抢占式；对于进程，可抢占式或非抢占式8.题目未说明时，默认是非抢占式。（三）1.非抢占式：调度时机为（1）进程运行完毕（2）进程I/O请求（3）执行Block原语 抢占式：抢占原则（1）优先权（2）短进程优先（3）时间片2.调度算法（1）轮转调度算法：基于时间片（2）优先级调度算法（3）多队列调度算法：多个就绪队列，不同队列采用不同的调度算法（4）多级反馈队列调度算法：对于长作业，往后时间片越长，得到的处理时间越长（5）最低松弛度优先算法：松弛度=必须完成时间-需要服务时间（四）1.可重用性资源（打印机）：请求资源->获得资源->释放资源 可消耗性资源（通信中的消息）：进程运行期间动态创建和消耗的，不再返回 可抢占性资源（CPU、内存）不可抢占性资源（打印机）：可能引起死锁2.引起死锁的3个原因：（1）竞争不可抢占性资源（2）竞争可消耗性资源（3）进程推进顺序不当（不安全区D）3.产生死锁的必要条件：（1）互斥条件（2）请求和保持条件（3）不可抢占条件（4）循环等待条件（产生回路）4.处理死锁的方法：（1）预防死锁（2）避免死锁（3）检测死锁（4）解除死锁5.预防死锁：破坏其中一个条件（1）互斥条件不能破坏还应保持（2）破坏请求和保持条件：A.一次性申请所需全部资源 B.申请部分资源，用完释放，然后继续申请(资源静态分配)（3）破坏不可抢占条件：提出新的资源请求时，必须释放自己已保持的所有资源（好像被抢占了）（4）破坏循环等待条件：每个进程按序号递增的顺序请求资源（资源有序分配）6.避免死锁：防止系统进入不安全状态（1）系统安全状态：分配资源后，系统能按一安全序列推进（2）银行家算法：二维数组 A.表示每个进程对每个资源的最大需求量 B.表示每个进程对每个资源已分配到的 C.表示每个进程对每个资源还需要的 一维数组 A.表示每类资源的可分配数 available B.表示每个资源当前可分配数（即加上某个进程运行完，释放后的资源数）work C.表示每个进程能否获得足够资源而运行 finish 算法思路：P112-1147.检测死锁：（1）资源分配图（2）死锁定理：S为死锁的充分条件:当且仅当S状态的资源分配图是不可完全简化的8.解除死锁：（1）抢占资源（2）终止（撤销）进程 方法：A.终止所有进程 B.逐个终止进程：付出代价最小的死锁解除算法P117-118第四章 存储器管理均称为传统存储器管理方式，具有2个特点：一次性和驻留性 P153（一）1.存储系统至少3级：最高层为CPU寄存器，内存，最底层为辅存。2.可执行存储器：寄存器和内存。3.进程访问可执行存储器：使用一条load或store指令即可 访问辅存：需通过I/O设备4.程序的装入方式（1）绝对装入方式：单道环境 程序的相对地址（逻辑地址）及内存地址完全相同（2）静态可重定位装入方式：多道环境 在装入时对目标程序中指令和数据地址进行修改，以后不再改变。（3）动态运行时的装入方式：程序运行过程在内存的位置经常会改变 装入内存，地址转换推迟到程序运行时才进行。 A.工作原理：增设一个重定位寄存器，存放程序在内存中的起始地址->真正访问内存地址=相对地址+寄存器中的地址 ->程序移动时，只需修改寄存器中的起始地址 B.在“紧凑（拼接）”时，要用到。（二）连续分配存储管理方式1.单一连续分配：单道环境 内存分为系统区（多放在低址）和用户区2.固定分区分配：多道环境 内存划分为若干个固定大小的区域，一个区域装入一道作业（1）a.分区大小相等 b.分区大小不等（2）地址映射：采用静态重定位（3）缺点：造成大量的内部碎片（4）数据结构：分区使用表 包括分区号、大小、起址、状态。3.动态分区分配（可变分区分配）：（1）分区分配：按需划分 分区回收：合并回收（2）数据结构：空闲分区表 包括分区号、大小、起址、状态（全都是未分配）空闲分区链 双向的（3）分配：P128 下面 回收：P129 注意不同合并方式会对空闲分区表的修改不同（4）基于顺序搜索的动态分区分配算法 A.首次适应算法：每次分配从头顺序查找，找到大小可以满足为止 特点：优先利用内存地址空闲区，保留了高址的大空闲区 缺点：低址不断被划分，产生许多碎片；查找效率低 对固定分区：整体分配，易形成内碎片 对可变分区：按需划分，易形成外碎片 B.循环首次适应算法：循环的，从上次找到的位置往下查找 特点：使内存的空闲分区分布得更均匀 缺点：缺乏大的空闲分区 C.最佳适应算法：所有空闲分区从小到大形成空闲分区链 缺点：留下许多碎片 对固定分区：内碎片小 对可变分区：易形成外碎片 D.最坏适应算法：所有空闲分区从大到小形成空闲分区链 优点：产生碎片的可能性最小；查找效率高 对固定分区：内碎片大 对可变分区：剩余分区可再次利用（5）基于索引搜索的动态分区分配算法 A.快速适应算法：相同容量的空闲分区形成一个空闲分区链 设置索引表查找 特点：不会对任何分区产生分割，不会产生内存碎片 优点：查找效率高在分配分区时，以进程为单位，一个分区只属于一个进程，或多或少存在浪费 B.伙伴系统：原理、分配、回收、计算伙伴地址 P132 C.哈希算法：建立哈希函数，构造哈希表4.动态重定位分区分配算法：及3（3）基本相同，差别仅在于增加了紧凑的功能（三）对换1.对换：进程或程序和数据：内存<->外存2.对换的类型：（1）整体对换（进程对换）：整个进程为单位对换（2）页面/分段对换（部分对换）：以进程的一个页面或分段为单位对换 目的：支持虚拟存储系统3.磁盘空间分为文件区和对换区（对换空间） 文件区：离散分配 对换区：按需分配（分配算法上面4种都可以）、合并回收4. 进程的换进换出的选择标准 P137 换出：换到无阻塞进程为止 换入：第一个换“就绪”且换出时间最久的进程，继续换到无处于“就绪且换出”状态的进程为止（四）分页存储管理方式：提高内存利用率1.程序分为若干固定大小的页面，内存同样称为物理块（页框）2.页面大小应为2的幂，通常为1KB-8KB3.地址结构：页号P+页内地址W（一维的） 若页面的大小为L,则逻辑地址LA=P*L+W4.每个进程一张页面映像表（页表）：存放在内存里，实现从页号到物理块号的地址映射 页表大小=表项数*表项大小 P1395.地址变换机构：实现从逻辑地址到物理地址的转换6.页表寄存器：存放页表始址+页表长度 进程未执行时，页表始址+页表长度放在本进程PCB中->执行时，装入页表寄存器7.查找过程（2次访问内存）：页表寄存器->页表（内存里）->得到内存物理地址，到内存取指令8.具有快表（联想寄存器）：先查快表看能否命中，未能命中则查完页表后还要修改快表9.查快表t1,查页表和取指令t2: 若同时查块表和页表：命中：t1+t2 未命中：t2+t1(修改快表)+t2 若命中率为h,可得有效访问内存的时间:h*t1+(1-h)*(t2+t1)+t2（五）分段存储管理方式：满足用户编程和使用的要求1.作业分为若干个大小不同的段2.一个作业最多64K个段，每个段最大长度为64KB3.地址结构：段号+段内地址（二维的） 段号太大，段表中找不到则表示越界；段内地址太大，超过段表中目的段的大小，则表示段内越界。4.每个进程一张段映射表（段表）：存放在内存里，每个表项包含一个段的起始地址（基址）+该段的长度5.地址变换机构：段表寄存器，存放段表始址+段表长度6.查找过程（2次访问内存）：段表寄存器->段表（内存里）->得到内存物理地址，到内存取指令7.具有联想寄存器的：及分页式相同8.分页及分段的区别：P148(重)（六）段页式存储管理方式1.程序分成若干段，每个段再分成若干页2.地址结构：段号+段内页号+页内地址（二维的）3.需要段表寄存器、段表、页表：每个进程一张段表，段表包含页表始址+页表大小4.查找过程（3次访问内存）：段表寄存器->找段表（内存里），得到该段对应的页表起始地址->找页表（内存里），得到该页的物里块号->形成物理地址，到内存取指令5.具有联想寄存器的：及分页式相同第五章 虚拟储存器原理：局部性原理（时间局部性、空间局部性）（一）概述1.虚拟储存器：具有请求调入功能和置换功能，从逻辑上对内存容量扩充2.特征：多次性、对换性、虚拟性3.实现虚拟储存器的基础：离散存放、多次装入（二）请求分页存储管理方式1.页表增加4个字段：状态位（该页是否已调入内存）、访问位（访问次数或多久未访问）、 修改位（有被修改的置换时要写回外存）、外存地址2.缺页中断机构：指令执行期间，发现要访问的指令或数据不在内存，马上发出中断 这种属于陷进（软中断），之前打印机那些是硬中断3.地址变换过程 P158(重) 注意最后必有“修改访问位和修改位”这一步骤4.最小物理块数：进程能正常运行的最小物理块数5.内存分配策略：（1）固定分配局部置换 固定分配：为每个进程分配固定数目的物理块，不再改变 局部置换：只能从分配给该进程的页面中选一页换出（2）可变分配全局置换（3）可变分配局部置换 一进程运行时缺页率很低，可以减少分配给该进程的物理块数6.物理块分配算法（1）平均分配算法：平均分配给各个进程（2）按比例分配算法：按进程大小（3）考虑优先级的分配算法7.页面调入策略（1）何时调入 A.预调页策略：将预计不久后会被访问的页面预先调入内存，可用于首次调入时 B.请求调页策略：缺页请求时再调入，一次只调入一页（2）何处调入 UNIX方式：从未运行过的，从文件区调入 置换在对换区的，从对换区调入8.缺页率：访问页面失败的次数F/访问页面总次数A（三）页面置换算法1.最佳置换算法（无法实现的）：换出未来最迟被访问的页面2.先进先出置换算法：可能产生Belady异常，即分配的页面数越多，缺页率反而越多 原因：先进的一般都是经常被访问的3.最近最久未使用置换算法（LRU）:需要移位寄存器或栈两个硬件之一的支持 移位寄存器：每个在内存的页面配置一个 R=Rn-1Rn-2.R1R0 进程访问某物理块时，将相应的寄存器的Rn-1位置1。每隔一段时间寄存器右移一位。 最小数值那个就是最近最久未使用的页面。 栈：栈顶总是最近访问的页面号（命中时调到栈顶），栈低总是最久的（置换时从栈底淘汰）4.最少使用置换算法（LFU）:即看访问次数最少的 采用移位寄存器方式：每次访问某页，将该寄存器最高位置1，每隔一段时间右移一位。 最小数值那个就是最少使用的页面。5.简单的Clock置换算法（最近未用算法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.空闲页面链表：用于分配给频繁缺页的进程、一个未被修改的页面（有数据）要换出时，不换出，接到该链末尾 B.修改页面链表：一个已修改的页面要换出时，不换出，接到该链末尾，方便集中写回磁盘（四）抖动及工作集1.工作集：某段时间内，进程实际所要访问页面的集合 不同时间的工作集大小不同，所含的页面数也不同 P1712.抖动（1）产生原因：进程太多，缺页频繁，CPU效率急剧下降（进程处于“抖动”状态）（2）产生前提：采取可变分配+全局置换（3）预防方法：A.采取局部置换策略 B.把工作集算法融入到处理机调度中 调入作业之前，检查每个进程在内存的驻留页面是否足够多。 C.利用“L=S”准则调节缺页率 P172 D.选择暂停的进程：挂起若干进程第六章（一）I/O系统1.I/O系统的层次结构：从下往上：硬件->中断处理程序->设备驱动程序->设备独立性软件->用户层软件2.I/O系统的上、下接口：I/O系统接口、软件/硬件接口（下面就是硬件部分了）3.I/O系统的分层：从下往上：中断处理程序->设备驱动程序->设备独立性软件4.I/O系统接口：有3种（1）块设备接口 A.块设备：以数据块为单位（磁盘）特点：传输速率高；可寻址；磁盘设备的I/O常采用DMA方式 B.块设备接口特征：隐藏了磁盘的二维结构（磁道号+扇区）；将抽象的命令映射为底层操作（2）流设备接口 A.流设备：以字符为单位（键盘、打印机） 特点：传输速率低；不可寻址；流设备的I/O常采用中断驱动方式 B.程序用get和put操作，只能顺序存取 C.大多数流设备属于独占设备（互斥方式），要提供打开/关闭操作。（3）网络通信接口（二）硬件部分1.I/O设备的类型：存储设备和I/O设备、低速设备（键盘、鼠标）和中速设备（打印机）和高速设备（磁盘、光盘）2.设备控制器（控制一个或多个I/O设备）（1）三部分组成： A.设备控制器及CPU的接口（并行）： 数据总线->DR:内存<->设备 ->C/S:状态：设备->CPU 启动：CPU->设备 地址总线：设备名->译码电路（I/O逻辑）->接口 控制总线：操作码->译码电路->CR B.设备控制器及设备的接口（串行）： 数据线：设备<->DR 状态线：设备->C/S 控制线：C/S->设备 C.译码电路（I/O逻辑）：实现对设备的控制 上面2个译码功能+并行-（分解）-><-(组装)-串行（2）CPU启动一个设备的过程： 启动命令->设备控制器 地址（即要选哪个设备）-地址线->设备控制器->I/O逻辑进行译码->选中设备（3）设备->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.字节多路通道：每个字通道连接一个设备，按时间片轮转共享主通道 适合低速设备 B.数组选择通道：每次只允许一个设备传输数据 C.数组多路通道（三）设备驱动程序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 B.DMA控制器：三部分组成：DMA控制器及主机的接口、及设备的接口、I/O控制逻辑 含有4个寄存器：数据寄存器DR、控制/状态寄存器CR、数据计数器DC、内存地址寄存器MAR C.工作过程： CPU要读磁盘->发命令给磁盘控制器->设置CR、DC、MAR,磁盘源地址送至DMA控制器的I/O控制逻辑->启动DMA控制器，进行数据传送->读一个字节送至DR后，挪用一个存储器周期，送至内存，MAR+1，DC-1->传送完，DMA控制器发中断请求->CPU处理中断->以后调度到进程时再取数据（4）I/O通道控制方式：以一组数据块为单位 A.过程：CPU发I/O指令（包含通道程序的首址和访问的I/O设备）->通道->内存中取对应的通道程序并执行->完成后，向CPU发中断信号 B.通道程序由通道指令（通道命令）构成，包含操作码（读还是写）、内存地址、计数、记录结束标志R(R=1结束)、通道程序结束位P(P=1结束)（四）及设备无关的I/O软件1.增加该类软件，以实现设备独立性（设备无关性），要引入逻辑设备名2.及设备无关的I/O软件可以实现I/O重定向（用于I/O操作的设备可以更换，而不必改变应用程序）3.系统只识别物理设备名，要转换4.设备分配（1）数据结构 A.设备控制表DCT:每个设备一张 记录该设备相关内容 B.控制器控制表COCT:每个控制器一张 C.通道控制表THCT:每个一张 D.系统设备表SDT:含系统里所有设备(含DCT)（2）设备分配算法 A.先来先服务 B.优先级高者优先（3）设备分配中的安全性 A.安全分配方式：进程获得设备后阻塞，不得再申请设备。破坏了“请求及保存”条件，不会发生死锁 B.不安全分配方式：获得后进程还继续运行5.独占设备的分配过程：进程使用逻辑设备名请求I/O->系统在SDT里找第一个该类设备的DCT(若忙找下一个)-> ->计算本次分配安全性:不安全则将PCB插入DCT里的等待队列，安全则分配->由DCT可以 找到COCT，得知控制器是否空闲，若忙，挂入控制器的等待队列，否则分配控制器-> 由COCT可以找到CHCT,得知通道是否空闲，同上->分配成功6.逻辑设备名到物理设备名的映射：（1）需要一张逻辑设备表LUT：含逻辑设备名、物理设备名、设备驱动程序入口地址 每次为进程分配设备，就填写一个表项,下次时直接查找LUT（2）整个系统一张LUT:只能单用户 每个用户一张LUT:实现多用户（五）往后内容看书第 23 页