00000016.htm

一份很好的linux入门资料

17&nbsp;11gamma:20:8&nbsp;&nbsp;<BR>
$&nbsp;cat&nbsp;db4.dat&nbsp;&nbsp;<BR>
data1&nbsp;&nbsp;<BR>
Data&nbsp;for&nbsp;beta&nbsp;&nbsp;<BR>
Record3&nbsp;&nbsp;<BR>
#include&nbsp;&quot;db.h&quot;&nbsp;&nbsp;<BR>
int&nbsp;&nbsp;<BR>
main(void)&nbsp;&nbsp;<BR>
{&nbsp;&nbsp;<BR>
&nbsp;DB&nbsp;&nbsp;*db;&nbsp;&nbsp;<BR>
&nbsp;if&nbsp;(&nbsp;(db&nbsp;=&nbsp;db_open(&quot;db4&quot;,&nbsp;O_RDWR&nbsp;|&nbsp;O_CREAT&nbsp;|&nbsp;O_TRUNC,&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FILE_MODE))&nbsp;==&nbsp;NULL)&nbsp;&nbsp;<BR>
&nbsp;&nbsp;err_sys(&quot;db_open&nbsp;error&quot;);&nbsp;&nbsp;<BR>
&nbsp;if&nbsp;(db_store(db,&nbsp;&quot;Alpha&quot;,&nbsp;&quot;data1&quot;,&nbsp;DB_INSERT)&nbsp;!=&nbsp;0)&nbsp;&nbsp;<BR>
&nbsp;&nbsp;err_quit(&quot;db_store&nbsp;error&nbsp;for&nbsp;alpha&quot;);&nbsp;&nbsp;<BR>
&nbsp;if&nbsp;(db_store(db,&nbsp;&quot;beta&quot;,&nbsp;&quot;Data&nbsp;for&nbsp;beta&quot;,&nbsp;DB_INSERT)&nbsp;!=&nbsp;0)&nbsp;&nbsp;<BR>
&nbsp;&nbsp;err_quit(&quot;db_store&nbsp;error&nbsp;for&nbsp;beta&quot;);&nbsp;&nbsp;<BR>
&nbsp;if&nbsp;(db_store(db,&nbsp;&quot;gamma&quot;,&nbsp;&quot;record3&quot;,&nbsp;DB_INSERT)&nbsp;!=&nbsp;0)&nbsp;&nbsp;<BR>
&nbsp;&nbsp;err_quit(&quot;db_store&nbsp;error&nbsp;for&nbsp;gamma&quot;);&nbsp;&nbsp;<BR>
&nbsp;db_close(db);&nbsp;&nbsp;<BR>
&nbsp;exit(0);&nbsp;&nbsp;<BR>
}&nbsp;&nbsp;<BR>
程序16.1&nbsp;建立一个数据库并向其写三条记录&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;为了使这个例子简单，我们将每个ptr字段的大小定为4个ASCII字符，将Hash&nbsp;&nbsp;<BR>
表的大小（Hash链的条数）定为3。由于每一个ptr记录的是一个文件偏移量，所以&nbsp;&nbsp;<BR>
4个ASCII字符限制了一个索引文件或数据文件的大小最多只能为10000字节。在后&nbsp;&nbsp;<BR>
面的16.8节做一些性能方面的测试时，我们将ptr字段的大小设为6（这样文件的大&nbsp;&nbsp;<BR>
小可以达到1000000字节），将Hash表的大小设为100。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;索引文件的第一行为&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;0&nbsp;&nbsp;53&nbsp;&nbsp;35&nbsp;&nbsp;&nbsp;0&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;分别为空闲链表指针（0，表示空闲链表为空），和三个Hash链表的指针：53&nbsp;&nbsp;<BR>
，35和0。下一行&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;0&nbsp;&nbsp;10Alpha:0:6&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;显示了一条索引记录的结构。第一个4字符的字段（0）表示这一条记录是此H&nbsp;&nbsp;<BR>
ash链的最后一条。下一个4字符的字段（10）为idx&nbsp;len，表示此索引记录剩下部&nbsp;&nbsp;<BR>
分的长度。我们通过两个read操作来读取一条索引记录：第一个read读取这两个固&nbsp;&nbsp;<BR>
定长度的字段（chain&nbsp;ptr和idx&nbsp;len），然后再根据idx&nbsp;len来读取后面的不定长&nbsp;&nbsp;<BR>
部分。剩下的三个字段为：key（主键）、dat&nbsp;off（在数据文件中的偏移量）和d&nbsp;&nbsp;<BR>
at&nbsp;len（数据记录的长度）。这三个字段用分隔符隔开，在这里我们使用的是分号&nbsp;&nbsp;<BR>
。由于此三个字段都是不定长的，所以我们需要一个专门的分隔符，而且这个分隔&nbsp;&nbsp;<BR>
符不能出现在主键中。最后用一个回车符结束这一条索引记录。由于在idx&nbsp;len中&nbsp;&nbsp;<BR>
已经有了记录的长度，所以这个回车符并不是必须的，加上回车符是为了把各条索&nbsp;&nbsp;<BR>
引记录分开，这样就可以用标准的Unix工具如cat和more来查看索引文件。key是我&nbsp;&nbsp;<BR>
们将记录加入数据库时选择的主键。数据记录在数据文件中的偏移为0，长度为6。&nbsp;&nbsp;<BR>
从数据文件中我们看到数据记录确实从0开始，长度为6个字节。（与索引文件一样&nbsp;&nbsp;<BR>
，我们在这里自动在每条数据记录的后面加上一个回车符，以便于使用Unix工具。&nbsp;&nbsp;<BR>
在调用db_fetch时，此回车符不作为数据返回。）&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;如果在这个例子中跟踪三个Hash链，我们看到第一条Hash链上的第一条记录的&nbsp;&nbsp;<BR>
偏移量是53（gamma）。这条链上的下一条记录的偏移量为17（Alpha），并且是这&nbsp;&nbsp;<BR>
条链上的最后一条记录。第二条Hash链上的第一条记录的偏移量是35（beta），且&nbsp;&nbsp;<BR>
是此链上最后一条记录。第三条Hash链为空。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;请注意索引文件中索引记录的顺序和数据文件中对应数据记录的顺序与我们在&nbsp;&nbsp;<BR>
程序16.1中调用db_store的顺序一样。由于我们在调用db_open时使用了O_TRUNC标&nbsp;&nbsp;<BR>
志，索引文件和数据文件都被截断，整个数据库相当于从新初始化。在这种情形下&nbsp;&nbsp;<BR>
，db_store将新的索引记录和数据记录添加到对应的文件末尾。在后面我们将看到&nbsp;&nbsp;<BR>
db_store也可以重复使用这两个文件中因删除记录而生成的空间。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;在这里使用固定大小的Hash表作为索引是一个妥协。当每个Hash链均不太长时&nbsp;&nbsp;<BR>
，这个方法能保证快速的查找。我们的目的是能够快速地查找任意的键，同时又不&nbsp;&nbsp;<BR>
使用太复杂的数据结构，如B树或动态可扩充Hash表。动态可扩充Hash表的优点是&nbsp;&nbsp;<BR>
能保证仅用两次磁盘操作就能找到数据记录（详见Selter和Yigit[1991]）。B树能&nbsp;&nbsp;<BR>
够让我们用键的顺序来遍历数据库（采用Hash表的db_nextrec函数就做不到这一点&nbsp;&nbsp;<BR>
）。&nbsp;&nbsp;<BR>
16.5&nbsp;集中式或非集中式&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;当有多个进程访问数据库时，有两种方法实现库函数。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;1.集中式&nbsp;&nbsp;由一个进程作为数据库管理者，所有的数据库访问工作由此进程完&nbsp;&nbsp;<BR>
成。库函数通过IPC机制与此中心进程进行联系。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;2.非集中式&nbsp;每个库函数独立的申请并发控制（加锁），然后调用它自己的I/&nbsp;&nbsp;<BR>
O函数。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;使用这两种技术的数据库都有。在Unix系统中的潮流是使用非集中式方法。如&nbsp;&nbsp;<BR>
果有适当的加锁函数，因为避免使用了IPC，那么非集中式方法一般要快一些。图&nbsp;&nbsp;<BR>
16.2描绘了集中式方法的操作。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;在图中，我们特意表示出IPC象绝大多数Unix的消息传送一样需要经过操作系&nbsp;&nbsp;<BR>
统内核（在14.9节中的共享内存不需要这种经过内核的拷贝）。我们看到，在集中&nbsp;&nbsp;<BR>
方式下，中心控制进程将记录读出，然后通过IPC机制将数据送给请求进程。注意&nbsp;&nbsp;<BR>
到中心控制进程是唯一的通过I/O操作访问数据库文件的进程。&nbsp;&nbsp;<BR>
图16.2&nbsp;集中式数据库访问&nbsp;&nbsp;<BR>
图16.3&nbsp;非集中式数据库访问&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;集中式的优点是能够根据需要来对操作模式进行控制。例如，我们能够通过中&nbsp;&nbsp;<BR>
心进程给不同的进程赋予不同的优先级，而用非集中式方法这是很难做到的。在这&nbsp;&nbsp;<BR>
种情况下我们只能依赖于操作系统核心的磁盘I/O调度策略和加锁策略（如当三个&nbsp;&nbsp;<BR>
进程同时等待一个锁开锁时，哪个进程下一个得到锁）。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;图16.3描绘了非集中式方法，在本章我们的实现就是采用这种方法。使用库函&nbsp;&nbsp;<BR>
数访问数据库的用户进程是平等的，它们通过使用记录锁机制来实现并发控制。&nbsp;&nbsp;<BR>
16.6&nbsp;并发&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;由于很多系统的实现都采用两个文件（一个索引文件和一个数据文件）的方法&nbsp;&nbsp;<BR>
，所以我们也使用这种方法，这要求我们能够控制对两个文件的加锁。有很多方法&nbsp;&nbsp;<BR>
可用来对两个文件进行加锁。&nbsp;&nbsp;<BR>
粗锁&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;最简单的加锁方法是将这两个文件中的一个进行作为锁，并要求调用者在对数&nbsp;&nbsp;<BR>
据库进行操作前必须获得这个锁。我们将这称为粗锁。比方说，我们可以认为一个&nbsp;&nbsp;<BR>
进程对索引文件的第一个字节加了读锁后，才能获得读整个数据库的权力。一个进&nbsp;&nbsp;<BR>
程对索引文件的第一个字节加了写锁后，才获得修改整个数据库的权力。我们可以&nbsp;&nbsp;<BR>
使用Unix的记录锁机制来控制每次可以有多个读进程，而只能由一个写进程（见图&nbsp;&nbsp;<BR>
12.2）。db_fetch和db_nextrec函数将获得读锁，而db_delete、db_store以及db&nbsp;&nbsp;<BR>
_open则获得写锁。（db_open要获得写锁的原因是如果要创建新文件的话，要在索&nbsp;&nbsp;<BR>
引文件前端建立空闲区链表以及Hash链表。）&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;粗锁的问题是限制了最大程度的并发。用粗锁时，当一个进程向一条Hash链中&nbsp;&nbsp;<BR>
加一条记录时，其它进程无法访问在另一条Hash链上的记录。&nbsp;&nbsp;<BR>
细锁&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;下面我们用称为细锁的方法来加强粗锁以提高并发度。我们要求一个读进程或&nbsp;&nbsp;<BR>
写进程在操作一条记录前必须先获得此记录所在的Hash链的读锁或写锁。我们允许&nbsp;&nbsp;<BR>
对一条Hash链同时可以有多个读进程，而只能有一个写进程。另外，一个写进程在&nbsp;&nbsp;<BR>
操作空闲区链表（如db_delete或db_store）前，必须获得空闲区链表的写锁。最&nbsp;&nbsp;<BR>
后，当db_store向索引文件或数据文件加一条新记录时，必须获得对应文件相应区&nbsp;&nbsp;<BR>
域的写锁。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;我们期望细锁能比粗锁提供更高的并发度。在16.8节我们将给出一些实际的比&nbsp;&nbsp;<BR>
较测试结果。16.7节给出我们的采用细锁的实现，并详细讨论了锁的实现（粗锁是&nbsp;&nbsp;<BR>
我们实现的简化）。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;在源文件中，我们直接调用read，readv，write和writev。我们没有使用标准&nbsp;&nbsp;<BR>
I/O函数库。虽然使用标准I/O函数库也可以使用记录锁，但是需要非常复杂的缓存&nbsp;&nbsp;<BR>
管理。我们不希望例如fgets返回的数据是10分钟之前读入标准I/O缓存的，而被另&nbsp;&nbsp;<BR>
一个进程在5分钟之前修改了。&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;我们对并发讨论依据的是数据库函数库的简单的需求。商业系统一般有更多的&nbsp;&nbsp;<BR>
需要。关于并发的更多的细节可以参看Data[1982]的第三章。&nbsp;&nbsp;<BR>
16.7&nbsp;源码&nbsp;&nbsp;<BR>
我们从程序16.2中的头文件db.h开始。所有函数以及调用此函数库的用户进程都包&nbsp;&nbsp;<BR>
含这一头文件。&nbsp;&nbsp;<BR>
#include&nbsp;&lt;sys/types.h&gt;&nbsp;&nbsp;<BR>
#include&nbsp;&lt;sys/stat.h&gt;&nbsp;/*&nbsp;open()&nbsp;&amp;&nbsp;db_open()&nbsp;mode&nbsp;*/&nbsp;&nbsp;<BR>
#include&nbsp;&lt;fcntl.h&gt;&nbsp;&nbsp;/*&nbsp;open()&nbsp;&amp;&nbsp;db_open()&nbsp;flags&nbsp;*/&nbsp;&nbsp;<BR>
#include&nbsp;&lt;stddef.h&gt;&nbsp;&nbsp;/*&nbsp;NULL&nbsp;*/&nbsp;&nbsp;<BR>
#include&nbsp;&quot;ourhdr.h&quot;&nbsp;&nbsp;<BR>
&nbsp;&nbsp;/*&nbsp;flags&nbsp;for&nbsp;db_store()&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;DB_INSERT&nbsp;1&nbsp;&nbsp;/*&nbsp;insert&nbsp;new&nbsp;record&nbsp;only&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;DB_REPLACE&nbsp;2&nbsp;&nbsp;/*&nbsp;replace&nbsp;existing&nbsp;record&nbsp;*/&nbsp;&nbsp;<BR>
&nbsp;&nbsp;/*&nbsp;magic&nbsp;numbers&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;IDXLEN_SZ&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;/*&nbsp;#ascii&nbsp;chars&nbsp;for&nbsp;length&nbsp;of&nbsp;index&nbsp;record&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;IDXLEN_MIN&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;/*&nbsp;key,&nbsp;sep,&nbsp;start,&nbsp;sep,&nbsp;length,&nbsp;newline&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;IDXLEN_MAX&nbsp;1024&nbsp;/*&nbsp;arbitrary&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;SEP&nbsp;&nbsp;&nbsp;&nbsp;':'&nbsp;/*&nbsp;separator&nbsp;character&nbsp;in&nbsp;index&nbsp;record&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;DATLEN_MIN&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;/*&nbsp;data&nbsp;byte,&nbsp;newline&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;DATLEN_MAX&nbsp;1024&nbsp;/*&nbsp;arbitrary&nbsp;*/&nbsp;&nbsp;<BR>
&nbsp;&nbsp;/*&nbsp;following&nbsp;definitions&nbsp;are&nbsp;for&nbsp;hash&nbsp;chains&nbsp;and&nbsp;free&nbsp;list&nbsp;chain&nbsp;&nbsp;<BR>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;in&nbsp;index&nbsp;file&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;PTR_SZ&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;/*&nbsp;size&nbsp;of&nbsp;ptr&nbsp;field&nbsp;in&nbsp;hash&nbsp;chain&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;PTR_MAX&nbsp;&nbsp;&nbsp;999999&nbsp;/*&nbsp;max&nbsp;offset&nbsp;(file&nbsp;size)&nbsp;=&nbsp;10**PTR_SZ&nbsp;-&nbsp;1&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;NHASH_DEF&nbsp;&nbsp;137&nbsp;/*&nbsp;default&nbsp;hash&nbsp;table&nbsp;size&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;FREE_OFF&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;/*&nbsp;offset&nbsp;of&nbsp;ptr&nbsp;to&nbsp;free&nbsp;list&nbsp;in&nbsp;index&nbsp;file&nbsp;*/&nbsp;&nbsp;<BR>
#define&nbsp;HASH_OFF&nbsp;&nbsp;PTR_SZ&nbsp;/*&nbsp;offset&nbsp;of&nbsp;hash&nbsp;table&nbsp;in&nbsp;index&nbsp;file&nbsp;*/&nbsp;&nbsp;<BR>
typedef&nbsp;struct&nbsp;{&nbsp;/*&nbsp;our&nbsp;internal&nbsp;structure&nbsp;*/&nbsp;&nbsp;<BR>
&nbsp;&nbsp;int&nbsp;idxfd;&nbsp;/*&nbsp;fd&nbsp;for&nbsp;index&nbsp;file&nbsp;*/&nbsp;&nbsp;<BR>
&nbsp;&nbsp;int&nbsp;datfd;&nbsp;/*&nbsp;fd&nbsp;for&nbsp;data&nbsp;file&nbsp;*/&nbsp;&nbsp;<BR>
&nbsp;&nbsp;int&nbsp;oflag;&nbsp;/*&nbsp;flags&nbsp;for&nbsp;open()/db_open():&nbsp;O_xxx&nbsp;*/&nbsp;&nbsp;<BR>