进程互斥与同步

1.引言：多道程序设计存在的问题？

采用多道程序设计技术的操作系统，允许多个进程同时驻留内存并发执行。思考： A.如何协调多个进程对系统资源，如内存空间、外部设备等的竞争和共享？ B.如何解决多个进程因为竞争资源而出现执行结果异常，甚至导致系统不稳定、失效等问题？ 例如，多个进程同时申请文件打印，如何有效分配打印机？ 

1.1 临界资源访问实例1：

银行的联网储蓄业务允许储户同时用储蓄卡和存折对同一帐户进行存取款操作，如果某储户同时（在ATM机和营业柜台）办理两笔存款业务（假设分别为1000和2000元），思考：余额是如何进行修改的？
从系统的角度看，有两个进程【服务器上感知到的】将同时对储户余额等数据进行修改【银行数据管理中心-计算中心数据库】。如果两个进程同时读出原余额（假设为5000元），两个进程分别将最新余额修改为6000 （5000+1000） 和7000 （5000+2000），显然都不正确。
原因：两个进程同时修改同一数据，而没有进行有效控制。
正确的方法：如果有多个进程需要同时修改某一数据，系统必须控制，一次仅允许一个进程完成读数据，并修改数据两件事以后，才允许别的进程对同一数据的读和修改操作。【互斥：A进程先修改，B进程阻塞；同步：A进程完成任务后，负责唤醒B进程】

1.2 临界资源访问实例2：

假设1：系统中有3个进程P1、P2、P3，其中P1和P2是计算进程，P3是打印进程，每当P1或P2计算出一个结果以后，将计算结果送到缓存区中，以便P3进程从中取出数据打印。
假设2：缓冲区被划分为0、1、2...n-1共n个单元。
有两个指针:in指针用于计算进程存放数据，指向缓冲区中下一个空闲的单元，out指针用于打印进程取数据，指向缓冲区中下一个将取走数据的单元。
解答： 假设某时刻，0到3号单元空闲，4到6号单元被占用，这时候P1、P2进程都准备将数据送入缓冲区 ，如图所示：
可能发生的情况： 1. 进程P1需要向缓冲区存储数据，并知道in指针当前指向7号空闲缓冲单元。若这时进程P1的时间片用完，被中断，调度程序调度进程P2执行。 2. P2正好也需要向缓冲区存放数据，首先获取in指针位置，同样也是7，于是，P2将数据送入7号单元，并将in指针移动一格，指向8号单元，然后继续执行其他操作。  3.当进程P1再次被调度执行时，将从上次的断点继续执行，即将数据送入7号单元（覆盖进程P2的数据），并移动in指针指向8号单元，然后继续执行其他操作。 4.进程P3不会发现上述错误【打印进程无法发觉数据覆盖错误】，继续从缓冲区取数据，进行打印。显然，进程P2的相应计算结果不会被打印输出。 
问题分析： 由于进程P1和P2共享缓冲区和位置指针，而未对这种共享进行有效控制，导致打印数据的丢失。如果控制进程P1、P2互斥地访问缓冲区和修改位置指针，将避免这种因为并发执行而导致的程序执行结果的不确定性。

结论： 通过上述两个例子可见，采用多道程序并发设计技术的操作系统对诸进程的并发控制是非常重要和必需的。 

2.并发控制

2.1 竞争资源

当并发进程竞争使用同一资源时，它们之间就会发生冲突。如果操作系统将资源分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用时，由操作系统分配给它。如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就绪队列，阻塞队列等。一种极端的情况是，被阻塞进程永久得不到申请的资源，而死锁【多个进程之间的僵持现象】。 
进程竞争资源首先必须解决“互斥”问题。某些资源必须互斥使用，如打印机、共享变量、表格、文件等。这类资源又称为临界资源【一次仅允许一个进程使用的资源】，访问临界资源的那段代码称为临界区。任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。


当进程需要使用临界资源时，通过获得临界区的使用权实现的。
首先，在“进入区”判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其它后来的进程进入临界区。后来的进程通过查看临界区使用标志，知道自己不能进入临界区，就进入阻塞队列，将自己阻塞。
当临界区内的进程使用完毕，退出临界区时，即在“退出区”修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。

2.2 如何保证互斥地访问？

由于同一个临界资源在多个共享它的进程中将对应多个临界区，怎样才能保证诸进程间互斥地执行临界区呢？
这就必须保证“临界区使用标志”是可被系统中所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥进行。 

2.3 临界区使用条件（互斥条件）

1. 每次只允许一个进程处于 临界区（忙则等待）；
2. 进程只能在临界区内逗留有限时间，不得使其它进程在临界外无限期等待（有限等待）
3. 如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）；
4. 进入临界区的进程，不能在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（让权等待）
5. 不能限制进程的执行进度及处理机的数量

2.4 共同协作

多个进程常常需要共同修改某些共享变量、表格、文件数据库等，协作完成一些功能。
必须确保它们对共享变量的修改是正确的，保证数据的完整性。
共享协作同样涉及到互斥、死锁和饥饿问题，但更强调对数据的写操作必须互斥地进行。 只有该进程退出临界区以后，才允许别的进程进入临界区进行数据修改，以保证数据的一致性。

2.5 通信协作

当进程进行通信合作时，各个进程之间需要建立连接，进程通信需要同步和协调。进程通信的方式很多，包括消息传递、管道、共享存储区等。通过消息传递实现进程通信时，由于没有共享资源，故无须互斥，但仍可能出现死锁和饥饿。
例如：3个进程P1、P2、P3，其中P1不断尝试与P2或P3通信，P2和P3又不断尝试与P1通信，如果P1与P2总能成功建立连接进行通信，而P3一直阻塞等待P1，这样P3被长时间饥饿。 

3.竞争资源引起的死锁与饥饿现象

2.1 竞争引起的死锁

例如，两个进程P1、P2，竞争资源R1、R2。
假设 ，现在P1已经占用了R1，且P2占用了R2，如果此时P1申请R2，且P2申请R1。会怎么样呢？
结果是P1、P2双方都占用对方申请的资源而阻塞，谁也不让步地永久等待，这就是死锁，如图所示：

2.2 竞争引起的饥饿

假设有3个进程P1、P2、P3，每个进程都需要周期性的使用资源R。如果当前P1正在使用临界资源R，P2和P3因为等待R而阻塞。
Case：当P1退出临界区时，P2立即进入临界区执行，若P2还未退出临界区时，P1又申请使用临界资源R。
:假设P2退出临界区后，系统将R分给了P1，然后，当R空闲时，又将其分给P2，如此反复。【此时，P3就处于饥饿状态】【该情况对P3是不公平的，应该避免】

总结

以上是生活随笔为你收集整理的[OS复习]进程互斥与同步1的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。