操作系统第3章-3

1第三章、进程管理

3.1 进程的概念3.2 进程的描述3.3 进程状态及其转换3.4 进程控制3.5 进程互斥3.6 进程同步3.7 进程通信3.8 死锁问题3.9 线程23.7 进程通信一、进程通信：

进程之间的信息交换、数据传送。

低级通信：少量控制信息的交换，一个/几个字节。

高级通信：高效、大量地传送数据，交换信息。二、进程通信方式：1、主从式：（终端控制进程与终端进程）

1）主进程可自由使用从进程的资源和数据；

2）从进程动作受主进程控制；

3）主、从进程的关系固定。2、会话式：（用户进程与磁盘管理进程）

1）使用进程要得到服务进程的许可；

2）服务进程自控地完成对使用进程的服务；

3）通信时二者有固定的连接关系。33、共享存储区方式：（UNIXSystemV)

在存储区中划出一块共享存储区，两个进程通过对申请的共享存储区读、写实现通信。4、消息或邮箱机制：

1）发送进程和接收进程之间有用于存放传送消息的缓冲区或邮箱；

2）发送进程向空缓冲区或邮箱发送信息，接收进程从满缓冲区或邮箱接收信息；

3）发送进程和接收进程之间没有直接固定的联系。4三、消息缓冲机制：（直接通信方式，多对一）消息缓冲区： 进程通信的基本单位，记录消息的内容等信息，为多个进程共享，其数据结构描述为：

TYPEmessagebuffer=record

sender_ptr; 指向发送进程的指针

size; 消息长度

text; 消息正文

next_ptr; 指向下一个消息缓冲区的指针

end56公用信号量mutex：对消息缓冲区的的访问采取互斥措施;

私有信号量Sm：消息缓冲区无消息时，接收进程不能接收，同步措施。发送进程：Send(k,m)begin

向系统申请一个消息缓冲区

将发送消息m送到新消息缓冲区 把缓冲区链入接收进程k的消息队列

end接收进程：Receive(n)begin

摘下消息队列中消息n

把n复制到接收区 释放消息缓冲区

end

P(mutex)

V(mutex) V(Sm)

P(Sm) P(mutex)

V(mutex)7四、邮箱通信：（间接通信方式，灵活）邮箱：发送进程和接收进程之间设置的大小固定的私有数据结构（多个消息组成的队列），由接收进程所拥有。工作条件：发送至少有一个空格，接收时至少有一个满格。特点：发送、接收基本无时间限制。缺点：占用大量内存，接口多，效率低。（公用信箱）8同步措施：设置一对私有信号量，记录邮箱中空格满格的数量Deposit(m)beginlocalx

选择邮箱的一个空格x

把消息m放入空格x

置格x为满标志

end

Remove(m)beginlocalx

选择邮箱的一个满格x

取走消息m

置格x为空标志

endP(formnum)V(mesnum)P(mesnum)V(formnum)9实例1：管道P66

以比特流方式传送消息的通信管道，由文件系统的高速缓冲区构成。10例：创建管道，父子进程通过管道传递数据。#include<stdio.h>main(){intx,fd[2];charbuf[30],s[30];

pipe(fd);while((x=fork())==-1);if(x==0){sprintf(buf,"thisisanexample!");

write(fd[1],buf,30);

exit(0);}else{wait(0);

read(fd[0],s,30);printf("result:%s",s);}}11实例2：书例P1541、接收消息程序client.c2、发送消息程序server.c3、在msg.c中，创建三个子进程：其中两个调用client.c

另一个调用server.c

相互之间发送消息12接收消息程序client.c#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>#defineMSGKEY75structmsgform{longmtype;charmtext[256];};main(intargc,char*argv[]){structmsgformmsg;intmsgqid,pid,*pint;

msgqid=msgget(MSGKEY,0777|IPC_CREAT);printf("msgqid=%d\n\n",msgqid);pid=getpid();pint=(int*)msg.mtext;*pint=pid;msg.mtype=1;

msgsnd(msgqid,&msg,sizeof(int),0);

