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

《大学操作系统课本：操作系统知识点.docx》由会员分享，可在线阅读，更多相关《大学操作系统课本：操作系统知识点.docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、、虚拟设备技术 2空分复用技术虚拟磁盘技术、虚拟储存器技术4. 异步5. 操作系统两个最根本的特征：并发和共享第二章一1.前趋图有向无环图：描述进程之间执行的先后顺序2.顺序执行：顺序性、封闭性、可再现性 并发执行：间断性、失去封闭性、不可再现性与时间有关的错误 Bernstein条件二1.进程实体：包括程序段、数据的和PCB2.进程的特征：动态性、并发性、独立性、异步性按各自速度推进3.进程的三种根本状态：就绪、执行、阻塞 相互之间的转换 注意：执行-时间片完-就绪4.进程的创立状态：申请空白PCB-分配资源-挂到就绪队列 进程的终止状态：保存记录-PCB返还系统5.进程的挂起不再被调度不在

3、内存了、suspend原语 活动就绪-挂起-静止就绪 活动阻塞-挂起-静止阻塞 执行 -挂起-静止就绪 进程的激活active原语 静止就绪-激活-活动就绪 静止阻塞-激活-活动阻塞6.PCB中的信息：P41 PCB组织方式：线性方式、链接方式、索引方式(三)1.OS内核：常驻内存 OS状态:系统态管态、内核态 用户态目态2.父进程创立子进程：3种返回值 进程图:描述进程家族关系的一棵树3.进程的创立Creat原语 引起进程创立的事件：用户登录、作业调度、提供效劳创立打印进程、应用请求用户创立 创立过程：申请空白PCB-分配资源从系统或父进程-初始化进程控制块初始化内容见P45-插入就绪队列4

4、.进程的终止 引起进程终止的事件：正常结束、异常结束、外界干预 终止过程：P465.进程的阻塞block原语 引起事件：请求共享资源失败、等待某种操作的完成I/O操作、新数据未到达合作进程中、等待新任务的到来发送进程，没有信息可发送 阻塞过程：状态：执行变为阻塞-PCB挂到阻塞队列-调度其他进程6.进程的唤醒wakeup原语 唤醒过程：移除阻塞队列-挂到就绪队列四1.进程的同步1同步:即某件事要等待另一件事完成才可以开始22种相互制约关系：间接相互制约关系进程互斥访问资源、直接相互制约关系进程合作2.临界资源、临界区进入区、退出区、剩余区3.同步机制遵循的规那么:空闲让进、忙那么等待、有限等待

5、、让权等待请求资源失败应释放CPU4.3种信号量：互斥信号量初值为1、资源信号量初值可为n、同步信号量(初值为0) Pwait原语：减1 V(signal)原语：加1五1.进程的互斥和同步称为低级进程通信，还有基于共享数据结构的通信方式也是2.进程通信方式1直接通信方式基于共享存储区 申请一个缓冲区-将进程A发送区的内容复制给缓冲区-将缓冲区挂到进程B的消息队列-进程B将缓冲区复制到自己的接收区2管道通信方式对管道的write和read 管道是一个pipe文件，作为一个中介（3） 消息传递方式封装：直接和间接有中间实体：邮箱六进程和线程的区别 重第三章一1.三大调度：高级调度作业调度：调度作业

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

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

8、，即运行某进程过程中有新进程到达也不会重新调度后面3个对于作业只能非抢占式；对于进程，可抢占式或非抢占式8.题目未说明时，默认是非抢占式。三1.非抢占式：调度时机为1进程运行完毕2进程I/O请求3执行Block原语 抢占式：抢占原那么1优先权2短进程优先3时间片2.调度算法1轮转调度算法：基于时间片2优先级调度算法3多队列调度算法：多个就绪队列，不同队列采用不同的调度算法4多级反应队列调度算法：对于长作业，往后时间片越长，得到的处理时间越长5最低松弛度优先算法：松弛度=必须完成时间-需要效劳时间四1.可重用性资源打印机：请求资源-获得资源-释放资源 可消耗性资源通信中的消息：进程运行期间动态创

9、立和消耗的，不再返回 可抢占性资源CPU、内存 不可抢占性资源打印机：可能引起死锁2.引起死锁的3个原因：1竞争不可抢占性资源2竞争可消耗性资源3进程推进顺序不当不平安区D3.产生死锁的必要条件：1互斥条件2请求和保持条件3不可抢占条件4循环等待条件产生回路4.处理死锁的方法：1预防死锁2防止死锁3检测死锁4解除死锁5.预防死锁：破坏其中一个条件1互斥条件不能破坏还应保持2破坏请求和保持条件：A.一次性申请所需全部资源 B.申请局部资源，用完释放，然后继续申请(资源静态分配)3破坏不可抢占条件：提出新的资源请求时，必须释放自己已保持的所有资源好似被抢占了4破坏循环等待条件：每个进程按序号递增的

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

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

