操作系统原理ppt课件(完整版).ppt

第第1章章 操作系统概论操作系统概论 本章学习目标 本章主要讲解操作系统的基本知识。通过本章学习，读者应该掌握以下内容：操作系统的功能和地位 操作系统的发展过程 操作系统的特征 操作系统的结构第第1章章 操作系统概论操作系统概论1第第2 2章章 进程管理进程管理 本章学习目标 本章主要介绍进程的概念、状态、构成以及Linux进程的相关知识。掌握进程的概念掌握进程的描述、状态及转换理解进程的特征了解Linux进程的描述及进程通信掌握进程的同步与互斥，并能灵活运用理解线程的概念及特征 第第2 2章章 进程管理进程管理2 教学内容 2.1进程的引入2.2进程的描述2.3进程控制2.4进程的同步与互斥2.5进程同步问题举例2.6进程通信2.7线程本章小结 32.1 进程的引入进程的引入 2.1.1 程序的顺序执行程序的顺序执行1程序的顺序执行程序的顺序执行 程序是人们要计算机完成的一些指令序列，是一个按严格次序、顺序执行的操作序列，是一个静态的概念。我们把一个具有独立功能的程序独占处理机，直到最后结束的过程称为程序的顺序执行。2程序顺序执行时的特征程序顺序执行时的特征（1）顺序性。（2）封闭性。（3）可再现性。第第2 2章章 进程管理进程管理42.1.2 程序的并发执行及其特征程序的并发执行及其特征1并发执行的概念并发执行的概念 所谓程序的并发性，是指多道程序在同一时间间隔内同时发生。程序的并发执行可总结为：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的一种执行方式。第第2 2章章 进程管理进程管理52程序并发执行时的特征程序并发执行时的特征（1）间断性 程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。（2）失去封闭性 某程序在执行时，必然会受到其它程序的影响。（3）不可再现性 在并发环境下，同一个程序执行多次，执行的过程可能不同。用程序作为描述其执行过程以及共享资源的基本单位是不合适的。因此引入了进程作为描述程序的执行过程、共享资源的基本单位。第第2 2章章 进程管理进程管理62.1.3 进程的定义与特征进程的定义与特征1进程的定义进程的定义人们对进程下过许多定义。现列举其中的几种：（1）进程是程序的一次执行。（2）进程是可以和别的进程并发执行的计算。（3）进程就是一个程序在给定活动空间和初始条件下，在一个处理机上的执行过程。（4）进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单位（5）进程是动态的，有生命周期的活动。内核可以创建一个进程，最终将由内核终止该进程使其消亡。第第2 2章章 进程管理进程管理7进程和程序之间的关系进程和程序之间的关系 进程和程序是两个完全不同的概念，但又有密切的联系。它们之间的主要区别是：（1）程序是静态的概念，；而进程则是程序的一次执行过程。它是动态的概念。（2）进程是一个能独立运行的单位，能与其它进程并发执行；而程序是不能作为一个独立运行的单位而并发执行的。（3）程序和进程无一一对应的关系。（4）各个进程在并发执行过程中会产生相互制约关系，而程序本身是静态的，不存在这种异步特征。第第2 2章章 进程管理进程管理82进程的特征进程的特征从进程与程序的区别可以看出，进程具有如下特征：（1）动态性 动态性是进程最基本的特性。进程由创建而产生，由调度而执行，因得不到资源而暂停执行，以及因撤消而消亡。（2）并发性 这是指多个进程实体，同存于内存中，能在一段时间段内同时执行。并发性是进程的重要特征，同时也是操作系统的重要特征。提高并发性，可以提高系统的效率。（3）独立性 进程是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。（4）异步性 这是指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。（5）结构特征 从结构上看，进程实体是由程序段、数据段及进程控制块三部分组成，也称这三部分为进程映像。第第2 2章章 进程管理进程管理92.1.4 进程的基本状态及转换进程的基本状态及转换1进程的三个基本状态进程的三个基本状态 进程通常至少有三种基本状态：（1）就绪状态（ready）进程运行所需的外部条件满足，但因为其它进程已占用CPU，所以暂时不能运行。（2）执行状态(running)外部条件满足，进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态。（3）阻塞状态(blocked)进程因等待某种事件发生，而暂时不能运行的状态，称为阻塞状态，也称为等待状态。系统中处于这种状态的进程可能有多个，通常将它们排成一个队列，也有的系统则根据阻塞原因的不同将这些进程排成多个队列。第第2 2章章 进程管理进程管理102进程状态的转换进程状态的转换 对于一个系统中处于就绪状态的进程，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它由就绪态转变为执行状态。正在执行的进程也称为当前进程，如果因分配给它的时间片已用完而被暂停执行时，该进程便由执行状态又回到就绪状态；一个处在执行状态的进程，如果因发生某事件而使进程的执行受阻，使之无法继续执行，该进程将由执行状态转变为阻塞状态。一个处于阻塞状态的进程，当它所需的外部事件满足，它应由阻塞状态变为就绪状态。第第2 2章章 进程管理进程管理11程执行完成或撤消阻塞状态就绪状态调度用片间时进程创建进等待某事件发生如I/O请求外部事件发生图2-1进程的基本状态及转换图完第第2 2章章 进程管理进程管理123引入挂起状态时的进程状态引入挂起状态时的进程状态 所谓挂起状态，实际上就是一种静止的状态。一个进程被挂起后，不管它是否在就绪状态，系统都不分配给它处理机。在引入挂起状态后，进程之间的状态转换除了四种基本状态转换以外，又增加了以下几种：（1）活动就绪静止就绪。（2）活动阻塞静止阻塞。（3）静止就绪活动就绪。（4）静止阻塞活动阻塞。第第2 2章章 进程管理进程管理13完成或撤消执行外部事件满足外挂起激活挂起挂激活活动就绪静止就绪活动阻塞静止阻塞调度图2-2具有挂起状态的进程状态转换等部事件外待起部条件满足第第2 2章章 进程管理进程管理142.1.5 Linux进程的状态进程的状态 Linux系统的一个任务总体上有以下几种状态：（1）TASK-RUNNING状态。（2）TASK-INTERRUPTIBLE状态，可中断的等待状态。（3）TASK-UNINTERRUPTIBLE状态,不可中断等待状态。（4）TASK-ZOMBIE状态，僵死状态。（5）TASK-STOPPED状态，暂停状态。第第2 2章章 进程管理进程管理152.2 进程的描述进程的描述 进程实体通常是由程序、数据集合和PCB这三部分构成，也称为“进程映象”。PCB程序部分数据集合第第2 2章章 进程管理进程管理16图2-4 进程的一般组成模型2.2.1 进程控制块进程控制块PCB PCB集中反映一个进程的动态特征，当系统创建了一个新进程时，就为它建立一个PCB；当进程终止后，系统回收其PCB，该进程在系统中就不存在了。所以，PCB是进程存在的惟一标志。可以按照功能将PCB分成四个组成部分：进程标识符、处理机状态、进程调度信息、进程控制信息。第第2 2章章 进程管理进程管理171进程标识符进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：（1）进程内部标识符。（2）进程外部标识符。2处理机状态处理机状态：由各种寄存器中的内容组成。3进程调度信息进程调度信息（1）进程状态。（2）进程优先级。（3）进程调度所需要的其它信息。（4）事件，或阻塞原因。4进程控制信息进程控制信息，包括：（1）程序和数据的地址；（2）进程同步和通信机制；（3）资源清单；（4）链接指针。第第2 2章章 进程管理进程管理182.2.2 进程控制块的组织方式进程控制块的组织方式各进程的PCB有如下几种组织方式：线性方式、链接方式和索引方式。1线性方式线性方式将各进程的PCB依次放入一个表中，结构如下图所示。PCB1PCB2PCB3PCBn-1PCBn第第2 2章章 进程管理进程管理19图2-5 PCB的线性组织方式2链接方式链接方式 链接方式是经常采用的方式。其原理是：按照进程的不同状态分别将其放在不同的队列。Linux操作系统就是应用这种进程控制块组织方式。运行队列指针就绪队列指针PCBPCBPCB0阻塞队列1指针阻塞队列2指针PCB0PCBPCBPCB0PCBPCBPCB0图2-6PCB链接队列示意图第第2 2章章 进程管理进程管理203索引方式索引方式系统根据所有进程的状态建立几张索引表。阻塞索引表就绪索引表执行指针就绪表指针阻塞表指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7图2-7PCB索引结构示意图第第2 2章章 进程管理进程管理212.2.3 Linux进程的进程的PCB Linux系统中的进程称为任务。该系统的进程控制块PCB用一个称为task-struct的结构体来描述，Linux系统PCB包含以下信息：1 进程描述信息进程描述信息（1）进程标识号（pid，process identifier）（2）用户和组标识（user and group identifier）（3）连接信息（Links）2进程控制信息进程控制信息（1）进程当前状态（2）调度信息（3）记时信息（4）通信信息第第2 2章章 进程管理进程管理22 Linux支持典型的UNIX进程间通信机制信号、管道，也支持System 通信机制共享内存、信号量和消息队列。3 进程资源信息进程资源信息 记录了与该进程有关的存储器的各种地址和资料、文件系统以及打开文件的信息等等。4 CPU现场信息现场信息第第2 2章章 进程管理进程管理232.3 进程控制进程控制 所谓进程控制，就是系统使用一引起具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。系统在运行时分为两种状态，即核心态和用户态。核心态也叫系统态或管态，是指CPU在运行操作系统的核心模块；用户态也称用态，是指CPU正在运行用户的程序。第第2 2章章 进程管理进程管理24 原语的概念：把系统态下执行的某些具有特定功能的程序段称为原语，原语的特点是不可被中断。系统在创建、撤消一个进程以及要改变进程的状态时，都要调用相应的程序段来完成这些功能。用于进程控制的原语有创建原语、撤消原语、阻塞原语和唤醒原语等。2.3.1 进程的家族关系进程的家族关系 操作系统通过内核原语来实现进程控制。在系统初始化完成后，系统就可创建进程。创建者称为父进程，被创建的新进程称为子进程，子进程又可以创建自己的子进程，从而形成一棵有向的进程家族树。子进程与父进程之间有着密切的关系，子进程的许多属性都是从父进程继承来的，子进程与父进程的区别是形成自己独立的属性。子进程可以从父进程继承的属性包括：用户标识符、环境变量、打开文件、文件系统的当前目录、已经连接的共享存储区和信号处理处理例程入口表等。子进程不能从父进程继承的属性包括：进程标识符和父进程标识符等。2.3.2 进程的创建与终止进程的创建与终止1进程的创建进程的创建 导致进程创建的事件有：用户登录、作业调度、为用户提供服务等。创建原语Creat()，通过下述步骤创建一个进程。（1）申请空白PCB。（2）为新进程分配资源。（3）初始化进程控制块。（4）将新建进程插入就绪态队列。2进程的终止过程进程的终止过程 在进程中，操作系统调用进程终止原语，终止本进程。过程如下：（1）根据被终止进程的标识符，从PCB队列中检索出该进程的PCB，从中读出该进程的状态。（2）若被终止进程正处于执行状态，应立即终止该进程的执行，该进程被终止后应重新进程调度。（3）检查该进程有无子孙进程，若有，则应将其所有子孙进程终止。（4）释放终止的进程所占有的资源，将其归还它的父进程或者系统。（5）将被终止的进程从它的PCB队列中移出。第第2 2章章 进程管理进程管理272.3.3 进程的阻塞与唤醒进程的阻塞与唤醒 进程状态的转换需要通过进程之间的同步或通信机构来实现，也可直接使用“阻塞原语”和“唤醒原语”来实现。阻塞原语在一个进程期待某一事件发生，但发生条件还不满足时，被该进程自己调用来阻塞自己，并转换为等待状态。当等待队列中的进程所等待的事件发生时，等待该事件的进程都将被唤醒。唤醒一个进程有两种方法，一种是由系统进程唤醒，另一种是由事件发生进程唤醒。第第2 2章章 进程管理进程管理28 实现进程的执行状态到等待状态，又由等待状态到就绪状态转换的两种原语，分别为阻塞原语与唤醒原语。入口保存该进程的CPU现场字置该进程的状态为阻塞阻塞进程PCB进入等待队列转到进程调度入口从等待队列取被唤醒进程将被唤醒进程置为就绪态被唤醒进程插入就绪队列转到进程调度或返回图2-9阻塞原语的实现图2-10唤醒原语的实现2.3.4 Linux系统调用系统调用 在Linux系统中，系统向用户提供了一些对进程进行控制的系统调用。常用的有：1fork()系统调用系统调用 Linux利用fork()系统调用创建一个新进程。2Exec系统调用系统调用 利用exec系统调用执行另一个程序。3exit()系统调用系统调用 父进程在创建子进程时，应在进程的末尾写一条exit，使子进程自我终止。4wait系统调用系统调用 将调用进程挂起，直至其子进程因暂停或终止而发来软中断信号为止。第第2 2章章 进程管理进程管理302.4 进程的同步与互斥进程的同步与互斥2.4.1 临界资源的概念临界资源的概念1临界资源临界资源 两个或两个以上的进程不能同时使用的资源为临界资源。临界资源可能是一些独占设备，如打印机、磁带机等；也可能是一些共享变量、表格、链表等。第第2 2章章 进程管理进程管理312临界区临界区 每个进程中访问临界资源的那段代码称为临界区。在临界区前面增加一段用于进行检查的代码，把这段代码称为进入区；相应地，在临界区后面再加一段用于退出临界区的代码，称为退出区。进程中除去上述进入区和退出区，其它部分的代码，称为剩余区。这样，可将一个访问临界资源的进程描述如下：repeat 进入区；临界区；退出区；剩余区；until false;第第2 2章章 进程管理进程管理322.4.2 进程的互斥与同步进程的互斥与同步1互斥与同步的概念互斥与同步的概念 进程互斥是指多个进程不能同时使用同一个临界资源CR，即两个或两个以上进程必须互斥地使用临界资源，或不能同时进入临界区CS。两个逻辑上完全独立、毫无关系的进程，由于竞争同一个资源而相互制约，就称为进程的互斥。进程同步，是指有协作关系的进程之间，要不断地调整它们之间的相对速度或执行过程，以保证临界资源的合理利用和进程的顺利执行。实现进程同步的机制称为进程同步机制。2同步机制应遵循的规则同步机制应遵循的规则所有同步机制都应遵循下列准则：（1）空闲让进。（2）忙则等待。（3）有限等待。（4）让权等待。第第2 2章章 进程管理进程管理332.4.3 锁机制锁机制 实现互斥的一种软件是采用锁机制，即提供一对上锁（Lock）和开锁（UnLock）原语，以及一个锁变量w（或者是锁位个bit）。加锁及解锁原语可描述如下：加锁原语：Lock w：L：if w=1 goto L else w=1开锁原语：UnLock w：w=0;第第2 2章章 进程管理进程管理34改进的加锁和开锁原语改进的加锁和开锁原语加锁原语：Lock w（）while(w=1)保护当前进程的CPU现场；将当前进程放入W的的等待队列，将该进程置为“等待”状态；转进程调度；开锁原语：UnLock（）if(w等待队列不空)移出等待队列首元素；将该进程置为就绪状态，并放入就绪队列；w=02利用锁机制实现进程的互斥 所有要进入临界区的进程，必须先执行上锁原语。如果该上锁原语顺利通过，则进程可进入该临界区；在完成对该临界资源的访问后，再执行开锁原语，用以释放该临界资源。2.4.4 信号量机制信号量机制 申请和释放临界资源的两个原语操作：wait操作和signal操作，有时也称为操作和操作。信号量（Semaphore），也叫做信号灯，它是在信号量同步机制中用于实现进程的同步和互斥的有效数据结构。我们可以为每类资源设置一个信号量。它有多种类型的数据结构，即：整型信号量、记录型信号量、型信号量及信号量集等。第第2 2章章 进程管理进程管理371整型信号量整型信号量 整型信号量的数值表示当前系统中可用的该类临界资源的数量。如设置整型信号量s，则s的值意义为：s0，则s的值表示系统中空闲的该类临界资源的个数；s=0，则表示系统中该类临界资源刚好全部被占用，而且没有进程在等待该临界资源；s0，则s的绝对值表示系统中的进程等待该类临界资源的个数；第第2 2章章 进程管理进程管理382记录型信号量记录型信号量 记录型信号量的数据结构由两部分构成。例如：定义记录型信号量，则：s的值表示系统中可用的该类临界资源的数量，而为进程链表指针，指向等待该类资源的PCB队列。设变量为记录型信号量，则wait（）操作和signal（）操作的流程如下图所示：第第2 2章章 进程管理进程管理39Wati(S)是Wati(S)s=s-1申请到资源本进程继续本进程入阻塞队列s0否转进程调度图2-10Wait操作原语流是signal(S)s=s+1唤醒一阻塞态进程s0否图2-11signal操作原语流释放该类资源本进程继续第第2 2章章 进程管理进程管理40申请临界资源的原语wait操作可描述为：void wait(S)S.value=s.value-1;if S.value0 本进程继续；else 将本进程放入阻塞态队列；转进程调度;释放临界资源的原语signal操作可描述为：void signal(S)S.value=s.value+1;if s0 then 唤醒指针queue所指的阻塞态进程；第第2 2章章 进程管理进程管理412.5 进程同步问题举例进程同步问题举例 2.5.1 生产者生产者消费者问题消费者问题1问题的描述问题的描述 有一批生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为方便生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。第第2 2章章 进程管理进程管理42012in-2n-1 假设初始情况下缓冲池为空，即counter。为在生产者消费者问题中实现各进程的同步，可设下列信号量：（假设初始情况下没有进程使用缓冲池，且缓冲池中各缓冲区都是空的。）mutex：互斥使用缓冲池信号量，由于初始情况下无进程使用缓冲池，故初值mutex=；empty：使用缓冲池中空缓冲区的信号量，由于初始情况下所有缓冲区为空，故初值empty=n；full：使用缓冲池中满缓冲区的信号量，由于初始情况下没有缓冲区存放产品，故初值full。设开始时生产者进程存放产品和消费者进程取产品时，都从第号缓冲区开始，并设这些生产者和消费者地位相当，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。第第2 2章章 进程管理进程管理43inout图2-12生产者消费者问题中的缓冲池算法及程序semaphore mutex=1,empty=n,full=0;定义信号量并赋初值 message buffern;int in=0,out=0;定义存取指针的初始位置 void main()parbegin(proceducer,consumer);生产者进程void procedure()do 生产一件产品;wait(empty);wait(mutex);将产品放入缓冲区bufferin;in=(in+1)%n;signal(mutex);signal(full);while(true);第第2 2章章 进程管理进程管理44消费者进程void consumer()do wait(full);wait(mutex);从缓冲区bufferout中取走一件产品;out=(out+1)%n;signal(mutex);signal(empty);消费这件产品;while(true);第第2 2章章 进程管理进程管理454在生产者在生产者消费者问题中应注意：消费者问题中应注意：（）在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。（）对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的进程中，这样保证生产者进程和消费者进程的同步及交替执行。（）在每个进程中，多个wait操作顺序不能颠倒，而signal操作的次序是无关紧要的。第第2 2章章 进程管理进程管理462.5.2 读者读者写者问题写者问题 1问题的提出问题的提出 一文件可以被多个并发进程共享，将这些访问该文件的进程按访问方式分为两类：一类只能读共享对象的内容，把这类进程称为读进程或读者；另一类进程则要更新（写）共享对象文件F，将这些进程称为写进程或写者。试用Wait、Signal操作解决各进程间的同步问题。2问题的分析问题的分析 显然，多个读者同时读一个共享对象是可以的，然而一个写者不能与其它任何读者或写者同时共享该文件。亦即：在使用共享文件时，一个写进程与其它所有进程都是互斥的。但多个读进程之间不存在互斥的现象。如图2-13所示。第第2 2章章 进程管理进程管理47共享文件F写进程W读进程R1读进程Rn图2-13读者写者问题 设读进程为reader，写进程为writer。为实现reader与writer进程间的同步与互斥，设如下变量及信号量：wmutex：互斥使用该共享文件信号量。如：写进程write与读进程reader在使用文件时是互斥的；共享文件只有一个，设初始情况未被使用，则初值为1。readcount：整型变量，表示正在读的进程个数。初值为0。该变量属临界资源。rmutex：计数器readcount的信号量。因为readcount是一个可被多个reader进程访问的临界资源，为此设一信号量。设初始状态下无进程读和写，故rmutex的初值设为1。第第2 2章章 进程管理进程管理48 由于多个进程可以同时读，因此只要有一个reader进程在读，其它reader进程便不必申请该共享文件，直接读即可；若无文件在读，则第一个读文件的进程必须做申请该文件的操作。只要有read进程在执行，则不允许writer进程去写。因此，仅当readcount=0,即无reader进程在读时，reader进程才需要执行wait(wmutex)操作。若wait(wmutex)操作成功，reader进程便可去读，相应地，做readcount+1操作。同理，仅当reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让writer进程写。第第2 2章章 进程管理进程管理493算法及程序算法及程序 读者写者问题可描述如下：semaphore rmutex=1,wmutex=1;int readcount=0;void main()parbegin(reader,writer);读者进程：void reader()while(1)wait(rmutex);if(readcount=0)wait(wmutex);readcount+;signal(rmutex);第第2 2章章 进程管理进程管理50 进行读操作;wait(rmutex);readcount-;if(readcount=0)signal(wmutex);signal(rmutex);写者进程：void writer()while(1)wait(wmutex);执行写操作;signal(wmutex);第第2 2章章 进程管理进程管理514注意事项及提示注意事项及提示（1）对于写进程，共享文件是临界资源；而对于读进程，该文件不是临界资源。（2）整型变量readcount是临界资源，所以在使用前后要进行Wait、Signal操作。第第2 2章章 进程管理进程管理522.5.3 哲学家进餐问题哲学家进餐问题1问题的提出问题的提出 设有5个哲学家围坐在一张圆桌前吃饭。桌上有5只筷子，在每人之间放一只。哲学家要吃饭时，只有分别从左、右两边都拿到筷子时，才能吃饭。如果筷子已在他人手上，则该哲学家必须等待到他人吃完后才能拿到筷子；任何一个哲学家在自己未拿到两只筷子吃饭之前，决不放下自己手里的筷子。试描述5位哲学家吃饭的进程。第第2 2章章 进程管理进程管理53图2-14哲学家就餐餐问题第第2 2章章 进程管理进程管理542问题分析问题分析 放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以为每一只筷子设置一个信号量，由这五个信号量构成信号量数组：Var chopstick:array0,4 of semaphore;设初始条件下，所有哲学家都未吃，故所有信号量均被初始化为1。3实现方法实现方法 假设每一位哲学家拿筷子的方法都是：先拿起左边的筷子，再拿起右边的筷子，则第i位哲学家的活动可描述为：第第2 2章章 进程管理进程管理55 semaphore chopstick5=1,1,1,1,1;viod main()parbegin(P0(),P1(),P2(),P3(),P4();Pi()/*i=0,1,2,3,4*/while(1)wait(chopsticki);wait(chopstick(i+1)%5);eating;signal(chopsticki);signal(chopstick(i+1)%5);thinking;第第2 2章章 进程管理进程管理56 以上算法存在一个问题：假设5个哲学家同时拿起左边的筷子，那么再去拿右边的筷子时，就会产生死锁。下面给出几种解决方法。（1）至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。（2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。最后总会有一位哲学家能获得两只筷子而进餐。具体程序段参看实训教材。第第2 2章章 进程管理进程管理574不产生死锁的哲学家就餐问题算法不产生死锁的哲学家就餐问题算法2.6 进程通信进程通信 进程间的信息交换称为进程通信。通常，进程间的通信分为两种：控制信息的传送与大量信息的传送。将进程间控制信息的交换称为低级通信，而把进程之间大批量数据的交换称为高级通信。进程的互斥与同步为低级通信方式，相应地，也称wait、signal操作为低级的通信原语。仅通过P、V操作或锁的方法是无法实现进程的高级通信的。高级通信方式可分为三大类：共享存储器系统、消息传递系统和管道通信系统。第第2 2章章 进程管理进程管理582.6.1 共享存储器系统共享存储器系统1共享存储器系统的类型共享存储器系统的类型（1）基于共享数据结构的通信方式 在这种通信方式中，要使各进程共用某些数据结构，借以实现各进程间的信息交换。如在生产者消费者问题中，就是用有界缓冲区这种数据结构来实现通信的。这种通信方式是低效的，只适用于传递相对少量的数据。（2）基于共享存储区的通信方式。在存储器中划出了一块共享存储区，各进程可通过对共享存储区中的数据的读或写来实现通信。第第2 2章章 进程管理进程管理592Linux共享存储区通信的实现共享存储区通信的实现（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章章 进程管理进程管理622.6.2 消息传递系统消息传递系统 在消息传递系统中，进程间的数据交换，是以格式化的消息（message）为单位的。程序员直接利用系统提供的一组通信命令进行通信。因实现方式的不同分为直接通信方式和间接通信方式。间接通信方式又称为信箱通信方式。信箱是一种数据结构，逻辑上可分为两部分：信箱头和信箱体。信箱头包含箱体的结构信息，信箱体由多个格子构成。信箱通信一般是进程之间的双向通信。第第2 2章章 进程管理进程管理631直接通信方式直接通信方式 这种通信是固定在一对进程之间。用来发送和接收消息。两条原语的形式如下：send(B,message);发送一个消息给接收进程B；receive(A,message);接收进程A发来的消息；通常情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：receive(id,message);其中，id为接收消息进程的标识符。2间接通信方式间接通信方式 信箱体sendreceivereceivesend进程B信箱头图2-15进程的信箱通信方式进程A间接通信方式又称为信箱通信方式。信箱是一种数据结构，逻辑上可分为两部分：信箱头和信箱体。信箱头包含箱体的结构信息，信箱体由多个格子构成，它实际上就是一个有界缓冲池。信箱通信一般是进程之间的双向通信。如图2-15所示。3消息缓冲队列通信机制消息缓冲队列通信机制（1）消息缓冲队列通信机制中所用的主要数据结构是消息缓冲区。在设置消息缓冲队列时，还应添加用于对消息队列进行操作和实现同步的信号量，并将它们存入进程的PCB中。当一个发送进程要发送消息时，便形成一个消息，并发送给指定的接收进程。接收进程将所有的消息缓冲区链成一个队列，其队列首由接收进程PCB中的队列队首指针mq来指出。（2）发送原语（3）接收原语 接收进程调用接收原语，从自己的消息缓冲队列中，选取第一个消息缓冲区，并将其中的数据复制到指定的消息接收区内。发送进程在发送消息之前，应先在自己的内存空间设置一发送区，然后调用发送原语，把消息发送给接收进程。2.6.3 管道通信系统管道通信系统 所谓管道，是指用于连接一个读进程和一个写进程，以实现他们之间通信的一个共享文件，又名pipe文件。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：（1）互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。（2）同步，指当读写进程使用pipe时，需要同步使用。（3）确定对方是否存在，只有确定了对方已存在时，才能进行通信。第第2 2章章 进程管理进程管理682.6.4 信号通信机制信号通信机制 1信号的基本概念信号的基本概念 每个信号都对应一个正整数常量，即信号编号。信号机制具有以下三方面的功能：（1）发送信号。发送信号的程序用系统调用kill()实现；（2）预置对信号的处理方式。接收信号的程序用signal()来实现预置处理方式；（3）收受信号的进程按事先的规定完成对相应事件的处理。第第2 2章章 进程管理进程管理692信号的发送信号的发送 3信号的处理信号的处理 对软中断信号的处理分三种情况进行：（1）如果进程收到的软中断是一个已决定要忽略的信号（function=1），进程不做任何处理便立即返回；（2）进程收到软中断后便退出（function=0）；（3）执行用户设置的软中断处理程序。信号的发送，是指由发送进程把信号送到指定进程的信号域的某一位上。进程用kill()向一个进程或一组进程发送一个信号。4相关的相关的Linux系统调用系统调用（1）kill()功能：向一个或一组进程发送一个软中断信号。（2）signal()功能：预置对信号的处理方式，允许调用进程控制软中断信号。第第2 2章章 进程管理进程管理712.7 线程线程 线程是比进程更小的能独立运行的基本单位。2.7.1 线程的基本概念线程的基本概念 线程（thead）是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。在引入线程的操作系统中，可以在一个进程内部进行线程切换，现场保护工作量小。线程与进程的比较：（1）进程是资源分配的基本单位。同一进程的所有线程共享该进程的所有资源。（2）线程是分配处理机的基本单位，它与资源分配无关。（3）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。（4）线程在执行过程中，需要协作同步。第第2 2章章 进程管理进程管理722.7.2 线程的状态与转换操作线程的状态与转换操作 线程有3种基本状态，即执行、阻塞和就绪。针对线程的3种基本状态，存在5种基本操作来转换线程的状态。它们是：1派生（spawn）2调度（schedule）3阻塞（Block）4激活（unblock）5结束（Finish）第第2 2章章 进程管理进程管理732.7.3 引入线程的好处引入线程的好处 引入线程的好处有以下几点：1易于调度。2提高了系统的效率。3创建一个线程比创建一个进程花费的开销少，创建速度快。4有利于发挥多处理器的功能，提高进程的并行性。第第2 2章章 进程管理进程管理742.7.4 多线程的实现多线程的实现 多线程机制是指操作系统支持在一个进程内执行多个线程的能力。多种系统支持多线程实现的方式并不完全相同。1用户级线程用户级线程 用户级线程是由用户应用程序建立的，并由用户应用程序负责对这些线程进行调度和管理，操作系统内核并不知道有用户级线程的存在，只对进程进行管理。2内核级线程内核级线程 内核级线程简称为KLT，通常也称为“纯KLT”方法。内核级线程中所有线程的创建、调度和管理全部由操作系统内核负责完成。3用户级线程与核心态线程相结合的模式用户级线程与核心态线程相结合的模式 由于用户级线程和内核级线程各有其特色，因此，如果将两种方法结合起来，则可吸取两者的优点。将两种方法结合起来的系统称为多线程的操作系统。内核支持多线程的建立、调度和管理。同时系统中又提供使用线程库，允许用户应用程序建立、调度和管理用户级线程。2.7.5 Linux系统的线程系统的线程 Linux的内核级线程也称为系统级线程。Linux的内核级线程和其他操作系统的内核实现不同，它可以同时支持内核级线程和用户级线程。Linux内核级线程和进程的区别主要体现在资源管理方面。本章小结本章小结 进程是操作系统中的一个非常重要的概念。进程是程序的一次执行，同时它也是操作系统进行资源分配的单位。进程具有一些特征，是与程序有根本区别的概念。进程具有动态性、并发性