Distributed applications are increasingly being built by Web services. This paper explores a dynamic service execution technique on virtual machines to exploit parallelism of service-based applications. The Dynamic service execution technique is able to determine data dependence of service invocations at run-time and executes independent service invocations concurrently with the help of stateless property of Web services. Based on this technique, we design and implement a virtual machine-based runtime environment called Abacus Virtual Machine (AVM). On AVM, service-based applications are programmed in a conventional, sequential programming model, which involves no extra parallel programming complexity. At the same time AVM also need to make balancing between the goal of exploiting parallelism and the cost brought by the dynamic service execution. Our experiments show that the cost is no more than 9% of CPU time and 10% memory cost. We believe that the penalty is acceptable for the benefits that AVM provides.