操作系统实验指导书

1、 操作系统原理实验指导书羊四清 编 写适用专业： 计算机科学与技术 网络工程 湖南人文科技学院计算机科学技术系 2008年 8 月前 言操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生开设的一门计算机专业课程。操作系统是计算机系统的核心，操作系统课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统实验是操作系统课程的重要组成部分，属

2、于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业必修的专业基础课程，操作系统实验的作用是：理解操作系统的设计和实现思路，掌握典型算法。基本要求是：理解进程的概念，理解死锁，掌握银行家算法；掌握请求页式存储管理的实现原理及页面置换算法。学生应具有高级语言编程能力、具有数据结构等基础知识。说明：本实验指导书所提供的源程序均已在VC.下调试运行过目录实验一 进程创建模拟1实验二 进程撤销模拟9实验三 P、V 原语的模拟实现10实验四 带优先级的时间片轮换的进程调度算法的实现16实验五 银行家算法模拟26实验六 连续动态内存管

3、理模拟实现29实验七 请求页式存储管理中常用页面置换算法模拟31实验八 SCAN 磁盘调度模拟实现36实验九 UNIX基本操作37实验一 进程创建模拟实验学时：2实验类型：验证实验要求：必修一、实验目的1） 理解进程创建相关理论；2） 掌握进程创建方法；3） 掌握进程相关数据结构。二、实验内容本实验针对操作系统中进程创建相关理论进行实验。要求实验者输入实验指导书提供的代码并进行测试。代码简化了进程创建的多个步骤和内容。进程的树形结构采用广义二叉树的方式进行存储。三、实验原理1）进程控制块为了描述和控制进程的运行，系统为每个进程定义了一个进程控制块（PCB），它是进程实体的一部分，是操作系统管理

4、进程最重要的数据结构。其主要包含四类信息：(1) 进程标识符它唯一地标识一个进程。通常包括进程号 pid，父进程号 ppid 和用户号 uid。(2) 处理机状态处理器的状态通常由处理机的各种寄存器中的内容组成。PCB 存放中断（阻塞，挂起）时的各寄存器值，当该进程重新执行时，可以从断点处恢复。主要包括： a) 通用寄存器； b) 指令计数器； c) 程序状态字 PSW； d) 用户栈指针。(3) 进程调度信息 a) 进程状态； b) 进程优先级（用于描述优先使用 cpu 级别的一个整数，高优先级的进程先得到cpu，通常情况下，优先值越小优先级越高）； c) 其它信息（等待时间、总执行时间等）

5、； d) 事件（等待原因）。(4) 进程控制信息 a) 程序和数据的地址（程序在内存和外存中的首址）； b) 进程同步和通信机制； c) 资源列表（进程除 CPU 以外的所有资源）； d) 链接指针（进程队列中指向下一个进程的 PCB 首址）。2) 进程创建流程 (1) 申请空白 PCB 为新进程申请获得唯一的数字标识符，并从 PCB 集合中索取一个空白 PCB。如果无空白PCB，可以创建一个新的 PCB。在本实验中，每次动态创建 PCB。 (2) 为新进程分配资源 为新进程分配内存空间和栈空间。 (3) 初始化进程控制块 a) 初始化标识信息； b) 初始化处理机状态信息； c) 初始化处理

6、机控制信息。 (4) 将新进程插入就绪队列P1P2P3P4P5P6P7P8P9P10P11P12 3) 进程树 图 1-1 进程树 进程树用于描述进程家族关系，如图 1-1 中可以看出，进程 P1 创建了进程 P2、P3、P4、P5，而 P2 又创建了 P6、P7、P8 。在进程创建过程中，需要对每一个新增加的进程加入到进程树中，有了清晰的父子关系，可以使资源继承或进程删除等操作变得很方便。4) 进程总链它是一个 PCB 链表，每一个新创建的进程必须把其 PCB 放入总链中，该总链可以对破坏的进程树进行修复，也方便 PCB 查找。四、程序清单1.basic.h 文件#ifndef basic_

7、h#include<stdio.h>#include<string.h>#include<stdlib.h>#define basic_hchar *errormsg256;/process control blockstruct pcb int pid;/process id int ppid;/parent process id int prio;/priority int state;/state int lasttime;/last execute time int tottime; /totle execute time;/process node

8、struct pnode pcb *node; pnode *sub; pnode *brother; pnode *next;/信号量struct semphore char name5; /名称 int count;/计数值 int curpid;/当前进程 id pnode *wlist; /等待链表;#define geterror(eno) printf("%sn",errormsgeno) void initerror() errormsg0 = (char *)malloc(20); errormsg0="error command!" e

