《操作系统 串讲讲义北工大版ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统 串讲讲义北工大版ppt课件.ppt（194页珍藏版）》请在三一办公上搜索。
1、操作系统原理,第一章 操作系统概论,第二章 进程管理,第三章 内存管理,第四章 设备管理,第五章 文件管理和作业管理,操作系统原理,第一节 操作系统的概念,一、什么是操作系统,计算机硬件,操作系统,实用程序,应用程序,操作系统设计着,程序员,终端用户,定义：,操作系统是一个系统软件，它管理计算机系统中的软件和硬件资源，在计算机硬件和用户之间起到一个接口作用。,.程序图标显示、双击鼠标动作，命令行,.文件复制、磁盘内容察看、建立文件,.INT中断语句进行系统调用,.通过IE下载文件的同时可编辑另一个文本文件,？,第二节 操作系统的功能,一、进程管理,进程管理主要是对处理机进行管理。CPU是计算机
2、中最宝贵的硬件资源。为了提高CPU的利用率，操作系统采用了多道程序技术。当一个程序因等待某一条件而不能运行下去时，就把处理机占用权转交给另外一个可运行程序。或者，当出现了一个比当前运行的程序更重要的可运行程序时，后者应能抢占CPU。 为了描述多道程序的并发执行，就引入了进程的概念。通过进程管理协调多道程序之间的关系，解决处理机实施分配策略，使CPU资源得到最充分的利用。 正是由于操作系统对处理机分配策略的不同，从而呈现在用户面前的就是具有不同性质的操作系统，例如批处理方式、分时处理方式和实时处理方式等。,二、内存管理,存储器管理主要管理内存资源。它包括以下几点： 1）内存分配：在内存中除了OS
3、、其他系统软件外，还有一个或多个用 户程序，OS要解决分配问题，使其互不冲突。,第一节 作业的基本概念,2）存储保护：由于系统中有多个程序，要保证他们之间互部干扰，保证用,户程序不破坏系统程序。,设备管理是指对计算机系统中的所有输入输出设备的管理。它不仅涵盖进行实际I/O操作的设备，还涵盖了控制器、通道等I/O支持设备。,存容量时，就要把内存和外存结合起来，为用户提供一个比,实际内存大的多的虚拟存储器。,三、设备管理,3）内存扩充：当用户作业所需要的内存量超过计算机系统所提供的实际内,四、文件管理,系统中的信息资源（程序和数据）是以文件的形式存放在外存储器上,的，需要时再将其装入。文件管理的任
4、务就是有效支持文件存储、检索修,改，解决文件共享、保密和保护，以方便用户安全、方便地访问文件。,五、用户接口,1）程序级：提供一组广义指令供用户程序调用。,2）作业级：提供一组控制操作命令供用户去组织、控制自己的作业执行。,如同任何其他事物一样，操作系统也有它的诞生、成长和发展过程。为了更清楚地把握操作系统的实质，了解操作系统的发展是很有必要的，因为操作系统的许多概念都是在操作系统的发展过程中出现并逐步得到发展和成熟的。,一、手工操作 在第一代计算机时期，构成计算机的主要器件是电子管，计算机运行速度慢，没有操作系统。用户直接用机器语言编制程序，并在上机时独占全部计算机资源，用户既是程序员，又是
5、操作员。,穿孔-纸带（卡片）装上输入机-程序和数据送入计算机-控制台开关启动程序运行-计算-输出结果-取走指带。,操 作 过 程,第三节 操作系统的发展历史,二、批处理 20世纪50年代晶体管计算机出现，开始出现各种高级语言，操作人员、程序人员和维护人员开始有了明确分工。,程序员,穿孔,操作员,计算机室,卡片盒,许多机时被操作员在机房里走来走去的过程浪费了。,由于处理器速度的提高，造成手工操作的输入输出与计算机处理速度的不匹配现象。因此，人们设计了监督程序（或称为管理程序）来实现作业的自动转换处理。程序员将数据、程序以及用作业语言书写的作业说明书作为作业信息提交给操作员，操作员将这些作业信息“
6、成批”地输入到计算机中，有监督程序识别每一个作业进行处理。这种自动定序的处理方式称为“批处理”,监督程序,标准输入程序,编译程序,装配程序,标准输出和处理程序,输入用户作业程序,编译后的用户作业程序,装配好的用户作业程序,执行、输出结果,调用子程序,转到下一个作业,三、多道程序系统,第二代计算机后期，特别是计算机进入第三代以后，系统软件和硬件都有了很大发展，特别是主存容量的增大以及大容量辅助存储器的出现，这一切都使得计算机体系结构发生了很大变化。由以中央处理器为中心的结构改变为以主存为中心，而通道使得输入输出操作与CPU操作的并行处理成为可能。,所谓多道是指允许多个程序同时存在于主存中，由中央
7、处理器以切换方式为之服务，使得多个程序可以同时执行，计算机资源不再被某一个用户所独占。,待处理程序,存入,外存,形成,程序队列,作业调度,几个程序,进入,内存,有作业完成,再调度,多道程序的引入，使得不同用户的多道程序可以同时在系统内存并行运行，同时它们共享计算机的资源，并行和共享思想的引入大大增加了系统的复杂性。如，如何分配和管理内存、处理机如何调度以及外部设备如何分配等等。这些问题都需要一个复杂的管理机构合理有效地进行管理。它就是操作系统。,随着计算机的发展，硬件价格越来越低,人们开始关注计算机使用的方便性，也就是说如何提高和增加计算机的人-机对话功能，因此很快就出现了分时系统。这种系统是
8、在一台计算机上挂若干台联机终端，用户通过自己的终端与计算机对话来控制、调试、干预他的程序。而系统则是将处理机的时间划分为小的时间间隔（又称时间片），轮流地为每个终端上的作业服务，使每个用户都感觉好象自己在使用计算机。,多道和分时系统的出现，标志着操作系统的正式形成。,四、操作系统的形成,五、操作系统的分类,根据操作系统在用户界面的使用环境和功能特征的不同，操作系统一般可分为三种基本类型，即批处理系统、分时系统和实时系统。随着计算机体系结构的发展，又出现了个人操作系统、网络操作系统和分布式操作系统。,1、批处理操作系统（Batch Processing) 批处理操作系统的工作方式是：用户将作业交
9、给系统操作员，系统操作员将许多用户作业组成一批作业，输入到计算机中，在系统中形成一个自动转接的连续的作业流，然后启动操作系统，系统自动、依次执行每个作业。最后由操作员将作业结果交给用户。,优点：作业流自动化；效率高；吞吐率高。,缺点：无交互手段；调试程序困难。,2、分时操作系统（Time Sharing ) 分时操作系统的工作方式是：一台主机连接了若干终端，每个终端有一个用户在使用。用户交互地向系统提出命令请求，系统采用时间片轮转法方式处理服务请求，并通过交互方式在终端上向用户显示结果。,分时系统具有多路性、交互性、“独占”性和及时性的特征：,多路性：宏观上看多人同时使用一个CPU;,交互性：
10、用户根据系统响应结果进一步提出新请求；,“独占”性：用户感觉不到计算机为其他用户服务;,及时性：系统对用户提出的请求及时响应。,3、实时操作系统（Real Time Operation System) 实时操作系统是指计算机能及时响应外部事件的请求，在规定的严格时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致地工作的操作系统。,4、个人计算机操作系统（Person Operation System) 个人计算机系统是一种单用户多任务的操作系统。它主要供个人使用，功能强、价格便宜。其特点是采用图形界面人机交互的工作方式；使用方便。Dos是单用户单任务操作系统，早期Windows是单
11、用户多任务操作系统。,5、网络操作系统（Network Operation System) 网络操作系统是基于计算机网络的一种操作系统，是在各种计算机操作系统之上按网络体系结构协议标准开发的软件，包括网络管理、通讯、安全、资源共享和各种网络应用。其主要目标是计算机之间的相互通讯和资源共享。 因为现代操作系统的主要特征之一就是网络功能，因此，除了20世纪90年代初期时，Novell公司的Netware系统被称为网络操作系统之外，人们一般不再特指某个操作系统为网络操作系统,6、分布式操作系统（Distributed Operation System),大量的计算机通过网络被连接在一起，可以获得极高
12、的运算能力和广泛的数据共享。这种系统被称为分布式操作系统。,分布式操作系统具有：统一性、共享性、“透明性和自治性的特征：,统一性：它是一个统一的操作系统;,共享性：所有的分布式系统中的资源是共享的；,透明性：用户并不知道某一操作具体运行在哪一台计算机。,自治性：分布式系统中的多个主机都处于平等地位。,网络操作系统和分布式操作系统在概念上的区别是：,网络操作系统可以构架于不同的操作系统之上，通过网络协议实现网络资源的统一配置，需要显式地指明资源位置与类型，对本地资源和异地资源的访问要区别对待。,分布式强调单一性，它是一种操作系统构架的。所有资源用同一方式管理和访问，不必关心资源在哪，怎样存储。,
13、第二章 进程管理, 进程是什么 进程的状态如何 进程的互斥与同步 进程的通讯方式 操作系统如何解决进程死锁问题,第一节 进程的基本概念,通常，操作系统的重要任务之一是使用户充分、有效地利用系统中的资源，那么采用一个什么样的概念来描述用户程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的并发执行、资源共享呢？这个概念就是进程。,一、进程的定义,进程：是一个具有独立功能的程序段对某个数据集在处理机上的执行过程和分配资源的基本单位。,进程的概念是60年代初期首先在IBM的TTS/360系统中引用，人们对进程下过许多各式各样的定义： （1）进程是可以并行执行的计算部分； （2）进程是一个独立
14、的可以调度的活动； （3）进程是一实体，当它执行某个任务时，将要分配和释放各种资源。,以上定义尽管各有侧重，但在本质上是相同的，即主要注重进程是一个动态的执行过程，因此我们给出进程的一般性定义。,进程、程序的区别和关系：,b. 进程具有并行特征，而程序则没有。因为程序不反映执行过程,c. 进程是竞争计算机系统资源的基本单位，从而其并行性受到系统的制约。,d. 不同的进程可以 属于同一程序，只要该程序所对应的数据集不同。,a. 进程反映的是一个动态概念，而程序是一个静态概念；程序是指令的有序集合，没有任何执行的含义，而进程则强调的是执行过程，它动态被创建、执行和消亡。如程序是菜谱，则进程就是按照
15、菜谱炒菜的过程。,第二节 进程的描述,一个进程是一个程序对某一个数据集的执行过程，是分配资源的基本单位。那么，从处理机的活动角度来看，又如何识别和描述程序执行活动的进程呢？很显然，系统中需要有描述进程存在和能够反映其变化的物理实体，即进程的静态描述。,进程控制块PCB包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。系统根据PCB感知进程的存在和通过PCB中所包含的各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。由于进程的PCB是系统感知进程的唯一实体，所以进程的PCB结构几乎是常驻内存的。,进程的静态描述由三部分组成：进程控制块PCB(Process Co
16、ntrol Block)，有关程序段和该程序段对其进行操作的数据结构集。,进程的程序部分是描述进程所要完成的功能； 数据结构集是程序在执行时必不可少的工作区和操作对象。 这两部分是进程完成所需功能的物质基础，通常它们放在外存，直到进程执行时再调入内存。,进程描述,进程控制块PCB,有关程序段,数据结构集,一、进程控制块PCB,一般来说，不同的操作系统，PCB表所包含的内容多少有所不同，但总的来说还是大致相同的。,1、描述信息,进程的描述信息包括：进程名、用户名、家族关系。 进程名就是进程标识号，每个进程都有一个唯一的名称。 用户名就是指出该进程是隶属于哪个用户的。 家族关系是指该进程的父进程是
17、谁，即谁创建了该进程。,PCB块集中反映一个进程的动态特征。在进程并发执行时，由于资源共享，带来各进程之间的相互制约。很显然，为了反映这些制约关系和资源共享关系，在创建一个进程时，应首先创建它的PCB，然后才能根据PCB中的信息对进程实施有效的管理和控制。也就是说，PCB随着进程的创建而创建，随着进程的撤消而消亡。,2、控制信息,控制信息包括：进程当前状态、进程优先级、程序开始地址、各种计时信息、通讯信息。,进程当前状态说明进程当前处于何种状态。进程在活动期间可分为就绪态、执行态和等待状态。就绪态该进程准备占有处理机；执行态表示该进程正在占有处理机；而等待状态则表示进程因某种原因不能占有处理机
18、。,进程优先级是选取进程占有处理机的重要依据。,程序开始地址规定该进程对应的程序段以此地址开始运行。,各种计时信息给出进程占有和利用资源的有关情况。,通讯信息用来说明该进程在执行过程中与别的进程所发生的信息交换情况。,3、资源管理信息,资源管理信息包括： （1）占用内存大小、指针；（页表指针）；,（2）对换或覆盖用有关信息（对换程序段长度、外存地址），这些信息在申请、释放内存中使用；,（3）共享程序段的大小及起始地址；,（4）输入输出设备的设备号，所要传送的数据长度、缓冲区地址、及所用设备的有关数据结构指针等，这些信息在进程申请、释放设备以及数据传送中使用；,（5）指向文件系统的指针及有关标识
19、等，以便对文件系统操作。,第三节 进程的状态转换及控制,一、进程的状态及转换,任何一个事物都有他的生命期，进程也不例外。一个进程的生命期可以划分为一组状态，这些状态刻画了进程的整个生存过程。操作系统根据PCB中的状态值控制进程。,进程在其生命期内被划分为三种基本状态：就绪状态、执行状态、等待状态。,就绪状态(Ready)：刚被创建；或者等待事件发生被唤醒；,执行状态(Running)：获得处理机的使用权；,阻塞状态(Blocked)：等待某个事件的发生（I/O完成）,这只是进程的三种基本状态，有的系统可能划分得更细，但都是围绕着三个基本状态划分的。,提交,调度,时间片到,等待某个事件（内存、设
20、备等）,等待事件发生,就绪,执行,阻塞,除此之外，在有的系统中，将进程的状态进一步细分为五个状态，除了上述三个状态之外，增加了创建和退出两个状态。,创建状态（New)：进程还在创建过程中，还不能运行。 这时，操作系统要建立PCB、建立 资源表、分配资源、建立地址空间表。,退出状态（Exit)：进程运行结束，系统回收所占用资源。,创建,创建,提交,就绪,调度,执行,释放,退出,等待事件,阻塞,事件出现,超时,二、进程的控制,所谓进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态之间的转换，从而达到高效率并发执行和实现资源共享的目的。 用于进程控制的程序段有什么要求呢
21、？我们引入原语的概念。,原语：在系统状态下执行的具有特定功能的程序段称为原语，且它们在执行期间不允许被中断、不允许并发执行。,1）创建原语：就是系统为进程创建一个进程控制块PCB,并 填写PCB中相应信息项的过程。,2）撤消原语：就是系统释放进程所占有的各种资源和PCB结构本身。,导致进程撤消的原因有多种：,a. 该进程已完成所要求的功能而正常终止；,b. 该进程由于某种错误导致非正常终止；,c. 祖先进程要求撤消某个子进程；,3）阻塞原语：在一个进程期待某一事件发生，但发生条件 尚不具备时，进程调用该原语阻塞自己。,入口,保存当前进程CPU现场,置进程状态为“阻塞”,被阻塞进程入等待队列,转
22、进程调度,进程阻塞时，正处于执行状态，故先要保存CPU现场(PCB中）；另外最后转进程调度程序是很重要的，否则，处理机将会出现空转现象。,4）唤醒原语：当等待队列中的进程所等待的事件发生时， 等待该事件的所有进程都将被唤醒。但进程 本身不能自己唤醒自己，有两种方法：,a. 系统唤醒：系统统一管理和控制事件的发生，并将“发生”这一消息通知所有等待进程，而使他们进入就绪队列。,b. 事件发生进程唤醒唤醒：等待进程有事件发生进程唤醒，这时，事件发生进程和被唤醒进程之间是合作关系。,入口,从等待队列中摘下被唤醒进程,将被唤醒进程置为就绪状态,将被唤醒进程送入就绪队列,转进程调度,第四节 进程互斥,前面
23、我们已讲过，进程在执行时，各进程具有独立性和异步性等并行特征。但是，在计算机系统中，由于资源的有限必然导致进程之间对资源既有共享、又有竞争。因此并发进程的执行不仅仅是用户程序开始时间的随机性和资源利用率的问题，同时也造成了进程之间的相互制约。,一、资源共享引起的进程制约,从例题中可以看出，系统中进程相互影响的原因有二：,a. 系统内的进程共享资源（Diskreq队列，Insert程序段）；,b. 为完成同一任务的进程之间要进行协作（PHF和IOS)；,因此，我们给出两个定义：临界资源和临界区。,1、临界资源和临界区,临界资源：是指一次仅允许一个进程使用的资源。 （Critical Resour
24、ce) （Diskreq队列),临界区：最多只允许一个进程访问的程序段。 （Critical Section) （Insert程序段),2、进程互斥,定义：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。,3、并发进程互斥执行准则：,1）有空即进。并发进程中的某个进程不在临界区时，它 不阻止其它进程进入临界区。,2）择一而入。并发进程中的若干个进程申请进入临界区 时，只能允许一个进程进入。,3）限时进入。并发进程中的某个进程申请进入临界区开始，应在有限时间内得以进入临界区。,二、互
25、斥方法,进程互斥的解决方法有两种：一是由竞争各方平等协商；二是引入进程管理者，由管理者协调竞争各方对临界资源的使用。,为了保证临界资源的正确使用，我们可把临界资源的访问过程分成四部分：,进入区,退出区,a. 进入区：检查可否进入临界区；可进入，设置响应的标志，阻止其他进程。,b. 临界区：进程中访问临界资源的一段代码。,c. 退出区：将访问标志清除。,d. 退出区：代码中的其余部分。,临界区,剩余区,信号量和P、V原语,前面的互斥算法都是平等进程间的协商机制，它们存在的问题是平等协商无法解决时，需要引入一个管理者来解决公有资源的使用问题。信号量（Semaphore)就是由操作系统提供的管理公有
26、资源的有效手段。,1）信号量,信号量是一个整数，代表系统中可用资源实体的数量。,信号量 Sem,=0 表示可用临界资源的实体数；,0 表示等待使用该临界资源的 进程数,2）P、V原语,P、V是对信号量操作的两个原语操作，其中P原语操作使信号量减1，V原语操作使信号量加1。,假设系统中有一共有资源为S,并在系统中设有表示其实体数量的计数器Count和进程等待队列Queue,P、V原语操作描述如下：,P(S) -S.Count; if (S.Count0) 阻塞调用进程； 进程进入等待队列S.Queue; ,入口,-S.Count,S.Count=0,置进程为“阻塞”进入等待队列,转进程调度,返回
27、,Y,N,入口,+S.Count,S.Count0,唤醒等待队列中的一个进程,转进程调度,返回,N,Y,V(S) +S.Count; if (S.Count0) 从等待队列S.Queue 中取出一个进程； 将该进程入就绪队列； ,3）用P、V原语实现进程互斥,通过我们对临界区访问过程的分析，信号量机制中P原语相当于进入区操作，V原语相当于退出区操作。用P、V原语实现进程互斥就是将临界区置于P和V两个原语操作之间，进入时执行P操作，使信号量Sem减1，如果Sem=0,则进入临界区，否则不可进入。进程退出临界区时，执行V操作，使信号量Sem+1，表示释放临界资源。,设置互斥信号量Sem，并赋初值为
28、1 Sem=1,资源未被占用； Sem=0,资源被占用； Sem0,资源被占用，且有等待进程。,b. 描述：,P(Sem);,临界区,V(Sem),剩余区,4）进程互斥举例,例1：设有三个进程A、B、C需共享一个临界资源，用P、V操作写出其算法。,Semaphore Sem=1;Void P() while(true) P(Sem); 使用临界区； V(Sem); Void Main Parbegin Pa,Pb,Pc ,Sem Pa Pb Pc,1,P(Sem),0,P(Sem),-1,P(Sem),-2,V(Sem),-1,V(Sem),0,V(Sem),1,例3、读者-写者问题（Read
29、er-Writer Problem),在计算机系统中当若干个并发进程都要访问某个共享文件时应区分是读还是写。显然可允许多个进程同时读文件，不允许在进程读文件时让另外一进程去写文件，或者有进程在写文件时让另外一个进程去读该文件，更不允许多个外进程同时写同一文件。因此读-写进程之间关系为：“读-写”互斥、“写-写”互斥和“读-读”允许。,另外，因为允许多个进程同时读，系统应记录读进程的个数，而每个读进程去读文件或读文件结束后都要修改读者个数，因此，读者个数又是若干读进程的共享变量，即软件临界资源，它们也必须互斥地修改这个变量。,综上所述，我们定义两个互斥信号量和一个公共变量：Wmutex用于“读-
30、写”和“写-写”互斥；Rmutex用于若干读进程对读者个数修改的互斥；公共变量RCount用于记录当前正在读文件的读者数目。,过程描述：,Begin Wmutex,Rmutex:semaphore;,Rcount:integer;,Wmutex=Rmutex=1; Rcount=0;,Process Reader(I),Begin,+Rcount;,if Rcount=0,then,V(Rmutex);,ReadFile;,P(Rmutex);,-Rcount;,If Rcount=0,Then,V(Rmutex);,End;,Process Writer(I),Begin,P(Wmutex)
31、;,WriteFile;,V(Wmutex);,End;,End;,P(Rmutex);,P(Wmutex);,V(Wmutex);,第五节 进程同步,一、同步的概念,上一节我们介绍了并发进程对系统公有资源的竞争，从而引出了进程互斥的概念以及解决的办法，并发进程之间是否还存在其他制约关系呢？这就是同步问题。,例：设有计算和打印两个进程Pc和Pp,共同使用同一缓冲区Buffer，Pc向Buffer中存放计算结果，Pp从Buffer取计算结果送打印机输出。,Pc,Pp,Buffer,这两个进程的执行是相互制约的。即Pc的执行结果是Pp的执行条件；而Pp的执行结果也是Pc的执行条件，它们是相互制约的
32、。,我们把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为并发进程的直接制约，解决这种直接制约的方法称为同步。,（假设互斥已解决）,二、私有信号量,前面讲到进程互斥引入了信号量的概念，它是与所有并发进程都相关的，因此我们称其为公有信号量。那么在进程同步中，我们同样也引入信号量的概念，但它只是与制约进程和被制约进程有关，并不涉及所有的并发进程，因此我们称其为私有信号量。,上面计算进程和打印进程是相互制约的，让双方互相发送条件已经具备的信号，以协调两进程的运行，描述如下：,Pc,A:Wait(Bufferempty),计算；,计算结果送缓冲区；,Bufferfull=true
33、;,Signal(Bufferfull);,Goto A;,Pp,B:Wait(Bufferfull);,打印缓冲区中的数据；,Bufferempty=true;,Signal(Bufferempty);,Goto B;,三、用P、V原语实现进程同步,a. 为并发进程设置私有信号量；,b. 为私有信号量赋初值；,c. 用P、V原语和私有信号量实现同步。,上面例子中，我们假设缓冲区大小为n,同步过程如下：,a. 设Bufferempty为Pc进程的私有信号量，,Bufferfull为Pp进程的私有信号量，,b. 赋初值；Bufferempty=n,Bufferfull=0;,c. 实现：,Pc:
34、,Deposit(data),begin P(Bufferempty),Data BufferI;,V(Bufferfull);,end;,Pp:,Remove(data),begin P(Bufferfull);,BufferI Data;,V(Bufferempty);,end;,四、进程互斥、同步的应用,1.生产-消费者问题（Producer-Consumer Problem),如果把并发进程的互斥和同步问题一般化，我们可以得出一个抽象化的一般模型，即生产-消费者问题。在计算机系统中，每个进程都可以申请和释放各种不同类型的资源。通常把系统中申请资源的进程称为消费者，而释放资源的进程称为生
35、产者。众多并发进程共同存在于系统之中，必然要解决它们之间的互斥和同步问题。,如果我们把前面讲述的计算进程Pc和打印进程Pp互斥和同步同时考虑，就是我们要讨论的生产-消费者问题。,a. 设置公有信号量mutex，以实现互斥；,b. 设置私有信号量empty和full，以实现同步；,c. 赋初值：empty=n,full=0,mutex=1;,d. 实现deposit和remove.,Deposit(data),Begin,P(empty);,P(mutex);,data BufferunitI;,V(mutex);,V(full);,End;,Remove(data),Begin,P(full)
36、;,P(mutex);,V(mutex);,V(empty);,End;,（生产）,BufferunitI data;,（消费）,注意：P、V顺序。,第六节 进程通讯,一、进程通信方式,进程之间的通讯也就是进程之间进行信息、数据的交换。这种信息、数据的交换一般有两种：控制信息和大批量信息或数据。我们把进程之间控制信息的交换称为低级通讯；而把大批量信息、数据的交换称为高级通讯。前面我们所接触到的为了实现进程之间的同步，进程之间需要传递私有信号量，它是属于为了控制进程的执行速度而进行的低级通讯。下面我们介绍进程高级通讯的两种方式：消息缓冲机制和信箱机制。,a. 消息缓冲方式； b. 信箱方式。,一
37、、消息缓冲机制,它的基本思想是由系统统一管理一组缓冲存储区，其中每一个缓冲区存放一个消息。当发送进程要发送消息时，先想系统申请一缓冲区，然后把消息写进去，接着再把该缓冲区送到接收进程的一个消息队列中。接收进程则在适当时机从消息队列中去走所需消息，然后释放缓冲区。,由于消息缓冲机制所使用的缓冲区为公用缓冲区，两个通讯进程必须满足如下条件： a. 发送进程只有申请到空缓冲区，才能发送消息。 b. 消息队列无消息时，接收进程不能接收到任何信息。 c. 各进程对消息队列操作时，必须互斥。发送与发送，发送与接收，接收与接收。,1、消息缓冲区的结构,发送进程名,消息长度,消息正文,指针,消息缓冲区,发送消
38、息的进程名或标示符,消息的长度,消息的正文,指向下一个消息缓冲区的指针,2、进程PCB增加内容,PCB增加内容,Pm:指向进程接收到的消息队列队首的指针,Mutex:用于消息队列操作的互斥信号量。消息队列 属于临界资源，进程需互斥进行操作。,Sem:用于接收进程和发送进程之间实现同步。其值 表示接收进程消息队列中的消息个数。,接收消息的进程名或标示符,接收进程名,3、Send和Receive原语,发送进程A,接收进程B的PCB,接收进程B,.,Send(B,消息),.,接收进程名B,消息长度Size,消息正文Text,缓冲区指针,.,.,队首指针Pm,Mutex,Sem,Next,接收进程名B
39、,消息长度Size,消息正文Text,Nil,.,Receive(A,消息),.,接收进程名B,消息长度Size,消息正文Text,缓冲区指针,.,.,.,发送进程名A,发送进程名A,发送进程名A,Send(Receiver,信件）,向系统申请消息缓冲区；,将所要发送消息复制到消息缓冲区；,查找Receiver进程的PCB表；,P(Mutex);,将消息缓冲区链接到Receiver的PCB链上；,V(Mutex);,V(Sem);,返回;,Receiver(Sender,信件）,P(Sem)；,P(Mutex)；,取消息链上Receiver进程发出的消息；,将此消息复制到接收进程的接收区内;,
40、释放缓冲区；,V(Mutex);,返回;,二、信箱方式,消息缓冲方式是系统统一管理空缓冲区，为系统中所有进程共享。而信箱方式是指在发送进程和接收进程之间建立一个邮箱实现信息通信的一种方式，也就是说邮箱是发送进程和接收进程的私有数据结构。,信箱,信箱头：信箱名称、大小、传输方向、拥有该信 箱的进程名等,信箱体：存放信件。分成若干块，一块存放一个 信件。,（信箱数据结构定义及发送（SEND）、接收（RECEIVE）原语见书51）。,第七节 死锁,一、死锁的产生,前面我们介绍了多道程序环境下并发程序的执行带来的众多问题，这一节继续讨论另外一个问题死锁。,1,2,3,4,1,2,3,4,例1：交通死锁
41、,二、死锁的定义,在多道程序系统中，由于程序的并发执行，虽然提高了系统资源的利用率和系统的处理能力，但也带来了一些新的问题，如我们前面讲的互斥、同步等问题，除此之外，也可能会出现一种更危险的情况：当某一进程提出资源的使用请求后，使得系统中的一些进程处于无休止的阻塞状态，在无外力的作用下，这些进程永远都不能前进。因此我们给出死锁的定义。,死锁：是指并发进程彼此互相等待对方占有的资源，而这些 进程在得到对方占有的资源之前又不会释放自己占有 资源，从而造成进程永远无法执行的状态，,死锁不仅会给系统造成资源的浪费，甚至导致整个系统崩溃，因此我们分析一下造成死锁的因素。,二、造成死锁的因素,1) 具有多
42、个进程。多道程序环境的特点。,2) 多个资源。同类型资源多个单位；不同类型资源多个种类，如果只有一个资源，只要互斥使用即可。,3)部分分配。对各进程所需资源只分配一部分，否则无死锁。,4)申请与释放资源的动态性、分散性和独立性。动态性是指 进程申请、释放资源的随机性；分散性是指进程获取 资源后自己释放，系统无权干涉；独立性是指资源分 配与使用的分离，进程得到资源后并不一定一直使用，也可能闲置，但其他进程却无法使用。,以上因素反映了多道程序环境下并发进程与有限资源多种矛盾，因此必须解决这些矛盾，使系统有条不紊地运行。,三、死锁产生的条件,死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统
43、提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是可以采用适当的算法，达到消除死锁的目的。,1)互斥。任何资源在任何时刻只能被一个进程使用。,3)占有且等待。进程在等待申请资源的过程中，原占有资源 保持不变。,4)循环等待。发生死锁时，系统中必存在一进程循环等待链 即前一进程占有着后一进程所要求的资源。,2)非剥夺。进程占有的资源，该进程以外的进程不得抢占，只 能由占有者释放。,四、死锁的解决方法,上面四条是死锁产生的必要条件，若同时满足了这四个条件死锁便产生了。解决死锁的方法一般可分为预防、避免、检测和恢复等三种。,1、死锁
44、的预防,死锁的预防就是预先防止死锁的发生，那么只要破坏死锁产生的四个必要条件中任何一条就可以预防死锁的产生。,a. 破坏互斥。就是说允许一个资源可由多个进程同时使用，,但系统中多数资源必须互斥使用，此法不宜使用。,b. 破坏非剥夺。当某进程申请某一互斥资源时，如被拒绝， 则在进程进入阻塞状态前由操作系统剥夺或自行释放已 占有的所有资源，待以后系统再行分配。但为了保护进 程资源现场和以后的再次恢复，系统需付出高昂代价。,c. 破坏占有且等待或循环等待。为达到此目的，可以采用资 源静态分配和层次（顺序）分配两种方式：,* 静态分配方式,静态分配是指一个进程在被创建时就赋予它全部所需的资源，只有在该
45、进程所需的资源都得到满足的条件下，进程才开始执行。 此策略可以破坏占有且等待条件，可以预防死锁。但这种策略严重地降低了资源的利用率。因为这些被占有资源有的到进程执行的后半期才被使用，甚至只有例外的情况下才被用到，而其它进程又申请不到这些被占有资源。因此这种方式是低效的，原因有三：, 进程因等待所需要的资源阻塞时间过长，一部分即可；, 部分资源可能在相当长的时间内变得不可用；, 进程一次性知道所需全部资源不太可能。,* 层次（顺序）分配方式,层次分配方式的基本思想是将系统中的资源分成若干个层次，每个层次中包含有若干个资源。 某进程得到某一层的一个资源后，它只能再申请本层次或比本层次更高一层的资源
46、； 释放资源时，先释放较高层次的资源，后释放较低层次的资源； 一个进程得到某一层的资源后，若想再申请该层中的另一资源时，必须先释放该层中已占有的所有其它资源。,此种策略可防止循环等待情况的发生。此策略的一种特例就是将系统资源排成一个序列：RS1,RS2,.RSn,某进程申请了RSi(1=I=n)后不得再申请RSj(ji)。如系统中：#1:卡片读入机，#2:打印机，#3:绘图仪，#4:磁带输入机。申请：卡片读入机，绘图仪，磁带输入机予以分配。申请：打印机，卡片读入机，绘图仪不予分配。,2、死锁的检测和解除,上面讲述的各种方法虽然能很好地对死锁进行预防和避免，但它存在的问题就是资源的利用率不高，况
47、且各种算法会增加系统的开销。因此解决死锁的另一种途径就是对死锁进行检测。基本思想是系统对资源的分配不加任何限制，系统定时判断死锁是否已经出现，若检查出现了死锁，则采取一定措施解除死锁。,a. 死锁的检测方法,操作系统设置两张表格，一张表记录被阻塞进程等待资源的情况，另一张表记录已占有资源的情况，即哪些进程占有什么资源，我们不妨称其为Table1和Table2。,如果进程申请某一资源时，若该资源空闲，则进行分配，同时将该资源填资源占有情况表，即Table2;否则，阻塞该进程填写进程等待资源表，即Table1。,操作系统定期检查Table1和Table2，如果进程Pi等待Rk资源，而Rk又被Pj进
48、程占用，则认为Pi和Pj因该资源具有等,待关系，并记为W(Pi,Pj)。系统记下所有等待关系，如果出现如下序列：W(Pi,Pj),W(Pj,Pk),W(Ps,Pm),W(Pm,Pi)，则操作系统就认为系统中存在一组循环等待资源的进程：Pi,Pj,Ps,Pm,因而认为出现了死锁。,b.死锁的解除方法,如果检测到死锁，系统就必须采用某种恢复技术解除死锁：, 结束所有进程，并重新启动操作系统；, 结束所有卷入死锁的进程 ；, 一次结束卷入死锁的一个进程，然后再次检测直到死锁消失为止；, 从一个或多个卷入死锁的进程中抢占资源，把这些资源分配给卷入死锁的其它进程之一，然后恢复执行；,在实际操作系统中，一
49、般都是采用多种方法的组合，而并非采用单一的方法来解决死锁问题，如对资源进行分类，对外设类使用死锁避免的方法，而对存储系统使用预防的方法。总之，解决死锁问题要综合考虑。,第八节 处理器调度,处理器是计算机系统中的重要资源，处理器调度算法不仅对处理器的利用效率和用户进程的执行有影响，同时还与内存等其他资源的使用密切相关，对整个计算机系统的综合性能指标也有重要影响。,一、处理器调度类型,从处理器调度的对象、时间、功能等角度出发，将处理器调度分为宏观调度、中级调度和微观调度三个层次。,（1）宏观调度。从用户工作流程的角度，一个作业提交几个流程，其中每个程序按照流程进行调度执行；,（2）中级调度。涉及进
50、程在内外存之间的交换。,（3）微观调度。 也称低级调度，从处理器资源分配的角度来看，处理器需要经常选择就绪进程进入运行状态，因此微观调度的尺度是毫秒级的，宏观调度的尺度是分钟、小时或天，中级调度则是秒级的。,就绪挂起,挂起,就绪,调度,执行,释放,退出,等待事件,阻塞,事件出现,超时,阻塞挂起,激活,事件出现,激活,挂起,提交,提交,创建,宏观调度,中级调度,微观调度,三、进程调度(处理机调度)算法的功能,（1）记录系统中所有进程的执行情况。 a. 各进程的执行情况和状态特征记录在各进程的PCB表中； b. 根据各进程的状态特征和资源需求，将各进程的PCB排成相应队列并进行动态队列转换； c.
