18.5 读者-写者问题慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

下面我们来讨论另一个

经典的同步问题

那这就是我们这里说的

读者写者问题

读者写者问题呢

是我们在计算机系统当中

经常碰到的一个经典问题

它存在于数据库等很多

共享资源的访问当中

所谓的读者写者

是指我们对共享数据的访问

有两类使用者

一类是读者

他是只是读取数据不会去修改

另一类是写者

他可能会读和修改

读的时候呢

我是可以多过线程同时读

写呢那是我不可以同时写了

因为一段数据

你A和B同时往里写

各写一部分

最后写出来结果是谁也没法用的

好针对这种情况呢

我们需要在各个线程之间进行同步

那我们把这个问题抽象出来呢

就是我们这里的读者写者问题

那这里头我们到底

有些什么样的原则呢

首先第一个读读允许

也就说在同一时刻

允许多个读者同时进行读操作

第二条是说读写互斥

如果有写者正在写

那这时候你读者去读是没有意义的

因为他可能正写个半截

你读出来东西也不完整

你没有意义

另一种情况呢是

没有读者的时候你才能写

因为如果有读者在读

你这时候就写

那么你写了一半的过程当中

读者读到数据一部分是旧的

一部分是新的

那这时候这个数据呢

拿到一起来也是没法用的

第三个呢是写写互斥

也就说两个写者

同时往里写数据

这也是不允许的

因为A写一部分

B写一部分

写出来的结果呢它是不可用的

这是我们读者写者问题

所要遵守的三条规则

依据这三条规则

我们来看如何用信号量

实现读者写者问题解决方案

在这里头呢

我们把刚才这些约束

描述成信号量

首先第一个呢是读写互斥

当然读写互斥也负责

写者与写者之间的互斥

某种程度上来讲

你可以认为它就是一个临界区

但是临界区和这儿有点不一样

这一块访问的时候

多个读者是可以一起来访问的

作为互斥的话它的初值是1

然后还会再有一个计数

这个计数呢 Rcount

它是用来记录

正在进行读操作的读者的数目

它的初值呢是0

还有一个就是信号量 CountMutex

这个信号量是用来保护读者计数的

也就说如果我一个读者开始读

那么这时候呢它要把这个计数加1

如果说多个读者前后脚进来

那么它们同时对这个

计数进行加1的话

就有可能这个计数会出问题

它们俩之间也需要协调

好这时候的访问呢应该是互斥的

所以我们就有CountMutex这个信号量

它是用来保护

读写计数的互斥修改

这时候呢任何时刻

只允许一个线程

可以来修改这个计数

所以这个初值呢也是1

有了这三个变量之后

我们来看我们实现的

读者写者的解决方案是什么样的

在这儿呢我们给出了

读者进程写者进程

两边要做的核心操作一个是读

一个是写

那我们要进行

互斥保护这事做起来比较简单

两边都加上互斥信号量的

P操作和V操作

这是写者

它可以理解为

完全是一个临界区问题

在读者这头呢

我们如果说跟写者相对应

它也是一个临界区

前面一个P操作后面一个V操作

但是它有一些不同

就在于我如果第一个读者

进来的时候申请P操作

跟写者进行互斥

第二个来的时候

它就不能那么申请了

所以这个申请操作呢

只是对于第一个读者

所以我会在前面呢加一个判断

如果说当前的读者计数是0

第一个读者进来的时候

他需要申请

然后第二的话他就不用了

第二个就相当于

他只需要计数加1

也就说第一个进来的时候

不但申请并且计数加1

初始值计数是0

那他就变成一个

好第二个来说只加1

等他出来的时候呢也是一样的

计数减一这是每个都要减的

但只是对最后一个离开的读者

他才需要释放这个

读写互斥的这个信号量

好这样的话以便于后边的

写者可以开始写操作

那这时候说我们刚才读者计数

这个数的修改呢也需要保护

那这时候我再在前面

加上一个计数的信号量 CountMutex

底下这个地方呢也是一样的

有了这些操作之后

我们再来对照说

这是不是能满足

我们前面说的三条原则

