《操作系统》实验指导书

1、操作系统实验指导书目录实验一 进程调度模拟算法1实验二 预测分析法3附录1：实验报告模版5附录2：实验教学大纲6实验一 进程调度模拟算法课时：4实验环境：C/C+一、目的和要求进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。二、实验内容1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写两种调度算法程序： 优先数调度算法程序 循环轮转调度算法程序3

2、.按要求输出结果。 三、提示和说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（RUN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 （一）进程控制块结构如下： NAME进程标示符 PRIO/ROUND进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME进程累计占用CPU的时间片数 NEEDTIME进程到完成还需要的时间片数 STATE进程状态 NEXT链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行计算； 2.各进程的优先数或轮转时间片数，以及进程运行时间片数的初值，均由用户在程序运

3、行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下： RUN当前运行进程指针 READY就需队列头指针 TAIL 就需队列尾指针 FINISH 完成队列头指针 （三）程序说明 1. 在优先数算法中，进程优先数的初值设为： 50-NEEDTIME每执行一次，优先数减1，CPU时间片数加1，进程还需要的时间片数减1。 在轮转法中，采用固定时间片单位（两个时间片为一个单位），进程每轮转一次，CPU时间片数加2，进程还需要的时间片数减2，并退出CPU，排到就绪队列尾，等待下一次调度。 2. 程序的模块结构提示如下： 整个程序可由主程序和如下7个过程组成： （1）INSERT1在优先数

4、算法中，将尚未完成的PCB按优先数顺序插入到就绪队列中； （2）INSERT2在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾； （3）FIRSTIN调度就绪队列的第一个进程投入运行； （4）PRINT显示每执行一次后所有进程的状态及有关信息。 （5）CREATE创建新进程，并将它的PCB插入就绪队列； （6）PRISCH按优先数算法调度进程； （7）ROUNDSCH按时间片轮转法调度进程。 主程序定义PCB结构和其他有关变量。（四）运行和显示 程序开始运行后，首先提示：请用户选择算法，输入进程名和相应的NEEDTIME值。 每次显示结果均为如下5个字段

5、： name cputime needtime priority state 注： 1在state字段中，R代表执行态，W代表就绪（等待）态，F代表完成态。2应先显示R态的，再显示W态的，再显示F态的。 3在W态中，以优先数高低或轮转顺序排队；在F态中，以完成先后顺序排队。 实验二 存储管理动态分区分配及回收算法课时：4实验环境：C/C+一、目的和要求分区管理是应用较广泛的一种存储管理技术。本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同分配算法的特点。二、实验内容 1、编写：First Fit Algorithm 2、编写：Best Fit A

6、lgorithm3、编写：空闲区回收算法三、提示和说明 （一）主程序 1、定义分区描述器node，包括 3个元素： （1）adr分区首地址 （2）size分区大小 （3）next指向下一个分区的指针 2、定义 3个指向node结构的指针变量： （1）head1空闲区队列首指针 （2）back1指向释放区node结构的指针 （3）assign指向申请的内存分区node结构的指针 3、定义 1个整形变量： free用户申请存储区的大小（由用户键入） （二）过程 1、定义check过程，用于检查指定的释放块（由用户键入）的合法性 2、定义assignment1过程，实现First Fit Algor

7、ithm 3、定义assignment2过程，实现Best Fit Algorithm 4、定义acceptment1过程，实现First Fit Algorithm的回收算法 5、定义acceptment2过程，实现Best Fit Algorithm的回收算法 6、定义print过程，打印空闲区队列 （三）执行 程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。 （四）输出 要求每执行一次，输出一次空闲区队列情况，内容包括： 编号 首址 终址 大小 注：输出空闲区队列的

8、排序，应符合所用分配算法的要求。附录1：实验报告模版课程名称 分院 班 组 桌号 实验者姓名 实验日期 年 月 日评分 教师签名 一、 实验目的通过，了解，体会，掌握，提高。二、 实验要求。三、 实验过程1 准备A 查阅相关资料；B 初步编写程序；C 准备测试数据；D 。2 上机调试。3 主要流程和源代码。4 遇到的主要问题和解决方法A；B。四、 实验结果。五、 实验总结通过本次实验，我学到了，了解了，掌握了，提高了。附录2：实验教学大纲操作系统(A)实验教学大纲课程编号： 计划学时：12面向专业：计算机科学与技术专业制 订：计算机软件教研室执 笔 人：崔来堂审 定 人：邸书灵一、课程性质、目

