Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1473022
  • 博文数量: 148
  • 博客积分: 2234
  • 博客等级: 大尉
  • 技术积分: 3225
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-17 21:34
个人简介

未来很长。

文章存档

2017年(7)

2016年(4)

2015年(1)

2014年(6)

2013年(31)

2012年(99)

分类: C/C++

2012-05-18 17:03:33


点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdlib.h>

  4. #define PROCESS_NAME_LEN 32 //进程名字长度
  5. #define MIN_SLICE 10 //最小碎片大小
  6. #define DEFAULT_MEM_SIZE 1024 // 默认的内存大小
  7. #define DEFAULT_MEM_START 0 //起始地址

  8. #define MA_FF 1                    //首次适应算法
  9. #define MA_BF 2                    //最佳适应算法
  10. #define MA_WF 3                    //最坏适应算法


  11. //空闲分区的结构体
  12. typedef struct free_block_type{
  13.     int size;
  14.     int start_addr;
  15.     struct free_block_type *next;
  16. }free_block_type;
  17.  free_block_type *free_block;


  18.  //已分配分区的结构体
  19. typedef struct allocated_block{
  20.     int pid;
  21.     int size;
  22.     int start_addr;
  23.     char process_name[PROCESS_NAME_LEN];
  24.     struct allocated_block *next;
  25.  }allocated_block;

  26. struct allocated_block *allocated_block_head = NULL;

  27. int mem_size=DEFAULT_MEM_SIZE;
  28. int ma_algorithm = MA_FF;
  29. static int pid = 0;
  30. int flag = 0;

  31. //函数声明
  32. void display_menu();
  33. int set_mem_size();
  34. void set_algorithm();
  35. void rearrange(int algorithm);
  36. int new_process();
  37. int allocate_mem (struct allocated_block *ab);
  38. void kill_process();
  39. int free_mem (struct allocated_block *ab);
  40. int dispose (struct allocated_block *free_ab);
  41. int display_mem_usage();
  42. allocated_block * find_process(int pid);
  43. void rearrange_FF();
  44. void rearrange_BF();
  45. void rearrange_WF();

  46. //初始化空闲分区
  47. free_block_type* init_free_block(int mem_size){
  48.     free_block_type *fb;
  49.     fb=(free_block_type *)malloc(sizeof(free_block_type));
  50.     if(fb==NULL){
  51.         printf("No mem\n");
  52.         return NULL;
  53.         }
  54.     fb->size = mem_size;
  55.     fb->start_addr = DEFAULT_MEM_START;
  56.     fb->next = NULL;
  57.     return fb;
  58. }

  59. //显示主菜单
  60. void display_menu(){
  61.     printf("\n");
  62.     printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
  63.     printf("2 - Select memory allocation algorithm\n");
  64.     printf("3 - New process \n");
  65.     printf("4 - Terminate a process \n");
  66.     printf("5 - Display memory usage \n");
  67.     printf("0 - Exit\n");
  68. }

  69. /*设置内存大小*/
  70. int set_mem_size(){
  71.     int size;
  72.     if(flag!=0){ /*flag标志防止内存被再次设置*/
  73.         printf("Cannot set memory size again\n");
  74.         return 0;
  75.         }
  76.     printf("Total memory size =");
  77.     scanf("%d", &size);
  78.     if(size>0) {
  79.         mem_size = size;
  80.         free_block->size = mem_size;/*设置初始大小为 1024*/
  81.         }
  82.     flag=1;
  83.     return 1;
  84.  }
  85.  /*选择当前算法*/
  86. void set_algorithm(){
  87.     int algorithm;
  88.     printf("\t1 - First Fit\n");
  89.     printf("\t2 - Best Fit \n");
  90.     printf("\t3 - Worst Fit \n");
  91.     printf("Please input your choice : ");
  92.     scanf("%d", &algorithm);
  93.     if(algorithm>=1 && algorithm <=3)
  94.               ma_algorithm=algorithm;
  95.     
  96.     rearrange(ma_algorithm);
  97. }

  98. /*为每一个进程分配完内存以后重新按已选择的算法再次排序*/
  99. void rearrange(int algorithm){
  100.     switch(algorithm){
  101.         case MA_FF: rearrange_FF(); break;
  102.         case MA_BF: rearrange_BF(); break;
  103.         case MA_WF: rearrange_WF(); break;
  104.         }
  105. }
  106. /*首次适应算法,按地址的大小由小到达排序*/
  107. void rearrange_FF(){
  108.     free_block_type *temp,*p=NULL;
  109.     free_block_type *head=NULL;
  110.     int current_min_addr;

  111.     if(free_block){
  112.         temp=free_block;
  113.         current_min_addr=free_block->start_addr;
  114.         while(temp->next!=NULL){
  115.             if(temp->next->start_addr<current_min_addr){
  116.                 current_min_addr=temp->next->start_addr;
  117.                 p=temp;
  118.                 }
  119.             temp=temp->next;
  120.         }
  121.         if(p!=NULL){
  122.             temp=p->next;
  123.             p->next=p->next->next;
  124.             temp->next=free_block;
  125.             free_block=temp;
  126.         }
  127.         head=free_block;
  128.         p=head;
  129.         temp=head->next;
  130.         while(head->next!=NULL){
  131.             current_min_addr=head->next->start_addr;
  132.             while(temp->next!=NULL){
  133.                 if(temp->next->start_addr<current_min_addr){
  134.                     current_min_addr=temp->next->start_addr;
  135.                     p=temp;
  136.                 }
  137.             temp=temp->next;
  138.             }
  139.             if(p->next!=head->next){
  140.                 temp=p->next;
  141.                 p->next=p->next->next;
  142.                 temp->next=head->next;
  143.                 head->next=temp;
  144.             }
  145.         head=head->next;
  146.         temp=head->next;
  147.         p=head;
  148.         }
  149.     }
  150.     return ;
  151. }

  152. /*最佳适应算法,按内存块的大小由小到大排序*/
  153. void rearrange_BF(){
  154.     free_block_type *temp,*p=NULL;
  155.     free_block_type *head=NULL;
  156.     int current_min_size=free_block->size;
  157.     
  158.     temp=free_block;
  159.     while(temp->next!=NULL){
  160.         if(temp->next->size<current_min_size){
  161.             current_min_size=temp->next->size;
  162.             p=temp;
  163.         }
  164.         temp=temp->next;
  165.     }
  166.     if(p!=NULL){
  167.         temp=p->next;
  168.         p->next=p->next->next;
  169.         temp->next=free_block;
  170.         free_block=temp;
  171.     }
  172.     head=free_block;
  173.     p=head;
  174.     temp=head->next;
  175.     while(head->next!=NULL){
  176.         current_min_size=head->next->size;
  177.         while(temp->next!=NULL){
  178.             if(temp->next->size<current_min_size){
  179.                 current_min_size=temp->next->size;
  180.                 p=temp;
  181.             }
  182.             temp=temp->next;
  183.         }
  184.     if(p->next!=head->next){
  185.         temp=p;
  186.         p->next=p->next->next;
  187.         temp->next=head->next;
  188.         head->next=temp;
  189.         }
  190.         head=head->next;
  191.         temp=head->next;
  192.         p=head;
  193.     }

  194. }

  195. /*最坏适应算法,按地址块的大小从大到小排序*/
  196. void rearrange_WF(){
  197.        free_block_type *temp,*p=NULL;
  198.     free_block_type *head=NULL;
  199.     int current_max_size=free_block->size;
  200.     temp=free_block;
  201.     while(temp->next!=NULL){
  202.         if(temp->next->size>current_max_size){
  203.             current_max_size=temp->next->size;
  204.             p=temp;
  205.         }
  206.         temp=temp->next;
  207.     }
  208.     if(p!=NULL){
  209.         temp=p;
  210.         p->next=p->next->next;
  211.         temp->next=free_block;
  212.         free_block=temp;
  213.     }
  214.     head=free_block;
  215.     p=head;
  216.     temp=head->next;
  217.     while(head->next!=NULL){
  218.         current_max_size=head->next->size;
  219.         while(temp->next!=NULL){
  220.             if(temp->next->size>current_max_size){
  221.                 current_max_size=temp->next->size;
  222.                 p=temp;
  223.             }
  224.         temp=temp->next;
  225.         }
  226.         if(p->next!=head->next){
  227.             temp=p->next;
  228.             p->next=p->next->next;
  229.             temp->next=head->next;
  230.             head->next=temp;
  231.         }
  232.         head=head->next;
  233.         temp=head->next;
  234.         p=head;
  235.     }
  236.     return ;
  237. }
  238. //创建一个新的进程
  239. int new_process(){
  240.     struct allocated_block *ab;
  241.     int size;
  242.     int ret;
  243.     ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
  244.     if(!ab) exit(-5);
  245.     ab->next = NULL;
  246.     pid++;
  247.     sprintf(ab->process_name, "PROCESS-%02d", pid);
  248.     ab->pid = pid;
  249.     printf("Memory for %s:", ab->process_name);
  250.     printf("Please input you want to allocate process' size : ");
  251.     scanf("%d", &size);
  252.     if(size>0) {
  253.         
  254.         ab->size=size;
  255.     }
  256.     ret = allocate_mem(ab);
  257.     if((ret==1) &&(allocated_block_head == NULL)){
  258.         allocated_block_head=ab;
  259.         return 1; }
  260.    
  261.     else if (ret==1) {
  262.         ab->next=allocated_block_head;
  263.         allocated_block_head=ab;
  264.         return 2; }
  265.     else if(ret==-1){
  266.         printf("Allocation fail\n");
  267.         pid--;
  268.         free(ab);
  269.         return -1;
  270.      }
  271.     return 3;
  272.     }

  273. //内存分配
  274. int allocate_mem(struct allocated_block *ab){
  275.     free_block_type *fbt, *pre;
  276.     free_block_type *temp,*p,*p1;
  277.     allocated_block *q;
  278.     int request_size=ab->size;
  279.     int sum=0;
  280.     int max;
  281.     fbt = pre = free_block;
  282.     if(fbt){
  283.         if(ma_algorithm==MA_WF){
  284.             if(fbt==NULL||fbt->size<request_size)
  285.                     return -1;
  286.         }
  287.         else{
  288.             while(fbt!=NULL&&fbt->size<request_size){
  289.                 pre=fbt;        
  290.                 fbt=fbt->next;
  291.             }
  292.         }
  293.         if(fbt==NULL||fbt->size<request_size){
  294.             if(free_block->next!=NULL){
  295.                 sum=free_block->size;
  296.                 temp=free_block->next;
  297.                 while(temp!=NULL){
  298.                     sum+=temp->size;
  299.                     if(sum>=request_size)
  300.                         break;
  301.                     temp=temp->next;
  302.                 }
  303.                 if(temp==NULL)
  304.                     return -1;
  305.                 else{
  306.                     pre=free_block;
  307.                     max=free_block->start_addr;
  308.                     fbt=free_block;
  309.                     while(temp->next!=pre){
  310.                         if(max<pre->start_addr){
  311.                             max=pre->start_addr;
  312.                             fbt=pre;
  313.                         }
  314.                         pre=pre->next;
  315.                     }
  316.                     pre=free_block;
  317.             
  318.                     while(pre!=temp->next)
  319.                     {
  320.                         q=allocated_block_head;
  321.                         p=free_block;
  322.                     
  323.                             while(q!=NULL)
  324.                             {
  325.                                 if(q->start_addr>pre->start_addr)
  326.                                     q->start_addr=q->start_addr-pre->size;
  327.                                 q=q->next;
  328.                             }
  329.                             while(p!=NULL)
  330.                             {
  331.                                 if(p->start_addr>pre->start_addr)
  332.                                     p->start_addr=p->start_addr-pre->size;
  333.                                 p=p->next;
  334.                                 
  335.                             }
  336.                     
  337.                         pre=pre->next;
  338.                     }
  339.                 
  340.                 pre=free_block;
  341.                 while(pre!=temp->next){
  342.             
  343.                     p1=pre->next;
  344.                     if(pre==fbt)
  345.                         break;
  346.                     free(pre);
  347.                     pre=p1;
  348.                 
  349.                 }
  350.                 q=allocated_block_head;
  351.                 free_block=fbt;
  352.                 free_block->start_addr=q->start_addr+q->size;
  353.             
  354.                 free_block->size=sum;
  355.                 free_block->next=temp->next;
  356.                 if(free_block->size-request_size<MIN_SLICE){
  357.                     ab->size=free_block->size;
  358.                     ab->start_addr=free_block->start_addr;
  359.                     pre=free_block;
  360.                     free_block=free_block->next;
  361.                     free(pre);
  362.                 }
  363.                 else{
  364.                     ab->start_addr=free_block->start_addr;
  365.                     free_block->start_addr=free_block->start_addr+request_size;
  366.                     free_block->size=free_block->size-request_size;
  367.                 }
  368.                 
  369.             }
  370.         }
  371.         else
  372.             return -1;
  373.          }
  374.         else{
  375.             if(fbt->size-request_size<MIN_SLICE){
  376.                 ab->size=fbt->size;
  377.                 ab->start_addr=fbt->start_addr;
  378.                 if(pre->next==free_block){
  379.                     free_block=fbt->next;
  380.                 }
  381.                 else{
  382.                     pre->next=fbt->next;
  383.                 }
  384.                 free_block=fbt->next;
  385.                 free(fbt);
  386.             }
  387.             else{
  388.                 ab->start_addr=fbt->start_addr;
  389.                 fbt->start_addr=fbt->start_addr+request_size;
  390.                 fbt->size=fbt->size-request_size;
  391.             }
  392.         }
  393.         rearrange(ma_algorithm);
  394.         return 1;
  395.     }
  396.     else
  397.     {
  398.         printf("Free Memory already has been allocated over: ");
  399.         return -1;
  400.     }

  401. }

  402. //选择杀死一个进程

  403. void kill_process(){
  404.     struct allocated_block *ab;
  405.     int pid;
  406.     printf("Kill Process, pid=");
  407.     scanf("%d", &pid);
  408.     ab=find_process(pid);
  409.     if(ab!=NULL){
  410.         free_mem(ab);
  411.         dispose(ab);
  412.         }
  413. }
  414. //找到要杀死的进程的标号
  415. allocated_block * find_process(int pid){
  416.     allocated_block *abb;
  417.     abb=allocated_block_head;
  418.     if(abb->pid==pid)
  419.     {
  420.         return abb;
  421.     }
  422.     abb=allocated_block_head->next;
  423.     while(abb->next!=NULL){
  424.         if(abb->pid==pid)
  425.             return abb;
  426.         abb=abb->next;
  427.     }
  428.     return abb;
  429. }

  430. //释放杀死进程的内存块
  431. int free_mem(struct allocated_block *ab){
  432.        int algorithm = ma_algorithm;
  433.        struct free_block_type *fbt, *pre;
  434.        fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
  435.     pre=(struct free_block_type*) malloc(sizeof(struct free_block_type));
  436.        if(!fbt) return -1;

  437.     fbt->start_addr=ab->start_addr;
  438.     fbt->size=ab->size;
  439.     fbt->next=free_block;
  440.     free_block=fbt;
  441.     rearrange_FF();
  442.     pre->next=free_block;
  443.     pre->size=0;
  444.     while(pre->next&&(pre->next->start_addr!=fbt->start_addr))
  445.         pre=pre->next;
  446.     if(pre->size!=0&&fbt->next!=NULL){
  447.         if(((pre->start_addr+pre->size)==fbt->start_addr)&&((fbt->start_addr+fbt->size)==fbt->next->start_addr)){
  448.             pre->size=pre->size+fbt->size+fbt->next->size;
  449.             pre->next=fbt->next->next;
  450.             free(fbt->next);
  451.             free(fbt);
  452.         }
  453.         else if((pre->start_addr+pre->size)==fbt->start_addr){
  454.             pre->size=pre->size+fbt->size;
  455.             pre->next=fbt->next;
  456.             free(fbt);
  457.         }
  458.         else if(fbt->start_addr+fbt->size==fbt->next->start_addr){
  459.             fbt->size=fbt->size+fbt->next->size;
  460.             fbt->next=fbt->next->next;
  461.             free(fbt->next);
  462.         }
  463.     }
  464.     else if((pre->size==0)&&fbt->next){
  465.         if((fbt->start_addr+fbt->size)==fbt->next->start_addr){
  466.             fbt->size=fbt->size+fbt->next->size;
  467.             fbt->next=fbt->next->next;
  468.             free_block=fbt;
  469.             free(fbt->next);
  470.         }
  471.     }
  472.     else if(fbt->next==NULL){
  473.         if((pre->start_addr+pre->size)==fbt->start_addr){
  474.             pre->size=pre->size+fbt->size;
  475.             pre->next=fbt->next;
  476.             free(fbt);
  477.         }
  478.     }
  479.     rearrange(algorithm);
  480.     
  481.     return 1;
  482. }

  483. //销毁杀死进程的结点
  484. int dispose(struct allocated_block *free_ab){
  485.     struct allocated_block *pre,*ab;

  486.    if(free_ab == allocated_block_head) {
  487.      allocated_block_head = allocated_block_head->next;
  488.         free(free_ab);
  489.         return 1;
  490.         }
  491.     pre = allocated_block_head;
  492.     ab = allocated_block_head->next;
  493.     while(ab!=free_ab)
  494.     {
  495.      pre = ab;
  496.      ab = ab->next;
  497.     }
  498.     pre->next = ab->next;
  499.     free(ab);
  500.     return 2;
  501.  }

  502. //显示内存使用情况

  503. int display_mem_usage(){
  504.     struct free_block_type *fbt=free_block;
  505.     struct allocated_block *ab=allocated_block_head;
  506.     printf("----------------------------------------------------------\n");

  507.     if(fbt==NULL)
  508.     {
  509.         printf("Free Memory already used over !\n");
  510.     }
  511.     printf("----------------------------------------------------------\n");


  512.     if(fbt)
  513.     {
  514.         printf("Free Memory:\n");
  515.         printf("%20s %20s\n", " start_addr", " size");
  516.         while(fbt!=NULL){
  517.             printf("%20d %20d\n", fbt->start_addr, fbt->size);
  518.             fbt=fbt->next;
  519.             }
  520.     }
  521.     
  522.     printf("\nUsed Memory:\n");
  523.     printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
  524.     while(ab!=NULL){
  525.         printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
  526.         ab=ab->next;
  527.         }
  528.     printf("----------------------------------------------------------\n");
  529.     return 0;
  530. }

  531. //退出,销毁所有链表
  532. void do_exit()
  533. {
  534.     free_block_type *temp;
  535.     allocated_block *temp1;
  536.     temp=free_block->next;
  537.     while(temp!=NULL)
  538.     {
  539.         free_block->next=temp->next;
  540.         free(temp);
  541.         temp=free_block->next;
  542.     }
  543.     free(free_block);
  544.     temp1=allocated_block_head->next;
  545.     while(temp1!=NULL)
  546.     {
  547.         allocated_block_head->next=temp1->next;
  548.         free(temp1);
  549.         temp1=allocated_block_head->next;
  550.     }
  551.     free(allocated_block_head->next);

  552. }
  553. //主函数
  554. int main(){
  555.     char choice;
  556.     pid=0;
  557.     free_block=init_free_block(mem_size);
  558.     while(1) {
  559.     display_menu();    
  560.     fflush(stdin);

  561.    choice=getchar();    
  562.     switch(choice){
  563.         case '1': set_mem_size(); break;     
  564.         case '2': set_algorithm();flag=1; break;
  565.         case '3': new_process(); flag=1; break;
  566.         case '4': kill_process(); flag=1; break;
  567.         case '5': display_mem_usage(); flag=1; break;    
  568.         case '0': do_exit();exit(0);    
  569.         default: break;
  570.     }
  571.     }
  572.     return 0;
  573. }

阅读(3330) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~