程序员经验分享-hwhale

操作系统--进程同步

2023-10-27

进程同步概念

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。
举个例子：例如让系统计算1+2*3，假设系统产生2个进程，1个是加法进程，1个是乘法进程。要让计算结果正确，必须先是计算乘法后计算加法，如果不加以制约那么加法的进程可能在乘法之前，那么结果就会出错。因此引入了同步机制。

同步概念

  • 同步也叫制约关系，同步是指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待，传递信息所产生了制约关系。

临界资源概念

  • 一个时间段内只允许一个进程使用的资源称为临界资源

例：物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

互斥概念

  • 互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
  • 所以对临界资源的访问，必须互斥地进行。

系统中的2中资源共享方式

  1. 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
  2. 同步共享方式:系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问

对临界资源的互斥访问

在逻辑上分为如下四个部分：

do
{
  entry section;   //进入区
  critical section; //临界区
  exit section;    //退出区
  remainder section; //剩余区
}while(true)

如下图：
在这里插入图片描述

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1.空闲让进: 临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 忙则等待: 当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
3. 有限等待:对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
4. 让权等待:当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

如果没有进程互斥会发生什么呢？
在这里插入图片描述
那如何实现互斥呢？

单标志法

算法思想

  • 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

在这里插入图片描述
举个例子：
在这里插入图片描述
只能按 P0 -> P1 -> P0 -> P1 ->……这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问.

单标志法存在的主要问题是：违背“空闲让进”原则。

双标志先检查

算法思想

  • 设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 “flag[0] = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有 没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。

在这里插入图片描述

因为进入临界区的’‘检查’'和"上锁"不是原子操作，可能在上锁前发生进程切换。

  • 双标志先检查的问题是：违反了 "忙则等待"原则。

双标志后检查

后检查法是对先检查法的改进，先上锁，再检查

在这里插入图片描述

Peterson 算法

结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔 融让梨”（谦让）

在这里插入图片描述

例子：

1,2，3的步骤：
进入区: 1. 主动争取；2. 主动谦让；3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”
谁最后说了“客气话”，谁就失去了行动的优先权。
场景一：过年了，某阿姨给你发压岁钱。

阿姨：乖，收下阿姨的心意~ 你：不用了阿姨，您的心意我领了
阿姨：对阿姨来说你还是个孩子，你就收下吧
结局：自己收了压岁钱

场景二
阿姨：乖，收下阿姨的心意~ 你：不用了阿姨，您的心意我领了
阿姨：对阿姨来说你还是个孩子，你就收下吧
你：真的不用了阿姨，我已经成年了
结局：阿姨收起了红包

小结：
Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙 则等待、有限等待 三个原则，但是依然未遵循让权等待的原则。Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

进程互斥的硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）
前面讲过中断，
在这里插入图片描述

缺点:只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，不能交给用户自己使用，

TestAndSet指令

简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

指令的概念描述如下：

bool TestAndSet(bool *lock){
bool old;
old = *lock;  //old用来存放lock 原来的值
*lock = true; //无论之前是否加锁，都将lock设为true
return old;   //返回lock原来的值
}
//使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));//上锁并检查
临界区代码段...
lock = false;  //解锁
剩余代码段...

若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入
临界区。若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直
循环，直到当前访问临界区的进程在退出区进行“解锁”。

优缺点：

  • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

Swap指令

有的地方也叫 Exchange 指令，或简称 XCHG 指令。
Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

//Swap 指令的作用是交换2个变量的值
Swap(bool *a,bool *b){
bool temp;
temp = *a;
*a = *b;
*b = temp;
}
//以下是用Swap指令实现互斥的的算法逻辑
//lock 表示当前临界区是否被加锁
bool old = true;
while(old == true)
Swap(&lock,&old);
临界区代码段...
lock = false;
剩余代码段...

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变
量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程
对临界区上锁，则可跳出循环，进入临界区。

优缺点

  • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从
    而导致“忙等”。

信号量机制

在前面的方法中都无法实现"让权等待"的问题，1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制。

信号量概念：
信号量其实就是一个变量 ，可以用一个信号量来表示系统中某种资源的数量(例如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。)而用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

前面提过原语：原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。
信号量使用的一对原语是wait(S) 原语和 signal(S) 原语,也可以理解原语是我们写的一个函数，函数名分别为wait和signal，括号里的信号量就是调用函数时传入的参数。我们把这一对原语简称P、V操作。（来自荷兰语 proberen 和 verhogen）信号量分为整形信号量和记录型信号量。

整形信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