9、rrormsg1 = (char *)malloc(20); errormsg1="error parameter!"/get a substring in string schar * substr(char *s,int start,int end) char *s1; int len = strlen(s); if(start<0 | end>=len | start>end) return NULL; s1=(char *)malloc(end-start+2); for(int i=0;i<=end-start;i+) s1i = si+s

10、tart; s1i='0' return s1;/find the location of c in string sint instr(char *s,char c) unsigned i; for(i=0;i<strlen(s);i+) if(si=c) return i; return -1;/change the string to array dataint * strtoarray(char *s) int *a,count,x1; unsigned int i; char c, *s1,*s2; if(!s) printf("string can&

11、#39;t be null!n"); return NULL; count=0; s1=s; for(i=0;i<strlen(s1);i+) if(s1i=',') count+; count+; a = (int *)malloc(count); c=',' for(i=0;i<count;i+) x1 = instr(s1,c);if(x1>=0) s2=substr(s1,0,x1-1);else s2=s1;ai=atoi(s2);if(c=',') s1=substr(s1,x1+1,strlen(s1)-

12、1); return a;#endif2、源程序#include "basic.h"pnode *proot;/system process tree rootpnode *plink;/system process link head/create processint createpc(int *para) /add your code here pnode *p,*p1,*pp; int pflag; pflag=0; for(p=plink;p;p=p->next) if(p->node->pid = para0) /check if this p

13、id is already exist printf("pid %d is already exist!n",para0); return -1; if(p->node->pid = para1) /find parent pcb pflag=1; pp = p; if(!pflag) printf("parent id %d is not exist!n",para1); return -2; /init new pcbp1 = new pnode;p1->node=new pcb;p1->node->pid = para

14、0;p1->node->ppid = para1;p1->node->prio = para2;p1->sub=NULL;p1->next=NULL;p1->brother=NULL;/add to process treeif(!pp->sub) pp->sub=p1;else for(p=pp->sub;p->brother;p=p->brother); p->brother=p1;/ add to process linkfor(p=plink;p->next;p=p->next);p->ne

15、xt=p1;return 0;/show process detailvoid showdetail() /add your code here pnode *p,*p1; p=plink; for(;p;) /print all pcb info printf("%d(prio %d):",p->node->pid,p->node->prio); p1 = p->sub; for(;p1;) /print sub pcb printf("%d(prio %d)",p1->node->pid,p1->nod

16、e->prio); p1 = p1->brother; printf("n"); p = p->next; printf("n");/don't changevoid main() initerror(); short cflag,pflag; char cmdstr32; proot = new pnode; proot->node=new pcb; proot->node->pid=0; proot->node->ppid=-1; proot->node->prio=0; proot

17、->next=NULL; proot->sub=NULL; proot->brother=NULL; plink=proot; for(;) cflag=0; pflag=0; printf("cmd:"); scanf("%s",cmdstr); if(!strcmp(cmdstr,"exit") /exit the program break; if(!strcmp(cmdstr,"showdetail") cflag = 1;pflag = 1;showdetail(); else int

18、*para;char *s,*s1;s = strstr(cmdstr,"createpc"); /create process if(s) cflag=1; para = (int *)malloc(3); /getparameter s1 = substr(s,instr(s,'(')+1,strlen(s)-2); /get param string para=strtoarray(s1);/get parameter createpc(para); /create process pflag=1; if(!cflag) geterror(0); el

19、se if(!pflag) geterror(1); 五、实验步骤输入实验提供的代码后，可以输入 createpc 命令创建进程，输入 showdetail 显示每个进程及其子进程的信息，测试命令解释如下：1) createpc 创建进程命令。 参数： 1、 pid（进程 id） 2 、ppid（父进程 id）3、prio（优先级）。 示例：createpc(1,0,1) 。创建一个进程，其进程号为 1，父进程号为 0，优先级为 1.createpc(2,1,2) 。创建一个进程，其进程号为 2，父进程号为 1，优先级为 2。2) showdetail 显示进程信息命令。3) exit退出命令

20、行。六、思考题 1) 进程创建的核心内容是什么？2) 该设计和实际的操作系统进程创建相比，缺少了哪些步骤？实验二 进程撤销模拟实验学时：2实验类型：验证实验要求：必修一、实验目的1) 理解进程撤销相关理论；2) 掌握进程撤销流程。二、实验内容本实验针对操作系统中进程撤销相关理论进行实验。要求实验者设计一个程序，该程序可模拟撤销多个进程及其子孙进程。1) 采用动态或静态方法生成一颗进程树（进程数目20）；2) 设计进程撤销算法；3) 实现进程撤销函数，采用级联方式撤销；4) 可动态撤销进程；5) 可动态观察进程树的情况；6) 测试程序并得到正确结果。三、实验原理1)进程创建流程(1) 从 PCB

21、 链中找到该进程的 PCB，从中读出该进程的状态；(2) 如果该进程处于执行状态，则终止该进程并置调度标志为真；(3) 若该进程有子孙进程，需要撤销其子孙进程；(4) 释放该进程占有的资源；(5) 从 PCB 链中移出该进程的 PCB。2） 进程子树的删除对于已经创建的进程树（可以参考实验 1 创建进程），在删除的时候，首先需要考虑把该进程及其子孙从整棵树中脱离出来，这样才不会破坏整棵树的完整性。3） 进程总链元素的删除对于进程树种撤销的所有进程，必须在进程总链中进行删除。四、思考题1） 进程撤销的核心内容是什么？2） 进程总链在进程撤销过程中有什么作用？实验三 P、V 原语的模拟实现实验学时

22、：2实验类型：验证实验要求：必修一、实验目的1) 理解信号量相关理论；2) 掌握记录型信号量结构；3) 掌握 P、V 原语实现机制。二、实验内容本实验针对操作系统中信号量相关理论进行实验，要求实验者输入实验指导书提供的代码并进行测试。代码主要模拟信号量的 P 操作（down）和 V 操作（up）。1) 信号量信号量也称为信号锁，主要应用于进程间的同步和互斥，在用于互斥时，通常作为资源锁。信号量通常通过两个原子操作 dwon(P)和 up(V)来访问。dwon 操作使信号量的值+1，up 操作使信号量的值-1。2) 记录型信号量记录型信号量采用了“让权等待”的策略，存在多个进程等待访问同一临界资

23、源的情况，所以记录型信号量需要一个等待链表来存放等待该信号量的进程控制块或进程号。在本实验中，使用记录型信号量。三、实验要求1) 输入给定代码；2) 进行功能测试并得出正确结果。3) 分析 dwon 和 up 函数功能模块；4) 在实验报告中画出 dwon 和 up 函数流程图；5) 撰写实验报告。四、程序清单#include "basic.h" semphore sem5; /deinfe 5 semphorespnode * pr20; /define 0-19 total 20 process/down operation void down(char * sname

24、,int pid) int fflag,pflag; pnode *p,*p1; semphore *s; fflag=0; pflag=0; for(int i=0;i<5;i+) if(!strcmp(,sname)/find semaphore by name s=&semi; fflag=1; break; for(i=0;i<20;i+) /find pcb by pid if(pri->node->pid = pid) p1 = pri; pflag=1; break; if(!fflag) /semaphore is not ex

25、ist printf("the semphore '%s' is not exist!n",sname); return; if(!pflag) /pid is not exist printf("the process '%d' is not exist!n",pid); return; s->count-; /semaphore! s value -1 if(s->count>=0) /this pcb get the semaphore s->curpid = p1->node->

26、pid; else if(s->wlist) /the link is not NULL, add the pcb to the last for(p=s->wlist;p->next;p=p->next); p->next=p1; else /this pcb is the first pcb be added to the down list s->wlist=p1; /up operation void up(char *sname) int fflag=0; for(int i=0;i<5;i+) if(!strcmp(,sn

27、ame) /find the semaphore by name fflag=1; break; if(fflag) /find it semi.count+; if(semi.wlist) /there are processes in the down list semi.curpid = semi.wlist->node->pid; semi.wlist = semi.wlist->next; else printf("the semphore '%s' is not exist!n",sname); /show semphore i

28、nfomation void showdetail() int i; pnode *p; printf("n"); for(i=0;i<5;i+) if(semi.count<=0) printf("%s (current_process %d): ",,semi.curpid); p=semi.wlist; while(p) printf("%5d",p->node->pid); p=p->next; else printf("%s : ",);

29、printf("n"); /*/ void init() /init semaphore strcat(,"s0"); strcat(,"s1"); strcat(,"s2"); strcat(,"s3"); strcat(,"s4"); for(int i=0;i<5;i+) semi.wlist=NULL; semi.count=1; /init process for(i=0

30、;i<20;i+) pri = new pnode; pri->node=new pcb; pri->node->pid=i; pri->brother=NULL; pri->next=NULL; pri->sub=NULL; void main() short cflag,pflag; char cmdstr32; char *s,*s1,*s2; initerror(); init(); for(;) cflag=0; pflag=0; printf("cmd:"); scanf("%s",cmdstr);

31、if(!strcmp(cmdstr,"exit") /exit the program break; if(!strcmp(cmdstr,"showdetail") cflag = 1; pflag = 1; showdetail(); else s = strstr(cmdstr,"down"); /create process if(s) cflag=1; /getparameter s1 = substr(s,instr(s,'(')+1,instr(s,',')-1); s2 = substr(

32、s,instr(s,',')+1,instr(s,')')-1); if(s1 && s2) down(s1,atoi(s2); pflag=1; else s=strstr(cmdstr,"up");/delete process if(s) cflag=1; s1 = substr(s,instr(s,'(')+1,instr(s,')')-1); if(s1) up(s1); pflag=1; if(!cflag) geterror(0); else if(!pflag) geterror

33、(1); /*/ 五、测试要求1） 至少进行 10 次以上的 wait 和 signal 操作；2） 要求 wait 操作出现进程等待队列；3） 对有等待队列的信号量进行 signal 操作。六、实验指导 实验中提供了 5 个信号量（s0-s4）和 20 个进程（pid 0-19）。在程序运行过程中可以键入 down up 命令和 showdetail 命令显示每个信号量的状态。具体输入解释如下： 1) dwon 获取信号量操作（P 操作）。 参数： 1 sname 2 pid 。 示例：down(s1,2) 。进程号为 2 的进程申请名字为 s1 的信号量。 2) up 释放信号量操作（V