9、的及任务操作系统是计算机科学与技术专业的一门学位课。操作系统课程理论性强，较抽象，难以理解和接受。因此，有必要加强实验环节。通过上机编程，模拟操作系统对计算机资源管理的主要策略和算法，从而有效地加深学生对所学理论知识的理解和掌握，提高学生的系统开发能力和应用开发能力。二、主要参考书1、计算机操作系统 张尧学等 清华大学出版社 2000.8 2、计算机操作系统 刘乃琦等 电子工业出版社 2003.53、计算机操作系统 汤子瀛 西安电子科技大学出版社 2003.34、计算机操作系统 庞丽萍等 华中理工大学出版社 2000.12 三、考试考核办法根据考勤、实验检查及实验报告等综合考虑给定。四、实验项

10、目与内容提要序号实验项目名称实验内容提要实验性质实验者类别学时数开设组数每组人数实验消耗（元/人时）主要仪器设备名称及配套数1处理机调度编程模拟处理机调度算法验证 演示设计综合 研究生 微机、windows/unix/linux、TC/VB/ Dephi本科生67011专科生 2存储管理编程1模拟内存的分区管理验证 演示 设计 综合研究生 微机、windows/unix/linux、TC/VB/ Dephi本科生67011专科生 3存储管理编程2（选作）模拟内存的页式管理验证 演示 设计 综合研究生 微机、windows/unix/linux、TC/VB/ Dephi本科生47011专科生 实

11、验一源代码#include #include #include #include/*进程控制块数据结构*/typedef struct node char name10;/*进程名*/int prio; /*进程优先级*/ int round; /*循环轮转法进程每次轮转的时间片*/ int cputime; /*进程累计消耗的CUP时间*/int needtime; /*进程到完成还需要的CUP时间*/int count; /*循环轮转法一个是时间片内进程运行时间*/char state; /*进程的状态：R:运行,W：等待,F：结束*/struct node *next;/*指向下一个进程

12、的链指针*/ PCB;PCB *finish,*ready,*tail,*run;/*指向三个队列的队首的指针，finish为完成队列头指针，ready为就绪队列头指针，tail为就绪队列的队尾指针，run为当前运行进程头指针*/int N;/*定义进程的数目*/void firstin(void);/调度就绪队列的第一个进程投入运行； void print1(char a);/打印表头行信息void print2(char chose,PCB *p);/打印每一行的状态信息void print(char chose);/打印每执行一次算法后所有的进程的状态信息void insert_prio

13、(PCB *q);/在优先数算法中,将尚未完成的PCB按优先数顺序插入到就绪队列中；void prior_init(char chose);/进程优先级法初始化将进程按优先级插入到就绪队列里void priority(char chose);/进程优先级算法总函数void insert_rr(PCB *q);/在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾；void roundrun_init(char chose);/循环轮转法初始化将就绪队列保存为FIFO队列void roundrun(char chose);/循环轮转法总算法void main(

14、)/主函数char chose= ;while(chose!=q)&(chose!=Q)fflush(stdin);printf(选择进程优先级算法请输入P，选择循环轮转算法请输入R，退出请输入Qn);printf(请输入你的选择：);scanf(%c,&chose);if(chose!=q)&(chose!=Q)system(cls);if(chose=P)|(chose=p)prior_init(chose);priority(chose);system(cls); else if(chose=r)|(chose=R)roundrun_init(chose);roundrun(chose)

15、;system(cls); printf(谢谢使用！n);void firstin(void)/调度就绪队列的第一个进程投入运行； if(ready!=NULL) run=ready; ready=ready-next; run-state=R; run-next=NULL; else run=NULL; void print1(char a)/打印表头行信息if(toupper(a)=P)printf(name cputime needtime priority state n);elseprintf(name cputime needtime count round state n); v

