操作系统期末复习题赵伟华.doc

3学时(自学学时:6学时)1.1 操作系统概况v 操作系统的虚拟机观点操作系统是添加在硬件上的第一层软件,是对硬件功能的首次扩充和延伸.软件:系统软件和应用软件.系统软件用来管理计算机本身及应用软件;应用软件用来完成用户所要求的实际任务.硬件:指未配置任何软件的计算机.裸机又分为物理器件,微程序与机器语言三个层次.v 操作系统的资源管理观点资源分硬件资源和软件资源.硬件资源是计算机硬件系统的总和,包括中央处理机,主/辅助存储器,输入/输出设备等.软件资源是系统中各种程序和数据的总和,这些程序和数据均以文件的形式保存在计算机系统中.v 操作系统的用户服务观点操作系统是用户与计算机之间的一个接口.它为用户提供了两种使用操作系统的方式:命令方式,系统调用方式.命令方式:是指操作系统提供了一组联机,用户通过键盘或鼠标使用这些命令,并直接操纵计算机系统.系统调用方式:是指操作系统提供了一组系统调用,用户可在自己的程序中通过调用来相应的系统操纵计算机.v 定义操作系统:是计算机系统中的一个系统软件,用来管理和控制计算机系统中的软硬件资源,合理地组织计算机工作流程,提供用户和计算机之间的软件接口,方便用户使用计算机.v 操作系统目标目前存在着多种类型的操作系统,不同类型的操作系统其目标各有侧重.但一般来说都包括:方便性,有效性,可扩充性和开放性.v 操作系统的特征并发:指两个或两个以上事件在同一时间间隔内发生.共享:指系统中硬件和软件资源可为多个用户同时使用(互斥共享,同时访问)虚拟:指物理上的一个实体变成逻辑上的多个对应物.异步性:指内存中的多个进程均按照各自独立的,不可预知的速度向前推进.1.2 操作系统的形成和发展v 操作系统的历史操作系统的发展经历了以下几个阶段:手工存在阶段(无操作系统),脱机输入输出技术阶段,批处理技术阶段,多道程序设计技术阶段.1.3 操作系统的基本类型v 分类最常用分类方法(按照操作系统的用户服务方式分)主要有:多道批处理系统;分时系统;实时系统.其它操作系统还包括:通用操作系统,网络操作系统,并发操作系统,面向对象操作系统.v 多道批处理系统运行方式(了解)特征:多道性,无序性,调度性优缺点:优点:资源利用率高,系统吞吐量大.缺点:平均周转时间长,无交互能力.在设计批处理系统时,首先要考虑的是周转时间和系统的吞吐量.v 分时系统实现基本方法;设立时间片特性:多路性,独立性,及时性,交互性.响应时间:指从终端用户发出一条命令开始,到系统处理完这条命令并做出回答为止所需的最大时间间隔.影响响应时间的因素:系统开销,用户数目,时间片,信息对换量.改善响应时间的办法:一种可行的办法是减少信息对换量.而减少信息对换量可采用重入码技术和虚拟存储技术.设计分时操作系统时,首先要考虑的是交互性和响应时间.v 实时系统定义:是指系统对特定输入做出反应速度足以控制发出实时信号的对象的一种操作系统.实时系统的类型:1 实时控制系统;2 实时信息处理系统特征:多路性,独立性,及时性,交互性,高可靠性.设计实时操作系统时,首先要考虑的是实时性和可靠性.v 微机操作系统单用户单任务OS:只允许一个用户上机,且只允许用户程序作为一个任务运行.最具代表性的是CP/M和MS-DOS.单用户多任务OS:只允许一个用户上机,但允许将一个用户程序分为若干个任务,使它们并发执行.最具代表性的是OS/2和MS-WINDOWS.多用户多任务OS:允许多个用户通过各自的终端使用同一台主机,共享主机的各类资源,同时用户程序又可进一步分成几个任务,使它们并发执行.最具代表性的是UNIX OS.1.4 操作系统的服务与功能v 操作系统的服务操作系统公共服务类型:程序执行, I/O操作,文件系统管理,通信,资源分配,差错处理操作系统的服务方式:系统调用,系统程序.系统调用的类型:进程管理,设备管理,文件管理,信息维护和通讯五大类.v 操作系统功能从资源管理和用户接口的观点看,操作系统的基本功能为:处理机管理;存储管理;设备管理;信息管理(文件系统管理);用户接口.其中硬件资源为处理机,存储器和设备三类,软件资源为信息或文件(程序和数据的通称).v 用户接口命令接口:又分联机命令接口:为联机用户提供的,由一组键盘命令和命令解释程序组成;脱机命令接口:为批处理作业的用户提供,由一组作业控制语言JCL(job control language)组成.程序接口:是为用户程序在运行过程中访问系统资源而设定的,也是用户取得操作系统服务的唯一途径,由一组系统调用组成.图形接口v 处理机管理处理机管理功能可归结为进程管理,主要功能:进程控制;进程同步;进程通讯;进程调度.v 存储管理存储管理应具备的功能,为:内存分配;内存保护;地址映射;内存扩充.v 设备管理设备管理应具备的功能,为:缓冲管理;设备分配;设备处理;虚拟设备管理.v 文件管理文件管理的主要功能包括:文件存储空间管理;目录管理;文件读写管理;文件保护;文件系统的安全性;文件接口.1.5 操作系统结构v 分类从操作系统的内部结构来看,操作系统可分为三种主要类型:整体式系统(无结构);层次式系统;客户/服务器系统.v 整体式结构整个系统是一堆过程的集合,每一过程都有一个定义好的接口,包括入口参数和返回值,过程间可以相互调用而不受约束,UNIX的系统核心层是典型的没有层次的无结构型.v 层次式系统按照操作系统中模块的功能和相互依存关系把它们划分为若干个层次:最底层:OS对象;中间层:对对象进行管理和控制的软件集合;最高层:OS提供给用户使用的用户接口.v 客户/服务器系统在客户/服务器结构中,需要把操作系统的服务功能分为若干个服务器,而用户进程则称为客户进程.操作系统由微内核和核外服务器进程组成.微内核提供最基本的,最必要的服务,而OS的其他功能由运行在核外的服务器完成.主要优点:提高了系统的可靠性;适合于分布式系统中的应用.练习题:1:下面8个系统中,必须是实时操作系统的有个.1 计算机辅助设计系统;2 航空定票系统;3 过程控制系统;4 机器翻译系统;5 办公自动化系统;6 计算机激光照排系统;7情报检索系统;8导弹的制导系统2:在分时系统中为使多个用户能够同时与系统交互,最关键的问题是_,当用户数目为100时,为保证响应时间不超过2秒,此时时间片最大应为_.:A.计算机具有足够高的运行速度 B.内存容量应足够大 C.系统能及时地接收多个用户输入 D.能在一最短的时间内,使所有的用户都能运行 E.能快速地进行内外存交换 :A.10ms B.20ms C.50ms D.100ms E.200ms 3:OS/2操作系统是由_开发的,它属于_类操作系统;UNIX操作系统是由_推出的,它属于_类操作系统.,:A.IBM公司 B.Microsoft公司 C.Microsoft和IBM联合 D. Bell实验室,:A.单用户单任务 B.单用户多任务 C.多处理机 D.多用户多任务 4:分时系统形成和发展的主要动力是什么 5:操作系统中实现虚拟的关键技术是什么 并加以说明.6:设计实时环境的操作系统的主要困难是什么 7:一个分层结构操作系统有:i裸机; (用户; ( CPU调度和P,V操作; (文件管理; (作业管理; (内存管理; (设备管理; (命令管理等组成,请按层次结构的原则从内到外将各部分重新排列.8:操作系统是一种_.根据其服务对象,常用的单处理机操作系统可分为三种类型:允许多个用户在其终端上同时交互方式使用计算机的操作系统,称为_;允许多用户将若干个作业提交给计算机系统集中处理的操作系统称为_;在_的控制下,计算机系统能及时处理由过程控制反馈的数据,并做出响应;设计时,首先应考虑系统的_.: A.通用软件 B.应用软件 C.系统软件 D.操作的软件-: A.批处理操作系统 B.分时操作系统 C.实时操作系统 D.微机操作系统E.多处理机操作系统 F.分布式操作系统 G.网络操作系统: A.可靠性和灵活性 B.实时性和可靠性 C.优先权分配 D.时间片轮转 E.短作业优先 F.时间片加分配9:操作系统的基本特征有哪些 10:什么是操作系统 11:操作系统有哪几种基本类型 它们的主要特征有那些 12:分时系统的响应时间是什么 它与哪些因素有关 13:实时系统可分哪几类 14:多道程序和多重处理有何区别 参考答案:1解:1,2,3,7,82解:1 D ;2 B3解:1 c ; 2 b; 3 d; 4 d4答:主要动力是为了更好地满足用户的需要.主要表现在:1)缩短了作业的周转时间;2)提供人机交互能力;3)多个用户共享一台计算机.(批处理系统的主要推动力是不断提高系统的资源利用率和提高系统的吞吐量.)5答:是分时技术.例如,将一台物理处理机虚拟为多台逻辑上的处理机,是靠多道程序分时地使用同一台物理处理机来实现的.微观上,该处理机在每一时刻只运行一道程序,它们分时地运行;然而在宏观上,系统中确有几道程序在同时运行,从而给用户的感觉是系统中同时同时有多台处理机在为其中的每一道程序服务,显然用户所感觉到的处理机并不实际存在.6答:是在实时环境规定的时间限额内对用户作出相应的反应,否则就有可能导致系统的崩溃.因此,在设计时必须保证所采用的调度策略及相关技术不会使响应时间超过实时环境所规定的时间限额.7答:重新排列后顺序为:(裸机; ( CPU调度和P,V操作; (内存管理; (作业管理; (设备管理; (文件管理; (命令管理.8 解:C B A C B9 答:1 并发:指两个或两个以上事件在同一时间间隔内发生;2 共享:指系统中硬件和软件资源可为多个用户同时使用(互斥共享,同时访问);3 虚拟:指物理上的一个实体变成逻辑上的多个对应物;4 异步性:指内存中的多个进程均按照各自独立的,不可预知的速度向前推进.10 答:操作系统是计算机系统中的一个系统软件,用来管理和控制计算机系统中的软硬件资源,合理地组织计算机工作流程,提供用户和计算机之间的软件接口,方便用户使用计算机.11 答;操作系统的基本类型有:1 多道批处理系统;2 分时系统;3 实时系统.其中多道批处理系统的特征:多道性,无序性,调度性;分时系统的特征:多路性,独立性,及时性,交互性.实时系统的特征:多路性,独立性,及时性,交互性,高可靠性.12 答:分时系统的响应时间指从终端用户发出一条命令开始,到系统处理完这条命令并做出回答为止所需的最大时间间隔.它与下列因素有:系统开销,用户数目,时间片,信息对换量.13 答:实时系统的类型:1 实时控制系统;2 实时信息处理系统14 答:多道程序multiprogramming是作业之间自动调度执行,共享系统资源,并不是真正地同时执行多个作业;而多重处理multiprocessing系统配置多个CPU,能真正同时执行多道程序.要有效使用多重处理,必须采用多道程序设计技术,而多道程序设计原则上不一定要求多重处理系统的支持.第二章 用户接口教学内容1. 作业的基本概念2. 用户接口概述3.命令接口4.程序接口5.图形接口教学要求了解作业的基本概念;了解操作系统提供给用户的接口类型及各种接口的实现方法;熟悉命令接口在不同工作方式下的主要功能,作业和作业管理的基本概念;掌握系统调用的定义及其执行过程.自学要点重点是作业的基本概念和建立;用户接口的概念和类型;系统调用的概念和过程学时分配3学时(自学学时:6学时)2.1 作业的基本概念v 作业作业(Job)是用户提交给计算机进行加工的一个任务,由三部分组成,即程序,数据及作业说明书.通常一个作业又可分为若干个顺序处理的作业步,其中每个作业步又可细分为若干个作业步任务.v 作业的类型根据调度和控制的需要,可对作业进行分类.从调度的角度,可把作业分成:计算型作业,指任务中包含大量的计算,而其I/O较少的作业,如通常的科学计算;I/O 型作业,要求少量的计算而需大量I/O的作业,如通常的事务处理.从控制的角度,可把作业分成:脱机作业,在整个作业的运行过程中,只需根据作业说明书中的说明对作业进行控制,脱机作业通常是在批处理操作环境下运行,故也称为批量型作业;联机作业,通常是用键盘命令直接控制作业的运行,联机作业通常在分时操作环境下运行,故也称为终端型作业.v 作业的建立过程一个作业的建立过程包括两个子过程,即作业的输入方式和JCB的建立.作业的输入指将作业的程序,数据和作业说明书从输入设备(如键盘)输入到外存,并形成有关的初始信息.其输入方式主要有:联机输入方式脱机输入方式直接耦合方式SPOOLing系统网络输入方式.v 作业的组织程序,数据和作业说明书.程序和数据完成用户所要求的业务处理工作的具体内容,作业处理的说明是用户要求计算机所作的步骤.v 作业的状态及其转换作业从提交给系统直到它完成后离开系统前的整个活动过程,可分为:提交状态;后备状态;运行状态;完成状态.2.2 用户接口概述操作系统是用户和计算机之间的接口,用户通过操作系统的帮助可以快速,有效和安全可靠地使用计算机各类资源.通常操作系统为用户控制其作业提供命令接口,程序接口和图形接口.2.3 命令接口v 命令接口命令接口是操作系统为用户提供的各种操作命令,用户利用它来组织作业的工作流程和控制作业的运行.类型有:脱机命令接口;联机命令接口.v 脱机命令接口脱机命令接口是操作系统为脱机工作方式下的用户提供的一种接口.利用JCL语言将用户对作业的控制要求写成作业控制卡或作业说明书的形式.JCL:作业控制语言,是一种用来表达申请作业控制意图和步骤的语言.JCL的语句就是作业控制命令.不同批处理提供不同的JCL.v 联机命令接口联机命令接口指用户通过控制台或终端,采用人机会话的方式,直接控制作业的运行.又分为:1 键盘命令方式;2 命令文件方式.键盘命令方式:是通过逐条输入键盘命令语句,经解释后执行,以控制作业运行的一种方式,通常包括:1 系统管理;2 环境设置;3 编辑修改,编译,连接和运行命令;4 文件管理命令;5 操作员专用命令(执行权限管理);6 通信;7 资源要求.命令文件方式:是用键盘命令语言编写的一个键盘命令语言程序命令文件.一旦建立命令文件后,系统可连续执行若干条命令并且可以多次重复执行.命令文件中可以进行参数传递,也可以嵌套的方式调用其他的命令文件.2.4 程序接口(系统调用)v 程序接口程序接口是OS专门为用户程序设置的,也是用户程序取得OS服务的唯一途径,程序接口通常由各种各样的系统调用所组成.v 系统调用系统调用的基本概念:是OS提供给编程人员的唯一接口,是由操作系统中的一段程序来完成特定功能的,属于一种特殊的过程调用.有的计算机系统中,把它称为广义指令.调用的方式:采用访管方式来实现.通过产生一个访管中断,使处理机由目态(用户态)转为管态(系统态).(当中央处理器处于目态时不允许执行特权指令;而处于管态时可这些包括特权指令在内的一切机器指令)常用的访管指令的形式:SVC Nv 系统调用与一般过程调用的主要区别系统调用本质上一种过程调用,但它是一种特殊的过程调用,主要区别有: 运行状态不同:一般的过程调用,其调用和被调用过程或者都是子程序,或者都是系统程序,故运行在同一系统状态下:系统态或用户态.系统调用的调用过程是用户程序,它运行在用户态;其被调用过程是系统过程,运行在系统态下. 进入的方式不同:一般过程调用可以直接通过过程调用语句将控制转移到被调用的过程;而执行系统调用时,由于调用和被调用过程处于不同的系统状态,必须通过访管中断进入. 代码层次不同:一般的过程调用中的被调用程序是用户级程序,而系统调用是操作系统中的代码程序,是系统级程序.v 系统调用的实现过程用户在源程序中使用系统调用,给出系统调用名和函数后,即产生一条相应的陷入指令,通过陷入处理机制调用服务,引起处理机中断,然后保护处理机现场,取系统调用功能号并寻找子程序入口,通过入口地址表来调用系统子程序.执行完毕后,退出中断,返回到用户程序的断点,恢复现场,继续执行用户程序.2.5 图形接口v 图形用户接口图形用户接口的引入:主要是在使用命令接口时,要求用户熟悉并记住系统所提供各种命令的名称,功能和格式;此外还要求用户按照规定的格式准确的键入,这不仅不方便,而且需花费较多的时间;同时利用命令接口来进行文字处理,图形的绘制和编辑也是极为不便的.图形用户接口元素:窗口;图标;菜单;对话框图形用户接口元素的基本操作:菜单操作;窗口操作;对话框操作.练习题:1:在分时系统中是否应设置作业调度 为什么 实时系统呢 2:为什么说SPOOLING对批处理(多道程序)是必需的 对分时系统也是需要的吗 3:作业控制方式可分为两种,它们是_,_.-: A.命令方式 B.程序方式 C.联机方式 D.脱机方式 E.后备方式 F.执行方式 G.批量方式 H.调用方式4:用户作业被SPOOLing系统输入到外存时,称此作业处于_,在外存后备队列上的作业处于_,作业在内存处于_.-: A.进入状态 B.运行状态 C.完成状态 D.后备状态 E.就绪状态 5:什么是作业 6:操作系统为用户提供哪些接口 7:什么是系统调用 系统调用与一般过程的区别 8: 作业由哪几部分组成 各有什么功能 9:简述系统调用的实现过程 10:什么是作业 作业步 11:试述SPOOLING系统的工作原理 参考答案:1答:分时系统最重要的目标是实现人机交互,因此系统中所有的作业都是由用户从键盘终端直接输入到内存,从而保证在一较短的时间内,各终端作业都能被处理.如果将终端作业先送到外存输入井上再等待作业调度后,才将作业调入内存,则既不能保证人机交互的及时性,又显然是多此一举,故在分时系统中没有作业控制表,不需设置作业调度.在实时系统中,由于实时任务往往是其实时性更高的任务,它们一般常住内存,因而也不需要作业调度. 2答:是.理由是它允许事先从输入设备上读入信息并将输出文件暂存于输出设备中,直到输出设备准备接收它们为止.由于许多作业可能同时到达,所以,CPU将一个作业的计算与其他作业的I/O操作并发执行.分时系统则不需要.理由是每个事务通常较短,而且输出信息一般直接输出到打印设备上.3 解:C ,D4 解:A ,D ,B5 答:作业(Job)是用户提交给计算机进行加工的一个任务,由三部分组成,即程序,数据及作业说明书.6 答:命令接口(又分脱机命令接口;联机命令接口);程序接口(即系统调用),图形接口.7答:系统调用的基本概念:是OS提供给编程人员的唯一接口,是由操作系统中的一段程序来完成特定功能的,属于一种特殊的过程调用.主要区别:运行状态不同:一般的过程调用,其调用和被调用过程或者都是子程序,或者都是系统程序,故运行在同一系统状态下:系统态或用户态.系统调用的调用过程是用户程序,它运行在用户态;其被调用过程是系统过程,运行在系统态下.进入的方式不同:一般过程调用可以直接通过过程调用语句将控制转移到被调用的过程;而执行系统调用时,由于调用和被调用过程处于不同的系统状态,必须通过访管中断进入.代码层次不同:一般的过程调用中的被调用程序是用户级程序,而系统调用是操作系统中的代码程序,是系统级程序.8 答:程序,数据和作业说明书.程序和数据完成用户所要求的业务处理工作的具体内容,作业处理的说明是用户要求计算机所作的步骤.9 答:用户在源程序中使用系统调用,给出系统调用名和函数后,即产生一条相应的陷入指令,通过陷入处理机制调用服务,引起处理机中断,然后保护处理机现场,取系统调用功能号并寻找子程序入口,通过入口地址表来调用系统子程序.执行完毕后,退出中断,返回到用户程序的断点,恢复现场,继续执行用户程序.10答:作业是用户提交给计算机进行加工的一个任务,由三部分组成,即程序,数据及作业说明书.作业由不同顺序相连的作业步组成.作业步是在一个作业的处理过程中,计算机所做的相对独立的工作.11答:当用户提交一批作业后,操作员键入预输入命令启动预输入程序工作,预输入程序启动输入机读出作业信息,并把它们存放到输入井中.当主存储器可以装入作业时就从输入井中选择若干作业装入主存储器.被装入主存储器中的作业在执行中可请求井管理程序从输出井读需处理的信息或把处理结果写到输出井中.缓输出程序利用处理器空闲时间把作业执行结果在打印机上输出.第三章 进程管理教学内容1. 进程的基本概念2. 进程的实现3.进程控制4.进程的同步与互斥5.利用信号量机制解决经典进程同步问题6.进程通信7.线程的概念教学要求了解引入进程的原因,进程控制的方法;熟悉进程的基本状态及变迁,进程控制块和组织,信号量和P,V原语,进程通信的类型和方法;掌握用信号量机制解决各种互斥同步问题的方法.自学要点进程的基本概念,描述,基本状态及其转换;原语及其执行特点,进程控制原语的工作流程;临界区,信号量并发进程间的制约方式及原因.重点为信号量和P,V原语,并能解决一些各种同步互斥以及前趋图等实际问题.学时分配9学时(自学学时:18学时)3.1 进程的基本概念v 进程的引入 程序的顺序执行程序的顺序执行指一个具有独立功能的程序独占处理机直到得到最终结果的过程.具有:顺序性,封闭性和可再现性. 程序的并发执行程序的并发执行指一组在逻辑上相互独立的程序或程序段在执行过程中其执行时间在客观上互相重叠.程序的并发执行增强了计算机系统的处理能力和提高了资源的利用率.具有:间断性,失去了封闭性及不可再现性.例1:Int n=0程序 A条件为真1 n=n+1;程序A的其余部分程序B条件为真1 print(n);2 n=0;程序B的其余部分讨论可能出现的结果(三种情况:A1,B1,B2; B1,A1,B2; B1,B2,A1)v 程序并发执行的Bernstein条件定义有关程序的读集和写集R(Pi)=a1,a2,am,用来表示程序Pi在执行期间所需引用的变量集合,称为Pi的读集.W(Pi)=a1,a2,am,用来表示程序Pi在执行期间所需改变的变量集合,称为Pi的写集.Bernstein条件:若两个程序P1和P2能满足下述条件, R(P1)W(P2)UR(P2)W(P1)UW(P1)W(P2)= 它们便能并发执行,否则不能.例2:有四条语句:S1: a=x+yS2: b=z+1S3: c=a-bS4: w=c+1R(s1)=x,y,W(S1)=aR(s2)=z,W(S2)=bR(s3)=a,b,W(S3)=cR(s4)=c,W(S4)=wS1和S2能满足Bernstein条件,所以能并发执行;而对于S1和S3不能满足Bernstein条件,因为R(S3)W(S1)=a,所以不能并发执行.同理,S2和S3,S3和S4也不能并发执行.前趋图为:S1 0 S3 S40S2 v 前趋图前趋图是一个有向无循环图,图中每个结点可表示一个语句,一个程序段或一个进程,结点间的有向边表示结点之间的前趋关系.几个概念:1 直接前趋;2 直接后继;3 初始结点;4 终止结点 v 进程的定义和特征v 进程的定义进程的概念是60年代初期,首先在MIT的Multics系统中引入的,进程的定义有很多种.其中一种为进程是可并发执行的程序在一个数据集合上的运行过程.v 进程的特征进程具有五个基本特征,而程序则没有.具体为: 动态性.进程的实质是程序的一次执行过程, 因此动态性是进程的最基本特征.它还表现为有生命周期的,即由创建而产生,有调度而执行,由撤消而消亡.而程序只是一组有序指令的集合,是静态的. 并发性.指多个进程能在一段时间内同时运行,并发性是进程的重要特性.引入进程的目的也正是为了使其程序能和其它进程的程序并发执行. 独立性.指进程是一个能独立运行,独立分配资源和独立调度的基本单位,凡未建立进程的程序,都不能作为一个独立的单位参加运行. 异步性.指进程按各自独立的,不可预知的速度向前推进, 即按异步的方式运行.( 结构特征.从结构上看,进程是由程序段,数据段及进程控制块(PCB)三部分组成,这也是进程的静态描述.PCB是操作系统中最重要的数据结构, 它存放了操作系统所需的,用于描述进程情况和控制进程运行所需的全部信息,是进程存在的唯一标志.v 作业和进程的关系 作业是用户向计算机提交任务的任务实体.在用户向计算机提交作业之后,系统将它放入外存中的作业等待队列中等待执行;而进程则是完成用户任务的执行实体,是向系统申请分配资源的基本单位. 一个作业可由多个进程组成,且必须至少由一个进程组成,反之不然. 作业的概念主要用在批处理系统中,而进程的概念则用在几乎所有的多道系统中.v 进程的基本状态及其转换由进程运行的间断性,决定了进程至少具有下述三种状态: 就绪状态.当进程已分配到除CPU以外的所有必要资源后,只要能再获得处理机,便能立即执行所处的状态.一个系统中,可以有多个进程同时处于就绪状态,通常将它们排成一个队列,称为就绪队列. 执行状态.指进程已获得处理机,其程序正在执行.在单处理机系统中,只能有一个进程处于执行状态. 等待(阻塞)状态.进程因等待某事件而暂停执行时的所处的状态.通常将处于等待状态的进程排成一个队列,称为等待队列.进程状态的转换及原因 就绪执行:调度; 执行等待:等待某个事件发生而睡眠; 等待就绪:因等待的时间发生而唤醒; 执行就绪:时间片用完.v 新状态和终止状态新(New)状态:是一个进程刚刚建立,但还未将它送入就绪队列时的状态).终止(Terminated)状态:当一个进程已经正常结束或异常结束,OS已将它从就绪队列中移出,但尚未将它撤消时的状态.新就绪状态:当就绪进程能够接纳新进程时,OS就把处于新状态的进程移入就绪队列.执行终止状态:当一个进程已经完成或发生某事件(地址越界等)而异常终止时,进程将由执行转为终止状态.3.2 进程的实现v 进程的结构描述进程由三部分组成,即PCB,有关程序段和该程序段对其进行操作的数据结构集.各部分的作用: 进程控制块:用于描述进程情况及控制进程运行所需的全部信息. 程序段:是进程中能被进程调度程序在CPU上执行的程序代码段. 数据段:一个进程的数据段,可以是进程对应的程序加工处理的原始数据,也可以是程序执行后产生的中间或最终数据.v 进程控制块进程控制块PCB:是OS中最重要的数据结构,用于描述进程情况及控制进程运行所需的全部信息.系统根据PCB感知进程的存在和通过PCB中包含的各项变量的变化,掌握进程所处的状态以达到控制进程活动的目的,是进程存在的唯一标志.其基本内容是:有关进程的描述信息;控制信息;资源管理信息;CPU现场保护结构.PCB是有一定的生命期的.在创建一个进程时,应先创建PCB;然后才能根据PCB的信息对进程管理和控制;进程结束时,回收PCB,进程也随之消亡.在一个系统中,系统进程加上用户进程,进程数可达数十百个,为了有效的管理,应将它们组织起来.常用的组织方式有:链接方式;索引方式.3.3 进程控制v 进程控制机构进程控制主要任务:对进程生命期控制及实现进程状态的转换,是由操作系统内核中相应程序实现的.处理机的执行状态:系统态,用户态.系统态(核心态或管态),具有较高的特权,能执行一切硬件指令,访问所有寄存器和内存储器.用户态(目态),具有较低特权的执行状态,只能执行规定的指令,访问指定的寄存器和内存储器.操作系统内核:OS的内核通常运行在系统态,是计算机硬件扩充的第一层软件,主要是一些与硬件密切相关的模块,常驻内存.内核的功能:1支撑功能;中断处理,时钟管理,原语操作.2资源管理功能:进程管理,存储器管理,设备管理.原语:是OS系统内核中由若干条指令构成,用于完成特定功能的一个过程.与一般过程的区别:它们是原子操作.原子操作:一个操作中的所有动作,要么全做,要么全不做.即是一个不可分割的操作,是不可中断的.v 进程控制原语是对进程生命期控制和进程状态转换的原语,目的是达到多进程高效率并发执行和协调,实现资源共享.主要有:创建原语;撤消原语;阻塞原语;唤醒原语.v 进程创建原语创建方式:由系统程序模块统一创建;由父进程创建.进程图:用于描述进程家族关系的有向树.(了解父进程,子进程,祖父进程,祖先等概念)引起创建进程的典型事件:1用户登录;2作业调度;3提供服务;4应用请求;进程创建的步骤:1申请空白PCB;2为新进程分配资源;3初始化PCB;4将新进程插入就绪队列;5将新进程插入进程家族或进程链.v 进程撤消原语引起进程撤消的事件:1正常结束;2异常结束;(指在进程运行期间,由于出现某些错误和故障迫使进程终止,如越界错误,I/O故障等)3外界干预;(指进程应外界的请求而终止运行,这些干预有:操作员或OS干预;父进程请求;父进程终止)进程撤消过程:1根据被撤消进程的标识符,从PCB集合中检索出该进程的PCB,读出其状态;2若为执行状态,应立即终止其执行,并在其撤消后应重新调度,选择一新进程,把处理机分配给它;3若该进程有子孙进程,还应将其所有的子孙进程预以撤消,以防成为不可控;4将该进程全部资源,归还父进程或系统;5释放撤消进程的PCB结构本身.v 进程阻塞和唤醒原语引起进程阻塞和唤醒的事件:1请求系统服务;2启动某种操作;3新数据尚未到达;4无新工作可做;Block原语和Wakeup原语是一对作用刚好相反的原语.一般来说,如果某进程调用了阻塞原语,则必须在与之合作的另一进程或相关进程中,调用唤醒原语;否则被阻塞进程将会因不能被唤醒而长久处于阻塞状态,从而再无机会运行.进程阻塞过程:(这是进程自身的一种主动行为)1因进程处于执行状态,故应先中断处理机和保存该进程的CPU现场;2将进程的状态有执行改为阻塞;3将阻塞进程插入到阻塞(等待)队列;(若系统中设置了因不同事件而阻塞的多个阻塞队列,则应将进程插到具有相同事件的阻塞队列)4转进程调度;(防止处理机空转,而出现资源浪费)进程唤醒过程:1从阻塞(等待)队列中摘下需被唤醒的进程;2将其PCB的现行状态,由阻塞改为就绪;3并将该进程插入到就绪队列;4转进程调度或返回;3.4 进程的同步与互斥v 主要任务进程的同步和互斥机制的主要任务:控制并发执行的诸进程之间能有效地共享和相互协作,同时使并发执行的程序仍具有可再现性.v 进程互斥并发系统中诸进程由于资源共享,进程合作,而产生进程之间的相互制约;又因共享资源的方式不同,而导致两种不同的制约关系:间接相互制约.这种制约主要源于资源共享(进程互斥);直接相互制约.这种制约主要源于进程合作(进程同步).临界资源:一次仅允许一个进程访问的资源.临界区:每个进程中访问临界资源的那段代码.(不允许多个并发进程交叉执行的一段程序)进程互斥:不允许两个以上的共享该资源的并发进程同时进入临界区.同步机制的准则:空闲让进;忙则等待;让权等待;有限等待;例3:(与时间有关的错误)二个进程P1,P2共享变量 count(R1,R2是处理机中的寄存器):P1: R1=count; R1=R1+1; count=R1;P2: R2=count; R2=R2+1; count=R2; 结果应该count 增加了2,正确.但若执行顺序按P1,P2,P1,P1,P2,P2,虽然P1,P2各自对count进行了加1操作,但最后结果count仅增加了1.v 进程同步定义:指多个合作进程为了完成同一个任务,它们在执行速度上必须相互协调,即一个进程的执行依赖于另一个进程的消息,当没有消息时要等待,直到消息到达被唤醒.合作进程指具有同步关系的一组并发进程,合作进程间互相发送的信号称为消息或事件.进程同步和互斥间的关系同步互斥相似处:进程的互斥实际上是进程同步的一种特殊情况;进程的互斥和同步统称为进程同步.差别:进程互斥是进程间共享资源的使用权,这种竞争没有固定的必然联系,哪个进程竞争到使用权就归那个进程使用,直到不需要使用时在归还;而进程同步则涉及共享资源的并发进程间有一种必然的联系,当进程必须同步时,即使无进程在使用共享资源时,那么尚未得到同步消息的进程也不能去使用这个资源.v 利用信号量机制解决问题信号量机制:由Diskstra提出的一种解决进程的同步与互斥的工具.建立一个信号量必须经过说明所代表的意义,赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进程.信号量的值只能通过P,V原语操作来改变.记录型的信号量机制:是一个记录型的数据结构,包含两个数据项,一是记数值域,另一是等待该信号量的进程队列首指针域.描述如下:typedef struct semaphoreint value;PCB *p; v P(s)和V(s)操作原语void v(s)struct semaphore s;s.value=s.value+1;if (s.value=0) wakeup(s.p);void P(s)struct semaphore s;s.value=s.value-1;if (s.value0数值时,表示某类可用资源的数量.而当s.value0数值时,表示该类资源已分配完.若有进程请求该类资源,则被阻塞,其绝对值等于等待该类资源的进程数. 每次的P(s)操作,意味着进程请求分配该类资源的一个单位资源.相反,执行一次V(s) 操作意味着进程释放相应资源的一个单位资源.当值小于等于0时,表明有进程被阻塞,需要唤醒.v 用信号量解题的关键1 信号量的设置2 给信号量赋初值(常用的互斥和同步信号量值的大小)3 P,V操作安排的位置(其中,P的顺序不能颠倒,V的顺序任意)v 用信号量机制解决前趋图问题方法:若图中存在结点S1指向结点S2的有向边,表示进程P1中的程序段S1应该先执行,而进程P2中的程序段S2后执行.设置一个信号量s,初值为0,将V(s)放在S1后面,而在S2前面先执行P(s).进程P1的语句序列为:S1;V(s) 进程P2的语句序列为:P(s);S2 例4:(利用信号量机制解决前趋图问题)具有8个结点的前趋图.例子中的前趋图中共有有向边10条,可设10个信号量,初值均为0;有8个结点,可设计成8个并发进程,具体描述如下:struct semaphore a,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0cobegin a1;V(a);V(b);V(c);P(a);S2;V(d);P(b);S3;V(e);V(f);P(c);S4;V(g);P(d);P(e);S5;V(h);P(f);P(g);S6;V(i)P(h);P(i);S7;V(j);P(j);S8;coendv 利用互斥信号量实现二个进程互斥struct semaphore mutex=1cobegin void processA(void)while(TRUE)P(mutex);critical section A;V(mutex);Remainder section;void processA(void)while(TRUE)P(mutex);critical section A;V(mutex);Remainder section;coendv 利用信号量实现二个进程同步问题(计算进程和打印进程)struct semaphore sc,sp=1number x,y,buffer;cobegin void CP(void)while(TRUE)computer next numbe into x;P(sc);Buffer=x;V(sp);void pp(void)while(TRUE)P(sp);y=buffer;V(sc);Print y number;coendv 经典的进程同步问题例5:生产者消费者问题(一个最著名的进程同步问题)问题描述:一组生产者向一组消费者提供消息,它们共享一个有界缓冲池,生产者存入消息,消费者从中取得消息.struct semaphore s1,s2,empty,full=1,1,n,0;message buffern;int in,out=0,0;cobegin void produceri(void)(i=1,2,k) message x;while(TRUE)produce a new message into x;P(empty);P(s1);bufferin=x;in=(in+1) mod n;V(s1);V(full);void consumerj(void)(j=1,2,m) message y;while(TRUE)P(full);P(s2);y=bufferin;out=(out+1) mod n;V(s2);V(empty);consume message y; coend例6:读者写者问题问题描述:多个进程共享一个文件,其中只读文件的称为读者,其余只写文件的称为写者.读者可以同时读,但写者只能独立地写.(即是互斥的,一个进程在写的时候,其它进程即不能读,也不能写)struct semaphore mutex,wrt=1,1;int readcount=0;cobegin void readeri(void) (i=1,2,k) while(TRUE)P(mutex);if (readcount=0) then P(wrt);readcount:=readcount+1;V(mutex);perform read operation;P(mutex);Readcount:=readcount-1;if (readcount=0) then V(wrt);V(mutex);void writerj(void) (j=1,2,m) while(TRUE)P(wrt);perform write operation;V(wrt);coend例7:图书馆阅览室问题问题描述:假定阅览室最多可同时容纳100个人阅读,读者进入时,必须在阅览室门口的一个登记表上登记,内容包括姓名,座号等,离开时要撤掉登记内容.用P,V操作描述读者进程的同步算法. (解题分析:读者有任意多个,但进入阅览室阅读最多为100人,为此可设一个信号量s,代表空座位的数目;另登记表为临界资源,需设一个用于互斥的信号量mutex,防止2个及以上的读者进程同时对此表访问.对于每个读者的动作包括进入,阅读,离开.)struct semaphore s,mutex=100,1;cobegin void readeri(void) (i=1,2,k) while(TRUE)P(s);P(mutex);查登记表,置某座位为占用;V(mutex);reading;P(mutex);查登记表,置某座位为空;V(mutex);V(s);coend例8:吃水果问题问题描述:桌上有一只盘子,每次只能放一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子,儿子专等吃盘里的桔子,女儿专等吃盘里的苹果.只要盘子空,则爸爸或妈妈可向盘中放水果,仅当盘中有自己需要的水果时,儿子或女儿可从中取出,请给出四人之间的同步关系,并用PV操作实现四人正确活动的程序. 解:四人之间的关系:1爸爸,妈妈要互斥使用盘子,所以两者之间是互斥关系;2爸爸放的苹果,女儿吃,所以两者是同步关系;3妈妈放的桔子,儿子吃,所以两者也是同步关系.struct semaphore s,sp,so=1,0,0;cobegin void father (void) while(TRUE)have an apple;P(s);put an apple;V(sp);void mother (void) while(TRUE)have an orange;P(s);put an orange;V(so);void son (void) while(TRUE)P(sp);get an orange;V(s);eat an orange; void daught (void) while(TRUE)P(sp);get an apple;V(s);eat an apple;coend例9:司机售票员问题问题描述:设公共汽车上