Buffer Cache ——模拟实验（1）

 

这是参照《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[i] == NULL){
        hashtable[i] = p;
        p->next_hash = p;
        p->prev_hash = p;
    }else{
        p->next_hash = hashtable[i]->next_hash;
        p->prev_hash = hashtable[i];
        hashtable[i]->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[i] == p){
        //and it is the only one

        if(hashtable[i]->next_hash == p)
            hashtable[i] = NULL;
        else
            hashtable[i] = 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[i] != NULL) {
            p = hashtable[i];
            while(p != hashtable[i]->prev_hash &&
                  !(p->devnum == devnum && p->blknum == blknum)) {
                p = p->next_hash;
            }
            if(p == hashtable[i]->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[i].busy = 0;
        bfs[i].next_free = bfs + i + 1;
        bfs[i].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[i];
        while(p && p->next_hash != hashtable[i]){
            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);
}