2023年操作系统请求式存储管理实验报告.docx

《2023年操作系统请求式存储管理实验报告.docx》由会员分享，可在线阅读，更多相关《2023年操作系统请求式存储管理实验报告.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统实验三存储管理实验班级:学号:姓名:f o r (in t i =0; imax n ； i+)pa g e i = insti/10；)v o id FIFO_so 1 ve ()mem s et (in z fals e , size o f (in);int faultn = 0;/缺页率int p tr, i ;预调页填满空间Pt r = 0；下一个要放的位置fo r (i=0; ima xn & p t rs i ze; i + + )i f ( in p age i)(pi n ptr+ + = page i;inpagei = tr u e ；fault_n+;)/继续执

2、行剩下的指令pt r = 0 ;/队列里最先进来的位置，即下一个要被替换的位置f o r (; imaxn； i + + )if ( ! i n pa g e i)(in pin p tr = fal s e ；in p a ge i tru e ；pi n pt r = pagei;f a ult_n +；ptr = (ptr+ 1 ) % size;)p r i ntf ( nBy FIFO algor i thm, the fault-page n u mber i s： %dn”，f a u 1 t_n);printf (the hi t ratio i s ：% .21 f n H

3、, ( 1 -( f a u i t_n+0.0)/ 32 0 .0)； ) void LRU_solve ()(i n t 1 t u m a xp ; / / las t _t i me _useint t i = 1;/模拟时间in t f ault_n = 0；mems e t ( 1 tu, 0, siz e o f (Itu);memset (in, f alsez si z e of (in);memset (pi n , -1, sizeof (pi n );int min, ptr, i, j;f o r ( i =0; imaxn; i+)if (! in p agei)/

4、 /寻找1 rumin=10 0 00 0 0 ； ptr = 0;or ( j =0；j siz e ; j +)if (Itu j mi n )min =1 t u j ;ptr = j;/替换或写入if (p i n ptr != -1)in pi n ptr = f a Isein p ag e i = t r ue；pinptr = pa g e if a u 1 t _n +；Itu p t r = ti+ + ；)else/ /已经在内存里则只需更改最近使用时间(f o r (j = 0; j j ;mems e t ( i nz f al S ez size 0 f (in);

5、mems e t ( n tu, 1 z s i zeof (ntu)；/预调页填满i nt ptr = 0;for (i = 0； ima x n & fault _nsiz e ； i+)i(! inpagei)(in P a g e i = t r ue;pinptr = pa g e i；fa u It-n+ ;ptr -+;/初始化ntu数组p tr = 0;for ( j=i ; j m a xn & ptr32 ; j +)if (nt u page j =n t u page j = j ;pt r+；)in t max;for (; imaxn ; i+)(if ( ? i

6、npage i )(max = 0 ;ptr = 0;f o r ( j = 0 ； j max)(ma x = ntu pin j ;P t r = j；)inpin ptrf als einpage i trueP inptr = p age i ；fault- n +；ntu pagei = -1;f o r (j =i+l； j fault_n );p r i n t f ( the h it ratio i s ： %. 21fnn z (1 (faultn +0.0 )/320.0);)in t mai n ()s r and ( t ime (NULL)；we 1 c om e

7、()；int ch o ic e ；while(1)(in p ut_hi n t ();sea n f (d, &choic e )；prin t f ( nu)；i f ( c h oic e = 0)prin t f (BYE-BYE ! ! !n ) break:if (choice = 1)(p r odu c e _ i n st ()；turn_ p ag e _add r e ss ()；p r intf ( Ne w page address seq u ence i s set O K! ! ! n *)；)else i f (choi c e = 2)(pr i ntf

8、( P 1 e a se i np u t the size of m e m o ry p a ge n umbe r ： s canf( ”, &size);else if (c h oi c e = 3)F IFO_s o Ive ();e 1 s e if (choice = 4)LRU_ s olv e ()；else if (c h o ic e = 5)0 pT_solve ();elsep rintf (INPUT ERROR ! ! nH);re t urn 0 ;6.运营结果及分析6.1. 运营（以某两次运营结果为例，列表如下：）内存451015202532FIFO28 5

9、27 22 301781359032LRU2852742241 851399 132OPT22120 21 4 09 6684832FIFO2 7 22 622061671 288232LRU2712 652041631308632OPT2011 8312792664732随着页数的增多，除了 FIFO对某些序列会有Beladys anomaly （详见6.2）外,大部分情况和LRU算法、OPT算法都是缺页率减小。OPT是抱负情况，效率是最高的。当然当不缺页时，所有的算法缺页次数都是把所有页调进去的次数。LRU算法有时候和FIFO算法的效率差别并不大。甚至有时候它还比FIFO低一些的。6. 2

10、. Belady s anom a ly如下，我稍微改了下输入，手动输入课本上的样例，编程见证了 Belady异常现。这是只有FIFO算法才有的异常。12set memory page numher4solue by LRU algorithm0- -exit1 -create new instruction sequence3-solue by FIFO aIgorithm5- -solue by OPT algorithm mmmmmmwmmPlease input Vour choice：夕y FIFO Algorithm, the fault-page number is：9lease

11、 input the size of memory page number：1 - create new instruction sequence 3*-solue by FIFO algorithm5solve by OPT algorithm*Please input Vour choice：2 一-set memory page numberto 324solue by LRU algorithm0exitFIFO algorithm, the fault page nunhei* is ：10.。实验目的错误!未定义书签。1 .实验内容。错误!未定义书签。（1 ）通过随机数产生一个指令

12、序列，共320条指令错误!未定义书签。（2）将指令序列变换成为页地址流。错误!未定义书签。（3）计算并输出下述各种算法在不同内存容量下的命中率。错误!未定义书签。2 .随机数产生办法错误!未定义书签。环境说明错误!未定义书签。3 .。程序设计说明。错误!未定义书签。4 .1全局变量。错误!未定义书签。4. 2.，随机指令序列的产生错误!未定义书签。4. 3. FIFO算法错误!未定义书签。1.4. o LRU算法错误!未定义书签。1.5. OPT算法错误!未定义书签。5 .编程实现（源程序）:。错误!未定义书签。6 .。运营结果及分析错误!未定义书签。1. 1.运营（以某两次运营结果为例，列表

13、如下：）。错误!未定义书签。6. 2Belady s an o maly。错误!未定义书签。1 .实验目的存储管理的重要功能之一是合理地分派空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的H的是通过请求页式存储管理中页面置换算法模拟设计，解虚拟存储技术的特点，掌握请求页式存 储管理的页面置换算法。2 .实验内容（1 ）通过随机数产生一个指令序列，共3 2（）条指令指令的地址按下述原则生成：a ） 50%的指令是顺序执行的：b） 2 5%的指令是均匀分布在前地址部分；c） 25%的指令是均匀分布在后地址部分；具体的实行方法是：a） 在0 ,319的指令地址之间随机选取一起点m；b）顺序执

14、行一条指令,即执行地址为m+l的指令；c）在前地址0, m+l中随机选取一条指令并执行，该指令的地址为“；d）顺序执行一条指令，其地址为m，+l;e ） 在后地址m2, 31 9 中随机选取一条指令并执行；f）反好上述环节a ）f ）,直到执行320次指令。（2）将指令序列变换成为页地址流设：a）页面大小为1K；b）用户内存容量为4页到3 2页;c)用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第。页(相应虚存地址为0,9)；第1 0条第19条指令为第1页(相应虚存地址为1 0, 1 9 ); 第3 10条第319条

15、指令为第3 1页(相应虚存地址为310, 3 1 9)。按以上方式，用户指令可以组成32页。(3)计算并输出下述各种算法在不同内存容量下的命中率a)先进先出的算法(FIFO);b)最近最少使用算法(LRU)；c)最佳淘汰算法(OPT)；命中率=一页面失效次数/页地址流长度在本实验中，页地址流长度为320,页面失效次数为每次访问相应指令时，该指令所相应的页不在内存的次数。3.随机数产生办法关于随机数产生办法，可以采用操作系统提供的函数，如Linux或UN I X系统提供函数srand ()和rand(), 分别进行初始化和产生随机数。例如：sr a nd ()；语句可以初始化一个随机数；a0 =

16、 10* rand() / 32767* 3 19+1;a 1 =10*ran d ()/3 2 7 6 7*a0;语句可以用来产生a 0与中的随机数。环境说明此实验采用的是Win7下C o d e :blocks 10. 0 5编译器编程。此wo r d实验文档中采用notepa d +的语法高亮。4.程序设计说明4. 1.全局变量con s t int m a xn = 320;/ /序列个数const int max = m a xn +20; / /数组大小con s t int maxp = ma x / 10; / / 最大页数in t i nst max ”/指令序列int p

17、age m a x ;/页地址流int s i ze; / /内存能容纳的页数b ool in maxp ; /该页是否在内存里，提高效率int pi n maxp ；/现在在内存里的页其中in数组是为了方便直接判断该页是否在内存里，而不用遍历内存里所有页来判断。faul t _ n用来记录缺页次数。4. 2.随机指令序列的产生按照实验规定的写了，但是由于没有考虑细节，开始时出了点问题。（I）当m=3 1 9时,我们顺序执行m+1会产生第32页的页地址，从而使页地址没能按规定限制在0, 31 之间。解决方法:采用循环模加来避免超过范围。（2） 但是这样之后有也许出现模0的问题。所以我索性将等于

18、0的模数都赋值为1 6 0 .最后的程序如下。void pr 0 duce_i n s t ()i nt m, n ；int num = 0;while(num ma x n J(m = rand() % ma x n；i nst n um+ = (m+1) %maxn;f (num = m a xn) break;m = (m+2)% m a x n ；f (m = 0) m = 1 6 0 ;n = r a nd () % m;inst num+ = (n+ 1 ) %maxn；if (num = ma x n) b r eak ,n = (n+2) % maxn;m = maxn - n

19、;i f(m = 0) m = 1 60;m = r a nd() % m 4- n;inst n u m+ = m;)4. 3. FIFO 算法定义变量ptrc开始先预调页填满内存。在这部分,Ptr指向下个要存放的位置。之后继续执行剩下的指令。此时,Pir表达队列最前面的位置,即最先进来的位置，也就是下一个要被替换的 位置。pt r用循环加抑模拟循环队列。5. 4. LRU 算法定义数组ltu,即1 a s t_time_u s g来记录该页最近被使用的时间。定义变量ti模拟时间的变化，每执行一次加一。这个算法，我没有预调页，而是直接执行所有指令。若当前需要的页没在内存里，就寻找最近最少使用

20、的页，也就是1 t u口最小的页，即最近一次使用时间离现 在最久的页，然后替换掉它。或者在内存尚未满时，直接写入，这个我以初始化内存里所有页为T来实现。若已经在内存里了，则只遍历内存内的页，把当前页的最近使用时间改一下即可。6. 5. OPT算法定义数组ntu,即nex t _time_use来记录下一次被使用的时间，即将来最快使用时间。初始化为-1 .开始时预调页填满内存里的页。同样运用变量Plr来表达下一个要存放的位置从而控制预调页的过程。接着初始化ntu数组为-1。然后求出每一页卜.一次被使用的指令号，以此代替使用时间。假如所有剩卜的序 列都没有用该页时，则还是-1 .这种值为-1的页显

21、然是最佳替换对象。然后执行所有剩下的指令。当该页不在内存里时，遍历ntu数组，碰到-1的直接使用该页，没有则用nt u 值最大的，也就是最晚使用的。无论该页在不在内存里，由于这一次已经被使用了，所以都应当更新这个页的ntu,只需往前看要执行的页 流，记录下第一个碰到的该页即可。假如没有找到同样添一 I即可。7. 编程实现（源程序）:# i n c lud e include # inc 1 ude includ e string.husing name S p ace st d ;const int max n = 32 0 ；/序列个数const i nt max = m a x n +2

22、0 ; 数组大小const int m a xp = max/ 1 0; /最大页数i nt inst max ； /指令序列int pa g e max ； / /页地址流int si z e;/内存能容纳的页数bool i nm a x p ； 该页是否在内存里，提高效率int pin m a xp ；/现在在内存里的页void welc o me ()(printf ( * -k * * * * * *n);printf (* *B y s chne e On2023-12-06* *nH)；p r in t f ( * *班级：0 9 2 11 3 1 1 班内序号：30*nn);pr

23、intf ( *nn”)void i n p u t_hint ()pr i n t f ( M n 1 -create n ew inst r u c t i on se q uence2 -s e t memo r y pag en u mber (4 to 3 2) n )；printf (H3 -solve b y FIFO alg o r i thm4 -solve by L RU a 1 go r it h m n )；pri n t f (n5-sol v e by OPT a Igorit h m0 -exitn*);print f ( * * *p_e a s e input

24、 You r c hoi c e:);/*通过随机数产生一个指令序列，共320条指令*/v oid p r oduc e _i n s tint m, n;while ( n um maxn)m = r a nd () % maxn;inst num+ = (m+1) %m a x n：if (n u m = ma x n) break;m = (m+2) % ma x n ；i f (m = 0) m = 16 0;n = rand () % m；ins t num+ = ( n + 1 ) %ma x n;i f (num = maxn) b r ea k ;n = (n+2) % m a x n;m = max n - n；i f (m = 0) m = 16 0;m = rand() % m + n;inst num+ + = m;/ *将指令序列变换成为页地址流* /void t urn_ p ag e _ a ddr e ss ()