Task Assignment

In hard Real Time System, application system is partitioned into modules and each module is assigned to a processor, and most module assignment in done offline. Assignment is based on execution time requirement of job as the communication cost is minimal as well as minimization of communication cost . Communication cost of individual task is independent of where the task execute. In multiprocessor system task of same module may execute on different processors, the communication cost of these tasks is negligible due to shared memory architecture. During the early designed stage, we want to ignore it but it cost be depends on the system where task is executed.

Simple Bin Packing Formulation/ Algorithms:

• The task assignment problem can be generalized using a simple bin packing problem.
• There can be more than on job.
• The server utilization should not be greater be than 1 but if there are more than one job, the utilization can be greater than one.Therefore, all job cannot execute on a single processor.
• The bin packing formulation is used to find optimal number of processor to execute all jobs to execute all jobs with total utilization less than 1.
• The bin packing algorithms can use two approaches                                                                                                               a. Uniform size bin packing                                                                                                                                           b.  Variable size bin packing
• The variable size bin packing is the efficient method because it use the first fit method to select and execute the job on single processor.
• The job if single can be partitioned into different modules and by using bin packing formulation, an appropriate processor can be selected to execute each modules such that total utilization becomes less than 1.

Suppose a system with a 7 modules with utilization as 0.2 0.5     0.4     0.6      0.1 0.3 0.8 and bin size 0.9 then

Total utilization = 0.2 + 0.5 + 0.4 + 0.6 + 0.1 + 0.3 + 0.8 = 2.9

Different approaches like next fit, first fit and best fit are used to formulate the bin packing.

First Fit Algorithms:

• Keep a single open bin
• When an item does not fit, close this bin and open a new bin where closed bins are never used again.
• In this method the bin packing be done as below.

Next Fit Algorithms:

• Keep all bins open.
• An item is assigned to the first bin in which it fits.
• Check all previous bins to see if the next item will fit.
• If item does not fit in any open bin, open a new bin.