亲宝软件园·资讯

展开

基于哈希表实现页面置换算法

RhythmLian 人气:0

首先,在看这篇文章前,你需要了解缓存是干嘛的?

缓存

    众所周知,程序运行时,数据一般存在内存或磁盘里,而内存中的数据总是可以被更快速的获取。但是内存空间是有限的,大多数人PC的内存可能在4G~16G之间,这意味着你必须要舍弃一部分不频繁被访问的数据,把它们存在磁盘里;而把经常需要被访问的数据存在内存里,这就是缓存的基本思路。

    但对于程序(和你)而言,无法预测哪些数据是被经常访问的,所以你只能根据访问数据的历史来推测和统计哪些数据是被经常访问的,并把它存在内存里,如果内存满了就找个最不被经常访问的数据替换掉。这个统计过程和改写内存的策略通常被称为“页面置换算法”,事实上,所有可实现的缓存策略(页面置换算法)都是基于历史访问信息来实现的。科学家经过几十年的努力,发明了许许多多的页面置换算法,比如:FIFO、LFU、LRU、ARC、MQ、GD、GDSF....,它们各有所长,没有孰优孰劣。

    缺页数(率):为了评判页面置换算法的优劣,针对访问数据的次数n,和数据未被缓存命中的次数(缺页数)p,缺页率=p/n。显然,缺页率越小,页面置换算法越优秀。

 

