精华内容
下载资源
问答
  • 操作系统 原语模拟 VC 操作系统课程设计作业
  • 操作系统原语

    2021-01-29 14:13:47
    浅析原语概念

    按照层次设计的OS,底层包含一系列独立完成指定操作的公有程序,称为原语。

    原语具有以下特点:

    1. 处于OS最底层,最接近硬件。
    2. 运行起来具有原子性。
    3. 运行时间较短且调用频繁。

    定义原语的直接方法是关闭中断,让它的所有动作完整地进行完再打开中断。

    设备驱动、CPU切换、进程间通信等功能中的部分操作可定义为原语,作为OS内核的组成部分。

    展开全文
  • 操作系统同步原语

    2018-09-16 15:51:59
    在一般的操作系统中,不同的进程可能会分享一块公共的存储区域,例如内存或者是硬盘上的文件,这些进程都允许在这些区域上进行读写。操作系统有一些职责,来协调这些使用公共区域的进程之间以正确的方式进行想要的...
        

    竞态条件

    在一般的操作系统中,不同的进程可能会分享一块公共的存储区域,例如内存或者是硬盘上的文件,这些进程都允许在这些区域上进行读写。
    操作系统有一些职责,来协调这些使用公共区域的进程之间以正确的方式进行想要的操作。这些进程之间需要通信,需要互相沟通,有商有量,才能保证一个进程的动作不会影响到另外一个进程正常的动作,进而导致进程运行后得不到期望的结果。在操作系统概念中,通常用 IPC(Inter Process Communication,即进程间通信)这个名词来代表多个进程之间的通信。
    为了解释什么是竞态条件(race condition),我们引入一个简单的例子来说明:
    一个文件中保存了一个数字 n,进程 A 和进程 B 都想要去读取这个文件的数字,并把这个数字加 1 后,保存回文件。假设 n 的初始值是 0,在我们理想的情况下,进程 A 和进程 B 运行后,文件中 n 的值应该为 2,但实际上可能会发生 n 的值为 1。我们可以考量一下,每个进程做这件事时,需要经过什么步骤:

    1. 读取文件里 n 的值
    2. 令 n = n + 1
    3. 把新的 n 值保存回文件。

    在进一步解释竞态条件之前,必须先回顾操作系统概念中的几个知识点:

    1. 进程是可以并发运行的,即使只有一个 CPU 的时候)
    2. 操作系统的时钟中断会引起进程运行的重新调度,
    3. 除了时钟中断,来自其它设备的中断也会引起进程运行的重新调度

    假设进程 A 在运行完步骤 1 和 2,但还没开始运行步骤 3 时,发生了一个时钟中断,这个时候操作系统通过调度,让进程 B 开始运行,进程 B 运行步骤 1 时,发现 n 的值为 0,于是它运行步骤 2 和 3,最终会把 n = 1 保存到文件中。之后进程 A 继续运行时,由于它并不知道在它运行步骤 3 之前,进程 B 已经修改了文件里的值,所以进程 A 也会把 n = 1 写回到文件中。这就是问题所在,进程 A 在运行的过程中,会有别的进程去操作它所操作的数据。

    唯一能让 n = 2 的方法,只能期望进程 A 和进程 B 按顺序分别完整地运行完所有步骤。
    我们可以给竞态条件下一个定义了

    两个或者多个进程读写某些共享数据,而最后的结果取决于进程运行的准确时序,称为竞态条件。

    在上述的文字中,我们使用进程作为对象来讨论竞态条件,实际上对于线程也同样适用,这里的线程包含但不限于内核线程、用户线程。因为在操作系统中,进程其实是依靠线程来运行程序的。更甚至,在 Java 语言的线程安全中,竞态条件这个概念也同样适用。(参考《Java 并发编程实战》第二章)

    互斥与临界区

    如何避免 race condition,我们需要以某种手段,确保当一个进程在使用一个共享变量或者文件时,其它的进程不能做同样的操作,换言之,我们需要“互斥”。
    以上述例子作为例子,我们可以把步骤 1 - 3 这段程序片段定义为临界区,临界区意味着这个区域是敏感的,因为一旦进程运行到这个区域,那么意味着会对公共数据区域或者文件进行操作,也意味着有可能有其它进程也正运行到了临界区。如果能够采用适当的方式,使得这两个进程不会同时处于临界区,那么就能避免竞态条件。
    也就是,我们需要想想怎么样做到“互斥”。

    互斥的方案

    互斥的本质就是阻止多个进程同时进入临界区

    屏蔽中断

    之前提到的例子中,进程 B 之所以能够进入临界区,是因为进程 A 在临界区中受到了中断。如果我们让进程 A 在进入临界区后,立即对所有中断进行屏蔽,离开临界区后,才响应中断,那么即使发生中断,那么 CPU 也不会切换到其它进程,因此此时进程 A 可以放心地修改文件内容,不用担心其它的进程会干扰它的工作。
    然而,这个设想是美好,实际上它并不可行。第一个,如果有多个CPU,那么进程 A 无法对其它 CPU 屏蔽中断,它只能屏蔽正在调度它的 CPU,因此由其它 CPU 调度的进程,依然可以进入临界区;第二,关于权力的问题,是否可以把屏蔽中断的权力交给用户进程?如果这个进程屏蔽中断后再也不响应中断了, 那么一个进程有可能挂住整个操作系统。

    锁变量

    也许可以通过设置一个锁标志位,将其初始值设置为 0 ,当一个进程想进入临界区时,先检查锁的值是否为 0,如果为 0,则设置为 1,然后进入临界区,退出临界区后把锁的值改为0;若检查时锁的值已经为1,那么代表其他进程已经在临界区中了,于是进程进行循环等待,并不断检测锁的值,直到它变为0。
    但这种方式也存在着竞态条件,原因是,当一个进程读出锁的值为0时,在它将其值设置为1之前,另一个进程被调度起来,它也读到锁的值为0,这样就出现了两个进程同时都在临界区的情况。

    严格轮换法

    锁变量之所以出问题,其实是因为将锁变量由0改为1这个动作,是由想要获取锁的进程去执行的。如果我们把这个动作改为由已经获得锁的进程去执行,那么就不存在竞态条件了。
    先设置一个变量 turn,代表当前允许谁获得锁,假设有两个进程,进程 A 的逻辑如下所示:

            while (turn != 0){// 如果还没轮到自己获取锁,则进入循环等待
            }
            do_critical_region();// 执行临界区的程序
            turn = 1;// 由获得锁的一方将锁变量修改为其它值,允许其它进程获得锁
            do_non_critical_region();// 执行非临界区的程序

    进程 B 的逻辑如下所示:

            while (turn != 1) {// 如果还没轮到自己获取锁,则进入循环等待
            }
            do_critical_region();// 执行临界区的程序
            turn = 0;// 由获得锁的一方将锁变量修改为其它值,允许其它进程获得锁
            do_non_critical_region();// 执行非临界区的程序

    但这里需要考虑到一个事情,假设进程 A 的 do_non_critical_region() 需要执行很长时间,即进程 A 的非临界区的逻辑需要执行较长时间,而进程 B 的非临界区的逻辑很快就执行完,显然,进程 A 进入临界区的频率会比进程 B 小一点,理想的情况下,进程 B 应该多进入临界区几次。但是由于进程 B 在执行非临界区逻辑前会把 turn 设置为 0,等它很快地把非临界区的逻辑执行完后,回来检查 turn 的值时,发现 turn 的值一直都不是 1,turn 的值需要进程 A 把它设置为 1,而进程 A 此时却正在进行着漫长的非临界区逻辑代码,所以导致进程 B 无法进入临界区。
    这就说明,在一个进程比另一个进程慢很多的情况下,严格轮换法并不是一个好办法。

    Peterson 算法

    严格轮换法的问题就出在严格两个字上,即多个进程之间是轮流进入临界区的,根本原因是想要获得锁的进程需要依赖其它进程对于锁变量的修改,而其它进程都要先经过非临界区逻辑的执行才会去修改锁变量。
    严格轮换法中的 turn 变量不仅用来表示当前该轮到谁获取锁,而且它的值未改变之前,都意味着它依然阻止了其它进程进入临界区,恰恰好,一个进程总是要经过非临界区的逻辑后才会去改变turn的值。
    因此,我们可以用两个变量来表示,一个变量表示当前应该轮到谁获得锁,另一个变量表示当前进程已经离开了临界区,这种方法实际上叫做 Peterson 算法,是由荷兰数学家 T.Dekker 提出来的。

        static final int N = 2;
        int turn = 0;
        boolean[] interested = new boolean[N];
    
        void enter_region(int process) {
            int other = 1 - process;
            interested[process] = true;
            turn = process;
            while(turn == process && !interested[other]) {
            }
        }
    
        void exit_region(int process) {
            interested[process] = false;
        }

    进程在需要进入临界区时,先调用 enter_region,离开临界区后,调用 exit_region。Peterson 算法使得进程在离开临界区后,立马消除了自己对于临界区的“兴趣”,因此其它进程完全可以根据 turn 的值,来判断自己是否可以合法进入临界区。

    TSL 指令

    回顾一下我们之前提到的“锁变量”这种方法,它的一个致命的缺点是对状态变量进行改变的时候,如从 0 改为 1 或者从 1 改为 0 时,是可以被中断打断的,因此存在竞态条件。
    之后我们在锁变量的基础上,提出如果锁变量的修改不是由想要获取进入临界区的进程来修改,而是由已经进入临界区后想要离开临界区的进程来修改,就可以避免竞态条件,继而引发出严格轮换法,以及从严格轮换法基础上改进的 Peterson 算法。这些方法都是从软件的方式去考虑的。实际上,可以在硬件 CPU 的支持下,保证锁变量的改变不被打断,使锁变量成为一种很好的解决进程互斥的方法。
    目前大多数的计算机的 CPU,都支持 TSL 指令,其全称为 Test and Set Lock,它将一个内存的变量(字)读取寄存器 RX 中,然后再该内存地址上存一个非零值,读取操作和写入操作从硬件层面上保证是不可打断的,也就是说是原子性的。它采用的方式是在执行 TSL 指令时锁住内存总线,禁止其它 CPU 在 TSL 指令结束之前访问内存。这也是我们常说的 CAS (Compare And Set)。
    当需要把锁变量从 0 改为 1 时,先把内存的值复制到寄存器,并将内存的值设置为 1,然后检查寄存器的值是否为 0,如果为 0,则操作成功,如果非 0 ,则重复检测,知道寄存器的值变为 0,如果寄存器的值变为 0 ,意味着另一个进程离开了临界区。进程离开临界区时,需要把内存中该变量的值设置为 0。

    忙等待

    上述提到的 Peterson 算法,以及 TSL 方法,实际上它们都有一个特点,那就是在等待进入临界区的时候,它们采用的是忙等待的方式,我们也常常称之为自旋。它的缺点是浪费 CPU 的时间片,并且会导致优先级反转的问题。

    考虑一台计算机有两个进程, H 优先级较高,L 优先级较低。调度规则规定,只要 H 处于就绪状态,就可以运行。在某一时刻,L 处于临界区内,此时 H 处于就绪态,准备运行。但 H 需要进行忙等待,而 L 由于优先级低,没法得到调度,因此也无法离开临界区,所以 H 将会永远忙等待,而 L 总无法离开临界区。这种情况称之为优先级反转问题(priority inversion problem)

    进程的阻塞与唤醒

    操作系统提供了一些原语,sleep 和 wakeup。

    内核提供给核外调用的过程或者函数成为原语(primitive),原语在执行过程中不允许中断。

    sleep 是一个将调用进程阻塞的系统调用,直到另外一个进程调用 wakeup 方法,将被阻塞的进程作为参数,将其唤醒。阻塞与忙等待最大的区别在于,进程被阻塞后CPU将不会分配时间片给它,而忙等待则是一直在空转,消耗 CPU 的时间片。

    信号量

    首先需要明白的一点是,信号量的出现是为了解决什么问题,由于一个进程的阻塞和唤醒是在不同的进程中造成的,比如说进程 A 调用了 sleep() 会进入阻塞,而进程 B 调用 wakeup(A)会把进程 A 唤醒。因为是在不同的进程中进行的,所以也存在着被中断的问题。加入进程 A 根据逻辑,需要调用 sleep() 进入阻塞状态,然而,就在它调用 sleep 方法之前,由于时钟中断,进程 B 开始运行了,根据逻辑,它调用了 wakeup() 方法唤醒进程 A,可是由于进程 A 还未进入阻塞状态,因此这个 wakeup 信号就丢失了,等待进程 A 从之前中断的位置开始继续运行时并进入阻塞后,可能再也没有进程去唤醒它了。
    因此,进程的阻塞和唤醒,应该需要额外引进一个变量来记录,这个变量记录了唤醒的次数,每次被唤醒,变量的值加1。有了这个变量,即使wakeup操作先于sleep操作,但wakeup操作会被记录到变量中,当进程进行sleep时,因为已经有其它进程唤醒过了,此时认为这个进程不需要进入阻塞状态。
    这个变量,在操作系统概念中,则被称为信号量(semaphore),由 Dijkstra 在 1965 年提出的一种方法。
    对信号量有两种操作, down 和 up。
    down 操作实际上对应着 sleep,它会先检测信号量的值是否大于0,若大于0,则减1,进程此时无须阻塞,相当于消耗掉了一次 wakeup;若信号量为0,进程则会进入阻塞状态。
    而 up 操作对应着 wakeup,进行 up 操作后,如果发现有进程阻塞在这个信号量上,那么系统会选择其中一个进程将其唤醒,此时信号量的值不需要变化,但被阻塞的进程已经少了一个;如果 up 操作时没有进程阻塞在信号量上,那么它会将信号量的值加1。
    有些地方会把 down 和 up 操作称之为 PV 操作,这是因为在 Dijkstra 的论文中,使用的是 P 和 V 分别来代表 down 和 up。
    信号量的 down 和 up 操作,是操作系统支持的原语,它们是具有原子性的操作,不会出现被中断的情况。

    互斥量

    互斥量(mutex)其实是信号量的一种特例,它的值只有 0 和 1,当我们不需要用到信号量的计数能力时,我们可以使用互斥量,实际上也意味着临界区值同一时间只允许一个进程进入,而信号量是允许多个进程同时进入临界区的。

    展开全文
  • 竞态条件在一般的操作系统中,不同的进程可能会分享一块公共的存储区域,例如内存或者是硬盘上的文件,这些进程都允许在这些区域上进行读写。操作系统有一些职责,来协调这些使用公共区域的进程之间以正确的方式进行...

    竞态条件

    在一般的操作系统中,不同的进程可能会分享一块公共的存储区域,例如内存或者是硬盘上的文件,这些进程都允许在这些区域上进行读写。

    操作系统有一些职责,来协调这些使用公共区域的进程之间以正确的方式进行想要的操作。这些进程之间需要通信,需要互相沟通,有商有量,才能保证一个进程的动作不会影响到另外一个进程正常的动作,进而导致进程运行后得不到期望的结果。在操作系统概念中,通常用 IPC(Inter Process Communication,即进程间通信)这个名词来代表多个进程之间的通信。

    为了解释什么是竞态条件(race condition),我们引入一个简单的例子来说明:

    一个文件中保存了一个数字 n,进程 A 和进程 B 都想要去读取这个文件的数字,并把这个数字加 1 后,保存回文件。假设 n 的初始值是 0,在我们理想的情况下,进程 A 和进程 B 运行后,文件中 n 的值应该为 2,但实际上可能会发生 n 的值为 1。我们可以考量一下,每个进程做这件事时,需要经过什么步骤:

    读取文件里 n 的值

    令 n = n + 1

    把新的 n 值保存回文件。

    在进一步解释竞态条件之前,必须先回顾操作系统概念中的几个知识点:

    进程是可以并发运行的,即使只有一个 CPU 的时候)

    操作系统的时钟中断会引起进程运行的重新调度,

    除了时钟中断,来自其它设备的中断也会引起进程运行的重新调度

    假设进程 A 在运行完步骤 1 和 2,但还没开始运行步骤 3 时,发生了一个时钟中断,这个时候操作系统通过调度,让进程 B 开始运行,进程 B 运行步骤 1 时,发现 n 的值为 0,于是它运行步骤 2 和 3,最终会把 n = 1 保存到文件中。之后进程 A 继续运行时,由于它并不知道在它运行步骤 3 之前,进程 B 已经修改了文件里的值,所以进程 A 也会把 n = 1 写回到文件中。这就是问题所在,进程 A 在运行的过程中,会有别的进程去操作它所操作的数据。

    唯一能让 n = 2 的方法,只能期望进程 A 和进程 B 按顺序分别完整地运行完所有步骤。

    我们可以给竞态条件下一个定义了

    两个或者多个进程读写某些共享数据,而最后的结果取决于进程运行的准确时序,称为竞态条件。

    在上述的文字中,我们使用进程作为对象来讨论竞态条件,实际上对于线程也同样适用,这里的线程包含但不限于内核线程、用户线程。因为在操作系统中,进程其实是依靠线程来运行程序的。更甚至,在 Java 语言的线程安全中,竞态条件这个概念也同样适用。(参考《Java 并发编程实战》第二章)

    互斥与临界区

    如何避免 race condition,我们需要以某种手段,确保当一个进程在使用一个共享变量或者文件时,其它的进程不能做同样的操作,换言之,我们需要“互斥”。

    以上述例子作为例子,我们可以把步骤 1 - 3 这段程序片段定义为临界区,临界区意味着这个区域是敏感的,因为一旦进程运行到这个区域,那么意味着会对公共数据区域或者文件进行操作,也意味着有可能有其它进程也正运行到了临界区。如果能够采用适当的方式,使得这两个进程不会同时处于临界区,那么就能避免竞态条件。

    也就是,我们需要想想怎么样做到“互斥”。

    互斥的方案

    互斥的本质就是阻止多个进程同时进入临界区

    屏蔽中断

    之前提到的例子中,进程 B 之所以能够进入临界区,是因为进程 A 在临界区中受到了中断。如果我们让进程 A 在进入临界区后,立即对所有中断进行屏蔽,离开临界区后,才响应中断,那么即使发生中断,那么 CPU 也不会切换到其它进程,因此此时进程 A 可以放心地修改文件内容,不用担心其它的进程会干扰它的工作。

    然而,这个设想是美好,实际上它并不可行。第一个,如果有多个CPU,那么进程 A 无法对其它 CPU 屏蔽中断,它只能屏蔽正在调度它的 CPU,因此由其它 CPU 调度的进程,依然可以进入临界区;第二,关于权力的问题,是否可以把屏蔽中断的权力交给用户进程?如果这个进程屏蔽中断后再也不响应中断了, 那么一个进程有可能挂住整个操作系统。

    锁变量

    也许可以通过设置一个锁标志位,将其初始值设置为 0 ,当一个进程想进入临界区时,先检查锁的值是否为 0,如果为 0,则设置为 1,然后进入临界区,退出临界区后把锁的值改为0;若检查时锁的值已经为1,那么代表其他进程已经在临界区中了,于是进程进行循环等待,并不断检测锁的值,直到它变为0。

    但这种方式也存在着竞态条件,原因是,当一个进程读出锁的值为0时,在它将其值设置为1之前,另一个进程被调度起来,它也读到锁的值为0,这样就出现了两个进程同时都在临界区的情况。

    严格轮换法

    锁变量之所以出问题,其实是因为将锁变量由0改为1这个动作,是由想要获取锁的进程去执行的。如果我们把这个动作改为由已经获得锁的进程去执行,那么就不存在竞态条件了。

    先设置一个变量 turn,代表当前允许谁获得锁,假设有两个进程,进程 A 的逻辑如下所示:

    while (turn != 0){// 如果还没轮到自己获取锁,则进入循环等待

    }

    do_critical_region();// 执行临界区的程序

    turn = 1;// 由获得锁的一方将锁变量修改为其它值,允许其它进程获得锁

    do_non_critical_region();// 执行非临界区的程序

    进程 B 的逻辑如下所示:

    while (turn != 1) {// 如果还没轮到自己获取锁,则进入循环等待

    }

    do_critical_region();// 执行临界区的程序

    turn = 0;// 由获得锁的一方将锁变量修改为其它值,允许其它进程获得锁

    do_non_critical_region();// 执行非临界区的程序

    但这里需要考虑到一个事情,假设进程 A 的 do_non_critical_region() 需要执行很长时间,即进程 A 的非临界区的逻辑需要执行较长时间,而进程 B 的非临界区的逻辑很快就执行完,显然,进程 A 进入临界区的频率会比进程 B 小一点,理想的情况下,进程 B 应该多进入临界区几次。但是由于进程 B 在执行非临界区逻辑前会把 turn 设置为 0,等它很快地把非临界区的逻辑执行完后,回来检查 turn 的值时,发现 turn 的值一直都不是 1,turn 的值需要进程 A 把它设置为 1,而进程 A 此时却正在进行着漫长的非临界区逻辑代码,所以导致进程 B 无法进入临界区。

    这就说明,在一个进程比另一个进程慢很多的情况下,严格轮换法并不是一个好办法。

    Peterson 算法

    严格轮换法的问题就出在严格两个字上,即多个进程之间是轮流进入临界区的,根本原因是想要获得锁的进程需要依赖其它进程对于锁变量的修改,而其它进程都要先经过非临界区逻辑的执行才会去修改锁变量。

    严格轮换法中的 turn 变量不仅用来表示当前该轮到谁获取锁,而且它的值未改变之前,都意味着它依然阻止了其它进程进入临界区,恰恰好,一个进程总是要经过非临界区的逻辑后才会去改变turn的值。

    因此,我们可以用两个变量来表示,一个变量表示当前应该轮到谁获得锁,另一个变量表示当前进程已经离开了临界区,这种方法实际上叫做 Peterson 算法,是由荷兰数学家 T.Dekker 提出来的。

    static final int N = 2;

    int turn = 0;

    boolean[] interested = new boolean[N];

    void enter_region(int process) {

    int other = 1 - process;

    interested[process] = true;

    turn = process;

    while(turn == process && !interested[other]) {

    }

    }

    void exit_region(int process) {

    interested[process] = false;

    }

    进程在需要进入临界区时,先调用 enter_region,离开临界区后,调用 exit_region。Peterson 算法使得进程在离开临界区后,立马消除了自己对于临界区的“兴趣”,因此其它进程完全可以根据 turn 的值,来判断自己是否可以合法进入临界区。

    TSL 指令

    回顾一下我们之前提到的“锁变量”这种方法,它的一个致命的缺点是对状态变量进行改变的时候,如从 0 改为 1 或者从 1 改为 0 时,是可以被中断打断的,因此存在竞态条件。

    之后我们在锁变量的基础上,提出如果锁变量的修改不是由想要获取进入临界区的进程来修改,而是由已经进入临界区后想要离开临界区的进程来修改,就可以避免竞态条件,继而引发出严格轮换法,以及从严格轮换法基础上改进的 Peterson 算法。这些方法都是从软件的方式去考虑的。实际上,可以在硬件 CPU 的支持下,保证锁变量的改变不被打断,使锁变量成为一种很好的解决进程互斥的方法。

    目前大多数的计算机的 CPU,都支持 TSL 指令,其全称为 Test and Set Lock,它将一个内存的变量(字)读取寄存器 RX 中,然后再该内存地址上存一个非零值,读取操作和写入操作从硬件层面上保证是不可打断的,也就是说是原子性的。它采用的方式是在执行 TSL 指令时锁住内存总线,禁止其它 CPU 在 TSL 指令结束之前访问内存。这也是我们常说的 CAS (Compare And Set)。

    当需要把锁变量从 0 改为 1 时,先把内存的值复制到寄存器,并将内存的值设置为 1,然后检查寄存器的值是否为 0,如果为 0,则操作成功,如果非 0 ,则重复检测,知道寄存器的值变为 0,如果寄存器的值变为 0 ,意味着另一个进程离开了临界区。进程离开临界区时,需要把内存中该变量的值设置为 0。

    忙等待

    上述提到的 Peterson 算法,以及 TSL 方法,实际上它们都有一个特点,那就是在等待进入临界区的时候,它们采用的是忙等待的方式,我们也常常称之为自旋。它的缺点是浪费 CPU 的时间片,并且会导致优先级反转的问题。

    考虑一台计算机有两个进程, H 优先级较高,L 优先级较低。调度规则规定,只要 H 处于就绪状态,就可以运行。在某一时刻,L 处于临界区内,此时 H 处于就绪态,准备运行。但 H 需要进行忙等待,而 L 由于优先级低,没法得到调度,因此也无法离开临界区,所以 H 将会永远忙等待,而 L 总无法离开临界区。这种情况称之为优先级反转问题(priority inversion problem)

    进程的阻塞与唤醒

    操作系统提供了一些原语,sleep 和 wakeup。

    内核提供给核外调用的过程或者函数成为原语(primitive),原语在执行过程中不允许中断。

    sleep 是一个将调用进程阻塞的系统调用,直到另外一个进程调用 wakeup 方法,将被阻塞的进程作为参数,将其唤醒。阻塞与忙等待最大的区别在于,进程被阻塞后CPU将不会分配时间片给它,而忙等待则是一直在空转,消耗 CPU 的时间片。

    信号量

    首先需要明白的一点是,信号量的出现是为了解决什么问题,由于一个进程的阻塞和唤醒是在不同的进程中造成的,比如说进程 A 调用了 sleep() 会进入阻塞,而进程 B 调用 wakeup(A)会把进程 A 唤醒。因为是在不同的进程中进行的,所以也存在着被中断的问题。加入进程 A 根据逻辑,需要调用 sleep() 进入阻塞状态,然而,就在它调用 sleep 方法之前,由于时钟中断,进程 B 开始运行了,根据逻辑,它调用了 wakeup() 方法唤醒进程 A,可是由于进程 A 还未进入阻塞状态,因此这个 wakeup 信号就丢失了,等待进程 A 从之前中断的位置开始继续运行时并进入阻塞后,可能再也没有进程去唤醒它了。

    因此,进程的阻塞和唤醒,应该需要额外引进一个变量来记录,这个变量记录了唤醒的次数,每次被唤醒,变量的值加1。有了这个变量,即使wakeup操作先于sleep操作,但wakeup操作会被记录到变量中,当进程进行sleep时,因为已经有其它进程唤醒过了,此时认为这个进程不需要进入阻塞状态。

    这个变量,在操作系统概念中,则被称为信号量(semaphore),由 Dijkstra 在 1965 年提出的一种方法。

    对信号量有两种操作, down 和 up。

    down 操作实际上对应着 sleep,它会先检测信号量的值是否大于0,若大于0,则减1,进程此时无须阻塞,相当于消耗掉了一次 wakeup;若信号量为0,进程则会进入阻塞状态。

    而 up 操作对应着 wakeup,进行 up 操作后,如果发现有进程阻塞在这个信号量上,那么系统会选择其中一个进程将其唤醒,此时信号量的值不需要变化,但被阻塞的进程已经少了一个;如果 up 操作时没有进程阻塞在信号量上,那么它会将信号量的值加1。

    有些地方会把 down 和 up 操作称之为 PV 操作,这是因为在 Dijkstra 的论文中,使用的是 P 和 V 分别来代表 down 和 up。

    信号量的 down 和 up 操作,是操作系统支持的原语,它们是具有原子性的操作,不会出现被中断的情况。

    互斥量

    互斥量(mutex)其实是信号量的一种特例,它的值只有 0 和 1,当我们不需要用到信号量的计数能力时,我们可以使用互斥量,实际上也意味着临界区值同一时间只允许一个进程进入,而信号量是允许多个进程同时进入临界区的。

    展开全文
  • 计算机操作系统PV原语分析,介绍PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序……
  • 2.1.3 操作系统原语实现对进程的控制

    千次阅读 多人点赞 2020-03-15 16:56:00
    文章目录0.思维导图1.什么是进程控制?2.原语实现对进程的控制3.回忆进程的组织4.进程控制大致图解5.进程控制原语的相同点6....关于原语的作用和处在操作系统内核的重要地位可参考:https://blog.csdn.net/...


    0.思维导图

    在这里插入图片描述

    1.什么是进程控制?

    在这里插入图片描述

    2.原语实现对进程的控制

    3.回忆进程的组织

    • 进程在操作系统中的组织使各个进程能够有序的进行切换和运行
      在这里插入图片描述

    4.进程控制大致图解

    在这里插入图片描述

    这里说明一下调度和切换的区别:
    调度是指决定资源分配给哪个进程的行为,是一种决策行为
    切换是指实际分配的行为,是执行行为
    一般来说现有资源调度,后有进程切换

    5.进程控制原语的相同点

    在这里插入图片描述

    • 接下来我们就具体学习一下关于进程控制的五种原语,进程的创建、终止、唤醒、阻塞、切换;

    6.进程控制的五种原语

    (1)进程的创建原语

    在这里插入图片描述

    (2)进程的终止原语

    在这里插入图片描述

    (3)进程的唤醒和阻塞原语

    • 进程的阻塞和唤醒原语是成对存在的,必须成对使用
    • 阻塞原语是由被阻塞进程自我调用实现的
    • 唤醒原语是由一个被唤醒进程合作或被其他相关的进程调用实现的
      在这里插入图片描述

    (4)进程的切换原语

    在这里插入图片描述

    参考:https://www.bilibili.com/video/av70156862?p=9

    展开全文
  • 操作系统-进程控制原语

    千次阅读 2020-02-02 15:34:26
    为了实现进程控制,在操作系统内核中,有一组程序专门用于完成对进程的控制,这些原语至少需要包括创建新进程原语,阻塞进程原语,唤醒进程原语,终止进程原语,系统服务对用户开放,即用户可以通过相应的接口来使用...
  • 操作系统—同步原语

    2021-01-07 20:49:35
    同步原语 原来我们都用的是单核的CPU,但是单核的性能现在已经很难有突破了,所以开始在一个CPU中添加多个物理核。 但是原来的应用程序都是为单核设计的,在多核运行无法体现多核的性能,为了更充分的使用多核,应用...
  • 操作系统中有PV原语对进程同步和互斥进行管理,现在假如有三个进程A,B,C,而他们所需的资源系统只有一个,现在A进程运行,他会使用P原语使资源数减一成为0,这时B进程也在申请所以他会被阻塞,这时的资源数为-1,...
  • 原语操作系统

    千次阅读 2017-07-28 10:02:22
    一句话总结:个人理解成...原语操作系统的核心,它不是由进程而是由一组程序模块所组成,是操作系统的一个组成部分,它必须在管态(一种机器状态,管态下执行的程序可以执行特权和非特权两类指令,通常把它定义为操作
  • 原语

    2020-07-19 15:20:07
    第一次看到“原语”这种提法还是在学习操作系统的时候,而且要么不碰到,一碰就是一双,“PV操作”这对原语就是我最先接触到的操作系统原语。当年 Alan Turing 在定义图灵机六个基本操作的时候也用了 primitive 这个...
  • 一:桌上有1空盘,允许存放1个水果。...请用Wait()、Signal()原语实现爸爸、儿子、女儿三个并发进程的同步。Semaphore mutex=1,mutex1=0,mutex2=0;main(){cobeignfather();son();daugther();coend...
  • 让我们更加容易的了解书本上的一些知识点,希望大家来看看
  • 操作系统PV原语的基本原理和执行特点
  • 操作系统PV原语练习(1)

    千次阅读 2018-11-09 16:00:59
    // 执行cross操作 try { Container.numOfPasserOnBridge.acquire(); cross(); } catch (InterruptedException e) { e.printStackTrace(); } finally { Container.numOfPasserOnBridge.release(); } // ...
  • 题目描述: 有一个仓库,可以存放A 和B 两种产品,但要求: (1)每次只能存入一种产品(A 或B); (2)-N产品数量-B 产品数量。其中,N 和M 是正整数。 试用同步算法描述产品A 与产品B 的入库过程。...
  • 题目描述与思路如下: /** * 问题描述: * 读卡机上读卡片。这一项工作由三个进程get,copy和put以及两个缓冲区buffer1和 buffer2 完成。 * 进程get的功能是把一张卡片上的信息从读卡机上读进buffer1;...
  • 之间,进程的各状态之间的什么呀,转换 那么进程控制操作实际上就是具有特定功能的程序 那么这个程序执行的时候呢,由于不允许被中断,所以呢,我们把它称之为原语 那么进程相关的控制原语,有这样一些 那么什么是...
  • 原语 原语操作 原子操作

    千次阅读 2012-01-17 17:07:36
    原语 内核或微核提供核外调用的过程或函数称为原语...操作系统用语范畴。 primitive or atomic action 是由若干多机器指令构成的完成某种特定功能的一段程序,具有不可分割性.即原语的执行必须是连续的,在执行过程
  • 原语,primitive or atomic action,是操作系统用语范畴。原语分为四类,请求(Req)型原语,用于高层向低层请求某种业务;证实(Cfm)型原语,用于提供业务的层证实某个动作已经完成;指示(Ind)型原语,用于提供...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,465
精华内容 586
关键字:

操作系统原语