16、oid print2(char chose,PCB *p)/打印每一行的状态信息if(toupper(chose)=P) printf(%st%dt%dt%dt%cn,p-name,p-cputime,p-needtime,p-prio,p-state); elseprintf(%st%dt%dt%dt%dt%cn,p-name,p-cputime,p-needtime,p-count,p-round,p-state);void print(char chose)/打印每执行一次算法后所有的进程的状态信息PCB *p;print1(chose);if(run!=NULL)print2(chos

17、e,run);p=ready;while(p!=NULL) print2(chose,p); p=p-next;p=finish;while(p!=NULL)print2(chose,p);p=p-next;void insert_prio(PCB *q)/*在优先数算法中,将尚未 完成的PCB按优先数顺序插入到就绪队列中；*/PCB *p,*s,*r; /*p,r用来控制就绪队列滚动，S指向插入的队列*/ s=q;p=ready;r=p;if(s-prioready-prio)/ 要插入的进程的优先级大于ready的优先级 s-next=ready;ready=s; else/要插入的进程的

18、优先级不大于ready的优先级 while(p) if(p-prio=s-prio)r=p;p=p-next;elsebreak; /找到要插入的位置s-next=p;r-next=s;void prior_init(char chose)/*进程优先级法初始化将进程按优先级插入到就绪队列里*/PCB *p;int i,time;char na10;ready=NULL;finish=NULL;run=NULL;printf(输入进程 的个数 N:n);scanf(%d,&N);for(i=0;iname,na);p-cputime=0;p-needtime=time;p-state=W;p-

19、prio=50-time;/设置进程优先值初值if(ready=NULL) ready=p; ready-next=NULL;else insert_prio(p);printf(当前就绪队列的进程的信息n);print(chose);printf(%d个进程已按优先级从高到低进到就绪队列中n,N);printf(按回车键开始模拟优先级算法.n);fflush(stdin);getchar();firstin();void priority(char chose)/进程优先级算法总函数int i=1;while(run!=NULL)run-cputime+=1;run-needtime-=1;

20、run-prio-=1;if(run-needtime=0) run-next=finish; finish=run; run-state=F; run-prio=0; run=NULL; firstin(); else if(ready!=NULL)&(run-prioprio) run-state=W;insert_prio(run);run=NULL;firstin(); print(chose); getchar();void insert_rr(PCB *q)/在轮转法中，将执行了一个时间片单位（为2），/但尚未完成的进程的PCB，插到就绪队列的队尾；tail-next=q;tail

21、=q;q-next=NULL;void roundrun_init(char chose)/*循环轮转法初始化 将就绪队列保存为FIFO队列*/PCB *p;int i,time;char na10;ready=NULL;finish=NULL;run=NULL;printf(tt循环轮转算法模拟全过程nn);printf(输入进程 的个数 N:n);scanf(%d,&N);for(i=0;iname,na);p-cputime=0;p-needtime=time;p-count=0;p-state=W;p-round=2;if(ready!=NULL)insert_rr(p);else p

22、-next=ready; ready=p; tail=p;printf(当前就绪队列的进程的信息n);print(chose);printf(%d个进程已按FIFO进到就绪队列中n,N);printf(按回车键开始模循环轮转算法.n);fflush(stdin);getchar();run=ready;ready=ready-next;run-state=R; void roundrun(char chose)/循环轮转法总算法int i=1;while(run!=NULL)run-cputime+=1;run-needtime-=1;run-count+=1;if(run-needtime=

23、0) run-next=finish; finish=run; run-state=F; run-prio=0; run=NULL; if(ready!=NULL) firstin(); else if(run-count=run-round) run-count=0; if(ready!=NULL) run-state=W; insert_rr(run); firstin(); print(chose); getchar();实验二源代码#include#include#include#define MAX_SIZE 32767typedef struct node /定义分区描述器的结构i

