第一篇：操作系统课程设计
引言
操作系统是计算机科学与技术专业的主要专业基础课和主干课。操作系统对计算机系统资源实施管理，是所有其他软件与计算机硬件的唯一接口，所有用户在使用计算机时都要得到操作系统提供的服务。
通过模拟操作系统的全部或者部分功能的实现，加深对操作系统工作原理和操作系统实现方法的理解，达到练习编程的目的，提高学生运用理论知识分析问题、解决问题的能力，为学生从事科学研究和独立负担计算机及其应用方面的工作打好扎实的基础。
0 河北大学工商学院2011级操作系统课程设计论文（设计）课程设计任务及要求
2.1 设计任务
模拟采用多道程序设计方法的单用户操作系统，该操作系统包括进程管理、存储管理、设备管理、文件管理和用户接口四部分。
本部分要求实现文件的逻辑结构、文件的物理结构、目录结构、磁盘分配和回收、文件的保护和用户接口。
2.2 实现方法和原理
2.2.1文件的逻辑结构：
文件的逻辑结构采用流式结构； 文件均采用文本文件；
系统中有两种文件，一种是存放任意字符的文件，一种是可执行文件。可执行文件的内容就是模拟系统内进程的程序体。
文件中要有一种特定命令的“可执行”文件，文件中的命令非常简单，包括： x=?;
给x赋值一位数 x++;
x加1 x--;
x减1!??；
第一个？为A,B,C中某个设备，第二个？为一位数，表示使用设备的时间（由于没有实际设备，所以无法知道设备何时工作完成，所以假定一个数，这个数随着系统时间增加而递减，减到0时，认为是设备工作完成）；
end.表示文件结束，同时将结果写入文件out，其中包括文件路径名和x的值。2.2.2 磁盘模拟：
用一个文件disk模拟磁盘，磁盘的每个盘块64字节，模拟磁盘共有128块。第0、1块存放文件分配表，第2块存放根目录，其余存放子目录和文件。2.2.3目录结构
目录结构采用树型目录结构，目录项内容共十六个字节。①目录项内容（8个字节）： 目录名、文件名：3个字节；
河北大学工商学院2011级操作系统课程设计论文（设计）
扩展名：1个字节（可执行文件扩展名为e，目录没有扩展名）； 目录、文件属性：1字节； 起始盘块号：1个字节；
文件长度：2字节（目录没有长度）。②根目录
根目录位置固定，为磁盘第2块，大小固定，共8项，占用模拟磁盘第2块； ③子目录
位置不固定，大小不固定。2.2.4磁盘分配
磁盘的分配采用链接结构（显式链接）的分配方式。系统采用文件分配表方式记录磁盘空间的使用情况和链接结构的指针。
因为磁盘有占用磁盘由128块，所以文件分配表中一项需要1字节，而磁盘由128块，因而需要128项，所以模拟磁盘空间中的第0、1块被用来存放文件分配表。2.2.5用户接口
用户接口提供用户命令接口，要求实现以下命令： 创建文件：create 拷贝文件：copy 删除文件：delete 移动文件：move 显示文件：type 编辑文件：edit 改变文件属性：change 磁盘格式化命令 format 建立目录：makdir 改变目录路径：chadir
删除空目录：rdir 删除目录：deldir（既可删除空目录又可删除非空目录）
河北大学工商学院2011级操作系统课程设计论文（设计）
磁盘分区命令：fdisk 运行可执行文件：可执行文件的文件名（可创建进程）。
上述命令在实际系统中都是需要建立进程才可以实现的，这里由于模拟系统的能力达不到，所以除运行可执行文件需要建立进程外，其他指令执行不必在模拟系统中建立进程，可直接执行。
注意打开文件表。2.2.6屏幕显示
如图所示，屏幕显示要求包括：
用户命令接口，用于系统运行时用户输入命令； 磁盘目录显示，要求显示磁盘的树型目录结构；
磁盘使用情况，显示磁盘每一个磁盘块的空间是占用还是空闲。
3程序设计与实现
3.1目录结构的实现
3.1.1创建目录
#region CreateMenu(建立目录)
public void CreateMenu(string pathname,string harddisk)3.1.2删除空目录
删除空目录首先要找到该目录，如果目录不存在，执行指令失败；如果存在，但是根 河北大学工商学院2011级操作系统课程设计论文（设计）
目录或非空目录显示不能删除，操作失败；若是非空子目录，则删除器目录项并回收对应空间。删除空目录的过程和删除文件的过程相似。
3.1.3删除目录
#region DeleteMenu(删除目录)
public void DeleteMenu(string pathname, string harddisk)
{
if(Search(pathname,harddisk)== 1)
{
MessageBox.Show(“文件路径不正确！”, “注意”, MessageBoxButtons.OK, MessageBoxIcon.Exclamation);3.2文件 3.2.1创建文件
#region CreateFile(建立文件)public void CreateFile(string pathname, byte attribute, byte address, char length, string harddisk){
if(attribute == 3 || attribute == 5){
MessageBox.Show(“只读性质，建立失败！”, “注意”, MessageBoxButtons.OK，MessageBoxIcon.Exclamation);
return;} 3.2.2拷贝文件
#region CopyFile(复制文件,只复制FCB)
public void CopyFile(string pathname1, string pathname2, string harddisk)
{
string[] pnames = pathname1.Split(new char[] { '', '.' });
string halfpathname = pathname1.Remove(pathname1.Length1]);
UTF8Encoding utf = new UTF8Encoding();4 河北大学工商学院2011级操作系统课程设计论文（设计）
byte[] name = utf.GetBytes(pnames[pnames.Length1];
CreateFile(pathname2, buffer.Attribute, buffer.Address, buffer.Length,harddisk);
}
#endregion 3.2.3删除文件 #region DeleteFile(删除文件)
public void DeleteFile(string pathname, string harddisk)
{
if(Search(pathname,harddisk)==1)
{
MessageBox.Show(“文件路径不正确！”, “注意”, MessageBoxButtons.OK, MessageBoxIcon.Exclamation);
return;
}
else if(Search(pathname,harddisk)== 2)
//文件存在 {
string[] pnames = pathname.Split(new char[] { '', '.' });
string halfpathname = pathname.Remove(pathname.Length2]);
int disknum;
if(pnames.Length == 3)
//c:aaa.t
{
disknum = 3;
}
else
{
disknum = Search(halfpathname,harddisk);
}
int item = FindItem(disknum, name, attribute,harddisk)[0];
int address = FindItem(disknum, name, attribute,harddisk)[1];
byte addr = Convert.ToByte(address);
DeleteFCB(disknum, item,harddisk);
//删除FCB
if(addr==0)
{
return;3.2.4移动文件
#region CutFile(移动文件)
public void CutFile(string pathname1, string pathname2, string harddisk)
{
CopyFile(pathname1, pathname2,harddisk);//复制FCB到新目录下
string[] pnames = pathname1.Split(new char[] { '', '.' });
string halfpathname = pathname1.Remove(pathname1.Length1]);
UTF8Encoding utf = new UTF8Encoding();6 河北大学工商学院2011级操作系统课程设计论文（设计）
byte[] name = utf.GetBytes(pnames[pnames.Length1)+ 8 *(Itemnumber-1), SeekOrigin.Begin);
Disk.Write(buffer.Name, 0, buffer.Name.Length);
Disk.Seek(0, SeekOrigin.Current);
Disk.WriteByte(buffer.Type);
Disk.Seek(0, SeekOrigin.Current);
Disk.WriteByte(buffer.Attribute);
Disk.Seek(0, SeekOrigin.Current);
Disk.WriteByte(buffer.Address);7 河北大学工商学院2011级操作系统课程设计论文（设计）
Disk.Seek(0, SeekOrigin.Current);
Disk.WriteByte(Convert.ToByte(buffer.Length));
}
Disk.Close();
}
#endregion
3.2.7显示文件
#region ReadFile(读文件画节点)
public void ReadFile(TreeView treeView, ContextMenuStrip contextMenuStrip,ImageList imageList)
{
treeView.Nodes.Clear();
//删除集合中所有树节点
//重新添加树节点
treeView.ImageList = imageList;
TreeNode root = new TreeNode(“计算机”, 0, 0);
TreeNode node_C = new TreeNode(“本地磁盘C”, 4, 4);
TreeNode node_D = new TreeNode(“本地磁盘D”, 4, 4);
node_C.ContextMenuStrip = contextMenuStrip;
node_D.ContextMenuStrip = contextMenuStrip;
treeView.Nodes.Add(root);
root.Nodes.Add(node_C);
root.Nodes.Add(node_D);
DrawTree(node_C, 3,“disk1.txt”,contextMenuStrip);
DrawTree(node_D, 3, “disk2.txt”,contextMenuStrip);
treeView.ExpandAll();
}
#endregion
4.程序运行部分截图
4.1主页面 河北大学工商学院2011级操作系统课程设计论文（设计）
4.2创建文件
4.3编辑文件河北大学工商学院2011级操作系统课程设计论文（设计）
4.4创建目录 总结
在此系统我主要模拟的是文件部分。通过编写此系统，采用了c#语言。但是，在实现此系统中，一方面因为我对c#这门语言掌握的不是很熟练，另外一方面，对操作系统理解的不够深入以至于部分功能没有实现，让我发现了自己的不足，从而要在以后的学习中更加努力，不短提高自己个方面的能力。
河北大学工商学院2011级操作系统课程设计论文（设计）
装
订
第二篇：操作系统课程设计
湖北民族学院信息工程学院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();} 操作系统课程设计 注意事项： 0.请每位同学必须按时提交课程设计报告（包括电子版和纸质版），算入期末成绩 1.在三个题目中选择一个 2.如果选择题目 （一）进程调度算法，要求实现其中2个以上（包括2个）进程调度算法 3.如果选择题目 （二）银行家算法，要求能够判断系统的安全状态 4.如果选择题目 （三）页面调度算法，要求实现其中2个以上（包含2个）进程调度算法 5.报告应包含算法分析、实验截图、核心算法源代码，请各位同学认真对待，独立完成 6.提交要求：电子版（包括实验程序）请发至ropeal@163.com，纸质版请班长收齐，由班长统一在课堂上提交（并提交未交人员名单），截止时间第16周周三(2014.1.31)7.格式要求： 7.1 A4纸10页左右 7.2 封面请注明班级、姓名、学号、所选题目 7.3 电子版发送时，请打包成一个文件，将文件名设置为：学号+姓名+题目名称（如20130000张三进程调度算法课程设计），邮件主题同文件名 一、进程调度算法 1.1 实验目的： a、设计进程控制块PCB表结构，模拟实现进程调度算法：FIFO，静态优先级调度，时间片轮转调度，多级反馈队列调度。（实现其中之二）。* b、建立进程就绪队列。对不同算法编制入链子程序。c、编写一进程调度程序模拟程序。模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。* 由用户输入进程名和进程长度，然后按照短进程优先的进程处理顺序给出进程的排序。 1.2 实验原理 调度算法是指：根据系统的资源分配策略所规定的资源分配算法。1.2.1 先来先服务和短作业（进程）优先调度算法 1.先来先服务调度算法。先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业，而不利于I/O繁忙型的作业（进程）。 2.短作业（进程）优先调度算法。短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度，也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。1.2.2 高优先权优先调度算法 1.优先权调度算法的类型。为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度，将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时，又可以进一步把该算法分成以下两种： 1)非抢占式优先权算法 2)抢占式优先权调度算法（高性能计算机操作系统） 2.优先权类型。对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权，以及如何确定进程的优先权。3．高响应比优先调度算法 为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间 1.2.3 基于时间片的轮转调度算法 1.时间片轮转法。时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。2.多级反馈队列调度算法 多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。其实施过程如下： 1)设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中，为每个进程所规定的执行时间片就越小。 2)当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度„„ 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。3)仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1到第（i-1）队列空时，才会调度第i队列中的进程运行，并执行相应的时间片轮转。4)如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列，则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。 1．3 实验要求 a、使用模块化设计思想来设计； b、给出算法的流程图或伪码说明。c、学生可按照自身条件，随意选择采用的算法，（例如：采用冒泡法编写程序，实现短进程优先调度的算法） d、进程调度程序模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。 1.4 算法简析 a、每个进程可有三个状态，并假设初始状态为就绪状态。b、为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。c、在优先数算法中，优先数可以先取值为（50-该进程所需时间），进程每执行一次，优先数减3，CPU时间片数（CPUtime）加1，* 进程还需要的时间片数（needtime）减1。在时间片轮转算法中，采用固定时间片 （即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片（CPUtime）数加2，* 进程还需要的时间片数（needtime）减2，并排列到就绪队列的尾上。 d、对于遇到优先数一致的情况，采用FIFO策略解决。 二、银行家算法 2.1 概述 2.1.1 设计目的1、了解多道程序系统中，多个进程并发执行的资源分配。 2、掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。 3、掌握预防死锁的方法，系统安全状态的基本概念。 4、掌握银行家算法，了解资源在进程并发执行中的资源分配策略。 5、理解死锁避免在当前计算机系统不常使用的原因 2.2 关于死锁 2.2.1 死锁概念： 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 2.2.2 关于死锁的一些结论： 参与死锁的进程最少是两个（两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 2.2.3 资源分类： 永久性资源： 可以被多个进程多次使用（可再用资源），分为：可抢占资源与不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请--分配--使用--释放”模式 2.2.4 产生死锁的四个必要条件： 1、互斥使用（资源独占） 一个资源每次只能给一个进程使用 2、不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配） 4、循环等待 存在一个进程等待队列 {P1 , P2 , „ , Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，„，Pn等待P1占有的资源，形成一个进程等待环路 2.2.5 死锁的解决方案 1 产生死锁的例子 申请不同类型资源产生死锁 P1： „ 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 „ P2： „ 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 „ 申请同类资源产生死锁（如内存） 设有资源R，R有m个分配单位，由n个进程P1,P2,„,Pn（n > m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 m=2，n=3 资源分配不当导致死锁产生 2死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一 ①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 ②破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 ③破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 2.2.6 安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，„Pn，则系统处于安全状态。一个进程序列{P1，„，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量之和，系统处于安全状态(安全状态一定是没有死锁发生的)。 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。 2.3 数据结构设计 1.可利用资源向量矩阵AVAILABLE。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果AVAILABLE [j]= K，则表示系统中现有R类资源K个 2.最大需求矩阵MAX。这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果MAX [i,j]=K，则表示进程i需要R类资源的数目为K。 3.分配矩阵ALLOCATION。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果ALLOCATION [i,j]=K，则表示进程i当前已分得R类资源的数目为K。 4.需求矩阵NEED。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果NEED [i,j]=K，则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系： NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j] 2.4 算法的实现 2.4.1 初始化 由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。2.4.2 银行家算法 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 2.4.3 安全性检查算法 (1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。 三、页面调度算法 3.1 实验名称 页式虚拟存储管理：页面调度算法 3.2 实验目的 页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解。3.3 实验原理 页面调度算法 目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。 下面对各调度算法的思想作一介绍。 <1> 先进先出调度算法 先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。 <2>最近最少调度算法 先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。 <3>最近最不常用调度算法 由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。 缺页调度次数和缺页中断率、缺页置换率计算 缺页中断次数是缺页时发出缺页中断的次数。 缺页中断率=缺页中断次数/总的页面引用次数*100% 缺页调度次数是调入新页时需要进行页面调度的次数 缺页置换率=缺页调度次数/总的页面引用次数*100% 3.4 实验内容 （1）设计程序实现以上三种页面调度算法，要求： ①.可以选择页面调度算法类型； ②.可以为进程设置分到物理页的数目，设置进程的页面引用情况，可以从键盘输入页面序列，也可从文件中读取； ③.随时计算当前的页面调度次数的缺页中断率； ④.使用敲键盘或响应WM-TIMER的形式模仿时间的流逝； ⑤.以直观的的形式将程序的执行情况显示在计算机屏幕上； ⑥.存盘及读盘功能，可以随时将数据存入磁盘文件，供以后重复实验时使用。 （2）假定进程分配到3个物理块，对于下面的页面引用序列：（test.txt） 7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1 请分别用先进和先出调度算法，最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。 再假定进程分配到4、5个物理块，重复本实验。 （3）假定进程分配到3个物理块，对于下面的页面引用序列：（test2.txt） 4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9 请分别用先进先出调度算法、最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。 再假定进程分配到4、5个物理块，重复本实验。 （4）假定进程分配到3个物理块，使用程序的动态页面序列生成算法，生成一个页面序列，将此序列存入磁盘文件。再从磁盘文件读入该序列，用程序分别计算三种算法下的缺页中断次数、缺页中断率和缺页调度次数、缺页置换率。 《操作系统课程设计》教学大纲 一、课程设计基本信息 课程设计环节代码：230027 课程设计环节名称：操作系统课程设计 英文名称：Course Design of Operating System 课程设计周数：2周 学分：2.0 适用对象：计算机科学与技术专业、网络工程专业 先修课程与环节：高级语言程序设计、数据结构和操作系统 二、课程设计目的和任务 本课程是计算机专业的学生在学习了《操作系统》课程之后，为了加深和巩固学生对所学操作系统各个理论和算法知识的理解，同时提高学生利用操作系统知识综合运用的能力和分析问题、解决的问题的能力而开设的一门实践课程。 通过本环节学生能够充分把学到的知识应用到实际的编程实践中，有可以进一步巩固操作系统中学习的理论。通过算法实现各种控制应用进一步体会操作系统中基本功能模块的结构和实现方法的实质，建立深入了解现有操作系统的评价和比较的方法，加深体会利用操作系统的原理能够解决实际问题的在计算机系统编程和普通编程中解决实际问题的思路；通过对程序编写规范，可以培养学生良好的编程风格，包括程序结构形式，行文格式和程序正文格式等；并培养学生的上机调试能力。 三、课程设计方式 1、课程设计题目的选定 采用指导教师提供参考题目与学生自主命题相结合的办法选定课程设计题目。一人一题，不得重复。其中学生自主命题需要指导教师严格的审核，看是否满足课程要求，检查是否为重复课题。 2、课程设计任务的完成 在指导教师的指导下，各个学生独立完成课题分析、设计、代码编写和调试，独立撰写课程设计报告。所有工作任务主要在微机实验室完成。 四、课程设计教学方法与要求 课程设计教学方法：主要以学生上机操作为主，教师指导为辅 课程设计要求： 1、对系统进行功能分解、模块分析、控制模块分析正确 2、选择合适的操作系统原理所需要数据结构以及相应的算法 3、程序规模适中，着重于内核修订功能，也可以编写外围的程序驱动、文件系统的辅助工具和网络工具等。尽可能的使系统的功能更加完善和全面 4、掌握程序调试的方法 5、说明书、流程图要清楚，阐明设计思路。 6、撰写课程设计报告。按格式要求写出完整、规范的报告并打印。其中模块图、流程图要清楚、规范。特别要求学生自己独立完成。 五、课程设计内容和时间安排 （一）动员、准备及规划（1天） 实习具体内容：动员、选题、系统功能和需求的分析 时间分配：上午动员、下午选题及规划 实习地点：机房 （二）课程设计实施、检查（1天） 实习具体内容:需求分析说明书和任务规划，设计出每个功能 时间分配: 上午上机、下午初期检查 实习地点: 机房 （三）课程设计实施（12天） 实习具体内容: 具体功能的实现及系统的完善工作、中期检查 时间分配: 11.5天上机，0.5天中期检查 实习地点: 机房 （四）整理报告（1天） 实习具体内容: 文档整理、设计报告的完成 时间分配: 全部时间写报告 实习地点:机房或图书馆 六、课程设计基本要求 （一）动员、准备及规划 1、要求：通过学习，使学生了解所选择开发环境的程序运行环境中的调试功能，掌握跟踪、修改错误的技巧。 2、重点:题目的选定和结合操作系统原理的各个部分确定实现的功能以及和原理的结合，难点:对于程序运行环境学会断点设置以及中间结果的检查。 3、说明：题目自选也可以参考教师提供的题目，选题要紧密结合课堂教学内容；并建立一个可行的工作计划；熟悉程序运行环境。 （二）课程设计实施、检查 1、要求：领会按照实际的结构，使学生能根据实际问题选择数据结构，清晰的描述算法 2、重点和难点：算法分析和设计 3、说明：学生自检和指导教师检查相结合，严格按照拟订计划完成任务 （三）课程设计实施 1、要求：培养良好的编程风格，掌握所选编程语言 2、重点和难点：算法分析和设计 3、说明：学生自检和指导教师检查相结合，严格按照拟订计划完成任务 （四）整理报告 1、要求：通过学习,使学生掌握报告书写规范 2、重点：格式的规范 3、说明：指导教师检查 七、课程设计的考核方式和成绩评定标准 （一）课程设计考核方式 点名、各个环节的考核及程序检查、设计报告的综合评定。 （二）课程设计成绩评定标准 课程设计成绩=点名*10%+程序检查*30%+设计报告*60% 由指导教师根据学生完成任务的情况、课程设计报告的质量和课程设计过程中的工作态度等综合打分。成绩评定实行优、良、中、及格和不及格五个等级。不及格者不能得到相应的学分，需重新做课程设计，经指导教师考核及格后，方可取得相应学分。 优：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，其中有总体设计思想的论述；程序完全实现设计方案，设计方案先进，软件可靠性好； 良：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；有完全实现设计方案的软件，设计方案较先进； 中：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确； 及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确； 不及格：没有完整符合标准的文档，软件没有基本实现设计方案，设计方案不正确。提交的电子文档和软件必须是由学生自己独立完成，雷同者教师有权视其情况扣分或记零分。 八、课程设计指导书 孙钟秀编《操作系统教程》（高等教育出版社） 九、其他说明 （一）课程设计报告要求： 总结报告按如下内容顺序用A4纸进行撰写并打印装订成册： 1、统一的封面； 2、内容摘要； 3、目录； 4、课程设计正文包含以下内容：（1）需求分析 （2）概要设计：每个部分的算法设计说明可以是描述算法的流程图，说明每个程序中使用的存储结构设计（如果指定存储结构请写出该存储结构的定义）。 （3）详细设计：各个算法实现的源程序，源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。（4）调试分析：测试数据，测试输出的结果，算法时间复杂度分析 E结论和展望：每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），和算法的改进设想。课程设计过程的收获、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。 （5）按统一格式列出主要参考文献。 （二）学生上交材料： 1、程序源代码和一组较完备的测试数据（打包上传，发送到各个指导老师的邮箱中，文件名格式为“姓名-班级-学号”）； 2、上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明； 3、课程设计报告 大纲修订人：闫大顺 修订日期：2006年8月20 大纲审定人： 审定日期： 附：指导教师推荐题目（供参考）选题：题目大小适中 课题 一、编制银行家算法通用程序，并检测所给状态的系统安全性。 设计目的：主要是解决多种资源的被多个独立执行的程序使用的安全算法。银行家算法就是采用矩阵存储资源的数据进行处理的方法。设计的要求： 1）资源的种类和数目可以变化的 2）进程可以的任意的顺序创建和变化 3）采用保守的方法来分配资源。 课题 二、处理机调度程序：选择一个调度算法，实现处理机调度。 设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。设计要求： 1）进程调度算法包括：时间片轮转法，短作业优先算法，动态优先级算法。2）可选择进程数量 3）本程序包括三种算法，用C语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。 课题 三、用多进程同步方法解决生产者-消费者问题 设计目的:通过研究Linux 的进程机制和信号量实现生产者消费者问题的并发控制.说明:有界缓冲区内设有20个存储单元,放入/取出的数据项设定为1-20这20个整型数.设计要求: 1)每个生产者和消费者对有界缓冲区进行操作后,即时显示有界缓冲区的全部内容,当前指针位置和生产者/消费者县城的标识符.2)生产者和消费者各有两个以上.3)多个生产者或多个消费者之间须有共享对缓冲区进行操作的函数代码.课题 四、设计虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1)先进先出算法（FIFO） 2)最近最久未使用算法（LRU）3)最佳置换算法（OPT） 课题 五、编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1)先来先服务算法（FCFS） 2)最短寻道时间优先算法（SSTF）3)扫描算法（SCAN） 4)循环扫描算法（CSCAN） 课题 六、编程模拟多进程共享临界资源： 要求产生3个进程： 1)两个进程模拟需要进入临界区的用户进程，当需要进入临界区时，显示：“进程x请求进入临界区…”，同时向管理进程提出申请；申请返回，表示进入了临界区。在临界区中等待一段随机时间，并显示：“进程x正在临界区…”；当时间结束，显示：“进程x退出临界区…”,同时向管理进程提出退出申请；当申请返回，显示：“进程x已退出临界区。” 2)一个进程作为原语的管理进程，接受其他进程的临界区进入请求：如果允许进入，则设置相应变量，然后返回；如果不允许进入，则进入循环等待，直到允许为止； 3)对临界区的访问应遵循空闲让进、忙则等待、有限等待、让权等待的准则。4)进程间通信可以采用信号、消息传递、管道或网络通信方式。 课题七:为LINUX 设计一个简单的二级文件系统。要求做到以下几点： 1)可以实现下列几条命令（至少4条）。 Login 用户登录 Dir 列文件目录 Create 创建文件 Delete 删除文件 Open 打开文件 Close 关闭文件 Read 读文件 Write 写文件 2)列目录时要列出文件名、物理地址、保护码和文件长度。3)源文件可以进行读写保护。 课题八:存储管理---动态分区分配算法的模拟： 要求设计主界面以灵活选择某算法，且以下算法都要实现：首次适应算法、循环首次适应算法、最佳适应算法； 课题九:编程演示三种存储管理方式的地址换算过程： 1)分页方式的地址换算 分段方式的地址换算 3)段页式的地址换算 要求演示正确、清晰，编程所用工具不限。 课题 十、编写一个简单的端口扫描程序 目的：熟悉linux下socket、网络编程的基本方法； 任务：编写一个简单的程序，该程序可扫描局域网的某计算机开放了哪些端口； 课题 十一、编写一个基于TCP协议的客户/服务器程序 目的：熟悉linux下socket、网络编程的基本方法，掌握实现客户/服务器程序的编写方法； 任务：编写一个简单的程序，该程序可实现基于TCP协议的简单的客户/服务器方式。 课题 十二、编写一个使用数据报套接字的客户/服务器程序 目的：熟悉linux下socket、网络编程的基本方法，掌握客户/服务器程序的编写方法； 任务：编写一个简单的程序，该程序使用数据报套接字实现简单的客户/服务器方式。课题 十三、在linux平台编写一个简单的网络监听程序 目的：熟悉网络数据包格式，熟悉捕获网络数据包的基本方法 任务：在linux平台编写一个简单的网络监听程序，该程序能捕获网络数据包，并根据需要分析相应的数据包。 课题 十四、编写一个简单的内核模块。 目的：动态可加载内核模块是我们动态扩展内核功能的一种方便灵活的方式，可用来实现一种文件系统、一个驱动程序、或其它内核上层的功能。基本要求： 1)该模块至少需要有两个函数:一个是init_module()函数，在把模块装载到内核时被调用,向内核注册模块所提供的新功能;另一个是cleanup module()函数，在卸载模块时被调用，其任务是清除init_module()函数所注册的功能。编写完成后进行该模块的编译、装载和卸载操作。编写一个用户空间的程序来测试是否成功。 2)进一步的要求：向上面模块中再添加一些自己设计实现的新函数新功能；编写一个用户空间的程序来测试你的模块能否实现自己添加的功能。 课题 十五、编写一个简单的命令解释器—模拟shell功能 基本要求 1)可打开提示符，并获取用户输入的指令可解析指令 3)可寻找命令文件 4)可执行基本的命令 课题 十六、实现系统状态监测工具 目的：实现程序，通过获取/proc文件系统所提供的系统信息，检查系统当前的各种状态信息。要求：通过在命令行运行该程序，可获取以下信息： 1)CPU类型、型号、内核版本等信息从系统启动至今的时间等 3)内存总容量及当前可用内存量 4)系统平均负载 5)支持的文件系统类型 6)系统正在使用的module信息 附件2：课程设计题目 1.中文输入法程序 2.文件管理系统 3.线程管理 4.Windows进程多种同步案例演示 5.各种Window或Linux驱动程序编程 6.基于共享内存的进程之间的通信 7.文件加密 8.PE文件结构解析 9.异常处理系统 10.作业管理 11.中断驱动程序 12.可执行程序的加壳和脱壳 13.LRU动态内存管理模拟 14.注册表管理程序 15.内存管理程序 16.多系统启动程序 17.CPU的保护运行模式切换操作 18.扫描病毒算法模拟 19.木马扫描算法 20.硬盘碎片清理程序 21.程序卸载工具 22.文件系统FAT、NTFS、光盘、U盘分析程序 23.程序补丁 24.程序插件 25.文件压缩程序 26.文件备份系统 27.文件切割和组合 28.CPU参数监控程序 29.进程监控工具 30.文件系统搜索 31.系统监控软件 32.计算机看门狗 33.文件同步软件 34.个人信息同步软件 35.DLL文件创建和安装 36.小型操作系统编写 37.虚拟光驱软件 38.网络端口监测 39.内存管理——页面置换算法 附录3：课程设计封皮 仲恺农业技术学院 课程设计报告 课程名称：操作系统 实验题目：TCP/IP编程-网络聊天 院 系：计算机科学与工程学院 班 级： 2011级 ***班 姓 名： 张幸平学 号： ************* 二○○八年七月二十日第三篇：操作系统课程设计
第四篇：操作系统课程设计
第五篇：操作系统课程设计教学大纲
点击咨询 