Short work priority SJF

SJF Scheduling algorithm ：

       Short assignments ( process ) Priority scheduling algorithm SJ(P)F, It refers to the algorithm of priority scheduling for short jobs or short processes . They can be used for job scheduling and process scheduling respectively . Short job preferred (SJF) The scheduling algorithm is to select one or several jobs with the shortest estimated running time from the backup queue , Put them in memory to run . The short process takes precedence (SPF) The scheduling algorithm is to select a process from the ready queue with the shortest estimated running time , Assign the processor to it , Make it execute immediately and continue until it is finished , Or when an event occurs and is blocked, it will be rescheduled when the processor is abandoned .
      In order to and FCFS Scheduling algorithms are compared , We still use FCFS Examples used in the algorithm , And to switch to SJ(P)F Algorithm rescheduling , Then conduct performance analysis . From... In the above figure (a) and (b) It can be seen that , use SJ(P)F After algorithm , Whether it is the average turnover time or the average weighted turnover time , There are obvious improvements , Especially for short assignments D, The turnover time is changed from ( use FCFS When the algorithm )11 Reduced to 3; The average weighted turnaround time is from 5.5 drop to 1.5. This explanation SJF Scheduling algorithm can effectively reduce the average waiting time of jobs , Improve system throughput .
  SJ(P)F Scheduling algorithm also has shortcomings that cannot be ignored ：

1.     This algorithm is disadvantageous to long jobs , Such as homework C The turnaround time is determined by 10 to 16, Its weighted turnover time is from 2 to 3.1. More serious , If there is a long homework ( process ) Enter the backup queue of the system ( Ready queue ), Because the scheduler always prioritizes those ( Even the late comers ) Short assignments ( process ), It will lead to long work ( process ) Not scheduled for a long time .
2.     The algorithm does not consider the urgency of the job , As a result, urgent operations cannot be guaranteed ( process ) It will be dealt with in time .
3.     Because of the homework ( process ) The length of is only based on the estimated execution time provided by the user , And users may intentionally or unintentionally shorten the estimated running time of their jobs , As a result, the algorithm may not be able to achieve short job priority scheduling .

Reference and ：https://blog.csdn.net/houchaoqun_xmu/article/details/55539362
Code

#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;  // Process number 
	int _start;  // Entry time 
	void(*main_doing)(int args, char *ptr_argv[]);// Tasks completed by this process 
	int begin;   // Starting time 
	int finish;  // Completion time 
	int _function; // Run time required 
	int function; // Time that has been running 
	bool complete;	 // Whether it is completed or not    true  complete 
};

list<process_node*>q_list;// Process queue 


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 << " This is a running instance " << endl;
	Sleep(200);
}

void Come_Init_Prcess(void(*main_doing)(int args, char *ptr_argv[]),  int _function) // The simulation process arrives and initializes 
{
	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)// Work before the end of the time slice 
{
	if (current_process.function >= current_process._function)// Judge whether it is finished 
	{
		current_process.complete = true;
		current_process.finish = g_time;
		cout << " process " << current_process.prcess_id << " To complete the task " << endl;
		q_list.remove(&current_process);
	}
}
void One_End_Process(process_node & current_process)
{
	int current_point = g_time;
	cout << " current time " << 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()// Get priority 
{
	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 << " The priority is the program " << 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);
	}
}
// Time instances arrive 
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 <<" Time :["<<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 << " Instance arrives " << 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();

}