#include<>
#include<>
#include<>
#include<>
#include<>
#define NUM_OF_INSTRUSTIONS 320
void generate_instrustions(__u_int* instrustions,__u_int* original_page_address_flow)
{
__u_int page_no = 0;
for(size_t i = 0;i < NUM_OF_INSTRUSTIONS;i += 4) {
__u_int begin;
do
{
begin = (__u_int)rand() % NUM_OF_INSTRUSTIONS;
} while (begin == 319);
instrustions[i] = begin + 1;
original_page_address_flow[i] = (begin + 1) / 10;
__u_int before;
do
{
before = (__u_int)rand() % ((begin + 1) + 1) + 0;
} while (before > 317);
instrustions[i + 1] = before;
original_page_address_flow[i + 1] = before / 10;
instrustions[i + 2] = before + 1;
original_page_address_flow[i + 2] = (before + 1) / 10;
__u_int after = (__u_int)rand() % (319 - (before + 2) + 1) + (before + 2);
instrustions[i + 3] = after;
original_page_address_flow[i + 3] = after / 10;
}
}
__u_int merge(__u_int* original_page_address_flow,__u_int* page_address_flow)
{
__u_int num_of_page_address_flow = 0;
for(size_t i = 0;i < NUM_OF_INSTRUSTIONS;++i) {
if(i == 0) {
page_address_flow[num_of_page_address_flow] = original_page_address_flow[i];
++num_of_page_address_flow;
}
else {
if(original_page_address_flow[i] != original_page_address_flow[i - 1]) {
page_address_flow[num_of_page_address_flow] = original_page_address_flow[i];
++num_of_page_address_flow;
}
}
}
return num_of_page_address_flow;
}
void print_current_state(__u_int* array,__u_int length)
{
for(__u_int i = 0;i < length;++i) {
printf("%d ",array[i]);
}
printf("\n");
}
void fifo_algorithm(__u_int num_of_blocks,__u_int* page_address_flow,__u_int num_of_page_address_flow)
{
assert(num_of_blocks);
__u_int num_of_interrupt = 0;
__u_int current_index = 0;
__u_int blocks[num_of_blocks];
memset((void*)blocks,-1,sizeof(blocks));
for(__u_int i = 0;i < num_of_page_address_flow;++i) {
printf("Current page address flow:%d\n",page_address_flow[i]);
int find = 0;
for(__u_int j = 0;j < num_of_blocks;++j) {
if(blocks[j] == page_address_flow[i]) {
find = 1;
break;
}
}
if(!find) {
++num_of_interrupt;
blocks[current_index] = page_address_flow[i];
current_index = (++current_index) % num_of_blocks;
print_current_state(blocks,num_of_blocks);
}
}
printf("Number of page missing interrupts:%d\n",num_of_interrupt);
float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow;
printf("Page falut rate:%f\n",page_fault_rate);
}
void opt_algorithm(__u_int num_of_blocks,__u_int* page_address_flow,__u_int num_of_page_address_flow)
{
assert(num_of_blocks);
__u_int num_of_interrupt = 0;
__u_int blocks[num_of_blocks];
memset((void*)blocks,-1,sizeof(blocks));
for(__u_int i = 0;i < num_of_page_address_flow;++i) {
printf("Current page address flow:%d\n",page_address_flow[i]);
int find = 0;
for(__u_int j = 0;j < num_of_blocks;++j) {
if(blocks[j] == page_address_flow[i]) {
find = 1;
break;
}
}
if(!find) {
++num_of_interrupt;
__u_int distance[num_of_blocks];
for(__u_int j = 0;j < num_of_blocks;++j) {
distance[j] = __UINT16_MAX__;
}
for(__u_int j = i + 1;j < num_of_page_address_flow;++j) {
for(__u_int n = 0;n < num_of_blocks;++n) {
if(page_address_flow[j] == blocks[n] && distance[n] > j) {
distance[n] = j;
break;
}
}
}
__u_int target_index = 0;
__u_int max_distance = distance[target_index];
for(__u_int j = 0;j < num_of_blocks;++j) {
if(distance[j] == __UINT16_MAX__) {
target_index = j;
break;
}
if(distance[j] > max_distance) {
target_index = j;
max_distance = distance[j];
}
}
blocks[target_index] = page_address_flow[i];
print_current_state(blocks,num_of_blocks);
}
}
printf("Number of page missing interrupts:%d\n",num_of_interrupt);
float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow;
printf("Page falut rate:%f\n",page_fault_rate);
}
void lru_algorithm(__u_int num_of_blocks,__u_int* page_address_flow,__u_int num_of_page_address_flow)
{
assert(num_of_blocks);
__u_int num_of_interrupt = 0;
__u_int blocks[num_of_blocks];
memset((void*)blocks,-1,sizeof(blocks));
int interval[num_of_blocks];
for(__u_int i = 0;i < num_of_blocks;++i)
interval[i] = __UINT16_MAX__;
for(__u_int i = 0;i < num_of_page_address_flow;++i) {
printf("Current page address flow:%d\n",page_address_flow[i]);
int find = 0;
for(__u_int j = 0;j < num_of_blocks;++j) {
if(page_address_flow[i] == blocks[j]) {
find = 1;
interval[j] = 0;
break;
}
}
if(!find) {
++num_of_interrupt;
__u_int target_index = 0;
__u_int max_interval = interval[target_index];
for(__u_int j = 0;j < num_of_blocks;++j) {
if(interval[j] > max_interval) {
target_index = j;
max_interval = interval[j];
}
}
blocks[target_index] = page_address_flow[i];
interval[target_index] = 0;
print_current_state(blocks,num_of_blocks);
}
for(__u_int j = 0;j < num_of_blocks;++j) {
if(interval[j] != __UINT16_MAX__)
++interval[j];
}
}
printf("Number of page missing interrupts:%d\n",num_of_interrupt);
float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow;
printf("Page falut rate:%f\n",page_fault_rate);
}
int main(void)
{
srand((unsigned int)time(NULL));
__u_int instrustions[NUM_OF_INSTRUSTIONS];
memset((void*)instrustions,0,sizeof(instrustions));
__u_int original_page_address_flow[NUM_OF_INSTRUSTIONS];
memset((void*)original_page_address_flow,0,sizeof(original_page_address_flow));
generate_instrustions(instrustions,original_page_address_flow);
__u_int page_address_flow[NUM_OF_INSTRUSTIONS];
memset((void*)page_address_flow,-1,sizeof(page_address_flow));
__u_int num_of_page_address_flow = merge(original_page_address_flow,page_address_flow);
printf("The number of page address flow:%d\n",num_of_page_address_flow);
__u_int num_of_blocks;
scanf("%d",&num_of_blocks);
fifo_algorithm(num_of_blocks,page_address_flow,num_of_page_address_flow);
opt_algorithm(num_of_blocks,page_address_flow,num_of_page_address_flow);
lru_algorithm(num_of_blocks,page_address_flow,num_of_page_address_flow);
return 0;
}
采用如下规则生成指令集：
A：50%的指令是顺序执行的
B：25%的指令是均匀分布在前地址部分
C：25%的指令是均匀分布在后地址部分
具体的实施方法是：
A：在[0，319]的指令地址之间随机选取一起点m
B：顺序执行一条指令，即执行地址为m+1的指令
C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
D：顺序执行一条指令，其地址为m’+1
E：在后地址[m’+2，319]中随机选取一条指令并执行
F：重复步骤A-E，直到320次指令
页面大小为1K，用户虚存容量为32K
（OPT算法应该写得过于冗余了，封装一个struct Page应该会更好