msgrcv(msgqid,(structmsgform)&msg,sizeof(msg),pid,0);pint=(int*)msg.mtext;pid=(int)*pint;printf("Client%s:receivefromServerprocess%d\n",argv[1],pid);}13发送消息程序server.c--1#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>#defineMSGKEY75structmsgform{longmtype;charmtext[256];};intmsgqid;main(){structmsgformmsg;inti,*pint;intpid;externcleanup();for(i=0;i<20;i++)signal(i,cleanup);

msgqid=msgget(MSGKEY,0777|IPC_CREAT);printf("msgqid=%d\n\n",msgqid);

14发送消息程序server.c--2for(;;){msgrcv(msgqid,(structmsgform*)&msg,256,1,0);pint=(int*)msg.mtext;pid=(int)*pint;printf("Server:receivefromClientprocess%d\n\n",pid);msg.mtype=pid;pint=(int*)msg.mtext;*pint=getpid();

msgsnd(msgqid,&msg,sizeof(int),0);}cleanup(){msgctl(msgqid,IPC_RMID,0);exit();}15msg.c#include<sys/types.h>#include<stdio.h>#include<unistd.h>main(){intpid1,pid2,pid3;pid1=vfork();if(pid1==0)/*子进程2001*/

{printf("\nClient1process%4d:\n",getpid());execlp("/…/client","client","1",NULL);}else{pid2=vfork();if(pid2==0)/*子进程2002*/

{printf("Client2process%4d:\n",getpid());execlp("/…/client","client","2",NULL);}

else{pid3=vfork();if(pid3==0)/*子进程2000*/

{printf("Server3process%4d:\n",getpid());

execlp("/…/server","server",NULL);

}

else

{printf("\nThisisParentprocess%4d!\n",

getpid());

}

}

}

wait(0);

wait(0);

wait(0);

}16子进程2001子进程2002子进程2000TYPE：1TEXT：2001TYPE：1TEXT：2002TYPE：

2001TEXT：

2000TYPE：

2002TEXT：

2000消息队列书例P16317实例3：和控制台的通信i18①用户进程PiCCP的接口用户进程发出问题：P_write(m)Begin

P(rq)

把m插入RQ队列

V(rq)

V(question)EndCCP接收问题：U_receive(m)Begin

P(question)

P(rq)

把m从RQ队列取出

V(rq)End19②

CCP与DCP的接口CCP向outbuf送问题：

outbuf_empty=1Write(y)Begin

P(outbuf_empty) copy(outbuffromy)

V(outbuf_full)EndDCP从outbuf中接收：

outbuf_full=0Receive(k)Begin

P(outbuf_full) copy(outbuftok)

V(outbuf_empty)End20③

DCP与显示器的通信显示器控制进程DCP：

D_busy=1初始化{清除outbuf，echo=false}Beginif(outbuf满)then

receive(k)

P(D_busy)

把k送入显示器数据缓冲区

V(D_ready)else echo=true

echobuf中字符置入显示器缓冲区fiEnd显示器动作DP：

D_ready=0Repeat if(echo=true)then

打印显示器缓冲区中字符

else

P(D_ready)

打印显示器缓冲区中消息

V(D_busy)Until(显示器关机)21④

KCP与键盘的通信键盘控制进程KCP：

T_busy=1初始化{清除inbuf、echobuf}Begin

P(T_ready)

从键盘数据缓冲区x中取出字符x.m

Send(x.m)

将x.m送入echobuf

V(T_busy)End键盘动作KP：

T_ready=0Repeat

P(T_busy)

把键入字符送入键盘数据缓冲区x

V(T_ready)Until(终端关闭)22⑤

CCP与KCP的接口KCP向inbuf送回答：

inbuf_empty=1Send(k)Begin

P(inbuf_empty) copy(inbuffromk)

V(inbuf_full)EndCCP从inbuf中接收回答：

inbuf_full=0Read(x)Begin

P(inbuf_full) copy(inbuftox)V(inbuf_empty)End23⑥

CCP用户进程Pi的接口CCP发出回答：S_answer(a,i)Begin

