Service discovery middlewares allow users to find and use services through service discovery protocols without previous knowledge of the locations or characteristics of the services with minimum manual efforts in heterogeneous and ubiquitous environments. For this reason, in recently, many researchers have done the studies related on the service discovery middlewares and many papers dealing with this field have been published. However, when a number of service consumers request services to middle agents (e.g. matchmaker, broker, yellow page, blackboard, etc) within the service discovery middlwares, the middle agents does not guarantee efficient and rapid matching results because they only use a simple matching algorithm. In this paper, we address the issues of existing matching algorithms, and then propose a new matchmaking algorithm based on marriage matching algorithm of ATM network [1] to improve middle agents? performance, complementing shortcomings of existing matching algorithms. We also add a priority based matching to the new algorithms. Through this priority, important service request messages are processed faster than request messages that have low priorities. We expect the proposed matchmaking mechanism to increase users? satisfaction in dynamic environments.