操作系统学习笔记7 | 进程同步与合作

人工智能93

多进程图像不仅需要切换,还需要处理进程之间的交互。本节介绍流程之间的合作如何变得合理有序。它将涉及到对经典概念的理解,如信号量和临界区。

[En]

Multi-process images not only need to switch, but also need to deal with the interaction between processes. This section describes how cooperation between processes has become reasonable and orderly. It will involve the understanding of classical concepts such as semaphore and critical area.

参考资料:

1. 进程同步与信号量

总的来说 ,操作系统通过 !信号量! 实现进程同步

如果两个进程需要共同完成一项任务(即,进程协作),则它们需要信号进行通信。就像司机需要等待售票员关上车门并发出信号才能启动车辆一样。

[En]

If two processes need to complete a task together (that is, process cooperation), they need signals to communicate. Just as the driver needs to * wait for the conductor to close the door and send a signal before starting the vehicle.*

等待是进程同步的核心,进程同步的基本结构如下:

  • 进程A执行到某个环节时,发现某个条件不符合,则不继续向下执行,而是停下来等待;
  • 直到进程B运行到一定程度后产生这个条件,向进程A发送信号,进程A继续向下执行。

如上图所示,生活中 信号的例子有很多,那么要说的 信号量是什么?(从信号到信号量)

发明 信号量的迪杰斯特拉因此拿了图灵奖。此外他还发明了进程调度中非常著名的多级反馈队列算法。

这是一个典型的多进程合作的程序典例,生产者在缓冲区满的时候就不应该继续像缓冲区输入了,所以通过 while(counter==BUFFER_SIZE); 进行 阻塞,生产者进程开始等待

生产者不会继续执行,直到消费者进程运行,直到缓冲区空闲;同样,缓冲区为空,消费者必须等待缓冲区继续:

[En]

The producer does not continue execution until the consumer process runs until the buffer is free; similarly, the buffer is empty, and the consumer has to wait for the buffer to continue:

多进程的合作合理有序的关键就是要判断那些地方停(阻塞),哪些地方走(执行)。通过走走停停实现合作有序。

然而,上文介绍的信号,其本身的信息量还不能解决全部问题

  • 如果是一个消费者和两个生产者的情况:
    [En]

    if it is the case of one consumer and two producers:*

  • 如下图,所有消费者生产者共用一个缓冲区,缓冲区已满;
  • 生产者1 生产了一个item,但由于 缓冲区已满 counter == BUFFER_SIZE,所以进入休眠 sleep()
  • 由于缓冲区是公共的,此时如果再来一个生产者2,生产一个item, counter == BUFFER_SIZE,生产者2也进入休眠
  • 由于counter ≠ 0,消费者持续进行,counter-1,这时应当唤醒生产者: wakeup();这时唤醒了一个生产者1;
  • 消费者持续循环,此时 counter == BUFFER_SIZE-2,不触发唤醒条件,因此生产者2持续 sleep

    补充一个 while 引起的等待 跟 锁 之间的联系:

  • while并不一定就是自旋锁,自旋锁要看while内部的代码怎么写,如果内部有调度那就是无等待锁,如果内部没有调度那就是忙锁,也就是自旋锁
  • 使用while不会释放对cpu的所有权所以叫自旋,阻塞会释放对cpu的所有权
  • 使用while不会释放对cpu的所有权所以叫自旋,阻塞会释放对cpu的所有权
  • 这样问题就是 生产者2 永远休眠
  • 此处举例也并没有复杂到多个生产者与多个消费者,所以 仅用 counter 来进行语义判断是不够的,我们需要再用一个量记录有几个生产者进程在休眠。 如果我们能够记录有两个生产者进程在休眠,消费者进程运行至符合要求时,就可以根据该信息的提醒唤醒两个进程,而不产生遗漏。
  • 信号量:能够记录一些信息,并根据信息决定进程的休眠和运行。

