unix高级环境编程 第二十章 数据库函数库:习题讨论
缘由源代码看完了,大概看懂了,现在来自己回答一下课后练习题,来看看自己是不是真的看懂了。习题20.1题干在_db_dodelte中使用的加锁是比较保守的。例如,如果等到真正要用空闲链表时再加锁,则可获得更大的并发度。如果将调用write_lock移到调用_db_writedat和_db_readptr之间会发生什么呢?_db_dodelte方法如下:/** De
缘由
源代码看完了,大概看懂了,现在来自己回答一下课后练习题,来看看自己是不是真的看懂了。
习题20.1
题干
在_db_dodelte中使用的加锁是比较保守的。例如,如果等到真正要用空闲链表时再加锁,则可获得更大的并发度。如果将调用write_lock移到调用_db_writedat和_db_readptr之间会发生什么呢?
_db_dodelte方法如下:
/*
* Delete the current record specified by the DB structure.
* This function is called by db_delete and db_store, after
* the record has been located by _db_find_and_lock.
*/
static void
_db_dodelete(DB *db)
{
int i;
char *ptr;
off_t freeptr, saveptr;
/*
* Set data buffer and key to all blanks.
*/
for (ptr = db->datbuf, i = 0; i < db->datlen - 1; i++)
*ptr++ = SPACE;
*ptr = 0; /* null terminate for _db_writedat */
ptr = db->idxbuf;
while (*ptr)
*ptr++ = SPACE;
/*
* We have to lock the free list.
* zy:因为要将删除的记录移动到空闲链表上,这将改变空闲链表,
* 所以每次只能有一个进程这么做。
*/
if (writew_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
err_dump("_db_dodelete: writew_lock error");
/*
* Write the data record with all blanks.
*/
_db_writedat(db, db->datbuf, db->datoff, SEEK_SET);
/*
* Read the free list pointer. Its value becomes the
* chain ptr field of the deleted index record. This means
* the deleted record becomes the head of the free list.
*/
freeptr = _db_readptr(db, FREE_OFF);
/*
* Save the contents of index record chain ptr,
* before it's rewritten by _db_writeidx.
*/
saveptr = db->ptrval;
/*
* Rewrite the index record. This also rewrites the length
* of the index record, the data offset, and the data length,
* none of which has changed, but that's OK.
*/
_db_writeidx(db, db->idxbuf, db->idxoff, SEEK_SET, freeptr);
/*
* Write the new free list pointer.
*/
_db_writeptr(db, FREE_OFF, db->idxoff);
/*
* Rewrite the chain ptr that pointed to this record being
* deleted. Recall that _db_find_and_lock sets db->ptroff to
* point to this chain ptr. We set this chain ptr to the
* contents of the deleted record's chain ptr, saveptr.
*/
_db_writeptr(db, db->ptroff, saveptr);
if (un_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
err_dump("_db_dodelete: un_lock error");
}
我的解答
我认为不能这么干。
因为
_db_writedat(db, db->datbuf, db->datoff, SEEK_SET);
这一句代码中的,db->datbuf已经被设置为空格了,(因为作业约定删除的含义,就是将其设置为空格)。如果我们先设置为了空格之后,我们再执行这一句(也就是去锁住空闲链表,因为马上要对空闲链表进行操作了):
if (writew_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
err_dump("_db_dodelete: writew_lock error");
但是有一种可能发生,就是此时有另外一个线程正在处理空闲链表,此时该该进程堵塞在这一句。然而,由于我们已经把要删除的内容设置为空,这还会导致别的进程还能够去读我们刚刚已经把内容设置为空格的数据,别的读进程还以为其正常的处于其该在散列表内,正常的读取其内容,却只能读到错误的空格信息。writew_lock也不知道要堵塞到什么时候,堵塞期间那么就会一直读到错误的内容,就是空格内容。
书上的答案
给出db_nextrec的代码:
/*
* Return the next sequential record.
* We just step our way through the index file, ignoring deleted
* records. db_rewind must be called before this function is
* called the first time.
*/
char *
db_nextrec(DBHANDLE h, char *key)
{
DB *db = h;
char c;
char *ptr;
/*
* We read lock the free list so that we don't read
* a record in the middle of its being deleted.
*/
if (readw_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
err_dump("db_nextrec: readw_lock error");
do {
/*
* Read next sequential index record.
*/
if (_db_readidx(db, 0) < 0) {
ptr = NULL; /* end of index file, EOF */
goto doreturn;
}
/*
* Check if key is all blank (empty record).
*/
ptr = db->idxbuf;
while ((c = *ptr++) != 0 && c == SPACE)
; /* skip until null byte or nonblank */
} while (c == 0); /* loop until a nonblank key is found */
if (key != NULL)
strcpy(key, db->idxbuf); /* return key */
ptr = _db_readdat(db); /* return pointer to data buffer */
db->cnt_nextrec++;
doreturn:
if (un_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0)
err_dump("db_nextrec: un_lock error");
return(ptr);
}
我应该还是把握到了要点,只是书中答案给的更准确,注意_db_dodelte和db_nextrec都试图对空闲链表加锁,一个读的,一个是写的。注意答案中说的删除就是将内容设置为空白,然后添加到空闲链表中去。
习题20.2
题干
我的解答
这和上面那道题的分析类似。比如当两个线程,一个调用_db_dodelte,另一个调用db_nextrec,而现在db_nextrec不对空闲链表加锁,那么其可以随意的读取索引文件的内容。只要调用_db_dodelte的线程刚刚执行完
_db_writedat(db, db->datbuf, db->datoff, SEEK_SET);
操作,还没来得及改变这个记录的索引之前,db_nextrec的线程又跑去读索引和内容,那么就会得到空格数据,就是被删除的内容。
书上的答案
书中所说确实是一种情况。
但是我认为我说的也是一种正确的、可能发生的情况。除非这里我误解了一点,难道加了写锁之后,别的线程完全不能碰了?我觉得是可以碰的,也就是说另一个线程完全不顾这个地方的锁机制,然后自己干想干的。
我觉得这个地方涉及书上说的P366页的强制性锁和建议行锁的区别和联系,在这里显然加的是建议行锁,如果加的是强制性锁,那么内核会对每一个read和write还有open进行检查,有没有违背一把锁的作用。那么此时,我说的情况不会发生。
习题20.3
题干
我的解答
讨论的这几个问题还真是环环相扣呀。如果改为强制性锁,那么内核会对每一个read和write还有open进行检查,有没有违背一把锁的作用,所以所有试图对这个区域进行read、write的操作的函数都会堵塞。
所以改为强制性锁后,题干结论不成立。
书上的答案
习题20.4
题干
我的解答
fsync的作用在书上61页有写,当然也可以自己man一下。
简单来说,fsync的作用就让发生在缓冲区内修改过的内容立刻冲洗到磁盘。并且fsync会堵塞等待这个过程完成后才会返回。书中有句重要的提示就是:fsync用于数据库这样的应用程序,确保将修改过的块立刻写到磁盘上。
基本上这句话已经告诉我们答案了,我认为在修改数据库文件的内容的时候恐怕都需要调用这个函数,并且将文件描述符传给这个函数,注意, 我们有两个文件,一个索引文件、还有一个是数据库文件。所以,我觉得在调用了:
int db_store(DBHANDLE, const char *, const char *, int);
int db_delete(DBHANDLE, const char *);
/*
* Flags for db_store().
*/
#define DB_INSERT 1 /* insert new record only */
#define DB_REPLACE 2 /* replace existing record */
#define DB_STORE 3 /* replace or insert */
下面两个函数时候都有必要调用一下fsync函数。
书上的答案
没有这道题的答案。
习题20.5
题干
大概是说按照这样的顺序:
_db_writedat(db, data, 0, SEEK_END);
_db_writeidx(db, key, 0, SEEK_END, ptrval);
我的解答
很显然,如果是当写了索引记录之后,再去写数据记录,很有可能造成一种情况就是,当写了索引记录之后,进程发生了切换,当然别的进程又去读了这个索引,所以拿数据,显然是没有数据(可能抛空)。
但是注意,由于db_store是会调用_db_find_and_lock函数,这个函数会锁住散列链,那么某些函数db_fetch和db_delete都会拿调用_db_find_and_lock函数,也都会对同一个地方试图加锁,所以这两个函数倒不会有问题。但是db_nextrec这个函数是不会去拿散列表的锁的,所以和会调用db_nextrec的函数产生竞争。db_nextrec函数读了索引,却没有数据。
书上的答案
我怎么觉得还没我分析的用心呢?
习题20.6
题干
我的解答
这个问题,我觉得倒可以简化一下,因为实验的要求只是想知道一下散列函数是否恰当。从db_nextrec来读取记录,又计算记录的散列值,太麻烦了。我就直接用其_db_hash来算很多很多词的散列值。对于一个散列函数是否好,还有有一个评价的标准:分布的是否均匀。我就用这个标准来衡量一下。584页,说了137是素数,所以具有良好的分布特性。
实验过程以及代码如下:
/**
* 1.读取wordlist的里面的每一个单词(共27220个),没有重复
* 2.把每一个单词当作key,计算其hash值
* 3.将以hash值为数组的下标的元素+1
* 4.打印统计每一个hash值的个数
*/
#include <stdio.h>
#define MAXLINE 137//单词我都已经看过了.都比较短,不超过20个,保险起见稍稍填写高一些
typedef unsigned long DBHASH; /* hash values */
#define NHASH_DEF 137 /* hash table size */
#define NULL ((void *)0)
int static hash[NHASH_DEF];
/**
* 改写来自db.c的_db_hash函数
*/
void _db_hash(const char *key)
{
DBHASH hval = 0;
char c;
int i;
for (i = 1; (c = *key++) != 0; i++)
hval += c * i; /* ascii char times its 1-based index */
hash[hval % NHASH_DEF]++;
}
int main(int argc, char **argv) {
FILE *fp;
fp=fopen("wordlist.txt","r");
char word[MAXLINE];
while(1){
if(fgets(word,MAXLINE,fp)==NULL){//读的一行包括换行符号,并且在最后再添加一个‘\0’
fprintf(stderr,"get word failed\n");//读到结尾或者出错都会有问题
break;
}
_db_hash(word);
}
int i,j;
for(i=0;i<NHASH_DEF;i++){
printf("%d\t%d:",i,hash[i]);
for(j=0;j<hash[i]/10;j++){
printf(".");
}
printf("\n");
}
}
结果,直方图用点表示,每10个word一个点:
0 274:...........................
1 257:.........................
2 286:............................
3 280:............................
4 288:............................
5 272:...........................
6 283:............................
7 281:............................
8 278:...........................
9 279:...........................
10 289:............................
11 282:............................
12 291:.............................
13 275:...........................
14 297:.............................
15 285:............................
16 305:..............................
17 269:..........................
18 293:.............................
19 284:............................
20 279:...........................
21 290:.............................
22 290:.............................
23 258:.........................
24 284:............................
25 287:............................
26 280:............................
27 271:...........................
28 270:...........................
29 251:.........................
30 265:..........................
31 252:.........................
32 277:...........................
33 253:.........................
34 248:........................
35 250:.........................
36 253:.........................
37 242:........................
38 248:........................
39 231:.......................
40 232:.......................
41 228:......................
42 226:......................
43 215:.....................
44 221:......................
45 208:....................
46 213:.....................
47 200:....................
48 201:....................
49 193:...................
50 212:.....................
51 180:..................
52 173:.................
53 183:..................
54 195:...................
55 161:................
56 184:..................
57 171:.................
58 168:................
59 168:................
60 178:.................
61 141:..............
62 148:..............
63 155:...............
64 146:..............
65 128:............
66 124:............
67 135:.............
68 138:.............
69 130:.............
70 115:...........
71 115:...........
72 130:.............
73 103:..........
74 111:...........
75 101:..........
76 109:..........
77 87:........
78 103:..........
79 95:.........
80 103:..........
81 99:.........
82 105:..........
83 107:..........
84 108:..........
85 108:..........
86 108:..........
87 96:.........
88 103:..........
89 98:.........
90 106:..........
91 114:...........
92 108:..........
93 105:..........
94 113:...........
95 121:............
96 122:............
97 115:...........
98 136:.............
99 146:..............
100 122:............
101 138:.............
102 154:...............
103 145:..............
104 135:.............
105 159:...............
106 157:...............
107 158:...............
108 169:................
109 181:..................
110 167:................
111 184:..................
112 187:..................
113 178:.................
114 177:.................
115 210:.....................
116 196:...................
117 210:.....................
118 210:.....................
119 210:.....................
120 220:......................
121 241:........................
122 209:....................
123 235:.......................
124 223:......................
125 240:........................
126 233:.......................
127 259:.........................
128 231:.......................
129 262:..........................
130 245:........................
131 272:...........................
132 252:.........................
133 268:..........................
134 255:.........................
135 275:...........................
136 281:............................
从图中来看,分布基本上比较均匀,但是这其实是一个很复杂的问题,我试着取了一个130,反正不是素数的数吧,结果如下(我觉得好坏肉眼无法判定,我不太想研究,所以没研究了):
0 281:............................
1 277:...........................
2 295:.............................
3 299:.............................
4 271:...........................
5 282:............................
6 275:...........................
7 292:.............................
8 255:.........................
9 270:...........................
10 266:..........................
11 250:.........................
12 258:.........................
13 257:.........................
14 258:.........................
15 263:..........................
16 241:........................
17 238:.......................
18 225:......................
19 224:......................
20 227:......................
21 227:......................
22 223:......................
23 210:.....................
24 206:....................
25 216:.....................
26 200:....................
27 193:...................
28 204:....................
29 184:..................
30 186:..................
31 198:...................
32 190:...................
33 166:................
34 161:................
35 163:................
36 153:...............
37 145:..............
38 132:.............
39 137:.............
40 131:.............
41 147:..............
42 137:.............
43 133:.............
44 137:.............
45 128:............
46 119:...........
47 135:.............
48 120:............
49 138:.............
50 106:..........
51 125:............
52 123:............
53 115:...........
54 119:...........
55 106:..........
56 117:...........
57 136:.............
58 105:..........
59 119:...........
60 114:...........
61 121:............
62 116:...........
63 142:..............
64 118:...........
65 125:............
66 130:.............
67 133:.............
68 140:..............
69 143:..............
70 142:..............
71 142:..............
72 154:...............
73 149:..............
74 162:................
75 165:................
76 155:...............
77 175:.................
78 170:.................
79 190:...................
80 185:..................
81 199:...................
82 176:.................
83 191:...................
84 199:...................
85 218:.....................
86 196:...................
87 217:.....................
88 217:.....................
89 223:......................
90 217:.....................
91 246:........................
92 221:......................
93 236:.......................
94 233:.......................
95 254:.........................
96 239:.......................
97 250:.........................
98 245:........................
99 249:........................
100 261:..........................
101 271:...........................
102 257:.........................
103 267:..........................
104 264:..........................
105 268:..........................
106 263:..........................
107 261:..........................
108 269:..........................
109 292:.............................
110 267:..........................
111 276:...........................
112 270:...........................
113 281:............................
114 277:...........................
115 309:..............................
116 280:............................
117 299:.............................
118 276:...........................
119 303:..............................
120 285:............................
121 297:.............................
122 295:.............................
123 305:..............................
124 285:............................
125 307:..............................
126 278:...........................
127 289:............................
128 283:............................
129 294:.............................
书上的解答
没有答案
习题20.7
题干
我的解答
这个题,挺没意思。 反正使用到了NHASH_DEF一共四个地方,把这四个地方改为db->nhash,再在db_open函数里多写一个参数给db->nhash赋值即可。还有些细节,比如多写一个参数给db->nhash赋值一定要在最开始的时候执行。在所有使用到db->nhash的地方之前。书上的解答
没有答案点击打开链接
习题20.8
题干
我的解答
找了很久,连英文都没有答案,不过通过我阅读来看,感觉应该是不支持了。如果使用NFS的话,好像有自己的一套机制。
参见:NFS中的文件锁
书上的解答
书上没有答案
更多推荐
所有评论(0)