CS 251/EE 255: Real-Time Embedded Systems
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS 251/EE 255: Real-Time Embedded Systems
HW Project #2: Task Scheduling and Monitoring
2022
1. Introduction
This homework project is designed to exercise the following topics:
• Accessing task information in the kernel data structures
• Linux scheduler basics
• Timers
Before you start working:
• Read the handout carefully: background, writeup questions and the tips section aim to give you hints about design and implementation.
• Whenever the handout asks you to do something without explaining how to accomplish it, please consult references on kernel development. That's by design.
• To be awarded full credit, your kernel must not crash or freeze under any circumstances.
2. Background Information 2.1. Periodic Task Parameters
In real-time systems, tasks are conventionally modeled as a periodic sequence of jobs. Jobs are released every T units of time and each job needs to finish within a relative deadline of D units of time from its release. To guarantee schedulability, we only admit a task into the system if the schedulability of the resulting task set is guaranteed. To perform a schedulability test, it is necessary to calculate the amount of resources each task uses, e.g., task 's utilization = / , or the worst-case response time.
However, our guarantee relies on the task to never exceed its allowed execution time, C. Unfortunately, tasks are not that obedient in practice and may overrun their budget due to an inaccurately estimated execution time, timing penalties from memory access, etc. To maintain the timing safety of the system in light of this, you will implement a simple monitoring framework in the kernel which will keep track ofthe task budget (i.e., maximum of C computation time every T).
2.2. Processes and Threads
In the Linux kernel, the kernel object corresponding to each process/thread is a task. Every process/thread running under Linux is dynamically allocated a struct task_struct structure, called Task Control Block (TCB). The TCB is declared in
The Linux kernel assigns a task ID to each task. Hence, both processes and threads have task IDs and each task's ID is stored in its TCB, in a member variable pid_t pid (not ‘tid’ due to historical reasons). In a single-threaded process, the task ID is equal to the process ID. In a multi-threaded process, all threads have the same process ID, but each one has a unique task ID. The process ID is also called a thread group leader ID (TGID) and it is stored in pid_t tgid of a TCB.
You can use ps and top commands in shell to view the list of running processes and (optionally) threads. You can also see the family relationship between the running processes in a Linux system using the pstree command.
For example, type “ps -eLfc” in the command line.
root 11 2 11 1 FF 139 Nov29 ? 00:00:00 [migration/0] root 12 2 12 1 TS 19 Nov29 ? 00:00:00 [cpuhp/0] ...
... |
This command prints all tasks including processes and threads running in the system. The second column, PID, displays the process ID of a task, and the fourth column, LWP, shows the actual task ID. See lines in cyan and yellow. PID and LWP fields are the same. That means it is either a single-threaded process or the leader thread (or also called master or main thread) of a multi-threaded process. In fact, PID 804 is a multi- threaded process. You can see two green lines, where PID is also 804 but LWP is different. This means these two tasks, 809 and 810, are the child threads ofthe process 804.
The TCBs of tasks are maintained in a doubly-linked list in the kernel. To find a task's TCB with a task ID (pid), you can use: find_task_by_pid_ns(
Each task is associated with a priority level. In Linux, the priority value range is divided into general- purpose priorities and real-time priorities (see rt_priority field in struct task_struct). All real- time priorities supersede all general-purpose priorities. A real-time task is a task whose scheduling class is a real-time class and rt_priority value is within the real-time priority value range (1 to 99). The chrt command can be used to give a process/thread real-time priority in a shell terminal. sched_setscheduler() is a system call to set real-time priority in C programs.
Let’s take a look at the above “ps -eLfc” example again. The scheduling class and priority of tasks are shown in the CLS and PRI columns, respectively. For convenience, Linux displays the priorities of time- sharing scheduling class (e.g., SCHED_OTHER) in the range of 0 to 40 and those of real-time scheduling class (e.g., SCHED_FIFO, SCHED_RR) in the range of 41 to 139 (meaning real-time priority 1 to 99). See the line in cyan, PID 11. Its CLS is FF, meaning its scheduling class is SCHED_FIFO; its PRI is 139, indicating its real-time priority is 99 (the highest priority level). You can verify this observation by ‘chrt -p
2.3. Task Scheduling
To keep track of the amount of computation resources a task consumes, the task will need to be followed throughout its lifetime: birth, context switch in, context switch out, and death.
In lecture, you were introduced to Linux processes and threads. The kernel shares the available CPU(s) among the tasks in the system. The kernel must be able to suspend the instruction stream of one task and resume the instruction stream of another previously-suspended task. This activity is referred to as a context switch.
When executing on one CPU, all tasks share the CPU registers. Hence, after suspending a task, the kernel must save the values of registers to restore them when the task is resumed. The set of data that must be loaded into the registers before the task resumes its execution on the CPU is called the hardware context.
A context switch involves saving the task control block (TCB, struct task_struct) of the task being switched out and replacing it with that of the task being switched in place. The context switch in the Linux kernel is initiated from one well-defined point: __schedule() function in kernel/sched/core.c.
static void __schednotrace__schedule(bool preempt) { struct task_struct *prev, *next; unsigned long *switch_count; unsigned long prev_state; int cpu; cpu = smp_processor_id(); /* get current CPU ID */ ... |
The __schedule() function is central to the kernel scheduler. Its objective is to find a task in the run- queue (a list of tasks ready to run) and assign the CPU to it. The function involves several kernel routines. It sets a local variable prev, which points to the TCB of the currently-running task on the current CPU.
... next = pick_next_task(rq, prev, &rf); clear_tsk_need_resched(prev); if (likely(prev != next)) { rq->nr_switches++; ... rq = context_switch(rq, prev, next, &rf); } else { ... } } |
Next, it picks a next task to be run and sets a local variable next to the next task's TCB. If next is different from prev, then finally context switch happens. If no runnable task has higher priority than the current task, then next coincides with prev and no context switch takes place.
2.4. Timing
The in-kernel timer of choice for this project is the high-resolution hrtimer. The documentation with lots of crucial usage information is available in the kernel source tree at Documentation/timers/hrtimers.rst and in include/linux/hrtimer.h. Examples are available athttps://developer.ibm.com/tutorials/l-timers-list/. Understand the various modes and choose the best ones for your purposes. Do not forget to cancel the timer after use or when it is no longer needed. Not doing so is a recipe for resource leak and kernel panic.
Hrtimer works with time values ofthe type ktime_t, which is a 64-bit signed integer representing time in nanoseconds.
A good, but not the only, function for getting the current time in the kernel is ktime_get().
3. Build Directory
You need to create a subfolder proj2/ in the top-level directory of your repository. Your source files to be implemented will fall into three categories:
Category |
Location in kernel repo |
Build method |
built-in kernel code |
proj2/kernel |
built together with the kernel image |
kernel modules |
proj2/modules |
standalone using the kernel build system |
user-space applications |
proj2/apps |
standalone using user-space libraries |
Follow the instructions in the HW #1 handout to setup Makefile (and Kbuild for kernel source code).
4. Assignment (total 120 points)
4.1. Periodic Real-time User-level Test Program (no points; needed for testing your kernel) Source code location:
Let us run the user-level application that takes C, T, CPUID arguments as input and busy-loops for C milliseconds every T milliseconds on the CPU CPUID. It supports C and T values up to 10,000 ms (10
secs). C and T values should be greater than 0 (C <= T). CPUID should be greater than or equal to 0 (0 means the first CPU core). The program is runnable on the stock kernel too: it does not rely on any of your modifications to the kernel. The program should continue to run until a user presses ‘Ctrl-C’ or terminates it by sending a KILL signal.
Download periodic.tgz from Canvas (Modules – Projects). Extract the file and build by:
1 2 3 4 5 6 7 |
$ mv periodic.tgz
$ cd
|
Once compiled successfully, you can run it with some input parameters and this program will print out its PID and the given input parameters. See the below example for formatting.
2022-02-24