The Influence of Domain and Interdomain Process Migration on the Performance of Parallel Ex

Distributed Systems1

Damien De Paoli and Andrzej Goscinksi

(ddp, ang@deakin.edu.au)

School of Computing and Mathematics

Deakin UniversityGeelong, Victoria 3217

November 9, 1997

Abstract

This paper presents domain and interdomain process migration and its influence on theperformance of parallel execution on distributed systems based on RHODOS’ process migra-tion facility and its interaction with load balancing in RHODOS. In RHODOS, we propose theuse of coarse grained parallelism and subsequently migrate fragments of parallel code to bal-ance the system load. These parallel code fragments can be migrated between two machines onthe same Local Area Network (LAN), i.e. within the one domain, or on two LANs connectedby a Wide or Metropolitan Area Network (WAN/MAN). By considering the likely structure ofour load balancing design, it was noted that most fragments being migrated will be within theone communication domain. In this paper we show that migrating within the one communica-tion domain allows several performance enhancements to be used, which have yielded a sixtyper cent decrease in migration time.1. Introduction

Parallel execution has come under increasing scrutiny by the research community. By sepa-rating a given task into several fragments that can be executed in parallel, the task can be com-pleted in a shortest time and can make better use of the available resources on its host.

The benefits of being able to use multiple (cheap) workstations instead of one (expensive)powerful mainframe or supercomputer to do the same tasks has led to ever increasing attentionfrom the research community to the field of load balancing. This is especially true, as manybusinesses and institutions already have many workstations linked up via a network. If loadbalancing does become an effective tool, then without purchasing any extra hardware, thecomputational power for each user will be noticeable improved. The benefits of parallel execu-1. This work was partly supported by the Australian Research Council Grant A49232429 and theDeakin University Research Grant 0504010151

tion when combined with load balancing increase the capability to improve the throughput fora computer system as a whole.

Static allocation can be used to place fragments of programs onto idle or lightly loadedcomputers. However, simply using static allocation can be too slow to take advantage of fluc-tuating load changes. Barak and Laden demonstrated how with process migration, PVM canyield performance improvements of hundreds of percents, over PVM without process migra-tion [Barak and Laden 95].

In general, process migration is transferring a running process from a source machine to adestination machine. Importantly, these two machines can be on the same Local Area Network(LAN), i.e. within the one domain, or on two LANs connected by a Wide Area Network(WAN), i.e., across domains. In theory, a process can be migrated over extraordinary distances(as long as both machines are running the same distributed operating system). Of course, if anoperating system is attempting to balance the load it is more likely to choose a machine that isin the same domain, rather than go afield for a destination machine. In fact, in RHODOS, ourload balancing design uses a flat grouping if the number of computers is small and a hierarchi-cal grouping if the number of computers is large, such that the load on any one domain is bal-anced and only when each machine in the domain is over the load threshold, then processes aremigrated between these domains.

This paper focuses on the implications of migrating processes between machines within asingle domain, and between machines of different domains and shows how exploitation ofthese situations has yielded a significant speed difference when migrating a process.

In Section 2, a general introduction to process migration within various domains is pre-sented. Section 3 discusses the ResearcH Oriented Distributed Operating System (RHODOS)architecture, with special interest on the process migration facility. Section 4 presents the test-ing undertaken and results obtained for process migration within and across domains. Finally,Section 5 concludes this paper.2. Process Migration

The task of balancing the load of a distributed system requires each host to collect dataabout its local host, and determine whether or not it is overloaded. If the host is overloaded,then a process is chosen to be migrated to a new computer, the destination machine. Once thecandidate process and destination machine have been chosen, the Migration Manager cantransfer the candidate process to the destination. In general, the migrant process’ address spaceand state must be transferred, whilst any resources the process has must also be handled, e.g.,files and communication end points.

Each host can determine if it is overloaded by communicating with other hosts. However,such connectivity between these hosts does not scale to larger systems. Thus, one of host willbe a master to the others, so that a group of machines have one entity that monitors their loadas a whole. In general, each domain has several computers in the one communication domain.As an example, at our University the School of Computing is on a separate LAN to each ofthe other schools, and in fact has several LANs within the school. Each set of machines on oneLAN are ideal candidates for a given domain. In RHODOS, our design follows such a course,and we felt that careful consideration of such an architecture would lend itself to optimisationsthat would increase the overall system throughput. Each of these domains would contain aserver that has an accurate picture of the resources and load on each of the machines in thedomain. However, in such environments we must deal with the fact that such groups can bemade up of heterogeneous computing resources. This indicates the need to use some form ofresource discovery to determine which computing resources (if any) are capable of accepting a

