第十一章数据库管理类的实现

第十一章 数据库管理类的实现 文件目录系统是一个类；它的方法表只有一个，而属性表较为特殊，可以包含很多类的对象；并是可以动态增长的；可以说文件目录系统是一个多类的对象集。数据库是文件目录系统中的一个子目录；从某种角度看，我们也可以将文件目录

第十一章 数据库管理类的实现

文件目录系统是一个类；它的方法表只有一个，而属性表较为特殊，可以包含很多类的对象；并是可以动态增长的；可以说文件目录系统是一个多类的对象集。数据库是文件目录系统中的一个子目录；从某种角度看，我们也可以将文件目录系统看是一个数据库。其实，很多资源管理都具有数据库的特征；如内存、磁盘空间，进程，一个进程中的线程、对象、类、打开的文件号、消息等等的管理。我们把这些等等、都看作是系统对象，那么如何管理这些系统对象？它们的抽象点是什么？无论如何，对象都是由表、从而数据变量、子表构成；而数据都是位的容器；只是大小和保存方式不一样吧。表由一些变量组成，而变量也可能是另一个表或动态表；动态表的成员也可能是一个表；这样会有2种基本形式：
1、表中表、表再表…树状结构，典型的就是文件目录系统。
2、动态变化的表，即是成员数变化的表；如果动态表的成员都具有相同的类型，称为线性表。

2种形式都有，典型的是我们常用的数据库；数据库作为一个目录节点，而子节点就是目录下的一堆表文件。文件表通常是由文件头属性表和文件体属性表构成；如果我们把一个表的基本不变部分的属性放在文件头，而线性表作为文件体；那就是表文件。这时，线性表的成员通常叫为记录。目录就可以看作是一个线性表；它的成员记录就是文件。

理论上，动态表是不可穷尽的；但资源是有限的。在APO中，一个卷下的文件和目录数、也即是i节点数是不能超过4G个的。一个目录下的文件和子目录数不能超过4G个。一个动态表的成员数大小不能超过4G个；动态表的成员也可以是一个表。所以，一个线性表的记录如超过4G个；你可放到另一个表文件。理论上，一个数据库可以16E个记录，实际上不行；因为不能超过一个卷的磁盘空间4G个数据块 = 8PB。

动态表有2种模式：大模式，成员数大小不超过4G个；小模式，成员数大小不超过64K个。对资源的管理，2种模式都可能使用到。比如，本地内存的管理：本地内存有64K个块，以连续块分配、释放的管理模式就是小模式。每个数据块有64K个行，以连续行分配、释放的管理模式就是大模式。又比如通常的数据库：线性表文件数、线性表中的记录数是使用大模式；而一个表的字段数则是用小模式。又比如一个卷的磁盘空间4G个数据块的管理：一个单元是64K个数据块，一个卷有64K个单元。一个页域有64个页区，一个页区有64K个页；一个页是256行，即256H。所以，以连续单元、连续页区分配、释放的管理模式就是小模式。以连续数据块、连续页分配、释放的管理模式就是大模式。不管如何，对表中的成员进行操作的基本方法有4种：增加、删除、修改、查询。后2种方法通常是不同的应用程序去实现的，前2种方法是可以抽象为普式的方法。从另一个角度看，增加、删除可以看作是对资源的分配、释放。如果我们用一个二进制位来表示一个资源单位；资源单位可能是一段连续行、或一段连续数据块、或一条记录、或一个文件、或一个进程、或一个进程中的一个线程、或一段连续页、或一段连续页区、或一段连续单元、或一个i节点、或进程中的一个打开的文件号、或线性表中的一个字段、或进程中的一个类号、或进程中的一个对象号、或一个消息号、或一个过程号等等。这样，对应于小模式，需要64K个位来表示；也即BU64K A; 64K位的位图变量A就对应一个小模式。而大模式则需要64K个64K位的位图变量来描述。一个64K位的位图变量只是占存储空间256H，并不多；但大模式需要占存储空间256个数据块，就比较多了。为减少空间的浪费；对于大模式，我们通常是动态生成的。最初只是分配一个位图变量数据块，该块有256个64K位的位图变量；可以管理大模式中的16M个单位。如果还不能满足时，再申请分配一个位图变量数据块。。。最终会生成有n个（n

