如何用C语言实现处理机调度算法？

处理机调度算法是操作系统中的重要组成部分，它决定了在多道程序环境下，如何将处理机资源分配给就绪队列中的进程，本文详细介绍了几种常见的处理机调度算法及其实现方法，并通过C语言代码示例展示了短作业优先和优先级抢占式调度算法的实现过程。

一、处理机调度的目的与常见算法

1. 处理机调度的目的

在多道程序环境下，主存中有多个进程，其数目往往多于处理机数目，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行，处理机调度就是为了分配处理机，提高处理机的利用率及改善系统性能。

2. 常见调度算法

先来先服务（FCFS）调度算法：按照进程到达的顺序进行调度，有利于长作业，但不利于短作业。

短作业（进程）优先调度算法SJ(P)F：优先调度估计运行时间最短的作业，能有效地降低作业的平均等待时间，提高系统吞吐量。

高优先权优先（FPF）调度算法：根据进程的优先数进行调度，优先数高的进程先执行，适合紧急任务。

基于时间片的轮转调度算法：每个进程被分配一个时间片，轮流执行，保证所有进程在给定时间内均能获得处理机执行时间。

二、短作业优先调度算法的实现

以下是一个短作业优先调度算法的C语言实现示例，该算法用于模拟多道程序环境中的处理机调度过程。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef struct node {
    char id;
    int cputime;
    int needtime;
    int priority;
} PCB; //定义PCB结构体
#define jobNum 7 //作业数量
#define batch 2 //批处理作业个数
PCB pcb[jobNum]; //pcb数组用来保存所有作业的信息，其大小等于作业数量
PCB memory[2]; //memory数组用来保存被调入到主存中的所有作业信息，其大小等于批处理作业个数
PCB wait[jobNum batch]; //wait数组用来保存已到达作业，但没能被调入到主存中的作业，其大小等于jobNum-batch
int memoryNum = 0; //调入至主存中的作业个数，初始化为0
int waitNum = 0; //等待被调入的作业个数，初始化为0
int MaxTime = 1000; //定义最大的完成时间100
float totalTime = 0; //保存总的周转时间
float totalEndTime = 0; //保存总的结束时间
void sort(PCB *pcb, int count, char key);
void process(int currentTmp, int nextTmp);
int main(void) {
    PCB *tmp = (PCB*)malloc(sizeof(PCB));
    char id;
    int cputime, needtime, priority;
    int i, j;
    int current, next;
    printf("输入进程名(char)，到达时间(int)，所需运行时间(int)，优先数(int). 【按到达时间由先到后进行输入】
");
    for (i = 0; i < jobNum; i++) {
        rewind(stdin);
        printf("请输入第 %d 个作业的相关信息
", i + 1);
        scanf("%c%d%d%d", &id, &cputime, &needtime, &priority);
        tmp->id = id;
        tmp->cputime = cputime;
        tmp->needtime = needtime;
        tmp->priority = priority;
        pcb[i] = *tmp;
    }
    for (i = 0; i < jobNum; i++) {
        printf("作业 %c 的到达时间,所需运行时间,优先数分别为: %d, %d, %d;
", pcb[i].id, pcb[i].cputime, pcb[i].needtime, pcb[i].priority);
    }
    cout << "
不同时刻下内存中的运行作业序列、各作业进入内存的时刻及结束时刻: 
";
    for (i = 0; i < jobNum; i++) {
        current = pcb[i].cputime;
        if (i == jobNum 1) //说明是最后一个作业
            next = MaxTime;
        else
            next = pcb[i + 1].cputime; //保存下一个进程到达的时间，注意不能越界
        //先将作业放到wait中，再排序
        wait[waitNum] = pcb[i];
        waitNum++;
        if (next == current) continue; //两个作业同时到达后备队列
        if (waitNum > 1)
            sort(wait, waitNum, 'N');
        while (memoryNum < 2 && waitNum > 0) { //若当前主存中作业数量小于2，则把当前进程放入到主存中
            memory[memoryNum] = wait[0];
            cout << "作业 " << memory[memoryNum].id << " 进入内存的时刻是：" << memory[memoryNum].cputime << "；
";
            memoryNum++;
        }
        //逐个处理作业
        process(current, next);
    }
    return 0;
}
void sort(PCB *pcb, int count, char key) {
    int i, j;
    for (i = 0; i < count 1; i++) {
        for (j = 0; j < count i 1; j++) {
            if (key == 'D' && pcb[j].needtime > pcb[j + 1].needtime) { //降序排序
                PCB temp = pcb[j];
                pcb[j] = pcb[j + 1];
                pcb[j + 1] = temp;
            } else if (key == 'A') { //升序排序
                if (pcb[j].cputime > pcb[j + 1].cputime) {
                    PCB temp = pcb[j];
                    pcb[j] = pcb[j + 1];
                    pcb[j + 1] = temp;
                }
            }
        }
    }
}
void process(int currentTmp, int nextTmp) {
    int i;
    for (i = 0; i < memoryNum; i++) {
        memory[i].needtime--;
        if (memory[i].needtime == 0) {
            cout << "作业 " << memory[i].id << " 结束时刻：" << currentTmp << "；周转时间：" << currentTmp memory[i].cputime << "；
";
            totalTime += currentTmp memory[i].cputime;
            totalEndTime += currentTmp; //保存总的结束时间
            sort(wait, waitNum, 'N'); //重新排序，选择下一个要装入的作业
            memory[i] = wait[0]; //将新的作业装入内存
            waitNum--; //等待装入的作业数减一
            memoryNum = 2; //重新将内存中的作业数置为2
            cout << "作业 " << memory[i].id << " 进入内存的时刻是：" << currentTmp << "；
";
        }
    }
    currentTmp++; //时间增加一个单位
    if (currentTmp < nextTmp) {
        process(currentTmp, nextTmp); //递归调用process函数
    } else {
        cout << "所有作业已完成。
";
        cout << "平均周转时间：" << totalTime / jobNum << "；
";
        cout << "带权平均周转时间：" << totalTime / totalEndTime << "；
";
    }
}

三、优先级抢占式调度算法的实现

以下是一个优先级抢占式调度算法的C语言实现示例，该算法同样用于模拟多道程序环境中的处理机调度过程。

#include <iostream> #include <iomanip> using namespace std; const int N = 5; //“进程”结构体 struct Process { string p_name; Process* p_next; int time_needed; int priority; char status; void set(string p_name, int time_needed, int priority, char status, Process* p_next = NULL) { this->p_name = p_name; this->p_next = p_next; this->time_needed = time_needed; this->priority = priority; this->status = status; } } p[N]; bool cmp_pri(Process a, Process b) { return a.priority > b.priority; } void mySwitch(Process& a, Process& b) { Process t = a; a = b; b = t; } void printAll(Process p[]) { int i = 0; cout << "Pname: "; while (i != 5) cout << setw(6) << p[i++].p_name; cout << endl; i = 0; cout << "Pnext: "; while (i != 5) { if (p[i].p_next != NULL) cout << setw(6) << p[i++].p_next->p_name; else { cout << setw(6) << "NULL"; break; } } cout << endl; i = 0; cout << "Need:  "; while (i != 5) cout << setw(6) << p[i++].time_needed; cout << endl; i = 0; cout << "Prio:  "; while (i != 5) cout << setw(6) << p[i++].priority; cout << endl; i = 0; cout << "Status:" ; while (i != 5) cout << setw(6) << p[i++].status; while (1) if (getchar() == '
') break; } int main() { for (int i = 0; i < N; i++) { string P = "P"; string t = P.append(to_string(i)); p[i].set(t, (i + 1) * 13 % 7, (i + 1) * 3 % 7, 'R'); //模仿“随机”生成一个进程表 if (i != 4) p[i].p_next = &p[i + 1]; else p[i].p_next = NULL; } do { printAll(p); int maxpro = p[0].priority; int k2 = 0; for (int i = p[0].p_next; i != NULL; i = i->p_next) { if (maxpro < i->priority) { maxpro = i->priority; k2 = i->p_next->p_next p; } } mySwitch(p[0], *k2); if (p[0].time_needed > 0) { p[0].time_needed--; p[0].priority--; } else p[0].status = 'E'; } while (p[0].priority != 0); return 0; }

四、相关问题与解答栏目

Q1: 为什么短作业优先调度算法不一定能真正做到短作业优先？

A1: 因为短作业优先调度算法是根据用户所提供的估计时间来决定进程的长短，而用户对作业（进程）的估计运行时间可能不准确，导致算法不一定能真正做到短作业优先，该算法对长作业（进程）不利，可能导致长作业长期不被调用。

Q2: 在优先级抢占式调度算法中，如果两个进程的优先级相同，应该如何处理？

A2: 如果两个进程的优先级相同，可以采用先来先服务的原则进行处理，即先到达的进程先执行，或者也可以根据其他因素（如进程的到达时间、CPU使用时间等）来决定哪个进程先执行，具体处理方式可以根据实际需求进行设计。

到此，以上就是小编对于“处理机调度算法c语言”的问题就介绍到这了，希望介绍的几点解答对大家有用，有任何问题和不懂的，欢迎各位朋友在评论区讨论，给我留言。