更新时间：2024-05-21 15:10
并发是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能只有一道程序在执行，故微观上这些程序只能是分时交替执行。
1、多处理管理器：共享处理器时间
2、结构化应用程序：设计成一组并发进程
3、操作系统：上一点用于操作系统
是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作。
比如说进程A需要从缓冲区读取进程B产生的信息，当缓冲区为空时，进程A因为读取不到信息而被阻塞。而当进程B产生信息放入缓冲区时，进程A才会被唤醒。
是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。
比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行。
在操作系统中，进程是占有资源的最小单位（线程可以访问其所在进程内的所有资源，但线程本身并不占有资源或仅仅占有一点必须资源）。但对于某些资源来说，其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机，或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护，那么很有可能造成丢数据的问题)。
对于临界资源的访问，必须是互诉进行。也就是当临界资源被占用时，另一个申请临界资源的进程会被阻塞，直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。
对于临界区的访问过程分为四个部分：
1.进入区：查看临界区是否可访问，如果可以访问，则转到步骤二，否则进程会被阻塞
2.临界区：在临界区做操作
3.退出区：清除临界区被占用的标志
4.剩余区：进程与临界区不相关部分的代码
互斥的要求：
必须强制实施互斥，即一次只允许一个进程进入临界区。一个在非临界区停止的程序不能干涉其他程序。有限等待，即决不允许需要访问临界区的进程被无限延迟的情况，即死锁或饿死，有空让进，临界区空闲时，请求程序可进，对相关进程的执行速度和处理器的速度没有任何要求和限制。一个进程驻留在临界区的时间必须是有限的。
互斥的实现：
软件的方法：由并发执行进程担任这个责任
机器指令：减少开销，但不能通用
硬件实现方法
中断禁用
单处理器中并发进程不能重叠只能交替，一个进程一直运行到调用系统服务或被中断。保证互斥只需保证一个进程不被中断
缺点：一长时间中断禁止，中断效率会降低。二不能用于多处理结构中
专用机器指令
用于保证访问的原子性。1、比较和交换指令（compare and swap）、2、Exchange指令
机器指令方法的特点：
1、适合在单处理器或共享内存的多处理器上的任何数目的进程
2、非常简单且易于证明
3、可用于支持多个临界区，可用自己的变量定义
缺点
1、忙等待，进程等待进入临界区，仍然会继续消耗CPU的时间
2、可能饥饿，当需要等待程序进入时，某些可能被无限拒绝
3、可能死锁，低优先级的进程占用高优先级的进程所需的资源
信号量实现方法
解决并发问题基本原理
两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到它接到某一个特定的信号。复杂的合作需求都可以通过适当的信号结构完成。只需要一个特殊的变量（整数型）：称为信号量
信号量的三个操作
1、信号量s可以初始化成非负数
用于互斥：s=1
用于同步：s>=0
2、semWait(s)进程请求分配一个资源，操作使信号量减1，若为负。进程阻塞。否则继续执行
3、semSignal(s)进程释放一个资源，操作使信号量加1，若小于或等于0.则阻塞的进程被解除阻塞
信号量的使用规则
1、semWait和seSignal必须成对出现
互斥时，位于同一进程，临界区的前后
同步时，交错出现在两个合作进程内
2、多个seWait次序不能颠倒，否则可能导致死锁
3、用于同步的semWait应出现在用于互斥的semSignal之前
4、多个semSigal次序可以任意
5、在进程对信号量减1之前无法提前知道该信号量是否会被阻塞
6、当进程对一个信号量加1后。另一个进程会被唤醒，两个进程继续并发运行
7、在向信号量发出信号后，不需要知道是否有另一个进程在正在等待，被解除阻塞的进程数量或者没有或者是1
管程实现方法
信号量为实施互斥和进程间合作提供了强大灵活的工具，但存在难点。即semWait和semSignal操作可能分布在整个程序中，很难看出整体效果，因此提出管程（Monitor），一个程序设计语言结构，可以锁定任何对象，提供与信号量相同的功能，更易于控制
使用信号的管程
定义：管程由一个或多个进程、一个初始化序列和局部数据组成的软件模块
特点：
1、局部数据变量只能被管程的过程访问，任何外部过程都不能访问
2、一个进程通过调用管程的一个过程进入管程
3、在任何时候、只能有一个进程在管程中执行，调用管程的其他任何程序都被阻塞
管程的几个要素
1、管程中的共享变量在外部不可见，只能通过管程内所说明的过程间接访问
2管程必须互斥进入：管程中的数据变量每次只能被一个进程访问，保证数据完整性
3、管程通常用来管理资源，应当没有进程等待队伍、相应的等待及唤醒
4、Q进去管程等待时，释放管程互斥权，P进入管程，唤醒Q
P等待Q继续，直到Q退出或等待
P等待Q继续，直到P退出或等待
规定唤醒为进程中最后一个操作
利
生产者--消费者问题
生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来
这里生产者和消费者是既同步又互斥的关系，首先只有生产者生产了，消费着才能消费，这里是同步的关系。但他们对于临界区的访问又是互斥的关系。因此需要三个信号量empty和full用于同步缓冲区，而mut变量用于在访问缓冲区时是互斥的。参考程序如下：
class ProducerAndCustomer
{
//临界区信号量
private static Mutex mut = new Mutex();
private static Semaphore empty = new Semaphore(5, 5);
//空闲缓冲区
private static Semaphore full = new Semaphore(0, 5);
//生产者-消费者模拟
static void Main()
{
for (int i = 1; i < 9; i++)
{
Thread Thread1 = new Thread(new ThreadStart(Producer));
Thread Thread2 = new Thread(new ThreadStart(Customer));
Thread1.Start();
Thread2.Start();
}
Console.ReadKey();
}
private static void Producer()
{
empty.WaitOne();//对empty进行P操作
mut.WaitOne();//对mut进行P操作
mut.ReleaseMutex();//对mut进行V操作
full.Release();//对full进行V操作
}
private static void Customer()
{
Thread.Sleep(12000);
full.WaitOne();//对full进行P操作
mut.WaitOne();//对mut进行P操作
mut.ReleaseMutex();//对mut进行V操作
empty.Release();//对empty进行V操作
}
}
读者--写者问题
规定:允许多个读者同时读一个共享对象，但禁止读者、写者同时访问一个共享对象，也禁止多个写者访问一个共享对象，否则将违反Bernstein并发执行条件。
通过描述可以分析，这里的读者和写者是互斥的，而写者和写者也是互斥的，但读者之间并不互斥。
由此我们可以设置3个变量，一个用来统计读者的数量，另外两个分别用于对读者数量读写的互斥，读者和读者写者和写者的互斥。参考程序如下：
class ReaderAndWriter
{
private static Mutex mut = new Mutex();//用于保护读者数量的互斥信号量
private static Mutex rw = new Mutex();//保证读者写者互斥的信号量
static int count = 0;//读者数量
static void Main()
{
for (int i = 1; i < 6; i++)
{
Thread Thread1 = new Thread(new ThreadStart(Reader));
Thread1.Start();
}
Thread Thread2 = new Thread(new ThreadStart(writer));
Thread2.Start();
Console.ReadKey();
}
private static void Reader()
{
mut.WaitOne();
if (count == 0)
{
rw.WaitOne();
}
count++;
mut.ReleaseMutex();
Thread.Sleep(new Random().Next(2000));//读取耗时1S
mut.WaitOne();
count--;
mut.ReleaseMutex();
if (count == 0)
{
rw.ReleaseMutex();
}
}
private static void writer()
{
rw.WaitOne();
rw.ReleaseMutex();
}