实验：作业调度算法模拟

【题目描述】

先来先服务调度（FCFS）编程模拟： 对所输入的若干作业，按FCFS算法模拟调度，观察、记录并分析调度的输出结果情况。打开job.c文件，完成FCFS函数的编写。

短作业调度算法非抢占的（SJF）编程模拟：编程实现由短作业优先算法对模拟作业的调度，并观察分析运行结果。打开job.c文件，完成SJF函数的编写。

【输入】

分别输入几个作业的作业号、作业到达时间、作业的服务时间

【输出】

输出调度后每个作业的作业号、到达时间、开始时间、完成时间、周转时间

【输入输出样例1：FCFS算法】

输入 输出
A,0,4;B,1,3;C,2,5;D,3,2;E,4,4; A 0 0 4 4
B 1 4 7 6
C 2 7 12 10
D 3 12 14 11
E 4 14 18 14

【输入输出样例2：SJF算法】

输入 输出
A,0,4;B,1,3;C,2,5;D,3,2;E,4,4; A 0 0 4 4
D 3 4 6 3
B 1 6 9 8
E 4 9 13 9
C 2 13 18 16

【实验代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

struct Job_type
{ 
  char num;  // 作业号
  int arrival_time;  // 到达时间
  int runtime;  // 服务时间
} x, job[SIZE];

void load()
{
    int i;
    printf("\nEnter the Jobs' datas:\n");
    for (i = 0; i < SIZE; i++)
    {
        scanf(" %c,%d,%d;", &job[i].num, &job[i].arrival_time, &job[i].runtime);
    }
}

void fcfs()
{
    int i;
    int start_time[SIZE];       // 开始时间
    int completion_time[SIZE]; // 完成时间
    int turnaround_time[SIZE]; // 周转时间
    int current_time = 0;       // 当前时间

    for (i = 0; i < SIZE; i++)
    {
        // 如果当前时间小于作业到达时间，则跳到作业到达时间
        if (current_time < job[i].arrival_time)
        {
            current_time = job[i].arrival_time;
        }

        // 计算开始时间和完成时间
        start_time[i] = current_time;
        completion_time[i] = current_time + job[i].runtime;

        // 计算周转时间
        turnaround_time[i] = completion_time[i] - job[i].arrival_time;

        // 更新当前时间
        current_time = completion_time[i];

        // 输出结果
        printf("%c\t%d\t\t%d\t\t%d\t\t%d\n",
               job[i].num, job[i].arrival_time, start_time[i],
               completion_time[i], turnaround_time[i]);
    }
}


void sjf()    //短作业调度函数
{ 
    int i;
    int start_time[SIZE];       // 开始时间
    int completion_time[SIZE]; // 完成时间
    int turnaround_time[SIZE]; // 周转时间
    int visited[SIZE] = {0};    // 标记是否已调度
    int current_time = 0;       // 当前时间
    int completed_jobs = 0;     // 已完成的作业数量

    while (completed_jobs < SIZE)
    {
        int shortest_index = -1;
        int shortest_runtime = 1e9; // 假设一个很大的值

        // 找到服务时间最短且到达的作业
        for (i = 0; i < SIZE; i++)
        {
            if (!visited[i] && job[i].arrival_time <= current_time && job[i].runtime < shortest_runtime)
            {
                shortest_runtime = job[i].runtime;
                shortest_index = i;
            }
        }

        // 如果没有可调度的作业，跳到下一个作业的到达时间
        if (shortest_index == -1)
        {
            for (i = 0; i < SIZE; i++)
            {
                if (!visited[i])
                {
                    current_time = job[i].arrival_time;
                    break;
                }
            }
            continue;
        }

        // 调度找到的最短作业
        i = shortest_index;
        start_time[i] = current_time;
        completion_time[i] = current_time + job[i].runtime;
        turnaround_time[i] = completion_time[i] - job[i].arrival_time;

        // 更新状态
        current_time = completion_time[i];
        visited[i] = 1;
        completed_jobs++;

        // 输出作业调度信息
        printf("%c\t%d\t\t%d\t\t%d\t\t%d\n",
               job[i].num, job[i].arrival_time, start_time[i],
               completion_time[i], turnaround_time[i]);
    }
}

