A Load Distribution Policy for A New Transcation Service Considering The Pre-Loaded Services
by
Sukanya Suranauwarat
Department of Computer Science, School of Applied Statistics, National Institute of Development Administration, Bangkok 10240, Thailand.
In this paper, we describe and evaluate our load distribution policy. This policy makes placement decisions for processes of each service in such a way that the estimated response time is optimized while the estimated throughput is in the range that the user desires. Our target service is a transaction service consisting of multiple processes that communicate with each other. Our target system is a distributed system consisting of workstations connected by a local area network. The outstanding feature of our policy is that it takes account of pre-loaded service, ones for which process allocation has already been determined before the newly arrived service. In other words, our policy tries to keep the performance of the pre-loaded services at a desirable level while the newly arrived service processes are loaded and run. We measured the response time and the throughput when the process allocation is
determined using our policy, and we compared them with those our policy estimates. The results show that our policy provides an appropriate process allocation, and that calculated results agree well with the measured ones.
Introduction
The advent of inexpensive microcomputers, powerful workstations, and wide-bandwidth networks caused distributed systems to become increasingly popular. One of the most important features of such systems is the possibility of achieving high performance by means of load distribution. Load distribution attempts to improve the performance of application programs by distributing their processes (i.e., the load) among the computers in a network.
The effect of load distribution depends on the load distribution policy. So far, many load distribution
policies (e.g., [1]-[9],[11]) have been proposed, most of which focused on the load on a single resource in a computer especially a CPU resource, even though processes usually require various types of resources for their execution. In this case, it may not be meaningful to assign an incoming I/O-bound process to a computer that the CPU is lightly loaded while the I/O resources it uses are not. In other words, an incoming I/O-bound process will not necessarily run faster on a more lightly loaded CPU, and it might even run slower if the I/O resources it uses are congested. Moreover, the previous studies [1]-[8] have demonstrated the performance benefit of their policies using simple workload and system models. For example, the workload consists of only CPU-bound processes and all the computers in a network are identical, which makes the comparison of the load among the computers easier since the information about the specifications of the computers and the network is not a concern, and thus the processes are simply assigned to the computers that have the least number of processes. Another example, only application programs that generate a single process are considered, thus the relation and interaction between processes of the same program is not a concern.
Therefore, the policies mentioned above are not suitable for the programs that are widely used in business and require have high performance like transaction processing programs, because the execution of each transaction processing program usually causes the creation and the execution of multiple cooperative processes which require various types of resources and interprocess communication (IPC) in order to carry out each transaction. Hence, we propose a load distribution policy for transaction processing programs on distributed systems consisting of heterogeneous workstations connected by a local area network (LAN). Unlike previous policies, our policy takes
into account the information about the specifications of the computers and the network and the information about the execution behavior of the programs, i.e., the resource consumption behavior of each process and its interaction with other processes (i.e., IPC), in making placement decisions for each process. To be more specific, our policy estimates the response time and the throughput of any transaction service using the information about the specifications of the computers and the network and the information about the execution behavior of the programs, and distributes each process of the service in such a way that the estimated response time is optimized while the estimated throughput is in the range that users desire (i.e., our policy allows users to set the lower and the upper limits of the throughput).
However, when some services have already been executed on the distributed system (pre-loaded services), it becomes harder to estimate the response time, because the correlation between the newly arrived service (new service) and the pre-loaded services has to be considered. For example, consider a situation in which a process of a new service is assigned to a computer. Beginning an execution of a new process on a computer requires reallocation of the computing resource (such as the CPU or memory) for each process running on the computer. This will affect the time it takes to complete one transaction in each process, and thus affecting the processes of the same services running on the other computers, because the processes use IPC. Consequently, just one new process affects all the other processes in the system. The effect spreads through the system until all the processes on the system are stable. This makes it difficult to take account of the pre-loaded services in the calculation. We name this problem the process chain problem. As a solution, we introduce the bottleneck coefficient into our load distribution policy.
The rest of this paper is organized as follows. Section 2 briefly discusses the related work. Section 3 describes the model of our system. Section 4 describes the method of estimating response time of a transaction service. Section 5 describes our load distribution policy. Section 6 describes our experiments and explains the results we obtained. Section 7 offers our conclusions and future work.
Related Work
Load distribution methods that have been proposed in previous studies [1]-[8] can be classified roughly
into two types: (1) those based on the centralized dispatcher model [1]-[3], and (2) those based on the autonomous dispatcher model [4]-[8]. In the centralized dispatcher model, just one computer called dispatch server makes the placement decisions for all processes. This model is simple but not scalable, because a dispatch server might end up being a bottleneck of an entire system. In the autonomous dispatcher model, each computer in the system can make placement decisions for the processes submitted to it, which leads to a robust system from the viewpoint of fault tolerance. However, each computer has to collect load information from other computers, which may cause the network to get clogged up. Besides, in these models, the target services are the services that consist of a single process, which has no IPC [1]-[8]. Therefore, they are not suitable for handling transaction services with multiple processes.
Load distribution methods that support multiple processes on a multiprocessor system have also been
reported [9]. However, their system models are very different from those of distributed systems.
For the discussion of load balancing, simplified models of distributed systems are usually adopted [1]-
[9]. For example, no network latency [4][5][9], or no I/O is considered [1]-[9]. Another example, all the computers in a network are assumed to be homogeneous [4][7], since it is easier to make the comparison of the load among the computers and thus the processes are simply assigned to the computers that have the least number of processes.
Therefore, the methods mentioned above are not suitable for transaction processing programs because the execution of them causes the creation and the execution of multiple processes which require various types of resources including I/O and need to communicate with one another. Also, practically and naturally, computers in the distributed systems tend to be heterogeneous.
Previous methods proposed in [4][6][8][10] make the placement decisions for processes in a similar way to ours, using the following steps: (1) select a process to reallocate, (2) select a workstation for the selected process, and (3) decide whether or not to reallocate. The details of each step vary from method to the method and can be found in the corresponding papers. Our method differs from the previous ones in that it takes account of preloaded services to estimate response times and throughputs more precisely. Exact estimation is very important, because an inaccurate estimation may cause unpredictable performance degradation [10][12]. In Section 6, we will show that taking account of pre-loaded services allows more precise estimation.
Selecting a process to reallocate can be done either before beginning its execution or after its execution
has begun. Our method and those mentioned above are the former type, while the methods based on the latter type can be found in [13]-[15], for example.
Download Full Text
| Create Date : 30 มิถุนายน 2550 |
| Last Update : 2 กรกฎาคม 2550 12:53:49 น. |
|
1 comments
|
| Counter : 794 Pageviews. |
 |
|
ฝากข้อความหลังไมค์
Rss Feed
ผู้ติดตามบล็อก : 7 คน [