12、地址转换推迟到程序运行时才进行。 A.工作原理：增设一个重定位存放器，存放程序在内存中的起始地址-真正访问内存地址=相对地址+存放器中的地址 -程序移动时，只需修改存放器中的起始地址 B.在“紧凑拼接时，要用到。二连续分配存储管理方式1.单一连续分配：单道环境 内存分为系统区多放在低址和用户区2.固定分区分配：多道环境 内存划分为假设干个固定大小的区域，一个区域装入一道作业1a.分区大小相等 b.分区大小不等2地址映射：采用静态重定位3缺点：造成大量的内部碎片4数据结构：分区使用表 包括分区号、大小、起址、状态。3.动态分区分配可变分区分配：1分区分配：按需划分 分区回收：合并回收2数据结构：

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

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

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

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

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

18、分页式相同8.分页与分段的区别：P148(重)六段页式存储管理方式1.程序分成假设干段，每个段再分成假设干页2.地址结构：段号+段内页号+页内地址二维的3.需要段表存放器、段表、页表： 每个进程一张段表，段表包含页表始址+页表大小4.查找过程3次访问内存：段表存放器-找段表内存里，得到该段对应的页表起始地址-找页表内存里，得到该页的物里块号-形成物理地址，到内存取指令5.具有联想存放器的：与分页式相同第五章 虚拟储存器原理：局部性原理时间局部性、空间局部性一概述1.虚拟储存器：具有请求调入功能和置换功能，从逻辑上对内存容量扩充2.特征：屡次性、对换性、虚拟性3.实现虚拟储存器的根底：离散存放、

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

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

21、未使用置换算法LRU:需要移位存放器或栈两个硬件之一的支持 移位存放器：每个在内存的页面配置一个 R=Rn-1Rn-2.R1R0 进程访问某物理块时，将相应的存放器的Rn-1位置1。每隔一段时间存放器右移一位。 最小数值那个就是最近最久未使用的页面。 栈：栈顶总是最近访问的页面号命中时调到栈顶，栈低总是最久的置换时从栈底淘汰4.最少使用置换算法LFU:即看访问次数最少的 采用移位存放器方式：每次访问某页，将该存放器最高位置1，每隔一段时间右移一位。 最小数值那个就是最少使用的页面。5.简单的Clock置换算法最近未用算法NRL： 每页设置访问位(A)，将内存中所有页面构成循环队列。 某页被访问

22、时，访问位置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.工作集：某段

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

24、/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设备、低速设备键盘、鼠标和中速设备打印机和

25、高速设备磁盘、光盘2.设备控制器控制一个或多个I/O设备1三局部组成： A.设备控制器与CPU的接口并行： 数据总线-DR:内存设备 -C/S:状态：设备-CPU 启动：CPU-设备 地址总线：设备名-译码电路I/O逻辑-接口 控制总线：操作码-译码电路-CR B.设备控制器与设备的接口串行： 数据线：设备DR 状态线：设备-C/S 控制线：C/S-设备 C.译码电路I/O逻辑：实现对设备的控制 上面2个译码功能+并行-分解-设备控制器 地址即要选哪个设备-地址线-设备控制器-I/O逻辑进行译码-选中设备3设备-DR:数据准备；DR-内存：数据传送4设备控制器的功能： A.接收和识别命令 B.

26、数据交换 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.检查

27、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轮询的可

28、编程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,磁盘源地

29、址送至DMA控制器的I/O控制逻辑-启动DMA控制器，进行数据传送-读一个字节送至DR后，挪用一个存储器周期，送至内存，MAR+1，DC-1-传送完，DMA控制器发中断请求-CPU处理中断-以后调度到进程时再取数据4I/O通道控制方式：以一组数据块为单位 A.过程：CPU发I/O指令包含通道程序的首址和访问的I/O设备-通道-内存中取对应的通道程序并执行-完成后，向CPU发中断信号 B.通道程序由通道指令通道命令构成，包含操作码读还是写、内存地址、计数、记录结束标志R(R=1结束)、通道程序结束位P(P=1结束)四与设备无关的I/O软件1.增加该类软件，以实现设备独立性设备无关性，要引入逻辑设

30、备名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：含逻辑设备名、物理设备名、设备驱动程序入口地址 每次为进程分配设备，就填写一个表项,下次时直接查找LUT2整个系统一张LUT:只能单用户 每个用户一张LUT:实现多用户五往后内容看书