16.htm

UNIX环境下C编程的详细详细介绍

<p>16.5 集中式或非集中式 </p>

<p>当有多个进程访问数据库时，有两种方法实现库函数。 </p>

<p>1.集中式 
由一个进程作为数据库管理者，所有的数据库访问工作由此进程完 </p>

<p>成。库函数通过IPC机制与此中心进程进行联系。 </p>

<p>2.非集中式 
每个库函数独立的申请并发控制（加锁），然后调用它自己的I/ </p>

<p>O函数。 </p>

<p>使用这两种技术的数据库都有。在Unix系统中的潮流是使用非集中式方法。如 
</p>

<p>果有适当的加锁函数，因为避免使用了IPC，那么非集中式方法一般要快一些。图 
</p>

<p>16.2描绘了集中式方法的操作。 </p>

<p>在图中，我们特意表示出IPC象绝大多数Unix的消息传送一样需要经过操作系 
</p>

<p>统内核（在14.9节中的共享内存不需要这种经过内核的拷贝）。我们看到，在集中 
</p>

<p>方式下，中心控制进程将记录读出，然后通过IPC机制将数据送给请求进程。注意 
</p>

<p>到中心控制进程是唯一的通过I/O操作访问数据库文件的进程。 </p>

<p>图16.2 集中式数据库访问 </p>

<p>图16.3 非集中式数据库访问 </p>

<p>集中式的优点是能够根据需要来对操作模式进行控制。例如，我们能够通过中 
</p>

<p>心进程给不同的进程赋予不同的优先级，而用非集中式方法这是很难做到的。在这 
</p>

<p>种情况下我们只能依赖于操作系统核心的磁盘I/O调度策略和加锁策略（如当三个 
</p>

<p>进程同时等待一个锁开锁时，哪个进程下一个得到锁）。 </p>

<p>图16.3描绘了非集中式方法，在本章我们的实现就是采用这种方法。使用库函 
</p>

<p>数访问数据库的用户进程是平等的，它们通过使用记录锁机制来实现并发控制。 
</p>

<p>16.6 并发 </p>

<p>由于很多系统的实现都采用两个文件（一个索引文件和一个数据文件）的方法 
</p>

<p>，所以我们也使用这种方法，这要求我们能够控制对两个文件的加锁。有很多方法 
</p>

<p>可用来对两个文件进行加锁。 </p>

<p>粗锁 </p>

<p>最简单的加锁方法是将这两个文件中的一个进行作为锁，并要求调用者在对数 
</p>

<p>据库进行操作前必须获得这个锁。我们将这称为粗锁。比方说，我们可以认为一个 
</p>

<p>进程对索引文件的第一个字节加了读锁后，才能获得读整个数据库的权力。一个进 
</p>

<p>程对索引文件的第一个字节加了写锁后，才获得修改整个数据库的权力。我们可以 
</p>

<p>使用Unix的记录锁机制来控制每次可以有多个读进程，而只能由一个写进程（见图 
</p>

<p>12.2）。db_fetch和db_nextrec函数将获得读锁，而db_delete、db_store以及db </p>

<p>_open则获得写锁。（db_open要获得写锁的原因是如果要创建新文件的话，要在索 
</p>

<p>引文件前端建立空闲区链表以及Hash链表。） </p>

<p>粗锁的问题是限制了最大程度的并发。用粗锁时，当一个进程向一条Hash链中 
</p>

<p>加一条记录时，其它进程无法访问在另一条Hash链上的记录。 </p>

<p>细锁 </p>

<p>下面我们用称为细锁的方法来加强粗锁以提高并发度。我们要求一个读进程或 
</p>

<p>写进程在操作一条记录前必须先获得此记录所在的Hash链的读锁或写锁。我们允许 
</p>

<p>对一条Hash链同时可以有多个读进程，而只能有一个写进程。另外，一个写进程在 
</p>

<p>操作空闲区链表（如db_delete或db_store）前，必须获得空闲区链表的写锁。最 
</p>

<p>后，当db_store向索引文件或数据文件加一条新记录时，必须获得对应文件相应区 
</p>

<p>域的写锁。 </p>

<p>我们期望细锁能比粗锁提供更高的并发度。在16.8节我们将给出一些实际的比 
</p>

<p>较测试结果。16.7节给出我们的采用细锁的实现，并详细讨论了锁的实现（粗锁是 
</p>

<p>我们实现的简化）。 </p>

<p>在源文件中，我们直接调用read，readv，write和writev。我们没有使用标准 
</p>

<p>I/O函数库。虽然使用标准I/O函数库也可以使用记录锁，但是需要非常复杂的缓存 
</p>

<p>管理。我们不希望例如fgets返回的数据是10分钟之前读入标准I/O缓存的，而被另 
</p>

<p>一个进程在5分钟之前修改了。 </p>

<p>我们对并发讨论依据的是数据库函数库的简单的需求。商业系统一般有更多的 
</p>

<p>需要。关于并发的更多的细节可以参看Data[1982]的第三章。 </p>

<p>16.7 源码 </p>

<p>我们从程序16.2中的头文件db.h开始。所有函数以及调用此函数库的用户进程都包 
</p>

