操作系统zxj2进程管理课件

1、第二章 进程管理2.1.1 程序的顺序执行及特征一、程序执行有固定的时序。二、特征：顺序性:处理机的操作必须严格按照程序所规定的顺序执行封闭性：程序一旦开始执行，其计算结果不受外界影响可再现性：只要初始条件相同，一个程序多次重复执行，将得到相同的结果。2.1进程的基本概念I1C1P1I2C2P22.1.2前趋图定义有向无循环图（DAG）:描述进程间执行的前后关系表示方式：（1）p1-p2（2）-=(p1,p2)| p1 必须在p2开始前完成节点表示：一条语句，一个程序段，一进程。 P1P2P3P42.1.3 程序的并发执行一、多个程序的并发执行（可能性分析）I1I2I3I4C1C2C3C4P1

2、P2P3P4t程序的并发执行(2)二、特征间断性：程序之间相互制约的关系，将导致程序具有间断性失去封闭性：主要由共享资源引起不可再现性：设N的初值为n。举例：有2个循环程序A和B，它们共享一个变量N，程序A每执行一次时，都要做N:=N+1; B则每次要执行Print(N), 然后再做N:=0. 若程序A,B以不同的速度运行有以下三种不同的结果程序的并发执行(3)N:=N+1在print(N)和N:=0之前，则N值分别为n+1,n+1,0.N:=N+1在print(N)和N:=0之后，则N值分别为n,0，1.N:=N+1在print(N)和N:=0之间，则N值分别为n,n+1,0. 2.1.4进

3、程的特征和状态1. 进程的特征和定义一、定义：程序在并发环境下的一次执行过程1.结构特征进程：由程序段、数据段及进程控制块三部分构成，总称“进程映像”。2.动态性由“创建”而产生，由“调度”而执行；由得不到资源而阻塞；由撤消而消亡。（而程序是静态的）。2.1.4进程的特征和状态(2)3.并发性只有建立了进程，才能并发执行。4.独立性。独立运行，独立获得资源。5.异步性：（间断性）进程与程序区别程序是静态的，进程是动态的;进程更能真实地描述并发,而程序不能;一个程序可对应多个进程;进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的;程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的

4、；进程是系统分配调度的独立单位，能与其他进程并发执行;进程具有创建其他进程的功能，而程序没有。2.1.4进程的特征和状态(3)2. 进程的三种基本状态就绪状态：执行状态阻塞状态就绪阻塞执行时间片完进程调度I/O请求I/O完成图25 进程的三种基本状态及其转换2.1.4进程的特征和状态(4)3. 挂起状态（被换出内存的状态）引入原因终端用户请求父进程请求负荷调节需要（实时系统）操作系统需要进程状态的转换(图2-6)活动就绪 静止就绪活动阻塞 静止阻塞静止就绪 活动就绪静止阻塞 活动阻塞图26 具有挂起状态的进程状态图执行活动就绪静止就绪活动阻塞静止阻塞激活挂起激活挂起释放释放挂起请求I/O思考题

5、1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；阻塞进程最多几个，最少几个？2. 有没有这样的状态转换，为什么？ （1） 阻塞运行； （2） 就绪阻塞实验写一个程序描述进程状态迁移过程。要求：提供导致进程状态变化的调用接口，包括创建、删除、调度、阻塞、时间到、挂起、激活等。实现进程列表显示的接口。注：这里设计的进程是一个假设的对象实体，是由程序自己创建和删除，不是系统维护的进程。2.1.5进程控制块1.进程控制块的作用是进程存在的唯一标志；PCB(process control block)常驻内存2.进程控制块中的信息标识、处理机状态，进程调度信息，进程控制信

6、息pid进程状态现场优先级阻塞原因程序地址同步机制资源清单链接指针2.1.5进程控制块(2)3.PCB的组织链接索引执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91等待队列示例struct wait_queue struct task_struct * task;struct wait_queue * next;PCBPCBPCB2.1.5进程控制块(3)3.PCB的组织索引(p34图2-8)PCB1PCB2PCB3PCB4PCB5PCB6PCB7执行指针就绪表指针阻塞表指针补充PCB和进程的代码数据放在一起吗

