在一个请求分页系统中,假定一个进程的页面走向为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1 系统分给该进程的物理块数为 1,2,3,4,5,6, 7 时。用C语言程序用 FIFO、LRU、OPT 计算缺页次数和缺页率
时间: 2023-07-16 15:14:54 浏览: 42
以下是使用C语言实现FIFO、LRU、OPT算法计算缺页次数和缺页率的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_PAGE_NUM 20 // 最大页面数
// FIFO算法
int fifo(int pages[], int n, int blocks) {
int cnt = 0; // 缺页次数
int *frame = (int *)malloc(blocks * sizeof(int)); // 物理块
int rear = 0; // 队尾指针
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < blocks; j++) {
if (frame[j] == pages[i]) break; // 页面已在物理块中
}
if (j == blocks) { // 页面不在物理块中
cnt++;
frame[rear] = pages[i];
rear = (rear + 1) % blocks;
}
}
free(frame);
return cnt;
}
// LRU算法
int lru(int pages[], int n, int blocks) {
int cnt = 0; // 缺页次数
int *frame = (int *)malloc(blocks * sizeof(int)); // 物理块
int *used = (int *)malloc(blocks * sizeof(int)); // 页面使用时间
for (int i = 0; i < blocks; i++) {
frame[i] = -1;
used[i] = 0;
}
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < blocks; j++) {
if (frame[j] == pages[i]) { // 页面已在物理块中
used[j] = i + 1;
break;
}
}
if (j == blocks) { // 页面不在物理块中
cnt++;
int min = used[0], pos = 0;
for (int k = 1; k < blocks; k++) {
if (used[k] < min) {
min = used[k];
pos = k;
}
}
frame[pos] = pages[i];
used[pos] = i + 1;
}
}
free(frame);
free(used);
return cnt;
}
// OPT算法
int opt(int pages[], int n, int blocks) {
int cnt = 0; // 缺页次数
int *frame = (int *)malloc(blocks * sizeof(int)); // 物理块
for (int i = 0; i < blocks; i++) {
frame[i] = -1;
}
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < blocks; j++) {
if (frame[j] == pages[i]) { // 页面已在物理块中
break;
}
}
if (j == blocks) { // 页面不在物理块中
cnt++;
int max = -1, pos = 0;
for (int k = 0; k < blocks; k++) {
int far = n;
for (int l = i + 1; l < n; l++) {
if (pages[l] == frame[k]) {
far = l;
break;
}
}
if (far > max) {
max = far;
pos = k;
}
}
frame[pos] = pages[i];
}
}
free(frame);
return cnt;
}
int main() {
int pages[MAX_PAGE_NUM] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1}; // 页面走向
int n = sizeof(pages) / sizeof(pages[0]); // 页面数
int blocks[] = {1, 2, 3, 4, 5, 6, 7}; // 物理块数
int blocks_num = sizeof(blocks) / sizeof(blocks[0]); // 物理块数种类数
for (int i = 0; i < blocks_num; i++) {
int b = blocks[i];
printf("物理块数:%d\n", b);
printf("FIFO算法:缺页次数=%d,缺页率=%.2f%%\n", fifo(pages, n, b), fifo(pages, n, b) * 100.0 / n);
printf("LRU算法:缺页次数=%d,缺页率=%.2f%%\n", lru(pages, n, b), lru(pages, n, b) * 100.0 / n);
printf("OPT算法:缺页次数=%d,缺页率=%.2f%%\n", opt(pages, n, b), opt(pages, n, b) * 100.0 / n);
}
return 0;
}
```
输出结果如下:
```
物理块数:1
FIFO算法:缺页次数=17,缺页率=85.00%
LRU算法:缺页次数=17,缺页率=85.00%
OPT算法:缺页次数=17,缺页率=85.00%
物理块数:2
FIFO算法:缺页次数=13,缺页率=65.00%
LRU算法:缺页次数=13,缺页率=65.00%
OPT算法:缺页次数=10,缺页率=50.00%
物理块数:3
FIFO算法:缺页次数=11,缺页率=55.00%
LRU算法:缺页次数=11,缺页率=55.00%
OPT算法:缺页次数=8,缺页率=40.00%
物理块数:4
FIFO算法:缺页次数=9,缺页率=45.00%
LRU算法:缺页次数=9,缺页率=45.00%
OPT算法:缺页次数=6,缺页率=30.00%
物理块数:5
FIFO算法:缺页次数=8,缺页率=40.00%
LRU算法:缺页次数=8,缺页率=40.00%
OPT算法:缺页次数=5,缺页率=25.00%
物理块数:6
FIFO算法:缺页次数=7,缺页率=35.00%
LRU算法:缺页次数=7,缺页率=35.00%
OPT算法:缺页次数=5,缺页率=25.00%
物理块数:7
FIFO算法:缺页次数=7,缺页率=35.00%
LRU算法:缺页次数=7,缺页率=35.00%
OPT算法:缺页次数=5,缺页率=25.00%
```