操作系统课程设计Linux下进程调度算法的模拟实现

1、枣 庄 学 院信息科学与工程学院课程设计任务书 题目： linux下进程调度算法的模拟实现 学 生1： 学 生2： 学 生3： 专 业： 计算机应用技术 课 程： 操作系统 指导教师： 职称： 副教授 完成时间： 2015年 12月-2016 年 1月枣庄学院信息科学与工程学院制2015年12月20日课程设计任务书及成绩评定课程设计的任务和具体要求操作系统课程设计是操作系统课程学习的延续。主要目的是配合操作系统课程的学习，对linux操作系统有一定掌握，能够熟练操作，并能在linux系统下模拟实现操作系统的功能，有助于对操作系统的理解。本次课程设计共分两部分，其中第一部分为操作题，同学们需要对

2、linux的基本的命令（常用的几个，讲课的时候强调的），这部分，任课教师实时检查，让学生用命令完成一定的功能，然后，根据完成情况评定成绩。第二部分为编程设计题，每组同学必须独立完成，可以选择进程调度，也可以根据自己的兴趣，选择模拟实现磁盘调度、银行家算法、页面置换算法等。指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等软件: vc 6.0 windows xp上的虚拟机上运行的red hat linux硬件: cpu，主频1ghz以上；内存512m以上；硬盘30g以上；1024768显示分辨率课程设计进度计划起至日期工作内容备注12月1日12月4日1

3、2月5日12月8日12月9日12月12日12月13日12月17日搜集课程设计资料以及整理课程设计算法思路。在linux环境下熟悉相关指令的功能对两种算法程序进行设计，调试，运行。对前面的工作进行整合，写课程设计。参考文献、资料索-引序号文献、资料名称编著者出版单位1严蔚敏, 吴伟民. 数据结构. 清华大学出版社, 2005.112谭浩强. c语言程序设计. 清华大学出版社, 2005.113汤小丹, 梁红兵, 哲凤屏, 汤子瀛. 计算机操作系统. 西安电子科技大学出版社, 2007.519目 录1. 引言32. 常用基本命令介绍42.1 linux目录管理有关命令42.2 更改目录或文件访问权

4、限的命令52.3 显示文件内容的命令72.4 文件管理命令93. 进程调度程序的设计93.1进程调度介绍93.2 进程调度算法103.3 程序的设计思路103.4程序代码113.5程序及运行情况154. 实验过程中出现的问题及解决方法175. 总结171. 引言 linux是一套免费使用和自由传播的类 unix操作系统，它主要用于基于 intel x86系列 cpu的计算机上。这个系统是由世界各地的成千上万的程序员设计和实现的。其目的是建立不受任何商品化软件的版权制约的、全世界都能自由使用的 unix兼容产品。 linux的出现，最早开始于一位名叫 linus torvalds的计算机业余爱好

5、者，当时他是芬兰赫尔辛基大学的学生。他的目的是想设计一个代替 minix（是由一位名叫 andrew tannebaum的计算机教授编写的一个操作系统示教程序）的操作系统，这个操作系统可用于 386、 486或奔腾处理器的个人计算机上，并且具有 unix操作系统的全部功能，因而开始了 linux雏形的设计。 linux以它的高效性和灵活性著称。它能够在 pc计算机上实现全部的 unix特性，具有多任务、多用户的能力。 linux是在 gnu公共许可权限下免费获得的，是一个符合 posix标准的操作系统。 linux操作系统软件包不仅包括完整的 linux操作系统，而且还包括了文本编辑器、高级语

6、言编译器等应用软件。它还包括带有多个窗口管理器的 x-windows图形用户界面，如同我们使用 windows nt一样，允许我们使用窗口、图标和菜单对系统进行操作。 linux相对于windows的许多变化都是有益的。空闲的gui的开销被归还给服务。任务可以脚本化并可以自动执行。配置文件基于文本并且人类可读。在大多数情况下不必重新引导系统,linux还有很多好处，总之，能够很好地掌握linux的使用是非常必要的。2. 常用基本命令介绍2.1 linux目录管理有关命令命令一般格式: 命令名 -选项 参数对每个命令掌握: a.命令名 b.命令功能 c.命令格式 d.常用参数（1）pwd -显示