migrant process from within a different communication domain, as shown in Figure 1. Theresults of our work show that resource discovery could be easily provided by a Trader, which isa server combining both attributed naming and resource management [Ni and Goscinski 94].This structure scales well, as each Trader manages the load for a group of machines, and theTraders can communicate together to manage the load for the system. Of course, determininghow large these groups of computers are is a difficult task. Certainly, one factor in whether anumber of computers will be considered a group, is whether they are on the same Local AreaNetwork.

When messages are sent within the one domain, there is no need to use routing informationand the error rate of the media is generally low. This allows within domain messages to bemanaged with a reduced protocol stack. The opposite is the case with across domain messages,these messages require routing information and error rates are much higher. As process migra-tion requires data to be sent between machines on different LANs connected by a MAN/WAN,process migration itself is executed under these conditions, i.e., a full protocol stack must beused when migrating outside one communication domain.

Domain 1ResourceDiscoveryTraderTraderDomain 2GlobalSchedulerMigrationManagerGlobalSchedulerMigrationManagerWithinDomainMigrationGlobalSchedulerMigrationManagerGlobalSchedulerMigrationManagerGlobalSchedulerMigrationManagerGlobalSchedulerMigrationManagerAcrossDomainMigrationTraderDomain 3GlobalSchedulerMigrationManagerGlobalSchedulerMigrationManagerGlobalSchedulerMigrationManagerFigure 1 Interaction between different communication domains3. Migration in RHODOS

RHODOS is a modern message passing microkernel based operating system, that uses theclient server model. The microkernel (Nucleus) performs the basic functions of interrupt han-dling, local interprocess communication, context switching, and page handling. The policiesthat govern these functions are embodied in kernel servers with the support of system serversto provide the full functionality of a traditional operating system (Figure 2). The RHODOSsystem was also designed as a testbed to compare and measure different algorithms and theirimpact upon distributed systems. Using a microkernel in conjunction with a client/server inter-face allows RHODOS to be flexible and as such various modules can be removed or replacedeasily [De Paoli, et al 95].

As shown in Figure 2, the Migration Manager is considered a kernel server, i.e., it has priv-ileges to alter kernel data. In a typical migration scenario, the Global Scheduler (GS) obtainsinformation from the Data Collection Manager (DCM) to determine the load of its host. If theload is high enough, then the Global Scheduler will find a destination.

USER — Application — OS ProcessesLibrary Calls and RoutinesLIBRARIES

System CallsNameServerNetworkManagerProcessManagerInterruptHandlingAuthenticationServer/AgentIPCManagerMemoryManagerLocalIPCFileServerMigrationManagerSerialDriverGlobalSchedulerData CollectionManagerEthernetDriverContextSwitchingTraderRemoteExecutionManagerTerminalDriverPageHandlingSYSTEMSERVERSAPPLICATIONS

KERNELSERVERS

THENUCLEUS

Figure 2 The RHODOS Architecture

However, if the load of all of the machines within the domain are high, then the processmust be migrated to another domain. In RHODOS we have a Trader process that maintainsinformation about the physical resources within a domain [Ni and Goscinski 94]. For example,each machine has an entry with: the type of processor, the version of the operating system it isrunning, the amount of memory, whether it has a disk, etc. which is stored as a set of attributes.Cooperation between the Traders allows the determination of a suitable destination in a differ-ent domain.

Once the Global Scheduler has found a destination, it chooses a candidate process formigration, then the Global Scheduler informs the Migration Manager of which process tomigrate where. The Migration Manager then (directly) uses the services of the Process, Mem-ory, IPC Managers and (indirectly) the Network Manager to migrate the process [De Paoli 93],see Figure 3.

Each of the Process, Space and IPC Managers must create messages about the migrant proc-esses’ resource(s) and transfer these messages to their peer entities on the destination compu-ter. As processes can be migrated, their communication end points can migrate around the

system, and as such there is a need to maintain transparent communication to the migratedprocesses. In RHODOS, this is the IPC Manager’s task.

The network manager module provides the services of the Transport, Network and DataLink Layers of the OSI/ISO Reference model. In particular, the Transport layer is supported bythe RHODOS Reliable Datagram Protocol (RRDP) and the Network layer is supported by theInternet Protocol (IP). In RHODOS, the Data Link Layer conforms to IEEE 802.3 (connection-less service) and is supported by our Lance ethernet driver. RHODOS has the capability ofaccessing the functionality of each protocol layer separately [Joyce, et al 95].

When a migration request comes in from the Global Scheduler, the destination machine isone of the parameters of the migration request. Thus while the migration is being performedcommunication transparency (to the destination for the migrating process) has been main-tained automatically. Once the process migration operation has been completed, the MigrationManager enlists the aid of the IPC Manager to maintain transparent communications with themigrant process.

WAN, MANor LAN