例：在某计算机系统中有一台打印机：

int S = 1；//初始化整形信号量S，表示当前系统中有1台打印机资源

void wait(int S){    //wait原语，相当于进入区
    while(S <= 0){   //如果资源不够，就会一直循环等待
    S = S - 1;       //如果资源够，则占用一个资源
    }
}

void signal(int S){ //signal 原语，相当于退出区
     S = S + 1;     //使用完资源后，在退出区释放资源
}

//进程P0
...
wait(S); //进入区，申请资源
使用打印机资源;//临界区，使用资源
signal(S);//退出区，释放资源
...

在这里插入图片描述

记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表
示的信号量。

记录型信号量结构：

typedef struct{
    int value;  //剩余资源数
    struct process *L;//等待队列
}semaphore;

wait操作

void wait (semaphore S){
  S.value--;
  if(S.value < 0){
    block(S.L);
  }
}

singal操作

void signal(semaphore S){
  S.value++;
  if(S.value <= 0){
    wakeup(S.L);
  }
}

在这里插入图片描述
来个例子：
某计算机系统中有2台打印机…，则可在初始化信号量 S 时将 S.value 的值设为 2，队列 S.L 设置为空
在这里插入图片描述

在开始题目中 wait(S)、signal(S) 也可以记为 P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”。

对信号量 S 的一次 P 操作意味着进程请求一个单位的该 类资源，因此需要执行 S.value–，表示资源数减1，当S.value < 0 时表示该类资源已分配完毕，因此进程应调 用 block 原语进行自我阻塞（当前运行的进程从运行态->阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态->就绪态）。

用信号量实现进程同步、互斥

信号量实现互斥

信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

  • P( S ) —— 申请一个资源S，如果资源不够就阻塞等待
  • V( S ) —— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

实现互斥步骤

  1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
  2. 设置互斥信号量 mutex，初值为 1
  3. 在进入区 P(mutex)——申请资源
  4. 在退出区 V(mutex)——释放资源

注意：
对不同的临界资源需要设置不同的互斥信号量。 P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。
记录信号量的定义：

typedef struct{
    int value;  //剩余资源数
    struct process *L;//等待队列
}semaphore;

如果题目中没特别说明，可以把信号量的声明简写成这种形式：

P1(){
...
P(mutex); //使用临界资源前需要加锁
临界区代码;
V(mutex);//使用完临界区资源解锁
...
}

例如互斥的使用打印机

P1(){
...
P(mutex); //使用临界资源前需要加锁
临界区代码;
使用打印机；
V(mutex);//使用完临界区资源解锁
...
}

信号量实现同步

用信号量实现同步的步骤

  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
  2. 设置同步信号量 S, 初始为 0
  3. 在“前操作”之后执行 V(S)
  4. 在“后操作”之前执行 P(S)

口诀：前V后P

例题：
在这里插入图片描述
在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

进程管理

os

信号量

同步与互斥

操作系统--进程同步 的相关文章

