-
Notifications
You must be signed in to change notification settings - Fork 0
/
buffer.c
173 lines (137 loc) · 4.67 KB
/
buffer.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <stdio.h>
#include "buffer.h"
#include "free-list.h"
#include "hash-queue.h"
/* Mock the Hard disk size */
#define HARD_DISK_SIZE 1024 * 1000 * 10
/* Define the number of buffers in buffer cache */
#define BUFFER_COUNT 1000
/* Define the number of hash queues */
#define HASH_QUEUE_COUNT 20
/* Pseudo Hard Disk */
unsigned char HARD_DISK[HARD_DISK_SIZE];
/* The Buffer Cache */
buffer BUFFER_CACHE[BUFFER_COUNT];
/* Free List Header */
buffer *FREE_LIST;
/* Hash Queue Headers Array */
buffer *HASH_QUEUE;
int main (int argc, char **argv)
{
// function declarations
buffer *getblk(unsigned int file_system_number, unsigned int block_number);
void brelse(buffer *block);
buffer *bread (unsigned int file_system_number, unsigned int block_number);
buffer *breada(unsigned int file_system_number, unsigned int block_number, unsigned int afile_system_number, unsigned int ablock_number);
void bwrite(buffer *block);
// code
FREE_LIST = init_free_list (BUFFER_CACHE, BUFFER_COUNT);
HASH_QUEUE = init_hash_queue (BUFFER_CACHE, BUFFER_COUNT, HASH_QUEUE_COUNT);
/* CHECK LISTS ARE CREATED AS REQUIRED
print_free_list(FREE_LIST);
print_hash_queue(&HASH_QUEUE[0]);
print_hash_queue(&HASH_QUEUE[1]);
/* Hash Function
printf("Hash Queue for block 2014: %d \n", hash(0, 2014));
printf("Hash Queue for block 0: %d \n", hash(0, 0));
printf("Hash Queue for block 2021: %d \n", hash(0, 2021));
/* Free List Function
print_free_list(FREE_LIST);
remove_free_list(FREE_LIST);
remove_free_list(FREE_LIST->next_Free_List);
print_free_list(FREE_LIST);
/* Set Hash Queue Test
printf("\nHash Queue 0: ");
print_hash_queue(&HASH_QUEUE[0]);
printf("\nHash Queue 1: ");
print_hash_queue(&HASH_QUEUE[2]);
FREE_LIST->next_Free_List->logical_block_number = 1002;
set_hash_queue(FREE_LIST->next_Free_List, HASH_QUEUE);
printf("\nHash Queue 0: ");
print_hash_queue(&HASH_QUEUE[0]);
printf("\nHash Queue 1: ");
print_hash_queue(&HASH_QUEUE[2]);
/* LOCK and UNLOCK buffer mechanism
buffer *block = FREE_LIST->next_Free_List;
block->status |= BF_LOCKED;
block->status |= BF_VALID;
printf("%x ", block->status);
block->status &= (~BF_LOCKED);
printf("%x ", block->status);
/************************************************************/
printf("\n -- done -- \n");
return 0;
}
/******************** ALGORITHMS ********************/
/*
* getblk - get a free buffer from buffer cache
* input1 - logical device number / file system number
* input2 - logical block number
* output - locked buffer
*/
buffer *getblk(unsigned int file_system_number, unsigned int block_number)
{
buffer *blk = NULL;
int onHashQueue = 0;
int hash_queue_index = hash(file_system_number, block_number);
while(!blk) /* while buffer not found */
{
/* scan hash queue for required block */
buffer *ptr = HASH_QUEUE[hash_queue_index].next_Hash_Queue;
while(ptr->status != BF_DUMMY)
{
if(ptr->logical_block_number == block_number)
{
onHashQueue = 1;
break;
}
ptr = ptr->next_Hash_Queue;
}
if(onHashQueue) /* block in hash queue */
{
if(ptr->status & BF_LOCKED) /* scenario 5 */
{
/* sleep (event: buffer becomes free) */
continue;
}
ptr->status |= BF_LOCKED; /* scenario 1 */
remove_free_list(ptr);
return ptr;
}
else /* block not on hash queue */
{
if(FREE_LIST->next_Free_List->status & BF_DUMMY) /* scenario 4 */
{
/* sleep (event: any buffer becomes free) */
continue;
}
blk = get_free_buffer(FREE_LIST);
if(blk->status & BF_DWRITE) /* scenario 3 */
{
/* ASYNC bwrite() */
continue;
}
/* scenario 2 */
set_hash_queue(blk, HASH_QUEUE);
blk->status |= BF_LOCKED;
return(blk);
}
}
}
/*
* brelse - release a locked buffer
* input - locked buffer
* output - none
*/
void brelse(buffer *block)
{
/* wakeup: all who are waiting for any buffer to become free */
/* wakeup: all who are waiting for this buffer to become free */
/* buffer is valid and is not old */
if ((block->status & BF_VALID) && !(block->status & BF_OLD))
insert_end_free_list (FREE_LIST, block);
else
insert_head_free_list(FREE_LIST, block);
/* unlock buffer */
block->status &= (~BF_LOCKED);
}