从01开始 从01开始
首页
  • 计算机科学导论
  • 数字电路
  • 计算机组成原理

    • 计算机组成原理-北大网课
  • 操作系统
  • Linux
  • Docker
  • 计算机网络
  • 计算机常识
  • Git
  • JavaSE
  • Java高级
  • JavaEE

    • Ant
    • Maven
    • Log4j
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • Servlet
  • Spring
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC
  • SpringBoot
  • 学习网课的心得
  • 输入法
  • 节假日TodoList
  • 其他
  • 关于本站
  • 网站日记
  • 友人帐
  • 如何搭建一个博客
GitHub (opens new window)

peterjxl

人生如逆旅,我亦是行人
首页
  • 计算机科学导论
  • 数字电路
  • 计算机组成原理

    • 计算机组成原理-北大网课
  • 操作系统
  • Linux
  • Docker
  • 计算机网络
  • 计算机常识
  • Git
  • JavaSE
  • Java高级
  • JavaEE

    • Ant
    • Maven
    • Log4j
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • Servlet
  • Spring
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC
  • SpringBoot
  • 学习网课的心得
  • 输入法
  • 节假日TodoList
  • 其他
  • 关于本站
  • 网站日记
  • 友人帐
  • 如何搭建一个博客
GitHub (opens new window)
  • 计算机历史

  • 数字电路

  • 计算机组成原理

  • 汇编语言

  • C语言

  • 数据结构

  • 操作系统

    • 我的操作系统学习笔记

    • 我的操作系统实验笔记

    • 操作系统网课-王道考研

      • 0_课程白嫖指南
      • 1_1_操作系统的概念(定义)、功能和目标
      • 1_2_操作系统的特征
      • 1_3_操作系统的发展与分类
      • 1_4_操作系统的运行机制与体系结构
      • 1_5_中断和异常
      • 2_1_1_进程的定义、组成、组织方式、特征
      • 2_1_6_系统调用
      • 2_1_2_进程的状态与转换
      • 2_1_3_进程控制
      • 2_1_4_进程通信
      • 2_1_5_线程概念和多线程模型
      • 2_2_1_处理机调度的概念、层次
      • 2_2_2_进程调度的时机、切换与过程、方式
      • 2_2_3_调度算法的评价指标
      • 2_2_4_FCFS、SJF、HRRN调度算法
      • 2_2_5_调度算法:时间片轮转、优先级、多级反馈队列
      • 2_3_1_进程同步、进程互斥
      • 2_3_2_进程互斥的软件实现方法
      • 2_3_3_进程互斥的硬件实现方法
      • 2_3_4_信号量机制
        • 信号量机制
        • 整型信号量
        • 记录型信号量
        • 小结
      • 2_3_5_用信号量实现进程互斥、同步、前驱关系
      • 2_3_6_生产者-消费者问题
      • 2_3_7_多生产者-多消费者问题
      • 2_3_8_吸烟者问题
      • 2_3_9_读者-写者问题
      • 2_3_10_哲学家进餐问题
      • 2_3_11_管程
      • 2_4_1_死锁的概念(1)
      • 2_4_2_死锁的处理策略—预防死锁
      • 2_4_3_死锁的处理策略—避免死锁
      • 2_4_4_死锁的处理策略—检测和解除
      • 3_1_1_内存的基础知识
      • 3_1_2_内存管理的概念
      • 3_1_3_覆盖与交换
      • 3_1_4_连续分配管理方式
      • 3_1_5_动态分区分配算法
      • 3_1_6_基本分页存储管理的基本概念
      • 3_1_7_基本地址变换机构
      • 3_1_8_具有快表的地址变换机构
      • 3_1_9_两级页表
      • 43_3_1_10_基本分段存储管理方式
      • 3_1_11_段页式管理方式
      • 3_2_1_虚拟内存的基本概念
      • 3_2_2_请求分页管理方式
      • 3_2_3_页面置换算法
      • 3_2_4_页面分配策略
      • 4_1_1_初识文件管理
      • 4_1_2_文件的逻辑结构
      • 4_1_3_文件目录
      • 4_1_4_文件的物理结构(上)
      • 4_1_4_文件的物理结构(下)
      • 54_4_1_5_文件存储空间管理
      • 4_1_6_文件的基本操作
      • 4_1_7_文件共享
      • 4_1_8_文件保护
      • 4_1_9_文件系统的层次结构
      • 4_2_1_磁盘的结构
      • 4_2_2_磁盘调度算法
      • 4_2_3_减少磁盘延迟时间的方法
      • 4_2_4_磁盘的管理
      • 5_1.2_I-O控制器
      • 5_1.3_I-O控制方式
      • 65_5_1_1_I-O设备的概念和分类
      • 5_1_4_I-O软件层次结构
      • 5_1_5_I-O核心子系统
      • 5_1_6_假脱机技术
      • 5_1_7_设备的分配与回收
      • 5_1_8_缓冲区管理
    • 操作系统
  • Linux

  • 计算机网络

  • Git

  • 数据库

  • 计算机小知识

  • 编译原理

  • 名人堂

  • 计算机基础
  • 操作系统
  • 操作系统网课-王道考研