7、？系统态和用户态系统空间和用户空间系统调用和普通调用的区别？系统调用会引起从用户态进入核心态进程-进程控制处理机执行状态系统态用户态进程控制机构内核：中断处理，时钟管理，进程管理，存储器管理，设备管理等。原语（primitive）由若干条指令构成的“原子操作(atomic operation)”过程，作为一个整体而不可分割要么全都完成，要么全都不做。许多系统调用就是原语。2.2 进程控制2.2.1 进程的创建一、进程图：描述了进程的家族关系：（P34 图2-9）子进程可继承父的资源，撤消时应归还给父进程，父的撤消会撤消全部子进程。根ABCGFED祖先二、引起创建进程的事件：1.用户登录：为终端

8、用户建立一进程2.作业调度：（不是进程调度）为被调度的作业建立进程3.提供服务：如要打印时建立打印进程4.应用请求：由应用程序建立多个进程2.2.1 进程的创建(2)三、进程的创建：（creat原语）1.申请空白PCB（一个系统的PCB是有限的）2.为新进程分配资源（不同于一般的分配，PCB-LIST在一个特殊区域）3.初始化PCB4.将新进程插入就绪队列。一个典型的进程创建原语Create (s0,m0,pi) p=Get_New_PCB(); /分配新的PCB pid=Get_New_PID(); /分配进程的PID pID=pid; /设置进程的PID p-CPU_State=s0; /

9、CPU的状态 p -Memory=m0; /内存 p -Priority=pi; /优先级 p -Status.Type=Ready; /进程状态 p -Status.List=RL; /进程队列 Insert(RL,p); /将进程p插入就绪队列 Scheduler(); /调度程序 2.2.2 进程的终止一、引起进程终止的事件1.正常结束：进程运行完成而推出2.异常结束：进程因异常而强行结束越界错误；保护错；非法指令；特权指令错；运行超时；等待超时；算术运算错；I/O故障3.外界干预：a.系统员kill进程；b.父进程终止；c.父进程请求。2.2.2 进程的终止(2)二、进程的终止过程（终

10、止进程的实质就是回收PCB）（1）检查进程状态；（2）执行态中止，且置调度标志为真。（3）有无子孙需终止。（4）归还资源给其父进程或系统。（5）从PCB队列中移出PCB.(并回收PCB)进程-进程控制一个典型进程终止原语如下：Destroy ( pid )p=Get_PCB(pid); /获取进程控制块 Kill_Tree(p); /删除整个进程树 Scheduler(); /调度器2.2.3 进程的阻塞与唤醒一、引起进程阻塞和唤醒的事件1.请求系统服务而得不到满足时，如问系统请求打印。2.启动某种操作而需同步时：如该操作和请求该操作的进程需同步运行（即非异步操作）。3.新数据尚未到达：如进程

11、A写，进程B读，则A未写，完B不能读。4.无新工作可做。2.2.3 进程的阻塞与唤醒(2)二、进程阻塞过程：是进程自身的一种主动行为a.调block原语b.停止执行，修改PCB入阻塞队列（一个或多个），并转调度。三、唤醒过程其它相关进程完成。a.wakeup原语b.修改PCB，入就绪队列可见，有block原语，在其它进程中就应有wakeup原语。Block( ) /获取当前进程的进程控制块 p=Get_PCB(); /保存当前进程的状态 s=p-Status.Type; cpu=p-Processor_ID; /处理机状态 /保存处理机现场 p-CPU_State=Interrupt(cpu)

12、; /将进程的状态改为阻塞 p-Status.Type=Blocked； Insert(BL,p); /将进程插入等待队列 Scheduler();阻塞原语的实现过程Wakeup( pid ) /获取进程控制P=Get_PCB(pid); /从阻塞队列中移出进程pRemove(p-Status.List,p);/进程的状态改为就p-Status.Type=Ready; /将进程插入到就绪队列Insert (RL,p); /调度程序Scheduler ();唤醒原语的执行过程如下：2.2.4 进程的挂起与激活 一、进程的挂起过程由进程自己或其父进程调suspend原语完成，将该进程PCB移到指定

13、区域，注意状态的改变，有可能要重新调度。二、进程的激活过程。active原语（如在外存，调入内存，改变状态，根据情况看是否调度，如抢先或非抢先）。阻塞、唤醒一般由OS实现，而挂起与激活可由用户干预。进程-进程控制实例研究：Linux和Windows系统创建进程Linux系统中进程创建fork 在Linux系统中，用户或系统可以使用系统调用fork来创建一个新的进程。fork的函数原形为： pid_t fork()当一个进程调用fork创建一个子进程后，父进程和子进程都在自己独立的地址空间内执行。它们之间不共享任何地址空间，但是父子进程具有相同的程序代码、数据和堆栈段， 因此，为了区别运行中的父

