1、 目录目录实验一实验一 进程同步与互斥进程同步与互斥实验二实验二 银行家算法实现资源分配银行家算法实现资源分配实验三实验三 调度算法的使用调度算法的使用实验四实验四 请求页式存储管理请求页式存储管理l一、实验目的一、实验目的l1.掌握基本的同步与互斥算法,理解生产者消费者模型。l2.学习使用Windows 2000/XP中基本的同步对象,掌握相关API的使用方法。l3.了解Windows 2000/XP中多线程的并发执行机制,实现进程的同步与互斥。l二、实验内容二、实验内容l以生产者/消费者模型为依据,在Windows 2000环境下创建一个控制台进程,在该进程中创建n个线程模拟生产者和消费者
2、,实现进程(线程)的同步与互斥。l三、实验性质三、实验性质l验证性l四、实验学时四、实验学时l2学时l五、实验环境五、实验环境lC与C+程序设计学习与实验系统 l六、实验原理及步骤六、实验原理及步骤l测试用例文件l测试用例文件用于描述各线程的有关信息,该文件内容及格式如下:l3l1 P 3l2 P 4l3 C 4 1l4 P 2l5 C 3 1 2 4说明:第一行给出的是程序中设置的临界区个数;其余各行是各进程信息。每行中的数据之间用Tab键分隔。第一列(除第一行外):线程号。第二列:P生产者,C消费者。第三列:线程在生产和消费前的休眠时间,单位为秒。第四及以后各列:消费的产品所对应的生产者线
3、程号。l程序结构l 为了方便,程序结构用如下的文字予以描述。l (1)主函数l (2)初始化缓冲区、消费请求队列及部分同步对象l (3)提取线程信息l (4)完成线程相关同步对象的初始化l (5)创建线程,模拟生产者和消费者l (6)等待所有线程结束l (7)程序结束l (8)消费者l l (9)有无消费请求?有,则继续(10);无,则转(16)l (10)此请求可满足?可满足,转(11);否,则阻塞,再转(10)l (11)确定产品位置l (12)此产品正被消费?是,则阻塞,再转(12);否,则转(13)l (13)进入临界区(请求同一产品的消费者之间互斥)l (14)消费产品,并判断是否应
4、该释放产品所占缓冲区l (15)退出临界区,转(9)l (16)结束消费者线程 (17)生产者 (18)存在空缓冲区?有,则继续(19);无,则阻塞,再转 (18)(19)另一生产者在写?否,则转(20);是,则阻塞,再转 (19)(20)进入临界区(请求同一产品的生产者之间互斥)(21)在缓冲区中为本线程产品分配空间 (22)退出临界区 (23)写入产品到分配的缓冲区空间中 (24)结束生产者线程七、实验报告内容七、实验报告内容1.实验的程序源码2.运行程序,给出运行结果截图3.分析实验结果,得出结论l一、实验目的一、实验目的l在了解和掌握银行家算法的基础上,能熟练的处理课本例题中所给状态的
5、安全性问题,能编制银行家算法通用程序,将调试结果显示在计算机屏幕上,再检测和笔算的一致性。l二、实验内容二、实验内容l设计五个进程P0,P1,P2,P3,P4共享三类资源A,B,C的系统,A,B,C的资源数量分别为10,5,7。进程可动态地申请资源和释放资源,系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列;显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。l三、实验性质三、实验性质l验证性l四、实验学时四、实验学时l2学时l五、实验环境五、实验环境lC与C+程序设计学习与实验系统 l六、实验原理及步骤六、实验原理及步骤l1
6、.进程pi提出资源申请时,系统执行下列步骤:l(1)若RequestiNeedi,转(2);l 否则错误返回l(2)若RequestiAvailable,l 转(3);否则进程等待l3)假设系统分配了资源,则有:lAvailable:=Available-Requesti;lAllocationi:=Allocationi+Requesti;lNeedi:=Needi-Requestil(4)执行安全性算法,若系统新状态是安全的,则分配完成,若系统新状态是不安全的,则恢复原状态,进程等待l2.进行安全性检查,定义数据结构:lWork:ARRAY0.m-1 of integer;lFinish:
7、ARRAY0.n-1 of Boolean;lm代表资源的数量,n代表进程的数量l(1)Work:=Available;l Finish:=false;l(2)寻找满足下列条件的i:l a).Finishi=false;l b).NeediWork;l如果不存在,则转(4)l(3)Work:=Work+Allocationi;l Finishi:=true;l 转(2)l(4)若对所有i,Finishi=true,则系统处于安全状态,否则处于不安全状态l设request-i为进程pi的请求向量,如果requestij=K,表示进程pi需要K个Rj资源。当系统发出请求后,系统按下述步骤开始检查:
8、l(1)、如果requestij=needij,转向步骤2;否则报告出错,申请的资源已经大于它需要的最大值。l(2)、如果requestijid1-id2l BLOCK_QUEUE:-id3-id4l六、实验原理及步骤六、实验原理及步骤l1.启动C语言环境,新建文件。l2.假设在调度前,系统中有5个进程,他们的初始状态如下:lID 0 1 2 3 4lPRIORITY 9 38 30 29 0lCPUTIME 0 0 0 0 0lALLTIME 3 3 6 3 4lSTARTBLOCK 2 -1 -1 -1 -1lBLOCKTIME 3 0 0 0 0lSTATE 都为 READYl3.按照给
9、定进程,作为程序的输入,编写程序运行。l七、实验报告内容七、实验报告内容l1.实验的程序源码l2.运行程序,给出运行结果截图l3.分析实验结果,得出结论l一、实验目的一、实验目的l通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解,熟悉虚存管理的各种页面淘汰算法。通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。l二、实验内容二、实验内容l(1)用C语言实现对分页式存储管理中的硬件的地址转换和产生缺页中断。l(2)设计页表。l分页式虚拟存储系统是把作业的副本存放在磁盘上,当作业被选中时,可把作业的开始几页先装入主存且启动执行。为此,在为作业建立页表时,应说明哪些页已在主存
10、,哪些页尚未装入主存,页表的格式为:页 号 标 志 主存块号 在磁盘上的位置l(3)地址计算。l作业执行时,指令中的逻辑地址指出了参加运算的操作数存放的页号和单元号,硬件的地址转换机构按页号查页表,若该页对应标志为“1”,则表示该页已在主存,这时根据关系式:l 绝对地址=块号*块长+单元号l计算出欲访问的主存单元地址。按计算出的绝对地址可以取到操作数,完成一条指令的执行。若访问的页标志为“0”,则表示该页不在主存,这时硬件发“缺页中断”信号,由OS按该页在磁盘上的位置,把该页信息从磁盘读出装入主存后再重新执行这条指令。l(4)设计“地址转换”程序模拟硬件的地址转换工作。l当访问的页在主存时,则
11、形成绝对地址,但不去模拟指令的执行,而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时,则输出“*该页页号”,表示产生了一次缺页中断,执行缺页中断程序。该模拟程序的算法如图1.1所示。开始是取一条指令取指令中访问的页号查页表该页标志 =1?转缺页中断子程序形成绝对地址输出绝对地址有后继指令?结束取一条指令否是否l(5)缺页中断模拟 l如果访问页不在主存且页表未满,则调入一页并打印页表情况;如果该页不在主存且页表已满,则产生缺页中断,模拟算法如图1.2所示。l实验中采用FIFO算法进行页面淘汰。把在主存的页的页号按进入主存的先后次序排成队列,每次总是调出队首页。用数组存放页号的队列。
12、若分配给该作业的物理块数为m,则数组由m个元素组成,p0,p1pm-1,队首指针head,队尾指针tail。当装入新页时,将其页号装入数组。输出:页号lnumber输出:*lnumber页号为lnumber淘汰页的页号j=phead将页lnumber装入队尾输出:页号j修改页表:第j页存在标志改为“0”第lnumber页存在标记改为“1”第lnumber页修改标记改为“0”第lnumber页主存块号为第j页原主存块号l六、实验原理及步骤六、实验原理及步骤l1.启动C语言环境,新建文件。l2.假定主存的每块长度为128个字节;现有一个共七页的作业,其中的第0页至第3页已经装入主存,其余三页未装入
13、主存,主存;该作业的页表为:015011118012219013311021400225002360121l如果作业依次执行的指令序列(操作,页号,单元号)为:l(+,0,070)、(+,1,050)、(*,2,015)、(存,3,021)、(取,0,056)、(,6,040)、(移位,4,053)、(+,5,023)、(存,1,037)、(取,2,078)、(+,0,070)、(+,4,001)、(存,6,084)。l运行设计的地址转换程序,显示或打印运行结果。因仅模拟地址转换,并不模拟指令的执行,故可不考虑上述指令序列中的操作。l3.编写程序运行。l七、实验报告内容七、实验报告内容l1.实验的程序源码l2.运行程序,给出运行结果截图l3.分析实验结果,得出结论