GlobalSchedulerMigrate ProcessGlobalSchedulerMigrate ProcessTransferAddress SpaceSpaceManagerMigrationManagerTransferProcessStateProcessManagerTransferPorts/MessagesIPCManagerTransferAddress SpaceSpaceManagerMigrationManagerTransferProcessStateProcessManagerTransferPorts/MessagesIPCManagerFigure 3 Interaction of Global Scheduler, Migration, Space, Process and IPC ManagersProcess migration needs reliability to ensure that only one process can exists on one hostafter a migration has completed. In RHODOS, this reliability is ensured by utilising a transac-tion oriented approach to process migration, with a commit message being reliably sent to con-firm (or rollback) the migration operation. Hence, there is a high level protocol between theMigration Managers and as such, when migrating a process there is a duplication of reliability,hence the transport layer is not required. When migrating a process within the one communica-tion domain, we are migrating within the one network, and hence the network layer is also notrequired. With all these points in mind, one can see that migrating within the one communica-tion domain can be performed with simply the Data Link and Physical Layers to allow mes-sage delivery. Due to RHODOS’ flexibility, the full protocol stack can be used if processes aremigrated across communication domains, or the reduced protocol stack can be used for processmigration within the one communication domain.

4. Performance of Process Migration

To assess the influence of communication domain on the performance of process migrationtesting was conducted on a pair of Sun 3/50s were used. A user process that had a one hundredkilobyte address space was used for the migrant process. This process simply incremented aninteger indefinitely, whilst printing out the current total every few million iterations. The print-ing of the counter passes through the Device Manager via local IPC. The process’ addressspace was migrated by transferring the dirty pages directly to the destination computer.

The average time to migrate a 100 Kilobyte process within the same domain was 235.9 mswith a standard deviation of 0.5 ms. The average time to migrate a 100 Kilobyte process acrosscommunication domains was 371.8 ms with a standard deviation of 1.8 ms, which is a per-formance increase of approximately sixty per cent., these results are summarised in Table 4.1.Note as mentioned in Section 3, RHODOS’ process migration utilises a transaction basedapproach which requires a reliable message to be passed between the migration managers. Asreliability is provided by RRDP, this message must pass through the protocol stack whichresults in an approximate increase of five per cent, and in future versions this added overheadwill be addressed.

Table 4.1 The Performance of Domain and Interdomain Process Migration

Time to migrate a100K processWithin one domainAcross domain235.9 ms371.8 msStandardDeviation0.5 ms1.8 ms5. Conclusion

By carefully considering the likely environment for parallel execution in conjunction withload balancing, a number of interesting conclusions can be drawn. Notably, that a full protocolstack is not required to migrate a process within the one communication domain, and thatresource discovery will be needed to determine available resources amongst different commu-nication domains.

By taking advantage of this situation, the time taken to migrate a process in the RHODOSdistributed operating system has decreased from 371.8 ms to 235.9 ms, which represents a sub-stantial gain in performance. On the other hand it is also possible to migrate long running proc-esses to other domains to improve the performance of parallel execution in a distributedsystem.

One obvious implication of this work, is that parallel fragments of a process that aremigrated should be migrated within the one communication domain not only to achieve betterperformance for the migrated fragment, but also as any fragment migrated across domains cancause a considerable delay to any other fragments awaiting its completion. Thus, if fragmentsare to be migrated across domains, careful consideration should be given to which fragmentsare chosen so as to minimise the impact on the parallelised process execution time.

Acknowledgments

The authors would like to thank Mr. Philip Joyce for the implementation and his assistancewith the descriptions of the protocols mentioned in this paper.References

[Barak and Laden 95]A. Barak and O. Laden. Performance of PVM with the MOSIX

Preemptive Process Migration. Submitted to the Parallel and Distributed SystemsConference, Washington DC.

[De Paoli 93]D. De Paoli. The Multiple Strategy Process Migration for RHODOS: The

Logical Design. Technical Report TR C93/37, Deakin University, Australia.

[Joyce, et al 95]P. Joyce, D. De Paoli, A. Goscinski and M. Hobbs. Implementation and

Performance of the Interprocess Communications Facility in RHODOS. Submittedto the International Conference on Networks SICON/ICIE’95, June.

[De Paoli, et al 95]D. De Paoli, A. Goscinski, M. Hobbs and G. Wickham. The RHODOS

Microkernel, Kernel Servers and Their Cooperation.IEEE First InternationalConference on Algorithms And Architectures for Parallel Processing, Brisbane,April.

[Ni and Goscinski 94]Y. Ni and A. Goscinski. Trader Cooperation to Enable Object Sharing

Among Users of Homogenous Distributed Systems.Computer Communications,Vol. 17, No. 3.