《操作系统原理及应用(Linux)》第2章 进程管理

第2章进程管理本章学习目标本章主要介绍进程的概念、状态、构成以及Linux进程的相关知识。掌握进程的概念掌握进程的描述、状态及转换理解进程的特征了解Linux进程的描述及进程通信掌握进程的同步与互斥，并能灵活运用理解线程的概念及特征第2章进程管理*教学内容2.1进程的基本概念2.2进程的描述2.3进程控制2.4进程的同步与互斥2.5进程同步问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 举例2.6进程通信2.7线程本章小结*2.1进程的基本概念2.1.1程序的顺序执行及其特征1．程序的顺序执行程序是人们要计算机完成的一些指令序列，是一个按严格次序、顺序执行的操作序列，是一个静态的概念。我们把一个具有独立功能的程序独占处理机，直到最后结束的过程称为程序的顺序执行。2．程序顺序执行时的特征（1）顺序性。（2）封闭性。（3）可再现性。第2章进程管理*2.1.2程序的并发执行及其特征1．并发执行的概念所谓程序的并发性，是指多道程序在同一时间间隔内同时发生。程序的并发执行可 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 为：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的一种执行方式。第2章进程管理*2．程序并发执行时的特征（1）间断性程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。（2）失去封闭性某程序在执行时，必然会受到其它程序的影响。（3）不可再现性在并发环境下，同一个程序执行多次，执行的过程可能不同。用程序作为描述其执行过程以及共享资源的基本单位是不合适的。因此引入了进程作为描述程序的执行过程、共享资源的基本单位。第2章进程管理*2.1.3进程的定义与特征1．进程的定义人们对进程下过许多定义。现列举其中的几种：（1）进程是程序的一次执行。（2）进程是可以和别的进程并发执行的计算。（3）进程就是一个程序在给定活动空间和初始条件下，在一个处理机上的执行过程。（4）进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单位（5）进程是动态的，有生命周期的活动。内核可以创建一个进程，最终将由内核终止该进程使其消亡。第2章进程管理*进程和程序之间的关系进程和程序是两个完全不同的概念，但又有密切的联系。它们之间的主要区别是：（1）程序是静态的概念，；而进程则是程序的一次执行过程。它是动态的概念。（2）进程是一个能独立运行的单位，能与其它进程并发执行；而程序是不能作为一个独立运行的单位而并发执行的。（3）程序和进程无一一对应的关系。（4）各个进程在并发执行过程中会产生相互制约关系，而程序本身是静态的，不存在这种异步特征。第2章进程管理*2．进程的特征从进程与程序的区别可以看出，进程具有如下特征：（1）动态性动态性是进程最基本的特性。进程由创建而产生，由调度而执行，因得不到资源而暂停执行，以及因撤消而消亡。（2）并发性这是指多个进程实体，同存于内存中，能在一段时间段内同时执行。并发性是进程的重要特征，同时也是操作系统的重要特征。提高并发性，可以提高系统的效率。（3）独立性进程是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。（4）异步性这是指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。（5）结构特征从结构上看，进程实体是由程序段、数据段及进程控制块三部分组成，也称这三部分为进程映像。第2章进程管理*2.1.4进程的基本状态及转换1．进程的三个基本状态进程通常至少有三种基本状态：（1）就绪状态（ready）进程运行所需的外部条件满足，但因为其它进程已占用CPU，所以暂时不能运行。（2）执行状态(running)外部条件满足，进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态。（3）阻塞状态(blocked)进程因等待某种事件发生，而暂时不能运行的状态，称为阻塞状态，也称为等待状态。系统中处于这种状态的进程可能有多个，通常将它们排成一个队列，也有的系统则根据阻塞原因的不同将这些进程排成多个队列。第2章进程管理*2．进程状态的转换对于一个系统中处于就绪状态的进程，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它由就绪态转变为执行状态。正在执行的进程也称为当前进程，如果因分配给它的时间片已用完而被暂停执行时，该进程便由执行状态又回到就绪状态；一个处在执行状态的进程，如果因发生某事件而使进程的执行受阻，使之无法继续执行，该进程将由执行状态转变为阻塞状态。一个处于阻塞状态的进程，当它所需的外部事件满足，它应由阻塞状态变为就绪状态。第2章进程管理*程执行完成或撤消阻塞状态就绪状态调度用片间时进程创建进等待某事件发生如I/O请求外部事件发生图2-1进程的基本状态及转换图完第2章进程管理*3．引入挂起状态时的进程状态所谓挂起状态，实际上就是一种静止的状态。一个进程被挂起后，不管它是否在就绪状态，系统都不分配给它处理机。在引入挂起状态后，进程之间的状态转换除了四种基本状态转换以外，又增加了以下几种：（1）活动就绪——静止就绪。（2）活动阻塞——静止阻塞。（3）静止就绪——活动就绪。（4）静止阻塞——活动阻塞。第2章进程管理*执行外部事件满足外挂起激活挂起挂激活活动就绪静止就绪活动阻塞静止阻塞调度图2-2具有挂起状态的进程状态转换等部事件外待起部条件满足完成或撤消第2章进程管理*2.1.5Linux进程的状态Linux系统的一个任务总体上有以下几种状态：（1）运行状态（running）该状态对应state取值为TASK_RUNNING。（2）等待状态（waiting）（3）中断处理状态（interruptroutine）此状态对应state取值TASK_RUNNING。（4）系统调用期间（systemcall）此状态对应state取值TASK_RUNNING。（5）从系统调用返回（returnfromsystemcall）第2章进程管理*（6）就绪态（ready）处于此状态的进程正在竞争处理机，但此刻处理机正在为另一个进程服务。此状态对应state取值TASK_RUNNING。Linux系统内核在进程控制块中用state成员描述进程当前的状态，并明确定义了5种进程状态。它们分别是：（1）TASK-RUNNING状态，Linux系统中的运行状态实际包含了上述基本状态中的执行和就绪两种状态。（2）TASK-INTERRUPTIBLE状态，可中断的等待态。进程正在等待某些事件。（3）TASK-UNINTERRUPTIBLE状态，等待态，不可中断。（4）TASK-ZOMBIE状态，僵死态。（5）TASK-STOPPED状态，暂停态。第2章进程管理*Linux任务状态转换图运行态从系统调用返回中断例程系统调用等待就绪调度中断用户态系统态图2-3Linux任务状态转换图2.2进程的描述进程实体通常是由程序、数据集合和PCB这三部分构成，也称为“进程映象”。数据集合程序部分PCB第2章进程管理*图2-4进程的一般组成模型2.2.1进程控制块PCBPCB集中反映一个进程的动态特征，当系统创建了一个新进程时，就为它建立一个PCB；当进程终止后，系统回收其PCB，该进程在系统中就不存在了。所以，PCB是进程存在的惟一标志。可以按照功能将PCB分成四个组成部分：进程标识符、处理机状态、进程调度信息、进程控制信息。第2章进程管理*1．进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：（1）进程内部标识符。（2）进程外部标识符。2．处理机状态：由各种寄存器中的内容组成。3．进程调度信息（1）进程状态。（2）进程优先级。（3）进程调度所需要的其它信息。（4）事件，或阻塞原因。4．进程控制信息，包括：（1）程序和数据的地址；（2）进程同步和通信机制；（3）资源清单；（4）链接指针。第2章进程管理*2.2.2进程控制块的组织方式各进程的PCB有如下几种组织方式：线性方式、链接方式和索引方式。1．线性方式将各进程的PCB依次放入一个表中，结构如下图所示。PCBnPCBn-1……PCB3PCB2PCB1第2章进程管理*图2-5PCB的线性组织方式2．链接方式链接方式是经常采用的方式。其原理是：按照进程的不同状态分别将其放在不同的队列。Linux操作系统就是应用这种进程控制块组织方式。运行队列指针就绪队列指针PCBPCBPCB0阻塞队列1指针阻塞队列2指针PCB0PCBPCBPCB0PCBPCBPCB0图2-6PCB链接队列示意图第2章进程管理*3．索引方式系统根据所有进程的状态建立几张索引表。阻塞索引表就绪索引表执行指针就绪表指针阻塞表指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7图2-7PCB索引结构示意图第2章进程管理*2.2.3Linux进程的PCBLinux系统中的进程称为任务。该系统的进程控制块PCB用一个称为task-struct的结构体来描述，Linux系统PCB包含以下信息：1．进程描述信息（1）进程标识号（pid，processidentifier）（2）用户和组标识（userandgroupidentifier）（3）连接信息（Links）2．进程控制信息（1）进程当前状态（2）调度信息（3）记时信息（4）通信信息第2章进程管理*Linux支持典型的UNIX进程间通信机制——信号、管道，也支持SystemⅤ通信机制——共享内存、信号量和消息队列。3．进程资源信息记录了与该进程有关的存储器的各种地址和资料、文件系统以及打开文件的信息等等。4．CPU现场信息第2章进程管理*2.3进程控制所谓进程控制，就是系统使用一引起具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。原语：把系统态下执行的某些具有特定功能并且不可被中断的程序段称为原语。原语的特点是：系统程序、不可被中断。系统在创建、撤消一个进程以及要改变进程的状态时，都要调用相应的程序段来完成这些功能。用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等。第2章进程管理*2.3.1进程的创建与终止1．进程的创建导致进程创建的事件有：用户登录、作业调度、为用户提供服务等。创建原语Creat()，通过下述步骤创建一个进程。（1）申请空白PCB。（2）为新进程分配资源。（3）初始化进程控制块。（4）将新建进程插入就绪态队列。2．进程的终止过程在进程中，操作系统调用进程终止原语，终止本进程。过程如下：（1）根据被终止进程的标识符，从PCB队列中检索出该进程的PCB，从中读出该进程的状态。。（2）若被终止进程正处于执行状态，应立即终止该进程的执行，该进程被终止后应重新进程调度。（3）检查该进程有无子孙进程，若有，则应将其所有子孙进程终止。（4）释放终止的进程所占有的资源，将其归还它的父进程或者系统。（5）将被终止的进程从它的PCB队列中移出。第2章进程管理*3．进程阻塞与进程唤醒进程状态的转换需要通过进程之间的同步或通信机构来实现，也可直接使用“阻塞原语”和“唤醒原语”来实现。（1）进程的阻塞当一个进程所等待的某一事件尚未发生时，该进程调用阻塞原语block()将自己阻塞，转换为等待状态。（2）进程的唤醒处于等待状态的进程，只有当该进程所等待的外部事件发生时，才由发生该事件的进程调用唤醒原语wakeup()将它唤醒。第2章进程管理*2.3.2几个相关的Linux系统调用在Linux系统中，系统向用户提供了一些对进程进行控制的系统调用。常用的有：1．fork()系统调用Linux利用fork()系统调用创建一个新进程。2．Exec系统调用利用exec系统调用执行另一个程序。3．exit()系统调用父进程在创建子进程时，应在进程的末尾写一条exit，使子进程自我终止。4．wait系统调用将调用进程挂起，直至其子进程因暂停或终止而发来软中断信号为止。第2章进程管理*2.3.3进程的阻塞与唤醒实现进程的执行状态到等待状态，又由等待状态到就绪状态转换的两种原语，分别为阻塞原语与唤醒原语。入口保存该进程的CPU现场字置该进程的状态阻塞进程PCB进入等待队列转进程调度入口从等待队列取被唤醒进程将被唤醒进程置为就绪态被唤醒进程插入就绪队列转进程调度或返回图2-8阻塞原语的实现图2-9唤醒原语的实现第2章进程管理*2.4进程的同步与互斥2.4.1临界资源的概念1．临界资源两个或两个以上的进程不能同时使用的资源为临界资源。临界资源可能是一些独占设备，如打印机、磁带机等；也可能是一些共享变量、表格、链表等。第2章进程管理*2．临界区每个进程中访问临界资源的那段代码称为临界区。在临界区前面增加一段用于进行检查的代码，把这段代码称为进入区；相应地，在临界区后面再加一段用于退出临界区的代码，称为退出区。进程中除去上述进入区和退出区，其它部分的代码，称为剩余区。这样，可将一个访问临界资源的进程描述如下：repeat进入区；　临界区；　退出区；　剩余区；untilfalse;第2章进程管理*2.4.2进程的互斥与同步1．同步与互斥的概念所谓进程互斥，是指多个进程不能同时使用同一个临界资源CR。即两个或两个以上的进程必须互斥地使用临界资源，或不能同时进入临界区CS。两个逻辑上完全独立、毫无关系的进程，由于竞争同一个资源而相互制约，就称为进程的互斥。所谓进程同步，是指有协作关系的进程之间，要不断地调整它们之间的相对速度或执行过程，以保证临界资源的合理利用和进程的顺利执行。实现进程同步的机制称为进程同步机制。2．同步机制应遵循的规则所有同步机制都应遵循下列准则：（1）空闲让进。（2）忙则等待。（3）有限等待。（4）让权等待。第2章进程管理*2.4.3锁机制实现互斥的一种软件是采用锁机制，即提供一对上锁（Lock）和开锁（UnLock）原语，以及一个锁变量w（或者是锁位１个bit）。加锁及解锁原语可描述如下：加锁原语：Lockw：L：ifw=1thengotoLElsew:=1开锁原语：UnLockw：w：=0;第2章进程管理*2.4.4信号量机制申请和释放临界资源的两个原语操作：wait操作和signal操作，有时也称为Ｐ操作和Ｖ操作。信号量（Semaphore），也叫做信号灯，它是在信号量同步机制中用于实现进程的同步和互斥的有效数据结构。我们可以为每类资源设置一个信号量。它有多种类型的数据结构，即：整型信号量、记录型信号量、ＡＮＤ型信号量及信号量集等。第2章进程管理*1．整型信号量整型信号量的数值表示当前系统中可用的该类临界资源的数量。如设置整型信号量s，则s的值意义为：s>0，则s的值表示系统中空闲的该类临界资源的个数；s=0，则表示系统中该类临界资源刚好全部被占用，而且没有进程在等待该临界资源；s<0，则s的绝对值表示系统中的进程等待该类临界资源的个数；第2章进程管理*2．记录型信号量记录型信号量的数据结构由两部分构成。例如：定义记录型信号量Ｓ，则：s的值表示系统中可用的该类临界资源的数量，而Ｌ为进程链表指针，指向等待该类资源的PCB队列。设变量Ｓ为记录型信号量，则wait（Ｓ）操作和signal（Ｓ）操作的流程如下图所示：第2章进程管理*Wati(S)是Wati(S)s=s-1申请到资源本进程继续本进程入阻塞队列s≥0否转进程调度图2-10Wait操作原语流是signal(S)s=s+1唤醒一阻塞态进程s≤0否图2-11signal操作原语流释放该类资源本进程继续第2章进程管理*申请临界资源的原语wait操作可描述为：procedurewait(S)varS:semaphore;begins:=s-1;ifs≥0then本进程继续；else{将本进程放入阻塞态队列；转进程调度;}end释放临界资源的原语signal操作可描述为：proceduresignal(S)varS:semaphore;begins:=s+1;ifs≤0then唤醒指针L所指的阻塞态进程；end第2章进程管理*3．ＡＮＤ型信号量ＡＮＤ同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完成后再一起释放。只要有一个资源尚未能分配给进程，其它所有可能分配的资源，也不能分配给它。也称为ＡＮＤ同步。AND型信号量集机制可描述如下：第2章进程管理*Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endforelse将该进程放入阻塞态队列；endifSsignal(S1,S2,…,Sn)fori:=1tondoSi=Si+1;唤醒所有因Si不满足而进入阻塞队列的进程；endfor;第2章进程管理*4．信号量集信号量集机制的基本思想是：在AND型信号量集的基础上进行扩充，进程对信号量Si的测试值为ti（用于信号量的判断，即Si>=ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si=Si-d1和Si=Si+d1）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般“信号量集”的几种特定情况：（1）Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配；（2）Swait(S,1,1)表示互斥信号量；（3）Swait(S,1,0)作为一个可控开关（当S≥1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）；（4）“信号量集”未必成对使用Swait和Ssignal。如：一起申请，但可以不一起释放。第2章进程管理*2.5进程同步问题举例2.5.1生产者—消费者问题1．问题的描述有一批生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为方便生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。第2章进程管理*n-1n-2………i……210假设初始情况下缓冲池为空，即counter＝０。为在生产者—消费者问题中实现各进程的同步，可设下列信号量：（假设初始情况下没有进程使用缓冲池，且缓冲池中各缓冲区都是空的。）mutex：互斥使用缓冲池信号量，由于初始情况下无进程使用缓冲池，故初值mutex=１；empty：使用缓冲池中空缓冲区的信号量，由于初始情况下所有缓冲区为空，故初值empty=n；full：使用缓冲池中满缓冲区的信号量，由于初始情况下没有缓冲区存放产品，故初值full＝０。设开始时生产者进程存放产品和消费者进程取产品时，都从第０号缓冲区开始，并设这些生产者和消费者地位相当，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。第2章进程管理*inout图2-12生产者—消费者问题中的缓冲池算法及程序Varmutex,empty,full:semaphore∶=1,n,0;　　／＊定义信号量并赋初值＊／buffer:array［0,…,n-1］ofitem;in,out:integer∶=0,0;　　　　　／＊定义存取指针的初始位置＊／beginparbegin生产者进程proceduer：beginrepeat…生产一件产品;…wait(empty);wait(mutex);将产品放入下一个缓冲区;in∶=(in+1)modn;signal(mutex);signal(full);untilfalse;end第2章进程管理*消费者进程consumer：beginrepeatwait(full);wait(mutex);从下一个缓冲区中取走一件产品;out∶=(out+1)modn;signal(mutex);signal(empty);消费这件产品;untilfalse;endparendend第2章进程管理*4．在生产者—消费者问题中应注意：（１）在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。（２）对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的进程中，这样保证生产者进程和消费者进程的同步及交替执行。（３）在每个进程中，多个wait操作顺序不能颠倒，而signal操作的次序是无关紧要的。第2章进程管理*2.5.2读者—写者问题1．问题的提出一文件Ｆ可以被多个并发进程共享，将这些访问该文件的进程按访问方式分为两类：一类只能读共享对象的内容，把这类进程称为读进程或读者；另一类进程则要更新（写）共享对象文件F，将这些进程称为写进程或写者。试用Wait、Signal操作解决各进程间的同步问题。2．问题的分析显然，多个读者同时读一个共享对象是可以的，然而一个写者不能与其它任何读者或写者同时共享该文件。亦即：在使用共享文件时，一个写进程与其它所有进程都是互斥的。但多个读进程之间不存在互斥的现象。如图2-13所示。第2章进程管理*共享文件F写进程W读进程R1读进程Rn…图2-13读者—写者问题设读进程为reader，写进程为writer。为实现reader与writer进程间的同步与互斥，设如下变量及信号量：wmutex：互斥使用该共享文件信号量。如：写进程write与读进程reader在使用文件时是互斥的；共享文件只有一个，设初始情况未被使用，则初值为1。readcount：整型变量，表示正在读的进程个数。初值为0。该变量属临界资源。rmutex：计数器readcount的信号量。因为readcount是一个可被多个reader进程访问的临界资源，为此设一信号量。设初始状态下无进程读和写，故rmutex的初值设为1。第2章进程管理*由于多个进程可以同时读，因此只要有一个reader进程在读，其它reader进程便不必申请该共享文件，直接读即可；若无文件在读，则第一个读文件的进程必须做申请该文件的操作。只要有read进程在执行，则不允许writer进程去写。因此，仅当readcount=0,即无reader进程在读时，reader进程才需要执行wait(wmutex)操作。若wait(wmutex)操作成功，reader进程便可去读，相应地，做readcount+1操作。同理，仅当reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让writer进程写。第2章进程管理*3．算法及程序读者—写者问题可描述如下：Var:rmutex,wmutex:semaphore:=1,1;Readcount:integer:=0;beginparbegin读者进程：Reader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);readcount:=Readcount+1;signal(rmutex);第2章进程管理*…进行读操作;…wait(rmutex);readcount:=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;end写者进程：writer:beginrepeatwait(wmutex);执行写操作;signal(wmutex);untilfalse;endparendend第2章进程管理*4．注意事项及提示（1）对于写进程，共享文件是临界资源；而对于读进程，该文件不是临界资源。（2）整型变量readcount是临界资源，所以在使用前后要进行Wait、Signal操作。第2章进程管理*2.5.3哲学家进餐问题1．问题的提出设有5个哲学家围坐在一张圆桌前吃饭。桌上有5只筷子，在每人之间放一只。哲学家要吃饭时，只有分别从左、右两边都拿到筷子时，才能吃饭。如果筷子已在他人手上，则该哲学家必须等待到他人吃完后才能拿到筷子；任何一个哲学家在自己未拿到两只筷子吃饭之前，决不放下自己手里的筷子。试描述5位哲学家吃饭的进程。第2章进程管理*图2-14哲学家就餐餐问题第2章进程管理*2．问题分析放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以为每一只筷子设置一个信号量，由这五个信号量构成信号量数组：Varchopstick:array［0,…,4］ofsemaphore;设初始条件下，所有哲学家都未吃，故所有信号量均被初始化为1。3．实现方法假设每一位哲学家拿筷子的方法都是：先拿起左边的筷子，再拿起右边的筷子，则第i位哲学家的活动可描述为：第2章进程管理*Pi()beginVarchopstick:array［0,…,4］ofmaphore=[1,1,1,1,1];repeatwait(chopstick［i］);wait(chopstick［(i+1)mod5］);eat;…signal(chopstick［i］);signal(chopstick［(i+1)mod5］);think;untilfalse;end第2章进程管理*以上算法存在一个问题：假设5个哲学家同时拿起左边的筷子，那么再去拿右边的筷子时，就会产生死锁。下面给出几种解决方法。（1）至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。（2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。最后总会有一位哲学家能获得两只筷子而进餐。具体程序段参看实训教材。第2章进程管理*4．不产生死锁的哲学家就餐问题算法2.6进程通信进程间的信息交换称为进程通信。通常，进程间的通信分为两种：控制信息的传送与大量信息的传送。将进程间控制信息的交换称为低级通信，而把进程之间大批量数据的交换称为高级通信。进程的互斥与同步为低级通信方式，相应地，也称wait、signal操作为低级的通信原语。仅通过P、V操作或锁的方法是无法实现进程的高级通信的。高级通信方式可分为三大类：共享存储器系统、消息传递系统和管道通信系统。第2章进程管理*2.6.1共享存储器系统1．共享存储器系统的类型（1）基于共享数据结构的通信方式在这种通信方式中，要使各进程共用某些数据结构，借以实现各进程间的信息交换。如在生产者—消费者问题中，就是用有界缓冲区这种数据结构来实现通信的。这种通信方式是低效的，只适用于传递相对少量的数据。（2）基于共享存储区的通信方式。在存储器中划出了一块共享存储区，各进程可通过对共享存储区中的数据的读或写来实现通信。第2章进程管理*2．Linux共享存储区通信的实现（1）共享存储区的建立利用系统调用shmget()建立一块共享存储区。该系统调用将返回该共享存储区的描述符shmid；若尚未建立，便为进程建立一个指定大小的共享存储区。（2）共享存储区的操纵可以用shmctl()系统调用对共享存储区的状态信息进行查询，如其长度、所连接的进程数、创建者标识符等；也可设置或修改其属性，如共享存储区的许可权、当前连接的进程计数等；还可用来对共享存储区加锁或解锁，以及修改共享存储区标识符等。3.共享存储区的附接与断开在进程已经建立了共享存储区或已获得了其描述符后，还须利用系统调用shmat()将该共享存储区附接到用户给定的某个进程的虚地址shmaddr上，并指定该存储区的访问属性，即指明该区是只读，还是可读可写。此后，此共享存储区便成为该进程虚地址空间的一部分。进程可采取与对其它虚地址空间一样的存取方法来访问。当进程不再需要该共享存储区时，再利用系统调用shmdt()把该区与进程断开。4．几个相关系统调用共享存储区通信中常用的系统调用：（1）shmget(key,size,flag)：功能：获得一个共享存储区，若成功，其返回值为该共享存储区的描述符。（2）shmat(id,addr,flag)从逻辑上将一个共享存储区附接到进程的虚拟地址空间上。（3）shmdt(addr)：把一个共享存储区从指定进程的虚地址空间断开。（4）shmctl(id,cmd,buf)对与共享存储区关联的各种参数进行操作，从而对共享存储区进行控制。第2章进程管理*2.6.2消息传递系统在消息传递系统中，进程间的数据交换，是以格式化的消息（message）为单位的。程序员直接利用系统提供的一组通信命令进行通信。因实现方式的不同分为直接通信方式和间接通信方式。间接通信方式又称为信箱通信方式。信箱是一种数据结构，逻辑上可分为两部分：信箱头和信箱体。信箱头包含箱体的结构信息，信箱体由多个格子构成。信箱通信一般是进程之间的双向通信。第2章进程管理*1．直接通信方式这种通信是固定在一对进程之间。用来发送和接收消息。两条原语的形式如下：send(B,message);发送一个消息给接收进程B；receive(A,message);接收进程A发来的消息；通常情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：receive(id,message);其中，id为接收消息进程的标识符。2．间接通信方式间接通信方式又称为信箱通信方式。信箱是一种数据结构，逻辑上可分为两部分：信箱头和信箱体。信箱头包含箱体的结构信息，信箱体由多个格子构成，它实际上就是一个有界缓冲池。信箱通信一般是进程之间的双向通信。如图2-15所示。信箱体sendreceivereceivesend进程B信箱头图2-15进程的信箱通信方式进程A3．消息缓冲队列通信机制（1）消息缓冲队列通信机制中所用的主要数据结构是消息缓冲区。在设置消息缓冲队列时，还应添加用于对消息队列进行操作和实现同步的信号量，并将它们存入进程的PCB中。当一个发送进程要发送消息时，便形成一个消息，并发送给指定的接收进程。接收进程将所有的消息缓冲区链成一个队列，其队列首由接收进程PCB中的队列队首指针mq来指出。（2）发送原语（3）接收原语接收进程调用接收原语，从自己的消息缓冲队列中，选取第一个消息缓冲区，并将其中的数据复制到指定的消息接收区内。发送进程在发送消息之前，应先在自己的内存空间设置一发送区，然后调用发送原语，把消息发送给接收进程。4．Linux系统关于消息传递的相关系统调用（1）msgget(key,flag):功能：获得一个消息的描述符，该描述符指定一个消息队列以便用于其他系统调用。（2）msgsnd(id,msgp,size，flag);功能：发送一消息。（3）msgrcv(id,msgp,size,type,flag)功能：接受一消息。（4）msgctl(id,cmd,buf)：功能：查询一个消息描述符的状态,设置它的状态及删除一个消息描述符。2.6.3管道通信系统所谓管道，是指用于连接一个读进程和一个写进程，以实现他们之间通信的一个共享文件，又名pipe文件。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：（1）互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。（2）同步，指当读写进程使用pipe时，需要同步使用。（3）确定对方是否存在，只有确定了对方已存在时，才能进行通信。第2章进程管理*2.6.4信号通信机制1．信号的基本概念每个信号都对应一个正整数常量，即信号编号。信号机制具有以下三方面的功能：（1）发送信号。发送信号的程序用系统调用kill()实现；（2）预置对信号的处理方式。接收信号的程序用signal()来实现预置处理方式；（3）收受信号的进程按事先的规定完成对相应事件的处理。第2章进程管理*2．信号的发送信号的发送，是指由发送进程把信号送到指定进程的信号域的某一位上。进程用kill()向一个进程或一组进程发送一个信号。3．信号的处理对软中断信号的处理分三种情况进行：（1）如果进程收到的软中断是一个已决定要忽略的信号（function=1），进程不做任何处理便立即返回；（2）进程收到软中断后便退出（function=0）；（3）执行用户设置的软中断处理程序。4．相关的Linux系统调用（1）kill()功能：向一个或一组进程发送一个软中断信号。（2）signal()功能：预置对信号的处理方式，允许调用进程控制软中断信号。第2章进程管理*2.7线程线程是比进程更小的能独立运行的基本单位。2.7.1线程的基本概念线程（thead）是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。在引入线程的操作系统中，可以在一个进程内部进行线程切换，现场保护工作量小。线程与进程的比较：（1）进程是资源分配的基本单位。同一进程的所有线程共享该进程的所有资源。（2）线程是分配处理机的基本单位，它与资源分配无关。（3）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。（4）线程在执行过程中，需要协作同步。第2章进程管理*2.7.2线程的状态与转换操作线程有3种基本状态，即执行、阻塞和就绪。针对线程的3种基本状态，存在5种基本操作来转换线程的状态。它们是：1．派生（spawn）2．调度（schedule）3．阻塞（Block）4．激活（unblock）5．结束（Finish）第2章进程管理*2.7.3引入线程的好处引入线程的好处有以下几点：1．易于调度。2．提高了系统的效率。3．创建一个线程比创建一个进程花费的开销少，创建速度快。4．有利于发挥多处理器的功能，提高进程的并行性。第2章进程管理*2.7.4多线程的实现多线程机制是指操作系统支持在一个进程内执行多个线程的能力。多种系统支持多线程实现的方式并不完全相同。1．用户级线程用户级线程是由用户应用程序建立的，并由用户应用程序负责对这些线程进行调度和管理，操作系统内核并不知道有用户级线程的存在，只对进程进行管理。2．内核级线程内核级线程简称为KLT，通常也称为“纯KLT”方法。内核级线程中所有线程的创建、调度和管理全部由操作系统内核负责完成。3．用户级线程与核心态线程相结合的模式由于用户级线程和内核级线程各有其特色，因此，如果将两种方法结合起来，则可吸取两者的优点。将两种方法结合起来的系统称为多线程的操作系统。内核支持多线程的建立、调度和管理。同时系统中又提供使用线程库，允许用户应用程序建立、调度和管理用户级线程。本章小结进程是操作系统中的一个非常重要的概念。进程是程序的一次执行，同时它也是操作系统进行资源分配的单位。进程具有一些特征，是与程序有根本区别的概念。进程具有动态性、并发性、异步性、独立性的特性。反映进程动态性的是进程状态的变化。进程从创建到被撤消，要经过一些具有生命状态的活动。进程的三个基本状态包括阻塞、就绪、执行，除此之外，不同的操作系统还具有其它一些状态。进程的状态转换由相应的原语来完成。进程的并发执行是指，在同一时间间隔内多个进程同时发生。进程的并发特性反映在进程对资源的竞争以及由资源竞争所引起的对进程执行速度的制约。我们可以通过提高进程的并发性，来提高整个系统的效率。第2章进程管理*进程上下文由以下部分组成：进程控制块、正文段、数据段以及各种寄存器和堆栈中的值。进程控制块PCB是进程存在的惟一标志，它包含进程的运行信息和程序的控制信息。进程控制块在内存中的组织方式有：线性方式、链接方式和索引方式。对于Linux系统，我们可以通过几个常用的进程创建和控制的系统调用，实现对进程的控制。第2章进程管理*不能被多个进程同时使用的资源称为临界资源。将每个进程中访问临界资源的那段代码称为临界区。多个进程不能同时进入同一个临界区，叫做进程之间的互斥；多个进程在使用临界资源时，表现出来的相互协调、相互合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。具有同步关系的一组并发进程称为合作进程。实现进程的互斥和同步，可以用锁或P、V操作来实现。P操作是申请临界资源的原语操作，也称为wait操作；V操作是释放临界资源的原语操作，也称为signal操作。信号量是P、V操作的对象。第2章进程管理*进程通信可包括低级通信和高级通信。对于进程进行控制的通信是低级通信；传递大量数据的通信称为高级通信。高级通信包括：共享存储器系统、消息传递系统和管道通信系统。与进程概念密切相关的概念是线程。线程可看成是进程中指令的不同执行路线，它是为了提高操作系统的执行效率而引入的。线程又称为轻型进程，在有线程的操作系统中，它是操作系统分配处理机的基本单位，而进程是分配资源的基本单位。线程分为两类：用户线程和内核线程。第2章进程管理*