操作系统复习-张尧学.ppt

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