Operating System 实验二 内存管理实验

目录

实验目标：

实验设备：

实验内容：

（1）验证FIFO和Stack LRU页面置换算法

【代码（注释率不低于30%）】

【实验过程（截图）】

【结论】

（2）分别用FIFO和Stack LRU页置换算法，自己设定一个页面引用序列，绘制页错误次数和可用页帧总数的曲线并对比（可用Excel绘制或手绘）；能否重现FIFO导致的Belady异常；

【代码】

【过程】

【结论】

（3）[选做]编程实现最优页置换算法，用课件上的序列验证

【代码】

【过程】

【结论】

Linux环境下尝试过程：（成功！）

1、使用winscp 将文件从windows文件夹复制到linux文件夹。

2、安装cmake和vi

3、练习vi使用

4、Cmake使用

---

本栏目不存在实验一

实验目标：

1. 熟悉linux下C程序的编译和链接；熟悉CMake工具使用；
2. 熟悉命令行方式下，用vi修改源代码文件
3. 编写程序验证FIFO和Stack LRU页面置换算法
4. 分别用FIFO和Stack LRU页置换算法，自己设定一个页面引用序列，绘制页错误次数和可用页帧总数的曲线并对比（可用Excel绘制或手绘）；能否重现FIFO导致的Belady异常；
5. [选做]编程实现最优页置换算法，用课件上的序列验证。

实验设备：

1. 硬件：微机，hyper-V虚拟化平台或者远程linux终端
2. 软件：cmake，demo代码

实验内容：

（1）验证FIFO和Stack LRU页面置换算法

【代码（注释率不低于30%）】

Main.c

//模拟了两种经典的页面置换算法：先进先出（FIFO） 和 最近最少使用（LRU）
#include <stdio.h>
#include "queue.h"
#include "stack.h"int test_fifo(int frameCount, int reference[], int totalCount) {//模拟 FIFO 页面置换算法。int i, victim;int errCount = 0;// 用于统计页面错误的次数queue_init(frameCount);//初始化一个队列，队列大小为 frameCount，表示内存中的页框数量。for (i = 0; i < totalCount; i++) {printf("-------------------------------\n");int page = reference[i];// 当前引用的页面int index = queue_find(page);// 在队列中查找当前页面，返回索引if (index >= 0) {// 有映射的页帧，成功printf("page OK!\n");continue;// 跳过当前循环，处理下一个页面}// 发生了页错误errCount++;printf("page fault: ");if (!queue_is_full()) {// 队列未满，有可用页帧，载入新页queue_push(page);printf(" load for page: %d\n", page);} else {// 没有可用页帧，选择一个牺牲帧(出队一个最早的页)victim = queue_pop();//移除最早进入的printf("swap out %d, ", victim);queue_push(page);//加入新页面printf("swap in %d\n", page);}queue_print();//打印队列当前状态}return errCount; // 返回页面错误的总次数}int test_lru_stack(int frameCount, int reference[], int totalCount) {//模拟 LRU 页面置换算法。选择最久未使用的页面作为牺牲页面。int i, victim;int errCount = 0;stack_init(frameCount);// 初始化栈，设置栈大小为 frameCountfor (i = 0; i < totalCount; i++) {printf("-------------------------------\n");int page = reference[i];//引用当前int index = stack_find(page);//栈中查找if (index >= 0) {// 有映射的页帧，成功；将该页移动到栈顶stack_move_to_top(index);printf("page OK!\n");continue;}// 发生了页错误errCount++;printf("page fault: ");if (!stack_is_full()) {// 有可用页帧，载入新页stack_push(page);printf(" load for page: %d\n", page);} else {// 没有可用页帧，从栈底选择一个LRU牺牲帧victim = stack_pop_bottom();printf("swap out %d, ", victim);stack_push(page);// 将新页面压入栈printf("swap in %d\n", page);}stack_print();}return errCount;
}int main() {//程序入口，定义页面引用序列并调用测试函数int reference[] = {//ppt示例7, 0, 1, 2, 0,3, 0, 4, 2, 3,0, 3, 2, 1, 2,0, 1, 7, 0, 1};int totalCount = sizeof(reference) / sizeof(int);// 计算引用序列的长度int errCount;int frameCount = 3;// // 设置内存页框数量为 3errCount = test_fifo(frameCount, reference, totalCount);// 调用 FIFO 算法 预计701（LRU为107）printf("FIFO: frames:%d total: %d,  error: %d, error rate: %.0f%%\n", frameCount, totalCount, errCount,100.0 * errCount / totalCount);return 0;
}