仔细核对每一种情况

这时候是满足的

我们在满足前面三条的基础上

我们看我们这个实现办法

还有些什么样的特征

大家看一下如果说

我一直在里头有读者在读

后面的读者是一直能进去的对吗

如果这个时候

有一个写者申请写会是什么情况

那它就等着呢

一直等到什么时候呢

等到所有的读者全部离开

如果说有一个读者在里头读

这时候下一个读者又进来了

好那这时候他先于那个写者的

头一个读者离开

也就说后来的读者一定是会先于

等待的写者进行读操作的

那对于这种情况呢

就是我们这里说的读者优先

读者优先呢

在某些情况下是有意义的

比如说我们在这里头

我读数据更是

我优先级高这是可以的

但是对于通常的数据更新来讲

我们希望读到的数据

都是最新的数据

所以这时候呢我们希望是写者优先

这就是我们这里说到的

读者写者问题的两种优先策略

一个是读者优先

只要有读者正在读

后续的读者就可以直接进入

在这种情况下呢

只要读者是持续不断地进入

写者就处于饥饿

而另一种策略呢是写者优先

只要是有写者就绪

那么写者就应尽快执行写操作

这句话的意思是

后来的读者就必须阻塞

如果说有写者持续不断地写入

那么这时候呢读者会处于饥饿状态

这是两种不同的优先策略

那这时候问

这种如何来实现

还有没有其它的优先策略

那实际上还有

就是我两边公平的

有读者就绪了

那么写者不能往里写

有写者就绪了读者不能往里写

这时候两边工程也是可以的

那这些做法呢如何来实现

就请同学们下去思考了

这是我们用信号量来实现的

读者写者问题

那接下来呢我们用管程

来尝试一下解决读者写者问题

我们说管程是把

你的这些同步操作

封装到一个类里头

这就是我们管程

对于读者写者问题呢

我们对外提供的基本方法有两个

一个是读

如果说在前面已经有写者

我一直等到写者结束我开始读

出来的时候呢

我看是不是有其他的写者

而另一个呢是写操作

看前面有没有读者或者写者

如果没有他开始写

写完之后看有没有另外的读者

或者写者把他们唤醒

让他继续进行操作

这时候我在管程里

我维护一些什么内容

我维护这样四个变量

当前正在读的读者

当前正在写的写者

等待读的读者

和等待写的写者

这四个它有一些关系

你比如说正在读和正在写

这两个只会有一个是大于0的

好那等的呢

可能都会大于0都有可能的

好然后我们在这儿呢

管程里头设置一个锁

然后我们设置两个条件变量

一个是可以去读

一个是可以去写

我们看详细的方法如何来做

那我们刚才说

对外提供一个开始读一个完成读

这是对于读者这一头的

它内部的实现呢

对于管程我们都会申请

管程的互斥访问

这是一开头一结尾

在内部呢它开始读的时候呢

一定是当前正在读的计数要加1

那在什么时候会进行等待呢

判断条件然后把它

排到等的队列里头

等的计数加1

并且排到这个条件变量上

等它出来的时候呢

等待读的计数减1

那关键的问题是

在这里我加什么样的条件

这个条件呢又体现出来

我们到底是对读者优先

对写者优先还是两边公平

我们在这儿呢设的条件是

如果说正在有写者在写

或者说有写者在申请写

那这时候呢

我就进入等待队列

也就说写者是优先的

只要有写者它都优先于这个读者

好然后它完成读的时候怎么做呢

申请互斥访问管程这是一样的

然后计数减1

然后关键的问题是说

我需要唤醒哪一些

那么这个唤醒的条件不同呢

也体现你优先策略不同

我们在这儿设的呢没有读者

那这时候最后一个读者

是不是有写者等着

如果有写者等着

那我就让他释放了

另一头呢是写者这头

我们也是开始写完成写

这两个需要你实现一个操作

那具体来说呢

申请和释放管程的互斥访问

这个都是一样的

开始写的时候

当前正在写的计数加1

那他最多会是1

好在这儿之前他会进行等待

等待的时候呢

等待写者计数加1

并且加入到等待队列当中

这是这里的条件变量

好关键问题也是一样的

那地方的条件

我们在这儿设条件呢是

有正在写的写者

或者说有正在读的读者

我就会等着

也就说如果有等待申请读的读者

我是不等着的

好这种情况呢

就说明它是写者优先的

而对于释放的这一头也是一样

计数减1

当前正在写的写者计数减1

然后唤醒哪些

这地方我们设条件是

先优唤醒等待写的

如果说你释放的时候

另外有一个等待写的

我优先唤醒它

如果说没有等待写的 else

我才去唤醒读者

等待读的这些读者把它唤醒

所以从这几个角度来讲呢

我们在这个管程里是写者优先的

好我们从这儿可以看到

基于管程的实现

我们更方便的能够把这种

优先策略呢体现出来

这种优先策略体现

也是比较直接的

所以从这个角度来说呢

管程是简化了

处理同步问题的实现方法

好今天的课呢就上到这里下课

操作系统课程列表：

第零讲在线教学环境准备

-0.1 Piazza讨论区

--piazza访问和使用

--html

-0.2 在线实验平台

-0.2在线实验平台

第一讲操作系统概述

-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.2 系统启动流程

-3.3 中断、异常和系统调用比较

--3.3 中断、异常和系统调用比较

-第三讲启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较

-3.4 系统调用

--3.4 系统调用

-第三讲启动、中断、异常和系统调用--3.4 系统调用

-3.5 系统调用示例

--3.5 系统调用示例

-3.6 ucore+系统调用代码

--3.6 ucore+系统调用代码

第四讲实验一 bootloader启动ucore os

-4.1 启动顺序

-4.2 C函数调用的实现

-4.3 GCC内联汇编

-4.4 x86中断处理过程

-4.5 练习一

-4.6 练习二

-4.7 练习三

-4.8 练习四练习五

-4.9 练习六

第五讲物理内存管理: 连续内存分配

-5.1 计算机体系结构和内存层次

-5.2 地址空间和地址生成

-5.3 连续内存分配

-5.4 碎片整理

-5.5 伙伴系统

-第五讲物理内存管理: 连续内存分配--5.6 练习

第六讲物理内存管理: 非连续内存分配

-6.1 非连续内存分配的需求背景

-6.2 段式存储管理

-6.3 页式存储管理

-6.4 页表概述

-6.5 快表和多级页表

-6.6 反置页表

-6.7 段页式存储管理

-第六讲物理内存管理: 非连续内存分配--6.8 练习

第七讲实验二物理内存管理

-7.1 了解x86保护模式中的特权级

--7.1 了解x86保护模式中的特权级

-第七讲实验二物理内存管理--7.1 了解x86保护模式中的特权级

-7.2 了解特权级切换过程

--7.2 了解特权级切换过程

-第七讲实验二物理内存管理--7.2 了解特权级切换过程

-7.3 了解段/页表

--7.3 了解段/页表

-第七讲实验二物理内存管理--7.3 了解段/页表

-7.4 了解UCORE建立段/页表

--7.4 了解ucore建立段/页表

-第七讲实验二物理内存管理--7.4 了解UCORE建立段/页表

-7.5 演示lab2实验环节

--7.5 演示lab2实验环节

第八讲虚拟存储概念

-8.1 虚拟存储的需求背景

-8.2 覆盖和交换

-8.3 局部性原理

-8.4 虚拟存储概念

-8.5 虚拟页式存储

-8.6 缺页异常

第九讲页面置换算法

-9.1 页面置换算法的概念

--9.1 页面置换算法的概念

-9.2 最优算法、先进先出算法和最近最久未使用算法

--9.2 最优算法、先进先出算法和最近最久未使用算法

-第九讲页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法

-9.3 时钟置换算法和最不常用算法

--9.3 时钟置换算法和最不常用算法

-第九讲页面置换算法--9.3 时钟置换算法和最不常用算法

-9.4 Belady现象和局部置换算法比较

--9.4 Belady现象和局部置换算法比较

-第九讲页面置换算法--9.4 Belady现象和局部置换算法比较

