Patent ID: 9298505
Filing Date: 2016-03-29
CPC Classification: G06F

Claim Text:
1. A time and space-deterministic task scheduling apparatus using a multi-dimensional scheme, comprising: a preparation list generation unit configured to generate a preparation list, including a preparation table having an array structure configured to have each bit formed of a binary number indicative of a priority of a task, and also including a preparation group cluster configured to include a plurality of preparation groups, each including bits corresponding to the respective binary numbers of the preparation table, and also configured to have an upper and lower dimension relationship between the plurality of preparation groups; and a task insertion unit configured to perform bit masking on the preparation group cluster and the preparation table corresponding to a task P having a specific priority and to thus insert the task into the preparation group cluster and the preparation table, wherein the task P having a specific priority includes a bit indicative of a location in each of the plurality of preparation groups having an upper and lower dimension relationship and a bit indicative of a location in the preparation table, wherein the preparation list generation unit is further configured to: form a first preparation group, that is, a preparation group having a highest dimension of the preparation group cluster, using 4 bits; form a second preparation group corresponding to a next higher dimension, that is, a lower dimension of the first preparation group formed of 4 bits, with respect to each bit of the first preparation group; form a third preparation group corresponding to a next lower dimension, that is, a lower dimension of the second preparation group formed of 4 bits, with respect to each bit of the second preparation group; and generate the preparation list by setting a specific bit of the first preparation group to 1 in order to indicate that a task in an execution preparation state is present in the first preparation group if a value of any one of the bits of the second preparation group, the third preparation group and the preparation table corresponding to the specific bit of the first preparation group is 1, wherein the preparation list generation unit is further configured to classify the task P, having a specific priority formed of 8 bits, into pairs of 2 bits, and to generate the preparation list so that the task P is mapped to each of the first preparation group, the second preparation group, the third preparation group and the preparation table in accordance with a value of each of four 2 bits, and wherein the task insertion unit is further configured to perform: based on the map table having an array structure stored in a repository in order to enable performance without requiring sequential search of the preparation list, first insertion execution for performing bit masking on the first preparation group in accordance with a value of the map table in which a value of highest 2 bits of the task P having a specific priority has been indexed; second insertion execution for performing bit masking on the second preparation group in accordance with a value of the map table in which a value of next higher 2 bits of the task P having a specific priority has been indexed; third insertion execution for performing bit masking on the third preparation group in accordance with a value of the map table in which a value of next lower 2 bits of the task P having a specific priority has been indexed; and fourth insertion execution for performing bit masking on the preparation table in accordance with a value of the map table in which a value of lowest 2 bits of the task P having a specific priority has been indexed.