1、操作系统实验实验一 进程调度一、设计目的在多道程序设计中，如果若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。此设计采用优先调度法处理机调度问题，以此加深对进程调度的理解。二、设计任务与要求1. 用语言来实现对 n 个进程采用不同调度算法的进程调度。2. 每个用来标识进程的进程控制块 PCB 用结构来描述，包括以下字段：（1） 进程优先数 ID，其中 0 为闲逛进程，用户进程的标识数为 1，2，3。（2） 进程优先级 Priority，闲逛进程（idle）的优先级为 0，用户进程的优先级大于 0， 且随机产生，优先数越大，优先级越高。（3） 进程占用
2、的 CPU 时间 CPUtime，进程每运行一次，累计值等于 4。（4） 进程总共需要运行时间 Alltime，利用随机函数产生。（5） 进程状态，0：就绪态；1：运行态；2：阻塞态。（6） 队列指针 next，用来将多个进程控制块 PCB 链接为队列。3. 优先数改变的原则（1） 进程在就绪队列中每呆一个时间片，优先数增加 1。（2） 进程每运行一个时间片，优先数减 3。4. 在调度前，系统中拥有的进程数 PCB_number 由键盘输入，经初始化后，所有的进程控制块 PCB 链接成就绪队列。三、实验流程图四实验过程：（1） 输入：进程流文件（1.txt），其中存储的是一系列要执行的进程，
3、每个作业包括四个数据项：进程名进程状态(1 就绪2 等待3 运行)所需时间优先数(0 级最高)进程 01502进程 12104进程 21150进程 33285进程 42191进程 5387输出: 进程执行流等待时间，平均等待时间（2） 程序代码#include #include #include #includeconst int block_time=4; /定义时间片的长度为 4 秒const int MAXPCB=100; /定义最大进程数/定义进程结构体typedef struct nodeint id;int status; int alltime; intpriority; int
4、 finished;int wait_time; node *next;pcb;pcb pcbsMAXPCB; int count;int i;/初始化函数void initial()couti;count=i; for(i=0;iMAXPCB;i+)pcbsi.id=i+1;pcbsi.status=1; pcbsi.time=random(20); pcbsi.priority=random(2); pcbsi.finished=0; pcbsi.wait_time=0;/优先数调度算法void order()void pri()if(count!=0)int passed_time=0;
5、 int total;int queueMAXPCB;int current_privilege=1000; for(i=0;iquantity;i+)current_privilege=1000; for(j=0;jquantity;j+)if(pcbsj.finished=0)&(pcbsj.privilegecurrent_privilege) p=j; current_privilege=pcbsj.privilege;queuei=p; pcbsp.finished=1;pcbsp.wait_time+=passed_time; passed_time+=pcbsp.time;/输出
6、优先数调度执行流coutendl*endl;cout优先数调度执行流:endl;cout进程名 等待时间endl; for(i=0;iquantity;i+)cout pcbsqueuei.name pcbsqueuei.wait_timeendl;total=0; for(i=0;iquantity;i+) total+=pcbsi.wait_time; cout总等待时间:total 平均等待时间:total/quantityendl;/主函数void main()int flag; version(); initial(); flag=readData(); if(flag=1) FIF
7、O();init(); privilege(); init();timer();（3） 运行结果：输入进程流文件名 1.txt 即可得出以下输出结果：实验二 银行家算法一、实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、实验要求设计有 n 个进程共享 m 个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于
8、用户观察和分析；三、数据结构1. 可利用资源向量 Available，它是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果 Available（j）=k，标是系统中现有 Rj 类资源 k 个。2. 最大需求矩阵 Max，这是一个 nm 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 Max（i，j）=k，表示进程 i 需要 Rj 类资源的最大数目为 k。3. 分配矩阵 Allocation，这是一个 nm 的矩阵，它定义了系统中的每类资源当前一分配
9、到每一个进程的资源数。如果 Allocation（i，j）=k，表示进程 i 当前已经分到 Rj 类资源的数目为 k。Allocation i 表示进程 i 的分配向量，有矩阵 Allocation 的第 i 行构成。4. 需求矩阵 Need，这是一个 nm 的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程 i 还需要 Rj 类资源 k 个，才能完成其任务。Need i 表示进程 i 的需求向量， 由矩阵 Need 的第 i 行构成。上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；四、银行家算法Request i
10、 是进程 Pi 的请求向量。Request i （j）=k 表示进程 Pi 请求分配 Rj 类资源 k 个。当 Pi 发出资源请求后，系统按下述步骤进行检查：1. 如果 Request iNeed，则转向步骤 2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2. 如果 Request iAvailable，则转向步骤 3；否则，表示系统中尚无足够的资源满足 Pi 的申请，Pi 必须等待。3. 系统试探性地把资源分配给进程 Pi，并修改下面数据结构中的数值： Available = Available - Request iAllocationi= Allocationi+ R
11、equest iNeed i= Need i - Request i4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程 Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。假定系统有 5 个进程（p0,p1,p2,p3,p4）和三类资源（A，B，C），各种资源的数量分别为 10，5，7，在T0 时刻的资源分配情况如下图：MaxAllocationNeedAvailableA B CABCABCA B CP0753010743332( 230 )P1322200122(302 )(020 )P2902302600
12、P3222211011P4433002431五、安全性算法1. 设置两个向量。Work：它表示系统可提供给进程继续运行的各类资源数目，它包含 m 个元素，开始执行安全性算法时，Work = Available。Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始 Finish（I）=false；当有足够资源分配给进程 Pi 时，令 Finish（i）=true；2. 从进程集合中找到一个能满足下述条件的进程。Finish（i）= = false；Need iwork；如找到则执行步骤 3；否则，执行步骤 4；3. 当进程 Pi 获得资源后，可顺利执行直到完成，并释放出分配给它
13、的资源，故应执行Work = work + Allocationi Finish（i）=true；转向步骤 2；4. 若所有进程的 Finish（i）都为 true，则表示系统处于安全状态；否则，系统处于不安全状态。六、系统流程图开 始输入资源数 m,及各类资源总数，初始输入进程数结 束YinNNmax资源Yi 加 1输入进程 i 的最大需求向量初始化 need提示错误重新该进程的 NeedN输入该进程的资源请求量YNeed 矩阵为N任选一个进程作为该进程已运行所有进程运行调用银行家算法，及安全性算法，完成分配， Y七银行家算法程序代码#include #include #include us
14、ing namespace std;typedef struct Max1/ 资源的最大需求量int m_a; int m_b; int m_c;Max;typedef struct Allocation1/已分配的资源数int a_a; int a_b; int a_c;Allocation;typedef struct Need1/还需要的资源数int n_a; int n_b; int n_c;Need;struct Available1/可利用的资源量 q;int av_a; int av_b; int av_c;struct pr/定义一个结构char name;Max max;Al
15、location allocation;Need need;int finishflag;p5;char na5;/* void init()/读入文件1.txtcout各进程还需要的资源数 NEED：endl;FILE *fp;fp=fopen(1.txt,r+); / 打开文件1.txt for(int i=0;i5;i+)fscanf(fp,%c,%d,%d,%d,%d,%d,%dn,&pi.name,&pi.max.m_a,&pi.max.m_b, &pi.max.m_c,&pi.allocation.a_a,&pi.allocation.a_b,&pi.allocation.a_c)
16、;pi.need.n_a=pi.max.m_a-pi.allocation.a_a; pi.need.n_b=pi.max.m_b-pi.allocation.a_b; pi.need.n_c=pi.max.m_c-pi.allocation.a_c;coutpi.name: pi.need.n_a pi.need.n_b pi.need.n_cendl;fclose(fp);/关闭文件/* int fenpei()/分配资源coutAvailable:;coutq.av_a q.av_b q.av_cendl; int finishcnt=0,k=0,count=0;for(int j=0;
17、j5;j+) pj.finishflag=0;while(finishcnt5)for(int i=0;i=pi.need.n_a&q.av_b=pi.need.n_b&q.av_c=pi.need.n_c)q.av_a+=pi.allocation.a_a; q.av_b+=pi.allocation.a_b; q.av_c+=pi.allocation.a_c; pi.finishflag=1; finishcnt+; nak+=pi.name;break;count+;/禁止循环过多if(count5)return 0;return 1;/* int shq()/申请资源int m=0,
18、i=0,j=0,k=0;/m 为进程号; i,j,k 为申请的三类资源数cout请输入进程号和请求资源的数目!endl;cout如：进程号 资源 A B Cendl; cout02 0 2mijk;if(i=pm.need.n_a&j=pm.need.n_b &k=pm.need.n_c)if(i=q.av_a&j=q.av_b&k=q.av_c)elseelsepm.allocation.a_a+=i; pm.allocation.a_b+=j; pm.allocation.a_c+=k;pm.need.n_a=pm.max.m_a-pm.allocation.a_a; pm.need.n_
19、b=pm.max.m_b-pm.allocation.a_b; pm.need.n_c=pm.max.m_c-pm.allocation.a_c;cout各进程还需要的资源数 NEED:n; for(int w=0;w5;w+)coutpw.name: pw.need.n_a pw.need.n_b pw.need.n_cendl; return 1;coutAvailable 让进程m等待 endl;coutNeed,让进程m等待endl;return 0;/* void main()int flag; char c;cout/* 银行家算法*/endl;cout确认已经在1.txt文档中正
20、确输入各进程的有关信息后按回车键endl; getch();init();q.av_a=10;/各种资源的数量q.av_b=5;q.av_c=7;while(flag)for(int i=0;i5;i+)q.av_a-= pi.allocation.a_a; q.av_b-= pi.allocation.a_b; q.av_c-= pi.allocation.a_c;if(fenpei()cout这样配置资源是安全的!endl;cout其安全序列是：; for(int k=0;k5;k+) coutnak; coutendl;cout有进程发出 Request 请求向量吗?(Enter y o
21、r Y)endl; coutendl;c=getch(); if(c=y|c=Y)if(shq()continue; else break;else flag=0;elseflag=0;cout不安全!endl;八运行结果一实验目的实验三存储管理存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二实验内容（1） 通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中
22、的次数。命中率 = 1 - 页面失效次数页地址流长度在本实验中，假定页面大小为 1k，用户虚存容量为 32k，用户内存容量为 4 页到 32 页。（2） produce_addstream 通过随机数产生一个指令序列，共 320 条指令。A、 指令的地址按下述原则生成：1） 50%的指令是顺序执行的2） 25%的指令是均匀分布在前地址部分3） 25%的指令是均匀分布在后地址部分B、具体的实施方法是：1） 在0，319的指令地址之间随机选取一起点 m；2） 顺序执行一条指令，即执行地址为 m+1 的指令；3） 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为 m；4） 顺序执行一条指令
23、，地址为 m+1 的指令5） 在后地址m+2，319中随机选取一条指令并执行；6） 重复上述步骤 1）5），直到执行 320 次指令C、将指令序列变换称为页地址流在用户虚存中，按每 k 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：第 0 条第 9 条指令为第 0 页（对应虚存地址为0，9）；第 10 条第 19 条指令为第 1 页（对应虚存地址为10，19）；。第 310 条第 319 条指令为第 31 页（对应虚存地址为310，319）；按以上方式，用户指令可组成 32 页。（3） 计算并输出下属算法在不同内存容量下的命中率。1） 先进先出的算法（FIFO）；2）
24、 最近最少使用算法（LRU）；3） 最佳淘汰算法（OPT）；4） 最少访问页面算法（LFR）；其中 3）和 4）为选择内容三系统框图开始生成地址流N1S4Y是否用其他算法继续N结 束Msize32YS=?1234LFU()LRU()FIFO()OPT()用户内存空间 msize=2提示出错， 重新输入输入算法号 S形成地址页号Msize 加 1四页面置换算法程序代码：#include #include #includeconst int MAXSIZE=1000;/定义最大页面数const int MAXQUEUE=3;/定义页框数typedef struct node int loaded;
25、 int hit;page;page pagesMAXQUEUE; /定义页框表int queueMAXSIZE;int quantity;/初始化结构函数void initial()int i; for(i=0;iMAXQUEUE;i+)pagesi.loaded=-1; pagesi.hit=0; for(i=0;iMAXSIZE;i+)queuei=-1;quantity=0;/初始化页框函数void init()int i; for(i=0;iMAXQUEUE;i+)pagesi.loaded=-1; pagesi.hit=0;/读入页面流void readData()FILE *fp;char fname20; int i;coutfname; if(fp=fopen(fname,r)=NULL)elsecout错误,文件打不开,请检查文件名;while(!feof(fp)fscanf(fp,%d ,&queuequantity); quantity+;cout读入的页面流:; for(i=0;iquantity;i+)coutqueuei ;/FIFO 调度算法vo