-9.5 工作集置换算法

--9.5 工作集置换算法

-第九讲页面置换算法--9.5 工作集置换算法

-9.6 缺页率置换算法

--9.6 缺页率置换算法

-第九讲页面置换算法--9.6 缺页率置换算法

-9.7 抖动和负载控制

--9.7 抖动和负载控制

第十讲实验三虚拟内存管理

-10.1 实验目标：虚存管理

--10.1 实验目标：虚存管理

-第十讲实验三虚拟内存管理--10.1 实验目标：虚存管理

-10.2 回顾历史和了解当下

-- 10.2 回顾历史和了解当下

-第十讲实验三虚拟内存管理--10.2 回顾历史和了解当下

-10.3 处理流程、关键数据结构和功能

--10.3 处理流程、关键数据结构和功能

-第十讲实验三虚拟内存管理--10.3 处理流程、关键数据结构和功能

-10.4 页访问异常

--10.4 页访问异常

-第十讲实验三虚拟内存管理--10.4 页访问异常

-10.5 页换入换出机制

--10.5 页换入换出机制

-第十讲实验三虚拟内存管理--10.5 页换入换出机制

第十一讲进程和线程

-11.1 进程的概念

--11.1 进程的概念

-第十一讲进程和线程--11.1 进程的概念

-11.2 进程控制块

--11.2 进程控制块

-第十一讲进程和线程--11.2 进程控制块

-11.3 进程状态

--11.3 进程状态

-第十一讲进程和线程--11.3 进程状态

-11.4 三状态进程模型

--11.4 三状态进程模型

-11.5 挂起进程模型

--11.5 挂起进程模型

-第十一讲进程和线程--11.5 挂起进程模型

-11.6 线程的概念

--11.6 线程的概念

-第十一讲进程和线程--11.6 线程的概念

-11.7 用户线程

--11.7 用户线程

-第十一讲进程和线程--11.7 用户线程

-11.8 内核线程

--11.8 内核线程

-第十一讲进程和线程--11.8 内核线程

第十二讲进程控制

-12.1 进程切换

--12.1 进程切换

-第十二讲进程控制--12.1 进程切换

-12.2 进程创建

--12.2 进程创建

-第十二讲进程控制--12.2 进程创建

-12.3 进程加载

--12.3 进程加载

-第十二讲进程控制--12.3 进程加载

-12.4 进程等待与退出

--12.4 进程等待与退出

-第十二讲进程控制--12.4 进程等待与退出

第十三讲实验四内核线程管理

-13.1 总体介绍

-13.2 关键数据结构

-13.3 执行流程

-13.4 实际操作

第十四讲实验五用户进程管理

-14.1 总体介绍

--14.1 总体介绍

-14.2 进程的内存布局

--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.5 进程复制

-14.6 内存管理的copy-on-write机制

--14.6 内存管理的copy-on-write机制

第十五讲处理机调度

-15.1 处理机调度概念

--15.1 处理机调度概念

-第十五讲处理机调度--15.1 处理机调度概念

-15.2 调度准则

--15.2 调度准则

-15.3 先来先服务、短进程优先和最高响应比优先调度算法

--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-第十五讲处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

-第十五讲处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc

-15.5 实时调度和多处理器调度

--15.5 实时调度和多处理器调度

-第十五讲处理机调度--15.5 实时调度和多处理器调度

-15.6 优先级反置

--15.6 优先级反置

-第十五讲处理机调度--15.6 优先级反置

第十六讲实验六调度器

-16.1 总体介绍和调度过程

-16.2 调度算法支撑框架

-16.3 时间片轮转调度算法

-16.4 Stride调度算法

第十七讲同步互斥

-17.1 背景

--17.1 背景

-17.2 现实生活中的同步问题

--17.2 现实生活中的同步问题

-第十七讲同步互斥--17.2 现实生活中的同步问题

-17.3 临界区和禁用硬件中断同步方法

--17.3 临界区和禁用硬件中断同步方法

-第十七讲同步互斥--17.3 临界区和禁用硬件中断同步方法

-17.4 基于软件的同步方法

