查看: 2054|回复: 0

【计算机操作系统】作业调度算法的 C++ 实现（附源码）

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2021-4-9 15:36 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

【计算机操作系统】作业调度算法的 C++ 实现（附源码）
文章目录
一、实验目的
二、实验内容
2.1 单道处理系统的作业调度
2.2 多道程序系统的作业调度
三、流程图
3.1 单道批处理系统的作业调度
四、设计思想
4.1 设计思路
4.2 单道批处理系统
4.2.1 代码结构
4.2.2 FCFS
4.2.3 SJF
4.2.4 HRRN
4.3 多道批处理系统
4.3.1 FCFS + PSA
五、代码实现
六、运行结果
6.1 单道批处理（FCFS）
6.2 单道批处理（SJF）
6.3 单道批处理（HRRN）
6.4 多道批处理（FCFS + PSA）
七、结尾
一、实验目的
用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。因为源码中我对一些关键步骤的注释已经比较清晰了，所以在本文中不会再对每一个细节都进行分析，只分析整体的代码结构和所使用到的设计模式。

博客内所有文章均为原创，所有示意图均为原创，若转载请附原文链接。

二、实验内容
2.1 单道处理系统的作业调度
作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRRN）的调度算法。
对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。

2.2 多道程序系统的作业调度
作业调度算法：采用基于先来先服务的调度算法或基于优先级的作业调度算法。
对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。

三、流程图
3.1 单道批处理系统的作业调度

四、设计思想
4.1 设计思路
对于单道批处理系统，由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。
作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。
作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。
而对于多道批处理系统来说，作业调度（响应比）按一定的算法从磁盘上的“输入井”中选择资源能得到满足的作业装入内存，使作业有机会去占用处理器执行。但是，一个作业能否占用处理器，什么时间能够占用处理器，必须由进程调度来决定。所以，作业调度选中了一个作业且把它装入内存时，就应为该作业创建一个进程，若有多个作业被装入内存，则内存中同时存在多个进程，这些进程的初始状态为就绪状态，然后，由进程调度（优先数）来选择当前可占用处理器的进程，进程运行中由于某种原因状态发生变化，当它让出处理器时，进程调度就再选另一个作业的进程运行。因此，作业调度与进程调度相互配合才能实现多道作业的并行执行。

4.2 单道批处理系统
4.2.1 代码结构
因为这里的单道批处理系统需要实现多种算法，因此使用了模板方法设计模式 + 策略模式来进行开发，下面为各种算法的类签名，算法的具体实现可见代码实现。

/* 单道批处理系统基类 */
class SchedulingAlgorithm;

/* First-Come First-Served 先来先服务算法 */
class FCFSSchedulingAlgorithm : public SchedulingAlgorithm;

/* Short Job First 短作业优先算法 */
class SJFSchedulingAlgorithm : public SchedulingAlgorithm;

/* Highest Response Ratio Next 高响应比优先算法 */
class HRRNSchedulingAlgorithm : public SchedulingAlgorithm;
1
2
3
4
5
6
7
8
9
10
11
4.2.2 FCFS
因为这里使用优先级队列来实现，所以我们只需要为每种算法定义不同的比较函数即可，比如对于FCFS算法来说，它的比较算法就是比较该作业提交的时间。

