操作系统复习张尧学市公开课一等奖百校联赛获奖课件.pptx

计算机操作系统教程计算机操作系统教程（四）（四）清华大学出版社清华大学出版社 主编主编:张尧学张尧学 史美林史美林 第1页操作系统复习操作系统复习l考试题型 单项选择题、简答题、综合题l考试范围 第1、2、3、4、5、8、9章 l重点章节 第3、4、5章l复习内容 各章主要知识点第2页第第1 1章章 绪论绪论l 知识重点第3页1.1.操作系统定义及特征操作系统定义及特征 操操作作系系统统是是管管理理和和控控制制计计算算机机系系统统中中软软硬硬件件资资源源，合合理理组组织织计计算算机机工工作作流流程程，方方便便用用户户操操作使用机器程序集合。作使用机器程序集合。基本特征基本特征:（1 1）执行并发性）执行并发性 （2 2）资源共享性）资源共享性 （3 3）操作异步性）操作异步性 第4页2.2.操作系统功效操作系统功效(1).(1).处理机管理处理机管理(包含：进程管理）包含：进程管理）(2).(2).存放管理存放管理(3).(3).设备管理设备管理(4).(4).文件系统管理文件系统管理(5).(5).用户接口（作业管理）用户接口（作业管理）第5页3.3.操作系统三种基本类型及特点操作系统三种基本类型及特点(1).批处理系统批处理系统主要特点：主要特点：脱机操作；脱机操作；成批处理；成批处理；多道程序运行；多道程序运行；无交互性。无交互性。(2).分时系统分时系统主要特点：主要特点：交互性；交互性；同时性；同时性；独立性；独立性；及时性。及时性。(3).实时系统实时系统主要特点：主要特点：实时时钟管理实时时钟管理；连续人机对话连续人机对话；过载防护，安全可靠；过载防护，安全可靠；资源利用率低资源利用率低第6页4.4.多道程序运行及特点多道程序运行及特点多道程序设计：允许多作业同时进入内存轮番交替占用CPU运行技术。特点：（1）多道性 （2）宏观上并行 （3）微观上串行第7页第第2 2章章 用户界面用户界面l 知识重点第8页1.作业组成作业组成作业由程序、数据和作业说明书三部份组成，但最少包含一个程序。其中：程序：表明完成任务及操作 数据：操作对象；作业说明书：表达用户控制意图。第9页2.计算机与用户之间接口及用途计算机与用户之间接口及用途 (1)操作命令接口：OS为用户提供各种操作命令，供用户直接组织作业工作流程和控制作业运行；(2)系统调用接口：OS为用户提供一组系统功效调用(广义指令)，供用户编程时调用系统功效，请求操作系统提供服务。第10页知识重点知识重点第第3 3章章 进程管理进程管理第11页1.程序次序执行及特点程序次序执行及特点程序在处理机上执行是严格按序。特点：特点：次序性 封闭性 可再现性 第12页2进程并发执行及特点进程并发执行及特点进程进程在处理机上执行时间是交叉重合，是提升CPU利用率而采取一个同时操作技术。特点：特点：独立性 随机性 资源共享性第13页3.进程定义及引入目标进程定义及引入目标定义 一个含有独立功效程序关于某个数据集在处理机上一次执行过程及分配资源基本单位。引入目标 为了控制和协调并发程序对软硬件资源共享和竞争。为了描述程序动态执行过程和有个分配资源基本单位。第14页4.进程基本特征进程基本特征 动态性动态性并发性并发性独立性独立性异步性异步性第15页5.进程描述进程描述进程描述包含三部分：进程描述包含三部分：程序程序 数据结构集数据结构集 进程控制块（进程控制块（PCBPCB）第16页6.进程状态及转换进程状态及转换 运行状态运行状态 一个进程正占用一个进程正占用CPUCPU执行。执行。等候状态等候状态 进进程程因因等等候候某某事事件件不不能能享享用用CPU.CPU.就绪状态就绪状态 进进程程已已具具备备运运行行条条件件还还未未占占用用CPU。运行运行就绪就绪等候等候调度调度时间时间片到片到等候事件等候事件事件发生事件发生第17页7.临界区与临界区与管理标准管理标准临界区：不允许多个并发进程交叉执行程序段。管理标准 每次至多一个进程进入临界区；进程不能无限期留在临界区；进程不能相互阻塞。第18页8.两种制约关系两种制约关系间接制约：并发执行程序共享公用资源而引发执行速度上制约。(造成进程互斥)直接制约：并发执行进程共享对方私用资源而引发执行速度上制约。(造成进程同时)第19页9.进程同时与互斥进程同时与互斥l进进程程同同时时 相相互互合合作作并并发发进进程程之之间间在在一一些些点点要要相相互互通通信信，相相互互协协调调，共共同同完完成成任任务务过程过程。l进进程程互互斥斥 不不允允许许两两个个或或两两个个以以上上并并发发进进程同时进入临界区。程同时进入临界区。第20页10.信号量与信号量与PVPV原语原语信号量（信号量（SemaphoreSemaphore）表示系统中资源实体数目或资源使用表示系统中资源实体数目或资源使用情况整型量情况整型量,其值只能由其值只能由PVPV原语操作改变。原语操作改变。n n个进程共享个进程共享m m个资源，信号量改变范围个资源，信号量改变范围 （m-nm-nm-nm-n）S mS mS mS mP(S)P(S)：代表申请使用资源操作：代表申请使用资源操作 S SS-1S-1；若若S S0,0,则则该该进进程程被被阻阻塞塞后后与与该该信信号号相相对对应应对对列列中中,然然后后转转进程调度；进程调度；若若S0,S0,则则,调用调用P(S)P(S)原语原语进程继续运行。进程继续运行。V(S)V(S)：代表释放偿还资源操作：代表释放偿还资源操作 S SS+1S+1；若若S0,S0,则则唤唤醒醒一一个个等等候候S S进进程程后后,调调用用P(S)P(S)原原语语进进程程继继续续运行或转进程调度；运行或转进程调度；若若S S0,0,则则,调用调用V(S)V(S)原语原语进程继续运行。进程继续运行。第21页11.进程并发执行描述进程并发执行描述Begin,s:semaphore;/*定义信号量*/;s=XXX;/*赋初值*/COBEGIN Process P1;/*并发进程 */process p2;.COENDEnd 主程序主程序第22页12.PVPV原语实现进程互斥原语实现进程互斥Process PProcess P BeginBeginP(s);P(s);临界区；临界区；V(s)V(s)；EndEndProcess QProcess Q BeginBeginP(s);P(s);临界区；临界区；V(s)V(s)；EndEnd设公用信号量设公用信号量S，初值为，初值为1（或（或k）第23页PVPV原语实现进程互斥例子原语实现进程互斥例子Process P()Process P()BeginBeginP(s);P(s);进程进程P使用打印机使用打印机;V(s)V(s)；EndEndProcess Q()Process Q()BeginBeginP(s);P(s);进程进程Q使用打印机使用打印机;V(s)V(s)；EndEnd设进程设进程P P、Q Q共享一台打印机，打印机任何共享一台打印机，打印机任何时刻只能被一个进程使用，不能同时使用。时刻只能被一个进程使用，不能同时使用。设公用信号量设公用信号量S，初值为，初值为1。第24页13.PVPV原语实现进程同时原语实现进程同时Process PProcess P BeginBeginP(s1);P(s1);P P推进；推进；V(s2)V(s2)；EndEndProcess QProcess Q BeginBeginP(s2);P(s2);Q Q推进；推进；V(s1)V(s1)；EndEnd分别设私用信号量分别设私用信号量s1，初值为，初值为1（或（或k）；）；s2，初值为，初值为0第25页PVPV原语实现进程同时例子原语实现进程同时例子Process R()Process R()BeginBeginL1:读一个数;P(s1);P(s1);Buf=Buf=数；数；V(s2)V(s2)；Goto L1;Goto L1;EndEndProcess W()Process W()BeginBeginL2:L2:P(s2);P(s2);打印打印Buf中数；中数；V(s1)V(s1)；Goto L2;Goto L2;EndEnd 现有现有2个进程个进程R、W，它们共享能够存放一个数缓冲区，它们共享能够存放一个数缓冲区Buf。进。进程程R每次读入一个数存放到每次读入一个数存放到Buf中，由进程中，由进程W打印输出。打印输出。设私用信号量设私用信号量s1,初值为初值为1，s2,初值为初值为0。第26页14.死锁及死锁必要条件死锁及死锁必要条件 假如系统死锁，则必假如系统死锁，则必同时满足同时满足4 4条：条：不剥夺条件不剥夺条件 互斥条件互斥条件 部份分配部份分配 环路条件环路条件第27页15.15.处理死锁方法处理死锁方法 (1)预防(2)防止(3)检测与恢复第28页知识重点知识重点第第4章章处理机调度处理机调度第29页1.1.分级调度分级调度作业调度：宏观调度，或高级调度。交换调度：又称中级调度。其主要任务是按照给定标准和策略，将处于外存交换区中就绪状态或等候状态进程调入内存，或把处于内存就绪状态或内存等候状态进程交换到外存交换区。进程调度：微观调度或低级调度。第30页2.2.进程调度功效进程调度功效 统计进程状态;从就绪进程选取一个进程；实施进程上下文切换。第31页3.引发进程调度时机引发进程调度时机（1）正在执行进程执行完成。这时，假如不选择新就绪进程执行，将浪费处理机资源。（2）执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等候状态。（3）执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等候资源进程队列。（4）执行中进程提出I/O请求后被阻塞。（5）在分时系统中时间片已经用完。（6）在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完成，从而可调度选择一新用户进程执行。（7）就绪队列中某进程优先级变得高于当前执行进程优先级，从而也将引发进程调度。第32页4.调度算法调度算法（1 1）先来先服务算法（先来先服务算法（FCFSFCFS）（2 2）轮转法（轮转法（RRRR）（3）多级反馈轮转法多级反馈轮转法（4）优先数法优先数法（5）最短作业优先法（最短作业优先法（SJF）（6）最高响应比优先法（最高响应比优先法（HRN）第33页4.算法性能衡量算法性能衡量平均周转时间 T 其中 TiT完成T提交平均带权周转时间 W 其中 Wi周转时间/运行时间第34页知识重点知识重点第第5章章存放管理存放管理第37页1.存放管理功效存放管理功效（1 1）虚拟存放器实现虚拟存放器实现（2 2）完成地址重定位）完成地址重定位 （3）内存分配与回收）内存分配与回收（4 4）内存信息共享和保护）内存信息共享和保护（5 5）局部性原理和抖动问题）局部性原理和抖动问题）局部性原理和抖动问题）局部性原理和抖动问题 第38页2.虚拟存放器虚拟存放器 用户程序中代码、数据等逻辑地址组成虚拟空间。实质是把外存当成内存使用一个技术。特点：虚拟存放器容量由机器地址结构和寻址方式以及外存容量确定；虚拟存放器由软件、硬件共同支撑实现：软件负责内外信息交换；硬件实现虚实地址转换。第39页3.地址地址重定位重定位 将程序中逻辑地址转换映射成内存中物理地址过程。定位方式有：（1）静态重定位 程序执行前，由软件一次性完成。（2）动态重定位 程序执行中，由专门硬件地址变换机构实现。第40页3.分区分配管理分区分配管理（1）固定分区分配）固定分区分配 预先把主存放器空间分成若干个连续区域。（2）动态分区分配）动态分区分配 依据作业需求和内存情况动态分配区域。分配算法：最先适应法 最正确适应法 最坏适应法第41页4页式存放管理页式存放管理v将将进程进程逻辑地址空间分成若干大小相同页，同时将内存逻辑地址空间分成若干大小相同页，同时将内存空间分成若干块，块大小与页相同；存放分配时，以块空间分成若干块，块大小与页相同；存放分配时，以块为单位分配，但块与块之间不一定连续；经过页表和硬为单位分配，但块与块之间不一定连续；经过页表和硬件地址转换机构实现地址转换。件地址转换机构实现地址转换。v进程执行时，只把当前需要页装入内存（实页），其余进程执行时，只把当前需要页装入内存（实页），其余页暂留外存（虚页），当进程访问虚页时，产生缺页中页暂留外存（虚页），当进程访问虚页时，产生缺页中止，再由系统动态装入。止，再由系统动态装入。v动态页式管理实现了虚拟存放器。动态页式管理实现了虚拟存放器。第42页页式地址表示页式地址表示 页大小应取2整数次方幂。比如：一个8个页面（页面大小为1024字节）组成逻辑地址装入到32个物理块存放器中。则：（1）逻辑地址需要10+3=13位 （2）物理地址需要10+5=15位23210页式地址由页号页式地址由页号P和页内地址和页内地址d两部分组成：两部分组成：23=825=32第43页页式地址转换举例页式地址转换举例设页长为设页长为1K虚拟地址虚拟地址虚拟地址虚拟地址 09c4H=2500页页表表21c4H=8644物理地址物理地址物理地址物理地址l8l2l3l1l2l0l块号l页号0000 1001 1100 01000010 0001 1100 0100(1)步步地址表示地址表示(3)步步拼接地址拼接地址(2)步步查页表查页表第44页 页面调度算法页面调度算法1.1.随机数淘汰页面算法随机数淘汰页面算法2.2.轮转法（轮转法（RRRR法）法）3.3.先进先出算法先进先出算法(FIFO(FIFO算法算法)4.4.最近最久未使用页面淘汰法最近最久未使用页面淘汰法 (LRU(LRU算法算法)5.5.最不经常使用页面淘汰法最不经常使用页面淘汰法(LFU(LFU算法算法)6.6.最近没有使用页面淘汰法最近没有使用页面淘汰法(NUR(NUR算法算法)7.7.理想型淘汰法理想型淘汰法(OPT(OPT算法算法)第45页9.9.用用FIFOFIFO算法计算缺页中止率算法计算缺页中止率 产生缺页中止 F=10次。缺页中止率f10/1376.9。设问页次序为：7、0、1、2、0、3、0、4、2、3、0、3、2系统分配3个块，采取FIFO算法计算缺页中止率。第46页10.10.采取采取LRULRU算法计算缺页中止率算法计算缺页中止率 设问页次序为：7、0、1、2、0、3、0、4、2、3、0、3、2 系统分配3个内存块,采取LRU算法计算缺页中止率。产生缺页中止9次。缺页中止率f9/1369.2。第47页知识重点知识重点第第8章章文件管理文件管理第48页1.文件系统文件系统文件系统：文件系统：操作系统中与管理文件相关软件和数据。负责文件建立、撤消、读写、修改、复制等，并完成对文件按名存取，方便用户使用。特点：特点：含有友好用户接口；对文件按名存取，对用户透明；提供对文件共享保护功效；有大容量存放设备。第49页2.2.文件逻辑结构文件逻辑结构 流式文件 文件是无结构依次存放字符流。统计式文件 文件是有结构相关逻辑统计组成。第50页3.文件存取方法文件存取方法(1)次序存取法 按文件逻辑地址次序存取。(2)直接存取法 按文件逻辑统计编号随机存取统计。(2)按键存取法 依据键名搜索统计逻辑位置，再转换成对应物理地址存取。第51页4.4.文件物理结构（文件物理结构（1 1）（1）连续文件 文件信息依次存放到物理设备上相邻物理块中。特点 管理简单，存取速度快；不便于对文件动态扩从；存放空间利用率低。第52页4.4.文件物理结构（文件物理结构（2 2）（2）串联文件 文件信息用指针存放到物理设备上非连续物理块中。特点 存放空间利用率高；便于对文件动态扩充；只能次序存取，速度慢；指针增加额外空间开销，可靠性低。第53页4.4.文件物理结构（文件物理结构（3 3）（3）索引文件 文件信息经过索引表存放到物理设备上非连续物理块中。特点 存放空间利用率高；便于对文件动态扩充；可次序、直接存取，存取速度快；索引表增加空间开销。第54页5.5.文件存放空间管理文件存放空间管理(1)空闲文件目录表(2)空闲块链表法(3)位示图第55页6.文件目录文件目录 文件目录是文件系统实现对文件“按名存取”依据。包含内容：标识信息；结构信息；管理信息；控制信息。组织结构：(1)一级目录 简单，文件不能同名。(2)二级目录 文件可同名，搜索快，便于共享。(3)树型目录 文件可同名，搜索快，结构清楚第56页知识重点知识重点第第9章章设备管理设备管理第57页1.设备分类设备分类（1）独占设备：一次只能给一个进程使用低速设备。如：打印机、键盘等。（2）共享设备：允许多个进程同时使用高速设备。如：内存放器、磁盘等。（3）系统设备：OS生成时就已配置好标准设备。如：键盘、软盘机等。（4）用户设备：由用户安装、由OS管理非标准设备。如：一些显示器、光驱等。第58页2.数据传送控制方式数据传送控制方式设备和CPU之间数据传送有4 4种控制方式 (1)程序直接控制方式 (2)中止控制方式 (3)DMA控制方式 (4)通道控制方式第59页3.3.中止概念中止概念中止 指计算机在执行期间，系统中发生任何非寻常或预期急需处理事件，使得CPU暂时中止当前正在执行程序而转去执行对应事件处理程序，待处理完成后又返回原来被中止处继续执行或调度新进程执行过程。（计算机与外部设备进行信息交换一个方式）（计算机与外部设备进行信息交换一个方式）中止技术由硬件、软件共同协作完成：硬件：产生中止源、发出中止信号、开/关中止。软件：处理中止事件。第60页4.缓冲及引入目缓冲及引入目缓冲区：内存与外设交换信息时，I/O前后暂时存放数据内存区域。是提升CPU与外设并行工作能力技术。引入缓冲目标 为了匹配外设与CPU速度；为了降低中止次数及中止处理时间；为了处理通道或DMA方式下“瓶颈”问题。缓冲技术：单缓冲 双缓冲 多缓冲 缓冲池第61页5.通道技术通道技术通道通道是一个用来控制外部设备工作硬件机制，相当于一个功效简单处理机。通道是独立于CPU专门负责数据输入输出工作处理机，它对外部设备实现统一管理，代替CPU对I/O操作进行控制，从而使I/O操作能够与CPU并行工作。通道是实现计算和传输并行基础，以提升整个系统效率。第62页练习题练习题一、选择题一、选择题（本大题共有本大题共有12个小题，每小题个小题，每小题2分，共分，共24分分）1.在多道程序系统中，（）作用是从就绪状态中挑选一个进程投入运行。A.作业调度 B.交换调度 C.进程调度 D.SPOOLING调度2.对操作系统文件系统而言，一个源程序、一批数据、一篇文章或一张图片等都能够被称为文件，只要它是（）。A连续分布在一片磁盘区域中信息集合 B采取链接方式连接起来多个磁盘块组成信息集合 C逻辑上含有完整意义信息集合 D属于同一个用户一个信息集合第63页3 3、在操作系统中，用户在使用在操作系统中，用户在使用I/OI/O设备时，通常采取设备时，通常采取（）。）。A.物理设备名 B.逻辑设备名 C.虚拟设备名 D.设备牌号 4 4、缓冲技术用于（缓冲技术用于（）。A扩充相对地址空间 B.提供主、辅存接口 C.提升设备利用率 D提升主机和设备交换信息 速度 第64页二、简答题二、简答题（本大题共有本大题共有5个小题，每小题个小题，每小题4分，共分，共20分分）1.在操作系统中为何要引入进程概在操作系统中为何要引入进程概念？它会产生什么样影响？念？它会产生什么样影响？2.什么是虚拟存放器，其特点是什么是虚拟存放器，其特点是什么？什么？第65页1.1.为了控制和协调各程序段执行过程中软、硬件为了控制和协调各程序段执行过程中软、硬件资源共享和竞争，显然，必须应该有一个描述资源共享和竞争，显然，必须应该有一个描述各程序段执行过程和共享资源基本单位。从上各程序段执行过程和共享资源基本单位。从上述讨论能够看出，因为程序次序性、静态性以述讨论能够看出，因为程序次序性、静态性以及孤立性，用程序段作为描述其执行过程和共及孤立性，用程序段作为描述其执行过程和共享资源基本单位既增加操作系统设计与实现复享资源基本单位既增加操作系统设计与实现复杂性，也无法反应操作系统所应该含有程序段杂性，也无法反应操作系统所应该含有程序段执行并发性、用户随机性，以及资源共享等特执行并发性、用户随机性，以及资源共享等特征。也就是说，用程序作为描述其执行过程以征。也就是说，用程序作为描述其执行过程以及共享资源基本单位是不适当。需要有一个能及共享资源基本单位是不适当。需要有一个能描述程序执行过程且能用来共享资源基本单位。描述程序执行过程且能用来共享资源基本单位。这个基本单位被称为这个基本单位被称为进程进程（或任务）。（或任务）。答案：答案：第66页定义进程定义进程：一个含有独立功效程序一个含有独立功效程序对某个数据集在处理机上执行过程对某个数据集在处理机上执行过程和分配资源基本单位。和分配资源基本单位。影响影响:使程序并发执行得以实施。使程序并发执行得以实施。第67页2.2.虚拟存放器：虚虚拟拟存存放放器器是是一一个个扩扩大大内内存存容容量量设设计计技技术术，它它把把外外存存作作为为计计算算机机内内存存放放器器后后援援。看看成成业业提提交交给给系系统统时时，首首先先进进入入外外存存，运运行行时时，只只将将其其中中相相关关部部分分装装入入内内存存，其其它它部部分分仍仍在在外外存存中中，当当运运行行过过程程中中需需要要用用到到不不存存在在内内存存信信息息时时，再再把把它它们们调调入入到到内内存存，以以确确保保程程序序正正常常运运行行。这这么么一一个个看看上上去去容容量量很很大大、但但实实际际上不存在大存放器，就被称为上不存在大存放器，就被称为“虚拟存放器虚拟存放器”。或者答：虚拟存放器是指含有请求调入功效和置换功效，能从逻虚拟存放器是指含有请求调入功效和置换功效，能从逻辑上对内存容量进行扩充一个存放器系统。在虚拟存辑上对内存容量进行扩充一个存放器系统。在虚拟存放器系统中，作业无需全部装入，只要装入一部分就放器系统中，作业无需全部装入，只要装入一部分就可运行。可运行。答案：答案：第68页或者答：或者答：虚拟存放器虚拟存放器是计算机系统内存管理一个技术。它使得应用程序认为它拥有连续可用内存（一个连续完整地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存放在外部磁盘存放器上，在需要时进行数据交换。第69页虚拟存放器特点：虚拟存放器特点：1.允许用户用比主存空间大多空间来访问主存。2.每次访问都要进行虚实地址转换。虚拟存放器管理由硬件（MMU，Memory Management Unit）和软件（操作系统）共同实现。第70页综合题：（本大题共有2个题，共16分）1.P1276-P127 图5.20 地址变换 2.P48 图3.6 进程状态与转换第71页