A review paper about processes and processors in distributed systems 

Distributed Systems: A distributed system, also known as distributed computing, is a system with multiple components located on different machines that communicate and coordinate actions in order to appear as a single coherent system to the end-user. 

Hardware and software architectures are used to maintain a distributed system. Everything must be interconnected—CPUs via the network and processes via the communication system. 

Distributed Processing

Originally, conventional microprocessors involved just one CPU on a chip. As microprocessor engineering evolved, manufacturers discovered that to speed up processes, more than one processor could be combined on a single unit. Many modern processors involve a multi-core design, such as a quad-core design pioneered by companies like Intel, where four separate processors offer extremely high speeds for program execution and logic.

Distributed processing also can be used as a rough synonym for parallel processing, in which programs are made to run more quickly with multiple processors. With the strategy of including more than one processor on a microprocessor chip, hardware users also can string multiple computers together to implement parallel processing with applications known as distributed processing software.

The distributed processing concept goes along with Moore’s law, which posits that the number of transistors on an individual integrated circuit (IC) doubles every two years. As this theory has largely proven correct over the last four decades, engineering strategies like distributed processing also have added to the speed of logical devices for some amazing advances in the ability of computers to perform functional tasks.

 When a problem has large computational demands and there is a network of processors available, a programmer can utilize the computational power of many processors. The pro- grammer divides a problem so that pieces of the problem can be computed in parallel. It is common to see processors con- nected by local area networks. To effectively run a distri- buted program on a local area network as well as other inter- connection networks, a good queueing discipline must take into account that its processor and other processors have pieces of the same program. When several processes from the ssme or different distri- buted programs have been assigned to a processor in a distri- buted system, an important design question is how a proces- sor selects the next process to run. This problem has not been considered in a distributed environment. An interesting question arises: How do the processes at other processors and question arises: How do the processes at other processors and communication delays the system impact the selection of the next process to run? As a beginning study we investigated the standard queueing disciplines- frist come first serve, round robin fixed quantum, preemptive priority, and nonpreemptive priority- in a distributed environment. The study shows that the response time metric can differ by 50% with different choices of queueing disciplines of three problems.

 Another important question is under what conditions are substantial gains in performance achieved by an appropriate method of selection. Communication delays are a factor; thus a graph of the response time metric was plotted as communication delays varied for each of the three problems. Trends are observed in these graphs. 

The queueing disciplines were studied with three prob- lems that differ functionally and have different behavioral characteristics. The partial differential equation solver is based on an iterative grid technique that is similar to those used in multidimensional applications such as weather predic- tion, structural mechanics, hydrodynamics, heat transport, and radiation transport. The centralized monitor has the typical tree structure of hierarchically designed applications. The producer-consumer pairs represent a multiprogramming environment in the distributed system and each pair is representative of a large class of  problems.

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 diskful


• †If diskful, the private disk may be used for Paging and temporary files
  ... and system binaries
  ... and file caching
  Complete local file system (with remote mounting)
  Disk Usage Advantages Disadvantages

(diskless)

Low cost; easy hardware and software maint.; symmetry and flexibility

Heavy network usage; bottlenecks on file servers

Paging, temporary files	Reduces network load	High cost to purchase disks
Paging, temporary files, binaries	Reduces network load even more	High cost; updating binaries
Paging, temporary files, binaries, caching	Reduces network load even more; reduces load on file server	High cost; cache consistency
Full local file system	V. low network load; no need for file servers	Loss of transparency

Locating an idle processor: 

Issues 

• †What is an idle workstation?
  A workstation is idle if no user-initated 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?
  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 machine's "owner" comes back?

Do nothing, but what about performance for owner? Kill the cuckoo, but what about work done? Migrate the cuckoo - hard, hard, hard!
Always leave the machine as you found it... 

The Processor Pool Model 

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


• †Alleviates problem of migrating processes


• †Implicit assumption that file system is shared
  Processor Allocation


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


• †For processor pool, question is which processor to use for an incoming process General strategies


• †Migratory vs. Nonmigratory


• †Optimisation of CPU time vs. Optimisation of response time
  Design Issues for processor alocation algorithms


• †Deterministic vs. Heuristic algorithms


• †Centralised 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 maximising CPU usage


• †Coordinator manages centralised 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
  coordinator to allocate another CPU to the process


• †How 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 usage 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 process there. If 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 machine accepts process or probe limit is exceeded


• †C. Sender probes k machines for their loads. Sends process to machine with 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 work, or timer lapses


• †Better than previous algorithm when 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)