操作系統之存儲管理——FIFO算法和LRU算法

操作系統之進程調度——優先權法和輪轉法（附上樣例講解）

操作系統之銀行家算法—詳解流程及案例數據

操作系統之多線程編程—讀者優先/寫者優先詳解

操作系統之存儲管理——FIFO算法和LRU算法

操作系統之磁盤調度——SCAN實例講解

要求

一、實驗目的

存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。

本實驗的目的是通過請求頁式管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式存儲管理的頁面置換算法。

二、實驗內容

（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）順序執行一條指令，地址為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）最近最少使用算法（LRU）；

3）最佳淘汰算法（OPT）；

4）最少訪問頁面算法（LFR）；

其中3）和4）為選擇內容

三、系統框圖

一、運行結果

a、運行程序：終端先顯示：

Start memory management.

Producing address flow, wait for while, please.

b、地址流、地址頁號流生成后，終端顯示：

There are algorithms in the program

1、Optimization algorithm

2、Least recently used algorithm

3、First in first out algorithm

4、Least frequently used algorithm

Select an algorithm number, please.

用戶輸入適當淘汰算法的號碼，并按回車，若是第一次選擇，輸出相應的地址頁號流。然后輸出該算法分別計算的用戶內存從2k ~ 32k時的命中率，若輸入的號碼不再1~4中，則顯示：

there is not the algorithm in the program,并重復b。

c、輸出結果后，終端顯示 “do you try again with anther algorithm(y/n)”。若鍵入y則重復b,否則結束。（一般講四種算法都用過后結束，以便比較）。

二、運行結果討論

1、比較各種算法的命中率

2、分析當用戶內存容量增加是對命中率的影響

分析

上面就是實驗要求，因為時間關系，只寫了fifo和lru兩種，但是這兩個會了，剩下的了解算法原理就很容易實現。

對于兩種算法的理解和實現為：

先進先出算法算法（Fifo）：

這個算法原理沒有算法，就是先進先出。對于這個結構最好采用的就算隊列了，對于java而言，我用的是list集合，每次添加數據的時候添加到第0位置，而如果移除的時候移除末尾的頁數。在這個過程中，每執行一條指令的時候，如果這個指令對應的地址（指令/10）在list中，那么就命中，否則就是缺頁，需要移除尾，在0位置添加元素。

舉個例子，頁面內存為3，（只能存三頁），要執行指令地址頁面對應為：4 2 3 4 1 2 1 5 6 3

那么流程順序為：（4）缺頁—>(2,4)缺頁—>(3,2,4)缺頁—>4命中—>（1,3,2）缺頁4被置換—>2命中—>1命中—>（5,1,3）缺頁2被替換—>(6,5,1)缺頁2被替換—>（3,6,5）缺頁1被替換。

最近最少使用算法（LRU）：

這個算法跟fifo其實還是挺像的，但是有一點區別，最近最少使用。也就是說在一個正常序列的時候如果命中的化，就會把這個地址的頁號移動到首位（或者鏈表首位）。而如果缺頁的時候，要把這個鏈表的末尾位置移除，因為末尾的元素是最近用的最少的（很久前才有的）。對于數據結構，我依然選擇Arraylist。每次遇到指令地址的時候我只需要特殊判斷下就可以了。我只為了實驗的目的，沒有考慮性能，因為檢查是否存在地址的時候我用了list.contains（）方法，這是線性查詢復雜度O（n）,如果數據量大可以list map組合使用，將查詢降低到O(logn).還可以開一個boolean數組標記讓查詢復雜度降低到O（1），（但是這樣的化增大空間），還好數據量不大，影響不大。

如果頁面內存為3，（只能存三頁），要執行指令地址頁面對應為：4 2 3 4 1 2 1 5 6 3

那么流程順序為（4)—>(2,4)—>(3,2,4)—>(4,3,2)命中—>(1,4,3)缺頁2被替換—>(2,1,4)缺頁—>(1,2,4)命中—>(5,1,2)缺頁—>(6,5,1)缺頁—>(3,6,5)缺頁

代碼

大致流程就是這樣，有一點區別。

下面附上我的ac代碼。有的解釋會在注釋中：

package 實驗; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; import java.util.Scanner; public class storemanage { static int mingzhong; static int lenyeliu=320; static int errortime;//失效次數 static int random[]=new int[330];//隨機指令 static Scanner sc=new Scanner(System.in); static void init()//初始隨機數 { int index=0; while(index<320) { int m=(int) (Math.random()*320); random[index++]=m;//順序指令 int m1=(int) (Math.random()*(m+1)); if(m1==320) {continue;}//跳出問本次 random[index++]=m1;//前地址部分 最大317 if(m1+1==320) {continue;}//跳出問本次 random[index++]=m1+1;//順序指令 int m2=(int) (Math.random()*(319-(m1+2))+m1+2); if(m2==320) {continue;}//跳出問本次 random[index++]=m2;//后地址 if(index>320) { break; } } } private static void lur() { for(int memory=2;memory<=32;memory++) { mingzhong=0;errortime=0; Queueq1=new ArrayDeque<>(); int index=0; while(index<320) { if(q1.size()list=new ArrayList<>(); int index=0; while(index<320) { if(list.size()

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

執行結果

可以看得出成功了。并且最后都是0.9因為固定缺頁數(首次命中)達到0.1.

如果對后端、爬蟲、數據結構算法等感性趣歡迎關注我的個人公眾號交流：bigsai

HTTP

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。