进程同步与死锁

目录

进程同步与互斥

进程互斥的实现

进程互斥的软件实现方法

单标志法

双标志先检查

双标志后检查

Peterson算法

进程互斥的硬件实现方法

中断屏蔽方法

TestAndSet

Swap指令

互斥锁

信号量机制

用信号量机制实现进程互斥

用信号量机制实现进程同步

用信号量机制实现进程前驱关系

经典的进程同步问题

生产者消费者问题

多生产者多消费者问题

吸烟者问题

读者写者问题

哲学家进餐问题

管程

死锁

死锁的预防

死锁的避免

死锁的检测和解除

进程同步与互斥

并发性带来了异步性，有时需要通过进程同步解决这种异步。有的进程之间需要相配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。

对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源。

进入区和退出区是负责实现互斥的代码段。临界区是进程中访问临界资源的代码段，也可称为临界段。

进程互斥的实现

进程互斥的软件实现方法

单标志法

双标志先检查

双标志后检查

Peterson算法

进程互斥的硬件实现方法

中断屏蔽方法

TestAndSet

Swap指令

互斥锁

信号量机制

在进程同步中，让权等待是指当进程在等待进入临界区时，应主动释放处理机（CPU），将自身阻塞并加入等待队列，让其他就绪进程有机会运行。这样可以避免CPU空转，提高系统效率。

四种软件实现方式和三种硬件实现方式均存在以下问题：

• 软件实现方式：在进入临界区前，进程通常会在一个循环中反复检查条件（如标志位或锁状态），这个过程称为忙等待（Busy Waiting）。在此期间，进程持续占用CPU执行检查指令，不会主动让出CPU，因此无法实现让权等待。

• 硬件实现方式：

  • 中断屏蔽：通过关闭中断来保证互斥，但在此期间系统无法进行进程调度，当前进程独占CPU，若它不进入临界区也不释放CPU，则其他进程无法运行。

  • TS/TSL指令和Swap/XCHG指令：常用于实现自旋锁（Spinlock），进程会在循环中反复执行这些指令尝试获取锁，同样属于忙等待，不会主动释放CPU。

这些方法的共同缺陷是：进程在等待时持续占用CPU资源，而不是阻塞自己并让出CPU，因此都无法满足让权等待的要求。这会导致CPU利用率降低，尤其在多道程序系统中可能严重影响系统性能。为了克服这一问题，后来引入了信号量（Semaphore）等机制，这些机制可以在进程等待时将其阻塞并切换至其他进程，从而实现真正的让权等待。

信号量机制

用信号量机制实现进程互斥

用信号量机制实现进程同步

用信号量机制实现进程前驱关系

经典的进程同步问题

生产者消费者问题

多生产者多消费者问题

吸烟者问题

读者写者问题

哲学家进餐问题

如何防止死锁的发生呢？

①可以对哲学家进程施加一些限制条件：比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

③仅当一个哲学家左右两支筷子都可用时才允许他们拿起筷子：

管程

死锁

死锁的预防

死锁的避免

死锁的检测和解除

🙃🙃🙃...