Queue.h

#ifndef MYC_QUEUE_H
#define MYC_QUEUE_Hvoid queue_init(int capacity);int queue_push(int number);int queue_pop();int queue_find(int value);void queue_print();void stack_print();int queue_is_full();#endif //MYC_QUEUE_H

Queue.c

/*queue_ init()初始化队列，分配内存并设置队列的容量
queue push()向队列中添加一个元素。
queue_pop()从队列中移除一个元素。
queue_find()在队列中查找一个元素
queue is fu11():判断队列是否已满。
queue_size():返回队列中元素的数量,
queue_print():打印队列的当前状态*/
#include <stdio.h>
#include <stdlib.h>static int *g_data = NULL;  // 指向队列数据的指针
static int g_capacity = 0;  // 队列的最大容量
static int rear = 0;        // 队尾指针
static int front = 0;       // 队头指针
static int is_full = 0;     // 标志队列是否已满
void queue_init(int capacity) {int i;if (g_data) free(g_data);  // 如果队列已初始化，释放原有内存g_capacity = capacity;     // 设置队列容量g_data = (int *)malloc(g_capacity * sizeof(int));  // 分配内存front = rear = 0;          // 初始化队头和队尾指针is_full = 0;               // 初始化队列为空for (i = 0; i < g_capacity; i++) {g_data[i] = -1;        // 初始化队列数据为 -1（表示空位）}
}
int queue_push(int number) {if (is_full) {// 如果队列已满，返回 -1 表示失败return -1;}g_data[rear] = number;     // 将元素添加到队尾rear = (rear + 1) % g_capacity;  // 更新队尾指针（循环队列的关键）if (rear % g_capacity == front) {// 如果队尾指针追上队头指针，队列已满is_full = 1;}return 0;  // 成功返回 0
}
int queue_is_full() {return is_full;
}int queue_size() {//计算队列中当前的元素数量。return (rear - front + g_capacity) % g_capacity;
}int queue_pop() {int i;if (!is_full) {// 队空return -1;}is_full = 0;int value = g_data[front];  // 获取队头元素g_data[front] = -1;         // 将队头位置标记为空front = (front + 1) % g_capacity;  // 更新队头指针return value;  // 返回移除的元素
}int queue_find(int value) {int i;for (i = 0; i < g_capacity; i++) {if (g_data[i] == value)return i;// 找到元素，返回其索引}return -1;
}void queue_print() {int i;for (i = 0; i < g_capacity; i++) {if (g_data[i] < 0)printf("- ");// 空位打印 `-`else printf("%d ", g_data[i]);    // 打印队列中的元素}printf("\n");
}

stack.h

#ifndef MYC_STACK_H
#define MYC_STACK_Hvoid stack_init(int capacity);int stack_push(int number);int stack_pop();int stack_find(int value);int stack_move_to_top(int index);int stack_pop_bottom();int stack_is_full();#endif //MYC_STACK_H

stack.c

#include <stdlib.h>
#include <stdio.h>static int *g_data = NULL;  // 指向栈数据的指针
static int g_capacity = 0;  // 栈的最大容量
static int g_size = 0;      // 栈中当前元素的数量void stack_init(int capacity) {int i;if (g_data) free(g_data);  // 如果栈已初始化，释放原有内存g_data = (int *)malloc(capacity * sizeof(int));  // 分配内存g_capacity = capacity;  // 设置栈的容量g_size = 0;  // 初始化栈为空for (i = 0; i < g_capacity; i++) {g_data[i] = -1;  // 初始化栈数据为 -1（表示空位）}
}
int stack_push(int number) {if (g_size >= g_capacity) {// 如果栈已满，返回 -1 表示失败return -1;}g_data[g_size] = number;  // 将元素添加到栈顶return g_size++;  // 更新栈的大小