FZU 1893 內存管理

E - 內存管理

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

在為進程動態分配內存時,操作系統必須對其進行管理。一種管理內存的方式是，維護一張記錄內存使用情況的表來模擬內存的存儲情況，其任一表項可能是以下兩種情況之一：一個已分配給進程的內存區或者一個空閒的內存區。表中每一個表項含有以下內容：空閒區或已使用內存區的指示標志、內存大小、指向下一表項的指針。

一個表項一般有一個前驅表項和一個後繼表項（除非這個表項是內存的最底端或最頂端），已使用區表項的前驅表項和後繼表項可能是已使用區表項也可能是空閒區表項，而空閒區表項的前驅表項和後繼表項只可能是已使用區表項，因為如果兩個空閒區表項如果互為相鄰的表項，我們就可以將它們合並為一個空閒區表項，內存大小為兩個空閒區表項之和。

當系統創建一個新的進程時，有很多種方法可以用來為新創建的進程分配內存，在這裡我們假設已知新進程要占用的內存大小，並只可能給進程分配連續的內存空間。在本題中，我們采用最佳適配算法來分配內存。最佳適配算法搜索整個表，找出夠用的最小的空閒區（如有多個，取表中最前的），並將新進程分配在空閒區的頂部，如有剩余內存仍作為空閒區表項，並且為新已使用區表項的下一表項。

當系統結束一個進程時，在整個表中找到相應的已使用區表項並將其變為空閒區表項。

你的任務是編寫一個程序，來實現這樣一個內存管理的過程。在本題中,初始時內存表只有一個內存空閒區表項，且內存大小為100個單位大小。 Input

 

 

輸入數據第一行為一整數T，表示有T組輸入數據。

每組數據每行是一個系統命令，包括“Create”,“Delete”,“Print”，“End”，每條命令後面的參數如下：

Create：兩個整數i和size，i表示新進程的進程號，i>0，size表示新進程需占用的內存大小，size>0，輸入保證新進程的進程號與已存在的進程號不同。

Delete：一個整數i，i>0，表示要結束的進程號。

Print：無參數。

End：無參數，不做任何處理，表示系統終止命令。

注意：輸入保證出現的表項個數不超過100個。Output

 

 

對於Create命令，如果成功創建新進程，輸出一行“Create process i of size s successfully!”，其中i為新進程的進程號，s為新進程占用的內存大小；如果無足夠大小的內存空閒區，輸出一行“No enough memory!”。

對於Delete命令，如果成功結束進程，輸出一行“Delete process i of size s successfully!”，其中i為結束進程的進程號，s為該進程占用的內存大小；如果內存中無該進程，輸出一行“No such process!”。

對於Print命令，將內存表從表頭開始按順序輸出，每行輸出一個表項，進程表項格式為“P 進程號 內存大小”，空閒區表項格式為“H 內存大小”。

對於End命令，不做任何處理，終止程序。Sample Input

 

2

Create 1 30

Create 2 20

Create 3 30

Print

Create 4 100

Delete 4

Delete 2

Print

Delete 3

Print

End

Create 1 100

Print

End

Sample Output

Create process 1 of size 30 successfully!

Create process 2 of size 20 successfully!

Create process 3 of size 30 successfully!

P 1 30

P 2 20

P 3 30

H 20

No enough memory!

No such process!

Delete process 2 of size 20 successfully!

P 1 30

H 20

P 3 30

H 20

Delete process 3 of size 30 successfully!

P 1 30

H 70

Create process 1 of size 100 successfully!

P 1 100

 

其實這道題就根據題目意思一步一步來寫就可以了，簡單是簡單，但是很煩，細節要注意，尤其是關於頭和尾的操作要單獨算，也不要忘記把相鄰的空內存合並，發現很多人都用鏈表寫的，表示還沒學哇，就用vector寫了一個，應該還是很好理解的。

代碼如下：

 

#include
#include
#include
#include
#include
using namespace std;
char str[100];
int arr[105];
struct node
{
	int id;
	char state;
	int size;
};
vector G;
int main()
{
	int t, tmp, msize, flag, a, j;
	scanf("%d", &t);	
	while(t--)
	{
		node in;
		in.id = 0;
		in.state = 'H';
		in.size = 100;
		G.push_back(in);
		while(~scanf("%s", str))
		{
			if(strcmp(str, "End") == 0) break;
			
			if(strcmp(str, "Create") == 0) 
			{
				scanf("%d%d", &in.id, &in.size);
				tmp = 0,  msize = 200;
				for(int i = 0; i < G.size(); i++)
				{
					if(G[i].state == 'H')
					{
						if(G[i].size >= in.size && G[i].size < msize)
						{
							msize = G[i].size;
							tmp = i;
						}
					}
				}
				if(msize == 200) printf("No enough memory!\n");
				else
				{
					in.state = 'P';
					G[tmp].size -= in.size;
					G.insert(G.begin()+tmp, in);
					if(G[tmp].size == 0)
					{
						G.erase(G.begin() + tmp);
					}
					printf("Create process %d of size %d successfully!\n", in.id, in.size);
				}
			}
			
			if(strcmp(str, "Print") == 0)
			{
				for(int i = 0; i < G.size(); i++)
				{
					if(G[i].state == 'P')
						printf("%c %d %d\n", G[i].state, G[i].id, G[i].size);
					else
						if(G[i].size != 0)
						printf("H %d\n", G[i].size);
				}
			}
			
			if(str[0] == 'D')
			{
				flag = 1;
				scanf("%d", &a);
				for(j = 0; j < G.size(); j++)
				{
					if(G[j].id == a && G[j].state == 'P')
					{
						printf("Delete process %d of size %d successfully!\n", a, G[j].size);
						a = 0;
						G[j].state = 'H';
						if(j == 0)
						{
							if(G[1].state == 'H')
							{
								G[0].size += G[1].size;
								G.erase(G.begin() + 1);
							}	
						}
						else
						{
							if(j == G.size())
							{
								if(G[j-1].state == 'H')
								{
									G[j-1].size += G[j].size;
									G.erase(G.begin() + j);
								}	
							}
							else
							{
								if(G.size() > 1)
								{
									if(G[j-1].state == 'H')
									{
										G[j].size += G[j-1].size;
										G.erase(G.begin()+j-1);
										flag = 0;
									}
									if(G[j+flag].state == 'H')
									{
										G[j+flag-1].size += G[j+flag].size;
										G.erase(G.begin()+j+flag);
									}
								}
								break;
							}
						}
					}
				}
				if(a != 0) printf("No such process!\n");
			}
		}
		G.clear();		
	}
	return 0;
}