第一篇：操作系统课程设计报告
课程设计报告
题 目： 模拟请求页式管理
课程名称： 计算机操作系统 学 院： 信息工程学院
专 业： 计算机科学与技术
班 级： 14计本（1）学生姓名： * * * 学 号： 201403031** 指导教师： * * 成 绩：
开课时间： 2016-2017 学年 一 学期
模拟请求页式管理
第1章 需求分析
1.1设计要求
请求页式管理是一种常用的虚拟存储管理技术。本设计通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。本实验要求用Vc＋＋或其他高级语言编写和调试。
编写程序实现：
（1）先进先出页面置换算法（FIFO）（2）最近最久未使用页面置换算法（LRU）最佳置换页面置换算法（OPT）设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。
1.2解决方案
首先确定实现语言使用c#实现图形化界面，后确定要实现哪些功能，比如算法选择，页面添加，模拟控制。然后确定输出结构以便于程序的测试和验证。将基本框架建立后再进行编程。编程前进行算法结构分析最后编程实现。
1.3算法实现原理
1、先进先出置换算法（FIFO）：
发生缺页中断时按照页面进入内存顺序总是淘汰最先进入内存的页面。
2、最近最久未使用置换算法（LRU）：
发生缺页中断时总是淘汰存在内存中最长时间未被使用的页面。
3、最佳置换算法（OPT）：
发生缺页中断时若一个或几个页面将来将不会被调用则按先进先出原则淘汰页面，若将来都有调用则比较调用时刻选择最远时刻页面淘汰。
4、缺页率：缺页次数占页面调用次数的百分比。
第2章 概要设计
2.1数据设计
常变量：调用页面最大数量（MaxN），内存最大页面数（MaxM）待调用页面数组：page_dd[MaxN]存放等待调用的页面号
页面数组专用指针 page_p，用于指向page_dd数组中正需调入内存的页号 内存块数组：Memery[MaxM]，存放内存当前存放的页号 缺页计数器：count，记录缺页次数
内存块状态数组：M1[MaxN],M2[MaxN],M3[MaxN]，记录每次页面调用结束后内存各块的状态
缺页记录数组s[MaxN]，用于记录页面调用时是否产生缺页中断，初始化为是
2.2函数设计
1、页面添加函数：void btnAdd_Click(object sender, EventArgs e)用于实现通过点击按钮实现数据输入。
2、内存初始化函数：init(int[] a, int[] b,int []m1,int[]m2,int[]m3)参数有页面数组、内存数组、状态数组，采用先进先出算法对内存先进行装满 服务于先进先出页面置换函数和最佳置换函数。
3、输出函数：void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)用于输出模拟结果，参数有页面数组，内存数组，状态数组，缺页记录数组。再模拟之后调用。
4、模拟控制函数：void btnmo_Click(object sender, EventArgs e）用于实现通过单击模拟按钮，根据用户所选算法进行模拟并显示结果。
5、先进先出算法模拟函数：
void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)用于实现先进先出算法模拟，参数有页面数组，内存数组、内存状态记录数组，缺页记录数组。在模拟函数中调用。
6、最近最久未使用算法模拟函数：
void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于 3 实现最近最久未使用算法模拟，参数有页面数组，内存数组，内存状态记录数组，缺页记录数组。在模拟函数中被调用。
7、最近最久未使用函数辅助函数：void LUR_I(int[] a,int e)用于对最近最久未使用算法中所用辅助数组（记录页面存在时长）进行调整，参数有辅助数组及需调整的数据下标。在最近最久未使用函数中调用。
8、最佳置换算法模拟函数：
void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于模拟最佳置换算法。参数有页面数组，内存数组，内存状态记录数组，缺页记录数组。在模拟函数中被调用。
9、最佳置换算法辅助函数：void OPT_F(int[] a, int e)用于对最佳置换算法中的辅助数组进行调整。参数有辅助数组，需调整数据下标。在最佳置换算法中被调用。
10、重置函数：void btncz_Click(object sender, EventArgs e)用于重新选择算法进行新的模拟。
2.3主要算法设计
1、初始化函数算法：
第一步：将第一个页面调入内存，调整最佳置换算法辅助数组，缺页计数器加一，保存内存数组状态。
第二步：调用下一个页面并判断内存中是否有本页面有转第三步，无转第四步。第三步：更改缺页数组对应下标值，记录当前内存状态，调整最佳置换算法辅助数组，页面指针指向下一页。
第四步：将页面调入内存，调整最佳置换算法辅助函数，缺页计数器加一，保存内存数组状态。若内存尚不满转第一步。具体见图1初始化算法流程图。
开始页面调入内存缺页计数器加一记录内存状态调用下一页否否内存是否有该页面是记录内存状态修改缺页数组内存已满是结束
图1 初始化算法流程图
2、先进先出页面置换算法：
第一步：检查内存中是否已有需调用页面，有则转第二步，无则转第三步。第二步：记录当前内存状态，修改缺页数组对应下标值。
第三步：内存中无需要调用的页面，进行出队操作，然后进行入队操作，记录内存块状态，缺页计数器加一。
第四步：若页面数组未被调用结束转第一步。具体见图2先进先出算法流程图。
开始页面调入内存该页在内存中是否已存在是否否先出队操作后入队操作记录内存状态修改缺页数组值记录内存状态缺页计数器加一页面调用结束是结束
图2 先进先出算法流程图
3、最近最久未使用置换算法：
第一步：将页面调入内存，记录内存状态，缺页计数器加一，调整辅助数组，页面指针加一。
第二步：检查内存中是否已有所需页面，有转第三步，无转第一步。
第三步：修改缺页数组对应下标记录，记录内存状态，调整辅助数组，页面指针加一。第四步：内存是否已满，无则转第一步，是则转第五步。
第五步：检查内存中是否有所需页面，有则记录当前内存状态，修改缺页数组对应下标值。无则转第六步。
第六步：检查辅助数组找出最大值并记录其下标，置换内存中对应下标的数据，调整辅助数组，缺页计数器加一。
第七步：页面是否调用结束未结束则转第五步。具体见图3最近最久未使用算法流程图。
开始调入页面至内存记录内存状态计数器加一否调整辅助数组调用下一页内存中是否已有该页否内存已满是通过辅助数组确定淘汰页面是修改缺页数组记录内存状态调整辅助数组否页面置换记录内存状态计数器加一调用结束是结束
图3 最近最久未使用算法
4、最佳置换算法：
第一步：检查内存中是否已有所需页面，有则记录内存状态，修改缺页数组对应下标数值。无则转第二步。
第二步：判断内存中各页面的未来调用情况，记录是否还有调用，若有则记录调用时刻。
第三步：分析调用情况，内存中页面都在将来不会被调用转第四步，有一个被调用转第五步，有两个被调用转第六步，全被调用转第七步。
第四步:查找辅助数组找到内存中存在时间最长的页面进行置换，修改内存状态，缺页计数器加一，修改辅助数组。
第五步：查找到不会被调用的页面，并根据辅助数组选择最早进入内存的页面将其置换。修改内存状态，缺页计数器加一，修改辅助数组。
第六步：查找辅助数组找到将来不需要在调用的页面将其置换，修改辅助数组，记录内存状态，缺页计数器加一。
第七步：查找辅助数组，找寻最晚被调用的页面，将其置换。记录内存状态，修改辅助数组，缺页计数器加一。
第八步：页面是否调用完成，否则转第一步。具体见图4最佳置换算法流程图
开始调入页面记录内存状态计数器加一更新辅助函数是页面已存在否向后检查内存当前页面调用情况所有页面都不会再度调用否是一个页面会调用否否是两个页面会调用是否查找辅助数组得到最先进入页面通过辅助数组得到不会再调用的页面通过辅助数组获取最晚调用的页面通过辅助数组得到另外两个页面中最先进入的页面置换页面记录内存状态计数器加一更新辅助函数页面调用结束是结束
图4 最佳置换算法流程图 2.4界面设计
采用c# 设计windows窗体应用程序，使用下拉列表框选择算法，通过按钮添加待调用的页面。通过文本控件显示模拟结果。显示样式：第一行：算法名称；
第二行：调用页面顺序；
第三行至第五行显示内存在每调用一次页面后的状态；
第六行：是否缺页；
最后一行显示缺页率；
第3章 详细设计与实现
3.1函数设计
1、添加按钮功能实现代码
主要功能：实现单击一次添加一个调用页面，并给出相应的提示，如正在输入的是第几次调度页面，在输入为空时能够弹出对话框提示用户，在输入完成时为避免数组越界应在输入完成时隐藏；输入过程中始终保证时输入焦点。private void btnAdd_Click(object sender, EventArgs e){ if(txtAdd.Text!= “")//输入不为空才能继续输入 { page_dd[i_add] = Convert.ToInt32(txtAdd.Text);/*将输入值赋值给页面数组*/ txtShow.Text += txtAdd.Text + ” “;/*显示供用户查阅*/ i_add++;txtAdd.Clear();/*清空*/ if(i_add == MaxN)//输入结束时 { txtAdd.ReadOnly = true;//不允许继续输入 btnAdd.Hide();//按钮隐藏 return;} txtAdd.Focus();//设置为输入焦点
label2.Text = ”第“ +(i_add + 1)+ ”次调度页面：“;/*提示用户正在输入的是第几次调度页面*/ } /*输入为空则弹出对话框提示用户输入为空*/ else { MessageBox.Show(”请输入调用页面！“, ”输入为空“, MessageBoxButtons.OK, MessageBoxIcon.Warning);txtAdd.Focus();} }
2、初始化函数
主要功能：将内存一先进先出方式填满，并记录每个页面进入时间，服务于先进先出页面置换算法和最佳置换算法。
void init(int[] a, int[] b,int []m1,int[]m2,int[]m3){ /*内存未满时循环*/ for(int i = 0;i < MaxM&&page_p //调整辅助数组将刚进入内存的页面的对应时间 OPT_F(O_Q ,i)； count++;//缺页计数器加一 m1[page_p] = b[0];//保存内存状态 m2[page_p] = b[1];m3[page_p] = b[2];page_p++;//调用下一页面 //检查内存中是否原先就有需要的页面； for(int j = 0;j <= i&&page_p s[page_p] = 'F';//缺页数组对应数据更改 m1[page_p] = b[0];//记录内存状态 m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);//调整最佳置换算法辅助函数 page_p++;//调用下一页 j =-1;//重新开始寻找 } } } } 3、先进先出页面置换函数 主要功能：根据先进先出算法要求在产生缺页中断时采用先进先出方式确定淘汰页面，并在每次页面调用时记录下内存状态，缺页次数；采用循环队列使得每次出队的一定是最先进入内存的。 private void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s){ int Fpage_p = page_p;int front, rear;//定义队列对手和对尾指针并初始化 front = 0;rear = MaxM1;int sa;for(;Fpage_p < MaxN;Fpage_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//检查内存中是否已有要调用的页面。 { if(b[i] == a[Fpage_p]){ m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];s[Fpage_p] = 'F';sa = 1;break;} } if(sa == 0){ front =(front + 1)% MaxM; rear =(rear + 1)% MaxM;b[rear] = a[Fpage_p];m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];count++;} else continue;} } /*最近最久未使用算法辅助数组调整函数*/ private void LUR_I(int[] a,int e){ int temp;temp = a[e];a[e] = 1;for(int i = 0;i < MaxM;i++){ if(a[i] < temp && i!=e)a[i]++;} } /*最佳置换算法辅助数组调整函数*/ private void OPT_F(int[] a, int e){ if(e!=-1){ a[e] = 0;for(int i = 0;i < MaxM;i++){ if(i!= e)a[i]++;} } else for(int i = 0;i < MaxM;i++){ a[i]++;} } /*最近最久未使用算法*/ private void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){ int[] L_Q = new int[MaxM]{3,3,3};int sa;for(int i = 0;i < MaxM && page_p < MaxN;i++){ b[i] = a[page_p];//调入内存 count++;m1[page_p] = b[0];//保存内存状态 m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);page_p++;for(int j = 0;j <= i && page_p < MaxN;j++){ if(b[j] == a[page_p]){ s[page_p] = 'F';m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, j);page_p++;j =-1;} } } for(;page_p < MaxN;page_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//用的页面。{ if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];s[page_p] = 'F';LUR_I(L_Q, i);sa = 1;break;} } if(sa == 0){ 检查内存中是否已有要调40 for(int i = 0;i < MaxM;i++){ if(L_Q[i] == 3){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);break;} } count++;} else continue;} } /*最佳置换算法*/ private void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){ int sa;int O_p;int Ocount;int[] OPT_I=new int [MaxM ]{-1 ,-1 ,-1 };int[] OPT_J=new int [MaxM]{MaxN ,MaxN ,MaxN };for(;page_p < MaxN;page_p++){ for(int i = 0;i < MaxM;i++){ OPT_I[i] =-1;//刷新状态数组 OPT_J[i] = MaxN;} sa = 0;for(int i = 0;i < MaxM;i++)//检查内存中是否已有要调用的页面。 { if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1); s[page_p] = 'F';sa = 1;break;} } if(sa == 0)//缺页 { Ocount = 0;for(int i = 0;i < MaxM;i++){ O_p = page_p + 1;for(;O_p < MaxN;O_p++){ if(b[i] == a[O_p]){ Ocount++;OPT_I[i] = 1;OPT_J[i] = O_p;break;} } } switch(Ocount){ case 0://全部页面以后都不会再度调用 int temp = 0;for(int i = 0;i < MaxM;i++){ if(O_Q[i] > O_Q[temp])temp = i;} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 1://有一个页面将在以后调用 temp = 0;for(int i = 0;i < MaxM;i++){ if(OPT_I[i]!= 1 && O_Q[i] > O_Q[temp])temp = i; } b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 2: for(int i = 0;i < MaxM;i++){ if(OPT_I[i] ==-1){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, i);count++;} } break;case 3: int p = 0;for(int i = 0;i < MaxM;i++){ if(OPT_J[i] >OPT_J[p])p = i;} b[p] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, p);count++;break;} } } } /*重置函数*/ private void btncz_Click(object sender, EventArgs e){ comboBox1.SelectedIndex = 0; txtAdd.Text = ”“;page_p = 0;i_add = 0;count = 0;//txtShow.Text = ”";for(int i = 0;i < MaxM;i++)Memery[i] =-1;for(int i = 0;i < MaxN;i++)s[i] = 'T';} } } 操 作 系 统 课 程 设 计 实 验 报 告 学院：计算机科学与技术学院 班级：计112 学号：1113022032 姓名: 一、实验名称： 用C++实现驱动调度算法、页面替换算法、银行家算法、处理器调度算法 二、实验要求： 书写实验报告，包括的内容有： （1）实验题目 （2）程序中使用的数据结构及主要文字说明 （3）带有注释的源程序 （4）执行程序说明，表明各进程控制快的初始状态，以及各算法的运行状态 （5）通过实验后的收获与体会及对实验的改进意见和见解 二、实验目的： 通过自己编程来实现各类操作系统算法，进一步理解操作系统的概念及含义，提高对操作系统的认识，同时提高自己的动手实践能力。加强我们对各类算法的理解。 三、实验内容： 1、实现页面替换算法 （1）FIFO 先进先出页面替换算法 （2）LRU最近最少使用页面替换算法 （3）LFU最少使用频率页面替换算法 2、银行家算法 3、实现驱动调度算法 （1）先来先服务算法 （2）电梯算法 （3）扫描算法 4、实现处理器调度 （1）先进先出处理器调度 （2）时间片轮转法 （3）优先级调度 四、实验原理： 1、页面替换算法 先进先出页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面加以淘汰。将已调入内存的页面按先后次序链接成一个队列，将最先调入的页面与新页面进行置换 最近最久未使用置换算法：该算法是利用“最近的过去”作为“最近的将来”，将最近最久未使用的页面加以淘汰。将已调入内存的页面按先后顺序链接成一个队列，为每一个页面增加一个访问字段，用来记录一个页面自上次被访问以来所经历的是时间t，当需淘汰一个页面时，选择现有页面中其t值最大，即最近最久未使用的页面加以淘汰 2、银行家算法 先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。 3、驱动调度算法 先进先出算法（FIFO）：总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会 经常更换移动方向，效率有待提高 电梯调度算法：总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。 扫描算法（scan algorithm）：总是从最外向最内（或最内向最外）进行扫描，然后在从最内向最外（或最外向最内）扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或最内的请求时不会移动到最外或最内柱面。 4、处理器调度算法 先进先出处理器调度：按照作业进入系统后备工作队列的先后次序来挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后移入就绪队列。 时间片轮转法调度算法：调度次序每次把CPU分配给就绪队列进程/线程使用规 定的时间间隔，就绪队列中每个进程/线程轮流的运行一个时间片，当时间片耗尽时，就强迫当前运行进程/线程让出处理器，转而排列到就绪队列尾部，等候下一轮调度。 优先级调度：根据确定的优先级来选取进程/线程，总是选择就绪队列中的优先 级最高者投入运行，即优先级越高，先被调用。 五、数据结构设计 对操作系统的各类算法设计数据结构如下： 页面替换算法：void FIFO()；void LRU()；void LFU()； 银行家算法：void Init()初始化算法 void Bank()银行家算法 bool Safe()安全性算法 驱动调度算法： struct MagneticHead//磁头构成{ int site; int count; bool direct; }； struct Range//磁盘磁道范围 { int mStart; int mEnd; }; struct RequestList//请求序列 { int site; bool state; }; struct Data//基本数据集合{ MagneticHead magneticHead; RequestList *requestList; int *executeList; Range range; int length; }; 处理器调度： typedef struct pcb//时间片轮转法 { char pname[N]; int runtime; int arrivetime; char state; struct pcb*next; }PCB; typedef struct PCB1//先进先出服务 { char ID[3];//进程号 char name[10];//进程名 char state;//运行状态 floatarrivetime;//到达时间 floatstarttime;//进程开始时间 floatfinishtime;//进程结束时间 floatservicetime;//服务时间 float turnaroundtime;//周转时间 float weightedturnaroundtime;//带权周转时间 struct PCB1 *next;//指向下个进程 }pcb1; struct pcb2 {优先级调度 char name[10]; char state; int super; int ntime; int rtime; struct pcb2* link; }*ready=NULL,*d; typedef struct pcb2 PCB2; 六、课程设计总结 在本次课程设计中，就是讲平时所做的实验结合起来，实现操作系统的各类算法，了解操作系统的运行原理以及其基本概念，更好的将操作系统的原理很好的展现出来。同时，在本次实验中遇到了很多问题，需要我们仔细的检查和修改。其次，实验中为了能更好的体现各类算法的运行情况，需要做一个清晰的界面，以能清楚地看出运行结果。 操作系统课程设计报告 专 业：计算机科学与技术 学 号： 姓 名: 提交日期： 操作系统课程设计报告 【设计目的】 （1）本实验的目的是通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能和内部实现。 （2）结合数据结构、程序设计、计算机原理等课程的知识，设计一个二级文件系统，进一步理解操作系统。 （3）通过分对实际问题的分析、设计、编程实现，提高学生实际应用、编程的能力 【设计内容】 为Linux系统设计一个简单的二级文件系统。要求做到以下几点： 1.可以实现下列几条命令： login 用户登录 dir 列目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件 cd 进出目录 2．列目录时要列出文件名，物理地址，保护码和文件长度 3．源文件可以进行读写保护 【实验环境】 Windows xp/7 C++/VC++ 【相关知识综述】 1、文件系统 文件系统是操作系统用于明确存储设备（常见的是磁盘，也有基于NAND Flash的固态硬盘）或分区上的文件的方法和数据结构；即在存储设备上组织文件的方法。操作系统中负责管理和存储文件信息的软件机构称为文件管理系统，简称文件系统。文件系统由三部分组成：文件系统的接口，对对象操纵和管理的软件集合，对象及属性。从系统角度来看，文件系统是对文件存储设备的空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索的系统。具体地说，它负责为用户建立文件，存入、读出、修改、转储文件，控制文件的存取，当用户不再使用时撤销文件等。 2、位示图 位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配。有的系统把“0”作为盘块已分配的标记，把“1”作为空闲标志。(它们的本质上是相同的，都是用一位的两种状态标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。 操作系统课程设计报告 【设计思路】 本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。 首先应确定文件系统的数据结构：主目录、子目录及活动文件等。主目录和子目录都以文件的形式存放于磁盘，这样便于查找和修改。 用户创建的文件，可以编号存储于磁盘上。如：file0,file1,file2„并以编号作为物理地址，在目录中进行登记。 【程序主要流程图】 否 验证是否成 功？ 是 目录 右键进行选择 操作 新建目录新建文件打开文件 结束 开始登录删除属性 2 操作系统课程设计报告 【源程序清单】 typedef struct //文件结构体 /*the structure of OSFILE*/ { int fpaddr; /*file physical address*/ int flength; /*file length*/ int fmode; /*file mode:0-Read Only;1-Write Only;2-Read and Write;3-Protect;*/ char fname[MAXNAME]; /*file name*/ } OSFILE; typedef struct //用户文件目录结构体 user file directory /*the structure of OSUFD*/ { char ufdname[MAXNAME]; /*ufd name*/ OSFILE ufdfile[MAXCHILD]; /*ufd own file*/ }OSUFD; typedef struct //登陆 /*the structure of OSUFD'LOGIN*/ { char ufdname[MAXNAME]; /*ufd name*/ char ufdpword[8]; /*ufd password*/ } OSUFD_LOGIN; typedef struct //文件打开模式 /*file open mode*/ { int ifopen; /*ifopen:0-close,1-open*/ int openmode; /*0-read only,1-write only,2-read and write,3-initial*/ }OSUFD_OPENMODE; void DeleteF()/*Delete File*/ { int i,j,k=0;char str[255],str1[255];char fname[MAXNAME];k=ExistD(dirname);//获取用户的序号 printf(“Please input filename:”);gets(fname);//获得需要打开的文件名fname for(i=0;i if(strcmp(strupr(ufd[k]->ufdfile[i].fname),strupr(fname))==0) { 操作系统课程设计报告 } } void OpenF()/*Open File*/ { int i,k=0;char fname[MAXNAME];//printf(“nnC:%s>”,strupr(dirname));k=ExistD(dirname);printf(“Please input filename:”);gets(fname);//获得需要打开的文件名fname for(i=0;i if(strcmp(strupr(ufd[k]->ufdfile[i].fname),strupr(fname))==0) { ifopen[k][i].ifopen=1;//打开文件 ifopen[k][i].openmode=ufd[k]->ufdfile[i].fmode;//将读写属性赋值 //test// printf(“i=%d,k=%dn”,i,k); ///test// printf(“openmode=%dn”,ifopen[k][i].openmode); printf(“Open file successfully!n”); break;//打开文件则跳出循环 itoa(ufd[k]->ufdfile[i].fpaddr,str,10);//itoa函数，把数字转换成字符串 strcpy(str1,“file”);strcat(str1,str);strcpy(str,“c:osfilefile”);strcat(str,str1);strcat(str,“.txt”);//str为文件的物理路径 if(remove(str)==0) //调用remove函数删除 第k个用户的第i个文件ufd[k]->ufdfile[i] { fpaddrno[ufd[k]->ufdfile[i].fpaddr] = 0;//位示图置为0，表示没被占用 for(j = i;j<=fcount[k]-1;j++)//文件顺序往前移一位 ufd[k]->ufdfile[j] = ufd[k]->ufdfile[j+1]; fcount[k] = fcount[k]-1;//文件数-1 printf(“Delete file successfully!n”); //除了删除原文件，还要 删除dir中的东西 } else printf(“Delete file fail!n”);break;} 操作系统课程设计报告 } } } void CloseF()/*Close File*/ { int i,k=0;char fname[MAXNAME]; k=ExistD(dirname);printf(“Please input filename:”);gets(fname);//获得需要关闭的文件名fname for(i=0;i if(strcmp(strupr(ufd[k]->ufdfile[i].fname),strupr(fname))==0) { ifopen[k][i].ifopen=0;//关闭文件 ifopen[k][i].openmode=4;//fmode改为初始值4 printf(“Close file successfully!n”); break; } } } void WriteF()/*Write File*/ { int i,k,n=0;char fname[MAXNAME];char str[255],str1[255];int flag=1; if(strcmp(strupr(ltrim(rtrim(dirname))),“")==0) { printf(”nError.Please convert to ufd dir before read.n“); wgetchar=1; return;} printf(”nCaution:Open file firstn“);printf(”Opened File(s)List:n“);k=ExistD(dirname); 操作系统课程设计报告 for(i=0;i //文件属性为只写或者是读写才能write { printf(”%15s“,ufd[k]->ufdfile[i].fname); n++;} if((n%4==0)&&(n!=0))printf(”n“); } printf(”n%d files openned.n“,n); if(n==0)wgetchar=1;if(n!=0){ printf(”nPlease input FileName:“);gets(fname);ltrim(rtrim(fname));i=ExistF(fname);if(i>=0){ if(ifopen[k][i].ifopen==1) { if((ifopen[k][i].openmode==1)||(ifopen[k][i].openmode==2)) { itoa(ufd[k]->ufdfile[i].fpaddr,str,10); strcpy(str1,”file“); strcat(str1,str); strcpy(str,”c:osfilefile“); strcat(str,str1); strcat(str,”.txt“);//物理路径 int length=0; char c; printf(”Please input text('#' stands for end):n“); fp_file=fopen(str,”ab+“);//在文件末尾加 add bit while((c=getchar())!='#')//以#为结尾 { fputc(c,fp_file); if(c!='n')length++; } //fprintf(fp_file,”n“); 操作系统课程设计报告 fclose(fp_file); ufd[k]->ufdfile[fcount[i]-1].flength += length;//原长度加输入长度 printf(”n'%s' has been written successfully!n“,fname); } else { printf(”nError.'%s' has been opened with WRITE ONLY mode.It isn't read.n“,fname); wgetchar=1; } } else { printf(”nError.'%s' is in closing status.Please open it before readn“,fname); wgetchar=1; } } else { printf(”nError.'%s' does not exist.n",fname); wgetchar=1; } } } 操作系统课程设计报告 【测试结果】 1、创建用户 2、创建文件，并且打开读取文件 操作系统课程设计报告 3、写文件 4、删除文件 操作系统课程设计报告 【设计总结】 这两周的课程设计时间非常短，从中学到了很多知识，也为我们的学习提供了良好的实践平台。首先，通过老师的细心指导和同学们的相互帮助，让我对题目【二级文件系统】有了进一步了解。接下来，主要是研究老师所给的大部分代码，参考他的基本思路，并且思考每一个结构体在代码中的具体作用。这期间和一些同学交流了各自的思路，在交流中，大家渐渐的明确了这个程序的思路、框架结构等。我们所做的主要是补充了删除文件，打开文件，关闭文件，写文件这几个部分。 代码编写完了之后，实现了题目所要求的基本功能，但是在测试的过程中，还发现了这个程序存在各种各样的bug。不断的测试修改后，得到完善。 这次课设最大的收获在于：学会交流以及相互帮助。在大家的交流沟通之中，我们解决了一个又一个难题。 在这次课设中，我还意识到，要把这门课真真正正地学好，不单单只是为了能够应付考试，平时还要多加学习，多加努力才对。 【参考文献】 【1】C语言程序设计（第三版）谭浩强 【2】计算机操作系统教程(第三版).张尧学 史美林 张高 【3】计算机操作系统,西安电子科技大学出版社，方敏主编,2004.8 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 （操作系统课程设计） 连续动态分区内存 管理模拟实现 学生姓名： 韩 慧 学生学号： 031140312 班 级： 031140--3 0311401、02、03、04班制 二〇一三年十二月 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 目录 《操作系统》课程设计.......................................................1 引言......................................................................3 课程设计目的和内容......................................................3 需求分析.........................................................................3 概要设计...................................................................3 开发环境........................................................................4 系统分析设计.....................................................................4 有关了解内存管理的相关理论..................................................4 内存管理概念........................................................................4 内存管理的必要性..............................................................4 内存的物理组织.............................................................4 什么是虚拟内存.................................................................5 连续动态分区内存管理方式...................................................5 单一连续分配（单个分区)...................................................5 固定分区存储管理...............................................................5 可变分区存储管理（动态分区）..............................................5 可重定位分区存储管理........................................................5 问题描述和分析....................................................................6 程序流程图........................................................................6 数据结构体分析..................................................................8 主要程序代码分析...............................................................9 分析并实现四种内存分配算法.................................................11 最先适应算.....................................................................11 下次适应分配算法..........................................................13 最优适应算法...............................................................16 最坏适应算法...............................................................18 回收内存算法................................................................20 调试与操作说明.................................................................22 初始界面.......................................................................22 模拟内存分配...............................................................23 已分配分区说明表面............................................................24 空闲区说明表界面.............................................................24 回收内存界面.....................................................................25 重新申请内存界面..........................................................26.总结与体会......................................................................28 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 参考文献.........................................................................28 引言 操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。 存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。 课程设计目的和内容： 理解内存管理的相关理论，掌握连续动态分区内存管理的理论；通过对实际问题的编程实现，获得实际应用和编程能力。 编写程序实现连续动态分区内存管理方式，该程序管理一块虚拟内存，实现内存分配和回收功能。分析并实现四种内存分配算法，即最先适应算法，下次最先适应算法，最优适应算法，最坏适应算法。内存分配算法和回收算法的实现。 需求分析 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。常用的数据结构有动态分区表和动态分区链。在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法），在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容 概要设计 本程序采用机构化模块化的设计方法，共分为四大模块。⑴最先适应算法实现 从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。⑵下次适应分配算法实现 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 该算法是最先适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。⑶最优适应算法实现 它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。⑷最坏算法实现 最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 开发环境： win7 下 VC++6.0 系统分析设计： 相关算法原理，算法流程图，涉及的数据结构内容都相应包含在各章节中 有关了解内存管理的相关理论 内存管理概念： 内存管理，是指软件运行时对计算机内存资源的分配和使用的技术。其最主要的目的是如何高效，快速的分配，并且在适当的时候释放和回收内存资源。内存不是预先划分好的，而是在系统运行的过程中建立分区.当作业装入主存时，根据作业所需要的主存容量查看是否有足够的主存空间，若有则按需要分割一个分区给该作业；否则令该作业等待.分区长度不固定分区个数不固定。这种存储管理的方法克服了固定分区严重浪费主存的问题，提高了主存资源的利用率。 内存管理的必要性： 内存管理对于编写出高效率的 Windows 程序是非常重要的，这是因为Windows 是多任务系统，它的内存管理和单任务的 DOS 相比有很大的差异。DOS是单任务操作系统，应用程序分配到内存后，如果它不主动释放，系统是不会对它作任何改变的；但 Windows 却不然，它在同一时刻可能有多个应用程序共享内存，有时为了使某个任务更好地执行，Windows 系统可能会对其它任务分配的内存进行移动，甚至删除。因此，我们在 Windows 应用程序中使用内存时，要遵循Windows 内存管理的一些约定，以尽量提高 Windows 内存的利用率。湖北民族学院信息工程学院11级计算机专业操作系统课程设计 1.3 内存的物理组织： 物理地址： 把内存分成若干个大小相等的存储单元，每个存储单元占 8 位，称作字节（byte）。每个单元给一个编号，这个编号称为物理地址（内存地址、绝对地址、实地址）。 二、物理地址空间： 物理地址的集合称为物理地址空间（主存地址空间），它是一个一维空间。 什么是虚拟内存： 虚拟内存是内存管理技术的一个极其实用的创新。它是一段程序（由操作系统调度），持续监控着所有物理内存中的代码段、数据段，并保证他们在运行中的效率以及可靠性，对于每个用户层（user-level）的进程分配一段虚拟内存空间。当进程建立时，不需要在物理内存件之间搬移数据，数据储存于磁盘内的虚拟内存空间，也不需要为该进程去配置主内存空间，只有当该进程被被调用的时候才会被加载到主内存。 连续动态分区内存管理方式的实现 在早期的操作系统中，主存分配广泛采用连续分配方式。连续分配方式，是指为一个用户程序分配一个连续的内存空间，该连续内存空间指的的是物理内存。下面介绍连续分配的四种方式。 单一连续分配（单个分区） 最简单的存储管理方式，用于多道程序设计技术之前。内存分为系统区和用户区，系统区由操作系统使用。用户区作为一个连续的分区分配给一个作业。分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多 4个用户程序同时存在系统内存中，即共享内存空间。按分区划分方式可分为固定分区和可变分区。 固定分区存储管理 把内存的用户区预先划分成多个分区，每个分区大小可以相同，也可以不同。（分区的划分由计算机的操作员或者由操作系统给出，并给出主存分配表）分区个数固定，分区的大小固定。一个分区中可装入一个作业，作业执行过程中不会改变存放区域。早期的 IBM 的 OS/MFT（具有固定任务数的多道程序系统）采用了这种固定分区的方法。 可变分区存储管理（动态分区） 内存不是预先划分好的，而是在系统运行的过程中建立分区.当作业装入主存时，根据作业所需要的主存容量查看是否有足够的主存空间，若有则按需要分割一个分区给该作业；否则令该作业等待。分区长度不固定分区个数不固定。这种存储管理的方法克服了固定分区严重浪费主存的问题，提高了主存资源的利用率。ＩＢＭ操作系统ＯＳ／ＭＶＴ采用可变分区存储管理。湖北民族学院信息工程学院11级计算机专业操作系统课程设计 可重定位分区存储管理 解决碎片问题的一种简单方法是采用可重定位分区分配.。其中心思想是，把不同程序，且在内存中地址不连续的想法让他们连续。 例：内存中现有 3 个空闲区，现有一作业到达，要求获得 30k 内存空间，没有分区满足容量要求，若想把作业装入，可将内存中所有作业进行移动，这样把原来分散的空闲区汇集成一个大的空闲区。将内存中的作业进行移动使它们连接在一起把原来分散的多个小分区拼接成一个大的空闲区.这个过程称为”紧凑”或”移动”。需解决的问题:每次”紧凑”后程序或数据装入的物理地址变化采用动态重定位。 问题描述和分析 系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小大于请求分区大小，则从该分区中按改请求的大小划分出一块内存空间大小划分出一块内存空间分配出去，余下的部分仍留在空闲链表中。然后，将分配区的首址返回给调用者。 当进程运行完毕师范内存时，系统根据回收区的首址，从空闲区中找到相应的插入点，此时可能出现以下四种情况之一： ⑴该空闲区的上下两相邻分区都是空闲区：将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。 ⑵该空闲区的上相邻区是空闲区：将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后，修改上空闲区对应的可用表的表目项或自由链指针。 ⑶该空闲区的下相邻区是空闲区：将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空闲区之和。同理，合并后修改可用表或自由链中相应的表目项或链指针。 ⑷两相邻区都不是空闲区：释放区作为一个新空闲可用区插入可用表或自由链。 程序流程图 内存分配流程图，如图 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 从头开始查表检索完否？NY返回分区大小>所需大小N继续检索下一个表项Y分区大小-所需大小<=不可再分割大小N从该分区中划出所需大小的新分区Y将该分区从链中移出将该分区分配给请求者修改有关数据结构返回 内存回收流程图，如图 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 开始判断空闲区上下内存情况上为空下为空上下都为空上下都不为空将上面的空闲区合并，并回收将下面的空闲区合并，并回收将上下的空闲区合并，并回收直接将其回收结束 数据结构体分析 ⑴进程属性结构体 typedef struct readyque { char name[10];int size;}readyque,*readyqueue;⑵空闲链表结构体 typedef struct idlyspace { int from;int size;idlyspace * next;}idlyspace,*idly;⑶已分配链表结构体 typedef struct busyspace { int from;readyque r;湖北民族学院信息工程学院11级计算机专业操作系统课程设计 busyspace * next;}busyspace,*busy 主要程序代码分析 ⑴主函数//代码请添加适当的注释。int main(){ Is=(idly)malloc(sizeof(idlyspace));Is->from=0;Is->size=256;Is->next=NULL;Is2=Is;Bs=(busy)malloc(sizeof(busyspace));Bs->next=NULL;int t,t1;printf(“n.......................欢迎来到动态分区存储管理系统..................nn”);printf(“...........................请选择要执行的算法:...........................n”);printf(“.........................1.最先适应算法 ...............................n”);printf(“.........................2.下次适应算法............................n”);printf(“..........................3.最优适应算法 ...............................n”);printf(“.........................4.最坏适应算法................................n”);printf(“........................................................................n”);printf(“请输入您的选择:”);scanf(“%d”,&t);int i;while(i!=5){ printf(“........................................................................n”); printf(“.........................操作菜单如下：（请选择）.......................n”); printf(“..........................1.输入进程分配空间...........................n”); printf(“.........................2.进程撤销回收空间...........................n”); printf(“.........................3.输出所有空闲分区 ..........................n”); printf(“..........................4.输出所有已分配分区..........................n”); printf(“..........................5.退 出..........................n”); printf(“........................................................................n”); scanf(“%d”,&i); switch(i) { case 1: switch(t) { case 1: t1=FF();湖北民族学院信息工程学院11级计算机专业操作系统课程设计 break; case 2: t1=NF(); break; case 3: t1=BF(); break; case 4: t1=WF(); break; default: printf(“选择算法错误n”); return 1; } if(t1) printf(“分配空间成功n”); else printf(“分配空间失败n”); break; case 2: t1=recover(); if(t1) printf(“回收成功n”); else printf(“回收失败n”); break; case 3: Isprint(); break; case 4: Bsprint(); break; } } return 0;} 第三章 ：分析并实现四种内存分配算法 最先适应算法 空闲区按地址从小到大的次序排列。 分配：当进程申请大小为 SIZE 的内存时，系统顺序查找空闲区表（链），直到找到容量满足要求（≥SIZE）的空闲区为止。从该空闲区中划出大小为 SIZE的分区分配给进程，余下的部分仍作为一个空闲区，但要修改其首址和大小。湖北民族学院信息工程学院11级计算机专业操作系统课程设计 优点：这种算法是尽可能地利用低地址部分的空闲区，而尽量地保证高地址 6部分的大空闲区，有利于大作业的装入。 缺点:主存低地址和高地址分区利用不均衡。在低地址部分集中了许多非常小的空闲区碎片降低了主存的利用率。最先适应算法 int FF(){ int t=0;readyque D;printf““请输入进程名:””);scanf““%””,D.name); printf““输入进程申请空间大小:””);scanf““%””,&D.size); idly l=Is;int mt=256;busy b=Bs;idly min=NULL;while(l) //寻找空闲表中大小满足申请进程所需大小并且起址最小的空闲结点 { if(D.size<=l->size) { if(l->from { mt=l->from;min=l;t=1; } } l=l->next;} if(mt!=256) { busy j; j=(busy)malloc(sizeof(busyspace)); //如果找到则为进程分配空间 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 j->from=min->from; for(int i=0;i<10;i++) { j->r.name[i]=D.name[i]; } j->r.size=D.size; while(b->next) { if(b->next->from b=b->next;else break; } j->next=b->next; b->next=j; min->from=min->from+D.size; min->size=min->size-D.size;} return t;} 下次适应分配算法 最先适应算法的变种。 总是从空闲区上次扫描结束处顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止，分割一部分给作业，剩余部分仍作为空闲区。下次适应分配算法 int NF(){ int t=0;readyque D;printf““请输入进程名:””);scanf““%””,D.name); 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 printf““输入进程申请空间大小:””);scanf““%””,&D.size); int mt=256;idly l=Is2;idly min=NULL;busy b=Bs;while(l)//寻找空闲表中大小满足申请进程所需大小并且起址最小的空闲结点 { if(D.size<=l->size) { if(l->from { mt=l->from;min=l;t=1; } } l=l->next;} if(mt!=256) { busy j; j=(busy)malloc(sizeof(busyspace)); j->from=min->from; for(int i=0;i<10;i++) { j->r.name[i]=D.name[i]; } j->r.size=D.size; while(b->next) { if(b->next->from b=b->next;else break; //如果找到则为进程分配空间 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 } //将申请空间进程插入到已分配链表中 j->next=b->next; b->next=j; //修改相应空闲节点的起址和大小 min->from=min->from+D.size; min->size=min->size-D.size; Is2=min->next; 结点 t=1; return t;} l=Is;//l指向空闲表的头 while(l!=Is2) { if(D.size<=l->size) { if(l->from { mt=l->from;min=l;t=1; } } l=l->next;} if(mt!=256){ busy j; j=(busy)malloc(sizeof(busyspace)); j->from=min->from; for(int i=0;i<10;i++) { //ls2指向修改结点的下一个 //循环查找 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 j->r.name[i]=D.name[i]; } j->r.size=D.size; while(b->next) { if(b->next->from b=b->next;else break; } j->next=b->next; b->next=j; min->from=min->from+D.size; min->size=min->size-D.size; Is2=min->next; t=1; return t;} return t;} 最优适应算法 空闲区按容量递增的次序排列。 分配：当进程申请存储空间，系统顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止。采用最优适应算法选中的空闲区是满足容量要求的最小空闲区。优点：选中的空闲区是满足容量要求的最小空闲区，而不致于毁掉较大的空闲区。 缺点：空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储空间的浪费。最优适应算法 int BF(){ int t=0;湖北民族学院信息工程学院11级计算机专业操作系统课程设计 readyque D;printf““请输入进程名:””);scanf““%””,D.name); printf““输入进程申请空间大小:””);scanf““%””,&D.size); idly l=Is;idly min=NULL;int mt=256;busy b=Bs;while(l)//在空闲链中寻找第一个大于所输入的进程大小的空闲块 { if(D.size<=l->size) { if(l->size { mt=l->size;min=l;t=1; } } l=l->next;} if(mt!=256) { busy j; j=(busy)malloc(sizeof(busyspace));空间 j->from=min->from; //申请分配用于存放进程的内存 //找到第一个满足要求的空闲块 //将第一个满足要求的空闲块（min）的首地址赋给j for(int i=0;i<10;i++) { j->r.name[i]=D.name[i];16 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 } j->r.size=D.size; while(b->next) //按从小到大的顺序查找新进程在已分配区中的位置 { if(b->next->from b=b->next;else break; } j->next=b->next; b->next=j; min->from=min->from+D.size; min->size=min->size-D.size; } return t;} 最坏适应算法 为了克服最佳适应算法把空闲区切割得太小的缺点，人们提出了一种最坏适应算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，剩余的部分仍是一个较大的空闲区。避免了空闲区越分越小的问题。要求空闲区按容量递减的顺序排列。 分配：进程申请存储区时，检查空闲区表（链）的第一个空闲区的大小是否满足要求，若不满足则令进程等待；若满足则从该空闲区中分配一部分存储区给用户，剩下的部分仍作为空闲区。最坏适应算法 int WF(){ int t=0;readyque D;printf““请输入进程名:””);scanf““%””,D.name); printf““输入进程申请空间大小:””); //将所输入的进程插入进程链 //改变该空闲块的起始地址 //改变该空闲块的剩余大小 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 scanf““%””,&D.size); //输入进程申请的空间大小 idly l=Is;//l指向空闲链表ls头 idly min=NULL;int mt=0;busy b=Bs; //b指向已分配链表Bs头 //找到空闲分区中大小满足进程的请求且尺寸最大的结点 while(l){ if(D.size<=l->size)//判断进程所申请的大小是否小于空闲区的各结点大小 { if(l->size>mt) { mt=l->size;min=l;//min指向空闲区中尺寸最大的结点 t=1; } } l=l->next;} if(mt!=0)点 { busy j; j=(busy)malloc(sizeof(busyspace)); j->from=min->from; for(int i=0;i<10;i++) { j->r.name[i]=D.name[i]; } j->r.size=D.size; //判断是否找到了空闲区的满足结 //l指向空闲链表下一个结点 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 while(b->next)置 //寻找插入到已分配链表中的位 { if(b->next->from b=b->next;else break; } //把此进程结点j插入到已分配链表中 j->next=b->next; b->next=j; //修改空闲链表的相应结点的参数 min->from=min->from+D.size; min->size=min->size-D.size;} return t;} 可变分区的回收 当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻若相邻则把释放区合并到相邻的空闲区去，否则把释放区作为一个空闲区插入到空闲表的适当位置。 释放区与空闲区相邻的四种情况。 （1）释放区与前空闲区相邻：把释放区与前空闲区合并到一个空闲区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大小之和。 （2）释放区与后空闲区相邻：则把释放区合并到后空闲区，其首地址为释放区首地址，大小为二者之和。 （3）释放区与前后两空闲区相邻：这三个区合为一个空闲区，首地址为前空闲区首址，大小为这三个空闲区之和，并取消后空闲区表目。 （4）释放区不与任何空闲区相邻：将释放区作为一个空闲区，将其大小和首址插入到空闲区表的适当位置。 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 回收内存算法 int recover(){ readyque D;printf““请输入想要回收的进程名””); scanf““%””,D.name); busy b=Bs;idly l=Is;while(b->next)链表中 { bool yo=1; for(int i=0;i<10;i++) { if(b->next->r.name[i]==D.name[i])yo=yo*1; else yo=0; } //如果在已分配链表中则释放该结点所占空间 if(yo) { int t=b->next->from; int ts=b->next->r.size; //查找输入的进程名是否在已分配湖北民族学院信息工程学院11级计算机专业操作系统课程设计 while(l) { if(l->from>t+ts)不邻接 { idly tl;tl=(idly)malloc(sizeof(idlyspace));tl->from=t;tl->size=ts;tl->next=l;Is=tl;break;} if(l->from==t+ts) l->from=t; l->size=l->size+ts; busy tb=b->next; b->next=b->next->next; free(tb); return 1;} if(l->from+l->size idly tl; tl=(idly)malloc(sizeof(idlyspace)); tl->from=t; tl->size=ts; tl->next=l->next; l->next=tl; break;} else if(l->from+l->size==t) //所回收进程与空闲结点上邻接 { //所回收进程与空闲结点上下都不邻接 //所回收进程与空闲结点下邻接 { //所回收进程与空闲结点上下都 21 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 l->size=l->size+ts; if(l->from+l->size==l->next->from)接 { l->size=l->size+l->next->size; idly tm=l->next; l->next=l->next->next; freI); } br l=l->next; } //从已分配链表中释放所回收进程 busy tb=b->next; b->next=b->next->next; free(tb); return 1; } b=b->next;} printf(“没找到这”进程n”);return 0;} //所回收进程与空闲结点上下都邻调试与操作说明 初始界面 程序初始界面，有四个块选择，选择要执行的算法，调试以最坏算法为例，如图 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 选择最坏适应算法，如图 模拟内存分配 给进程a分配内存20，如图 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 已分配分区说明表界面 同理，给进程b分配内存30，给进程c分配内存40，给进程d分配50，给进程e分配60，如图 空闲分区说明表界面 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 查看空闲分区，如图 回收内存界面 回收进程b和d所占内存，如图 已分配分区说明表和空闲分区说明表 如图 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 重新申请内存界面 再为新进程i分配内存30，如图 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 根据最坏适应算法结合图所示可知，该算法将会从空闲分区表中选择一块最大的内存空间分配给进程i，从图也可看出该模拟算法实现了最坏适应算法 湖北民族学院信息工程学院11级计算机专业操作系统课程设计 总结与体会 本次做的课题是动态分区分配算法实现，此次课程设计成功实现了内存分配和内存回收，内存分配中包含了四种算法，分别是首次适应算法，循环首次适应算法，最佳适应算法和最坏适应算法。经编码调试，表明该程序模块是有效可行的。 通过这门课程的学习让我充分了解了内存管理的机制实现，从而更深一步的的对计算机 有了很多了解，这对于以后我们的研究和学习计算机系统起到了很重要的作用。 对于本次论文制作，自己的编程能力有所提高，对操作系统内存分配，存储空间的回收都有全新的认识。 在这次操作系统课程设计中，我使用了c++编写系统软件，对os中可变分区存储管理有了深刻的理解，但是过程中遇到了很多困难，一边做一边学，对c++有了比较多的理解。 实验中遇到很多问题，浪费了很多时间，总而言之是自己学习还不够好，不扎实，希望在以后学习中加以改善，学到更多知识。 参考文献 【1】 汤子瀛，哲凤屏，汤小丹.计算机操作系统.西安：西安电子科技大学出版社，2001.。湖北民族学院信息工程学院11级计算机专业操作系统课程设计 【2】 任爱华.操作系统实用教程.北京：清华大学出版社，2001。 长春理工大学 软件学院 0813111班 27号 姓名：丁为胜 一． 概述 1、课程设计目的及任务课程设计地点及要求 每个学生一台微机，需要安装windows98或windows2000操作系统，配备VC、VB、java或C编程语言，每个学生上机时间不少于24个小时。 操作系统是计算机专业的核心专业课，“操作系统课程设计”是理解和巩固操作系统基本理论、原理和方法的重要的实践环节。 操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统基本理论与管理方式。在算法基础上，解决实际的管理功能的问题，提高学生实际应用、编程的能力。 主要任务是实现操作系统和相关系统软件的设计，其中涉及进程创建，同步，进程间的通信，存储管理，文件系统等操作系统概念。 2.课程设计地点及要求 每个学生一台微机，需要安装windows98或windows2000操作系统，配备VC、VB、java或C编程语言，每个学生上机时间不少于24个小时。 3.课程设计的内容 设计二： 设计任务： 掌握进程的管道通讯机制和信号量同步互斥机制。1． 进程的管道通讯 编制一个程序，程序中创建一个子进程。然后父子进程各自独立运行，父进程不断地在标准输入设备上读入小写字母，写入管道。子进程不断地从管道中读取字符，转换为大写字母后输出到标准输出设备上。当读到x时，结束。 2． 信号量实现的同步互斥机制 编制一个程序，程序中创建5个子进程，代表五位哲学家，然后父进程结束。使用信号量机制解决哲学家进餐问题。当哲学家进餐时，屏幕输出： [进程号] eating!当哲学家思考时，屏幕输出： [进程号] thinging!相关的系统调用和函数：pipe();write();read();semget();sepop();semctl();要求：查找并阅读上述系统调用的相关资料，将上述相关的函数封装为P()、V()操作，使用你封装的P()、V()操作实现5位哲学家的同步和互斥。 二． 设计的基本概念和原理 1.进程的管道通讯 管道（Pipe）实际是用于进程间通信的一段共享内存，创建管道的进程称为管道服务器，连接到一个管道的进程为管道客户机。命名管道（Named Pipes）是在管道服务器和一台或多台管道客户机之间进行单向或双向通信的一种命名的管道。一个命名管道的所有实例共享同一个管道名，但是每一个实例均拥有独立的缓存与句柄，并且为客户——服务通信提供有一个分离的管道。实例的使用保证了多个管道客户能够在同一时间使用同一个命名管道。 2.信号量实现的同步互斥机制 规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号 的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即 五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获 得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲 学家会较先可以吃饭，因此不会出现饿死的哲学家。 三． 总体设计 1.实现的方法和主要技术路线 1.无名管道 无名管道用于具有亲缘关系的父子进程，子子进程之间的通讯。它的实现函数有 int pipe(int fd[2]); //fd[2] 为描述符数组，包含一个读描述符与一个写描述符，在使用管道通信时，关闭某些不需要的读或写描述符，建立起单向的读或写管道，然后用read 和write 像操作文件一样去操作它即可。 如图便是进程1 到进程2 的一个读管道。 分别在父进程和父子进程里向管道写数据，然后在子进程和子子进程里读数据。2.哲学家进餐伪码： semaphore chopstick[5]={1，1，1，1，1};void philosopher(int i){ while(true){ think(); if(i%2 == 0)//偶数哲学家，先右后左。 { wait(chopstick[ i + 1 ] mod 5);wait(chopstick[ i]);eat(); signal(chopstick[ i + 1 ] mod 5);signal(chopstick[ i]);} Else //奇数哲学家，先左后右。 { wait(chopstick[ i]); wait(chopstick[ i + 1 ] mod 5);eat(); signal(chopstick[ i]); signal(chopstick[ i + 1 ] mod 5);} } 四． 详细设计 进程的管道通信代码： import java.io.IOException;import java.io.PipedReader; public class ReceiverThread1 extends Thread { PipedReader pipedReader; public ReceiverThread1(SenderThread1 sender)throws IOException { pipedReader=new PipedReader(sender.getPipedWriter()); } public void run() { char[] ch=new char[100];StringBuffer sb=null;String str=null;int i=0;try { while((i=pipedReader.read(ch))!=-1) { sb=new StringBuffer(); for(int j=0;j { sb.append(ch[j]); } str=sb.toString(); System.out.println(“子进程读取的字符为：”+str.toUpperCase()); if(!str.endsWith(“x”)) { System.out.print(“父进程读入字符为：”); }else if(str.endsWith(“x”)) { System.out.println(“结束无法再次输入字符”); } } } catch(IOException e){ e.printStackTrace();}finally{ try { pipedReader.close(); } catch(IOException e){ e.printStackTrace(); } } } } import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PipedWriter; public class SenderThread1 extends Thread { PipedWriter pipedWriter; public SenderThread1(){ pipedWriter=new PipedWriter();} public PipedWriter getPipedWriter(){ return pipedWriter;} public void run() { BufferedReader ir=new BufferedReader(new InputStreamReader(System.in));char[] ch=new char[100];StringBuffer sb=null;String str=null;int i=0;System.out.print(“父进程读入字符为：”);try { while((i=ir.read(ch))!=-1) { sb=new StringBuffer(); for(int j=0;j { if(ch[j]>='a' && ch[j]<='z') { sb.append(ch[j]); if(ch[j]=='x') { break; } } } str=sb.toString(); pipedWriter.write(str); if(str.startsWith(“x”)||str.endsWith(“x”)) { break; // this.stop(); } } } catch(IOException e){ e.printStackTrace();}finally{ try { ir.close(); pipedWriter.close(); } catch(IOException e){ e.printStackTrace(); } } } } public class ThreadComm1 { public static void main(String[] args)throws Exception{ SenderThread1 sender=new SenderThread1();ReceiverThread1 receiver=new ReceiverThread1(sender);sender.start();receiver.start();} } 哲学家进餐问题代码： #include “stdafx.h” using namespace std;bool chop[100];//定义筷子 class ph { protected: bool * left,* right;//哲学家的左右手指向的筷子 int eattime;//哲学家的吃饭时间 public: bool check()//用于检查哲学家左右手的筷子是不是被占用 { if(*left && *right) return true; else return false;} void eat(int ineattime)//哲学家开始进餐 { eattime=ineattime; *left=false; *right=false;} bool finish()//检查哲学家是否完成进餐 { if(eattime>0)//没完成的话剩余时间减少 { eattime--; if(eattime==0)//完成的话归还筷子 { *left=true; *right=true; return true; } else return false; } else return false;} void init(int num,int max)//初始化哲学家，指定他们使用的筷子 { eattime=0; left=&chop[num]; if(num right=&chop[num+1]; else right=&chop[0];} };void main(){ system(“title 哲学家进餐问题”);int in,i,temp,time,j=1;queue for(int i=0;i<5;i++){ chop[i]=1; } for(int i=0;i<5;i++){ P[i].init(i,5);} cout<<“输入哲学家进餐队列：”< break;else if(in>5) { cout<<“一共只有”<<5<<“个人！”< } else { Q.push(in-1); } } cout<<“每个人吃饭时间：”< P[temp].eat(time); cout< if(temp+2>5) cout<<1< else cout< Q.push(temp);} for(i=0;i<5;i++) { if(P[i].finish()) cout< } //Q.push(-1); for(i=0;i { temp=Q.front(); Q.pop(); //if(temp!=-1) { cout< Q.push(temp); } //else { // Q.pop(); break; } } } for(int j=0;j if(P[i].finish()) { cout< } getch();}第二篇：操作系统课程设计报告
第三篇：操作系统课程设计报告
第四篇：操作系统课程设计
第五篇：操作系统课程设计
点击咨询 