华中科技大学操作系统第四章并发处理-课件2.ppt

进程的相互制约关系,在多道环境中，进程可并发执行，同时又要共享资源，这些资源有些可以共享使用（如硬盘），有些以独占方式使用（如打印机），由此将产生一系列的矛盾，产生错综复杂的相互制约的关系。 制约关系产生的原因： 资源共享 进程合作,（四）进程互斥,一、进程互斥的概念 1. 临界资源 例1：两个进程A、B共享一台打印机 若不加以控制，两个进程的输出结果可能交织在一起，很难区分。 例2：两个进程共享一个变量x 设： x代表某航班已卖出的机座数，初值为0。p1和p2为两个售票进程，功能是对共享变量x的值加1。 这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。,两进程并发执行的两种可能次序:,序列A 序列B p1: r1 := x ; p1: r1 := x ; r1 := r1 + 1 ; p2: r2 := x; x := r1 ; r2 := r2 + 1 ; P2: r2 := x ; x := r2 ; r2 := r2 + 1 ; p1: r1 := r1 + 1 ; x := r2 ; x := r1 ;,执行结果：x = 2,执行结果：x = 1,特点：当两个进程公用一个变量时，它们必须顺序的访问，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。 （1）什么是临界资源 一次（一段时间内）仅允许一个进程使用的资源。 物理设备：输入机、打印机、磁带机 软件资源：公用变量、数据、表格、队列等,（2）什么是临界区（临界段） 每个进程中访问临界资源的那段程序段。,（3）什么是互斥,在操作系统中，当某一进程正在访问某一存储区域时，不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约的关系称为互斥。 例如：进程A正在执行CSa段时，进程B就不能进入CSb段执行。 进程A 进程B x = 0 CSb x = x + 1 CSa x = x + 1 ,操作系统如何保证进程的互斥呢？,（1）保证进入 当有若干个进程欲进入临界区时，应在有限的时间内使其进入； （2）排它性 每次至多有一个进程处于临界区； （3）有限性 进程在临界区内仅逗留有限的时间； 进程在进入临界区前仅等待有限的时间。 ?这些原则如何实现呢？,二. 锁和上锁、开锁操作,1. 什么是锁 用变量w代表某种资源的状态，w称为“锁” 2. 进程使用临界资源的操作,每个临界资源设置一个锁位: 0:资源可用 1:资源占用,锁操作： 1.考察锁位的值； 2.若原来的值是为“0”，将锁位置为“1”（占用该资源）； 3.若原来值是为“1”，（该资源已被别人占用），则转到1。 开锁操作： 进程使用完资源后，将锁位置为“0”，称为开锁操作。,3. 操作系统如何实现锁,硬件方式 中断屏蔽法：禁止一切中断发生 代价高，影响并发性 不安全，将禁止一切中断的权利给了普通用户 局限性：不适合多CPU，进程只能禁止本CPU的中断 硬件指令法：设置“测试并设置”指令 一条指令完成读写两个操作 忙等待、饥饿现象 软件方式 锁机制（上锁/开锁原语） 信号灯机制,4. 上锁原语和开锁原语,（1）上锁原语 算法 lock 输入：锁变量w 输出：无 test ： if (w为1) goto test ;/* 测试锁位的值 */ else w = 1 ; /* 上锁 */ ,（2）开锁原语 算法 unlock 输入：锁变量w 输出：无 w = 0 ; /* 开锁 */ ,问题： （1）效率低。当锁已上时，当前上锁的进程忙等； （2）无法实现。当锁已上时，当前上锁（原语）的进程占有CPU不放，谁来开锁呢？忙等待,改进的算法,算法：lock（w） 输入：W（锁变量） 输出：无 if（w = 1） sleep(pri,w); W = 1； /* 上锁 */ ,算法：unlock（w） 输入：W（锁变量） 输出：无 if（等待W队列不空） wakeup(w)； W = 0； /* 开锁 */ ,5. 用上锁原语和开锁原语实现进程互斥,进程A,进程B,假设有两个进程共享打印机，两个进程中使用打印机的程序段为临界区。 为保证打印的正确，设置打印机的锁位print，其初值为“0”，表示打印机可用。,main（） int print = 0； cobegin ppa（）； ppb（）； coend ,ppa（） ； lock（print）； 使用打印机； unlock（print）； ； ,ppb（） ； lock（print）； 使用打印机； unlock（print）； ； ,三. 信号灯和P、V操作,什么是信号灯 信号灯是整型变量。 s 0时，表示绿灯，进程可继续执行。 s 0时，表示红灯，进程停止执行。 信号灯是一个确定的二元组（s，q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的值对并发进程和共享资源进行控制和管理。 注意：创建信号灯时，应准确说明信号灯s的意义和初值。,软硬件的锁机制都存在一定的缺点，荷兰计算机科学家Dijkstra于1965年提出了一个同步机构，称为信号灯。其基本原则是在多个相互合作的进程之间使用相同的信号来同步，一个进程强制的被停止在一个特定的地方直到收到一个专门的信号，这个信号就是信号灯。,2. P、V操作,（1）P操作 P操作定义 对信号灯s的P操作记为P（s）。 P（s）是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用P（s）的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。,置“等待状态”,转进程调度,Y,N,原子操作,信号灯的值只能由P、V操作来改变。,（2） V操作,V操作定义 对信号灯s的V操作记为V（s）。 V（s）是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行， 否则，要帮助唤醒在信号灯等待队列上的一个进程。,原子操作,3. 用信号灯的P、V操作实现进程互斥,设：mutex为互斥信号灯，初值为1。,main( ) int mutex = 1; /*互斥信号灯*/ cobegin Pa（）； Pb（）； coend ,Pb( ) P(mutex); CSb; V(mutex); ,Pa( ) P(mutex); CSa; V(mutex); ,用两个进程共享打印机的例子,设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有一台打印机)。 (print也是用于互斥的信号灯，教材上设置为mutex。),如何验证信号灯设置的准确性：,第一步：语法检查 创建信号灯时，应准确说明信号灯的意义和初值 除初始化外，仅能由P、V原语对信号灯进行操作 P、V操作一定成对出现 P操作在前，V操作在后 第二步：语义检查 模拟程序的并发执行，校验信号灯及P、V操作的执行效果,（3）信号灯可能的取值,假设有N个并发进程共用一台打印机，设互斥信号灯mutex的初值为1，则：mutex的取值范围为多少？信号灯的值分别代表什么含义？,mutex的取值为：1-(N-1) 1 ：无进程进入临界区。有一个空闲资源 0 ：1个进程进入临界区。无空闲资源，无进程等待 -i ：1个进程进入临界区。无空闲资源，且有i (i=N)个进程等待,当多个并发进程共享多个临界资源，如4个进程共享2台打印机，情况又如何？,（五）进程同步,两位同学约好星期天去东湖，早上8:00在校门口，不见不散。 当一个同学先来到校门口，要等另一个同学，到齐后一道打的去东湖。,一、进程同步的概念 1. 进程同步的例子,2. 什么是进程同步,同步： 所谓同步就是并发进程在一些关键点上需要相互等待与互通消息，这种相互制约关系称为进程同步。 互斥的概念来自于诸进程对独占使用资源（设备）的竞争 同步来源于多个进程的合作 在人类社会中竞争与合作是永恒的,病人就诊的例子,病人看病活动： 要病人去化验； 等化验结果； 继续诊病；,医生化验活动： 等要化验的病人； 进行化验； 开出化验单； ,等待,等待,唤醒后,唤醒后,3. 进程同步的分类,操作系统中，有各种各样的同步，归纳起来分为两类： 诸进程合作完成某工作的逻辑顺序 对系统资源的共享,a.合作进程的执行次序 用进程流图描述诸进程合作完成某任务的次序。,1、分析进程的同步关系,2、设置信号灯，说明含义、初值 s13 = 0 表示进程P1尚未执行完成 s23 = 0 表示进程P2尚未执行完成,3、写出程序描述,P1( ) ; v(s13); ,P3( ) p(s13); p(s23); .; ,P2( ) ; v(s23); ,进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。,b.共享缓冲区的合作进程的同步,设有一个缓冲区buffer，大小为一个字节，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。,要保证打印结果的正确，CP、IOP必须遵循以下同步规则： (1)当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待； (2)当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。,解决问题的步骤： (1)分析问题，弄清楚同步关系，如上分析； (2)设置信号灯，说明含义、初值； (3)写出程序描述。,c. 生产者消费者问题,把上面的例子扩充，假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。 生活中有很多这样的例子。,生产者消费者问题,同步问题： 对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待； 对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。,互斥问题： 缓冲区是个临界资源，诸进程对缓冲区的操作程序是一个共享临界区,P：一组生产者共用的指向空缓冲区头的指针 C：一组消费者共用的指向满缓冲区头的指针,生产者消费者问题,main（） int full=0； int empty=n； int mutex=1； cobegin Producer 1; Producer n; Consumer1; Consumer m; coend ,full：缓冲区产品数目，初值为0；empty：缓冲区可存放产品的空位，初值为n；mutex：缓冲区的互斥信号灯，初值为1；,Producer i（） while (生产未完成) 生产一个产品； P(empty); P(mutex); 将产品放入缓冲区； V(mutex); V(full); ,Consumer i（） while (还要继续消费) P(full); P(mutex); 从缓冲区中取出产品; V(mutex); V(empty); 消费一个产品； ,对指针P的操作,对指针C的操作,设置两个互斥信号灯分别控制对指针P、C的操作,例 题,用PV操作解决下面问题： 司机进程： Repeat 启动车辆； 正常行驶； 到站停车； Until ,售票员进程： Repeat 关门； 售票； 开门； Until ,32,同步要求：先关门，后开车； 先停车，后开门； 信号灯：S_Door, 初值为0 S_Stop, 初值为0,司机进程： Begin Repeat P(S_Door); 启动； 驾驶； 停车； V(S_Stop); Until false; End,售票员进程： Begin Repeat 关门； V(S_Door); 售票； P(S_Stop); 开门； Until false； End,33,补充题：读者写者问题,有十个读者和两个编辑同时处理一篇文章，试用信号灯及P、V操作描述读者与编辑之间协同工作，并给出类C程序。,读-读共享：对于读操作是可以同时进行的 读-写互斥：若有读者正在读，编辑就不能工作 若编辑正在处理，读者就不能读 写-写互斥：编辑与编辑的工作不能同时进行,34,main（） int mutex=1，couter=0； cobegin readi（）； (i=1-10) editerj（）； (j=1,2) coend ,readi() if(couter = = 0) p(mutex); couter +; 读文章； couter -; if(couter = 0) v(mutex); ,editerj() p(mutex); 处理文章; v(mutex); ,一种解法，正确吗？,读者、编辑问题正解,mutex: 用于读者与编辑、编辑与编辑的互斥信号灯，初值为1 mutex1: 用于对couter操作的互斥的信号灯，初值为1。,35,36,main（） int mutex1= mutex=1， couter=0； cobegin readi（）； editeri（）； coend ,readi() p(mutex1); couter +; if (couter = = 1) p(mutex); v(mutex1); 读文章； p(mutex1); couter -; if (couter = 0) v(mutex); v(mutex1); ,editj() p(mutex); 处理文章; v(mutex); ,进程间的通信,进程通信：进程之间的信息交换 作业若干个可并行执行的进程协同完成一个工作（同步）进程通信（在进程之间交换一定数量的信息） 进程通信方式： 低级通信原语：交换信息量较少。如互斥，同步机构 高级通信原语：交换信息量较多。如直接通信，间接通信 高级通信原语： 直接通信：一个进程直接发送消息给接受者进程； Send( P, Msg ); Receive( P, Msg ); 间接通信：进程通过一个“信箱”来传递消息。 Send( A, Msg ); Receive( A, Msg );,Linux系统进程间的通信,管道：进程间1对1通讯 信号量： 控制并发，多个进程对共享资源的访问 消息队列：进程间1对多或多对1通讯 信号：控制程序流程及异常处理，通知接收进程某个事件已经发生 共享内存：进程间传递数据，最快 套接字：多个网络上的进程通信,(六)线程的基本概念,操作系统中引入进程的目的是为了使多个程序并发执行，以改善资源使用率和提高系统效率,进程给并发程序设计效率带来问题 进程切换开销大 进程间通信代价大 不能很好的利用多处理器,引入线程的目的 减少进程/线程上下文切换开销 简化进程间的通信 更好的支持多处理器，达到最大程度的并行,进程的两项功能“独立分配资源”与“被调度分派执行”分离开来 进程作为系统资源分配和保护的独立单位，不需要频繁地切换 线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换 在这种指导思想下，产生了线程的概念,解决问题的基本思路,1. 什么是线程 线程是比进程更小的活动单位，它是进程中的一个执行路径（进程内一个相对独立的、可调度的执行单元）。有时称轻量级进程。,2. 线程的特点 并行性：同一进程的多个线程可在一个或多个处理器上并发或并行运行，从而提高系统的并行处理能力，加快进程处理速度 共享性：同一个进程中的所有线程共享进程获得的主存空间和一切资源，因此，同一个进程中线程切换很简单，线程间通信也简单方便 动态性：线程也是程序在相应数据集上的一次执行，由创建而产生，至撤销而消亡，有生命周期,3. 线程的性质,线程是进程内一个相对独立的可执行单元 线程是操作系统中的基本的调度单元 进程中至少要有一个或一个以上的线程 线程可以创建其他线程 线程并不拥有资源，只是使用他们，进程是资源分配和拥有的基本单元 由于共享资源，线程间需要通信和同步机制 线程有生命期，有诞生和死亡,4. 进程与线程的比较,调度：进程中可能有多个线程，一个线程阻塞并不影响整个进程，进程中的其他线程仍然可以参与调度运行 并发性：进程间可并发，同一进程中的线程间亦可并发 拥有资源：进程拥有资源，进程中有挂起操作，线程不拥有资源，没有权力决定进程或自己从主存撤出，挂起只是进程一级的概念 系统开销：线程上下文切换比进程上下文切换要快得多，同一进程中的线程切换系统开销小 地址空间和其他资源：进程间相互独立，同一进程的各线程间