Select Git revision
Forked from
Per Lindgren / klee_tutorial
Source project has a limited visibility.
main.rs 7.60 KiB
mod common;
use common::*;
use std::collections::HashSet;
fn main() {
let t1 = Task {
id: "T1".to_string(),
prio: 1,
deadline: 100,
inter_arrival: 100,
trace: Trace {
id: "T1".to_string(),
start: 0,
end: 10,
inner: vec![],
},
};
let t2 = Task {
id: "T2".to_string(),
prio: 2,
deadline: 200,
inter_arrival: 200,
trace: Trace {
id: "T2".to_string(),
start: 0,
end: 30,
inner: vec![
Trace {
id: "R1".to_string(),
start: 10,
end: 20,
inner: vec![Trace {
id: "R2".to_string(),
start: 12,
end: 16,
inner: vec![],
}],
},
Trace {
id: "R1".to_string(),
start: 22,
end: 28,
inner: vec![],
},
],
},
};
let t3 = Task {
id: "T3".to_string(),
prio: 3,
deadline: 50,
inter_arrival: 50,
trace: Trace {
id: "T3".to_string(),
start: 0,
end: 30,
inner: vec![Trace {
id: "R2".to_string(),
start: 10,
end: 20,
inner: vec![],
}],
},
};
// builds a vector of tasks t1, t2, t3
let tasks: Tasks = vec![t1, t2, t3];
// println!("tasks {:?}", &tasks);
println!("tot_util {}", load_factor(&tasks));
let (ip, tr) = pre_analysis(&tasks);
println!("ip: {:?}", ip);
println!("tr: {:?}", tr);
print_analysis(&tasks, &ip, &tr);
}
// Prints out vector with [task id, response time, wcet time, blocking time, preemption time]
fn print_analysis(tasks: &Tasks, ip: &IdPrio, tr: &TaskResources) {
for t in tasks {
let b = blocking(t, &tasks, &ip, &tr);
// let p = preemptions(t, &tasks);
let p = recurrence_preemption(t, &tasks, &ip, &tr, true).unwrap();
let r = response_time(t, &tasks, &ip, &tr, true);
let c = wcet(t);
let tasks_analysis = vec![t.id.to_string(), r.to_string(), c.to_string(), b.to_string(), p.to_string()];
println!("{:?}", tasks_analysis)
}
}
fn response_time(task: &Task, tasks: &Tasks, ip: &IdPrio, tr: &TaskResources, exact_solution: bool) -> u32 {
let b = blocking(task, &tasks, &ip, &tr);
let c = wcet(task);
// let p = preemptions(task, &tasks);
let p = recurrence_preemption(task, &tasks, &ip, &tr, exact_solution).unwrap();
return b + c + p;
}
fn wcet(task: &Task) -> u32 {
let c = task.trace.end.wrapping_sub(task.trace.start);
return c
}
fn load_factor(tasks: &Tasks) -> f32{
let mut l_tot: f32 = 0.0;
for t in tasks {
let c = wcet(t);
let a = t.inter_arrival;
l_tot = l_tot + (c as f32)/(a as f32);
}
return l_tot;
}
fn recurrence_preemption(task: &Task, tasks: &Tasks, ip: &IdPrio, tr: &TaskResources, exact_solution: bool) -> Result<u32, String> {
if !exact_solution {
return Ok(preemptions(task, &tasks, 0, exact_solution));
}
let sum = wcet(task) + blocking(task, &tasks, &ip, &tr);
let mut current_busy_period: u32 = sum + preemptions(task, &tasks, sum, exact_solution);
loop {
let busy_period: u32 = current_busy_period + preemptions(task, &tasks, current_busy_period, exact_solution);
if current_busy_period == busy_period {
return Ok(busy_period);
}
if current_busy_period > task.deadline {
return Err("Deadline miss!".to_string());
}
current_busy_period = busy_period;
}
}
fn preemptions(task: &Task, tasks: &Tasks, busy_period: u32, exact_solution: bool) -> u32 {
let mut p_time = 0;
let mut busy_period = busy_period;
if !exact_solution {
busy_period = task.deadline;
} for t in tasks {
if t.id == task.id {
continue;
}
if t.prio >= task.prio {
let inter_arrival = t.inter_arrival;
// println!("bp{} ia{}", busy_period, inter_arrival);
p_time = p_time + wcet(t)*(((busy_period as f32) / (inter_arrival as f32)).ceil() as u32);
}
}
println!("{}", p_time);
return p_time;
}
fn blocking(task: &Task, tasks: &Tasks, ip: &IdPrio, tr: &TaskResources) -> u32 {
// Checks if the Task is claming a resource
if !tr.contains_key(&task.id) {
// println!("0");
return 0;
}
// Find lower prio tasks
let mut lower_prio_tasks = HashSet::new();
for t in tasks {
if t.prio < task.prio {
lower_prio_tasks.insert(t.id.to_string());
}
}
// Do these task hold a resource, if not delete from list
for t in tasks {
if !lower_prio_tasks.contains(&t.id) {
continue;
}
if !tr.contains_key(&t.id) {
lower_prio_tasks.remove(&t.id);
}
}
// println!("{:?}", lower_prio_tasks);
if lower_prio_tasks.len() == 0 {
// println!("0");
return 0;
}
/* Finding longest blocking */
let resources = &tr[&task.id];
// Checking every resource it holds
let mut max_block = 0;
let mut current_block = 0;
// Iterate through current task resources
for r1 in resources {
// println!("Resource 1: {}, Resources 1 {:?}", r1, resources);
// Iterate through lower prio tasks
for t_id in &lower_prio_tasks {
let mut lower_prio_task_resources = &tr[t_id];
// Iterate through lower prio task resources
for r2 in lower_prio_task_resources {
// println!("Resource 2: {}, Resources 2 {:?}", r2, lower_prio_task_resources);
// When current task use the same resource as a task
if r1 == r2 {
// Takes forward the blocking task
for t in tasks {
if &t.id == t_id {
// Iterate through first layer
for inner in &t.trace.inner {
if &inner.id == r2 {
current_block = inner.end.wrapping_sub(inner.start);
if max_block < current_block {
max_block = current_block;
}
// println!("1: start:{}, end:{}", inner.start, inner.end);
// println!("For id {} and resource 2 {}", t_id, r2)
} // Iterate through second layer
for inner2 in &inner.inner {
if &inner2.id == r2 {
current_block = inner2.end.wrapping_sub(inner2.start);
if max_block < current_block {
max_block = current_block;
}
// println!("2: start:{}, end:{}", inner2.start, inner2.end);
// println!("For id {} and resource 2 {}", t_id, r2)
}
}
}
}
}
}
}
}
}
// println!("{}", max_block);
return max_block;
}