14、子进程，fork系统调用向父子进程返回不同的值。它向子进程返回0，而向父进程返回子进程的PID。.Beforefork()After.forkfork执行前一个控制流进入内核fork模块。Beforefork()After。Beforefork()Afterforkfork执行后调用后，从fork返回两个控制流父进程子进程/* - The file create.c introduces the use of fork. -*/ #include main() int pid; printf(“Before: my pid is %d .n”,getpid(); pid=fork(); /cr

15、eate new process if (pid = -1) /出错处理 perror(“Can not fork process!”); /error else if (pid =0) /子进程代码 printf(“I am the child. My pid is %d .n”, getpid();else /父进程代码 printf(“I am the parent. My child is %d .n”,pid); 进程-进程控制Windows系统中进程的创建CreateProcess 在windows系统，一个进程可以调用win32 API的CreateProcess函数来创建一个新

16、的进程及其主线程，以执行指定的任务。在利用CreateProcess建立进程时，操作系统要为新进程分配新的地址空间和资源，建立新的主线程。一旦新进程建立，父进程仍然使用原来的地址空间继续执行，而新进程则在新的地址空间执行一个新的程序。CreateProcess含有10个参数来指定建立进程的方式，具体参数的含义可参考相关的Win32 API手册。 #include #include #include STARTUPINFO startInfo; PROCESS_INFORMATION processInfo; strcpy(lpCommandLine,“c:WINNTSYSTEM32NOTEPA

17、D.EXE temp.txt”);ZeroMemory(&startupInfo,sizeof(startInfo);startInfo.cb=sizeof(startInfo);if (! CreateProcess（NULL,lpCommandLine,NULL,NULL,FALSE, HIGH_PRIORTY_CLASS CREATE_NEW_CONSOLE, NULL, NULL,&startInfo, &processInfo) fprintf(stderr,”CreateProcess failed!”); ExitProcess(1);CloseHandle(&processIn

18、fo.hThread);2.3进程同步同步：并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。2.3.1 进程同步的基本概念1.两种形式的制约关系资源共享关系：（进程间接制约）需互斥地访问临界资源。相互合作关系：（进程直接制约）2. 临界资源：（一次仅允许一个进程访问的资源）引起不可再现性是因为临界资源没有互斥访问。进程的同步进程同步举例：公共汽车中的司机和售票员司机 P1 售票员 P2 while (true) while (true) 关门； 启动车辆； 正常运行； 售票； 到站停车； 开门； 进程的同步是指系统中多个进程中发生的事件存在某种时序关系，需要相互合

19、作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。进程的互斥例如：系统中只有一台打印机，进程p1，p2都需要使用打印机。临界资源（Critical Resource）一次只能被一个进程使用形式：硬件，软件：变量、数据、队列等当临界资源由一个进程占用后，其它进程如果要使用它，必须等待占用进程使用完毕并把它释放后，才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。生产者消费者问题Var n, integer;Type item=;var buffer:array0,1,n-1

20、 of item;in, out: 0,1, , n-1;counter: 0,1,n;生产者消费者问题producer: repeat produce an item in nextp; while counter=n do no-op;bufferin:=nextp;in:=(in+1)mod n;counter:=counter+1;until false;consumer: repeatwhile counter=0 do no-op;nextc:=bufferout;out:=(out+1) mod n;counter:=counter-1;consumer the item in

21、nextc;until false;生产者消费者问题（2）设counter的初值为5register1:=counter; register2:=counter;register1 :=register1+1; register2:=register2-1;counter :=register1; counter :=register2;register1:=counter; (register1:=5)register1 :=register1+1; (register1:=6)register2:=counter; (register2:=5)register2 :=register2-1

22、; (register2:=4)counter :=register1;(counter:=6)counter :=register2; (counter:=4)定义：进程访问临界资源的那段代码。由于临界区的出现，需要对进入临界区的进程加以管理。管理方法为互斥和同步在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。3. 临界区临界区的调度原则一次至多允许一个进程进入临界区内一个进程不能不限地停留在临界区内一个进程不能无限地等待进入临界区 有空让进 无空等待 择一而入 算法可行访问临界资

23、源的描述：进入区：检查有无进程进入临界区：退出区：将访问标志复位RepeatEntry sectionCritical sectionExit sectionUntil false使用LOCK和UNLOCK原语系统为每一个临界资源设置一把锁，当一个进程欲进入临界区时，首先关锁，推出临界区时，把锁打开。Lock原语：Lock(W) begin L:if W=1 then goto L else W:=1; end;UNLOCK原语：UNlock(W) begin W:=0; end用变量W代表某种资源的状态，w称为锁，锁位值 为0；表示资源可用，而用1表示资源已被占用。进程同步和互斥的区别互斥的

24、各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只要当它们互相配合、共同协调推进时才能得到正确的运行结果。互斥的进程只要求它们不能同时进入临界区，而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软件方法 其基本思路是在进入

25、区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 其中的主要问题是设置什么标志和如何检查标志软件解法的缺点： 1. 忙等待 2. 实现过于复杂 3. 需要高的编程技巧进程互斥的硬件方法 “测试并设置”指令“交换”指令“开关中断”指令进入临界区前执行： 执行“关中断”指令离开临界区后执行： 执行“开中断”指令能够实现进程互斥，但不能满足“让权等待”，造成处理机资源浪费4.同步机制应遵循的准则 1.空闲让进2.忙则等待3.有限等待：应保证为有限等待，不会产生死等。4.让权等待：不能进入临界区的执行进程应放弃CPU执行权。2.3.2 信号量机制1 整型信号

26、量是一个整型量，通过2个原子操作wait(s)和signal(s)来访问。Wait(s): while s= 0 do no-ops:=s-1;Signal(s):s:=s+1;2 记录型信号量 由于整型机制中会不断测试不满足“让权等待”而引入type semaphore=recordvalue:integer;L: list of process;endL:为进程链表，用于链接所有等待该类资源进程。procedure wait(s)var s: semaphorebegins.value:=s.value 1;if s.value 0 them block (S,L)end2 记录型信号量(

27、2) procedure signal (S)var s:semaphonebegins.value:=s.vaule+1if s.value=0 then wakeup(s.L)end用wait(s)和signal(s)实现同步与互斥。在记录型信号量机制中：s.value初值：表示系统中某类资源的数目。s.value0:表该信号量链表中已阻塞进程的数目。信号量的说明：在信号量的实现中，S.value的初值表示系统某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源。当S.value0时，表示该类资源已分配完毕，因而进程调用block原语，进行自我阻塞

28、，放弃处理机，并插入到信号量链表S.L中。此时，S.value的绝对值表示在该信号量链表中已阻塞进程的个数、亦即恰好等于对信号量S实施wait操作而被封锁起来并进入信号量S队列的进程数。对信号量的每次signal操作，表示执行进程释放一个单位资源。 3 AND型信号量当不用它时，有可能发生系统死锁。死锁：在无外力作用下的一种僵持状态。AND信号量例：特点：要么全分配，要么一个也不分配。在一些应用场合，是一个进程需要先获得两个或更多的共享资源后，方能执行其任务。3 AND型信号量问题的引入 假定有两个进程A和B，它们都要求访问共享数据D和E。当然，共享数据都应作为临界资源。为此，可为这两个数据分

29、别设置用于互斥的信号量Dmutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即 process A: process B: wait (Dmutex); wait(Emutex); wait (Emutex); wait(Dmutex); 若进程A和B按下述次序交替执行wait操作： process A: wait(Dmutex);于是Dmutex=0 process B: wait(Emutex);于是Emutex=0 process A: wait(Emutex);于是Emutex=-1,A阻塞 process B: wait

30、(Dmutex);于是Dmutex=-1,B阻塞出现死锁的原因主要在于进程运行时需要多个资源，在为每个进程分配所需的全部资源时，不能保证原子操作，从而导致进程之间相互等待对方释放所占资源的死锁状态。为了解决进程同时需要多种资源且每种资源要占用一段时间的问题，人们提出了AND型信号量同步机制。AND型信号量的基本思想 将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。亦即，对若干个临界资源的分配，采取了原子操作方式：要么全部分配给进程，要么一个也不分配。3 AND型信号量Swait(s

31、1,s2,sn)if s11 and and sn 1 then for i:=1 to n do si:=si-1; endforelseplace the process in the waiting queue with the first si found with si1，记录型信号量。S=1时，互斥型信号量。（3）Swait(s,1,0)，可控开关，当时，允许进入，S1时，不能进入。2.3.3 信号量的应用 1.利用信号量实现互斥var mutex: semaphore:=1beginparbeginprocess1:beginrepeat wait(mutex); critica

32、l setion signal(mutex); remainder sectionuntil false; end1.利用信号量实现互斥(2) process2: begin repeat wait(mutex); critical setion signal(mutex); remainder sectionuntil false; endparend2.利用信号量来描述前趋关系(1)S1S2S3S4S5S6abcdegf图210 前趋图举例利用信号量来描述前趋关系(2)Var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;Beginparbegin begi

33、n S1; signal(a); signal(b); end; begin wait(a);S2; signal(c); signal(d); end; begin wait(b);S3; signal(e); end; begin wait(c);S4; signal(f); end; begin wait(d);S5; signal(g); end; begin wait(e); wait(f);wait(g);S6; end;parendend 经典进程同步问题 生产者消费者问题哲学家进餐问题读者写者问题 一、利用记录型信号量解决生产者一消费者问题问题描述 生产者消费者问题可描述如下：

34、有n个生产者和m个消费者，连接在一个有N个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。如右图所示。 问题分析为了使这两类进程协调工作，防止盲目生产和消费，它们应满足如下的同步条件：任何时刻所有生产者存放产品的数目不能超过缓冲区的总容量（N）;所有消费者取出的产品总量不能超过所有生产者当前生产的产品总量。 设置三个信号量： full：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保

35、证任何时候只有一个进程使用缓冲区。Var mutex,empty,full:semaphore:=1,n,0; buffer:array0,1,n-1 of item;in, out: integer: =0,0;begin parbeginproducer: begin repeat Produce an item in nextp; 一、利用记录型信号量解决生产者一消费者问题wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1) mod n;signal(mutex);signal(full);Until false;endconsumer

