/*實習二  主存空間的分配和回收
一、實習內容
主存儲器空間的分配和回收。
二、實習目的
通過本實習幫助理解在不同的存儲管理方式下應怎樣貯存空間的分配和回收。
三、實習題目
本實習有兩題，可任選一題。
第一題：在可變分區管理方式下采用首次適應算法實現主存分配和回收。
[提示]：
(1)	可變分區方式是按作業需要的主存空間大小來分割分區的。當要裝入一個作業時，根據作業需要的主存
容量查看是否有足夠的空閑空間，若有，則按需分配，否則，作業無法裝入。假定內存大小為128K，
初始狀態見右圖。空閑區說明表格式為：
起址--指出空閑區的啟始地址；
長度--一個連續空閑區的長度；
狀態--有兩種狀態，一種是"未分配"狀態，另一種是"空表目"狀態。
(2)	采用首次適應算法分配。運行時，輸入一系列分配請求和回收請求。
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

struct block{
	int start;  //起址
	int len;    //長度
	int state;  //狀態:0為未分配，1為已分配
	struct block *next;
};

struct block *create(){

	struct block *head,*temp,*present;
	temp = (struct block *)malloc(sizeof(struct block));
	temp->start = 5;
	temp->len = 5;
	temp->state = 1;
	head = present = temp;
	temp = (struct block *)malloc(sizeof(struct block));
	temp->start = 10;
	temp->len = 4;
	temp->state = 1;
	present->next = temp;
	present = temp;
	temp = (struct block *)malloc(sizeof(struct block));
	temp->start = 14;
	temp->len = 12;
	temp->state = 0;
	present->next = temp;
	present = temp;
	temp = (struct block *)malloc(sizeof(struct block));
	temp->start = 26;
	temp->len = 6;
	temp->state = 1;
	present->next = temp;
	present = temp;
	temp = (struct block *)malloc(sizeof(struct block));
	temp->start = 32;
	temp->len = 96;
	temp->state = 0;
	temp->next = NULL;
	present->next = temp;
	return head;
}

void main( void ){
	int choice;      //用戶選擇	
	int cap;         //要求分配或者收回的空間大小
	struct block *head,*present,*temp;
	head = create();
	present = head;
	
	while(1){
		printf("=========分配和收回請求===========\n");
		printf("\t1.分配；\n");
		printf("\t2.收回；\n");
		printf("\t3.顯示；\n");
		printf("\t0.退出。\n");
		printf("==================================\n");
		printf("Your choice is:");
		scanf("%d",&choice);
		if(choice==0)
			break;
		while(choice!=0){
			switch(choice){
			case 1:
				printf("\nPlease input the capability you want to assign:");
				scanf("%d",&cap);
				
				while(present!=NULL){
					if((present->len>cap)&&(present->state==0)){
						
						temp = (struct block *)malloc(sizeof(struct block));
						temp->len = present->len - cap;
						temp->state = 0;
						temp->start = present->start+cap;
						present->len = cap;
						present->state = 1;
						temp->next = present->next;
						present->next = temp;
						break;
					}
					else
						present = present->next;
				}
				if(present->next==NULL)
					printf("\nThere are no sufficient capablity for you require!\nPlease try to assign a litter one.\n");
				choice = 0;
				break;
			case 2:
				printf("\nPlease input the capablity you want to get back:");
				scanf("%d",&cap);
				
				temp = head;
				present = temp->next;
				//判斷頭結點是否滿足條件
				if((temp->len==cap)&&(temp->state==1)){
					if(temp->next->state==0){
						temp->len += cap;
						temp->next = temp->next->next;
					}
					else		
						temp->state = 0;
					choice = 0;
					break;
				}
				
				while(present!=NULL){
					if((present->len==cap)&&(present->state==1)){   //找到滿足條件的
						if(temp->state==0){             //上面一個為空結點
							
							temp->len += present->len;
							temp->next = present->next;
							if(present->next->state==0){
								temp->len += present->next->len;
								temp->next = present->next->next;
								present = present->next->next;
							}
						}//if
						else{
							
							if(present->next->state==0){         //下面一個為空結點
								
								present->len += present->next->len;
								present->next = present->next->next;
														
							}//if                    
							present->state = 0;								
						}//else
						
						choice = 0;
						break;
					}//if
					else{						
						temp = temp->next;
						present = temp->next;
					}//else
				}//while
				if(temp->next==NULL)					
					printf("\nERROR!Cannot find this block in the list!\n");				
					
				choice=0;
				break;
			case 3:
				printf("\nThe resent stuation of the Memory portion is:\n");
				printf("**************************************************\n");
				printf("\tFROM\tTO\tCAPABLITY\tSTATE\n");
				temp = head;
				while(temp!=NULL){
					printf("\t%d\t%d\t%d\t\t%s\n",temp->start,temp->start+temp->len,temp->len,(temp->state==0)?"free":"busy");
					temp = temp->next;
				}
				printf("**************************************************\n");
				choice = 0;
				break;

				
			default:

				printf("Input Error!Please try again!\n");
				choice = 0;
				break;
			}	
		}
		

	}//while(1)
	

}

/*第二題：在分頁式管理方式下采用位示圖來表示主存分配情況，實現主存分配和回收。
[提示]：
(1)	假定系統的主存被分成大小相等的64個塊，用0/1對應空閑/占用。初始位示圖如右圖。
(2)	當要裝入一個作業時，根據作業對主存的需求量，先查空閑塊數是否能滿足作業要求，若能滿足，
則查位示圖，修改位示圖和空閑塊數。位置與塊號的對應關系為：
塊號=j*8+i，其中i表示位，j表示字節。
根據分配的塊號建立頁表。頁表包括兩項：頁號和塊號。
(3)	回收時，修改位示圖和空閑塊數。
(4)	要求程序能顯示位示圖和空閑塊數的變化。
*/