第一篇:操作系统课程设计题目及代码
题目一
模拟操作系统设计
设计一个模拟操作系统管理程序,实现下列管理功能: 1.内存管理功能 2.文件管理功能 3.磁盘管理功能
题目二
虚拟存储器各页面置换算法的实现与比较 内 容:设计一个虚拟存储区和内存工作区,通过产生一个随机数的方法得到一个页面序列,假设内存给定的页面数由键盘输入,分别计算使用下述各方法时的内存命中率:
先进先出算法(FIFO)、最近最少使用算法(LRU)、最佳淘汰算法(OPT)、最少访问页面算法(LFU)等。
参考资料
题目二
资料
虚拟存储器各页面置换算法的实现与比较
1.实验目的
存储管理的主要功能之一是合理的分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。2.实验内容
(1)通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成: 1)50%的指令是顺序执行的;
2)25%的指令是均匀分布在前地址部分; 3)25%的指令是均匀分布在后地址部分; 具体的实施方法是:
1)在[0,319]的指令地址之间随机选取一起点m; 2)顺序执行一条指令,即执行地址为m+1的指令;
3)在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m'; 4)顺序执行一条指令,其地址为m'+1;
5)在后地址[m'+2,319]中随机选取一条指令并执行; 6)重复上述步骤1)-5),直到执行320次指令。(2)将指令序列变换成为页地址流 设:1)页面大小为1k;
2)用户内存容量为4页到32页; 3)用户虚存容量为32k; 在用户虚存中,按每k存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为: 第0条-第9条指令为第0页(对应虚存地址为[0,9]); 第10条-第19条指令为第1页(对应虚存地址为[10,19]);
...第310条-第319条指令为第31页(对应虚存地址为[310,319]);
按以上方式,用户指令可组成为32页。
(3)计算并输出下列各种算法在不同内存容量下的命中率。1)先进先出的算法(FIFO); 2)最近最少使用算法(LRR);3)最佳淘汰算法(OPT):先淘汰最不常用的页地址; 4)最少访问页面算法(LF.U); 5)最近最不经常使用算法(NUR)。其中3)和4)为选择内容。命中率=1-页面失效次数/页地址流长度
在本实验中,页地址流长度为320,页面失效次数为每次访问相应指令时,该指令所对应的页不在内存的次数。3.随机数产生办法
关于随机数产生办法,Linux或Unix系统提供函数srand()和rand(),分别进行初始化和产生随机数。例如: srand();
语句可初始化一个随机数; a[0]=10*rand()/32767*319+1;a[1]=10*rand()/32767*a[0];
..语句可用来产生a[0]与a[1]中的随机数。
提示:
首先用Srand()和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的命中率。
命中率=1-页面失效次数/页地址流长度
1、数据结构
(1)页面类型 typedef struct{
int pn,pfn,counter,time;}pl-type;
其中pn为页号,pfn为页面号,count为一个周期内访问该页面的次数,time为访问时间。
(2)页面控制结构 pfc_struct{
int pn,pfn;
struct pfc_struct *next;
};typedef struct
pfc_struct pfc_type;pfc_type
pfc[total_vp],*freepf_head,*busypf_head;pfc_type *busypf_tail;其中,pfc[total_vp]定义用户进程虚页控制结构,*freepf_head为空页面头的指针,*busypf_head为忙页面头的指针,*busyf_tail为忙页面尾的指针。
2、函数定义
(1)Void initialize():初始化函数,给每个相关的页面赋值。(2)Void FIFO():计算使用FIFO算法时的命中率。(2)Void LRU():计算使用FIFO算法时的命中率。(4)VoidOPT():计算使用OPT算法时的命中率。(5)Void LFU():计算使用LFU算法时的命中率。(6)Void
NUR():计算使用NUR算法时的命中率。
3、变量定义
(1)int a[tatal_instruction] :指令流数据组。
(2)int page[total_instruction]:每条指令所属页号。
(3)int offset[total_instruction]:每页装入不敷出0条指令后取模运算页号偏移量。(4)int total_pf:用户进程的内存页面数。(5)int diseffect:页面失效次数。
程序清单
程序: 程序: #include “stdio.h” #include “process.h” #include “stdlib.h” #define TRUE 1 #define FALSE 0 #define INVALID-1 #define null 0 #define total_instruction 320 /*指令流长*/ #define total_vp 32 /*虚页长*/ #define clear_period 50 /*清0周期*/ typedef struct { int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp];/*页面数据结构*/ struct pfc_struct{ /*页面控制结构*/ int pn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect,a[total_instruction];int page[total_instruction],offset[total_instruction];void initialize();void FIFO();void LRU();void OPT();void LFU();void NUR();main(){ int S,i,j;srand(getpid()*10);/*由于每次运行时进程号不同,故可用来作为初始化随机数队
列的种子*/ S=(float)319*rand()/32767+1;for(i=0;i
busypf_head=busypf_tail=freepf_head;else {busypf_tail->next=freepf_head;busypf_tail=freepf_head;} freepf_head=p;} } printf(“FIFO:%6.4”,1-(float)diseffect/320);} void LRU(total_pf)/*LRU*/ int total_pf;{ int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i 1、操作系统实验教程 张丽芬编著 清华大学出版社 2、操作系统原理实验教程(基于Linux)胡峰松编 清华大学出版社 辽宁科技大学操作系统课程设计指导书 一、课程设计目的和要求 本设计是专业基础课《操作系统》的课程设计。由于操作系统课的学时有限,安排实验的次数不多。为了进一步巩固实验成果,加强理论联系实际、分析问题、解决问题的能力,加深对操作系统的基本概念、原理、技术和方法的理解,特安排此次课程设计。它是操作系统课程的实践环节。由于具体的操作系统相当复杂,在短短的一周之内,不可能对所有管理系统进行详细地分析。因此,选择了操作系统中最重要的管理之一进程管理(或进程的死锁、页面置换算法)作为本设计的任务。另外,通过此次设计使学生在使用系统调用的同时,进一步了解系统内部是如何实现系统调用的全过程,使学生在更深层次上对操作系统有所了解。要求: 1.在具有自主版权的Linux环境下,用c或c++语言,以及相关的系统调用,编程实现进程的创建、控制、软中断通信、管道通信等功能。2.利用某种高级语言编程实现银行家算法。 3.常用的页面置换算法有:最佳置换算法(Optimal)、先进先出法(Fisrt In First Out)、、最近最久未使用(Least Recently Used),至少实现其中的两种算法。 二、课程设计内容 设计题目1:进程管理及理解(1)进程的创建 编写一段程序,使用系统调用fork()创建两个子进程。当此程序运行时,在系统中有一个父进程和两个子进程活动。让每一个进程在屏幕上显示一个字符:父进程显示“a”;子进程分别显示字符“b”和“c”。试观察记录屏幕上的显示结果,并分析原因。 (2)进程的控制 修改已编写的程序,将每个进程输出一个字符改为每个进程输出一句话,再观察程序执行时屏幕上出现的现象,并分析原因。 如果在程序中使用系统调用lockf(),来给每一个进程加锁,可以实现进程之间的互斥,观察并分析出现的现象。 (3)①编制一段程序,使其实现进程的软中断通信。 要求:使用系统调用fork()创建两个子进程,再用系统调用signal()让父进程捕捉键盘上来的中断信号;当捕捉到中断信号后,父进程用系统调用kill()向两个子进程发出信号,子进程捕捉到信号后分别输出下列信息后终止: Child Process11 is Killed by Parent!Child Process12 is Killed by Parent! 父进程等待两个子进程终止后,输出如下的信息后终止: Parent Process is Killed! ②在上面的程序中增加系统调用signal(SIGINT,SIG_IGN)和signal(SIGQUIT,SIG_IGN),观察执行结果,并分析原因。 (4)进程的管道通信 编制一段程序,实现进程的管道通信,使用系统调用pipe()建立一个管道文件;两个子进程P1和P2分别向管道各写一句话: Child1 is sending a message!Child2 is sending a message! 而父进程则从管道中读出来自于两个子进程的信息,显示在屏幕上。 要求父进程先接收子进程P1发来的消息,然后再接收子进程P2发来的消息。设计题目2:银行家算法实现资源分配 要求如下: (1)进程可动态地申请资源和释放资源,系统按各进程的申请动态地分配资源。(2)要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列的功能。(3)显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。 (4)可能用到的数据结构: 可利用资源向量Available。它是一个含有m个元素的数组,其中每个元素代表一类可利用资源的数目。 最大需求矩阵Max。n*m矩阵,表示n个进程的每一个对m类资源的最大需求。 分配矩阵Allocation。n*m矩阵,表示每个进程已分配的每类资源的数目。 需求矩阵Need。n*m矩阵,表示每个进程还需要各类资源数。设计题目3:虚拟页面置换算法的实现 要求如下: (1)至少实现OPT、FIFO、LRU三种置换算法中的两种。 (2)做成GUI界面最好,若不能,则要求界面尽量友好,便于操作。(3)算法中涉及到的页面访问序列可以固定,也可以随机生成。 (4)在实现算法的同时要计算每种算法的缺页数。(5)以表格的形式输出最终的页面置换结果。 注:以上三个题目任选其一,还可以自拟其它题目。 选择题目1的同学,应事先了解(1)Linux的命令及使用格式; 可通过下面的几个任务熟悉有关文件(夹)操作的命令。 (2)在虚拟机vmware下让Linux加载U盘的方法。 (3)利用gcc、gdb编译、调试C/C++程序 操作系统课程设计要求 一.设计目的 熟悉Linux编程环境,加强对Linux命令的理解及函数的运用 二.设计内容 1.在Linux环境下模拟实现简单命令解释器。(1)要求实现的基本命令包括: pwd //显示当前所在目录的路径名 dir <目录名> //列出指定目录名中的所有目录及文件 cd <目录名或路径> //改变当前工作目录 newdir <目录名> //新建目录 deldir <目录名> //删除目录 exit //退出命令解释程序(2)可选做的扩展命令包括: rename <旧文件名> <新文件名> //重命名一个文件或目录 find <目录>-name <待查找的文件名> //在指定的目录及其子目录中查找指定的文件 date //显示当前日期(3)提示:整个程序的大致框架可参考如下: while(exit未被输入){ 接收键盘的一行输入 分析输入的命令 对输入的命令进行处理,调用系统函数实现功能 } 2.设计要求 (1)设计必须在Linux环境下进行。 (2)命令解释程序的提示符为:姓名拼音@(3)程序编写中不得使用system()系统调用。 (4)整个程序必须严格经过测试,完成所有基本功能。源程序应有较详尽的注释。 3.可能用到的系统调用: open(),close(),read(),write(),creat()chdir(), opendir(),readdir(),rewinddir(),closedir(),rmdir(),mkdir()getcwd(), ftw() time(), localtime(), asctime()三. 提交要求: 1.完成的源程序和可执行程序必须保存在Linux服务器上。 2.要求实现的基本命令必须全部实现。完成可选做的扩展命令将得到较高的分数。容错性强和功能细节考虑更完全也将得到较高的分数。 3.每位同学必须完成操作系统课程设计说明书并上交纸质打印版(不少于3000字),设计说明书格式请从ftp下载《操作系统课程设计说明书(模板)》查看。(学习委员收齐后交到老师办公室)。说明书电子版提交到老师的FTP 11计算机2班的同学: 交给韦婷老师 说明书电子版提交到:ftp://we:345678@10.5.1.请提交到该ftp的“/作业/操作系统课程设计/”文件夹中 每位同学的课程设计说明书按以下格式命名: “班内序号-姓名.doc” 例如:05-李凯.doc 4.独立完成,不得抄袭,凡是发现抄袭的(无论抄与被抄者),均不及格。5.课程设计上交截止日期: 11月12 日 6.设计提交后将抽取一部分同学进行答辩,答辩时间另行通知。 注意: 1.Linux服务器远程连接方式:telnet 10.5.1.6(telnet连接服务器的过程可能需要十几秒,属正常现象,请耐心等待)2.登陆的用户名和密码 11计算机2班的同学: 用户名:112班内序号 例如: 11计算机2班的5号同学的用户名是:11205 初始密码:123456 3.在Linux环境编程,若要使用cin、cout,则必须用 #include 4.本课程设计所需资料从ftp://we:345678@10.5.1.5 “/下载/操作系统课程设计/” 文件夹中下载。 操作系统代码 1,查询航班:AVH/紧跟输入城市段、日期(数字)、月份(英文)后回车查看。如果查询指定航空公司月份后加“/”再加航空公司代号。 2,订座:SD后紧跟序号计划预定仓位跟人数后回车。(如果显示JET代表待定航班) 3.人名:NM1后紧跟客人姓名,如果多个个客人,人名雨人名之间用数字1隔开(国际航班必须输入英文,中国人姓在前后加/,外国人名在前) 4,联系方式:CT后输入联系电话 5,预留时间:TKTL/后跟几点/日期月份BJS…(代码) 6,封口:@IK(封口号码为5位数字) 7,提记录:RT后紧跟封口号码 8,取消订票:XEPNR 9,价格查询:FD:城市段(只使用于国内查询)PAT:A 查国内税和价格 10:查询那些航空公司飞:SKPEK紧跟目的地 11,查询指定日期直达航班:AV:城市段/日期月份 12,查询经停点:IT:航班号/日期月份 13,查询航班经停的城市起降时间和机型:FF:航班号/日期月份(没有经停的不显示)14,查税(价格):QTE:/承运人(航空公司)(必须输入完行程封口或达到上面第二步),如果出来很多仓位,在输入XSFSQ后跟代表仓位代码的序号。(共享的航班不能查税)15, 查询学生机票的税和价格QTE:SD/航空公司 16,查询移民机票价:QTE:EM/航空公司 17,查询青年机票价格:QTE:ZZ/航空公司 18,OPE票的预定指令:SN:承运人---舱位---出发地与目的地 19,查询SPA价格的指令:NFAD:城市段/CA(只能用于国航联运协议的航空公司。国际段的查询) 20,查汇率:XS(空格跟FSC后跟币种代码/人民币(可以互换) 21,查代码代表城市:CD:跟城市代码 22,用姓名查找记录:RT/旅客姓的拼音/航班号/日月年 23,SK:城市段/日期 查询在特定周期内所有航班的信息,所显示的航班信息时间为指定时间的前后三天一周的时间 24,查看是否出票:提记录后,输入PG1回车,有票号证明已经出票完毕。 25,查询国际段航班价格指令:XSFSD(空格)行程/日期/航空公司,如果后加X,最便宜的会显示在最前面。 26,如果没有舱位需要候补舱位:SD后跟序号在跟舱位/LL后跟人数 CP全清屏I清上次屏PN下翻PB上翻PF最前页PG重新显示当前页PL最后页。Q值的计算方法:Q值乘以兑换率。(如果使用系统里票面价格的时候不用单独计算Q值,因为系统里的报价已经包含全部费用,如果使用促销价即不使用系统里显示的价格的时候要计算Q值再加税) 学生票:LH的Q舱位UA的V舱位 大部分情况下代表学生票 外航(例如:AC,UA,NW等)大部分是Q票面,(国际段的价格票面应该以做境外段的票务公司报出的价格为准)国航的价格看系统或大本政策。去往北美洲国航联运的比较AC,UA等转机的价格略高。去往欧洲的国航相对法航的要便宜,HU飞日本韩国便宜 去往东南亚国家南航便宜,北京去往韩国MU,北京到香港CZ便宜 操作系统课程设计 注意事项: 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个物理块,使用程序的动态页面序列生成算法,生成一个页面序列,将此序列存入磁盘文件。再从磁盘文件读入该序列,用程序分别计算三种算法下的缺页中断次数、缺页中断率和缺页调度次数、缺页置换率。第二篇:操作系统课程设计题目
第三篇:《操作系统课程设计》题目要求
第四篇:机票操作系统代码
第五篇:操作系统课程设计