优先级进程调度算法

实验要求

(1)系统有N个进程,每个进程用一个进程控制块来代表,进程控制块的结构如下所示:

  • 进程名
  • 到达时间
  • 估计运行时间
  • 进程优先级
  • 进程状态
  • ……
  • 链接指针

进程的优先级、估计运行时间由用户程序任意设定,且优先数越低,优先级越高。调度时,总是选择优先级最高的进程运行。

(2)为了调度方便,设计一个指针指向就绪队列中的第一个进程。另外再设一个当前运行进程指针,指向当前正运行的进程。

(3)处理机调度时,总是选择已经到达队列的优先级最高的进程运行,进程每运行一次,优先级减1。为了采用动态优先级调度,进程每运行一次,其优先级就减1。由于本实验是模拟实验,所以对选中进程并不实际启动运行,而只是执行:优先数加1估计运行时间减1,用这两个操作来模拟进程的一次运行。

(4)进程运行一次后,若剩余时间不为0,且其优先级低于就绪队列的其他进程优先级,则选择一个高优先级进程抢占CPU;若剩余时间为0,把它撤出就绪队列。

(5)若就绪队列不空,则重复上述的步骤(3)和(4),直到所有进程成为完成状态。

(6)在所设计的调度程序中,应包含显示或打印语句,以便显示或打印每次选中进程的名称及运行一次后队列的变化情况。

程序代码

/*实验3 按优先级调度的算法
* 王宇松 admin@wangyusong.cn
*/

#include <iostream>
using namespace std;

int currentTime = 0;    //记录当前时间

typedef struct pcb    //进程控制块结构
{
    char pname[100];        //进程名
    int runtime;            //运行时间
    int arrivetime;            //到达时间
    char state;            //进程状态
    int priority;            //进程优先级
    int finishtime;          //进程结束时间
    struct pcb* next;        //链接指针
}PCB;

/*----------函数声明----------*/
//建立进程,输入进程数目n,读入进程信息,并建立链表;
void InputProcess(PCB*& head_input);
//输出就绪队列
void PrintReadyList(PCB* head_input);
//检查就绪队列并运行进程
int ReadyProcess(PCB* head_input, PCB* head_run);
//运行进程
int RunProcess(PCB*& head_run);
//删除运行结束的进程
void DeleteFinishProcess(PCB*& head_input);
//创建带头节点的链表
void CreateList(PCB*& node);


void CreateList(PCB*& node) {
    //创建带头节点的链表
    node = new PCB;
    node->next = nullptr;
}

void DeleteFinishProcess(PCB*& head_input) {
    //删除运行结束的进程
    PCB* p = head_input->next;
    PCB* pre = head_input;
    while (p != nullptr) {
        if (p->runtime == 0) {    //进程运行结束,移除
            pre->next = p->next;
            p = p->next;
        }
        else {
            pre = pre->next;
            p = p->next;
        }
    }
}

void InputProcess(PCB*& head_input) {
    //建立进程,输入进程数目n,输入各个进程信息,并建立链表;
    cout << "输入需要运行的进程数量:";
    int n;
    cin >> n;
    //输入进程信息:进程名,运行时间,到达时间等信息
    cout << "请输入进程信息:进程名称、运行时间、到达时间、优先数" << endl;
    PCB* rear = head_input;
    for (int i = 0; i < n; i++) {
        PCB* node = new PCB;
        cin >> node->pname >> node->runtime >> node->arrivetime >> node->priority;
        node->state = 'n';        //进程状态设置
        rear->next = node;        //将结点连接至就绪队列
        rear = rear->next;
    }
    rear->next = nullptr;            //尾结点next指针置空
    cout << endl << "进程信息输入完成,开始运行!" << endl << endl;
}

