操作系统总结

1、第一章1、操作系统是计算机硬件与应用之间的系统软件 用处：方便人们更高效的使用计算机硬件，方便人们管理计算机资源，实现了对资源的抽象化。2、操作系统的发展（三个线索） 线索一：20世纪50年代中单道批处理系统（一次处理一个作业）20世纪60年代中多道批处理系统（一次处理多个）程序一旦进入用户不能进行干预分时系统-允许用户通过多个终端同时访问主机资源-人机交互、 共享主机、及时接收、 及时处理UNIX出现Unix到LINUX 线索二： PC与DOS、MS_DOS到windows 线索三： MAC OS3、操作系统的主要功能 1>处理机管理 进程控制（进程的创建、撤销、状态转换）、进程同步、

2、进程通信、调度（作业调度、进程调度） 2>存储器管理内存分配、内存保护、地址映射（逻辑地址到物理地址转换）、内存扩充（请求调入功能、置换功能）3>设备管理任务：(1) 完成用户进程提出的I/O请求，为用户进程分配所需的I/O设备，并完成指定的I/O操作。(2) 提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备。功能：缓冲管理、设备分配、设备处理4>文件管理功能文件存储空间的管理、目录管理、文件的读/写管理和保护5>接口管理用户接口（联机用户接口、脱机用户接口、图形用户接口）、程序接口4、操作系统的结构<1>整体结构-无结构<2&g