2023-05-15
目录

234_信号量机制

# 2.3_4_信号量机制

那么在正式聊本节的内容之前,我们先用之前小节学过的内容来两个问题。之前咱们学过在进程互持当中有4种软件实现方式和3种硬件实现方式,其中单标志法双标志先检查和双标志后检查,这三种方法都存在着比较严重的一些问题的隐患。 大家尝试回忆一下还能不能想起来。那么在双标志先检查法当中,我们之前聊过造成双标志先检查法的问题的主要原因在于他在进入区的检查和上锁,这两个操作是无法一气呵成的,中间有可能先执行了检查就进行进程切换,所以在这种情况下,如果两个进程并发执行的话,那么就有可能导致两个进程同时进入临界区的问题。

各位同学大家好,在这个小节中我们会学习信号量机制,这个极其重要的知识点,在考研当中我们需要掌握两种类型的信号量,一种是整型信号量,另一种是记录型信号量,我们会在后面分别展开讲解。

那么我们提出第一个问题,能不能用某种方法能够让检查和上锁,这两个操作都可以一气呵成,从而避免双标志检查先检查法的严重问题。第二个问题,除了这三种问题比较大的算法之外,Peterson算法还有后面的三种硬件实现方式,其实问题都不大,但是这些方式也都无法实现让权等待这个原则。那么第二个问题就是我们能不能用某种方式实现真正的让这些并发执行的进程,能够遵守让权等待的原则,这是第二个问题。

其实这两个问题在很早很早以前,1965年有一个荷兰学者叫做迪杰斯特拉,如果学过数据结构的同学对这个名字可能并不陌生,他提出了一个很好的解决方式,解决方案叫做信号量机制,那么信号量机制就可以比较好的解决进程互斥和进程同步的问题。

​

‍

‍

‍

# 信号量机制

我们先来看一下对信号量机制的一些文字性的描述,用户可以通过​操作系统提供的一对原语来对信号量进行操作,然后实现进程互斥进程同步这样的事情。​这提到的信号量,其实我们可以简单的理解为它就是某一种变量,​它可以是一个整数,也可以是比较复杂的记录型的这种数据结构的变量。​一个信号量,它可以用来表示系统当中的某种资源的数量。​比如说一个系统当中有一台打印机,那么我们就可以为打印机设置一个和它对应的信号量,​让信号量的值把它初始值设为1,那么就表示这个系统当中打印机这种资源的数量​是有1个,​所以这是信号量的用法,那么之后我们还会根据更多的例子来让大家加深对这段话的理解。

这提到的原语咱们在之前也介绍过,它其实就是一种特殊的程序段,就是由操作系统提供的,一种在执行的过程当中不可以被中断,只能一气呵成的这种程序。

而原语的具体实是怎么实现的,咱们之前也介绍过,还记得刚开始开篇的时候,咱们提过的问题吗?双标志先检查法的问题主要在于它在进入区当中的检查和操作,检查和上锁这两个操作无法一气呵成。那么既然原语拥有这种一气呵成不可被中断的特性,如果说我们把检查和上锁这两个操作都放在一个原语当中完成,那么是不是就可以避免它无法一气呵成的这种问题了呢?所以这就是为什么信号量机制会想到用原语来解决问题的一个原因。

