Article directory
-
- 1. Experimental purpose
- 2. Experiment content
- 3. Experimental requirements
- 4. Experimental ideas
- 5. Deadlock detection algorithm simulation implementation program implementation
-
- 5.1. Introduction to relevant environments
- 5.2.Test
- 6. Experiment summary
-
- 6.1. Completion of experimental requirements
- 6.2. Technical difficulties and solutions
- 6.3. Experimental thoughts and experience summary
- 6.4. Reference links
- 7. Code Appendix
1. Experiment purpose
Understand and master the basic design ideas, key data structures and algorithm processes of deadlock detection algorithms.
2. Experimental content
Use C language to design and implement the deadlock detection algorithm, build the process-resource scenario randomization mechanism of the computer system, and test and verify your own deadlock detection algorithm implementation plan.
3. Experimental requirements
(1) Design and implementation of deadlock detection algorithm based on C language;
(2) The construction of a process-resource scenario random generation mechanism of the computer system (randomly generates the system’s various resource allocation details, a set of concurrent processes, and the current occupancy/demand quantity of various resources);
(3) The algorithm prototype should be able to correctly determine whether the corresponding process-resource scenario is in a deadlock state;
(4) Carry out complete testing and verification based on process-resource scenarios for the deadlock detection algorithm prototype.
4. Experimental ideas
According to the experimental requirements, the total number of system resources is randomly generated, so that it is better to use a process group test sample to determine whether there is a deadlock situation.
According to the ppt explanation in the classroom, first set up the Finish, Work, Max, Allocation, Need, Available and other arrays to simulate thread resources. It is divided into init function, distribute function and show function to perform the main functions.
The init function mainly reads the number of threads, the resources required by each thread and the number of allocated resources from the txt file according to the established format. And the total number of system resources is generated along with the file.
The Distribute function is used to determine whether there is a deadlock. If so, an alarm will be issued. If not, a safe sequence will be found. Several functions are also set up to assist the distribute function. Yes, the structure is more clear.
The Show function displays a safety sequence or deadlock alarm while there is a safety sequence.
5. Deadlock detection algorithm simulation implementation program implementation
5.1. Introduction to relevant environments
Operating system: window 10 21H2
Development environment: Clion-2022.2.1-Windows
Compiler: mwing-10.0
5.2. Test
Initial data
Chart 5 1 test1 initial data
Result Verification
Chart 5 2 test test results
The Init function generates a different total number of system resources each time. It first determines that the resources that have been allocated in the system can be satisfied. This ensures that system deadlock occurs during the running process, not at the beginning.
In this way, as long as a safe sequence can be found, it will be printed out and continue running; finally, as long as a deadlock is found, the program will stop and the program that has been executed before the deadlock will be output.
6. Experiment summary
6.1. Completion of experimental requirements
Successfully complete lab requirements.
6.2. Technical difficulties and solutions
At the beginning, I found that the program would get stuck. Finally, I located the location of resource initialization and found that some arrays were not reinitialized and data overlay occurred, so I used the memset function to reset them.
6.3. Experimental thoughts and experience summary
We can store a lot of initialized data or configuration information in files and perform file reading and writing operations, thus ensuring the input format and efficiency.
It is found that the buffers of cout and cerr may not be the same. In this case, the contents of cout and cerr may be misaligned without refreshing the buffer. This is also a situation that has not been encountered before.
6.4. Reference links
- ZGSOS Operating System Experiment Guide “Experimental Topic 11_Deadlock Detection Algorithm Simulation Implementation”
7. Code Appendix
8. #include <iostream>
9. #include <vector>
10. #include <fstream>
11. #include <iostream>
12. #include <string>
13. #include <string.h>
14.
15.
16. using namespace std;
17. #define THREAD 5
18. #define RESOURCE 3
19.
20. int Finish[THREAD] = {<!-- -->0};
21. int Work[RESOURCE] = {<!-- -->0};
22. int Max[THREAD][RESOURCE] = {<!-- -->0};
23. int Allocation[THREAD][RESOURCE] = {<!-- -->0};
24. int Need[THREAD][RESOURCE] = {<!-- -->0};
25. int Available[RESOURCE] = {<!-- -->0};
26. int n; // num for thread
27. int m; // num for classification of resource
28. ifstream fin;
29.
30. int Security[THREAD] = {<!-- -->-1};
31. int count = 0; // the order of security line
32. int tem_allocation[RESOURCE] = {<!-- -->0};
33.
34.
35. int init(string & amp;test_file_path= (string & amp;) "../test1"){<!-- -->
36.
37. fin.open(test_file_path);
38. if(!fin){<!-- -->
39. cerr << "file " << test_file_path << " open error!\\
";
40. return -1;
41. }
42.
43. fin >> n >> m;
44.
45.
46.
47.
48. for(int i=0;i<n; + + i){<!-- -->
49. for(int j=0;j<m; + + j){<!-- -->
50. fin >> Max[i][j];
51. }
52. for(int j=0;j<m; + + j){<!-- -->
53. fin >> Allocation[i][j];
54. tem_allocation[j] + = Allocation[i][j];
55. }
56. for (int j=0; j<m; + + j) {<!-- -->
57. Need[i][j] = Max[i][j] - Allocation[i][j];
58. }
59. }
60.
61. while(1){<!-- -->
62. for (int i = 0; i < m; + + i) {<!-- -->
63. Available[i] = rand();
64. // consider the test sample, make random num range [0, 15] to make the die lock happen
65. }
66. int flag_allocation = 0;
67. for(int i=0;i<m; + + i){<!-- -->
68. if(tem_allocation[i] >= Available[i]){<!-- -->
69. flag_allocation = 1;
70.break;
71. }
72. Available[i] -= tem_allocation[i];
73. }
74. if(flag_allocation){<!-- -->
75. // cout<< "test sample error initial allocation resource is bigger than total \\
";
76.continue;
77. }
78. else {<!-- -->
79. cout << "the random original Available array is \\
";
80. for (int i = 0; i < m; + + i) {<!-- -->
81. cout << Available[i] << "\t";
82. }
83. cout << "\\
";
84.break;
85. }
86. }
87.
88. // fin.close();
89. return 0;
90. }
91.
92. int finish_all_true(){<!-- -->
93. int result = 0;
94. for(int i=0;i<n; + + i){<!-- -->
95. result + =Finish[i];
96. }
97. if(result==n){<!-- -->
98. return 0;
99. }
100. else{<!-- -->
101. return -1;
102. }
103. }
104. int satisfied(int & id_thread){<!-- -->
105. int flag = 0;
106. for(int i=0;i<m; + + i){<!-- -->
107. if(Work[i]>=Need[id_thread][i]) continue;
108. else {<!-- -->
109. flag = 1;
110.break;
111. }
112. }
113. if(flag) return -1;
114. else return 0;
115. }
116. int work_assign_available(){<!-- -->
117. for(int i=0;i<m; + + i){<!-- -->
118. Work[i] = Available[i];
119. }
120. return 0;
121. }
122. int distribute(){<!-- -->
123. string tem_string;
124.
125. fin >> tem_string;
126. // if(tem_string == "end"){
127. //
128. // }
129. // else if(tem_string=="request"){
130. // int tem_id_thread;
131. // int tem_resource_array[m];
132. // int num_special_request;
133. // fin >> num_special_request;
134. //
135. // for(int j=0; j<num_special_request; + + j){
136. // fin >> tem_id_thread;
137. // int flag = 0;
138. // for (int i = 0; i < m; + + i) {
139. // fin >> tem_resource_array[i];
140. // if(tem_resource_array[i]<=Need[tem_id_thread][i]){}
141. // else{
142. // flag = 1;
143. // return -1;
144. // }
145. // }
146. //
147. // if(flag==1){}
148. // else{
149. // int k = 0;
150. // for(;k<m; + + k){
151. // if(tem_resource_array[k]<=Need[tem_id_thread][k] & amp; & amp; tem_resource_array[k]<=Available[tem_id_thread]){}
152. // else {
153. // return -1;
154. // break;
155. // }
156. // }
157. // if(k==m){
158. // work_assign_available();
159. // if(Finish[tem_id_thread]==0 & amp; & amp; satisfied(tem_id_thread)==0) {
160. // Finish[tem_id_thread] = 1;
161. // Security[count + + ] = tem_id_thread;
162. // for (int j = 0; j < m; + + j) {
163. // Available[j] = Work[j] + Allocation[tem_id_thread][j];
164. // }
165. // }
166. // else{
167. // return -1;
168. // }
169. // }
170. // }
171. // }
172. // }
173.
174.
175.
176.
177. while(1){<!-- -->
178. int flag = 0;
179. if(finish_all_true()==0){<!-- -->
180. cout << "this test sample has a security line\\
";
181. return 0;
182. break;
183. }
184. work_assign_available();
185.
186. for(int i=0;i<n; + + i){<!-- -->
187. if(Finish[i]==0 & amp; & amp; satisfied(i)==0){<!-- -->
188. Finish[i] = 1;
189. Security[count + +] = i;
190. for(int j=0;j<m; + + j){<!-- -->
191. Available[j] = Work[j] + Allocation[i][j];
192. }
193. work_assign_available();
194. flag = 1;
195. }
196. }
197. if(!flag){<!-- -->
198. cout << "this test sample has no security line\\
";
199. return -1;
200.break;
201. }
202. }
203.
204. }
205.
206. int show_security_line(string & amp;path){<!-- -->
207. cout << path << " security line is followed\\
";
208. for(int i=0;i<n; + + i){<!-- -->
209. cout << Security[i] << "\t";
210. }
211. cout << endl;
212. fin.close();
213. }
214. int show_die_lock(string & amp; test_file_path){<!-- -->
215. cout << test_file_path<< " die lock" << endl;
216. cout << " btw the Finish array is followed\\
";
217. for (int i = 0; i < n; + + i) {<!-- -->
218. cout << Finish[i] << "\t";
219. }
220. cout << "\\
";
221. cout << " the order is\\
";
222. for (int i = 0; i < count; + + i) {<!-- -->
223. cout << Security[i] << "\t";
224. }
225. cout << '\\
';
226. fin.close();
227. }
228. int main() {<!-- -->
229. string test_file_path = "../test1";
230.
231. while(1){<!-- -->
232. if (init(test_file_path) == -1) return -1;
233. if(distribute()==0){<!-- -->
234. show_security_line(test_file_path);
235. memset(Finish, 0, sizeof(Finish));
236. memset(tem_allocation, 0, sizeof(tem_allocation));
237. count = 0;
238. cout << endl;
239. }
240. else{<!-- -->
241. show_die_lock(test_file_path);
242. break;
243. }