7、当前工作目录的绝对路径格式: pwd （2） cd -改变当前工作目录 命令格式：cd 目录名 (3) ls- 列出文件目录的信息 命令格式：ls 可选项 子目录名 文件名 与dos的cd命令类似; 当前目录/绝对路径/相对路径可选项: -a ：列出全部的文件，包括那些隐藏文件.-l ：按长格式列目录，输出信息包括文件目录，文件的权限、所属用户组、文件建立和修改的时间等信息。 -d ：只列出子目录信息。 -o ：用不同颜色显示各种类型的文件，蓝色表示子目录、绿色表示可执行文件、红色表示压缩文件、浅蓝色表示连接文件、灰色表示其它文件。 (4) mkdir - 建立目录 命令格式：mkdir 可选

8、项 目录名 可选项：-m ：设置目录的存取权限，这也可以在目录建立后用命令chmod 来设定。-p ：如果连续建立两级以上的目录，例如原来只有/usr/srcp目录，可以输入：mkdir p /usr/inin/mors/cs。(5) rmdir -删除目录 本命令用于删除指定的一个或多个目录，必须保证要删除的目录中没有任何文件。命令格式：rmdir 可选项 目录名 可选项：-p ：如果删出一个目录后，它的上一层目录也变为空目录了，这个选项会一并删除上一层也变为空的目录。-verbose ：为每一个创建的目录显示一条信息。 通配符的使用与windows类似: *,?. 如:1-9* -所有以1

9、-9中任意一个字符开头的文件 1,3,5* - 所有以1或3或5开头的文件 2.2 更改目录或文件访问权限的命令linux中的访问权限 在linux中，对目录访问的用户分为三种：目录属主（u表示）、目录属主所在组的用户（g表示）、其他用户（o表示）。对文件访问有三种不同类型的用户：文件所有者，同组用户、其他用户。目录或文件的权限就是这三种用户对目录或文件进行访问时的权限。 每种用户的权限进一步细分为读，写和可执行三种，分别用r 、w、 x表示。每一文件或目录的访问权限都有三组，每组用三位表示 例如: ls l 某文件 可列出该文件的三组访问权限file1 rwxurwxgrw-or- ls-查

10、看访问权限格式: ls l 文件名# ls l sobsrc.tgz -rw-rr1 root root 483997 ju1 l5 17:3l sobsrc.tgz 文件类型 权限 链接数 文件属主 文件组 文件大小 时间 文件名确定了一个文件的访问权限后，用户可以利用linux系统提供的chmod命令来重新设定不同的访问权限。也可以利用chown命令来更改某个文件或目录的所有者。利用chgrp命令来更改某个文件或目录的用户组。 chmod -改变文件或目录的访问权限 命令格式：chmod 可选项 权限 目录或文件名 可选项: -v ：报告权限更改信息； -c ：每次发生权限的实质性更改时给

11、出一条信息。 (1) 文字设定法格式:chmod who + |-|= mode 文件名 | 目录名 who: uuser ggroup oothers aall+ 添加 - 取消 = 赋予给定权限并取消其他所有权限 例如: $chmod g+r,o+r example (2) 数字设定法用八进制数07来表示一组“rwx”权限,如6表示rw-首先规定 0表示没有权限; 1表示可执行权限; 2表示写权限; 4表示可读权限 然后将四个数相加,其指范围为07例如: # chmod 644 temp1.txt 相当于 chmod u=rw,g=r,o=r temp1.txt(3) chgrp命令 -改

12、变文件或目录所属的组。 命令格式：chgrp 选项 group filename选项： -r：递归式地改变指定目录及其下的所 有子目录和文件的属组 例：命令：$ chgrp r book /opt/local /book 功能：改变/opt/local /book/及其子目录下的所有文件的属组为book。 (4) chown -更改某个文件或目录的属主和属组 命令格式：chown 选项 文件或目录的新属主.文件或目录所在的新组 文件名|目录 选项: -r ：递归地改变指定目录及其下的所有目录和文件的拥有者 -v ：显示chown命令所作的工作。 2.3 显示文件内容的命令（1）cat -显示，