这儿提到的一对原语指的是wait(S)原语和signal(S)原语,这两个原语其实我们就把它理解为是一种我们自己写的程序段,这个wait其实就是函数名,然后括号里的 s我们就把它理解为是一种函数调用时候的一个参数。这个地方大家如果学过数据结构或者自己有一些编程基础的话,应该不难理解。

另外 wait和signal这两个原语或者说这两个程序也可以简称为pv操作。 Pv操作我在自己复习的时候一直不明白它的来历,然后之前查了一下才知道他其实是来自两个荷兰语,具体什么意思,有兴趣的同学大家可以去查一下。

**P原语:**P是荷兰语Proberen(测试)的首字母。为阻塞原语,负责把当前进程由运行状态转换为阻塞状态,直到另外一个进程唤醒它。操作为:申请一个空闲资源(把信号量减1),若成功,则退出;若失败,则该进程被阻塞;

**V原语:**V是荷兰语Verhogen(增加)的首字母。为唤醒原语,负责把一个被阻塞的进程唤醒,它有一个参数表,存放着等待被唤醒的进程信息。操作为:释放一个被占用的资源(把信号量加1),如果发现有被阻塞的进程,则选择一个唤醒之。

‍

在我们的考研当中经常会把wait和signal这两个函数这两个原语把它简写为p和v这样的一种简写的形式。说了这么多,其实这整块想要告诉大家的无非就是两件事,第一,信号量它是一种变量,可以用信号量来表示我们系统当中某种资源的数量。第二,我们可以用系统提供的一对原语,wait原语和signal原语来对信号量进行操作,具体是怎么操作,我们之后的讲解还会展开。

​

‍

# 整型信号量

我们注意这个地方的有一句话,信号量这种变量它可以是一个整数,也可以是一个更复杂的记录型的变量。那么根据这个问题,我们就引申出了两种类型的信号量,一种叫整型信号量,一种叫记录型信号量。

我们先来看第一种整型信号量,整型信号量其实就是用一个整数来表示某一种系统资源的数量,那么它和普通的整型变量有什么区别呢?普通的整型变量我们可以对它进行加减乘除,各种各样的操作运算。但是对于作为信号量来说的这种整型变量来说,我们只能对这种信号量进行三种操作,一种是初始化,另一种是p操作,还有一种是v操作。

所以按照它的定义,如果说一个计算机系统当中有一台打印机,那么我们就可以定义一个和打印机这种系统资源对应的整型信号量,我们把它变量名设置为S=1,也就是说这个系统当中原本是有一台打印机这种系统资源的,我们可以通过weight和signal,或者说pv这两个操作,对s信号量进行一些更改,一些操作。具体wait和signal做了一些什么事情,我们直接来看一个例子。

如果一个进程p0它想要使用打印机这种资源,那么由于这种资源是有限的,它只有一个,并且我们需要互斥的访问这个打印机,所以在使用打印机资源之前,p0它必须要先执行一个wait原语,对信号量s进行操作。

wait原语当中做了两件事情。第一件事就是这句代码他会检查当前剩余的资源数量是否还足,如果S小于等于0,就说明现在系统当中已经没有这种资源了,那么进程就会被一直卡在这个循环下不去

但是由于p0进程执行wait原语的时候, s的值是1,所以这个循环并不会卡住,它会跳出这个循环,然后执行下一句,是把s的值减一,也就是说打印机资源已经被分配给p0进程了,因此系统当中打印机资源的数量s要减一,所以这是这一步的意思,所以s就变为了0这个值。

那么当p0在访问打印机资源的过程当中,假如说发生了进程切换,有另外的进程,比如说进程p1,他也想使用打印机这种资源,那么他在使用之前先执行wait原语,不过由于此时s的值已经是0,也就是说此时系统当中已经没有打印机资源了,所以p1进程在执行while这个循环的时候,所以它会一直循环等待,直到p0进程把打印机资源释放了,其他的进程也一样,即使他们都想争着使用打印机资源,但是由于这个循环是过不了的,所以他们会一直循环等待,一直到p0使用完打印机资源之后,他又执行了signal原语。