正事

    本文基于哈希表的内存管理结构,简单地实现线程安全的缓存算法(LFU, LRU, ARC, MQ, GD, GDSF):

  首先看API:(cache.h)

 1 #pragma once
 2 
 3 #include <sys/time.h>
 4 #ifdef __cplusplus
 5 extern "C" {
 6 #endif
 7 
 8 typedef struct _cache *cache_t, _cache;
 9 typedef struct _cache_ele cache_pair;
10 typedef struct _cache_ret { /// 读缓存返回结果
11     long cost;        /// 代价
12     const char*cache; /// 数据
13 }cache_ret;
14 /**
15  * @API
16  * create, delete, search, read
17  */
18 cache_t   new_cache        (unsigned capacity, cache_ret(*model)(cache_t, const char*)); /// 新建
19 void      del_cache        (cache_t cache);                                              /// 删除
20 unsigned  cache_page_fault (cache_t cache);                                              /// 缺页数
21 cache_ret read_cache       (cache_t cache, const char*filename);                         /// 读缓存
22 
23 /**
24  * @Cache_Algorithm_Model
25  * cache_ret(*)(cache_t, const char*)
26  */
27 cache_ret LRU (cache_t cache, const char*request); /// 页面替换算法模型
28 cache_ret LFU (cache_t cache, const char*request);
29 cache_ret ARC (cache_t cache, const char*request);
30 cache_ret MQ  (cache_t cache, const char*request);
31 cache_ret GD  (cache_t cache, const char*request);
32 cache_ret GDSF(cache_t cache, const char*request);
33 
34 #ifdef __cplusplus
35 }
36 #endif

 

    数据结构:

    缓存:  

 1 struct _cache_ele {                   /// 数据单元
 2     char *key, *file_cache;           /// 键值、数据 
 3     long cost;                        /// 代价(长度)
 4     struct timeval pre_t;             /// 上次访问时间
 5     unsigned int cnt;                 /// 访问次数
 6     struct _cache_ele *nxt, *pre;
 7 };
 8 
 9 struct _cache {
10     cache_pair table[HASHTABELSIZE], *first_table;      /// 哈希表,first_table根据需要生成
11     cache_ret (*f)(cache_t, const char *);              /// 页面置换策略
12     pthread_mutex_t mutex;                              /// 线程安全的锁
13     unsigned int capacity, _cur, first_cur, page_fault; /// 容量、当前量、ft当前量、缺页数
14 };/// *cache_t

     缓存策略实现:

     缓存策略实际上是一个选择问题,如果缓存没有满,那么显然可以直接把新请求的数据直接读到缓存中,如果满了,则按照策略选一个数据替换掉。

     (cache.c完整代码)

  1 #include "cache.h"
  2 #include <zconf.h>
  3 #include "stdlib.h"
  4 #include <sys/mman.h>
  5 #include "pthread.h"
  6 #include "string.h"
  7 #include <sys/time.h>
  8 #include <fcntl.h>
  9 
 10 #define RMALLOC(type,n) (type*)malloc(sizeof(type)*(n))
 11 #define MALLOC(p,type,n) type*p = RMALLOC(type, n)
 12 #define MAX_BUFFER_LEN 1024ll * 1024
 13 #ifndef HASHTABLESZIE
 14 #define HASHTABELSIZE 10005
 15 #endif
 16 
 17 unsigned int string_hash(const char *str) {
 18     unsigned int hash = 0;
 19     int i;
 20     for (i = 0; *str; i++) {
 21         if ((i & 1) == 0)hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
 22         else hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
 23     }
 24     return (hash & 0x7FFFFFFF);
 25 }
 26 
 27 struct _cache_ele {
 28     char *key, *file_cache;
 29     long cost;
 30     struct timeval pre_t;
 31     unsigned int cnt;
 32     struct _cache_ele *nxt, *pre;
 33 };
 34 
 35 cache_pair*new_cache_pair(){
 36     MALLOC(res, cache_pair, 1);
 37     res->key = res->file_cache = NULL;
 38     res->cnt = res->cost = 0;
 39     res->nxt = res->pre = NULL;
 40     return res;
 41 }
 42 
 43 void del_cache_pair(cache_pair *del) {
 44     free(del->key);
 45     free(del->file_cache);
 46     free(del);
 47 }
 48 
 49 struct _cache {
 50     cache_pair table[HASHTABELSIZE], *first_table;      /// hash table
 51     cache_ret (*f)(cache_t, const char *);              /// function pointer
 52     pthread_mutex_t mutex;
 53     unsigned int capacity, _cur, first_cur, page_fault;
 54 };/// *cache_t
 55 
 56 cache_t new_cache(unsigned capacity, cache_ret(*model)(cache_t, const char *)) {
 57     if (model) {
 58         MALLOC(ret, _cache, 1);
 59         pthread_mutex_init(&ret->mutex, NULL);
 60         ret->capacity = capacity;
 61         ret->page_fault = ret->first_cur = ret->_cur = 0;
 62         memset(ret->table, 0, sizeof(cache_pair) * HASHTABELSIZE);
 63         if (model == ARC)ret->first_table = RMALLOC(cache_pair, HASHTABELSIZE);
 64         else if(model == MQ)ret->first_table = RMALLOC(cache_pair, HASHTABELSIZE * 3);
 65         else ret->first_table = NULL;
 66         ret->f = model;
 67         return ret;
 68     }
 69     return NULL;
 70 }
 71 
 72 cache_ret read_cache(cache_t cache, const char *filename) {
 73     pthread_mutex_lock(&cache->mutex);
 74     cache_ret res = cache->f(cache, filename);
 75     pthread_mutex_unlock(&cache->mutex);
 76     return res;
 77 }
 78 
 79 unsigned cache_page_fault(cache_t cache){
 80     return cache->page_fault;
 81 }
 82 
 83 void del_cache(cache_t cache) {
 84     pthread_mutex_destroy(&cache->mutex);
 85     for (int i = 0; i < HASHTABELSIZE; ++i) {
 86         cache_pair *p = cache->table[i].nxt;
 87         while (p) {
 88             cache_pair *tmp = p;
 89             p = p->nxt;
 90             del_cache_pair(tmp);
 91         }
 92     }
 93     if (cache->first_table) {
 94         for (int i = 0; i < HASHTABELSIZE; ++i) {
 95             cache_pair *p = cache->first_table[i].nxt;
 96             while (p) {
 97                 cache_pair *tmp = p;
 98                 p = p->nxt;
 99                 del_cache_pair(tmp);
100             }
101         }
102         free(cache->first_table);
103     }
104     free(cache);
105 }
106 
107 cache_pair *is_in_table(cache_pair *table, const char *request, int *ret) {
108     unsigned int index = string_hash(request) % HASHTABELSIZE;
109     cache_pair *src = table + index;
110     if (!src->nxt) {
111         *ret = 0;
112         return src;
113     }
114     src = src->nxt;
115     while (strcmp(src->key, request)) {
116         cache_pair *pre = src;
117         src = src->nxt;
118         if (!src) { /// not in table: return pre node
119             *ret = 0;
120             return pre;
121         }
122     }
123     *ret = 1;
124     return src;
125 }
126 
127 void replace_after_src(cache_pair *src, const char *request) {
128     src = src->nxt;
129     src->cnt = 1;
130     gettimeofday(&src->pre_t, NULL);
131     src->key = src->key ? (char *) realloc(src->key, strlen(request) + 1) : RMALLOC(char, strlen(request) + 1);
132     strcpy(src->key, request);
133     int fd = open(request, O_RDONLY);
134     if (fd > 0) {
135         char *fp = mmap(NULL, MAX_BUFFER_LEN, PROT_READ, MAP_SHARED, fd, 0);
136         src->cost = strlen(fp) + 1;
137         src->file_cache = src->file_cache ? (char *) realloc(src->file_cache, src->cost) : RMALLOC(char, src->cost);
138         strcpy(src->file_cache, fp);
139         munmap(fp, MAX_BUFFER_LEN);
140         close(fd);
141     } else {
142         src->cost = -1;
143         if (src->file_cache)free(src->file_cache);
144         src->file_cache = NULL;
145     }
146 }
147 
148 void add_after_src(cache_pair *src, const char *request) {
149     src->nxt = new_cache_pair();
150     src->nxt->pre = src;
151     replace_after_src(src, request);
152 }
153 
154 void replace_copy(cache_pair *src, cache_pair *aim) {
155     src = src->nxt;
156     src->cnt = aim->cnt;
157     gettimeofday(&src->pre_t, NULL);
158     src->cost = aim->cost;
159     free(src->key);
160     free(src->file_cache);
161     src->key = aim->key;
162     src->file_cache = aim->file_cache;
163     aim->pre->nxt = aim->nxt;
164     free(aim);
165 }
166 
167 void add_copy(cache_pair *src, cache_pair *aim) {
168     src->nxt = new_cache_pair();
169     src->nxt->pre = src;
170     replace_copy(src, aim);
171 }
172 
173 cache_pair *LRU_CHOOSE(cache_pair *table) {
174     double mn = -1;
175     cache_pair *res = NULL;
176     for (int i = 0; i < HASHTABELSIZE; ++i)
177         if (table[i].nxt) {
178             cache_pair *ptr = table + i;
179             while (ptr->nxt) {
180                 cache_pair *pre = ptr;
181                 ptr = ptr->nxt;
182                 double cur = ptr->pre_t.tv_sec * 1000.0 + ptr->pre_t.tv_usec / 1000.0;
183                 if (mn < 0 || cur < mn) {
184                     mn = cur;
185                     res = pre;
186                 }
187             }
188         }
189     return res;
190 }
191 
192 cache_pair *LFU_CHOOSE(cache_pair *table) {
193     int mn = -1;
194     cache_pair *res = NULL;
195     for (int i = 0; i < HASHTABELSIZE; ++i)
196         if (table[i].nxt) {
197             cache_pair *ptr = table + i;
198             while (ptr->nxt) {
199                 cache_pair *pre = ptr;
200                 ptr = ptr->nxt;
201                 int cur = ptr->cnt;
202                 if (mn < 0 || cur < mn) {
203                     mn = cur;
204                     res = pre;
205                 }
206             }
207         }
208     return res;
209 }
210 
211 cache_pair *GD_CHOOSE(cache_pair *table) {
212     double mn = -1;
213     cache_pair *res = NULL;
214     for (int i = 0; i < HASHTABELSIZE; ++i)
215         if (table[i].nxt) {
216             cache_pair *ptr = table + i;
217             while (ptr->nxt) {
218                 cache_pair *pre = ptr;
219                 ptr = ptr->nxt;
220                 double cur = ptr->cost + ptr->pre_t.tv_sec;
221                 if (mn < 0 || cur < mn) {
222                     mn = cur;
223                     res = pre;
224                 }
225             }
226         }
227     return res;
228 }
229 
230 cache_pair *GDSF_CHOOSE(cache_pair *table) {
231     double mn = -1;
232     cache_pair *res = NULL;
233     for (int i = 0; i < HASHTABELSIZE; ++i)
234         if (table[i].nxt) {
235             cache_pair *ptr = table + i;
236             while (ptr->nxt) {
237                 cache_pair *pre = ptr;
238                 ptr = ptr->nxt;
239                 double cur = ptr->cnt * ptr->cost + ptr->pre_t.tv_sec;
240                 if (mn < 0 || cur < mn) {
241                     mn = cur;
242                     res = pre;
243                 }
244             }
245         }
246     return res;
247 }
248 
249 cache_ret LRU(cache_t set, const char *request) {
250     int flag;
251     cache_pair *src = is_in_table(set->table, request, &flag);
252     if (flag) { /// real node
253         src->cnt++;
254         gettimeofday(&src->pre_t, NULL);
255     } else { /// pre node
256         ++set->page_fault;
257         if (set->_cur == set->capacity) { /// choose and replace
258             src = LRU_CHOOSE(set->table);
259             replace_after_src(src, request);
260         } else { /// add node
261             add_after_src(src, request);
262             ++set->_cur;
263         }
264         src = src->nxt;
265     }
266     return (cache_ret) {src->cost, src->file_cache};
267 }
268 
269 cache_ret LFU(cache_t set, const char *request) {
270     int flag;
271     cache_pair *src = is_in_table(set->table, request, &flag);
272     if (flag) {
273         src->cnt++;
274         gettimeofday(&src->pre_t, NULL);
275     } else {
276         ++set->page_fault;
277         if (set->_cur == set->capacity) {
278             src = LFU_CHOOSE(set->table);
279             replace_after_src(src, request);
280         } else {
281             add_after_src(src, request);
282             ++set->_cur;
283         }
284         src = src->nxt;
285     }
286     return (cache_ret) {src->cost, src->file_cache};
287 }
288 
289 cache_ret ARC(cache_t set, const char *request) {
290     int flag;
291     cache_pair *first_table = set->first_table;
292     cache_pair *src = is_in_table(set->table, request, &flag);
293     if (flag) { /// in second table
294         src->cnt++;
295         gettimeofday(&src->pre_t, NULL);
296     } else {
297         cache_pair *first_src = is_in_table(first_table, request, &flag);
298         if (flag) { /// in first table
299             ++first_src->cnt;
300             if (set->_cur == set->capacity) { /// choose and replace
301                 src = LRU_CHOOSE(set->table);
302                 replace_copy(src, first_src); /// copy data to nxt src and delete first_src
303             } else { /// add node
304                 add_copy(src, first_src); /// create node and replace
305                 ++set->_cur;
306             }
307             src = src->nxt;
308         } else { /// not in first table
309             ++set->page_fault;
310             if (set->first_cur == set->capacity) {
311                 first_src = LRU_CHOOSE(first_table);
312                 replace_after_src(first_src, request);
313             } else {
314                 add_after_src(first_src, request);
315                 ++set->first_cur;
316             }
317             src = first_src->nxt;
318         }
319     }
320     return (cache_ret) {src->cost, src->file_cache};
321 }
322 
323 cache_ret MQ(cache_t set, const char *request) {
324     int flag;
325     cache_pair *first_table = set->first_table;
326     cache_pair *src = is_in_table(set->table, request, &flag);
327     if (flag) { /// in second table
328         src->cnt++;
329         gettimeofday(&src->pre_t, NULL);
330     } else {
331         cache_pair *first_src = is_in_table(first_table, request, &flag);
332         if (flag) { /// in first table
333             ++first_src->cnt;
334             if (set->_cur == set->capacity) { /// choose and replace
335                 src = LRU_CHOOSE(set->table);
336                 replace_copy(src, first_src); /// copy data to nxt src and delete first_src
337             } else { /// add node
338                 add_copy(src, first_src); /// create node and replace
339                 ++set->_cur;
340             }
341             src = src->nxt;
342         } else { /// not in first table
343             ++set->page_fault;
344             if (set->first_cur == set->capacity) {
345                 first_src = LRU_CHOOSE(first_table);
346                 replace_after_src(first_src, request);
347             } else {
348                 add_after_src(first_src, request);
349                 ++set->first_cur;
350             }
351             src = first_src->nxt;
352         }
353     }
354     return (cache_ret) {src->cost, src->file_cache};
355 }
356 
357 cache_ret GD(cache_t set, const char *request) {
358     int flag;
359     cache_pair *src = is_in_table(set->table, request, &flag);
360     if (flag) {
361         src->cnt++;
362         gettimeofday(&src->pre_t, NULL);
363     } else {
364         ++set->page_fault;
365         if (set->_cur == set->capacity) {
366             src = GD_CHOOSE(set->table);
367             replace_after_src(src, request);
368         } else {
369             add_after_src(src, request);
370             ++set->_cur;
371         }
372         src = src->nxt;
373     }
374     return (cache_ret) {src->cost, src->file_cache};
375 }
376 
377 cache_ret GDSF(cache_t set, const char *request) {
378     int flag;
379     cache_pair *src = is_in_table(set->table, request, &flag);
380     if (flag) {
381         src->cnt++;
382         gettimeofday(&src->pre_t, NULL);
383     } else {
384         ++set->page_fault;
385         if (set->_cur == set->capacity) {
386             src = GDSF_CHOOSE(set->table);
387             replace_after_src(src, request);
388         } else {
389             add_after_src(src, request);
390             ++set->_cur;
391         }
392         src = src->nxt;
393     }
394     return (cache_ret) {src->cost, src->file_cache};
395 }
View Code

 

 

---版权:代码遵从MIT协议开源,可以按需使用。(地址:cache.c)

---转载需标明出处,侵权必究

---作者:RhythmLian: https://github.com/Rhythmicc

加载全部内容

相关教程
猜你喜欢
用户评论