操作系统(9) (并发-----原子性/互斥临界区/生产者消费者问题/临界区问题三条件/互斥性/进展性/公平性)

目录

1. 并发（Concurrency）的定义

2. 原子性（Atomicity）

3. 互斥（Mutual Exclusion)

4. 生产者-消费者问题（Producer-Consumer Problem）

5. 临界区Critical Section

6. 临界区问题（Critical Section Problem）及其解决方案三个条件：

---

\

1. 并发（Concurrency）的定义

• 并发是指多个指令序列（multiple instruction sequences）同时执行（at the same time）。这可以通过多进程（multiple processes）或者多线程（multiple threads）来实现。
• 这种情况通常出现在操作系统中，当有多个进程/线程运行时，它们可能会并行运行（parallel execution）或者并发执行（concurrent execution）。
• 进程/线程（Processes/Threads）通过共享内存（shared memory）或消息传递（message passing）进行通信，也可以共享资源，如设备（devices）、变量（variables）和数据结构（data structures）等。

2. 原子性（Atomicity）

• 原子性指的是一段操作必须是不可分割的，不能在中途被其他操作打断或看到其中间状态。这段代码要么完全执行，要么完全不执行，没有部分完成的状态。
• 举例：如果一个操作是原子的，那么即使多个进程或线程并发执行，这段代码也不会被其他进程或线程“看见”部分执行的结果。比如硬件提供的原子操作（如test_and_set）就是这样，即使在多核系统中，这种操作也是不可中断的。

3. 互斥（Mutual Exclusion)

• 互斥是针对临界区的，它确保在同一时间只能有一个进程或线程进入临界区（critical section），其他进程或线程必须等待直到当前进程离开临界区。这可以防止多个线程或进程同时修改共享资源，从而避免数据不一致的问题。
• 互斥通过某种同步机制来确保只有一个线程能进入临界区，比如使用锁（mutex），或者使用Peterson's solution这种软件实现。
• 举例：在多线程程序中，若两个线程需要修改共享变量counter，互斥确保只有一个线程可以在某个时刻进入临界区并修改counter，另一个线程必须等待。

4. 生产者-消费者问题（Producer-Consumer Problem）

生产者和消费者共享一个有限大小的缓冲区，生产者负责往缓冲区中添加项，消费者则从缓冲区中取出项。这个问题的挑战在于如何保证生产者和消费者在不发生冲突的情况下操作同一个缓冲区。

主要概念：

• 有界缓冲区（Bounded Buffer）：缓冲区中最多可以存放 N 个项。
• 计数器（Counter）：用于记录当前缓冲区中存放的项的数量。
  • 当生产者添加项时，计数器增加。
  • 当消费者取出项时，计数器减少。

并发问题：

和其他并发计算一样，生产者和消费者可能会因为共享资源（缓冲区）和计数器而产生竞争条件（Race Condition）。这可能导致缓冲区溢出或消费者读取空缓冲区等问题。

代码说明：

生产者（Producer）逻辑：

while (true) {     // 当缓冲区满时，生产者等待     while (counter == BUFFER_SIZE) ; /* do nothing */     // 有空间时，生产者添加新项     buffer[in] = new_item;     in = (in + 1) % BUFFER_SIZE;  // 环形缓冲区的实现     counter++;  // 更新计数器 }

1. 等待：如果缓冲区已满（counter == BUFFER_SIZE），生产者会等待。

1. 添加项：当有空间时，生产者会把新的项添加到缓冲区中，并更新缓冲区索引 in，这个索引是一个环形缓冲区的实现，防止数组越界。
2. 计数器递增：生产者成功添加项后，计数器 counter 自增。

消费者（Consumer）逻辑：

while (true) {     // 当缓冲区为空时，消费者等待     while (counter == 0) ; /* do nothing */     // 从缓冲区中取出项     consumed = buffer[out];     out = (out + 1) % BUFFER_SIZE;  // 环形缓冲区的实现     counter--;  // 更新计数器     // 消费该项 }

1. 等待：如果缓冲区为空（counter == 0），消费者会等待。
2. 取出项：当有项可以消费时，消费者从缓冲区中取出项，并更新缓冲区索引 out。
3. 计数器递减：消费者成功取出项后，计数器 counter 自减。

5. 临界区Critical Section

临界区定义：

• 临界区（Critical Section）是进程中一段需要访问共享资源的代码，这段代码不能与其他进程同时执行。
• 假设有 n 个进程 P0,P1,...,Pn−1P0, P1, ..., Pn-1P0,P1,...,Pn−1，每个进程都有一段代码被称为“临界区”。
• 进程在临界区中会修改共享变量、更新表格、写入文件等。当一个进程在执行临界区代码时，其他进程不能进入它们的临界区。

临界区的典型流程如下：

1. 进入临界区前，检查或同步机制。
2. 在临界区内执行共享资源相关操作。
3. 退出临界区，允许其他进程进入。

6. 临界区问题（Critical Section Problem）及其解决方案三个条件：

1. 互斥性（Mutual Exclusion）：

• 共享厨房中的某些资源（如炉灶或冰箱）一次只能被一个学生使用。如果两个学生同时尝试使用同一个资源，可能会导致混乱、冲突，甚至事故。因此，必须确保同一时间只有一个人可以使用这些资源。
• 这种情况类似于临界区中的互斥条件：当一个进程在访问共享资源时，其他进程必须被阻止，直到该进程完成操作。

2. 进展性（Progress）：

• 如果厨房空闲且有学生想要使用厨房，那么那些已经准备好烹饪的学生应该能够进入厨房，开始使用资源。决定谁可以进入厨房应该基于学生的实际准备情况，而不是随机因素。
• 这对应着进展条件：当没有进程在临界区内时，进程应该能够及时进入，而不应该被其他不相关的进程或因素阻挡。

3. 公平性/有界等待（Fairness/Bounded Waiting）：

• 如果有学生正在等待使用炉灶，应该有一个限制，确保这个学生不会无限期等待，直到所有其他学生完成烹饪。这样可以确保每个学生都有公平的机会，不会因为过多的等待而导致无法使用资源。
• 这与有界等待条件相似：每个进程在请求进入临界区后，应该有一个限制，确保它最终可以进入，而不会无限期等待。