Signal的原语做的事情很简单,其实就是把s的值加一,也就是告诉把打印机还给系统,并且把打印机对应的信号量的值加一,也就表示打印机资源的数量变多了。当打印当s等于一之后,p1或者说其中的某一个正在等待打印机的进程,这个循环就可以被跳过然后再继续执行下面的询下面的语句,于是p1进程就可以使开始使用打印机,然后一直到p1再把打印机释放,然后又把打印机资源交给别的进程使用,这就是整型信号量做的一个事情。

​

‍

‍

‍

其实通过对比大家会发现整型信号量在wait原语当中的这两个操作,其实逻辑上来看和双标志先检查法当中,先检查后上锁其实做的是一样的事情,大家可以对比着来串联一下这两个知识点。

那么因为它是用一个原语来实现的检查和上锁,所以他这两个操作一气呵成,就避免了双标志先检查法那种就是两个进程同时进入临界区的问题。

‍

第二点,在整型信号量机制当中,我们可以看到这个地方有一个while循环,如果说此时一个进程暂时进不了临界区,暂时使用不了这个资源,那么它会一直卡在这个循环这儿,因此会发生进程一直占用处理机盲等的这种情况,并不满足让权等待的原则。

这个地方可能会有一个疑问,如果一个进程暂时进不了临界区,也就意味着它被卡在wait原语的 while循环里,那么既然wait原语它是不可被中断的,那么也就意味着当前正在执行while循环的进程,是不是一直不会被切换呢?这个地方确实是一个让人感觉不太严谨的地方,有兴趣的同学可以自己下去研究一下。但是我们在很多经典的教材当中,其实他们都是这么写的,所以这个地方我们姑且认为它没有问题,不会导致一个进程一直占用处理机的情况。

在整型信号量当中其实比较容易考察的是它存在的问题,这一点经常会把整型信号量和记录性的信号量做对比,那么它俩的区别就在于整型信号量不满足让权等待,会发生盲等,所以这个地方是大家需要重点关注的。

而刚才提出的问题有兴趣的同学可以自己下去研究一下。

‍

‍

‍

# 记录型信号量

接下来我们介绍第二种信号量叫做记录型信号量。刚才的整型信号量有一个很大的缺陷,就是如果一个进程暂时进不了临界区,系统的那种资源暂时不够的话,它会一直占用处理机一直循环检查,从而导致盲等的情况,不满足让权等待的原则。

所以后来人们又提出了记录型信号量,就是为了解决刚才所说的问题,这种信号量是用一个记录型的数据结构来表示,其中 value表示的是当前这种系统资源的剩余数量,比如说刚才咱们提到的打印机,第二个比较重要的是在这种信号量当中,它还会保持一个指向,等待这种系统资源的等待,队列指向等待他的那些进程,具体的咱们之后用一个具体的例子来再展开细聊。

对于记录型信号量的wait操作是这样的,首先执行了wait操作,就意味着某一个进程它需要使用与信号量对应的那种系统资源,所以我们会把这个资源的数量,也就是它的value的值做一个减一的操作。当它减一之后,又会对 Value的值进行一个检查。如果说我们在执行了减一操作之后,导致 value的值已经小于0了,那么就说明它在减一之前其实已经没有这种系统资源了,因此在这个时候是没有系统资源可以分配给当前申请这种资源的进程的。因此在这个地方需要执行一个block原语,作用就是把当前的进程阻塞起来,主动的阻塞,放弃处理机,并且把它挂到这个信号量对应的队列等待队列当中,这是wait操作。

而signal操作是当一个进程,他在使用完这种系统资源的时候会执行的一个原语操作,首先是会把这种资源的数量进行一个加1的操作,如果value的值在加1之后仍然小于等于0,那么就说明在进程释放资源之前,依然还有一些进程是处于等待队列的,所以就需要再调用一个wake up原语,也就是从信号量对应的等待队列当中唤醒其中的某一个进程,然后让他从阻塞态回到就绪态,并且把这他所申请的他所等待的资源分配给他。

