模拟操作系统中进程的三种基础状态与内存的分配和回收(最佳适配算法)

利用键盘模拟进程的三种操作状态，并且使用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 }