模擬操作系統中進程的三種基礎狀態與記憶體的分配和回收(最佳適配演算法)

利用鍵盤模擬進程的三種操作狀態，並且使用C++中的list模板模擬記憶體的分配和回收。

 能夠模擬進程的創建與撤銷過程

l可對進程的狀態進行全面的控制

按先進先出方式管理就緒和阻塞隊列，能夠按隊列形式輸出進程狀

用PCB代表進程，用全局變數表示進程的個數。

  1 #include <iostream>
  2 #include <list>
  3 #include <numeric>
  4 #include <algorithm>
  5 #include<stdlib.h>
  6 using namespace std;
  7 
  8 
  9 struct PCB                    //PCB結構體
 10 {
 11     char name[10];            //外部標記
 12     int PID;                //內部標記
 13     int    begin;                //起始地址
 14     int length;                //長度
 15     struct PCB* next;
 16 };
 17 
 18 
 19 struct Memory
 20 {
 21     int start;    //起始地址
 22     int len;    //長度
 23     bool operator < (const struct Memory  p) const
 24     {
 25         return len < p.len;
 26     }
 27 
 28 };
 29 typedef list <Memory> Memy;//用模板定義Memory的列表
 30 
 31 int SIZE;            //用來存儲記憶體的大小
 32 Memy   LM;            //用來存儲記憶體分配的鏈表
 33 Memy::iterator K;
 34 Memory L;            //第一塊完整的記憶體
 35 static int number = 0;
 36 //number用來標記進程的數量。
 37 
 38 //創建三個鏈表，分別代表，就緒，執行，阻塞
 39 struct PCB* Ready = new struct PCB;
 40 struct PCB* Blocked = new struct PCB;
 41 struct PCB* Running = new struct PCB;
 42 
 43 
 44 bool px(struct Memory m, struct Memory n)
 45 {
 46     return m.start < n.start;
 47 }
 48 
 49 
 50 void CreateProcess(struct PCB* &Ready, Memy &LM)//創建進程
 51 {
 52     LM.sort();
 53     struct PCB* P = new struct PCB;
 54     struct PCB* X = new struct PCB;//利用X來做到插入隊尾
 55 
 56     X = Ready;
 57 
 58     //cout << "請輸入此進程的名稱：" << endl;
 59     cin >> P->name;
 60 
 61     
 62     //cout << "請輸入此進程大小：" << endl;
 63     cin >> P->length;
 64 
 65     for (K = LM.begin(); K != LM.end(); K++)//分配記憶體，
 66     {
 67         Memy::iterator x;
 68         if (K->len <= 0)
 69         {
 70             cout << "已經沒有足夠的記憶體空間！" << endl;
 71             return;
 72         }
 73         if (K->len < P->length)
 74         {
 75             x = K;
 76             K++;
 77             if (K == LM.end())
 78             {
 79                 cout << "已經沒有足夠的記憶體空間！" << endl;
 80                 return;
 81             }
 82             else
 83             {
 84                 K = x;
 85                 continue;
 86             }            
 87         }
 88         else if (K->len >= P->length)
 89         {
 90             if (K->len - P->length <= 2)
 91             {
 92                 P->begin = K->start;
 93                 P->length = K->len;
 94                 LM.erase(K);
 95                 number++;
 96                 break;
 97             }
 98             else
 99             {
100                 P->begin = K->start;
101                 K->start += P->length;//修改起始地址
102                 K->len -= P->length;
103                 number++;
104                 break;
105             }
106         }
107         else
108         {
109             continue;
110         }
111     }
112 
113     P->PID = number;            //利用number來進行唯一系統內部進程標示
114     while (X->next != NULL)        //新建節點連接到鏈表尾部
115     {
116         X = X->next;
117     }
118     X->next = P;
119     P->next = NULL;
120 }
121 
122 
123 void sort1(Memy &LM)                //按照長度進行排序
124 {
125     LM.sort();
126 }
127 
128 
129 void EndProcess(struct PCB* &Running, Memy &LM)                //結束進程
130 {
131     if (Running->next == NULL)
132     {
133         cout << "沒有進程處於執行態！" << endl;
134         system("pause");
135         return;
136     }
137     LM.sort(px);
138     Memory O;
139     O.start = Running->next->begin;
140     O.len = Running->next->length;
141     if (LM.size() == 0)                            //系統剩餘空間為0，直接插入。
142     {
143         Memory M;
144         M.len = O.len;
145         M.start = O.start;
146         LM.push_back(M);
147     }
148     else
149     {
150         for (K = LM.begin(); K != LM.end(); K++)
151         {
152             if (K->start>(O.start + O.len))                        //上下都被占用            直接插入前面
153             {
154                 Memory m;
155                 m.len = O.len;
156                 m.start = O.start;
157                 LM.push_front(m);
158                 break;
159             }
160             else if ((O.start + O.len) == K->start)                //上占下空   改下區基址，改長度
161             {
162                 K->start = O.start;
163                 K->len += O.len;
164                 break;
165             }
166             else if ((K->start + K->len) == O.start)                //上空==============================================
167             {
168                 int l = K->len;
169                 Memy::iterator X;
170                 X = K;
171                 ++K;
172                 if (K != LM.end())
173                 {
174                     if (K->start == (O.start + O.len))            //上空下空
175                     {
176                         X->len = K->len + l + O.len;                //長度三合一//刪除++K
177                         LM.erase(K);
178                         break;
179                     }
180                     else                                             //上空 下占 改上區長度
181                     {
182                         X->len += O.len;
183                         break;
184                     }
185                 }
186                 else                                                //上空 下占 改上區長度
187                 {
188                     X->len += O.len;
189                     break;
190                 }
191             }
192             else if ((K->start + K->len)<O.start)                            //提前進入下一次迴圈                    
193             {
194                 continue;
195             }
196         }
197     }
198 
199 
200     while (Running->next != NULL)
201     {
202         struct PCB* P = Running->next;
203         P->next = NULL;
204         delete P;
205         Running->next = NULL;
206         number--;
207     }
208 }
209 
210 
211 void show(struct PCB* Ready, struct PCB* Running, struct PCB* Blocked)//顯示三種狀態的進程情況
212 {
213     cout << "就緒態：";
214     while (Ready->next != NULL)
215     {
216         cout << " name: " << Ready->next->name << "  begin: " << Ready->next->begin << "  length: " << Ready->next->length;
217         Ready = Ready->next;
218     }
219     cout << endl;
220     cout << "執行態：";
221     if (Running->next != NULL)
222     {
223         cout << "name: " << Running->next->name << " begin: " << Running->next->begin << " len: " << Running->next->length;
224     }
225     cout << endl;
226     cout << "阻塞態:";
227     while (Blocked->next != NULL)
228     {
229         cout << "name: " << Blocked->next->name << " begin: " << Blocked->next->begin << " len: " << Blocked->next->length;
230         Blocked = Blocked->next;
231     }
232     cout << endl;
233     int sum = 0;
234     for (K = LM.begin(); K != LM.end(); K++)
235     {
236         cout << "記憶體起始地址： " << K->start << "記憶體長度：" << K->len << endl;
237         sum += K->len;
238     }
239     cout << "進程所占空間: " << (SIZE - sum) << endl;
240     cout << "系統空閑空間: " << sum << endl;
241     sum = 0;
242 }
243 
244 
245 void Run(struct PCB* &Ready, struct PCB* &Running)       //執行函數，查詢就緒態中的PCB
246 {
247     while ((Ready->next != NULL) && (Running->next == NULL))
248     {
249         struct PCB* Z = Ready->next;
250         Running->next = Z;
251         Ready->next = Ready->next->next;
252         Z->next = NULL;
253     }
254 }
255 
256 
257 void Block(struct PCB* &Running, struct PCB* &Blocked)     //執行到阻塞的轉換
258 {
259     struct PCB* Head = Blocked;
260     while (Running->next != NULL)
261     {
262         while (Head->next != NULL)
263         {
264             Head = Head->next;
265         }
266         Head->next = Running->next;
267         Running->next = NULL;
268     }
269 }
270 
271 
272 void TimeUp(struct PCB* &Running, struct PCB* &Ready)                    //時間片到
273 {
274     struct PCB* Head = Ready;
275     struct PCB* P = Running->next;
276     P->next = NULL;
277     while (Running->next != NULL)
278     {
279         while (Head->next != NULL)
280         {
281             Head = Head->next;
282         }
283         Head->next = P;
284         Running->next = NULL;
285     }
286 }
287 
288 
289 void Wake(struct PCB* &Blocked, struct PCB* &Ready)//喚醒進程
290 {
291     if (Blocked->next == NULL)
292     {
293         cout << "沒有進程處於阻塞態！" << endl;
294         system("pause");
295         return;
296     }
297     struct PCB* P = Ready;
298     while (P->next != NULL)
299     {
300         P = P->next;
301     }
302     if (Blocked->next != NULL)
303     {
304         P->next = Blocked->next;
305         Blocked->next = Blocked->next->next;
306         P->next->next = NULL;
307     }
308     else
309     {
310         cout << "沒有處於阻塞狀態的進程！" << endl;
311     }
312 
313 }
314 
315 
316 void interface()
317 {
318     cout << "========幫助========" << endl;
319     cout << "C----------創建進程" << endl;
320     cout << "T----------時間片到" << endl;
321     cout << "S----------進程阻塞" << endl;
322     cout << "W----------喚醒進程" << endl;
323     cout << "E----------結束進程" << endl;
324     cout << "H----------查看幫助" << endl;
325 
326 }
327 
328 
329 void start()
330 {
331     cout << "請輸入記憶體的起始地址：" << endl;
332     cin >> L.start;
333     cout << "請輸入記憶體的大小：" << endl;
334     cin >> L.len;
335     SIZE = L.len;
336     LM.push_front(L);
337 }
338 
339 
340 void process()                    // 中間過程
341 {
342     interface(); 
343     system("pause");
344     char choice;
345     do
346     {
347         system("cls");        
348         cin >> choice;
349         switch (choice)
350         {
351         case 'C':LM.sort(px); CreateProcess(Ready, LM); Run(Ready, Running); show(Ready, Running, Blocked); system("pause"); break;
352         case 'T':TimeUp(Running, Ready);  Run(Ready, Running); show(Ready, Running, Blocked); system("pause");  break;
353         case 'S':Block(Running, Blocked);  Run(Ready, Running); show(Ready, Running, Blocked); system("pause"); break;
354         case 'W':Wake(Blocked, Ready); Run(Ready, Running); show(Ready, Running, Blocked); system("pause"); break;
355         case 'E':EndProcess(Running, LM); Run(Ready, Running); show(Ready, Running, Blocked); sort1(LM); system("pause"); break;
356         case 'H':interface();break;
357         default:cout << "輸入錯誤，請重新輸入！" << endl;  system("pause"); break;
358         }
359 
360     } while (number != 0);
361 }
362 
363 
364 void main()
365 {
366     Ready->next = NULL;
367     Blocked->next = NULL;
368     Running->next = NULL;
369     start();
370     process();
371     cout << "所有進程已結束" << endl;
372     system("pause");
373 
374 }