As service-oriented architectures (SOA) and web-services become widely employed in modern software solutions, their performance emerges as a pressing concern, which becomes even more urgent with the emergence of multi-core processors. This dissertation exploits parallel and concurrent programming techniques to bring the performance enhancement of multi-core processors to the service-oriented software, and we tackle the challenge from two pillars of SOA: XML processing and service orchestration. As the standard format of data and messages, XML plays a pivot role in SOA. However, its processing is the fundamental performance bottleneck of SOA. In the first part of this dissertation we present ParaXML, a general data-parallel XML processing model designed for multi-core processors. ParaXML treats the XML processing task as the parallel traversal algorithm over the XML document structure and it adopts a work-stealing mechanism to dynamically partition the XML document in a balanced manner. In addition, ParaXML introduces a stealing-tracing mechanism for reducing results and some performance tuning techniques particularly designed for large XML documents. To show the effectiveness of ParaXML model, we demonstrate our parallel algorithms of XML searching and serialization. We will also present a novel two-pass-scanning based parallel XML parsing algorithm. The empirical study shows that our parallel algorithms substantially improve the performance and scale well on the multi-core processor. As the service orchestration is becoming a dominant composition paradigm in SOA, in the second part of this dissertation we investigate the asynchronous concurrent programming technology for building a scalable service-orchestration runtime on multi-core processors. We propose a service-orchestration library (SOX), which provides a set of fine-grained library API for service-orchestration constructs derived from web-services workflow language (WS-BPEL). SOX library implements these orchestration-constructs by mapping WS-BPEL concurrency semantics into asynchronous events and Join-patterns. The event-driven architecture empowers the orchestration run-time to efficiently handle the massive concurrency on the multi-core processor. Meanwhile the library enables the user to write the asynchronous concurrent workflow in an intuitive serial programming model, thus greatly reducing the complexity of developing the large-scale service-orchestration program. Our experiments shows that services together with the scalable orchestration runtime is a reasonable programming model which can effectively exploit multi-scale resources from multi-core chips to the cluster of computers.