单位是指空间的划分单位。一个单位，如果是表示xx号，就很好办；它对应大、小模式中的一个位；结果就是位序号。无论如何，一个单位就是一种规定的位容器。内存、磁盘空间的位容器规格是固定的，有：行H、数据块64KH、页256H、页区64K页、单元64K个数据块、页域64K个页区、卷64K个单元。不过，似数据库表中的一条记录等；单位就不一定是固定的。一条记录或许是600H，或许是一页，或许是10个数据块等等。不管如何，它们最终都是需要磁盘空间、内存空间的固定位容器来装载。一条记录的单位大小，第0号记录在内存空间的开始地址会在表文件头表现、第0号记录在磁盘空间的开始地址会在表文件的目录项体现。为何要用连续单位分配、释放？目的是要取消低速的链表方式。如果一个表文件大小是1G个数据块，如果用链表方式；你大约要1G次I/O及磁道定位，才能找到最后的记录；差不多用3000小时。就算你把链表头指针放在公共文件来提高速度，也要多占4GB的空间。使用连续单位分配，空间、时间都要省得多；1G个数据块可以分配连续16K个单元；即使是逐步生成的，也不会有多少段；链表可以很小。为何文件的磁盘空间定位、大小放在目录项？假如要删除一个具有1G个文件或子目录的目录；那么只是对一个目录文件进行I/O及释放；否则，3000小时都算是快的了。

对应小模式：
数据库表中的一个字段，或一个进程中的一个对象号或类号或线程号或过程号或消息号或打开的文件号，或磁盘空间中的一段连续单元，或一个进程，或磁盘空间中页域下的一段连续页区，或本地内存中的一段连续数据块。将空间划分成一个单位是1/64K。

对应大模式：
数据库表中的一条记录，或目录下的一个文件，或磁盘空间中的一段连续数据块，或磁盘空间中的一段连续页，或磁盘空间中的一个文件i节点，或本地内存中的一段连续行。将空间划分成一个单位是1/4G。

1、小模式管理

APO的内核中，集成有64K位的多功能辅助硬件模块；分配、释放都在一个方法内执行。请求分配、或释放一段连续单位；我们需要先把64K位的位图变量拷贝进硬件模块，之后执行分配、或释放命令；完了再把64K位的位图变量回传。尽管，硬件模块的执行时间只是10ns；但来回拷贝整个位图256行却需要256ns。所以，我们需要考虑；只是拷贝需要的那一行（只需1ns）进硬件模块，来增加速度。为此，增加一个变量BU32 A1; A1的高16位表示位图中的最大连续为1的数值，而低16位表示该数值所在的行序号。这样，我们一开始先判断A1H是否满足要求；是，我们只拷贝A1L这行开始的相关行来进行分配；否，拷贝256行的整个位图，来进行分配；A1重新设定。释放相对来说要简单，只是需要拷贝相关的行。对于非连续单位，即一个位的管理；就简单多了。我们先拷贝16行，SS1；如成功才耗36ns，失败拷贝下16行；最多循环16次。

小模式属性表：
XMUB{ // 256H + 3W。
BU64K XMUWT; // 小模式管理位图变量；256H。
BU1W MAXLX1; // 位图变量中的最大的连续为1的位数及起始位号所属的行号。
BU1W KSXYU; // 位图变量管理的空闲单位数。
BU1W UIJIU; // 位图变量管理的实际单位数。
}

分配：入口，申请的连续单位数或说是位数；出口，返回连续单位数的开始单位号、和位图的最大连续单位数的开始单位号。失败，状态寄存器PSR的标志，PSR.YJ = 0。
释放：入口，释放的连续单位数和开始单位号；出口，返回位图的最大连续单位数的开始单位号。

