2022年北京工业大学操作系统课设报告 .pdf

操作系统课程设计学号 110703xx 姓名 xxx 指导教师金雪云2014年 1 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 28 页 - - - - - - - - - 一、 报告摘要报告实现了三次实验的全部要求，均以流程图和源代码的形式做了展示，并附上了实验结果图。二、 关键词进程调度，空间分配，磁盘调度，流程图。三、 引言本次实验我选择的是完成实验六、实验七和实验九三个任务。四、实验六 . 进程调度4.1 设计目的：（1）要求学生设计并实现一个模拟进程调度的算法（时间片轮转及先来先服务）。（2）理解进程控制块的结构。（3）理解进程运行的并发性。（4）掌握进程调度算法。4.2 设计要求：（1）实现时间片轮转算法完成进程的调度。（2）实现先来先服务算法完成进程的调度。4.3 详细设计：4.3.1 数据结构设计及变量说明进程控制块：typedef struct node char name10;/进程标识符 int round_num;/进程时间轮转时间片 int cputime;/进程占用 cpu 时间 int needtime;/还需的时间 int count;/计数器 char state;/进程状态 struct node* next;/指向链表下一个节点PCB;/ 进程控制块变量说明：PCB *ready_head, *finish_head, *ready_ptr, *finish_ptr, *ready_rear, *finish_rear;/就绪队列头指针，尾指针，操作指针和完结队列的头指针，尾指针，操作指针 int process_num = 0;/进程数 int reamin_num;/剩余进程数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 28 页 - - - - - - - - - int choose;/算法选择 1 时间片轮转 2. 先来先服务43.2 时间片轮转算法接收进程数接收各进程名称及运行时间构造 ready链表取头指针表头需要时间0输出调度信息需要时间 =01.表尾 = 表头；2.表头 = 表头 -next;插入finish链表表尾结束Needtime-1ynn表头 = 表头 -next结果演示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 28 页 - - - - - - - - - 4.3.3 先来先服务算法接收进程数接收各进程名称及运行时间构造 ready链表表头需要时间0取头指针输出调度信息需要时间 =0插入finish链表表尾结束Needtime-1ynn表头 = 表头 -next名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 28 页 - - - - - - - - - 结果演示：4,3,4 实验源码：#include #include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 28 页 - - - - - - - - - typedef struct node char name10;/进程标识符 int prio;/进程优先数 int round_num;/进程时间轮转时间片 int cputime;/进程占用 cpu 时间 int needtime;/还需的时间 int count;/计数器 char state;/进程状态 struct node* next; PCB; void InitPCB(PCB* pcb) strcpy(pcb-name, none); pcb-prio = 1000; pcb-round_num = 0; pcb-cputime = 0; pcb-needtime = 0; pcb-count = 0; pcb-state = W; pcb-next = NULL; void main() PCB *ready_head, *finish_head, *ready_ptr, *finish_ptr, *ready_rear, *finish_rear;/就绪队列头指针，尾指针，操作指针和完结队列的头指针，尾指针，操作指针 int process_num = 0;/进程数 int reamin_num;/剩余进程数 int choose;/算法选择 1 时间片轮转 2. 先来先服务 while (1) printf(请选择调度算法：n); printf(1. 时间片轮转法 2.先来先服务算法 0. 退出 n); scanf(%d, &choose); if (0 = choose) return; if (1 = choose) printf(请输入进程数：n); scanf(%d, &process_num); reamin_num = process_num;/初始化剩余进程数为进程数 for (int i = 0; i next = ready_head;/首尾相连 InitPCB(ready_head); scanf(%s%d, ready_head-name, &ready_head-needtime); else ready_ptr = (PCB *)malloc(sizeof(PCB); InitPCB(ready_ptr); scanf(%s%d, ready_ptr-name, &ready_ptr-needtime); ready_rear-next = ready_ptr; ready_ptr-next = ready_head; ready_rear = ready_rear-next; finish_head = NULL;/初始化为空 while (ready_head-needtime 0) printf(=新一轮调度初态=n); printf(进程名 tcpu时间 t所需时间 t状态 n); ready_ptr = ready_head;/ptr用来保留原有head 信息，用于输出链表 finish_ptr = finish_head;/ptr用来保留原有head 信息，用于输出链表 ready_head-state = R;/就绪队列头设置为运行 for (int i = reamin_num; i 0; i-) /输出所有剩余节点信息 printf(%st%dt%dt%cn, ready_ptr-name, ready_ptr-cputime, ready_ptr-needtime, ready_ptr-state); ready_ptr = ready_ptr-next; while (finish_ptr != NULL) /输出调度结束节点的信息 printf(%st%dt%dt%cn, finish_ptr-name, finish_ptr-cputime, finish_ptr-needtime, finish_ptr-state); finish_ptr = finish_ptr-next; /getch(); ready_ptr = ready_head;/ptr用来保留原有head 信息，用于释放空间 ready_head-cputime+;/所用时间增加 ready_head-needtime-;/需要时间减1 ready_head-state = W;/调度结束，还原就绪态 if (0 = ready_head-needtime) /如果不再需要时间且为队头 ready_head = ready_head-next;/循环链表的移动 ready_rear-next = ready_head; ready_ptr-next = NULL;/断开连接 ready_ptr-state = F; if (reamin_num = process_num) /头一个进入finish队列的 finish_rear = finish_head = ready_ptr; else finish_rear-next = ready_ptr; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 28 页 - - - - - - - - - finish_rear = ready_ptr; reamin_num-; else /如果没有做完则移动到队尾，下一个作业变为队头 ready_rear = ready_head; ready_head = ready_head-next; finish_ptr = finish_head;/ptr用来保留原有head 信息，用于输出链表 printf(=调度结束 =n); while (finish_ptr != NULL) /输出调度结束节点的信息 printf(%st%dt%dt%cn, finish_ptr-name, finish_ptr-cputime, finish_ptr-needtime, finish_ptr-state); finish_ptr = finish_ptr-next; if (2 = choose) printf(请输入进程数：n); scanf(%d, &process_num); reamin_num = process_num;/初始化剩余进程数为进程数 for (int i = 0; i name, &ready_head-needtime); else ready_rear-next = (PCB *)malloc(sizeof(PCB); InitPCB(ready_rear-next); scanf(%s%d, ready_rear-next-name, &ready_rear-next-needtime); ready_rear = ready_rear-next; finish_head = NULL;/初始化为空 while (reamin_num 0) printf(=新一轮调度初态=n); printf(进程名 tcpu时间 t所需时间 t状态 n); ready_ptr = ready_head;/ptr用来保留原有head 信息，用于释放空间 finish_ptr = finish_head; ready_head-state = R;/就绪队列头设置为运行 for (int i = reamin_num; i 0; i-) /输出所有剩余节点信息 printf(%st%dt%dt%cn, ready_ptr-name, ready_ptr-cputime, ready_ptr-needtime, ready_ptr-state); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 28 页 - - - - - - - - - ready_ptr = ready_ptr-next; while (finish_ptr != NULL) /输出调度结束节点的信息 printf(%st%dt%dt%cn, finish_ptr-name, finish_ptr-cputime, finish_ptr-needtime, finish_ptr-state); finish_ptr = finish_ptr-next; ready_ptr = ready_head;/ptr用来保留原有head 信息，用于释放空间 ready_head-cputime+;/已用时间加1 ready_head-needtime-;/需要时间减一 /ready_head-state = W;/调度结束，还原就绪态 if (0 = ready_head-needtime) /如果不再需要时间 ready_head = ready_head-next; ready_rear-next = ready_head; ready_ptr-next = NULL;/断开连接 ready_ptr-state = F; if (reamin_num = process_num) /头一个进入finish队列的 finish_rear = finish_head = ready_ptr; else finish_rear-next = ready_ptr; finish_rear = ready_ptr; reamin_num-; finish_ptr = finish_head;/ptr用来保留原有head 信息，用于输出链表 printf(=调度结束 =n); while (finish_ptr != NULL) /输出调度结束节点的信息 printf(%st%dt%dt%cn, finish_ptr-name, finish_ptr-cputime, finish_ptr-needtime, finish_ptr-state); finish_ptr = finish_ptr-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 28 页 - - - - - - - - - 五、实验七 . 主存空间的分配与回收5.1 设计目的：主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机系统的性能。主存分配是指在多道作业和多进程环境下，如何共享主存空间。主存回收是指当作业执行完毕或进程运行结束后将主存空间归还给系统。主存分配与回收的实现是与主存储器的管理方式有关。本次设计主要是为了帮助学生深入理解主存空间的分配与回收的几种算法。（1） 掌握最先适应分配算法（2） 掌握最优适应分配算法（3） 掌握最坏适应分配算法5.2 设计要求：（1） 设计一个内存分配回收的程序使用最先适应分配算法（2） 设计一个内存分配回收的程序使用最优适应分配算法（3） 设计一个内存分配回收的程序使用最坏适应分配算法用户提出内存空间请求，系统根据申请者要求，选择上述算法的一种分配策略分析内存空间的使用情况，找出合适的空闲区，分给申请者，当进程执行完毕时，系统收回它所占用的内存空间。5.3 详细设计：5.3.1 数据结构设计及变量说明typedef struct node int start;/区块起始地址 int length;/区块长度 char tag20;/区块标识 struct node* next;/下一区块JOB;/区块变量说明int count_select_3 = 0; /记录“显示空闲表和分配表”选项被使用的次数 int job_num = 0; /初始化区块数为0 char input_file_name30;/文件名 char job_name10;/用户输入的作业名 int length;/作业长 int select;/保存用户的命令选择，共有03 四个选项 JOB* job_start, *job_ptr, *job_rear, *job_ptr1, *job_use_start, *job_use_rear, *job_use_ptr, *job_use_ptr1, *job_use_temp; FILE* fp;/文件指针名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 28 页 - - - - - - - - - 5.3.2 最先适应分配算法开始从文件接收初始化区块信息，构建区块链表接收用户操作接收作业名及长度接收要删除的作业名显示当前所有区块信息空闲区表中还有结点取头指针123已分配表还有结点取头指针名字相同Y删除并加入空闲区合并YN&指针后移N更新适配差值Y指针后移取求得最小差值的块进行分配N结果展示：分配：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 28 页 - - - - - - - - - 删除：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 28 页 - - - - - - - - - 5.3.3 最优适应分配算法开始从文件接收初始化区块信息，构建区块链表接收用户操作接收作业名及长度接收要删除的作业名显示当前所有区块信息空闲区表中还有结点取头指针123已分配表还有结点取头指针名字相同删除并加入空闲区合并YN&指针后移N更新适配差值Y指针后移取求得最小差值的块进行分配N结果展示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 28 页 - - - - - - - - - 5.3.4 最差适应分配算法开始从文件接收初始化区块信息，构建区块链表接收用户操作接收作业名及长度接收要删除的作业名显示当前所有区块信息空闲区表中还有结点取头指针123已分配表还有结点取头指针名字相同Y删除并加入空闲区合并YN& 指针后移N更新空闲区表最大值Y指针后移取最大块进行分配N结果展示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 28 页 - - - - - - - - - 5.3.5 实验源码（源码较长，只截取了第一个实验的部分）#include #include #include #define MEMORY_NUM 6 / 定义初始可分配区块数为MEMORY_NUM 个typedef struct node int start; int length; char tag20; struct node* next; JOB; void InitJOB(JOB* job) job-start = 0; job-length = 0; strcpy(job-tag, free); job-next = NULL; void main() int count_select_3 = 0; / 记录“显示空闲表和分配表”选项被使用的次数int job_num = 0; / 初始化区块数为0 char input_file_name30;/文件名char job_name10;/ 用户输入的作业名int length;/ 作业长int job_length_temp; int suanfa_select; int min_zuiyou;/ 用于最优适应算法保存最优int max_rongliang;/ 用于最差适应算法保存最差int select;/ 保存用户的命令选择，共有03 四个选项JOB* job_start, *job_ptr, *job_rear, *job_ptr1, *job_temp, *job_temp_suanfa2; FILE* fp;/ 文件指针printf( 可变分区模拟管理系统nn); printf( 请输入初始空闲文件名：); scanf(%s, input_file_name); if (fp =fopen(input_file_name, r) = NULL) printf( 无法打开此文件n); return; printf(n=); printf(n可变分区模拟管理系统); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 28 页 - - - - - - - - - printf(n=n); while (1) printf( 请选择分配算法：n); printf(1. 最先适应分配 t2. 最优适应分配 t3. 最坏适应分配t0. 退出 n); scanf(%d, &suanfa_select); if (0 = suanfa_select) return; if (1 = suanfa_select) / 首次适配printf(n=n); printf(1. 申请空间 t2. 撤销作业 t3. 显示空闲表和分配表t0. 退出 n); while(1) printf( 请选择：); scanf(%d, &select); if (0 = select) fp =fopen(input_file_name, w); job_ptr = job_start; while (job_ptr != NULL) if (job_ptr-length != 0) fprintf(fp, %d,%d,%sn, job_ptr-start, job_ptr-length, job_ptr-tag); job_ptr = job_ptr-next; fclose(fp); printf(n=n); break; if (1 = select) printf( 请输入作业及长度：n); scanf(%s%d, job_name, &length); job_ptr = job_start; while (job_ptr != NULL) if (length length & strcmp(job_ptr-tag, free) = 0) /如果小于区块长job_length_temp = job_ptr-length - length;/区块空闲长更新为减去length 之后的长度if (0 = job_length_temp) /如果该区块全部分配出去,tag 直接标记为作业名strcpy(job_ptr-tag, job_name); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 28 页 - - - - - - - - - else job_ptr-length = length; strcpy(job_ptr-tag, job_name); job_temp = (JOB*)malloc(sizeof(JOB);/ 插入头结点之后的结点job_num+; InitJOB(job_temp); job_temp-start = job_ptr-start + length; job_temp-length = job_length_temp; job_temp-next = job_ptr-next;/插入结点job_ptr-next = job_temp; break; / 如果小于区块长job_ptr = job_ptr-next; printf(n=n); if (2 = select) printf(n请输入要撤销的作业名：); scanf(%s, job_name); job_ptr1 = job_ptr = job_start; while (job_ptr != NULL) if (strcmp(job_ptr-tag, job_name) = 0) if (job_ptr = job_start & strcmp(job_start-next-tag, free) = 0) /如果待释放的区域在最前面,且其后为空闲，可合并job_start-length = job_start-length + job_start-next-length; job_start-next = job_start-next-next; strcpy(job_start-tag, free); job_num-; break; if (job_ptr = job_start & strcmp(job_start-next-tag, free) != 0) /如果待释放的区域在最前面，且其后不为空闲，不可合并strcpy(job_start-tag, free); break; if (strcmp(job_ptr1-tag, free) = 0 & strcmp(job_ptr-next-tag, free) = 0) job_ptr1-length = job_ptr1-length + job_ptr-length + job_ptr-next-length;/三区块合并长度job_ptr1-next = job_ptr-next-next; job_num-; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 28 页 - - - - - - - - - job_num-; break; if (strcmp(job_ptr1-tag, free) = 0) job_ptr1-length = job_ptr1-length + job_ptr-length;/两区块合并长度job_ptr1-next = job_ptr-next; job_num-; break; if (strcmp(job_ptr-next-tag, free) = 0) job_ptr-length = job_ptr-length + job_ptr-next-length;/两区块合并长度job_ptr-next = job_ptr-next-next; strcpy(job_ptr-tag, free); job_num-; break; strcpy(job_ptr-tag, free); break; job_ptr1 = job_ptr; job_ptr = job_ptr-next; printf(n=n); if (3 = select) printf( 当前空闲表：n); printf( 起始地址 t 长度 t 状态 tn); job_num =0;/ 初始化区块数为0 if (0 = count_select_3) while (!feof(fp) if (job_num = 0) / 构造未分配表的表头job_start = (JOB*)malloc(sizeof(JOB); InitJOB(job_start); job_ptr = job_rear = job_start; else / 构造未分配表job_rear-next = (JOB*)malloc(sizeof(JOB); InitJOB(job_rear-next); job_rear = job_rear-next; fscanf(fp, %d,%d,%s, &job_rear-start, &job_rear-length, job_rear-tag); if (job_rear-length != 0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 28 页 - - - - - - - - - printf(%dt%dt%stn, job_rear-start, job_rear-length, job_rear-tag); job_num+;/ 获得了当前的区块数 printf( 当前区块数： %dn, job_num); fclose(fp); count_select_3+;/ 选项 3 被选中的次数加1 else job_ptr = job_start; while (job_ptr != NULL) if (strcmp(job_ptr-tag, free) = 0 & job_ptr-length != 0) job_num+; printf(%dt%dt%stn, job_ptr-start, job_ptr-length, job_ptr-tag); job_ptr = job_ptr-next; printf( 起始地址 t 长度 t 占用作业名 tn); job_ptr = job_start; while (job_ptr != NULL) if (strcmp(job_ptr-tag, free) != 0) job_num+; printf(%dt%dt%stn, job_ptr-start, job_ptr-length, job_ptr-tag); job_ptr = job_ptr-next; printf( 当前区块数： %dn, job_num); printf(n=n); /3 = select else continue; /while(1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 28 页 - - - - - - - - - 六、实验九 . 磁盘调度6.1 设计目的：（1）要求学生设计一个模拟磁盘调度的程序（2）理解磁盘调度过程中的三个时间段（3）理解磁盘调度的三种算法6.2 设计要求：（1）设计并实现一个函数，完成先来先服务的磁盘调度功能（2）设计并实现一个函数完成最短寻道时间优先的磁盘调度功能。（3）设计并实现一个函数完成电梯算法的磁盘调度功能。6.3 详细设计：6.3.1 数据结构设计及变量说明：struct JobPid int job_pid;/作业所在磁道号 char job_flag;/访问标志 JobPid* next;/下一作业 JobPid* prior;/前一作业; 6.3.2 先来先服务：开始接收进程序列，构造双向链表链表还有结点Ptr = head总磁道数 +=本磁道数 -上一磁道数Y指针后移输出总磁道数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 28 页 - - - - - - - - - 结果展示：6.3.3 最短寻道优先：开始接收进程序列，构造双向链表剩余磁道数 0Ptr = head接收磁道数链表中还有结点更新结点与当前磁道号的最短距离指针后移以最短距离对应磁道号作为下一磁道号N剩余磁道数 -1输出访问顺序及总磁道数N总磁道数 += 最短距离名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 28 页 - - - - - - - - - 结果展示：6.3.3 LOOK 算法：开始接收进程序列，构造双向链表接收当前磁道号接收磁臂方向1向内前面还有结点输出磁道号Y总磁道数 += 初始磁道号与当前磁道号的差值N以初始磁道号为当前结点初始磁道号作为当前磁道号后面还有节点输出磁道号Y指针后移总磁道数 += 当前磁道号与初始磁道号的差值N输出总磁道数以初始磁道号为当前结点0向外后面还有节点指针前移输出磁道号Y指针后移总磁道数 +=当前磁道号与初始磁道号的差值N初始磁道号作为当前磁道号前面还有结点输出磁道号Y指针前移总磁道数 + =初始磁道号与当前磁道号的差值N输出总磁道数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 28 页 - - - - - - - - - 结果展示：6.3.4 实验源码#include #include #include struct JobPid int job_pid; char job_flag; JobPid* next; JobPid* prior; ; void InitJobPid(JobPid* job) job-job_pid = 0; job-job_flag = u; job-next = NULL; job-prior = NULL; void main() int user_select;/ 用户选择int temp_job_num; int total_distance = 0;/ 移动的总磁道数int cidaohao;/ 磁道号int now_min = 1000;/当前最短寻道时间int temp_min = 0;/临时最短寻道时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 28 页 - - - - - - - - - int job_num;/ 作业总数int temp_cidaohao;/存储当前磁臂位置int direction;/移动臂的移动方向JobPid* head, *ptr, *ptr1, *rear , *ptr_temp, *ptr1_temp ; printf(nn=请选择调度模式=n); printf(t1. 先来先服务 t2. 最短寻道时间优先t3.LOOK 算法 nn); printf(=n); while (1) head = ptr = ptr1 = rear = NULL; printf( 请选择： ); scanf(%d, &user_select); if (1 = user_select) total_distance = 0; printf(n请输入进程队列标识符（以0 结束） ：n); while (1) scanf(%d, &temp_job_num); if (0 = temp_job_num) break; if (NULL = head) head = (JobPid*)malloc(sizeof(JobPid); InitJobPid(head); head-job_pid = temp_job_num; rear = head; else rear-next = (JobPid*)malloc(sizeof(JobPid); InitJobPid(rear-next); rear = rear-next; rear-job_pid = temp_job_num; /while printf( 进程队列： ); ptr1 = ptr = head; while (ptr != NULL) printf(%d , ptr-job_pid); total_distance += abs(ptr1-job_pid - ptr-job_pid); ptr1 = ptr; ptr = ptr-next; printf(n移动的总磁道数：); printf(%dn, total_distance); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -