Allocation Models:

Before describing allocating processor, here are some assumptions about the allocation models which are important for processor allocation:

• All machines are identical or at least code compatible


• They differ at most by speed (MIPS or FLOPS)


• Homogeneity (architecture)


• The system is fully connected (doesn’t always mean a wire to each system; just that transport connections can be established)


• New work is generated when a process decides to fork or otherwise create a sub-process

ISSUES IN PROCESSOR ALLOCATION

• Design Issues


• Deterministic vs Heuristic Algorithms


• Centralized vs Distributed Algorithms


• Optimal vs Sub-optimal Algorithms


• Local vs Global Algorithms


• Sender-initiated vs Receiver-initiated Algorithms


• Implementation Issues

PROCESSOR ALLOCATION ALGORITHMS

• There are many algorithms like


• A GRAPH-THEORETIC DETERMINISTIC ALGORITHM


• A CENTRALIZED ALGORITHM


• A HIERARCHICAL ALGORITHM


• A SENDER-INITIATED DISTRIBUTED HEURISTIC ALGORITHM


• A RECEIVER INITITATED DISTRIBUTED HEURISTIC ALGORITHM


• A BIDDING ALGORITHM


• In this part we will study only about


• A GRAPH-THEORETIC DETERMINISTIC ALGORITHM