24、nt id; /编号int adr; /分区首地址int size; /分区大小struct node *next;/指向下一个分区的指针Node;Node *head1,*head2,*back1,*back2,*assign;/*head-空闲区队列首指针 back-指向释放区Node结构的指针 assign-指向申请的内存分区Node结构的指针*/int request; /用户申请存储区的大小（由用户输入）int check(int add,int siz,char c)/用于检查指定的释放块（由用户键入）的合法性Node *p,*head;int check=1;if(add0|si

25、znext;while(p!=NULL)&check)/*地址不能和空闲区表中结点出现重叠*/ if(addadr)&(add+sizp-adr)|(add=p-adr)&(addadr+p-size) check=0; else p=p-next;if(check=0) printf(t输入释放区地址或大小有错误！n); return check; /*返回检查结果*/void init()/初始化，生成两个带头节点的空闲队列指针， /head1指向first-fit的空闲队列头，head2指向best-fit的空闲队列头Node *p;head1=(Node*)malloc(sizeof(

26、Node);head2=(Node*)malloc(sizeof(Node);p=(Node*)malloc(sizeof(Node);head1-next=p;head2-next=p;p-size=MAX_SIZE;p-adr=0;p-next=NULL;p-id=0;Node* assignment1(int num,int req)/实现首次适应算法的分配Node *before,*after,*ass;ass=(Node*)malloc(sizeof(Node);before=head1;after=head1-next;ass-id=num;ass-size=req;while(a

27、fter-sizenext;after=after-next;if(after=NULL)ass-adr=-1;/分配失败elseif(after-size=req)/空闲分区恰好等于所申请的内存大小before-next=after-next;ass-adr=after-adr;else/空闲分区大于所申请的内存大小after-size-=req;ass-adr=after-adr;after-adr+=req; return ass; void acceptment1(int address,int siz,int rd)/实现首次适应算法的回收Node *before,*after;in

28、t insert=0;back1=(Node*)malloc(sizeof(Node);before=head1;after=head1-next;back1-adr=address;back1-size=siz;back1-id=rd;back1-next=NULL;while(!insert&after)/将要被回收的分区插入空闲区（按首址大小从小到大插入）if(after=NULL)|(back1-adradr)&(back1-adr=before-adr)before-next=back1;back1-next=after;insert=1;elsebefore=before-next

29、;after=after-next; if(insert)if(back1-adr=before-adr+before-size)/和前边分区合并before-size+=back1-size;before-next=back1-next;free(back1); else if(after&back1-adr+back1-size=after-adr)/和后边分区合并back1-size+=after-size;back1-next=after-next;back1-id=after-id;free(after);after=back1;printf(t首先分配算法回收内存成功！n);els

30、eprintf(t首先分配算法回收内存失败！n); Node* assignment2(int num,int req)/实现最佳适应算法的分配 Node *before,*after,*ass,*q;ass=(Node*)malloc(sizeof(Node);q=(Node*)malloc(sizeof(Node);before=head2;after=head2-next;ass-id=num;ass-size=req;while(after-sizenext;after=after-next;if(after=NULL)ass-adr=-1;/分配失败elseif(after-size

31、=req)/空闲分区恰好等于所申请的内存大小before-next=after-next;ass-adr=after-adr; else/空闲分区大于所申请的内存大小q=after;before-next=after-next;ass-adr=q-adr;q-size-=req;q-adr+=req;before=head2;after=head2-next;if(after=NULL)before-next=q;q-next=NULL;elsewhile(after-size)size)before=before-next;after=after-next; before-next=q;q-

32、next=after; return (ass); void acceptment2(int address,int siz,int rd)/实现最佳适应算法的回收Node *before,*after;int insert=0;/是否被回收的标志back2=(Node*)malloc(sizeof(Node);before=head2;after=head2-next;back2-adr=address;back2-size=siz;back2-id=rd;back2-next=NULL;if(head2-next=NULL)/空闲队列为空head2-next=back2;head2-siz

33、e=back2-size;else/空闲队列不为空while(after)if(back2-adr=after-adr+after-size)/和前边空闲分区合并before-next=after-next;after-size+=back2-size;back2=after; elsebefore=before-next;after=after-next;before=head2;after=head2-next;while(after)if(after-adr=back2-adr+back2-size)/和后边空闲区合并before-next=after-next;back2-size+=after-size;elsebefore=before-next;after=after-next;before=head2;after=head2-next;while(!insert)/将被回收的块插入到恰当的位置（按分区大小从小到大）if(after=NULL|(after-sizeback2-size)&(before-sizesize) before-next=back2; back2-next=after; insert=1;break; else before=before-next; after=after-next; if(insert)pri