管理员方法：GKLIYK( 命令参数变量B2, 参数变量B3, &XMUWT位图变量地址, &MAXLX1 );
方法中的参数总是对应压入R0-R3寄存器的。
硬件模块YJMK有3个参数与控制寄存器B2、B3、B4。执行指令：SS1; 所以，你调用GKLIYK方法时，需要传入这3个相关参数。
BU64K YJMK; // 64K位的硬件模块YJMK变量，分为256行，每行256位。

与位操作相关：
B2H: 高8位为指令属性，低8位是指令码。 最高位为SS1启动位；完成时，B2H.15 = 0。
B2L: 低16位是你要COPY进去的位图行数 （也就是你的位图大小）。
B3H: 高16位是你的申请或释放的连续1位数。
B3L: 低16位是申请的连续1位数的返回结果开始位地址，或释放的连续1位数的开始位地址。
B4: 返回结果：是位图的最大连续1位数及开始位所属的行号。
为保存B4返回结果，还需传入位图的最大连续1位数及开始位所属的行号的变量地址到R3。
保存B4的返回结果，可以使得你下次时，一开始就知道如何判断；也无须整个位图放进去，只需一行；速度会加快很多。

硬件模块YJMK的指令码最多有16个，8位命令码中只是低4位有效。跟位图有关的常用的有5个：0—5号指令码。
allot(分配指令)，release（释放指令）= Set（位置1），clr（位清0），CMP（比较）
compress（压缩），insert（插入）, replace（替换）三合一CIR指令。

指令功能：
SS1指令启动后，需约6-10ns完成；期间用户CPU空转，直到SS1完成；才执行下一条指令。

allot(分配指令)：搜索位图满足B3H个连续1位数的开始位地址到B3L；成功PSR.YJ = 1、还将B3H个连续1位数的1全部取反（变为0,表示占用）。等同搜索成功后，执行为部分清0的clr指令。已经搜索完位图、失败，位图内容不变，PSR.YJ = 0；B2H.15 = 0。

release（释放指令）：将你请求释放的连续位数的开始位地址起的B3H个连续位0全部置为1，释放定成功；等同部分位置1的Set指令。 返回结果(R3) = B4是位图的最大连续1位数及开始位所属的行号。

CMP(无符号比较指令)：最多只是比较256行中的值；位图内容不变。
B2H: 高8位的低4位是CMP属性: 字/字符比较、关系/求值、关系有：等于/不等于，等于：小于等于/大于等于；不等于：大于/小于；如是求值有：最大值/最小值。0000x1xx，0000x0x0
B3: 32位是你需要与n行中的32位值比较的数值。n B3H: 16位是你需要与n行中的16位值比较的数值。
B4L: 返回结果：R0 = B4L是第一个符合条件的字或字符开始地址；B4H不变，可作记录号高半字
已经搜索完位图、失败； PSR.YJ = 0；B2H.15 = 0。

一次比较只得到第一个符合条件的字或字符开始地址；可以保存B4，再SS1，直到搜索完位图；PSR.YJ = 0为止。这样，多次SS1；就可得到256行中符合条件的多个记录。可以自己编写对多功能硬件模块操作的方法，不一定非要调用GKLIYK()。

CMP指令对于数据库查询非常高效；如果一个字段是映射到字符或字数值，需要做数值条件查询。那么，我们可以一次拷贝256H = 2KW = 4KZ的数据段进硬件模块来进行比较，如果平均一个数据段可查询到1-8条符合条件的记录；那么，在内存中的数据库表查找速度对字方式约是：
2K/0.27us ~= 7G条记录/秒，对字符方式约是：14G条记录/秒；即约为150亿条记录/秒。

CIR指令：compress（压缩），insert（插入）, replace（替换）。
压缩：可对1-256H中的指定字符或字进行清除，并压缩存放。
插入：可对1-256H中的指定字符或字位置插入一个字符或字。
替换：可对1-256H中的指定字符或字进行替换，或指定位置的字符或字进行替换。

