# US 2017/0255488 A1 · Method and system for analyzing task group schedulability for hard real-time scheduling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255488 A1
- Document ID: US20170255488A1
- Status: Published application
- Kind: A1
- Application number: 15/440,052
- Filed: 2017-02-23
- Published: 2017-09-07
- Earliest claimed: 2016-03-04
- Assignees: Agency for Defense Development
- Applicants: Agency for Defense Development
- Inventors: Dong-Kuk RYU; Sang-Il LEE; Hyun-Wook JIN; Yin-Goo YIM; Hyun-Chul JO
- Web page: https://patentgrep.com/patent/US20170255488A1

## CPC

- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- G06F 11/3696: {Methods or tools to render software testable}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The method and system for analyzing schedulability configured for a computer for operating an operating system that supports a task group of hard real-time scheduling or a user processor operated in an embedded circuit. The system includes an operating system including a file system and a kernel, and generating non-periodic real-time task information and periodic real-time task information from the file system and the kernel, a tool for testing hard real-time schedulability that collecting the non-periodic real-time task information by applying a first predetermined scheduling algorithm and determining schedulability of a reserved resource for a real-time task group including the non-periodic real-time task information through a second predetermined scheduling algorithm.

## Claims

### Claim 1

A system for analyzing task group schedulability for hard real-time scheduling, the system comprising:
an operating system including a file system and a kernel, and generating non-periodic real-time task information and periodic real-time task information and periodic real-time task group information including the non-periodic real-time task information from the file system and the kernel; and
a tool for testing hard real-time schedulability that collecting the non-periodic real-time task information by applying a first predetermined scheduling algorithm and determining schedulability of a reserved resource for a real-time task group including the non-periodic real-time task information through a second predetermined scheduling algorithm.

### Claim 2 (depends on 1)

The system of claim 1, wherein the tool for testing hard real-time schedulability includes:
a first module for collecting non-periodic real-time task information, the first module collecting real-time task group information;
a second module for collecting periodic real-time task information, the second module collecting the periodic real-time task information; and
a third module for testing schedulability, the third module determining the schedulability of the reserved resource for the real-time task group including the periodic real-time task information through the real-time task information and the periodic real-time task information.

### Claim 3 (depends on 2)

The system of claim 2, wherein the first algorithm collects real-time task information including priorities by using a file system capable of accessing scheduling information including a period and an execution time of a task, or by using a system call.

### Claim 4 (depends on 2)

The system of claim 2, wherein the second algorithm determines the schedulability of the reserved resource for the real-time task group by using the periodic real-time task information including a period of an execution time of the periodic real-time task and priority information within the real-time task group, and by using the real-time task information allowed to a CPU.

### Claim 5 (depends on 2)

The system of claim 2, wherein the second module explores an executing process from folders of the file system, determines if a task policy of the folder matches to a deadline scheduling policy, and if so, collects a period and an execution time of a task that corresponds to the executing process.

### Claim 6 (depends on 2)

The system of claim 2, wherein the first module explores the real-time task group in the file system, explores priority information of a task within the real-time task group, and adds the explored real-time task group to a schedulability analysis subject set.

### Claim 7 (depends on 4)

The system of claim 4, wherein the periodic real-time task group determines the priority of the task group based on the priority of the non-periodic real-time task in the group and the periodic real-time task group selects the highest priority and the lowest priority of the non-periodic real-time task in the group as the maximum and minimum priority of the periodic real-time task group, and the periodic real-time task group is sorted in a descending order based on the highest-priority information.

### Claim 8 (depends on 2)

The system of claim 2, wherein the third module
determines whether the non-periodic real-time task information and the periodic real-time task information correspond to a schedulability analysis subject set or to a schedulability calculation subject set, adds the determined subject set to the corresponding subject set,
performs a schedulability analysis algorithm by exploring the schedulability analysis subject set from beginning to end,
determines the schedulability of the schedulability analysis subject set at the last schedulability analysis subject set, and
when the schedulability analysis subject set is determined to be impracticable, determines that the schedulability of the reserved resource for the real-time task group is impracticable.

### Claim 9 (depends on 8)

The system of claim 8, each schedulability analysis subject in the schedulability analysis subject set is always a schedulability analysis operation object having a relatively high priority, and the schedulability analysis operation is performed by calculating other schedulability analysis objects having the highest priority higher than the minimum priority of the schedulability analysis subject in the schedulability object analysis set as CPU resource usage in the worst case.

### Claim 10 (depends on 8)

The system of claim 8, wherein the real-time task group includes a non-periodic real-time task with high priority, and the third module determines
the schedulability of the reserved resource for the real-time task group by comparing a remaining time of a preempted time that is preempted by the real-time task group including the non-periodic real-time task allowed to a CPU or the real-time task group including non-periodic real-time task with a higher priority than the periodic real-time task, and the periodic real-time task, with an execution time required to execute the corresponding real-time group.

### Claim 11 (depends on 10)

The system of claim 10, wherein the execution time of the real-time task group is calculated by the following formula
∑
k
=
1
n
-
1

⌈
p
n
÷
p
k
⌉
×
e
k
<=
=
p
n
-
e
n
(Wherein, when k and n are natural numbers, a priority order of each task is shown in descending order. In other words, a task having top priority is expressed as T1. Therefore, Tk means a task having a kth priority. As the value of k increases, a task having kth priority has relatively low priority. When a current subject of schedulability analysis has an nth priority, then a corresponding task expressed as Tn, pn refers to a period of Tn, and cn refers to an execution time of Tn. A task group or a periodic real-time task having higher priority than the schedulability analysis subject is expressed as Tk. A period of Tk is expressed as pk, and an execution time of Tk is expressed as ek. Wherein, k is a natural number between 1 and n).

### Claim 12

A method of analyzing schedulability of a task group for hard real-time scheduling, wherein the method uses an operating system including a file system and a kernel and is performed by a tool for testing hard real-time schedulability, the method performed by a tool for testing hard real-time schedulability and comprising:
generating non-periodic real-time task information and periodic real-time task information and periodic real-time task group information including the non-periodic real-time task information from the file system and the kernel;
collecting non-periodic real-time task information by applying a first predetermined scheduling algorithm; and
determining schedulability of a reserved resource for a real-time task group including the non-periodic real-time task information by applying a second predetermined scheduling algorithm.