Buffer Cache ——模拟实验（1）

pz0513

这是参照《UNIX操作系统设计》一书中的缓冲区算法做的缓冲区模拟实验，没有delayed-write, 没有实际块读写。

为了容易观察，hashtable的大小只有2，所有bufferheader的数量只有5个。

测试的输入内容是
7
0 0 3
0 1 5
1 0 9
1 1 8
0 2 13
3 4 43
2 4 22



#include stdio.h>
#define HASHSIZE 2
#define NR_BUFFER 5
struct bufferhead {
    int data;
    int devnum;
    int blknum;
    int busy;
    struct bufferhead *prev_hash;
    struct bufferhead *next_hash;
    struct bufferhead *prev_free;
    struct bufferhead *next_free;
};
struct bufferhead *hashtable[HASHSIZE];
struct bufferhead *freelist = &(struct bufferhead){};
struct bufferhead bfs[NR_BUFFER];
#define HASH(devnum, blknum) ((devnum) ^ (blknum)) % HASHSIZE
void insert_to_hashqueue(struct bufferhead *p) {
    int i;
    i = HASH(p->devnum, p->blknum);
    if(hashtable == NULL){
        hashtable = p;
        p->next_hash = p;
        p->prev_hash = p;
    }else{
        p->next_hash = hashtable->next_hash;
        p->prev_hash = hashtable;
        hashtable->next_hash = p;
        p->next_hash->prev_hash = p;
    }
}
void remove_from_hashqueue(struct bufferhead *p) {
    int i;
    i = HASH(p->devnum, p->blknum);
    if(p->next_hash)
        p->next_hash->prev_hash = p->prev_hash;
    if(p->prev_hash)
        p->prev_hash->next_hash = p->next_hash;
    //if p is head
    if(hashtable == p){
        //and it is the only one
        if(hashtable->next_hash == p)
            hashtable = NULL;
        else
            hashtable = p->next_hash;
    }
}
struct bufferhead *getblk(int devnum, int blknum) {
    int i, found;
    struct bufferhead *p;
    found = 0;
    while(!found){
        //search the buffer for the block in hashtable
        i = HASH(devnum, blknum);
        if(hashtable != NULL) {
            p = hashtable;
            while(p != hashtable->prev_hash &&
                  !(p->devnum == devnum && p->blknum == blknum)) {
                p = p->next_hash;
            }
            if(p == hashtable->prev_hash){//if this is the last
                //and it match
                if(p->devnum == devnum && p->blknum == blknum)
                    found = 1;
            }
            else
                found = 1;
        }
        //we find it
        if(found) {
            //but it is busy, so sleep until it is release, then search again
            if(p->busy) {
                pause();
                found = 0;
                continue;
            }
            //it is free
            p->busy = 1;
            p->prev_free->next_free = p->next_free;
            p->next_free->prev_free = p->prev_free;
            return p;
        }else {// we cannot find it
            //the free list is empty, so, sleep until a buffer is released
            if(freelist->next_free == freelist) {
                pause();
                continue;
            }
            //do not consider delay write, so just remove it from freelist and
            //old hash queue, and add to new hashqueue
            //allocate a new buffer from the free list
            p = freelist->next_free;
            freelist->next_free = p->next_free;
            p->next_free->prev_free = freelist;
            remove_from_hashqueue(p);
            p->devnum = devnum;
            p->blknum = blknum;
            p->busy = 1;
            insert_to_hashqueue(p);
            return p;
        }
    }
}
void brelse(struct bufferhead *p) {
    p->busy = 0;
    p->next_free = freelist;
    p->prev_free = freelist->prev_free;
    freelist->prev_free = p;
    p->prev_free->next_free = p;
}
void init_bufferhead() {
    int i;
   
    freelist->next_free = bfs;
    freelist->prev_free = bfs + NR_BUFFER - 1;
    for(i = 0; i  NR_BUFFER; i++) {
        bfs.busy = 0;
        bfs.next_free = bfs + i + 1;
        bfs.prev_free = bfs + i - 1;
    }
    bfs[0].prev_free = freelist;
    bfs[NR_BUFFER - 1].next_free = freelist;
}
void testshow() {
    int i;
    struct bufferhead *p;
    for(i = 0; i  HASHSIZE; i++){
        p = hashtable;
        while(p && p->next_hash != hashtable){
            printf("(%d, %d, %d) ", p->devnum, p->blknum, p->data);
            p = p->next_hash;
        }
        if(p) {
            printf("(%d, %d, %d)\n", p->devnum, p->blknum, p->data);
        }
    }
    printf("---------------------------------\n");
}
int main() {
    struct bufferhead *p;
    int n, m, devnum, blknum, data;
   
    init_bufferhead();
    scanf("%d", &n);
    while(n > 0) {
        scanf("%d%d%d", &devnum, &blknum, &data);
        p = getblk(devnum, blknum);
        p->data = data;
        brelse(p);
        testshow();
        n--;
    }
    //test too
    p = getblk(1, 1);
    printf("%d\n", p->data);
    brelse(p);
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/77943/showart_1993763.html