《操作系统第1章第4章华中科技大学版》由会员分享,可在线阅读,更多相关《操作系统第1章第4章华中科技大学版(227页珍藏版)》请在金锄头文库上搜索。
1、操作系统第操作系统第1章章-第第4章章(华中科技大学版华中科技大学版)操作系统操作系统裸机裸机应用软件应用软件用户程序用户程序操作系统的重要性操作系统的重要性地位:地位:操作系统是现代计算机、软件的操作系统是现代计算机、软件的基础基础收获:收获:通过学习操作系统的,我们可以:通过学习操作系统的,我们可以: 掌握掌握底层底层、大型软件大型软件的构造,及实现方法的构造,及实现方法2 掌握并行处理的思想掌握并行处理的思想只有一个只有一个CPU在工作在工作如何使计算机同时完成多项任务呢?如何使计算机同时完成多项任务呢? 程序间合作的方法程序间合作的方法如:多个如:多个独立独立的程序,的程序,合作合作完
2、成一项复杂任务完成一项复杂任务如何正确地保证它们如何正确地保证它们有序有序地执行呢?地执行呢? 死锁的处理死锁的处理一些复杂的系统常常会死机。一些复杂的系统常常会死机。死机的原因有那些,和程序间的合作有关吗?死机的原因有那些,和程序间的合作有关吗? 为以后进行软件系统的开发,打好基础为以后进行软件系统的开发,打好基础3 了解操作系统的基本原理、概念了解操作系统的基本原理、概念掌握操作系统的掌握操作系统的实现技术实现技术通过实例的分析,培养通过实例的分析,培养解决问题的能力解决问题的能力如何学习操作系统如何学习操作系统提问:提问:没有操作系统,计算机能否运行?没有操作系统,计算机能否运行?计算机
3、中为什么要配备操作系统计算机中为什么要配备操作系统?4配备操作系统的目的配备操作系统的目的管理各种软、硬件资源,管理各种软、硬件资源, 提高资源的利用率提高资源的利用率方便用户使用方便用户使用计算机计算机(2)(2)原理原理 并发处理:让一个并发处理:让一个CPUCPU与所有的设备同时工作与所有的设备同时工作二、操作系统二、操作系统1.早期的操作系统早期的操作系统(1)目标目标提高提高CPU的利用率的利用率,将一个物理上的单处理机,将一个物理上的单处理机改造成逻辑上的多处理机。为多个用户服务改造成逻辑上的多处理机。为多个用户服务(3)(3)采用的软件技术采用的软件技术 多道程序设计技术:多个程
4、序在内存执行多道程序设计技术:多个程序在内存执行2.当今的当今的操作系统及发展操作系统及发展 (1) (1)多样化多样化 (2) (2)注重用户操作界面的友好注重用户操作界面的友好 (3) (3)多处理机的多处理机的并行处理并行处理 (4) (4)嵌入式操作系统嵌入式操作系统 (5) (5)微软的观点微软的观点 制定资源的分配策略及实施技术制定资源的分配策略及实施技术 解决程序之间的相互制约、及合作解决程序之间的相互制约、及合作引入虚拟机的概念引入虚拟机的概念1.2 1.2 操作系统的形成和发展操作系统的形成和发展(1 1)受应用)受应用 需求需求 的推动的推动(2 2)受硬件结构、软件技术的
5、制约和推动)受硬件结构、软件技术的制约和推动从时间上,可分为三个阶段:从时间上,可分为三个阶段:形成、完善、发展形成、完善、发展从硬件载体上,可分为三个主要的分支:从硬件载体上,可分为三个主要的分支:多用户操作系统多用户操作系统(大、中、小型计算机、服务器,研究的主体大、中、小型计算机、服务器,研究的主体)单用户操作系统单用户操作系统(个人计算机个人计算机)嵌入式操作系统嵌入式操作系统(无完整的计算机无完整的计算机) 批处理批处理(出现管理软件出现管理软件) 联机联机批处理批处理 脱机脱机批处理批处理 执行执行系统系统 操作系统形成操作系统形成实时系统实时系统多道程序系统多道程序系统 多道批多
6、道批分时分时处理系统处理系统系统系统 手工操手工操作阶段作阶段(无管理软件无管理软件)多处理机、多核多处理机、多核系统系统单用户操作系统单用户操作系统网络操作系统网络操作系统分布式操作系统分布式操作系统嵌入式操作系统嵌入式操作系统操作系统形成和发展的各个阶段操作系统形成和发展的各个阶段三三.多道程序设计技术多道程序设计技术91、一个程序在内存的运行一个程序在内存的运行(单道程序设计单道程序设计)用户程序用户程序监督程序监督程序IO操作操作计算计算请求输入请求输入启动启动IO IO完成完成继续计算继续计算 结束中断结束中断中央处理机中央处理机外部设备外部设备原因?原因? 空闲空闲解决方法:解决方
7、法:在内存中,存放多个可运行的用户程序在内存中,存放多个可运行的用户程序10 2、多个多个程序在内存的运行程序在内存的运行(多道程序设计多道程序设计)CPU打印机打印机输出输出结束结束程序程序B打印打印输出输出绘图绘图输出输出绘图绘图输出输出输出结束输出结束输出结束输出结束程序程序A输出输出结束结束程序程序A程序程序B打印打印输出输出绘图仪绘图仪 空闲?空闲?11 (1)什么是什么是多道程序设计技术多道程序设计技术 在主存中同时存放几道相互在主存中同时存放几道相互独立的独立的程序程序;在管理程序控制之下,相互穿插地运行;在管理程序控制之下,相互穿插地运行;当某道程序不能继续运行时当某道程序不能
8、继续运行时(如等待外部设备如等待外部设备传输数据传输数据):便将另一道程序投入运行。便将另一道程序投入运行。12 (2)多道运行的特征多道运行的特征 多道多道 宏观上并行宏观上并行 微微观上串行观上串行执行系统采用多道程序设计技术后,就形成执行系统采用多道程序设计技术后,就形成了操作系统。了操作系统。13操作系统形成操作系统形成 批处理 手工操 作阶段 联机批处理 脱机批处理 执行 系统实时系统实时系统多道程序系统多道程序系统 多道批多道批分时分时处理系统处理系统系统系统问题:问题:只有一个只有一个CPU,在内存中运行的每一个程序,在内存中运行的每一个程序如何才能得到如何才能得到CPU 、并保
9、持、并保持对其的占有对其的占有的呢?的呢?141.什么是多道成批处理什么是多道成批处理 所有的所有的作业输入外存;作业输入外存; 根据资源条件、及根据资源条件、及调度原则调度原则选择一批作业进入内存选择一批作业进入内存 进入内存的作业按某种次序进入内存的作业按某种次序交替运行交替运行 当前运行当前运行的程序,的程序,只要不自动放弃只要不自动放弃CPU就一直运行下去就一直运行下去。即:即:CPU不能被强行剥夺不能被强行剥夺第一种:第一种:系统不干涉程序的执行系统不干涉程序的执行四四.多道成批处理、及批量操作系统多道成批处理、及批量操作系统15 2.批量操作系统批量操作系统采用多道、成批处理的操作
10、系统,称为采用多道、成批处理的操作系统,称为批量批量操作系统操作系统。也称为。也称为批处理系统批处理系统。它是操作系统的一种基本类型。它是操作系统的一种基本类型。 作业运行的方式作业运行的方式系统把用户提交的作业送入计算机外存;系统把用户提交的作业送入计算机外存;在适当的时机,由系统的在适当的时机,由系统的作业调度程序作业调度程序在外在外存选择一批作业,装入内存进行多道运行。存选择一批作业,装入内存进行多道运行。 特点:特点:脱机操作脱机操作(即:用户只需将程序提交给系统即:用户只需将程序提交给系统)合理搭配作业合理搭配作业多道运行多道运行16 优点:优点: 资源利用率高、系统吞吐量大资源利用
11、率高、系统吞吐量大缺点:缺点:(1)(1)用户作业的用户作业的周转时间周转时间长,长,或或对用户的对用户的响应时间响应时间慢;慢;(2) (2) 用户无法与程序交互,用户无法与程序交互,使用不方便使用不方便 解决?解决?第二种:第二种:由系统控制内存中各个程序的执行由系统控制内存中各个程序的执行17五五.分时技术与分时操作系统分时技术与分时操作系统1.分时技术分时技术 产生的原因:用户希望产生的原因:用户希望能与程序交互能与程序交互、有较快的有较快的响应时间快响应时间快、甚至、甚至独占计算机独占计算机 分时技术:分时技术:把处理机的时间划分成把处理机的时间划分成很短的时间片很短的时间片(如几百
12、如几百毫秒毫秒),轮流分配轮流分配给各个给各个联机联机的作业使用的作业使用如果某个作业在分配的时间片用完后,计算如果某个作业在分配的时间片用完后,计算仍未完成,就暂时中断执行,等待下一轮仍未完成,就暂时中断执行,等待下一轮18作业作业i作业作业i+1作业作业n作业作业i提问:提问:与批处理相比,与批处理相比,CPU的效率有没有降低?的效率有没有降低?即:即:CPU的占用是的占用是可剥夺可剥夺的。的。193.分时操作系统的特点分时操作系统的特点 多路调制性多路调制性(一台主机与多个用户终端设备相连接一台主机与多个用户终端设备相连接) 独占性独占性 交互性交互性 作业运行的方式作业运行的方式一台计
13、算机与多个终端设备连接一台计算机与多个终端设备连接用户以用户以联机联机的方式使用计算机的方式使用计算机因此,也称为因此,也称为交互式交互式系统系统。20六实时操作系统六实时操作系统什么是实时什么是实时?说明:说明:实时处理,实时处理,也可由也可由分时操作系统分时操作系统提供的实时处理功能来实现。提供的实时处理功能来实现。(实时用户实时用户优先优先使用使用CPU) 1.实时操作系统的定义实时操作系统的定义对外部输入的信息对外部输入的信息能够在能够在很短的、规定时间内很短的、规定时间内处理完毕处理完毕并作出反应的一种并作出反应的一种专用专用操作系统操作系统212.实时处理的类型实时处理的类型(1)
14、实时控制实时控制(必须物理实时必须物理实时)如生产过程控制、作战指挥等。如生产过程控制、作战指挥等。(2)实时信息处理实时信息处理(可以逻辑实时可以逻辑实时)如订票系统、情报检索等。如订票系统、情报检索等。3.实时操作系统的特点实时操作系统的特点 及时响应及时响应 高可靠性和安全性高可靠性和安全性 系统的整体性强系统的整体性强22 批处理 手工操 作阶段 联机批处理 脱机批处理 执行 系统 操作系统形成实时系统多处理机、多核多处理机、多核系统系统单用户操作系统单用户操作系统网络操作系统网络操作系统分布式操作系统分布式操作系统嵌入式操作系统嵌入式操作系统多道程序系统 多道批 分时处理系统 系统操
15、作系统的进一步发展操作系统的进一步发展23并行的方式:并行的方式:流水线流水线(一条指令一条指令分解为多个步骤分解为多个步骤)向量机向量机(一条指令一条指令同时在多个运算器上执行同时在多个运算器上执行)七七多运算器多运算器的单处理机系统的单处理机系统CPU特点:特点:一条指令在多个运算器上执行一条指令在多个运算器上执行目的:目的:提高计算速度提高计算速度适用性:适用性:适应面较窄,主要为适应面较窄,主要为专用专用24特点:特点:CPU可分可合可分可合分开:相当于多台主机分开:相当于多台主机合作:提高计算速度合作:提高计算速度(执行并行程序执行并行程序)多核?多核? 八多处理机系统八多处理机系统
16、cpucpucpucpu25 网络操作系统除具备一般操作系统的功能网络操作系统除具备一般操作系统的功能外,还要增加一个外,还要增加一个网络通信网络通信模块。模块。该模块由以下内容组成:该模块由以下内容组成:通信接口中断处理程序;通信接口中断处理程序;通信控制程序;通信控制程序;各级网络协议软件各级网络协议软件十网络操作系统十网络操作系统265.网络网络OS扩充的功能扩充的功能(1)节点间文件的复制、远程打印、电子邮件节点间文件的复制、远程打印、电子邮件(2)联合文件系统联合文件系统(3)程序的远程执行程序的远程执行(如通过如通过Telnet进行远程登进行远程登)6.不足之处不足之处(1)节点间
17、相互独立节点间相互独立(2)节点对用户不透明节点对用户不透明(CORBA有改进有改进)(3)要有一个集中管理的控制节点要有一个集中管理的控制节点 操作系统是一个操作系统是一个大型的大型的程序系统程序系统负责计算机的全部软、硬件资源的管理负责计算机的全部软、硬件资源的管理即:即:资源的调度和分配资源的调度和分配控制和协调并发的活动控制和协调并发的活动实现信息的存取和保护实现信息的存取和保护问题:问题:操作系统是如何对操作系统是如何对资源资源进行管理的呢?进行管理的呢?为用户使用计算机提供接口为用户使用计算机提供接口 使用户获得一个良好的工作环境使用户获得一个良好的工作环境1.3操作系统的概念操作
18、系统的概念28三、三、操作系统的操作系统的资源管理功能资源管理功能 系统资系统资源分类源分类处理机处理机主存主存 I/O设备设备软件软件资源资源操作系统操作系统功能模块功能模块处理机处理机管管理理存储存储管管理理设备设备管管理理文件文件系系统统291.4OS的特性及应解决的问题的特性及应解决的问题一、特性一、特性并发并发共享共享不确定性不确定性二、应解决的基本问题二、应解决的基本问题、提出资源分配的策略、提出资源分配的策略要考虑:要考虑:利用率、公平利用率、公平、资源的特性、资源的特性、协调并发活动的关系、协调并发活动的关系原因:并发活动也存在直接、间接的制约原因:并发活动也存在直接、间接的制
19、约多个独立的程序,进行合作的要求多个独立的程序,进行合作的要求、保证数据的、保证数据的一致性一致性保证系统及用户的程序、数据不被破坏保证系统及用户的程序、数据不被破坏避免避免与时间有关的错误与时间有关的错误、实现数据的存取控制、实现数据的存取控制操作系统的组织结构可从三个方面来描述操作系统的组织结构可从三个方面来描述(1)系统的结构:系统功能的系统的结构:系统功能的分组分组、及如何、及如何交互交互(2)接口:是接口:是用户用户、及、及用户程序用户程序使用系统的手段使用系统的手段(3)运行时的结构:定义了系统运行过程中运行时的结构:定义了系统运行过程中存在的实体类型、及调用方式存在的实体类型、及
20、调用方式2.2 2.2 操作系统的组织结构操作系统的组织结构一、系统的结构化组织一、系统的结构化组织操作系统是一组软件模块的集合。操作系统是一组软件模块的集合。为了满足系统的为了满足系统的正确性正确性、可维护性可维护性和和性能性能的要求的要求其功能模块,通常可采用多种方法来进行组织其功能模块,通常可采用多种方法来进行组织 缺点:缺点:结构不清晰,难于理解结构不清晰,难于理解难以难以维护、维护、及及验证正确性验证正确性(因因数据的交叉引用数据的交叉引用) 1.一体化结构一体化结构操作系统的所有操作系统的所有功能模块功能模块和和数据结构数据结构,放在一,放在一个个逻辑模块逻辑模块中,任何中,任何子
21、模块子模块都不提供都不提供外部接口外部接口应用软件应用软件其他系统软件其他系统软件操作系统功能模块操作系统功能模块内核功能内核功能优点:优点:通信开销小,系统效率高;安全性好通信开销小,系统效率高;安全性好应用:应用:OS问世后被许多系统采用问世后被许多系统采用典型的代表是典型的代表是UNIX系统系统,如:,如:AT&Tsystem、BSDUNIXUNIX核心的结构核心的结构 应用软件应用软件其他系统软件其他系统软件其他操作系统功能其他操作系统功能优点:优点:系统能作为系统能作为抽象数据类型抽象数据类型或或对象对象的方法来实现的方法来实现2.模块结构模块结构(采用采用面向对象面向对象技术技术)
22、操作系统的功能,通过操作系统的功能,通过逻辑独立逻辑独立的模块来划分的模块来划分而且而且相关模块间相关模块间,具有良好定义的接口,具有良好定义的接口内核功能内核功能缺点:缺点:存在潜在的存在潜在的性能退化性能退化应用:应用:还没有主要的商用操作系统采用此结构还没有主要的商用操作系统采用此结构特例:特例:一种一种试验性质试验性质的操作系统:的操作系统:Choices通过快速原型法,进行操作系统的通过快速原型法,进行操作系统的设计实验设计实验应用软件应用软件其他系统软件其他系统软件其他操作系统功能其他操作系统功能优点:优点:便于便于系统的扩充、移植,系统的扩充、移植,形成不同策略的操作系统形成不同
23、策略的操作系统3.可扩展内核结构可扩展内核结构以一个公共的以一个公共的基本功能基本功能集合集合(核心核心)为基础为基础可实现各可实现各特定特定操作系统的一种模块化组织结构操作系统的一种模块化组织结构缺点:缺点:模块间的通信开销大,降低了系统效率模块间的通信开销大,降低了系统效率应用:应用:Mach操作系统操作系统(卡内基卡内基-梅隆大学开发梅隆大学开发)WindowsNT核心功能核心功能基础核心基础核心主要支持:主要支持:微内核微内核操作系统操作系统 操作系统由操作系统由内核内核和核外的多个和核外的多个服务服务(器器)进程进程组成组成内核提供最基本的功能内核提供最基本的功能其他功能由服务器进程
24、完成其他功能由服务器进程完成(采用面向对象的采用面向对象的原则原则)安全安全调用调用进程进程管理管理本地本地过程过程虚拟虚拟内存内存I/O管理管理文件系统文件系统缓冲管理缓冲管理对象管理对象管理系系统统服服务(务(执执行行体体API) 内核内核 设设备备(网网络络)驱驱动动程程序序硬硬件件抽抽象象层层 WindowsNT的客户机服务器结构的客户机服务器结构 .层次结构层次结构操作系统由若干操作系统由若干逻辑层逻辑层组成。每一层都依赖于组成。每一层都依赖于该层该层以下各层以下各层提供的功能。提供的功能。优点:优点:易于扩充、可靠性增强、相当于多层虚拟机易于扩充、可靠性增强、相当于多层虚拟机问题:
25、问题:难于确定难于确定功能的划分功能的划分、各层的内容各层的内容和和调用顺序调用顺序问题:问题:系统过于庞大,存在大量系统过于庞大,存在大量冗余冗余第层第层用户程序用户程序第层第层输入输出管理输入输出管理第层第层操作员管理台操作员管理台第层第层存储管理存储管理第层第层CPU调度和信号量调度和信号量第层第层硬件硬件应用:应用:在一些操作系统中在一些操作系统中只是作为设计的一种指导性原则只是作为设计的一种指导性原则(尽可能尽可能)经典案例:经典案例:Dijkstr的的THE系统系统意义:意义:通过它探索了怎样通过它探索了怎样构造一个能证明其正确构造一个能证明其正确性的,操作系统的方法性的,操作系统
26、的方法结论:结论:由于分层结构的限制过于严格由于分层结构的限制过于严格还没有一个现代操作系统还没有一个现代操作系统完全完全按此方法构造按此方法构造.3 .3 基本的硬件结构基本的硬件结构指令预取指令译码指令执行指令执行地址生成回写内存内存内存U指指令令流流水水V指指令令流流水水指令预取指令预取指令译码指令译码指令执行指令执行地址生成地址生成回写内存回写内存I1I+1I+I+I 一、微机微机CPU的结构及指令的执行的结构及指令的执行 指指令令CACHE 数数据据CACHE 关键问题:关键问题:预取指令的命中率预取指令的命中率指令指令CACHE数据数据CACHE内存内存二、微机存储器的结构二、微机
27、存储器的结构外存外存CPU速度快速度快成本高成本高容量小容量小 CASH与内存的与内存的分组分组数据交换数据交换CPU512B512B512B0131块号块号512B512B512B512B512B512BCACHE内内存存 0311mm+1m+31块号块号问题:问题:在在CPU上执行的有上执行的有各种程序,它们执行时的权各种程序,它们执行时的权利是相等的吗?利是相等的吗?三、三、处理机状态及特权指令处理机状态及特权指令1. 为什么要设置处理机的状态为什么要设置处理机的状态原因:原因:系统中有两类程序:系统中有两类程序:管理程序管理程序用户程序用户程序管理系统资源提出使用资源的申请管理系统资源
28、提出使用资源的申请控制程序运行控制程序运行被控制被控制实现:实现:区分处理机的当前工作状态。区分处理机的当前工作状态。目的:目的:为操作系统建立一个为操作系统建立一个保护环境保护环境对用户程序的执行对用户程序的执行加以限制加以限制2.什么是处理机的什么是处理机的状状态态是用来表明处理机,当前正在是用来表明处理机,当前正在执行哪一类程序执行哪一类程序的一种的一种标志标志。3.处理机处理机状状态的分类态的分类(1)管态管态(Supervisormode,或,或系统态系统态) 操作系统的程序执行时,操作系统的程序执行时,处理机处理机所处的状态所处的状态在此状态下运行的程序:在此状态下运行的程序:可执
29、行全部指令可执行全部指令(包括一组所谓的包括一组所谓的特权指令特权指令)可使用系统的全部资源可使用系统的全部资源(包括整个存储区包括整个存储区)说明说明:有的系统又将有的系统又将系统态系统态进一步细分为:进一步细分为: 核态:核态:操作系统的操作系统的内核内核执行时,执行时,处理机处理机所处所处的状态。在此状态下:的状态。在此状态下:可执行全部的指令可执行全部的指令(包括包括特权指令特权指令)使用全部的系统资源。使用全部的系统资源。 管态:管态:操作系统的操作系统的管理程序管理程序执行时所处的状执行时所处的状态。在此状态下:态。在此状态下:仅可使用系统的部分资源仅可使用系统的部分资源不能执行特
30、权指令。不能执行特权指令。 (2)用户态用户态(Usermode)用户程序执行时,机器所处的状态。用户程序执行时,机器所处的状态。在此态下:在此态下:禁止使用特权指令、及修改机器状态禁止使用特权指令、及修改机器状态不能直接使用资源不能直接使用资源只允许访问程序自己的存储区只允许访问程序自己的存储区某个事件某个事件发生时发生时:(如如I/ /O结束、电源掉电、定点加溢出等结束、电源掉电、定点加溢出等)系统中止现行程序的运行;系统中止现行程序的运行;引出处理该事件的程序,对该事件进行处理;引出处理该事件的程序,对该事件进行处理;处理完毕后返回断点继续执行。处理完毕后返回断点继续执行。一、一、中断的
31、概念中断的概念正在执行正在执行的的程程序序继续执行继续执行中断处中断处理程序理程序中断进入中断进入中断中断返回返回1.4中断技术中断技术所谓中断是指:所谓中断是指:可以认为:可以认为:现代操作系统的一切机制,都是由中断来激活的现代操作系统的一切机制,都是由中断来激活的二、二、中断的类型中断的类型按中断信号的来源可分为按中断信号的来源可分为(1)外中断外中断(中断中断)由处理机外部事件引起的中断称为外中断,由处理机外部事件引起的中断称为外中断,简称为中断。包括简称为中断。包括输入输出中断、外中断输入输出中断、外中断。(2)内中断内中断(俘获俘获)由处理机内部事件引起的中断称为内中断,由处理机内部
32、事件引起的中断称为内中断,又称为俘获又称为俘获(或陷阱、陷入:或陷阱、陷入:Trap)。包括。包括:访管中断、程序性中断、机器故障中断访管中断、程序性中断、机器故障中断等等 三、三、中断进入中断进入 要解决的问题:要解决的问题:(1)如何判别中断是否发生,及是哪一种中断?如何判别中断是否发生,及是哪一种中断?(2)如何保证中断如何保证中断处理完后返回断点继续执行?处理完后返回断点继续执行?(3)如何得到该中断处理程序的地址?如何得到该中断处理程序的地址?正在执行的用正在执行的用户程序户程序继续执行继续执行中断处中断处理程序理程序中断进入中断进入中断中断返回返回另一种方式另一种方式:外部设备也可
33、通过总线来传递中断码外部设备也可通过总线来传递中断码 7 6 5 4 3 2 1 0 0 0 0 1 0 0 0 0CPU中断码:中断码:00010000外部设备外部设备.外外中断中断触发器触发器问题问题2:如何保证中断如何保证中断处理完后,返回断点继续执行?处理完后,返回断点继续执行?.保护现场和恢复现场保护现场和恢复现场(1)现场现场指在中断的那一时刻,能确保指在中断的那一时刻,能确保当前运行程序当前运行程序继续运行的有关信息。主要包括三类:继续运行的有关信息。主要包括三类:后继指令的主存地址后继指令的主存地址程序运行时所处的状态程序运行时所处的状态当前当前指令的执行情况指令的执行情况各种
34、通用寄存器中的内容各种通用寄存器中的内容 (2)保护保护现场现场当中断发生时,必须立即把当前运行程序的当中断发生时,必须立即把当前运行程序的现场信息现场信息保存在保存在主存主存中,称之为保护现场。中,称之为保护现场。问题:问题:除通用寄存器外,除通用寄存器外,其余的现场信息又是放在什么地方呢?其余的现场信息又是放在什么地方呢?(3)恢复恢复现场现场被中断的程序重新运行之前,把该程序的现被中断的程序重新运行之前,把该程序的现场信息,从主存送至原有的现场环境中。场信息,从主存送至原有的现场环境中。称为恢复现场。称为恢复现场。 .程序状态字程序状态字(PSW) (1)什么是程序状态字什么是程序状态字
35、程序状态字是反映程序执行时,当前机器程序状态字是反映程序执行时,当前机器状态状态(在在指令一级指令一级)的一组代码。的一组代码。主要内容包括:主要内容包括:后继指令的内存地址后继指令的内存地址当前指令执行情况当前指令执行情况机器处于何种状态机器处于何种状态程序执行时应程序执行时应屏蔽屏蔽的中断的中断(为什么为什么?)寻址方法、编址、保护键寻址方法、编址、保护键 (2)程序状态字的实例程序状态字的实例 IBM370机机运行程序的运行程序的PSW放在放在程序状态字寄存器程序状态字寄存器中中 PC机机(DOS)CS及及IP指令地址指令地址lag标志寄存器标志寄存器 PDP11系列机系列机PC指令计数
36、器指令计数器PS处理器状态寄存器处理器状态寄存器(见见P38图图2.10)问题问题3:如何得到如何得到中断处理程序中断处理程序的地址?的地址? .中断向量中断向量中断向量:中断向量:存放在内存中的,某类中断处理程序的存放在内存中的,某类中断处理程序的入口入口地址、地址、及及处理器状态字处理器状态字的内容的内容中断向量表中断向量表:用于存放各类中断向量的一组连续的主存单用于存放各类中断向量的一组连续的主存单元。元。通常在内存的低地址端。通常在内存的低地址端。为什么?为什么? (1)什么是中断响应什么是中断响应中断响应是指:中断响应是指:当中央处理机发现已有中断请求时,当中央处理机发现已有中断请求
37、时,中止现行程序的执行,并自动引出中断处中止现行程序的执行,并自动引出中断处理程序的过程。理程序的过程。 .中断响应中断响应 (2)中断响应过程的图示中断响应过程的图示 PC进栈进栈PS进栈进栈中断处理程序的中断处理程序的PC中断处理程序的中断处理程序的PS向量向量堆栈堆栈PCPS堆栈栈堆栈栈顶指针顶指针 (1)(2) (3)中断响应的实质中断响应的实质 交换指令地址及处理机的状态信息,达到:交换指令地址及处理机的状态信息,达到: 保留程序断点及处理机有关信息保留程序断点及处理机有关信息 自动转入相应的中断处理程序执行自动转入相应的中断处理程序执行 思考思考:中断响应的功能,能否由由软件来完成
38、?中断响应的功能,能否由由软件来完成? 6.中断进入及处理的全过程中断进入及处理的全过程 *k k+1当前执行程序当前执行程序 PSPC* * * * * * * L0 0 0 0 0 0 0 0 L PS PC*k+1 中中断断处处理理程程序序3级中断级中断 k + 1 1 L k+1 中中断断触触 发发 器器四四. 软件完成的软件完成的中断处理功能中断处理功能当硬件完成了中断进入过程后,由相应的当硬件完成了中断进入过程后,由相应的中断处理程序得到中断处理程序得到CPU的控制权,进入了由的控制权,进入了由软件实现软件实现的中断处理过程。的中断处理过程。 保留被中断程序的现场保留被中断程序的现
39、场 进入相应的进入相应的中断服务中断服务例程例程 恢复被中断程序的现场恢复被中断程序的现场中断中断返回返回中中 断断进入进入k+0现行程序现行程序k+1 例:例:UNIX的时钟中断处理的时钟中断处理时时钟钟中中断断处处理理,是是UNIX中中最最具具代代表表性性的的中中断处理程序。其完成的功能如下:断处理程序。其完成的功能如下:1、重新启动时钟、重新启动时钟当当时时钟钟中中断断发发生生后后,有有些些处处理理机机要要求求由由软软件指令重新启动时钟件指令重新启动时钟(重新计时重新计时)。从从而而在在适适当当的的时时间间间间隔隔后后,能能再再次次中中断断处处理机。理机。 2、系统内部定时(内部闹钟)、
40、系统内部定时(内部闹钟)有些系统操作,如设备驱动,要求有些系统操作,如设备驱动,要求延延时调时调用用核心的一些函数,则可用到系统内部定时。核心的一些函数,则可用到系统内部定时。如用户敲回车键会产生一个键盘中断。如用户敲回车键会产生一个键盘中断。但也可以使终端处于原始方式:但也可以使终端处于原始方式:核心在固定的时间间隔后,核心在固定的时间间隔后,自动读键盘输入自动读键盘输入的内容的内容,而不必等待用户敲回车键。,而不必等待用户敲回车键。(如从键盘输入大量的数据如从键盘输入大量的数据) 3、统计程序执行的频度、统计程序执行的频度用程序统计直方图来描述:用程序统计直方图来描述:某个程序执行时,该程
41、序的某个程序执行时,该程序的各个部分各个部分在内存在内存中被访问的频度中被访问的频度4、计算进程的优先数、计算进程的优先数用于调整进程优先数的有关参数用于调整进程优先数的有关参数计算某些进程的优先数计算某些进程的优先数(每秒钟每秒钟) UNIX的中断处理过程的中断处理过程 1 1、中断的中断的总控程序总控程序当当出出现现中中断断后后,系系统统转转到到中中断断的的总总控控程程序序统统一进行处理。完成的工作是:一进行处理。完成的工作是:保护现场保护现场为中断处理程序,产生并传递为中断处理程序,产生并传递参数参数通过中断向量,调用相应的通过中断向量,调用相应的中断处理程序中断处理程序2、中断处理程序
42、中断处理程序进行中断服务,进行中断服务,完成后返回到完成后返回到总控程序总控程序 3、总控程序:总控程序:对对中断前的处理机状态中断前的处理机状态进行判别。进行判别。(1)若中断若中断(或陷入或陷入)前在前在核态核态下运行:下运行:恢复现场,返回断点恢复现场,返回断点(2)若中断若中断(或陷入或陷入)前在前在用户态用户态下运行,且下运行,且重调度标志重调度标志未设:恢复现场,返回断点未设:恢复现场,返回断点重调度标志重调度标志已设:已设:转进程调度程序转进程调度程序 3.1 3.1 用户工作环境用户工作环境一、一、用户环境用户环境有了操作系统后,用户是通过操作系统来有了操作系统后,用户是通过操
43、作系统来使用计算机。使用计算机。即:操作系统必须为即:操作系统必须为每个用户每个用户提供一个使提供一个使用计算机的用计算机的工作环境工作环境(称为称为用户环境用户环境)。问题:问题:不同的不同的用户环境,是如何产生的呢?用户环境,是如何产生的呢?66二、二、系统生成系统生成 系统生成现在也称为安装。系统生成现在也称为安装。通常是指:通常是指:为了满足物理设备的约束和对系统功能的为了满足物理设备的约束和对系统功能的需求,通过组装一批模块,产生一个清晰的、需求,通过组装一批模块,产生一个清晰的、使用方便的操作系统的过程。使用方便的操作系统的过程。根据自己的经验根据自己的经验思考:思考:通过安装可完
44、成什么工作?通过安装可完成什么工作?哪些软件要安装?哪些软件要安装?67三、三、系统初启系统初启 系统初启又称为系统初启又称为系统引导系统引导。 其任务是:其任务是: 将将操作系统的必要部分,装入内存并执行操作系统的必要部分,装入内存并执行系统引导的过程:系统引导的过程: 可分为三个阶段来实现可分为三个阶段来实现68(1)初始引导初始引导也称为也称为自举自举。即:。即:操作系统操作系统把自己装入内存把自己装入内存(DOS如何实现的?如何实现的?)(2)核心核心初始化初始化建立系统的建立系统的数据结构数据结构,执行系统的,执行系统的常驻程序常驻程序等等(3)系统系统初始化初始化执行执行命令处理程
45、序命令处理程序,使系统处于命令接受状态,使系统处于命令接受状态69.操作系统的用户界面操作系统的用户界面一、操作系统的一、操作系统的用户界面用户界面 1.什么是操作系统的用户界面什么是操作系统的用户界面 操作系统的用户界面操作系统的用户界面(或称接口或称接口),是操作系,是操作系统提供的,用户与计算机打交道的统提供的,用户与计算机打交道的外部机制外部机制。即:即:可实现的功能,及使用的方式。可实现的功能,及使用的方式。用户借助这种机制,来控制计算机系统。用户借助这种机制,来控制计算机系统。70 2.用户界面的形式用户界面的形式 (1)操作命令操作命令(命令接口命令接口)用户用户使用操作命令,来
46、使用操作命令,来组织组织上机的工作流程、上机的工作流程、控制控制程序的运行程序的运行(2)系统功能调用系统功能调用(程序接口程序接口)用户程序用户程序在其运行过程中,使用系统功能调在其运行过程中,使用系统功能调用,来用,来请求请求操作系统的服务操作系统的服务71用户界面的实例用户界面的实例 DOS:键盘命令键盘命令(命令接口命令接口)、系统功能调用系统功能调用Windows:图形用户界面图形用户界面(命令接口命令接口)、系统功能调用系统功能调用unix(及及linux):键盘命令、图形用户界面键盘命令、图形用户界面(命令接口命令接口)系统功能调用系统功能调用72二、操作命令二、操作命令根据上机
47、方式的不同,操作命令可分为二种根据上机方式的不同,操作命令可分为二种类型类型(目前有三种方式目前有三种方式): 作业控制语言:作业控制语言:用于用于脱机脱机操作。如:操作。如:批处理操作系统批处理操作系统 键盘命令:键盘命令:用于用于交互式交互式操作。如:操作。如:分时操作系统、个人计算机操作系统分时操作系统、个人计算机操作系统 图形用户界面图形用户界面:是键盘命令的另一种表现形式是键盘命令的另一种表现形式73 1.作业控制语言作业控制语言在在批处理批处理或或脱机脱机操作的方式下操作的方式下由于用户不能使用终端由于用户不能使用终端故故不能直接参与不能直接参与上机的过程。上机的过程。系统提供作业
48、控制语言系统提供作业控制语言(JCL)让用户让用户预先制定预先制定自己上机操作的完整过程。自己上机操作的完整过程。74(1)什么是作业控制语言什么是作业控制语言是一种命令语言。是一种命令语言。其内容包括:其内容包括:对作业进行处理的对作业进行处理的操作命令操作命令对资源的对资源的请求命令请求命令对上机过程进行组织、控制的对上机过程进行组织、控制的语句语句75(2)批处理系统中作业的组成批处理系统中作业的组成 作业申请作业申请,内容包括:,内容包括:作业名作业名需用需用CPU时间时间最迟完成时间最迟完成时间资源请求资源请求(如:主存、外设如:主存、外设)等等 操作说明书操作说明书用用作业控制语言
49、编写的作业控制语言编写的命令程序命令程序。内容包括:。内容包括:76操作命令操作命令如:编译、连接、运行等如:编译、连接、运行等干预控制语句干预控制语句如:判别、选择、循环等如:判别、选择、循环等 执行程序与数据执行程序与数据(3)上机的环境上机的环境批处理系统批处理系统分时系统的分时系统的后台后台操作操作77 2.键盘命令键盘命令在交互式系统中,为联机用户在交互式系统中,为联机用户(交互用户交互用户)提提供的操作命令。供的操作命令。由用户自己,通过由用户自己,通过键盘键盘输入这些命令,组织输入这些命令,组织上机的过程,控制和干预程序的运行上机的过程,控制和干预程序的运行。因此,称为键盘命令因
50、此,称为键盘命令(1)用户上机的过程用户上机的过程先注册一个帐号,成为系统的合法用户先注册一个帐号,成为系统的合法用户上机的过程是:上机的过程是:78(a)登录登录(Login)通过输入用户名和口令。用于:通过输入用户名和口令。用于:验证用户的合法性、建立用户所需要的环境验证用户的合法性、建立用户所需要的环境(b)通信通信用户与计算机之间的用户与计算机之间的交互操作交互操作。用于:。用于:申请资源、控制上机过程、运行程序等。申请资源、控制上机过程、运行程序等。(c)注销注销(Logout)退出系统。退出系统。目的:目的:终止系统的记帐终止系统的记帐保护用户免受他人的侵害保护用户免受他人的侵害7
51、93、与用户进行交互的处理程序、与用户进行交互的处理程序DOD:COMMANFD.COM(称为命令处理程序称为命令处理程序)UNIX:shell(通常称为外壳程序通常称为外壳程序)WINDOWS:桌面管理程序桌面管理程序 SCOOpenServer的操作的操作、启动、启动(服务器服务器)开机开机 :、用户注册、用户注册(接上面、或开终端接上面、或开终端)Login:输入注册名输入注册名(帐号帐号)Password:输入口令输入口令(重复一次重复一次)$1)单用户单用户(用于系统维护用于系统维护):输入输入root的口令的口令 2)多用户多用户(提供上机服务提供上机服务):按按Ctrl+DLog
52、in:81、操作命令、操作命令1)命令格式命令格式命令名命令名选择项参数参数选择项参数参数例:用长格式例:用长格式显示根目录下、子目录显示根目录下、子目录user的内容的内容$ls-l/user 822)联机帮助联机帮助(显示命令参考手册显示命令参考手册)格式:格式:man选择项选择项sectiontitlesction:分类:分类title:标题:标题(待了解项待了解项)例例1:了解命令:了解命令date的使用。的使用。$mandate例例2:显示系统中的所有命令。:显示系统中的所有命令。$ls/binmore或或ls/bin/dev/lp834、用户的注销、用户的注销$按按Ctrl+DLo
53、gin:5、由多用户转为单用户环境、由多用户转为单用户环境权限:权限:root用户用户目的:目的:进行系统维护进行系统维护shutdown-gnsu/*n为一整数,表示延迟的时间为一整数,表示延迟的时间(分钟分钟)846、关闭整个系统、关闭整个系统权限:权限:root用户用户1)为用户保留准备时间为用户保留准备时间shutdown-gn2)不保留准备时间不保留准备时间etc/haltsys85三三.图形图形化化用户界面用户界面1.什么是图形化的用户界面什么是图形化的用户界面图形化界面是一种更友好的用户交互界面图形化界面是一种更友好的用户交互界面它将它将菜单驱动、图符驱动、面向对象菜单驱动、图符
54、驱动、面向对象技术等技术等集成在一起。集成在一起。形成一个图文并茂的操作环境。形成一个图文并茂的操作环境。与用户进行交互的处理程序:与用户进行交互的处理程序:屏幕管理程序屏幕管理程序User86它涉及到二个方面:它涉及到二个方面: (1)操作系统提供实现各种功能的操作系统提供实现各种功能的系统子例程系统子例程(2)执行方式执行方式在在程序中使用程序中使用访管指令访管指令通过访管中断通过访管中断(软中断软中断)实现对系统例程的调用实现对系统例程的调用(简称为简称为系统调用系统调用)四、系统功能调用四、系统功能调用 1.程序中如何使用程序中如何使用OS供的服务?供的服务?87 应用程序应用程序 系
55、统调用系统调用 中央中央处理机处理机 存储器存储器 系系统统程程序序 外外部部设设备备 88 2.访管指令的访管指令的汇编语言汇编语言形式形式一般形式:一般形式:svcnsvc:访管指令的操作码记忆符:访管指令的操作码记忆符n:地址码:地址码(功能号功能号)UNIX:trapn用户程序中使用用户程序中使用emtnPDP11中中系统程序系统程序使用使用DOS:nAHint21H89(1)在汇编语言中:显式调用。如在汇编语言中:显式调用。如DOS中:中: 功能号功能号 寄存器寄存器ahint213.调用方式调用方式(3)在在C语言中:既可隐式调用、又可显式调用语言中:既可隐式调用、又可显式调用Un
56、ix中每个系统调用都有一个中每个系统调用都有一个C的函数形式的函数形式如:如:trap3read()(2)在一般高级语言中:隐式调用。如:在一般高级语言中:隐式调用。如: read()(4)有有些系统允许嵌入系统调用的汇编形式些系统允许嵌入系统调用的汇编形式 4.什么是系统功能调用什么是系统功能调用系统功能调用是用户系统功能调用是用户在程序一级请求操作系在程序一级请求操作系统服务的一种手段统服务的一种手段它不是硬件指令,它不是硬件指令,而是带有功能号的而是带有功能号的“访管指令访管指令”其功能由其功能由操作系统中的操作系统中的一段程序来完成一段程序来完成(与硬件指令的区别与硬件指令的区别)并由
57、访管并由访管(软软)中断转入中断转入(与子程序调用的区别与子程序调用的区别) 916.子例程的连接方式子例程的连接方式(1)常规的例程库常规的例程库子例程子例程静态连接静态连接(嵌入嵌入)到主程序的执行程序中到主程序的执行程序中问题:问题:没有实现共享,浪费内存没有实现共享,浪费内存5.访管中断访管中断执行访管指令时发生的中断,称为访管中断执行访管指令时发生的中断,称为访管中断表示当前运行程序对操作系统的某种服务请求表示当前运行程序对操作系统的某种服务请求思考:思考:为什么要用中断来转入呢?为什么要用中断来转入呢?(2)系统功能调用系统功能调用在运行程序在运行程序执行系统功能调用时执行系统功能
58、调用时,通过中断,通过中断的方式,转入内存的子例程执行。的方式,转入内存的子例程执行。局限性:局限性:系统功能调用的子例程必须全部常驻内存系统功能调用的子例程必须全部常驻内存若子例程的数量很庞大,且调用频度不均衡,若子例程的数量很庞大,且调用频度不均衡,则仍然会降低内存的利用率;则仍然会降低内存的利用率;因此,只适用于少量的因此,只适用于少量的系统常用子例程系统常用子例程(3)动态连接动态连接(动态连接库或运行时间库动态连接库或运行时间库)在应用程序在应用程序装入、或执行调用时装入、或执行调用时,才与子例,才与子例程进行链接。程进行链接。如如Windows中,应用程序与中,应用程序与外部函数外
59、部函数的连接的连接(包括包括设备驱动程序设备驱动程序)(a)在应用程序连接在应用程序连接(Link)时:时:为为每一个每一个外部函数都建立一个引用外部函数都建立一个引用人口号人口号以及该外部函数的以及该外部函数的调用链表调用链表记录其在应用程序中各个记录其在应用程序中各个调用点调用点的位置的位置(b)在应用程序装入后:在应用程序装入后: 搜索搜索所有所有外部函数的调用链表外部函数的调用链表 对其中的对其中的每一个每一个外部函数外部函数 搜索搜索外部函数外部函数(DLL中的引出函数中的引出函数)模块表模块表判别判别该该函数是否已装入内存函数是否已装入内存 若已装入:将其在若已装入:将其在模块表模
60、块表中的中的引用数引用数加加1否则:否则:装入该函数,将引用数置为装入该函数,将引用数置为1 将该外部函数的将该外部函数的入口地址入口地址填写到其调用链表的每一个节点上填写到其调用链表的每一个节点上 7.系统功能调用的实现系统功能调用的实现 例行子程序例行子程序Sub 0Sub 1Sub2Sub na0a1anam a1a0an例行子程序例行子程序入口地址表入口地址表A+0A+1A+n 保护现场保护现场取取n值值按按n值散转值散转恢复现场恢复现场访管中断访管中断处理程序处理程序 svcn用户程序用户程序+A 96一、系统调用的分类一、系统调用的分类 UNIX UNIX系统中,系统调用大致可分为
61、系统中,系统调用大致可分为进程管理进程管理、文件系统的应用文件系统的应用(含设备)和(含设备)和系统状态的设置系统状态的设置三类。三类。 1. 1.有关进程管理的系统调用有关进程管理的系统调用 fork fork 创建一个子进程创建一个子进程 exit exit 进程终止进程终止 exec exec 执行用户程序执行用户程序 wait wait 等待子进程终止等待子进程终止 3.43.4 UNIX的的系统调用系统调用 sleepsleep 进程睡眠进程睡眠Wakeup Wakeup 进程唤醒进程唤醒nice nice 设置进程的优先数设置进程的优先数 2.2.与文件有关的系统调用与文件有关的系
62、统调用 openopen 打开文件打开文件 closeclose 关闭文件关闭文件 readread 读文件读文件 writewrite 写文件写文件 lseeklseek 修改读写指针修改读写指针link连接文件(取别名)连接文件(取别名) unlink取消连接(及删除文件)取消连接(及删除文件) mount安装子文件系统安装子文件系统unmount拆卸子文件系统拆卸子文件系统. 3.与系统状态有关的系统调用与系统状态有关的系统调用getuid取取用户号用户号setuid设置用户号设置用户号getgid取取用户组号用户组号setgid设置用户组号设置用户组号time取日历时间取日历时间sti
63、me设置日历时间设置日历时间times取进程执行时间取进程执行时间 2、trap指令指令 traptrap的机器指令,用八进制表示为:的机器指令,用八进制表示为: 1044 104400 00 104410447777 前前4 4位为指令码,后位为指令码,后2 2位位为系统调用为系统调用功能号功能号( (最多最多6464种种) ) 二、二、系统调用的数据结构和实现系统调用的数据结构和实现 UNIXUNIX中,系统调用是由自陷指令中,系统调用是由自陷指令traptrap来实现的来实现的。 它是它是 PDP 11 PDP 11 的的4 4种种软中断机制软中断机制之一之一。1、trap向量向量tra
64、p属于俘获类型,中断向量地址为属于俘获类型,中断向量地址为034、036单元单元PS值为:值为:340+6(6为俘获类型号,用于系统调用为俘获类型号,用于系统调用)3、系统调用入口参数表、系统调用入口参数表描述了每个系统调用的描述了每个系统调用的入口地址入口地址、和传递、和传递参参数的个数数的个数。定义为:。定义为:structsysentintcount;/*参数的个数参数的个数*/int(*call)();/*执行程序人口地址执行程序人口地址*/sysent;系统初始化后,系统调用表如下:系统初始化后,系统调用表如下: intsysent0,&nullsys, /*0=indir*/ 0,
65、&rexit,/*1=exit*/0,&fork,/*2=fork*/2,&read,/*3=read*/,0,&nosys,/*49=x*/,0,&nosys,/*63=x*/; nosys()nosys() u.u_error = 100; u.u_error = 100; 是一个非法的系统调用是一个非法的系统调用( (没有用到没有用到) )该系统调用,将返回一个系统调用失败的错误码。该系统调用,将返回一个系统调用失败的错误码。 更详细的细节见:更详细的细节见:P59:图:图3.5 4、系统调用的实现过程、系统调用的实现过程6 6、系统调用、系统调用执行执行的实例的实例 ( (readre
66、ad) )(1)C语言形式语言形式charbufferintnbytesfiles=open(.)read(files,buffer,nbytes)(2)生成的部分汇编代码)生成的部分汇编代码(id=3)/*设置命令的操作数,为设置命令的操作数,为reab的功能号的功能号3(files=r0)/*寄存器寄存器r0,专用于程序间传递,专用于程序间传递第第0个参数个参数sysid/*目标代码为:目标代码为:104403(即即104400+3,见见P58)buffer/*系统调用的系统调用的第第1个参数个参数nbytes/*系统调用的系统调用的第第2个参数个参数(a)中断响应:中断响应:将当前进程的
67、将当前进程的PC、PS的压入核心栈的压入核心栈中断向量:中断向量:(034)=PC、(036)=340+6 =PS转入转入俘获总控程序俘获总控程序(入口地址为入口地址为trap)(b)俘获俘获总控程序执行:总控程序执行:保护现场保护现场(包括:寄存器包括:寄存器r0=u.u_aror0)由由俘获类型俘获类型:dev=6,转入,转入系统调用分支程序系统调用分支程序(3)sys指令的指令的执行过程执行过程(c)系统调用分支程序系统调用分支程序执行执行:取系统调用功能号取系统调用功能号(即:即:sys指令的操作数指令的操作数 3)从从system3,得到,得到read的入口地址、参数个数的入口地址、
68、参数个数根据根据read的参数个数的参数个数2:将断点后将断点后2个参数复制到当前进程的个参数复制到当前进程的user区保存单元区保存单元u.u_arg0、u.u_arg1将将PC的值加的值加4,使断点后移,使断点后移4个字节个字节(2个指令个指令字字)(d)read子例程子例程执行:执行:完成读操作后,实际传输数完成读操作后,实际传输数=u.u_aror0作为返回值作为返回值(f)俘获俘获总控程序总控程序执行执行:恢复现场,返回新断点自继续执行恢复现场,返回新断点自继续执行(或或调度其他进程调度其他进程)(e)系统调用分支程序系统调用分支程序俘获俘获总控程序总控程序将将user区中,区中,u
69、.u_aro0的值,复制到的值,复制到r0寄存器寄存器(作为传递给子程序参数作为传递给子程序参数),然后转,然后转read子例程子例程 3.5 3.5 UNIX的的命令程序命令程序设计语言设计语言shell特点:特点:可将可将程序设计元素程序设计元素、与多个独立的与多个独立的UNIX执行执行程序程序(或命令或命令)组成一个组成一个shell过程过程,存放在一个文,存放在一个文件中件中(通常称为通常称为命令处理文件命令处理文件)。通过该文件,通过该文件,集成集成为一个逻辑整体为一个逻辑整体(应用系统应用系统)shell过程中,可包括的过程中,可包括的程序设计元素程序设计元素主要有:主要有:108
70、1.变量变量包括:包括: 字符串变量字符串变量 输入变量:用输入变量:用read从键盘读入其内容从键盘读入其内容 shell过程的位置参数:过程的位置参数:$0,$1,$9 环境变量环境变量(用于获得环境信息用于获得环境信息),包括:,包括:用户用户注册名注册名及及主目录主目录(用户的用户的根目录根目录)名、名、检索存放信件的检索存放信件的文件路径文件路径、检查信件的检查信件的时间间隔时间间隔、.等等等等1092.特殊符号特殊符号 通配符:通配符:、?、?符号列表符号列表、起始符起始符-终止符终止符!. 输入输出重定向符:输入输出重定向符:、 管道:管道: 后台命令后台命令符符:&110 多条
71、命令多条命令执行结果执行结果的逻辑值的逻辑值(可检测可检测)命令命令1&命令命令2命令命令1|命令命令2 成组的执行命令成组的执行命令命令列表命令列表每条命令都在同一每条命令都在同一shell下执行下执行(命令列表命令列表)每条命令都在新的每条命令都在新的shell下执行下执行1113.控制结构控制结构 if 命令表命令表1then命令表命令表2else命令表命令表3 case语句语句while语句语句 until语句语句 for变量变量取值表取值表do命令表命令表done 循环退出或短路:循环退出或短路:break、continue 退出命令程序:退出命令程序:exit1124.算术表达式算
72、术表达式5.函数的定义和执行函数的定义和执行6.特殊命令:特殊命令:trap命令表命令表信号表信号表(016)/*按收到的按收到的信号信号,执行相应的,执行相应的命令命令 waitn/*等待等待进程标识进程标识为为n的的进程进程(执行程序执行程序)终止终止1137.后台命令后台命令(不使用终端不使用终端)的执行方式的执行方式例:例:$ls-luserf1&Unix:52$ccmost1.cf2&Unix:76$vimost2.c114采用了多道程序设计技术后,采用了多道程序设计技术后,我们希望了解:我们希望了解:(1)为了提高效率)为了提高效率在内存的多个程序是在内存的多个程序是如何执行如何执
73、行的的(2)多个程序的并发执行会带来什么)多个程序的并发执行会带来什么问题问题(3)为了避免这类问题)为了避免这类问题对内存并发执行程序应对内存并发执行程序应如何进行管理如何进行管理(4)如何实现对程序的)如何实现对程序的制约制约以及程序间的相互以及程序间的相互合作合作115 计算计算:由:由CPU对一有限的数据集合所施行的对一有限的数据集合所施行的一组一组操作。操作。一、一、程序的顺序执行程序的顺序执行1.什么是程序的顺序执行什么是程序的顺序执行 若一个计算的若干若一个计算的若干操作操作必须按照必须按照严格的先后次序严格的先后次序执行执行则这类计算过程就是程序的则这类计算过程就是程序的顺序执
74、行顺序执行过程过程程序的顺序执行,也称为程序的顺序执行,也称为顺序程序设计顺序程序设计 4.1并发活动并发活动进程的引入进程的引入1162.单道单道系统中一批作业的执行过程系统中一批作业的执行过程 设:每个作业仅运行一个程序设:每个作业仅运行一个程序(一个一个计算计算)每个程序的执行过程均为:每个程序的执行过程均为:首先首先输入程序和数据输入程序和数据然后然后进行计算进行计算最后最后打印计算结果打印计算结果形式化的表示为形式化的表示为: I:输入操作输入操作C:计算操作计算操作P:输出操作输出操作117P2C2 I2P1C1 I1即:严格地说,程序的顺序执行是指:即:严格地说,程序的顺序执行是
75、指:不仅不仅一个计算内的各个操作一个计算内的各个操作是顺序执行的是顺序执行的而且而且多个计算之间的执行多个计算之间的执行也是顺序的也是顺序的不满足上述的任何一条不满足上述的任何一条就就不是不是程序的顺序执行程序的顺序执行(称为称为并发执行并发执行)那么在那么在单道单道环境下,环境下,一批一批作业的作业的所有操作所有操作会会形成一个什么样的形成一个什么样的执行序列执行序列呢?呢?1183.顺序程序的特点顺序程序的特点 (1)顺序性顺序性 处理机的操作,严格按程序所处理机的操作,严格按程序所规定的顺序规定的顺序执执行行(传统的程序传统的程序都具有此特点都具有此特点)(2)封闭性封闭性程序的执行,不
76、受外界因素的影响。程序的执行,不受外界因素的影响。为什么为什么?(3)可再现性可再现性(由封闭性保证由封闭性保证)即:初始条件相同,得到的结果就相同即:初始条件相同,得到的结果就相同(3)也称为也称为与时间无关性与时间无关性即:程序执行的结果即:程序执行的结果只与初始条件有关,而与执行的速度无关只与初始条件有关,而与执行的速度无关(结果唯一结果唯一、可预期的可预期的)119 1.什么是程序的并发执行什么是程序的并发执行 多个程序多个程序(或程序段或程序段),同时在系统中运行,同时在系统中运行若它们执行的若它们执行的起始起始时间时间段有重叠段有重叠的部分的部分(一个的执行尚未结束,另一个的执行已
77、开始一个的执行尚未结束,另一个的执行已开始)则称这几个程序段是并发执行的则称这几个程序段是并发执行的PQR例:三个并发执行的程序段例:三个并发执行的程序段多个程序段的并发执行,应如何来表示呢?多个程序段的并发执行,应如何来表示呢? 二、程序的二、程序的并发执行并发执行120问题:问题:从并发的形式化描述中,能看出程序的执行次序吗?从并发的形式化描述中,能看出程序的执行次序吗? 2.并发执行的表示并发执行的表示 (1)用并发语句表示用并发语句表示 cobeginS1;S2;SncoendS0并发执行的一般性含义:并发执行的一般性含义:指多个程序、或程序段的执行,指多个程序、或程序段的执行,没有任
78、何次序的限制没有任何次序的限制S4S2S1S3(2)用次序图表示用次序图表示探讨的问题:探讨的问题:在一个在一个实际实际的并发环境中,多个程序段的并发执行的并发环境中,多个程序段的并发执行是否完全没有是否完全没有次序的限制次序的限制?会不会带来会不会带来意外的问题呢?意外的问题呢? 121思考:思考:它们的并发执行,会得到什么样的它们的并发执行,会得到什么样的结果结果呢?呢?打印出的打印出的n值?值? n的终值?的终值? 四、四、与时间有关与时间有关的错误的错误例:两个程序共享一个初值为例:两个程序共享一个初值为0的公共变量的公共变量n程序程序A执行时:完成执行时:完成n加加1的操作的操作程序
79、程序B执行时:先打印执行时:先打印n的值,再将的值,再将n置为置为0与时间有关的错误与时间有关的错误是指:是指:多个程序并发执行时,可能会有多个不同的结果。多个程序并发执行时,可能会有多个不同的结果。除一个结果正确外,其余的都除一个结果正确外,其余的都认为认为是错误的。是错误的。称其为与时间有关的错误。称其为与时间有关的错误。122程序程序A的的n:=n+1,与,与程序程序B的的两语句两语句之间的执行次序:之间的执行次序: 之前之前 10 之后之后 01 中间中间 00 打印的结果打印的结果:n的终值的终值:程序程序An:=n+1程序程序Bprint(n)n:=0将上述错误称为与时间有关的错误
80、。将上述错误称为与时间有关的错误。什么问题?什么问题?123 (1)失去程序的失去程序的封闭性封闭性和可和可再现性再现性如果程序如果程序A的执行,可以的执行,可以改变程序改变程序B的环境的环境(即程序即程序B失去了封闭性失去了封闭性)五、并发程序的特点五、并发程序的特点思考:思考:如果程序如果程序B本身是封闭的呢本身是封闭的呢?则:程序则:程序B的运行的运行结果结果就与二个程序之间,执行的就与二个程序之间,执行的相对速度相对速度有关有关(即即失去了可再现性失去了可再现性)124编译编译1C编译程序编译程序编译编译2.编译编译n(2)程序与计算程序与计算不再一一对应不再一一对应 一个程序可以对应
81、多个计算。如:一个程序可以对应多个计算。如:(3)程序的并发执行也存在着相互制约程序的并发执行也存在着相互制约 直接的直接的相互制约:相互制约:由程序的逻辑决定由程序的逻辑决定 间接的间接的相互制约:相互制约:由共享资源而引起由共享资源而引起归纳:归纳:产生了新的问题产生了新的问题,有待解决,有待解决 125六、并发程序执行中应解决的问题六、并发程序执行中应解决的问题(1)由于失去了可再现性,而带来由于失去了可再现性,而带来与时间有关的错误与时间有关的错误(与与占有占有CPU的的次序次序有关有关)(2)由于程序与计算不再一一对应由于程序与计算不再一一对应资源分配给谁资源分配给谁?因此,操作系统
82、必须解决:因此,操作系统必须解决:(1)如何描述每个程序,在内存的如何描述每个程序,在内存的执行过程执行过程?(何时占有何时占有CPU、何时没有,怎么表示、何时没有,怎么表示)(2)资源分配的对象资源分配的对象是什么?是什么?已获得的资源记录在何处?已获得的资源记录在何处?4.2进程的概念进程的概念一一.进程定义进程定义 程序并发执行时,占有程序并发执行时,占有CPU的活动规律为:的活动规律为: 执行执行 暂停暂停 执行执行 因此必须用一个因此必须用一个数据结构数据结构,描述描述程序程序执行时的执行时的 活动规律活动规律、以及对、以及对资源的使用情况资源的使用情况 将其将其描述的对象称为:描述
83、的对象称为:Processing1.什么是什么是Processing(进程进程)所谓进程,就是一个所谓进程,就是一个程序程序在给定活动空间和在给定活动空间和初始环境下,在一个处理机上初始环境下,在一个处理机上的执行过程的执行过程127 (1)运行状态运行状态(running) 该进程已获得运行所必需的一切资源该进程已获得运行所必需的一切资源它的程序它的程序正在处理机上执行正在处理机上执行二二.进程的状态、及状态变迁进程的状态、及状态变迁 1.进程的基本状态进程的基本状态 思考:思考:没有运行的进程没有运行的进程根据其根据其原因原因,能否再作进一步的区分呢,能否再作进一步的区分呢?128(3)等
84、待状态等待状态(wait)进程正进程正等待等待着某一着某一事件的发生事件的发生即使将即使将CPU的控制权给它,也的控制权给它,也无法执行无法执行问题:问题:各种状态是如何进行转换的呢?各种状态是如何进行转换的呢?(2)就绪状态就绪状态(ready)进程已获得除进程已获得除CPU之外,运行所必需的一切资之外,运行所必需的一切资源源一旦得到一旦得到CPU的控制权的控制权,立即可以执行,立即可以执行129 2.进程状态的变迁进程状态的变迁 进程的状态,是随着进程自身的推进和外界进程的状态,是随着进程自身的推进和外界条件的变化,而发生变化的。条件的变化,而发生变化的。 运运行行 等等待待 就就绪绪服务
85、请求服务请求/等待一个等待一个事件的发生事件的发生服务完成服务完成/事件已发生事件已发生进程调度进程调度时间片到时间片到130三三.进程的描述进程的描述 多个进程并发执行时,就产生了多个进程并发执行时,就产生了动态的特征动态的特征由于进程对资源的不断占有和释放由于进程对资源的不断占有和释放从而造成了一个不断从而造成了一个不断变化的外部环境变化的外部环境而且,进程间还存在而且,进程间还存在相互制约相互制约因此对因此对每个进程每个进程,必须至少用一个数据结构,必须至少用一个数据结构对其运行的过程进行描述对其运行的过程进行描述 1311.进程控制块进程控制块描述一个进程的数据结构,称为描述一个进程的
86、数据结构,称为进程控制块进程控制块(ProcessControlBlockPCB),它描述了进程:,它描述了进程:当前所处的当前所处的状态状态对对资源的使用情况资源的使用情况以及以及与其他进程的关系与其他进程的关系用途:用途:操作系统是通过操作系统是通过PCB而而感知感知到进程的存在到进程的存在并对进程进行并对进程进行控制控制1323.PCB的主要内容的主要内容 进程标识符进程标识符进程当前状态进程当前状态当前队列指针当前队列指针总链队列指针总链队列指针程序开始地址程序开始地址进程优先级进程优先级CPU现场保护区现场保护区通信信息通信信息家族联系家族联系占有资源清单占有资源清单(1)进程标识符
87、:进程标识符:进程符号名、或内部进程符号名、或内部id号号(2)进程当前状态:进程当前状态:本进程目前处于何种状态本进程目前处于何种状态(运行、就绪、等待运行、就绪、等待)(3)当前队列指针当前队列指针next:同一状态的同一状态的下一个进程的下一个进程的PCB地址地址 133(4)总链队列指针总链队列指针all_q_next:用于将系统中,所有的进程的连为一个整体用于将系统中,所有的进程的连为一个整体(5)程序开始地址:程序开始地址:该进程的程序将从此地址开始执行。该进程的程序将从此地址开始执行。(6)进程优先级:进程优先级:反映了进程要求反映了进程要求CPU的紧迫程度的紧迫程度(7)CPU
88、现场保护区现场保护区:当进程由于某种原因释放处理机时,当进程由于某种原因释放处理机时,CPU现场现场信息被保存在信息被保存在pcb的该区域中的该区域中134(8)通信信息:通信信息:进程间进行通信时,所记录的有关信息。进程间进行通信时,所记录的有关信息。(9)家族联系:家族联系:进程与家族的联系,通常为进程与家族的联系,通常为指向父进程的指针指向父进程的指针(10)占有资源清单占有资源清单为了对系统中的为了对系统中的所有的进程所有的进程进行管理进行管理系统中还需要哪些系统中还需要哪些其他的数据结构呢?其他的数据结构呢? 135ready_start pcb1pcb2pcb9就绪队列就绪队列ne
89、xtwait_startpcb3pcb7 next打印机等待队列打印机等待队列其他的就绪队列其他的就绪队列其他的等待队列其他的等待队列136 all_start pcb1pcb2pcbn总链队列总链队列 nextrunningpcb4 next运行指针运行指针 Unix系统中的进程系统中的进程(映像映像)137一一.进程控制的概念进程控制的概念1.什么是进程控制什么是进程控制 指由指由一组系统功能调用子例程一组系统功能调用子例程,对系统中的,对系统中的全部进程实施有效管理,并负责其状态的改变全部进程实施有效管理,并负责其状态的改变完成的功能包括进程的:完成的功能包括进程的:无无有有消亡消亡 U
90、nix中的进程树中的进程树4.3进程控制进程控制创建创建撤消撤消就绪运行就绪运行运行等待运行等待等待就绪等待就绪调度调度唤醒唤醒等待等待由于这些由于这些子例程子例程在执行时不能被中断在执行时不能被中断(至少在逻辑上至少在逻辑上),因此被称之为,因此被称之为原语原语139二二.进程创建进程创建1.进程创建原语的进程创建原语的一般形式一般形式create(name,priority,start_addr)进程的创建,通常会涉及到进程的创建,通常会涉及到3个主要的参数个主要的参数 name:新进程的符号名:新进程的符号名(或或进程标识符进程标识符) priority:进程的优先级:进程的优先级 st
91、art_addr:程序的开始地址:程序的开始地址 2.常用的进程控制原语常用的进程控制原语 创建原语、撤消原语、阻塞原语、唤醒原语等创建原语、撤消原语、阻塞原语、唤醒原语等1402.进程创建原语的进程创建原语的一般一般功能功能建立新进程的建立新进程的PCB结构结构创建一个具有指定标识符的进程:创建一个具有指定标识符的进程:(1)从从PCB池分配一个空池分配一个空PCB结构结构ab-1PCB池池(2)填写填写PCB的内容的内容(如:状态为如:状态为就绪就绪、.)(3)将将PCB插入就绪队列插入就绪队列调用者:调用者:作业调度程序作业调度程序、终端进程终端进程、执行程序执行程序(父进程父进程)Un
92、ix的进程创建的进程创建141三三.进程撤消进程撤消 当进程完成任务后,可使用进程撤消原语来当进程完成任务后,可使用进程撤消原语来自己终止自己自己终止自己1.进程撤消原语的形式进程撤消原语的形式 exit()或或kill()()2.进程撤消原语的功能进程撤消原语的功能 撤消当前运行的进程。撤消当前运行的进程。具体为:具体为:释放该进程所占用的所有资源释放该进程所占用的所有资源从总链队列中摘除从总链队列中摘除pcb结构,归还到结构,归还到pcb池池转转进程调度程序进程调度程序1423.进程撤消原语的算法描述进程撤消原语的算法描述算法算法kill输入:无输入:无输出:无输出:无由由运行指针运行指针
93、得当前进程的得当前进程的pcb释放该进程所占用的所有资源释放该进程所占用的所有资源该进程从总链队列中摘除该进程从总链队列中摘除释放此释放此pcb结构结构转进程调度程序转进程调度程序 Unix的进程撤销的进程撤销143调用者:调用者:大多为大多为系统调用子例程系统调用子例程。即:。即:用户进程用户进程系统调用子例程系统调用子例程等待原语等待原语四四.进程等待进程等待当进程需要等待某一事件的完成时:当进程需要等待某一事件的完成时:它可以调用等待原语,把自己挂起它可以调用等待原语,把自己挂起1.进程等待原语的形式进程等待原语的形式susp(chan)chan:进程等待的原因:进程等待的原因(用来指明
94、等待队列用来指明等待队列)2.进程等待原语的功能进程等待原语的功能中止调用进程的执行中止调用进程的执行将其插入到等待将其插入到等待chan的等待队列中;最后的等待队列中;最后转进程调度转进程调度1443.进程等待原语的算法描述进程等待原语的算法描述算法算法susp输入:输入:chan等待的事件等待的事件(阻塞原因阻塞原因)输出:无输出:无保护现行进程的保护现行进程的CPU现场到现场到PCB结构中;结构中;置该进程为置该进程为“等待等待”态;态;将该进程将该进程pcb插入到相应插入到相应chan的等待队列;的等待队列;转进程调度转进程调度 145五五.进程唤醒进程唤醒 当等待进程所等待的当等待进
95、程所等待的事件已发生事件已发生时时由由发现者发现者进程,调用唤醒原语来唤醒它。进程,调用唤醒原语来唤醒它。1.进程唤醒原语的形式进程唤醒原语的形式wakeup(chan)chan:进程等待的原因:进程等待的原因(对应一个等待队列对应一个等待队列)2.进程唤醒原语的功能进程唤醒原语的功能唤醒等待该事件的唤醒等待该事件的所有进程所有进程但但有的系统有的系统(或对某些或对某些特定的资源特定的资源)仅唤醒等待该事件的仅唤醒等待该事件的首进程首进程(以后详细讨论以后详细讨论)1463.进程唤醒原语的算法描述进程唤醒原语的算法描述保护运行进程的保护运行进程的CPU现场现场置运行进程为置运行进程为“就绪就绪
96、”态;插入就绪队列态;插入就绪队列找到该阻塞原因的等待队列找到该阻塞原因的等待队列对等待队列中的所有对等待队列中的所有(或第一个或第一个)进程进程将进程移出此等待队列将进程移出此等待队列置进程状态为置进程状态为“就绪就绪”将进程入就绪队列将进程入就绪队列 转进程调度转进程调度(看起来不合理,看起来不合理,原因?原因?) 147(1)调用者为调用者为系统进程系统进程(2) 增加调度的机会增加调度的机会(如在如在Unix中中)使使优先级最高优先级最高的进程能马上得到的进程能马上得到CPU在有些系统中:在有些系统中:调用者:调用者:通常为该事件的通常为该事件的中断处理程序中断处理程序返返回:回:被中
97、断的进程被中断的进程(因此,也不用再保护运行进程的现场)(因此,也不用再保护运行进程的现场)说明:说明:若没有等待的进程若没有等待的进程唤醒原语什么也不做,直接返回唤醒原语什么也不做,直接返回 六六.进程的延迟进程的延迟(睡眠睡眠)和唤醒和唤醒1.进程的延迟进程的延迟指进程等待一段时间后,由指进程等待一段时间后,由时钟中断时钟中断唤醒唤醒 延迟延迟时间通常用时间通常用相对的相对的延迟延迟时间时间来表示来表示有什么好处?有什么好处? 3 0 2例:某时刻系统中有三个例:某时刻系统中有三个睡眠进程睡眠进程 其其当前的当前的延迟时钟延迟时钟间间隔隔分别为分别为3、3、5 则延迟队列则延迟队列的形式为
98、:的形式为:1492. 2. 延迟进程的延迟进程的唤醒唤醒由时钟中断处理程序完成:由时钟中断处理程序完成:(1) (1) 将首元素的等待时间减将首元素的等待时间减1;1;(2) (2) 若首元素的等待时间为若首元素的等待时间为0 0,则:,则:从首节点开始从首节点开始 将等待时间将等待时间为为0 0的所有节点的所有节点唤醒;唤醒;另外:另外:有的系统还允许有的系统还允许在唤醒时执行一个函数在唤醒时执行一个函数LinuxLinux中:中: 延迟延迟时间用真实时间时间用真实时间( (绝对绝对时钟间隔时钟间隔) )表示表示 1504.5进程互斥进程互斥由于共享资源,多个进程之间的由于共享资源,多个进
99、程之间的间接制约间接制约还还有什么其他有什么其他更一般的更一般的表现形式呢?表现形式呢?结果有可能会交织在一起,很难区分结果有可能会交织在一起,很难区分一、一、进程互斥的概念进程互斥的概念1、临界资源、临界资源例例1:设两个进程:设两个进程A、B共享一台打印机。共享一台打印机。若不加以控制,最终会打印出什么结果?若不加以控制,最终会打印出什么结果?151 例例2:设服务器上有一个变量:设服务器上有一个变量X,初值为,初值为0代表某航班已卖出的机票数代表某航班已卖出的机票数P1和和P2为二个客户机上的售票进程为二个客户机上的售票进程每卖出一张票,对服务器上的变量每卖出一张票,对服务器上的变量X加
100、加1思考:思考:若二个售票进程各卖出了一张票若二个售票进程各卖出了一张票可能会出现什么结果呢?可能会出现什么结果呢?假定:假定:二个进程并发执行,并分别二个进程并发执行,并分别先先在自己的在自己的内部寄存器内部寄存器r1、r2中,对中,对变量变量的值进行处理的值进行处理152p2:r2:=x0r2:=r2+1;x:=r2;1p1:r1:=r1+1x:=r1;1执行结果:执行结果:x=1序列序列A(顺序顺序)x值值P1:r1:=x;0r1:=r1+1;x:=r1;1p2:r2:=x;1r2:=r2+1;x:=r2; 2 执行结果:执行结果: x=2二进程二进程并发执行并发执行时的两种可能次序时的
101、两种可能次序: 序列序列B(交错交错) x值值p1:r1:=x;0153当多个进程共享这类资源时:当多个进程共享这类资源时:它们必须它们必须顺序地使用顺序地使用即:只有一个进程用完后,其他进程才能使用即:只有一个进程用完后,其他进程才能使用 这一类问题应如何解决呢?这一类问题应如何解决呢?()临界资源临界资源将一次将一次(一段时间内一段时间内)仅允许仅允许一个进程使用的资源,称为一个进程使用的资源,称为临界资源临界资源具有这种性质的资源有:具有这种性质的资源有:硬件资源硬件资源:输入机、扫描仪、打印机、绘图仪:输入机、扫描仪、打印机、绘图仪软件资源软件资源:会修改会修改的变量、表格、队列等的变
102、量、表格、队列等154问题:问题:为了尽可能地实现多进程的并发运行为了尽可能地实现多进程的并发运行以提高资源的利用率,以提高资源的利用率,这段时间如何确定?这段时间如何确定?最好是与该资源有关的最好是与该资源有关的部分程序段部分程序段顺序地执行顺序地执行是多个是多个进程进程顺序地执行顺序地执行(依次创建进程依次创建进程)?还是多个进程的还是多个进程的程序程序顺序地执行?顺序地执行?或多个进程的部分或多个进程的部分程序段程序段顺序地执行呢?顺序地执行呢?通常将其称为封锁的通常将其称为封锁的“粒度粒度”155 (2)临界区临界区 在每个进程中在每个进程中访问临界资源的访问临界资源的那段程序那段程序
103、能够从逻辑上分离出来能够从逻辑上分离出来称其为称其为临界区临界区、或、或临界段临界段156注意:注意:(a)访问同一临界资源的多个进程访问同一临界资源的多个进程每个进程每个进程都有都有自己的自己的临界段临界段而且其代码通常不相同而且其代码通常不相同(b)同一进程中,可能有同一进程中,可能有访问多个访问多个不同临界资源不同临界资源的的多个临界段多个临界段(c)只有访问只有访问同一临界资源的同一临界资源的临界段临界段才需要才需要相互制约相互制约157csA进程进程A进程进程C CScyY=0CScxX=X+10进程进程BYYcsB例:例:158 (3)互斥互斥 当某一进程正在访问某一临界资源时:当
104、某一进程正在访问某一临界资源时:就不允许其他进程访问该资源就不允许其他进程访问该资源(否则,可能会发生后果否则,可能会发生后果无法估计的错误无法估计的错误)将进程间的这种相互制约关系,称为将进程间的这种相互制约关系,称为互斥互斥csA进程进程A进程进程CCScyY=0CScxX=X+10例:进程例:进程A、进程、进程C并发执行并发执行159操作系统是如何保证操作系统是如何保证临界段的互斥执行呢?临界段的互斥执行呢?对互斥处理的三原则:对互斥处理的三原则:(1)可进入性可进入性(2)排它性排它性(3)有限性有限性进程之间是相互独立、并且互不可知的。进程之间是相互独立、并且互不可知的。那么,那么,
105、当前执行进程当前执行进程又是如何实现这些原则的呢?又是如何实现这些原则的呢?为此引入了锁的概念为此引入了锁的概念二、锁、上锁及开锁操作二、锁、上锁及开锁操作1.什么是锁什么是锁 用一个变量用一个变量w(或二进制位或二进制位)代表某种资源的代表某种资源的状态状态(空闲空闲、或、或被占用被占用),称其为,称其为锁锁2.进程使用临界资源的步骤进程使用临界资源的步骤(1)上锁操作上锁操作 检测检测w的值的值 如果如果w的值为的值为1(表示已表示已上锁上锁,资源资源被占用被占用):则继续检测,直到则继续检测,直到锁打开锁打开161 如果如果w的值为的值为0(表示表示未上锁未上锁,资源资源空闲空闲):将锁
106、将锁w置为置为1(上锁上锁防别人防别人)(2)进入临界区执行进入临界区执行(3)开锁操作开锁操作 临界资源使用完毕后,将锁置临界资源使用完毕后,将锁置0(开锁开锁)最最好好由系统完成由系统完成 问题:问题:由谁来完成由谁来完成上锁、开锁上锁、开锁的的具体操作具体操作呢?呢?1623.上锁原语和开锁原语上锁原语和开锁原语(1)简单的算法简单的算法(a) 上锁原语上锁原语 lock(w)test:if(w=1)gototest*重复测试锁重复测试锁elsew=1*上锁上锁163(b)开锁原语开锁原语 unlock(w)w=0*开锁开锁分析:分析:164上锁原语:上锁原语:test:if(w=1)g
107、ototestelsew=1开锁原语:开锁原语:w=0思考:思考:有没有什么问题呢?有没有什么问题呢?效率低:效率低:当锁已上时,当前执行上锁的进程当锁已上时,当前执行上锁的进程忙等忙等无法实现:无法实现:由于执行的是原语由于执行的是原语当已当已上锁上锁时,占着时,占着CPU的进程不断地测试锁的进程不断地测试锁谁来开锁呢?谁来开锁呢?死锁!死锁!如果不是原语呢?如果不是原语呢?如何改进呢?如何改进呢?165(2)改进算法的思想改进算法的思想采用采用上锁等待上锁等待和和开锁唤醒开锁唤醒。(b)开锁原语开锁原语if(有进程等待有进程等待)唤醒等待的进程唤醒等待的进程w=0*开锁开锁 基本的描述是:
108、基本的描述是:(a) 上锁原语上锁原语 if(w=1) 调用进程等待调用进程等待 elsew=1 *上锁上锁思考:思考:假定有多个进程在等待,资源释放后:假定有多个进程在等待,资源释放后:根据唤醒算法,资源可能会根据唤醒算法,资源可能会先分给谁?先分给谁?被唤醒进程使用资源前,还要不要被唤醒进程使用资源前,还要不要测试锁?测试锁?该算法有没有该算法有没有可完善可完善的地方?的地方? 对改进算法的深入分析对改进算法的深入分析4.用上锁原语和开锁原语实现进程互斥用上锁原语和开锁原语实现进程互斥 上锁上锁 临界区临界区csb开锁开锁进程进程B上锁上锁 临界区临界区csa开锁开锁进程进程A问题:问题:
109、(1)若有多个若有多个不同的不同的临界资源怎么办?临界资源怎么办?(2)若有若有同一类型的同一类型的多个临界资源又怎么办?多个临界资源又怎么办?1684.6信号灯和信号灯和p、v操作操作1.什么是信号灯什么是信号灯信号灯可看作是一种广义的锁,它的结构是信号灯可看作是一种广义的锁,它的结构是一个二元组一个二元组(S,q)。其中:。其中:S是一个是一个初值初值00的整型变量的整型变量表示表示同一类同一类资源资源中,中,可用的可用的资源数资源数q表示该资源的等待队列,表示该资源的等待队列,初始状态为空初始状态为空由于每个由于每个S都对应于一个都对应于一个q,因此在实用中,因此在实用中通常将通常将q省
110、略,直接将省略,直接将S称为称为信号灯信号灯169信号灯的用途:信号灯的用途:S0 0:表示表示有有S个个资源资源 请求资源的进程可继续执行请求资源的进程可继续执行S0 0:表示无资源,请求进程必须表示无资源,请求进程必须等待等待注意:注意:创建信号灯时创建信号灯时应说明信号灯应说明信号灯S的的用途用途定义信号灯定义信号灯S初值初值(不能为不能为负值负值。为什么?为什么?)操作系统通过操作系统通过判别判别、改变改变信号灯的值,对多个信号灯的值,对多个并发进程共享并发进程共享同一类的资源同一类的资源进行控制和管理进行控制和管理1702.P、V操作的原语操作的原语 信号灯信号灯S是受保护的是受保护
111、的特权特权变量变量(内核模式内核模式访问访问)只能由系统的只能由系统的P、V操作原语来操作原语来读读、写写(1)P操作操作(可看作一种可看作一种广义的上锁广义的上锁)对信号灯对信号灯S的的P操作记为操作记为P(S),定义为:,定义为:(a)s=s1(b)若若s0:调用:调用P(S)的进程被阻塞的进程被阻塞(c)否则:返回调用的进程否则:返回调用的进程继续执行继续执行?171 P操作原语的算法描述操作原语的算法描述S=S1;if(S 0)保留调用进程保留调用进程CPU现场现场将该进程入将该进程入S的等待队列的等待队列置为置为等待等待状态状态转进程调度转进程调度唤醒后的执行点唤醒后的执行点(以后不
112、用以后不用再测试再测试信号灯信号灯)172(2)V操作操作(可看作一种可看作一种广义的开锁广义的开锁)对信号灯对信号灯S的的V操作记为操作记为V(S)定义为:定义为:(a)S=S+1(b)若若s0(有进程在等待有进程在等待):唤醒信号灯等待队列的唤醒信号灯等待队列的首进程首进程(c)返回调用返回调用V(S)的进程的进程继续执行继续执行173 V操作原语的算法描述操作原语的算法描述输入:变量输入:变量S输出:无输出:无SS1;if(S =0)移出移出S等待队列的等待队列的首进程首进程/*简单的简单的FIFO将该进程插入就绪队列将该进程插入就绪队列将该进程置为将该进程置为就绪就绪状态状态174程序
113、描述程序描述 main()mutex=1*互斥信号灯互斥信号灯*cobeginpa()pb()coend3.用信号灯实现进程互斥用信号灯实现进程互斥例:二个进程例:二个进程Pa、Pb共享一个临界资源共享一个临界资源175 pa() p(mutex)csa:使用资源使用资源v(mutex)阻塞阻塞pb() p(mutex)csb:使用资源使用资源V(mutex) mutex=1 0 -1176(3)互斥信号灯互斥信号灯的取值及含义的取值及含义 设设N个并发进程互斥,信号灯个并发进程互斥,信号灯mutex的初值为的初值为1mutex的取值范围为:的取值范围为:1(N1)。含义为。含义为:1:无进程
114、进入临界区无进程进入临界区有有1个资源,无进程等待个资源,无进程等待0:一个进程一个进程正在访问临界资源正在访问临界资源无资源无资源,无进程等待无进程等待i:一个进程一个进程正在访问临界资源正在访问临界资源无资源无资源,而且有,而且有i个个进程等待进程等待1774.7进程的同步进程的同步 多个并发进程多个并发进程合作合作,为了避免与时间有关的,为了避免与时间有关的错误,是否也存在着其他的错误,是否也存在着其他的直接制约直接制约呢?呢?若有,它们又有哪些表现形式呢?若有,它们又有哪些表现形式呢?一一.进程同步的概念进程同步的概念1.什么是进程的同步什么是进程的同步 所谓同步,就是多个并发进程,在
115、一些关键所谓同步,就是多个并发进程,在一些关键点上需要点上需要互相等待互相等待(有次序限制有次序限制)、互通消息。互通消息。2.进程同步的例子进程同步的例子178例:二个合作进程,循环共享一例:二个合作进程,循环共享一单位单位缓冲区缓冲区buf完成数据的处理。其中:完成数据的处理。其中:计算进程计算进程cp:对数据进行计算后,结果送入对数据进行计算后,结果送入buf打印进程打印进程iop:从从buf中取出结果后,再打印中取出结果后,再打印正确性要求:正确性要求:对一组结果数据,从对一组结果数据,从buf中中取出取出打印的次序,打印的次序,应与应与送入送入buf的次序相一致的次序相一致 缓冲区缓
116、冲区iopcp为了打印结果的正确,为了打印结果的正确,二个进程的执行,二个进程的执行,有没有次序的限制有没有次序的限制?180二、二、执行次序执行次序确定确定(唯一唯一)的进程的同步的进程的同步图中用图中用连接点连接点表示:表示:对进程对进程开始开始和和结束结束的约束的约束如:如:1.执行次序执行次序已知已知的多个进程同步的多个进程同步若一组进程的执行次序是已知的若一组进程的执行次序是已知的则可用则可用进程流图进程流图来描述它们的执行时间轨迹来描述它们的执行时间轨迹s fP5P6P7P3 sfP4P1P2p5s fP9P10P8182 例例1:设:设P1、P2、P3、P、P为一组合作进程为一组
117、合作进程用信号灯的用信号灯的P、V操作实现这五个进程的同步操作实现这五个进程的同步 sfp2p1p3p4p5问题:问题:用什么来表示资源呢用什么来表示资源呢?183sp1p3p4fp2p5p5:等等p1完成完成资源,不释放资源资源,不释放资源p4:等等P2、p3资源,不释放资源资源,不释放资源p3:等等p1资源资源,释放一个资源释放一个资源P2:不等资源,不等资源,释放一个资源释放一个资源p1:不等资源,不等资源,释放二个资源释放二个资源观察:观察:有有几类几类抽象的资源?抽象的资源?分析:分析:若一进程必须等待进程若一进程必须等待进程A完成后才能执行完成后才能执行则可将进程则可将进程A的完成
118、的完成视为一类抽象视为一类抽象资源资源S1S3S2因此,设因此,设3个同步信号灯:个同步信号灯:s1、s2、s3分别表示分别表示进程进程p1、p、p是否是否完成完成再观察:再观察:信号灯的设置,信号灯的设置,有无规律?有无规律?184sp1p3p4fp2p5S1S2S3程序描述程序描述 main()s1=s2=s3=0*分别表示分别表示*进程进程p1、p2、p是否完成是否完成cobeginp()p()p()p()p()coend问题:问题:怎么对进程进行描述呢?怎么对进程进行描述呢?185sp1p3p4fp2p5S1S2S3P2()v(s2) p()v(s)v(s)p3()p(s)v(s3)
119、p4()p(s2)p(s3) P5()p(s1) 再观察:再观察:进程的描述,进程的描述,有无规律?有无规律?思考:思考:为实现控制,为实现控制,至少要几个信号灯?至少要几个信号灯? 最少信号灯最少信号灯186问题:问题:若没有若没有明显的次序明显的次序,或,或难于画出次序难于画出次序如何解决?如何解决?设计进程:设计进程:P1:x1=a+bP2:x2=c+dP3:x3=x1*x2先画出进程流图,再实现同步先画出进程流图,再实现同步例例2:在下列表达式中,:在下列表达式中,每一步计算每一步计算由一个进程完成。画出进程流图,由一个进程完成。画出进程流图,并用并用p、v操作实现各计算进程的同步操作
120、实现各计算进程的同步(a+b)*(c+d)s fP1P2P3 程序描述:程序描述: 画进程流图:画进程流图:187 2.共享共享一个缓冲区一个缓冲区的合作进程同步的合作进程同步例:设一个计算进程例:设一个计算进程cp、和一个打印进程、和一个打印进程iop共享共享一个单位一个单位缓冲区,完成计算与打印。缓冲区,完成计算与打印。用信号灯的用信号灯的p、v操作实现两个进程的同步操作实现两个进程的同步 iopcp二进程的二进程的执行规律:执行规律:交错执行交错执行(而且而且cp先执行先执行)559876566778899执行次序:执行次序:可用次序图表示,但图、程序的描述都较繁琐可用次序图表示,但图、
121、程序的描述都较繁琐 188 (1)用用缓冲区的状态缓冲区的状态为资源,进程的同步限制为为资源,进程的同步限制为 对对cp进程进程只有当只有当buf为空为空时,才能将结果送入时,才能将结果送入buf(即:开始、或即:开始、或iop进程已将数据取走进程已将数据取走)否则,必须等待否则,必须等待 对对iop进程进程只有只有buf内内有数据有数据时,才能从时,才能从buf中取出数据中取出数据(即:即:cp进程把一个新的结果送入进程把一个新的结果送入buf后后)否则,必须等待否则,必须等待 对对buf的操作要的操作要互斥互斥(缓冲区作为一个单位缓冲区作为一个单位)189 (2)算法描述算法描述将同步的限
122、制看作资源,可设置信号灯:将同步的限制看作资源,可设置信号灯:sa:表示缓冲区中:表示缓冲区中是否有新数据是否有新数据,初值为,初值为0;sb:表示缓冲区:表示缓冲区有无空位置有无空位置,初值为,初值为1;先暂时不设置互斥信号灯,算法描述为:先暂时不设置互斥信号灯,算法描述为:cp:产生一个结果数据;产生一个结果数据;p(sb);将数据放入将数据放入bufv(sa);iop:p(sa);从从buf中取数据;中取数据;v(sb);打印;打印;190(3)程序描述程序描述 main() intsa=0; *表示表示buf中有无中有无数据数据intsb=1;*表示表示buf中有无中有无空位置空位置c
123、obegincp();iop();coend191cp()while(计算未完成计算未完成)产生一个结果数据产生一个结果数据;p(sb);将数送到缓冲区中;将数送到缓冲区中;v(sa);考虑:考虑:是否实现了对缓冲区的是否实现了对缓冲区的互斥互斥操作?操作? 是否实现了二个进程的是否实现了二个进程的同步同步?iop()while(打印未完成打印未完成)p(sa);从缓冲区中取数从缓冲区中取数据据;v(sb);在在打印机上输出;打印机上输出;观察:观察:信号灯的操作有什么规律?信号灯的操作有什么规律?192初始初始Sa=0Sb=1iop()cp()CPCP执行执行V(sa)操作后操作后Sa=1S
124、b=0iop()cp()IOPCP执行执行p(sb)操作后操作后Sa=0Sb=0iop()cp()iOP执行执行p(sa)操作后操作后Sa=0Sb=0iop()cp()思考:思考:若有多个若有多个CP和和iOP进程,该模型是否适用?进程,该模型是否适用? 此时,此时,iop能对缓冲区进行操作吗?能对缓冲区进行操作吗?不能,实现不能,实现互斥互斥的原因的原因?同样互斥同样互斥193三、生产者三、生产者消费者问题消费者问题问题的提出:问题的提出:多个并发进程的同步,更一般的情况是:多个并发进程的同步,更一般的情况是:存在某种存在某种次序限制次序限制,但这种次序又,但这种次序又不唯一不唯一若将这种限
125、制理解为一种抽象的资源,则:若将这种限制理解为一种抽象的资源,则:释放释放资源的进程可看作是一个资源的进程可看作是一个生产者生产者占用占用资源的进程可看作是一个资源的进程可看作是一个消费者消费者因此,可将多进程间因此,可将多进程间同步的一般问题同步的一般问题抽象为资源抽象为资源(或产品或产品)的的生产和消费生产和消费1941、生产者生产者消费者问题的消费者问题的一般模型一般模型 (1) 有一个有界的有一个有界的多缓冲区多缓冲区(资源、限制资源、限制) (2) 多个多个生产者生产者,生产产品后,生产产品后,放入缓冲区放入缓冲区 (3) 多个多个消费者消费者,从缓冲区中,从缓冲区中取出产品取出产品
126、后,进行消费后,进行消费说明:说明:共享一个缓冲区,可看作它的一个特例共享一个缓冲区,可看作它的一个特例c1p1 c2c3ckp2p3pm1952、生产者生产者消费者的消费者的实例实例(1)多进程之间的通信问题多进程之间的通信问题生产者生产者(即即发送消息发送消息进程进程send):不断地产生消息不断地产生消息然后将消息送到消息缓冲区中然后将消息送到消息缓冲区中消费者消费者(即即接收消息接收消息进程进程receive):不断地从消息缓冲区中取消息不断地从消息缓冲区中取消息然后对消息进行处理然后对消息进行处理196(2)通过通过缓冲区缓冲区进行外部设备的进行外部设备的输出输出(或输入或输入)生产
127、者生产者(数据处理进程数据处理进程cp),重复完成:,重复完成:每次将一个缓冲区写满后每次将一个缓冲区写满后将缓冲区插入到将缓冲区插入到输出队列输出队列中中消费者消费者(输出进程输出进程iop),重复完成:,重复完成: 每每次从次从输出队列输出队列中取出一个缓冲区中取出一个缓冲区将其内容输出到外部设备将其内容输出到外部设备 1973、同步限制、同步限制(不是考虑次序,而是考虑不是考虑次序,而是考虑规律规律) 对生产者的限制对生产者的限制当缓冲区中有空位置时:当缓冲区中有空位置时:可将产品送入缓冲区中可将产品送入缓冲区中(不限定产品位置的次序不限定产品位置的次序,因为是,因为是抽象的模型抽象的模
128、型) 对消费者的限制对消费者的限制当缓冲区中有产品时:当缓冲区中有产品时:可从缓冲区取出产品可从缓冲区取出产品(也不限定位置的次序也不限定位置的次序) 对对buf的操作要互斥的操作要互斥1985、程序描述、程序描述 main()intfull=0*满缓冲区信号灯满缓冲区信号灯intempty=n*空缓冲区信号灯空缓冲区信号灯intmutex=1*缓冲区互斥信号灯缓冲区互斥信号灯cobeginP(i)i=1,2m/*也可分别也可分别C(j)j=1,2k/*列出各个进程列出各个进程coend199 P(i)i=1,2mwhile(还要生产还要生产) 生产一个产品生产一个产品C(j)j=1,2kwh
129、ile(还要消费还要消费)p(full);p(mutex)从缓冲区中取一个产品从缓冲区中取一个产品v(mutex)v(empty)p(empty)p(mutex)送一个产品到缓冲区送一个产品到缓冲区v(mutex)v(full)消费一个产品消费一个产品为什么要互斥为什么要互斥:可能有多个进程都有操作的权利可能有多个进程都有操作的权利应防止应防止多个进程操作多个进程操作,造成的,造成的与时间有关错误与时间有关错误200思考思考:(1)若只有一个生产者和消费者)若只有一个生产者和消费者该模型是否适用?该模型是否适用?(2)现实中,若要求送入)现实中,若要求送入数据的次序数据的次序与取出数据的次序相
130、一致,应如何解决?与取出数据的次序相一致,应如何解决?(3)两个)两个P操作的次序操作的次序是否不重要?是否不重要?交换次序交换次序后可能会出现什么问题?后可能会出现什么问题? Pi()Cj()while(还要生产还要生产)while(还要消费还要消费)p(mutex)生产一个产品;生产一个产品;p(full);p(empty);从缓冲区中取产品;从缓冲区中取产品;p(mutex);v(mutex);送一个产品到缓冲区;送一个产品到缓冲区;v(empty);v(mutex);v(full);消费一个产品;消费一个产品; 阻塞阻塞阻塞阻塞阻塞阻塞当缓冲区当缓冲区全为空全为空,一个消费者,一个消费
131、者先执行时先执行时这是一种什么样的问题呢?这是一种什么样的问题呢?连续进行连续进行二次封锁二次封锁,处理不当,就有可能造成,处理不当,就有可能造成死锁死锁.202 p1()p2()while(生产未完成生产未完成)while(还要继续消费还要继续消费)p(full);生产一个产品;生产一个产品;p(mutex);p(mutex);从缓冲区取产品;从缓冲区取产品;p(empty);v(mutex);送一个产品到缓冲区;送一个产品到缓冲区;v(empty);v(mutex);v(full);消费一个产品;消费一个产品;也会产生什么死锁吗也会产生什么死锁吗?在什么情况下会?在什么情况下会?203解同
132、步问题的解同步问题的5个要点个要点1.确定同步类型确定同步类型次序唯一、且次序唯一、且无循环无循环:次序图:次序图;否则:否则:互斥互斥 共享一个缓冲区共享一个缓冲区 生产者生产者-消费者消费者2.设计信号灯设计信号灯(包括其他的附加限制包括其他的附加限制)3.写写mand():定义信号灯、并赋初值:定义信号灯、并赋初值(0)4.用过程写进程的描述步骤(用过程写进程的描述步骤(至少分为二步至少分为二步)在在受限制的程序段受限制的程序段前进行前进行P操作操作(一次一次或或多次多次)在在受限制的程序段受限制的程序段后进行后进行V操作操作(一次一次或或多次多次)5.检查,至少:检查,至少:P(Si)
133、=V(Si)P(Si)=V(Si)例例1:习题:习题4.12(P116) 缓冲区缓冲区S 缓冲区缓冲区Tgetcopyput 缓冲区缓冲区Scopyget5432154321 缓冲区缓冲区Tputcopy共享一个缓冲区共享一个缓冲区?或生产者消费者问题或生产者消费者问题?54321任何同步的关键:任何同步的关键:都是避免与时间有关的错误都是避免与时间有关的错误此题:此题:可对各个局部考虑其正确性可对各个局部考虑其正确性 main() intsa=0 *表示缓冲区表示缓冲区S是否为满是否为满intsb=1*表示缓冲区表示缓冲区S是否为空是否为空intta=0*表示缓冲区表示缓冲区T是否为满是否为
134、满inttb=1*表示缓冲区表示缓冲区T是否为空是否为空cobeginget()copy()put()coend206get()while(还要计算还要计算)产生一个结果数据产生一个结果数据p(sb)数数据据送缓冲区送缓冲区s s中中v(sa)put()while(还要输出还要输出)p(ta)从缓冲区从缓冲区t t中中取数取数据据v(tb)在打印机上输出在打印机上输出207copy()while(还要复制还要复制)p(sa)取取s中的数中的数据据v(sb) p(tb)将数将数据据送到送到t中中v(ta) copy()while(还要复制还要复制)p(sa)p(tb)将将s中的数中的数据据复制到
135、复制到tv(ta)v(sb)那一种算法的那一种算法的并发性并发性好些呢?好些呢?同步的类型,还能进行更深入的划分吗?同步的类型,还能进行更深入的划分吗?典型典型1:读者写者问题:读者写者问题(可可互斥互斥、共享共享的资源的资源)定义:定义:一个一个数据数据对象对象(如如文件文件、数据库表数据库表等等)可由多个并发进程读、写。可由多个并发进程读、写。其同步限制是:其同步限制是:(1)当一进程正在当一进程正在写写时:时:其他进程其他进程不能读,不能写不能读,不能写(反之亦然反之亦然)(2)当一进程正在当一进程正在读读时:时:其他进程其他进程能读,能读,但不能写但不能写分析:分析:对写进程,对写进程
136、,互斥问题互斥问题对读进程,要区分对读进程,要区分三种可能三种可能的情形的情形第一个进程读之前第一个进程读之前:申请资源申请资源(互斥问题互斥问题)第二个及以后的进程读之前第二个及以后的进程读之前:没有限制没有限制最后一个进程读完后最后一个进程读完后:释放资源释放资源(互斥问题互斥问题)实现实现:(1)(1)写进程完成:写进程完成:对数据对象进行封锁对数据对象进行封锁将数据写入数据对象将数据写入数据对象解除对数据对象的封锁解除对数据对象的封锁(2)(2)读进程读进程通过一个计数器通过一个计数器完成:完成:计数器计数器加加1,设定自己的身份,设定自己的身份若是第一个读者:若是第一个读者:对数据对
137、象进行封锁对数据对象进行封锁读数据对象读数据对象完成后,完成后,计数器计数器减减1若是最后一个读者:若是最后一个读者:解除数据对象的封锁解除数据对象的封锁 思考:思考:程序的描述程序的描述( (特别是特别是读进程读进程) )? 同步的类型:同步的类型:对对互斥互斥问题的进一步扩展问题的进一步扩展思考题:思考题:过隧道的问题过隧道的问题东东西西思考:思考:更完善的解法更完善的解法(读者问题、或两边分批通过)(读者问题、或两边分批通过)简单的解法简单的解法整体作为一个整体作为一个临界临界资源资源互斥互斥问题?问题?典型典型2 2:哲学家进餐的问题:哲学家进餐的问题 5 5个个哲学家坐在餐桌旁思考问
138、题哲学家坐在餐桌旁思考问题 不与邻座的同事发生任何联系不与邻座的同事发生任何联系( (相互独立相互独立) ) 饥饿时饥饿时( (随机,或随机,或定点开饭定点开饭) ) 拿手边的筷子吃饭拿手边的筷子吃饭 一次只能拿一只筷子一次只能拿一只筷子 只有拿到两只筷子后只有拿到两只筷子后( (二次封锁二次封锁) ),才能吃饭,才能吃饭 否则,就必须等待否则,就必须等待 他们可能他们可能会饿死吗?会饿死吗?如何解决?如何解决?01432解决办法:解决办法:必须保证有必须保证有一个人一个人不参与争抢不参与争抢但又不能将一个人但又不能将一个人置于死地置于死地,如何实现呢?,如何实现呢?01234(1)0号哲学家
139、先拿左边的筷子号哲学家先拿左边的筷子其余的先拿右边的筷子其余的先拿右边的筷子014320、1号哲学家,机会至少比号哲学家,机会至少比平均数平均数少一半少一半问题问题?(2)双号哲学家先拿左边的筷子双号哲学家先拿左边的筷子单号哲学家先拿右边的筷子。单号哲学家先拿右边的筷子。问题?问题?014324号哲学家的机会比号哲学家的机会比平均数平均数多一倍多一倍如何才能做到如何才能做到相对公平相对公平? (3)(3)使用一个使用一个轮转令牌轮转令牌,由令牌决定谁特殊,由令牌决定谁特殊 令牌最初发给令牌最初发给0 0号哲学家号哲学家 此轮结束后:此轮结束后: 将令牌传给下一号哲学家将令牌传给下一号哲学家 如
140、此循环如此循环公平性:公平性:吃亏、或占便宜的吃亏、或占便宜的概率相等概率相等 有令牌有令牌的哲学家先拿的哲学家先拿左边左边的筷子的筷子 其余的哲学家先拿其余的哲学家先拿右边右边的筷子的筷子一般的实现:一般的实现:用二个数组分别表示用二个数组分别表示 5 5个个哲学家哲学家,及,及对对5 5只筷子的只筷子的互斥信号灯互斥信号灯思考:思考:程序的描述程序的描述 此问题能此问题能用用生产者生产者消费者消费者模型模型来实现吗?来实现吗?(也要用一个数组来指明不同的资源也要用一个数组来指明不同的资源)适用的同步方式:适用的同步方式:多个多个进程进程,与,与多个多个资源资源存在存在对应关系对应关系 用数
141、组的下标,来标明用数组的下标,来标明进程进程、及、及资源资源实现算法的意义:实现算法的意义:资源肯定不足资源肯定不足 典型典型3:多种同步类型的综合多种同步类型的综合理发店里有一个理发师、一张理发店里有一个理发师、一张理发椅理发椅(坐坐1个个顾客顾客)4把供顾客用的把供顾客用的等待椅等待椅(多缓冲区多缓冲区)约定:约定:对理发师:对理发师:理发椅上有顾客,则给顾客理发理发椅上有顾客,则给顾客理发否则在一旁否则在一旁等待等待对顾客:对顾客:(1)没有空闲的没有空闲的等待椅等待椅,则不理发,则不理发离开离开理发店理发店否则:坐在否则:坐在等待椅等待椅上,等待上,等待理发椅理发椅为空为空(2)直到直
142、到理发椅理发椅为空,坐上理发椅理发为空,坐上理发椅理发理完发后离开理发椅理完发后离开理发椅同步限制同步限制 :(1)理发师、与顾客:理发师、与顾客:共享一个缓冲区共享一个缓冲区模型模型(2)顾客与顾客:顾客与顾客:生产者生产者/消费者消费者,但但椅子椅子满了不等待满了不等待故要对已坐人的椅子故要对已坐人的椅子计数计数,判别身份,判别身份(类似于类似于读者读者)互斥问题的深入探讨互斥问题的深入探讨 理发师理发师 顾客顾客K4.8 进程的通信进程的通信一、进程通信的概念一、进程通信的概念同步的实质:同步的实质:只传递一个信号只传递一个信号通过预先的通过预先的约定约定,实现进程间的合作,实现进程间的
143、合作进程通信:进程通信:指多个进程通过传递消息指多个进程通过传递消息实现进程间的实现进程间的信息交换信息交换能解决:能解决:可不可以可不可以做、以及做、以及如何如何做的问题做的问题能解决:能解决:可不可以做可不可以做的问题的问题无法解决:在多种做法中进行无法解决:在多种做法中进行选择选择(如何做如何做)221二、消息缓冲通信二、消息缓冲通信类似于每户有一个类似于每户有一个信箱信箱,用来放,用来放名信片名信片1.主要的数据结构主要的数据结构(1)消息缓冲区消息缓冲区(共享的结构共享的结构)size:消息的:消息的长度长度text:消息正文:消息正文sptr:指向指向发送进程发送进程的指针的指针(
144、或或标识标识,发送者发送者)nptr:消息消息(接受接受)队列的链接指针队列的链接指针222(2)消息发送区消息发送区(在在发送进程发送进程的私有空间中的私有空间中)id:接受进程的标识接受进程的标识(接受者接受者)size:消息的长度:消息的长度text:消息正文:消息正文(3)消息接受区消息接受区(在在接受进程接受进程的私有空间中的私有空间中)id:发送进程的标识发送进程的标识(发送者发送者)size:消息的长度:消息的长度text:消息正文:消息正文(4)接受进程的消息队列接受进程的消息队列队列首指针在队列首指针在接受进程接受进程的的PCB中中2.简单的消息缓冲通信原理简单的消息缓冲通信
145、原理由发送进程、接受进程,分别调用相应的原语由发送进程、接受进程,分别调用相应的原语封锁接受进程的消息队列封锁接受进程的消息队列(P操作操作)将消息缓冲区挂到将消息缓冲区挂到接受进程接受进程的消息队列的消息队列释放接受进程的消息队列释放接受进程的消息队列(V操作操作) 唤醒接受进程唤醒接受进程(V操作操作) (1)发送原语发送原语Send(m)从消息缓冲池申请一个空消息缓冲区从消息缓冲池申请一个空消息缓冲区(P操作操作)复制发送区复制发送区m的内容到消息缓冲区的内容到消息缓冲区(2)接受原语接受原语Receive(n,id)检测检测调用进程消息队列调用进程消息队列是否有消息是否有消息(P操作操
146、作)封锁消息队列封锁消息队列(P操作操作)将将指定消息指定消息从消息队列中摘除从消息队列中摘除释放消息队列释放消息队列(V操作操作)(3)实质:实质:在同步在同步(生产者消费者生产者消费者)的基础上,传递信息的基础上,传递信息复制消息缓冲区的内容到消息接受区复制消息缓冲区的内容到消息接受区释放消息缓冲区到消息缓冲池释放消息缓冲区到消息缓冲池(V操作操作)(4)过程演示过程演示 Id:Size::Text: Send(m)Id:7Size::6Text:Hellow Receive(n,5)mn发送进程发送进程(Id=5)接受进程接受进程(Id=7)接受进程接受进程PCB接受进程消息队列接受进程消息队列消息缓冲区消息缓冲区1消息缓冲区消息缓冲区n Id:5Size::6Text:HellowId:5Size::6Text:Hellow思考:思考:怎么实现发送进程和接受进程同步?怎么实现发送进程和接受进程同步?