进程调度试验、模拟分页存储管理、电梯调度实验

《进程调度试验、模拟分页存储管理、电梯调度实验》由会员分享，可在线阅读，更多相关《进程调度试验、模拟分页存储管理、电梯调度实验（24页珍藏版）》请在装配图网上搜索。

1、一. 实习题目：设计一个按优先数调度算法实现处理器调度的程序。二. 实习目的：在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器 数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实习模拟在单处理器情况下的处理器调度， 帮助学生加深了解处理器调度的工作。三. 问题分析：(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名指针要求运行时间优先数状态其中，进程名一一作为进程的标识，假设五个进程的进程名分别为P1, P2, P3, P4, P5。指针按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的

2、首地址，最 后一个进程中的指针为“0”。要求运行时间一一假设进程需要运行的单位时间数。优先数一一赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为就绪”，用“R”表示， 当一个进程运行结束后，它的状态为“结束”，用“E”表示。(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时 间”。(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针 指出队列的连接情况。例：队首标志K21K P1K2P2K3P3K4P4K5P50K4K5K3K1231

3、2415342RRRRRPCB1PCB2PCB3PCB4PCB5(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减1”。 由于本实习是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理 器运行，直到出现等待事件或运行结束。在这里省去了这些工作。(5) 进程运行一次后，若要求运行时间0，则再将它加入队列(按优先数大小插入，且置队首标志)； 若要求运行时间=0，则把它的状态修改成“结束”(E)，且退出队列。(6)

4、 若“就绪”状态的进程队列不为空，则重复上面(4)和(5)的步骤，直到所有进程都成为“结束” 状态。(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后 进程队列的变化。(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打 印逐次被选中进程的进程名以及进程控制块的动态变化过程。四. 编程模拟实现：通过上面的问题分析后，编程实现不是一个很难的问题。我们可以根据以上的内容从而定义一个队列，然后定义两个对象，一个用来保存就绪的进程，一个 用来保存结束的进程!然后根据以上的思路来进行操作，当用来保存就绪进程的队列为空时

5、，循环结束，也 就是说完成了所有进程的调度。由于这个调度需要考虑进程的优先级数，所以我们可以用一个优先队列来保存就绪进程，每次对队 首元素进行操作。具体实现见源程序以及注释说明。所用数据结构：优先队列，优先的排序准则为各进程的优先级。优先队列的实现方法：直接调用STL中的标准模版库#include的优先队列priority_queue；实现的难点：虽然可以直接调用STL中的优先队列，无需自己写优先队列的实现类，大大简化了编程的工作量， 然而如何确定优先队列的优先准则是个难点。由于队列中的元素是一个自定义类的对象PCB，需对对象中 的priority数据成员进行优先排序，不能直接简单的调用，通过

6、查阅STL中的相关资料发现，要实现这个 功能需自己编写优先准则函数，我们可以写一个包含排序准则的仿函数的类PCBSortCriterion来实现。符号说明：PCB：进程类，包含进程的名字（name），运行时间（runtime），优先级（priority），状态（state）， 指针（next）等五个数据程序和一个方法print（）用来输出打印。为了简化，将数据成员和方法都设置为 publicoPCBSortCriterion :包含一个仿函数的方法的排序准则类；number：为测试中要建立的进程个数；pcb：为一个PCB的数组用来保存就绪进程p1：为一个PCB的数组用来保存已经结束的进程p：为

7、一个PCB型的变量，用来保存队首元素pQueue：为以PCBSortCriterion为排序准则的优先队列q：优先队列pQueue的一个对象，对这个队列进行主操作temp:优先队列pQueue的一个对象，是q的一个拷贝对象，作为实现打印输出的一个中间变量n：进程执行的次数m：完成进程的个数五. 源程序处理器调度，优先级算法#include #include #include typedef struct proc （char name32;int run_time;int req_time;int pri;char state;struct proc *next;PROC;int g_t =

8、0;char k;PROC *g_h = NULL, *g_c = NULL;void Init()(PROC *p, *p0;g_h = (PROC*)malloc(sizeof(PROC);g_h-next = NULL;p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P1);p-run_time = 0;p-req_time = 4;p-pri = 1;p-state=r;p-next = NULL;g_h-next = p;p0 = p;p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P2);p-r

9、un_time = 0;p-req_time = 3;p-pri = 5;p-state=r;p-next = NULL;p0-next = p;p0 = p;p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P3);p-run_time = 0;p-req_time = 1;p-pri = 3;p-state=r;p-next = NULL;p0-next = p;PO = P；p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P4);p-run_time = 0;p-req_time = 3;p-pri =

10、 4;p-state=r;p-next = NULL;p0-next = p;PO = P；p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P5);p-run_time = 0;p-req_time = 5;p-pri = 2;p-state=r;p-next = NULL;p0-next = p;PO = P； p0-next = g_h;void PrintInfo()(PROC *p = g_h-next;printf(Time : %dt Process Information”, g_t);printf(name run_time req_

11、time pri staten);printf(”n”);while(p != g_h)(printf(%4s %8d %8d %3d %5sn”，p-name, p-run_time, p-req_time,p-pri, p-state= r? ”r” : ”e”)；p = p-next;printf(Current process is %sn, g_c-name);printf(nn);printf(press k to go onn);k=getchar();void Run()(PROC *p_temp = g_h;g_c = g_h-next;PrintInfo();while(g

12、_h-next!= g_h)&(k!=NULL)(g_t+;g_c-run_time+;if(g_c-run_time = g_c-req_time)(g_c-state=e;PrintInfo();p_temp-next = g_c-next;free(g_c);g_c = p_temp-next;else (PrintInfo();g_c = g_c-next;p_temp = p_temp-next;if(g_c = g_h)(g_c = g_c-next;p_temp = p_temp-next;p_temp-next = g_c;printf(press k to go onn);k

13、=getchar();main()(Init();Run();free(g_h);A模拟分页式存储管理中硬件的地址转换和产生缺页中断一、实验目的在计算机系统中，为了提高主存利用率，往往把辅助存储器(如磁盘)作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验帮助同学理解在分页式存储管理中怎样实现 虚拟存储器。二、实验要求及实验环境第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中 断。分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业 被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为 作业

14、建立页表时，应说明哪些页已在主存，哪些页尚未装入主存。作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页 号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为 “1”，则表示该页已在主存，这时根据关系式“绝对地址=块号X块 长+单元号”计算出欲访问的主存单元地址。如果块长为2的幕次， 则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而 成绝对地址。若访问的页对应标志为“0”，则表示该页不在主存，这 时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把 该页信息从磁盘读出装入主存后再重新执行这条指令。设计一个“地 址转换”程序来模拟硬件的地址转换工作。当访问的页在

15、主存时，则 形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代 替一条指令的执行。当访问的页不在主存时，则输出“*该页页号”， 表示产生了一次缺页中断。第二题：用先进先出（FIFO）页面调度算法处理缺页中断。在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操 作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用 FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁 盘上，然后再把当前要访问的页装入该块。调出和装入后都要修改页 表页表中对应页的标志。FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页， 因此可以用一个数组来表示该作业已在主存的页面。假定作业被

16、选中 时，把开始的m个页面装入主存，则数组的元素可定为m个。编制一个FIFO页面调度程序，为了提高系统效率，如果应淘汰 的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副 本）而直接装入一个新页将其覆盖。由于是模拟调度算法，所以，不 实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的 页号来代替一次调出和装入的过程。三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1 .程序流程图斓出孔页号表 示发生就页中断取指金中问的页号形成翻对地址推;|整对地址取 -条指令取一查页走以下为FIFO算法流程:2 .逻辑设计使用线性表保存页表。每个

17、节点信息包括调入主存的标志，主 存块号，在磁盘上的位置，修改标志等。使用线性表保存FIFO算法 使用的对应关系数组P,用数组模拟实现调度的队列。该队列需支持 查找，插入和删除操作（即替换操作）。3、物理设计全局定义如下：struct info/ 页表（bool flag; /标志long block;/ 块号long disk;/在磁盘上的位置bool dirty;/修改标志pagelistSizeOfPage;long po;/队列标记long PM;使用函数init()进行初始化，使用循环结构读入各条指令。四、测试结果实际运行的结果如下：请选择题号(1/2):1请输入指令的页号和单元号：0

18、 70绝对地址=710请输入指令的页号和单元号：4 053* 4请输入指令的页号和单元号：1 50绝对地址=1074请输入指令的页号和单元号：5 023* 5请输入指令的页号和单元号：2 15绝对地址=1167请输入指令的页号和单元号：1 037绝对地址=1061请输入指令的页号和单元号：exit请选择题号(1/2):2请输入指令的页号、单元号，以及是否为存指令：0 70 N绝对地址=710请输入指令的页号、单元号，以及是否为存指令：4 053 Nout 0in 4请输入指令的页号、单元号，以及是否为存指令：1 50 N绝对地址=1074请输入指令的页号、单元号，以及是否为存指令：5 023

19、Nout 1in 5请输入指令的页号、单元号，以及是否为存指令：2 15 N绝对地址=1167请输入指令的页号、单元号，以及是否为存指令：1 037 yout 2in 1请输入指令的页号、单元号，以及是否为存指令：3 21 Y绝对地址=149请输入指令的页号、单元号，以及是否为存指令：2 078 Nout 3in 2请输入指令的页号、单元号，以及是否为存指令：0 56 Nout 4in 0请输入指令的页号、单元号，以及是否为存指令：4 001 Nout 5in 4请输入指令的页号、单元号，以及是否为存指令：6 40 Nout 1in 6请输入指令的页号、单元号，以及是否为存指令：6 084 Y

20、绝对地址=1236请输入指令的页号、单元号，以及是否为存指令：exit数组P的值为：P0=0P1=4P2=6P3=2五、系统不足与经验体会系统的不足包括健壮性尚不够好，界面比较简单，对页表的 初始化需要修改程序。经验体会：注意体会算法的精神，程序前后逻辑要一致。注 意测试时数据的全面性。六、附录：源代码（带注释）#include #include #define SizeOfPage 100#define SizeOfBlock 128#define M 4struct info/ 页表(bool flag; /标志long block;/ 块号long disk;/在磁盘上的位置bool d

21、irty;/修改标志pagelistSizeOfPage;long po;/队列标记long PM;void init_ex1()(memset(pagelist,0,sizeof(pagelist);pagelist0.flag=1;pagelist0.block=5;pagelist0.disk=011;pagelist1.flag=1;pagelist1.block=8;pagelist1.disk=012;pagelist2.flag=1;pagelist2.block=9;pagelist2.disk=013;pagelist3.flag=1;pagelist3.block=1;pa

22、gelist3.disk=021;void work_ex1()(bool stop=0;long p,q;char s128;do(printf(-请输入指令的页号和单元号：n);if (scanf(%ld%ld,&p,&q)!=2)(scanf(%s”,s);if (strcmp(s,exit)=0)(stop=1;else(if (pagelistp.flag)(printf(绝对地址=%ldn,pagelistp.block*SizeOfBlock+q);else(printf(* %ldn,p);while (!stop);void init_ex2()(po=0;P0=0;P1=1

23、;P2=2;P3=3;memset(pagelist,0,sizeof(pagelist);pagelist0.flag=1;pagelist0.block=5;pagelist0.disk=011;pagelist1.flag=1;pagelist1.block=8;pagelist1.disk=012;pagelist2.flag=1;pagelist2.block=9;pagelist2.disk=013;pagelist3.flag=1;pagelist3.block=1;pagelist3.disk=021;void work_ex2()(long p,q,i;char s100;b

24、ool stop=0;do(printf(请输入指令的页号、单元号，以及是否为存指令：n);if (scanf(%ld%ld,&p,&q)!=2)(scanf(%s”,s);if (strcmp(s,exit)=0)(stop=1;else(scanf(%s”,s);if (pagelistp.flag)(printf(绝对地址=%ldn,pagelistp.block*SizeOfBlock+q);if (s0=Y | s0=y)(pagelistp.dirty=1;else(if (pagelistPpo.dirty)(将更新后的内容写回外存pagelistPpo.dirty=0;page

25、listPpo.flag=0;printf(out %ldn”,Ppo);printf(in %ldn,p);pagelistp.block=pagelistPpo.block;pagelistp.flag=1;Ppo=p;po=(po+1)%M;while (!stop);printf(数组P的值为：n);for (i=0;iM;i+)(printf(P%ld=%ldn,i,Pi);void select()(long se;char s128;doprintf(-请选择题号(1 /2):);if (scanf(%ld,&se)!=1)(scanf(%s”,s);if (strcmp(s,e

26、xit)=0)(return;else(if (se=1)(init_ex1();work_ex1();if (se=2)(init_ex2();work_ex2();while (1);int main()(select();return 0;三、电梯调度#include #include #include #include typedef struct _procchar name32;/*定义进程名称*/int team;/*定义柱面号*/int ci;/*定义磁道面号*/int rec;/*定义记录号*/struct _proc *prior;struct _proc *next;PR

27、OC;PROC *g_head=NULL,*g_curr=NULL,*local;int record=0;int yi=1;void init()/*初始化链表（初始I/OPROC *p;表)*/g_head = (PROC*)malloc(sizeof(PROC);g_head-next = NULL;g_head-prior = NULL;p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P1);p-team=100;p-ci=10;p-rec=1;p-next = NULL;p-prior = g_head;g_head-next = p;g_

28、curr=g_head-next;p = (PROC*)malloc(sizeof(PROC); strcpy(p-name, P2);p-team=30;p-ci=5;p-rec=5;p-next = NULL;p-prior = g_curr;g_curr-next = p;g_curr=p;p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P3);p-team=40;p-ci=2;p-rec=4;p-next = NULL;p-prior = g_curr;g_curr-next = p;g_curr=p;p = (PROC*)malloc(si

29、zeof(PROC);strcpy(p-name, P4);p-team=85;p-ci=7;p-rec=3;p-next = NULL;p-prior = g_curr;g_curr-next = p;g_curr=p;p = (PROC*)malloc(sizeof(PROC);strcpy(p-name, P5);p-team=60;p-ci=8;p-rec=4;p-next = NULL;p-prior = g_curr;g_curr-next = p;g_curr=g_head-next;local = (PROC*)malloc(sizeof(PROC);/* 选中进程*/strc

30、py(local-name, P0);local-team=0;local-ci=0;local-rec=0;local-next=NULL;local-prior=NULL;void PrintInit()/*打印 I/O 表*/PROC *t = g_head-next;printf(n);printf( I/O LISTn);printf( process team ci rec n);while(t!=NULL)printf(%4s %8d %8d %5dn, t-name, t-team, t-ci, t-rec );t = t-next;printf(nnCurrent proce

31、ss is :n);printf(nn);printf( process team ci rec n);printf(%4s %8d %8d %5dn”, local-name, local-team, local-ci, local-rec ); switch(yi) case 1:printf(current direction is UPn);break; case 0:printf(current direction is downn);break; void acceptreq() PROC *p;p = (PROC*)malloc(sizeof(PROC);printf(pleas

32、e input the information of processnprocess-name:nprocess-teamnprocess-cinprocess-recn);printf(1.namen);scanf(%s”,p-name);printf(2.team 0-199n);scanf(%d”,&p-team); printf(3.ci 0-19n); scanf(%d”,&p-ci); printf(4.rec 0-7n); scanf(%d”,&p-rec); getchar();g_curr=g_head;while(g_curr-next!=NULL) g_curr=g_cu

33、rr-next;p-next=NULL;p-prior=g_curr; g_curr-next=p; g_curr=g_head-next; printf(NEW I/O LISTnn); PrintInit(); void qddd() PROC *out;int min;int max=g_head-next-team;if (g_head-next=NULL); else /*接受请求函数*/*输入请求进程信息*/*将此节点链入I/O请求表*/*将新的I/O请求表输出*/*驱动调度函数*/*若已全部调度，则空操作*/thenewswitch (yi) case 1:min=g_head-

34、next-team;out=g_head-next;/*选出最小的 team进程，模拟启动此进程*/strcpy(local-name,out-name);local-team=out-team;local-ci=out-ci;local-rec=out-rec;for (g_curr=g_head-next;g_curr!=NULL;g_curr=g_curr-next)if (g_curr-team record) min = g_curr-team;break;for (g_curr=g_head-next;g_curr!=NULL;g_curr=g_curr-next)if (min=

35、g_curr-team&g_curr-teamrecord)min=g_curr-team;out=g_curr;strcpy(local-name,out-name);local-team=out-team;local-ci=out-ci;local-rec=out-rec;printf(nn);printf(the process choosed :n);printf( process team ci rec n);printf(%4s %8d %8d %5dn”, out-name, out-team, out-ci,out-rec );record = local-team;print

36、f(%d”,record);for (g_curr=g_head-next;g_curr!=NULL;g_curr=g_curr-next)if (maxteam) max=g_curr-team;if(max=record)yi=0;record=1000;break;break;/*case 1*/case 0:/*case 1的对称过程*/max=g_head-next-team;out=g_head-next;strcpy(local-name,out-name);local-team=out-team;local-ci=out-ci;local-rec=out-rec;for (g_

37、curr=g_head-next;g_curr!=NULL;g_curr=g_curr-next)if (g_curr-team team;break;for (g_curr=g_head-next;g_curr!=NULL;g_curr=g_curr-next)if (maxteam&g_curr-teamteam;out=g_curr;strcpy(local-name,out-name);local-team=out-team;local-ci=out-ci;local-rec=out-rec;printf(nn);printf(the process choosed :n);print

38、f( process team ci rec n);printf(%4s %8d %8d %5dn, out-name, out-team, out-ci,out-rec );min=g_head-next-team;for (g_curr=g_head-next;g_curr!=NULL;g_curr=g_curr-next)if (ming_curr-team)min=g_curr-team;record = local-team;if(min=record)yi=1;record=0;break;break;/*switch*/if (out-next=NULL)/*将选中的进程从I/O

39、请求表中删除*/out-prior-next=NULL;free(out); elseout-prior-next=out-next;out-next-prior=out-prior; free(out);/*else*/void acceptnum()/*通过输入01选择驱动调度或是接受请求*/float num;char c;while(1)printf(n);printf(please input a number between 0 and 1nnum0.5:qudong diaodunnnum=2:I/O LISTnnnum=?n);scanf(%f”,&num);getchar()

40、;while(num1)&num!=2)/*过滤不合法数据 注意：本程序其他输入数据可能未过滤*/printf(number ERROR!Input again please!nnum=?n );scanf(%f”,&num);getchar();if(num0.5&num!=2)/* 驱动调度*/if (g_head-next=NULL) printf(nn);printf(n);printf(I/O list is empty!n);elseprintf(qudong diaodun);qddd();/*调用函数进行调度*/else if (num=0.5)printf(accept re

41、questnn);acceptreq();else if (num=2)printf(I/O LIST;);printf(n);PrintInit();printf(n);/*请求表为空无需调度*/*接受请求*/*通过输入2显示当前请求I/O表*/printf(n);printf(choose n to quit else to continuen);/*输入 n 离开本程序*/if(c=getchar()=n)|(c=getchar()=N)printf(nnnnnn);printf(thank you for testing my program!n);printf( -by01n);printf(侦nBYEbye!”);main ()/*主程序*/init();PrintInit();acceptnum();