## 3 Backward Reachability-Based Schedulability Test
### Using the Schedulability Test for Checking Systems with an Arbitrary Number of Processors  
So far, we have assumed that our scheduler uses dynamic scheduling: in a multiprocessor system, such a scheduler determines the next (according to its priority) ready task to be executed by any of the freed processors. In static scheduling on a multiprocessor system, only one of many processors is assigned a set of tasks in advance, and the scheduler schedules each task for its assigned processor. We propose _semi-dynamic scheduling_: the set of tasks is divided into groups in advance, each of which is assigned not one processor, as in static scheduling, but several ones. This technique allows us to effectively use our schedulability test proposed in the previous section. The idea is to partition the task set into _1-test groups_ that include (1) \(n_{i}+1\) tasks to be executed on \(n_{i}\) processors, and (2) the remaining groups of \(n_{j}\) tasks to be executed on \(m_{j}\) processors, such that the numbers \(n_{j}\) and \(m_{j}\) are small enough for exact schedulability testing these groups, using known methods such as [9; 17] or using the SPIN verifier [14]. Such partitioning depends on the ratio of the number of tasks and processors. In general, this partition problem can be represented as a version of the well-known bin-packing problem, widely used in the analysis of real-time systems [3; 30]. The bins here are multiprocessor clusters, and items are tasks. This version is quite complex, since the size and number of bins depend on both the size and number of items. We propose the following algorithm that constructs 1-test groups for a desired partition of a real-time system \(T\), taking into account the task utilization \(C_{i}/D_{i}\) and partially tests \(T\). Let procedure \(Test1(T)\) use Algorithm 1 to return a schedulability verdict for a real-time system \(T\), and procedure \(sort(T)\) sort the tasks of real-time system \(T\) by their utilization value from highest to lowest. The following procedures preserve this sorting:\(first(T,k)\) returns the first \(k\) tasks in \(T\), \(head(T)\) returns the first task in \(T\) removing it from \(T\), \(remove\_first(T,k)\) removes the first \(k\) tasks from \(T\), and \(replace(T,k,x)\) replaces task \(k\) in \(T\) with task \(x\). Our Algorithm 3 takes a real-time system running on a multiprocessor platform as the input and returns a set of 1-test groups for this system or a result FAIL, which means that the algorithm cannot find a partition with schedulable groups of the required size. The algorithm first sorts the tasks of the real-time system \(T\) by their utilization from largest to smallest. It then successively divides the number of processors by two (line 4), testing the schedulability of the corresponding number of the first most-expensive tasks using Algorithm 3 (line 8). If it finds that this set of tasks is not schedulable, it replaces these tasks with less expensive ones in line 13, until it either makes a schedulable set \(T^{\prime}\) (line 17) or fails to do so (line 15). ```
1:real-time system \(T\) with \(n\) tasks and \(m\) processors (\(m<n\)).