<div><div>I will be adding container support to litmus over the next</div><div>year. Exciting. My goals are to support a hierarchical container</div><div>scheme where each container can have its own scheduling policy and a</div>
<div>single container can be run on multiple CPUs simultaneously.</div></div><div><br></div><div>This is my idea and I would love it to be critiqued.</div><div><br></div><div><b>-- Interface --</b></div><div>Tasks should be able to join and leave containers dynamically, but I</div>
<div>don't intend to support (initially) dynamic creation of a container</div><div>hierarchy. Instead, plugins will configure their own containers.</div><div><br></div><div>I intend to completely copy the container proc interface from</div>
<div>Linux. The interface looks something like this:</div><div> - <plugin>/<container-id>*/tasks</div><div>Tasks are added and removed from containers by echoing their IDs into</div><div>the tasks file of each container.</div>
<div><br></div><div>For example, a CEDF plugin with containers would work as follows:</div><div>1. The scheduling plugin CODE would create a container for each</div><div>cluster, and the container framework would automatically expose them</div>
<div>under proc:</div><div> - CEDF/0/tasks</div><div> - CEDF/1/tasks</div><div> - CEDF/2/tasks</div><div> - CEDF/3/tasks</div><div>2. The scheduling plugin USER would create tasks, and echo their PIDs</div><div>into these containers as he/she sees fit.</div>
<div><br></div><div><b>-- The framework --</b></div><div>The framework I'm showing is designed with the following thoughts:</div><div>* Eventual support for less ad-hoc slack stealing</div><div>* Not breaking locking code too much</div>
<div>* Trying to minimize amount of extra data being passed around</div><div>* Keeping as much container code out of the plugins as possible</div><div><br></div><div>The basic idea is to have rt_task's become the fundamental schedulable</div>
<div>entity in Litmus. An rt_task can correspond to a struct task_struct,</div><div>as they do now, or an rt_cpu. I want to use these rt_tasks to abstract</div><div>out the code needed to manage container hierarchies. Per-plugin</div>
<div>scheduling code should not have to manage containers at all after initialization.</div><div><br></div><div>An rt_cpu is a virtual processor which can run other tasks. It can</div><div>have a task which is @linked to it, and it optionally enforces budget</div>
<div>with an @timer. The virtual processor is run when its corresponding</div><div>rt_task, or @server, is selected to run. When the rt_cpu is selected</div><div>to run, it chooses a task to execute by asking its corresponding</div>
<div>@container.</div><div><br></div><div><font face="'courier new', monospace">struct rt_cpu {</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>unsigned int cpu; /* Perhaps an RT_GLOBAL macro corresponds to</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * a wandering global virtual processor?</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_task *server; /* 0xdeadbeef for no server maybe?</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * I'm thinking of doing something</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * special for servers which have</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * full utilization of a processor,</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * as servers in the BASE container</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * will.</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_task *linked; /* What is logically running */</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct enforcement_timer timer;</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct bheap_node *hn; /* For membership in heaps */</font></div><div><font face="'courier new', monospace"><br>
</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_container *container; /* Clearly necessary */</font></div><div><font face="'courier new', monospace">};</font></div>
<div><br></div><div>An rt_container struct is a group of tasks scheduled together. The container</div><div>can run tasks when one or more @procs are selected to run. When a</div><div>container can run a task, it selects the next task to run using a</div>
<div>@policy.</div><div><br></div><div><font face="'courier new', monospace">struct rt_container {</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Potentially one of these for each CPU */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_cpu *procs;</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>cpumask_t cpus; /* Or perhaps num_cpus? I want O(1) access to</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * partitioned CPUs, but a container may also</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * have multiple global rt_cpus. I am not sure</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * how to accomplish O(1) access with global</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * rt_cpus. Ideas? I'll try to think of something.</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* To create the container hieararchy */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_container *parent;</font></div><div><font face="'courier new', monospace"><br></font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* The per-container method for scheduling container task */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct *rt_policy policy;</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Metadata kept seperate from the rest of the container</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * because it is not used often. E.g. a task list, proc</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * entries, or a container name would be stored in this.</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_cont_data *data;</font></div>
<div><font face="'courier new', monospace">};</font></div><div><br></div><div>An rt_policy is a per-container scheduling policy. It consists of</div><div>@ops for selecting a task.</div><div><br></div><div><font face="'courier new', monospace">struct rt_policy {</font></div>
<div><font face="'courier new', monospace"> struct rt_policy_ops *ops;</font></div><div><font face="'courier new', monospace"> int type; /* GSN-EDF, PSN-EDF, PFAIR, MC, etc */</font></div><div>
<font face="'courier new', monospace">};</font></div><div><br></div><div>Implementations of rt_policy's will wrap the policy with necessary</div><div>state for decision making, like so:</div><div><br></div><div>
<font face="'courier new', monospace">struct edf_policy {</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_policy policy;</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_domain domains;</font></div><div><font face="'courier new', monospace">};</font></div><div>
<font face="'courier new', monospace">container.policy = alloc_gedf_policy();</font></div><div><br></div><div>The rt_policy_ops correspond to the methods of our plugins today. They</div><div>can access per-policy state using magic container-of macros. They are</div>
<div>passed in an rt_container so that they can make decisions using that</div><div>container's @procs. My design of rt_policy's is pretty similar to how</div><div>we do litmus_lock's today and what is recommended in the</div>
<div>"Object-oriented design patterns in the kernel" series on LWN.</div><div><br></div><div><font face="'courier new', monospace">struct rt_policy_ops {</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_task* (*schedule)(struct rt_container*, struct rt_task*);</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>void (*block)(struct rt_container*, struct rt_task*);</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>void (*wake_up)(struct rt_container*, struct rt_task*);</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Why not new and exit? Semantics. These are different from</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * a new task joining and leaving the system. Hypothetically,</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * servers could migrate between containers, but they are not</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * "exiting". I'm flexible naming, though.</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>void (*remove)(struct rt_container*, struct rt_task*);</font></div><div><font face="'courier new', monospace"><br>
</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Why no admit_task(), but returning a long? Conceivably, the</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * admit_task() code could require access to synchronized</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * state. What if a task passes admit_task() in a container,</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * then the state changes so that it would fail, then the task</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * calls add()? Failure. Dealing with this would require the</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * caller to acquire locks for our sake, which I don't want to</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * do. Checks are done in the add method instead.</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>long (*add)(struct rt_container*, struct rt_task*);</font></div><div><font face="'courier new', monospace">};</font></div>
<div><br></div><div>The rt_param struct is a bit toned down, what with most of the work</div><div>moving into rt_task's. It is still the real-time data for system</div><div>processes.</div><div><br></div><div><font face="'courier new', monospace">struct rt_param {</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* The server provided by the task */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_task server;</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* The USERSPACE view of the task */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_job job;</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* When there is no budget enforcement or slack stealing, the</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * task.server.job will match the task.server.job.</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * With budget enforcement and no slack stealing, the</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * server.job corresponds with the KERNELSPACE view of the</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * task, and the task.job corresponds with the USERSPACE view</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * of the task.</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * With slack stealing, the server might run other tasks</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * entirely.</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Where the task is actually running. This only makes sense</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * when referring to a process so is left in this struct.</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>unsigned int scheduled_on;</font></div><div><font face="'courier new', monospace">};</font></div><div>
<br></div><div>The rt_task struct becomes the main schedulable entity, and will be</div><div>passed around by rt_domains and rt_policy's.</div><div><br></div><div><font face="'courier new', monospace">struct rt_task {</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>lt_t wcet, period, phase;</font></div><div><font face="'courier new', monospace"><br></font></div><div>
<font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>struct rt_job job;</font></div><div><font face="'courier new', monospace"> struct rt_container *container;</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* To figure out how to schedule a task. When a plugin returns</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * an rt_task, the container framework will use this to choose</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * between returning a process or calling into a container.</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>task_type_t type;</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>task_class_t class; /* BE, HRT, SRT, etc */</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>budget_polity_t policy; /* Budget enforcment */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>unsigned int cpu; /* Where the task must run */</font></div>
<div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace">#ifdef CONFIG_LITMUS_LOCKING</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Locking stuff, so that we can apply our locking protocols</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * within containers (unlikely to be used for a while)</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div>
<div><font face="'courier new', monospace">#endif</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Collection membership */</font></div>
<div><font face="'courier new', monospace">};</font></div><div><br></div><div><font face="'courier new', monospace">typedef enum {</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>VIRTUAL, PROCESS</font></div>
<div><font face="'courier new', monospace">} task_type_t;</font></div><div><br></div><div>Finally, rt_job represents what it always has: the current job of a</div><div>task.</div><div><br></div><div><font face="'courier new', monospace">struct rt_job {</font></div>
<div><font face="'courier new', monospace"> lt_t release;</font></div><div><font face="'courier new', monospace"> lt_t deadline;</font></div><div><font face="'courier new', monospace"> lt_t exec_time;</font></div>
<div><font face="'courier new', monospace"> unsigned int job_no;</font></div><div><font face="'courier new', monospace"><br></font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>/* Where the task / process is logically running. This is in</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * rt_job (instead of rt_task) because, with slack stealing,</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * a process's server may be linked running one task, while</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * another server attempts to run this task. This makes a</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> * seperate link for the process and its server necessary.</font></div>
<div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span> */</font></div><div><font face="'courier new', monospace"><span class="Apple-tab-span" style="white-space:pre"> </span>unsigned int linked_on;</font></div>
<div><font face="'courier new', monospace">};</font></div><div><br></div><div><div>To put it all together, a scheduling decision works as follows:</div><div>1. Linux calls into Litmus's schedule method.</div>
<div>
2. Litmus calls schedule on the base container.</div><div>3. The base container returns some rt_task.</div><div>4. If the rt_task corresponds to a task_struct, the task_struct is</div><div>returned. Otherwise...</div><div>
5. The rt_task's container is found. Litmus calls schedule on that</div><div>container.</div><div>6. Repeat steps 4 and 5 until a task_struct or NULL is returned.</div><div><br></div><div>Some decisions will work in reverse.</div>
<div>1. Linux calls into Litmus's block method for some task.</div><div>2. Litmus calls the task's container's block method.</div><div>3. That block method does some work. If it sees that its container can</div>
<div>no longer run on one of its @procs, it calls its parent container's</div><div>block method, passing in the rt_task corresponding to that @proc.</div><div>4. Repeat steps 2 and 3 until their is either no parent container or</div>
<div>the called container does not have to block on a processor.</div><div><br></div><div>Obviously, with how much work is going to be put into this, comments</div><div>and criticisms are welcome. I also may have been less than clear on</div>
<div>some points and will gladly clarify them.</div><div><br></div><div><div>I also assume I haven't thought of lots of things and would appreciate</div><div>being called out on that.</div></div></div><div><br></div>
-- <br>
Jonathan Herman<br>Department of Computer Science at UNC Chapel Hill<br>