void GetPriorityProcess(PCB* head_input, PCB*& head_run) {
    //获取优先级最高的进程
    if (head_input->next == nullptr)    //就绪队列为空
        head_run = nullptr;        //返回nullptr
    else {
        head_run = head_input->next;
        PCB* p = head_input->next;
        while (p != nullptr) {    //比较优先级
            if (p->arrivetime > currentTime) {
                //当前时间,进程尚未到达,跳过当前进程
                continue;
            }
            if (p->priority < head_run->priority)
                head_run = p;
            p = p->next;
        }
    }
}

void PrintReadyList(PCB* head_input) {    //输出就绪队列
    PCB* p = head_input->next;
    if (p != nullptr) {
        cout << "-----当前进程运行结束后的就绪队列-----" << endl;
        while (p != nullptr) {
            cout << "进程名称:" << p->pname << " 优先数:"
                << p->priority << " 剩余运行时间:" << p->runtime;
            if (p->arrivetime > currentTime)
                cout << "(当前时间,进程尚未到达)";
            cout << endl;
            p = p->next;
        }
        cout << endl;
    }
}


int RunProcess(PCB*& head_run) {    //运行进程
    //修改进程的状态
    head_run->state = 'r';
    //输出进程运行信息 
    cout << "process: " << head_run->pname << " is running!" << endl;
    head_run->runtime--;    //运行时间减一
    head_run->priority++;    //优先数加一,优先级降低
    head_run->state = 'n';
    currentTime++;
    return 0;
}

int ReadyProcess(PCB* head_input, PCB* head_run) {    //检查就绪队列并运行进程
    //就绪队列为空时,结束运行
    GetPriorityProcess(head_input, head_run);
    if (head_run == nullptr) {
        return 0;
    }
    //取出一个进程运行它,将时间减1
    while (head_run != nullptr) {
        RunProcess(head_run);    //运行进程
        DeleteFinishProcess(head_input);    //将运行结束的进程移除
        PrintReadyList(head_input);    //打印就绪队列
        GetPriorityProcess(head_input, head_run);    //获取下一优先级最高进程
    }
    cout << endl << "全部进程运行结束,程序运行结束,总耗时" << currentTime << "!" << endl;
    return 0;
}

int main() {     //主函数
    PCB* head_input;        //就绪队列头指针
    PCB* head_run;            //运行进程指针
    CreateList(head_input);    //初始化就绪队列
    CreateList(head_run);    //初始化就绪队列
    InputProcess(head_input);    //读入进程信息,创建就绪队列
    ReadyProcess(head_input, head_run);    //检查就绪队列并运行进程
    return 0;
}

运行结果

优先级进程调度

位示图法磁盘空间管理

实验要求

(1)假定现有一个磁盘组,共有48个柱面。每个柱面有4个磁道,每个磁道又划分成4个物理记录。磁盘的空间使用情况用位示图表示。位示图用若干个字构成,每一位对应一个磁盘块。“1”表示占用,“0”表示空闲。假定字长为16位,一个字可用来模拟磁盘的一个柱面,其位示图如下图所示。系统设置一个变量S记录当前的空闲磁盘块个数。位示图的初始状态为第1个字为“1”,其他全部空闲。

(2)申请一个磁盘块时,磁盘可以不连续分配,由磁盘块分配程序查位示图,找出一个为0的位,并计算磁盘的物理地址,即求出它的柱面号、磁道号和扇区号。

(3)当释放一个相对物理块时,运行回收程序,计算该块在位示图中的位置,再把相应由“1”改为“0”。

程序代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int TOTALNUM = 768;    /* 总磁盘块数 */
int m[48][16] = { 0 };        /* 磁盘块位示图 */
int s = TOTALNUM;        /* 空闲磁盘块数 */
int fileCount = 0;

class myFile;

/* -----函数声明----- */
int getRelativeBlockNo(int& m, int& n);
vector<int> getPhysicsNo(int relative_block_no);
int freeGetRelativeBlockNo(int x, int y, int z);
pair<int, int> freeGetNo(int relative_block_no);
void showDiskInfo(vector<myFile>& file);
void freeBlock(myFile& f);
pair<int, int> getFreeBlockNo();
void allocBlock(myFile& f, bool& flag);
void createFile(vector<myFile>& file);
void deleteFile(vector<myFile>& file);