所以这就是wait原语和signal原语要做的两件事情。他们做的一个共同点是不管怎么说,肯定是对value的值先减减或者先加加,然后之后还会再对value的值做一个检查,再来判断是否需要对进程进行阻塞,或者是否需要唤醒某一个进程。

​

‍

‍

具体我们来看一个例子,如果说一个计算机系统当中有两台打印机,那么我们可以把初始的信号量的初始值把它设置为二,就是value值设置为二,而刚开始等待打印机资源的等待队列肯定是空的,各个进程在使用这个打印机资源之前,需要先用wait原语来申请打印机资源,在使用完之后又需要执行signal原语来释放一个打印机资源,所以所有各个进程的代码大概是这个样子,这些省略号就是其余的部分。

​

‍

‍

假如说刚开始CPU是为p0进程服务的,那么当它执行到wait原语的时候,首先会执行的事情是value--对吧?所以S.value这个值它会由二减为一。之后系统判断它此时是有打印机资源的,所以会把其中的一个打印机分配给p0进程。然后p0可以呃往下开始使用打印机。之后切换到了 p1进程,p1进程同样的它执行wait原语的时候,其实也是在申请一个打印机资源,首先做的事情是会让s.value的值做一个减一的操作,所以这个值从1变为了0之后系统会把打印机分配给p1进程,然后p1进程可以开始使用打印机。那么我们可以看到当 value的值变为了0的时候,此时系统当中的所有的打印机刚好就已经全部分配给了某一些进程,说明资源恰好分配完毕。

​

‍

那么接下来如果CPU再为p2进程执行,而p2进程同样需要使用打印机资源,他在执行wait操作的时候,同样首先肯定是让这个信号量的value值做一个减1的操作,所以value会由0变为-1,当value的值在减1之后小于0,那么就说明此时系统当中已经没有多余的资源可以分配给这个进程了。因此这个进程会主动的在wait原语当中主动的执行一个block原语,也就是把自己阻塞的原语,所以p2进程它会被挂到打印机这种资源的等待队列里。在这个地方我们会发现,当 value的值等于-1的时候,是有一个进程在等待打印机资源,刚好就是负数的绝对值

​

‍

‍

‍

接下来CPU再转向为p3进程服务。那么同样的它在执行wait的原语的时候,首先是对 value值减一,同样的当它减一之后小于0,所以也会知道此时这种资源打印机资源已经分配完毕,所以p3进程也会主动的执行block原语,因此p3也会被插入到等相应的等待队列的对尾,就是这个样子

​

‍

那么由于p2和p3都不能执行,因此接下来CPU只能为p0或者p1服务。

假设接下来CPU是为p0进程服务的,p0在使用完打印机之后执行了一个signal原语,还记得signal原语做了什么事情吗?首先它会让 value的值做一个加1的操作,所以value会从-2变成-1。

而如果value的值在加1之后,它依然是小于等于0的,那么就说明此时在等待队列当中依然还有一些进程正在等待。所以 p0进程在signal原语当中,他会主动的执行一个wake up原语,用来唤醒信号量对应的等待队列当中的队头的进程,也就是p2。所以p2进程会从阻塞队列的放回就绪队列,并且会把 p0刚刚才释放的打印机资源分配给p2。

那么接下来p0在执行了其他语句之后就执行完毕,之后如果说CPU再接着为p2进程服务,p2就可以得以开始使用打印机资源,然后在使用完了之后,会对打印机资源进行释放,执行一个signal原语。那么同样的它首先是会对 value的值进行加1的操作,由于它加1之后,它的值依然是小于等于0的,所以说明此时在等待队列当中还是有进程,正在等待这种资源,所以它也会执行一个wake up原语来唤醒此时处于等待队列队头的进程,也就是p3进程。因此在执行了这个wake up原语之后,p3进程会从阻塞态变回就绪态,并且 p2刚才释放的打印机资源会被分配给p3,然后p3的信息会从等待队列当中消失,这样的话等待队列就变为了空的状态。