P(sqi)

把a插入SQi队列

V(sqi)

V(answeri)End用户进程接收回答：P_read(a)Begin

P(answeri)

P(sqi)

把a从SQi队列取出

V(sqi)

End24会话控制进程CCP的动作描述Localk,m,xRepeat

U_receive(m)

将消息m的进程标号置入k中 将消息m解码变换到x

write(x)

read(x)

将x编码到m

S_answer(m,k)Until（CCP结束）253.8 死锁问题一、死锁的定义

指多个进程因竞争资源而造成的僵局，即各自等待对方的资源，而在得到对方资源前又不会释放自己拥有的资源，在无外力作用下，各进程将永远不能向前推进。26二、死锁的起因1、资源竞争： 可剥夺性资源（CPU、内存） 非剥夺性资源（打印机）：分配后不能强行收回。272、进程推进顺序非法：合法非法28三、产生死锁的必要条件：1、互斥条件：2、不剥夺条件：3、部分分配条件（请求和保持）：4、环路条件： 防止死锁发生，破坏四个必要条件中的一个或多个即可（主要是第3、4个，第1、2条受资源特性的限制）。29四、死锁的排除方式1、死锁的预防2、死锁的避免3、死锁的检测和恢复301、死锁的预防——破坏四个必要条件中的一个或多个2）有序资源使用法——打破“环路条件”

内容：把资源编号排序，要求进程必须按编号递增的顺序申请资源：

m个资源，R1<R2<…<Rm，进程P1保持了Ri，只能申请Rj，（j>i）;

原理：总有一个进程占据较高序号的资源，其后申请的资源必空闲，从而满足需要一直往前推进，再释放已用资源。

编号原则：常用资源低序号，不常用资源高序号；

缺点：序号顺序相对稳定限制新设备；当一个进程的资源使用顺序和编号顺序不一致时，资源闲置浪费；限制用户的编程自由。1）预先静态分配法——打破“部分分配条件”

内容：进程一次性申请和分配全部所需资源，未全部满足则等待。

缺点：资源严重浪费；进程延迟运行。312、死锁的避免思路：在动态分配资源的过程中预测出发生死锁的可能性，加以避免。判断此次分配是否会导致系统进入“不安全状态”？安全状态：系统至少存在一个安全序列不会发生死锁。例：进程需求量已分配空闲资源A1053B42C92

把空闲的3个中的2个分给B

把空闲的3个中的2个分给C安全的分配：不安全分配：32银行家算法基本模式： 将进程分为若干步，每一步使用的资源固定，当进程每一步申请资源时，将请求、分配、释放、空闲的情况结合起来计算，看是否符合分配条件。数据结构：

n个并发进程P1…Pn共享m个资源R1…Rm： 可用资源向量Available[m]:Available[j]—资源Ri现有的空闲个数 最大需求矩阵Max[n*m]:Max[i,j]—进程Pi对资源Rj的最大需要数 分配矩阵Allocation[n*m]:Allocation[i,j]—进程Pi已获得资源Rj的数量 需求矩阵Need[n*m]:Need[i,j]—进程Pi还需要资源Rj的数量

Need[i，j]=Max[i，j]-Allocation[i，j]333435例：五个进程共享三类资源A、B、C，每类资源数量为10、5、7。时刻T0的资源分配情况如下：MaxAllocationNeedAvaillableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P44330024311057-725 = 33236

