版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
./《计算机操作系统》教案备课教师:晁妍职称:助教教学班级计科专业09级本科2班时间:2011年9月已教轮数:1计算机与信息学院2011-2012学年度第一学期课程教学目的及教学要求:本课程是计算机科学与技术专业的主要专业基础课和主干课。本课程的学习目的在于使学生掌握操作系统的基本概念、基本原理、设计方法和实现技术,具有初步分析实际操作系统的能力,为其今后在相关领域开展工作打下坚实的基础。教学时数与学时分配:共51学时,周学时:17,<分单双周,每次2个学时>章次标题教学手段学时数第一章操作系统引论4第二章进程管理12第三章处理机调度与死锁4第四章存储管理10第五章设备管理6第六章文件系统8第七章操作系统接口4第八章网络操作系统1第九章系统安全性1第十章UNIX系统内核结构1教材:《计算机操作系统》〔第三版汤小丹等推荐参考书:[1]《计算机操作系统》〔第二版汤子瀛等XX电子科技大学出版社[2]《计算机操作系统教程》张尧学史美林清华大学出版社[3]《UNIX教程》〔第2版〔美SyedMansoorSarwarRobertKoretsky张玉洁孟祥武译机械工业出版社[4]《计算机操作系统.学习指导与题解》梁红兵、汤小丹XX电子科技大学出版社[5]《操作系统实验指导—基于linux内核》徐虹编清华大学出版社.第1、2讲〔周次:第2周<注:线右侧写教学方法、实验演示、新增补内容、重要标注、时间分配等>教学章节:1.1操作系统的目标和作用〔简略1.2操作系统的发展过程〔每种OS的不足与各自特点教学目的及要求:目的:是使学生建立起OS的基本概念。要求:了解OS的引入和发展;理解多道程序设计技术;重点、难点:<注:重点和难点如果一致,则写在一起,若不同则应分开写>:OS引入和发展、OS的基本特征和功能。教学内容:板书设计见PPT。<注:内容每节课1-2页为宜>复习引入:首先说明对课程的成绩如何评定,提出学习要求,以及教材的使用并推荐参考教材。然后介绍本课程的特点、性质和目的,以及如何学习,最后对本课程内容以及课时分配做简单的介绍。新课讲授:操作系统在计算机系统中的地位:〔结合课件中图加以说明,由此引出目标和作用计算机系统由硬件和软件组成;操作系统在硬件基础上的第一层软件;是其他软件和硬件之间的接口。操作系统在计算机系统中占据着特别重要的地位,是计算机中最重要的系统软件,是其他系统软件和应用软件运行的基础。1.1操作系统的目标和作用操作系统的目标方便性<用户的观点>:提供良好的、一致的用户接口。无需了解许多有关硬件和系统软件的细节。有效性<系统管理人员的观点>:合理地组织计算机的工作流程,管理和分配硬件、软件资源,提高资源的利用率;提高系统的吞吐量。可扩充性<开放的观点>:操作系统必须能方便地开发、测试和引进新的系统功能,以适应计算机硬件和体系结构的迅速发展以及应用不断扩大的要求。给计算机系统的功能的扩展提供开放式的支撑平台。开放性:可移植性和互操作性其中有效性和方便性是设计OS时最重要的两个目标,设计现代OS的主要目标也是对提高资源利用率和方便用户。操作系统的作用1.从一般用户的观点来看,OS作为用户与计算机硬件系统之间的接口〔桥梁用户并不直接与计算机硬件打交道,而是通过操作系统提供的命令、系统功能调用以及图形化接口来使用计算机。2.从资源管理的观点来看,OS作为计算机系统资源的管理者〔管家处理机的分配和控制,内存的分配和回收,I/O设备的分配和处理,文件的存取、共享和保护工作都是由操作系统完成的。主要功能有:处理机管理、存储管理、设备管理、文件管理3.从虚拟机的观点来看,OS用作扩充机器〔实现了对计算机资源的抽象〔虚拟机或扩充机硬件处在最底层,不附加任何软件的物理计算机"裸机".操作系统是附加在裸机上的第一层,是对裸机的首次扩充,构成了一个比裸机更强,使用更方便的"虚拟计算机"。所有系统软件以及更上层的用户应用软件在操作系统虚拟机上运行,它们受操作系统的统一管理和控制,通过操作系统使用各种资源来完成特定的任务。引出OS的定义〔以提问的方式操作系统的定义:是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度,以及方便用户使用计算机的程序的集合。推动操作系统发展主要动力〔稍后补充1.2操作系统的发展过程〔介绍OS的引入与发展,以及推动发展的主要动力1.2.11.人工操作方式1946-50年代中:电子管时代〔第一代计算机,计算机速度慢,无操作系统,计算机资源昂贵;工作方式:用户:既是程序员又是操作员;用户是计算机专业人员;编程语言:机器语言;输入输出:纸带或卡片;计算机的工作特点:用户独占全机,资源利用率极低;CPU等待用户,计算前,手工装入纸带或卡片;计算完成后,手工卸取纸带或卡片;CPU利用率低;主要矛盾:人机矛盾人工操作严重降低了计算机资源的利用率提高效率的途径:脱机输入/输出技术。2.脱机输入/输出<Off-LineI/O>方式:脱机输入方式是指在一台外围机〔它是一台专门用来管理I/O的、功能较简单的计算机的控制下,预先将程序和数据从低速输入设备到磁带,当CPU需要这些程序和数据时,再从磁带高速地读入内存。类似地,脱机输出方式是指当CPU需要输出时,先高速地将数据写入磁带,然后在一台外围机的控制下,通过低速输出设备进行输出。相反,在主机的直接控制下进行的I/O方式被称为联机I/O方式。脱机I/O方式的主要优点:减少了CPU的空闲时间、提高I/O速度〔缓和了人机矛盾1.2.2单道批处理系统1.单道批处理系统处理过程晶体管时代〔第二代计算机批处理技术是在系统中配置一个监督程序,并在该监督程序的控制下,能够对一批作业自动进行处理的一种技术。把一批作业以脱机方式输入到磁带或磁盘上,并在系统中配上监督程序<Monitor>,在它的控制下使这批作业能一个接一个的连续处理。2.单道批处理系统的特征:自动性:无需人工干预。顺序性:作业完成的顺序与它们进入内存的顺序以及作业在磁带上的顺序一致。单道性:内存中仅能存放一道作业。不足:无法充分利用系统中的所有的资源1.2.3多道批处理系统1.多道程序设计技术是指在内存中同时存放若干个作业,使它们共享系统资源并同时运行的技术。在单处理机环境下,这些作业仅在宏观上同时运行,而在微观上交替执行。2.多道批处理系统采用多道程序设计技术的批处理系统被称作多道批处理系统。多道批处理系统中必须配置一组软件〔调度程序,来解决多道程序对系统资源的共享和争用问题,并对作业进行合理的组织和调度。外存〔后备队列——>作业调度——>内存〔共享CPU和系统中的各种资源就形成了现代意义上的OS3.具有的主要特征:〔与单道批处理的特征对比多道性:内存中可同时存放多个作业调度性:〔作业调度、进程调度需通过作业调度从外存中选取若干个作业装入内存,还需通过进程调度在内存的多个作业中分配CPU。无序性:作业调度的次序与作业在外存中次序无关,作业完成的次序与作业进入内存的次序也无关。4.多道批处理系统需解决的问题〔1多道程序对OS的基本要求存储管理--系统必须为若干作业分派空间CPU调度--系统必须在就绪作业中选择准备运行.设备分配—既方便用户使用,又能提高设备利用率.〔2多道批处理系统需解决的问题:处理机管理问题、内存管理问题、设备管理问题、文件管理问题、作业管理问题5.优缺点:优点:资源利用率高——CPU和内存利用率较高;系统吞吐量大——〔单位时间内所完成的总工作量缺点:平均周转时间长——〔从作业进入系统开始,直至其完成并退出系统为止所经历的时间,短作业的周转时间显著增长无交互能力——整个作业完成后或中间出错时,才与用户交互,不利于调试和修改;1.2.41.分时系统的产生引入:为了解决批处理系统无法进行人机交互的问题,并使多个用户〔包括远程用户能同时使用昂贵的主机资源,又引入了分时系统。分时系统:是指在一台主机上连接了多个带有显示器和键盘的终端,同时允许多个用户通过自己的终端,以交互方式使用计算机,共享主机中的资源。2.分时系统的设计思想〔1采用了分时技术:既把处理机的时间划分成很短的时间片〔eg,几百毫秒,轮流地分配给各个终端作业使用。〔若在分配给它的时间片内,作业仍没执行完,它也必须将CPU交给下一个作业使用,并等下一轮得到CPU时再继续执行〔2设计目标:系统能及时响应用户的终端命令〔3实现中的最关键问题:使用户能与自己的作业进行交互。〔及时接收、及时处理响应时间RT<responsetime>:从键盘命令进入<按下回车键为准>到开始在终端上显示应答的时间间隔.。在分时系统中,响应时间≈时间片×用户数.改变批处理系统的运行方式:作业直接进入内存系统采用时间片轮转方式处理服务请求4.分时系统的特征多路性:多个用户同时使用一台计算机,共享CPU和其他资源,充分利用系统资源。宏观上:是多个人同时使用一个CPU微观上:多个人在不同时刻轮流使用CPU独立性:用户感觉不到计算机为其他人服务,各用户独立操作,互不干扰。及时性:通过时间片技术和轮转调度算法保证及时响应。〔指用户能在很短的时间内获得系统的响应,是以人们所能接受的等待时间决定的,一般为2~3秒交互性:能进行广泛的人机交分时系统的关键问题是使用户能与自己的作业进行交互,或者说它追求的主要目标是系统能及时响应用户的终端命令。1.2.5引入:由于前几种操作系统都不能很好的满足在实时控制和实时信息处理领域的需要1.实时系统及其类型〔1实时系统是指系统能及时<或即时>响应外部事件的请求,在规定的时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。〔2可分成两大类:实时控制系统:通常使指以计算机为中心的生产过程控制系统和武器控制系统。这类系统要求实时采集现场数据,并对数据进行及时处理,进而自动地控制相应的执行机构。如工业自动控制、火炮自动控制、飞机自动驾驶、导弹制导等。实时信息处理系统:通常使指对信息进行实时处理的系统。这类系统要求及时接受从终端〔包括远程终端发来的服务请求,按请求的内容对信息进行检索和处理,并在很短的时间内为用户做出正确的回答。如飞机订票、情报检索等。2.实时任务的类型〔1按任务执行时是否呈现周期性来划分周期性实时任务非周期性实时任务——截止时间开始截止时间:某任务在某时间以前必须开始执行完成截止时间:某任务在某时间以前必须完成〔2根据对截止时间的要求来划分〔与截止时间联系的是否严格硬实时任务软实时任务3.三种基本操作系统的比较:多路性独立性及时性交互性可靠性批处理系统无无差差一般分时系统多终端服务有好好可靠实时系统多路采集、多路控制有最好一般高度可靠补充:推动批处理系统的形成与发展的主要动力:提高系统资源利用率;推动分时系统形成与发展的动力室方便是用户;推动OS发展的主要动力:计算机硬件的不断更新换代1.2.6微机OS的发展1.单用户单任务OS:只允许用户程序作为一个任务运行eg.CP/M、MS-DOS2.单用户多任务OS:允许用户把程序分为若干个任务,使它们并发执行eg.MS-Windows3.多用户多任务OS:允许多个用户通过各自的终端使用一台机器。eg.UNIX、LINUX教课小结:1、了解操作系统的目标,理解操作系统的作用,了解推动操作系统发展的主要动力2、了解无操作系统的计算机系统和单道批处理系统。理解多道批处理系统、分时系统和实时系统的特征和优缺点。预习要求:作业布置:1、作业:2、补充习题:<若没有可以删去>推荐参考书目、网站及阅读材料:<若没有可以删去>实验一:LINUX入门第3讲〔第3周<注:线右侧写教学方法、实验演示、新增补内容、重要标注、时间分配等>教学章节:1.3操作系统的特征1.4操作系统的主要功能1.5操作系统的结构设计教学目的及要求:1.掌握操作系统的功能和特征。2.了解分层式结构和微内核结构。重点、难点:<注:重点和难点如果一致,则写在一起,若不同则应分开写>OS的基本特征和功能。教学内容:板书设计见PPT。<注:内容每节课1-2页为宜>复习引入:上节课学习了OS的引论,介绍了OS的发展过程,其中主要功能小节也是对本书的简要的概括,需要同学们掌握。OS是系统软件,对于这种大型的软件,在开发的过程中,其软件的结构设计是怎么样的发展过程,下面就来学习:新课讲授:1.3操作系统的特征采用多道程序设计技术的现代操作系统具有如下四个基本特征:并发、共享、虚拟、异步。其中并发和共享是OS的两个最基本的特征。1.并发并行性:两个或多个事件在同一时刻发生并发性:两个或多个事件在同一时间间隔内发生在多道程序系统〔单处理器中,宏观上并行,微观上串行〔交替执行程序〔静态实体不能并发执行,为使多个程序并发执行,引入进程。进程——在系统中能独立运行并作为资源分配的基本单位,〔是活动实体。现代OS中还引入一个比进程更小的单位——线程,此时,一个进程中可包含若干个线程,资源分配的基本单位虽仍然是进程,但独立运行、独立调度和分配处理机的基本单位却是线程。2.共享在操作系统环境下,所谓共享是指系统中的资源可供内存中多个并发执行的进程<线程>共同使用共享方式:互斥共享方式:资源分配后到释放前,不能被其他进程所用,如打印机、变量、队列等。临界资源<独占资源>:一段时间内只允许一个进程访问的资源同时访问方式:在同一段时间内可以被多个作业同时访问。如可重入代码,磁盘文件。宏观并行微观串行。并发和共享是OS的两个最基本的特征,又互为存在的条件。3.虚拟〔是以并发和资源共享为前提虚拟——通过某种技术把一个物理实体变为若干个逻辑上的对应物。虚拟是操作系统管理系统资源的重要手段,可提高资源利用率。用于实现虚拟的技术,称为虚拟技术时分复用技术:虚拟处理机、虚拟设备技术〔分时使用方式空分复用技术:虚拟内存、虚拟磁盘技术4.异步性〔是并发与共享的必然结果指进程的执行顺序和执行时间的不确定性;指进程以人们不可预知的速度向前推进。进程的运行速度不可预知:多个进程并发执行,"时走时停",不可预知每个进程的运行推进快慢;无论快慢,结果应该相同。通过进程互斥和同步手段来保证;1.4操作系统的主要功能包括:处理机管理功能、存储器管理功能、设备管理功能、文件管理功能、用户接口1.4.1主要是对处理机的分配和运行进行管理。〔创建和撤销进程<线程>,对诸进程<线程>的运行进行协调,实现进程<线程>之间的信息交换,以及按照一定的算法把处理机分配给进程<线程>。主要功能包括:进程控制:为作业创建进程、撤销已结束的进程,以及控制进程在运行过程中的状态转换进程同步:为多个进程<含线程>的运行进行协调〔协调方式:互斥和同步进程通信:用来实现在相互合作的进程之间的信息交换;调度:作业和进程的状态切换,包括作业调度和进程调度存储器管理功能存储器管理为多道程序的运行提供良好的环境,方便用户使用存储器,提高存储器的利用率以及能从逻辑上扩充内存存储器管理功能有:内存分配:为每道程序分配内存空间,提高存储器的利用率,允许正在运行的程序申请附加的内存空间;存储保护:确保每道用户程序都只在自己的内存空间中运行,彼此互不干扰;地址映射<变换>:进程的逻辑地址到内存物理地址的映射。内存扩充:用虚拟存储技术解决内存容量不足的问题;请求调入功能页面置换功能设备管理功能设备管理的主要任务:完成用户进程提出的I/O请求,为用户进程分配其所需的I/O设备,提高CPU和I/O设备的利用率,提高I/O速度,方便用户使用I/O设备。设备管理的功能有:缓冲管理:匹配CPU和外设的速度,提高两者的利用率和并行操作程度;设备分配:根据用户进程的I/O请求、系统的现有资源情况以及按照某种设备分配策略,为之分配其所需的设备;设备处理:设备驱动程序用于实现CPU和设备控制器之间的通信。设备独立性和虚拟设备:1.4.4文件系统管理的主要任务:对用户文件和系统文件进行管理,以方便用户使用,并保证文件的安全性。文件管理的功能有:文件存储空间的管理:为每个文件分配必要的外存空间,提高外存的利用率,并能有助于提高文件系统的运行速度;——解决如何存放信息的问题目录管理:为每个文件建立其目录项,并对众多的目录项加以有效组织,实现方便的按名存取,能实现文件共享,提供快速的目录查询手段。<通过目录方式来组织文件,以实现文件的按名存取>——解决信息检索问题文件的读/写管理和保护:实现文件的读写操作,并提供有效的存取控制功能,保护文件的安全性。——解决信息安全问题。OS与用户之间的接口1.用户接口〔提供给用户使用〔1命令接口:用户可通过该接口向作业发出命令以控制作业的运行。联机用户接口:由一组键盘操作命令和命令解释程序组成脱机用户接口:由一组作业控制语言JCL组成〔2图形接口:2.程序接口〔提供给程序员在编程时使用为用户程序在执行中访问系统资源而设置,由一组系统调用组成。1.5操作系统的结构设计操作系统的结构:整体式〔无结构、模块化结构、层次式结构、微内核结构1、整体式OS结构整体式系统是早期操作系统和一些较小的操作系统所采用的一种结构模型。整个系统是一堆过程的集合,每个过程都可以随便调用任意其它过程。采用这种结构的操作系统不仅调试和维护不方便,而且其可读性和可扩充性都较差。2、模块化OS结构〔关键问题:模块的划分和规定好模块之间的接口模块化程序设计技术,是基于"分解"和"模块化"原则来控制大型软件的复杂度的。将OS按其功能划分为若干个具有一定独立性和大小的模块。并规定好各模块间的接口,各模块之间能通过该接口实现交互。衡量模块独立性的两个标准:内聚性和耦合度。模块化OS结构优缺点优点:提高设计的正确性、可理解性和可维护性增强可适应性;加速开发过程缺点:模块的划分和接口的规定较困难模块间还存在着复杂的依赖关系,是os结构变得不够清晰。〔在模块化结构设计中,各模块的设计齐头并进,无法寻找到一个可靠的决定顺序,造成各种决定的"无序性"3、层次式结构为了将模块化中的"决定顺序"无序性变为有序性,引入了有序分层法,常采用自底向上法来铺设这些中间层。层次式结构是对模块化结构的一种改进。将一个操作系统分为若干个层次,每层又由若干个模块组成,各层之间只存在着单向的依赖关系,即高层仅依赖于紧邻它的底层。层次结构的优点:正确性有保证、便于系统维护、扩充层次结构的缺点:模块间需要通信机制、系统开销大、效率低在OS结构中,分层式结构是最为成熟的一种OS结构,而20世纪90年代兴起的微内核结构是最具有发展前途的OS结构。补充:分层式结构与模块式结构的主要区别在于:分层结构中各模块之间有序的。分层式结构将各个功能模块按它们的功能流图的调用次序安排成若干层,各层之间的模块不能像模块式结构那样通过接口毫无规则地相互依赖、相互调用,而只能是单向调用,即每层中的模块只能使用较低层模块提供的功能和服务。因此在分层结构中,模块间的组织结构和依赖关系更加清晰,这不仅增加系统的可读性,同时还使每一层建立在可靠的基础上,从而提高系统的可靠性。4、微内核OS结构微内核结构是指将C/S技术、面向对象技术用于基于微内核技术的OS中所形成的结构。微内核的主要思想是:在操作系统内核中只留下一些最基本的功能,而将其他服务尽可能地从内核中分离出去。内核的基本组成:中断处理、进程调度、同步机制用若干个运行在用户态下的进程〔即服务器进程来实现,形成所谓的"客户/服务器"模式。普通用户进程〔即客户进程可通过内核向服务器进程发送请求,以取得操作系统的服务。C/S技术把OS分为两个部分:一部分是用于提供各种服务的服务器另一部分是用于实现os最基本功能的内核,其全部工作是处理C与S之间通信。优点:易于扩充,易于移植、提高系统的可靠性、提供多种操作环境、适宜于分布计算模式、有助于多处理器系统的实现、支持实时任务缺点:消息传递方式增加开销,使响应变慢几个商品化系统:WindowsNT,NextStepXINU,OSF/11.3,WorkspaceOS,Chorus/MixV.4,acG3,QNX,CTOS举例:微内核的开放式系统环境、一个分布式系统中的客户服务器模型在现代OS的设计中,常常还融入面向对象的程序设计技术。面向对象技术,该技术是基于"抽象"和"隐蔽"原则来控制OS的复杂度。它利用被封装的数据结构和一组对数据结构进行操作的过程来表示系统中的某个资源,这样,可使资源的管理因一致而简化。当前广泛使用的Windows2000操作系统,就采用了微内核的结构,同时还融入了面向对象的程序设计技术。具有面向对象的特点:封装性、继承性、多态性微内核的基本功能:通常都是一些最基本的功能,如进程管理、存储器管理、进程间通信、低级I/O功能。教课小结:预习要求:作业布置:第4讲〔第4周<注:线右侧写教学方法、实验演示、新增补内容、重要标注、时间分配等>教学章节:第2章进程管理2.1进程的基本概念程序的顺序执行及其特征前趋图程序的并发执行及其特征进程的特征与状态进程控制块教学目的及要求:学习目的是使学生建立起进程的概念。进程是OS中最重要的基本概念,本章是全书中最重要的一章。要求掌握进程的基本概念,重点、难点:<注:重点和难点如果一致,则写在一起,若不同则应分开写>进程的引入、特征、基本状态、进程控制块教学内容:板书设计见PPT。<注:内容每节课1-2页为宜>复习引入:通过第一章的学习,对操作系统有了整体上的认识,以后的章节就是对各个部分的功能加以详细的论述。新课讲授:第2章进程管理思考问题:为什么要引入进程进程具有哪些基本特征进程具有哪些基本状态进程控制块的作用和内容2.1进程的基本概念引入进程的目的是为了使多个程序能并发执行。程序的顺序执行及其特征1.程序的顺序执行程序的顺序执行是指若干个程序或程序段之间必须严格按照某种先后次序来执行,仅当前一程序或程序段执行完后,才能执行后面的程序或程序段。例:每个程序有三个顺序执行的操作——I:输入操作、C:计算操作、P:输出操作2.程序顺序执行时的特征<1>顺序性处理机的操作严格按照程序所规定的顺序执行。<2>封闭性程序一旦开始执行,其计算结果不受外界因素的影响。即程序运行时独占全机资源,资源的状态〔除初始只有本程序才能改变它。<3>可再现性程序执行的结果与它的执行速度无关<即与时间无关>,而只与初始条件有关。前趋图为了描述一个程序的各部分〔程序段、语句间的依赖关系,或是一个大的计算的各子任务间的因果关系,采用前驱图方式。前趋图是一个有向无循环图<DAG>,用于描述程序段或进程之间执行的先后次序关系。结点:描述一个程序段或进程,或一条语句。有向边:结点之间的偏序或前趋关系""={<Pi,Pj>|在Pj开始前Pi必须完成},若<Pi,Pj>∈,可写成PiPjPiPj:Pi必须在Pj开始之前完成则Pi是Pj的直接前趋,Pj是Pi的直接后继初始结点:没有前趋的结点终止结点:没有后继的结点例:具有九个结点的前驱图:前趋关系:P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9注意:前趋图中绝对不能出现循环程序的并发执行及其特征1.程序的并发执行例:在系统中有n个作业,每个作业都有三个处理步骤,输入数据、处理、输出,即Ii,Ci,Pi<i=1,2,3,...,n>。这些作业在系统中执行时是对时间的偏序,有些操作必须在其它操作之前执行,这是有序的,但有些操作是可以同时执行的。2.程序并发执行时的特征<1>间断性在多道程序设计的环境下,程序是并发执行的,它们为完成一项任务而相互合作,这些程序之间要共享系统的资源,形成了相互制约的关系。相互制约导致并发程序具有"执行——暂停——执行"这种间断性的活动规律。<2>失去封闭性程序在并发执行时,多道程序共享系统的资源,因而这些资源的状态由多道程序来改变,程序运行失去封闭性。一程序的运行受到其他程序的影响。<3>不可再现性程序在并发执行时,失去封闭性导致其失去可再现性。重复执行时,虽执行环境和初始条件相同,但结果却不同。〔加入实例进程的特征与状态在计算机中,程序的并发执行具有不可再现性。那么,如何使程序既能并发执行,又具有可再现性呢?这就必须引入进程的概念,也就是说,引入进程的目的是为了使程序能够正确地并发执行。〔为什么进程实体却能与其他进程并发执行?1进程的特征与定义〔1进程的特征结构性、动态性、并发性、独立性、异步性①结构性进程控制块<PCB>+程序段+相关的数据段=进程实体。②动态性——进程是程序在处理机上的一次执行过程。具有生命期,它必须由创建而产生,由调度而执行,由撤销而消亡。是进程的一个最基本的特征。③并发性——多个进程实体同存于内存中,在一段时间内同时运行。以提高资源利用率。只有为程序创建进程后,多个程序才能正确地并发运行。并发是引入进程的目的,也是进程的另一个最基本的特征。④独立性——进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位,而程序则不是。⑤异步性——进程按各自独立的、不可预知的速度向前推进。〔2进程〔Process的定义进程是程序的一次执行。进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位。进程的定义:进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。〔3进程与程序的区别进程是动态的,程序是静态的进程是暂时的,程序是永久的进程与程序的组成不同:
进程包括程序、数据和进程控制块〔即进程状态信息进程与程序的对应关系:
不是一一对应。通过多次执行,一个程序可对应多个进程;通过调用关系,一个进程可包括多个程序。2.进程的三种基本状态①就绪状态<Ready>:进程已获得了除CPU之外的所有资源,处于就绪态的进程有多个,它们存放在就绪队列中。②执行状态<Running>:已获得CPU的进程进入执行状态。③阻塞状态<Blocked>:进程因发生某个事件〔如请求I/O、申请缓冲空间而暂停执行的状态。即进程的执行受到阻塞进程的三种基本状态以及各状态之间的转换关系对单个进程而言,任何时刻,它只能处于三种基本状态之一,而随着进程自身的推进和外界环境条件的变化,它的状态可以动态地转换:处于就绪状态地进程,通过进程调度获得CPU后,便从就绪状态转换成执行状态;分时系统中,正在执行地进程由于时间片用完而暂停执行时,便从执行状态转换成就绪状态;正在执行地程序,由于等待某种事件地完成而无法继续执行时,便从执行状态转换成阻塞状态;阻塞地进程所等待的事件完成后,便转为就绪状态。对整个系统而言,每个时刻允许同时有多个处于就绪和阻塞的进程,但对执行状态的进程,每个处理机最多只允许有一个。3.挂起状态"挂起"的实质是使进程不能继续执行,即使挂起后的进程处于就绪状态,它也不能参与对CPU的竞争。因此,被挂起的进程处于静止状态,相反,没被挂起的进程则处于活动状态。而且,处于静止状态的进程只有通过"激活"动作,才能转换成活动状态。引起挂起状态的原因:终端用户的请求、父进程请求、负荷调节的需要、操作系统的需要"挂起"常被用在进程对换中,此时,挂起〔即换出进程可以腾出内存空间给就绪进程使用;"挂起"还可用在其他场合,如用来调节系统的负荷、方便用户考查自己的运行进程或父进程考查子进程、方便操作系统检查运行中的资源使用情况或进行记帐等。<2>进程状态的转换①活动就绪静止就绪〔挂起、激活②活动阻塞静止阻塞〔挂起、激活③执行静止就绪〔挂起4.创建和终止状态〔1创建状态①创建PCB,填写必要的管理信息②转入就绪状态并插入就绪队列中一般而言,此时的进程已拥有了自己的PCB,但进程自身还未进入主存,即创建工作尚未完成,进程还不能被调度运行,其所处的状态就是创建状态。〔2终止状态①等待OS进行善后处理②将其PCB清零,并将PCB空间返还系统。进入终止态的进程以后不能再执行,但在OS中依然保留一个记录供其他进程收集,一旦其他进程完成了对终止状态进程的信息的提取后,OS将删除该进程。思考问题:问题:PCB的作用,为什么说是进程存在的唯一标志?进程控制块为了描述和控制进程的运行,系统为每个进程定义了一个数据结构——进程控制块〔PCB。进程控制块的作用存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构。PCB是进程实体的一个组成部分,在其中记录了OS所需的、用于描述进程的当前状态以及控制进程的全部信息。其作用是将程序变成可并发执行的进程。系统根据进程的PCB感知到一进程的存在,并对它进行控制,因此,进程控制块是进程存在的唯一标志。由于PCB要被系统频繁访问,它必须常驻内存。在创建时,建立PCB,并伴随进程运行的全过程,直到进程撤消而撤消。PCB就象我们的户口。系统的所有PCB组织成链表或队列,常驻内存的PCB区。2.进程控制块中的信息1>进程标识符信息每个进程都必须有一个唯一的标识符。另外,还可以用父进程的标识符、子进程的标识符来描述进程的家族关系。内部标识符:便于系统使用外部标识符:便于用户使用2>处理机状态信息处理机状态信息主要由处理机的各种寄存器中的内容组成。处理机运行时的信息存放在寄存器中,当被中断时这些信息要存放在PCB中。通用寄存器、指令计数器、程序状态字PSW、用户栈指针3>进程调度和控制信息——用于进程调度和控制。主要包括进程状态、优先级、等待和使用CPU的时间总和、程序和数据的地址、进程同步和通信信息、资源清单和进程队列指针等。3.进程控制块的组织方式在一个系统中通常有许多PCB,称为PCB集合。为了便于管理,系统必须用适当的方式将PCB组织起来,常用的方式有链接和索引方式。1>链接方式把具有同一状态的PCB用其中的链接字链接成一个队列。就绪队列;若干个阻塞队列;空白队列2>索引方式系统根据所有进程的状态建立几张索引表,把各表的内存首地址记录在内存的专用单元中。索引表的表目中记录了相应状态的某个PCB在PCB表中的地址。其他方式:线性表或链表教课小结:预习要求:作业布置:第5讲〔第4周<注:线右侧写教学方法、实验演示、新增补内容、重要标注、时间分配等>教学章节:2.2进程控制进程的创建进程的终止进程的阻塞与唤醒进程的挂起与激活2.3进程同步进程同步的基本概念信号量机制教学目的及要求:了解进程控制的过程掌握进程间的相互关系,以及进程同步的有效机制信号量机制。重点、难点:信号量的物理意义教学内容:板书设计见PPT。复习引入:上次课提及到进程的几种状态以及之间如何转换,本次课将详细介绍引起进程各种状态的原因,以及相应原语的创建过程。新课讲授:2.2进程控制进程控制是进程管理中最基本的功能,它用于创建和撤销进程,并对进程在整个生命周期中各种状态之间的转换进行有效控制。进程控制是OS的内核通过原语来实现的。原语的作用是为了实现进程通信和控制,是由若干条指令组成的,用于完成一定功能的一个过程;原语的执行具有原子性,即原语在执行过程中不可分割,在执行过程中不允许被中断。许多系统调用就是原语。处理机运行时的两种状态:核心态和用户态,〔1系统状态:也叫管态或核心态,它具有较高的特权,能执行一切指令,访问所有寄存器和存储区。通常,OS内核就运行在系统态下。〔2用户态:也叫目态,是一种具有较低特权的执行状态。它只能执行规定的指令、访问规定的寄存器和存储区。通常用户程序都运行在用户态。用户态时不可直接访问受保护的OS代码;核心态时执行OS代码,可以访问全部进程空间通过这两个状态的划分,可防止用户程序破坏OS内核代码和数据。进程的创建1.进程图描述进程的家族关系的有向树〔结点:代表进程,根结点为该家族的祖先;有向边:父子关系;树:表示一个家族进程Pi创建了进程Pj,则Pi是Pj的父进程,Pj是Pi的子进程,用一条由进程Pi指向进程Pj的有向边来描述。创建父进程的进程为祖先进程,由此形成进程树,树根为进程家族的祖先。提问:进程图与前趋图比较〔1前趋图:描述的是任务之间的前趋关系,只有在前趋进程完成后,其后继进程才能运行〔2进程图:创建者和被创建者可以并发执行,也可以父进程等待其所有子进程结束后再执行,这完全取决于创建原语和创建者的需要。2.引起创建进程的事件在多道程序环境中,只有进程才能在系统中运行。导致创建进程的典型事件有:〔分时系统的用户登录、〔批处理系统中的作业调度、提供服务———这三种情况是由系统内核为其创建一个新进程。应用请求——应用程序本身也可以根据需要去创建新的进程〔自己创建一个新进程3.进程的创建操作系统发现要求创建新进程的事件后,调用进程创建原语Creat<>创建新进程。创建过程:<1>申请空白PCB:申请进程标识符,并从PCB集合中索取一个空白PCB<2>为新进程分配资源:为新进程的程序和数据以及用户栈分配必要的内存空间。<3>初始化进程控制块:初始化标识信息、处理机状态信息、进程调度和控制信息。<4>将新进程插入就绪队列进程的终止当进程完成任务或遇到异常情况和外界干预需要结束时,应通过进程终止原语来终止进程。终止进程的实质是收回PCB。1.引起进程终止的事件1>正常结束——用于表示进程已经运行完成的指示2>异常结束——运行间,某些错误和故障而迫使进程终止越界错误、保护错、非法指令、特权指令错、运行超时等3>外界干预——并非异常事件,而应外界的请求而终止运行操作员或操作系统干预、父进程请求、父进程中止2.进程的终止过程<1>找到要终止进程的PCB——根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态。<2>若被终止进程正处于执行状态,应立即终止该进程的执行,置调度标志为真,用于指示该进程被终止后应重新进行调度。<3>终止属于该进程的所有子孙进程——若该进程有子孙进程,应将其所有子孙进程予以终止,以防他们成为不可控的进程。<4>释放终止进程所拥有的全部资源——将被终止进程所拥有的全部资源,或归还其父进程,或归还系统。<5>将终止进程移出它所在的队列并收回PCB——将被终止进程的PCB从所在队列或链表中移出,等待其他程序搜索信息进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件1>新数据尚未到达2>无新工作可做3>请求系统服务4>启动某种操作当正在执行的进程需要等待某种事件的完成或本身无新工作可做时,应调用阻塞原语将自己从执行状态转换为阻塞状态2.进程阻塞过程——是进程本身的一种主动行为调用阻塞原语阻塞自己,中止该进程的执行,将PCB中的状态改为阻塞,并加入到阻塞队列中;然后转进程调度,将处理机分配给另一进程,并进行进程切换以及处理机状态的保护与重新设置。3.进程唤醒过程阻塞进程等待的事件发生,有关进程调用唤醒原语把等待该事件的进程唤醒。唤醒原语的执行:把阻塞进程从等待该事件的阻塞队列中移出,将其PCB中的现行状态改为就绪,将PCB插入到就绪队列中。阻塞原语与唤醒原语作用相反,成对使用。注意:阻塞是进程自己阻塞自己的,而进程唤醒不是自己唤醒自己,它需要另一进程来实现。进程的挂起与激活1.进程的挂起当出现引起进程挂起的事件时,系统利用挂起原语将指定进程或处于阻塞的进程挂起。挂起原语的执行:检查被挂起进程的状态,若处于活动就绪,则改为静止就绪,若处于活动阻塞,则改为静止阻塞,将该进程PCB复制到内存指定区域,若挂起的进程正在执行,则重新进行进程调度。如果挂起是为了对换,则在挂起进程时还必须将它换出到外存中。2.进程的激活过程当发生激活进程的事件时,系统利用激活原语将指定进程激活。激活原语先将进程从外存调入内存,检查该进程的状态,若处于静止就绪,则改为活动就绪,若处于静止阻塞,则改为活动阻塞。若进程转换成活动就绪状态,而系统又采用抢占调度策略,则应检查该进程是否有权抢占CPU,若有则应进行进程调度。同样,若挂起是为了对换,则在激活被挂起的进程时还必须将它调入内存。2.3进程同步思考问题:引入进程同步的目的临界资源和临界区引入进程同步:OS引入进程提高了资源利用率和系统吞吐量,但由于进程的异步性导致了系统混乱,尤其争用临界资源时,〔引用实例:当多个进程去争用一台打印机时,有可能使多个进程的输出结果交织在一起难于区分。为此,OS必须引入某种机制,即进程的同步机制〔进程同步。进程同步是指对多个相关进程在执行次序上进行协调,它的目的是使系统中诸进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性。用来实现同步的机制被称作同步机制。进程同步的基本概念在多道程序的环境下:所有进程都是相互独立的、进程以异步方式并发执行,致使进程在活动中会相互制约1.两种制约关系直接:相互制约关系源于进程合作,表现为:进程进程〔同步间接:相互制约关系源于资源共享,表现为:进程资源进程〔互斥〔1同步同步是进程间共同完成一项任务时直接发生相互作用的关系同步举例:输入进程和计算进程通过单缓冲区来协调工作同步进程间具有合作关系在执行时间上必须按一定的顺序协调进行〔2互斥互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系互斥进程彼此在逻辑上是完全无关的它们的运行不具有时间次序的特征2.临界资源一次仅允许一个进程使用的共享资源,如果多个进程同时使用这些资源,则有可能造成系统的混乱,如:打印机,多个进程同时使用一台打印机,将使其输出结果交织在一起,难于区分;又如共享变量,多个进程同时使用一个共享变量,会使结果具有不可再现性。3.临界区〔如何保证诸进程互斥地访问临界资源每个进程中访问临界资源的那段代码叫临界区。对欲访问的临界资源进行检查,………………进入区若此刻未被访问,设正在访问的标志访问临界资源………………临界区将正在访问的标志恢复为未被访问的标志……退出区其余部分………………剩余区为了使多个进程能有效地共享临界资源,并使程序的执行具有可再现性,系统必须保证它们互斥地使用临界资源,即保证它们互斥地进入自己地临界区。如果一进程已进入临界区使用临界资源,另一企图进入临界区使用同一临界资源的进程便必须等待,直到前一进程退出临界区为止。不难看出,互斥的实质就是同步,互斥是同步的一种特殊形式。4.同步机制应遵循的规则为实现进程互斥地进入自己地临界区,采用同步机制来协调各进程间地运行。空闲让进-临界资源空闲时,应允许一个请求进入临界区的进程立即进入自己的临界区,以便有效地利用资源。忙则等待——当临界资源正被访问时,其他要求进入临界区地进程必须等待,以保证对临界资源地互斥使用。有限等待——任何要求访问临界资源的进程应能在有限的时间内进入自己的临界区,以免"死等"让权等待——不能进入临界区的进程应立即释放CPU,以免"忙等"信号量机制思考问题:信号量的含义〔信号量的P、V操作如何实现;各种信号量机制的特点为了实现同步,OS引入多种管理机制,其中信号量机制是最有效的。1965年荷兰Dijkstra提出的进程同步工具。〔这个Dijkstra,就是那个提出"goto有害论"的Dijkstra,就是那个提出信号量和PV原语,解决了有趣的"哲学家聚餐"问题的Dijkstra,那个Dijkstra最短路径算法的创造者。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖信号量代表可用资源实体的数量。信号量又叫信号灯〔semaphore,是表示资源的实体,是一个与队列有关的整型变量,除初值外其值仅能由P、V原语操作来改变。操作系统利用信号量对进程和资源进行控制和管理。公用〔互斥信号量:用于实现进程之间的互斥,初值为1,它所联系的一组并发进程均可对其实施P、V操作;除初值外,信号量的值仅由P、V操作改变P、V分别代表荷兰语的"等待"Wait,"发信号"SignalP、V操作原语—P操作〔wait原语申请一个单位资源—V操作〔signal原语释放一个单位资源1.整型信号量整型量,除初始化外,仅能通过两个原子操作来访问。Wait操作wait<S>: WhileS<=0dono-op;S:=S-1;Signal操作signal<S>: S:=S+1;Wait、Signal操作是原子操作,不可中断。整型信号量的主要问题是,只要S<=0,wait操作就会不断地测试,因而,没能做到"让权等待"2.记录型信号量整型信号量未遵循"让权等待"原则,导致"忙等"。记录型信号量:一般是由两个成员组成的数据结构,其中一个成员是整型变量,表示该信号量的值,另一个是指向PCB的指针。引入整型变量value<代表资源数目>、进程链表L<链接所有等待进程>记录型数据结构:typesemaphore=recordvalue:integer;L:listofPCB;end;信号量的值是与相应资源的使用情况有关的。当它的值大于0时,表示当前可用资源的数量;当它的值小于0时,则其绝对值表示等待使用该资源的进程数,即在该信号量队列上排队的PCB的个数。wait<S>:S.value:=S.value-1;ifS.value<0thenblock<S,L>当S.value<0时表示该类资源已分配完毕,进程应调用block原语自我阻塞,放弃处理机,插入到链表S.L中。signal<S>:S.value:=S.value+1;ifS.value<=0thenwakeup<S,L>若加1后仍是S.value<=0,则表示在信号量链表中仍有等待该资源的进程被阻塞,应调用wakeup原语,将S.L链表中的第一个等待进程唤醒。前面介绍的进程互斥问题,属于多个进程共享一个临界资源。而AND型信号量是为了解决多个进程共享多个临界资源。3.AND型信号量AND同步机制的基本思想:将进程在整个运行过程中需要的所有资源,一次性全部分配给进程,待进程使用完后再一起释放。只要尚有一个资源未能分配给进程,其他所有可能为之分配的资源,也不分配给它,即对临界资源的分配采取原子操作。4.信号量集一般信号量集的几种特殊情况:Swait<S,d,d>,只有一个信号量S,允许每次申请d个资源,若现有资源数少于d,不予分配。Swait<S,1,1>,蜕化为一般的记录型信号量<S>1时>或互斥信号量<S=1时>。Swait<S,1,0>,当S>=1时,允许多个进程进入某特定区,当S变为0后,阻止任何进程进入特定区,相当于可控开关。教课小结:预习要求:作业布置:实验二Linux进程控制第6讲〔第5周教学章节:信号量的应用实例分析教学目的及要求:要求掌握信号量和管程机制的应用重点、难点:信号量机制及其应用教学内容:板书设计见PPT。复习引入:总结:信号量的物理意义问题:信号量的物理含义以及每次wait和signal操作又分别意味什么一般说来,信号量的值与相应资源的使用情况有关。当S>0时,其值表示可用资源的数量,执行一次Wait操作意味着请求分配一个单位的资源;若S<=0,表示已无资源,申请资源的进程被阻塞,并排入信号量S的等待队列中,执行一次Signal操作,意味着释放一个单位的资源。新课讲授:信号量的应用1.利用信号量实现进程互斥为使多个进程能互斥地访问某个临界资源,只需为该资源设置一互斥信号量mutex,初值为1,然后将访问该资源的临界区置于wait<mutex>和signal<mutex>之间。利用信号量实现互斥的说明为临界资源设置一个互斥信号量mutex,其初值为1在每个进程中将临界区代码置于Wait<mutex>和Signal<mutex>原语之间必须成对使用Wait和Signal原语:遗漏Wait原语则不能保证互斥访问,遗漏Signal原语则不能在使用临界资源之后将其释放〔给其他等待的进程Wait、Signal原语不能次序错误、重复或遗漏2.把信号量作为进程间的同步工具〔实现前驱关系若pi是pj的直接前趋,则可设置一个初值为0的公用信号量S,并将signal<S>操作放在pi后,而在pj前插入wait<S>操作,以保证pi在pj开始执行之前完成。举例:设有两个并发执行的进程P1和P2,P1中有语句S1,P2中有语句S2,希望在S1执行后再执行S2。使进程P1和P2共享一个公用信号量S,并赋予其初值为0。进程P1:S1;signal<S>;进程P2:wait<S>;S2;例一:供者和用者对缓冲区的同步设2个信号量:empty——缓冲区是否为空〔初值为1full——缓冲区是否为满〔初值为0.供者进程L1:Wait〔empty将信息送入缓冲区;Signal〔fullgotoL1用者进程L2:Wait〔full从缓冲区取出信息;Signal〔emptygotoL2.在现实生活中,同步的例子也比比皆是。例二:在一辆公交车上,司机和售票员各行其职,独立工作。司机负责开车和到站停车;售票员负责售票和开关车门。但两者需要密切配合、协调一致。即当司机驾驶的车辆到站并把车辆停稳后,售票员打开车门,让乘客上下车,然后关好车门,这时司机继续开车行驶。此即典型的同步关系!设司机进程设置一信号量run,用于判断司机能否进行工作,初值为0;售票员进程设置一个信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0;.司机:RepeatP<run>;启动车辆;正常行车;到站停车;V<stop>;Untilfalse;售票员:Repeat上乘客;关车门;V<run>;售票;P<stop>;开车门;下乘客;Untilfalse;.关于信号量实现同步的说明分析进程间的制约关系,确定信号量的种类。信号量的初值与相应资源的数量有关,也与P、V操作在程序代码中出现的位置有关。同一信号量的P、V操作要成对出现,但它们分别在不同的进程代码中。把信号量视为某种类型的共享资源的剩余个数,实现对一类共享资源的访问。例:某超市门口为顾客准备了100辆手推车,每位顾客在进去买东西时取一辆推车,在买完东西结完帐以后再把推车还回去。试用P、V操作正确实现顾客进程的同步互斥关系。分析:把手推车视为某种资源,每个顾客为一个要互斥访问该资源的进程。解:semaphores_cartnum;//空闲的手推车数量,初值为100voidconsumer<void>//顾客进程{p<s_cartnum>;买东西;结帐;v<s_cartnum>;}关于信号量的进一步说明同步和互斥这两种制约关系的区别:进程的互斥是进程间竞争共享资源的使用权,这种竞争没有固定的必然联系;而进程同步时,涉及到共享资源的并发进程之间一种必然的依赖关系。用P、V操作解决进程并发问题时首先应确定问题是属于进程互斥还是进程同步,或是互斥与同步的混合问题,然后根据共享资源的数量以及使用共享资源的规则正确的定义信号量及其初值。如果用于互斥,只要用一个信号量与一组相关临界区联系起来,信号量的初值定义为"1"。每个进程要进入临界区之前调用P操作,测试自己是否可以立即进入临界区;执行完临界区的代码后,调用V操作表示自己退出临界区。①对于两个并发进程,S只有1、0、-1三个取值:s=1:无进程进入临界区;s=0:有一个进程进入临界区;s=-1:有一个进程在临界区,另一个进程等待进入临界区。②对于n个并发进程,信号量S可取值的范围是:
1~-<n-1>,当S<0时,表示有一个进程已进入临界区,而且还有|S|个进程正在等待进入临界区,它们处于等待队列中。4如果用于同步,常称为同步〔私用、资源信号量,每个信号量与一个消息对应,根据各个消息量的物理含义确定初值,初始值可以为0或为某个正整数n〔视资源数而定。进程通过调用P操作来测定自己需要的消息是否到达,通过调用V操作把其他进程需要的消息发送出去。实例分析:教课小结:预习要求:作业布置:1、作业:2、补充习题:<若没有可以删去>推荐参考书目、网站及阅读材料:<若没有可以删去>第7讲〔第7周<注:线右侧写教学方法、实验演示、新增补内容、重要标注、时间分配等>教学章节:管程机制2.4经典进程的同步问题生产者——消费者问题〔是最著名的进程同步问题实例分析教学目的及要求:用P、V操作解决进程同步问题重点、难点:<注:重点和难点如果一致,则写在一起,若不同则应分开写>经典进程的同步问题教学内容:板书设计见PPT。<注:内容每节课1-2页为宜>2.3.4管程<monitor>管程的引入:用信号量可实现进程间的同步,但由于同步操作wait<S>和signal<S>分散在各个进程中,并遍布整个程序。这不仅给系统的管理和程序的维护和修改带来了麻烦,而且还会因同步操作的使用不当造成死锁。为了解决上述问题,又产生了一种新的进程同步工具——管程。信号量同步的缺点同步操作分散:信号量机制中,同步操作分散在各个进程中,使用不当就可能导致各进程死锁;易读性差:要了解对于一组共享变量及信号量的操作是否正确,必须通读整个系统或者并发程序;不利于修改和维护:各模块的独立性差,任一组变量或一段代码的修改都可能影响全局;正确性难以保证:操作系统或并发程序通常很大,很难保证这样一个复杂的系统没有逻辑错误;管程的基本概念1973年,由Hoare和Hanson所提出;其基本思想是把信号量及其操作原语封装在一个对象内部。即:将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。〔1管程的定义:管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。基本思想:是把信号量及其操作原语封装在一个对象内部,即:集中在一个模块中。〔2优点:管程可增强模块的独立性:系统按资源管理的观点分解成若干模块,用数据表示抽象系统资源,使同步操作相对集中,从而增加了模块的相对独立性引入管程可提高代码的可读性,便于修改和维护,正确性易于保证:采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成,一个模块通常较短,模块之间关系清晰。管程的组成名称:数据结构说明:一组局部于管程的共享变量操作原语:对共享变量进行操作的一组原语过程〔程序代码初始化代码:对控制变量进行初始化的代码对共享变量和临界资源进行操作的一组原语过程〔程序代码,是访问该管程的唯一途径。这些原语本身是互斥的,任一时刻只允许一个进程去调用,其余需要访问的进程就等待。TYPEmonitor_name=MONITOR;共享变量说明;procedure过程名〔形参表;过程局部变量说明; begin语句序列; end;function函数名〔形参表:值类型;函数局部变量说明;begin语句序列;end;begin共享变量初始化语句序列;end;管程具有以下特点:局部于管程的数据结构,仅被局部于管程的过程访问。局部于管程的过程,也仅能访问管程内的数据结构。任何进程只能通过调用管程提供的过程入口进入管程任一时刻,最多只能有一个进程在管程中执行,管程〔相当于围墙把共享变量和对它进行操作的若干过程围起来。5.条件变量<condition>条件变量的引入:在任何时刻,最多只有一个进程在管程中执行,因此用管程很容易实现互斥,只要将需要互斥访问的资源用数据结构来描述,并将该数据结构放入管程中便可。若要用管程来实现同步,则在相应条件不满足时〔如临界资源得不到时必须能够将在管程内执行的进程阻塞。由于阻塞的原因不同,为了将他们区分开,引入局部于管程的条件变量。每个条件变量表示一种等待原因,并不取具体数值--相当于每个原因对应一个队列。同步操作原语wait和signal:针对条件变量x,执行x.wait的进程将自己阻塞在x队列中,x.signal将x队列中的一个进程唤醒。wait操作。如x.wait用来将执行进程挂到与条件变量x相应的等待队列上;signal操作。x.signal用来唤醒与x相应的等待队列上的一个进程。值得注意的是,若没有等待进程,则x.signal不起任何作用。这与信号量机制中的signal操作不同。6.管程与进程的异同设置的目标不同进程实现系统并发;管程解决共享资源的互斥使用系统管理数据结构不同进程私有数据结构PCB;管程公共数据结构〔等待队列管程被进程调用管程是OS的固有成分,无创建和撤消2.4经典进程的同步问题生产者——消费者问题〔是最著名的进程同步问题思考问题:该问题用于解决什么问题的如何实现互斥如何实现同步对程序的阅读方式问题的描述:问题的描述:一组生产者与一组消费者,它们共享一个有界缓冲池,生产者向池中投入产品,消费者从中取出产品。假定在生产者和消费者之间的公用缓冲池具有n个缓冲区,每个缓冲区只能存放一个类型为item的产品,而所有的生产者和消费者是相互等效的。生产者进程和消费者进程都以异步方式运行,但它们之间必须保持同步。生产者——消费者问题实际上是相互合作的进程关系的一种抽象。比如输入进程和计算进程、计算进程和打印进程都是生产者——消费者问题的反映,因此,该问题具有很大的实用价值。分析:1实现互斥缓冲池是临界资源,一次只允许一个生产者投入消息,或者一个消费者从中取出消息,即生产者和消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex——它代表缓冲池资源,用于实现诸进程对缓冲池的互斥使用,其初始值为1。2实现同步A.只有缓冲池中至少有一个缓冲区是空时,生产者才能把消息放入缓冲区;否则生产者必须等待。为了满足此同步条件,设置一个资源信号量empty,它代表缓冲池中空缓冲区的数量,初始值为n,表示整个缓冲池为空。这个资源是生产者进程所拥有,生产者进程可以申请该资源并对它施加P操作,而消费者进程对它实施V操作。B.只有在缓冲池中至少有一个缓冲区已存入消息后,消费者才能从中提取消息;否则消费者必须等待。同样为了满足此同步条件,设置一个资源信号量full,它代表缓冲池中满缓冲区的数量,初始值为0,当其值为n时,整个缓冲池为满。这个资源是消费者进程所拥有,消费者进程可以申请该资源并对它施加P操作,而生产者进程对它实施V操作。具体的算法描述略。<用记录型信号量和AND信号量描述>注意:1.每个程序中用于实现互斥的wait<mutex>和signal<mutex>必须成对地出现。2.对资源信号量empty和full的wait和signal操作,同样需要成对地出现,但处于不同的程序中。3.在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作,再执行对互斥信号量的wait操作,否则可能引起进程死锁。利用管程解决生产者-消费者问题在利用管程方法来解决生产者——消费者问题时,首先便是为它们建立一个管程,并明名为Producer-Consumer,或简称为PC。其中,包含两个程:put<item>过程:将生产的消息投放到缓冲池中,:当count>或=n时,表示缓冲池已满,生产者需等待,等待缓冲池不全满条件成立。get<item>过程:消费者利用该过程从缓冲池中取得一个消息,当count<或=n时,表示缓冲池中已无可用消息,消息者应等待。PC管程可描述如下:条件变量notfull、notempty分别对应于缓冲池不全满、缓冲池不全空两个条件Typeproducer-consumer=monitor变量定义;.Procedureentryput<item>BeginIfcount>或=nthennotfull.wait;//等待缓冲池不全满条件成立……投放数据Ifnotempty.queuethennotempty.signal;//缓冲池不全空条成立EndProcedureentryget<item>BeginIfcount<或=0thennotempty.wait;//等待缓冲池不全空条件成立……取数据Ifnotfull.queuethennotfull.signal;//缓冲池不全满条件成立EndBeginin:=out:=0;count:=0;end.在利用管程解决生产者——消费者问题时,其中的生产者和消费者可描述为:.producer:beginrepeatproduceaniteminnextp;PC.put<item>;Untilfalse;EndConsumer:beginRepeatPC.get<item>;Consumetheiteminnextc;Untilfalse;End.实例分析例一:生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里,现要用自动分拣系统把黑子和白子分开,该系统由两个并发执行的进程组成,功能如下:
〔1进程A专门拣黑子,进程B专门拣白子;
〔2每个进程每次只拣一个子,当一个进程在拣子时不允许另一个进程去拣子;由于进程A和进程B要互斥进入箱子去拣棋子,箱子是两个进程的公有资源,所以设置一个信号量mutex,其值取决于公有资源的数目,由于箱子只有一个,mutex的初值就设为1。.processA……P<mutex>;
拣黑子;
V<mutex>;
……processB
……P<mutex>;
拣白子;
V<mutex>;
…….〔3当一个进程拣了一个棋子〔黑子或白子以后,必让另一个进程拣一个棋子〔黑子或白子。对于进程A可设置一个私有信号量black,该私有信号量用于判断进程A是否能去拣黑子,初值为1。对于进程B同样设置一个私有信号量white,该私有信号量用于判断进程B是否能去拣白子,初值为0。当然你也可以设置black初值为0,white初值为1。.processA
……P<black>;
拣黑子;
V<white>;processB
……P<white>;
拣白子;
V<black>;…….例二桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。应设置三个信号量plate、orange、apple,信号量plate表示盘子是否为空,其初值为l;信号量orange表示盘中是否有桔子,其初值为0;信号量apple表示盘中是否有苹果,其初值为0。.father<>……P<plate>;将水果放入盘中;if〔放入的是桔子V<orange>;
elseV<apple>;
……son<>
……
P<orange>;
从盘中取出桔子;
V<plate>;
吃桔子;
……daughter<>
……
P<apple>;
从盘中取出苹果;
V<plate>;
吃苹果;
…….例三设有一台计算机,有两条I/O通道,分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中,加工处理后再搬到缓冲区B2中,并在打印机上打印,问:①系统要设几个进程来完成这个任务?各自的工作是什么?②这些进程间有什么样的相互制约关系?③用P、V操作写出这些进程的同步算法信号量含义及初值:B1full——缓冲区B1满,初值为0;B1empty——缓冲区B1空,初值为1;B2full——缓冲区B2满,初值为0;B2empty——缓冲区B2空,初值为1。.P1进程……P<B1empty>输入信息写入缓冲区B1V<B1full>P2进程……P<B1full>V<B1empty>加工信息P<B2empty>结果送入B2V<B2full>P3进程……P<B2full>从B2中取出信息V<B2empty>.教课小结:预习要求:作业布置:P82第24、25题:第8讲〔第8周教学章节:哲学家进餐问题读者——写者问题2.5进程通信教学目的及要求:重点、难点:<注:重点和难点如果一致,则写在一起,若不同则应分开写>教学内容:板书设计见PPT。<注:内容每节课1-2页为宜>复习引入:哲学家进餐问题由Dijkstra提出并解决的哲学家进餐问题也是一个经典的同步问题。问题描述:五位哲学家以交替思考、进餐的方式生活,他们坐在一张圆桌旁,桌子上有5个碗和5只筷子。当一个哲学家思考时,他与相邻的两个哲学家不会相互影响;但当他进餐时,需同时获得最靠近他的左右两只筷子,若其中一只筷子被相邻的哲学家拿走,他就必须等待,因此,他们相互制约。该问题中,哲学家争用的临界资源是筷子,因此需为每只筷子分别设置一初值为1的互斥信号量。第i位哲学家的活动可描述为:repeatwait<chopstick[i]>;//当哲学家饥饿时,总是先拿左边的筷子,再拿右边的筷子。wait<chopstick[<i+1>mod5]>;…eat;…signal<chopstick[i]>;//当哲学家进餐毕,先放下左边的筷子,再放下右边的筷子。signal<chopstick[<i+1>mod5]>;…think;untilfalse;上述解法虽然可以保证互斥地使用筷子,但可能造成死锁。假如5个哲学家同时拿起各自左边地筷子,便将出现循环等待的局面,发生死锁现象。具体的解决办法有:至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用毕后释放出他用过的两只筷子,从而使更多的哲学家能够进餐。限制并发执行的进程数仅当哲学家的左右两只筷子均可用时,才允许他拿起筷子进餐。采用信号量集规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;偶数号哲学家则相反。保证总会有一个哲学家能同时获得两只筷子而进餐读者——写者问题问题的描述:一个数据对象,如文件或记录,能被多个进程共享,可把那些只要求读的进程称为"读者",其他进程则称为"写者"。显然,多个读者可同时读一个共享对象,但不允许一个写者与其他读者或写者同时访问共享对象,否则会造成数据的不一致性。这个经典同步问题就是"读者——写者问题"〔一个数据文件或记录可被多个进程共享。只要求读文件的进程称为"Reader进程",其它进程则称为"Writer进程"。允许多个进程同时读一个共享对象,但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。"读者——写者问题"是保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。具体的算法描述略。其中,变量readcount表示正在进行读的读者数目,由于每个读者都要对它进行访问并作修改,因此readcount是一个临界资源,必须被所有读者互斥使用;互斥信号量rmutex用来实现对变量readcont的互斥访问,其初值为1;互斥信号量wmutex用来实现写者之间的互斥,或写者与读者之间的互斥,其初值为1。由于只要有一个读者在读,其余读者便无需等待而可直接进行读操作,因此,仅当readcounter=0时,表示尚无读者在读时,读者进程才需要进行wait<wmutex>操作;而写者必须与任意其他进程互斥,故每次写操作之前窦必须进行wait<wmutex>操作。2.5进程的通信思考问题:①进程通信的几种类型②消息传递通信的实现方法③消息缓冲队列通信机制〔发送和接收进程如何完成,以及进程间如何实现互斥和同步的④比较直接通信方式和间接通信方式进程通信是指进程之间的信息交换。根据进程间通信的规模和方式不同,可以分为:低级通信和高级通信。交换的信息量,少则是一个状态或数值,进程的互斥和同
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论