自顶向下-多级反馈队列

  • 多级反馈队列算法
    • 算法原理
    • 算法描述
    • 题目摘要
  • 自顶向下模块化设计
    • 整体框架
    • 具体实现
      • Generator
      • Scheduler
      • Executor
    • 整体代码实现
  • 总结及心得
    • 总结
    • 心得

多级反馈队列算法

多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。

算法原理

  1. 设有N个队列（Q1,Q2…QN），其中各个队列对于处理机的优先级不一样，即位于各个队列中的作业(进程)的优先级不一样。一般来说，优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高，依次类推其它的队列。
  2. 对于优先级最低的队列来说，里面是遵循时间片轮转法。位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。
  3. 各个队列的时间片不一样，它们的时间片随着优先级的增加而减少，优先级越高的队列中的时间片越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大。

算法描述

  1. 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
  2. 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
  3. 对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列末尾，直至完成。
  4. 在最后一个队列QN中的各个进程，按照时间片轮转分配时间片调度。
  5. 在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i-1队列全部为空时，才会去执行第i队列的进程（抢占式）。

特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。

题目摘要

  1. 假设有 5 个运行队列，它们的优先级分别为 1，2，3，4，5，它们的时间片长度分别为10ms,20ms,40ms,80ms,160ms，即第 i 个队列的优先级比第 i-1 个队列要低一级，但是时间片比第 i-1 个队列的要长一倍。
  2. 多级反馈队列调度算法包括四个部分：主程序main，进程产生器 generator，进程调度器函数 scheduler，进程运行器函数 executor。
  3. 结果输出：在进程创建、插入队列、执行时的相关信息，并计算输出总的平均等待时间。

补充说明：

  • 其中，Generator 用线程来实现，每隔一个随机时间(例如在[1,100]ms 之间)产生一个新的进程 PCB，并插入到第 1 个队列的进程链表尾部。
  • Scheduler 依次探测每个队列，寻找进程链表不为空的队列，然后调用 Executor, executor 把该队列进程链表首部的进程取出来执行。
  • 要设置 1 个互斥信号量来实现对第 1 个队列的互斥访问，因为generator 和 executor 有可能同时对第 1 个队列进行操作。
  • 同时要设置 1 个同步信号量，用于 generator 和scheduler 的同步：generator 每产生 1 个新进程，就 signal 一次这个同步信号量；只有所有队列不为空时，scheduler 才会运行，否则 scheduler要等待这个同步信号量。
  • 当所有进程运行完毕后，scheduler 退出，主程序结束。

自顶向下模块化设计

所谓的自顶向下的编程方法，本质上就是编写程序的视角从整体的宏观性逐层进入具体的微观性的一种编程思想。我们编写程序时一开始不用思考得事无巨细，把所有细节都想清楚；也不要面条式的想到哪里写到哪里。而应该是自顶向下的，从一个大的粗的核心的任务开始，逐级细分，最后再完成最底层的具体实现。

整体框架

根据题意，算法在整体上分为了四个部分：main、generator、scheduler、executor

  • main函数主要负责创建线程用以调度generator、scheduler函数，以及其他的一些次要工作（例如创建信号量、关闭线程等等）。
  • generator函数主要负责模拟进程的产生以及信号量的同步，模拟进程产生之后会被放置在多级队列中的第一队列队尾，并且分别释放两个信号量传递给scheduler和executor。前者用以激活调度（第一次激活后不一定再用到），后者用以解锁对第一队列中“进程”的使用权（generator和executor在第一队列互斥）。
  • scheduler函数主要负责调度executor函数来执行线程，在得到了来自generator的信号量之后，其会进入对多级队列的扫描循环，直到队列内为空（若进程没有执行完，则继续等待同步的信号量到来）或所有进程执行完毕。每次从上到下扫描到队列中的进程时，将其传入executor进行执行，同时再从头开始扫描（实现“优先级”），以此往复。
  • executor函数主要负责执行模拟进程，即对进程信息进行某种操作，执行完之后scheduler会根据进程的信息对进程进行转移或者删除操作。特别的executor在执行第一队列的模拟进程时，需要等待来自generator的信号量，同时和generator进行互斥访问，以防止冲突发生。