下图PPT是在说信号的不足,需要引入信号量。

  • 缓冲区满,生产者1执行,生产者1休眠,赋 sem=-1;
  • 生产者2执行,生产者2休眠,赋 sem=-2;
  • 消费者一次循环, wakeup 生产者1,赋 sem=-1;

    相当于阻塞队列,唤醒先阻塞的。这个算法也可以自己设计。

  • 消费者第2次循环,wakeup 生产者2,赋 sem=0;
  • 这里 sem 就是 信号量 ,根据信号量来进行进程的等待唤醒。很显然较于counter(信号)表达了 更多的信息
  • 消费者第3次循环,赋值 sem = 1;
  • 生产者3 执行,sem > 0 ,表明缓冲区还有一个空位;不需要休眠,赋值 sem=0;
  • ...(如果接下来还有生产者执行,则 sem

讲道理,视频这里的弹幕水准 相当低。逻辑很简单,非要过度发挥!

信号量的核心思想是,使用情况用于记录必要的信息,信号用于管理进程是否处于等待/阻塞状态。下面是一个具体的实现。

[En]

The core idea of semaphores is that usage is used to record the necessary information, and signals are used to manage whether the process is waiting / blocking. Here is a concrete implementation.

  • 信号量的定义:semaphore结构体
  • 1个 int 类型的 value,用于记录资源个数(缓冲区空余);
  • 1个 PCB 队列,记录等待在该信号量上的进程;
  • 进程(对应上文生产者)调用 P 函数判断是否需要等待

    P 的意思就是 test,等价于上面1.3 中手动赋值 sem-- 并据此判断的过程

  • P 函数中 value - 1,对应 上文的 sem - 1;
  • 如果 value < 0,资源不够则进程 s 休眠,放入阻塞队列。
  • 进程(对应上问消费者)调用 V 函数来唤醒进程;

    V 的意思就是 increment,等价于上面1.3 中手动赋值 sem ++ 并据此判断的过程

  • V 的代码 应当为:
V(semaphore s) {
    s.value++;
    if (s.value

讲到现在,我们是否能用信号量对 1.2 中分析出的 counter 的不足进行改进呢?

我们需要分析 进程 "停" 的含义,给出正确的信号量(0为临界):

  • Producer当缓冲区已满且Producer停止时,哪个值为0?
    [En]

    producer when the buffer is full and the producer stops, which value is 0?*

  • 于是设计 empty 初值为 BUFFER_SIZE,当 empty 为 0 则满 ;
  • 生产者进程每次进行时调用P函数测试empty: P(empty);
  • 对应使 empty 增加的进程就是消费者,对应在消费者进程写: V(empty);
  • 消费者在缓冲区为空时停止。哪个值是0?
    [En]

    consumers stop when the buffer is empty. Which value is 0?*

  • 于是设计 full 初值为 0,当 full = 0 时缓冲区空;
  • 消费者进程每次进行时调用 P 函数测试 full: P(full);
  • 对应使 full 增加的进程就是生产者,对应在生产者进程写: V(full);
  • 缓冲区如何定义:
  • 可以是一个文件:buffer.txt
  • 由于是对文件进行操作, 同一时间只能一个进程进行操作互斥

    具体我此前有过体会:即Linux环境下打开某个普通文件,再次打开(非管理员权限)时会显示 只读,如果修改会有提示。

  • 需要定义一个新的信号量 mutex,初值为1,当 mutex = 0 表示有进程正在修改文件/读写缓冲区;
  • 这个信号量应当对生产者和消费者其同样的效用;同时在生产者消费者进程加入:
P(mutex);//将要使用缓冲区, 1->0;
V(mutex);//将要释放使用权, 0->1

提到了实验五,可以开始做了,linux0.11没有提供信号量,需要在内核中实现信号量的系统调用

2. 信号量临界区保护

上一部分讲到 通过对信号量的访问和修改,可以实现进程的同步、有序推进,但是我们还 需要对信号量进行保护

上述逻辑似乎是完美的。有什么问题吗?

[En]

The above logic seems to be perfect. What's wrong with it?

  • 正如 学习笔记4中多进程图像实现过程需要解决的问题中的举例2,我们的信号量必须要 !正确! 如果信号量的含义不对,那么对于进程同步的指挥只会一团糟。
  • 重复一下 笔记4 中提到的那个信号量可能出错的例子:
  • 由于进程任务正执行时时间片用完等因素,操作系统进行了本不应该进行的 reschedule, 使得多进程图像出现了错误的执行序列
    操作系统学习笔记7 | 进程同步与合作
  • empty初始值为 -1,P1执行,P1.register=-2;
  • 而在第二行结束切出,P2执行,P2.register 在-1 的基础上-1 == -2;而本应该累加为 -3 这就出现了错误
  • 这就是一种竞争条件,这种调度会让共享数据(empty)发生错误:
  • 类似的,内核中的共享数据,如果不做保护,在多进程时间片轮转的调度策略下,就会出现人无法控制与预料的错误;
    操作系统学习笔记7 | 进程同步与合作

那就是给信号量上锁:

  • 当进程访问信号量并准备修改信号量时,锁阻止其他进程访问它。
    [En]

    when the process accesses the semaphore and is ready to modify the semaphore, the lock prevents other processes from accessing it.*

  • 在进程修改信号量并切换出后,可以解锁,让其他进程也可以这样做。
    [En]

    after the process has modified the semaphore and switched out, it can be unlocked and let other processes do the same.*

这种 只能一次做完,不能做一半停下来的工作,OS中就称为 原子操作,突出一个 不可分割

!临界区! 是指: 一次只允许一个进程进入的某进程的那一段代码。比如 读写、修改信号量的那段代码一定是临界区。

如何对关键区域进行标注,达到关键区域的预期效果?

[En]

How to mark the critical area and achieve the expected effect of the critical area?

  • 在计算机中以代码实现(进入区和退出区)
    [En]

    it is implemented in code in the computer ( * entry zone and exit zone * )*

  • 下面会介绍 三个方法

临界区保护的原则:

  • 基本原则:互斥进入; 如果一个进程在临界区中执行,则其他进程不能进入;
  • 有空让进:临界区空闲的时候,应尽快选择出一个进程进入临界区(不能所有人卡着门口,结果一个人都进不去)
  • 有限等待:进程发出请求进入临界区的等待时间必须是有限的,不能出现饥饿问题(不能总是让别人进,我也要尽快进去)

像值日一样,轮到进程A( turn==0),进程A就进入临界区,轮不到则使用 while(turn!=0)&#xFF1B;自旋空转;当进程A 退出临界区,则 turn=1,轮到下一个进程使用。

让我们来分析一下这种方法:

[En]

Let's analyze this method:

  • 满足互斥进入,一次只能进入一个进程
    [En]

    meet mutually exclusive entry, only one process can be entered at a time*

  • 不满足有空让进,如果P0退出临界区,P1不进入临界区,则turn还是1,P0再度想进入临界区,就会被拒绝。但此时临界区使用者为空。
  • 轮换法也不一定满足 有限等待,如果P0完成一次临界区操作后,P1在剩余区死循环,那么P0就永远进不去临界区了,产生了饥饿

轮换法的主要缺点是,你有空时不允许进入,就像值班一样。如果你看到垃圾,但并不是因为你没有值班权限,你只能视而不见。

[En]

The main drawback of the rotation method is that you are not allowed to enter when you are free, just like on duty. If you see garbage, but it is not because you do not have the authority to be on duty, you can only turn a blind eye to it.

如何改进呢?还有一个直观的想法。

[En]

How to improve it? There is also an intuitive idea.

  • 下图中的例子是一对夫妇购买牛奶的情况。如果采用轮换的方法,如果轮换时间为10分钟,夫妻双方都会去买牛奶,如下图所示,结果是买得更多。
    [En]

    the example in the figure below is the situation in which a couple buys milk. If the rotation method is adopted, if the rotation time is 10 minutes, both husband and wife will go to buy milk as shown below, resulting in buying more.*

    操作系统学习笔记7 | 进程同步与合作

标记是如何起作用的?

[En]

How does markedness work?

  • 看看代码:
  • P0 要进临界区,就先标记自己, flag[0]=true,然后判断 P1 的标记,如果 P1 已经标记,就等待;

    同理其他进程也是,进临界区之前先标记自己为true,然后等待别的进程的标记变为false

下面分析这种方法:

  • 互斥:满足两个进程不能同时进入临界区。
    [En]

    Mutual exclusion: satisfied that two processes cannot enter the critical zone at the same time.*

  • 有空让进:也不满足,如果进程P0执行第一句, flag[0]=true,接着P1 进行第一句 flag[1]=true,再切换回P0执行while时进入自旋空转了。同理 切回 P1的while也发生自旋空转。谁也进不去临界区。
    操作系统学习笔记7 | 进程同步与合作
  • 有限的等待:这并不能满足有限的等待。
    [En]

    Limited waiting: this does not satisfy limited waiting.*

  • 所以事实上,我们应该让其中一对夫妻更加勤奋--不对称的分数。也就是说,在一个过程中多做考虑:比如,让丈夫多想一想:妻子看到纸条,就不用再考虑买牛奶了;丈夫看到纸条,就等一段时间,看看有没有牛奶。如果没有,那就更勤奋去买牛奶。如下图所示:
    [En]

    so in fact, we should make one of the husband and wife more diligent-asymmetrical marks. That is, to do more consideration in a process: for example, let the husband think more: when the wife sees the note, she no longer has to think about buying milk; when the husband sees the note, he waits for a period of time to see if there is milk. If not, then * more diligently * to buy milk. As shown in the following figure:*

标记和轮转的结合。

事实上,轮换(值班)是不对称的,在负责的时间里思考更多的事情。尝试将上述两个基本考虑因素结合起来。

[En]

In fact, rotation (on duty) is asymmetrically marked, thinking about more things in the responsible time. Try to combine the above two basic considerations.

  • 依然打标记
flag[0]=true;
flag[1]=true;
  • 加上值日/轮转,给进程P0的 turn 初值赋1;P1的 turn 初值赋0;

    视频弹幕的主要问题是:不理解左右两个turn是一个变量,这么写并不冲突,只是在防止上文两者卡死的情况出现

  • 达到的效果是:
  • 对于进程P0,如果P1标记了,并且轮到了P1( turn=1),则P0自旋空转,让P1进入临界区;
  • 当P1退出临界区,turn = 0;那么P0就可以结束while空转,进入临界区。

下面分析这种方法:

  • 互斥性:满足。可用反证法假设两个进程都进入,turn=0=1,不可能。
  • 有空让进:满足。有空,假设进程P1不在临界区,即flag[1]=false,那么P0就不会在while处空转,直接进入临界区。
  • 有限等待:满足。这是因为turn只能取0/1,两者不会同时停在while。

如下图右侧所示,使用此流程(红色):

[En]

As shown on the right side of the following figure, use this process (red):

  • 进入临界区时,置位 flag[i]=true, turn=j,如果 j 进程的 flag==true,则空转,
  • 否则进入临界区修改信号量。
    [En]

    otherwise, enter the critical area to modify the semaphore.*

  • 退出临界区时flag[i]=false;

就不会使 empty 出现语义错误。这个算法是正确的。

多进程情况下,采用面包店算法;是 Peterson算法的扩展与改进。

  • 标记:
  • 每个进程进入时取一个非零序号

    进入时获得的非零序号是当前最大的序号 +1,保证有序。

  • 进程离开时置序号位为0,

    不为0的序号就算为打上标记

  • 轮换:当多个进程被标记(非零)时,序列号最小的条目
    [En]

    rotation: when multiple processes are marked (non-zero), the entry with the lowest sequence number*

    这保证了非对称性,总有一个优先。

  • 具体代码实现如下图:
  • 进入时,除了取号(最大值+1),还需要设计一个 choosing 数组,来确保每次挑选序号的进程只有一个。如果有人正在选号: while(choosing[j]);则等待。
  • 退出时将 标记/序号 置为0 : num[i]=0;

让我们分析一下这个算法:

[En]

Let's analyze this algorithm:

  • 相互排斥:满意。因为由于取数的限制,只有一个最小的。
    [En]

    Mutual exclusion: satisfaction. Because due to the restriction of taking numbers, there is only one smallest one.*

  • 允许让行:如果关键区域内没有进程,则必须进入最小序号进程。
    [En]

    available to give way: if no process is in the critical area, the minimum sequence number process must enter.*

  • 有限等待:离开临界区的流程必须再次排在队列末尾,这样才能进行有限时间的等待。
    [En]

    Limited waiting: the process leaving the critical area must be at the end of the queue again, so waiting for a limited time can be carried out.*

但是这种 算法还是太麻烦,并且不断取号,序号会有溢出风险,我们还需要设置机制来避免溢出。

上述算法是在软件层面上完成的,比较复杂,以下两种方法在硬件上实现。

[En]

The above algorithm is done at the software level, which is more complex, and the following two methods are implemented in hardware.

  • 关键区:只允许一个进程进入;换句话说,此时阻止调度其他进程。
    [En]

    critical area: only one process is allowed to enter; in other words, other processes are prevented from being scheduled at this time.*

  • 进程调度取决于中断。如果在硬件级别关闭中断,则不会插入其他进程,也不会有指令交错。
    [En]

    process scheduling depends on interrupts. If interrupts are turned off at the hardware level, no other processes will be inserted, and there will be no interleaving of instructions.*

  • cli 命令就是关闭中断的指令;
  • sti 命令 打开中断
  • schedule() 是主动的程序调度,不使用中断,而检查程序时间片是否用完了进行的调度涉及时钟中断, 所以这里的关中断是防止发生不受控制的时钟中断,从而引起程序调度
  • 更细致版本: cli()sli() 修改的是 IF 中断标志位,其位于 EFLAGS 寄存器中, schedule() 切换到下一进程后马上会执行 iret,此时会将内核栈中的EFLAGS 弹栈,再次开启中断

但是这种方法在多CPU、多核的情况下效果不好:

  • 中断的原理:CPU上有一个中断寄存器INTR,如果置为1(比如时钟中断来临时),则代表需要中断,引起调度;
  • 而多核CPU上,我们只能控制当前CPU的INTR,不能管理别的CPU的中断与否。

实验五信号量的实现可以使用这种方案,工大的模拟器模拟出来的计算机是单CPU的。

让我们再考虑一件事:为了只有一个进程进入临界区工作,我们必须锁定信号量,临界区。什么是锁?

[En]

Let's think about one more thing: in order for only one process to enter the critical section to work, we have to lock the semaphore, the critical section. * what is a lock?

  • 可以考虑用一个信号量/一个整数来描述锁的状态,就像上文1.5中的 mutex
  • 但这种想法显然为时过早,因为我们使用信号量来保护信号量。
    [En]

    but this idea is obviously premature, because we use semaphores to protect semaphores.*

  • 这就意味着不可行吗?不妨考虑一下前面提到的原子性。
  • 如果把修改 mutex 的指令做成 原子指令

    即中途不可能打断,要么执行,要么不执行, 那么执行时也就自动上锁.

  • 用硬件原子指令修改一个整型变量,然后根据该变量判断是否进入临界区。

    [En]

    modify an integer variable with hardware atomic instructions, and then judge whether it should enter the critical area according to this variable.*

  • 下图是一种代码实现: 通过 TestAndSet 原子性操作,实现 while(TestAndSet(&lock));的一次执行,不会被打断。

    这里弹幕的问题主要是不理解 X 和 lock 是公用的一块内存,因为传递的参数是地址。

一句话: 用临界区保护信号量,用信号量实现进程同步。

3. 信号量代码实现

信号量的原理很复杂,但代码实现相对简单。

[En]

The principle of semaphore is complex, but the code implementation is relatively simple.

信号量的用途:

  • 用户程序可以使用信号量来实现同步
    [En]

    user programs can use semaphores to achieve synchronization*

  • OS内部也要使用大量信号量代码来完成进程同步

下面还是以 生产者-消费者 为例,

  • sem_wait() 根据传入的 sd 找到对应的 value,如果 value-- < 0,说明没有空余位置,应当阻塞自己,将自己放入等待队列;

    注意:这里后--; 是先执行判断再减1 即前提是if为true才会减value。 放入等待队列后 进行 schedule,切换下一个进程就绪.

这里的不完整代码就是实验五需要完成的内容之一。
* 本部分假定与LInux 0.11 适配,使用 单CPU,可以使用2.5.5 中的硬件指令关中断的方法。
* 在临界区前后加入 cli() 和 sti() 保护信号量。

Linux 0.11 的内核中没有上述信号量的设计,如何实现进程间同步呢?

例子:用户程序发出read系统调用,在内核中最终调用bread,到磁盘上读磁盘块;

具体细节会在后面讲文件系统的时候讲;

  • 首先获得一个空闲的内存bh用于缓冲数据,bh的数据类型是 buffer_head;采用DMA将磁盘块内容逐步读进来。
  • ll_rw_block(READ, bh),启动磁盘读;
  • wait_on_buffer(bh),在缓冲区bh上等待, 即启动磁盘读之后睡眠,等待磁盘读完由相关中断唤醒。
  • bh中有类似信号量的数据: bh->b_lock; 各个进程根据这个lock决定如何工作; 同样需要对其进行保护,添加 cli() 和 sti().

读取磁盘时, lock_buffer() 中的 b_lock=1,表示已经锁上了;那么当前进程 sleep_on(&bh->b_wait); 当读完后通过中断会解锁。 这里的机制跟前面信号量机制不同的是:
- 这里用的是 while(1) (而不是if)
- 为什么是while 看下面:

while(信号量) 的工作机制:

  • 我们需要从 sleep_on 这里看起,看看进程如何 "睡"、如何唤醒(唤醒时就能看出 while 的机制)
  • 如下图右侧代码所示:
    [En]

    as shown in the code on the right side of the following figure:*

    *

struct task_struct *tmp;
tmp=*p;
*p=current;

这是很隐蔽的队列,就是 把当前进程放入阻塞队列
* 将自己的状态改为阻塞状态,调用 schedule 切换进程;后面被唤醒,再调度切换回来时,会从这里恢复执行
* f (tmp) temp->state=0; 当前进程被唤醒了,那么队列中的下一个进程也被唤醒;

上面提到的秘密队列到底是什么样子的?

[En]

What exactly does the secret queue mentioned above look like?

  • sleep_on 的函数参数应当是一个队列,所以按照以前的知识,我们应当传入队首的指针,而这里**p是队首指针的指针。
  • tmp 是局部变量,使其指向 task_struct.

  • 再将 *p 指向 current,移向了当前(正要入队)的 task_struct;按照数据结构的知识,这里是新来的放到了队首。

  • 按照数据结构的头插法,task_struct 应该有一个 next 指针,让当前进程的 task_struct->next 指向 tmp,队列链接就完成了
  • 但是设计者考虑了内核的特性,这里的tmp局部变量,已经保存在了内核栈中
  • tmp 局部变量的作用,就是用于指向队列中下一个进程的 task_struct,作用相当于 next 指针,如下图中的虚线所示

解释为什么 tmp 可以作为 next 指针:

  • 局部变量tmp是放在栈中,代码在内核态执行,tmp是放在内核栈。
  • 当前进程的内核栈在当前进程中能找到,切换时内核栈会跟着切换,所以切换后可以找到当前进程的内核栈,当前进程的内核栈中可以找到当前进程的tmp
  • 而当前进程的tmp指向了下一个进程的PCB,下一个进程的PCB中可以找到下一个进程的内核栈,下一个进程的内核栈中可以找到也可以找到下一个进程的tmp,下一个进程的tmp指向再下一个进程的PCB,以此循环

如何将放入 sleep_on 的进程唤醒呢?

  • 执行磁盘中断时,会执行 end_request(1)
  • end_request(1) 会执行 unlock_buffer();
  • unlock_buffer() 会将 lock 置为0,并wake_up;
  • wake_up 在队列不空的情况下( p&&*p)将队首的PCB的state置为0,即为就绪态,此时唤醒了队首进程

进程A被唤醒,应当从哪里执行?

  • 显然,从你睡觉前停下来的地方。
    [En]

    obviously, from where you stopped before you went to sleep.*

  • 回看上面 sleep_on 的代码,state设为阻塞态,schedule到其他进程切换
  • 所以唤醒后继续执行 :
if(tmp){
    tmp -> state = 0;
}

这两行代码唤醒了队首进程的下一个进程B;同样这个进程B会执行相同的两行代码唤醒B的下一个进程C。依次递推, 将阻塞队列中的全部进程唤醒。

  • 注意这里的"唤醒",只是它们能够被调度,并不意味着已经被调度。
  • 接下来会用调度算法去找优先级最高的下一个进程X,调度执行。
  • 该进程X执行后进入临界区,会把lock 锁上(=1);这时其他进程依次while,把自己休眠掉。

到这里其实就解释了 3.2 最开始 lock_buffer 中,为什么使用的是 while 循环,因为这里会把阻塞队列中的所有进程唤醒,而接下来只有一个进程能够进入临界区并上锁,剩下的进程需要再次sleep

而 if 只唤醒阻塞队列中第一个。

为什么要将所有进程都唤醒?我们前面介绍的 if 方案只需要唤醒一个。

  • if 方案中 排在前面的进程一定先执行,但是后来的进程优先级可能更高;
  • 在阻塞队列中,你不能确定剩下的进程的优先级是否更高,所以干脆全部唤醒,让 schedule() 来决定到底切换给谁
  • 回看前面的while循环:
lock_buffer(buffer_head *bh){
    cli();
    while(bh->b_lock){
        sleep_on(&bh->b_wait);
    }
    bh -> b_lock = 1;
    sti();
}

可见这里的while循环是对所有唤醒的进程进行判断的过程,让高优先级的进入,其他的经过循环判断后睡眠。

while(lock) 和前面 if(signal) 有什么异同?

  • 前者不需要负数,不需要记要记录阻塞队列中有多少进程在等待。因为它每次都把所有都唤醒,通过 while 判断将不能进入临界区的进程休眠。
  • 前者唤醒阻塞队列中的所有进程,并根据优先级进行调度
    [En]

    the former wakes up all processes in the blocking queue and schedules them according to priority*

  • 后者唤醒第一个阻塞队列并按顺序(且仅按顺序)调度它们;后者的想法是直观的,但缺点是显而易见的。
    [En]

    the latter wakes up the first of the blocking queues and schedules them in order (and only in order); the idea of the latter is intuitive, but the drawback is obvious.*

推荐用 if 这个直观想法实现 实验五,再用 while 实现。

4. 死锁处理

这是这一过程的最后一部分。对于多进程图像,死锁也可能是一个问题。

[En]

This is the last part of the process. Deadlocks can also be a problem with multi-process images.

再回到 生产者-消费者 这个例子;回到 1.5 Part.

  • 如果您更改信号量的使用顺序,如下所示,将会出现死锁:
    [En]

    if you change the order in which semaphores are used, as shown below, a deadlock will occur:*

    因为是用户程序,用户完全可以这样调换(默认用户不知情);即先申请mutex后申请empty。

  • 运行一下:
  • 生产者 A 进程(左)运行mutex ,原为1,赋值为0;
  • A进程运行 empty,0,表示缓冲区满了,执行完后变为-1, 阻塞
  • 消费者 B进程 执行,mutex 0变为-1, 阻塞
  • 而 A 进程锁在 empty,必须 B进程 执行V(empty)方可解锁;而 V(empty) 依赖于 P(mutex);
  • B 的 P(mutex) 依赖于 A 的 V(mutex),而后者已经卡住了。操作系统学习笔记7 | 进程同步与合作

死锁:多个进程由于互相等待对方持有的资源而造成谁都无法执行的情况

设想再来一个进程C,想要申请 mutex,也会死锁,与之关联的进程可能也会死锁。这样就像感染一样,牵连到的进程越来越多。电脑变得很慢,卡死。

关于死锁,有一个很形象的图,下图右侧,A的前进被B阻碍,B的前进被C阻碍,C的前进被D阻碍,D的前进被A阻碍...

具体成因归纳:

  • 有些资源(如信号量)是互斥的,不能被其他人使用
    [En]

    some resources (such as semaphores) are mutually exclusive and cannot be used by others*

  • 进程X占用了这种资源,不释放,又去申请其他资源;
  • 恰巧申请的资源正被进程N占用,进程X会等待;
  • 如果进程N正好 要申请 X 占用的互斥资源,则进入死锁。

简单地说,死锁的必要条件是:

[En]

To be brief, the necessary conditions for deadlocks:

联系生活,处理好以下几个方面的问题:

[En]

Connect with life and deal with a problem in the following aspects:

死锁忽略:死锁还是一个小概率事件,假如个人PC机死机了,则可以重启来解决;但另外一些比较重要的场景,例如卫星上的操作系统,银行的操作系统就肯定不能死锁忽略了。

死锁预防的基本思想是在进程执行之前打破死锁发生的必要条件,有两个考虑因素:

[En]

The basic idea of deadlock prevention is to break the necessary conditions for deadlocks to occur before the process is executed, and there are two considerations:

  • 流程实施前一次性申请所有所需资源,不必同时申请其他资源。(中断请求和保持条件)
    [En]

    apply for all required resources at once before the implementation of the process, so that you do not have to apply for other resources at the same time. * (break request and hold conditions) * *

  • 缺点:
    1. 需要预知未来,编程困难; 比如有一些资源是通过if来决定是否申请的,这种方法需要编译时列出全部需要资源,全部申请。
    2. 申请全部资源意味着一些分配到的资源很长时间后才会被使用,资源利用率低;
  • 资源顺序分配,首先对系统中的资源进行编号,规定每个进程必须按编号递增的顺序请求资源,类似的资源(即编号相同的资源)一次性申请。(打破循环等待条件)
    [En]

    Sequential resource allocation, first numbering the resources in the system, stipulating that each process must request resources in the order of increasing numbers, and similar resources (that is, resources with the same number) are applied all at once. * (break the loop wait condition) * *

    这个不太好理解: 一个进程只有已占有小编号的资源时,才有资格申请更大编号的资源。按此规则,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象。
    操作系统学习笔记7 | 进程同步与合作

死锁避免的考虑是 判断进程的此次请求是否会引起死锁。而判断算法就是 银行家算法

银行家算法:寻找是否存在可完成的执行序列/安全序列 P0.P1.P2...Pn

算法过程:

  • 上表三栏依次显示已分配的资源、需要的资源和仍在系统内的资源。
    [En]

    the three columns of the table above show in turn the resources allocated, the resources needed and the resources still in the system.*

  • 根据 2-3-0 的资源剩余量,只能决定给P1使用,P1执行完毕释放资源为 5-3-2
  • 继续同理判断...

  • 答案是AD;

银行家算法的实现,其实就跟上面的过程相差不大,时间复杂度 T(n)=O(mn2)

银行家算法只计算出安全序列。它如何为避免僵局服务?

[En]

*The banker algorithm only works out the security sequence. How can it serve for deadlock avoidance? *

  • 分支预测。 将申请假设为分配策略,然后用银行家算法判断是否存在安全序列。如果没有,则拒绝申请。

  • 算法分析:系统中的进程和资源都相当多,并且每次申请都要这么做,计算量很大。

由于避免死锁的成本太高,而发生死锁的概率很低,所以在发现死锁后就可以处理死锁,而且成本很低。

[En]

Since the cost of avoiding deadlock is too high, and the probability of deadlock is very low, we can deal with deadlock after finding deadlock, and the cost is very low.

  • 定时检测或系统发现资源利用率低时,再次执行庄家算法
    [En]

    timing detection or when the system finds that the resource utilization is low, execute the banker algorithm again*

  • 找到死锁的进程序列,从中挑选一个进程回滚。
    [En]

    find the deadlock process sequence and pick a process from it to roll back.*

  • 如何回滚?
  • 尝试,回滚到一定程度再用银行家算法测试;
  • 选择哪个进程回滚?
  • 挑选哪个进程回滚都不是很合适。因为有些进程可能已经运行了很长时间,甚至接近结束。
  • 如何实现回滚?
  • 有许多机制。比如设立一种机制让系统记录进程的历史信息,设置还原点。

PC的通用操作系统上还是采用 死锁忽略这个朴素方法的。因为可见4.3.1~4.3.3 的三种方法 消耗都不小,而死锁忽略的代价很小。

Original: https://www.cnblogs.com/Roboduster/p/16643905.html
Author: climerecho
Title: 操作系统学习笔记7 | 进程同步与合作



相关阅读

Title: 【文献阅读】FastFlow: Unsupervised Anomaly Detection and Localization via 2D Normalizing Flows

FastFlow: Unsupervised Anomaly Detection and Localization via 2D Normalizing Flows

摘要

  1. 简述问题背景:当采集和标记足够的异常数据是不可行的时候,无监督的异常检测和定位对实际应用至关重要
  2. 前人方法存在的问题:现有的大多数 representation-base的方法都是通过深度卷积神经网络提取正常图像特征,并通过 非参数估计的方法刻画相应的分布。通过计算 测试图像的特征与 估计分布之间的距离来计算异常分数。然而,目前的方法:1不能有效地将图像特征映射为 可处理的基分布,2忽略了 局部特征和全局特征之间的关系,而这对识别异常很重要。
  3. 我们提出的方法:提出了使用 2D normalizing flowFastFLow,并使用它来估计概率分布。具体来说, FastFLow可以作为 plug-in模块,与任意的深度特征提取器(如ResNet和Vision Transformer)一起使用,用于无监督异常检测和定位。在训练阶段,FastFlow学习将输入的视觉 特征转化为可处理的 分布,并在测试阶段得到异常的似然(即概率)。
  4. 得到的结果:在MVTec AD数据集上的大量实验结果表明,fastflow在准确性和推理效率方面超过了以往的先进方法。该方法具有较高的推理效率,异常检测AUC达到99.4%。

1 Introduction

\qquad 计算机视觉中的异常检测与定位的目的是确定异常图像,以及定位异常,广泛应用于工业检测缺陷,医学影像检查,安全检查等领域。然而,由于异常的概率密度低,正常与异常数据通常表现出严重的长尾分布,甚至在某些情况下没有异常样本。这一现实的缺点使得在实践中很难收集和注释大量的异常数据来进行监督学习。为了解决这一问题,提出了一种无监督异常检测方法,即 one-class 分类或 _out-of-distribution_检测方法。也就是说,我们在训练中只使用正常样本但是在测试中要可以检测出异常。
\qquad 一种很有前途的无监督异常检测方法是利用深度神经网络获取正态图像的特征,并用一些统计方法对其分布进行建模,然后检测具有不同分布的异常样本该方法包括两个主要部分: 特征提取module和 分布估计module。

\qquad 在分布估计模块上,以往的方法都是采用 非参数方法对正态图像的特征分布进行建模。例如,通过计算特征的均值和方差估计 多维高斯分布,或者使用聚类算法,通过 标准聚类估计这些正常样本的特征。最近,一些工作开始使用 normalizing flow来估计分布。通过 最大化正态图像特征的对数似然的可训练过程,他们将正态图像特征嵌入到标准正态分布中,并使用概率来识别和定位异常。然而,原有的一维归一化流模型需要将二维输入特征平面化为一维向量来估计其分布,这破坏了二维图像固有的空间位置关系,限制了流模型的能力。除此之外,这些方法需要通过 滑动窗口法对图像中大量的 _patch_进行特征提取,并对每个 _patch_进行异常检测,从而获得异常定位结果,这导致 推理复杂度高,限制了这些方法的实用价值。\qquad 为了解决上述问题,我们提出了 FastFlow,将原来的归一化流扩展到二维空间。我们在流模型中使用 全卷积网络作为子网,它可以 保持空间的相对位置,提高异常检测的性能。同时支持对整幅图像进行端到端推理,直接将异常检测和定位结果一次性输出,提高了推理效率。

\qquad对于异常检测中的特征提取模块,除了使用CNN的一些backbone如ResNet 获取判别特征外,大部分现有工作重点研究如何合理利用多尺度特征在不同尺度和语义层次识别异常,并通过滑动窗口方法实现像素级异常定位。 全局信息与局部异常相关性的重要性无法充分利用,而滑动窗口方法需要测试大量的图像patch,计算复杂度高。为了解决这些问题,我们使用FastFlow通过 端到端测试阶段来获得全局和局部特征分布的可学习建模,而不是设计复杂的多尺度策略和使用滑动窗口方法。我们在两种backbone上进行了实验:Vision Transformers和CNN。与CNN相比,Vision Transformers可以提供一个全局的接受域,更好地利用全局和局部信息,同时保持不同深度的语义信息。因此,我们在Vision Transformers中只使用某一层的特征。用Vision Transformers替换CNN似乎微不足道,但我们发现,在其他方法中执行这个简单的替换实际上会降低性能,但我们的2D流在使用CNN时获得了具有竞争力的结果。我们的FastFlow具有更强的全局和局部建模能力,所以它可以更好地发挥Transformers的有效性。

\qquad如图1所示,在我们的方法中,我们首先通过 特征提取器提取视觉特征,然后将其输入到FastFlow中来 估计概率密度。在训练阶段,我们的FastFlow用正常图像进行训练,以二维方式将原始分布转化为标准正态分布。在推理中,我们使用二维特征上每个位置的概率值作为异常得分。

\qquad 综上所述,本文的主要贡献是:

  1. 我们提出了一种二维归一化流FastFlow来进行异常检测和定位,该流采用全卷积网络和二维损失函数来有效地模拟 全局和局部分布。
  2. 我们为FastFlow设计了一种轻量级的网络结构,所有步骤都采用大卷积核和小卷积核交替叠加。该方法采用端到端的推理阶段,具有较高的效率。
  3. 提出的FastFlow模型可以作为plug-in模型使用各种不同的特征提取器。在MVTec异常检测数据集上的实验结果表明,我们的方法在准确性和推理效率方面都优于以往最先进的异常检测方法。

2 Related Work

3 Methodology

在本节中,我们将介绍方法的pipeline和FastFlow的架构,如图2所示。首先建立了无监督异常检测的 问题定义,并介绍了基于表示方法的 可学习概率密度估计模型的基本方法。然后分别对 特征提取器FastFlow模型进行了详细描述。
操作系统学习笔记7 | 进程同步与合作

; 3.1 Problem Definition and Basic Methodology

无监督异常检测也称为one-class分类或out-of-distribution检测,需要模型来判断测试图像是正常还是异常。异常定位需要一个更细粒度的结果,给出每个像素的异常标签。在训练阶段,只观察到正常图像,但在 测试中正常图像和异常图像同时出现。主流方法之一是基于表示的方法,即从正常图像或正常图像patch中提取判别特征向量,构造分布,并根据测试图像的embedding与分布的距离计算异常得分。 该分布的典型特征是:正常图像的 中心为n-sphere,正常图像呈 高斯分布,或者从KNN中获得存储在存储库中的正常embedding聚类。
(为了看得清楚,另起一段来写)
\qquad在提取训练数据集D = x 1 , x 2 , ⋅ ⋅ ⋅ , x N D={x_1,x_2,···,x_N}D =x 1 ​,x 2 ​,⋅⋅⋅,x N ​的特征之后,其中x i , i = 1 , 2 , ⋅ ⋅ , N x_i,i=1,2,··,N x i ​,i =1 ,2 ,⋅⋅,N是来自分布p X ( x ) p_X(x)p X ​(x )(正常图像特征的分布)的样本,基于表示的异常检测模型P = { P θ : θ ∈ Θ } P={P_θ:θ∈Θ}P ={P θ​:θ∈Θ}(可以理解为一个映射)旨在学习在参数空间Θ ΘΘ中的参数θ θθ,以将来自原始分布p X ( x ) p_X(x)p X ​(x )的所有x i x_i x i ​映射到同一分布p Z ( z ) p_Z(z)p Z ​(z ),其中异常像素或实例映射在分布外。在我们的方法中,我们遵循这一方法,提出了FastFlow P θ P_θP θ​将从backbone中提取的正常图像的高维视觉特征投影到标准正态分布中。

3.2 Feature Extractor

在整个过程中,我们首先通过ResNet或Vision Transformer从输入图像中提取具有代表性的特征。正如第一节中提到的,异常检测任务中的一个重大挑战是把握全局关系,以将这些异常区域与其他局部部分区分开来。因此,在使用Vision Transformer(ViT)时,我们只使用某一层的特征,因为ViT具有更强的捕捉 局部patches和全局特征之间关系的能力。对于ResNet,我们直接使用前三个block中最后一层的特征,并将这些特征放入三个对应的FastFlow模型中。

3.3 2D Flow Model(老实讲我觉得论文这一部分写的没有很详细,建议先去看看Normalizing Flows的相关知识)

我们的2 flow f : X → Z f:X→Z f :X →Z用于投影图像特征X ∈ p X ( x ) X∈p_X(x)X ∈p X ​(x )进入隐藏变量z ∈ z∈z ∈具有双射可逆映射的p Z ( z ) p_Z(z)p Z ​(z )。对于该双射函数,X的分布可以这样得出:

操作系统学习笔记7 | 进程同步与合作
我们可以通过以下方式从p Z ( z ) p_Z(z)p Z ​(z )出发来估计图像特征的对数似然:
操作系统学习笔记7 | 进程同步与合作
其中z ∼ N ( 0 , 1 ) z\sim N(0,1)z ∼N (0 ,1 ),并且上述的分式为双射可逆流模型雅可比行列式,z = f θ ( x ) z=f_\theta(x)z =f θ​(x )并且x = f θ − 1 ( z ) x=f_\theta^{-1}(z)x =f θ−1 ​(z ),θ \theta θ是2D流模型的参数。在测试阶段,异常图像的特征应该是分布之外的,因此具有比正常图像更低的似然,并且该似然可以用作异常分数。具体来说,我们对每个通道的二维概率求和,以获得最终的概率图,并使用双线性插值将其上采样到输入图像分辨率。在实际实现中,我们的流模型f 2 d f_{2d}f 2 d ​通过将多个可逆转换块f i f_{i}f i ​堆叠在一个序列中来构建,该序列:

操作系统学习笔记7 | 进程同步与合作
并且:
操作系统学习笔记7 | 进程同步与合作

其中2D flow模型为:
操作系统学习笔记7 | 进程同步与合作
即一共有K个映射block,每个转换块由多个步骤组成。按照那篇文献的研究,我们在每个块中使用仿射耦合层,每个步骤的公式如下:
操作系统学习笔记7 | 进程同步与合作
其中 s ( y a ) s(y_a)s (y a ​) 和 b ( y a ) b(y_a)b (y a ​) 是两个神经网络的输出。s p l i t ( ) split()s p l i t ()和c o n c a t ( ) concat()c o n c a t ()函数沿通道维度执行拆分和串联操作。在原归一化流模型中,两个子网s ( ) s()s ()和b ( ) b()b ()通常被实现为全连接网络,需要对从2D到1D的输入视觉特征进行faltten和squeeze,破坏了特征图中的空间位置关系。为了将原始归一化流转换为2D方式,我们在默认子网中采用二维卷积层来保留流模型中的空间信息,并相应地调整损失函数。特别地,我们采用了一个3×3卷积和1×1卷积交替出现的全卷积网络,它在流模型中保留了空间信息。

; 4 Experiments

4.1 Datasets and Metrics

\qquad我们在三个数据集上对所提出的方法进行了评估:MVTec AD,BTAD和CIFAR-10。MVTec AD和BTAD都是带像素级注释的工业异常检测数据集,用于异常检测和定位。CIFAR-10是为图像分类而建立的,我们使用它来进行异常检测。在前人工作的基础上,我们选择其中一个类别为正常,其余类别为异常。这些工业数据集的异常比CIFAR-10中的异常要细,而且CIFAR-10中的异常更多地与语义高层信息有关。例如,MVTec AD中的异常被定义为小区域,而CIFAR-10数据集中的异常被定义为不同的对象类别。在无监督的情况下,我们使用每个类别的正常图像来训练我们的模型,并在包含正常图像和异常图像的测试图像中对其进行评估。
\qquad该方法和所有可比方法的性能通过图像或像素级的接收工作特性曲线(AUROC)下的面积来衡量。对于检测任务,需要评估模型输出每个输入测试图像的单一分数(异常分数)。在定位任务中,方法需要输出每个像素的异常分数。

4.2 Complexity Analysis

从推理速度、附加推理时间和附加模型参数三个方面对FastFlow等方法进行了复杂性分析,"附加"是指不考虑主干本身。用于测试的机器的硬件配置是...SPADE和PatchCore在每张图像patch的特征上面进行KNN聚类,以及储存图像的patch的特征,它们不需要引入主干以外的参数。CFlow避免了耗时的k近邻搜索过程,但仍需要以切片窗口的形式执行测试阶段。FastFlow采用端到端的推理阶段,推理效率高。分析结果如表1所示,我们 可以知道我们的方法比其他方法快10倍。与同样使用流动模型的CFlow相比,我们的方法可以获得1.5倍的加速比和以及2倍的参数减少。当使用ViT作为特征提取器时,我们的FastFlow可以达到99.4图像级的异常检测AUC,优于CFlow和Patch Core。从额外推理时间的角度来看,我们的方法比Cflow减少了4倍,比Patch Core减少了10倍。在使用ResNet模型作为特征提取器的情况下,我们的FastFlow仍然具有很好的性能。

4.3 Quantitative Results

略(关于CIFAR-10数据集上的表现,该文章的auc并不高,目前已知的最高是97.5,不知道作者为什么要写这个数据集,cifar-10和mvtec数据集本就差异性很大,不适合作为同一个任务来处理)

4.4 Ablation Study

简要概括就是在不同backbone下比较了3x3和1x1交替以及只用3x3的卷积核的速度和AUC。

4.5 Feature Visualization and Generation.

我们的FastFlow模型是一个双向可逆的概率分布转换器。在正向过程中,将来自backbone的特征图作为输入,将其原始分布转化为 二维空间中的标准正态分布。在逆向过程中,FastFlow的逆可以从 特定的概率采样变量生成视觉特征。为了从FastFlow的角度更好地理解这种能力,我们可视化了正向(从视觉特征到概率图)和反向(从概率图到视觉特征)过程。

如图4所示,我们提取了属于皮革类的输入图像的特征,异常区域见红色箭头。通过FastFlow模型进行转发,得到概率图。我们的FastFlow成功地将原始分布转换为标准正态分布。然后,在概率图中用黄色箭头表示的特定空间区域添加噪声干扰,并利用逆Fastflow模型从污染概率图中生成皮革特征张量。在该特征张量中,我们可视化了一个通道的特征图,可以观察到在相应的污染位置出现了新的异常。通过FastFlow模型后,得到 概率图。我们的FastFlow成功地 将原始分布转换为标准正态分布。然后,在概率图中用黄色箭头表示的特定空间区域 添加噪声干扰,并利用 逆Fastflow模型从干扰后的概率图中生成皮革图特征tensor。在该特征张量中,我们可视化了一个通道的特征图,可以观察到在相应的污染位置出现了新的异常。
操作系统学习笔记7 | 进程同步与合作
图:FastFlow的双向可逆过程。"FE"是特征提取器,"FF"是我们的FastFlow模型,"F F − 1 FF^{−1}F F −1"是FastFlow的逆。红色和黄色箭头分别指向原始异常和噪声干扰后引入的新异常。

; 5 Conclusion

本文提出了一种新的无监督异常检测和定位方法FastFlow。我们的主要观察结果是,异常检测和定位需要综合考虑全局和局部信息,采用一种可学习的分布建模方法和高效的推理过程,而这些都是现有方法所忽略的。为此,我们提出了一种具有轻量级结构的二维流模型FastFlow,用于在训练时将正态图像的特征分布投影到标准正态分布,并将这些概率作为测试中的异常得分。FastFlow可以插件的形式用于典型的特征提取网络,例如ResNet和VIT。在MVTec AD数据集上的大量实验结果表明,FastFlow在准确率和推理效率方面优于现有的方法。

Original: https://blog.csdn.net/Q7777727/article/details/121897576
Author: StatisticsLiu
Title: 【文献阅读】FastFlow: Unsupervised Anomaly Detection and Localization via 2D Normalizing Flows