接下来p2在执行完剩余的代码,然后就结束了。在之后如果说CPU又回到了为P1服务,那么P1当他使用完打印机资源之后,又会对打印机进行释放,此时它会对首先是会对value的值进行一个加1的操作,于是从value的值从0变为一,而由于加1之后它已经大于0了,所以说明此时在等待队列当中已经没有进程在等待了。所以p1进程它在执行signal操作的时候并不需要执行wake up原语,接下来系统会回收分配给PE的打印机资源,然后P1得以继续往下执行

最后还有p3进程没有结束,所以 CPU会为p3进程服务。那么p3在使用完打印机之后,也是会对打印机资源进行释放,同样的 value的值会加一变为二,然后之后系统回收打印机资源,然后p3得以顺利的执行,最后结束,那么这就是一个记录型信号量的一个具体的例子,相信根据通过刚才的动画,大家应该能够比较形象的理解。

‍

‍

​

那么我们再结合刚才的weight和signal的代码再来进行一个总结。wait和signal这两个原语分别可以用于对系统资源的申请和释放的时候,那么这个value的初值其实是表示系统当中某一种资源的数目,如果对一个信号量s进行一次p操作,也就是申请信号量s对应的那种系统资源的话,那么就意味着 p操作会导致系统的这种剩余资源数会减一,所以我们需要首先进行一个value减这样一个操作。如果说在它减一之后,发现它的值已经小于0了,那么就意味着这种资源其实之前就已经分配完毕了,所以它需要主动的调用block原语来进行自我阻塞,这会导致进程的状态从运行态变为阻塞态,并且进程相关的信息会被挂到 s这个信号量对应的等待队列当中,用于之后的唤醒工作。那么可以看到这种机制其实遵循了所谓的让权等待原则,因为当一个进程他暂时申请得不到他所申请的这种系统资源的时候,他会主动的进行自我阻塞,主动的放弃CPU,所以就不会出现之前的那些解决方案当中忙等的这种现象。

另外如果对一个信号量s进行v操作,那么就意味着需要释放一个与s这个信号量相对应的那种资源。所以我们此时需要对 value的值进行加一的操作,如果说加1之后,它仍然是小于等于0的,就意味着此时在 s对应的等待队列当中,依然还有进程在等待这种资源的分配,所以就需要调用wake up原语,从队列的对头当中把对头的进程给唤醒,也就是让他从阻塞重新回到就绪态,并且把资源分配给进程,所以这就是记录型信号量在p操作和v操作当中做的事情。

‍

‍

‍

‍

# 小结

那么我们再来简单的回顾一下小节,讲了整型信号量和记录型信号量,​其中整型信号量比较容易考察的是它存在的问题,也就是不满足让权等待的原则,有可能会出现盲等的现象。​

而记录型信号量可以说是操作系统这门课当中最重要的知识点,​在大题和小题当中都会有很高的概率会考察记录型信号量。那么我们需要注意的是,​那么大家需要自己在草稿纸上动手写一下记录型信号量的pv操作,​还有在什么条件下需要执行block和wake up这两个原语,​一定不能用死记硬背的方式,需要把这个地方彻底的理解。​

从刚才的讲解我们也知道这种记录性的信号量,其实可以很方便的用于实现系统资源的申请和释放这样的一个操作。除此之外,记录型信号量还可以实现进程互斥进程同步,这两个咱们之前提过的问题,但这两个问题咱们会放到下个小节的视频当中再进行讲解。另外我们需要强调的一点是,如果说在题目当中出现了对某一个信号量s的p操作和v操作,如果说题目中没有特别说明的话,这个s这个信号量指的都是记录性的信号量,也就是说如果说 p操作暂时得不到他所申请的资源的话,那么进程不会盲等,而是会进入到阻塞的状态

​

在GitHub上编辑此页 (opens new window)
上次更新: 2023/5/16 10:03:43
2_3_3_进程互斥的硬件实现方法
2_3_5_用信号量实现进程互斥、同步、前驱关系

← 2_3_3_进程互斥的硬件实现方法 2_3_5_用信号量实现进程互斥、同步、前驱关系→

Theme by Vdoing | Copyright © 2022-2023 粤ICP备2022067627号-1 粤公网安备 44011302003646号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式