说到存储管理, 是操作系统中最重要的资源之一. 因为任何程序和数据等都需要占有一定的存储空间, 存储管理会直接影响到系统的性能.
在上大学的时候, 学习操作系统感觉特别枯燥, 都是些条条框框的知识点, 感觉和实际应用的关联不大. 发现越是工作以后, 在工作中越想深入了解, 发现操作系统知识越发重要. 在实践中结合理论还是不错的一种学习方法. 自从接触数据库以后, 越来越感觉到很多东西其实都是相通的, 操作系统中的很多设计思想在数据库中也有借鉴和改进之处.
说到存储管理, 是操作系统中最重要的资源之一. 因为任何程序和数据等都需要占有一定的存储空间, 存储管理会直接影响到系统的性能.
存储器是由主存和外存组成. 对于外存, 可能覆盖面更广, 像硬盘, 移动硬盘, 光盘, 磁带, SSD 等等都是外存的覆盖范围. 主存大家很熟悉, 这些年主存的大小也有了极高的提升, 现在的服务器配置中几百 GB 的内存都是很正常的.
关于存储的管理技术, 先讨论以下两个部分.
固定分区
先来点操作系统的知识.
关于固定分区管理技术, 就是把主存分为若干个固定大小的存储区, 每个分区提供给某一个作用使用, 如果作业完成会把相应的存储区归还.
在多道作业系统中, 主存中分区的个数是固定不变的, 而且每个分区的大小也是固定不变的. 如果分区总是大于作业, 那么就有很多分区没有充分使用, 产生碎片.
来结合数据库来看一看(shared pool 中的 free list)
在数据库中, shared pool 中的 free list(bucket)管理和固定分区管理很相似.
shared pool 中存储单位是 chunk, 多个 chunk 组成一个链表, 也叫做 bucket, 每个 bucket 都对 chunk 的大小都有一定的范围, 是一个连续的值, 没有交叉.
在 10g,11g 中都设置了 255 个 bucket, 可以通过 trace 文件来了解一下.
[ora11g@rac1 trace]$ grep Bucket *18155*.trc
- Bucket 0 size=32
- Bucket 1 size=40
- Bucket 2 size=48
- Bucket 3 size=56
- Bucket 4 size=64
- Bucket 5 size=72
- ...
- Bucket 250 size=12352
- Bucket 251 size=12360
- Bucket 252 size=16408
- Bucket 253 size=32792
- Bucket 254 size=65560
可能对于 bucket 的大小没有一个直观的感受, 可以生成一个图来看看就很清楚了.
随着 bucket 的增长, 对应的 chunk 大小都在递增, 绝大多数的 bucket 中, chunk 的大小都在 5k 以内. 只有很小的一部分 bucket 的支持的 chunk size 很大, 这个也是 Oracle 在不断的改进中得到的一个最优值, 按照比例来划分, 保证每次访问需要的 chunk 大小都能够合理的分配, 尽量减少冗余.
同时不是每个 bucket 里面都是有 chunk 的, 这个 chunk 的分配还是根据进入 shared pool 以后申请 chunk 大小紧密相关, bucket 中的 chunk 数目可不是平均的.
Oracle 在早期的版本中也碰到了不少的问题, 在 10g,11g 中都对 bucket 的数目做了提升(目前都是 255 个), 而且分区的大小也做了调整. 这是一个比较均衡的比例, 能够保证每次请求的大小都在 bucket 的范围之内, 尽量提高效率.
回到操作系统中, 我们再补充几点.
在存储的管理中, 存储的分配和释放都需要根据分区来说明. 在固定分区中采用了一个存储分块表 (MBT) 来维护而存储的区的信息, 存储区的信息在操作系统中有一个专有名词叫做数据基, 数据基听起来挺抽象, 其实理解起来还是蛮简单的.
我们用下面的图标来说明. 我们假设下面的这个表格就是存储分块表, 其中数据基就包括, 存储的分区大小, 存储位置还有状态.
猛一看, 上面的方式还是比较简单而且可行的. 但是还是固定分区的硬伤, 主存利用率不高, 对于进入主存中的作业大小我们也没法预知, 而且对于 MBT 表的管理感觉还是不够清晰. 如果需要查找哪些分区可用, 需要重新分配的时候, 就得遍历整个表, 遍历了已经使用的分区, 这样分配的过程就比较长了.
这个时候可以参考一下:
可变分区的多道管理技术
这种技术在一定程度上解决了固定分区带来的问题, 可变分区在主存中不会事先创建一个个分区, 而是在作业进入主存的时候按照作业大小再来创建分区.
这样的话, 分区个数不固定, 分区大小不固定, 在 Oracle 中也有一些相似之处.
Oracle 中的 deferred_segment_creation
比如说对于分区的不固定, 在 11g 中有一个参数 deferred_segment_creation, 如果我们设定为 true, 那么在创建之初是不会分配对应的分区的, 直到开始插入数据之后, 它才会根据插入的数据来创建分区.
Oracle 中的 interval partitoning
如果根据需要动态的创建分区, 而且分区的大小也不固定.
比如在数据库的表空间管理中, 我们可以指定分区的.
对于可变分区的数据基管理, 是采用了两个存储分区表来管理的, 已使用分区表 (UBT) 和空闲分区表(FBT), 这样就可以减少存储分配和释放的性能.
在这点上, Oracle 表空间中的数据字典管理方式是一致的.
Oracle 中早期是采用 FET$,UET$ 两个数据字典表来维护分区的信息的. 只是在数据基上会有一定的差别.
FET$ 和 UET$ 的结构如下:
这种方式在早期的 Oracle 版本中采用, 这种表空间管理方式叫数据字典管理.
但是在 Oracle 的不断改进中, 发现这种方式还是存在一定的问题, 资源消耗还是比较高的. 对于这两种数据字典表的 DML 操作, 会产生较多的递归 SQL 来间接完成对两个数据字典表的更新, 在更新的过程中也会存在事务, 存在事务也就会产生一定的 undo 和 redo. 最后就是对于相邻空闲空间的合并, 在 Oracle 中是通过 SMON 进程来实现的.
回到操作系统, 操作系统中对于数据基的管理还有一种方式, 就是空闲存储链表.
这种方式就是把空闲分区通过链表的形式串起来, 形成了一条空闲存储块链.
这种技术在数据库中可有一个很响亮的名字, 在 buffer cache 中叫做 LRU 链表.
在 buffer cache 中的实现方式也是类似的. 当然在 Oracle 中会采用其它的算法和策略. Oracle 中是把 buffer 按照被使用的先后顺序挂在 LRU 链表 上, 先被使用的 buffer 放在了链表的后面, 后被使用的 buffer 挂载 LRU 链表的前面, 如果 buffer 被修改的时候, buffer 就会从 LRU 链 表上取出. 这样始终保持 LRU 链表中都是可用的数据块.
可变分区的存储算法
然后来简单说一下可变分区的存储算法.
目前主要有以下几种:
最佳适用算法
这种方式就是从所有未分配的分区中挑选一个最接近于作业尺寸且大于或者等于作业大小的分区分配.
最先适应法
按照分区序号从存储分块表中的第一个表目找找, 把最先找到且大约等于作业大小的分区分配.
最坏适应法
把所有未分配的分区中挑选最大的且大于等于作业大小的分区分配.
位图法
把所有的分区使用一个位来表示状态, 1 表示块已经被使用, 0 表示分区空闲.
在 Oracle 中的存储算法可能更接近于最佳适应算法, 唯一的不同的是在 Oracle 中采用了 hash 来该分配到哪个 bucket. 但是都会保证分配的空间是大于等于请求的大小.
而位图法在表空间管理中也有相似的使用方式.
表空间的管理有两种方式, 数据字典管理和本地管理.
本地管理中会在数据文件的头部采用多个位来存放. 这个 bitmap 类似下面的形式.
11110111001110100.....
1 代表分区已被使用, 0 代表分区还是空闲, 当进程需要分区的时候, 只要扫描数据文件的头部的 bitmap, 就可以找到值为 0 的分区. 分配了分区之后把它修 改为 1, 释放空间就会从 1 修改为 0. 修改数据文件头部的操作速度快且不存在事务, 就没有 redo,undo, 更不会有递归 SQL. 对于相邻分区的合并来说, 两个连续的 0 就能说明是连续的空闲 分区, 所以也不需要再合并相邻的可用分区了.
前面讨论了固定分区和可变分区管理的一些情况, 它们的主要缺点就是主存使用的低效率和存储分配释放的低速. 固定分区是分区内部的碎片造成主存利用率低, 而可变分区是分区外部的碎片, 往往小到无法使用, 从而主存利用率不高. 对于这个问题, 分页是一种很有效的方法.
分页技术
分页技术主要是把主存分为许多同样大小的存储块, 并以这种存储块作为存储分配单位. Oracle 数据库中物理存储单位有段, 区, 数据块, 这个时候所说的数据块和操作系统数据块存在着映射, 一般都比操作系统块要大. 数据库中默认为 8K, 数据的存储都是以 8K 的基本单位来存储的. 如果把这一点继续延伸, Oracle 中的区 (extent) 就和分页技术中所说的页很类似.
分页存储中的基本实现过程, 有以下几点:
把主存分为相同大小的存储块, 叫做页架, 页架从 0 开始, 编号依次是 0,1,2....
用户逻辑地址的分页, 用户逻辑地址可以划分为和页架大小相同的部分, 叫做页. 页号从 0 开始, 依次为 0,1,2...
逻辑地址的表示, 既然说到了逻辑地址, 表示方法也很重要. 每一个逻辑地址都是相对地址, 用一个数对 (p,d) 来表示, p 代表页号, d 代表逻辑地址在也好为 p 的页中相对的地址, 也叫偏移量.
听起来挺枯燥啊, 可以简单举个例子, 我们常看的书就是一个很好的例子, 书有很多大小, 四开, 八开, 十六开, 可以理解为页架, 书中的每一页就是我们所说的页, 逻辑地址可以这么理解, 一本书有很多章节, 小结, 比如第二章第 3 页, 我们就能够很快找到, 这个时候, 页号就是 2, 偏移量就是 3, 用 (p,d) 来表示就 是(2,3)
举一个严谨的例子, 比如给定一个虚地址 3456, 假设页面大小为 1000B, 则第 0 页对应的地址为 0-999, 第 1 页为 1000-1999, 则虚地址 3456=(3,456)
这一点和 Oracle 中创建表空间时指定的 extent management 管理方式很相似, 比如我们创建一个表空间 test 指定分区大小为 1M, 表空间大小为 100M, 则语句如下:
create tablespace test add datafile '/u01/app/db/test01/data01/test01.dbf' size 100M extent management local uniform size 1M ;
这样我们指定分区大小为 1M, 如果存储了 100M 的数据, 这样 100M 就会分为 100 个分区. 如果数据大于分区 1M, 则可以存储在相应的分区上, 不一定连续.
可以用下面的表格来说明.
对应到每个进程对应的地址, 就是我们所说的逻辑地址, 比如进程 1 对应的逻辑地址就是
- 0-999
- 1000-1999
- 2000-3999
所以在分页思想中的难点就是对于地址的表示, 我们已经说使用 (p,d) 来表示, 但是这个数在机器指令的地址场中表示还有不同, 首先会把地址分为两部分, 一部分表示页号, 一部分表示页内地址.
这种方式每次访问一个主存单元都用一次除法得到页号和页内地址就很繁琐, 实际上效率要更差. 这个时候相比前人也是考虑了很多招数, 最后还是使用二进制来搞定, 指定页面尺寸是 2 的幂, 这样就会省去很多额外的转换.
最后一个例子很关键, 如果看懂了说明你对分页思想算是明白了.
假设页的大小为 1KB, 计算逻辑地地址为 4101 的页号, 页内地址.
按照二进制的思想, 4101 可以这样表示 4101=2^12+2^1+2^1+2^0
用 0,1 来表示就是
0001000000000101
页的大小是 1KB=2^10, 则在二进制串中, 后 10 位就是对应的页内地址, 二进制 0101 代表的是 5, 表示页内地址为 5
0001000000000101
页号对应的二进制串 000100 表示页号为 4
所以 4101 对应的逻辑地址表示为(4,5)
这种方法可以省去除法运算, 硬件层面会自动把逻辑地址拆分为两部分, 对应页号和页内地址.
问题来了, 地址能够表示了, 那使用的时候是怎么转换的呢, 首先会把逻辑地址抽取出来, 像上面的例子, 页号是 4, 然后根据页号为索引找到该页存放的主存页架号. 比如存放的地址为 2000-2999, 则页架号为 2, 然后把页架号取代逻辑地址, 和右边的页内地址组成了最终的物理地址去访问内存.
这种思想还是需要些时间去消化一下, 优点也是很明显的, 基本上没有页内碎片, 同时也不会存在小到无法再用的页外碎片. 因为每个碎片都是页架的整数倍.
分页中使用的二进制方式处理地址是一种很值得借鉴的方式, 可以减少很多额外的开销, 和 Oracle 中的 rowid 存储方式也很类似.
分段式存储
分段式存储管理系统中, 会为每个段分配一个连续的分区, 而进程中的各个段可以离散地移入内存中不同的分区中, 说起分段就会联想到分页, 我们来聊聊分页与分段的主要区别.
分页和分段有许多相似之处, 比如两者都不要求作业连续存放. 但在概念上两者完全不同, 主要表现在以下几个方面:
页是信息的物理单位, 分页是为了实现非连续分配, 以便解决内存碎片问题, 或者说分页是由于系统管理的需要. 段是信息的逻辑单位, 它含有一组意义相对完整的信息, 分段的目的是为了更好地实现共享, 满足用户的需要.
页的大小固定, 由系统确定, 将逻辑地址划分为页号和页内地址是由机器硬件实现的. 而段的长度却不固定, 决定于用户所编写的程序, 通常由编译程序在对源程序进行编译时根据信息的性质来划分.
分页的作业地址空间是一维的, 分段的地址空间是二维的.
从数据库的角度来看, 感觉和数据库中的段概念还是比较类似的. 数据库中段包含多个分区. 各个分区也可以在不相邻的分区中.
找一个图来说明.
在分段情况下, 会要求每个进程的地址空间划分为若干个段, 每个段都有自己的段名, 对应到下图中就是一个段号. 每个段的地地址空间都是从 0 开始, 是一个连续的地址空间.
从地址的存储情况来说, 段和页的存储方式都是类似的, 都会包含两部分. 分段存储中是段号和段内地址, 和分页存储中的页号和页内地址类似.
由于一个进程由很多段组成, 而且各个段可能被分配在主存中的多个不相邻的分区中, 为了将进程的逻辑地址转换为物理地址, 需要有一个短标来指出进程的某段放在主存中的位置以及段长.
这一点从数据库层面来说有类似的方面, 首先是进程由多个段组成, 数据库中可以理解为一个表包含多个段, 数据段, 索引段, LOB 段, LOB 索引段等等. 这些都是独立的段, 在存储的时候也可能分布在不同的表空间中, 所以可能不是一个相邻的分区.
而段的信息在操作系统层面是通过段表来维护的, 数据库层面则是通过数据字典, user_segments,user_extents 来维护的, 每个表包含的段, 每个段包含的区都是很详实的.
从分段和分页的优点来说, 因为它们涉及的层面和应用方向不同, 但是还是有一定的可比性, 在段共享方面, 分段存储还是很有优势, 谁让它是段共享呢.
从操作系统层面举个例子就是一个多用户系统, 有一个应用程序可能包含的程序段是 100K, 数据段是 40K, 按理说需要 40K*40+100k*40=1600+4000=5600k
在分段存储中则需要 100k+40k*40=1700k, 从这一点上来说还是很大的改进.
从这一点上来说, 数据库中的同义词就有点分段存储的味道, 每个同义词都可以访问源表, 相当于共享了数据, 同义词占用的存储空间很小, 几乎可以忽略.
可能分段存储和分页存储都各有千秋, 但是都是在不断的使用和改进中主键发展起来的, 分段存储没有段内碎片, 只有外部碎片, 简单分段技术也是基于多重分区技 术的发展而来. 另外简单分页对于用户是不可见的, 用户无法了解进程被分页或者分页的细节, 但是简单分段对于用户基本是可见的, 当进程被交换出内存的时候, 对应的页表和段表也需要随着进程一起撤出内存.
当然分页分段方式还在不断的发展中, 要不怎么有后续的段页式存储呢, 很多时候类比操作系统方面的知识, 就会让我们对于很多事物有了全新的认识和了解.
当然顺带帮大家复习了操作系统的基础知识, 我的目的也算达到了.
来源: http://stor.51cto.com/art/201804/570630.htm