(精品)《操作系统》复习.ppt

操作系统操作系统复习复习第第1章章引论引论1.概念概念多道程序设计技术多道程序设计技术多道批处理系统多道批处理系统分时系统分时系统实时系统实时系统系统吞吐量系统吞吐量作业的周转时间和平均周转时间作业的周转时间和平均周转时间OS基本类型基本类型2.内容内容处理机管理处理机管理存储器管理存储器管理设备机管理设备机管理文件管理文件管理用户接口用户接口进程控制进程控制进程同步进程同步进程通信进程通信进程调度进程调度缓冲管理缓冲管理设备分配设备分配设备处理设备处理文件存储空间管理文件存储空间管理目录管理目录管理文件读文件读/写管理写管理命令接口命令接口程序接口程序接口图形接口图形接口内存分配与保护内存分配与保护地址映射地址映射地址扩充地址扩充OS的功能的功能(五个功能五个功能)OS的特征的特征(四个特征四个特征)并发并发共享共享虚拟性虚拟性异步性异步性OS的作用的作用(三个作用三个作用)用户与计算机接口用户与计算机接口计算机资源的管理者计算机资源的管理者机器的扩充机器的扩充(虚拟机虚拟机)lOS发展过程发展过程单道批处理系统单道批处理系统-在解决人机矛盾，在解决人机矛盾，CPU与与I/O设备速度不匹设备速度不匹配的矛盾中形成。配的矛盾中形成。旨在提高资源利用率和系统吞吐量旨在提高资源利用率和系统吞吐量。单道：内存中只保持一道作业。单道：内存中只保持一道作业。批处理：一批作业存放在磁带上，由监督程序逐个调批处理：一批作业存放在磁带上，由监督程序逐个调入内存运行。入内存运行。单道批处理的工作特点是：单道批处理的工作特点是：自动性自动性顺序性顺序性单道性单道性多道批处理系统多道批处理系统-通过引入多道程序设计技术，通过引入多道程序设计技术，进一进一步提高资源利用率以及系统吞吐量步提高资源利用率以及系统吞吐量多道：内存中保持多道作业。多道：内存中保持多道作业。批处理：一批作业存放在磁带上，由监督程序一次调批处理：一批作业存放在磁带上，由监督程序一次调入多个作业到内存运行。入多个作业到内存运行。多道批处理的工作特征是：多道批处理的工作特征是：多道性多道性无序性无序性调度性调度性多道批处理系统的优缺点：多道批处理系统的优缺点：优点：优点：提高资源利用率提高资源利用率(CPU,内存内存,I/O设备设备)提高系统吞吐量。提高系统吞吐量。缺点：缺点：平均周转时间长平均周转时间长无交互能力。无交互能力。分时系统分时系统-保持多道批处理系统的优点保持多道批处理系统的优点(共享主机共享主机)，克服无交互能力的缺点克服无交互能力的缺点实现分时系统的关键问题：实现分时系统的关键问题：用户与自己的作业进行交互用户与自己的作业进行交互键入命令能及时接收键入命令能及时接收及时处理及时处理分时系统的特征分时系统的特征：多路性多路性一台主机同时联接多台终端为多个用户服务一台主机同时联接多台终端为多个用户服务交互性交互性人机对话多种服务人机对话多种服务独占性独占性用户感觉独占主机用户感觉独占主机及时性及时性用户请求及时响应用户请求及时响应实时系统：指能及时响应外部事件请求，在规定时间内完成对实时系统：指能及时响应外部事件请求，在规定时间内完成对事件的处理，并控制所有实时任务协调一致地运行的事件的处理，并控制所有实时任务协调一致地运行的（与分时系统的比较）（与分时系统的比较）l操作系统的结构设计操作系统的结构设计第一代操作系统第一代操作系统-无结构无结构(整体结构整体结构)第二代操作系统第二代操作系统-模块化结构模块化结构 第三代操作系统第三代操作系统-层次结构层次结构操作系统的微内核结构操作系统的微内核结构微内核技术微内核技术-精心设计精心设计OS的最基本的核心功能组成的最基本的核心功能组成操作系统的内核。内核常驻内存，不被换出。操作系统的内核。内核常驻内存，不被换出。然后在外层添加新的功能。然后在外层添加新的功能。第第2章章进程管理进程管理1.概念概念进程（进程的引入、定义、特征进程（进程的引入、定义、特征）进程控制块进程控制块PCB(作用、包含信息、作用、包含信息、为什么为什么PCB是进程存在的唯一标志是进程存在的唯一标志)进程的状态进程的状态(就绪，阻塞，执行，挂起就绪，阻塞，执行，挂起)进程的并发与并行执行进程的并发与并行执行进程同步进程同步临界资源与临界区临界资源与临界区信号量信号量P，V操作操作线程（定义，与进程的区别）线程（定义，与进程的区别）2内容内容（1）进程控制）进程控制程序顺序执行和并发执行的特点程序顺序执行和并发执行的特点用前趋图描述进程的并发执行。用前趋图描述进程的并发执行。进程控制的定义。进程控制的定义。进程的三个基本状态及状态变迁图。进程的三个基本状态及状态变迁图。进程创建原语和终止原语的过程进程创建原语和终止原语的过程附：附：PCB中的信息中的信息进程标识符信息进程标识符信息处理机状态信息处理机状态信息进程调度信息进程调度信息进程控制信息进程控制信息内部标识符内部标识符外部标识符外部标识符通用寄存器通用寄存器指令计数器指令计数器程序状态字程序状态字用户栈指针用户栈指针进程状态进程状态进程优先级进程优先级事件事件其它信息其它信息程序和数据的地址程序和数据的地址进程同步和通信机制进程同步和通信机制资源清单资源清单链接指针链接指针PCBPCB（2）进程同步（对进程执行次序的协调）进程同步（对进程执行次序的协调）进程之间相互制约的形式进程之间相互制约的形式(直接制约和间接制约直接制约和间接制约)。同步机制应遵循的规则同步机制应遵循的规则(空闲让进空闲让进;忙则等待忙则等待;有限等待有限等待;让权等待让权等待)信号量信号量整形信号量：整形信号量：P,V操作可描述为：操作可描述为：P(s)：whiles0dono-ops:s一一1；V(s)：s:s十十1；P操作操作申请一个资源申请一个资源,V操作操作释放一个资源。释放一个资源。缺点缺点:“忙等忙等”，只要，只要s0就不断测试，未遵循就不断测试，未遵循“让权等让权等待待”记录型信号量的记录型信号量的P，V操作操作P P（S S）（）（waitwait（S S）S.V-S.V0 表示某类可用资源的数量 =0 绝对值表示因请求该资源而被阻塞的进程数 S.V的初值为1时，表示只允许一个进程访问临界资 源，此时的信号量转化为互斥信号量。用信号量实现同步和互斥的模型用信号量实现同步和互斥的模型使用信号量的同步机制的应用：使用信号量的同步机制的应用：前驱图前驱图生产者生产者-消费者问题（消费者问题（P，V算法描述）算法描述）(3)进程通信进程通信定义：进程间信息交换定义：进程间信息交换类型类型(低级通信，高级通信（包括共享存储器、消低级通信，高级通信（包括共享存储器、消息传递、管道）息传递、管道）)消息传递通信机制：指以格式化的消息为进程间数消息传递通信机制：指以格式化的消息为进程间数据交换单位的进程通信方式据交换单位的进程通信方式直接通信：直接通信：消息缓冲队列通信机制消息缓冲队列通信机制（发送原语，发送原语，接收原语接收原语流程）流程）间接通信间接通信（4）线程）线程线程的定义线程的定义线程的作用线程的作用线程与进程的区别线程与进程的区别（进程与程序的区别）（进程与程序的区别）进程同步例题进程同步例题有三个共行进程P、Q和R以及一对供存数据的缓冲BufI和BufO，P进程把数据输入BufI，R进程输出BufO中的数据。Q地把BufI中的数据变换后送入BufO，在上述假定之下,使三个进程实现最大并行性。试在下述类PASCAL程序中虚线位置分别填上信号量、信号量初值和P、V操作实现三个进程正确的并发执行。P Q BufIBufO R解：解：设置信号量设置信号量emptyIemptyI,fullIfullI，emptyOemptyO,fullOfullO，初值分别为，初值分别为1,0,1,0 1,0,1,0；PP(emptyI)送入送入BufIV(fullI)QP(fullI)从从BufI取数据取数据V(emptyI)数据变换数据变换;P(emptyO)送入送入BufOV(fullO)RP(fullO)从从BufO取数据取数据;V(emptyO)例题2：桌子上有一只盘子，最多可容纳一个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘于中放桔子(orange)，儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系第第3章章处理机调度与死锁处理机调度与死锁1.概念：概念：处理机调度处理机调度-按一定的算法将处理机分配给就绪队列上某个 进程。抢占式的调度和非抢占式的调度抢占式的调度和非抢占式的调度周转时间周转时间：是指从作业提交给系统开始，到作业完成为止的 这段时间间隔(称为作业周转时间)带权周转时间带权周转时间平均周转时间平均周转时间响应时间响应时间死锁死锁系统的安全状态系统的安全状态2.内容内容（1）三级调度）三级调度高高-作业调度作业调度中中-将暂不运行的进程调到外存将暂不运行的进程调到外存低低-进程调度进程调度（2）调度算法选择的准则）调度算法选择的准则准则准则面向系统面向系统面向用户面向用户吞吐量吞吐量处理机的利用率处理机的利用率各类资源平衡利用各类资源平衡利用周转时间周转时间响应时间响应时间截止时间截止时间优先权准则优先权准则（3）进程调度算法进程调度算法（计算）（计算）先来先先来先服务（服务（FCFS）短作业优（短作业优（SJ(P)F）高优先权优先高优先权优先高响应比优先高响应比优先基于时间片的轮转调度基于时间片的轮转调度响应比响应比RP（等待时间（等待时间+要求要求服务时间）服务时间）/要求服务时间要求服务时间响应时间响应时间/要求服务时要求服务时间间（4）实时调度）实时调度最早截止时间优先最早截止时间优先最低松弛度优先最低松弛度优先-实施过程实施过程（5）死锁原因和必要条件死锁原因和必要条件产生死锁的原因。产生死锁的原因。产生死锁的必要条件产生死锁的必要条件互斥条件互斥条件请求和保持条件请求和保持条件不剥夺条件不剥夺条件环路条件环路条件（6）死锁处理的基本方法）死锁处理的基本方法死锁的预防死锁的预防破坏四个必要条件中的一个（各自采用的方法）破坏四个必要条件中的一个（各自采用的方法）死锁的避免死锁的避免银行家算法银行家算法死锁的检测和解除死锁的检测和解除资源分配图及死锁定理资源分配图及死锁定理第第4章章存储器管理存储器管理1.概念概念逻辑地址，物理地址逻辑地址，物理地址地址空间，存储空间地址空间，存储空间重定位，静态重定位，动态重定位重定位，静态重定位，动态重定位碎片，页表，段表，共享段表，碎片，页表，段表，共享段表，快表快表虚拟存储器虚拟存储器，置换算法，置换算法抖动抖动belady现象现象2内容内容l连续分配：连续分配：（）单一连续分配（）单一连续分配(单用户，系统区，用户区单用户，系统区，用户区)（）固定分区分配（）固定分区分配分区大小和数目固定，但大小可相等或不相等。分区大小和数目固定，但大小可相等或不相等。数据结构：分区说明表，分区按从小到大排队。数据结构：分区说明表，分区按从小到大排队。（）（）动态分区分配动态分区分配分区大小不固定分区大小不固定数据结构：空闲分区表或空闲分区链数据结构：空闲分区表或空闲分区链首次适应算法分区首址递增链表首次适应算法分区首址递增链表循环首次适应算法循环首次适应算法最佳适应算法按大小递增链表最佳适应算法按大小递增链表分区分配与回收的具体步骤分区分配与回收的具体步骤分配算法分配算法：（）动态重定位分区分配（）动态重定位分区分配问题的提出：碎片利用。问题的提出：碎片利用。解决办法：移动作业位置进行解决办法：移动作业位置进行“紧缩紧缩”和和“重定位重定位”。硬件支持：重定位寄存器硬件支持：重定位寄存器(存放程序或数据的内存首址存放程序或数据的内存首址)。访问地址重定位寄存器中的地址相对地址访问地址重定位寄存器中的地址相对地址l离散分配离散分配克服动重定位分区分配中进行克服动重定位分区分配中进行“紧凑紧凑”“拼接拼接”引起的额外开销，将作业装入离散的分区中。引起的额外开销，将作业装入离散的分区中。（1）基本分页存储管理方式基本分页存储管理方式：作业一次性装入内存离散区域。：作业一次性装入内存离散区域。分页的地址结构分页的地址结构页 号 P位移量W逻辑地址逻辑地址A到分页地址的变换到分页地址的变换数据结构数据结构-页表页表页号块号硬件支持：硬件支持：页表寄存器页表寄存器(存页表内存首址和表长存页表内存首址和表长)；地址变换机构地址变换机构(硬件硬件)；快表快表(高速缓冲寄存器又称联想寄存器高速缓冲寄存器又称联想寄存器)-存放当前访问的那些存放当前访问的那些页表项页表项每个进程的页表首址和长度存在每个进程的页表首址和长度存在PCB中。运行中的进程的中。运行中的进程的页表首址和长度存在页表寄存器。页表首址和长度存在页表寄存器。地址变换机构的工作过程地址变换机构的工作过程分段管理的目的分段管理的目的方便编程方便编程信息共享信息共享-共享段共享段信息保护信息保护-分段越界中断，段表中的分段越界中断，段表中的存取控制字段存取控制字段动态增长动态增长-段表中设增长标志段表中设增长标志段段段的地址结构段的地址结构段表段表硬件支持硬件支持(段表寄存器存放段表首址和长度，地址变换机构段表寄存器存放段表首址和长度，地址变换机构)（2）基本分段存储管理方式）基本分段存储管理方式分页与分段的主要区别分页与分段的主要区别页是信息的物理单位，段是信息的逻辑单位。页是信息的物理单位，段是信息的逻辑单位。页面大小固定由系统决定，所以系统中只能有一种大小的页面大小固定由系统决定，所以系统中只能有一种大小的页面。页面。分页的地址空间为一维的，程序员只需用一个记忆符便能分页的地址空间为一维的，程序员只需用一个记忆符便能表示一个地址；分段的地址为二维的，程序员标识地址需表示一个地址；分段的地址为二维的，程序员标识地址需给出段名和段内地址。给出段名和段内地址。（3）段页式存储管理）段页式存储管理-先将用户程序分成若干段，先将用户程序分成若干段，再将每段分为若干页。再将每段分为若干页。虚拟存储管理的基本概念虚拟存储管理的基本概念前述存储管理方式的特点前述存储管理方式的特点一次性一次性作业一次性地全部装入内存作业一次性地全部装入内存驻留性驻留性装入后到运行结束一直驻留在内存装入后到运行结束一直驻留在内存局部性原理局部性原理-虚拟存储的理论基础虚拟存储的理论基础虚拟存储器的定义虚拟存储器的定义指具有请求调入功能和置换功能，能从逻辑上对内存容指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。是具有多次性特征的存量加以扩充的一种存储器系统。是具有多次性特征的存储器系统。储器系统。关键技术关键技术：覆盖和交换：覆盖和交换硬件支持硬件支持请求分页请求分页(段段)的页的页(段段)表机制；表机制；缺页缺页(段段)中断机构中断机构地址变换机构地址变换机构软件支持软件支持-请求调页请求调页(段段)和页和页(段段)置换功能软件。置换功能软件。虚拟存储器的特征：虚拟存储器的特征：多次性多次性对换性对换性虚拟性虚拟性虚拟存储器的实现方法：虚拟存储器的实现方法：请求分页系统请求分页系统请求分段系统请求分段系统1.请求分页存储管理方式请求分页存储管理方式-在基本分页的基础上在基本分页的基础上增加请求调页和置换功能。增加请求调页和置换功能。（1）硬件支持）硬件支持页表机构要扩充页表机构要扩充缺页中断机构缺页中断机构指令执行期间可能产生和处理中断指令执行期间可能产生和处理中断一条指令可能产生多次缺页中断。一条指令可能产生多次缺页中断。特征特征 地址变换机构地址变换机构硬件实现硬件实现（2）物理块的分配策略和分配算法）物理块的分配策略和分配算法固定分配局部置换固定分配局部置换可变分配全局置换可变分配全局置换可变分配局部置换可变分配局部置换物理块的物理块的分配策略分配策略物理块的物理块的分配算法分配算法平均分配平均分配按比例分配按比例分配考虑优先权的分配考虑优先权的分配（3）调页策略）调页策略何时调页何时调页何处调页何处调页调页过程调页过程(步骤步骤)缺页中断处理缺页中断处理预调页预调页请求调页请求调页从文件区调页从文件区调页从对换区调页从对换区调页（4）页面置换算法（缺页中断的计算）页面置换算法（缺页中断的计算）最佳置换算法最佳置换算法-只有理论价值，不能实现只有理论价值，不能实现(着眼未来着眼未来)先进先出先进先出(FIFO)置换算法置换算法LRU算法算法(最近最久未使用）最近最久未使用）Clock算法算法2.请求分段存储管理请求分段存储管理在基本分段存储管理基础上增在基本分段存储管理基础上增加调段和段置换功能加调段和段置换功能（1）硬件支持）硬件支持段表机制段表机制缺段中断机构缺段中断机构地址变换机构地址变换机构（2）分段共享和保护）分段共享和保护为共享段建立共享段表为共享段建立共享段表越界中断越界中断存取控制存取控制环保护机构环保护机构段的保护段的保护第第5章章设备管理设备管理I/O系统系统（设备、控制器、通道）（设备、控制器、通道）I/O控制方式控制方式（程序测试、中断、（程序测试、中断、DMA、通道）、通道）缓冲池缓冲池设备独立性设备独立性：逻辑设备与物理设备：逻辑设备与物理设备磁盘调度磁盘调度虚拟设备（虚拟设备（Spooling系统）系统）1.相关概念相关概念2设备管理设备管理设备管理设备管理缓冲管理缓冲管理设备分配设备分配设备处理设备处理3缓冲管理缓冲管理4（1）为什么引进缓冲？为什么引进缓冲？5（2）缓冲的种类：）缓冲的种类：6专用缓冲单缓冲专用缓冲单缓冲双缓冲双缓冲循环缓冲循环缓冲(多缓冲多缓冲)7公用缓冲池公用缓冲池由多个公用的缓冲区组成，分成三由多个公用的缓冲区组成，分成三个缓冲个缓冲8区队列。区队列。缓冲池的组成：缓冲池的组成：空缓冲队列空缓冲队列emq-空缓冲区组成空缓冲区组成输入队列输入队列inq-装满输入数据的缓冲区组成装满输入数据的缓冲区组成输出队列输出队列outq-装满输出数据的缓冲区组成装满输出数据的缓冲区组成三个三个队列队列四个四个工作工作缓冲区缓冲区收容输入缓冲区收容输入缓冲区输入进程用输入进程用提取输入缓冲区提取输入缓冲区-计算进程计算进程用用收容输出缓冲区收容输出缓冲区-计算进程计算进程用用提取输出缓冲区提取输出缓冲区-输出进程输出进程用用两个两个过程过程有互斥和有互斥和同步机制同步机制Getbuf从从参数指定的缓冲队列上取下缓冲区参数指定的缓冲队列上取下缓冲区Putbuf缓冲区放到参数指定的缓冲队列上缓冲区放到参数指定的缓冲队列上数据结构数据结构设备控制表设备控制表DCT控制器控制表控制器控制表COCT通道控制表通道控制表CHCT系统设备表（系统设备表（SDT）记录设备情况记录设备情况4设备分配设备分配独占设备的分配过程独占设备的分配过程 设备独立性设备独立性-用户使用逻辑设备名申请，与物理设备无关用户使用逻辑设备名申请，与物理设备无关设备独立性实现关键：设备独立性实现关键：逻辑设备表逻辑设备表LUT-逻辑设备到物理设备的映射逻辑设备到物理设备的映射5I/O软件软件 I/O软件分层软件分层 中断处理过程中断处理过程5.虚拟设备：虚拟设备：虚拟设备定义虚拟设备定义什么是什么是SPOOLing？SPOOLing系统的组成：系统的组成：SPOOLing的特点的特点(优点优点)提高提高I/O速度速度将独占设备改造为共享设备将独占设备改造为共享设备实现虚拟设备实现虚拟设备输入井，输出井输入井，输出井输入缓冲区，输出缓冲区输入缓冲区，输出缓冲区输入进程，输出进程输入进程，输出进程6磁盘存储器管理磁盘存储器管理l磁盘访问时间（三部分）磁盘访问时间（三部分）l磁盘调度管理的主要目的磁盘调度管理的主要目的l磁盘调度算法磁盘调度算法FCFS，SSTF，SCAN，CSCAN第第6章章文件管理文件管理1.概念概念文件文件文件系统文件系统 文件目录文件目录索引节点索引节点（引入原因，包含信息）（引入原因，包含信息）文件逻辑结构文件逻辑结构文件物理结构文件物理结构文件打开操作（引入原因，操作过程）文件打开操作（引入原因，操作过程）文件关闭操作文件关闭操作l文件物理结构文件物理结构（外存分配方式）（外存分配方式）(每种分配方式每种分配方式的优缺点的优缺点)连续分配（顺序文件）连续分配（顺序文件）链接分配链接分配(链接文件链接文件)索引分配索引分配(索引文件索引文件)为每个文件分配一为每个文件分配一个索引块，索引块中存放该文件的所有盘个索引块，索引块中存放该文件的所有盘块号。块号。（一级索引，二级索引，（一级索引，二级索引，UNIX混合索引）混合索引）隐式链接隐式链接显式链接显式链接(FAT所占空间的计算所占空间的计算)2内容内容l 文件逻辑结构文件逻辑结构（用户角度所看到的文件的组织形式）（用户角度所看到的文件的组织形式）有结构文件：顺序，索引，索引顺序有结构文件：顺序，索引，索引顺序无结构文件无结构文件l文件存取方式文件存取方式顺序存取顺序存取随机存取随机存取l文件操作文件操作打开（引入原因，操作过程）打开（引入原因，操作过程）关闭关闭l 目录管理目录管理为每一个文件建立文件名到物理块的映射为每一个文件建立文件名到物理块的映射目录项目录项FCB：包含内容：包含内容目标：目标：按名存取；提高对目录的检索速度；文件共享；按名存取；提高对目录的检索速度；文件共享；允许文件重名。允许文件重名。结构：一级目录，二级目录，多级目录结构：一级目录，二级目录，多级目录 文件存储空间的管理文件存储空间的管理空闲表法空闲表法空闲链表法空闲链表法位示图法（盘块号与矩阵行列换算）位示图法（盘块号与矩阵行列换算）成组链接法（分配回收过程）成组链接法（分配回收过程）文件共享与保护（文件共享与保护（两种共享方法各自特点两种共享方法各自特点）利用索引点的文件共享；利用索引点的文件共享；利用符号链的文件共享；利用符号链的文件共享；利用磁盘容错技术的文件保护利用磁盘容错技术的文件保护