### Next fit Algorithm for RM Scheduling

1. This algorithm uses the same assumptions used in the Rate Monotonic Scheduling
2. This algorithm is based on the RM Scheduling algorithm for each processors
3. The multi processor is assumed to consists of identical processors.
4. The tasks are assumed to require no resources other than the CPU Time
5.

The tasks are allocated to processors according to the classes in which they belong. Each classes contains a set of processors that is only allocated the tasks of that class.

Tasks are allocated one by one to the appropriate processor classes until all the tasks have been scheduled.

If any class fails to produce a feasible RM Schedule, then a new processor will be added to the same class and the corresponding task (which does not meets its deadline) is allocated to the new processor class.

Example

Let us say M=4 classes. The following table lists the classes

 Class Bound C1 (0.41,1] C2 (0.26,0.41] C3 (0.19,0.26] C4 (0, 0.19]

The tasks sets are given below

 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 ei 5 7 3 1 10 16 1 3 9 17 21 Pi 10 21 22 24 30 40 50 55 70 90 95 u(i)=ei/Pi 0.50 0.33 0.14 0.04 0.33 0.40 0.02 0.05 0.13 0.19 0.22 Class C1 C2 C4 C4 C2 C2 C4 C4 C4 C4 C3

Steps

6. Since C1 class contains only one task T1, it will be RM Schedulable, so p1 is a processor under C1
7. C2 contains three tasks, T2, T5 and T6, upon RM Scheduling T6 fails to meets its deadline, so a new processor is added to class C2. So class C2 contains two processors p2 and p5
8. C3 is also having only one Task T11 and it will also be schedulable under RM, so p3 is a processor under C3.
9. C4 contains 6 tasks namely, T3,T4, T7,T8,T9 and T10. All the tasks meets their deadlines under RM Scheduling, so p4 is a processor under C4
10.

 Processor Tasks p1 T1 p2 T2, T5 p3 T11 p4 T3,T4,T7,T8,T9,T10 p5 T6