操作系统原理并发处理1并发活动进程引入.pptx

n 第四章第四章 并发处理并发处理n操操作作系系统统的的两两大大重重要要特特性性是是并并发发与与共共享享，即即在在系系统统中中（内内存存）同同时时存存在在几几个个相相互互独独立立的的程程序序，这这些些程程序序在在系系统统中中既既交交叉叉地地运运行行，又又要要共共享享系系统统中中的的资资源源，这这就就会会引引起起一一系系列列的的问问题题，包包括括：对对资资源源的的竞竞争争、运运行行程程序序之之间间的的通信、程序之间的合作与协同等等。通信、程序之间的合作与协同等等。n 要要解解决决这这些些问问题题，用用程程序序的的概概念念已已经经不不能能描描述述其其在在内内存存中中运运行行的的状状态态，必须引入新的概念进程。必须引入新的概念进程。4.1 4.1 并发活动进程的引入并发活动进程的引入4.1 4.1 并发活动进程的引入并发活动进程的引入4.1.1 程序的顺序执行程序的顺序执行n 一、概念一、概念n 一一个个程程序序由由若若干干个个程程序序段段组组成成，而而这这些些程程序序段段的的执执行行必必须须是是顺顺序序的的，这这种种程程序序执执行行的方式就称为的方式就称为程序的顺序执行程序的顺序执行。n 例如：例如：4.1 并发活动进程的引入并发活动进程的引入4.1.1 程序的顺序执行程序的顺序执行 n二、程序顺序执行的特点二、程序顺序执行的特点n1.顺序性顺序性n 处处理理机机严严格格按按照照程程序序所所规规定定的的顺顺序序执执行行，即即每每个个操作必须在下一个操作开始之前结束操作必须在下一个操作开始之前结束。n2.封闭性封闭性n 程程序序一一旦旦开开始始执执行行，其其计计算算结结果果不不受受外外界界的的影影响响，当当程程序序的的初初始始条条件件给给定定之之后后，其其后后的的状状态态只只能能由由程序本身确定，即只有本程序才能改变它。程序本身确定，即只有本程序才能改变它。n3.可再现性可再现性n 程程序序执执行行的的结结果果与与初初始始条条件件有有关关，而而与与执执行行时时间间无无关关。即即只只要要程程序序的的初初始始条条件件相相同同，它它的的执执行行结结果果是是相相同同的的，不不论论它它在在什什么么时时间间执执行行，也也不不管管计计算机的运行速度。算机的运行速度。4.1 并发活动进程的引入并发活动进程的引入4.1.2 程序的并发执行程序的并发执行n例：例：n 在在系系统统中中有有n个个作作业业，每每个个作作业业都都有有三三个个处处理理步步骤骤，输输入入数数据据、处处理理、输输出出，即即Ii,Ci,Pi(i=1,2,3,.,n)。n 这这些些作作业业系系统统中中执执行行时时是是对对时时间间的的偏偏序序，有有些些操操作作必必须须在在其其它它操操作作之之前前执执行行，这这是是有序的，但有些操作是可以同时执行的。有序的，但有些操作是可以同时执行的。n例如例如:n I1、C1、P1的的执执行行必必须须严严格格按按照照I1，C1，P1的的顺顺序序，而而P1与与I2，C1与与I2，I3与与P1是是可可以同时执行的。以同时执行的。4.1 并发活动进程的引入并发活动进程的引入4.1.2 程序的并发执行程序的并发执行n例如例如:n I1、C1、P1的执的执行必须严格按照行必须严格按照I1，C1，P1的顺序，的顺序，而而P1与与I2，C1与与I2,I3与与P1是可以同是可以同时执行的。时执行的。4.1 并发活动进程的引入并发活动进程的引入4.1.2 程序的并发执行程序的并发执行n程序并发执行程序并发执行（定义）（定义）n 若若干干个个程程序序段段同同时时在在系系统统中中运运行行，这这些些程程序序的的执执行行在在时时间间上上是是重重迭迭的的，一一个个程程序序段段的的执执行行尚尚未未结结束束，另另一一个个程程序序段段的的执执行行已已经经开开始始，即即使使这这种种重重迭是很小的，也称这几个程序段是并发执行的。迭是很小的，也称这几个程序段是并发执行的。4.1 并发活动进程的引入并发活动进程的引入4.1.2 程序的并发执行程序的并发执行n程序并发执行的描述程序并发执行的描述n cobeginn S1;S2;S3;.;SNn coend;n Si(i=1,2,3,.,n)表表示示n个个语语句句（程程序序段段），这这n个个语语句句用用cobegin和和coend括括起起来来表表示示这这 n个个 语语 句句 是是 可可 以以 并并 发发 执执 行行 的的。co是是concurrent的头两个字符。的头两个字符。n 这是这是Dijkstra提出的。提出的。4.1 并发活动进程的引入并发活动进程的引入4.1.2 程序的并发执行程序的并发执行n假设有一个程序由假设有一个程序由nS0Sn+1个语句，个语句，n其其中中 S1Sn语语句句是是并并发执行的，程序如下：发执行的，程序如下：n S0;n cobeginn S1;S2;S3;.;SN;n coendn Sn+1;4.1 并发活动进程的引入并发活动进程的引入4.1.3 并发执行实例誊抄并发执行实例誊抄n一、一个循环程序顺序执行的誊抄一、一个循环程序顺序执行的誊抄n算法算法1：n输入：输入：f 输出：输出：gnn while(f 不为空）不为空）n n input;n output;n n n由这个程序完成誊抄工作是不会出错的。由这个程序完成誊抄工作是不会出错的。4.1 并发活动进程的引入并发活动进程的引入4.1.3 并发执行实行誊抄并发执行实行誊抄n二、两个程序并发执行完成誊抄二、两个程序并发执行完成誊抄n设有一台标准输入设备（键盘），和一台标准设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。出程序从缓冲区中取数据，送标准设备输出。4.1 并发活动进程的引入并发活动进程的引入4.1.3 并发执行实行誊抄并发执行实行誊抄n二、两个程序并发执行完成誊抄二、两个程序并发执行完成誊抄 算法：算法：2n cobeginn while(不为结束符）不为结束符）/*输入程序段输入程序段 */n input;/*从从标标准准输输入入设设备备读读入入一一个个数数据据*/n send;/*将读入的数据送到将读入的数据送到bufferf*/n n while(buffer不为空）不为空）/*输出程序段输出程序段*/n receive;/*从从bufferf中取数据中取数据*/n output;/*送打印机输出送打印机输出*/n n coend n 4.1 并发活动进程的引入并发活动进程的引入4.1.3 并发执行实行誊抄并发执行实行誊抄n这两个程序段并发执行时可能出现如下情况：这两个程序段并发执行时可能出现如下情况：n1、输输出出程程序序运运行行的的速速度度比比输输入入程程序序快快时时，有有些些输输出会重复；出会重复；n 如如输输入入送送入入了了一一个个字字符符“A”，输输出出取取出出打打印印“A”，当当输输入入还还未未送送入入新新的的数数据据，输输出出程程序序已已执执行行，又又取取出出“A”打打印印，这这样样“A”的的输输出出就就重重复复了，出错。了，出错。n2、输输入入程程序序执执行行的的速速度度比比输输出出程程序序快快时时，有有些些数数据会丢失；据会丢失；n 如如输输入入程程序序送送入入一一个个字字符符“B”，紧紧接接着着（当当输输出出程程序序还还未未取取走走字字符符“B”）又又送送入入字字符符“N”，这时输出程序取走的是这时输出程序取走的是“N”，“B”就丢失了。就丢失了。4.1 并发活动进程的引入并发活动进程的引入4.1.3 并发执行实行誊抄并发执行实行誊抄n三、三个并发执行程序的誊抄三、三个并发执行程序的誊抄nget程序输入数据并送到缓冲区程序输入数据并送到缓冲区s中中;ncopy程序把缓冲区程序把缓冲区s中的数据复制到缓冲区中的数据复制到缓冲区t中去中去;nput程序从缓冲区程序从缓冲区t中取出数据打印。中取出数据打印。4.1 并发活动进程的引入并发活动进程的引入4.1.3 并发执行实行誊抄并发执行实行誊抄 三、三个并发执行程序的誊抄三、三个并发执行程序的誊抄n 假假设设有有两两个个缓缓冲冲区区，每每个个缓缓冲冲区区只只存存放放一一个个字字符符，get程程序序负负责责从从输输入入序序列列f中中读读一一个个字字符符，然然后后，送送到到缓缓冲冲区区s中中，copy程程序序负负责责将将s中中的的字字符符复复制制到到t中中，put负负责责从从t中中提提取取字字符符打打印印。这这个个算算法法是是正正确确的。的。4.1 并发活动进程的引入并发活动进程的引入4.1.4 与时间有关的错误与时间有关的错误n假定假定f系列中有记录系列中有记录 n f=(R1,R2,.,Rn)n g=()n在誊抄完成后：在誊抄完成后：n f=()n g=(R1,R2,.,Rn)n算法中的：算法中的：ncopyt=s put put(t,g)get get(s,f)4.1 并发活动进程的引入并发活动进程的引入4.1.4 与时间有关的错误与时间有关的错误n若程序错写成：若程序错写成：nwhile(誊抄未完成）誊抄未完成）nn cobeginn copy;n put;n get;n coendn n初始状态：初始状态：n f=(R1,R2,.,Rn)n s=()t=()g=()n首先执行了首先执行了get(s,f)n f=(R1,R2,.,Rn)n s=R1,t=(),g=()n假假设设第第一一次次循循环环时时执执行行顺顺序序为为copy、put、get;f=(R1,R2,.,Rn)n s=R2,t=R1,g=(R1)4.1 并发活动进程的引入并发活动进程的引入4.1.4 与时间有关的错误与时间有关的错误n然然后后，第第二二次次循循环环时时，copy,put,get三三个个程程序序段段并并发执行，就有六种组合：发执行，就有六种组合：n1、copy;put;get 导致结果：导致结果：g=(R1,R2)n2、copy;get;put 导致结果：导致结果：g=(R1,R2)n3、put;copy;get 导致结果：导致结果：g=(R1,R1)n4、put;get;copy 导致结果：导致结果：g=(R1,R1)n5、get;copy;put 导致结果：导致结果：g=(R1,R3)n6、get;put;copy 导致结果：导致结果：g=(R1,R1)n这就是这就是与时间有关的错误与时间有关的错误。4.1 并发活动进程的引入并发活动进程的引入4.1.5 程序并发执行的特点程序并发执行的特点n一、失去了程序的封闭性一、失去了程序的封闭性n 如如果果程程序序执执行行的的结结果果是是一一个个与与时时间间无无关关的的函数，即具有封闭性。函数，即具有封闭性。n 若若一一个个程程序序的的执执行行可可改改变变另另一一个个程程序序的的变变量量，象象二二个个并并发发程程序序完完成成誊誊抄抄的的例例子子，程程序序执执行行的的结结果果不不仅仅依依赖赖于于程程序序的的初初始始条条件件，还还依依赖赖于于程程序序执执行行时时的的相相对对速速度度，在在这这种种情况下就失去了程序的封闭性。情况下就失去了程序的封闭性。n 4.1 并发活动进程的引入并发活动进程的引入4.1.5 程序并发执行的特点程序并发执行的特点n二、程序与计算不再一一对应二、程序与计算不再一一对应n 在在程程序序顺顺序序执执行行时时，一一个个程程序序总总是是对对应应一一个个具具体体的的计计算算，但但在在程程序序的的并并发发执执行行时时，可可能能有有多多用用户户共共享享使使用用同同一一个个程程序序，但但处处理理（计计算算）的的对对象象却却是是不不同同的的，例例如如，在在多多用用户户环环境境下下，可可能能同同时时有有多多个个用用户户调调用用C语语言言的的编编译译程程序序，这这就就是是典典型型的的一一个个程程序序对对应应多多个用户源程序的情况个用户源程序的情况。4.1 并发活动进程的引入并发活动进程的引入4.1.5 程序并发执行的特点程序并发执行的特点n三、程序并发执行的相互制约三、程序并发执行的相互制约n 在在多多道道程程序序设设计计的的环环境境下下，程程序序是是并并发发执执行行的的。即即系系统统中中有有多多道道程程序序在在“同同时时”执执行行，这这些些程程序序之之间间要要共共享享系系统统的的资资源源，程程序序之之间间有有合合作作（通通信信）的的关关系系。合合作作与与竞竞争争产产生生一一系系列列的的矛矛盾盾，这这些些矛矛盾盾实实际际上上是一种相互制约，有直接的，也有间接。是一种相互制约，有直接的，也有间接。n