操作系统学习笔记2.3互斥

进程同步

进程同步是指多个进程在执行时，为了协调彼此的执行顺序和数据共享，确保它们能够正确地访问共享资源，而采取的一系列机制。主要目的是避免竞争条件，确保数据的一致性和完整性。

实现方式

• 信号量（Semaphore）：一种同步机制，可以控制多个进程对共享资源的访问。信号量有两种类型：
  

  

记录型信号量的定义数据结构
还是要稍微记一下

typedef struct{
int value;
Struct process *L;
}semaphore;

P操作（等待操作）：申请资源，尝试获取信号量。如果信号量的值大于0，则将其减1，表示占用一个资源；如果值为0，则进程进入等待状态。
V操作（释放操作）：释放资源， 释放信号量，将其值加1，表示释放一个资源。如果有其他进程在等待这个信号量，则唤醒其中一个进程。

信号量机制实现前驱关系

看着吓人，实际上一般，牢牢记住，前V后P。

• 互斥锁（Mutex）：专门用于实现互斥的锁，保证在同一时刻只有一个进程能够访问共享资源。

• 条件变量（Condition Variable）：用于在某些条件不满足时，阻塞一个进程，并在条件满足时通知它继续执行。

• 读写锁：允许多个进程同时读取资源，但在写入时只能有一个进程访问。

进程互斥

原则：
空闲让进
忙则等待
优先等待
让权等待
进程互斥是指多个进程在访问共享资源时，必须保证同一时刻只有一个进程可以访问。互斥是实现同步的基础，防止竞争条件的发生。

实现方式

• 互斥锁：同上所述，确保在任意时刻只有一个进程可以获得锁，从而访问共享资源。

• 信号量：通过设置信号量的值为1来实现互斥。
  本质上是一个变量。使用原语操作，waitS),signal(S),P,V操作

• 自旋锁：一种轻量级的锁，当一个进程发现锁已被其他进程占用时，会在循环中持续检查，而不是被挂起。

• 临界区：使用临界区机制，确保同一时刻只有一个进程能够进入访问共享资源的区域。

软件实现方法

单标志法：只判断
双标志先检查法：两个bool量，先判断是否要上厕所
双标志后检查法：先上锁后检查
Peterson算法。即判断，也谦让

硬件实现方法

中断屏蔽指令
测试和设置（Test-and-Set）:测试和设置是一种简单的原子操作，用于实现互斥锁。
swap指令：
互斥锁

同步问题

生产者-消费者问题

生产者-消费者问题是经典的同步问题，涉及两个进程：生产者和消费者，它们共享一个固定大小的缓冲区。生产者负责生成数据并放入缓冲区，而消费者则从缓冲区中取出数据进行处理。问题在于如何协调这两个进程，以确保数据的一致性和缓冲区的有效使用。

问题描述

• 缓冲区：固定大小的缓冲区，通常用数组实现，限制生产者和消费者的并发行为，必须要互斥访问，。
• 生产者：生成数据并放入缓冲区。如果缓冲区满，生产者需要等待。
• 消费者：从缓冲区取出数据进行处理。如果缓冲区空，消费者需要等待。

解决方案

为了解决这个问题，可以使用信号量、互斥锁和条件变量来实现生产者和消费者之间的同步。

代码解析

• 缓冲区：使用数组 buffer 实现，in 和 out 指针分别表示生产者和消费者的操作位置。
• 信号量：
  • empty：表示空缓冲区的数量，初始值为数组大小。
  • full：表示满缓冲区的数量，初始值为 0。
• 互斥锁：mutex 用于保护对缓冲区的访问。
• 生产者和消费者：分别在 producer 和 consumer 函数中实现，使用信号量和互斥锁控制对缓冲区的访问。

多生产者-多消费者问题

多生产者多消费者问题是生产者-消费者问题的扩展，涉及多个生产者和多个消费者共享一个固定大小的缓冲区。这个问题的关键在于如何有效地管理多个生产者和消费者之间的同步，以确保数据的一致性和缓冲区的有效使用。

问题描述

• 缓冲区：固定大小的缓冲区，限制生产者和消费者的并发行为。
• 多个生产者：同时生成数据并放入缓冲区。
• 多个消费者：同时从缓冲区取出数据进行处理。
• 同步需求：需要确保在缓冲区满时，生产者能够等待；在缓冲区空时，消费者能够等待。