class myFile {            /* 定义文件类 */
public:
    int fid;        /* 文件编号 */
    string name;        /* 文件名称 */
    vector<int> RBN;    /* 为文件分配的磁盘相对块号 */
    int size;        /* 文件大小,单位为磁盘块 */
public:
    myFile(int fid = 0, string name = "", vector<int> v = {}, int size = 0) {
        this->fid = fid;
        this->name = name;
        this->RBN = v;
        this->size = size;
    }
    void showFile();    /* 显示文件详细信息 */
};

void myFile::showFile() {
    cout << "文件详细信息如下:" << endl;
    cout << "文件编号:" << this->fid;
    cout << "    文件名:" << this->name;
    cout << "    文件大小:" << this->size << endl;
    cout << "此文件分配到的磁盘空间如下:" << endl;
    for (auto it = this->RBN.begin(); it != this->RBN.end(); ++it) {
        vector<int> res = getPhysicsNo(*it);
        cout << "磁盘相对块号:" << *it << "   ";
        cout << "对应磁盘物理信息--->柱面号:" << res[0] << "  磁头号:"
            << res[1] << " 物理块号:" << res[2] << endl;
    }
    cout << endl;
}

int main() {
    vector<myFile> file;    /* 记录已创建的文件 */
    string choice;            /* 记录用户输入 */
    for (int i = 0; i < 16; ++i) {
        m[0][i] = 1;        /* 初始状态:第1个字为“1”,其他全部空闲 */
        s--;
    }
    while (true) {
        cout << "----1.创建文件----2.删除文件----3.查看磁盘状况----4.退出程序----" << endl;
        cin >> choice;
        if (choice == "1") {
            createFile(file);
        }
        else if (choice == "2") {
            deleteFile(file);
        }
        else if (choice == "3") {
            showDiskInfo(file);
        }
        else if (choice == "4") {
            cout << "程序已正常退出!" << endl;
            break;
        }
        else {
            cout << "输入错误!" << endl;
        }
    }
    return 0;
}

/* 由字号、位号计算磁盘的相对块号 */
int getRelativeBlockNo(int& m, int& n) {
    int res = m * 16 + n;        /* 相对块号 */
    return res;
}

/* 相对块号转换成磁盘的物理地址 */
vector<int> getPhysicsNo(int relative_block_no) {
    vector<int> res;
    res.push_back(relative_block_no / 16);        /* 柱面号 */
    res.push_back((relative_block_no % 16) / 4);    /* 磁头号 */
    res.push_back((relative_block_no % 16) % 4);    /* 物理块号 */
    return res;
}

/* 释放空间时,计算相对块号 */
int freeGetRelativeBlockNo(int x, int y, int z) {
    int res = x * 16 + y * 4 + z;    /* 相对块号 */
    return res;
}

/* 释放空间时,根据相对块号计算字号和位号 */
pair<int, int> freeGetNo(int relative_block_no) {
    int x = relative_block_no / 16;            /* 字号 */
    int y = relative_block_no % 16;            /* 位号 */
    return { x,y };
}


/* 显示磁盘信息,包括剩余空闲盘块、已分配盘块等信息 */
void showDiskInfo(vector<myFile>& file) {
    cout << "磁盘信息如下:" << endl;
    cout << "总盘块数:" << TOTALNUM << "    已分配盘块数:"
        << (TOTALNUM - s) << "    空闲盘块数:" << s << endl;
    if (!file.empty()) {
        cout << endl << "文件统计信息如下:" << endl;
        for (auto it = file.begin(); it != file.end(); ++it) {
            cout << "文件编号:" << (*it).fid << "    文件名:" << (*it).name 
                << "  大小:"    << (*it).size << "个磁盘块" << endl;
        }
    }
    cout << endl;
}

