实验一
题目
![image]()
代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 进程控制块（PCB）结构体定义
// NAMF: 进程标识符（进程名）
// PRIO: 进程优先级
// CPUTIME: 进程累计占用CPU的时间片数
// NEEDTIME: 进程到完成还需要的时间片数
// STATE: 进程状态（R: 执行态, W: 就绪态, F: 完成态）
// NEXT: 链表指针，指向下一个PCB
typedef struct PCB {char NAMF[10]; // 进程名int PRIO; // 优先级int CPUTIME; // 已占用CPU时间int NEEDTIME; // 还需时间char STATE; // 进程状态struct PCB* NEXT; // 链表指针
} PCB;// 全局指针变量
PCB* RUN = NULL; // 当前运行进程指针
PCB* READY = NULL; // 就绪队列头指针
PCB* TAIL = NULL; // 就绪队列尾指针
PCB* FINISH = NULL; // 完成队列头指针// INSERT1函数：在优先数算法中，将尚未完成的PCB按优先数顺序插入到就绪队列中
// 参数p：待插入的进程控制块指针
void INSERT1(PCB* p) {PCB* q, *r;// 如果就绪队列为空，直接插入if (READY == NULL) {READY = p;TAIL = p;p->NEXT = NULL;} else {q = READY;r = NULL;// 按优先级从高到低排序插入（优先级数值越大越优先）while (q != NULL && q->PRIO >= p->PRIO) {r = q;q = q->NEXT;}// 插入到队列头部if (r == NULL) {p->NEXT = READY;READY = p;} else {// 插入到r和q之间p->NEXT = r->NEXT;r->NEXT = p;// 如果插入到队尾，更新TAIL指针if (q == NULL)TAIL = p;}}
}// INSERT2函数：在轮转法中，将执行了一个时间片单位的进程插到就绪队列的队尾
// 参数p：待插入的进程控制块指针
void INSERT2(PCB* p) {// 如果就绪队列为空，直接插入if (READY == NULL) {READY = p;TAIL = p;p->NEXT = NULL;} else {// 插入到队尾TAIL->NEXT = p;TAIL = p;p->NEXT = NULL;}
}// FIRSTIN函数：调度就绪队列的第一个进程投入运行
void FIRSTIN() {if (READY != NULL) {RUN = READY; // 将就绪队列头进程设为运行进程READY = READY->NEXT; // 更新就绪队列头指针RUN->NEXT = NULL; // 运行进程指针置空RUN->STATE = 'R'; // 设置状态为执行态}
}// PRINT函数：显示每执行一次后所有进程的状态及有关信息
// 显示顺序：执行态(R) -> 就绪态(W) -> 完成态(F)
void PRINT() {PCB* p;// 打印表头printf("进程名 已用时间 剩余时间 优先级 状态\n");printf("------------------------------------------------\n");// 先显示执行态进程if (RUN != NULL)printf("%-8s%-11d%-12d%-12d%c\n", RUN->NAMF, RUN->CPUTIME, RUN->NEEDTIME, RUN->PRIO, RUN->STATE);// 再显示就绪态进程p = READY;while (p != NULL) {printf("%-8s%-11d%-12d%-12d%c\n", p->NAMF, p->CPUTIME, p->NEEDTIME, p->PRIO, p->STATE);p = p->NEXT;}// 最后显示完成态进程p = FINISH;while (p != NULL) {printf("%-8s%-11d%-12d%-12d%c\n", p->NAMF, p->CPUTIME, p->NEEDTIME, p->PRIO, p->STATE);p = p->NEXT;}printf("\n");
}// CREATE函数：创建新进程，并将它的PCB插入就绪队列
// 参数name：进程名
// 参数needtime：进程需要的时间片数
// 参数algo：算法选择（1: 优先数算法, 2: 轮转算法）
void CREATE(char* name, int needtime, int algo) {PCB* p;// 分配PCB内存p = (PCB*)malloc(sizeof(PCB));strcpy(p->NAMF, name); // 设置进程名p->CPUTIME = 0; // 初始化已用时间为0p->NEEDTIME = needtime; // 设置需要的时间片数p->STATE = 'W'; // 初始状态为就绪态// 优先数算法：优先级 = 50 - NEEDTIME// 轮转算法：优先级设为0（不使用）if (algo == 1) {p->PRIO = 50 - needtime;} else {p->PRIO = 0;}p->NEXT = NULL;// 根据算法选择插入方式if (algo == 1)INSERT1(p);elseINSERT2(p);
}// PRISCH函数：按优先数算法调度进程
// 规则：每执行一次，优先数减1，CPU时间片数加1，剩余时间片数减1
void PRISCH() {int flag = 1;while (flag) {if (READY != NULL) {FIRSTIN(); // 调度就绪队列第一个进程RUN->PRIO--; // 优先级减1RUN->CPUTIME++; // CPU时间加1RUN->NEEDTIME--; // 剩余时间减1// 如果进程完成if (RUN->NEEDTIME == 0) {RUN->STATE = 'F'; // 设置为完成态RUN->NEXT = FINISH; // 插入完成队列FINISH = RUN;RUN = NULL;} else {RUN->STATE = 'W'; // 设置为就绪态INSERT1(RUN); // 按优先级插入就绪队列RUN = NULL;}PRINT(); // 打印当前状态} else {flag = 0; // 就绪队列为空，调度结束}}
}// ROUNDSCH函数：按时间片轮转法调度进程
// 规则：采用固定时间片单位（2个时间片为一个单位），每轮转一次CPU时间加2，剩余时间减2
void ROUNDSCH() {int flag = 1;int time;while (flag) {if (READY != NULL) {FIRSTIN(); // 调度就绪队列第一个进程// 确定本次执行的时间片数（最多2个）time = (RUN->NEEDTIME >= 2) ? 2 : RUN->NEEDTIME;RUN->CPUTIME += time; // CPU时间增加RUN->NEEDTIME -= time; // 剩余时间减少// 如果进程完成if (RUN->NEEDTIME == 0) {RUN->STATE = 'F'; // 设置为完成态RUN->NEXT = FINISH; // 插入完成队列FINISH = RUN;RUN = NULL;} else {RUN->STATE = 'W'; // 设置为就绪态INSERT2(RUN); // 插入就绪队列尾RUN = NULL;}PRINT(); // 打印当前状态} else {flag = 0; // 就绪队列为空，调度结束}}
}// 主函数：程序入口
int main() {int algo, i, needtime;char name[10];// 提示用户选择调度算法printf("===== 进程调度模拟程序 =====\n");printf("请选择调度算法：\n");printf("1. 优先数调度算法\n");printf("2. 时间片轮转调度算法\n");printf("请输入选择（1或2）：");scanf("%d", &algo);// 输入5个进程信息printf("\n请输入5个进程的名称和所需时间片数：\n");for (i = 0; i < 5; i++) {printf("进程 %d 名称: ", i + 1);scanf("%s", name);printf("进程 %d 需要时间片数: ", i + 1);scanf("%d", &needtime);CREATE(name, needtime, algo);}// 显示初始状态printf("\n=== 初始状态 ===\n");PRINT();// 开始调度printf("=== 开始调度 ===\n\n");if (algo == 1) {PRISCH(); // 优先数调度} else {ROUNDSCH(); // 时间片轮转调度}printf("=== 调度完成！ ===\n");return 0;
}
实验二
题目
![image]()
代码
/** 存储管理动态分区分配及回收算法模拟程序* 实验二：存储管理* 实现内容：* 1. First Fit 算法 - 首次适应算法* 2. Best Fit 算法 - 最佳适应算法* 3. 空闲区回收算法（支持相邻空闲区合并）*/#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>// 分区描述器结构体定义
typedef struct node {int adr; // 分区首地址int size; // 分区大小struct node *next; // 指向下一个分区的指针
} node;// 全局指针变量
node *head1 = NULL; // 空闲区队列首指针
node *back1 = NULL; // 指向释放区 node 结构的指针（预留）
node *assign = NULL; // 指向申请的内存分区 node 结构的指针（预留）
int free_size; // 用户申请存储区的大小/*** 打印空闲区队列* 输出格式：编号、首址、终止地址、大小*/
void print() {node *p = head1;int count = 1;printf("\n空闲区队列：\n");printf("编号\t首址\t终止\t大小\n");while (p != NULL) {// 终止地址 = 首地址 + 大小 - 1printf("%d\t%d\t%d\t%d\n", count, p->adr, p->adr + p->size - 1, p->size);p = p->next;count++;}printf("\n");
}/*** 检查指定的释放块的合法性* @param adr: 释放块首地址* @param size: 释放块大小* @return: 1-合法，0-不合法*/
int check(int adr, int size) {node *p = head1;while (p != NULL) {if (p->adr == adr && p->size == size) {return 1; // 找到匹配的空闲区，合法}p = p->next;}return 0; // 未找到匹配的空闲区，不合法
}/*** First Fit 分配算法* 从空闲区链表头开始查找，找到第一个大小足够的空闲区进行分配*/
void assignment1() {node *p, *q;p = head1; // p 指向当前检查的空闲区q = NULL; // q 指向 p 的前驱节点// 遍历空闲区链表，寻找第一个足够大的空闲区while (p != NULL) {if (p->size >= free_size) {break; // 找到合适的空闲区}q = p;p = p->next;}// 未找到足够大的空闲区if (p == NULL) {printf("没有足够的空闲区！\n");return;}// 分配处理if (p->size == free_size) {// 空闲区大小恰好等于申请大小，直接删除该节点if (q == NULL) {head1 = p->next; // 头节点特殊处理} else {q->next = p->next;}free(p);} else {// 空闲区大于申请大小，分割空闲区p->adr += free_size;p->size -= free_size;}printf("分配成功！\n");print();
}/*** Best Fit 分配算法* 遍历所有空闲区，找到最小的但足够大的空闲区进行分配*/
void assignment2() {node *p, *q, *best, *best_prev;int min_size;p = head1; // p 指向当前检查的空闲区q = NULL; // q 指向 p 的前驱节点best = NULL; // best 指向最佳空闲区best_prev = NULL; // best_prev 指向最佳空闲区的前驱min_size = 32768; // 初始化为最大内存容量+1// 遍历空闲区链表，寻找最佳空闲区while (p != NULL) {if (p->size >= free_size && p->size < min_size) {min_size = p->size;best = p;best_prev = q;}q = p;p = p->next;}// 未找到足够大的空闲区if (best == NULL) {printf("没有足够的空闲区！\n");return;}// 分配处理if (best->size == free_size) {// 空闲区大小恰好等于申请大小，直接删除该节点if (best_prev == NULL) {head1 = best->next; // 头节点特殊处理} else {best_prev->next = best->next;}free(best);} else {// 空闲区大于申请大小，分割空闲区p->adr += free_size;best->size -= free_size;}printf("分配成功！\n");print();
}/*** First Fit 回收算法* 将释放区插入到空闲区链表的适当位置，并合并相邻的空闲区* 空闲区按地址顺序排列* @param adr: 释放区首地址* @param size: 释放区大小*/
void acceptment1(int adr, int size) {node *p, *q, *new_node;// 创建新的空闲区节点new_node = (node *)malloc(sizeof(node));new_node->adr = adr;new_node->size = size;new_node->next = NULL;// 如果空闲区链表为空if (head1 == NULL) {head1 = new_node;} else {p = head1;q = NULL;// 找到合适的插入位置（按地址顺序）while (p != NULL && p->adr < adr) {q = p;p = p->next;}// 检查是否可以与前一个空闲区合并if (q != NULL && q->adr + q->size == adr) {q->size += size;free(new_node);new_node = q;// 检查是否可以与后一个空闲区合并if (p != NULL && new_node->adr + new_node->size == p->adr) {new_node->size += p->size;new_node->next = p->next;free(p);}}// 检查是否可以与后一个空闲区合并else if (p != NULL && adr + size == p->adr) {p->adr = adr;p->size += size;free(new_node);}// 无法合并，直接插入else {new_node->next = p;if (q == NULL) {head1 = new_node; // 插入到链表头部} else {q->next = new_node;}}}printf("回收成功！\n");print();
}/*** Best Fit 回收算法* 将释放区插入到空闲区链表，并合并相邻的空闲区* 空闲区按大小顺序排列（从小到大）* @param adr: 释放区首地址* @param size: 释放区大小*/
void acceptment2(int adr, int size) {node *p, *q, *new_node;// 创建新的空闲区节点new_node = (node *)malloc(sizeof(node));new_node->adr = adr;new_node->size = size;new_node->next = NULL;// 如果空闲区链表为空if (head1 == NULL) {head1 = new_node;} else {p = head1;q = NULL;// 找到合适的插入位置（按地址顺序，便于合并）while (p != NULL && p->adr < adr) {q = p;p = p->next;}// 检查是否可以与前一个空闲区合并if (q != NULL && q->adr + q->size == adr) {q->size += size;free(new_node);new_node = q;// 检查是否可以与后一个空闲区合并if (p != NULL && new_node->adr + new_node->size == p->adr) {new_node->size += p->size;new_node->next = p->next;free(p);}}// 检查是否可以与后一个空闲区合并else if (p != NULL && adr + size == p->adr) {p->adr = adr;p->size += size;free(new_node);}// 无法合并，直接插入else {new_node->next = p;if (q == NULL) {head1 = new_node;} else {q->next = new_node;}}// Best Fit 需要按大小排序（选择排序）p = head1;q = NULL;while (p != NULL) {node *r = p;node *r_prev = q;node *min_p = p;node *min_prev = q;// 找到最小的空闲区while (r != NULL) {if (r->size < min_p->size) {min_p = r;min_prev = r_prev;}r_prev = r;r = r->next;}// 如果最小节点不是当前节点，交换位置if (min_p != p) {if (q == NULL) {head1 = min_p;} else {q->next = min_p;}if (min_prev != NULL) {min_prev->next = min_p->next;}min_p->next = p;}q = min_p;p = min_p->next;}}printf("回收成功！\n");print();
}/*** 主函数* 程序入口，初始化空闲区并提供用户交互界面*/
int main() {int choice, algo, adr, size;// 初始化空闲区：首址为0，大小为32767head1 = (node *)malloc(sizeof(node));head1->adr = 0;head1->size = 32767;head1->next = NULL;// 显示初始空闲区printf("初始空闲区：\n");print();// 选择分配算法printf("请选择分配算法：\n");printf("1. First Fit Algorithm\n");printf("2. Best Fit Algorithm\n");scanf("%d", &algo);// 主循环：处理用户操作while (1) {printf("\n请选择操作：\n");printf("1. 分配内存\n");printf("2. 回收内存\n");printf("3. 退出\n");scanf("%d", &choice);// 退出程序if (choice == 3) {break;}// 分配内存if (choice == 1) {printf("请输入申请区的大小：");scanf("%d", &free_size);if (algo == 1) {assignment1(); // 使用 First Fit} else {assignment2(); // 使用 Best Fit}}// 回收内存else if (choice == 2) {printf("请输入释放区的首址：");scanf("%d", &adr);printf("请输入释放区的大小：");scanf("%d", &size);if (algo == 1) {acceptment1(adr, size); // 使用 First Fit 回收算法} else {acceptment2(adr, size); // 使用 Best Fit 回收算法}}}return 0;
}