--17.4 基于软件的同步方法

-第十七讲同步互斥--17.4 基于软件的同步方法

-17.5 高级抽象的同步方法

--17.5 高级抽象的同步方法

-第十七讲同步互斥--17.5 高级抽象的同步方法

第十八讲信号量与管程

-18.1 信号量

--18.1 信号量

-第十八讲信号量与管程--18.1 信号量

-18.2 信号量使用

--18.2 信号量使用

-第十八讲信号量与管程--18.2 信号量使用

-18.3 管程

--18.3 管程

-第十八讲信号量与管程--18.3 管程

-18.4 哲学家就餐问题

--18.4 哲学家就餐问题

-18.5 读者-写者问题

--18.5 读者-写者问题

第十九讲实验七同步互斥

-19.1 总体介绍

--19.1 总体介绍

-19.2 底层支撑

--19.2 底层支撑

-第十九讲实验七同步互斥--19.2 底层支撑

-19.3 信号量设计实现

--19.3 信号量设计实现

-第十九讲实验七同步互斥--19.3 信号量设计实现

-19.4 管程和条件变量设计实现

--19.4 管程和条件变量设计实现

-第十九讲实验七同步互斥--19.4 管程和条件变量设计实现

-19.5 哲学家就餐问题

--19.5 哲学家就餐问题

第二十讲死锁和进程通信

-20.1 死锁概念

--20.1 死锁概念

-第二十讲死锁和进程通信--20.1 死锁概念

-20.2 死锁处理方法

--20.2 死锁处理方法

-第二十讲死锁和进程通信--20.2 死锁处理方法

-20.3 银行家算法

--20.3 银行家算法

-第二十讲死锁和进程通信--20.3 银行家算法

-20.4 死锁检测

--20.4 死锁检测

-第二十讲死锁和进程通信--20.4 死锁检测

-20.5 进程通信概念

--20.5 进程通信概念

-第二十讲死锁和进程通信--20.5 进程通信概念

-20.6 信号和管道

--20.6 信号和管道

-第二十讲死锁和进程通信--20.6 信号和管道

-20.7 消息队列和共享内存

--20.7 消息队列和共享内存

-第二十讲死锁和进程通信--20.7 消息队列和共享内存

第二十一讲文件系统

-21.1 文件系统和文件

--21.1 文件系统和文件

-第二十一讲文件系统--21.1 文件系统和文件

-21.2 文件描述符

--21.2 文件描述符

-第二十一讲文件系统--21.2 文件描述符

-21.3 目录、文件别名和文件系统种类

--21.3 目录、文件别名和文件系统种类

-第二十一讲文件系统--21.3 目录、文件别名和文件系统种类

-21.4 虚拟文件系统

--21.4 虚拟文件系统

-第二十一讲文件系统--21.4 虚拟文件系统

-21.5 文件缓存和打开文件

--21.5 文件缓存和打开文件

-第二十一讲文件系统--21.5 文件缓存和打开文件

-21.6 文件分配

--21.6 文件分配

-第二十一讲文件系统--21.6 文件分配

-21.7 空闲空间管理和冗余磁盘阵列RAID

--21.7 空闲空间管理和冗余磁盘阵列RAID

-第二十一讲文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID

第二十二讲实验八文件系统

-22.1 总体介绍

--22.1 总体介绍

-第二十二讲实验八文件系统--22.1 总体介绍

-22.2 ucore 文件系统架构

--22.2 ucore 文件系统架构

-第二十二讲实验八文件系统--22.2 ucore 文件系统架构

-22.3 Simple File System分析

--22.3 Simple File System分析

-第二十二讲实验八文件系统--22.3 Simple File System分析

-22.4 Virtual File System分析

--22.4 Virtual File System分析

-第二十二讲实验八文件系统--22.4 Virtual File System分

-22.5 I/O设备接口分析

--22.5 I/O设备接口分析

-第二十二讲实验八文件系统--22.5 I/O设备接口分析

-22.6 执行流程分析

--22.6 执行流程分析

第二十三讲 I/O子系统

-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

--html

18.5 读者-写者问题在线视频