详细以后用到再介绍；排序另文叙述。

系统中的方法都可看作是“原子”的；你不必担心调用方法时，中断造成的同步竞争问题；即使是内核也不能抢占。系统中的方法运行时间小于0.3us，通常小于0.1us。

GKLIYK(){ // 占空间25W，4H；耗时：256行时，276ns ；占用R31、R0、R2。 R1、R3不变
R31 = &YJMK; B3 = R1; B2 = R0; // R0 = 指令属性.指令.行数n，
R0H = &0x000F;
COPYH+( (R31), (R2), R0L ); // 传送；R2+、R31+直到R0L- = 0。
SS1; // 开始执行，时间10ns。PSR.YJ = 0。
Switch(R0H){ // 4位一项的跳转表；据R0H的值跳转；PPCL = (PPCL + 1).R0H。
Allot; release; clr; CMP; CIR; RET(保留); RET; …. 共11个RET。
}
Allot:
BT0 PSR.YJ, UIBT; // 失败返回；不该回传。
ALL1:
R0L = B2L;
COPYH-( (R2), (R31), R0L ); // 成功则回传；R2-、R31-直到R0L- = 0。
R0 = B3; (R3) = B4; // 返回结果
UIBT:
RET
release: clr:
JMP ALL1; // 释放或set对1位或连续位置1是必定成功的，跳回传。
// clr对1位或连续位清0是必定成功的，跳回传。
CMP: CIR:
R0 = B4; // 无论失败、成功都返回；在你的代码中判断PSR.YJ；不回传。
RET // 17+H/2 ns，16行时为25ns。

}

这是一个共用的方法；在之前，你还应落实具体的是那一行开始，是多少行。
比如向本地内存申请连续3个数据块。
Allot1( 0.Allot.0.1, 3.0, &mem_XMUB, &mem_XMUB.MAXLX1 );

Allot1:
CMPZ (R3).H, R1H; // 最大连续1的值能满足要求？
JNN ALT1; // 是跳
R0 = 0.Allot.1.0; // 否，需要拷贝整个位图256行。
GKLIYK();
BT0 PSR.YJ, UIBTIL; // 失败，跳错误处理。
RET
ALT1:
R2 = +(R3).L; // 只拷贝一行；总耗时25ns。
JMP GKLIYK();
UIBTIL: // 错误处理。。。
….
RET

又比如向本地内存释放一个对象，它占连续300个数据块；块号开始地址1000。因为释放时，位图中的最大连续1的数值和开始地址都会变化。最好，还是整个位图拷贝进去；时间要多花点；也不到0.3us。所以，调用就是：
GKLIYK( 0.release.1.0, 300.1000, &mem_XMUB, &mem_XMUB.MAXLX1 );

又比如在一个进程里，代码需要请求一个打开的文件号。如果想简单，就：
GKLIYK( 0.Allot.1.0, 1.0, &ji_fs_no_XMUB, &ji_fs_no_XMUB.MAXLX1 );
但要花约0.28us的时间；想省时间，我们先拷贝16行，SS1；如成功才耗36ns，失败拷贝下16行；最多循环16次。

2、大模式管理

本地内存空间本来就有限，如果代码中声明一个字变量，也要分配一个页（4KB）；那就很不合理，很扯蛋了；现代操作系统内存分配的粒度还是比较粗的。APO中，对于本地内存用连续行分配方式较之其它更为合理，可以说无碎片问题，粒度可小到1H(32B、1W)。对于磁盘空间的粒度是1页256H(8KB)，好像是大了点；但文件小于2KB的都放在i节点了，而无须磁盘空间分配；所以，还是很合理的。

在一个本地数据块内的连续行分配，在一个页区内的连续页分配，在一个单元内的连续数据块分配；i节点号分配，数据块记录号分配等等。这些项目的分配方法是需要使用到线性表的；因为分配是在4G的空间进行，要使用到64K个64K位的位图变量；是大模式。本来，连续行或连续页分配就挺复杂的；感觉再用链表就更复杂了。分配与释放是需要分成2个方法；newH和releaseH。

