From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001 From: Sven Eisenhauer Date: Fri, 10 Nov 2023 15:11:48 +0100 Subject: add new repo --- .../Praktikum1/Aufgabe3/src/DMSScheduler.cpp | 57 ++++++++ .../Praktikum1/Aufgabe3/src/DMSScheduler.h | 37 +++++ .../Praktikum1/Aufgabe3/src/EDFScheduler.cpp | 75 ++++++++++ .../Praktikum1/Aufgabe3/src/EDFScheduler.h | 40 ++++++ .../Praktikum1/Aufgabe3/src/Global.h | 13 ++ .../Praktikum1/Aufgabe3/src/RMSScheduler.cpp | 64 +++++++++ .../Praktikum1/Aufgabe3/src/RMSScheduler.h | 40 ++++++ .../Aufgabe3/src/ResponseTimeAnalysis.cpp | 155 +++++++++++++++++++++ .../Praktikum1/Aufgabe3/src/ResponseTimeAnalysis.h | 30 ++++ .../Praktikum1/Aufgabe3/src/Task.cpp | 81 +++++++++++ .../Praktikum1/Aufgabe3/src/Task.h | 117 ++++++++++++++++ .../Praktikum1/Aufgabe3/src/main.cpp | 99 +++++++++++++ 12 files changed, 808 insertions(+) create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.cpp create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.h create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.cpp create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.h create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Global.h create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.cpp create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.h create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/ResponseTimeAnalysis.cpp create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/ResponseTimeAnalysis.h create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.cpp create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.h create mode 100644 Master/Real-Time Systems/Praktikum1/Aufgabe3/src/main.cpp (limited to 'Master/Real-Time Systems/Praktikum1/Aufgabe3/src') diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.cpp b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.cpp new file mode 100644 index 0000000..7c40037 --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.cpp @@ -0,0 +1,57 @@ +/* + * DMSScheduler.cpp + * + * Created on: 02.11.2010 + * Author: sven + */ +#ifndef GLOBAL_H_ + #include "Global.h" +#endif + +#include "DMSScheduler.h" +#include + +DMSScheduler::DMSScheduler() { + // TODO Auto-generated constructor stub + +} + +DMSScheduler::~DMSScheduler() { + // TODO Auto-generated destructor stub +} +void DMSScheduler::run(task_set& tasks,int ci) +{ + cout << "D M S" << endl; + for(unsigned int task_count = 0; task_count < tasks.size(); task_count++) + { + m_queue.push(&tasks[task_count]); + } + while (!m_queue.empty()) { + Task* t = m_queue.top(); + t->dump(); + m_queue.pop(); + } + for(int step= 0; step < ci; step++) + { + cout << (step + 1) << " "; + for(unsigned int task_count = 0; task_count < tasks.size(); task_count++) + { + m_queue.push(&tasks[task_count]); + } + bool scheduledAtask = false; + while (!m_queue.empty()) { + Task* t = m_queue.top(); + if(!scheduledAtask && (t->getActC() > 0) ) { + t->execute(); + scheduledAtask = true; + } else { + t->requeue(); + } + m_queue.pop(); + } + if (!scheduledAtask) { + cout << "no task needs to run"; + } + cout << endl; + } +} diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.h b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.h new file mode 100644 index 0000000..95d73a7 --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/DMSScheduler.h @@ -0,0 +1,37 @@ +/* + * DMSScheduler.h + * + * Created on: 02.11.2010 + * Author: sven + */ + +#ifndef DMSSCHEDULER_H_ +#define DMSSCHEDULER_H_ +#ifndef TASK_H_ + #include "Task.h" +#endif + +#include + +class DMSComparator; + +typedef priority_queue,DMSComparator> dms_queue; + +class DMSComparator +{ +public: + bool operator()(Task*& a, Task*& b) const + { + return ( b->getOrigD() < a->getOrigD() ); + } +}; +class DMSScheduler { +public: + DMSScheduler(); + virtual ~DMSScheduler(); + void run(task_set&,int); +private: + dms_queue m_queue; +}; + +#endif /* DMSSCHEDULER_H_ */ diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.cpp b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.cpp new file mode 100644 index 0000000..2f3a5c2 --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.cpp @@ -0,0 +1,75 @@ +/* + * EDFScheduler.cpp + * + * Created on: 07.11.2010 + * Author: sven + */ + +#include "EDFScheduler.h" +#include +EDFScheduler::EDFScheduler() { + // TODO Auto-generated constructor stub + +} + +EDFScheduler::~EDFScheduler() { + // TODO Auto-generated destructor stub +} +void EDFScheduler::run(task_set& tasks,int ci) +{ + cout << "EDF" << endl; + if(!test(tasks)) { + cout << "Taskset not schedulable!" << endl; + return; + } + for(unsigned int task_count = 0; task_count < tasks.size(); task_count++) + { + m_queue.push(&tasks[task_count]); + } + while (!m_queue.empty()) { + Task* t = m_queue.top(); + t->dump(); + m_queue.pop(); + } + for(int step= 0; step < ci; step++) + { + cout << (step + 1) << " "; + edf_queue edfq; + for(unsigned int task_count = 0; task_count < tasks.size(); task_count++) + { + edfq.push(&tasks[task_count]); + } + bool scheduledAtask = false; + while (!edfq.empty()) { + Task* t = edfq.top(); + if(!scheduledAtask && (t->getActC() > 0) ) { + t->execute(); + scheduledAtask = true; + } else { + t->requeue(); + } + edfq.pop(); + } + if (!scheduledAtask) { + cout << "no task needs to run"; + } + cout << endl; + } +} +bool EDFScheduler::test(task_set& taskset) +{ + bool res = false; + unsigned int sum = 0; + for(unsigned int i=0;i(t.getOrigC()) / static_cast(t.getOrigP()); + if(t.getOrigC() > t.getOrigP()) { + return false; + } + } + if( sum <= 1.0) { + res = true; + } + return res; +} diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.h b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.h new file mode 100644 index 0000000..a790a0f --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/EDFScheduler.h @@ -0,0 +1,40 @@ +/* + * EDFScheduler.h + * + * Created on: 07.11.2010 + * Author: sven + */ + +#ifndef EDFSCHEDULER_H_ +#define EDFSCHEDULER_H_ + +#ifndef TASK_H_ + #include "Task.h" +#endif + +#include + +class EDFComparator; + +typedef priority_queue,EDFComparator> edf_queue; + +class EDFComparator +{ +public: + bool operator()(Task*& a, Task*& b) const + { +// return ( b->getActD() < a->getActD() ); + return ( b->getNextDeadline() < a->getNextDeadline() ); + } +}; +class EDFScheduler { +public: + EDFScheduler(); + virtual ~EDFScheduler(); + void run(task_set&,int); + bool test(task_set&); +private: + edf_queue m_queue; +}; + +#endif /* EDFSCHEDULER_H_ */ diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Global.h b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Global.h new file mode 100644 index 0000000..b2a91ef --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Global.h @@ -0,0 +1,13 @@ +/* + * Global.h + * + * Created on: 31.10.2010 + * Author: sven + */ + +#ifndef GLOBAL_H_ +#define GLOBAL_H_ + +using namespace std; + +#endif /* GLOBAL_H_ */ diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.cpp b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.cpp new file mode 100644 index 0000000..df1bcdd --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.cpp @@ -0,0 +1,64 @@ +/* + * RMSScheduler.cpp + * + * Created on: 02.11.2010 + * Author: sven + */ + +#include "RMSScheduler.h" + +#ifndef RESPONSETIMEANALYSIS_H_ + #include "ResponseTimeAnalysis.h" +#endif + +#include + +RMSScheduler::RMSScheduler() { + // TODO Auto-generated constructor stub + +} + +RMSScheduler::~RMSScheduler() { + // TODO Auto-generated destructor stub +} +void RMSScheduler::run(task_set& tasks,int ci) +{ + cout << "R M S" << endl; + for(unsigned int task_count = 0; task_count < tasks.size(); task_count++) + { + m_queue.push(&tasks[task_count]); + } + ResponseTimeAnalysis rta; + if(!rta.analyse(m_queue)) { + cout << "Task set not runnable. RTA failed" << endl; + return; + } + while (!m_queue.empty()) { + Task* t = m_queue.top(); + t->dump(); + m_queue.pop(); + } + for(int step= 0; step < ci; step++) + { + cout << (step + 1) << " "; + for(unsigned int task_count = 0; task_count < tasks.size(); task_count++) + { + m_queue.push(&tasks[task_count]); + } + bool scheduledAtask = false; + while (!m_queue.empty()) { + Task* t = m_queue.top(); + if(!scheduledAtask && (t->getActC() > 0) ) { + t->execute(); + scheduledAtask = true; + } else { + t->requeue(); + } + m_queue.pop(); + } + if (!scheduledAtask) { + cout << "no task needs to run"; + } + cout << endl; + } +} diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.h b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.h new file mode 100644 index 0000000..5d93fba --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/RMSScheduler.h @@ -0,0 +1,40 @@ +/* + * RMSScheduler.h + * + * Created on: 02.11.2010 + * Author: sven + */ + +#ifndef RMSSCHEDULER_H_ +#define RMSSCHEDULER_H_ + +#ifndef TASK_H_ + #include "Task.h" +#endif + +#include + +class RMSComparator; + +typedef priority_queue,RMSComparator> rms_queue; + +class RMSComparator +{ +public: + bool operator()(Task*& a, Task*& b) const + { + return ( b->getOrigP() < a->getOrigP() ); + } +}; + + +class RMSScheduler { +public: + RMSScheduler(); + virtual ~RMSScheduler(); + void run(task_set&,int); +private: + rms_queue m_queue; +}; + +#endif /* RMSSCHEDULER_H_ */ diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/ResponseTimeAnalysis.cpp b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/ResponseTimeAnalysis.cpp new file mode 100644 index 0000000..807b39a --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/ResponseTimeAnalysis.cpp @@ -0,0 +1,155 @@ +/* + * ResponseTimeAnalysis.cpp + * + * Created on: 07.11.2010 + * Author: sven + */ + +#include "ResponseTimeAnalysis.h" +#ifndef GLOBAL_H_ + #include "Global.h" +#endif + +#include +#include +#include + +ResponseTimeAnalysis::ResponseTimeAnalysis() { + // TODO Auto-generated constructor stub + +} + +ResponseTimeAnalysis::~ResponseTimeAnalysis() { + // TODO Auto-generated destructor stub +} +bool ResponseTimeAnalysis::analyse(rms_queue& task_queue) +{ + bool res = true; + unsigned int task_count = 0; + vector task_set(task_queue.size()); + while(!task_queue.empty()) { + Task* t = task_queue.top(); + task_set[task_count++] = t; + task_queue.pop(); + } + unsigned int c = 0; + for(c=0;c higherPriorizedTasks(c); + for(unsigned int j=0;jgetName() << " has " << higherPriorizedTasks.size() << " higher priorized tasks: "; + for(unsigned int j=0;jgetName(); + } + cout << endl; + unsigned int ri = t->getOrigC(); + if (c == 0) { + cout << "Response Time of Task " << t->getName() << " is " << ri << endl; + continue; + } + do { + unsigned int rii = t->getOrigC(); + for(unsigned int j=0;j(ri)/static_cast(h->getOrigP())); + double r = a*h->getOrigC(); +// cout << "(Ri)/Tj*Cj = (" << ri << "/" << h->getOrigP() << ")*"<< h->getOrigC() << " = " << r << endl; + rii += r; + } +// cout << "Ri = " << rii << endl; + if(rii == ri) { + break; + } + ri = rii; + } while (1); + cout << "Response Time of Task " << t->getName() << " is " << ri << endl; + if (ri > static_cast(t->getOrigD()) ) { + cout << "Response time of Task "<< t->getName() << " exceeds D:" << ri << ">" << t->getOrigD() << endl; + res = false; + break; + } + } + return res; +} +void ResponseTimeAnalysis::calcOptimalStaticPriorities(task_set& tasks) +{ + unsigned int N = tasks.size(); + vector prios(N); + for(unsigned int p=0;pgetName() << " with prio " << actPrio << endl; + + // find tasks with higher priority + vector higherPrioTasks; + unsigned int higherPrioTasksCounter = 0; + for(unsigned int taskPrio=actPrio+1;taskPriogetName() << " to tasks with higher prio" <getOrigC(); + if(higherPrioTasksCounter > 0) { + do { + int rii = candidate->getOrigC(); + for(unsigned int k=0;k(ri)/static_cast(t->getOrigP())); + double r = a*t->getOrigC(); + rii += r; + } + if(rii == ri) { + break; + } + ri = rii; + } while(1); + } + // check response time + OK = (ri <= candidate->getOrigD()); + cout << "Response Time of Task " << candidate->getName() << " is " << ri << " with prio " << actPrio << endl; + if(OK) { + cout << "Task "<< candidate->getName() << " runs at prio " << actPrio << endl << endl; + break; + } else { + cout << "Task "<< candidate->getName() << " cannot run at prio " << actPrio << endl; + } + } // inner for loop + if(!OK) { + cout << "Not schedulable! No task to run at prio " << actPrio << endl; + break; + } + }// outer for loop + if(OK) { + cout << "Optimal priorities:" << endl; + for(unsigned int c=0;cgetName() << endl; + } + } + } +} +void ResponseTimeAnalysis::swap(vector& prios,int a,int b) +{ + Task *taskA = prios[a]; + Task *taskB = prios[b]; + cout << "Swapping " << taskA->getName() << " ("<getName() << " (" < +#include + +class ResponseTimeAnalysis { +public: + ResponseTimeAnalysis(); + virtual ~ResponseTimeAnalysis(); + bool analyse(rms_queue&); + void calcOptimalStaticPriorities(task_set&); + void swap(vector&,int,int); +}; + +#endif /* RESPONSETIMEANALYSIS_H_ */ diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.cpp b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.cpp new file mode 100644 index 0000000..0f3edf8 --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.cpp @@ -0,0 +1,81 @@ +/* + * Task.cpp + * + * Created on: 31.10.2010 + * Author: sven + */ + +#include "Task.h" +#include + +Task::Task() { + // TODO Auto-generated constructor stub + +} + +Task::Task(char* name,int c,int p,int d) +:m_Name(name),m_origC(c),m_origP(p),m_origD(d),m_actC(c),m_actD(d) +,m_stepCounter(0),m_absoluteStepCounter(0) +{ +// this->dump(); +} +Task::~Task() { + // TODO Auto-generated destructor stub +} +void Task::dump() const { + cout << "Task: " << m_Name << " " << m_origC << " " + << m_origP << " " << m_origD << endl; +} +void Task::dumpStep() const { + cout << endl << m_Name << " actD " << m_actD << " actC " << m_actC + << " stepcounter " << m_stepCounter; +} +void Task::execute() { +// if (m_actC <= 0) { +// cout << " " << getName() << " execute error: actC <= 0 : " << m_actC << endl; +// } else { +// m_actC--; +// } +// if (m_actD < 0) { +// cout << " " << getName() << " execute error: actD < 0 : " << m_actD; +// } else { +// m_actD--; +// } + m_actC--; + m_actD--; + m_stepCounter++; + m_absoluteStepCounter++; + checkPeriod(); + cout << getName(); +} +void Task::requeue() { +// if (m_actD < 0) { +// cout << " " << getName() << " requeue error: actD < 0 : " << m_actD; +// } else { +// m_actD--; +// } + if(m_actC > 0) { + m_actD--; + } + m_stepCounter++; + m_absoluteStepCounter++; + checkPeriod(); +} +void Task::checkPeriod() { + if(m_stepCounter == m_origP) { + if( (m_actC > 0) && (m_actD > 0) ) { + cout << " deadline miss "; + dumpStep(); + } + m_stepCounter = 0; + m_actC = m_origC; + m_actD = m_origD; + } +} +int Task::getNextDeadline() +{ + double numDeadlines = std::floor(static_cast(m_absoluteStepCounter) / static_cast(m_origD)); + double nextDeadline = m_origD * (numDeadlines+1); + cout << "Next deadline of task " <(nextDeadline); +} diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.h b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.h new file mode 100644 index 0000000..bd8c773 --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/Task.h @@ -0,0 +1,117 @@ +/* + * Task.h + * + * Created on: 31.10.2010 + * Author: sven + */ + +#ifndef TASK_H_ +#define TASK_H_ + +#ifndef GLOBAL_H_ + #include "Global.h" +#endif + +#include +#include +#include + +class Task; + +typedef vector task_set; + +class Task { +public: + Task(); + Task(char*,int,int,int); + virtual ~Task(); + + void dump() const; + void dumpStep() const; + void execute(); + void requeue(); + void checkPeriod(); + + int getStepCounter() const + { + return m_stepCounter; + } + + void setStepCounter(int m_stepCounter) + { + this->m_stepCounter = m_stepCounter; + } + + int getActC() const + { + return m_actC; + } + + int getActD() const + { + return m_actD; + } + + string getName() const + { + return m_Name; + } + + int getOrigC() const + { + return m_origC; + } + + int getOrigD() const + { + return m_origD; + } + + int getOrigP() const + { + return m_origP; + } + + void setActC(int m_actC) + { + this->m_actC = m_actC; + } + + void setActD(int m_actD) + { + this->m_actD = m_actD; + } + + void setName(string m_Name) + { + this->m_Name = m_Name; + } + + void setOrigC(int m_origC) + { + this->m_origC = m_origC; + } + + void setOrigD(int m_origD) + { + this->m_origD = m_origD; + } + + void setOrigP(int m_origP) + { + this->m_origP = m_origP; + } + int getNextDeadline(); + +private: + string m_Name; + int m_origC; + int m_origP; + int m_origD; + int m_actC; + int m_actD; + int m_stepCounter; + int m_absoluteStepCounter; +}; + +#endif /* TASK_H_ */ diff --git a/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/main.cpp b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/main.cpp new file mode 100644 index 0000000..c616f9b --- /dev/null +++ b/Master/Real-Time Systems/Praktikum1/Aufgabe3/src/main.cpp @@ -0,0 +1,99 @@ +/* + * main.cpp + * + * Created on: 31.10.2010 + * Author: sven + */ +#ifndef GLOBAL_H_ + #include "Global.h" +#endif +#ifndef TASK_H_ + #include "Task.h" +#endif +#ifndef RMSSCHEDULER_H_ + #include "RMSScheduler.h" +#endif +#ifndef DMSSCHEDULER_H_ + #include "DMSScheduler.h" +#endif +#ifndef EDFSCHEDULER_H_ + #include "EDFScheduler.h" +#endif +#ifndef RESPONSETIMEANALYSIS_H_ + #include "ResponseTimeAnalysis.h" +#endif + +#include +#include +#include +#include + +const char* TASKS_FILE_NAME = "tasks.txt"; + +int lcm(int,int); +int gcd(int,int); +int load_tasks(const char*,task_set&); + +int main(int argc,char* argv[]) +{ + int ci = 1; + task_set tasks; + load_tasks(TASKS_FILE_NAME,tasks); + for(uint i=0;i> name >> c >> p >> d; + if(name[0] != 0) { + Task t(&name[0],c,p,d); + tasks.push_back(t); + } + } + task_file.close(); + return EXIT_SUCCESS; +} +// Least Common Multiple +int lcm(int a, int b) +{ + return (a*b)/gcd(a, b); +} +// Greatest Common Divisor +int gcd(int a, int b) +{ + if(b == 0) + { + return a; + } + if(a == 0) + { + return b; + } + return gcd(b, a%b); +} -- cgit v1.2.3