|
SJF调度算法：
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
为了和FCFS调度算法进行比较，我们仍利用FCFS算法中所使用的实例，并改用SJ(P)F算法重新调度，再进行性能分析。由上图中的(a)和(b)可以看出，采用SJ(P)F算法后，不论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业D，其周转时间由原来的(用FCFS算法时)11降为3；而平均带权周转时间是从5.5降到1.5。这说明SJF调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
SJ(P)F调度算法也存在不容忽视的缺点：
- 该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。
- 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
- 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
参考与：https://blog.csdn.net/houchaoqun_xmu/article/details/55539362
代码
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<queue>
#include<list>
#include<thread>
#include<mutex>
#include<Windows.h>
using namespace std;
#define MAX_TIME 99999
int g_time = 0;
mutex g_mutex_time;
struct process_node
{
int prcess_id; //进程编号
int _start; //进入时间
void(*main_doing)(int args, char *ptr_argv[]);//本进程完成的任务
int begin; //开始时间
int finish; //完成时间
int _function; //需要运行时间
int function; //已经运行的时间
bool complete; //是否完成 true 完成
};
list<process_node*>q_list;//进程队列
void showlist()
{
for (auto ib = q_list.begin(); ib != q_list.end(); ib++)
{
cout << (*ib)->prcess_id << " ";
}
cout << "\n";
}
void main_doing(int args, char *ptr_argv[])
{
cout << args << "这是一个运行的实例" << endl;
Sleep(200);
}
void Come_Init_Prcess(void(*main_doing)(int args, char *ptr_argv[]), int _function) //模拟进程到来并且初始化
{
static int id = 0;
process_node *p = new process_node;
p->prcess_id = ++id;
p->_start = g_time;
p->main_doing = main_doing;
p->_function = _function;
p->begin = MAX_TIME;
p->finish = MAX_TIME;
p->function = 0;
p->complete = false;
q_list.push_back(p);
}
void Time_End_Work(process_node & current_process)//时间片结束的前的工作
{
if (current_process.function >= current_process._function)//判断是否完成
{
current_process.complete = true;
current_process.finish = g_time;
cout << "进程" << current_process.prcess_id << "完成任务" << endl;
q_list.remove(¤t_process);
}
}
void One_End_Process(process_node & current_process)
{
int current_point = g_time;
cout << "当前时间" << current_point << endl;
while (current_point + current_process._function >= g_time)
{
current_process.main_doing(current_process.prcess_id, NULL);
}
current_process.function += g_time - current_point;
Time_End_Work(current_process);
}
process_node& Obtain_Obtain()//获取优先者
{
int temp = 9999;
process_node *p_temp = nullptr;
while (q_list.size() == 0);
for (auto ib = q_list.begin(); ib != q_list.end(); ib++)
{
if ((*ib)->_function - (*ib)->function < temp)
{
temp = (*ib)->_function - (*ib)->function;
p_temp = (*ib);
}
}
cout << "优先的是程序" << p_temp->prcess_id << endl;
p_temp->begin = g_time;
return *p_temp;
}
void Run_begin()
{
while (1)
{
process_node &p_temp = Obtain_Obtain();
showlist();
One_End_Process(p_temp);
}
}
//时间实例到达
void pthread_model()
{
time_t ts;
srand((unsigned int)time(&ts));
while (1)
{
int x_temp = 0;
lock_guard<mutex>ldg(g_mutex_time);
cout <<"时间:["<<g_time<<"]" << endl;
if (g_time%2==0)
{
while (1)
{
x_temp = rand() % 5;
if (x_temp > 0)
{
break;
}
}
Come_Init_Prcess(main_doing, x_temp);
cout << "实例到达" << endl;
}
Sleep(1000);
g_time++;
}
}
int main()
{
thread th_model(pthread_model);
thread th_main(Run_begin);
th_model.join();
th_main.join();
cin.get();
}
| 
转播