一个作为大模式分配的64K个资源单位的单位数据块，需要一个指向该单位块的指针，和一个64K位的位图变量；每位对于一个单位。可能会有很多个的这种连续资源单位分配的单位块；一个数据块可以装256个64K位的位图变量，对应着256个连续资源单位分配的单位块。理论上，64K个单位块需要256块位图变量数据块来管理。实际上，位图变量数据块是动态的，按需增长。最初，只是一个位图变量数据块；而位图变量数据块中的256个位图变量，也并非全部使用。比如，文件目录系统中；一个单位是指代表一个文件或目录的i节点。新建一个文件或目录，就是在大模式中请求分配一个空闲位，也就是分配一个i节点。类似的还有在一个数据库表中增加一条记录、为文件分配连续n页等等。大模式的单位序号是1W表示，连续单位数最大是半字1Z表示。因为最多有256个位图变量数据块、每个位图变量数据块最多有256个位图变量；所以单位序号的高16位的高8位是位图变量数据块序号，低8位是位图变量数据块中的位图变量序号；而低16位是相应位图变量的位序号。

大模式属性表：在磁盘空间中会有单元号，但在内存中只是块号。
DMUB{ // 4KH + 48H + 1W
BU1Z [256] WTKP; // 256个位图变量/块，本地内存的块号指针数组；不用或未分配的为0
BU1Z [256] WTKXU; // 每块256个位图变量中，空闲的位图变量数的数组。
BU1Z [256] MMLX1; // 每块256个位图变量中，最大连续为1的数值之最大值数组。
BU16H [256] MLYXUW1;// 256个位图变量块中256个最大连续为1的16位最大值数组的数组。
BU1W MAXLX1; // 位图变量中的最大的连续为1的位数及起始位号所属的行号。
}

每块256个位图变量中，可能有些位图变量还没使用；未使用的位图变量，其对应的最大连续为1的16位最大值为0；但位图变量的所有位都初始化为1。空闲的位图变量数的16位是空闲数，最多为256。没有使用到的位图块，其块号指针为0；其对应的位图变量最大连续为1的数值之最大值数为0；其对应的空闲的位图变量数为：0x0100。

newH分配方法：第一步，在最大连续为1的数值之最大值数组寻找是否有满足要求的位图变量块序号；有，拷贝相应块序号的256个最大连续为1的16位最大值数组（16H），比较得到满足要求的位图变量序号；将对应的位图变量拷贝进硬件模块进行分配。返回结果：32位的单位序号；耗时378ns。否，第二步，在空闲的位图变量数的数组中寻找大于等于1的第一个位图变量块的序号；失败跳错误处理；成功，用空闲的位图变量拷贝进硬件模块进行分配，空闲的位图变量数-1。