具体实现

根据上述整体框架的分析，我们可以对三大函数（main结构简单就不需要再拆解了）进行任务拆解。通过任务拆解得到其中的细分函数（子函数），然后用它们拼出最终的“大函数”。

Generator

结合题意，通过在整体框架中的分析可以得到generator及其所需子函数：

  1. 创建模拟进程：init_PCB
  2. 插入（第一）队列：insert_queue
  3. 输出若干信息：print_…
DWORD WINAPI generator(LPVOID q_);   //generator和它的子函数，以此类推PCB* init_PCB(int pid, int time);    //初始化PCBvoid insert_queue(queue* q, PCB* pcb);  //插入队列void print_generated(PCB* pcb);  //输出生成进程信息void print_sleep(int sleep);    //输出休眠信息
// generator整体实现DWORD WINAPI generator(LPVOID q_) {    srand((unsigned)time(NULL));//随机数种子    queue* q = (queue*)q_;    int count_process = 0;  //记录已生成的进程数    int sleep = 0;  //记录休眠时间    int count_sleep = 0;    //记录总计休眠时间    while (count_process < num_Process) {        PCB* pcb = init_PCB(count_process, count_sleep); //填入pid和到达时间（不觉得很怪吗）        print_generated(pcb);        sleep = 1 + rand() % 100;        count_sleep += sleep;        print_sleep(sleep);        EnterCriticalSection(&cs);        insert_queue(q, pcb);   //插入第一队列的队尾        LeaveCriticalSection(&cs);        ReleaseSemaphore(Sema[0], 1, NULL); //同步scheduler进行调度第一队列        ReleaseSemaphore(Sema[1], 1, NULL); //唤醒访问第一队列的executor        count_process++;        Sleep(sleep);    //隔一个随机的时间段    }    return 0;}

Scheduler

结合题意，通过在整体框架中的分析可以得到scheduler及其所需子函数：

  1. 查看当前多级队列是否为空：isEmpty
  2. 对进程进行队列间转移：transfer
  3. 对已完成进程进行删除操作：delete_（关键字冲突）
  4. 输出若干信息：print_…
DWORD WINAPI scheduler(LPVOID q_);bool isEmpty(queue q[]);    //查看队列是否为空void transfer(queue* q, queue* q_);   //队列间转移void delete_(queue* q);  //执行完的进程踢出队列并删除void print_transfer(queue q);  //输出转移插入信息void print_finish(queue q); //输出完成信息
// scheduler整体实现DWORD WINAPI scheduler(LPVOID q_) {    queue* q = (queue*)q_;    int count_finish = 0;    while (count_finish < num_Process) {    //当完成数没达到总线程数时进行循环        WaitForSingleObject(Sema[0], INFINITE); //当多级队列为空、以及开始时等待同步信号量        do {    //当不为空时进入调度            for (int i = 0; i < num_Queue; i++) {                if (q[i].list != NULL) {                    executor(&q[i], q);                    if (q[i].list->neededTime > q[i].list->usedTime) {                        if (i < (num_Queue - 1)) {                            EnterCriticalSection(&cs);                            transfer(&q[i], &q[i + 1]);                            print_transfer(q[i + 1]);                            LeaveCriticalSection(&cs);                        }                    }                    else {                        print_finish(q[i]);                        delete_(&q[i]);                        count_finish++;                    }                    break;  //执行完一次后重新从一级队列开始扫描                }            }        } while (!isEmpty(q));    }    print_average_WaitTime(WaitTime);    return 0;}

Executor