<p>含这一头文件。 </p>

<p>#include &lt;sys/types.h&gt; </p>

<p>#include &lt;sys/stat.h&gt; /* open() &amp; db_open() mode */ </p>

<p>#include &lt;fcntl.h&gt; /* open() &amp; db_open() flags */ </p>

<p>#include &lt;stddef.h&gt; /* NULL */ </p>

<p>#include &quot;ourhdr.h&quot; </p>

<p>/* flags for db_store() */ </p>

<p>#define DB_INSERT 1 /* insert new record only */ </p>

<p>#define DB_REPLACE 2 /* replace existing record */ </p>

<p>/* magic numbers */ </p>

<p>#define IDXLEN_SZ 4 /* #ascii chars for length of index record */ </p>

<p>#define IDXLEN_MIN 6 /* key, sep, start, sep, length, newline */ </p>

<p>#define IDXLEN_MAX 1024 /* arbitrary */ </p>

<p>#define SEP ':' /* separator character in index record */ </p>

<p>#define DATLEN_MIN 2 /* data byte, newline */ </p>

<p>#define DATLEN_MAX 1024 /* arbitrary */ </p>

<p>/* following definitions are for hash chains and free list chain </p>

<p>in index file */ </p>

<p>#define PTR_SZ 6 /* size of ptr field in hash chain */ </p>

<p>#define PTR_MAX 999999 /* max offset (file size) = 10**PTR_SZ - 1 */ </p>

<p>#define NHASH_DEF 137 /* default hash table size */ </p>

<p>#define FREE_OFF 0 /* offset of ptr to free list in index file */ </p>

<p>#define HASH_OFF PTR_SZ /* offset of hash table in index file */ </p>