main()
{
  load();
  printf("FCFS algorithm：\n");
  fcfs();
  printf("SJF algorithm：\n");
  sjf();
}

实验：内存管理算法模拟

【题目描述】

打开os.c文件，模拟内存动态分配的最佳算法完成Best_allocate函数的编写。

【输入】

采用最佳适应算法分配时，可以按照块的大小按序输入数据。

样例1：

【输入】

3

72 50

228 28

154 10

再输入：12

【输出】

分配的空闲区域是：228 28

分配后的空闲表如下：

空闲起始地址为：154；长度为：10

空闲起始地址为：240；长度为：16

空闲起始地址为：72；长度为：50

样例2：

【输入】

3

72 50

228 28

154 10

再输入：60

【输出】

没有适合的空闲区域

分配后的空闲表如下：

空闲起始地址为：154；长度为：10

空闲起始地址为：228；长度为：28

空闲起始地址为：72；长度为：50

【实验代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <stdlib.h>

#define minsize 10   /*定义物理块的最小值*/
 typedef struct free_table{   /*定义未分配区表*/    
    long address;
    long size;
    struct free_table *next;
}Node,*NodeList ;
NodeList head;
void createLink()
{
    NodeList p;
  int n;  //链表长度(节点数目)
    head=(NodeList)malloc(sizeof(Node)); 
    p=head;
    printf("请输入空闲区域数：");
  scanf("%d", &n);  //链表长度(节点数目)
  while( n-- ) {
    p->next = (NodeList)malloc(sizeof(Node)); //创建1个新的链表节点 
    p = p->next;    //链表游标 -> 后移一个节点
    scanf("%d", &p->address); 
    scanf("%d", &p->size); 
  }
  p->next = NULL; //链表最后一个节点指向下一个节点的指针 --> 指向空NULL
}
void Best_allocate(int request)/*最佳适应分配函数，根据申请的request字节数来分配空间*/
{
    // 先对空闲分区链表按大小升序排序
    if (!head || !head->next) {
        printf("空闲分区表为空，无法分配内存。\n");
        return;
    }
    // 使用插入排序对链表排序
    NodeList sorted = NULL; // 排序后的链表
    NodeList current = head->next; // 当前节点
    while (current) {
        NodeList next = current->next; // 保存下一个节点
        // 插入到排序链表中
        if (!sorted || current->size < sorted->size) {
            // 插入到排序链表的头部
            current->next = sorted;
            sorted = current;
        } else {
            // 插入到排序链表的适当位置
            NodeList temp = sorted;
            while (temp->next && temp->next->size <= current->size) {
                temp = temp->next;
            }
            current->next = temp->next;
            temp->next = current;
        }
        current = next; // 处理下一个节点
    }
    head->next = sorted; // 更新链表头指向排序后的链表
    // 执行分配逻辑
    NodeList temp = head;
    while (temp->next) {
        NodeList current = temp->next;
        if (current->size >= request) { // 找到符合要求的分区
            printf("分配的空闲区域是：%ld  %ld\n", current->address, request);
            if (current->size - request >= minsize) {
                // 剩余空间足够，拆分分区
                current->address += request;
                current->size -= request;
            } else {
                // 剩余空间不足，分配整个分区
                temp->next = current->next;
                free(current);
            }
            return;
        }
        temp = temp->next;
    }
    // 若没有找到合适的分区
    printf("内存分配失败：没有足够大的空闲分区。\n");
}
void Link_printf()
{
   NodeList temp1;
   temp1=head->next;
   printf("分配后的空闲表如下：\n" );
   while(temp1){     
    printf("空闲起始地址为：%d；长度为：%d\n",temp1->address,temp1->size );
    temp1=temp1->next ;
   }
}
main()
{ 
  int a,request;
  createLink(); 
  printf("请输入作业申请长度：");
  scanf("%d",&request);
  Best_allocate(request);
  Link_printf();
}