3、t;模块化结构-按功能分成不同的模块模块独立性：高内聚（模块内部各部分联系紧密），低耦合（模块间相互联系和相互影响程度低）-模块的独立性好<3>分层式结构-自底向上的设计（每一层软件都是在他下层软件基础上构建的）优：易保证系统正确性、易扩充和易维护 缺：系统效率低<4>虚拟机<5>客户-服务器模型（微内核）第二章-进程的描述与控制1、前趋图：DAG 有向无循环图 结点间的有向线段表示两结点有前趋或偏序关系偏序（Partial Order）：设A是一个非空集，P是A上的一个关系，若P满足下列条件： 对任意的aA，（a,a）P;(自反性） 若（a,b）P，且（b

4、,a）P，则 a=b;（反对称性） 若（a,b）P，（b,c）P，则（a,c）P;（传递性）则称P是A上的一个偏序关系2、程序顺序执行 特点：顺序性，封闭性（一旦开始不受外界干扰，占用全部资源），可再现性（执行环境，初始条件相同）3、程序并发执行 特点：间断性（由于共享资源，相互合作，导致相互制约）、失去封闭性、不可再现性4、进程-具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。（由程序、数据、PCB构成）【1】特征：动态性（最基本）、并发性、独立性、异步性程序是一组有序指令的集合，是静态的。【2】三种基本状态：就绪、执行、阻塞状态【3】创建状态

5、：申请空白PCB 写入控制和管理信息 分配资源 进入就绪队列 终止状态：等待OS进行善后处理 PCB清零，并返还系统【4】挂起操作：停止一切，处于静止状态，原因：终端用户要求，父进程请求，负荷调节需要、操作系统需要一旦进程被挂起，必须经过激活操作才能继续进行5、进程控制块PCB【1】作用：作为独立运行基本单位的标志、实现间断性运行方式、提供进程管理所需信息、提供进程调度所需信息、实现与其他进程的同步与通信。【2】包含信息：1）进程标识符：外部标识符、内部标识符2）处理机状态（各种寄存器内容）3）进程调度信息（进程状态、优先级、所需信息、事件-阻塞原因）4）进程控制信息（程序和数据的地址、同步和

6、通信机制、资源清单、链接指针）【3】组织方式：线性方式、链接方式、索引方式6、进程控制（创建、终止、置于阻塞态、运行中状态转换）一般由OS中的原语实现处理机执行状态：系统态（管态/内核态），用户态（自态）。7、OS内核包含功能【1】支撑功能：中断处理（最基本）、时钟管理（基本）、原语操作（原子操作-不可中断分割）【2】资源管理功能：进程控制、存储器管理、设备管理8、进程创建：【1】引起创建的事件：用户登录、作业调度、提供服务、应用请求9、进程终止：【1】引起的事件：正常结束、异常结束、外界干预10、进程阻塞：是进程自身的一种主动行为。调用阻塞原语block阻塞，调用唤醒原语wakeup唤醒，必

7、须成对出现。唤醒后由阻塞状态 转变为 就绪状态。11、进程同步-协调进程次序，更好的共享资源，避免出现死锁【1】制约关系：间接相互制约关系（访问临界资源-先申请，再访问）、直接相互制约关系（一个进程等待其他进程的结果）【2】同步机制要遵守的规则：空闲让进、忙则等待、有限等待、让权等待12、硬件同步机制（P51）：【1】关中断-进入锁测试之前关闭中断，测试完成上锁后再打开中断【2】利用Test-and-Set（TS）指令实现互斥，【3】利用Swap指令实现进程互斥13、信号量机制【1】整型信号量仅通过两个原子操作（执行中不能中断）P、V操作wait(S)和(signal(S)来访问Wait(S)

8、 /S资源数目 signal（S）While(S<=0); s-; S+; 【2】记录型信号量-不存在“忙等”现象进程同步机制-增加一个进程链表指针list，用于链接所有等待进程【3】AND型信号量-共享数据作为临界资源And同步机制基本思想：将进程所需的资源，一次性全部分配给进程，只要有一个资源不到位其他资源也不分配给他。【4】信号量集-每次分配前测试资源数量是否大于可分配下限，再决定是否分配14、信号量的应用【1】利用信号量实现进程互斥-多个进程互斥访问临界资源，增添一个互斥信号量，将临界区至于P、V操作之间【2】利用信号量实现前趋关系-前趋图【1】定义：代表共享资源的数据结构、对该

9、数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，称之为管程【2】组成：管程的名称局部于管程的共享数据结构说明对该数据结构进行操作的一组过程对局部于管程的共享数据设置初始值的语句【3】特性：模块化，抽象数据类型，信息掩蔽【4】与进程的区别：（P54）【5】条件变量：利用管程实现同步时，必须设置同步工具16、进程通信【1】进程间的信息互换【2】进程互斥与同步低级进程通信【3】进程通信类型：共享存储器系统（基于数据结构的通信方式（低级），基于共享存储区的通信方式（高级）、管道通信系统（管道链接一个读进程、一个写进程，必须提供三方面协调能力：互斥、同步、确定对方是否

10、存在）、消息传递系统（高级、分成：直接通信方式、间接通信方式）、客户机-服务器系统（三种实现方法：套接字、远程过程调用和远程方法调用）【4】 消息传递的实现方式;1、直接消息传递系统1） 直接通信原语：对称寻址方式、非对称寻址方式2） 消息的格式3） 进程的同步方式4） 通信链路2、信箱通信间接通信方式-进程间的通信1）信箱的结构-信箱头+信箱尾2）信箱的通信原语创建、撤销、发送（send()），接收（receive（）3）类型：私有、公有、共享关系：一对一，一对多，多对一，多对多【5】 直接消息传递系统实例1、 消息缓冲队列通信机制中的数据结构消息缓冲区PCB中有关通信的数据项2、 发送原语

11、-send()3、 接受原语-receive(b)17、线程1、作为调度和分配的基本单位2、运行时的三种状态：执行状态、就绪状态、阻塞状态3、线程控制块-TCB4、线程是进程的一部分，一个进程可以还有多个线程，是CPU调度的基本单位，可以并发执行，5、缺点：一个线程崩溃，所有线程都要崩溃第三章、处理机调度与死锁311、调度实质资源分配。处理机调度是对处理机资源进行分配2、处理机调度层次：1）高级调度（几分钟一次）-长程调度/作业调度调度对象：作业2）低级调度（10-100MS一次）-进程调度/短程调度调度对象：进程（或内核级线程）3）中级调度（介于以上两者之间）-内存调度目的：提高内存利用率和

12、系统吞吐量3、处理机调度算法的目标1、共同目标：（1）资源利用率（2）公平性：获得合理的CPU时间（3）平衡性：为使系统中的CPU和各种外部设备都能经常处于忙碌状态（4）策略强制执行2、批处理系统的目标（1）平均周转时间短（2）系统吞吐量高（3）处理机利用率高3、分时系统的目标（1）相应时间快（2）均衡性4、实时系统的目标（1）截至时间的保证-HRT（硬实时系统）任务必须确保对截至时间的要求，SRT（软实时系统）任务基本上能保证对截至时间的要求（2）可预测性3.21、作业：从外存调入内存的基本单位-包含:程序、数据、作业说明书，系统根据作业说明书来控制程序2、作业步：作业经过若干个相互独立又相

13、互关联的顺序加工步骤（作业步）得到3、作业控制块-JCB4、作业运行的三个阶段，三个状态：收容、运行、完成-后备状态、运行状态、完成状态5、作业调度的主要任务：决定接纳多少个作业（根据系统规模、运行速度、作业大小、能否获得较好的系统性能）、接纳哪些作业-分时系统、实时系统不需要作业调度6、调度算法<1>先来先服务(FCFS)-依据进程进入就绪状态的先后顺序排列<2>短作业优先（SJF）-选取就绪队列中运行时间最短的进入运行状态<3>优先级调度算法（PSA）-外部赋予优先级<4>高响应比优先调度算法（HRRN）跟据响应比RP确定执行顺序（1）等待时

14、间相同，要求的服务时间越短，优先级越高，类似SJF （2）要求服务时间相同，等待时间越长，优先级越高，类似FCFS （3）对于长作业，随等待时间的增加，优先级提高3.3 进程调度1、进程调度的任务：保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程2、调度机制中应具有：排队器、分派器、上下文切换器3、进程的调度方式：非抢占式、抢占式抢占原则：优先权原则、短进程优先原则、时间片原则4、轮转调度算法：【1】按先来先服务策略排成队列，设置一个时间片，把CPU分配给对首进程，并令其执行一个时间片，所有进程都能获得一个时间片的处理机时间。【2】进程切换时机 若一个时间片尚未用完，正在运行的进程

15、便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。5、优先级调度算法非抢占式优先级调度算法，抢占式优先调度算法（用于实时性要求高的系统）【1】优先级类型：静态优先级（创建进程时确定，整个运行期间不变），动态优先级（创建时先赋予一个，其值岁进程的推进或等待时间的增加而改变）6、多队列调度算法7、多级反馈队列调度算法目前公认的一种较好的调度算法按优先级将就绪队列分成多个队列，优先级高的时间片小，每个队列采用FCFS算法，按队列优先级调度8

16、、基于公平原则的调度算法：保证调度算法（每个进程都获得相同的处理机时间）、公平分享调度算法（多个用户共享相同的处理机时间，不考虑进程数目）3.4 实时调度1、 实现实时调度的基本条件1） 提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级2） 系统处理能力强：假定系统中有m个周期性的硬实时任务HRT，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件系统才是可调度的 多处理机情况下，处理机数为N <=N3） 采用抢占式调度机制4） 具有快速切换机制-该机制应具有如下两方面的能力1、 对中断的快速响应能力2、 快速的任务

17、分派能力2、 实时调度算法分类1、 根据实时任务性质：硬实时调度算法、软实时调度算法2、 按调度方式：非抢占调度算法（非抢占式轮转调度算法、非抢占式优先调度算法）、抢占调度算法（基于时钟中断的抢占式优先级调度算法、立即抢占的优先级调度算法）3、最早截止时间优先算法（EDF）1、根据任务的截至时间确定优先级，截至时间早，优先级高2、非抢占式调度方式用于非周期实时任务3、抢占式调度方式用于周期实时任务4、最低松弛度优先（LLF）算法 1、确定任务优先级根据任务的紧急（或松弛）程度，愈紧急优先级越高，松弛度小优先级高2、主要用于可抢占的调度方式中5、优先级倒置 1、 高优先级进程被低优先级进程延迟或

18、阻塞的现象称为优先级倒置现象 2、解决方法：共享临界资源时，占有资源的低优先级进程，继承等待资源的高优先级进程的优先级3.5死锁概述1、定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么改组进程是死锁的2、产生死锁的必要条件：互斥条件、请求和保持条件、不可抢占条件、循环等待条件3、产生死锁的几种情况：竞争不可抢占性资源引起的死锁，竞争可消耗资源引起的死锁、进程推进顺序不当引起的死锁4、处理死锁的方法：预防，避免，检测，解除 1）、预防死锁：破坏产生死锁的必要条件中一个或几个，主要破坏后三个，互斥条件应加以保证。 【1】破坏请求和保持条件：不能持有不可抢占的资源

19、；通过两种协议实现：一次性申请整个运行过程中的全部资源。：获取初期资源，运行过程中逐步释放已用完的，再逐步请求新的资源【2】破坏不可抢占条件-代价大申请资源的不到满足时，释放已有的资源【3】破坏“循环等待”条件对资源类型进行线性排序，并赋予不同序号，进程请求时按序号递增的顺序请求2）、避免死锁-在资源动态分配过程中，避免系统进入不安全状态系统进入不安全状态，有可能出现死锁【1】 银行家算法（1） 数据结构：（1） 可利用资源向量Available，m个元素的数组（2） 最大需求矩阵Max ，n*m矩阵（3） 分配矩阵Allocation, n*m（4） 需求矩阵Need ,n*mNeedi,j

20、=Maxi,j-Allocationi,j (2)银行家算法(1) 如果RequestijNeedi, j，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej = Availablej-Requestij; Allocationi, j = Allocationi, j+Requestij; Needi, j = Needi, j-Requestij; (4) 系统执行

21、安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。（3）安全性算法(1) 设置两个向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work := Available； Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi := false；当有足够资源分配给进程时，再令Finishi := true。(2) 从进程集合中找到一个能满足下述条件的进程： Finishi=fa

22、lse; Needi, jWorkj;若找到，执行步骤(3)，否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj = Workj+Allocationi, j; Finishi =true; go to step 2; (4) 如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。3）死锁的检测与解除<1>死锁检测算法<2>死锁的解除：抢占资源、终止（或撤销）进程（终止所有死锁进程、逐个终止进程）第四章、存储器管理1、存储层次至少三层：最高层CPU寄存器、中

23、间是主存、最底层是辅存2、CUP寄存器、主存属于操作系统存储管理的管辖范畴，掉电后存储的信息不复存在，辅存属于设备管理的管辖范畴，存储的信息长期保存RAM 随机存储器 断电后信息丢失ROM 只读存储器 断电后信息不丢失3、可执行存储器：寄存器和主存储器4、主存储器简称为内存或主存，主存储器的访问速度远低于CPU指令的速度5、寄存器具有与处理机相同的速度，完全能与CPU协调工作，造价昂贵6、高速缓存：介于存储器和寄存器之间的存储器、主要备份主存中常用的数据4.2 程序的装入和链接1、程序变成可执行程序经过：编译 、 链接 、装入2、程序的装入：【1】绝对装入方式：适合单道系统【2】可重定位装入方

24、式（静态重定位）：装入后不再移动【3】动态运行时的装入方式：将逻辑地址装入，等到运行时再转换为物理地址，装入后可移动3、程序的链接：【1】静态链接方式：运行之前链接，不再拆开【2】装入时动态链接：边装入边来链接【3】运行时动态链接：在程序运行的时候需要该模块的时候才链接4.3连续分配存储管理方式分为四类1、单一连续分配：用户区内存中仅装有一道用户程序，即整个内存的用户空间由该程序独占2、固定分区分配：将整个用户内存分区分成固定大小的区域（相等/不等），每个区域只装入一道作业3、动态分区分配：按照进程的需要动态的分配内存分配算法顺序搜索【1】首次适应（FF）算法：空闲分区地址递增排序，找到第一个

25、大小能满足的分区【2】循环首次适应（NF）算法：不再从头查找，从上一次的空闲分区开始查找，直至找到一个能满足进程需要的空闲分区【3】最佳适应（BF）：按空间从小到大排序，分配第一个合适的空闲分区【4】最坏适应（WF）：按空间从大到小排序，分配第一个合适的空闲分区-索引搜索1、快速适应算法（分类搜索法）：将空闲分区根据其大小分类，每一类单独设立一个空闲分区链表，同时设立一张管理索引表 查找效率高，分区归还时算法复杂，以空间换时间2、伙伴系统：该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，lkm)。通常2m是整个可分配内存的大小(也就是最大分区的大小)。 假设进程需要长度为

26、n的存储空间： （1）计算i，使2i-1-1 < n <= 2i，在空闲分区大小为2i的空闲分区链表中查找，如果找到，则分配。 （2）没找到，则在2i+1的空闲分区链表中查找，如果找到，则将该区等分，一个分配，一个加入2i的空闲分区链表。 （3）如果仍没找到，则继续类似（2）的处理。在伙伴系统中，对于一个大小为2k，地址为x的内存块，其伙伴块的地址则用buddyk(x)表示，其通式为3、哈希算法：建立哈希函数，分配时根据所需空闲分区大小，通过哈希函数计算，得到空闲分区的位置4、动态重定位分区分配算法：在动态分区的基础上，增加紧凑功能（合并小的空闲分区）。4.5、分页存储管理方式离散分配1、分页存储管理方式 将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame)。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。【1】地址结构：A：逻辑地址空间的地址，页面大小L，页号P，页内地址dINT 整除 MOD 求余【2】页表-记录相应页在内存中对应的物理块号 每一个进程有一个页表，页表的作用是实现页号到物理块号的地址映射。【3】地址变换机构：