随机推荐

  • kettle配置资源库

    kettle 数据库资源库配置 在使用kettle过程中可以配置资源库 将建好的作业和转换都保存在资源库中 下次直接登录就可以看到所有保存的作业和转换 本教程使用kettle v8 2 mysql 5 7 24做演示 方法 步骤 前期准备工

  • C++五种排序方法（有参考）

    快速排序 堆排序 希尔排序 冒泡排序 选择排序 数据结构选择 数组 概要设计 定义一个容量为一亿个整数的数组 定义变量n 用rand函数生成n个随机数 并赋值给数组 用clock函数计算排序所用时间 编写排序函数和主函数 一 快速排序 in

  • gmpy2常见函数使用

    gmpy2常见函数使用 1 初始化大整数 import gmpy2 gmpy2 mpz 909090 result mpz 909090 2 求大整数a b的最大公因数 import gmpy2 gmpy2 gcd 6 18 result

  • 【Python_PySide2学习笔记（十三）】QMainWindow 和 QWidget 的区别（转载）

    QMainWindow 和 QWidget 的区别 转载 前言 此篇文章中介绍QMainWindow 和 QWidget 的区别 转载自 pyside2 系列之QMainWindow和QWidget 正文 1 QWidget QWidget

  • 多模数据库

    随着业务数据量不断增长的同时 数据结构也变得越来越灵活多样 数据不再局限于规整的结构化数据 半结构化 非结构化数据在数据域处理中的占比逐年上升 因此对不同模态的数据进行智能化数据处理的需求越来越迫切 中国信通院在数据库发展研究报告 2021

  • 算法通关村-----海量数据的处理方法

    从40亿中产生一个不存在的数 问题描述 给定一个文件 包含40亿个非负整数 请你设计一个算法 产生一个不在该文件中的数字 假设你只有1GB内存 问题分析 40亿整数 在java中 用int存储的话 大概需要40亿 4B 大约16G 现在只有

  • [Python知识图谱] 四.Python和Gephi实现中国知网合作关系知识图谱

    该系列文章主要讲解知识图谱或关系图谱的构建方法 前文介绍了Neo4j图数据库和Jieba PyLTP的基本用法 本篇文章主要采用Python和Gephi构建中国知网某个领域的作者合作关系和主题词共现的知识图谱 重点阐述了一种可操作的关系图谱

  • 数据库元数据metadata获取

    数据库元数据metadata获取 项目需求 SQL语句获取数据库元数据信息 JdbcTemplate获取metadata元数据信息 使用java原生的jdbc获取metadata元数据信息 JdbcTemplate执行SQL语句 获取met

  • java学习之线程3与反射

    线程 Daemon 守护线程 该方法必须在启动线程前调用 主线程结束时 子线程也结束 join 插队 哪个线程调用这个方法 就会拿到CPU的执行权 先完成执行 分析 在多线程程序中 这个单例安全吗 为什么 如何解决 加锁来保证同一时间只有一

  • Error response from daemon: Get “https://registry-1.docker.io/v2/“: net/ttp: request canceled while

    在用docker容器运行hello world时出现报错 Error response from daemon Get https registry 1 docker io v2 net ttp request canceled while

  • condition_variable 条件变量

    文章目录 条件变量 头文件 condition variable 公共方法 wait wait Lck 流程图 示例 错误示例 等待前通知 导致无法获得通知 wait Lck Pred 流程图 示例 等待后通知 示例 等待前通知 错误示例

  • Shell全局变量、局部变量与特殊变量笔记总结

    变量类型 全局变量 环境变量 和局部变量 本地变量 环境变量可以在定义它们的shell及其派生出来的任意子进程的shell中使用 局部变量只能在定义它们的函数 脚本中使用 还有一些变量是用户创建的 其他的则是专用的shell变量 1 全局变

  • 执行ajax的步骤即封装

    一 执行AJAX 1 四个步骤 step1 获取核心对象 step2 设置发送请求地址 step3 发送请求 请求数据 step4 接受相应数据 业务处理 1 1 step1 获取核心对象 判断window中是否有在网页加载后与服务器进行通

  • FFmpeg常用滤镜

    常用的滤镜中重点的是 scale trim overlay yadif rotate movie 比如常用的scale 可以用来做缩放 trim可以做比较精确的帧级的剪切 overlay可以来实现视频混流 画中画或多画面等叠加处理 rota

  • 子类能不能继承父类的构造函数

    一 子类能继承父类的构造函数 答案是不能的 构造函数是创建对象时完成时数据的初始化 当我们在new一个对象并传入参数时 会自动调用有参数的构造完成参数的初始化 也就是属性的初始化 试想子类中继承父类的构造方法 不仅不符合构造方法的命名规则

  • Mysql查找当前数据库端口

    默认端口为3306 也可以执行以下命令查询 show global variables like port

  • 点云 3D 目标检测 - RangeDet（ICCV 2021）

    点云 3D 目标检测 RangeDet In Defense of Range View for LiDAR based 3D Object Detection 基于LiDAR的3D目标检测的距离视图防御 ICCV 2021 摘要 1 引言

  • 学嵌入式 - 第一天

    一 了解 虚拟机 中的终端 键盘按下 CTRL ALT T 三个键打开终端 加入终端界面我们会看到如下界面 hgj ubuntu 是命令提示符提示你输入命令 hgj 表示的是用户名 是分隔符 ubuntu 是主机名 是分隔符 是当前工作路径

  • BES2300x笔记（0） -- 学习笔记索引

    博文索引 一篇文章带你搞定BES平台 提供全网最全的开发调试笔记和文档下载 持续更新 BES2300x笔记 1 SDK代码架构与Battery模块 BES2300x笔记 2 如何区分左右耳 BES2300x笔记 3 编写自动化编译脚本 BE

  • 操作系统--进程同步

    进程同步 进程同步概念 进程互斥的软件实现方法 单标志法 双标志先检查 双标志后检查 Peterson 算法 进程互斥的硬件实现方法 中断屏蔽方法 TestAndSet指令 Swap指令 信号量机制 整形信号量 记录型信号量 用信号量实现进

热门标签