13、新建，连接文件功能1：新建文件 功能2：在标准输出上显示文件 格式：cat -选项 文件选项：-v 用一种特殊形式显示控制字符，lfd与tab除外。加了-v选项后，-t和-e选项将起作用。-t 将tab显示为“ i”。该选项需要与-v选项一起使用。即如果没有使用-v选项，则这个选项将被忽略。-e 在每行的末尾显示一个符。该选项需要与-v选项一起使用。 -a 等于-vte。-b 系统会在文件每一非空白行前加入编号，以便识别。功能3：连接两个或多个文件 （2） more -在终端屏幕按屏显示文本文件。 命令格式： more - 选项 文件 说明： 该命令一次显示一屏文本，显示满之后，停下来，并在终

14、端底部打印出- - more- - ，系统还将同时显示出已显示文本占全部文本的百分比，若要继续显示，按回车或空格键即可。 选项： - p 显示下一屏之前先清屏。 - c 先从最顶端显示，在清除每行后剩余的旧内容，可使显示加快。 - d 在每屏的底部显示更友好的提示信息： - - more- - （xx%）press space to ontinue , q to quit . 而且若用户输入了个错误命令则显示出错信息，而不是简单地鸣响终端。 在more命令的执行过程中，用户可以使用more自己的一系列命令动态地根据需要来选择显示的部分。more在显示完一屏内容之后，将停下来等待用户输入某个命令

15、。下表列出了more指令在执行中用到的一些常用命令，而有关这些命令的完整内容，可以在more执行时按h查看。这些命令的执行方法是先输入i（行数）的值，再打所要的命令，不然它会以预设值来执行命令。 i空格 若指定i，显示下面的i行；否则，显示下一整屏。如：5空格，即显示下面的5行。 i回车 若指定i，显示下面的i行；否则，显示下一行。 iz 同“i空格”类似，只是i将成为以下每个满屏的缺省行数。 is 跳过下面的i行再显示一个整屏。预设值为1。如：3s，即跳过下面的3行显示整屏。 命令：if 跳过下面的i屏再显示一个整屏。预设值为1。 q或q 退出more。 = 显示当前行号。 v 在当前行启动

16、/usr/bin/vi对之进行编辑修改。 h 显示各命令的帮助信息。 i:f 显示当前文件的文件名和行数。 .（点） 重复上次键入的命令。 (3) less less命令的功能几乎和more命令一样，也是用来按页显示文件，不同之处在于less命令在显示文件时允许用户既可以向前又可以向后翻阅文件。 less命令的功能几乎和more命令一样，也是用来按页显示文件，不同之处在于less命令在显示文件时允许用户既可以向前又可以向后翻阅文件。(4) head-显示文件或标准输入的头几行 命令格式：head - n 文件 该命令显示每个指定文件的前面n行。如果没有给出n值，缺省设置为10。如果没有指定文件

17、，head就从标准输入读取。 (5) tail-显示文件的尾部 命令格式：tail + / - num 参数 文件 说明：该命令显示一个文件的指定内容。它把指定文件的指定显示范围内的内容显示在标准输出上。本命令特别适用于阅读一个有用信息在其尾部的大文件，如系统信息中的出错记录文件（/var/log/message）。 选项： num 从第num行以后开始显示。 - num 从距文件尾num行处开始显示。如果省略num参数，系统默认值为10。 参数l： 以文本行为num的计数单位。与参数选项num或- num选项同时使用时，num表示要显示的文本行行数。 参数c： 以字节为num的计数单位。与参

18、数选项num或- num选项同时使用时，num表示要显示的字符数。2.4 文件管理命令(1) touch -功能：将文件的修改时间改为当前时间，如果文件不存在则建立一个空文件。 命令格式： touch - 选项 文件 (2) cp -功能：文件或目录的拷贝 ，如同dos的copy 命令格式： cp 选项 源文件或目录 目标文件或目录 -a 该选项通常在拷贝目录时使用。它保留链接、文件属性，并递归地拷贝目录，其作用等于dpr选项的组合。 - d 拷贝时保留链接。 - f 删除已经存在的目标文件而不提示。 - i 和f选项相反，在覆盖目标文件之前将给出提示要求用户确认。回答y时目标文件将被覆盖，是

