进程同步讲解课件

《进程同步讲解课件》由会员分享，可在线阅读，更多相关《进程同步讲解课件（43页珍藏版）》请在金锄头文库上搜索。

1、3.6进程同步,3.6.1同步的概念 3.6.2私用信号量 3.6.3用PV原语操作实现同步 3.6.4 经典进程同步问题,3.6.1同步的概念,并发进程之间存在相互制约关系 进程P1 : 进程P2: L1:P(S) L2:V(S) 信号量初值:S=0,同步：,一个进程到达了某写点后，除非另一个进程已经完成了某写操作，否则就不得不停下来等待这些操作的结果，这就是进程同步。,用消息wait(消息名）等待合作进程发来消息用消息signal(消息名）表示向合作进程发去消息初始Bufempty=n(缓冲区个数)，Buffull=0,并发进程之间存在相互制约关系 Pc: . Pp:. A:wait( B

2、ufempty) B:wait(Buffull) 计算 得到计算结果 打印Buf中的数据 Buf 计算结果 清除Buf中的数据 Bufemptyfalse Buffullfalse Signal(Buffull) Signal(Bufempty) Goto A Goto B,3.6.2私用信号量,就是信号量与制约进程及被制约进程有关而不是与整组并发进程有关。该信号量为私用信号量（private semaphere)。 互斥时使用的信号量为公用信号量,3.6.3用PV原语实现进程同步,有了私用信号量，用P，V原语操作可以实现进程间的同步。 例如：Pa为发送进程，由deposit(data)调用发

3、送过程。Pb 为接收进程，remove(data)调用接收过程。 Pa的私用信号量Bufempty,初值n Pb的私用信号量Buffull,初值0,Pa:deposit(data): Pb:remove(data): begin local x begin local x P(Bufempty); P(Buffull); 按FIFO方式选择一空Buf(x) 按FIFO方式选择一满Buf(x) Buf(x)data data Buf(x) Buf(x)置满标志 Buf(x)置空标志 V(Buffull) V(Bufempty) end end,3.6.4 经典进程同步问题,1. 生产者消费者问题

4、(the producer-consumer problem),问题描述：若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。,采用信号量机制： full是“满”数目，初值为0， avail是“空”数目，初值为N。 实际上，full和avail是同一个含义：full + avail = N mutex用于访问缓冲区时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁 采用AND信号量集：Swait(avail, mutex), Ssignal(ful

5、l, mutex), ,Q： j = 0; while (true) P(full); P(mutex); 从Bufferj取产品; V(mutex); V(avail); 消费产品; j = (j+1) % n; ;,P：i = 0;while (true) 生产产品; P(avail); P(mutex); 往Buffer i放产品; V(mutex); V(full); i = (i+1) % n; ;,P(mutex); P(avail);,设某一时刻mutex=1， avail=0 ，若P进程优先于Q进程,P(avail); P(mutex);,2. 读者写者问题(the reade

6、rs-writers problem),问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个 “读写”互斥， “写写”互斥， 读读允许,采用信号量机制： S表示允许写，初值是1。 公共变量Rc表示“正在读”的进程数，初值是0； Sr表示对rc互斥操作，初值是1。,采用一般信号量集机制：问题增加一个限制条件：同时读的读者最多R个 Wmutex表示允许写，初值是1 Rcount表示允许读者数目，初值为R,3. 哲学家进餐问题(the dining philosophers problem),问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌

7、子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；,解决的方案,一个信号量表示一支筷子，五个信号量构成一信号量数组。 信号量数组定义如下： Var S:array0,1,2,3,4of semaphore:=(1,1,1,1,1) 相当于: s0=1,s1=1,s2=1,s3=1,s4=1,描述如下：,Repeat p(si) p(s(i+1)mod 5) . eat . v(si) v(s(i+1)mod 5),

8、. think . eat Until false 都拿自己面前的筷子，引起死锁。,解决问题的办法,只允许四位同时进餐，保证有一位可以进餐。 仅当哲学家左右筷子均可使用，可进餐。 规定奇数拿左，再拿右。偶数拿右，再拿左，保证有人可进餐。,1,3.7 进程间通信(IPC, INTER-PROCESS COMMUNICATION),3.7.1 进程通信方式 3.7.2 消息缓冲机制 3.7.3 邮箱通信 3.7.4进程通信的实例管道,返回,主从式 会话式 消息或邮箱机制 共享存储区方式,3.7.1 进程通信方式,1. 四种,主从式,主进程可以自由使用从进程的资源和数据。 从进程的动作受主进程的控制

9、。 主进程和从进程的关系是固定的。,会话方式 通信进程双方分别称为使用进程和服务进程，使用进程调用服务进程工作,使用进程调用服务进程必须得到许可 提供服务的服务进程的控制由自身完成 使用进程与服务进程的通信联系是固定的,消息和邮箱机制,消息包括四部分： 发送进程名 接受进程名 操 作 有关的数据,消息和邮箱机制特点,只要存在空缓冲区或邮箱，发送进程就可以发送消息。 发送和接受进程无关。 发送和接受进程之间存在缓冲区或邮箱,3.7.2 消息缓冲机制,发送进程在发送消息前，先在自己的内存中设置一个发送区，把要发送的消息填入其中，由发送进程发送。 接收进程在接收消息前，先在自己的内存中设置一个接收区

10、，由接收进程接收消息。 注意：发送时禁止访问，接收时要有消息。存在互斥，同步关系,共用信号量mutex=1私用信号量，接收sm=0Send(m)和Receive(n)可分别描述为：,Send(m) Receive(n) Begin begin 申请一缓冲 p(sm) P(mutex) p(mutex) 消息送缓冲区 取消息n V(mutex) 从缓冲区复制到接收区 V(sm) 释放缓冲 End v(mutex),3.7.3 邮箱通信 邮箱通信是由发送进程申请建立与接收进程相链接的邮箱,好处是：双方没有时间限制 双方是同步关系,实例：管道,管道在逻辑上为管道文件，物理上为高速缓冲区。 发送用wr

11、ite(fd1,buf,size) 接收用read(fd0,buf,size) Fd1为管道入口 Fd0为管道出口,管道(pipe),返回,管道是一条在进程间以字节流方式传送的通信通道。它由OS核心的缓冲区（通常几十KB）来实现，是单向的；常用于命令行所指定的输入输出重定向和管道命令。在使用管道前要建立相应的管道，然后才可使用。,#include main() int fd2; char a30,b30; pipe(fd); if (fork()=0) scanf(“%s”,a); write(fd1,a,30); exit(0); if(fork=0) read(fd0,b,30); pri

12、ntf(“%sn”,b); exit(0); wait(0); wait(0); ,3.8 线程(THREAD),3.8.1 线程的引入,进程：资源分配单位（存储器、文件）和CPU调度（分派）单位。又称为任务(task) 线程：作为CPU调度单位，而进程只作为其他资源分配单位。 只拥有必不可少的资源，如：线程状态、寄存器上下文和栈 同样具有就绪、阻塞和执行三种基本状态 线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。 线程的创建时间比进程短； 线程的终止时间比进程短； 同进程内的线程切换时间比进程短； 由于同进程内线程间共享内存

13、和文件资源，可直接进行不通过内核的通信；,进程与线程的关系,OS对线程的实现方式,内核维护进程和线程的上下文信息； 线程切换由内核完成； 一个线程发起系统调用而阻塞，不会影响其他线程的运行。 时间片分配给线程，所以多线程的进程获得更多CPU时间。,依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。Windows NT和OS/2支持内核线程；,内核线程(kernel-level thread),用户线程(user-level thread),用户线程的维护由应用进程完成； 内核不了解用户线程的存在； 用户线程切换不需要内核特权； 用户线程调度算法可针对应用优化；,不依赖于O

14、S核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。,轻权进程(Light Weight Process),它是内核支持的用户线程。一个进程可有一个或多个轻权进程，每个轻权进程由一个单独的内核线程来支持。,4.3.2 进程和线程的比较,地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的

15、线程在其他进程不可见 通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性 调度：线程上下文切换比进程上下文切换要快得多；,线程切换和进程切换,一个进程中 有一个线程,一个进程中有多线程,4.3.3 线程举例,1. SUN Solaris 2.3,Solaris支持内核线程(Kernel threads)、轻权进程(Lightweight Processes)和用户线程(User Level Threads)。一个进程可有大量用户线程；大量用户线程复用少量的轻权进程，不同的轻权进程分别对应不同的内核线程。,Solaris用户线程和轻权进程,用户线程、轻权进程和核心线程的关系,就绪状态(Ready)：进程已获得除处理机外的所需资源，等待执行。 备用状态(Standby)：特定处理器的执行对象，系统中每个处理器上只能有一个处于备用状态的线程。 运行状态(Running)：完成描述表切换，线程进入运行状态，直到内核抢先、时间片用完、线程终止或进行等待状态。 等待状态(Waiting)：线程等待对象句柄，以同步它的执行。等待结束时，根据优先级进入运行、就绪状态。 转换状态(Transition)：线程在准备执行而其内核堆栈处于