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

 

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

1. Since C1 class contains only one task T1, it will be RM Schedulable, so p1 is a processor under C1
2. 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
3. C3 is also having only one Task T11 and it will also be schedulable under RM, so p3 is a processor under C3.
4. 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

 

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