解决方案

可以使用信号量、互斥锁和条件变量来实现多生产者和多消费者之间的同步。

代码解析

• 缓冲区：使用数组 buffer 实现，in 和 out 指针分别表示生产者和消费者的操作位置。
• 信号量：
  • empty：表示空缓冲区的数量，初始值为 BUFFER_SIZE。
  • full：表示满缓冲区的数量，初始值为 0。
• 互斥锁：mutex 用于保护对缓冲区的访问。
• 多个生产者和消费者：通过循环创建多个生产者和消费者线程，并传递各自的ID以便于打印。

总结

注意一定要从事件的角度分析问题而不是关系相互之间的角度分析问题

抽烟者问题

问题背景

问题设定如下：

• 三个抽烟者：每个抽烟者缺少某一种材料才能卷烟抽烟。

  • 第一个抽烟者缺少烟草，他拥有纸和火。
  • 第二个抽烟者缺少纸，他拥有烟草和火。
  • 第三个抽烟者缺少火柴，他拥有烟草和纸。

• 制造者：制造者随机地将两种不同的材料放在桌子上，每次会放两种材料，留下一种材料供缺少该材料的抽烟者使用。

• 抽烟流程：

  • 制造者每次将两种材料放在桌子上，然后通知对应缺少材料的抽烟者来取材料。
  • 如果桌上有烟草和纸，缺少火的抽烟者会取走它们并开始抽烟。
  • 每个抽烟者在使用材料后，必须通知制造者继续放新的材料。

同步与互斥的挑战

• 互斥问题：同一时刻，最多只有一个抽烟者能拿走材料并抽烟，其他人必须等待桌子上有他们所需的材料。因此需要控制抽烟者对桌上资源的访问，避免冲突。

• 同步问题：抽烟者不能盲目行动，必须等到制造者放好了他们所需的材料后才能拿走。这种同步控制通常通过信号量或者条件变量实现。

解决方案

1. 使用互斥量：互斥量可以保证在任意时刻，只有一个抽烟者在访问桌子上的资源。
2. 使用条件变量：条件变量可以让抽烟者等待直到满足特定条件（即桌子上有他们所需的两种材料），然后进行操作。

实现步骤

下面是详细的实现思路：

1. 全局变量：

   • tobacco：标志桌子上是否有烟草。
   • paper：标志桌子上是否有纸。
   • fire：标志桌子上是否有火。
   • mtx：互斥锁，用于保护对这些变量的并发访问。
   • cv：条件变量，用于通知抽烟者材料已经准备好。

2. 制造者逻辑：

   • 制造者随机放置两种材料在桌子上。
   • 制造者放好材料后，唤醒等待的抽烟者。
   • 制造者必须确保材料放置正确，并且在每轮抽烟后重新放置新的材料。

3. 抽烟者逻辑：

   • 抽烟者在循环中工作，不断检查桌子上是否有他们需要的材料。
   • 抽烟者在检测到自己所缺少的材料后，取走材料并抽烟。
   • 抽烟完后，抽烟者需要通知制造者以便放置新的材料。

代码解释

1. std::mutex mtx;：用于保护访问共享资源的互斥锁，防止多个抽烟者同时访问桌子上的材料。
2. std::condition_variable cv;：条件变量，用于同步制造者和抽烟者之间的工作，抽烟者会等待材料齐全时才会行动。
3. smoker函数：
   • 抽烟者会根据他们所缺少的材料来决定何时行动。当条件满足时，即桌子上有他所需要的两种材料时，他会取走材料并抽烟。
   • 抽烟结束后，抽烟者会清空桌子上的材料标志并通知制造者。
4. manufacturer函数：
   • 制造者会随机生成两种不同的材料放在桌子上。
   • 每次生成材料后，制造者会通知抽烟者桌上材料已准备好。

关键点

• 互斥和同步：通过互斥量保证每次只能有一个抽烟者拿走材料，同时使用条件变量来实现制造者和抽烟者之间的同步。
• 死锁和饥饿：代码通过合理使用条件变量和互斥量避免了死锁和饥饿现象。