System Models for Distributed Systems

The Workstation Model

• Workstations each have one or more CPUs


• Either in use or "idle"


• A shared central file server may be available


• Can be diskless or disk full


• If disk full, the private disk may be used for

• Paging and temporary files


• Paging and system binaries


• Paging and file caching

Complete local file system (with remote mounting)

Locating an idle processor

Issues

• What is an idle workstation?

A workstation is idle if no user-imitated processes are running and if input devices have not been touched for several minutes - a machine that is idle can still have a heavy load

• How is an idle workstation found?

The idle workstation can either be hunted for (client-driven) or can announce its availability (server-driven)

• How can a remote process be run transparently?

The process may need data from the local environment, local files, etc. But temp. files can be created remotely. What about input from keyboard and output to monitor?

• What happens if a machine's "owner" comes back?

Do nothing, but what about performance for the owner?

Kill the cuckoo, but what about work done?

Migrate the cuckoo - hard, hard, and hard!

Always leave the machine as you found it...

The Processor Pool Model

• Stick all CPUs into a centralized box and farm out compute power on demand


• Alleviates the problem of migrating processes


• The implicit assumption that the file system is shared

Processor Allocation

• For workstation model, the question is when is a process executed locally and when remotely - and on which remote machine


• For processor pool, the question is which processor to use for an incoming process

General strategies

• Migratory vs. No migratory


• Optimization of CPU time vs. Optimization of response time

Design Issues for processor allocation algorithms

• Deterministic vs. Heuristic algorithms


• Centralized vs. Distributed algorithms


• Optimal vs. approximate algorithms


• Local vs. global algorithms


• Sender-initiated vs. Receiver-initiated algorithms

Example algorithms...

The up-down algorithm

• Up-Down tries to distribute CPU time fairly, rather than maximizing CPU usage


• The coordinator manages centralized usage table containing an entry for each workstation


• Whenever a CPU performs a significant scheduling event, a message is sent to the coordinator


• Upon creation of a new process, if a CPU doesn't want to run it locally, it asks the coordinator to allocate another CPU to the process


• How the process is scheduled depends on the recent past history of the workstation


• For every second of borrowed CPU time, the usage table entry accumulates penalty points


• Whenever the coordinator is unable to allocation a CPU to a process, points are deducted from the user table entry


• Processes in the (shared) ready queue are ordered according to the number of points they have accumulated


• The process with the least number of points will be serviced first

Sender-Initiated Distributed Heuristic Algorithms

• A. Sender picks a machine at random and sends a process there. If the receiver cannot handle it, it randomly picks another machine, etc., until some machine accepts it or a hop count is exceeded


• B. Sender picks a machine at random and sends a probe to enquire about its availability. Continues until the machine accepts process or probe limit is exceeded


• C. Sender probes k machines for their loads. Sends process to the machine with the lowest load.

Receiver-Initiated Distributed Heuristic Algorithm

• When a machine is idle, it sends a probe to a randomly chosen computer to ask for work


• Continues until somebody sends it to work or timer lapses


• Better than the previous algo when the system is overloaded

 

Scheduling in Distributed Systems

• Not much to say, because scheduling is local


• However, sometimes there are problems when two processes (running on different CPUs) are closely related (need to communicate)


• Optimal performance is obtained when both processes are run at the same time (otherwise, performance can degenerate to worse than that of uniprocessor systems)