36、:beginrepeat wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty);Consumer the item in nextc;Until false;endparendend二、利用AND信号量解决生产者消费者问题 var mutex, empty, full: semaphore:=1,n,0;buffer:array0,n-1 of item;in out: integer :=0,0; beginparbegin producer: begin repeat

37、 produce an item in nextp; swait(empty, mutex); buffer(in):=nextp;in:=(in+1) mod n;ssingal(mutex, full);Until false;EndConsumer: begin repeatswait(full, mutex);nextc:=buffer(out);out:=(out+1) mod n;ssignal(mutex, empty);consumer the item in nextc; until false;endparendend哲学家进餐问题问题描述： 假设有五个哲学家，他们花费一生

38、的时光思考和吃饭。这些哲学家公用一个圆桌，每个哲学家都有一把椅子。在桌中央有一碗米饭。每个哲学家面前有一只空盘于，每两人之间放一根筷子（如右图）。当一个哲学家思考时，他与其他同事不交互，时而，哲学家会感到饥饿，并试图拿起与他最近的两支筷子（他与邻近左、右两人之间的筷子）。一个哲学家一次只能拿起一支筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时有两支筷子时，他就能不用释放他的筷子而自己吃了。当吃完后，他会放下两支筷子，并再次开始思考。1.利用记录型信号量解决哲学家进餐问题Var chopstick: array0, , 4 of semaphore;Repeat wait(c

39、hopsticki); wait(chopstick(i+1)mod 5); eat signal(chopsticki); signal(chopstick(i+1)mod 5); think;Until false分析:以上解法会出现死锁。为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。哲学家进餐问题1.利用AND信号量解决哲学家进餐问题Var chopstick

