《进程间同步和通信》课件

进程间同步和通信本课件旨在深入探讨进程间同步与通信的关键概念和技术我们将从介绍进程间同步和通信的基本概念入手，逐步分析其必要性，并深入研究并发执行带来的挑战通过本课程，您将了解如何解决临界区问题，掌握信号量、管程等同步工具，并熟悉消息传递系统等通信机制，从而为构建高效、稳定的并发程序奠定坚实基础课程介绍什么是进程间同步和通信？进程间同步进程间通信进程间同步是指多个进程在执行过程中，由于资源共享或协作需进程间通信是指多个进程之间交换信息的过程由于进程拥有独求，需要在某些关键点上协调执行顺序，以避免数据不一致或错立的地址空间，它们不能直接访问彼此的数据因此，需要特定误同步机制确保共享资源在同一时间只能被一个进程访问，从的通信机制来实现数据共享和信息交换常见的通信方式包括管而维护数据完整性道、消息队列、共享内存和套接字等为什么需要进程间同步和通信？资源共享协作执行12多个进程可能需要访问共享的某些任务需要多个进程协作完资源，如文件、数据库或打印成通信机制允许进程之间交机同步机制可以确保对这些换信息，协调工作进度，从而资源的访问是互斥的，避免数实现任务的分解和并行处理据损坏提高效率3通过并发执行和进程间通信，可以充分利用系统资源，提高程序的执行效率和响应速度例如，生产者-消费者模型可以实现数据的异步生产和消费，提高整体吞吐量进程并发执行带来的问题数据不一致竞争条件死锁多个进程并发访问和修改共享数据时，可进程的执行结果依赖于多个进程的执行顺多个进程互相等待对方释放资源时，可能能导致数据不一致例如，两个进程同时序时，可能出现竞争条件例如，两个进导致死锁例如，进程A占用了资源X，更新同一账户余额，可能导致金额计算错程同时尝试分配同一块内存，可能导致分等待资源Y，而进程B占用了资源Y，等误配失败或内存冲突待资源X，从而形成循环等待竞争条件Race Condition定义示例竞争条件是指程序的执行结果依赖于多个进程或线程执行的相对考虑两个进程同时对一个共享变量进行递增操作如果两个进程顺序或时间当多个进程或线程以非预期的方式访问共享资源时交错执行，可能会出现以下情况进程A读取变量的值，进程，就会发生竞争条件，导致程序出现不可预测的行为B读取变量的值，进程A将变量的值加1，进程B将变量的值加1最终，变量的值只增加了1，而不是预期的2临界区的Critical Section概念定义特点临界区是指多个进程或线程都可临界区具有互斥性，即任何时候以访问的共享资源的代码段为只有一个进程可以进入临界区了保证数据的一致性，每次只允其他进程必须等待，直到当前进许一个进程或线程进入临界区程退出临界区保护为了保护临界区中的数据，需要使用同步机制，如互斥锁、信号量或管程，来控制对临界区的访问临界区问题的解决方案需要满足的条件互斥Mutual Exclusion在任何时刻，只有一个进程可以进入临界区其他进程必须等待，直到当前进程退出临界区前进Progress如果没有进程在临界区内，并且有进程想要进入临界区，那么这些进程不应该被无限期地阻塞在临界区之外也就是说，应该允许某个进程进入临界区有限等待Bounded Waiting每个进程等待进入临界区的时间必须是有限的也就是说，不能出现某个进程一直无法进入临界区的情况互斥Mutual Exclusion实现互斥可以通过多种同步机制来实现，如2互斥锁、信号量、管程等这些机制可定义以保证对共享资源的独占访问互斥是指在任何时刻，只有一个进程可以访问共享资源或执行临界区代码其1重要性他进程必须等待，直到当前进程释放资源或退出临界区互斥是保证数据一致性和避免竞争条件的关键如果没有互斥，多个进程同时3访问共享资源可能导致数据损坏或程序崩溃前进Progress定义1前进是指如果没有进程在临界区内，并且有进程想要进入临界区，那么这些进程不应该被无限期地阻塞在临界区之外也就是说，应该允许某个进程进入临界区保证2前进性要求同步机制不能导致无限等待如果多个进程竞争进入临界区，必须保证最终有一个进程能够成功进入避免3为了保证前进性，需要避免优先级反转和饥饿现象优先级反转是指低优先级进程阻塞高优先级进程的情况，饥饿现象是指某个进程一直无法获得所需资源的情况有限等待Bounded Waiting保证有限等待性要求同步机制不能导致饥饿2现象每个进程都应该有机会进入临界定义区，不能出现某个进程一直被其他进程抢占资源的情况有限等待是指每个进程等待进入临界区1的时间必须是有限的也就是说，不能实现出现某个进程一直无法进入临界区的情况为了保证有限等待性，可以使用公平的调度算法，如先来先服务FCFS或轮转3调度Round Robin，来分配资源和控制进程的执行顺序软件解决方案算法Peterson轻量级1纯软件实现，无需硬件支持简单易懂2算法逻辑清晰，易于理解和实现解决互斥3保证两个进程之间的互斥访问Peterson算法是一种经典的软件解决方案，用于解决两个进程之间的临界区问题它通过共享两个变量（flag和turn）来实现互斥访问该算法简单易懂，易于实现，但只适用于两个进程的情况算法的实现Peterson//共享变量boolean flag

