操作系统作业之CPU调度算法的简单实现

#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执行
结束
*/