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 /include/linux/sched.h.

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(, &init_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 ’ in a shell.

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;

struct rq_flagsrf;

struct rq *rq;

int cpu;

cpu = smp_processor_id(); /* get current CPU ID */

rq = cpu_rq(cpu);

prev = rq->curr;

...

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);

clear_preempt_need_resched();

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: /proj2/apps/periodic/periodic.c

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 /proj2/apps/

$ cd /proj2/apps

$ tar xvfz periodic.tgz

#

$ cd periodic

$ ls

Makefile periodic.c

$ make

#

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.