Multiprocessor system is tightly coupled system where global status and workflow information on all processor can be kept at a low cost. These systems may use centralized scheduler or each processor may have its own scheduler. Fig below shows a typical multiprocessor system.

A distributed system is loosely coupled system where global status and workflow information update process is costly due to communication cost. Here each processor of the system has its own scheduler.

Fig below shows the typical distributed system.

Identical vs. Heterogeneous Processors:

Identical processors can be used interchangeably such as each core of multi-core CPU. Heterogeneous processors cannot be used interchangeably such as disk drive, transmission line etc. fig below shows a typical processor organization of the identical as well as heterogeneous processors.

  • If all processors of system have equal speed and capabilitie then they are called as identical processor.
  • If all processors have equal capabilities but different speeds then they are called as uniform heterogeneous (or homogenous) multiprocessor.

If no regular relation assumed and tasks may not be able to execute on all processors then such system is called unrelated heterogenous multiprocessors.

Problems Associated with Resource Assignment in Multiprocessor Scheduling:

The major problrm in resource assignment in multiprocessor system is the task assignment problems. The task assignment problem is related with following two problems.

  • The hard real time system are concern with the static system in which the task are prtitoned and statistically bound to the processor. The problem is how to partition the system of task and passive resources into modules and how to assign the modules to individuals processors.
  • Another problem is related with the interprocessor communication and synchronization . A synchronization protocol is required to maintan precedence constraints of jobs on different  processors.

Job shops and Flow shops:

According to job shop model, each task Ti in the system is a chain of n(i) jobs, denoted by Ji,k for k = 1,2…..n(i). Adjacent jobs Ji, k and Ji, k+1 on the chain execute on different processors. Ji, k +1 becomes ready for execution when Ji,k completes its execution. Processor are specified for each job to run by the visit sequence Vi = (vi, 1, vi, 2, …… vi, n(i) ). Visit sequence V1 = (p1, p2) denote the job sequence has two jobs and first job execute on first processor and second job on second processor.

A flow shop is a special job shop which has identical visit sequence.

End to End Task:

Let the release time ri of task Ti be the release time of first job Ji, 1 in the task and the deadline di of the task is the deadline of its last job Ji,n(i) . As long as the last job completes by the task deadline, it is not important when other jobs of the task complete then such model is known as end to end task model.

Periodic End to End tasks:

An end to end task Ti is periodic with period pi if the chain of n(i) jobs is released every pi (or more) and the jobs in the chain execute in turn on processors according to visit sequence Vi = (vi, 1, vi, 2, …… vi, n(i) ).

Local versus Remote Resource(MPCP Resource Model):

Here P1 is synchronization processor of resource printer while P2 is the synchronization of resource file server. Printer is local resource of J1 and J2 while fileserver is remote resource of J1. File server is global resource as it is needed by multiple jobs residing on different processor. When a job access global resource its global critical section executes on synchronization processor of that resource.

End to End resource model:

No jobs can make nested request for the resources residing on different processors. J1 on P1 and P1 à R1, P2 à R2

L(R1) L(R2) U(R2) U(R1) à not allowed L(R1) U(R1) L(R2) U(R2) à allowed

Inter-processor Communication:

Inter processor communication (IPC) is a set of programming interfaces that allow a programmer to coordinate activities among different program processes that can run concurrently in an operating system. This allows a program to handle many user requests at the same time. Since even a single user request may result in multiple processes running in the operating system on the user's behalf, the processes need to communicate with each other. The communication between two or more processor in a multi-processor organization to share the information/data is called inter-processor communication.

By using different algorithms, we can partitionton an application system into the compnents called modules and assigns the modules to processor. These algorithms make the use of information provided by interconnection parameters of jobs like volume of shared data stored on memory exchanged beteen each pair of jobs. The time reqire to synchronize jobs and transmit the data among them comes into account in several ways as inter-processor communication.


Fig(a). realtime monitor system that consists many field processor. Those jobs that collects and process the sensor data are called producer jobs since they generates the data. Those jobs that correlate and displays the data by executing on central processor are called consumer jobs. The jobs are communicated via. shared memory. Here each field processors are connected with shared memory via. a dedicated link that is shared by all field processors. The system contains three types of processors as field processor, shared-memory, control processor. The workload consists of end to end jobs, each job containing memory accessing jobs. In this way , delay in completion of each job caused by memory contention is taken into account. Hence shared memory cal be modeled as global resource whose synchronization processor is shared memory processor and both consumer and produceser requires this job.


Fig(b). shows a model in which all the producer are connected via. a network as controller area network(CAN). The result produced by each job on field processor are sent via network to control processor. Here network can be modeled as processor on which message transmission jobs are scheduled on a fixed priority basis. There is no need to account the interprocessor communication cost because they are taken into account by message transmission jobs in network.