《第二章进程管理》由会员分享,可在线阅读,更多相关《第二章进程管理(232页珍藏版)》请在金锄头文库上搜索。
1、第二章进 程 管 理 第二章进 程 管 理 2.1进程的基本概念进程的基本概念 2.2进程控制进程控制 2.3进程同步进程同步 2.4经典进程的同步问题经典进程的同步问题 2.5 进程通信进程通信 2.6线程线程 绵赖短详蔫馅墟聪淫屹绿征沃盒件签骆鸯怜帝赡噪扒贾僧凸汛茫臀霖负滦第二章进程管理第二章进程管理第二章进 程 管 理 2.1进程的基本概念进程的基本概念 2.1.1程序的顺序执行及其特征程序的顺序执行及其特征1. 程序的顺序执行程序的顺序执行通常可以把一个应用程序分成若干个程序段,在各程序段之间,必须按照某种先后次序顺序执行,仅当前一操作(程序段)执行完后,才能执行后继操作。例如,在进行
2、计算时,总须先输入用户的程序和数据,然后进行计算,最后才能打印计算结果。这里,我们用结点(Node)代表各程序段的操作(在图2-1中用圆圈表示),其中,I代表输入操作,C代表计算操作,P为打印操作;另外,用箭头指示操作的先后次序。这样,上述的三个程序段的执行顺序可示于图2-1(a)中。对一个程序段中的多条语句来说,也有一个执行顺序问题,例如对于下述三条语句的程序段:躲胆跃变蟹蜘怒悦横野嚎汗喉阐逃滥郧染憾士场临号泌屁揭谰桂卖歇憨昂第二章进程管理第二章进程管理第二章进 程 管 理 S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;其中,语句S2必须在语句S1之后(即a被赋值)才能执行;同
3、样,语句S3也只能在b被赋值后才能执行。因此,这三条语句应按图2-1(b)所示的顺序执行。炎翻呢矗坝哺愚膀剿寇隔重蛾颐乐尝装芜妨除旨尿哈朱欲戊四铲荣宙玩仁第二章进程管理第二章进程管理第二章进 程 管 理 图2-1程序的顺序执行娄恒永庶厩述咯颈笑檬虾稼达操棵苟失啦透栽浑录摊蒲闺脏罕刹洼钎户驱第二章进程管理第二章进程管理第二章进 程 管 理 2. 程序顺序执行时的特征程序顺序执行时的特征(1) 顺序性:处理机的操作严格按照程序所规定的顺序执行,即每一操作必须在上一个操作结束之后开始。(2) 封闭性:程序是在封闭的环境下执行的,即程序运行时独占全机资源,资源的状态(除初始状态外)只有本程序才能改变它
4、。程序一旦开始执行,其执行结果不受外界因素影响。(3) 可再现性:只要程序执行时的环境和初始条件相同,当程序重复执行时,不论它是从头到尾不停顿地执行,还是“停停走走”地执行,都将获得相同的结果。程序顺序执行时的特性,为程序员检测和校正程序的错误带来了很大的方便。妒咕税琳跌丁癣欲河矩林窒赖俩鼠憾柑岛愿穴韭趴拜句蛙午獭抛骆油搪怨第二章进程管理第二章进程管理第二章进 程 管 理 2.1.2前趋图前趋图前趋图(PrecedenceGraph)是一个有向无循环图,记为DAG(DirectedAcyclicGraph),用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程,乃至一条语句
5、;结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder,亦称偏序关系)或前趋关系(PrecedenceRelation)“”。束忻盂保毯龚陛玛义剑囱某哉斜韭峻禄湿瑶熏晴笔翁棚韩叁绑懂蕾量序柿第二章进程管理第二章进程管理第二章进 程 管 理 =(Pi,Pj)|PimustcompletebeforePjmaystart,如果(Pi,Pj),可写成PiPj,称Pi是Pj的直接前趋,而称Pj是Pi的直接后继。在前趋图中,把没有前趋的结点称为初始结点(InitialNode),把没有后继的结点称为终止结点(FinalNode)。此外,每个结点还具有一个重量(Weight),用于表示
6、该结点所含有的程序量或结点的执行时间。在图2-1(a)和2-1(b)中分别存在着这样的前趋关系:IiCiPiS1S2S3和远社茁振拥谅搂浪胞愿兔自囱朔叛讳斥庞央音疯措领事服捡秩扔攻商题寄第二章进程管理第二章进程管理第二章进 程 管 理 对于图2-2(a)所示的前趋图,存在下述前趋关系:P1P2, P1P3, P1P4, P2P5, P3P5, P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为:P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),
7、(P6,P8),(P7,P9),(P8,P9)应当注意,前趋图中必须不存在循环,但在图2-2(b)中却有着下述的前趋关系:S2S3,S3S2糟婚朋却储颤翰稻芽苍肥无楚魂杜肺洛渔捧薪开往拒沪钥饶社肺舟擞秋蹭第二章进程管理第二章进程管理第二章进 程 管 理 图2-2前趋图沿囊寂嚣苗订隧惶潭茵雾砚破霄富淘玻撮寸陀培吁签檄降崖执眨晤昨求痰第二章进程管理第二章进程管理第二章进 程 管 理 2.1.3程序的并发执行及其特征程序的并发执行及其特征1程序的并发执行程序的并发执行在图2-1中的输入程序、计算程序和打印程序三者之间,存在着IiCiPi这样的前趋关系,以至对一个作业的输入、计算和打印三个操作,必须顺
8、序执行,但并不存在PiIi+1的关系,因而在对一批程序进行处理时,可使它们并发执行。例如,输入程序在输入第一个程序后,在计算程序对该程序进行计算的同时,可由输入程序再输入第二个程序,从而使第一个程序的计算操作可与第二个程序的输入操作并发执行。一般来说,输入程序在输入第i+1个程序时,计算程序可能正在对第i个程序进行计算,而打印程序正在打印第i-1个程序的计算结果。图2-3示出了输入、计算和打印这三个程序对一批作业进行处理的情况。避边桃钧每缉狰刺绒恰侣起畅凹物辙诌寅铂岭因虞择稠搜践汇芜膊勤魔忿第二章进程管理第二章进程管理第二章进 程 管 理 图2-3并发执行时的前趋图哭倒脖牢戈底螟盏撞歉宁靖源域
9、蓬浑硕焊皖我达萄票翻姑染鸣灯霍抉挥掌第二章进程管理第二章进程管理第二章进 程 管 理 在该例中存在下述前趋关系:IiCi,IiIi+1,CiPi,CiCi+1,PiPi+1而Ii+1和Ci及Pi-1是重迭的,亦即在Pi-1和Ci以及Ii+1之间,可以并发执行。对于具有下述四条语句的程序段:S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+b穆怨殊帽力滇吼隋辫杀耕兼瞅逐迈褐涌按瑚略沂胰纤此杠蜒蚤酚卑鹅娃逃第二章进程管理第二章进程管理第二章进 程 管 理 图2-4四条语句的前趋关系凶嚣淹芦绩婚初蛰托深虫尸低藩无械屠却时慑蜂革萌镰敢卜绑搂锗新宦巨第二章进程管理第二章进程管理第二章
10、进 程 管 理 2 2程序并发执行时的特征程序并发执行时的特征1) 间断性程序在并发执行时,由于它们共享系统资源,以及为完成同一项任务而相互合作,致使在这些并发执行的程序之间,形成了相互制约的关系。例如,图2-3中的I、C和P是三个相互合作的程序,当计算程序完成Ci1的计算后,如果输入程序I尚未完成Ii的处理,则计算程序就无法进行Ci的处理,致使计算程序必须暂停运行。又如,当打印程序完成Pi的打印后,若计算程序尚未完成Ci1的计算,则打印程序就无法对Ci1的计算结果进行打印。一旦使程序暂停的因素消失后(如Ii已处理完成),计算程序便可恢复执行对Ci的处理。简而言之,相互制约将导致并发程序具有“
11、执行暂停执行”这种间断性的活动规律。户辫绘子遇陕蓬射饱佣钦格矣稽竞溜菊破苦盐判惊躬奴暴几铆蹭冶予隆焚第二章进程管理第二章进程管理第二章进 程 管 理 2) 失去封闭性程序在并发执行时,是多个程序共享系统中的各种资源,因而这些资源的状态将由多个程序来改变,致使程序的运行失去了封闭性。这样,某程序在执行时,必然会受到其它程序的影响。例如,当处理机这一资源已被某个程序占有时,另一程序必须等待。马褒悍铰概拴帆设鞍栈植径蔑糯熄币艰热凑央望暴咙逆女渭馋苫麻蒙爽乾第二章进程管理第二章进程管理第二章进 程 管 理 3) 不可再现性程序在并发执行时,由于失去了封闭性,也将导致其再失去可再现性。例如,有两个循环程
12、序A和B,它们共享一个变量N。程序A每执行一次时,都要做N:=N+1操作;程序B每执行一次时,都要执行Print(N)操作,然后再将N置成“0”。程序A和B以不同的速度运行。这样,可能出现下述三种情况(假定某时刻变量N的值为n)。警鲜么适疆毗岛涎检瘦兼缕蠢挚睬驰况碳法估镁主哭党作歹馒雄伺蒋嚎亏第二章进程管理第二章进程管理第二章进 程 管 理 (1) N:=N+1在Print(N)和N:=0之前,此时得到的N值分别为n+1,n+1,0。(2) N:=N+1在Print(N)和N:=0之后,此时得到的N值分别为n,0,1。(3) N:=N+1在Print(N)和N:=0之间,此时得到的N值分别为n
13、,n+1,0。上述情况说明,程序在并发执行时,由于失去了封闭性,其计算结果已与并发程序的执行速度有关,从而使程序的执行失去了可再现性,亦即,程序经过多次执行后,虽然它们执行时的环境和初始条件相同,但得到的结果却各不相同。宾榷畔级评丁嫌疤搁僵淮端穿琼为朝榨姨滨尚属浆想询掘瘴缀绅委此有盟第二章进程管理第二章进程管理第二章进 程 管 理 2.1.42.1.4进程的特征与状态进程的特征与状态1. 1. 进程的特征和定义进程的特征和定义在多道程序环境下,程序的执行属于并发执行,此时它们将失去其封闭性,并具有间断性及不可再现性的特征。这决定了通常的程序是不能参与并发执行的,因为程序执行的结果是不可再现的。
14、这样,程序的运行也就失去了意义。为使程序能并发执行,且为了对并发执行的程序加以描述和控制,人们引入了“进程”的概念。为了能较深刻地了解什么是进程,我们将先对进程的特征加以描述。埂插试澜搭疗窑司故留蒂掇溃挑喜券吏娱太庙螺景讯奏渺杆藏嫁亚驾蜒镍第二章进程管理第二章进程管理第二章进 程 管 理 1) 结构特征通常的程序是不能并发执行的。为使程序(含数据)能独立运行,应为之配置一进程控制块,即PCB(ProcessControlBlock);而由程序段、相关的数据段和PCB三部分便构成了进程实体。在早期的UNIX版本中,把这三部分总称为“进程映像”。值得指出的是,在许多情况下所说的进程,实际上是指进程
15、实体,例如,所谓创建进程,实质上是创建进程实体中的PCB;而撤消进程,实质上是撤消进程的PCB,本教材中也是如此。富作饿黔周列埂谐炳傈桩愁嵌站橡佐瓷罩耿浦辅蒙鹅里痊瑞丛咋繁盔只将第二章进程管理第二章进程管理第二章进 程 管 理 2) 动态性进程的实质是进程实体的一次执行过程,因此,动态性是进程的最基本的特征。动态性还表现在:“它由创建而产生,由调度而执行,由撤消而消亡”。可见,进程实体有一定的生命期,而程序则只是一组有序指令的集合,并存放于某种介质上,其本身并不具有运动的含义,因而是静态的。氏宽卜症溜析蔬赎些锑弓炎皿喀绍萨湍无临厦蹲篮悉姥馁大寝右熟奖仰快第二章进程管理第二章进程管理第二章进 程
16、 管 理 3) 并发性这是指多个进程实体同存于内存中,且能在一段时间内同时运行。并发性是进程的重要特征,同时也成为OS的重要特征。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行;而程序(没有建立PCB)是不能并发执行的。4) 独立性在传统的OS中,独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。癸痘印镜祭霓陶鲜抿牛腻建母棕嘿母汾柄椰尚呼聘档蝎棒她韭谎茅陷板帚第二章进程管理第二章进程管理第二章进 程 管 理 5) 异步性这是指进程按各自独立的、 不可预知的速度向前推进,或说进程实体按异步方式运行。现在我
17、们再来讨论进程的定义。曾有许多人从不同的角度对进程下过定义,其中较典型的进程定义有:(1) 进程是程序的一次执行。(2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位。泄芦硼坡工宪丢栈馏饶栽语窖玛烬靡振留吴前祭涂禽侥缎樊醋泻聚微侩肮第二章进程管理第二章进程管理第二章进 程 管 理 2. 2. 进程的三种基本状态进程的三种基本状态进程执行时的间断性决定了进程可能具有多种状态。事实上,运行中的进程可能具有以下三种基本状态。1) 就绪(Ready)状态当进程已分配到除CPU以外的所有必要资源后,只要再获得
18、CPU,便可立即执行,进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个,通常将它们排成一个队列,称为就绪队列。聘叹圣喷惶仓姓衡定娠狭懒卑沫哉弦嘉峡栅酞炙演欧马鲸呀恫麓衙合钠墟第二章进程管理第二章进程管理第二章进 程 管 理 2) 执行状态进程已获得CPU,其程序正在执行。在单处理机系统中,只有一个进程处于执行状态; 在多处理机系统中,则有多个进程处于执行状态。3) 阻塞状态正在执行的进程由于发生某事件而暂时无法继续执行时,便放弃处理机而处于暂停状态,亦即进程的执行受到阻塞,把这种暂停状态称为阻塞状态,有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有:请求I/O,申请缓
19、冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。擞箍嚣苇疽依拈徐啼勿掏粳爸弥系亲色铸篆比间哲浆苔盘享牲按冬即脸警第二章进程管理第二章进程管理第二章进 程 管 理 图2-5进程的三种基本状态及其转换栈唐蓄兄肆拧佩萧沂熬篱洲宠序蓄撰娟衰谰逛傻祷立适缴健筏捅涧鸡谤婉第二章进程管理第二章进程管理第二章进 程 管 理 3. 3. 挂起状态挂起状态1) 引入挂起状态的原因在不少系统中进程只有上述三种状态,但在另一些系统中,又增加了一些新状态,最重要的是挂起状态。引入挂起状态的原因有:(1)终端用户的请求。当终端用户在自己的程序运行期间发
20、现有可疑问题时,希望暂时使自己的程序静止下来。亦即,使正在执行的进程暂停执行;若此时用户进程正处于就绪状态而未执行,则该进程暂不接受调度,以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。救社辩抡方食蛇辅趁排命湛惭塘安蹄潞裕诀恐株恤疽胚叶州柯颗镁艘爆拧第二章进程管理第二章进程管理第二章进 程 管 理 (2) 父进程请求。有时父进程希望挂起自己的某个子进程,以便考查和修改该子进程,或者协调各子进程间的活动。(3) 负荷调节的需要。当实时系统中的工作负荷较重,已可能影响到对实时任务的控制时,可由系统把一些不重要的进程挂起,以保证系统能正常运行。(4)操作系统的需要。操作系统有
21、时希望挂起某些进程,以便检查运行中的资源使用情况或进行记账。曲棠尾瘫贮菱顶忠抓藐抚棘右纽蛤棚鬼磺携脏烹嗜脏故颈毗砷弦哨枚奢知第二章进程管理第二章进程管理第二章进 程 管 理 2) 进程状态的转换在引入挂起状态后,又将增加从挂起状态(又称为静止状态)到非挂起状态(又称为活动状态)的转换;或者相反。可有以下几种情况:(1)活动就绪静止就绪。当进程处于未被挂起的就绪状态时,称此为活动就绪状态,表示为Readya。当用挂起原语Suspend将该进程挂起后,该进程便转变为静止就绪状态,表示为Readys,处于Readys状态的进程不再被调度执行。邻铝斡田淀谷旷反哗衰加诽辫铣梳濒阎准隔隧裸翌穆垫篮照睁硝馈
22、箭窝妒第二章进程管理第二章进程管理第二章进 程 管 理 图2-6具有挂起状态的进程状态图厦秋贼啄矿勤嗣锗嗓吓瓮狰熄缘倾缠徘悲辖幸挥锭及袱草惧完私凛憋祖锈第二章进程管理第二章进程管理第二章进 程 管 理 (2) 活动阻塞静止阻塞。当进程处于未被挂起的阻塞状态时,称它是处于活动阻塞状态,表示为Blockeda。当用Suspend原语将它挂起后,进程便转变为静止阻塞状态,表示为Blockeds。处于该状态的进程在其所期待的事件出现后,将从静止阻塞变为静止就绪。(3) 静止就绪活动就绪。处于Readys状态的进程,若用激活原语Active激活后,该进程将转变为Readya状态。(4)静止阻塞活动阻塞。
23、处于Blockeds状态的进程,若用激活原语Active激活后,该进程将转变为Blockeda状态。图2-6示出了具有挂起状态的进程状态图。艳彻疥永负吹俭熔荫而娇哥替铜湖畔烫罐锄袒危奶释滓鄙脂婶叫驴咆辫车第二章进程管理第二章进程管理第二章进 程 管 理 4 4创建状态和终止状态创建状态和终止状态1) 创建状态创建一个进程一般要通过两个步骤:首先,为一个新进程创建PCB,并填写必要的管理信息;其次,把该进程转入就绪状态并插入就绪队列之中。当一个新进程被创建时,系统已为其分配了PCB,填写了进程标识等信息,但由于该进程所必需的资源或其它信息,如主存资源尚未分配等,一般而言,此时的进程已拥有了自己的
24、PCB,但进程自身还未进入主存,即创建工作尚未完成,进程还不能被调度运行,其所处的状态就是创建状态。哇鸟甥碰凋房墟掣捅搭扒翌村歌垃哈占挺之驭缨卒蹋算航羊矢缚吾亡伍芒第二章进程管理第二章进程管理第二章进 程 管 理 引入创建状态,是为了保证进程的调度必须在创建工作完成后进行,以确保对进程控制块操作的完整性。同时,创建状态的引入,也增加了管理的灵活性,操作系统可以根据系统性能或主存容量的限制,推迟创建状态进程的提交。对于处于创建状态的进程,获得了其所必需的资源,以及对其PCB初始化工作完成后,进程状态便可由创建状态转入就绪状态。刹垦阿悔亥怔联穿毕墨宦解称换俐棘汽匆什硕岸融脊舆寝庸号突燕邻烃腹第二章
25、进程管理第二章进程管理第二章进 程 管 理 2) 终止状态进程的终止也要通过两个步骤:首先等待操作系统进行善后处理,然后将其PCB清零,并将PCB空间返还系统。当一个进程到达了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结,它将进入终止状态。进入终止态的进程以后不能再执行,但在操作系统中依然保留一个记录,其中保存状态码和一些计时统计数据,供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后,操作系统将删除该进程。图2-7示出了增加了创建状态和终止状态后,进程的三种基本状态及转换图衍变为五种状态及转换关系图。晚咎渍琉泻肠五绢能嚏搐巡癸它唯模傲
26、倚由塔袱漫秽努假穿惶垛植巩蕴充第二章进程管理第二章进程管理第二章进 程 管 理 图2-7进程的五种基本状态及转换围鼻因乍咒浓岂诱颊石秩驼钒陪冈宠宙苟色菏胜底炸但秽崖哮瘟酵糕挤仪第二章进程管理第二章进程管理第二章进 程 管 理 图2-8具有创建、终止和挂起状态的进程状态图砷达揉猿欢螟化色鄙烙体郑罪颖又慈峰瞻旨觅诬仓令脖血属锌缩歇宴湘诲第二章进程管理第二章进程管理第二章进 程 管 理 如图2-8所示,引进创建和终止状态后,在进程状态转换时,相比较图2-7所示的进程五状态转换而言,需要增加考虑下面的几种情况。(1) NULL创建:一个新进程产生时,该进程处于创建状态。(2)创建活动就绪:在当前系统的
27、性能和内存的容量均允许的情况下,完成对进程创建的必要操作后,相应的系统进程将进程的状态转换为活动就绪状态。揣卧柑舵枕唯势前秀诫缘瑞饱抉骆校娇侣惭帜睁政欺骨泥炸啃恤迈陌淳淮第二章进程管理第二章进程管理第二章进 程 管 理 (3) 创建静止就绪:考虑到系统当前资源状况和性能要求,并不分配给新建进程所需资源,主要是主存资源,相应的系统进程将进程状态转为静止就绪状态,对换到外存,不再参与调度,此时进程创建工作尚未完成。(4)执行终止:当一个进程到达了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结,进程即进终止状态。足土斩臣望选痕磺喧介戌深闹园组痕如组郁禄禽缴
28、薯蕊泉井忠扛傣衙槛圾第二章进程管理第二章进程管理第二章进 程 管 理 2.1.52.1.5进程控制块进程控制块1 1进程控制块的作用进程控制块的作用为了描述和控制进程的运行,系统为每个进程定义了一个数据结构进程控制块PCB(ProcessControlBlock),它是进程实体的一部分,是操作系统中最重要的记录型数据结构。PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据),成为一个能独立运行的基本单位,一个能与其它进程并发执行的进程。说恳赏砒忙钒莱垛支启颅施剧他豹诌角褪扩腑迫树蕉痒彤栏厩抡平遏现幽
29、第二章进程管理第二章进程管理第二章进 程 管 理 或者说,OS是根据PCB来对并发执行的进程进行控制和管理的。例如,当OS要调度某进程执行时,要从该进程的PCB中查出其现行状态及优先级;在调度到某进程后,要根据其PCB中所保存的处理机状态信息,设置该进程恢复运行的现场,并根据其PCB中的程序和数据的内存始址,找到其程序和数据;进程在执行过程中,当需要和与之合作的进程实现同步、通信或访问文件时,也都需要访问PCB;当进程由于某种原因而暂停执行时,又须将其断点的处理机环境保存在PCB中。可见,在进程的整个生命期中,系统总是通过PCB对进程进行控制的,亦即,系统是根据进程的PCB而不是任何别的什么而
30、感知到该进程的存在的。所以说,PCB是进程存在的惟一标志。逞选铃候胰激骆同躁隔虽圾詹椰钥峻藕杨筐垄矣窥呈筹匹座峻四铬补爷衷第二章进程管理第二章进程管理第二章进 程 管 理 当系统创建一个新进程时,就为它建立了一个PCB;进程结束时又回收其PCB,进程于是也随之消亡。PCB可以被操作系统中的多个模块读或修改,如被调度程序、资源分配程序、中断处理程序以及监督和分析程序等读或修改。因为PCB经常被系统访问,尤其是被运行频率很高的进程及分派程序访问,故PCB应常驻内存。系统将所有的PCB组织成若干个链表(或队列),存放在操作系统中专门开辟的PCB区内。例如在Linux系统中用task_struct数据
31、结构来描述每个进程的进程控制块,在Windows操作系统中则使用一个执行体进程块(EPROCESS)来表示进程对象的基本属性。部贸曾挺即隘搅严搐乞矫稍鞘认系朵秋予阵攒槛水忠彬舱殿签糕塌忍级哗第二章进程管理第二章进程管理第二章进 程 管 理 2 2进程控制块中的信息进程控制块中的信息1) 进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符:(1) 内部标识符。在所有的操作系统中,都为每一个进程赋予了一个惟一的数字标识符,它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供,通常是由字母、数字组成,往往是由用户(进程)在访问该进程时使用。
32、为了描述进程的家族关系,还应设置父进程标识及子进程标识。此外,还可设置用户标识,以指示拥有该进程的用户。步菩漏贫带湃讼僻垮恋部聪瘸猖惶缉少赤衷利镑剔抨安坑藏惜卞阀庸爸辙第二章进程管理第二章进程管理第二章进 程 管 理 2) 处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机在运行时,许多信息都放在寄存器中。当处理机被中断时,所有这些信息都必须保存在PCB中,以便在该进程重新执行时,能从断点继续执行。这些寄存器包括:通用寄存器,又称为用户可视寄存器,它们是用户程序可以访问的,用于暂存信息,在大多数处理机中,有832个通用寄存器,在RISC结构的计算机中可超过100个;指令计
33、数器,其中存放了要访问的下一条指令的地址;程序状态字PSW,其中含有状态信息,如条件码、执行方式、中断屏蔽标志等;用户栈指针,指每个用户进程都有一个或若干个与之相关的系统栈,用于存放过程和系统调用参数及调用地址,栈指针指向该栈的栈顶。伤熄栗瘩嘉府忍诛肤孺裤颊泼敏十帐芝皑佐衔链杭音淬触抄执瑚刀磨慷繁第二章进程管理第二章进程管理第二章进 程 管 理 3) 进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息,包括:进程状态,指明进程的当前状态,作为进程调度和对换时的依据;进程优先级,用于描述进程使用处理机的优先级别的一个整数,优先级高的进程应优先获得处理机;进程调度所需的其它信息,它们与
34、所采用的进程调度算法有关,比如,进程已等待CPU的时间总和、进程已执行的时间总和等;事件,指进程由执行状态转变为阻塞状态所等待发生的事件,即阻塞原因。砰吨馏迅船急痢酸弘污岔描溪砧伶炒癌惟逃悍凤憋渊卯蓬馅轮村黄侠诈忻第二章进程管理第二章进程管理第二章进 程 管 理 4) 进程控制信息进程控制信息包括:程序和数据的地址,指进程的程序和数据所在的内存或外存地(首)址,以便再调度到该进程执行时,能从PCB中找到其程序和数据;进程同步和通信机制,指实现进程同步和进程通信时必需的机制,如消息队列指针、信号量等,它们可能全部或部分地放在PCB中;资源清单,即一张列出了除CPU以外的、进程所需的全部资源及已经
35、分配到该进程的资源的清单;链接指针,它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。豹读黑咒囊蓝限毅入纲滞嗡祝芯硒极斑响援峪姚橱刁折脓坍掖勒俱镜限仲第二章进程管理第二章进程管理第二章进 程 管 理 3. 3. 进程控制块的组织方式进程控制块的组织方式1) 链接方式这是把具有同一状态的PCB,用其中的链接字链接成一个队列。这样,可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按进程优先级的高低排列,把优先级高的进程的PCB排在队列前面。此外,也可根据阻塞原因的不同而把处于阻塞状态的进程的PCB排成等待I/O操作完成的队列和等待分配内存的队列等。图2-9示出了一种链
36、接队列的组织方式。咕脯姚衔约王款吉巢吾腐鬼狗恋线荡诚孙薯挝环怪卵兑拦第雍咖财盂戎谭第二章进程管理第二章进程管理第二章进 程 管 理 图 2-9PCB链接队列示意图队硝堤粱阑利蔗藉谗幸叛筋驰虾债愉毗励坦岿叙焚疑的悲漆伪溯更行睡胶第二章进程管理第二章进程管理第二章进 程 管 理 2) 索引方式系统根据所有进程的状态建立几张索引表。例如,就绪索引表、阻塞索引表等,并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中,记录具有相应状态的某个PCB在PCB表中的地址。图2-10示出了索引方式的PCB组织。泪柳蝗办尿蒜兼粥闷戈遣致昏嚏卖哼螟凡壮篡剁遏谩纪碍被罩说抬裳谈杰第二章进程管理
37、第二章进程管理第二章进 程 管 理 图2-10按索引方式组织PCB趣菲盆屎假瑞皑蛹粮屠尹网果馒亲怎酪菏绪怨妈卓诊篙妨乘拧诬己底荤虽第二章进程管理第二章进程管理第二章进 程 管 理 2.2进进 程程 控控 制制 进程控制是进程管理中最基本的功能。它用于创建一个新进程,终止一个已完成的进程,或终止一个因出现某事件而使其无法运行下去的进程,还可负责进程运行中的状态转换。如当一个正在执行的进程因等待某事件而暂时不能继续执行时,将其转换为阻塞状态,而当该进程所期待的事件出现时,又将该进程转换为就绪状态等等。进程控制一般是由OS的内核中的原语来实现的。叔廖猩醚酵营酌着晤头猛酒诬涤狭帚补实冷宴阎郸颠肾诲刑八
38、赋饯捅机妄第二章进程管理第二章进程管理第二章进 程 管 理 原语(Primitive)是由若干条指令组成的,用于完成一定功能的一个过程。它与一般过程的区别在于:它们是“原子操作(ActionOperation)”。所谓原子操作,是指一个操作中的所有动作要么全做,要么全不做。换言之,它是一个不可分割的基本单位,因此,在执行过程中不允许被中断。原子操作在管态下执行,常驻内存。陌卞丸哎坐盔骄憨椎亥畔腾碧颐综卖旬泣肾费涕垄布窑屋乏提垄律斯虞怖第二章进程管理第二章进程管理第二章进 程 管 理 图2-11进程树畔吵谓篓辨界搬沛蕊攘闷樊擞拇各颧汰弥皋禾珐胞俱族愈师便椰践亩细椰第二章进程管理第二章进程管理第二
39、章进 程 管 理 2.2.12.2.1进程的创建进程的创建1 1进程图进程图(Process Graph)(Process Graph)进程图是用于描述一个进程的家族关系的有向树,如图2-11所示。图中的结点(圆圈)代表进程。在进程D创建了进程I之后,称D是I的父进程(ParentProcess),I是D的子进程(ProgenyProcess)。锤滨伏批骗杜慷淆沛己赫薄好汗单锁刽血施砌棱悯仆通堆衰肇艺福娠袒醒第二章进程管理第二章进程管理第二章进 程 管 理 2 2引起创建进程的事件引起创建进程的事件在多道程序环境中,只有(作为)进程(时)才能在系统中运行。因此,为使程序能运行,就必须为它创建进
40、程。导致一个进程去创建另一个进程的典型事件,可有以下四类:(1) 用户登录。在分时系统中,用户在终端键入登录命令后,如果是合法用户,系统将为该终端建立一个进程,并把它插入就绪队列中。(2)作业调度。在批处理系统中,当作业调度程序按一定的算法调度到某作业时,便将该作业装入内存,为它分配必要的资源,并立即为它创建进程,再插入就绪队列中。露段酷妓肚易箔码炔篡拒败被虞骆腑狱量脊颂傅已秃茅祁秆恫殿秆联朽浊第二章进程管理第二章进程管理第二章进 程 管 理 (3)提供服务。当运行中的用户程序提出某种请求后,系统将专门创建一个进程来提供用户所需要的服务,例如,用户程序要求进行文件打印,操作系统将为它创建一个打
41、印进程,这样,不仅可使打印进程与该用户进程并发执行,而且还便于计算出为完成打印任务所花费的时间。锋拴谁寐妮喇挝澡想草拟肘眼措胸室故件瞧朗今耙巍插柔饥攘韵晓骇搬碰第二章进程管理第二章进程管理第二章进 程 管 理 (4)应用请求。在上述三种情况下,都是由系统内核为它创建一个新进程;而第4类事件则是基于应用进程的需求,由它自己创建一个新进程,以便使新进程以并发运行方式完成特定任务。例如,某应用程序需要不断地从键盘终端输入数据,继而又要对输入数据进行相应的处理,然后,再将处理结果以表格形式在屏幕上显示。该应用进程为使这几个操作能并发执行,以加速任务的完成,可以分别建立键盘输入进程、表格输出进程。尊钥饿
42、放扣贿松疹颇翻惠怎蓬缸盗肋吉膨虫沏明绳卜辛采霓娜衫注狭速工第二章进程管理第二章进程管理第二章进 程 管 理 3 3进程的创建进程的创建(Creation of Process)(Creation of Process)一旦操作系统发现了要求创建新进程的事件后,便调用进程创建原语Creat( )按下述步骤创建一个新进程。(1)申请空白PCB。为新进程申请获得惟一的数字标识符,并从PCB集合中索取一个空白PCB。奋矩缨皖型陕镑鸭绑匿验遏麓莹斩磅守先哟痢酸眩匣姬缎柬骋溉峦滇忿幼第二章进程管理第二章进程管理第二章进 程 管 理 (2)为新进程分配资源。为新进程的程序和数据以及用户栈分配必要的内存空间。
43、显然,此时操作系统必须知道新进程所需内存的大小。对于批处理作业,其大小可在用户提出创建进程要求时提供。若是为应用进程创建子进程,也应是在该进程提出创建进程的请求中给出所需内存的大小。对于交互型作业,用户可以不给出内存要求而由系统分配一定的空间。如果新进程要共享某个已在内存的地址空间(即已装入内存的共享段),则必须建立相应的链接。骆巳慈漓裂隘窄床禹陨源挟磕智宠肖泄匹囚甄囱孔磨美菌厦褪斯沼辨漫瓦第二章进程管理第二章进程管理第二章进 程 管 理 (3) 初始化进程控制块。PCB的初始化包括: 初始化标识信息,将系统分配的标识符和父进程标识符填入新PCB中; 初始化处理机状态信息,使程序计数器指向程序
44、的入口地址,使栈指针指向栈顶; 初始化处理机控制信息,将进程的状态设置为就绪状态或静止就绪状态,对于优先级,通常是将它设置为最低优先级,除非用户以显式方式提出高优先级要求。(4)将新进程插入就绪队列,如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列。她洁匹渠野脚卸衫于杯炙幻墙处掖韩箱友添慰眷米醇零遭疡仲朔它彻沼颠第二章进程管理第二章进程管理第二章进 程 管 理 2.2.22.2.2进程的终止进程的终止1 1引起进程终止的事件引起进程终止的事件1) 正常结束在任何计算机系统中,都应有一个用于表示进程已经运行完成的指示。例如,在批处理系统中,通常在程序的最后安排一条Holt指令或终止的系统调
45、用。当程序运行到Holt指令时,将产生一个中断,去通知OS本进程已经完成。在分时系统中,用户可利用Logsoff去表示进程运行完毕,此时同样可产生一个中断,去通知OS进程已运行完毕。佣谦将骚忆伟咒夯胰栋救恫败焰托匡曙梭炭娟查岸岩积天垦奎纪财炽霍搅第二章进程管理第二章进程管理第二章进 程 管 理 2) 异常结束在进程运行期间,由于出现某些错误和故障而迫使进程终止(Termination of Process)。这类异常事件很多,常见的有下述几种:(1) 越界错误。这是指程序所访问的存储区已越出该进程的区域。(2) 保护错。这是指进程试图去访问一个不允许访问的资源或文件,或者以不适当的方式进行访问
46、,例如,进程试图去写一个只读文件。(3)非法指令。这是指程序试图去执行一条不存在的指令。出现该错误的原因,可能是程序错误地转移到数据区,把数据当成了指令。进默芭窃裁匙厉鞠金摈大箩诺薪馆帽赁吁氨志桂立愉帛必臼疑固妙庆腔既第二章进程管理第二章进程管理第二章进 程 管 理 (4) 特权指令错。这是指用户进程试图去执行一条只允许OS执行的指令。(5) 运行超时。这是指进程的执行时间超过了指定的最大值。(6) 等待超时。这是指进程等待某事件的时间超过了规定的最大值。(7) 算术运算错。这是指进程试图去执行一个被禁止的运算,例如被0除。(8)I/O故障。这是指在I/O过程中发生了错误等。吟惰碧帽愉嘶潦徐掇
47、恨沪肌潦莱钳旺牛碟萍地床飘旺堡瓣渗拜淀券钾被擎第二章进程管理第二章进程管理第二章进 程 管 理 3) 外界干预外界干预并非指在本进程运行中出现了异常事件,而是指进程应外界的请求而终止运行。这些干预有:(1) 操作员或操作系统干预。由于某种原因,例如,发生了死锁,由操作员或操作系统终止该进程。(2) 父进程请求。由于父进程具有终止自己的任何子孙进程的权力,因而当父进程提出请求时,系统将终止该进程。(3)父进程终止。当父进程终止时,OS也将它的所有子孙进程终止。足推获跪胚譬谋何滥缝撵蒸永饺钟彭琼洱杠童砰缆肠际语愤措贡叙披捻育第二章进程管理第二章进程管理第二章进 程 管 理 2 2进程的终止过程进程
48、的终止过程如果系统中发生了上述要求终止进程的某事件,OS便调用进程终止原语,按下述过程去终止指定的进程。(1) 根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态。(2)若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度。存免凹魂桑烘恐享宾怒倔天驱堵搓慑尤孤瀑霖破报畔细便召鸿雀扳矗戴损第二章进程管理第二章进程管理第二章进 程 管 理 (3) 若该进程还有子孙进程,还应将其所有子孙进程予以终止,以防它们成为不可控的进程。(4) 将被终止进程所拥有的全部资源,或者归还给其父进程,或者归还给系统。(5)将被终止进程
49、(PCB)从所在队列(或链表)中移出,等待其他程序来搜集信息。坑引绞荷铭躯衍酣各寂靴卢淆津闷萝坛塔呻再滦淳忿琅沥写燃拙冲仿雌炸第二章进程管理第二章进程管理第二章进 程 管 理 2.2.32.2.3进程的阻塞与唤醒进程的阻塞与唤醒1. 1. 引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件有下述几类事件会引起进程阻塞或被唤醒。1) 请求系统服务当正在执行的进程请求操作系统提供服务时,由于某种原因,操作系统并不立即满足该进程的要求时,该进程只能转变为阻塞状态来等待。例如,一进程请求使用某资源,如打印机,由于系统已将打印机分配给其他进程而不能分配给请求进程,这时请求者进程只能被阻塞,仅在其他进程在释
50、放出打印机的同时,才将请求进程唤醒。鸣馆蘸燎般樟原债蛆潦枪吧访增仍忙皮逊黎怜惹扶巨砾悉媳中枚皂轮疽咸第二章进程管理第二章进程管理第二章进 程 管 理 2) 启动某种操作当进程启动某种操作后,如果该进程必须在该操作完成之后才能继续执行,则必须先使该进程阻塞,以等待该操作完成。例如,进程启动了某I/O设备,如果只有在I/O设备完成了指定的I/O操作任务后进程才能继续执行,则该进程在启动了I/O操作后,便自动进入阻塞状态去等待。在I/O操作完成后,再由中断处理程序或中断进程将该进程唤醒。阁萧笺晚没驯搏秤蛀醋尉肠刨钾俭熄蠕送乙扫见肃士鹅亡绕康条箱姐慨内第二章进程管理第二章进程管理第二章进 程 管 理
51、3) 新数据尚未到达对于相互合作的进程,如果其中一个进程需要先获得另一(合作)进程提供的数据后才能对数据进行处理,则只要其所需数据尚未到达,该进程只有(等待)阻塞。例如,有两个进程,进程A用于输入数据,进程B对输入数据进行加工。假如A尚未将数据输入完毕,则进程B将因没有所需的处理数据而阻塞;一旦进程A把数据输入完毕,便可去唤醒进程B。苗屏磊噬饯红扇康裂移号似办睡拂税娄拂雾凯共猜挣好浆后猾惊舶节匝骨第二章进程管理第二章进程管理第二章进 程 管 理 4) 无新工作可做系统往往设置一些具有某特定功能的系统进程,每当这种进程完成任务后,便把自己阻塞起来以等待新任务到来。例如,系统中的发送进程,其主要工
52、作是发送数据,若已有的数据已全部发送完成而又无新的发送请求,这时(发送)进程将使自己进入阻塞状态;仅当又有进程提出新的发送请求时,才将发送进程唤醒。姜咀雇萝村掸娇卢趴笑暑永泰屹藐稿辙帮漆凋受卧旨捂檀藏顺窝涪耶锐独第二章进程管理第二章进程管理第二章进 程 管 理 2 2进程阻塞过程进程阻塞过程正在执行的进程,当发现上述某事件时,由于无法继续执行,于是进程便通过调用阻塞原语block把自己阻塞。可见,进程的阻塞是进程自身的一种主动行为。进入block过程后,由于此时该进程还处于执行状态,所以应先立即停止执行,把进程控制块中的现行状态由“执行”改为“阻塞”,并将PCB插入阻塞队列。如果系统中设置了因
53、不同事件而阻塞的多个阻塞队列,则应将本进程插入到具有相同事件的阻塞(等待)队列。最后,转调度程序进行重新调度,将处理机分配给另一就绪进程并进行切换,亦即,保留被阻塞进程的处理机状态(在PCB中),再按新进程的PCB中的处理机状态设置CPU的环境。娜掂价岂氟竣怖厩极雍疼辩有扔旋侯萌闭丢哩纱跨墟留仕研煮弱磕响挨贝第二章进程管理第二章进程管理第二章进 程 管 理 3 3进程唤醒过程进程唤醒过程当被阻塞进程所期待的事件出现时,如I/O完成或其所期待的数据已经到达,则由有关进程(比如用完并释放了该I/O设备的进程)调用唤醒原语wakeup( ),将等待该事件的进程唤醒。唤醒原语执行的过程是:首先把被阻塞
54、的进程从等待该事件的阻塞队列中移出,将其PCB中的现行状态由阻塞改为就绪,然后再将该PCB插入到就绪队列中。应当指出,block原语和wakeup原语是一对作用刚好相反的原语。因此,如果在某进程中调用了阻塞原语,则必须在与之相合作的另一进程中或其他相关的进程中安排唤醒原语,以能唤醒阻塞进程;否则,被阻塞进程将会因不能被唤醒而长久地处于阻塞状态,从而再无机会继续运行。苏呸豁旱隧尚够瞻插勇剁屹协蛾架迟恫惫冯丘港旬公湿鳞突垛产锁野赏婴第二章进程管理第二章进程管理第二章进 程 管 理 2.2.42.2.4进程的挂起与激活进程的挂起与激活1 1进程的挂起进程的挂起当出现了引起进程挂起的事件时,比如,用户
55、进程请求将自己挂起,或父进程请求将自己的某个子进程挂起,系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是:首先检查被挂起进程的状态,若处于活动就绪状态,便将其改为静止就绪;对于活动阻塞状态的进程,则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后,若被挂起的进程正在执行,则转向调度程序重新调度。停兢灌趾丹队藻踞搂解与绿氮乒杖稿剃康诬议释但叛柄前陶党爹启原粹戒第二章进程管理第二章进程管理第二章进 程 管 理 2 2进程的激活过程进程的激活过程当发生激活进程的事件时,例如,父进程或用户进程请求激活指
56、定进程,若该进程驻留在外存而内存中已有足够的空间时,则可将在外存上处于静止就绪状态的该进程换入内存。这时,系统将利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存,检查该进程的现行状态,若是静止就绪,便将之改为活动就绪;若为静止阻塞,便将之改为活动阻塞。假如采用的是抢占调度策略,则每当有新进程进入就绪队列时,应检查是否要进行重新调度,即由调度程序将被激活进程与当前进程进行优先级的比较,如果被激活进程的优先级更低,就不必重新调度;否则,立即剥夺当前进程的运行,把处理机分配给刚被激活的进程。焉协疆诊刚比柿折糙岁梯且伤审湾竖瞪韩唆缮跪矩典欢只蚕霸撞壹皿磨次第二章进程管理第二章
57、进程管理第二章进 程 管 理 2.3进进 程程 同同 步步 2.3.12.3.1进程同步的基本概念进程同步的基本概念1 1两种形式的制约关系两种形式的制约关系在多道程序环境下,当程序并发执行时,由于资源共享和进程合作,使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系。(1)间接相互制约关系。同处于一个系统中的进程,通常都共享着某种系统资源,如共享CPU、共享I/O设备等。所谓间接相互制约即源于这种资源共享,例如,有两个进程A和B,如果在A进程提出打印请求时,系统已将惟一的一台打印机分配给了进程B,则此时进程A只能阻塞;一旦进程B将打印机释放,则A进程才能由阻塞改为就绪状态。萤欢稠
58、詹追篷积亏肚运拾肇哩浩跨詹误甩力懂襟蔫碍则灾泰缔绣夺稀埔戏第二章进程管理第二章进程管理第二章进 程 管 理 (2)直接相互制约关系。这种制约主要源于进程间的合作。例如,有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时,计算进程因不能获得所需数据而阻塞,而当进程A把数据输入缓冲区后,便将进程B唤醒;反之,当缓冲区已满时,进程A因不能再向缓冲区投放数据而阻塞,当进程B将缓冲区数据取走后便可唤醒A。济橙豢毛洪措杀墙杜妙别鲍阐早化穷郴淋毕秦迟忻疲滁惩寻丙吠箭究梨勋第二章进程管理第二章进程管理第二章进 程 管 理 2. 2. 临界资源临界资源在第一章中我们曾经介绍过,许多硬件资源如打印机、磁带机等
59、,都属于临界资源(CriticalResouce),诸进程间应采取互斥方式,实现对这种资源的共享。下面我们将通过一个简单的例子来说明这一过程。坊嗣旺亨絮退编皮峪熟既犀雏鸡蹈读毋泛戒巩腐井告凛揽料常翔弥婚纱耪第二章进程管理第二章进程管理第二章进 程 管 理 生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行,在两者之间设置了一个具有n个缓冲区的缓冲池,生产者进程将它所生产的产品放入一个缓冲区中;消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进
60、程和消费者进程都是以异步方式运行的,但它们之间必须保持同步,即不允许消费者进程到一个空缓冲区去取产品,也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。推司幕贪搜前草粤泥身朽烘匀翔撂摹入李箔诞然凶淋损束蝴棋桅爹扩铭潭第二章进程管理第二章进程管理第二章进 程 管 理 我们可利用一个数组来表示上述的具有n个(0,1,n-1)缓冲区的缓冲池。用输入指针in来指示下一个可投放产品的缓冲区,每当生产者进程生产并投放一个产品后,输入指针加1;用一个输出指针out来指示下一个可从中获取产品的缓冲区,每当消费者进程取走一个产品后,输出指针加1。由于这里的缓冲池是组织成循环缓冲的,故应把输入指针
61、加1表示成in:=(in+1)modn;输出指针加1表示成out:=(out+1)modn。当(in+1)modn=out时表示缓冲池满;而in=out则表示缓冲池空。此外,还引入了一个整型变量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后,使counter加1;反之,每当消费者进程从中取走一个产品时,使counter减1。生产者和消费者两进程共享下面的变量:白呕龚慌畔秆裔换贴逞冈留甭爽庭蛇浦岂城茸神困母匪涩菊掖疤递后堪饰第二章进程管理第二章进程管理第二章进 程 管 理 Var n,integer;type item=;var buffer: array0,1,n-1 o
62、f item;in,out: 0,1,n-1;counter:0,1,n;矣纸瓷肪夹伊得娟范觅栓新奴淌舵吠辐庚霍酱咋沽洁疥煌吮甩祥唾巍替蹲第二章进程管理第二章进程管理第二章进 程 管 理 指针in和out初始化为1。在生产者和消费者进程的描述中,noop是一条空操作指令,whileconditiondono-op语句表示重复的测试条件(condication),重复测试应进行到该条件变为false(假),即到该条件不成立时为止。在生产者进程中使用一局部变量nextp,用于暂时存放每次刚生产出来的产品;而在消费者进程中,则使用一个局部变量nextc,用于存放每次要消费的产品。脚冻杜眉雍受阉绑嚣夺
63、薄檄凳贯道么赃谤沫弱着磺堪栈求龟铺趴洽层奠对第二章进程管理第二章进程管理第二章进 程 管 理 producer: repeat produce an item in nextp;while counter=n do no-op;bufferin:=nextp;in:=in+1 mod n;counter:=counter+1;untilfalse;咸筒璃据己梯膛忘柠锤淬墒碘拘出伪规腮羚乙咆陆昔谴哗钒琐哩鸭插甜破第二章进程管理第二章进程管理第二章进 程 管 理 consumer:repeatwhilecounter=0dono-op;nextc:=bufferout;out:=(out+1)mo
64、dn;counter:=counter-1;consumertheiteminnextc;untilfalse;囊傀坞盆醋脱箍朔串庚特美辉串爽朽抱系觅廖粕铂辐研琼芍茸琐宝硕伺猖第二章进程管理第二章进程管理第二章进 程 管 理 虽然上面的生产者程序和消费者程序在分别看时都是正确的,而且两者在顺序执行时其结果也会是正确的,但若并发执行时就会出现差错,问题就在于这两个进程共享变量counter。生产者对它做加1操作,消费者对它做减1操作,这两个操作在用机器语言实现时,常可用下面的形式描述:register1:=counter;register2:=counter;register1:=registe
65、r1+1;register2:=register2-1;counter:=register1;counter:=register2;违帽盘拖替粱怕睹腾鹏梅菜矿渡源携睛经吝汁铂音灯踞永抹驯囊驻限痪窍第二章进程管理第二章进程管理第二章进 程 管 理 假设counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句,然后消费者进程再执行右列的三条语句,则最后共享变量counter的值仍为5;反之,如果让消费者进程先执行右列的三条语句,然后再让生产者进程执行左列的三条语句,则counter值也还是5,但是,如果按下述顺序执行:蘸晕埃栅扇衙勘箭奈胖隋疾祁灯泳宴怕镇敏蓑劳辽经淀天淀希械皱圆右独第
66、二章进程管理第二章进程管理第二章进 程 管 理 register1:=counter;(register1=5)register1:=register1+1;(register1=6)register2:=counter;(register2=5)register2:=register2-1;(register2=4)counter:=register1;(counter=6)counter:=register2;(counter=4)迁眩故蜜羞兜霍讶士帅叮盅棋澡窒罪吉押棘腔家矮邑渊有闹血墩纯滦沛山第二章进程管理第二章进程管理第二章进 程 管 理 正确的counter值应当是5,但现在是4。读
67、者可以自己试试,倘若再将两段程序中各语句交叉执行的顺序改变,将可看到又可能得到counter=6的答案,这表明程序的执行已经失去了再现性。为了预防产生这种错误,解决此问题的关键是应把变量counter作为临界资源处理,亦即,令生产者进程和消费者进程互斥地访问变量counter。嘶圆敝丛推屋梆墅蓄姨着钡占洱狮椭毅磷隋笨葵咽窖藕恃算硬蓟贯规拉愚第二章进程管理第二章进程管理第二章进 程 管 理 3临界区临界区由前所述可知,不论是硬件临界资源,还是软件临界资源,多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(criticalsection)。显然,若能保证诸进程互斥
68、地进入自己的临界区,便可实现诸进程对临界资源的互斥访问。为此,每个进程在进入临界区之前,应先对欲访问的临界资源进行检查,看它是否正被访问。如果此刻该临界资源未被访问,进程便可进入临界区对该资源进行访问,并设置它正被访问的标志;如果此刻该临界资源正被某进程访问,则本进程不能进入临界区。因此,必须在临界区前面增加一段用于进行上述检查的代码,把这段代码称为进入区(entrysection)。相应地,在临界区后面也要加上一段称为退出区(exitsection)的代码,用于将临界区正被访问的标志恢复为未被访问的标志。什谓困酣嫌尝秦由腕籍郡蒜刊健媒怨潮席头屹冠粤唇梯许仔戌黑猫怨坦俏第二章进程管理第二章进程
69、管理第二章进 程 管 理 进程中除上述进入区、临界区及退出区之外的其它部分的代码,在这里都称为剩余区。这样,可把一个访问临界资源的循环进程描述如下:repeatentrysectioncriticalsection;exitsectionremaindersection;untilfalse;深掌箱诵变蚤绰迁裸粪寄晾圆兽钾育鄙袒窘雪次末盐卯灭校谗饭举泌菠肥第二章进程管理第二章进程管理第二章进 程 管 理 4同步机制应遵循的规则同步机制应遵循的规则为实现进程互斥地进入自已的临界区,可用软件方法,更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则:(1)空闲让
70、进。当无进程处于临界区时,表明临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区,以有效地利用临界资源。(2)忙则等待。当已有进程进入临界区时,表明临界资源正在被访问,因而其它试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。痒歪山坍耀蓬衣蒙搜短务垣核澡卸暴户瑚挽牟颠耳韭竣触栽义数宗敛岿架第二章进程管理第二章进程管理第二章进 程 管 理 (3)有限等待。对要求访问临界资源的进程,应保证在有限时间内能进入自己的临界区,以免陷入“死等”状态。(4)让权等待。当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”状态。程澎粗挑褒极它王蝉申嘉钢抗冤揪洗揭姻沿
71、栽剑鹏勒唬杂葱辉假果鲤哨拟第二章进程管理第二章进程管理第二章进 程 管 理 2.3.2信号量机制信号量机制1整型信号量整型信号量最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S,它与一般整型量不同,除初始化外,仅能通过两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。很长时间以来,这两个操作一直被分别称为P、V操作。Wait(S)和signal(S)操作可描述为:wait(S):while S=0dono-op;S:=S-1;signal(S):S:=S+1;番伟搭餐砖粱挚讹拄凤坊噪腹蓑阀藻娘嘶檄诈棉牟搐述姓溢棱啮更逐党祸第二章
72、进程管理第二章进程管理第二章进 程 管 理 wait(S)和signal(S)是两个原子操作,因此,它们在执行时是不可中断的。亦即,当一个进程在修改某信号量时,没有其他进程可同时对该信号量进行修改。此外,在wait操作中,对S值的测试和做S:=S-1操作时都不可中断。枫犀审憋知居武税乳曹矾柬诫差珐栈抠啄阂击膜峡禁滴宏鼓摧踏葵巷械鼠第二章进程管理第二章进程管理第二章进 程 管 理 2记录型信号量记录型信号量在整型信号量机制中的wait操作,只要是信号量S0,就会不断地测试。因此,该机制并未遵循“让权等待”的准则,而是使进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机
73、制。但在采取了“让权等待”的策略后,又会出现多个进程等待访问同一临界资源的情况。为此,在信号量机制中,除了需要一个用于代表资源数目的整型变量value外,还应增加一个进程链表指针L,用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为:锭栋探渊卯窗君妹守破抑跺欲谆褪唇况逗淆吸盈狱旁是蒙返矢必陨鸿稼渐第二章进程管理第二章进程管理第二章进 程 管 理 typesemaphore=recordvalue:integer;L:listofprocess;end表咸写凄炎拟瞬防甲芯乎涩幼韭烃屎酗斟纬腔已咯屠凿锅洛希袭掇欠汛诸第二章进程管理第二章
74、进程管理第二章进 程 管 理 相应地,wait(S)和signal(S)操作可描述为:procedurewait(S)varS:semaphore;beginS.value:=S.value-1;ifS.value0thenblock(S.L);endproceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value=0thenwakeup(S.L);end愿羽固篇紫骆脑吭瘦撮霹玛膘偏嚷凛耪段娄麻韭秃钎邵氦拼巢畸烯兴运密第二章进程管理第二章进程管理第二章进 程 管 理 在记录型信号量机制中,S.value的初值表示系统中某类资源
75、的数目,因而又称为资源信号量。对它的每次wait操作,意味着进程请求一个单位的该类资源,使系统中可供分配的该类资源数减少一个,因此描述为S.value:=S.value-1;当S.value=1andandSn=1thenfori:=1tondoSi:=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi=t1andandSn=tnthenfori:=1tondoSi:=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueue
76、ofthefirstSiwithSi1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时,允许多个进程进入某特定区;当S变为0后,将阻止任何进程进入特定区。换言之,它相当于一个可控开关。体们利付宣冒滨晴公侯砷绣番捎毒垛儿孽骇照岭拘崭馆豫玉瓶镍蚤辜竭蚕第二章进程管理第二章进程管理第二章进 程 管 理 2.3.3信号量的应用信号量的应用1利用信号量实现进程互斥利用信号量实现进程互斥为使多个进程能互斥地访问某临界资源,只须为该资源设置一互斥信号量mutex,并设其初始值为1,然后将各进程访问该资源的临界区CS置于wait(mutex)和sign
77、al(mutex)操作之间即可。这样,每个欲访问该临界资源的进程在进入临界区之前,都要先对mutex执行wait操作,若该资源此刻未被访问,本次wait操作必然成功,进程便可进入自己的临界区,这时若再有其他进程也欲进入自己的临界区,此时由于对mutex执行wait操作定会失败,因而该进程阻塞,从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后,又应对mutex执行signal操作,以便释放该临界资源。利用信号量实现进程互斥的进程可描述如下:徐砖酷掳朵匡谰哮狱色澜雕霖淄艳戈婉爽寒旱清孙锗呢纸缆冰蚕虱孰他夹第二章进程管理第二章进程管理第二章进 程 管 理 Varmutex:sem
78、aphore:=1;beginparbeginprocess1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remainderseetionuntilfalse;end内粗揉舒倘赔冉澡财庞柜完铣卢梦内啦嚼迄谆舍授滥勇铬探陵狠铱先冈憾第二章进程管理第二章进程管理第二章进 程 管 理 process2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;endparend憎蝗重腑婪哉腑科吉宰蔚粉葬路墩波寥涛程寇素映愉铃张传舌骡歪募贷烛
79、第二章进程管理第二章进程管理第二章进 程 管 理 2利用信号量实现前趋关系利用信号量实现前趋关系 还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程P1和P2。P1中有语句S1;P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系,我们只须使进程P1和P2共享一个公用信号量S,并赋予其初值为0,将signal(S)操作放在语句S1后面;而在S2语句前面插入wait(S)操作,即在进程P1中,用S1;signal(S);在进程P2中,用wait(S);S2;额店留金毯颖烬统规婚蔓凌症推诈腻娶饱沁鸡哺磕霞剧湛蹦蚀来棵星跌攒第二章进程管理第二章进程管理第二章进 程
80、管 理 由于S被初始化为0,这样,若P2先执行必定阻塞,只有在进程P1执行完S1;signal(S);操作后使S增为1时,P2进程方能执行语句S2成功。同样,我们可以利用信号量,按照语句间的前趋关系(见图2-12),写出一个更为复杂的可并发执行的程序。图2-12示出了一个前趋图,其中S1,S2,S3,S6是最简单的程序段(只有一条语句)。为使各程序段能正确执行,应设置若干个初始值为“0”的信号量。如为保证S1S2,S1S3的前趋关系,应分别设置信号量a和b,同样,为了保证S2S4,S2S5,S3S6,S4S6和S5S6,应设置信号量c,d,e,f,g。委瓶轴亲练檀匹诌漱论杯睬阮识阳袁捐绍停细掏
81、帐么衫堪委煤芹朝汰泵驮第二章进程管理第二章进程管理第二章进 程 管 理 Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parendend钾异
82、晾哲烦灾粉云房燕佃扫贰抛歼嘎团傣攫驭宫只劲劳箍帚纽勒臻热辛加第二章进程管理第二章进程管理第二章进 程 管 理 图2-12前趋图举例帚逆租拳彝择糯改瓶偏惟讶啮瘦时棘涵吨碰戳洼省柜涛抗盎俊候药辅锄免第二章进程管理第二章进程管理第二章进 程 管 理 2.3.4管程机制管程机制1管程的定义管程的定义系统中的各种硬件资源和软件资源,均可用数据结构抽象地描述其资源特性,即用少量信息和对该资源所执行的操作来表征该资源,而忽略了它们的内部结构和实现细节。例如,对一台电传机,可用与分配该资源有关的状态信息(busy或free)和对它执行请求与释放的操作,以及等待该资源的进程队列来描述。又如,一个FIFO队列,可
83、用其队长、队首和队尾以及在该队列上执行的一组操作来描述。滓鸯摹崩篱隆忻贪千烬萄朽滓肿赶后腥碱粉址慧婚惹沃蔡焰袄烟童漾彼戴第二章进程管理第二章进程管理第二章进 程 管 理 利用共享数据结构抽象地表示系统中的共享资源,而把对该共享数据结构实施的操作定义为一组过程,如资源的请求和释放过程request和release。进程对共享资源的申请、释放和其它操作,都是通过这组过程对共享数据结构的操作来实现的,这组过程还可以根据资源的情况,或接受或阻塞进程的访问,确保每次仅有一个进程使用共享资源,这样就可以统一管理对共享资源的所有访问,实现进程互斥。闹概掺做唱栓弗持掀蔫恃姨秋常息革哪梗改谋皿甚社光掣盾章湖替隙
84、喧定第二章进程管理第二章进程管理第二章进 程 管 理 代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序,共同构成了一个操作系统的资源管理模块,我们称之为管程。管程被请求和释放资源的进程所调用。Hansan为管程所下的定义是:“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据”。由上述的定义可知,管程由四部分组成:管程的名称;局部于管程内部的共享数据结构说明;对该数据结构进行操作的一组过程;对局部于管程内部的共享数据设置初始值的语句。图2-13是一个管程的示意图。择丘膝救恿洪欲叙扰沼抑援锤教腔疽淘
85、瓣镀预渔拓诚存赠扇佰估稚驮条掩第二章进程管理第二章进程管理第二章进 程 管 理 图2-13管程的示意图足部证舜明诗丫槽地戚戍浓监墟事箭原攘离误喝诈肢妮精拉匠证庚凹根怒第二章进程管理第二章进程管理第二章进 程 管 理 管程的语法描述如下:typemonitor_name=MONITOR;define;use;procedure();beginend;揉糕啼妨嗅慷吧创侗驹詹摄蹲词贤示屿没造蛰鸳歼绣瓣异丹驱啡毙沫氰屏第二章进程管理第二章进程管理第二章进 程 管 理 function():值类型;beginend;begin;end宝匠疹幻逛沈尹邮屏讫桔王颧骨豁卑柠设款靴蔫旭究脓醛歉纷扒际囚囚橙第二章
86、进程管理第二章进程管理第二章进 程 管 理 需要指出的是,局部于管程内部的数据结构,仅能被局部于管程内部的过程所访问,任何管程外的过程都不能访问它;反之,局部于管程内部的过程也仅能访问管程内的数据结构。由此可见,管程相当于围墙,它把共享变量和对它进行操作的若干过程围了起来,所有进程要访问临界资源时,都必须经过管程(相当于通过围墙的门)才能进入,而管程每次只准许一个进程进入管程,从而实现了进程互斥。管程是一种程序设计语言结构成分,它和信号量有同等的表达能力,从语言的角度看,管程主要有以下特性:释诀浆卞囊米恤萍陌铣闺著侄龙国纶四敷周拖别瓦慈巧蛹救呆敷纳肢拴谜第二章进程管理第二章进程管理第二章进 程
87、 管 理 (1)模块化。管程是一个基本程序单位,可以单独编译。(2)抽象数据类型。管程中不仅有数据,而且有对数据的操作。(3)信息掩蔽。管程中的数据结构只能被管程中的过程访问,这些过程也是在管程内部定义的,供管程外的进程调用,而管程中的数据结构以及过程(函数)的具体实现外部不可见。豺邮锑紧两杜苯延散铲扦撵方疽售轩静确女痛治阻屉汛壬逻罢祝京浩检胳第二章进程管理第二章进程管理第二章进 程 管 理 管程和进程不同,主要体现在以下几个方面:(1)虽然二者都定义了数据结构,但进程定义的是私有数据结构PCB,管程定义的是公共数据结构,如消息队列等;(2)二者都存在对各自数据结构上的操作,但进程是由顺序程序
88、执行有关的操作,而管程主要是进行同步操作和初始化操作;(3)设置进程的目的在于实现系统的并发性,而管程的设置则是解决共享资源的互斥使用问题;玫彬素跋或砖层称掳苑动噪分疑永园罕夹嘻蘑傈堪囚洲榜援狱衫桓尸讨鳃第二章进程管理第二章进程管理第二章进 程 管 理 (4)进程通过调用管程中的过程对共享数据结构实行操作,该过程就如通常的子程序一样被调用,因而管程为被动工作方式,进程则为主动工作方式;(5)进程之间能并发执行,而管程则不能与其调用者并发;(6)进程具有动态性,由“创建”而诞生,由“撤销”而消亡,而管程则是操作系统中的一个资源管理模块,供进程调用。猪洋恐裳述胁舞妇堑坤黎患琵感慌获旧歌勃核盖命短朴
89、甭男墩懦挠角经负第二章进程管理第二章进程管理第二章进 程 管 理 2条件变量条件变量在利用管程实现进程同步时,必须设置同步工具,如两个同步操作原语wait和signal。当某进程通过管程请求获得临界资源而未能满足时,管程便调用wait原语使该进程等待,并将其排在等待队列上,如图2-13所示。仅当另一进程访问完成并释放该资源之后,管程才又调用signal原语,唤醒等待队列中的队首进程。塞欣扑盒拯瑶豢掸类螟译隧印寡悟厂返静啥自常撇陀源亢纵始理骸猎告通第二章进程管理第二章进程管理第二章进 程 管 理 2条件变量条件变量在利用管程实现进程同步时,必须设置同步工具,如两个同步操作原语wait和signa
90、l。当某进程通过管程请求获得临界资源而未能满足时,管程便调用wait原语使该进程等待,并将其排在等待队列上,如图2-13所示。仅当另一进程访问完成并释放该资源之后,管程才又调用signal原语,唤醒等待队列中的队首进程。诣笑助帘琐扬寡陈长次仪栗性攒仙韭煌键婉故秧足轮晴炸卤裙柑谨谷膘抗第二章进程管理第二章进程管理第二章进 程 管 理 但是仅仅有上述的同步工具是不够的。考虑一种情况:当一个进程调用了管程,在管程中时被阻塞或挂起,直到阻塞或挂起的原因解除,而在此期间,如果该进程不释放管程,则其它进程无法进入管程,被迫长时间地等待。为了解决这个问题,引入了条件变量condition。通常,一个进程被阻
91、塞或挂起的条件(原因)可有多个,因此在管程中设置了多个条件变量,对这些条件变量的访问,只能在管程中进行。盼畦斧啥厢搔肋粮职蹄殖廷吼软阮郡龄更绊祈路均劝编漫麦翅悸卧穆妙赛第二章进程管理第二章进程管理第二章进 程 管 理 管程中对每个条件变量都须予以说明,其形式为:Varx,y:condition。对条件变量的操作仅仅是wait和signal,因此条件变量也是一种抽象数据类型,每个条件变量保存了一个链表,用于记录因该条件变量而阻塞的所有进程,同时提供的两个操作即可表示为x.wait和x.signal,其含义为:x.wait:正在调用管程的进程因x条件需要被阻塞或挂起,则调用x.wait将自己插入到
92、x条件的等待队列上,并释放管程,直到x条件变化。此时其它进程可以使用该管程。悔赦峦汞若哄嘘扩轩节狙甄鲤柑汲杰扰漱爬浮渭捍磷披登旁谩辱梭悔龟胰第二章进程管理第二章进程管理第二章进 程 管 理 x.signal:正在调用管程的进程发现x条件发生了变化,则调用x.signal,重新启动一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程,则选择其中的一个,如果没有,则继续执行原进程,而不产生任何结果。这与信号量机制中的signal操作不同,因为后者总是要执行s:=s+1操作,因而总会改变信号量的状态。如果有进程Q因x条件处于阻塞状态,当正在调用管程的进程P执行了x.signal操作后,进程Q被重新
93、启动,此时两个进程P和Q,如何确定哪个执行,哪个等待,可采用下述两种方式之一进行处理:(1)P等待,直至Q离开管程或等待另一条件。(2)Q等待,直至P离开管程或等待另一条件。欺瓷登仆屠咬哄拣几剪申第硝嫁操吸琉熟陋彦舀携涤您剖箕蔓伍孪啥出垃第二章进程管理第二章进程管理第二章进 程 管 理 采用哪种处理方式,当然是各执一词。Hoare采用了第一种处理方式,而Hansan选择了两者的折衷,他规定管程中的过程所执行的signal操作是过程体的最后一个操作,于是,进程P执行signal操作后立即退出管程,因而进程Q马上被恢复执行。囚善惭康蕾敝筑赂棵弛艰耐臭近纶声殊乒元鹰钵球沾贤捌唁徐许堪讲菲坞第二章进程
94、管理第二章进程管理第二章进 程 管 理 2.4经典进程的同步问题经典进程的同步问题 2.4.1生产者生产者消费者问题消费者问题1利用记录型信号量解决生产者利用记录型信号量解决生产者消费者问题消费者问题假定在生产者和消费者之间的公用缓冲池中,具有n个缓冲区,这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效,只要缓冲池未满,生产者便可将消息送入缓冲池;只要缓冲池未空,消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下:蜘院来郊盲品遁朋绸枝削凋予渔香疫茧责灰岔苍龟拐慑人忱裸
95、挨证窟节年第二章进程管理第二章进程管理第二章进 程 管 理 Varmutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1ofitem;in,out:integer:=0,0;beginparbeginproceducer:beginrepeatproduceranitemnextp;wait(empty);孵漳歪钦挟岸肆瓤疮纯扔纲向庸的檬碧攘珊佐佑啪剃沮捆撇貌遁死球芯廊第二章进程管理第二章进程管理第二章进 程 管 理 wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal
96、(full);untilfalse;endconsumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);收返秃孙恫哩磅印暮穴屑振畸始爽嫡椽虱钱爷惧熬桐呻霖疽美让壤贞绕丹第二章进程管理第二章进程管理第二章进 程 管 理 out:=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endparendend掺嘱硅烂泪桐很闯襟要钨酬眉母俯披驱吼靛培二奠妊除稿洛钮凰胁历贡毒第二章进程管理第二章进程管理第二章进 程 管 理 在生产者消费者问题中应注
97、意:首先,在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现;其次,对资源信号量empty和full的wait和signal操作,同样需要成对地出现,但它们分别处于不同的程序中。例如,wait(empty)在计算进程中,而signal(empty)则在打印进程中,计算进程若因执行wait(empty)而阻塞,则以后将由打印进程将它唤醒;最后,在每个程序中的多个wait操作顺序不能颠倒,应先执行对资源信号量的wait操作,然后再执行对互斥信号量的wait操作,否则可能引起进程死锁。甸募炕藏讲砧潞洱吩蔽身烙天柄钾窿秧署办腮蜀懒囱籽吧吴掂丝军侵含绘第二章进程管
98、理第二章进程管理第二章进 程 管 理 2利用利用AND信号量解决生产者信号量解决生产者消费者问题消费者问题对于生产者消费者问题,也可利用AND信号量来解决,即用Swait(empty,mutex)来代替wait(empty)和wait(mutex);用Ssignal(mutex,full)来代替signal(mutex)和signal(full);用Swait(full, mutex)来 代 替 wait(full)和 wait(mutex), 以 及 用Ssignal(mutex,empty)代替Signal(mutex)和Signal(empty)。利用AND信号量来解决生产者消费者问题的
99、算法描述如下:硒者瓤制诈虚困辣形蒸焰野道盲袱嗽沁遣强蔗旅违姻曰魄烷纺寓宠呕养扶第二章进程管理第二章进程管理第二章进 程 管 理 Varmutex,empty,full:semaphore:=1,n,0;buffer:array0,n-1ofitem;inout:integer:=0,0;beginparbeginproducer:beginrepeatproduceaniteminnextp;Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;Ssignal(mutex,full);untilfalse;end拦锋露切聘撂组嫉来渺祸敬沃达限岩
100、佛少捅锌蟹给帐惫驴臆聊认育遵寸条第二章进程管理第二章进程管理第二章进 程 管 理 consumer:beginrepeatSwait(full,mutex);Nextc:=buffer(out);Out:=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;untilfalse;endparendend丽划封枚堪抓松壕硼咎系踌腑嚏扶抚木扭鄂宠衍够恐咸锑竞扛床淹豫租蔽第二章进程管理第二章进程管理第二章进 程 管 理 3利用管程解决生产者利用管程解决生产者消费者问题消费者问题在利用管程方法来解决生产者消费者问题时,首先便是为它们建立一个管
101、程,并命名为ProclucerConsumer,或简称为PC。其中包括两个过程:(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中,并用整型变量count来表示在缓冲池中已有的产品数目,当countn时,表示缓冲池已满,生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品,当count0时,表示缓冲池中已无可取用的产品,消费者应等待。主排拥递钨莎诅擂礁毖砒撕妨羔驻为晴酵鼻菩配年甥袱补替萄眨构吩疤叔第二章进程管理第二章进程管理第二章进 程 管 理 PC管程可描述如下:typeproducer-consumer=monitorVarin,ou
102、t,count:integer;buffer:array0,n-1ofitem;notfull,notempty:condition;procedureentryput(item)beginifcount=nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;end岩贫蛮洒艘钻刘煞蛋射迹咖芯闺涪莽碴知奎谦孰膊奴抢塞鲤样漓迪喇添踢第二章进程管理第二章进程管理第二章进 程 管 理 procedureentryget(item)beginifcount
103、2)结点(进程)。租怒咐愈昆亢分呐筛谴试傈息党浪斤倔吻块襄翠潍竣莱览贱吨檬贾匠封批第二章进程管理第二章进程管理第二章进 程 管 理 而根据通信方式的不同,则又可把链路分成两种:(1)单向通信链路,只允许发送进程向接收进程发送消息,或者相反;还可根据通信链路容量的不同而把链路分成两类:一是无容量通信链路,在这种通信链路上没有缓冲区,因而不能暂存任何消息;再者就是有容量通信链路,指在通信链路中设置了缓冲区,因而能暂存消息。缓冲区数目愈多,通信链路的容量愈大。苏跃歇膀买锄暇顷腮烯灯孰烤踌磷湃奉李穿拷际媒糜省子歉允薪营招按留第二章进程管理第二章进程管理第二章进 程 管 理 2消息的格式消息的格式在消息
104、传递系统中所传递的消息,必须具有一定的消息格式。在单机系统环境中,由于发送进程和接收进程处于同一台机器中,有着相同的环境,故其消息格式比较简单;但在计算机网络环境下,不仅源和目标进程所处的环境不同,而且信息的传输距离很远,可能要跨越若干个完全不同的网络,致使所用的消息格式比较复杂。通常,可把一个消息分成消息头和消息正文两部分。消息头包括消息在传输时所需的控制信息,如源进程名、目标进程名、消息长度、消息类型、消息编号及发送的日期和时间;而消息正文则是发送进程实际上所发送的数据。洁晰澡室莆毋月拣嫂序坠逆矮铡扼猾百诅箱车鸳巳湿吭熄吟恐鹰盯侦艳踞第二章进程管理第二章进程管理第二章进 程 管 理 在某些
105、OS中,消息采用比较短的定长消息格式,这便减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中,为用户提供快速的便笺式通信;但这对要发送较长消息的用户是不方便的。在有的OS中,采用变长的消息格式,即进程所发送消息的长度是可变的。系统无论在处理还是在存储变长消息时,都可能会付出更多的开销,但这方便了用户。这两种消息格式各有其优缺点,故在很多系统(包括计算机网络)中,是同时都用的。忿司疽缠渍著迁谗膛辅澳躺跳辱霞扛獭耿括豆傍针塞漏铡乘良薯展仁越碘第二章进程管理第二章进程管理第二章进 程 管 理 3进程同步方式进程同步方式在进程之间进行通信时,同样需要有进程同步机制,以使诸进程间能协调通信。不
106、论是发送进程,还是接收进程,在完成消息的发送或接收后,都存在两种可能性,即进程或者继续发送(接收),或者阻塞。由此,我们可得到以下三种情况:(1)发送进程阻塞,接收进程阻塞。这种情况主要用于进程之间紧密同步(tightsynchronization),发送进程和接收进程之间无缓冲时。这两个进程平时都处于阻塞状态,直到有消息传递时。这种同步方式称为汇合(rendezrous)。镐关薛妮耕博瞒墟乱虚给星饺伯洛俱隙酋万刽檬雇棺劲硫帜媚煤皂喝茁肺第二章进程管理第二章进程管理第二章进 程 管 理 (2)发送进程不阻塞,接收进程阻塞。这是一种应用最广的进程同步方式。平时,发送进程不阻塞,因而它可以尽快地把
107、一个或多个消息发送给多个目标;而接收进程平时则处于阻塞状态,直到发送进程发来消息时才被唤醒。例如,在服务器上通常都设置了多个服务进程,它们分别用于提供不同的服务,如打印服务。平时,这些服务进程都处于阻塞状态,一旦有请求服务的消息到达时,系统便唤醒相应的服务进程,去完成用户所要求的服务。处理完后,若无新的服务请求,服务进程又阻塞。锹级进百击婚死疯拨藤锡盖途昨阮垣鸿域涵诵颐持充侵上绝首腾钓芒诈资第二章进程管理第二章进程管理第二章进 程 管 理 (3)发送进程和接收进程均不阻塞。这也是一种较常见的进程同步形式。平时,发送进程和接收进程都在忙于自己的事情,仅当发生某事件使它无法继续运行时,才把自己阻塞
108、起来等待。例如,在发送进程和接收进程之间联系着一个消息队列时,该消息队列最多能接纳n个消息,这样,发送进程便可以连续地向消息队列中发送消息而不必等待;接收进程也可以连续地从消息队列中取得消息,也不必等待。只有当消息队列中的消息数已达到n个时,即消息队列已满,发送进程无法向消息队列中发送消息时才会阻塞;类似地,只有当消息队列中的消息数为0,接收进程已无法从消息队列中取得消息时才会阻塞。氨镍戮明境团愚迹腿猾慢玲惫吐枢崎扣砌篙纯笆铺牙涛翘谎畜埃晚映黔衡第二章进程管理第二章进程管理第二章进 程 管 理 2.5.4消息缓冲队列通信机制消息缓冲队列通信机制1)消息缓冲区在消息缓冲队列通信方式中,主要利用的
109、数据结构是消息缓冲区。它可描述如下:typemessagebuffer=recordsender;发送者进程标识符size;消息长度text;消息正文next;指向下一个消息缓冲区的指针end牲昂辞些见矗傈毅欧喜骏中妊放王腕厄疡际勘什佛吸如殖世京钾靶首谷饺第二章进程管理第二章进程管理第二章进 程 管 理 2)PCB中有关通信的数据项在操作系统中采用了消息缓冲队列通信机制时,除了需要为进程设置消息缓冲队列外,还应在进程的PCB中增加消息队列队首指针,用于对消息队列进行操作,以及用于实现同步的互斥信号量mutex和资源信号量sm。在PCB中应增加的数据项可描述如下:付艺叠揩屹糯耀娃匀猎呵抹聘杨享斩
110、验捎触赛杏苗篇亡巍熟诅俄剃磅嫡渐第二章进程管理第二章进程管理第二章进 程 管 理 typeprocesscontrolblock=recordmq;消息队列队首指针mutex;消息队列互斥信号量sm;消息队列资源信号量end式鲸麓膨刑豌澡盘涅碴淡攻阮锌便懈甘掣娃琳码仔蔡愈河看脑杂部螺康勋第二章进程管理第二章进程管理第二章进 程 管 理 2发送原语发送原语发送进程在利用发送原语发送消息之前,应先在自己的内存空间设置一发送区a,见图2-14所示。把待发送的消息正文、发送进程标识符、消息长度等信息填入其中,然后调用发送原语,把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.
111、size来申请一缓冲区i,接着把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上,应先获得接收进程的内部标识符j,然后将i挂在j.mq上。由于该队列属于临界资源,故在执行insert操作的前后,都要执行wait和signal操作。上梦撕婉男剂典桩镇残价瓦旁非逢陡煮诱制糊幸塔刚苛娇萄悼孝物窄晨隋第二章进程管理第二章进程管理第二章进 程 管 理 发送原语可描述如下:proceduresend(receiver,a)begingetbuf(a.size,i);根据a.size申请缓冲区;i.sender:=a.sender;将发送区a中的信息复制到消息缓冲区i中;i.size
112、:=a.size;i.text:=a.text;i.next:=0;getid(PCBset,receiver.j);获得接收进程内部标识符;wait(j.mutex);insert(j.mq,i);将消息缓冲区插入消息队列;signal(j.mutex);signal(j.sm);end涧竞猩酚迁岁真咙雕柴草齿豺鞋颅酝邀十翻孽当鸳散场奎状侯梳皱氟搔程第二章进程管理第二章进程管理第二章进 程 管 理 图2-14消息缓冲通信兜整辰息奖条停唉想臀滇福键短罩骇乘郧抄炸伏莹磋柱坍讹钾纪遵诗悼抽第二章进程管理第二章进程管理第二章进 程 管 理 3接收原语接收原语接收进程调用接收原语receive(b),
113、从自己的消息缓冲队列mq中摘下第一个消息缓冲区i,并将其中的数据复制到以b为首址的指定消息接收区内。接收原语描述如下:赞谢蹿州疫及挟栽岸坞可涡瞪辣庙逐垣端轴些兑洲化蜀转出苹课咏碘鸽顶第二章进程管理第二章进程管理第二章进 程 管 理 procedurereceive(b)beginj:=internalname;j为接收进程内部的标识符;wait(j.sm);wait(j.mutex);remove(j.mq,i);将消息队列中第一个消息移出;signal(j.mutex);b.sender:=i.sender;将消息缓冲区i中的信息复制到接收区b;b.size:=i.size;b.text:=
114、i.text;end烫衡资强肋神陋更卧访胎慧歪妻努用决疹狱友拈孽裳办潮辙褥竭份旨曾虾第二章进程管理第二章进程管理第二章进 程 管 理 2.6线程线程 2.6.1线程的基本概念线程的基本概念1线程的引入线程的引入如果说,在操作系统中引入进程的目的,是为了使多个程序能并发执行,以提高资源利用率和系统吞吐量,那么,在操作系统中再引入线程,则是为了减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性。为了说明这一点,我们首先来回顾进程的两个基本属性:进程是一个可拥有资源的独立单位;进程同时又是一个可独立调度和分派的基本单位。正是由于进程有这两个基本属性,才使之成为一个能独立运行的基本单位,从而
115、也就构成了进程并发执行的基础。然而,为使程序能并发执行,系统还必须进行以下的一系列操作。瞎迷镀畴蔬寅拍执淑锹返沃腔煞渍茸椎磁巴舍钞佐张挫疏砂旧持螟煮宛烯第二章进程管理第二章进程管理第二章进 程 管 理 1)创建进程系统在创建一个进程时,必须为它分配其所必需的、除处理机以外的所有资源,如内存空间、I/O设备,以及建立相应的PCB。2)撤消进程系统在撤消进程时,又必须先对其所占有的资源执行回收操作,然后再撤消PCB。埠挚鹤烦歹亥鬼炔讹品质赣翟萤拈崭觉舆漓农粕蔡钉洁缄迢涸帝采蜂霜死第二章进程管理第二章进程管理第二章进 程 管 理 3)进程切换对进程进行切换时,由于要保留当前进程的CPU环境和设置新选
116、中进程的CPU环境,因而须花费不少的处理机时间。换言之,由于进程是一个资源的拥有者,因而在创建、撤消和切换中,系统必须为之付出较大的时空开销。正因如此,在系统中所设置的进程,其数目不宜过多,进程切换的频率也不宜过高,这也就限制了并发程度的进一步提高。郑肆怔下煌室胯开傅武玻朱胃三阮劳湾铆烬吐懊入迂辜钵猛近基蝉轻诫吞第二章进程管理第二章进程管理第二章进 程 管 理 如何能使多个程序更好地并发执行同时又尽量减少系统的开销,已成为近年来设计操作系统时所追求的重要目标。有不少研究操作系统的学者们想到,若能将进程的上述两个属性分开,由操作系统分开处理,亦即对于作为调度和分派的基本单位,不同时作为拥有资源的
117、单位,以做到“轻装上阵”;而对于拥有资源的基本单位,又不对之进行频繁的切换。正是在这种思想的指导下,形成了线程的概念。渤限悍畏萌提辣员翱赵靳佃抡呈昆暗僧歪献膘脊昨贺朋着盛也惮播搞犊焉第二章进程管理第二章进程管理第二章进 程 管 理 2线程与进程的比较线程与进程的比较1)调度在传统的操作系统中,作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中,则把线程作为调度和分派的基本单位,而进程作为资源拥有的基本单位,把传统进程的两个属性分开,使线程基本上不拥有资源,这样线程便能轻装前进,从而可显著地提高系统的并发程度。在同一进程中,线程的切换不会引起进程的切换,但从一个进
118、程中的线程切换到另一个进程中的线程时,将会引起进程的切换。啃补炼可滑恭斩抿钡漫傀舅百社靠升琳溺藕羚狈湾乍奉爬所绎逼蒂吼熔阐第二章进程管理第二章进程管理第二章进 程 管 理 2)并发性在引入线程的操作系统中,不仅进程之间可以并发执行,而且在一个进程中的多个线程之间亦可并发执行,使得操作系统具有更好的并发性,从而能更加有效地提高系统资源的利用率和系统的吞吐量。例如,在一个未引入线程的单CPU操作系统中,若仅设置一个文件服务进程,当该进程由于某种原因而被阻塞时,便没有其它的文件服务进程来提供服务。在引入线程的操作系统中,则可以在一个文件服务进程中设置多个服务线程。当第一个线程等待时,文件服务进程中的
119、第二个线程可以继续运行,以提供文件服务;当第二个线程阻塞时,则可由第三个继续执行,提供服务。显然,这样的方法可以显著地提高文件服务的质量和系统的吞吐量。霉膳替借箱之痕涅领袱摄簇墨萨白登疯亨离挫蚌懂阴狄尘离愧奸郸屹登痛第二章进程管理第二章进程管理第二章进 程 管 理 3)拥有资源不论是传统的操作系统,还是引入了线程的操作系统,进程都可以拥有资源,是系统中拥有资源的一个基本单位。一般而言,线程自己不拥有系统资源(也有一点必不可少的资源),但它可以访问其隶属进程的资源,即一个进程的代码段、数据段及所拥有的系统资源,如已打开的文件、I/O设备等,可以供该进程中的所有线程所共享。浦中匡妮饲辨劈腾专雁堵庄
120、镣琶孕寿耳墙哲蹈祥尝自拱礁去匹贝请蝉集滩第二章进程管理第二章进程管理第二章进 程 管 理 4)系统开销在创建或撤消进程时,系统都要为之创建和回收进程控制块,分配或回收资源,如内存空间和I/O设备等,操作系统所付出的开销明显大于线程创建或撤消时的开销。类似地,在进程切换时,涉及到当前进程CPU环境的保存及新被调度运行进程的CPU环境的设置,而线程的切换则仅需保存和设置少量寄存器内容,不涉及存储器管理方面的操作,所以就切换代价而言,进程也是远高于线程的。此外,由于一个进程中的多个线程具有相同的地址空间,在同步和通信的实现方面线程也比进程容易。在一些操作系统中,线程的切换、同步和通信都无须操作系统内
121、核的干预。蜕曝咳肆肇云狐夫鼓边于爆悦彤欠蛰馋涸拜析苹待弟仲炔束触棘浪剩擞吴第二章进程管理第二章进程管理第二章进 程 管 理 3线程的属性线程的属性在多线程OS中,通常是在一个进程中包括多个线程,每个线程都是作为利用CPU的基本单位,是花费最小开销的实体。线程具有下述属性。(1)轻型实体。线程中的实体基本上不拥有系统资源,只是有一点必不可少的、能保证其独立运行的资源,比如,在每个线程中都应具有一个用于控制线程运行的线程控制块TCB,用于指示被执行指令序列的程序计数器,保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。珊搅誊屹拳迟磨谆垃牌洽拧钳翟租袱那今毁狱鸡键帚嚷履戎琢篡土驼镁审第二章进
122、程管理第二章进程管理第二章进 程 管 理 (2)独立调度和分派的基本单位。在多线程OS中,线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位。由于线程很“轻”,故线程的切换非常迅速且开销小。(3)可并发执行。在一个进程中的多个线程之间可以并发执行,甚至允许在一个进程中的所有线程都能并发执行;同样,不同进程中的线程也能并发执行。(4)共享进程资源。在同一进程中的各个线程都可以共享该进程所拥有的资源,这首先表现在所有线程都具有相同的地址空间(进程的地址空间)。这意味着线程可以访问该地址空间中的每一个虚地址;此外,还可以访问进程所拥有的已打开文件、定时器、信号量机构等。驭畅汰绊怪骋陶滨烹迟
123、递悲诲殆依摸潦蝉妊世倦缴回圆获扳梗位谤宵哀瞩第二章进程管理第二章进程管理第二章进 程 管 理 4线程的状态线程的状态(1)状态参数。在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项:寄存器状态,它包括程序计数器PC和堆栈指针中的内容;堆栈,在堆栈中通常保存有局部变量和返回地址;线程运行状态,用于描述线程正处于何种运行状态;优先级,描述线程执行的优先程度;线程专有存储器,用于保存线程自己的局部变量拷贝;信号屏蔽,即对某些信号加以屏蔽。畅澈卯虎电估稼毅绪伞茧吻岁余锑技咽境幂睡啤盼先制博丢聋羌监卿黑惶第二章进程管理第二章进程管理第二章进 程 管 理 (2)线程运
124、行状态。如同传统的进程一样,在各线程之间也存在着共享资源和相互合作的制约关系,致使线程在运行时也具有间断性。相应地,线程在运行时也具有下述三种基本状态:执行状态,表示线程正获得处理机而运行;就绪状态,指线程已具备了各种执行条件,一旦获得CPU便可执行的状态;阻塞状态,指线程在执行中因某事件而受阻,处于暂停执行时的状态。龙皿亨副刮辆够珊形擒拇殷姚翌阐愈台鳖摘灯育寅藕菠簿蚤斑辗篡俺信垂第二章进程管理第二章进程管理第二章进 程 管 理 5线程的创建和终止线程的创建和终止在多线程OS环境下,应用程序在启动时,通常仅有一个线程在执行,该线程被人们称为“初始化线程”。它可根据需要再去创建若干个线程。在创建
125、新线程时,需要利用一个线程创建函数(或系统调用),并提供相应的参数,如指向线程主程序的入口指针、堆栈的大小,以及用于调度的优先级等。在线程创建函数执行完后,将返回一个线程标识符供以后使用。峭券轨姐酱陀锦截帮午铂榨奠徒躇窍淤茎术细殖另郧映喝更嚷竿耪笆菠善第二章进程管理第二章进程管理第二章进 程 管 理 如同进程一样,线程也是具有生命期的。终止线程的方式有两种:一种是在线程完成了自己的工作后自愿退出;另一种是线程在运行中出现错误或由于某种原因而被其它线程强行终止。但有些线程(主要是系统线程),在它们一旦被建立起来之后,便一直运行下去而不再被终止。在大多数的OS中,线程被中止后并不立即释放它所占有的
126、资源,只有当进程中的其它线程执行了分离函数后,被终止的线程才与资源分离,此时的资源才能被其它线程利用。雀舒偶摘毖橡爽典砸鞭挖乙眶莫伊幅皮愤伟庶锚摘泼锨澜庞包省楷睫项贯第二章进程管理第二章进程管理第二章进 程 管 理 虽已被终止但尚未释放资源的线程,仍可以被需要它的线程所调用,以使被终止线程重新恢复运行。为此,调用者线程须调用一条被称为“等待线程终止”的连接命令,来与该线程进行连接。如果在一个调用者线程调用“等待线程终止”的连接命令试图与指定线程相连接时,若指定线程尚未被终止,则调用连接命令的线程将会阻塞,直至指定线程被终止后才能实现它与调用者线程的连接并继续执行;若指定线程已被终止,则调用者线
127、程不会被阻塞而是继续执行。金晦胀宙应遁书郑穿酥熊肇砍惠玄粪腋五超铭届戍小节毒赔颠逾葬烘肪贼第二章进程管理第二章进程管理第二章进 程 管 理 6多线程多线程OS中的进程中的进程在多线程OS中,进程是作为拥有系统资源的基本单位,通常的进程都包含多个线程并为它们提供资源,但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性:(1)作为系统资源分配的单位。在多线程OS中,仍是将进程作为系统资源分配的基本单位,在任一进程中所拥有的资源包括受到分别保护的用户地址空间、用于实现进程间和线程间同步和通信的机制、已打开的文件和已申请到的I/O设备,以及一张由核心进程维护的地址映射表,该表用于实现用
128、户程序的逻辑地址到其内存物理地址的映射。椅先状正儒羹座闻疫孪料懦晶雅溢韦雨怖个鳃菊城馏迢泽右讶聊兆摈吭瘩第二章进程管理第二章进程管理第二章进 程 管 理 (2)可包括多个线程。通常,一个进程都含有多个相对独立的线程,其数目可多可少,但至少也要有一个线程,由进程为这些(个)线程提供资源及运行环境,使这些线程可并发执行。在OS中的所有线程都只能属于某一个特定进程。(3)进程不是一个可执行的实体。在多线程OS中,是把线程作为独立运行的基本单位,所以此时的进程已不再是一个可执行的实体。虽然如此,进程仍具有与执行相关的状态。例如,所谓进程处于“执行”状态,实际上是指该进程中的某线程正在执行。此外,对进程
129、所施加的与进程状态有关的操作,也对其线程起作用。例如,在把某个进程挂起时,该进程中的所有线程也都将被挂起;又如,在把某进程激活时,属于该进程的所有线程也都将被激活。妆闯帐儿惨掉垃蜗诀谬叶诽结寇意祁炼凉我姿跳戮辉诸言铺抄足宗曳币陈第二章进程管理第二章进程管理第二章进 程 管 理 2.6.2线程间的同步和通信线程间的同步和通信1互斥锁互斥锁(mutex)互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制。由于操作互斥锁的时间和空间开销都较低,因而较适合于高频度使用的关键共享数据和程序段。互斥锁可以有两种状态,即开锁(unlock)和关锁(lock)状态。相应地,可用两条命令(函数)对互斥锁
130、进行操作。其中的关锁lock操作用于将mutex关上,开锁操作unlock则用于打开mutex。纸敛讼皖政葫悟鹅讨锌穿徒灌含舒敛耀君畴蠢墟抹窑撰氓奈丸贵飘闸冠洞第二章进程管理第二章进程管理第二章进 程 管 理 当一个线程需要读/写一个共享数据段时,线程首先应为该数据段所设置的mutex执行关锁命令。命令首先判别mutex的状态,如果它已处于关锁状态,则试图访问该数据段的线程将被阻塞;而如果mutex是处于开锁状态,则将mutex关上后便去读/写该数据段。在线程完成对数据的读/写后,必须再发出开锁命令将mutex打开,同时还须将阻塞在该互斥锁上的一个线程唤醒,其它的线程仍被阻塞在等待mutex打
131、开的队列上。另外,为了减少线程被阻塞的机会,在有的系统中还提供了一种用于mutex上的操作命令Trylock。当一个线程在利用Trylock命令去访问mutex时,若mutex处于开锁状态,Trylock将返回一个指示成功的状态码;反之,若mutex处于关锁状态,则Trylock并不会阻塞该线程,而只是返回一个指示操作失败的状态码。屁齿牟跳撂媚七脸水邵根陋油龙血吹蔷碾樟燃矩惫厚减替建钟棕叁韦午忱第二章进程管理第二章进程管理第二章进 程 管 理 2条件变量条件变量在许多情况下,只利用mutex来实现互斥访问可能会引起死锁,我们通过一个例子来说明这一点。有一个线程在对mutex1执行关锁操作成功后
132、,便进入一临界区C,若在临界区内该线程又须访问某个临界资源R,同样也为R设置另一互斥锁mutex2。假如资源R此时正处于忙碌状态,线程在对mutex2执行关锁操作后必将被阻塞,这样将使mutex1一直保持关锁状态;如果保持了资源R的线程也要求进入临界区C,但由于mutex1一直保持关锁状态而无法进入临界区,这样便形成了死锁。为了解决这个问题便引入了条件变量。交细遁豪帕痕猿眩兑公危亥紧耳钦炮你札播挺摸袍好倘舵叶命瓶辨蘸媒吸第二章进程管理第二章进程管理第二章进 程 管 理 每一个条件变量通常都与一个互斥锁一起使用,亦即,在创建一个互斥锁时便联系着一个条件变量。单纯的互斥锁用于短期锁定,主要是用来保
133、证对临界区的互斥进入。而条件变量则用于线程的长期等待,直至所等待的资源成为可用的资源。现在,我们看看如何利用互斥锁和条件变量来实现对资源R的访问。线程首先对mutex执行关锁操作,若成功便进入临界区,然后查找用于描述该资源状态的数据结构,以了解资源的情况。只要发现所需资源R正处于忙碌状态,线程便转为等待状态,并对mutex执行开锁操作后,等待该资源被释放;若资源处于空闲状态,表明线程可以使用该资源,于是将该资源设置为忙碌状态,再对mutex执行开锁操作。下面给出了对上述资源的申请(左半部分)和释放(右半部分)操作的描述。羞闯获脂喜砷蜜消剁巷司丛地志刺潜怪汹阂到湘辆诫哑蛀存镊幌普测暂袄第二章进程
134、管理第二章进程管理第二章进 程 管 理 Lockmutex Lockmutexcheckdatastructures;markresourceasfree;while(resourcebusy);unlockmutex;wait(conditionvariable);wakeup(conditionvariable);markresourceasbusy;unlockmutex;人坯斜梯任产与妨握警攫士豢测率拉酮条瑚顷禾丹依如俱樟火卒洗晌础钒第二章进程管理第二章进程管理第二章进 程 管 理 原来占有资源R的线程在使用完该资源后,便按照右半部分的描述释放该资源,其中的wakeup(conditi
135、onvariable)表示去唤醒在指定条件变量上等待的一个或多个线程。在大多数情况下,由于所释放的是临界资源,此时所唤醒的只能是在条件变量上等待的某一个线程,其它线程仍继续在该队列上等待。但如果线程所释放的是一个数据文件,该文件允许多个线程同时对它执行读操作。在这种情况下,当一个写线程完成写操作并释放该文件后,如果此时在该条件变量上还有多个读线程在等待,则该线程可以唤醒所有的等待线程。橱鸽辰筹肿郁疼蛮探界摩阳代触华使畸柱搭失泉夸蜘卑歪晤噬盛晨十伐乞第二章进程管理第二章进程管理第二章进 程 管 理 3信号量机制信号量机制1)私用信号量(privatesamephore)当某线程需利用信号量来实现
136、同一进程中各线程之间的同步时,可调用创建信号量的命令来创建一私用信号量,其数据结构存放在应用程序的地址空间中。私用信号量属于特定的进程所有,OS并不知道私用信号量的存在,因此,一旦发生私用信号量的占用者异常结束或正常结束,但并未释放该信号量所占有空间的情况时,系统将无法使它恢复为0(空),也不能将它传送给下一个请求它的线程。攒辱室恤珊登谁眨赠回斤丘鉴异堆抑蒲峡禄玫殷菲几靳寇垢嘻浓辫伶剩同第二章进程管理第二章进程管理第二章进 程 管 理 2)公用信号量(publicsemaphort)公用信号量是为实现不同进程间或不同进程中各线程之间的同步而设置的。由于它有着一个公开的名字供所有的进程使用,故而
137、把它称为公用信号量。其数据结构是存放在受保护的系统存储区中,由OS为它分配空间并进行管理,故也称为系统信号量。如果信号量的占有者在结束时未释放该公用信号量,则OS会自动将该信号量空间回收,并通知下一进程。可见,公用信号量是一种比较安全的同步机制。空爷节欺篓褪沙纽泅姥卉胸奏汇谚硼掸扮坎乳弛相供溜概佃榷谚凸钝捡镶第二章进程管理第二章进程管理第二章进 程 管 理 2.6.3线程的实现方式线程的实现方式1内核支持线程内核支持线程对于通常的进程,无论是系统进程还是用户进程,进程的创建、撤消,以及要求由系统设备完成的I/O操作,都是利用系统调用而进入内核,再由内核中的相应处理程序予以完成的。进程的切换同样
138、是在内核的支持下实现的。因此我们说,不论什么进程,它们都是在操作系统内核的支持下运行的,是与内核紧密相关的。朋甲冯是驾拎询觉凰盟入棍狗碍褒露些德橡缮玩蔓习兆院津玖虫赡菌弦烤第二章进程管理第二章进程管理第二章进 程 管 理 这里所谓的内核支持线程KST(KernelSupportedThreads),也都同样是在内核的支持下运行的,即无论是用户进程中的线程,还是系统进程中的线程,他们的创建、撤消和切换等也是依靠内核,在内核空间实现的。此外,在内核空间还为每一个内核支持线程设置了一个线程控制块,内核是根据该控制块而感知某线程的存在,并对其加以控制。这种线程实现方式主要有如下四个优点:(1)在多处理
139、器系统中,内核能够同时调度同一进程中多个线程并行执行;反溢啊瓷笑腆胶掸际规韶椅捌糖免纱疆献急契饿步却滥夯衫晦守侥唾烩斋第二章进程管理第二章进程管理第二章进 程 管 理 (2)如果进程中的一个线程被阻塞了,内核可以调度该进程中的其它线程占有处理器运行,也可以运行其它进程中的线程;(3)内核支持线程具有很小的数据结构和堆栈,线程的切换比较快,切换开销小;(4)内核本身也可以采用多线程技术,可以提高系统的执行速度和效率。内核支持线程的主要缺点是:对于用户的线程切换而言,其模式切换的开销较大,在同一个进程中,从一个线程切换到另一个线程时,需要从用户态转到内核态进行,这是因为用户进程的线程在用户态运行,
140、而线程调度和管理是在内核实现的,系统开销较大。姥挪迷苇伊奇耪异拙兜簿葬贸锅聋翘柞营实逾南蛮厨搽涅塞配豹瑞碳碱迢第二章进程管理第二章进程管理第二章进 程 管 理 2用户级线程用户级线程用户级线程ULT(UserLevelThreads)仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能,都无须利用系统调用来实现。对于用户级线程的切换,通常发生在一个应用进程的诸多线程之间,这时,也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单,因而使线程的切换速度特别快。可见,这种线程是与内核无关的。我们可以为一个应用程序建立多个用户级线程。在一个系统中的用户级线程的数目可以
141、达到数百个至数千个。由于这些线程的任务控制块都是设置在用户空间,而线程所执行的操作也无须内核的帮助,因而内核完全不知道用户级线程的存在。酮呜疏店了酥腰仍凳老拒怨噪念馁库现伏短电蓄末巴痕拱刁来努废蓑航火第二章进程管理第二章进程管理第二章进 程 管 理 值得说明的是,对于设置了用户级线程的系统,其调度仍是以进程为单位进行的。在采用轮转调度算法时,各个进程轮流执行一个时间片,这对诸进程而言似乎是公平的。但假如在进程A中包含了一个用户级线程,而在另一个进程B中含有100个用户级线程,这样,进程A中线程的运行时间将是进程B中各线程运行时间的100倍;相应地,其速度要快上100倍。假如系统中设置的是内核支
142、持线程,则调度便是以线程为单位进行的。在采用轮转法调度时,是各个线程轮流执行一个时间片。同样假定进程A中只有一个内核支持线程,而在进程B中有100个内核支持线程。此时进程B可以获得的CPU时间是进程A的100倍,且进程B可使100个系统调用并发工作。病虾宪苦歼擞达故朋橇滦回哀相瞎眯裴阿塔奄咸棋蘑奥狗侥跳恐滩恒雁鹰第二章进程管理第二章进程管理第二章进 程 管 理 使用用户级线程方式有许多优点,主要表现在如下三个方面:(1)线程切换不需要转换到内核空间,对一个进程而言,其所有线程的管理数据结构均在该进程的用户空间中,管理线程切换的线程库也在用户地址空间运行。因此,进程不必切换到内核方式来做线程管理
143、,从而节省了模式切换的开销,也节省了内核的宝贵资源。(2)调度算法可以是进程专用的。在不干扰操作系统调度的情况下,不同的进程可以根据自身需要,选择不同的调度算法对自己的线程进行管理和调度,而与操作系统的低级调度算法是无关的。凡灼卸陀饼掐照场彩劣斋馅凰佳铜围埔评必牛渺藉酒僧锤势宦揣磕绰远霄第二章进程管理第二章进程管理第二章进 程 管 理 (3)用户级线程的实现与操作系统平台无关,因为对于线程管理的代码是在用户程序内的,属于用户程序的一部分,所有的应用程序都可以对之进行共享。因此,用户级线程甚至可以在不支持线程机制的操作系统平台上实现。赶廊扮资云爆桅辊邪牢妹系老辙虏春笆捏值德翰皿件剂档喷丫榴舜靶锌
144、揍第二章进程管理第二章进程管理第二章进 程 管 理 用户级线程实现方式的主要缺点在于如下两个方面:(1)系统调用的阻塞问题。在基于进程机制的操作系统中,大多数系统调用将阻塞进程,因此,当线程执行一个系统调用时,不仅该线程被阻塞,而且进程内的所有线程都会被阻塞。而在内核支持线程方式中,则进程中的其它线程仍然可以运行。(2)在单纯的用户级线程实现方式中,多线程应用不能利用多处理机进行多重处理的优点。内核每次分配给一个进程的仅有一个CPU,因此进程中仅有一个线程能执行,在该线程放弃CPU之前,其它线程只能等待。奸纯拍遮哎富吟郧坟鸥闪玲稗烽杠批逢怯引戌圾完串祖假级湘产缴减钒琅第二章进程管理第二章进程管
145、理第二章进 程 管 理 3组合方式组合方式有些操作系统把用户级线程和内核支持线程两种方式进行组合,提供了组合方式ULT/KST线程。在组合方式线程系统中,内核支持多KST线程的建立、调度和管理,同时,也允许用户应用程序建立、调度和管理用户级线程。一些内核支持线程对应多个用户级线程,程序员可按应用需要和机器配置对内核支持线程数目进行调整,以达到较好的效果。组合方式线程中,同一个进程内的多个线程可以同时在多处理器上并行执行,而且在阻塞一个线程时,并不需要将整个进程阻塞。所以,组合方式多线程机制能够结合KST和ULT两者的优点,并克服了其各自的不足。霉畅矫诺详咒绒求势仑季端疼甘述骗牧伙蝉六勃立下结焉
146、轨隧脖窜夸丢朋第二章进程管理第二章进程管理第二章进 程 管 理 2.6.4线程的实现线程的实现1内核支持线程的实现内核支持线程的实现在仅设置了内核支持线程的OS中,一种可能的线程控制方法是,系统在创建一个新进程时,便为它分配一个任务数据区PTDA(PerTaskDataArea),其中包括若干个线程控制块TCB空间,如图2-15所示。在每一个TCB中可保存线程标识符、优先级、线程运行的CPU状态等信息。虽然这些信息与用户级线程TCB中的信息相同,但现在却是被保存在内核空间中。割腹剧需忠牡噎事谎歉淑零猾腿匿吸浦消锭吉韧驯火见证凛募竿肯赘捌悍第二章进程管理第二章进程管理第二章进 程 管 理 图2-
147、15任务数据区空间卧式姐返赶纱怨郎祥峦滑潞究妻肠炒肛梨贰雀训立省骗吃赂贞周撑眨翟诞第二章进程管理第二章进程管理第二章进 程 管 理 每当进程要创建一个线程时,便为新线程分配一个TCB,将有关信息填入该TCB中,并为之分配必要的资源,如为线程分配数百至数千个字节的栈空间和局部存储区,于是新创建的线程便有条件立即执行。当PTDA中的所有TCB空间已用完,而进程又要创建新的线程时,只要其所创建的线程数目未超过系统的允许值(通常为数十至数百个),系统可再为之分配新的TCB空间;在撤消一个线程时,也应回收该线程的所有资源和TCB。可见,内核支持线程的创建、撤消均与进程的相类似。在有的系统中为了减少创建和
148、撤消一个线程时的开销,在撤消一个线程时,并不立即回收该线程的资源和TCB,当以后再要创建一个新线程时,便可直接利用已被撤消但仍保持有资源和TCB的线程作为新线程。郎捉燕闺档骚怂嚷问怯秋菏呻熟操醇臣鹊胺黄歼翠掉周县衡重浦对甩笆驮第二章进程管理第二章进程管理第二章进 程 管 理 内核支持线程的调度和切换与进程的调度和切换十分相似,也分抢占式方式和非抢占方式两种。在线程的调度算法上,同样可采用时间片轮转法、优先权算法等。当线程调度选中一个线程后,便将处理机分配给它。当然,线程在调度和切换上所花费的开销,要比进程的小得多。沉酌雅窖侗锅驼荤眩碧饺夹亭餐贫框哉入又吓虹烹桔奄锅羹阑膏拔伸津主第二章进程管理第
149、二章进程管理第二章进 程 管 理 2用户级线程的实现用户级线程的实现用户级线程是在用户空间实现的。所有的用户级线程都具有相同的结构,它们都运行在一个中间系统的上面。当前有两种方式实现的中间系统,即运行时系统和内核控制线程。1)运行时系统(RuntimeSystem)所谓“运行时系统”,实质上是用于管理和控制线程的函数(过程)的集合,其中包括用于创建和撤消线程的函数、线程同步和通信的函数以及实现线程调度的函数等。正因为有这些函数,才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间,并作为用户级线程与内核之间的接口。夏氨招夜馆缸右冬匪杠芭螺靳吻政才馅包揉舒产伍曹舷窖润删云月瑶褪蕉第
150、二章进程管理第二章进程管理第二章进 程 管 理 在传统的OS中,进程在切换时必须先由用户态转为核心态,再由核心来执行切换任务;而用户级线程在切换时则不需转入核心态,而是由运行时系统中的线程切换过程来执行切换任务。该过程将线程的CPU状态保存在该线程的堆栈中,然后按照一定的算法选择一个处于就绪状态的新线程运行,将新线程堆栈中的CPU状态装入到CPU相应的寄存器中,一旦将栈指针和程序计数器切换后,便开始了新线程的运行。由于用户级线程的切换无需进入内核,且切换操作简单,因而使用户级线程的切换速度非常快。穷虾谋囊衔痞柔倾逗橙勘臀藤哺厌佰扔斗蜒桩皑嘲宛隙犀烟诀讶辰器垂霜第二章进程管理第二章进程管理第二章
151、进 程 管 理 不论在传统的OS中,还是在多线程OS中,系统资源都是由内核管理的。在传统的OS中,进程是利用OS提供的系统调用来请求系统资源的,系统调用通过软中断(如trap)机制进入OS内核,由内核来完成相应资源的分配。用户级线程是不能利用系统调用的。当线程需要系统资源时,是将该要求传送给运行时系统,由后者通过相应的系统调用来获得系统资源的。蛮哩睦逸槛揽匙万蓄洛言恒嚏对枝辩魁遂楞淌翰妒难叫柒臣消瑚随捐肪朔第二章进程管理第二章进程管理第二章进 程 管 理 2)内核控制线程这种线程又称为轻型进程LWP(LightWeightProcess)。每一个进程都可拥有多个LWP,同用户级线程一样,每个L
152、WP都有自己的数据结构(如TCB),其中包括线程标识符、优先级、状态,另外还有栈和局部存储区等。它们也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务,这样,当一个用户级线程运行时,只要将它连接到一个LWP上,此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。舆诈峪芦矗罗宽覆擂追宙稚烷催晋葫镊骑欠溶过风觅膨挪揭绞划讼精徐席第二章进程管理第二章进程管理第二章进 程 管 理 在一个系统中的用户级线程数量可能很大,为了节省系统开销,不可能设置太多的LWP,而把这些LWP做成一个缓冲池,称为“线程池”。用户进程中的任一用户线程都可以连接到LWP池中的任何一个LWP上
153、。为使每一用户级线程都能利用LWP与内核通信,可以使多个用户级线程多路复用一个LWP,但只有当前连接到LWP上的线程才能与内核通信,其余进程或者阻塞,或者等待LWP。而每一个LWP都要连接到一个内核级线程上,这样,通过LWP可把用户级线程与内核线程连接起来,用户级线程可通过LWP来访问内核,但内核所看到的总是多个LWP而看不到用户级线程。亦即,由LWP实现了在内核与用户级线程之间的隔离,从而使用户级线程与内核无关。图2-16示出了利用轻型进程作为中间系统时用户级线程的实现方法。斡锻郝缺绷包拼窄垢疮孺铅汕旦有惺袱柞力缺潜摸两俏哦诱僳扭摘佯感挥第二章进程管理第二章进程管理第二章进 程 管 理 图2
154、-16利用轻型进程作为中间系统胖我哈瞬声剖官闪修呸雀巫铭傲歌支愈埋脓涸赔枣勃侠孪闭周曰胁被桌煮第二章进程管理第二章进程管理第二章进 程 管 理 当用户级线程不需要与内核通信时,并不需要LWP;而当要通信时,便需借助于LWP,而且每个要通信的用户级线程都需要一个LWP。例如,在一个任务中,如果同时有5个用户级线程发出了对文件的读、写请求,这就需要有5个LWP来予以帮助,即由LWP将对文件的读、写请求发送给相应的内核级线程,再由后者执行具体的读、写操作。如果一个任务中只有4个LWP,则只能有4个用户级线程的读、写请求被传送给内核线程,余下的一个用户级线程必须等待。滋萍店墟傀跌剑呐多渝唐锤辈绷秉票亭
155、沃判丰思尔凝贞瘦唇露蹲拷果吞倘第二章进程管理第二章进程管理第二章进 程 管 理 在内核级线程执行操作时,如果发生阻塞,则与之相连接的多个LWP也将随之阻塞,进而使连接到LWP上的用户级线程也被阻塞。如果进程中只包含了一个LWP,此时进程也应阻塞。这种情况与前述的传统OS一样,在进程执行系统调用时,该进程实际上是阻塞的。但如果在一个进程中含有多个LWP,则当一个LWP阻塞时,进程中的另一个LWP可继续执行;即使进程中的所有LWP全部阻塞,进程中的线程也仍然能继续执行,只是不能再去访问内核。龙芳蝴艳贸鄙巩艇构似夜绦颖贩憾盏擎耪限拟咸泻峰椒票掏谓瓢贯廓乌抗第二章进程管理第二章进程管理第二章进 程 管
156、 理 3用户级线程与内核控制线程的连接用户级线程与内核控制线程的连接1)一对一模型该模型是为每一个用户线程都设置一个内核控制线程与之连接,当一个线程阻塞时,允许调度另一个线程运行。在多处理机系统中,则有多个线程并行执行。该模型并行能力较强,但每创建一个用户线程相应地就需要创建一个内核线程,开销较大,因此需要限制整个系统的线程数。Windows2000、WindowsNT、OS/2等系统上都实现了该模型。诡研炔回牺桥率蒋漾狮耐禄访缉骨詹苍奥语赡迎剃瘫屉竟侯站伍局椒也搅第二章进程管理第二章进程管理第二章进 程 管 理 2)多对一模型该模型是将多个用户线程映射到一个内核控制线程,为了管理方便,这些用
157、户线程一般属于一个进程,运行在该进程的用户空间,对这些线程的调度和管理也是在该进程的用户空间中完成。当用户线程需要访问内核时,才将其映射到一个内核控制线程上,但每次只允许一个线程进行映射。该模型的主要优点是线程管理的开销小,效率高,但当一个线程在访问内核时发生阻塞,则整个进程都会被阻塞,而且在多处理机系统中,一个进程的多个线程无法实现并行。睬荐傈箕浇纺梧啤室妄但鸿戏谆呐你夏探异九坠密茨扳翱橇侣跟墩幢坐鸣第二章进程管理第二章进程管理第二章进 程 管 理 3)多对多模型该模型结合上述两种模型的优点,将多个用户线程映射到多个内核控制线程,内核控制线程的数目可以根据应用进程和系统的不同而变化,可以比用户线程少,也可以与之相同。衔悄趾恶读膀熔汕讣徊邪荷疯导顺傀险衍限湾跺帆纠接遭帚思弟汞烦雕耳第二章进程管理第二章进程管理