每周学点大数据 | No.60磁盘算法实践

NO.60

磁盘算法实践

Mr. 王:前面讨论了很多理论方面的内容,从今天开始,我们研究如何从实践的角度去进行磁盘算法、并行算法和众包算法的设计。

小可:嗯,我也很想实际写几个程序去操作前面提过的算法。

Mr. 王:那么我们就从磁盘算法的实践开始吧。

小可:我们平时使用的计算机上的数据很多都是以文件形式进行存储的,那么是不是只要借助C 语言读写文件的函数就可以操作磁盘了呢?

Mr. 王:文件的确是存储在磁盘上的,读写文件的操作也的确会产生磁盘读写。不过这样做大量的操作都是操作系统帮助我们完成的,对磁盘读写的大量细节我们并没有看到,在这里我会通过一些基本的程序,展示一个磁盘算法读写磁盘时的很多细节操作。

小可:嗯,在很多底层的操作中,操作系统和高级语言中封装好的函数为我们完成了太多的工作。

Mr. 王:现在我们就来深度剖析读写磁盘的过程。

首先给出两个用C/C++ 语言读写磁盘的程序。

Mr. 王:上面两个函数分别是从磁盘读取字节数据和向磁盘写入字节数据的实现代码。我们来研究一下这段代码,暂时不关心其中一些函数的实现细节,先来看看这两个函数完成了什么工作。先说说写磁盘程序。首先要明确的一点是,并不是每当要进行磁盘读写时,都直接读写磁盘,这样做是非常不经济的。所以当要读写磁盘时,就需要在内存中开辟一块空间,称作Buffer(缓冲区)。在写磁盘程序的开始,我们先检测缓冲区的页上还有没有剩余的空间去容纳所要写入的内容。如果有,就直接把它们先存放在缓冲区中,并且将缓冲区的偏移量位置向前移动。

但如果页上剩余的空间不足以容纳所要写入内容的大小,那么就先将这个内存页剩余的部

分填满。

接下来,对当前操作的内存页执行Unpin 操作。

然后增加页的编号,并且将偏移量归零。

再对新到达的内存页执行Pin 操作。

将在前一个页上还没有装满的数据填满,并设置偏移量。

小可:等等,老师,其中涉及了两个概念Pin 和Unpin,这是什么意思呢?

Mr. 王:这是磁盘操作中十分关键的两个操作。之前我们也讨论过,在操作磁盘的过程中,我们并不会直接去操作磁盘,而是将磁盘块加载到内存中来,在内存中进行操作和处理。读写磁盘也是一样,我们会在内存中建立一个缓冲区,在缓冲区中存放要操作的磁盘块的数据镜像。此时当需要读取某一部分数据时,如果磁盘中已经存在这部分数据,就不必要再从磁盘中读取数据了,而是从内存中读取该数据。

小可:嗯,毕竟操作内存要比操作磁盘快得多。

Mr. 王:可是,由于我们在不停地对磁盘进行着读写操作,所以很多时候,缓冲区中的数据和磁盘中的数据并不是一致的,这就会带来很严重的问题——“脏数据”。下面举一个例子来说明这个问题,比如有一个进程正在修改一个磁盘块的内容,而另一个进程要读取该内容,此时磁盘块中的数据并没有修改完成,所读取的数据并不是正确的数据。为了避免发生这种读取不一致数据的问题,我们引入了基本操作——Pin 和Unpin。正像它们的名字一样,Pin 是用一个“针”把这个磁盘块给“钉住”,不允许其他进程来读取它的值,因为有一个进程正在写它,这时候读取的值是不正确的。Unpin 正相反,就是写这个磁盘块的过程已经结束,现在内存中的缓冲区和磁盘块中的内容已经一致,可以安全地读取其数据了,此时就不必再“钉住”它了。

小可:哦,我懂了,简单来说,就是防止其他进程在写的过程中读取了正在被写的数据。

Mr. 王:是的。类似的机制在很多两级存储器中有所体现,比如内存和高速缓存(Cache)之间也有相似的机制,以防止CPU 读到Cache 和内存中不一致的数据。

小可:可是Pin 和Unpin 又是如何实现的呢?

Mr. 王:接下来我们就来谈谈Pin 和Unpin 的实现。其实Pin 和Unpin 这两个操作的原理很简单,我们只需要维护一个查找表,这个查找表标记着各个磁盘块和其对应的内存缓冲区的状态。PinPage 函数完成了这样的功能:对id 为pid 的页执行Pin 操作,程序会将磁盘中非空且不在缓冲区中的对应页加载到内存中。程序在执行过程中,首先会在缓冲区中为新来的页寻找空间,如果没有足够的空间,程序会从缓冲区中寻找一个页替换出去,以提供空间给新的页;如果仍然找不到这样的页,就会报错。如果读入的页不是空的,则将正常执行操作,Pin 操作,并且在Hash 表中存储页号和帧号,以标记这是一个已加入缓冲区的被Pin 页。下面是PinPage 的源代码。

小可:等等,老师,这里提到了一个概念Hash 表,这是什么呢?

文章作者:王宏志

文章编辑:秦革

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-11-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏奇点大数据

RHadoop应用(1)

使用RHadoop结合hdfs存储R语言输入数据 1 R语言是著名的开源统计分析和绘图语言,但限于功能,只能进行单机存储数据和计算,通过hadoop的功能可以...

3309
来自专栏云计算教程系列

如何在Ubuntu 18.04上使用devtools安装R包

R是一种流行的开源编程语言,专门研究统计计算和图形。它广泛用于开发统计软件和执行数据分析。R社区以不断为特定研究领域添加用户生成的包而闻名,这使其适用于许多领域...

2520
来自专栏后端技术探索

Nginx面试中最常见的18道题 抱佛脚必备

Nginx的并发能力在同类型网页服务器中的表现,相对而言是比较好的,因此受到了很多企业的青睐,我国使用Nginx网站的知名用户包括腾讯、淘宝、百度、京东、新浪、...

2313
来自专栏木头编程 - moTzxx

Nginx 反向代理学习及实例笔记

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/de...

5522
来自专栏java思维导图

图文并茂,深入浅出Nginx

01前言 Nginx是一款轻量级的Web服务器、反向代理服务器,由于它的内存占用少,启动极快,高并发能力强,在互联网项目中广泛应用。 ? 架构图 上图基本上说明...

4135
来自专栏龚军的专栏

Docker registry工作机制简介

Docker registry是存储docker image的仓库,本文通过对Docker registry的介绍,让大家更进一步了解Docker regist...

7460
来自专栏北京马哥教育

HA专题: corosync+pacemaker实现nginx高可用

前言 这几天都会学习高可用集群, 也会将其中的一些实验写出来分享给大家, 这个专题估计会写5篇左右, 实验介绍 这次的实验比较简单,在CentOS7使用cor...

43910
来自专栏耕耘实录

Linux修改密码是提示“passwd: 鉴定令牌操作错误”问题的处理办法

今早忽然想修改一下一个普通用户的密码,root登录进去之后键入修改密码命令之后发现提示“passwd: 鉴定令牌操作错误”。

3072
来自专栏纯洁的微笑

Java程序员必备的Intellij插件

支持lombok的各种注解,从此不用写getter setter这些 可以把注解还原为原本的java代码 非常方便

1352
来自专栏木头编程 - moTzxx

Laravel 文件上传功能实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/de...

1.6K4

扫码关注云+社区

领取腾讯云代金券