19、交互式拷贝。 - p 此时cp除复制源文件的内容外，还将把其修改时间和访问权限也复制到新文件中。 - r 若给出的源文件是一目录文件，此时cp将递归复制该目录下所有的子目录和文件。此时目标文件必须为一个目录名。 - l 不作拷贝，只是链接文件。 (3) mv -功能：为文件或目录改名或将文件由一个目录移入另一 个目录中 命令格式： mv 选项 源文件或目录 目标文件或目录 (4) rm -功能：删除一个目录中的一个或多个文件或目录，它也可以将某个目录及其下的所有文件及子目录均删除 命令格式： rm 选项 文件 选项：- f 忽略不存在的文件，从不给出提示。 - r 指示rm将参数中列出的全部目

20、录和子目录均递归地删除。 - i 进行交互式删除。3. 进程调度程序的设计3.1进程调度介绍进程调度是内核重要的组成部分，运行着的进程首先在使用计算机。要设计一个可以满足各种需求的调度算法是不现实的。不过linux内核的新调度程序尽量满足各个方面，并以较完善的可伸缩性位所有情况提供了比较好的解决方案。3.2 进程调度算法(1) 先来先服务调度算法(2) 进程优先调度算法(3) 时间片轮转算法3.3 程序的设计思路（1）先来先服务调度算法 先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最

21、先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用fcfs算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。fcfs算法比较有利于长作业（进程），而不利于短作业（进程）。（2）进程优先调度算法 短作业（进程）优先调度算法sj（p）f，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（sjf）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（spf）调度算法则是从就绪队列中选出一

22、个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。sj(p)f调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。（3）时间片轮转算法 在时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把cpu分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列

23、中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。3.4程序代码#include#include #include typedef struct pcb int name; int needtime; int arrivetime; int pri; int state; int cputime;plist;void action(plist * nowpro);void action(plist * nowpro) delay(1000); printf(now is process %d ,nowpro-name); nowpro

24、-needtime-; if(nowpro-needtime=0) printf( the process %d is endn,nowpro-name); /* nowpro-state=1; */ printf(-n); else printf(process %d needtime is %dn,nowpro-name,nowpro-needtime); printf(-n); void creatpro(int n,plist * process ) int j; for(j=0;jn;j+) = j; processj.needtime=rand()%10+

25、1; processj.arrivetime=rand()%10; processj.pri=rand()%4; processj.state=0; processj.cputime=0; void show( int n,plist * process) int j; for (j=0 ;jn;j+) printf(name of process%dt,); printf(needtime %dt,processj.needtime); printf(arrivetime %dt,processj.arrivetime); printf(pri %dn,proces

26、sj.pri); printf(state %dt,processj.state); printf(cputime %dn,processj.cputime); void main() void creatpro(int n,plist * process ); void show( int n,plist * process); void fcfs(int n,plist * process); void sjf(int n,plist * process); void rr(int n,plist * pro1); void hrrn(int n,plist * pro1); int n;

27、 /*the number of process*/ int k; plist process10; printf(please input the number of process from 0 to 10n); scanf(%d,&n); creatpro(n,process); show(n,process); printf(please choose the what you want to usen); printf(1 fcfst 2 sjft 3 hrrnt 4 rrn); scanf(%d,&k); switch(k) case 1: fcfs(n,process); bre

28、ak; case 2: sjf(n,process); break; case 3: hrrn(n,process); break; case 4: rr(n,process); break; default : break; getch();void fcfs(int n,plist * pro1) void show( int n,plist * process); int i,j,k; int m=0; int time; plist temp; plist pro210; for(i=0;in;i+) k=0; while(pro1k.state=1) k+; temp=pro1k;

29、for(j=k+1;jpro1j.arrivetime&pro1j.state!=1) temp=pro1j; k=j; pro2m+=temp; pro1k.state=1; show(n,pro2); for(i=0;i0) action(&pro2i); void sjf(int n,plist * pro1) void show( int n,plist * process); int i,j,k; int m=0; plist temp; plist pro210; for(i=0;in;i+) k=0; while(pro1k.state=1) k+; temp=pro1k; for(j=k+1;jpro1j.needtime&pro1j.state!=1) temp=pro1j; k=j; pro2m+=temp; pro1k.state=1; show(n,pro2); for(i=0;i0) action(&pro2i); void rr(int n,plist * pro1) void show( int n,plist * process); int i,j,k; int m=0; int time; plist temp; plist pro210; for(i=0;in;i+) k=0; while(pro1k.stat