当前课程知识点：操作系统 > 第十七讲 同步互斥 > 17.4 基于软件的同步方法 > 17.4 基于软件的同步方法
下面我们来介绍软件同步方法
基于软件的同步方法呢
它是在两个进程之间
通过共享变量的访问
来实现线程之间的同步
那这一类方法呢
我们给它的大致模式先给它描述
假定有两个线程 T0和T1
然后每一个线程呢
它的实现代码都是这样一种格局
进入区 临界区 退出区
然后我们在这里控制的地方呢
是在进入区和退出区里头
通过一些共享变量的修改
来同步它们之间的行为
那我们在这里的所有的方法呢
都是要讨论在进入区里头
我要对哪些共享的变量
进行什么样的设置和判断
那这些方法呢跟我们前面讨论到的
生活当中同步问题呢是一致的
我们跟那儿呢做一个类比性的讨论
首先第一个尝试 说
我在这里呢
在两个线程之间共享一个变量
这个变量呢表示允许谁进入临界区
那这里是允许进入
临界区的线程的ID
好 那这时候我们说
线程Ti实现代码呢是这样的
它先判断当前这个turn的值
到底是不是i
如果不是 也就相当于我本身是i
允许另外一个线程进入临界区
i不允许进入临界区
那这时候呢它就一直等待
等待另一个线程把它改成i
好 如果 这样的话就是
在它自己等待它变成是它之后
它能进去 进去之后呢
执行临界区的代码
执行完毕之后退出的时候呢
在退出区呢 它把turn改成j
也就说另一个线程ID
那我们看这种情况
能满足我们的要求吗
如果说turn的值是i
那么这时候呢线程Ti
进入一个判断是可以的
OK 它就进去了
好 如果不是那就它一直等着
那这时候说如果这个地方
是j来访问那它就进不去
那这时候我们看到
i和j之间访问临界区的
关系是啥样的
开始的时候假定它等于i
那么这时候呢i能进去
j能进去吗 j进不去
好 i进去之后它改成j
好 这时候如果i再来进的话
它进不去了 j也能进去
这时候我们就会发现一种现象
它们俩是交替进入临界区
这是很好的一种做法
但如果说某一个线程
想连续两次进入临界区
那这时候它就会有麻烦
所以这种做法呢
它能够满足我们说的忙则等待
也就说我在这里头
任何一个线程进到里头去的时候
不会有第二个同时在里头
但是它不满足空闲则入
也就相当于如果说这里是空闲的
但是这时候编号不是你
那你进不去了
好 那我们对这种做法呢
进行进一步的修改
那这是第二种做法
我们在前面呢
设置一个变量turn不够用
那我们这儿呢现在设置两个变量
也就相当于一个数组
描述每个线程它是否是在临界区
这种做法和刚才那个地方
有什么不一样呢
这就相当于我是用两个来表示
我尝试着解决两个线程
需要交替进入的问题
好 那这时候呢
线程Ti的实现代码我们这样来做
先判断另外一个线程它的flag是1
如果它不是
也就相当于它没在临界区里头
那我就把自己的标识改成1
那这时候我在临界区
然后进入临界区
出来的时候
我把自己这个标识呢改成0
那这种做法呢
和我们前面的第一种尝试
想想看有什么区别
线程Ti想进入临界区
它做判断
假设另一个没有在临界区
那它判断是通过的
OK 好 它这时候呢
把自己的标识改了然后进去
如果它再来一遍可以吗
它再来一遍同样的做法仍然没问题
一个线程连续进入是可以的
好 如果说它交替进入呢
那也没问题
好像改善了我们前面
第一种尝试里头的麻烦
但是它有什么问题吗
还记得我们在前面讲
采购当中那个同步
说两个先判断 后设置
两个同时判断之后会出现什么
同时设置
那同时设置之后呢
两个线程就同时进入到
临界区里头去了
那这时候这是它的毛病
它就不能满足忙则等待
好 那这种做法不行了
之后怎么办呢
我们把前面含义做一下改动
也就说前面我们就像
我们在采购那个同步里头
我们是先贴标签还是后贴标签
刚才那种做法呢
相当于是后贴标签
那这时候呢我把这个flag含义改了
不表示我在临界区
而表示我想进入临界区
那这时候呢相当于我是先贴标签
这是它的实现代码
先贴标签后做判断
这时候我们说 前面的采购同步里头
先贴标签后做判断会出现什么问题
两个都有可能判断完了之后
都觉得自己进不去
OK 那就都进不去了
那这是它的问题
它能够满足不能同时进
但是不能满足如果空闲我可以进去
这就是空闲则入
好 这种做法呢也不行
也就相当于我把标签贴在前头
贴在后头都不行
好 那这时候呢
我把这两个合在一起
这就是我们这里的Peterson算法
这是两个进程之间
能够完成同步的算法
它怎么做的呢
turn表示当前谁进入临界区
而flag表示我请求进入临界区
好 这时候我们说
进入区的代码是先设置标志
相当于这时候设置的标志有两个
一个是我想进入
第二个是turn的值
然后我在后面做一个判断
那这时候想想看
这和我们前面先设置标志
后做判断有什么区别
那这地方它俩同时
设置了一个变量 turn
这是问题的关键
我把这一步设置完了之后呢
我后面的判断
就能够区别出来它们俩
好 我们具体看一下
如果说另一个线程j
它没有申请进入
那我这儿直接能进去没问题
因为这两个条件里头
有一个不成立它就进来了
好 假定说另一个也申请了
它也变成true
好 那这时候会什么呢
会有这样一个turn在这儿等着
因为这个变量是
往存储单元里写数据
两个线程同时往里写
或者并发往里写
那总是有一前一后
好 不管是哪一个
因为在总线上仲裁之后
我是有一前一后的
在这里呢
假定我在这儿
我写的是j
如果我是最后一个写的
会什么样的情况
另一个flag是true
然后我的标志呢
turn的标志是按我最后写的
那我判断相当于
如果两个同时想进入的话
后设置turn这个标志的
那这个条件就成立
而先写的后面这个条件不成立
好 那这样的话
就是先写turn这个标志的能进去
而后写的就会在这儿等着
那等到在退出区里头我把flag改了
好 那么这个条件呢
前面这个就不成立了
好 那这是后写标志turn
也就能进去了
好 那这一个呢
我们说跟我们前面讲
采购同步一样的
把它们所有的情况
罗列出来进行分析
写标志 判断它们
所有可能的顺序一一进行分析
我们说Peterson算法呢
是可以完成
我们的两个进程之间同步
好 那在这种情况下我们说
要是更多的进程怎么办
我们先把这个两个进程的做法呢
换一种形式来写
这就是Dekkers算法
它的做法是什么呢
跟标志 跟我们前面的几乎一样的
但是这个进入区的判断呢
相对来说复杂一些
那实际上也是先写
然后后面去判断
判断完了之后
那看如果另一个也想进入
实际上它就把自己改为false
然后开始等待 前面这个
这种做法呢
退出去的做法跟那儿是一样的
这种做法呢
它可以很方便的扩展到多个线程
而扩展到多个线程的做法呢
就是我们这个图呢给出的图示
我在这里有一个turn这个变量
这是共享的
然后是每一个线程 若干个
我把它排成一个环
每一个里头有一个flag的标志
好 那我在进入的时候呢
我先填这个flag标志说我想进入
然后去看turn标志
如果有多个想写
那这个时候呢它总是会有最后一个
好 那么在这种情况下
这是当前正在访问临界区的那一个线程
好 我要做什么呢
进入区我就从这儿往后一直到i
这是个环
也可能会在另外一个位置
就从它起头 到i这个地方
这一段里是不是有其它线程
也跟我一样的 同时想进入
如果有 让他们先访问
访问完了之后
这个turn会一直往后蹿
蹿到我这儿
那这时候我进去
那这就是我们这里说的
进入区的做法
而退出区等我用完了之后
后面有可能
也有其他在等着的
我顺序的把标志
给到下一个想进入的
如果都没有转一圈之后
我把自己留这儿就行了
好 这是N个进程的软件同步方法
好 那我们看到
这几种方法搁到一起之后
我们发现这个
基于软件的同步方法它很复杂
两个进程之间需要多个共享数据项
我才能够完成这个同步
同时这是一个盲等待
也就说我在进入区里头
我必须频繁地来
查询共享变量的状态
那这是呢软件同步方法
所面临的问题
好 经过这几个算法的介绍呢
我们知道通过软件方法
是可以实现多个进程之间的同步的
但是这个方法比较复杂
里头有错之后也不好查找
如果说你是多个线程
多个临界区
那么这时候这个问题会变得更复杂
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