34、操作）。 参数 1 sname。 示例：up(s1)。释放信号量名字为 s1 的信号量。 3) showdetail 显示各信号量状态及其等待队列。 4) exit退出命令行。七、实验思考1) 如何修改 dwon 操作，使之能一次申请多个信号量？2）在某个时刻，一个进程最多可以等待多少个信号量？实验四 带优先级的时间片轮换的进程调度算法的实现实验学时：4实验类型：设计实验要求：必修一、实验目的（1）掌握进程状态转换过程（2）掌握时间片轮转的进程调度算法；（3）掌握带优先级的进程调度算法；二、实验内容（1）自定义PCB的数据结构；（2）使用带优先级的时间片轮转法调度进程，每运行一个时间片，优先级

35、减半。（3）命令集A）create 随机创建进程，进程的优先级与所需要的时间片随机决定；B）round 执行1次时间片轮转操作，其方法为运行高优先级队列的第1个，再降低其优先级，插入到相应的队列中。C）ps 查看当前进程状态D）sleep 命令将进程挂起E）awake 命令唤醒1个被挂起的进程F）kill 命令杀死进程G）quit命令退出（4）选用面向对象的编程方法。三、实验原理或算法本实验结合了进程状态转换、优先级调度、时间片轮转调度三方面的内容，根据进程状态转换图，设置SLEEP命令，将1个进程挂起，AWAKE命令唤醒1个被挂起的进程（从阻塞状态到就绪状态）。1) 优先级优先级体现了进程的

36、重要程度或紧迫程度，在大多数现代操作系统中，都采用了优先级调度策略。优先级从小到大（如 0-127） 优先级最高，127 最低。在本实验中按数值大小决定优先级，数值大的优先级高。2) 基于时间片调度将所有的就绪进程按照先来先服务的原则，排成一个队列，每次调度时，将 cpu 分配给队首进程，并令其执行一个时间片。当时间片用完时，由一个计时器发出时钟中断请求，调度程序把此进程终止，把该进程放到队尾。在该实验中，时间片以 100ms 为单位（实际的要小得多）。在调度过程中，需要通过时间函数检测进程的执行时间，当该进程执行时间时间片大小时，进行调度。3) 高优先级调度优先级高的进程优先得到 cpu，等

37、该进程执行完毕后，另外的进程才能执行。4) 基于时间片的高优先级调度在调度算法中，只有处于就绪状态的进程才能被调度，调度算法结合了优先级调度和时间片轮转调度算法，约定：从最高优先级队列取第1个就绪状态的进程进行调度，时间片到后降低其优先级（降低一半），然后插入到低优先级队列的尾部，每次调度后，显示进程的状态。四、程序清单#include <stdlib.h>#include <stdio.h>#include <time.h>/#include <dos.h>#include <string.h>/定义进程数#define LEN 1

