fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define TOTAL_MEMORY 640
  6.  
  7. // 定义分区节点结构
  8. typedef struct SubArea {
  9.     char name[20];      // 作业名称 (空闲区通常叫 "Free")
  10.     int start;          // 起始地址
  11.     int length;         // 分区长度
  12.     struct SubArea *next; // 指向下一个分区的指针
  13. } SubArea;
  14.  
  15. // 定义两个链表的头指针
  16. SubArea *free_head = NULL;       // 空闲分区表
  17. SubArea *allocated_head = NULL;  // 已分配分区表
  18.  
  19. // --- 辅助函数：初始化 ---
  20. void init() {
  21.     free_head = (SubArea*)malloc(sizeof(SubArea));
  22.     strcpy(free_head->name, "Free");
  23.     free_head->start = 0;
  24.     free_head->length = TOTAL_MEMORY;
  25.     free_head->next = NULL;
  26.  
  27.     allocated_head = NULL; // 初始没有作业
  28. }
  29.  
  30. // --- 辅助函数：显示当前内存状况 ---
  31. void print_memory() {
  32.     SubArea *p;
  33.     printf("\n-------------------------------------------------------\n");
  34.     printf("| %-15s | %-10s | %-10s |\n", "Partition Type", "Start Addr", "Length (KB)");
  35.     printf("-------------------------------------------------------\n");
  36.  
  37.     // 打印已分配分区
  38.     p = allocated_head;
  39.     while (p != NULL) {
  40.         printf("| Used (%-8s) | %-10d | %-10d |\n", p->name, p->start, p->length);
  41.         p = p->next;
  42.     }
  43.  
  44.     // 打印空闲分区
  45.     p = free_head;
  46.     while (p != NULL) {
  47.         printf("| Free            | %-10d | %-10d |\n", p->start, p->length);
  48.         p = p->next;
  49.     }
  50.     printf("-------------------------------------------------------\n");
  51. }
  52.  
  53. // --- 核心逻辑：分配内存 ---
  54. // alg_type: 1=First Fit, 2=Best Fit, 3=Worst Fit
  55. void allocate(char *job_name, int request_size, int alg_type) {
  56.     SubArea *p = free_head;
  57.     SubArea *prev = NULL;      // 遍历时的前驱
  58.     SubArea *target = NULL;    // 选中的空闲块
  59.     SubArea *target_prev = NULL; // 选中的空闲块的前驱
  60.  
  61.     // 根据算法查找合适的空闲块
  62.     if (alg_type == 1) { // 首次适应算法 (First Fit)
  63.         while (p != NULL) {
  64.             if (p->length >= request_size) {
  65.                 target = p;
  66.                 target_prev = prev;
  67.                 break; // 找到第一个就停止
  68.             }
  69.             prev = p;
  70.             p = p->next;
  71.         }
  72.     } 
  73.     else if (alg_type == 2) { // 最佳适应算法 (Best Fit)
  74.         int min_diff = TOTAL_MEMORY + 1; // 设置一个最大值
  75.         while (p != NULL) {
  76.             if (p->length >= request_size && (p->length - request_size < min_diff)) {
  77.                 min_diff = p->length - request_size;
  78.                 target = p;
  79.                 target_prev = prev;
  80.             }
  81.             prev = p;
  82.             p = p->next;
  83.         }
  84.     } 
  85.     else if (alg_type == 3) { // 最坏适应算法 (Worst Fit)
  86.         int max_diff = -1;
  87.         while (p != NULL) {
  88.             if (p->length >= request_size && (p->length - request_size > max_diff)) {
  89.                 max_diff = p->length - request_size;
  90.                 target = p;
  91.                 target_prev = prev;
  92.             }
  93.             prev = p;
  94.             p = p->next;
  95.         }
  96.     }
  97.  
  98.     // 开始分配
  99.     if (target == NULL) {
  100.         printf("\n[Fail] Memory allocation failed for %s (Size: %dKB). No suitable block.\n", job_name, request_size);
  101.         return;
  102.     }
  103.  
  104.     // 1. 创建新的已分配节点
  105.     SubArea *new_alloc = (SubArea*)malloc(sizeof(SubArea));
  106.     strcpy(new_alloc->name, job_name);
  107.     new_alloc->start = target->start;
  108.     new_alloc->length = request_size;
  109.     new_alloc->next = allocated_head; // 头插法插入已分配链表
  110.     allocated_head = new_alloc;
  111.  
  112.     // 2. 更新空闲链表
  113.     if (target->length == request_size) {
  114.         // 如果大小正好相等，直接从空闲链表中删除该节点
  115.         if (target_prev == NULL) { // 是头节点
  116.             free_head = target->next;
  117.         } else {
  118.             target_prev->next = target->next;
  119.         }
  120.         free(target);
  121.     } else {
  122.         // 如果有剩余空间，修改起始地址和长度
  123.         target->start += request_size;
  124.         target->length -= request_size;
  125.     }
  126.  
  127.     printf("\n[Success] Allocated %dKB to %s.\n", request_size, job_name);
  128. }
  129.  
  130. // --- 核心逻辑：回收内存 ---
  131. void reclaim(char *job_name) {
  132.     SubArea *p = allocated_head;
  133.     SubArea *prev = NULL;
  134.  
  135.     // 1. 在已分配表中查找作业
  136.     while (p != NULL) {
  137.         if (strcmp(p->name, job_name) == 0) break;
  138.         prev = p;
  139.         p = p->next;
  140.     }
  141.  
  142.     if (p == NULL) {
  143.         printf("\n[Error] Job %s not found in memory.\n", job_name);
  144.         return;
  145.     }
  146.  
  147.     // 2. 从已分配表中移除
  148.     if (prev == NULL) allocated_head = p->next;
  149.     else prev->next = p->next;
  150.  
  151.     int recover_start = p->start;
  152.     int recover_len = p->length;
  153.     free(p); // 释放已分配节点结构，准备创建新的空闲节点
  154.  
  155.     // 3. 插入空闲链表（按地址排序）
  156.     SubArea *new_free = (SubArea*)malloc(sizeof(SubArea));
  157.     strcpy(new_free->name, "Free");
  158.     new_free->start = recover_start;
  159.     new_free->length = recover_len;
  160.  
  161.     // 寻找插入位置
  162.     SubArea *curr = free_head;
  163.     SubArea *pre_curr = NULL;
  164.  
  165.     // 如果空闲表为空
  166.     if (free_head == NULL) {
  167.         free_head = new_free;
  168.         new_free->next = NULL;
  169.     } else {
  170.         // 找到第一个起始地址大于待插入块地址的节点
  171.         while (curr != NULL && curr->start < new_free->start) {
  172.             pre_curr = curr;
  173.             curr = curr->next;
  174.         }
  175.  
  176.         // 插入逻辑
  177.         if (pre_curr == NULL) { // 插在头部
  178.             new_free->next = free_head;
  179.             free_head = new_free;
  180.         } else { // 插在中间或尾部
  181.             new_free->next = pre_curr->next;
  182.             pre_curr->next = new_free;
  183.         }
  184.     }
  185.  
  186.     // 4. 合并空闲分区 (Coalescing)
  187.     // 检查是否可以与后一个合并
  188.     if (new_free->next != NULL && (new_free->start + new_free->length == new_free->next->start)) {
  189.         SubArea *temp = new_free->next;
  190.         new_free->length += temp->length;
  191.         new_free->next = temp->next;
  192.         free(temp);
  193.     }
  194.  
  195.     // 检查是否可以与前一个合并 (pre_curr是前一个节点)
  196.     // 注意：这里需要判断 pre_curr 是否存在且正好与 new_free 相邻
  197.     if (pre_curr != NULL && (pre_curr->start + pre_curr->length == new_free->start)) {
  198.         pre_curr->length += new_free->length;
  199.         pre_curr->next = new_free->next;
  200.         free(new_free);
  201.     }
  202.  
  203.     printf("\n[Success] Reclaimed memory from %s.\n", job_name);
  204. }
  205.  
  206. // --- 主菜单 ---
  207. int main() {
  208.     int choice;
  209.     int alg;
  210.     char name[20];
  211.     int size;
  212.  
  213.     init(); // 初始化内存
  214.  
  215.     printf("Select Allocation Algorithm:\n");
  216.     printf("1. First Fit (FF)\n");
  217.     printf("2. Best Fit (BF)\n");
  218.     printf("3. Worst Fit (WF)\n");
  219.     printf("Choice: ");
  220.     scanf("%d", &alg);
  221.  
  222.     while (1) {
  223.         print_memory();
  224.         printf("\n1. Allocate Job  2. Reclaim Job  0. Exit\n");
  225.         printf("Action: ");
  226.         scanf("%d", &choice);
  227.  
  228.         if (choice == 0) break;
  229.  
  230.         if (choice == 1) {
  231.             printf("Enter Job Name (e.g., J1): ");
  232.             scanf("%s", name);
  233.             printf("Enter Size (KB): ");
  234.             scanf("%d", &size);
  235.             allocate(name, size, alg);
  236.         } 
  237.         else if (choice == 2) {
  238.             printf("Enter Job Name to Reclaim: ");
  239.             scanf("%s", name);
  240.             reclaim(name);
  241.         }
  242.     }
  243.     return 0;
  244. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Select Allocation Algorithm:
1. First Fit (FF)
2. Best Fit (BF)
3. Worst Fit (WF)
Choice: 
-------------------------------------------------------
| Partition Type  | Start Addr | Length (KB) |
-------------------------------------------------------
| Free            | 0          | 640        |
-------------------------------------------------------

1. Allocate Job  2. Reclaim Job  0. Exit
Action:
https://ideone.com/stqcc2
language:
C (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!