[2];int turn;//进程i i=0或1flag[i]=true;//声明想进入临界区turn=j;//将进入临界区的机会让给进程jwhile flag[j]turn==j;//等待//临界区flag[i]=false;//退出临界区Peterson算法的实现代码如上所示进程i首先声明自己想进入临界区，然后将进入临界区的机会让给进程j接着，进程i进入一个循环等待，直到进程j不想进入临界区或者已经将机会让回给进程i最后，进程i退出临界区，并将flag[i]设置为false算法的正确性证明Peterson互斥性前进性有限等待性假设进程i和进程j同时进入临界区这如果进程i想进入临界区，但进程j不想如果进程i想进入临界区，但进程j一直意味着flag[i]和flag[j]都为true，并进入临界区，那么flag[j]为false，进占用临界区，那么turn的值会不断在i且turn的值等于i或j但这是不可能程i可以立即进入临界区如果进程j也和j之间切换由于turn的值最终会等的，因为turn的值只能由一个进程设置想进入临界区，那么turn的值最终会等于i，进程i最终可以进入临界区于i，进程i也可以进入临界区算法的局限性Peterson只适用于两个进程忙等待12Peterson算法只能解决两个Peterson算法使用忙等待进程之间的临界区问题对于busy waiting机制，即进多个进程的情况，需要使用其程在等待进入临界区时会不断他算法循环检查条件这会消耗大量的CPU资源依赖硬件3Peterson算法的正确性依赖于硬件的内存访问顺序在某些硬件平台上，可能会出现问题硬件解决方案TestAndSet指令硬件支持简化同步性能提升依赖硬件提供的原子指简化了临界区问题的解通常比软件解决方案性令决方案能更高指令的实现TestAndSetboolean TestAndSetboolean*target{boolean oldValue=*target;*target=true;return oldValue;}TestAndSet指令是一种原子指令，它可以测试一个共享变量的值，并将其设置为true该指令的实现代码如上所示TestAndSet指令的原子性保证了在多个进程同时调用该指令时，只有一个进程能够成功执行，从而实现互斥访问指令的优缺点TestAndSet优点缺点实现简单，易于理解和使用适用于多个进程的情况性能通常仍然存在忙等待问题，会消耗大量的CPU资源可能会导致饥比软件解决方案更高饿现象，即某个进程一直无法获得所需资源信号量的概念Semaphore定义操作信号量是一种用于控制多个进程信号量有两个基本操作wait对共享资源进行访问的同步工具和signalwait操作将信号它是一个整数变量，可以被初量的值减1，signal操作将信始化为一个非负值号量的值加1用途信号量可以用于实现互斥、同步和资源计数通过合理地使用信号量，可以避免竞争条件和死锁信号量的类型二进制信号量和计数信号量二进制信号量计数信号量二进制信号量的值只能为0或1它通常用于实现互斥锁，即计数信号量的值可以为任意非负整数它通常用于控制对有限保证对共享资源的独占访问资源的并发访问数量例如，可以使用计数信号量来限制同时访问数据库的进程数量信号量的操作和wait signalwaitsignal1wait操作将信号量的值减1如果信signal操作将信号量的值加1如果号量的值小于0，则进程进入等待状态此时有进程在等待该信号量，则唤醒其2，直到信号量的值大于等于0中一个进程信号量的实现typedef struct{int value;struct process*list;}semaphore;void waitsemaphore*s{s-value--;if s-value0{add thisprocess tos-list;block;}}void signalsemaphore*s{s-value++;if s-value=0{remove aprocess Pfrom s-list;wakeupP;}}信号量的实现代码如上所示wait操作首先将信号量的值减1如果信号量的值小于0，则将当前进程添加到信号量的等待队列中，并调用block函数将进程阻塞signal操作首先将信号量的值加1如果信号量的值小于等于0，则从信号量的等待队列中移除一个进程，并调用wakeup函数唤醒该进程使用信号量解决临界区问题初始化1将信号量初始化为1进入临界区2执行wait操作退出临界区3执行signal操作使用信号量解决临界区问题的步骤如上所示首先，需要将信号量初始化为1然后，在进程进入临界区之前，需要执行wait操作这将使信号量的值减1如果此时信号量的值为0，则进程可以进入临界区否则，进程将被阻塞，直到信号量的值大于0在进程退出临界区之后，需要执行signal操作这将使信号量的值加1，并唤醒等待该信号量的进程生产者消费者问题-问题描述解决方案生产者进程生产数据，并将数据放入缓冲区消费者进程从缓冲可以使用信号量来解决生产者-消费者问题需要使用三个信号区中取出数据进行消费需要保证生产者进程不会在缓冲区满时量互斥锁、空槽位和满槽位互斥锁用于保护对缓冲区的访问继续生产数据，消费者进程不会在缓冲区空时继续消费数据空槽位用于记录缓冲区中空槽位的数量满槽位用于记录缓冲区中满槽位的数量读者写者问题-问题描述解决方案多个进程可以同时读取共享数据，但只有一个进程可以写入可以使用信号量来解决读者-写者问题需要使用两个信号量共享数据需要保证写者进程在写入数据时，其他进程不能互斥锁和写者锁互斥锁用于保护对读者计数器的访问读取或写入数据同时，需要尽可能地提高读者的并发访问写者锁用于控制对共享数据的写入访问能力哲学家进餐问题问题描述1五个哲学家围坐在一张圆桌旁，每两个哲学家之间都有一根筷子哲学家需要同时拿起左边和右边的筷子才能进餐如果每个哲学家都先拿起左边的筷子，然后等待右边的筷子，可能会导致死锁解决方案2可以使用多种方法来解决哲学家进餐问题一种方法是限制同时拿起筷子的哲学家数量另一种方法是使用优先级来避免循环等待死锁的概念Deadlock原因死锁通常是由于资源分配不当或进程间2的同步机制不合理导致的定义1死锁是指多个进程互相等待对方释放资源，导致所有进程都无法继续执行的状避免态为了避免死锁，需要了解死锁发生的必要条件，并采取相应的预防、避免、检3测和恢复措施死锁发生的必要条件互斥条件请求与保持条件不可剥夺条件资源必须以独占方式分进程在占有资源的同时资源不能被强制剥夺，配，即一次只能被一个，可以请求新的资源只能由占有它的进程自进程使用愿释放循环等待条件存在一个进程循环等待资源的链，即每个进程都在等待下一个进程占有的资源互斥条件互斥条件是指资源必须以独占方式分配，即一次只能被一个进程使用如果多个进程可以同时使用某个资源，那么就不会出现死锁例如，如果多个进程可以同时读取同一个文件，那么就不会出现死锁但是，如果多个进程需要同时写入同一个文件，那么就需要使用互斥锁来保护对文件的访问，从而可能导致死锁请求与保持条件请求与保持条件是指进程在占有资源的同时，可以请求新的资源如果进程在请求新的资源之前必须释放所有已占有的资源，那么就可以避免死锁例如，如果进程在请求打印机之前必须释放所有已占有的文件，那么就可以避免死锁不可剥夺条件不可剥夺条件是指资源不能被强制剥夺，只能由占有它的进程自愿释放如果资源可以被强制剥夺，那么就可以避免死锁例如，如果操作系统可以强制剥夺某个进程占有的内存，那么就可以避免死锁但是，强制剥夺资源可能会导致进程执行失败或数据损坏循环等待条件循环等待条件是指存在一个进程循环等待资源的链，即每个进程都在等待下一个进程占有的资源如果打破循环等待条件，就可以避免死锁例如，可以对所有资源进行编号，并要求进程按照编号递增的顺序请求资源这样就可以避免循环等待死锁的预防打破互斥条件打破请求与保持条件打破不可剥夺条件打破循环等待条件尽可能使用允许多个进程并进程在请求资源之前释放所允许操作系统强制剥夺进程对所有资源进行编号，并要发访问的资源有已占有的资源占有的资源求进程按照编号递增的顺序请求资源死锁的避免银行家算法资源分配安全状态资源请求评估12系统能够找到一个安全序列，银行家算法在分配资源之前，使得所有进程都能顺利完成会评估分配后系统是否仍然处于安全状态动态分配3只有在分配后系统仍然安全的情况下，才会分配资源银行家算法是一种经典的死锁避免算法它通过维护系统的资源分配状态，并在分配资源之前评估分配后系统是否仍然处于安全状态，从而避免死锁的发生银行家算法需要知道每个进程的最大资源需求量，以及当前系统的可用资源量死锁的检测与恢复死锁检测死锁恢复定期检测系统是否存在死锁可以使用资源分配图来检测死如果检测到死锁，需要采取措施进行恢复常见的恢复方法锁包括进程终止、资源剥夺和进程回滚管程的概念Monitor定义组成特点管程是一种高级的同步机制，它提供了管程由共享变量、互斥锁和条件变量组管程保证了对共享资源的互斥访问，并一种更结构化的方式来管理共享资源的成提供了一种方便的机制来实现进程间的访问同步管程的组成互斥锁2管程的互斥锁，用于保证对管程内部的共享变量的互斥访问共享变量1管程内部的共享变量，用于存储共享资源的状态条件变量管程的条件变量，用于实现进程间的同3步条件变量ConditionVariable条件变量是管程内部的一种同步机制，用于实现进程间的同步进程可以使用wait操作等待某个条件满足，使用signal操作通知等待该条件的进程和操作wait signalwaitsignal进程调用wait操作，释放管程的互斥锁，并进入等待状态，进程调用signal操作，唤醒等待该条件变量的一个进程被直到其他进程调用signal操作唤醒它唤醒的进程重新获得管程的互斥锁，并继续执行管程的实现class Monitor{private:mutex m;condition_variable cv;//共享变量public:void waitcondition_variable cond{unique_lock lockm;cond.waitlock;}void signalcondition_variable cond{cond.notify_one;}};管程的实现代码如上所示管程内部包含一个互斥锁和一个或多个条件变量进程可以使用wait操作等待某个条件满足，使用signal操作通知等待该条件的进程消息传递系统Message PassingSystem进程间通信1允许进程之间交换信息独立地址空间2适用于拥有独立地址空间的进程同步与异步3支持同步和异步通信消息传递系统是一种用于进程间通信的机制它允许进程之间交换信息，即使这些进程拥有独立的地址空间消息传递系统支持同步和异步通信，可以满足不同的通信需求消息传递的两种方式直接通信和间接通信直接通信间接通信发送者直接将消息发送给接收者，需要知道接收者的进程ID发送者将消息发送给一个中间媒介（如信箱），接收者从该媒介中接收消息直接通信发送者和接收者的命名对称命名非对称命名发送者和接收者都需要明确指定对方的进程ID发送者需要明确指定接收者的进程ID，但接收者可以使用通配符来接收来自任何进程的消息间接通信信箱Mailbox信箱是消息传递系统中的一个中间媒介，用于存储消息发送者将消息发送给信箱，接收者从信箱中接收消息信箱可以由操作系统管理，也可以由进程创建和管理同步与异步通信同步通信异步通信发送者在发送消息后需要等待接收者发送者在发送消息后不需要等待接收接收消息才能继续执行者接收消息，可以继续执行阻塞式发送和接收阻塞式发送1发送者在发送消息后会被阻塞，直到消息被接收者接收阻塞式接收2接收者在接收消息时会被阻塞，直到收到消息非阻塞式发送和接收非阻塞式发送非阻塞式接收1发送者在发送消息后不会被阻塞，立即接收者在接收消息时不会被阻塞，如果2返回没有消息则立即返回进程间通信的实例管道Pipe半双工通信1数据只能单向流动父子进程2通常用于父子进程之间的通信字符流3以字符流的形式传递数据管道是一种常用的进程间通信机制它是一种半双工通信方式，数据只能单向流动管道通常用于父子进程之间的通信，以字符流的形式传递数据匿名管道和命名管道匿名管道命名管道只能用于具有亲缘关系的进程之间的通信，如父子进程匿名管可以用于任何进程之间的通信命名管道有名字，可以被多个进道没有名字，由操作系统自动创建和销毁程同时打开和使用进程间通信的实例消息队列Message Queue消息队列异步通信优先级消息的链表，存储在内支持异步通信可以根据优先级接收消核中息进程间通信的实例共享内存Shared Memory共享内存区域1多个进程可以访问同一块物理内存最快的通信方式2无需数据复制同步机制3需要额外的同步机制来保证数据一致性共享内存的实现//创建共享内存int shmgetkey_t key,size_t size,int shmflg;//将共享内存连接到进程的地址空间void*shmatint shmid,const void*shmaddr,int shmflg;//将共享内存从进程的地址空间分离int shmdtconstvoid*shmaddr;//控制共享内存int shmctlintshmid,int cmd,struct shmid_ds*buf;共享内存的实现需要使用操作系统提供的系统调用shmget用于创建共享内存，shmat用于将共享内存连接到进程的地址空间，shmdt用于将共享内存从进程的地址空间分离，shmctl用于控制共享内存进程间通信的实例套接字Socket网络通信多种协议用于不同机器之间的进程通信支持多种网络协议，如TCP和UDP灵活提供了灵活的通信接口远程过程调用RPC调用远程服务1像调用本地函数一样调用远程服务隐藏底层细节2隐藏了底层网络通信的细节提高开发效率3简化了分布式系统的开发远程过程调用RPC是一种允许程序调用位于另一台计算机上的子程序的协议程序员无需显式编码远程交互，程序就像调用本地函数一样调用远程服务，简化了分布式系统的开发的原理RPC客户端调用客户端调用本地的桩函数序列化客户端桩函数将调用参数序列化网络传输通过网络将序列化后的数据发送给服务器服务器调用服务器端的桩函数接收数据并调用实际的服务函数序列化与返回服务器将结果序列化后通过网络返回给客户端进程间通信的总结管道消息队列共享内存简单，但只能用于亲缘灵活，支持优先级最快，但需要同步机制关系进程套接字适用于网络通信如何选择合适的进程间通信方式？通信需求进程关系12根据通信的数据量、频率和实时性要求选择合适的通信方式根据进程之间的关系选择合适的通信方式，如父子进程可以使用管道，任何进程可以使用命名管道、消息队列或共享内存性能复杂性34根据性能要求选择合适的通信方式，如共享内存是最快的通信根据复杂性要求选择合适的通信方式，如管道是最简单的通信方式，但需要额外的同步机制方式，但功能有限课程总结与回顾本课程深入探讨了进程间同步与通信的关键概念和技术我们学习了如何解决临界区问题，掌握了信号量、管程等同步工具，并熟悉了消息传递系统等通信机制通过本课程的学习，相信您已经掌握了构建高效、稳定的并发程序所需的知识和技能练习题与思考题

1.解释什么是竞争条件，并举例说明如何避免竞争条件

2.比较和对比二进制信号量和计数信号量，并说明它们的应用场景

3.描述哲学家进餐问题，并提出至少两种解决方案

4.解释死锁发生的必要条件，并说明如何预防死锁

5.比较和对比管道、消息队列和共享内存，并说明它们的应用场景参考文献Operating Systems:Three EasyPieces RemziH.Arpaci-Dusseau andAndreaC.Arpaci-DusseauOperating SystemConcepts AbrahamSilberschatz,Peter BaerGalvinand GregGagneSynchronization computerscience-Wikipedia感谢聆听，欢迎提问感谢您的耐心聆听！希望本次课程对您有所帮助现在是提问环节，欢迎大家提出您在学习过程中遇到的问题，我们将尽力解答。