1、第三章第三章 进程管理进程管理 3.1 进程的概念3.2 进程的描述3.3 进程的状态及其转换3.4 进程控制3.5 进程互斥3.6 进程同步3.7 进程通信3.8 死锁问题3.9 线程第1页，共74页。3.1 进程的概念3.1.1 程序的并发执行 1.程序的顺序执行：一个具有独立功能的程序独占处理机直到最终结束的过程。顺序程序执行的特点：（1）程序执行的顺序性:每个操作必须在下一个操作 之前结束。（2）程序运行环境的封闭性:程序的运行环境只有它 自己的动作改变。（3）程序结果的确定性:其计算结果与执行速度、时间无关.（4）计算的可重现性:只要初始条件相同计算结果就必然相同。第2页，共74页。
2、2.多道程序系统中程序执行环境的变化多道程序系统中程序执行环境的变化 多道程序环境下执行环境的特点：（1）独立性:每道程序逻辑上完全独立，不存在相互的制约关系 （2）随机性:程序的开始执行、数据输入输出、完成时间都是随机的。（3）资源共享:系统内的所有资源都是被所有并发进程所共享。正是由于资源的共享，导致了对程序推进速度的制约。3.程序的并发、并行执行的含义程序的并发、并行执行的含义 （1）程序的并发执行：程序的并发执行：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在宏观上互相重叠。(强调时间段）第3页，共74页。（2）程序的并行执行：一组在逻辑上互相独立的程序或程序段在同一时刻
3、同时执行过程。（强调同一时刻）4.程序的并发执行所带来的影响 程序并发、并行执行最大的优点就是提高了计算机系统的处理能力，使计算机系统的资源利用率大大提高，为计算机的在各方面的低成本应用奠定了基础,也为计算机技术发展提供了条件。但是，也正是由于程序的并发执行，将会导致系统资源的共享和竞争，从而影响程序的推进进度，另外，也为操作系统和用户程序的开发带来一定的难度。程序的并发执行带来的问题：（与速度有关的错误）第4页，共74页。例如:x=0;Pa:Pb:printf(“x=%dn”,x);printf(“x=%dn”,x);由于Pa,Pb交替执行，打印出的结果可能是：（x=1，x=2）或（x=1，
4、x=1）结果不唯一，出错结果不唯一，出错!=RX=X R+=RR1+=XX;1=RX=X R+=RR1+=XX;1第5页，共74页。提出进程概念的原因提出进程概念的原因:由于程序的并发执行，导致程序执行的顺序性被打破；并发执行的程序段共享系统的软硬件资源，导致程序运行环境的封闭性不存在了；由于程序运行环境不再封闭，因此运行结果与程序运行速度有了一定的关系，顺序程序的程序结果的确定性和计算的可重现性也不复存在了。在多道程序系统中，如果我们的程序不采取一定的措施来控制和约束它们之间的推进速度的话，就会导致我们设计的程序的运行结果和我们预期完全不符的现象，得到一个错误的结果，从而给我们的计算机应用带
5、来很多的麻烦，这不是所我们期望的。因此必须有一个描述程序段的执执行过程和共享资源行过程和共享资源的基本单位。第6页，共74页。通过它来描述系统内程序段的运行过程中资源的当前对资源的请求情况、当前资源的实际获得情况和当前已使用完毕资源情况，从而为操作系统和用户程序的设计中对并发执行程序的推进速度的控制提供必要条件。但由于程序定义的顺序性、静态性和孤立性程序定义的顺序性、静态性和孤立性，用程序（段）作为描述其执行过程和共享资源的基本单位既增加操作系统设计和实现的复杂性，也无法反应操作系统所应该具有的程序段执行的并发性、用户随机性以及资源共享等特征，因此需要有一个能描述程序执行过程且能用来共享资源的
6、基本单位，这就是进程。第7页，共74页。3.1.2 进程的定义定义：定义：一个具有独立功能的程序对某个数据集在处 理机上的执行过程执行过程和资源分配的基本单位。进程和程序的区别和联系：进程和程序的区别和联系：（1）进程是动态的概念，而程序是静态的概念；（2）进程具有并行特征，而程序没有；（3）进程是竞争资源的基本单位，从而其并行性受到 系统自己的制约，而程序不是；（4）一个进程可以包含多个程序，一个程序可以对应 多个进程；（5）程序是进程的物理基础；（6）进程的生命周期是短暂的，而程序的生命周期与 进程相比则是长久的。第8页，共74页。进程的特征进程的特征:（1）动态性：进程的实质是程序的一次
7、运行过程，所以动态性是进程最基本的特征；动态性还表现在“它由创建而产生，由调度而执行，由撤消而消亡”；因此进程有一定的生命期。（2）并发性：多个进程能在一段时间内同时运行。（3）独立性：进程是一个能独立运行、独立分配资源和独立调度的基本单位。（4）异步性：各进程按各自独立的、不可预知的速度向前推进。（5）结构特征：为每个进程配置一个PCB。第9页，共74页。作业和进程的区别联系：作业和进程的区别联系：（1）作业是用户相计算机系统提交任务的任务实体，而进程则是完成用户任务的执行实体，是向系统 申请分配资源的基本单位。（2）作业在没有进入执行状态时被存入外存的后备作 业队列中等待调度执行；进程一旦
8、被创建，总有 相应部分被放入内存。（3）一个作业可由多个进程组成，且必须至少由一个 进程组成；但反过来不成立。（4）作业的概念应用范围主要局限于批处理系统中，而进程的概念则用于几乎所有多道程序系统中.第10页，共74页。3.2 进程的描述 进程的组成（进程的组成（静态描述）：）：进程是由程序、数据和进程控制块程序、数据和进程控制块（PCB）组成PCB的作用：的作用：1.PCB中包含进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。2.创建一个进程时首先创建其对应的PCB；当一个进程完成功能后，系统释放其PCB，进程随之消亡。3.系统根据PCB感知进程的存在,通过PCB中所包含的各
9、项变量的变化，掌握进程所处的状态。系统通过修改PCB中相应项的值来调整进程状态和控制进程的活动。4.PCB的全部或部分是常住内存的。第11页，共74页。PCB包含的基本内容：包含的基本内容：（1）进程的描述信息）进程的描述信息:进程名或进程标识号：是唯一的，代表进程身份用户名或用户标识：是代表该进程的归属家族信息：该进程的家族关系（2）进程的控制信息）进程的控制信息:进程状态：运行、就绪、阻塞 进程优先级：包括占用CPU时间、进程初始优先级等程序起始地址 计时信息：进程占用资源的时间 通信信息：进程之间信息交换的情况5.PCB是系统感知进程存在的唯一实体。第12页，共74页。(3)进程的资源管
10、理信息：存储器信息：占用内存信息和管理用数据结构、共享内存信息I/O设备信息：所用I/O设备编号及相应的管理数据结构文件信息:打开文件信息及管理用数据结构（4）CPU现场保护结构现场保护结构:在当前进程被迫让出处理机时，把当前进程运行的现场环境保存在这个结构中，下次恢复运行时又从这儿取出，恢复到系统中，为进程的再次运行作好准备。第13页，共74页。进程上下文进程上下文 是进程执行活动全过程的静态描述，它包括计算机中与执行该进程有关的各种寄存器的值、程序段在经过编译之后形成的机器指令代码集（正文段）、数据集及各种堆栈值和PCB结构。进程上下文可按一定的执行层次组合，如分为用户级上下文和系统级上下
11、文。进程的执行是在该进程的上下文中进行的,当系统调度新进程占用处理机时，新老进程的上下文就进行切换。UNIX System V中，进程上下文由用户级上下文、寄存器上下文、系统级上下文组成。系统级上下文又分为静态和动态两部分。第14页，共74页。进程空间（虚拟地址空间）进程空间（虚拟地址空间）进程中所有能使用地址的集合。所有程序的执行都在自己的进程空间中进行，用户 程序、进程的各种控制表格都按一定结构排列在进程空间中。进程空间的大小与处理机中指令的地址长度有关。在UNIX和Linux系统中，进程空间又被分为用户空间和系统空间两大部分，用户程序在用户空间中执行，处理机状态处于用户态；而系统程序则在
12、系统空间中执行,处理机状态处于核心态。第15页，共74页。3.3 进程状态及其转换 就绪状态就绪状态 进程已经获得了除CPU以外的所有资源，只要一旦由进程调度程序调度得到处理机便可立即投入运行。就绪状态又可分为：活动就绪状态（内存就绪）:进程在内存 静止就绪状态（外存就绪）:进程不在内存 运行状态运行状态 进程已经获得了包括CPU在内的所有资源,正在处理机上执行的状态。运行状态又可分为：用户执行状态:执行用户程序时的状态系统执行状态:执行系统核心代码时的状态第16页，共74页。等待状态（阻塞状态）等待状态（阻塞状态）进程因等待某事件的发生而放弃处理机后所处的状态。等待状态的分类：按进程是否在内
13、存分类：活动阻塞状态:进程在内存静态阻塞状态:进程不在内存 按等待事件分类：内存等待：当前没有足够内存 设备等待：当前所需设备忙 文件等待：文件输入输出未完成 数据等待：所需数据没有收到第17页，共74页。进程状态转换图之一就绪等待运行被作业调度选中被进程调度选中时间片到等待事件发生运行结束或出错等待事件已经发生第18页，共74页。进程状态转换图之二ReadyaBlockedaRunningReadysBlockeds事件发生事件发生等待事件等待事件时间片完时间片完被调度被调度挂起挂起挂起挂起解挂解挂解挂解挂挂起挂起事件发生事件发生具有挂起和解挂功能的操作系统中进程的状态变化第19页，共74页
14、。进程控制进程控制：系统使用具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换的过程。通过进程控制，可以达到多进程高效率并发执行，同时也能很好地协调并发进程之间的推进速度，实现资源共享。操作系统中是通过原语来完成对进程控制的。操作系统中是通过原语来完成对进程控制的。原语：原语：操作系统提供的为完成某系统功能的最基本的不可分割的操作。原语是不允许并发执行的。原语分为机器指令级的原语和功能级原语两类，它们都在核心态下执行 3.4 进程控制第20页，共74页。控制进程的原语：控制进程的原语：创建、撤销、阻塞、唤醒等 1.进程的创建：进程的创建：（1）创建方式：）创建方式：A)由系统程序统
15、一创建B)由父进程创建不管用那种方式创建进程，都是调用创建进程原语实现的（2）创建进程原语的工作过程：）创建进程原语的工作过程：A)申请空闲的PCB表项B)填PCB表的内容C)把当前PCB加入就绪队列D)将当前PCB加入进程家族或进程链第21页，共74页。2.进程的撤销：进程的撤销：（1）撤销进程的原因：）撤销进程的原因：A)进程完成任务，正常终止B)进程运行出错异常终止C)其祖先进程要求撤销 不管由于那种原因撤销进程，都是调用撤销进程原语实现的。进程的撤销方式有两种：A)仅撤销该PID代表的进程B)撤销该PID代表的进程及其所有子孙进程这两种方式各有优缺点第22页，共74页。(2)撤销进程原
16、语的工作过程：撤销进程原语的工作过程：A）根据进程PID查找进程链或进程家族，a)如找到，则看其有无子进程，如有:再调用撤销进程原语继续查找，若无，继续执行B b)若未找到，调出错处理 B）释放该进程所占有的资源 C）释放该进程的PCB D）返回第23页，共74页。(3)阻塞原语的工作过程：阻塞原语的工作过程：A）保存当前进程的CPU现场B）将其状态修改为等待状态C）将其插入对应的等待队列D）转进程调度程序(4)唤醒原语的工作过程：唤醒原语的工作过程：A）根据唤醒原因，从对应的等待队列中摘下一PCBB）将其状态修改为就绪状态C）将其插入就绪队列D）转进程调度程序或返回第24页，共74页。有关概
17、念有关概念:1.临界资源临界资源：在一段时间内只允许一个进程使用的资源 2.临界区（临界段）：临界区（临界段）：进程中访问临界资源的代码段 3.间接制约：间接制约：由共享公有资源而造成的对并发进程执行速度的间接制约，称为间接制约；受相互间接制约的各进程在推进顺序上是任意的。4.直接制约：直接制约：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程的直接制约。3.5 进程互斥第25页，共74页。5.进程互斥：进程互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共
18、享该资源的并发进程同时进入临界区称为互斥。6.临界段设计原则（互斥执行准则）：临界段设计原则（互斥执行准则）：（1）不能假设各并发进程的相对推进速度，即各进程享有平等的、独立的竞争共有资源的权利；（2）空闲让进；（3）若有多个进程同时要求进入，应在有限时间内，让其中之一进入。（4）进程只应在临界段内逗留有限的时间。第26页，共74页。互斥的实现互斥的实现 问题：有两个并发进程问题：有两个并发进程P0和和P1，互斥地共享单个资源。互斥地共享单个资源。设设P0和和P1是一个循环进程，每次只使用资源为一个有是一个循环进程，每次只使用资源为一个有限的时间间隔。限的时间间隔。一、软件实现方法一、软件实现
19、方法1.1.方法方法1:1:考虑用标志位来实现判别和处理考虑用标志位来实现判别和处理 用标志位flagi来标示进程i是否在临界段中执行，当flagi为真，则表示它正在执行临界段；反之不在临界段中执行。那么我们的临界区就可以如下设计那么我们的临界区就可以如下设计：第27页，共74页。#definefalse0#definetrue1 int flag2=0，0；Pi：do while（flagj）；flagi=true；Pi的临界段代码CSi；flagi=false；while（true）；第28页，共74页。2.方法2 用一个指针turn来指示应该哪个进程进入临界段。若turn=i，则进程Pi
20、进入临界段。Pi:int turn=0；dowhile（turn！=i）；Pi的临界段代码CSi；turn=j；while（true）；第29页，共74页。二、硬件实现方法二、硬件实现方法 1.临界段问题存在的原因：多个进程共同访问、修改同一个公共变量。导致问题出现的具体原因：(1)在单机系统中：由于中断的原因，使得一个进程对一个公共变量先取其值检测，然后修改的这两个动作之间，可以插入其他进程对此公用变量的访问和修改，从而破坏了此公用变量的完整性和正确性。(2)在多机系统中：该公用变量数据的完整性和正确性的破坏，是由于多个处理机共享主存，使得某处理机可以插入另一处理机的两个存储访问周期之间，访
21、问并修改共享变量。第30页，共74页。2.实现功能的硬件指令：(1)TS指令,其功能描述如下：int TestandSet（int*flag）int tmp；tmp=*flag；*flag=true；return（tmp）；注意：其功能是由一条处理机指令完成的，其执行过程是连续的.第31页，共74页。用TS指令实现互斥的程序结构为：为临界资源设置一个锁变量lock,lock的值为true时表示临界资源正被访问，为false时空闲。do；while（TS（*lock）；进程的临界段代码CS；lock=false；while（true）第32页，共74页。(2)SWAP指令,其功能描述如下：swa
22、p（int*a，int*b）int tmp；tmp=*a；*a=*b；*b=tmp；第33页，共74页。用TS指令实现互斥的程序结构为：(lock的意义同上)do；key=true；do swap（lock，key）；while（key=true）；进程的临界段代码CS；lock=false；while（true）;第34页，共74页。信号量和P、V原语 1.信号量（信号灯）1）问题的引入：为临界资源S设置锁key,当key为1时，资源可用，否则不可用。lock(keyS)测试key,若key为1，则将key赋值为0并退出，unlock(keyS)则将key赋值为1。结果：容易导致一个进程饥饿
23、。结果：容易导致一个进程饥饿。PA:A:lock(keyS)unlock(keyS)GOTO APB:B:lock(keyS)unlock(keyS)GOTO B第35页，共74页。2）信号量定义：信号量定义：信号量：除赋初值外仅能由同步原语（P、V操作）对其操作的整型变量，其值与其所代表的资源使用情况有关.信号量的物理意义：当其值0时，代表可用资源的数量 当其值0时，其绝对值代表因请求使用该信号量所代表的资 源而被阻塞的进程数量3）建立一个信号量时，必须说明所建信号量所代表的意义和赋初值第36页，共74页。4）信号量的分类：按其数据类型分类：整型信号量记录型信号量 struct semaph
24、oreint value；pointer：*struct PCB；第37页，共74页。5）信号量的初值：由于信号量是代表资源的相关属性的，因此，其初值就应该为当前该资源的可使用数量。如：我们设定用信号量S代表系统内的打印机资源，系统内有5台打印机，则S的初值就应该为5。2.2.P P、V V原语原语 P、V原语是操作系统中提供的用于对进程之间相互推进速度进行控制的最基本的操作。它他操作的对象只能是信号量。第38页，共74页。1）P（sem）原语的主要动作：sem=sem-1 若sem=0，则返回 否则调用阻塞原语把当前进程阻塞 转进程调度程序 2）V（sem）原语的主要动作：sem=sem+1
25、 若sem 0，则返回 否则调用唤醒原语把当前阻塞队列中的对首进程唤醒或全部唤醒 转进程调度程序或返回第39页，共74页。P原语的实现P(sem):关中断lock(lockbit)/用于防止多个进程同时调用P,V操作valsem=valsem 1if valsem 0 调用阻塞原语相关功能 unlock(lockbit)开中断3、P、V原语的实现第40页，共74页。V原语的实现V(sem):关中断lock(lockbit)/用于防止多个进程同时调用P,V操作valsem=valsem+1if valsem=0 调用唤醒原语相关功能 unlock(lockbit)开中断第41页，共74页。4、P
26、、V原语实现互斥 用用P P、V V原语实现进程互斥：原语实现进程互斥：(1)定义信号量，必须说明其所代表的资源 (2)设定信号量的初值：1 (3)在临界段进入区执行：P（信号量）操作 (4)在临界段退出区执行：V（信号量）操作第42页，共74页。3.6 进程同步一、同步的引入一、同步的引入Pc:C:Do 外部读一组数据存入存入局部变量CBuf中;While（CBuf !=Null）计算;计算结果送BUF GOTO CPp:P:Do 从BUF读一组数据存入存入局部变量PBuf中;While（PBuf !=Null）打印;清除Pbuf;GOTO P计算打印BUF第43页，共74页。二、同步的定义
27、 同步的定义：同步的定义：一组并发进程由于相互合作共同完成某种 任务，因而相互等待，使得各进程按一定的速度执行的过程。互斥也是一种特殊的同步互斥也是一种特殊的同步。私用信号量：只私用信号量：只与制约和被制约进程有关的信号量。用于同步的信号量。例：Buf1Buf2Bufn.PaPbu分析：分析：根据题意可知：只有当缓冲队列中有一个及一个以上满缓冲时，Pb才可以继续执行，否则等待Pa发送数据;第44页，共74页。同理只有当缓冲队列中有一个及一个以上空缓冲时，Pa才可以继续执行，否则等待Pb取走数据;因此，Pa和Pb之间存在同步关系。信号量的设定：信号量的设定：设代表满缓冲区数量的信号量为BufFu
28、ll设代表空缓冲区数量的信号量为BufEmpty设初值：BufFull=0,BufEmpty=n三、同步的实现 1、用消息通信实现进程的同步:Wait(消息名)和signal(消息名)实现。Wait(消息名)功能：若消息名变量为true,则退出Wait过程继续执行，若消息名变量为false,则等待，直到消息变量为true。Signal(消息名）功能：向合作进程发消息，并将其消息变量置为true。第45页，共74页。Pc:.A:wait(Bufempty)计算Buf计算结果Bufemptyfalsesignal(Buffull)gotoAPp:.B:wait(Buffull)打印Buf中的数据清
29、除Buf中的数据Buffullfalsesignal(Bufempty)gotoB消息变量的设置：设消息名Bufempty表示Buf空，消息名Buffull表示Buf满 设Bufempty=true,Buffull=false第46页，共74页。生产者-消费者问题分析 分析生产者进程和消费者进程间的同步互斥关系 1）生产者进程间（互斥）2）消费者进程间（互斥）3）生产者-消费者之间（同步互斥）2、用P、V实现进程同步示例1 2 3.nP1P2PmC1C2Cn第47页，共74页。信号量设定:设代表非空缓冲区数量的信号量为full，代表空缓冲区数量的信号量为avail，代表缓冲区资源使用情况的信号
30、量为mutex（互斥）设定初值：full=0,avail=n,mutex=1 书写算法：1.生产者：首先申请空缓冲资源，若无则等待 申请占用缓冲区(Why)查找空闲的缓冲区，在找到的空缓冲区中填入数据，置满缓冲标志 放弃对缓冲区的占用，增加可用满缓冲数量第48页，共74页。2.消费者：首先申请满缓冲资源，若无则等待 申请占用缓冲区(Why)查找满缓冲区，从找到的满缓冲区中取走数据，置空缓冲标志 放弃对缓冲区的占用，增加可用空缓冲数量 信号量初值设定原则（用于同步和互斥）：进程执行之前该信号量所代表的资源的可用数量就是该信号量的初值。第49页，共74页。算法（1）生产者：begin P(avai
31、l);P(mutex);送数据入缓冲区某单元；V(full);V(mutex);end;（2）消费者：begin P(full);P(mutex);取缓冲区某单元数据；V(avail);V(mutex);end;第50页，共74页。3.7 进程通信进程通信：进程间数据的传递过程。进程通信分类：1.低级通信：进程之间传送数据量很小，一般都是用来传送控制信息，从而实现进程之间的同步和互斥。2.高级通信：进程之间进行大批量数据传送的通信方式。其主要目的是为了交换信息。3.7.1 进程的通信方式（1）主从式：处于通信中的两进程其中之一处于支配地 位，而另外一个进程处于被支配地位。特点：主进程可以自由地
32、使用从进程的资源或数据 从进程的动作受主进程的控制；主进程和从进程之间的关系是固定的。第51页，共74页。（2）会话式：也就是通常所说的客户/服务器方式。处 于通信中的两进程其中之一是专门提供某种服务的服务器进程，而另外一个是需要使用该服务的进程。特点：客户进程使用服务之前需要得到服务器进程许可；服务器进程根据客户进程要求提供服务，但对所提供服务的控制由服务器进程完成。客户进程和服务器进程在进行通信时有固定的连接关系。（3）消息或邮箱通信方式：处于通信中进程没有直接的连接或依附关系。发送进程不管接收进程是否已经准备好，都要发送消息到消息缓冲区或邮箱，而接收进程可以根据需要随时收取消息。第52页
33、，共74页。特点：只有存在空缓冲区或邮箱时才能发送消息 发送进程与接收进程无直接连接 发送进程和接收进程之间存在缓冲区或邮箱，用来存放被传送消息。(4)共享存储区方式 处于通信中的两进程通过共享同一数据区来达到互通信息的目的。这个共享数据区是每个互通进程空间的一个组成部分。第53页，共74页。3.7.2几种具体的通信方式一、消息缓冲机制1、通信方式发送进程在发送之前，先在自己的内存空间中设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其发送出去。接收进程在接受之前，在自己的内存空间中设置相应的接收区，然后用接收过程接受消息。2、通信的必要条件在发送进程将消息写入缓冲区和把缓冲区挂入接
34、收进程的消息队列时，应禁止其他进程对消息队列的访问，接收进程从消息队列取消息缓冲时，也应禁止其他进程对消息队列的访问（即消息队列是临界资源，需互斥访问）当缓冲区中无消息时，接收进程不能接收任何消息。3、算法第54页，共74页。通过以上分析，设信号量mutex控制对缓冲区的互斥访问，初值为1，设sm为接收进程的私用信号量，初值为0。发送进程调用过程send(m)将消息送往缓冲区，接收进程调用receive(m)将消息m从缓冲区读入自己的数据区。发送过程：Send(m):begin 向系统申请一个消息缓冲区；P(mutex);将发送区消息m送入新申请的消息缓冲区；把消息缓冲区挂入接收进程的消息队列
35、；V(mutex);V(sm);end.第55页，共74页。接收过程：receive(m):begin P(sm);P(mutex);摘下消息队列中的消息m；将消息m从缓冲区复制到接受区；释放缓冲区；V(mutex);end.第56页，共74页。二、邮箱通信1、通信方式概述：由发送进程申请建立一与接收进程连接的邮箱，双方通过邮箱交换信息，邮箱可视为发送进程与接收进程之间的大小固定的私有数据结构。邮箱的结构发送进程发送进程邮箱头邮箱头 邮箱体邮箱体接收进程接收进程 deposit(m)remove(m)2、通信的必要条件（一对一发送和接收为例）发送消息时，邮箱中至少要有一个空格能存放消息接收消息
36、时，邮箱中至少要有一个消息存在第57页，共74页。3、通信算法由上述分析可知，发送进程和接收进程之间存在同步关系，可以设以下信号量：fromnum:表示邮箱中的空格数，初值为n,（n为总格数）mesnum:表示邮箱中的消息个数，初值为0发送过程deposit(m):begin local x P(fromnum)选择空格x 将消息放入空格x，置格x的标志为满V(mesnum)end.第58页，共74页。发送过程remove(m):begin local x P(mesnum)选择满格x 将满格x的消息取出放入m中，置格x的标志为空V(fromnum)end.三、管道通信（以无名管道为例）1、通
37、信方式管道为建立管道的进程及其子孙进程提供了一条以比特流方式传送消息的通信管道。管道在逻辑上被看作文件，物理上是由文件系统的高速缓冲区构成。第59页，共74页。发送：发送进程用文件系统的系统调用write(fd1,buf,size)，把 buf中长度为size的消息送入管道入口fd1接收：接收进程则使用系统调用read(fd0,buf,size)从管道出口fd0读出size字符的消息送入buf中。注意：管道按FIFO(先进先出）方式传送消息，且为单向传送。2、算法先定义一个整型：int fd2，其中fd1 为写入端，fd0为读出端，然后用系统调用pipe(fd)建立管道，最后调用write,r
38、ead完成具体的读写。3、示例#include main()int x,fd2;第60页，共74页。char buf30,s30;pipe(fd)；/*创建管道*/while(x=fork()=-1);/*创建字进程失败时，循环*/if(x=0)sprintf(buf,”This is an example n”);write(fd1,buf,30);/*写管道*/exit(0);else wait(0);read(fd0,s,30);/*读管道*/printf(“%s”,s);第61页，共74页。3.8死锁问题3.8.1 死锁的概念1.死锁的定义：死锁是一组并发进程，它们共享系统的某些资源，
39、该组进程中每个进程都已经占有了部分资源，但都在不释放自己占有资源的情况下要求获得被其它进程已经占有的资源，从而造成它们相互等待，永远不能继续推进的状态。2.死锁的起因：并发进程的资源竞争。产生死锁的根本原因是：（1）系统资源不足（2）进程推进进度不合理第62页，共74页。例：设有两个进程Pa和Pb，它们都需要使用系统内的打印机和输入机。它们的算法设计如下：设信号量S1代表输入机资源可用数量，S1=1设信号量S2代表打印机资源可用数量，S2=1Pa:P（S2）P（S1）V（S2）V（S1）Pa:P（S1）P（S2）V（S1）V（S2）第63页，共74页。3.产生死锁的必要条件：（1）互斥条件 （
40、2）不剥夺条件 （3）部分分配条件 （4）环路条件（循环等待条件）3.8.2 死锁的排除方法（静态措施）1.死锁的预防：打破死锁四个必要条件之一（1）打破互斥条件互斥条件是由于设备本身特性所决定的，不能简单的把其打破；只有通过改造设备特性实现。具体的办法是采用Spooling技术，把独占设备改造成共享设备来实现。第64页，共74页。（2）打破部分分配条件采用设备的静态预先分配办法采用设备的静态预先分配办法，具体作法是：作业调度程序在选择作业时，只选择那些系统能满足其运行时所需的全部资源的作业投入运行，并且在作业运行前，将其所需的全部资源一次性地分配给该作业。缺点：作业的周转时间被加长，系统资源
41、的使用率被降低。（3）打破环路条件采用有序资源使用法，具体作法是：系统把所有的资源类分配一个唯一的序号，如 输入机=1，打印机=2，。并且要求用户进程均应严格按序号递增的次序来请求资源。缺点：设备的利用率仍然不高。第65页，共74页。2.死锁的避免死锁的避免是动态的预防措施，系统允许进程动态地申请资源，如果措施得当，可以使系统获得较为满意的系统性能。具体的办法是具体的办法是：系统为进程分配资源之前，首先对系统的安全性进行计算，如果为进程分配了所需资源后，系统仍处于安全状态，那么就把资源分配给该进程，反之则不为该进程分配资源。比较著名的算法：银行家算法：该问题是研究一个银行家如何将其总数一定的现
42、金，安全的借给若干个顾客，使这些顾客既能满足对资金的要求又能完成其交易，也使银行家可以收回自己的资金不至于破产。第66页，共74页。安全状态与不安全状态安全状态：是指系统能按某种进程推进顺序（p1,p2,pn）,来为每个进程其所需资源，直至最大需求，使每个进程都能顺利完成其任务。只要系统存在这样的安全序列,则称系统处于安全状态。不安全状态：若系统不存在这样的安全序列,则称系统处于不安全状态。安全状态的例子假定系统有三个进程P1,P2和P3，共有12台磁带机，进程P1、P2、P3分别要求10台、4台和9台，设在T0时刻P1、P2、P3已分别获得5台、2台和2台，尚有2台空闲磁带机未分配出去，分配
43、情况如下所示：第67页，共74页。进程号最大需求（台）已分配（台）未分配（台）P11053P242P392经分析，在T0时刻系统是安全的，因为存在一个安全序列向不安全状态的转换若在T0时刻，P3请求1台磁带机，若满足其要求，则系统进入不安全状态。（为什么）银行家算法（1）数据结构可用资源向量Available(R1,R2,.Rm)Available(R1,R2,.Rm)中每一个元素代表一类可用的资源数目；第68页，共74页。最大需求矩阵Max 这是一个N M的矩阵，它定义了系统中的n个进程的每一个进程，对M类资源的最大需求，若Max(i,j)=K,表示进程i对j类资源的最大需求数目是K。分配矩
44、阵Allocation它是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一个进程的资源数。若Allocation(i,j)=K,表示进程I当前已分得j类资源的数目为K。需求矩阵Need 它是一个nm的矩阵,用以表示每一个进程尚需的各类资源数，若Need(i,j)=K,表示进程i需要j类资源K个，才能完成其任务。上述矩阵的关系：Need(i,j)=Max(i,j)-Allocation(i,j)第69页，共74页。（2）银行家算法设Requesti(r1,r2,.rm)是进程Pi的请求向量，若Requesti(j)=K,表示进程Pi需要K个j类资源，当进程发出请求后，系统将进行下述步骤的
45、检查：如果Requesti=Needi,则转步骤2，否则，认为出错，因为它请求的资源数超出了它的需求最大数；如果Requesti=Available，则转步骤3，否则，表示尚无足够资源，Pi必须等待；系统试探把进程需要的资源分给它，并修改以下数据结构中的数值：Available=Available-Request;Allocation=Allocation+Request;Needi=Needi-Request系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，则实施正式分配，否则，将试探分配作废，恢复原来的资源分配状态，让Pi等待。第70页，共74页。3.死锁的检测和恢复（
46、1）死锁的检测：这是一种事后处理的措施。具体方法是：1.判断是否构成环路条件 有限状态转移图法2.周期性检测方法:类似银行家算法(2)死锁的恢复：检测出有死锁时的处理方法 具体方法有：（1）撤销所有死锁进程（2）退回到前一检查点并从此点重新启动进程。（3）逐个撤销死锁进程，直到死锁不存在（4）逐个抢占死锁进程资源直到死锁不存在第71页，共74页。3.9 线程 3.9.1 线程的概念1.概念：一个进程中的基本调度单位2.引入目的：提高系统执行效率，减少处理机空转和调度切换的时间，便于系统管理3.进程与线程的区别联系 进程是资源分配、处理机分配的最基本单位，每个进程拥有完整的虚拟地址空间，由程序、
47、数据、PCB组成。线程不是资源分配、处理机调度的最基本单位，它和其他同属同一进程的线程一起共享进程的虚拟地址空间，由线程控制表、栈、寄存器组成第72页，共74页。3.9.2 线程的适用范围1.服务器中的文件管理或通信控制2.前后台处理3.异步处理3.9.3 线程的执行特性1.线程的基本状态：执行、就绪、阻塞2.线程的5种基本操作：（1）派生（2）阻塞（3）激活（4）调度（5）结束第73页，共74页。3.9.4 线程的分类1.用户级线程：其管理过程全部由用户程序完成，操作系统核心只对进程进行管理2.系统级线程 其管理过程由操作系统内核完成。操作系统内核给应用程序提供相应的系统调用和应用程序接口API,使用户程序可以创建、执行、撤销线程。可以并发和并行执行第74页，共74页。