// First-Come First-Served
class FCFSSchedulingAlgorithm : public SchedulingAlgorithm
{
public:
struct PriorityCmp
{
bool operator()(const JCB j1, const JCB j2)
{
return j1.submit_time > j2.submit_time;
}
};

FCFSSchedulingAlgorithm(){}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
4.2.3 SJF
对于SJF算法来说，它的比较函数就是比较作业的时间长度（时间越短优先级越高）。

// Short Job First
class SJFSchedulingAlgorithm : public SchedulingAlgorithm
{
public:
struct PriorityCmp
{
bool operator()(const JCB j1, const JCB j2)
{
return j1.required_running_time > j2.required_running_time;
}
};

SJFSchedulingAlgorithm(){}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
4.2.4 HRRN
该算法的比较函数比较的是每个作业的响应比：（等待时间+要求服务时间）/要求服务时间，响应比越高，优先级越高，越优先被调度。

// Highest Response Ratio Next
class HRRNSchedulingAlgorithm : public SchedulingAlgorithm
{
public:
struct PriorityCmp
{
double getPriority(JCB jcb)
{
return ((cur_time - jcb.submit_time) + jcb.required_running_time) / jcb.required_running_time;
}

bool operator()(const JCB j1, const JCB j2)
{
return getPriority(j1) > getPriority(j2);
}
};

HRRNSchedulingAlgorithm(){}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
4.3 多道批处理系统
4.3.1 FCFS + PSA
对于多道批处理系统来说，情况会复杂一些，因为对于多道批处理系统，除了作业的调度还存在进程的调度，也就是作业调度决定该任务能不能使用处理机（有没有资格），但就算该任务被调度了，因为多道批处理系统，还需要考虑相关的资源，因此能不能使用到处理机，还要看进程的调度。
因此在这里对于作业调度采用了FCFS算法，而对于进程的调度采用了PSA算法（静态优先级，可抢占），并且没有继续使用实验一中的进程调度算法的代码，而是重新写了一遍。
所有的任务初始会被存放在 back_queue 中，而就绪的任务和正在运行的任务都存储于 psa_ready_queue 中，等到 psa_ready_queue 中存在空间时，会通过任务调度算法从 back_queue 中选择合适的任务进行调度，当任务（准确说是进程）被调到 psa_ready_queue 中后，会根据它的优先级判断它是否能够优先运行，如果不能就只能保持就绪状态，一直等到优先级高的进程运行完毕后再运行。
因为这部分代码的逻辑比较复杂，所以就不在这里单独罗列了，具体可见下面的代码实现。需要注意的是多道批处理系统代码逻辑中被注释掉的代码为测试代码，可以使用其来对代码的准确性进行测试。

五、代码实现
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstdlib>
#include <ctime>
#include <unistd.h>
#include <iomanip>

typedef int TimeSlice;
typedef int Resource;
typedef std::queue<TimeSlice> * JobTimeSeries;

TimeSlice cur_time = 0;
int average_turnaround_time = 0;
double average_power_turnaround_time = 0;

enum ProcessStatus
{
Ready = 0,
Running = 1,
//Finish = 2
};

typedef int Pid;
typedef int TimeSlice;
typedef int Priority;

struct JCB;
typedef JCB * JCBptr;

struct PCB
{
PCB(JCBptr jcb_) : jcb(jcb_){}
Pid pid;
ProcessStatus status;
Priority priority;
JCBptr jcb;
};

typedef PCB * PCBptr;

enum JobStatus
{
Wait = 0,
Run = 1,
Finish = 2
};

struct JCB
{
std::string job_name;
TimeSlice submit_time;
TimeSlice required_running_time;

TimeSlice start_time = -1;
TimeSlice finish_time = 0;
TimeSlice already_run_time = 0;

Resource required_resource;
JobStatus job_status;
PCBptr pcb = new PCB(this);
};

class Util
{
public:
static inline int getRandom(const int min_val, const int max_val, int match)
{
srand(time(0) + match);
return rand() % (max_val - min_val - 1) + min_val;
}

static inline bool printJobData(const JCB jcb)
{
TimeSlice start_time = cur_time;
TimeSlice finish_time = start_time + jcb.required_running_time;
TimeSlice turnaround_time = finish_time - jcb.submit_time;
double power_turnaround_time = turnaround_time / (jcb.required_running_time / 1.0);

std::cout << "[Data] " << jcb.job_name << " "
<< " Start time: " << start_time << " "
<< " Finish time: " << finish_time << " "
<< " Turnaround time: " << turnaround_time << " "
<< " Power turnaround time: " << std::setprecision(2) << power_turnaround_time << std::endl;

average_turnaround_time += turnaround_time;
average_power_turnaround_time += power_turnaround_time;

return true;
}

static inline bool printJobData(const JCB jcb, bool isMul)
{
TimeSlice turnaround_time = jcb.finish_time - jcb.submit_time;
double power_turnaround_time = turnaround_time / (jcb.required_running_time / 1.0);

std::cout << "[Data] " << jcb.job_name << " "
<< " Finish time: " << jcb.finish_time << " "
<< " Turnaround time: " << turnaround_time << " "
<< " Power turnaround time: " << std::setprecision(2) << power_turnaround_time << std::endl;

average_turnaround_time += turnaround_time;
average_power_turnaround_time += power_turnaround_time;

return true;
}
};

class SchedulingAlgorithm
{
public:

// virtual bool initPCB(std::priority_queue<JCB, std::vector<JCB>, std::less<JCB>> * ready_queue, int process_num) = 0;
// virtual bool processPCB(JCB & pcb) = 0;
};

// First-Come First-Served
class FCFSSchedulingAlgorithm : public SchedulingAlgorithm
{
public:
struct PriorityCmp
{
bool operator()(const JCB j1, const JCB j2)
{
return j1.submit_time > j2.submit_time;
}
};

FCFSSchedulingAlgorithm()
{}

private:

};

// Short Job First
class SJFSchedulingAlgorithm : public SchedulingAlgorithm
{
public:
struct PriorityCmp
{
bool operator()(const JCB j1, const JCB j2)
{
return j1.required_running_time > j2.required_running_time;
}
};

SJFSchedulingAlgorithm()
{}

};

// Highest Response Ratio Next
class HRRNSchedulingAlgorithm : public SchedulingAlgorithm
{
public:
struct PriorityCmp
{
double getPriority(JCB jcb)
{
return ((cur_time - jcb.submit_time) + jcb.required_running_time) / jcb.required_running_time;
}

bool operator()(const JCB j1, const JCB j2)
{
return getPriority(j1) > getPriority(j2);
}
};

HRRNSchedulingAlgorithm()
{}
};

template<typename PriorityCmp>
class JobScheduling
{
public:
JobScheduling(int job_num)
{
job_num_ = job_num;
sa_ = new SchedulingAlgorithm();
wait_queue_ = new std::priority_queue<JCB, std::vector<JCB>, PriorityCmp>();
mock_jcbs_ = new std::priority_queue<JCB, std::vector<JCB>, PriorityCmpForMock>();
finish_queue_ = new std::queue<JCB>();

mockJCBs();
}

protected:
struct PriorityCmpForMock
{
bool operator()(const JCB j1, const JCB j2)
{
return j1.submit_time > j2.submit_time;
}
};

bool mockJCBs()
{
for (int i = 0; i < job_num_; ++i)
{
JCBptr jcb = new JCB();
jcb->job_name = "job" + std::to_string(i);
jcb->job_status = Wait;
jcb->submit_time = Util::getRandom(1, 20, i);
// The minimum value is 3 so that each segment can be divided into time slice
jcb->required_running_time = Util::getRandom(3, 10, i);

mock_jcbs_->push(*jcb);
std::cout << "[INFO] finish init " << jcb->job_name << " with "
<< " submit_time " << jcb->submit_time
<< " required_running_time " << jcb->required_running_time << std::endl;
}
}

void getCurrentReadyQueue()
{
while (!wait_queue_->empty())
{
JCB jcb = wait_queue_->top();
std::cout << jcb.submit_time << std::endl;
wait_queue_->pop();
}
}

int job_num_;
SchedulingAlgorithm* sa_;
std::priority_queue<JCB, std::vector<JCB>, PriorityCmpForMock>* mock_jcbs_;
std::priority_queue<JCB, std::vector<JCB>, PriorityCmp>* wait_queue_;
std::queue<JCB>* finish_queue_;
};

template<typename SchedulingAlgorithm, typename PriorityCmp>
class SimpleBatchProcessingSystemJobScheduling : JobScheduling<PriorityCmp>
{
public:
SimpleBatchProcessingSystemJobScheduling(int job_num)
: JobScheduling<PriorityCmp>(job_num)
{}

bool start()
{
cur_time = this->mock_jcbs_->top().submit_time;
while (!this->wait_queue_->empty() || !this->mock_jcbs_->empty())
{
// Simulate adding tasks dynamically
if (!this->mock_jcbs_->empty() && this->mock_jcbs_->top().submit_time <= cur_time)
{
JCB jcb = this->mock_jcbs_->top();
this->mock_jcbs_->pop();

std::cout << "[INFO] add " << jcb.job_name << " to wait queue." << std::endl;
this->wait_queue_->push(jcb);
}

if (!this->wait_queue_->empty())
{
JCB jcb = this->wait_queue_->top();
this->wait_queue_->pop();

std::cout << "[INFO] begin to do " << jcb.job_name << "." << std::endl;
jcb.job_status = Run;
// simulation do job
sleep(1);
std::cout << "[INFO] do " << jcb.job_name << " finish." << std::endl;

jcb.job_status = Finish;
// print job Data.
Util::printJobData(jcb);
this->finish_queue_->push(jcb);
cur_time += jcb.required_running_time;
}
else
{
// Slowly increase time slice when there is no job
cur_time += 1;
}
}
std::cout << "[INFO] all jobs finished." << std::endl;
std::cout << "[LOG] average turnaround time " << (average_turnaround_time / this->job_num_)
<< " average power turnaround time " << (average_power_turnaround_time / this->job_num_) << std::endl;
}

private:

};

class MultiprogrammedBatchProcessingSystemJobScheduling
{
public:
struct PriorityCmpForPCB
{
bool operator()(const PCBptr p1, const PCBptr p2)
{
return p1->priority < p2->priority;
}
};

struct PriorityCmpForBack
{
bool operator()(const JCBptr j1, const JCBptr j2)
{
return j1->submit_time > j2->submit_time;
}
};

MultiprogrammedBatchProcessingSystemJobScheduling()
{
back_queue_ = new std::priority_queue<JCBptr, std::vector<JCBptr>, PriorityCmpForBack>();
psa_ready_queue_ = new std::priority_queue<PCBptr, std::vector<PCBptr>, PriorityCmpForPCB>();

std::cout << "input job num:" << std::endl;
std::cin >> job_num_;
for (int i = 0; i < job_num_; i++)
{
std::cout << "input job" << i << " submit_time & required_running_time & priority" << std::endl;

JCBptr jcb = new JCB();
jcb->job_name = "job" + std::to_string(i);
jcb->job_status = Wait;
std::cin >> jcb->submit_time;
std::cin >> jcb->required_running_time;
std::cin >> jcb->pcb->priority;
back_queue_->push(jcb);
}

/*
job_num_ = 6;

JCBptr jcb = new JCB();
jcb->job_name = "A";
jcb->job_status = Wait;
jcb->submit_time = 0;
jcb->required_running_time = 50;
jcb->pcb->priority = 5;
back_queue_->push(jcb);

jcb = new JCB();
jcb->job_name = "B";
jcb->job_status = Wait;
jcb->submit_time = 20;
jcb->required_running_time = 60;
jcb->pcb->priority = 7;
back_queue_->push(jcb);

jcb = new JCB();
jcb->job_name = "C";
jcb->job_status = Wait;
jcb->submit_time = 50;
jcb->required_running_time = 40;
jcb->pcb->priority = 3;
back_queue_->push(jcb);

jcb = new JCB();
jcb->job_name = "D";
jcb->job_status = Wait;
jcb->submit_time = 80;
jcb->required_running_time = 80;
jcb->pcb->priority = 8;
back_queue_->push(jcb);

jcb = new JCB();
jcb->job_name = "E";
jcb->job_status = Wait;
jcb->submit_time = 100;
jcb->required_running_time = 30;
jcb->pcb->priority = 6;
back_queue_->push(jcb);

jcb = new JCB();
jcb->job_name = "F";
jcb->job_status = Wait;
jcb->submit_time = 120;
jcb->required_running_time = 70;
jcb->pcb->priority = 9;
back_queue_->push(jcb);
*/
}

bool start()
{
cur_time = back_queue_->top()->submit_time;
while (!back_queue_->empty() || !psa_ready_queue_->empty())
{
bool increase_time = true;
// Job FCFS
if(!back_queue_->empty() && psa_ready_queue_->size() < 2)
{
JCBptr jcb = back_queue_->top();
if (jcb->submit_time <= cur_time)
{
back_queue_->pop();

// Process PSA
if (!psa_ready_queue_->empty())
{
PCBptr pcb = psa_ready_queue_->top();
JCBptr jcb = pcb->jcb;

if (jcb->already_run_time >= jcb->required_running_time)
{
jcb->job_status = Finish;
psa_ready_queue_->pop();
//std::cout << "[LOG]" << jcb->job_name << " Finish At " << cur_time << std::endl;

jcb->finish_time = cur_time;
Util::printJobData(*jcb, true);
}
else
{
jcb->job_status = Wait;
pcb->status = Ready;
//std::cout << "[LOG]" << jcb->job_name << " Ready At " << cur_time << std::endl;
}
}

psa_ready_queue_->push(jcb->pcb);

PCBptr pcb = psa_ready_queue_->top();
JCBptr jcb = pcb->jcb;
jcb->job_status = Run;
pcb->status = Running;

//jcb->start_time = (jcb->start_time == -1) ? cur_time : jcb->start_time;
//std::cout << "[LOG]" << jcb->job_name << " Begin Running At " << cur_time << std::endl;

increase_time = false;
}
}
else if (!psa_ready_queue_->empty())
{
PCBptr pcb = psa_ready_queue_->top();
JCBptr jcb = pcb->jcb;

if (jcb->already_run_time >= jcb->required_running_time)
{
jcb->job_status = Finish;
psa_ready_queue_->pop();
//std::cout << "[LOG]" << jcb->job_name << " Finish At " << cur_time << std::endl;
jcb->finish_time = cur_time;
increase_time = false;

JCBptr jtop = psa_ready_queue_->top()->jcb;
//jtop->start_time = (jtop->start_time == -1) ? cur_time : jtop->start_time;
Util::printJobData(*jcb, true);
}
}

if (increase_time)
{
if (!psa_ready_queue_->empty())
{
PCBptr pcb = psa_ready_queue_->top();
pcb->jcb->already_run_time++;
}
cur_time++;
}
}
std::cout << "[INFO] all jobs finished." << std::endl;
std::cout << "[LOG] average turnaround time " << (average_turnaround_time / job_num_)
<< " average power turnaround time " << (average_power_turnaround_time / job_num_) << std::endl;
}

private:
int job_num_;
std::priority_queue<JCBptr, std::vector<JCBptr>, PriorityCmpForBack>* back_queue_;
std::priority_queue<PCBptr, std::vector<PCBptr>, PriorityCmpForPCB>* psa_ready_queue_;
};

/*
int main()
{
SimpleBatchProcessingSystemJobScheduling<FCFSSchedulingAlgorithm> js(4);
js.getCurrentReadyQueue();

// pause to see result
getchar();
return 0;
}
*/

六、运行结果
6.1 单道批处理（FCFS）

6.2 单道批处理（SJF）

6.3 单道批处理（HRRN）

6.4 多道批处理（FCFS + PSA）

七、结尾
如果本文描述的内容或使用的代码存在任何问题，请及时联系我或在本篇文章的下面进行评论，我会本着对每一位学技术同学的负责态度立即修改。在后续还会有三篇计算机操作系统的算法 C++ 复现博文，如果感兴趣可以关注我。
————————————————
版权声明：本文为CSDN博主「杨小帆_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40697071/article/details/106698130

zan