38、0/定义最高优先级 #define MAXPIOR 3/ 定义时间片#define QUANTUM 2#define PCB sizeof(struct pcb)struct pcb /PCBint ident;/标识符 int state;/状态 0-就绪，1运行，2堵塞 int pior;/优先级,MAXPIOR为最高优先级*/ int life;/生命期*/ struct pcb *next;/*指针*/ *arrayMAXPIOR;static int idlistLEN;/*标识符表*/int life=0;/*总生命期初始化为0*/char str20;char command71

39、0;int killtest=0;void init();int create();void kill(int x);void process();void routine();void ps();void init() int i=0; for (i=0;i<MAXPIOR;i+) arrayi=NULL; sprintf(command0,"quit"); sprintf(command1,"ps"); sprintf(command2,"create"); sprintf(command3,"kill"

40、); sprintf(command4,"round"); sprintf(command5,"sleep"); sprintf(command6,"awake");int create() int i=0,pior=0; struct pcb *p,*q,*s; while (idlisti!=0&&i<=LEN-1) i+; if (i=LEN) return -1; idlisti=1; srand(unsigned)time(NULL); pior=rand()%MAXPIOR; /最大优先级设定为02的

41、整数 /printf("pior=%dn",pior); s=(struct pcb *)malloc(PCB);/create a node to keep the process messege s->ident=i; s->state=0; s->pior=pior; s->life=1+rand()%20;/进程有生命期假设为120 s->next=NULL; life=life+(s->life); p=arraypior;/建立同优先级队列（链表） if (p=NULL) arraypior=s; else while(p!=

42、NULL) q=p; p=p->next; q->next=s; printf("success create process id=%d, current process state disp below:n",s->ident); ps(); /printf("end displayn"); return 1;void ps()int i=0; struct pcb *p; for (i=0;i<MAXPIOR;i+) p=arrayi; while (p!=NULL) printf("id:%d,state:%d,

43、pior:%d,life:%dn",p->ident,p->state,p->pior,p->life); p=p->next; void sleep(int x)int i=0,test=0; struct pcb *p=NULL,*q=NULL; while(test=0&&i!=MAXPIOR) p=arrayi; if (i!=MAXPIOR && p=NULL) i+;continue; while(p!=NULL) if (p->ident=x) test=1;killtest=1;break; else

44、 q=p;p=p->next; if (test=0) i+; /*找到X所在指针*/ if (i=MAXPIOR) printf("Invaild process number."); else if (p->state=2) printf("the process %d has blocked,cannot sleep again!",p->ident); else p->state=2; ps();void awake(int x)int i=0,test=0; struct pcb *p=NULL,*q=NULL; whi

45、le(test=0&&i!=MAXPIOR) p=arrayi; if (i!=MAXPIOR && p=NULL) i+;continue; while(p!=NULL) if (p->ident=x) test=1;killtest=1;break; else q=p;p=p->next; if (test=0) i+; /*找到X所在指针*/ if (i=MAXPIOR) printf("Invaild process number."); else if (p->state=0) printf("the p

46、rocess %d is ready state,cannot awake again!",p->ident); else p->state=0; ps();void kill(int x)int i=0,test=0; struct pcb *p=NULL,*q=NULL; while(test=0&&i!=MAXPIOR) p=arrayi; if (i!=MAXPIOR && p=NULL) i+;continue; while(p!=NULL) if (p->ident=x) test=1;killtest=1;break;

47、else q=p;p=p->next; if (test=0) i+; /*找到X所在指针*/ if (i=MAXPIOR) printf("Invaild process number."); else if (p=arrayi) arrayi=arrayi->next; idlistx=0; free(p); else q->next=p->next; idlistx=0; life=life-(p->life); free(p); void process()/对输入命令的处理int i=0,ii=0; for (i=0;i<7;i

48、+) if (stricmp(str,commandi)=0) break; switch(i) case 0:printf("thank you for using the program!n");exit(0); break; case 1:ps(); break; case 2:create(); break; case 3:printf("Which process you want to kill?n"); scanf("%d",&ii); kill(ii);break; case 4:routine();break

49、;case 5:printf("Which process you want to sleep?n"); scanf("%d",&ii); sleep(ii);break;case 6:printf("Which process you want to awake?n"); scanf("%d",&ii); awake(ii);break;default: printf("Error command.Please input create, ps, kill,sleep,awake,quitn"); void routine()/执行一次调度运行，将最高优先级队列的进程运行1个时间片，并降低其优先级 int i=MAXPIOR-1,pior=0,t; struct pcb *pp,*qq,*pr,*r; do while (i>=0 && arrayi=NULL) i=i-; if (i<