40、: array0, , 4 of semaphore:=(1,1,1,1,1);processiRepeat think; Sswait(chopstick(i+1)mod 5,chopsticki); eat Ssignal(chopstick(i+1)mod 5,chopsticki);Until false读者写者问题 特点：读进程可共享同一对象。写进程不可共享同一对象。读者优先：除非有写者在写，否则读者就无须等待一、利用记录型信号量解决读者写者问题 var rmutex, wmutex: semaphore: =1,1; readcount:integer: =0; begin par

41、begin reader: begin repeatwait(rmutex);if readcount=0 then wait(wmutex);/*当第一个读进程读数据库时,阻止写进程写*/ readcount:=readcount+1;signal(rmutex);perform read operation一、利用记录型信号量解决读者写者问题 perform read operationwait(rmutex);readcount:=readcount-1;if readcount=0 then signal(wmutex);signal(rmutex); until false; end

42、一、利用记录型信号量解决读者写者问题 writer: beginrepeat wait(wmutex) perform write operation; signal(wmutex)until false;end parend end二、信号量集解决读者写者问题(略) var RN integer;L, mx: semaphore: =RN, q; begin parbegin reader: begin repeat swait(L,1,1); swait(mx,1,0); perform read operation; ssignal(L,1); until false; end writ

43、er: begin 二、信号量集解决读者写者问题（略） writer: begin repeat swait(mx,1,1; L,RN,0); perform write operation; ssignal(mx, 1); until flase; end parend end理发师问题问题描述： 理发店有一位收银员，k位理发师、k张理发椅和n把供等候理发的顾客坐的沙发。如果没有顾客，理发师便在理发椅上睡觉。一个顾客到来时，他必须叫醒理发师。如果全部理发师正在理发时又有顾客来到，则如果有空沙发可坐，就坐下来等待，如果没有空沙发就离开这个理发店。问题分析为了解决这个问题，可以定义三个信号量cu

