# US 2015/0106819 A1 · Task scheduling method for priority-based real-time operating system in multicore environment

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

- Number: US 2015/0106819 A1
- Document ID: US20150106819A1
- Status: Published application
- Kind: A1
- Application number: 14/461,791
- Filed: 2014-08-18
- Published: 2015-04-16
- Earliest claimed: 2013-10-14
- Assignees: Electronics and Telecommunications Research Institute
- Applicants: Electronics and Telecommunications Research Institute
- Inventors: Sangcheol KIM; Seontae KIM; Pyeongsoo MAH
- Web page: https://patentgrep.com/patent/US20150106819A1

## CPC

- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed herein is a task scheduling method for a priority-based real-time operating system in a multicore environment, which solves problems occurring in real-time multicore task scheduling which employs a conventional decentralized scheme. In the task scheduling method, one or more scheduling algorithm candidates for sequential tasks are combined with one or more scheduling algorithm candidates for parallel tasks. Respective task scheduling algorithm candidates generated at combining, are simulated and performances of the candidates are evaluated based on performance evaluation criteria. A task scheduling algorithm exhibiting best performance is selected from among results obtained at evaluating the performances.

## Claims

### Claim 1

A task scheduling method for a priority-based real-time operating system in a multicore environment, comprising:
combining one or more scheduling algorithm candidates for sequential tasks with one or more scheduling algorithm candidates for parallel tasks;
simulating respective task scheduling algorithm candidates generated at combining, and evaluating performances of the task scheduling algorithm candidates based on performance evaluation criteria; and
selecting a task scheduling algorithm exhibiting best performance from among results obtained at evaluating the performances.

### Claim 2 (depends on 1)

The task scheduling method of claim 1, wherein the performance evaluation criteria include an execution time required until execution of a last subtask of an application is completed, and a number of cases where a task having lower priority is executed even if a task having higher priority is waiting in another core.

### Claim 3 (depends on 2)

The task scheduling method of claim 2, wherein the selecting the task scheduling algorithm is configured to select a task scheduling algorithm candidate having a highest value of average values as the task scheduling algorithm exhibiting best performance, wherein the average values are obtained by averaging a sum of percentages of execution times required until the execution of the last subtask of the application is completed and percentages of the number of cases where a task having lower priority is executed even if a task having higher priority is waiting in another core, based on results of the simulation of respective task scheduling algorithm candidates.

### Claim 4 (depends on 1)

The task scheduling method of claim 1, wherein:
the simulation at evaluating the performances is configured to perform simulation by applying each of the task scheduling algorithm candidates, generated at combining, to a multicore real-time operating system application program,
requirements of the multicore real-time operating system application program include a requirement that sequential tasks and parallel tasks need to be present in an application, a requirement that the sequential tasks need to have tasks repeatedly executed with periodicity, a requirement that the sequential tasks and the parallel tasks need to have dependency, and a requirement that all tasks need to have priorities and sizes.

### Claim 5 (depends on 4)

The task scheduling method of claim 4, wherein the multicore real-time operating system application program is an application program adopting a decentralized scheme having a hierarchical structure.

### Claim 6 (depends on 1)

The task scheduling method of claim 1, wherein the one or more scheduling algorithm candidates for the sequential tasks include Round Robin (RR), Minimum Number of Tasks (MNT), Load Balance (LB), and Number of Tasks, Waiting Time and Priority (NTWP) algorithms.

### Claim 7 (depends on 1)

The task scheduling method of claim 1, wherein the one or more scheduling algorithm candidates for the parallel tasks include Minimum (MIN)-RR, MIN-MNT, MIN-LB, MIN-NTWP, Maximum (MAX)-RR, MAX-MNT, MAX-LB, and MAX-NTWP algorithms.

### Claim 8 (depends on 1)

The task scheduling method of claim 1, wherein the task scheduling algorithm candidates generated at combining include RR/MIN-RR, RR/MIN-MNT, RR/MIN-LB, RR/MIN-NTWP, RR/MAX-RR, RR/MAX-MNT, RR/MAX-LB, RR/MAX-NTWP, MNT/MIN-RR, MNT/MIN-MNT, MNT/MIN-LB, MNT/MIN-NTWP, MNT/MAX-RR, MNT/MAX-MNT, MNT/MAX-LB, MNT/MAX-NTWP, LB/MIN-RR, LB/MIN-MNT, LB/MIN-LB, LB/MIN-NTWP, LB/MAX-RR, LB/MAX-MNT, LB/MAX-LB, LB/MAX-NTWP, NTWP/MIN-RR, NTWP/MIN-MNT, NTWP/MIN-LB, NTWP/MIN-NTWP, NTWP/MAX-RR, NTWP/MAX-MNT, NTWP/MAX-LB, and NTWP/MAX-NTWP algorithms.
