计算机操作系统.ppt

计算机操作系统,第一章绪论,分时、实时及批处理三种系统中每种系统的特点和适用范围。OS的功能、定义、目的、类型和基本特征。时间片、多道程序设计、吞吐量、并发及并行的概念。,本章重点：,分时、实时、批处理三种系统的实现、分布式OS的实现。,本章难点：,操作系统（OperatingSystem）概念OS的历史OS的基本类型OS的功能OS的基本特征计算机硬件简介OS的初启和生成算法的描述研究OS的几种观点OS与硬件、软件、用户之间的关系小结,1.1操作系统（OperatingSystem）概念,一、系统资源：硬件+软件系统资源：让计算机工作所需要的所有东西。,系统资源,硬件资源：,软件资源,CPU，内存，I/O设备,系统软件：,应用软件：,OS和其他系统管理软件,word,电子表格，浏览器等。,结论1：,OS是系统软件。,二、计算机系统的层次结构,OS的位置,对内：所有硬件都包含在其内部，OS把所有硬件管理起来，对硬件进行全面控制，全面管理。,对外：所有软件的运行都建立在OS之上的。,结论2：OS管理计算机系统资源，方便用户,三、OS的定义,OS是计算机系统中的一种系统软件，它用于管理计算机系统的软、硬件资源，控制程序的运行，并为用户使用计算机提供方便的接口。,OS的角色：,管理员,指挥员,接待员,四、OS的目的：,提高系统资源的利用率：使计算机系统资源更好、更充分地被用户利用。,高效：提高系统的效率,方便用户：使用户更方便地使用计算机。,可扩展：系统功能和结构的扩展不影响原有功能的使用。,开放：不同的计算机及设备能集成起来并有效、正确地被使用，实现应用程序的可移植性和互操作性。,五、为什么要学习操作系统？,设计和改写操作系统,更好地选择和使用操作系统,掌握系统软件设计方法和并发程序设计方法,1.2操作系统的历史,推动操作系统发展的三个因素,计算机硬件升级以及新的硬件类型的发展,用户需求扩大，OS提供的新服务,市场的激烈竞争，OS功能的完善（修补、汉化）,OS的演变,1946-20世纪50年代末：第一代，电子管时代,计算机技术的演变,20世纪50年代末-20世纪60年代中期，第二代，晶体管时代20世纪60年代中期-20世纪70年代末，第三代，集成电路时代,20世纪70年代末期-20世纪末，第四代，大规模集超大规模集成电路时代,早期手工阶段4650年代初（无操作系统）,操作系统的演变,单道批处理58年前后,多道程序系统65年前后,分时OS66年前后,实时OS68年前后,单用户OS，网络OS70年代,分布式OS（多机OS）、嵌入式OS、智能OS90年代,1.2.1手工操作阶段,计算机运行在一个集成了指示器、开关、输入设备（读卡机）、打印机的控制台上。,特点：,人机串行,资源独占,1.2.2早期批处理,引入：为解决人-机速度不匹配,实现：通过应用一种称为监控器的软件，使用户不必直接接触机器，而是先通过卡片机和纸带机向计算机控制器提交作业，由监控器将作业组织在一起构成一批作业，然后将整批作业放入由监控器管理的输入设备上，每当一个作业执行完毕返回监控器时，监控器自动装入下一个作业。,启动,读入第一个命令,解释读入命令并执行,读入下一个命令,监控器,1.联机批处理,作业的执行过程：,（1）作业被做成穿孔纸带或卡片（2）用户提交作业：程序+数据+作业操作说明书（3）操作员有选择地把若干作业合成一批，通过输入设备（纸带输入机或者读卡机）把他们存入磁带（4）监督程序读入一个作业（5）从磁带调入汇编程序或编译程序，将用户作业源程序翻译成目标代码（6）连接装配程序把编译后的目标码及所需的子程序装配成一个可执行程序（7）启动执行（8）执行完毕，善后处理程序输出计算结果（9）读入下一个作业重复，重复（5）-（9）（10）一批作业完成，返回（3），处理下一批,单：任何时刻机器中处理的作业只有一道。批：磁带上总是有一批作业等待处理。,2.脱机批处理,卡片机,打印机,卫星机,主机,日志,输入带,输出带,执行带,系统带,作业周转时间：一道作业从提交到运行完成所需要的时间。,1.2.3多道程序系统,引入：为提高各种资源的利用率，解决I/O设备与CPU的速度差异，提高CPU与外部设备的利用率,计算,启动I/O,I/O,I/O完成,继续计算,单道批处理示意图,有什么问题？,实现：内存放两道以上的程序，CPU交替执行各程序。,程序B,CPU,输入设备,输出设备,输入结束,请求打印,CPU空,请求输入,等待CPU,CPU输入设备CPU其他I/O,程序A程序BCPU输入设备等待CPUCPU,程序A运行流程：20403020程序B运行流程：302030,程序A,程序B,程序A,在单道情况下完成程序A和程序B需要时间：20+40+30+20+30+20+30=190CPU利用率：110/190X100%=58%,在多道情况下完成程序A和程序B需要时间：20+40+30+30=120CPU利用率：110/120X100%=92%,特点：多道：计算机内存中同时放几道互相独立的程序。宏观上并行：同时进入系统中的几道程序都处于运行状态，即：都开始运行且没运行完成。微观上串行：各到程序轮流使用CPU。,实质是“宏观上并行，微观上串行。”,吞吐量：在单位时间内计算机系统完成的作业的道数。,多道程序设计：将一个以上的作业放入主存，并且同时处于运行状态，这些作业共享处理机的时间和外围设备等其他资源。,多道批处理：采用多道程序设计技术实现的批处理系统。,多道程序系统的出现标志着在操作系统渐趋成熟的阶段先后出现了作业调度管理、处理机管理、存储器管理、外部设备管理、文件系统管理等功能,1.2.4分时操作系统,引入：批处理系统采用人脱机的方式工作，但有时不方便，不能满足所有的需要。实现：一台主机外接多个终端，每个用户占一台终端（CRT+键盘，是一种只有I/O而没有CPU的设备），CPU采用把时间分片的方法轮流为每个终端用户服务（即时间片轮转的方法），保证每个用户的响应时间。,时间片：CPU的时间段，时间片的大小由操作系统决定，可以是固定时间片（每个时间段长度一般为0.2s），也可以是可变时间片。时间片一定，用户数与响应时间成反比。,分时技术：把处理机的运行时间分成很小的时间片，按时间片轮流把处理机分给各联机作业使用，若某个作业在给定的时间片内不能完成，该作业暂时中断，处理机让给其它作业，等下一轮时间继续运行。,1.2.5实时操作系统,引入：60年代中期，计算机发展进入第三代，使机器性能得到了显著的提高，应用范围迅速扩大，从传统的科学计算扩展到商业数据处理以及各行各业，如工厂的生产控制、医疗诊断、教学以及飞机订票等，尤其是它应用于高科技，如：控制导弹发射，需要根据目标及时调整方向，各种参数需要随时改变，这时分时和批处理都解决不了，就引入实时系统。即：为满足自控等方面的需求而引入实时系统，主要解决那些需要在规定时间内处理完的问题。,发展：在嵌入式计算方面得到发展，特别是移动计算等非PC机、PDA和手机等。,思考：上网查找目前有哪些常见的手机操作系统?每种系统的特点及市场占用情况。,1.2.6通用操作系统,引入：批处理系统的不断发展，分时系统的不断改进，实时系统的出现及应用范围的日益广泛，致使操作系统日益完善，出现了通用操作系统。,通用操作系统：同时兼有多道批处理，分时，实时三种系统的功能或具有其中两种系统的功能。,例：OS/400和MVS：分、批，其中CPU的分配取分时，作业分为两种，前台（终端），采用分时，后台（批处理作业）前台时间片小，后台时间片大。UNIX：通用，分时，多用户操作系统。,1.2.7操作系统的进一步发展,PC机操作系统：网络操作系统分布式操作系统智能化操作系统嵌入式操作系统,课外作业：上网查找上述每种操作系统的实例,1.3操作系统的基本类型,按用户个数单用户多用户,按任务数分单任务多任务,按CPU个数单CPU多CPU,按使用环境及对作业的处理方式批处理操作系统分时操作系统实时操作系统个人计算机操作系统网络操作系统分布式操作系统,1.3.1批处理操作系统,类型：早期大型机操作系统,特点：脱机成批多道高效作业周转时间长需要的硬件支持：20世纪60年代初期发展起来的通道和中断技术。,多道程序系统与多重处理的区别：多重处理系统配置多个CPU，是真正的多道;多道程序设计不一定是多重处理，多重处理一定是多道,适用范围：大量的科学计算，大量的数据处理（大作业）,1.3.2分时系统,工作原理：采用时间片轮转的方式使一台计算机为多个终端用户服务，保证每个用户有足够快的响应时间,特点：交互性多用户同时性独立性,分时系统是一个联机的、多用户的、交互的操作系统。UNIX是典型的分时系统。,适用范围：开发、调试、测试软件性能，小作业。,实现：解决问题的关键在于系统的正确性不仅依赖于计算的逻辑结果而且依赖于结果产生的时间。处理问题的程序常驻内存。由事件激发程序的执行。CPU要根据事件的轻重缓急进行时间分配。需要有时钟管理模块，在线的人机对话，过载保护等保证系统绝对可靠。（高度可靠性和安全性需采用冗余措施，硬件上双机热备份）特点：实时性，可靠性，安全性，专用性。适用范围：实时控制：导弹发射，飞机飞行，钢水温度，发电。实时信息处理：情报检索，银行帐目往来，飞机订票。,1.3.3实时系统,分时，批处理，实时的比较：,交互性,效率,可靠性,较高,较强,特点：同时具有批处理、分时、实时三种操作系统中两种或两种以上操作系统的功能,1.3.4通用操作系统,1.3.机操作系统,引入：微机便宜，对环境要求低，没有必要多个人使用一台计算机实现：每个用户独立联机使用一台计算机。资源独占。特点：用户界面好文件管理功能强资源管理简单安全性差（用户上机时没有用户识别），病毒泛滥,1.3.网络操作系统,引入：通信和资源共享的要求引入计算机网络，相应产生网络操作系统。实现：在单机操作系统的基础上开发，按照网络体系结构的各个协议标准开发，具有网络管理、通信、资源共享、系统安全等功能。如NETWARE两个以上带有自己的OS的计算机通过通信设施连接起来。有各方认定的标准通信规则（协议）。在单机操作系统的基础上建立一个网络操作系统负责对网络资源和网络通信进行控制和管理，并为网络提供统一的接口。,特点：自治性：有自己的CPU，自己的内存，自己的OS互连性分布性：位置分布，功能分布，处理的任务分布统一性：整个网络对用户是统一的接口是一致的功能：NOS控制网络通信管理网络资源提供多种网络服务提供网络接口。网络服务有：文件服务，打印服务，新闻服务，数据库服务。,1.3.分布式操作系统,引入：除了共享和资源共亨外，还要进行任务的协作处理，（系统中多台机器同时做一件事）分布式OS的要求比NOS高得多。实现：两台以上计算机通过通信设施连接起来。要内部的通信规则（没有统一的标准），各机器没有主次之分。整个系统有一个统一的操作系统，对系统中的所有资源进行管理，调度，对系统当中所有任务进行协调，并为用户提供接口。,特点：自治性（比网络差）：每台机器有自己的CPU，内存，无操作系统。分布性（比网络差）：分布在一个楼内或一个办公室内。模块性：机器的机型相同（只有同构才能实现任务转移）并行性功能：进行任务的协作处理,NOS与DOS比较：,侧重点,1.OS的功能,粗分：管理资源控制流程提供接口,细分处理机管理：处理机的分配和调度存储管理：内存分配，存储保护，内存扩充设备管理：设备，通道，控制器的分配和回收，设备独立性文件管理：信息共享和保护，外存空间的管理用户接口：包括程序一级的接口（系统调用）和作业一级的接口（作业管理，负责作业调度）,1.5OS的基本特征,并发并发：两个或多个事件在同一时间间隔内发生管理资源并行：两个或多个事件在同一时刻发生共享指系统中的软、硬件资源不再为某个程序所独占，而是供多个用户共同使用。,并发和共享是操作系统的两个基本特征，二者互为存在条件，一方面资源共享是以程序的并发执行为条件的，若系统不允许程序的并发执行，自然不存在共享问题；另一方面，若系统不能对资源共享实施有效管理，必将影响到程序的并发执行，甚至根本无法执行。,处理器,I/O控制器,1.6计算机硬件介绍,1.6.1计算机的基本硬件元素,PC,IR,MAR,MBR,I/OAR,I/OBR,I/O控制器,缓冲,外部设备,总线,处理器：控制和执行计算机的指令操作，包括单处理器和双处理器。存储器：存储数据和程序，分为内存和外存、缓存（buffer）和高速缓存(cache)输入输出控制与总线：控制和暂存外部设备和计算机内存之间交换的数据和程序。外部设备：获取和输出数据和程序的基本单位，包括数字设备和模拟设备。设备通过总线互相连接,1.6.2与操作系统相关的几种主要的寄存器寄存器与操作系统密切相关，因为他们是在处理机中交换数据的速度比内存快、体积小、价格贵的暂存器件。数据寄存器：理论上对数据进行操作的任何机器指令都被允许访问数据寄存器。根据硬件设置的规定，这些寄存器也可能只被允许进行浮点运算或被其他某些规定所限制地址寄存器：一般用来存放内存中某个数据或指令的地址或者存放某段数据或者指令的入口地址，例如：地址标识位寄存器内存管理用各种始地址寄存器堆栈指针设备地址寄存器,条件码寄存器：称为标志寄存器程序计数器：下一周期被执行指令的地址。指令寄存器：待执行的指令程序状态字PSW：各位代表系统中当前的各种不同状态与信息，例如是否允许中断等中断现场保护寄存器：保存被中断程序的现场信息以及链接中断恢复处。过程调用用堆栈：保存过程调用时的调用名、调用参数、返回地址,1.6.3存储器的访问速度一、存储器的种类：可移动存储介质光盘磁盘磁带硬盘磁盘缓存内存（diskcache）高速缓存寄存器,二、存储器的速度容量越大，访问速度越慢，单位存储的成本越低,寄存器,高速缓存,内存,硬盘缓存,硬盘,光盘、磁盘,访问速度,大小,除了寄存器和存储介质之外，中断机构、I/O控制（通道和DMA器件）也与OS设计相关,1.6.4命令的执行和中断一、指令的执行执行指令的过程：处理机把指令从内存读入指令寄存器和执行指令。指令的读入是根据指令计数器PC所指地址读入，执行的是指令寄存器IR中的指令。指令周期：指令的读入和指令的执行,开始,读入下一条指令,执行当前指令,结束,指令执行的类型处理机与内存之间的数据交换处理机与外部设备之间的数据交换数据处理：算逻运算对其他指令的控制过程,二、指令的中断中断：外部设备或计算机内部发生来了亟待处理的数据或其他紧急事件处理信号，处理机暂停正在执行的程序，转去处理相应的紧急事件，待处理完毕后再返回原处继续执行。指令周期：指令的读入和指令的执行,中断,指令i,指令i+1,中断处理程序,开始,读入下一条指令,执行当前指令,结束,允许中断吗？,N,检查中断位,读入中断处理指令,Y,具有中断处理的指令执行过程,一、初启（BOOT）将OS从外存内存，并对其进行初始化，这段过程叫初启。只有经过初启，系统才能正常工作。初启的过程：系统一加电就到ROM中找自检程序自检完成后，执行装入程序（在ROM中）将外存上固定位置上的一段程序（引导区中的程序）装入内存后，将控制权交给引导程序引导程序将OS装入内存中固定区域，初始化寄存器、终端设备、数据结构等，控制权交给OS。,1.7操作系统的初启和生成,二、生成根据实际硬件配置和用户需求进行优化组合生成一个更实用的OS，由于OS功能非常全面，致使OS非常庞大，若对OS重新组装，则系统中提供一个实用程序生成system，执行该程序时，提问硬件数，用户数，内存等需求，由您的需求生成一个更实用的OS每次启动时，系统会提问使用哪一个OS。DOS通过config.sys来对OS进行优化组合,1.8算法的描述,算法的开头和结束BeginEnd“条件”不满足时重复执行所描述的操作Repeat操作Until条件“条件”满足时重复执行所描述的操作While条件Do操作OD如果满足条件执行相关操作，否则执行另一种操作If条件Then操作Else操作fi,RepeatIRMPC;PCPC+1;ExecuteIR;UntilCPUhalt;,P1.n为1到n的整数置换，i=1,2,3,4,5,6,7;Pi=4,7,3,2,1,5,6描述pi的循环置换算法Beginlocalx,k;k1；whilek文件名,功能：显示已经存在的文件内容,从键盘建立新文件,将两个或两个以上文件连接成一个文件,例：显示文本文件a1的内容$cata1,例：将文本文件a1和a2连接在一起结果放入a3中$cata1a2a3,例：从键盘创建文本文件$cata4.ctrl/d$,9.rm格式：rm选择项文件1文件2，文件3.,功能：删除一个或多个文件。,说明：选择项：,-r对目录和子目录进行递归删除-i当删除无写权文件时交互式删除-f无条件删除指定的所有文件,例：递归删除目录d1及其子目录$rm-rd1,例：删除文件a3$rma3,例：交互式删除当前目录下的所有文件$rm-i*,10.cp格式1：cp-i文件1，文件2.目标文件,功能：(1)拷贝一个文件到另一个文件,(2)拷贝一个或多个文件到一个目录下，要求目标目录事先建立。,格式2：cp-ir目录1目录2,例：将文件a1复制到另一个文件abf1中$cpa1abf1,功能：(3)拷贝一个目录到另一个目录下,说明：-i拷贝时进行确认是否覆盖已存在的目标文件-r递归拷贝，用于将一个目录拷贝到另一个目录下,例：将文件a1，a2，a3，a6拷贝到目录d21下$cpa1,a2,a3,a6d21$cp-ird1d2,11.man格式：man,功能：显示指定命令的联机帮助,12.mv格式：mv-f文件1文件2.目标文件,功能：重新命名或重新分配一个或多个文件,说明：,（1）将文件改名$mva1a8,（2）将目录改名$mvu1u8,13.chmod格式：chmod方式文件名或目录名,功能：改变文件或目录的操作权限。,说明：,(1)方式可以用相应的字符或八进制数字（07）,(3)文件默认权限：-rw-rw-r-目录默认权限：drwxrwxr-x,(2)只有文件所有者和超级用户可以更改文件属性。,(4)方式：u-用户（文件主）g-同组用户o-其他用户a-全部用户+增加权限-去掉权限=赋予权限,例：构造除本人外任何人都不能读写的文件a1,例：构造文件所有者、同组用户及其它用户都可以读写的文件a2,例：用绝对修改法使文件主对文件a7有读写执行权，同组用户有读写权，其它用户只有读权,$chmod764a7,$chmoda=rwa2,$chmodgo-rwa1,14.wc格式：wc-lwc文件名,功能：显示出文件中有多少行，字，字符数,说明：,(1)若给出多个文件，则记录出每个文件的总数,（3）缺省时给出的顺序是行、字、字符数,(2)其中参数,-l仅统计行数,例：统计文件a7包含的行数,-w仅统计字数,-c仅统计字符数,$wc-la7,10a7,例：统计文件a6包含的字数和行数,$wc-wla6,8114a6,例：统计文件a1和a2分别有多少行、字和字符,$wca1a2,201001206a11012268a2301121474total,15.输入、输出重定向,（1）输入转向：SHELL从普通文件中获得输入信息,格式：命令文件名,将一个命令的执行结果存放于一个文件中。,$mailuser3文件名,将一个命令的执行结果追加到文件的尾部。,例：以长列表方式列当前目录下的文件目录，将显示结果送入文件dir下保存,$ls-ldir,例：显示当前登录的用户情况，并将显示结果追加到文件dir的尾部,$whodir,16.管道,格式：命令1|命令2,例：统计一下当前目录下有多少文件,$lsl|wc-l,三、进程管理命令,1.后台进程,格式：id=i;shared=s;publicvoidrun()while(true)shared.enteringCriticalSection(id);System.out.println(name+”isinCS”);MutualExclusion.criticalSection();shared.leavingCriticalSection(id);System.out.println(name+”isoutofCS”);MutualExclusion.nonCriticalSection();privateStringname;privateintid;privateMutualExclusionshared;,MutualExclusionabstractclass,publicabstractclassMutualExclusionpublicstaticvoidcriticalSection()tryThread.sleep(int)(Math.random()*TIME);catch(InterruptExceptione)publicstaticvoidnonCriticalSection()tryThread.sleep(int)(Math.random()*TIME);catch(InterruptExceptione)publicabstractvoidenteringCriticalSection(intt);publicabstractvoidleavingCriticalSection(intt);publicstaticfinalintTURN_0=0;publicstaticfinalintTURN_1=1;publicstaticfinalintTIME=3000;,TestAlgorithmclass,publicclassTestAlgorithmpublicstaticvoidmain(Stringargs)MutualExclusionalg=newAlgorithm_1();Workerfirst=newWorker(“Runner0”,0,alg);Workersecond=newWorker(“Runner1”,1,alg);first.start();second.start();,1.Algorithm1,publicclassAlgorithm_1extendsMutualExclusionpublicAlgorithm_1()turn=TURN_0;publicvoidenteringCriticalSection(intt)while(turn!=t)Thread.yield();publicvoidleavingCriticalSection(intt)turn=1-t;Privatevolatileintturn;,2.Algorithm2,Algorithm1的问题是只记录允许哪些进程进入临界区，没记录关于进程目前所处状态的信息，解决办法：,用booleanflag=newboolean2代替变量turnFlagi=true表示进程i准备进入临界区,publicclassAlgorithm_2extendsMutualExclusionpublicAlgorithm_2()flag0=false;flag1=false；publicvoidenteringCriticalSection(intt)intother；other=1-t；flagt=true；while(（flagother=true)Thread.yield();publicvoidleavingCriticalSection(intt)flagt=false;Privatevolatilebooleanflag=newboolean2;,3.Algorithm3,Algorithm2的问题是只记录关于进程目前所处状态的信息，解决办法：,用booleanflag=newboolean2和变量turn一起控制并发过程。Flagi=true表示进程i准备进入临界区,publicclassAlgorithm_3extendsMutualExclusionpublicAlgorithm_3()flag0=false;flag1=false；turn=TURN_0;publicvoidenteringCriticalSection(intt)intother；other=1-t；flagt=true；turn=other；while(（flagother=true)Privatevolatilebooleanflag=newboolean2,3.5.2互斥的加锁实现（测试与设置）,1.实现原理：当某个进程进入临界区之后，将临界区锁上，直到他退出临界区为止。,3.实现代码：,2.当并发进程申请进入临界区时首先测试临界区是否是上锁的，如果锁上了，就等待；否则，上锁，进入临界区。,WhileTS（Lock）DOSKIP;CSunlock（Lock）,TS（lock）TSlocklockTRUE,unlock（Lock）LockFALSE,Lock=FLASE表示临界区可用，Lock=TRUE表示临界区不可用。,设控制临界区的锁变量为：Lock,4.加锁机制存在的问题,不公平！,PaA:WhileTS（Lock）DOSKIP;CSunlock（Lock）GoToA,PBB:WhileTS（Lock）DOSKIP;CSunlock（Lock）GoToB,3.5.3信号量和P、V操作,1.信号量（Semaphore）,（1）信号量是一个整型变量,（2）与一个资源有关,（3）只能进行P操作和V操作（初始化除外）,2.P操作：申请资源,P(S:Semaphore)s=s1;if(s0)w(s);/*阻塞原语*/,3.V操作：释放资源,V(S:Semaphore)s=s+1;if(s=0)R(s);/*唤醒原语*/,P、V操作本身都是原语操作,3.5.4信号量解决互斥关系,例：SP=1打印机,P1P(SP)使用打印机V（SP）,P2P(SP)使用打印机V（SP）,P3P(SP)使用打印机V（SP）,5台打印机怎么办？,信号量S值的含义：,（1）S0表示可用资源数（2）S0|S|表示等待的进程数（3）S=0表示无可用资源，无等待进程,临界区不是原语可以被中断。,一、信号量解决同步关系,公共汽车,司机,开车,停车,关门,卖票,开门,售票员,S1,S2,S1=S2=0,P（S1）,V（S2）,P（S2）,V（S1）,3.6进程同步,二、前趋图问题。,S1,S2,S3,S4,S5,S6,S7,P1;V(S1);V(S2);V(S3);,P(S1);P2;V(S4);,P(S2);P3;V(S5);,P(S3);P4;V(S6);,P(S4);P(S5);P5;V(S7);,P(S7);P(S6);P6;,三、经典的同步互斥问题,1.生产者与消费者问题,生产者生产产品，消费者消费产品，二者共享缓冲区,(1).buffer为队列，有界，大小为n,队列有两个指针in和out，in被所有的生产者使用，out所有的消费者使用。,Mutex1：所有的生产者互斥使用in指针；Mutex2：所有的消费者互斥使用out指针。,同步信号量：Empty=n;full=0,LP:生产一个产品；,Bufferin=item;,In=(in+1),GotoLP;,modn;,P(empty);,P(mutex1);,V(mutex1);,V(full);,LC:P(full);,item=Bufferout;,out=(out+1)modn;,消费一个产品；,P(mutex2);,V(mutex2);,V(empty);,GotoLc;,Buffer,(2).buffer为堆栈，有界，大小为n,堆栈有一个指针top，被所有的生产者和所有的消费者使用。,Mutex：所有的生产者和消费者互斥使用top指针；,同步信号量：Empty=n;full=0,LP:生产一个产品；,Buffertop=item;,top=top+1,GotoLP;,P(empty);,P(mutex);,V(mutex);,V(full);,LC:P(full);,item=Buffertop;,top=top-1；,消费一个产品；,P(mutex);,V(mutex);,V(empty);,GotoLc;,Buffer,(3).buffer为队列，无界,队列有两个指针in和out，in被所有的生产者使用，out所有的消费者使用。,Mutex1：所有的生产者互斥使用in指针；Mutex2：所有的消费者互斥使用out指针。,同步信号量：full=0,LP:生产一个产品；,Bufferin=item;,In=(in+1),GotoLP;,modn;,P(mutex1);,V(mutex1);,V(full);,LC:P(full);,item=Bufferout;,out=(out+1)modn;,消费一个产品；,P(mutex2);,V(mutex2);,GotoLc;,Buffer,(4).buffer为堆栈，无界,堆栈有一个指针top，被所有的生产者和所有的消费者使用。,Mutex：所有的生产者和消费者互斥使用top指针；,同步信号量：full=0,LP:生产一个产品；,Buffertop=item;,top=top+1,GotoLP;,P(mutex);,V(mutex);,V(full);,LC:P(full);,item=Buffertop;,top=top-1；,消费一个产品；,P(mutex);,V(mutex);,GotoLc;,Buffer,2.I-C-P问题,I是输入进程负责输入数据，C是计算进程，负责进行计算；P是打印进程负责打印结果；Buffer1大小为m，被I与C共享；Buffer2大小为n，被C与P共享；buffer1和buffer2均为队列，有界。,3.读者-写者问题,m个读者，n个写者，读者可以同时读，读写不能同时进行，写写不能同时进行,今晚有课明天放假后天停水,Reading,今晚有课明天放假后天停水元旦,Writing,进入读离开,进入写离开,如何解决同步与互斥？,Readcount=0;mutextr=1;Mutexw=1;,读者：,P(mutextr);,读；,readcount-readcount+1;,if(readcount=0)P(mutexw);,V(mutexr);,readcount-readcount-1;,P(mutextr);,if(readcount=0)V(mutexw);,V(mutexr);,走;,写者：,P(mutexw);,写；,V(mutexw);,4.,A产品和B产品是配套产品，要求：nA-nBy，nB-nAx，开始时：A和B数量均为0。如何实现A，B产品的生产过程。,几个信号量？初值分别为多少？,几个同步？几个互斥？,Sa,Sb,=y,=x,A产品,P(Sa);,生产一个A；,V（Sb）;,P(Sb);,生产一个B；,V（Sa）;,开始时：A已有m个，B已有n个。怎么办？,5.吃水果,桌上有一空盘子，允许存放一只水果，爸爸可向盘子中放苹果或橘子，儿子专吃盘子中的橘子，女儿专吃盘子中的苹果，规定当盘子空时一次只能放一只水果，请用P，V操作实现爸爸、儿子、女儿三个并发进程的同步。,几个信号量？初值分别为多少？,几个同步？几个互斥？,爸爸,儿子,女儿,apple=0,orange=0,empty=1,father,Lf：empty.P();,else,if(thefruitisorange),takeafruit;,putOrangeintoDish()orange.V();,GoToLf,Ls：orange.P(),eatOrange();,empty.V();,putAppleintoDish()apple.V();,son,GoToLs,Daughter,Ld：apple.P();,eatApple();,empty.V();,GoToLd,3.7进程通信,一、引入,进程通信：在进程间传输数据。,根据通信内容分类：,典型实例：终端控制进程和终端进程,低级通信：传送控制信号的通信,高级通信：在进程间传送大量数据,二、在单机系统中的几种进程通信方式：,1.主从式：,特点：,（1）主进程可自由使用从进程的资源和数据,（2）从进程的动作受主进程的控制,（3）主进程和从进程的关系是固定的,典型实例：用户进程与磁盘管理进程之间的通信,2.会话式：通信进程双方分别称为使用进程和服务进程，使用进程调用服务进程提供的服务,特点：,（1）使用进程在使用服务进程所提供的服务之前必须得到服务进程的许可。,（2）服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成,（3）使用进程和服务进程在进行通信时有固定连接关系,3.消息或邮箱机制：无论接受进程是否已准备好接受消息，发送进程都将把所要发送的消息送入缓冲区或邮箱。,特点：,（1）只要存在空缓冲区或邮箱，发送进程就可以发送消息。,（2）发送进程和接受进程之间无直接连接关系，接受进程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进程发来的消息。,（3）发送进程和接收进程之间存在缓冲区或邮箱,消息组成,缓冲区或邮箱结构：,4.共享存储区：不要求数据移动。两个需要互相交换信息的进程通过对同一共享区的操作达到通信的目的,这个共享数据区是每个进程的一部分,三、消息缓冲机制,用send、receive原语实现进程通信,向系统申请一个消息缓冲区P(mutex)将发送区消息m送入新申请的消息缓冲区把消息缓冲区插入到接受进程的消息队列中；V(mutex)V(S),Mutex=1，S=0,Receive(发送进程，放消息的地方)P（S）P（mutex）从消息队列中取出一个消息把消息拷贝到指定的空区中，归还消息缓冲区给系统V(mutex),四、管道通信,无名管道为建立管道的进程及其子孙提供一条比特流方式传送消息的通信管道，逻辑上是管道文件，物理上由高速缓存构成，很少启动外设,发送进程利用系统调用write(fd1,buf,size)把buf中长度为size字符的消息送入管道入口fd1,接收进程利用系统调用read(fd0,buf,size)从管道出口fd0读出size字符的消息送入buf中,Unix用系统调用pipe建立管道,Intfd2；Pipe（fd）,例：,#includeMain()Intfd2；charbuf50,s50;Pipe（fd）;while(x=fork()=-1);if(x=0)sprintf(buf,”Thisisanexamplen”);write(fd1,buf,50);exit(0);elsewait(0);read(fd0,s,50);printf(“%s”,s);,3.8进程死锁,例：P1打印机绘图仪P2绘图仪打印机,Pi思考P（Si）拿左叉P（S(i-1)mod5）拿右叉；吃饭；放左叉；V（Si）放右叉V（S(i-1)mod5）;,例：哲学家就餐问题,0,1,2,3,4,思考,吃饭,例：P2、P1都需3台打印机,P2P1,一、死锁的定义：,死锁：指各并发过程彼此互相等待对方所使用的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而造成了一种僵局。如果无外力作用，这些进程永远不能再向前推进。,二、死销产生的原因,竞争资源,进程推进顺序不当,P2(Rel(R1)P2(Rel(R2)P2(Req(R1)P2(Req(R2),P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2),三、产生死锁的四个必要条件,1.互斥条件,2.部分分配,3.不剥夺条件（不可抢占）,4.环路条件,四、死锁的解决,1.死锁的预防：打破死锁存在条件中的一个或几个有三种方法：,1）打破互斥和不剥夺条件：一个已保持了某些资源的进程。若新的资源要求不能立即得到满足，它必须释放已保持的所有资源，以后需要时再重新申请，这意味着一个进程已占有的资源，在运行过程中可能暂时地释放或说被剥夺。,2）打破部分分配条件：系统要求所有进程一次性申请所需的全部资源。若系统有足够的资源分配给一个进程时，便一次把所需资源分配给该进程。这样，进程在整个运行期间为会提出任何要求，但系统浪费严重，降低了并发性。,3）打破环路条件：将所有资源编号，申请时按顺序申请，先申请小号，再申请大号，这样，能保证申请到最大号者，肯定运行完成。,2、死锁的避免,1）安全与不安全状态：允许进程动态申请资源，系统进行资源分配前先计算资源分配的安全性，若此次分配不会导致进入不安全状态，则将资源分配给进程，否则进程等待。,安全状态：指将系统按照某种顺序如来为每一个进程分配其所需资源，直到最大需求使每个进程可顺序完成，若系统不存在这样一个安全系列，则系统处于不安全状态。只要系统处于安全状态，便可避免进死锁状态。,例：三个进程P1,P2,和P3所需要磁带机10，4，9系统中其12台。,T0时刻最大需求P110P24P39,T0时刻存在一个安全序列所以系统安全。,如果P3请求1台,状态发生变化.,已分配522,可用3,还需527,找不到一个安全序列.状态不安全.请求不能满足。,如果P1请求1台,状态发生变化.结果如何？,如果P2请求1台,状态发生变化.结果又如何？,2）数据结构,（1）可用资源向量availablem:availablei代表资源i的可用资源数。初值为系统中所配置的该类资源的全部可用资源数。availablej=k;Rj类资源有k个。,(2)Maxm,n:maxi,j=k表示进程i最多需要k个Rj资源。,(3)Allocationm,n:allocationi,j=k表示进程i已分得k个Rj资源。,(4)Needm,n:needi,j=k表示进程i还需要k个Rj资源。,存在关系：Need=Max-Allocation,3)银行家算法,requesti进程Pi的请求向量。requestij=k进程Pi申请k个Rj，Pi发出请求后，系统按如下方法做.,(1)ifrequesti=Needi,thengoto(b)elseerror,(2)ifrequesti=Available,thengoto(c)elsePiwaits,(3)系统试分配,修改数据结构。,Available=Available-requestiNeedi=Needi-requestiallocationi=allocationi+requesti,(4)系统执行安全性算法，若安全，正式分配，否则，试探作废，Pi等待,恢复原来的数据结构。,4)安全性算法,设置两个向量：工作向量work,表示系统能够提供给进程的资源数；Finish，表示系统是否有足够的资源满足每个进程，初始时Work=Available，Finish=false,(2)从进程集合中找满足下列条件的进程：Finishi=false且Needi=work,(3