X-Git-Url: http://v3vee.org/palacios/gitweb/gitweb.cgi?a=blobdiff_plain;f=palacios%2Fsrc%2Fextensions%2Fext_sched_edf.c;h=7b7c108d817722f9f849d83aea28ff4f93ed7bbf;hb=2282a040e60b24d3fb7c48bb197c5bff6636df67;hp=6cc7319d038b32276c6a224a0a3fed58aca1d402;hpb=2fff50d3e72abf29655326449ed4dc5cf6e8f429;p=palacios.git diff --git a/palacios/src/extensions/ext_sched_edf.c b/palacios/src/extensions/ext_sched_edf.c index 6cc7319..7b7c108 100644 --- a/palacios/src/extensions/ext_sched_edf.c +++ b/palacios/src/extensions/ext_sched_edf.c @@ -1,15 +1,15 @@ -/* +/* * This file is part of the Palacios Virtual Machine Monitor developed - * by the V3VEE Project with funding from the United States National - * Science Foundation and the Department of Energy. + * by the V3VEE Project with funding from the United States National + * Science Foundation and the Department of Energy. * * The V3VEE Project is a joint project between Northwestern University - * and the University of New Mexico. You can find out more at + * and the University of New Mexico. You can find out more at * http://www.v3vee.org * * Copyright (c) 2013, Oscar Mondragon * Copyright (c) 2013, Patrick G. Bridges - * Copyright (c) 2013, The V3VEE Project + * Copyright (c) 2013, The V3VEE Project * All rights reserved. * * Author: Oscar Mondragon @@ -34,54 +34,66 @@ #define PrintDebug(fmt, args...) #endif -/* Overview +/* Overview * * EDF Scheduling * * The EDF scheduler uses a dynamic calculated priority as scheduling criteria to choose - * what thread will be scheduled.That priority is calculated according with the relative + * what thread will be scheduled.That priority is calculated according with the relative * deadline of the threads that are ready to run in the runqueue. This runqueue is a per-logical - * core data structure used to keep the runnable virtual cores (threads) allocated to that - * logical core.The threads with less time before its deadline will receive better priorities. - * The runqueue is sorted each time that a vCPU becomes runnable. At that time the vCPU is - * enqueue and a new scheduling decision is taken. Each time a vCPU is scheduled, the parameter - * slice used time is set to zero and the current deadline is calculated using its period. Once - * the vCPU uses the logical core for slice seconds, that vCPU sleeps until its next scheduling - * period (when is re-inserted in the runqueue) and yields the CPU to allow the scheduling - * of the vCPU with best priority in the runqueue. + * core data structure used to keep the runnable virtual cores (threads) allocated to that + * logical core.The threads with less time before its deadline will receive better priorities. + * The runqueue is sorted each time that a vCPU becomes runnable or when its period is over. + * At that time the vCPU is enqueue. A new scheduling decision is taken is time that an interruption + * is received. At that time if the earliest deadline core is different that the current core, + * the current core goes to sleep and the earliest deadline core is wake up. Each time a vCPU is scheduled, + * the parameter "used_time" is set to zero and the current deadline is calculated using its period. + * One vCPU uses at least slice seconds of CPU.Some extra time can be allocated to that virtual core after + * all the other virtual cores consumes their slices. */ // Default configuration values for the EDF Scheduler -// time parameters in microseconds +// time parameters in microseconds #define MAX_PERIOD 1000000000 #define MIN_PERIOD 50000 #define MAX_SLICE 1000000000 -#define MIN_SLICE 10000 -#define CPU_PERCENT 100 +#define MIN_SLICE 50000 +#define CPU_PERCENT 80 +#define DEADLINE_INTERVAL 30000000 // Period in which the missed deadline ratio is checked + typedef uint64_t time_us; -/* - * Per-core EDF Scheduling information +/* + * Per-core EDF Scheduling information */ struct vm_core_edf_sched { - struct guest_info *info; // Core struct - struct rb_node node; // red-black tree node - time_us period; // Amount of time (us) during which the core may received a CPU allocation - time_us slice; // Minimum amount of time (us) received for the core during each period - time_us current_deadline; // Time (us) at which current core period ends - time_us used_time; // Amount of time (us) of the slice used whiting the current period - time_us last_wakeup_time; // Time at which the last wakeup started for this core - time_us remaining_time; // Remaining time (us) before current core period ends (before current deadline) - bool extra_time; // Specifies if the virtual core is eligible to receive extra CPU time - int miss_deadline; // Number of times the core has missed its deadline - time_us total_time; // Total scheduled time for this core. For now used for debugging purposes - int slice_overuse; // Statistical purposes - time_us extra_time_given; // Statistical + struct guest_info *info; // Core data struct + struct rb_node node; // red-black tree node + time_us period; // Amount of time (us) during which the virtual core may received a CPU allocation + time_us slice; // Minimum amount of time (us) received for the virtual core during each period + time_us current_deadline; // Time (us) at which current virtual core period ends + time_us used_time; // Amount of time (us) used whiting the current period + time_us last_wakeup_time; // Time at which the last wakeup started for this virtual core + time_us remaining_time; // Remaining time (us) to reach the expected time allocated to the virtual core + bool extra_time; // Specifies if the virtual core is eligible to receive extra CPU time (For now it is true always) + uint64_t deadline; // Total number of deadlines + int deadline_percentage; // Percentage of total missed deadlines + uint64_t miss_deadline; // Number of times the core has missed deadlines + uint64_t deadline_interval; // Total number of deadlines in the latest interval + int deadline_percentage_interval; // Percentage of missed deadlines in the latest interval + uint64_t miss_deadline_interval; // Number of times the core has missed deadlines in the last interval + time_us print_deadline_interval; // Last time missed deadline ratio was printed + time_us total_time; // Total scheduled time for this virtual core. + int slice_overuse; // Number of times a core consumes extra time + time_us extra_time_given; // Total extra time given to a virtual core + time_us start_time; // Time at which this virtual core start to be scheduled + time_us expected_time; // Minimum CPU time expected to be allocated to this virtual core + }; -/* +/* * Scheduler configuration */ @@ -90,41 +102,67 @@ struct vm_edf_sched_config { time_us max_slice; // Maximum allowed slice time_us min_period; // Minimum allowed period time_us max_period; // Maximum allowed period - int cpu_percent; // Percentange of CPU utilization for the scheduler in each physical CPU (100 or less) - + int cpu_percent; // Percentange of CPU utilization for the scheduler in each physical CPU (100 or less) + }; -/* - * Run queue structure. Per-logical core data structure used to keep the runnable virtual cores (threads) allocated to that logical core - * Contains a pointer to the red black tree, the structure of configuration options and other info +/* + * Run queue structure. Per-logical core data structure used to keep the runnable virtual cores (threads) allocated to that logical core + * Contains a pointer to the red black tree, the data structure of configuration options, and other info */ struct vm_edf_rq{ - - //int cpu_id; // Physical CPU id - int cpu_u; // CPU utilization (must be less or equal to the cpu_percent in vm_edf_sched_config) - struct rb_root vCPUs_tree; // Red-Black Tree + + int cpu_u; // CPU utilization (must be less or equal to the cpu_percent in vm_edf_sched_config) + struct rb_root vCPUs_tree; // Red-Black Tree struct vm_edf_sched_config edf_config; // Scheduling configuration structure - int nr_vCPU; // Number of cores in the runqueue - struct vm_core_edf_sched *curr_vCPU; // Current running CPU - struct rb_node *rb_leftmost; // vCPU with the earliest deadline (leftmost in the tree) - time_us last_sched_time; // statistical purposes + int nr_vCPU; // Number of cores in the runqueue + struct vm_core_edf_sched *curr_vCPU; // Current running CPU + time_us last_sched_time; // Last time a virtual core in this runqueue was scheduled + time_us check_deadline_time; // Last time in which the deadlines were recalculated + time_us smallest_period; // Smallest period of the virtual cores in the runqueue, used to control the period of deadlines recalculation + time_us print_time; // Last time of debugging print + time_us start_time; // Time at which first core started running in this runqueue + int sched_low; // Incremented when the time between interruptions is large + bool yielded; // CPU yielded to palacios (No core running) }; -/* - * Basic functions for scheduling +/* + * Basic functions for scheduling */ int v3_init_edf_scheduling(); +/* + * Debugging Function + */ +static void +print_parameters(time_us host_time, struct vm_edf_rq * runqueue, struct vm_core_edf_sched * core){ + + time_us elapsed_time = 0; + if(runqueue->start_time != 0) + elapsed_time = host_time - runqueue->start_time; + + PrintDebug(core->info->vm_info, core->info,"Test: %llu %llu %d %d %llu %llu %llu %d\n", + host_time, + elapsed_time, + core->info->vcpu_id, + core->info->pcpu_id, + core->total_time, + core->expected_time, + core->miss_deadline, + core->deadline_percentage); + + runqueue->print_time = host_time; +} /* * init_edf_config: Initialize scheduler configuration */ -static void +static void init_edf_config(struct vm_edf_sched_config *edf_config){ edf_config->min_slice = MIN_SLICE; @@ -139,7 +177,7 @@ init_edf_config(struct vm_edf_sched_config *edf_config){ * priv_data_init: Initialize the run queue */ -int +int priv_data_init(struct v3_vm_info *vm){ PrintDebug(vm, VCORE_NONE,"EDF Sched. Initializing EDF Scheduling \n"); @@ -152,7 +190,7 @@ priv_data_init(struct v3_vm_info *vm){ } int lcore = 0; - + PrintDebug(vm, VCORE_NONE,"EDF Sched. priv_data_init. Available cores %d\n", vm->avail_cores); for(lcore = 0; lcore < vm->avail_cores ; lcore++){ @@ -161,109 +199,85 @@ priv_data_init(struct v3_vm_info *vm){ struct vm_edf_rq * edf_rq_list = (struct vm_edf_rq *)vm->sched_priv_data; struct vm_edf_rq * edf_rq = &edf_rq_list[lcore]; - + edf_rq->vCPUs_tree = RB_ROOT; edf_rq->cpu_u=0; edf_rq->nr_vCPU=0; edf_rq->curr_vCPU=NULL; - edf_rq->rb_leftmost=NULL; edf_rq->last_sched_time=0; + edf_rq->check_deadline_time=0; + edf_rq->sched_low=0; + edf_rq->smallest_period=0; + edf_rq->start_time = 0; + edf_rq->yielded=false; init_edf_config(&edf_rq->edf_config); } - + return 0; - + } /* - * is_admissible_core: Decides if a core is admited to the red black tree according with + * is_admissible_core: Decides if a core is admited to the red black tree according with * the admisibility formula. */ -static bool +static bool is_admissible_core(struct vm_core_edf_sched * new_sched_core, struct vm_edf_rq *runqueue){ - struct v3_vm_info * vm = new_sched_core->info->vm_info; - - struct v3_time *vm_ts = &(vm->time_state); - int tdf = vm_ts->td_denom; - int curr_utilization = runqueue->cpu_u; - int new_utilization = curr_utilization + ((100/tdf) * new_sched_core->slice / new_sched_core->period); - int cpu_percent = (runqueue->edf_config).cpu_percent; + int new_utilization = curr_utilization + (100 * new_sched_core->slice / new_sched_core->period); + int cpu_percent = (runqueue->edf_config).cpu_percent; if (new_utilization <= cpu_percent) return true; else - return false; + return false; return true; } -/* - * count_cores: Function useful to count the number of cores in a runqueue (Not used for now) - * - */ - - -/*static int count_cores(struct vm_edf_rq *runqueue){ - - struct rb_node *node = v3_rb_first(&runqueue->vCPUs_tree); - struct vm_core_edf_sched *curr_core; - int number_cores = 0; - - while(node){ - - curr_core = container_of(node, struct vm_core_edf_sched, node); - node = v3_rb_next(node); - number_cores++; - } - - return number_cores; -}*/ - - /* - * insert_core_edf: Finds a place in the tree for a newly activated core, adds the node + * insert_core_edf: Finds a place in the tree for a newly activated core, adds the node * and rebalaces the tree */ -static bool +static bool insert_core_edf(struct vm_core_edf_sched *core, struct vm_edf_rq *runqueue){ struct rb_node **new_core = &(runqueue->vCPUs_tree.rb_node); struct rb_node *parent = NULL; struct vm_core_edf_sched *curr_core; - // Find out place in the tree for the new core + // Find out place in the tree for the new core while (*new_core) { - + curr_core = container_of(*new_core, struct vm_core_edf_sched, node); parent = *new_core; - - if (core->current_deadline < curr_core->current_deadline) + + if (core->current_deadline < curr_core->current_deadline) new_core = &((*new_core)->rb_left); else if (core->current_deadline > curr_core->current_deadline) new_core = &((*new_core)->rb_right); else // Is Possible to have same current deadlines in both cores! return false; } - // Add new node and rebalance tree. + // Add new node and rebalance tree. rb_link_node(&core->node, parent, new_core); v3_rb_insert_color(&core->node, &runqueue->vCPUs_tree); - + return true; - } + } /* * get_curr_host_time: Calculates the current host time (microseconds) */ -static uint64_t +static uint64_t get_curr_host_time(struct vm_core_time *core_time){ uint64_t cur_cycle = v3_get_host_time(core_time); @@ -276,12 +290,44 @@ get_curr_host_time(struct vm_core_time *core_time){ /* - * next_start_period: Given the current host time and the period of a given vCPU, + * count_cores: Function useful to count the number of cores in a runqueue (Not used for now) + * + */ + +/* +static int count_cores(struct vm_edf_rq *runqueue){ + + struct rb_node *node = v3_rb_first(&runqueue->vCPUs_tree); + struct vm_core_edf_sched *curr_core; + int number_cores = 0; + + while(node){ + + number_cores++; + curr_core = container_of(node, struct vm_core_edf_sched, node); + time_us host_time = get_curr_host_time(&curr_core->info->time_state); + PrintDebug(VM_NONE,VCORE_NONE,"Count %d. core %d, used time %llu, deadline %llu, host time %llu extra_time %llu\n", + number_cores, + curr_core->info->vcpu_id, + curr_core->used_time, + curr_core->current_deadline, + host_time, + curr_core->extra_time_given); + node = v3_rb_next(node); + + } + + return number_cores; +} +*/ + +/* + * next_start_period: Given the current host time and the period of a given vCPU, * calculates the time in which its next period starts. * */ -static uint64_t +static uint64_t next_start_period(uint64_t curr_time_us, uint64_t period_us){ uint64_t time_period_us = curr_time_us % period_us; @@ -299,7 +345,7 @@ next_start_period(uint64_t curr_time_us, uint64_t period_us){ struct vm_edf_rq * get_runqueue(struct guest_info *info){ struct vm_edf_rq *runqueue_list = (struct vm_edf_rq *) info->vm_info->sched_priv_data; - struct vm_edf_rq *runqueue = &runqueue_list[info->pcpu_id]; + struct vm_edf_rq *runqueue = &runqueue_list[info->pcpu_id]; return runqueue; } @@ -308,28 +354,24 @@ struct vm_edf_rq * get_runqueue(struct guest_info *info){ * wakeup_core: Wakeup a given vCPU thread */ -static void +static void wakeup_core(struct guest_info *info){ struct vm_core_edf_sched *core = info->sched_priv_data; struct vm_edf_rq *runqueue = get_runqueue(info); + time_us host_time = get_curr_host_time(&core->info->time_state); if (!info->core_thread) { PrintError(info->vm_info, info,"ERROR: Tried to wakeup non-existent core thread vCPU_id %d \n",info->vcpu_id); - } + } else { - PrintDebug(info->vm_info, info,"EDF Sched. run_next_core. vcpu_id %d, logical id %d, Total time %llu, Miss_deadlines %d, slice_overuses %d extra_time %llu, thread (%p)\n", - core->info->vcpu_id, - core->info->pcpu_id, - core->total_time, - core->miss_deadline, - core->slice_overuse, - core->extra_time_given, - (struct task_struct *)info->core_thread); - V3_Wakeup(info->core_thread); - core->last_wakeup_time = get_curr_host_time(&core->info->time_state); + if(core->start_time == 0){ + core->start_time = host_time; + print_parameters(host_time, runqueue, core); + } + core->last_wakeup_time = host_time; runqueue->curr_vCPU = core; } @@ -339,79 +381,92 @@ wakeup_core(struct guest_info *info){ /* * activate_core - Moves a core to the red-black tree. - * used time is set to zero and current deadline is calculated + * used time is set to zero and current deadline is calculated */ -static void +static int activate_core(struct vm_core_edf_sched * core, struct vm_edf_rq *runqueue){ - struct v3_vm_info * vm = core->info->vm_info; - struct v3_time *vm_ts = &(vm->time_state); - int tdf = vm_ts->td_denom; - if (is_admissible_core(core, runqueue)){ - + uint64_t curr_time_us = get_curr_host_time(&core->info->time_state); uint64_t curr_deadline = next_start_period(curr_time_us, core->period); - + core->current_deadline = curr_deadline; - core->used_time=0; - core->remaining_time=core->slice; - + core->used_time=0; + bool ins = insert_core_edf(core, runqueue); - /* + /* * If not inserted is possible that there is other core with the same deadline. - * Then, the deadline is modified and try again - */ - while(!ins){ + * Then, the deadline is modified and try again + */ + while(!ins){ core->current_deadline ++; - ins = insert_core_edf(core, runqueue); - } - - runqueue->cpu_u += (100/tdf) * core->slice / core->period; + ins = insert_core_edf(core, runqueue); + } + + runqueue->cpu_u += 100 * core->slice / core->period; runqueue->nr_vCPU ++; - + + if(runqueue->nr_vCPU == 1){ + runqueue->smallest_period = core->period; + } + + else if(core->period < runqueue->smallest_period){ + runqueue->smallest_period = core->period; + } + + /* * If this is the first time to be activated pick first earliest deadline core to wakeup. */ - if(core->last_wakeup_time == 0){ + if(!runqueue->curr_vCPU){ + + struct vm_core_edf_sched *next_core; + // Pick first earliest deadline core - struct vm_core_edf_sched *next_core; - - /* - * Pick first earliest deadline core - */ struct rb_node *node = v3_rb_first(&runqueue->vCPUs_tree); next_core = container_of(node, struct vm_core_edf_sched, node); - - // Wakeup next_core + + PrintDebug(VM_NONE, VCORE_NONE,"EDF Sched. First time activation, core %d, time %llu \n", next_core->info->vcpu_id, curr_time_us); + + // Wakeup next_core (It is not neccessary to wakeup since in this case this is the first core launched by Palacios + // however wakeup_core is called to initialize some needed parameters. + wakeup_core(next_core->info); - - //Sleep old core - - V3_Sleep(0); + next_core->start_time = get_curr_host_time(&next_core->info->time_state); + print_parameters(curr_time_us, runqueue, next_core); + runqueue->start_time = next_core->start_time; + + } - + } - else - PrintError(core->info->vm_info, core->info,"EDF Sched. activate_core. CPU cannot activate the core. It is not admissible"); + else + PrintError(core->info->vm_info, core->info,"EDF Sched. activate_core. CPU cannot activate the core. It is not admissible"); + return 0; + } /* - * edf_sched_core_init: Initializes per core data structure and + * edf_sched_core_init: Initializes per core data structure and * calls activate function. */ -int + +int edf_sched_core_init(struct guest_info * info){ struct vm_edf_rq *runqueue = get_runqueue(info); struct vm_core_edf_sched *core_edf; + struct v3_time *vm_ts = &(info->vm_info->time_state); + uint32_t tdf = vm_ts->td_denom; + uint_t cpu_khz = V3_CPU_KHZ(); - PrintDebug(info->vm_info, info,"EDF Sched. Initializing vcore %d\n", info->vcpu_id); + PrintDebug(info->vm_info, info,"EDF Sched. Initializing vcore %d, tdf %d\n", info->vcpu_id,tdf); core_edf = (struct vm_core_edf_sched *) V3_Malloc(sizeof (struct vm_core_edf_sched)); if (!core_edf) { @@ -419,90 +474,129 @@ edf_sched_core_init(struct guest_info * info){ return -1; } info->sched_priv_data = core_edf; - - // Default configuration if not specified in configuration file - - core_edf->info = info; - core_edf->period = 500000; - core_edf->slice = 50000; + + // Default configuration if not specified in configuration file + + core_edf->info = info; + core_edf->period = MIN_PERIOD; + core_edf->slice = MIN_SLICE; core_edf->used_time = 0; core_edf->last_wakeup_time = 0; - core_edf->remaining_time = core_edf->slice; + core_edf->remaining_time = 0; + core_edf->deadline = 0; core_edf->miss_deadline = 0; core_edf->extra_time = true; core_edf->total_time = 0; core_edf->slice_overuse = 0; core_edf->extra_time_given = 0; + core_edf->expected_time = 0; + core_edf->start_time = 0; + core_edf->deadline_interval = 0; + core_edf->deadline_percentage_interval = 0; + core_edf->miss_deadline_interval = 0; + core_edf->print_deadline_interval = 0; + v3_cfg_tree_t * cfg_tree = core_edf->info->vm_info->cfg_data->cfg; v3_cfg_tree_t * core = v3_cfg_subtree(v3_cfg_subtree(cfg_tree, "cores"), "core"); - + while (core){ char *id = v3_cfg_val(core, "vcpu_id"); char *period = v3_cfg_val(core, "period"); char *slice = v3_cfg_val(core, "slice"); char *extra_time = v3_cfg_val(core, "extra_time"); - + char *speed = v3_cfg_val(core, "khz"); + uint_t speed_khz = cpu_khz; + if (atoi(id) == core_edf->info->vcpu_id){ - - core_edf->period = atoi(period); - core_edf->slice = atoi(slice); - core_edf->remaining_time = core_edf->slice; - if (strcasecmp(extra_time, "true") == 0) - core_edf->extra_time = true; - else + + if(speed){ + speed_khz = atoi(speed); + } + + if(slice){ + core_edf->slice = atoi(slice); + } + else{ + core_edf->slice = MIN_SLICE; + } + + if(period){ + core_edf->period = atoi(period); + } + else{ + core_edf->period = (core_edf->slice * cpu_khz * tdf)/speed_khz; + core_edf->period += 0.3*(100*core_edf->slice/core_edf->period); // Give faster vcores a little more bigger periods. + } + + PrintDebug(info->vm_info,info,"EDF_SCHED. Vcore %d, Pcore %d, cpu_khz %u, Period %llu Speed %d, Utilization %d, tdf %d %llu \n", + core_edf->info->vcpu_id, + core_edf->info->pcpu_id, + cpu_khz, + core_edf->period, + speed_khz, + (int)(100*core_edf->slice/core_edf->period), + tdf, + runqueue->smallest_period); + + if(extra_time){ + if (strcasecmp(extra_time, "true") == 0) + core_edf->extra_time = true; + else + core_edf->extra_time = false; + } + else core_edf->extra_time = false; + break; } core = v3_cfg_next_branch(core); } - activate_core(core_edf,runqueue); - return 0; + return activate_core(core_edf,runqueue); + } + /* - * search_core_edf: Searches a core in the red-black tree by using its vcpu_id + * search_core_edf: Searches a core in the red-black tree by using its current_deadline */ -static struct vm_core_edf_sched * -search_core_edf(struct vm_core_edf_sched *core_edf, struct vm_edf_rq *runqueue){ +static struct vm_core_edf_sched * +search_core_edf(time_us current_deadline, struct vm_edf_rq *runqueue){ struct rb_node *node = runqueue->vCPUs_tree.rb_node; - + while (node) { - struct vm_core_edf_sched *core = container_of(node, struct vm_core_edf_sched, node); - - if (core_edf->current_deadline < core->current_deadline) + + if (current_deadline < core->current_deadline) node = node->rb_left; - else if (core_edf->current_deadline > core->current_deadline) + else if (current_deadline > core->current_deadline) node = node->rb_right; else - if(core->info->vcpu_id == core_edf->info->vcpu_id){ - return core; - } + return core; } return NULL; } -/* - * delete_core_edf: Deletes a core from the red black tree, generally when it has +/* + * delete_core_edf: Deletes a core from the red black tree, generally when it has * consumed its time slice within the current period. */ -static bool +static bool delete_core_edf( struct vm_core_edf_sched *core_edf , struct vm_edf_rq *runqueue){ - struct vm_core_edf_sched *core = search_core_edf(core_edf, runqueue); - if (core){ + struct vm_core_edf_sched *core = search_core_edf(core_edf->current_deadline, runqueue); + if (core){ - v3_rb_erase(&core->node, &runqueue->vCPUs_tree); - return true; - } + v3_rb_erase(&core->node, &runqueue->vCPUs_tree); + return true; + } else{ - PrintError(core->info->vm_info, core->info,"EDF Sched. delete_core_edf.Attempted to erase unexisting core"); - return false; + PrintError(VM_NONE,VCORE_NONE,"EDF Sched. delete_core_edf.Attempted to erase unexisting core"); + return false; } } @@ -511,85 +605,182 @@ delete_core_edf( struct vm_core_edf_sched *core_edf , struct vm_edf_rq *runqueu * deactivate_core - Removes a core from the red-black tree. */ -static void +static void deactivate_core(struct vm_core_edf_sched * core, struct vm_edf_rq *runqueue){ if(delete_core_edf(core, runqueue)){ runqueue->cpu_u -= 100 * core->slice / core->period; runqueue->nr_vCPU -- ; - } + } } +/* + * adjust_slice - Adjust vcore parameters values + */ + +static void adjust_slice(struct vm_core_edf_sched *core){ + + time_us host_time = get_curr_host_time(&core->info->time_state); + time_us used_time = host_time - core->last_wakeup_time; + + if(core->last_wakeup_time != 0){ + + core->used_time += used_time; + core->total_time += used_time; + if(core->start_time != 0){ + core->expected_time = ((host_time - core->start_time)/core->period)*core->slice; + } + if(core->total_time <= core->expected_time){ + core->remaining_time = core->expected_time - core->total_time; + } + else{ + core->remaining_time =0; + } + + if (core->used_time > core->slice){ + core->slice_overuse++; + } + } + +} + +/* + * Check_deadlines - Check virtual cores, and re-insert in the runqueue the ones which deadline is over + */ + + +static void check_deadlines(struct vm_edf_rq *runqueue){ + + struct rb_node *node = v3_rb_first(&runqueue->vCPUs_tree); + struct vm_core_edf_sched *next_core = container_of(node, struct vm_core_edf_sched, node); + time_us host_time = get_curr_host_time(&next_core->info->time_state); + struct vm_core_edf_sched * deadline_cores[runqueue->nr_vCPU]; + + + int nr_dcores=0; + int i=0; + memset(deadline_cores, 0, runqueue->nr_vCPU); + + while(node){ + + next_core = container_of(node, struct vm_core_edf_sched, node); + if(next_core->current_deadline < host_time){ + next_core->deadline++; + next_core->deadline_interval++; + deadline_cores[nr_dcores++]= next_core; + if(next_core->used_time < next_core->slice){ + next_core->miss_deadline++; + next_core->miss_deadline_interval++; + + /*PrintError(VM_NONE,VCORE_NONE,"Test: Core %d miss_deadlines %d, used time %llu, slice %llu, deadline %llu, host time %llu \n", + next_core->info->vcpu_id, + next_core->miss_deadline, + next_core->used_time, + next_core->slice, + next_core->current_deadline, + host_time);*/ + + } + else{ + next_core->extra_time_given += (next_core->used_time - next_core->slice); + + /* PrintError(VM_NONE,VCORE_NONE,"Test: Extra time, core %d, core used time %llu, slice %llu, extra time %llu, Total extra time %llu \n", + next_core->info->vcpu_id, + next_core->used_time, + next_core->slice, + (next_core->used_time - next_core->slice), + next_core->extra_time_given);*/ + + } + + } + else{ + break; + } + node = v3_rb_next(node); + } + + + for(i=0;icheck_deadline_time = host_time; +} + + /* * pick_next_core: Returns the next core to be scheduled from the red black tree */ -static struct vm_core_edf_sched * +static struct vm_core_edf_sched * pick_next_core(struct vm_edf_rq *runqueue){ - - + /* * Pick first earliest deadline core */ - struct rb_node *node = v3_rb_first(&runqueue->vCPUs_tree); - struct vm_core_edf_sched *next_core = container_of(node, struct vm_core_edf_sched, node); - - /* - * Verify if the earliest deadline core has used its complete slice and return it if not - */ + struct rb_node *node=NULL; + struct vm_core_edf_sched *next_core=NULL; + time_us core_deadline=0; // Deadline of the core with more time remaining + time_us core_extra_deadline=0; // Deadline of the core with extra time enable and earliest deadline + time_us max_remaining=0; + time_us host_time = get_curr_host_time(&runqueue->curr_vCPU->info->time_state); + + if(host_time - runqueue->check_deadline_time >= runqueue->smallest_period ){ + check_deadlines(runqueue); + } + + node = v3_rb_first(&runqueue->vCPUs_tree); + next_core = container_of(node, struct vm_core_edf_sched, node); if (next_core->used_time < next_core->slice){ - if(next_core->current_deadline < get_curr_host_time(&next_core->info->time_state)) - next_core->miss_deadline++; - return next_core; + return next_core; + } + + if(next_core->total_time < next_core->expected_time){ + max_remaining = next_core->remaining_time; + core_deadline = next_core->current_deadline; + } + + if(next_core->extra_time){ + core_extra_deadline = next_core->current_deadline; } - /* - * If slice used, pick the next core that has not used its complete slice - */ - else { - while(next_core->used_time >= next_core->slice){ - - if(next_core->current_deadline < get_curr_host_time(&next_core->info->time_state) || !next_core->extra_time ){ + // Pick the next core that has not used its whole slice + while(node){ - deactivate_core(next_core,runqueue); - activate_core(next_core,runqueue); - - } + next_core = container_of(node, struct vm_core_edf_sched, node); - node = v3_rb_next(node); - if(node){ - next_core = container_of(node, struct vm_core_edf_sched, node); + if(next_core->remaining_time > max_remaining){ + max_remaining = next_core->extra_time_given; + core_deadline = next_core->current_deadline; + if(core_extra_deadline !=0 && next_core->extra_time){ + core_extra_deadline = next_core->current_deadline; } - else{ - node = v3_rb_first(&runqueue->vCPUs_tree); // If all cores have used its slice return the first one - return container_of(node, struct vm_core_edf_sched, node); - } + } + if(next_core->used_time < next_core->slice){ + return next_core; } - } - - return next_core; -} -static void -adjust_slice(struct guest_info * info, int used_time, int extra_time) -{ - struct vm_core_edf_sched *core = info->sched_priv_data; - struct vm_edf_rq *runqueue = get_runqueue(info); + node = v3_rb_next(node); + } - core->used_time = used_time; - - if (extra_time >= 0) { - core->used_time += extra_time; + if(core_extra_deadline !=0){ + next_core = search_core_edf(core_extra_deadline, runqueue); } - if( core->used_time >= core->slice){ - deactivate_core(core,runqueue); - activate_core(core,runqueue); + else if (core_deadline != 0){ + next_core = search_core_edf(core_deadline, runqueue); } + + return NULL; } @@ -597,36 +788,68 @@ adjust_slice(struct guest_info * info, int used_time, int extra_time) * run_next_core: Pick next core to be scheduled and wakeup it */ -static void -run_next_core(struct guest_info *info, int used_time, int usec) +static void +run_next_core(struct guest_info *info, int usec) { struct vm_core_edf_sched *core = info->sched_priv_data; struct vm_core_edf_sched *next_core; struct vm_edf_rq *runqueue = get_runqueue(info); - - /* The next core to be scheduled is choosen from the tree (Function pick_next_core). - * The selected core is the one with the earliest deadline and with available time - * to use within the current period (used_time < slice) + time_us host_time = get_curr_host_time(&info->time_state); + + /* The next core to be scheduled is choosen from the tree (Function pick_next_core). + * The selected core is the one with the earliest deadline and with available time + * to use within the current period (used_time < slice) */ - - next_core = pick_next_core(runqueue); // Pick next core to schedule - - if (core != next_core){ + if(!runqueue->yielded){ + adjust_slice(core); + } + next_core = pick_next_core(runqueue); // Pick next core to schedule - // Wakeup next_core - wakeup_core(next_core->info); - core->total_time += used_time; + if(host_time - core->print_deadline_interval >= DEADLINE_INTERVAL){ - if (used_time > core->slice){ - core->slice_overuse++; - core->extra_time_given += (used_time - core->slice); + if(core->deadline_interval != 0){ + core->deadline_percentage_interval = (int)100*core->miss_deadline_interval/core->deadline_interval; } - // Sleep old core - - V3_Sleep(usec); - - } + PrintDebug(info->vm_info,info,"deadline: %d %llu %llu %d", + core->info->vcpu_id, + core->deadline_interval, + core->miss_deadline_interval, + core->deadline_percentage_interval); + + core->print_deadline_interval = host_time; + core->deadline_interval=0; + core->miss_deadline_interval = 0; + core->deadline_percentage_interval = 0; + } + + if(!next_core){ + runqueue->yielded=true; + V3_Yield(); + return; + } + runqueue->yielded=false; + + + if(core->deadline != 0) + core->deadline_percentage = (int)100*core->miss_deadline/core->deadline; + + if (core != next_core){ + + print_parameters(host_time, runqueue,core); + wakeup_core(next_core->info); + V3_Sleep(usec); + } + + else{ + // Necessary to update last_wakeup_time to adjust slice properly later + next_core->last_wakeup_time = get_curr_host_time(&next_core->info->time_state); + + if(host_time - runqueue->print_time >= runqueue->smallest_period ){ + print_parameters(host_time, runqueue,core); + } + } + } @@ -637,36 +860,29 @@ run_next_core(struct guest_info *info, int used_time, int usec) static void edf_schedule(struct guest_info * info, int usec){ - uint64_t host_time = get_curr_host_time(&info->time_state); - struct vm_edf_rq *runqueue = get_runqueue(info); - struct vm_core_edf_sched *core = (struct vm_core_edf_sched *) info->sched_priv_data; + uint64_t host_time = get_curr_host_time(&info->time_state); + struct vm_edf_rq *runqueue = get_runqueue(info); - uint64_t used_time = 0; - if(core->last_wakeup_time != 0) - used_time = host_time - core->last_wakeup_time; + /*PrintDebug(info->vm_info,info,"Test PCORE. %d host time: %llu Last sched_time: %llu, difference: %llu\n", + info->pcpu_id, host_time, runqueue->last_sched_time, host_time-runqueue->last_sched_time); */ - if(usec == 0) runqueue->last_sched_time = host_time; // Called from edf_sched_scheduled - adjust_slice(core->info, host_time - core->last_wakeup_time, usec); + /* if( (runqueue->last_sched_time !=0) && ((host_time - runqueue->last_sched_time) > 10000)){ + PrintDebug(info->vm_info,info,"%d Test PCORE. %d LOW SCHED FREQUENCY host time: %llu Last sched_time: %llu, difference: %llu\n", + ++runqueue->sched_low,info->pcpu_id, host_time, runqueue->last_sched_time, host_time-runqueue->last_sched_time); + }*/ - run_next_core(core->info,used_time, usec); + runqueue->last_sched_time = host_time; + run_next_core(info, usec); return; } /* - * edf_sched_schedule: Main scheduling function. Computes amount of time in period left, - * recomputing the current core's deadline if it has expired, then runs - * scheduler - * It is called in the following cases: - * A vCPU becomes runnable - * The slice of the current vCPU was used - * The period of a vCPU in the runqueue starts - * Other case?? - * TODO Something to do with extra time? - * TODO Check the use of remaining_time + * edf_sched_schedule: Main scheduling function. Called each time that an interruption occurs. + * */ -void +void edf_sched_schedule(struct guest_info * info){ edf_schedule(info, 0); @@ -677,25 +893,51 @@ edf_sched_schedule(struct guest_info * info){ * edf_sched_yield: Called when yielding the logical cpu for usec is needed */ -void +void edf_sched_yield(struct guest_info * info, int usec){ - edf_schedule(info, usec); return; - } /* + * edf_sched_core_stop. Stops virtual machine. All the virtual cores yield the CPU + */ + +int +edf_sched_core_stop(struct guest_info * info){ + + struct vm_edf_rq * runqueue = get_runqueue(info); + struct rb_node *node = v3_rb_first(&runqueue->vCPUs_tree); + struct vm_core_edf_sched *curr_core; + + while(node){ + + curr_core = container_of(node, struct vm_core_edf_sched, node); + wakeup_core(curr_core->info); + PrintDebug(VM_NONE,VCORE_NONE,"Waking up core %d, thread (%p)\n", + curr_core->info->vcpu_id, + (struct task_struct *)info->core_thread); + V3_Yield(); + PrintDebug(VM_NONE,VCORE_NONE,"Yielding Thread %p\n",(struct task_struct *)info->core_thread); + node = v3_rb_next(node); + + } + return 0; +} + + +/* * edf_sched_deinit: Frees edf scheduler data structures */ -int +int edf_sched_deinit(struct v3_vm_info *vm) { + PrintDebug(VM_NONE,VCORE_NONE,"Freeing vm\n"); void *priv_data = vm->sched_priv_data; - - if (priv_data) + + if (priv_data) V3_Free(priv_data); return 0; @@ -706,17 +948,22 @@ edf_sched_deinit(struct v3_vm_info *vm) * edf_sched_deinit: Frees virtual core data structures */ -int +int edf_sched_core_deinit(struct guest_info *core) { + PrintDebug(VM_NONE,VCORE_NONE,"Freeing core\n"); void *priv_data = core->sched_priv_data; - - if (priv_data) + + if (priv_data) V3_Free(priv_data); return 0; } +/* + * edf_sched_vm_int. Called when the VM starts + */ + int edf_sched_vm_init(struct v3_vm_info *vm){ return 0; } @@ -724,28 +971,33 @@ int edf_sched_vm_init(struct v3_vm_info *vm){ int edf_sched_admit(struct v3_vm_info *vm){ /* - * Initialize priv_data for the vm: + * Initialize priv_data for the vm: * For EDF this is done here because we need the parameter * avail_core which is set in v3_start_vm before the * v3_scheduler_admit_vm function is called. */ - + priv_data_init(vm); // TODO Admission - + return 0; } +/* + * vm_scheduler_impl. Functions that implement vmm_scheduler interface + */ + static struct vm_scheduler_impl edf_sched = { .name = "edf", .init = NULL, .deinit = NULL, .vm_init = edf_sched_vm_init, - .vm_deinit = NULL, + .vm_deinit = edf_sched_deinit, .core_init = edf_sched_core_init, + .core_stop = edf_sched_core_stop, .core_deinit = edf_sched_core_deinit, .schedule = edf_sched_schedule, .yield = edf_sched_yield, @@ -754,26 +1006,41 @@ static struct vm_scheduler_impl edf_sched = { .dvfs=NULL }; -static int + +/* + * ext_sched_edf_init. Creates an register the EDF scheduler. + */ + +static int ext_sched_edf_init() { PrintDebug(VM_NONE, VCORE_NONE,"Sched. Creating (%s) scheduler\n",edf_sched.name); return v3_register_scheduler(&edf_sched); } -static int +/* + * ext_sched_edf_vm_int. Called when the VM starts + */ + +static int ext_sched_edf_vm_init() { return 0; } + +/* + * v3_extension_impl. EDF extension functions + */ + + static struct v3_extension_impl sched_edf_impl = { .name = "EDF Scheduler", .init = ext_sched_edf_init, .vm_init = ext_sched_edf_vm_init, .vm_deinit = NULL, - .core_init = NULL, - .core_deinit = NULL, - .on_entry = NULL, - .on_exit = NULL + .core_init = NULL, + .core_deinit = NULL, + .on_entry = NULL, + .on_exit = NULL }; register_extension(&sched_edf_impl);