Earliest deadline first (EDF)

The earliest deadline takes precedence （EDF） Scheduling dynamically assigns priorities according to deadlines . The earlier the deadline , The higher the priority ; The later the deadline , The lower the priority .

according to EDF Strategy , When a process is runnable , It should publish the deadline requirements to the system . Priorities may need to be adjusted , To reflect the deadline of the new runnable process . Be careful Monotone rate scheduling And EDF Scheduling differences , The priority of the former is fixed .

chart 1 Monotonic rate scheduling that misses deadlines

To illustrate EDF Dispatch , We schedule again as shown in the figure 1 The process shown in , These processes are adjusted by monotonic rate The degree cannot meet the deadline . remember ： process P1 Yes ρ1 = 50 and t1 = 25, process P2 Yes ρ2 = 80 and t2 = 35, Of these processes EDF The scheduling is shown in the figure 2 Shown .

chart 2 Earliest deadline priority scheduling

process P1 The deadline for is at the earliest , So its initial priority is higher than that of the process P2 You have to be tall . When P1 Of CPU At the end of execution , process P2 Began to run . however , Although monotonic rate scheduling allows P1 In time 50（ At the beginning of the next cycle ） preemption P2, however EDF Scheduling allows processes P2 Continue operation . process P2 The priority ratio P1 Higher , Because its next deadline （ Time 80） Than P1 Of （ Time 100） Early . therefore ,P1 and P2 Can meet their first deadline .

process P1 In time 60 Start running again , In time 85 Finish the second one CPU perform , Also meet the second deadline （ In time 100）. At this time , process P2 Began to run , Just in time 100 By P1 preemption .P2 The reason why P1 Preemption is because P1 Deadline for （ Time 150） than P2 Of （160） Earlier . In time 125,P1 complete CPU perform ,P2 Resume execution ; In time 145,P2 complete , And meet its deadline . then , The system is idle until time 150; In time 150 process P1 Start being dispatched again .

Unlike monotonic rate scheduling ,EDF Scheduling does not require that the process should be periodic , Nor does it require a process CPU The length of execution is fixed . The only requirement is , When a process becomes runnable , Its deadline should be announced .

EDF The attraction of scheduling is , It is the best in theory . In theory , It can schedule processes , Make every process meet the deadline and CPU Utilization will be 100%. However , In practice, , Due to the cost of context switching and interrupt processing of the process , At this level CPU Utilization is impossible .

Reference resources ：http://c.biancheng.net/view/1254.html

This test case is ： Mission A And tasks B The cycle times of are 20s and 50s, The processing time of each cycle is 10s and 25s.

Code

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<queue>
#include<list>
#include<thread>
#include<mutex>
#include<Windows.h>
using namespace std;
#define A_RUN_TIME 10
#define B_RUN_TIME 25
#define A_STOP_TIME 20
#define B_STOP_TIME 50
#define time_film  10  // Time slice 
#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 
	int _end;    // By the time 
	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(500);
}

void Come_Init_Prcess(void(*main_doing)(int args, char *ptr_argv[]),int end ,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->_end = end;
	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&&current_process._end >= g_time)// 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;
		cout << "*********** Entry time ："<<current_process._start << endl;
		cout << "*********** By the time ：" <<current_process._end << endl;
		cout << "*********** Starting time ：" << current_process.begin << endl;
		cout << "*********** Completion time ：" << current_process.finish << endl;
		q_list.remove(&current_process);
	}
	else
	{
		q_list.pop_front();
		q_list.push_back(&current_process);
	}
}

void Ahead_Of_Time(process_node & current_process)// The process is completed ahead of schedule   Make time for the movie 
{
	int current_point = g_time;
	cout << " current time " << current_point << endl;
	while(current_point+current_process._function-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);
	showlist();
}
void One_Of_Time(process_node & current_process)
{
	int current_point = g_time;
	cout << " current time " << current_point << endl;
	while (current_point + time_film >= g_time + 1)
	{
		current_process.main_doing(current_process.prcess_id, NULL);
		if (g_time!=current_point&&g_time%time_film==0)
		{
			break;
		}
	}
	current_process.function += g_time-current_point;
	Time_End_Work(current_process);
}
void Time_File_Doing(process_node & current_process) // Time slice completed work 
{
	//cout << "+++++++++++++++++" << current_process._function - current_process.function<<"+++++++++++++++++++++++" << endl;
 	if (current_process._function - current_process.function<time_film)// Less than a time slice processing 
	{
		Ahead_Of_Time(current_process);
	}
	else
	{
		One_Of_Time(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;
	if (p_temp->begin== MAX_TIME)
	{
		p_temp->begin = g_time;
	}
	return *p_temp;
}



void Run_begin()
{
	
	while (1)
	{
		process_node &p_temp=Obtain_Obtain();
		showlist();
		Time_File_Doing(p_temp);
	}
}


// Time instances arrive 
void pthread_model()
{
	while(1)
	{
		lock_guard<mutex>ldg(g_mutex_time);
		cout << g_time << endl;
		if (g_time % 20 == 0)
		{
			Come_Init_Prcess(main_doing, A_STOP_TIME+g_time, A_RUN_TIME);
			cout << "A Instance arrives " << endl;
		}
		if (g_time % 50 == 0)
		{
			Come_Init_Prcess(main_doing, B_STOP_TIME + g_time, B_RUN_TIME);
			cout << "B 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();

}

test result