结合题意，通过在整体框架中的分析可以得到executor及其所需子函数：
（executor实现功能相对简单，故可分解部分较少）

  1. 执行某一进程后，让所有在队列中的模拟进程增加等待时间：add_WaitTime
  2. 输出若干信息：print_…
void executor(queue* q_,queue q[]);void add_WaitTime(queue* q_, queue q[]); //增加等待时间void print_executed(queue* q);   //输出执行信息
// executor整体实现void executor(queue* q_, queue q[]) {    if (q_->priority == 1) { //如果执行的队列是第一队列，则要等待生成器的信号，并且进入临界区执行        WaitForSingleObject(Sema[1], INFINITE);     //出现谜之问题        EnterCriticalSection(&cs);        Sleep(q_->timeSlice);        q_->list->usedTime += q_->timeSlice;        add_WaitTime(q_, q);        print_executed(q_);        LeaveCriticalSection(&cs);    }    else {        Sleep(q_->timeSlice);        q_->list->usedTime += q_->timeSlice;        add_WaitTime(q_, q);        print_executed(q_);    }    return;}

整体代码实现

理清上述三个主要函数的结构后，再对一些细节部分进行补充，整个算法的实现也就呼之欲出了。
// 多级反馈队列调度算法代码实现#include <stdio.h>#include <math.h>#include <time.h>#include <Windows.h>#include <stdlib.h>#define num_Process 10//定义必要的常量方便后面使用#define num_Queue 5#define maxWaitTime 100#define minTimeSlice 10#define neededTimeLB 2#define neededTimeUB 200CRITICAL_SECTION cs;    //创建临界区HANDLE Sema[2];     //一个用于generator和executor互斥访问第一个运行队列，另一个用于generator和scheduler同步int WaitTime = 0;   //累计每个进程的等待时间typedef struct PCB {    int pid;       //进程标识符，即进程的名字，改成int类型方便赋值    //以下部分为用于进程调度的信息    char state;         //‘r’: 运行状态；‘w’:就绪状态；‘b’:阻塞状态    int priority;       //进程优先级    int arrivalTime;    //进程的创建时间(到达时间)    int neededTime;     //进程需要的运行时间    int usedTime;       //进程已累计运行的时间    int totalWaitTime;  //进程已等待的CPU时间总和    //以下部分为进程的控制信息    struct PCB* next;   //指向下一个PCB的链表指针}PCB;typedef struct queue {    int priority;    //该队列的优先级    int timeSlice;   //该队列的时间片长度    struct PCB* list;   //指向该队列中进程PCB链表的头部 }queue;void init_queues(queue q[]);   //初始化队列DWORD WINAPI generator(LPVOID q_);   //generator和它的子函数，以此类推PCB* init_PCB(int pid, int time);    //初始化PCBvoid insert_queue(queue* q, PCB* pcb);  //插入队列void print_generated(PCB* pcb);  //输出生成进程信息void print_sleep(int sleep);    //输出休眠信息DWORD WINAPI scheduler(LPVOID q_);bool isEmpty(queue q[]);    //查看队列是否为空void transfer(queue* q, queue* q_);   //队列间转移void delete_(queue* q);  //执行完的进程踢出队列void print_transfer(queue q);  //输出转移插入信息void print_finish(queue q); //输出完成信息void executor(queue* q_,queue q[]);void add_WaitTime(queue* q_, queue q[]); //增加等待时间void print_executed(queue* q);   //输出执行信息void print_average_WaitTime(int time);     //输出总的平均等待时间int main() {    queue q[num_Queue] = {};    init_queues(q); //初始化多级队列        InitializeCriticalSection(&cs); //初始化临界区    Sema[0] = CreateSemaphore(NULL, 0, num_Process, NULL);    //创建信号量，注意把信号量上限调为最大进程数   X(    Sema[1] = CreateSemaphore(NULL, 0, num_Process, NULL);    HANDLE handle[2];   //给generator、scheduler函数辅以线程    handle[0] = CreateThread(NULL, 0, generator, (void*)&q[0], 0, NULL);    handle[1] = CreateThread(NULL, 0, scheduler, (void*)q, 0, NULL);    WaitForMultipleObjects(2, handle, TRUE, INFINITE);  //等待所有进程结束    for (int i = 0; i < 2; i++) {        CloseHandle(handle[i]);    }    DeleteCriticalSection(&cs);    getchar();    return 0;}void init_queues(queue q[]) {    //初始化队列    for (int i = 0; i < num_Queue; i++) {        q[i].priority = i + 1;        q[i].timeSlice = minTimeSlice * (int)pow(2, i);        q[i].list = NULL;    }    return;}DWORD WINAPI generator(LPVOID q_) {    srand((unsigned)time(NULL));//随机数种子    queue* q = (queue*)q_;    int count_process = 0;  //记录已生成的进程数    int sleep = 0;  //记录休眠时间    int count_sleep = 0;    //记录总计休眠时间    while (count_process < num_Process) {        PCB* pcb = init_PCB(count_process, count_sleep); //填入pid和到达时间（不觉得很怪吗）        print_generated(pcb);        sleep = 1 + rand() % 100;        count_sleep += sleep;        print_sleep(sleep);        EnterCriticalSection(&cs);        insert_queue(q, pcb);   //插入第一队列的队尾        LeaveCriticalSection(&cs);        ReleaseSemaphore(Sema[0], 1, NULL); //同步scheduler进行调度第一队列        ReleaseSemaphore(Sema[1], 1, NULL); //唤醒访问第一队列的executor        count_process++;        Sleep(sleep);    //隔一个随机的时间段    }    return 0;}PCB* init_PCB(int pid, int time) {    PCB* pcb = (PCB*)malloc(sizeof(PCB));    pcb->pid = pid;    pcb->arrivalTime = time;    pcb->neededTime = neededTimeLB + rand() % (neededTimeUB - neededTimeLB + 1);    pcb->next = NULL;    pcb->priority = 1;    pcb->state = 'w';    pcb->totalWaitTime = 0;    pcb->usedTime = 0;    return pcb;}void insert_queue(queue* q, PCB* pcb) {    if (q->list == NULL) {        q->list = pcb;        return;    }    else{   //否则往后传到队尾，令队尾的下一个为新来的pcb        PCB* temp = q->list;        while (temp->next != NULL) {            temp = temp->next;        }        temp->next = pcb;        return;    }}void print_generated(PCB* pcb) {    printf("Generator：Process %d is generated, neededTime = %d, arrivalTime = %d.\n", pcb->pid, pcb->neededTime, pcb->arrivalTime);    return;}void print_sleep(int sleep) {    printf("Generator：Sleep for %d ms before generating next new process...\n", sleep);    return;}DWORD WINAPI scheduler(LPVOID q_) {    queue* q = (queue*)q_;    int count_finish = 0;    while (count_finish < num_Process) {    //当完成数没达到总线程数时进行循环        WaitForSingleObject(Sema[0], INFINITE); //当多级队列为空、以及开始时等待同步信号量        do {    //当不为空时进入调度            for (int i = 0; i < num_Queue; i++) {                if (q[i].list != NULL) {                    executor(&q[i], q);                    if (q[i].list->neededTime > q[i].list->usedTime) {                        if (i < (num_Queue - 1)) {                            EnterCriticalSection(&cs);                            transfer(&q[i], &q[i + 1]);                            print_transfer(q[i + 1]);                            LeaveCriticalSection(&cs);                        }                    }                    else {                        print_finish(q[i]);                        delete_(&q[i]);                        count_finish++;                    }                    break;  //执行完一次后重新从一级队列开始扫描                }            }        } while (!isEmpty(q));    }    print_average_WaitTime(WaitTime);    return 0;}bool isEmpty(queue q[]){    for (int i = 0; i < num_Queue; i++) {        if (q[i].list != NULL) {            return false;        }    }    return true;}void transfer(queue* q, queue* q_) {    PCB* temp_ = q_->list;    PCB* temp = q->list;    //记录原队列头PCB的地址    while (temp_ != NULL && temp_->next != NULL) {  //功能是当队列不为空时，找到当前队列最后一个元素        temp_ = temp_->next;    }    q->list = q->list->next;  //原队列头指针指向下一个PCB    if (temp_ != NULL) {        temp_->next = temp;     //原队列头PCB被下一队列队尾(队尾不为空)指向    }    else {        q_->list = temp;   //原队列头PCB被下一队列队头(队列为空)指向    }    temp->next = NULL;      //原队列头PCB指向NULL，作为下一队列新的队尾    return;}void delete_(queue* q) {    WaitTime += q->list->totalWaitTime;  //记录等待时间    PCB* temp = q->list;    q->list = q->list->next;    free(temp);    return;}void print_transfer(queue q) {    while (q.list->next != NULL) {        q.list = q.list->next;    }    printf("Scheduler：Process %d is moved to queue %d, priority = %d.\n", q.list->pid, q.priority - 1, q.priority);    return;}void print_finish(queue q) {    printf("Scheduler：Process %d was done,total wait time = %d.\n", q.list->pid, q.list->totalWaitTime);    return;}void executor(queue* q_, queue q[]) {    if (q_->priority == 1) { //如果执行的队列是第一队列，则要等待生成器的信号，并且进入临界区执行        WaitForSingleObject(Sema[1], INFINITE);     //出现谜之问题        EnterCriticalSection(&cs);        Sleep(q_->timeSlice);        q_->list->usedTime += q_->timeSlice;        add_WaitTime(q_, q);        print_executed(q_);        LeaveCriticalSection(&cs);    }    else {        Sleep(q_->timeSlice);        q_->list->usedTime += q_->timeSlice;        add_WaitTime(q_, q);        print_executed(q_);    }    return;}void add_WaitTime(queue* q_, queue q[]) {    PCB* temp;    for (int i = 0; i < num_Queue; i++) {        if (q[i].priority != q_->priority) {            temp = q[i].list;            while (temp != NULL) {                temp->totalWaitTime += q_->timeSlice;                temp = temp->next;            }        }        else {            temp = q[i].list;            while (temp->next != NULL) {    //和上面不同，跳掉队头PCB                temp = temp->next;                temp->totalWaitTime += q_->timeSlice;            }        }    }    return;}void print_executed(queue* q) {    printf("Executor：Process %d in queue %d consumes %d ms.\n", q->list->pid, q->priority - 1, q->timeSlice);    return;}void print_average_WaitTime(int WaitTime) {    double avg_wt = WaitTime / num_Process;    printf("Main：All processes done, average wait time is %.2lf.\n", avg_wt);    return;}

总结及心得

总结

本次实验的具体实现流程可以分为几个部分：

  1. 分析题目的要求，得出整体框架（各部分的包含关系）
  2. 分解各部分的任务，得到子任务（子函数）
  3. 将各个子函数（未实现）以及其他细节像拼积木一样直接拼出各部分的实现
  4. 逐个实现子函数的功能
  5. 痛苦的DEBUG->完成

心得

  1. 面对较为复杂的任务时，自顶向下模块化设计的解决方式是非常管用的，因为它能够使你跳出对代码复杂具体实现的思考，让你在整体的、抽象的层面上进行规划和编排，并在这一过程中逐步分解出任务的层次结构，从而达到将整块大任务分解成一个个小任务的效果。
  2. 说人话就是，这相当于在做排除法，将任务切成一块一块的，以免遭遇到分析一整块大任务时，来自其内部不同部分的干扰，当排除了这些干扰，一次只做一两件事情，效率就会变得非常高。
  3. 第一次写博客，孩子很喜欢，下一次还要写，之后可能不单会写和编程相关的内容，还会写一些个人的思考、跨学科相关的想法等等。