#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:%dn",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:%dn",num_of_interrupt); float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow; printf("Page falut rate:%fn",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:%dn",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:%dn",num_of_interrupt); float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow; printf("Page falut rate:%fn",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:%dn",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:%dn",num_of_interrupt); float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow; printf("Page falut rate:%fn",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:%dn",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应该会更好