/* 获取第一个空闲磁盘块的字号和位号 */
pair<int, int> getFreeBlockNo() {
    for (int i = 0; i < 48; ++i) {
        for (int j = 0; j < 16; ++j) {
            if (m[i][j] == 0) {        /* 寻找空闲磁盘块 */
                return { i,j };        /* 返回字号、块号 */
            }
        }
    }
    return { -1,-1 };    /* 没有空闲磁盘块 */
}

/* 为文件f分配磁盘块 */
void allocBlock(myFile& f,bool& flag) {
    if (f.size <= s) {    /* 磁盘剩余空间足够 */
        int size = f.size, rbn = -1;
        pair<int, int> val;
        while (size-- > 0) {
            flag = true;
            val = getFreeBlockNo();        /* 获取空闲磁盘块信息 */
            m[val.first][val.second] = 1;    /* 更新位示图 */
            rbn = getRelativeBlockNo(val.first, val.second);
            f.RBN.push_back(rbn);        /* 保存分配到的相对块号 */
            s--;                /* 磁盘空闲盘块数减一 */
        }
    }
    else {        /* 磁盘空间不足,分配失败 */
        flag = false;
    }
}

/* 释放文件f的磁盘块 */
void freeBlock(myFile& f) {
    vector<int> res = f.RBN;
    pair<int, int> val;
    for (auto it = res.begin(); it != res.end(); ++it) {
        val = freeGetNo(*it);        /* 计算字号和位号 */
        m[val.first][val.second] = 0;    /* 释放空间,更新位示图 */
        s++;        /* 更新空闲盘块数 */
    }
}

/* 创建文件 */
void createFile(vector<myFile>& file) {
    myFile f;
    bool flag = false;
    cout << "请输入文件名称  文件大小:";
    cin >> f.name >> f.size;
    f.fid = ++fileCount;        /* 生成文件编号 */
    allocBlock(f,flag);        /* 分配磁盘块 */
    if (flag) {
        file.push_back(f);
        cout << endl << "文件创建成功!" << endl;
        f.showFile();        /* 输出文件详细信息 */
    }
    else {
        cout << "磁盘空间不足,文件创建失败!" << endl << endl;
    }
}

/* 删除文件 */
void deleteFile(vector<myFile>& file) {
    cout << "请输入待删除的文件编号(fid):";
    int fid;
    bool flag = false;    /* 标记是否找到待删除文件 */
    cin >> fid;            /* 读入待删除文件编号 */
    for (auto it = file.begin(); it != file.end(); ++it) {
        if ((*it).fid == fid) {        /* 找到待删除文件 */
            freeBlock(*it);        /* 释放磁盘块 */
            file.erase(it);        /* 文件数组中删除当前文件 */
            flag = true;        /* 更新标志位 */
            break;
        }
    }
    if (flag) {
        cout << "文件删除成功!" << endl << endl;
    }
    else {
        cout << "文件删除失败!" << endl << endl;
    }
}

运行结果及说明

初始状态,第1个字已被占用,其他全部空闲:

初始状态

创建3个文件,并分配存储空间,3个文件的信息分别为:

  1. 文件名:file1 文件大小:3个磁盘块
  2. 文件名:file2 文件大小:3个磁盘块
  3. 文件名:file3 文件大小:4个磁盘块

分配完成后,剩余空闲盘块数变为742个:

位示图法

删除文件file2,并显示当前磁盘信息:

文件file2(大小为3个磁盘块)删除完成后,空闲磁盘块由之前的742变为745:

位示图法

创建比file2更大的文件file4,文件大小为5个磁盘块,创建完成后,空闲盘块数由745变为740:

位示图法

尝试创建文件大小比当前空闲盘块数更大的文件,提示磁盘空间不足,文件创建失败:

位示图法

尝试输入不存在的文件编号,试图删除不存在的文件,提示删除失败:

位示图法

删除全部文件,查看空闲磁盘块情况,全部删除后,恢复至初始状态,即0~15号磁盘块已被占用,空闲盘块为752:

位示图法


最后修改:2021 年 07 月 11 日 10 : 45 AM