对T0时刻进行安全性分析后，可以找到一个安全序列{P1，P3，P4，P2，P0}，则系统安全。T0WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057true37P1发出请求Req(1,0,2）

<=Need(1,2,2）及Availlable(3,3,2）

为P1试探分配，修改Availlable、Allocation、Need

T1时刻进行安全性分析，找到安全序列{P1，P3，P4，P0，P2}说明系统安全，可以为P1实施分配T1WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057trueT033212220038P4发出请求Req(3，3，0）：

Req(3，3，0）<=Need(4，3，1)

Req(3，3，0）>Availlable(2，3，0)，不能分配，等待。

P0发出请求Req(0，2，0）：

Req(0，2，0）<=Need(7，4，3)

Req(0，2，0）<=Availlable(2，3，0)，试探分配，修改数据：AllocationNeedAvaillableABCABCABCP0030723210P1302020P2302600P3211011P4002431无法满足任何进程不能分配393、死锁的检测和恢复1）死锁的检测：判断死锁是否发生？2）死锁的恢复： 终止各进程，或逐个终止，直至先后释放的资源能够满足剩余进程的需要。403.9 线程一、线程的引入

为实现持续的并发执行，引入进程，但由于各种原因，若干进程间会出现频繁调度、切换，进行上下文切换的开销花去不少CPU时间，降低并发的效率。

进程的性质：

1、是系统进行资源分配和调度的基本单位—PCB。

2、是程序对某个数据集在处理机上的执行过程。

把两个特点分开，由进程负责资源的管理，由进程创建的若干个线程完成运行的特性，线程共享所属进程的资源，减少线程间切换的花销。进程上下文

进程执行活动过程的静态描述，是进程执行所依赖的环境。

当系统调度新进程占有处理机时，新老进程的上下文发生转换。42二、线程的概念

进程内的基本调度单位； 是相对独立的执行单元（子任务）；进程线程资源分配的基本单位。处理机调度的基本单位，与资源分配无关，多个线程共享所属进程的资源。不同进程有不同的虚拟地址空间，有外存挂起状态。同一进程内的线程共享同一地址空间，无外存挂起状态。进程存在的标志：进程控制块PCB上下文切换时间长线程的存在标志：线程控制表TCB及相关堆栈和寄存器上下文切换时间短43线程控制块TCB的内容1、线程的状态；2、CPU现场信息:

PC、PSW、通用寄存器、堆栈指针44三、线程的特点1、由进程所创建，一个进程至少创建一个线程，线程也可以创建线程；2、线程不拥有资源，只共享所属进程的资源；3、同一进程下的线程运行在相同的地址空间；4、线程之间需要互斥和同步机制；5、线程有生命期，在生命期中有状态的变化；6、类似程序，但一般不是完整的程序。45四、线程的状态1、就绪：具备运行条件，只等CPU；2、执行：占有CPU运行；3、阻塞：因为某事件让出CPU，等待；46五、线程的优点1、创建和撤消线程、线程切换的开销小，提高了并发效率；一个进程的开销大约是一个线程开销的30倍左右.2、线程共享同一地址空间的内存和文件，减少了通信的开销；3、减少用户等待时间，提高系统响应速度；4、促使用户设计出边界清晰、模块独立性好的程序。47六、线程的使用范围1、多处理机系统：

用户程序根据功能划分成不同线程，放在不同处理机上运行。2、单处理机系统：

1）多个用户对文件服务器提出文件访问请求；

2）前台和后台的分工处理；

3）异步处理；

4）加快执行速度；

5）组织复杂的工作；48七、线程的分类1、用户级线程：

用户程序在用户空间执行线程库，创建、调度、撤消线程，操作系统内核只管理进程； 用户级线程调度只进行线程上下文切换，不涉及处理机状态，与内核无关；2、系统级线程：

操作系统内核进行管理，内核提供系统调用和应用程序接口创建、调度、撤消线程； 负责进程和线程的调度；49例：Linux下的多线程程序example.c#include<stdio.h>#include<pthread.h>voidthread(void)

{inti;

for(i=0;i<3;i++)

printf("Thisisapthread.\n");

}intmain(void)

{pthread_tid;

inti,ret;

ret=pthread_create(&id,NULL,(void*)thread,NULL);

if(ret!=0)

{

printf("Createpthreaderror!\n");exit(1);

}

for(i=0;i<3;i++)

printf("Thisisthemainprocess.\n");

pthread_join(id,NULL);

return(0);

}50相关函数函数pthread_create用来创建一个线程：

第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。 创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。函数pthread_join用来等待一个线程的结束：

第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存储被等待线程的返回值。 这个函数是一个线程阻塞的函数，调用它的函数将一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。编写运行Linux下的多线程程序，需要使用头文