#include <stdio.h>
#define NUM_TASKS 5
#define MEMORY_CAPACITY 100 // 用户可用主存(K)
#define TAPE_CAPACITY 4 // 磁带机台数
typedef struct {
const char* name;
int nArrivalTime; // 到达时刻（从 00:00 起的分钟）
int nServiceTime; // 运行时间（分钟）
int nMemoryNeed; // 主存需求
int nTapesNeed; // 磁带机需求（台）
int nAdmittedTime; // 进入系统（分到内存+磁带）时刻；-1 表示尚未进入
int nStartTime; // 获得CPU的时刻
int nFinishTime; // 完成时刻
} Task;
/*
返回t之后的下一次到达时刻；若不存在返回 -1
*/
int NextArrivalTimeAfter(const Task tasks[], int n, int t)
{
int nNextTime = -1;
for (int i = 0; i < n; ++i)
{
if (tasks[i].nAdmittedTime == -1 && tasks[i].nArrivalTime > t)
{
if (nNextTime == -1 || tasks[i].nArrivalTime < nNextTime)
{
nNextTime = tasks[i].nArrivalTime;
}
}
}
return nNextTime;
}
/* 在当前时刻 nCurrentTime，尽可能让已到达的作业进入系统（分配内存和磁带）
- 主存可变分区且允许紧凑：只需比较“剩余总内存”是否足够
- 磁带机静态分配：进入系统后一直占用到完成为止
进入系统的作业按 FCFS 顺序入就绪队列。*/
void AdmitArrivedTasks(
Task tasks[], int n, int nCurrentTime,
int* nFreeMemory, int* nFreeTapes,
int ReadyQueue[], int* nReadyTail)
{
for (int i = 0; i < n; ++i)
{
if (tasks[i].nAdmittedTime == -1 && tasks[i].nArrivalTime <= nCurrentTime)
{
if (tasks[i].nMemoryNeed <= *nFreeMemory &&
tasks[i].nTapesNeed <= *nFreeTapes)
{
*nFreeMemory -= tasks[i].nMemoryNeed; // 占用资源
*nFreeTapes -= tasks[i].nTapesNeed;
tasks[i].nAdmittedTime = nCurrentTime;
ReadyQueue[(*nReadyTail)++] = i; // 进入就绪队列
}
}
}
}
void PrintTime(int nMinutes)
{
printf("%02d:%02d", nMinutes / 60, nMinutes % 60);
}
int main(void)
{
Task tasks[NUM_TASKS] =
{
{"JOB1", 10 * 60 + 0, 40, 35, 3, -1, -1, -1},
{"JOB2", 10 * 60 + 10, 30, 70, 1, -1, -1, -1},
{"JOB3", 10 * 60 + 15, 20, 50, 3, -1, -1, -1},
{"JOB4", 10 * 60 + 35, 10, 25, 2, -1, -1, -1},
{"JOB5", 10 * 60 + 40, 5, 20, 2, -1, -1, -1},
};
int nFreeMemory = MEMORY_CAPACITY;
int nFreeTapes = TAPE_CAPACITY;
int ReadyQueue[NUM_TASKS]; // 就绪队列
int nReadyHead = 0;
int nReadyTail = 0;
int nExecutionOrder[NUM_TASKS]; // CPU 实际执行顺序
int nExecutionCount = 0;
int nRemainingTasks = NUM_TASKS;
int nCurrentTime = -1;
int nRunningTask = -1; // 当前在CPU上的作业索引，-1表示空闲
int nPlannedFinishTime = 0;
while (nRemainingTasks > 0)
{
// 若 CPU 空闲且就绪队列也空，则时间推进到“下一次到达”
if (nRunningTask == -1 && nReadyHead == nReadyTail)
{
int nNextArrivalTime = NextArrivalTimeAfter(tasks, NUM_TASKS, nCurrentTime);
nCurrentTime = nNextArrivalTime;
AdmitArrivedTasks(tasks, NUM_TASKS, nCurrentTime,
&nFreeMemory, &nFreeTapes,
ReadyQueue, &nReadyTail);
}
// 有就绪作业则按FCFS取队头运行
if (nRunningTask == -1 && nReadyHead != nReadyTail)
{
int nTaskId = ReadyQueue[nReadyHead++];
tasks[nTaskId].nStartTime = nCurrentTime;
tasks[nTaskId].nFinishTime = nCurrentTime + tasks[nTaskId].nServiceTime;
nRunningTask = nTaskId;
nPlannedFinishTime = tasks[nTaskId].nFinishTime;
nExecutionOrder[nExecutionCount++] = nTaskId;
}
// 到达与完成事件处理
if (nRunningTask != -1)
{
int nNextArrivalTime = NextArrivalTimeAfter(tasks, NUM_TASKS, nCurrentTime); // nCurrentTime返回下一个JOB
// 遍历在当前JOB结束之前是否有后续JOB满足条件
if (nNextArrivalTime != -1 && nNextArrivalTime <= nPlannedFinishTime)
{
// 运行期间有新作业到达，尝试装入
nCurrentTime = nNextArrivalTime;
AdmitArrivedTasks(tasks, NUM_TASKS, nCurrentTime,
&nFreeMemory, &nFreeTapes,
ReadyQueue, &nReadyTail);
continue; // 再找
}
// 作业完成
nCurrentTime = nPlannedFinishTime;
tasks[nRunningTask].nFinishTime = nCurrentTime;
// 释放资源
nFreeMemory += tasks[nRunningTask].nMemoryNeed;
nFreeTapes += tasks[nRunningTask].nTapesNeed;
nRunningTask = -1; // CPU恢复空闲
nRemainingTasks--;
// 作业完成后可能使等待作业得以装入
AdmitArrivedTasks(tasks, NUM_TASKS, nCurrentTime,
&nFreeMemory, &nFreeTapes,
ReadyQueue, &nReadyTail);
}
}
// 输出执行顺序
printf("作业执行顺序： ");
for (int i = 0; i < nExecutionCount; ++i)
{
printf("%s%s", tasks[nExecutionOrder[i]].name,
(i + 1 < nExecutionCount ? " " : ""));
}
printf("\n");
// 输出每个作业的到达—完成、周转与带权周转
for (int i = 0; i < NUM_TASKS; ++i)
{
int nTurnaround = tasks[i].nFinishTime - tasks[i].nArrivalTime;
double weighted = (double)nTurnaround / tasks[i].nServiceTime;
printf("%s：", tasks[i].name);
PrintTime(tasks[i].nArrivalTime);
printf("");
PrintTime(tasks[i].nFinishTime);
printf("周转时间：%d 带权周转时间：%.2f\n", nTurnaround, weighted);
}
return 0;
}–
/*
在本题我们使用了队列与贪心算法
1. 维护一个就绪队列(ReadyQueue)，按实际被系统接受(资源足够)进入队列的顺序
2. 使用贪心算法，表现在谁先到、且资源够，就立即进入系统
就绪队列用于记录已经成功进入系统的作业（即内存和磁带机资源均满足要求）
模拟执行：
JOB1(35,3)运行期间剩余(65,1)没有任何新作业能进入就绪队列
JOB1释放后，剩余(100,4)
JOB2(70,1)运行期间剩余(30，3)，JOB4(25,2)进入就绪队列，剩余(5,1)，此时没有任何新作业能进入就绪队列
JOB2释放后，剩余(75,2)
JOB4(25,2)运行期间剩余(75,2)，JOB5(20,2)进入就绪队列，剩余(55,0)，没有任何新作业能进入就绪队列
JOB4释放后，剩余(80,2)，JOB3(50,3)无法进入队列
JOB5释放后，剩余(100,4)，JOB3进入队列
JOB3执行
结束
*/