44、stomer、barbers和mutex以及一个计数变量waiting。信号量customer用来记录等待理发的顾客数（不包括正在理发的顾客），其初值化为0。信号量barbers用来记录正在等候顾客的理发师数，其值为k。Count:计数器，用于记录等候的顾客数；信号量mutex 用于实现计数器count的互斥访问，其初值为1。 semaphore customers = 0; /*等候理发的顾客数*/semaphore barbers = k; /*等候顾客的理发师数*/semaphore mutex = 1;Int count=0;/*等候顾客数(还没有理发的)*/void barber(

45、) while(TRUE); /*理完一人,还有顾客吗?*/ wait(cutomers); /*若无顾客,理发师睡眠*/ wait(mutex); /*进程互斥*/ waiting=waiting - 1; /等候顾客数少一个 cut_hair( ); /理发师为一个顾客理发 signal(mutex); /*开放临界区*/ signal(barbers); /理发师为顾客理完发 3.具体解法如下：void customer( ) wait(mutex); /*进程互斥*/ if (count 同步的实现。receive（sender,message）send(receiver,messag

46、e)三、管道通信管道：连接一个读进程和一个写进程之间通信的共享文件。功能： （以字符流的形式）大量的数据发收。注意：（1）互斥当一个进程正在对pipe执行读/写操作时，其它（另一）进程必须等待（2）同步当输入进程把一定数量的数据写入pipe，便去睡眠等待，直到输出进程取走数据后，再把它唤醒。（3）对方是否存在为了协调双方通信，管道通信机制必须对发送进程和接收进程在利用管道进行通信时实施同步和互斥，并只有在确定了对方存在时才能进行通信进程通信的类型 直接/间接通信方式（消息通信的2种方式） 一、直接send(Receiver, message)receive(Sender, message)例：

47、解决生产消费问题。repeat produce an item in nextp; send(consumer, nextp); until false; repeat receive( producer, nextc); consumer the item in nextc; until false;直接/间接通信方式（消息通信的2种方式） 二、间接（可以实现非实时通信）优点：在读/写时间上的随机性写进程 信箱（中间实体）读进程原语（1）信息的创建与撤消：信箱名 属性（公用、私用、共享）（共享者名字）（2）消息的发送和接收Send (mailbox, message)Receive (mai

48、lbox, message)直接/间接通信方式（消息通信的2种方式） 二、间接（可以实现非实时通信）信箱类型（1）私用：拥有者有读/写数，其它只有写权，（单向）存在期进程存在期。（2）公用：系统创建，双向，存在期=系统存在期。（3）共享信箱：一般进程创建，并指明其共享者，是双向。发送接收进程之间的关系：（1）一对一关系；（2）多对一关系；（3）一对多关系；（4）多对多关系：公用信箱。消息传递系统中的几个问题 一、通信链路：（1）显式建立：（进程完成）（2）隐式建立：（系统完成）链路类型：（1）由连接方法分：点点链路，多点链路。（2）由通信方式分：单向、双向。（3）由容量分：无容量（无缓冲区）、

49、有（有缓冲区）。消息传递系统中的几个问题 二、消息格式：消息头：含控制信息如：收/发进程名，消息长度、类型、编号消息内容：定长消息：系统开销小，用户不便（特别是传长消息用户）变长消息：开销大，用户方便。消息传递系统中的几个问题 三、进程同步方式1.发送和接收进程阻塞（汇合）用于紧密同步，无缓冲区时。2.发送进程不阻塞，接收进程阻塞（多个）相当于接收进程（可能是多个）一直等待发送进程，如：打印进程等待打印任务。3.发送/接收进程均不阻塞一般在发、收进程间有多个缓冲区时。消息缓冲队列通信机制 一、数据结构1.消息缓冲区type message buffer =recordsender:size:t

50、ext:next:指向下一指针2.PCB中应增数据项：type pcb=recordmq 消息队列指针mutex 消息队列互斥信息量sm消息队列资源信息量（表资源消息数）消息缓冲队列通信机制 二、发送原语 procedure send(receiver, a) begin getbuf(a.size, i); i.sender:=a.sender; i.size:=a.size; i.text:=a.text; i.next:=0; getid(PCB set, receiver.j); wait(j.mutex); insert(j.mq, i); signal(j.mutex); sign

51、al(j.sm);end消息缓冲队列通信机制 三、接收原语procedure receive(b)begin j:=internal name; wait(j.sm); wait(j.mutex); remove(j.mq, i); signal(j.mutex); b.sender:=i.sender; b.size:=i.size; b.text:=i.text;end消息缓冲队列通信机制 mqmutexsmsender:Asize:5text:Hellosend(B,a)sender :Asize :5text:hellonext:0发送区Asender:Asize:5text:Hell

52、oreceive(b)接收区Bab进程APCB(B)进程B练习试说明如果使用send_mailbox和receive_mailbox 原语实现打印文件的系统。欲打印的进程将要打印的文件名发送到邮箱printer,打印机假脱机将打印邮箱中出现名字的任何文件/process wish to printCharfilename ;Status=send_mailbox(“printer”,filename);If (status 0) /failure/print spoolerchar filename while (true)status=receive_mailbox(“printer”,fi

53、lename);if(status 0)/failureprint(filename);线程 线程的基本概念 1.线程的引入问题：可能会有很多个客户访问服务器，WEB服务器如何处理这多个访问？这台计算机上运行着WEB服务器程序，管理着许多网站这台计算机上运行着IE浏览器程序HTTP协议请求应答线程WEB服务器程序作为单个进程顺序处理：一次处理一个用户请求，处理完后再处理下一个请求 用户等待的时间可能会很长使用多个进程：有一个进程负责侦听，看是否有用户的请求到来。如果有，则创建另一个进程处理请求。一个用户请求对应一个进程。 进程频繁的创建与撤销，频繁的进程切换，开销大线程 1.线程的引入减少并发

54、执行时的时空开销，进程的创建、撤消、切换较费时空，因它既是调度单位，又是资源拥有者。线程是系统独立调度和分派的基本单位，其基本上不拥有系统资源，只有少量资源（IP，寄存器，栈），但共享其所属进程所拥有的全部资源。 线程的概念线程是指进程内部的一个可独立执行的实体，线程是处理机调度的基本单位。线程拥有少量必不可少的资源，如程序计数器、一组寄存器、栈，它可与同属一个进程的其他线程共享进程所拥有的全部资源。因为同一进程内线程共享内存和文件，因此他们之间相互通信，无需调用内核。由于同一进程内的线程都可访问整个进程的所有资源，所以它们之间的通信比进程间通信更方便，而同一进程内的线程间切换也会由于许多上下

55、文的相同而简化。线程 线程的优点创建线程比创建进程所需时间短撤销线程比撤销进程花费的时间短线程间切换比进程间切换花费时间短线程可以提高通信效率。由于同进程内线程间共享内存和文件资源，可以不通过内核直接进行通信适合多处理机系统进程和线程的比较 地址空间资源 不同进程的地址空间是相互独立的，而同一进程的各线程共享同一地址空间通信关系 进程间通信必须使用操作系统提供的进程间通信机制，而同一进程中各线程间的通信也需要同步和互斥手段的辅助，以保证数据的一致性。调度方面 在进程级操作系统中，拥有资源的基本单位都是进程，而在引入线程的操作系统中，线程是处理机执行的基本单位，进程是拥有资源的基本单位，在同一进程中，线程的切换不会引起进程的切换，在不同的进程中进行线程切换，将会引起进程的切换。同一进程