<p>typedef struct { /* our internal structure */ </p>

<p>int idxfd; /* fd for index file */ </p>

<p>int datfd; /* fd for data file */ </p>

<p>int oflag; /* flags for open()/db_open(): O_xxx */ </p>

<p>char *idxbuf;/* malloc'ed buffer for index record */ </p>

<p>char *datbuf;/* malloc'ed buffer for data record*/ </p>

<p>char *name; /* name db was opened under */ </p>

<p>off_t idxoff; /* offset in index file of index record */ </p>

<p>/* actual key is at (idxoff + PTR_SZ + IDXLEN_SZ) */ </p>

<p>size_t idxlen;/* length of index record */ </p>

<p>/* excludes IDXLEN_SZ bytes at front of index record */ </p>

<p>/* includes newline at end of index record */ </p>

<p>off_t datoff; /* offset in data file of data record */ </p>

<p>size_t datlen;/* length of data record */ </p>

<p>/* includes newline at end */ </p>

<p>off_t ptrval; /* contents of chain ptr in index record */ </p>

<p>off_t ptroff; /* offset of chain ptr that points to this index record </p>

<p>*/ </p>

<p>off_t chainoff;/* offset of hash chain for this index record */ </p>

<p>off_t hashoff;/* offset in index file of hash table */ </p>

<p>int nhash; /* current hash table size */ </p>

<p>#define HASH_OFF PTR_SZ /* offset of hash table in index file */ </p>

<p>typedef struct { /* our internal structure */ </p>

<p>int idxfd; /* fd for index file */ </p>

<p>int datfd; /* fd for data file */ </p>

<p>int oflag; /* flags for open()/db_open(): O_xxx */ </p>

<p>char *idxbuf;/* malloc'ed buffer for index record */ </p>

<p>char *datbuf;/* malloc'ed buffer for data record*/ </p>

<p>char *name; /* name db was opened under */ </p>

<p>off_t idxoff; /* offset in index file of index record */ </p>

<p>/* actual key is at (idxoff + PTR_SZ + IDXLEN_SZ) */ </p>

<p>size_t idxlen;/* length of index record */ </p>

<p>/* excludes IDXLEN_SZ bytes at front of index record */ </p>

<p>/* includes newline at end of index record */ </p>

<p>off_t datoff; /* offset in data file of data record */ </p>

<p>size_t datlen;/* length of data record */ </p>

<p>/* includes newline at end */ </p>

<p>off_t ptrval; /* contents of chain ptr in index record */ </p>

<p>off_t ptroff; /* offset of chain ptr that points to this index record </p>

<p>*/ </p>

<p>off_t chainoff;/* offset of hash chain for this index record */ </p>

<p>off_t hashoff;/* offset in index file of hash table */ </p>

<p>int nhash; /* current hash table size */ </p>

<p>long cnt_delok; /* delete OK */ </p>

<p>long cnt_delerr; /* delete error */ </p>

<p>long cnt_fetchok;/* fetch OK */ </p>

<p>long cnt_fetcherr;/* fetch error */ </p>

<p>long cnt_nextrec;/* nextrec */ </p>

<p>long cnt_stor1; /* store: DB_INSERT, no empty, appended */ </p>

<p>long cnt_stor2; /* store: DB_INSERT, found empty, reused */ </p>

<p>long cnt_stor3; /* store: DB_REPLACE, diff data len, appended */ </p>

<p>long cnt_stor4; /* store: DB_REPLACE, same data len, overwrote */ </p>

<p>long cnt_storerr;/* store error */ </p>

<p>} DB; </p>

<p>typedef unsigned long hash_t; /* hash values */ </p>

<p>/* user-callable functions */ </p>

<p>DB *db_open(const char *, int, int); </p>

<p>void db_close(DB *); </p>

<p>char *db_fetch(DB *, const char *); </p>

<p>int db_store(DB *, const char *, const char *, int); </p>

<p>int db_delete(DB *, const char *); </p>

<p>void db_rewind(DB *); </p>

<p>char *db_nextrec(DB *, char *); </p>

<p>void db_stats(DB *); </p>

<p>/* internal functions */ </p>

<p>DB *_db_alloc(int); </p>

<p>int _db_checkfree(DB *); </p>

<p>int _db_dodelete(DB *); </p>

<p>int _db_emptykey(char *); </p>

<p>int _db_find(DB *, const char *, int); </p>

<p>int _db_findfree(DB *, int, int); </p>

<p>int _db_free(DB *); </p>

<p>hash_t _db_hash(DB *, const char *); </p>

<p>char *_db_nextkey(DB *); </p>

<p>char *_db_readdat(DB *); </p>

<p>off_t _db_readidx(DB *, off_t); </p>

<p>off_t _db_readptr(DB *, off_t); </p>

<p>void _db_writedat(DB *, const char *, off_t, int); </p>

<p>void _db_writeidx(DB *, const char *, off_t, int, off_t); </p>

<p>void _db_writeptr(DB *, off_t, off_t); </p>

<p>程序16.2 db.h头文件 </p>

<p>这里，我们定义了实现的基本限制。如果要支持更大的数据库的话，这些限制 
</p>

<p>也可以修改。其中一些我们定义为常数的值也可定义为变量，只是会使实现复杂一 
</p>

<p>些。例如，我们设定Hash表的大小为137，一个也许更好的方法是让db_open的调用 
</p>

<p>者根据数据库的大小通过参数来设定这个值，然后将这个值存在索引文件的最前面 
</p>

<p>。 </p>

<p>在DB结构中我们记录一个打开的数据库的所有信息。db_open函数返回一个DB 
</p>

<p>结构的指针，这个指针被用于其它的所有函数。 </p>

<p>我们选择用db_开头来命名用户可调用的库函数，用_db_开头来命名内部函数 
</p>

<p>。 </p>

<p>在程序16.3中定义了函数db_open。它打开索引文件和数据文件，必要的话初 
</p>

<p>始化索引文件。通过调用_db_alloc来为DB结构分配空间，并初始化此结构。 
</p>

<p>#include &quot;db.h&quot; </p>

<p>/* Open or create a database. Same arguments as open(). */ </p>

<p>DB * </p>

<p>db_open(const char *pathname, int oflag, int mode) </p>

<p>{ </p>

<p>DB *db; </p>

<p>int i, len; </p>

<p>char asciiptr[PTR_SZ + 1], </p>

<p>hash[(NHASH_DEF + 1) * PTR_SZ + 2]; </p>

<p>/* +2 for newline and null */ </p>

<p>struct stat statbuff; </p>

<p>/* Allocate a DB structure, and the buffers it needs */ </p>

<p>len = strlen(pathname); </p>

<p>if ( (db = _db_alloc(len)) == NULL) </p>

<p>err_dump(&quot;_db_alloc error for DB&quot;); </p>

<p>db-&gt;oflag = oflag; /* save a copy of the open flags */ </p>

<p>/* Open index file */ </p>

<p>strcpy(db-&gt;name, pathname); </p>

<p>strcat(db-&gt;name, &quot;.idx&quot;); </p>

<p>if ( (db-&gt;idxfd = open(db-&gt;name, oflag, mode)) &lt; 0) { </p>

<p>_db_free(db); </p>

<p>return(NULL); </p>

<p>} </p>

<p>/* Open data file */ </p>

<p>strcpy(db-&gt;name + len, &quot;.dat&quot;); </p>

<p>if ( (db-&gt;datfd = open(db-&gt;name, oflag, mode)) &lt; 0) { </p>

<p>_db_free(db); </p>

<p>return(NULL); </p>

<p>} </p>

<p>/* If the database was created, we have to initialize it */ </p>

<p>if ((oflag &amp; (O_CREAT | O_TRUNC)) == (O_CREAT | O_TRUNC)) { </p>

<p>/* Write lock the entire file so that we can stat </p>

<p>the file, check its size, and initialize it, </p>

<p>as an atomic operation. */ </p>

<p>if (writew_lock(db-&gt;idxfd, 0, SEEK_SET, 0) &lt; 0) </p>

<p>err_dump(&quot;writew_lock error&quot;); </p>

<p>if (fstat(db-&gt;idxfd, &amp;statbuff) &lt; 0) </p>

<p>err_sys(&quot;fstat error&quot;); </p>

<p>if (statbuff.st_size == 0) { </p>

<p>如果数据库正被建立，则我们必须加锁。考虑两个进程同时试图建立同一个数