newH{ // 大模式分配方法：数据库记录、内存连续行、磁盘的连续数据块、连续页分配。
// 入口：R0-R4，返回R0：申请的连续行数或连续数据块或连续页数等及开始地址。
// R0-R4 = ( 7.CMP.0.16, 申请的连续1位数.0, &DMUB, &DMUB.MAXLX1, &变量)
// 占用：44W, 6H。 耗时：非新位图变量，378ns。否，411ns、32.418us
R27 = R2; R28 = R2 + 16; R29 = R2 +32; R30 = R2 + 48;// R27-R30指向DUMB成员
R2 = R29; R24 = R1; // R2 = &DMUB.MMLX1；保存R1。
GKLIYK(); // 返回R0 = 第一个符合条件的字符开始地址(位图变量块号的序号)。25ns
BT0 PSR.YJ, #ne3; // 失败跳、寻找还没分配的位图变量。到此，33ns
R26H = R0L; // 保存块序号到R26H,
R0 = 7.CMP.0.16; // 求满足要求的位图变量最大值的位图变量序号
ne1: // 这段耗时：343ns
R2 = R30 + R0L // DMUB.MLYXUW1.块序号成员（R0L R25 = R2; // 保存到R25。
GKLIYK(); // 返回R0L = 第一个符合条件的字符开始地址(位图变量序号)。
R26L = R0L;
ne2: // 这段耗时：314ns
R2 = R27.R26H + R0L R0 = 0.allot.1.0; R1 = R24; // 分配指令，恢复R1。
GKLIYK(); // 分配、拷贝相应位图变量的256行。
R25.R26L = (R3).H; //保存最大值到位图变量最大值数组。
R23L = R0L; // 保存16位在变量位图中的序号。
R2 = R25;
R0 = 4.CMP.0.16; // 求256个位图变量最大值数组中的最大值。
GKLIYK(); // 返回R0L = 第一个符合条件的字符开始地址(最大值的序号)。
R29.R26H = R25.R0L;// 保存最大值之最大值。DMUB.MMLX1.R26H
R0H = R26L + R26H R0L = R23L; // 返回R0为单位序号。
RET
ne3:
R2 = R28; // R2 = &DMUB.WTKXU。
R1H = 1;
R0 = 7.CMP.0.16; // 求256个空闲的位图变量数大于1的块序号。
GKLIYK(); // 返回R0L = 第一个符合条件的字符开始地址(块序号)。
R26H = R0L;
CMPZ R28.R0L, #0X0100;// 是空闲块？
JZ ne4; // 是、跳申请1个位图变量数据块。
R28.R0L-; //空闲位图变量数减1
R1 = 0; R0 = 6.CMP.0.16;
JMP ne1; // 求第一个为0的变量序号、并分配。本段耗时35ns
ne4:
Allot1( 0.Allot.0.1, 1.0,&mem_XMUB, &mem_XMUB.MAXLX1 );
R27.R26H = R0L; // 保存块号
KY_init(); // 块初始化为全1；DMUB.MLYXUW1.R0L R26L = 0; R28.R26H = 0X00FF;
JMP ne2; // 本段耗时32.071us
}

releaseH{
// 入口：R0-R4，返回R0：位图的最大连续单位数的开始单位号。
// R0-R4 = ( 0.release.1.0, 释放的连续1位数, &DMUB,&DMUB.MAXLX1, 单位序号 )
// 占用：12W, 2H。 耗时： ns
R1H = R1L; R1L = R4L; R30L = R4H;
R30L = >>8; R30H = R4H R2 = R2.R30L + R30H; // R2指向对应的位图变量
GKLIYK(); // 释放，如果整个位图释放了，最大值变为0；位图变量空闲数+1，如为0x0100
// 就要块释放。否，保存最大值、最大值判断、最大之最大值判断并保存。
。。。

}

晕了，费那么大力；这样复杂的内容、代码量才10H，还要不断修改。离目标代码量512H还很遥远，系统核心的核心只是2条指令2W；即使是进程、线程调度也就几行代码；如何是好？看来，要把应用程序的90%的代码量由系统来完成，各种框架、模式都集成到系统里去。

3、数据库连接

对于连接这种资源，可以看成是大模式；理论上，数据库服务进程就可以支持到4G个连接了。可以构建一个可管理64K个连接的动态线程类，成为模式框架集成到系统里去。连接资源，归类到进程、线程类。数据库应用程序还有：事务日志、显示管理、消息处理、事件过程等内容。前2项基本是集成到系统里；说实在，看起来复杂，什么窗口、按键类等等；编写出来总的也就10H的代码量。后2项，最少一大半是集成到系统里。编写操作系统，秒秒钟要考虑线程间通讯的同步问题；我会尽可能高效和简单。很多传统的同步方法我可能会放弃，用户是基本上无须考虑同步问题的。数据库应用程序的事务日志，解决了一些数据同步问题。同步问题是放在进程、线程类，还是另文；还在考虑。本章就啰嗦到此，诶、口水多过米。