1 第四章 并发处理2第四章 并发处理4.1 并发活动进程的引人 操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。 要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。34.1 并发活动进程的引人4.1.1 程序的顺序执行 一、概念 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。 例如： 44.1 并发活动进程的引人4.1.1 程序的顺序执行 二、程序顺序执行的特点1.顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性 程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。3.可再现性 程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。54.1 并发活动进程的引人4.1.2 程序的并发执行例： 在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi (i=1,2,3,.,n)。 这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如: I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2，I3与P1是可以同时执行的。64.1 并发活动进程的引人4.1.2 程序的并发执行例如: I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。74.1 并发活动进程的引人4.1.2 程序的并发执行程序并发执行 （定义） 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。84.1 并发活动进程的引人4.1.2 程序的并发执行程序并发执行的描述 cobegin S1;S2;S3;.;SN coend; Si(i=1,2,3,.,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。co是concurrent的头两个字符。 这是Dijkstra提出的。94.1 并发活动进程的引人4.1.2 程序的并发执行假设有一个程序由S0Sn+1个语句，其中 S1Sn语句是并发执行的，程序如下： S0; cobegin S1;S2;S3;.;SN coend; Sn+1;104.1 并发活动进程的引人4.1.3 并发执行实行誊抄一、一个循环程序顺序执行的誊抄算法1：输入：f 输出：g while (f 不为空） input ; output ; 由这个程序完成誊抄工作是不会出错的。114.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄 设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。124.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄算法：2 cobegin while (不为结束符）/* 输入程序段 */ input; /* 从标准输入设备读入一个数据 */ send; /* 将读入的数据送到bufferf */ while(buffer不为空） /* 输出程序段 */ receive; /* 从bufferf中取数据 */ output; /* 送打印机输出 */ coend 134.1 并发活动进程的引人4.1.3 并发执行实行誊抄二、两个程序并发执行完成誊抄这两个程序段并发执行时可能出现如下情况：1、输出程序运行的速度比输入程序快时，有些输出会重复； 如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。2、输入程序执行的速度比输出程序快时，有些数据会丢失； 如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。144.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄get程序负责人输入序列f中读取字符并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。154.1 并发活动进程的引人4.1.3 并发执行实行誊抄 三、三个并发执行程序的誊抄 假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。这个算法是正确的。164.1 并发活动进程的引人4.1.4 与时间有关的错误假定f系列中有记录 f=(R1,R2,.,Rn) g=()在誊抄完成后： f=() g=(R1,R2,.,Rn)算法中的：copyt=s put put(t,g) get get(s,f)174.1 并发活动进程的引人4.1.4 与时间有关的错误若程序错写成：while(誊抄未完成） cobegin copy; put; get; coend 初始状态： f=(R1,R2,.,Rn) s=() t=() g=()首先执行了get(s,f) f=(R1,R2,.,Rn) s=R1,t=(),g=()184.1 并发活动进程的引人4.1.4 与时间有关的错误然后，copy,put,get三个程序段并发执行，就有六种组合：1、copy;put;get 导致结果：g=(R1,R2) 2、copy;get;put 导致结果：g=(R1,R2) 3、put;copy;get 导致结果：g=(R1,R1) 4、put;get;copy 导致结果：g=(R1,R1) 5、get;copy;put 导致结果：g=(R1,R3) 6、get;put;copy 导致结果：g=(R1,R1) 这就是与时间有关的错误。194.1 并发活动进程的引人4.1.5 程序并发执行的特点一、失去了程序的封闭性 如果程序执行的结果是一个与时间无关的函数，即具有封闭性。 若一个程序的执行可改变另一个程序的变量，象二个并发程序完成誊抄的例子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。 教材P62介绍了两个并发程序共享变量的例子204.1 并发活动进程的引人4.1.5 程序并发执行的特点二、程序与计算不再一一对应 在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。214.1 并发活动进程的引人4.1.5 程序并发执行的特点三、程序并发执行的相互制约 在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。 回头来，我们再看看操作系统的第三个特性： 不确定性*224.2 进程概念(process) 4.2.1 进程的定义 在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引人新的概念进程。 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。234.2 进程概念(process) 4.2.1 进程的定义进程的定义（枚举法）行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw)进程是执行中的程序。（Ken Thompson and Dennis Ritchie )教材上给出的进程的定义： 进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。244.2 进程概念(process) 4.2.1 进程的定义 进程与程序的区别与联系：1、程序是指令的集合，是静态的概念。 进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并行（并发）活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。254.2 进程概念(process) 4.2.1 进程的定义 进程与程序的区别与联系：例子：光盘（CD、VCD）光盘（程序） 放光盘的活动（进程）264.2 进程概念(process)4.2.2 进程的类型在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程 系统进程起着资源管理和控制的作用。 或者：执行操作系统核心代码的进程。2、用户进程 执行用户程序的进程。274.2 进程概念(process)4.2.2 进程的类型系统进程与用户进程的区别：1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；2、用户进程不能直接做I/O操作，而系统进程可以做显示的、直接的I/O操作。3、系统进程在管态下活动，而用户进程则在用户态（目态）下活动。另一种分类：计算进程，I/O进程等注意：在UNIX系统中没有这样对进程进行分类。284.2 进程概念(process)4.2.3 进程的状态一、进程的基本状态进程在系统中的活动规律是： 执行 暂停 执行进程的三种基本状态： 运行状态 就绪状态 等待状态（又称阻塞、挂起、睡眠）294.2 进程概念(process)4.2.3 进程的状态 一、进程的基本状态1、就绪状态（Ready) 存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所取的状态为就绪状态。（有多个进程处于此状态）2、运行状态(Running） 当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，总只有一个进程处于此状态）3、等待状态（Wait) 若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。304.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图进程的状态不是固定不变的，而是在不断变换。314.2 进程概念(process)4.2.3 进程的状态二、进程状态变迁图运行 等待 等待某事件的发生（如等待I/O完成）等待 就绪 事件已经发生（如I/O完成）运行 就绪 时间片到（例如，两节课时间到，下课）新建进程 就绪 新创建的进程进入就绪状态就绪 运行 当处理机空闭时，由调度（分派）程序从就绪进程队列中选择一个进程占用CPU。324.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移 在批处理系统中一个用户程序的执行的全过程称为一个作业，当作业提交给计算中心（或机房）后，由机房工作人员录入到存储设备上（如磁带、磁盘等），然后，由作业调度程序按某种调度策略将作业调入计算机系统执行，执行完成后，由作业调度程序做作业的善后处理工作，至此一个作业完成。334.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移 我们把上述对作业的操作归纳成四种状态：1、提交状态 用户将自己的程序和数据放在输入设备上，等待；2、后备状态 系统响应用户的要求，将作业带领到直接存取的后援存储器中，等待调度；3、执行状态 从作业计算开始，到计算完成为止，该作业处于执行状态。4、完成状态 从作业计算完成开始，到善后处理完毕退出系统为止，称为作业完成状态。344.2 进程概念(process)4.2.3 进程的状态三、作业、作业状态及转移354.2 进程概念(process) 4.2.4 进程描述在系统中一个进程存在： 进程控制块（数据结构） 进程的执行程序（一个可执行文件） 进程总是位于某个队列(就绪、等待某事件队列) 处于某种状态（运行、就绪、等待） 占用某些系统资源（内存，打开某些文件、处理机、外设）364.2 进程概念(process)4.2.4 进程描述进程控制块 PCB (Process Control Block) 存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。374.2 进程概念(process)4.2.4 进程描述进程控制块 PCB 1、进程标识符 name 每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。UNIX系统中就是一个整型数。在进程创建时由系统赋予。 2、进程当前状态 status 说明进程当前所处的状态。 为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等。384.2 进程概念(process)4.2.4 进程描述进程控制块 PCB3、当前队列指针 next 登记与本进程处于同一队列的下一个进程的PCB的地址。394.2 进程概念(process)4.2.4 进程描述进程控制块 PCB4、总链指针 all-q-next5、执行程序开始地址 start-addr6、进程优先级 priority 进程的优先级反映进程的紧迫程序，通常由用户指定和系统设置。UNIX系统采用用户设置和系统计算相结合的方式确定进程的优先级。404.2 进程概念(process)4.2.4 进程描述进程控制块 PCB7、CPU现场保护区 cpustatus 当进程因某种原因不能继续占用CPU时（等待打印机），释放CPU，这时就要将CPU的各种状态信息保护起来，为将来再次得到处理机恢复CPU的各种状态，继续运行。例如，我们下课，这时我要记住这次讲到什么地方，下次课接着讲。8、通信信息 communication information 是指某个进程在运行的过程中要与其它进程进行通信，该区记录有关进程通信方面的信息。414.2 进程概念(process)4.2.4 进程描述进程控制块 PCB9、家族联系 process family 有的系统允许一个进程可创建自已的子进程，子进程还可以创建，一个进程往往处在一个家族之中，就需要记录进程在家族中位置的信息。10、占有资源清单 own-resource 进程占用系统资源的情况，不同的系统的处理差别很大，UNIX系统中就没有此项。424.3 进程控制4.3.1 进程控制的概念 进程是有生命周期的，产生、运行、暂停、终止。对进程的这些操作叫进程控制。 进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须提供对进程实行有效的管理。434.3 进程控制4.3.1 进程控制的概念 进程控制包括： 进程创建、 进程撤消、 进程阻塞、 进程唤醒。 这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。444.3 进程控制4.3.1 进程控制的概念运行状态 等待状态 进程阻塞等待状态 就绪状态 进程唤醒新建进程置为就绪状态 进程创建进程终止（消亡） 进程撤消就绪状态 运行状态 进程调度454.3 进程控制4.3.1 进程控制的概念 在UNIX系统中进程控制的系统调用有： fork() 创建子进程 sleep() 进程睡眠 exit() 进程自已终止（自杀） wait() (父）等待子进程终止 wakeup() 进程唤醒 在4.9节介绍。464.3 进程控制4.3.2 进程创建 在UNIX系统中用户键人一个命令（如date, ps,ls)，shell就创建一个进程。 一个程序（可执行的）如果可分成几个程序段，并且这些程序段可并发执行，用户程序可使用创建程序的系统调用创建多个进程，每个进程执行一个程序段。例如，放VCD程序。 进程创建类似于人出生后要到派出所报户口。474.3 进程控制4.3.2 进程创建进程创建系统调用： create(name,priority,start-addr)UNIX系统： fork()484.3 进程控制4.3.2 进程创建494.3 进程控制4.3.3 进程撤消 进程完成其任务，希望终止时，调用撤消进程的系统调用（进程撤消原语）撤消进程。相当于一个人死亡后，家人要去派出所消户口。 在一般操作系统中进程撤消的系统调用是：kill UNIX系统中是exit()。 504.3 进程控制4.3.3 进程撤消514.3 进程控制4.3.3 进程撤消524.3 进程控制4.3.4 进程挂起 当一个处在运行状态的进程，因等待某个事件的发生（如等待打印机）而不能继续运行时，将调用进程挂起系统调用，把进程的状态置为阻塞状态，并调用进程调度程序（等于让出处理机）。在UNIX系统中进程挂起调用sleep(chan, pri)。534.3 进程控制4.3.4 进程挂起 进程从运行状态转换成阻塞状态是由进程挂起原语实现的，因此，调用进程挂起操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变. 例如，进程是因等待打印机而进入阻塞状态，则该进程将加入到等待打印机的队列。进程挂起系统调用的算法和队列变化如下。544.3 进程控制4.3.4 进程挂起进程挂起的内部调用形式（UNIX系统）： sleep(chan,pri) 其中：chan 进程挂起（睡眠）的原因； pri 进程被唤醒后的优先级 一般调用形式： susp(chan) 其中：chan 进程等待的原因554.3 进程控制4.3.4 进程挂起564.3 进程控制4.3.4 进程挂起574.3 进程控制4.3.5 进程唤醒 一个正在运行的进程会因等待某事件（例如，等待打印机）的发生，由运行状态转换成阻塞状态，当它等待的事件发生后，这个进程将由阻塞状态转换成就绪状态。这种转换由进程唤醒操作完成。 调用进程唤醒操作一般在中断处理、进程通信等过程中。例如，打印机完成中断处理程序， 在完成了打印完成的操作后，就去检查等待打印机的队列，若不为空，则调用进程唤醒操作，唤醒一个（或多个）等待打印机的进程。 584.3 进程控制4.3.5 进程唤醒进程唤醒原语的形式： wakeup(chan) 其中：chan 唤醒进程阻塞的原因。594.3 进程控制4.3.5 进程唤醒算法：wakeup输入：chan:等待的事件（阻塞原因）输出：无 找到chan的等待队列的指针； for(该队列不为空） 从队列中移出一个进程； 置进程状态为“就绪”，并加入到就绪队列； 604.3 进程控制4.3.5 进程唤醒 按此算法，是把等待在chan事件上的所有进程唤醒，类似于UNIX系统的处理方式。也有的系统只唤醒一个等待chan事件的进程，若这样处理，等待队列就要按某种优先级排队。 进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。614.3 进程控制4.3.5 进程唤醒 按此算法，是把等待在chan事件上的所有进程唤醒，类似于UNIX系统的处理方式。也有的系统只唤醒一个等待chan事件的进程，若这样处理，等待队列就要按某种优先级排队。 进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。624.4进程的相互制约关系 在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。 产生这种错综复杂的相互制约关系的原因有二： 资源共享 进程合作634.5 进程互斥4.5.1 互斥的概念 引例： 宿舍电话的使用 打印机的使用 1. 临界资源：一次仅允许一个进程使用的资源称为临界资源。 引例中的电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。644.5 进程互斥 4.5.1 互斥的概念2、临界区：每个进程中访问临界资源的那段程序段称为临界区（临界段）。654.5 进程互斥 4.5.1 互斥的概念互斥定义定义: :在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生(后果)无法估计的错误。我们把进程之间的这种相互制约的关系称为互斥。例如：飞机定票系统中的机票库664.5 进程互斥 4.5.1 互斥的概念进入临界区的准则：(1)每次至多有一个进程处于临界区；(2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入；(3)进程在临界区内仅逗留有限的时间。674.5 进程互斥 4.5.2 锁和上锁、开锁操作 解决进程互斥的最简单的办法是加锁。 在系统中为每个临界资源设置一个锁位， 0 表示资源可用， 1 表示资源已被占用（不可用）。这样当一个进程使用某个临界资源之前必须完成下列操作：1、考察锁位的值；2、若原来的值是为“0”，将锁位置为“1”（占用该资源）；3、若原来值是为“1”，（该资源已被别人占用），则转到1。 当进程使用完资源后，将锁位置为“0“，称为开锁操作。68