一種高效的基于拍賣背包機制的移動Ａｇｅｎｔ調度策略

摘 要：在分析資源拍賣機制和操作系統分配CPU資源的調度策略基礎上，將NP類問題的背包問題和拍賣問題統一為拍賣背包問題，并以收入最大化為目標，提出一種將參與拍賣的Agent進行預處理的動態規劃算法。在調度開銷幾乎為0 ms的情況下，高效地實現了收入最大化。分析及試驗表明，提出的基于預處理方法的動態規劃策略更適合于移動Agent的有償調度，具有高效、實用、調度開銷小等特點。

關鍵詞：移動代理； 拍賣； 調度策略； 背包問題； 動態規劃

中圖分類號：TP393.07文獻標志碼：A

文章編號：1001-3695(2007)06-0052-03

移動Agent系統中眾多來訪Agent的調度策略對系統的性能有著直接的影響。當前的調度策略主要有兩種：①傳統的調度策略，如先來先分配策略、最短作業優先策略等；②引入市場機制和拍賣機制的調度分配策略［1，2］。這種策略下，移動Agent對資源的使用是有償的，因此各系統大多以收入最大化為目標來確定各來訪Agent的調度策略。由于是有償服務，該策略可有效地防止由來訪Agent所引起的拒絕服務攻擊。但上述策略存在一些共同缺點，如要修改底層操作系統的調度策略或修改虛擬機以及調度開銷問題。本文以模擬實際操作系統的進程/線程的CPU分配策略（即進程/線程調度策略）為前提，研究以最小的開銷規劃移動Agent的調度策略，進而在實現最大化收入的基礎上高效分配CPU資源。

1 進程/線程調度模型

CPU調度指的是在一組就緒的進程/線程中進行CPU分配。機器的通常狀態是：有多個就緒進程都在等待CPU變成可用，操作系統的調度策略必須為選擇哪個進程來執行定義準則。對特定進程而言，當CPU變為可用時，調度程序從屬于該進程的就緒線程中選擇一個來使用CPU。現代操作系統中的線程調度策略多采用多級反饋調度技術（如Windows、UNIX），試圖給那些需要很快響應的線程以很高的優先級，時間片為時鐘中斷間隔的倍數，在Windows NT/2000/XP機器中，時間片大約在20～200 ms［3］。因此不失一般性，這里建立的進程/線程調度仿真模型為：假定移動Agent系統進程獲得時間片（如將時間片定為50 ms）后，將在該時間片內一直執行各就緒的Agent線程隊列，直到時間片用完。這里就緒線程的調度先后順序即調度策略及開銷是本文研究的主要問題。

2 基于拍賣背包機制的移動Agent調度策略

拍賣機制作為一種市場交易機制存在已有數百年歷史，理論已較為成熟和完善。本文利用拍賣機制及背包問題的求解策略來研究移動Agent系統中的各Agent競爭CPU資源時的調度策略。

2.1 CPU拍賣協商協議

拍賣是實踐中廣泛采用的一種資源分配機制。由于拍賣在價格發現過程中起著重要的作用，大多用于拍賣品沒有固定的市場價值或賣方對市場價格不確定的情形。根據購買者出價的方式和拍賣品的數量，傳統拍賣可以劃分成四種方式，即英格蘭式拍賣、荷蘭式拍賣、最高價格封閉投標式拍賣和次高價格封閉投標式拍賣。根據不完全信息博弈理論，在基準拍賣模型中，拍賣方式無差別，賣者實現的價值完全相同。因此拍賣時的協商協議可采用任何一種拍賣方式實現。本文采用最高價格封閉投標式拍賣來描述CPU資源拍賣協商協議。考慮到操作系統及Java虛擬機的進程/線程調度機制，本文中CPU拍賣采用循環拍賣進程獲得的時間片方式。時間片的基本拍賣單位為毫秒的整數倍，最大不超過時間片長度（如100 ms）。每輪拍賣都以該時間片內可獲得的收入最大化為目標。具體的協商協議用有限狀態圖表示，如圖1、2所示。

協商的具體過程描述如下：協商中拍賣協商代理作為協商的發起者，首先宣布拍賣協商開始（Announce），從狀態Ss1轉到狀態Ss2，等待接收投標。投標方協商代理收到拍賣開始消息后，從狀態Sb1轉到狀態Sb2，選擇自己的投標策略投標，而后轉入Sb3狀態等待投標結果通知。當然在拍賣方等待時間到達前，如若悔標，需要給拍賣方發送撤標（Withdraw）消息。拍賣方等待時間到達前，如有投標或撤標的消息到來則響應相應要求，轉入Ss3狀態。對于投標者需根據其標值，利用優選策略選擇是否加入隊列。等待時間到達時，停止接收投標，并利用動態規劃算法對已接收的各投標計算拍賣方的最大收入（轉為Ss4狀態），確定相應的中標方。計算結束，從狀態Ss4轉到狀態Ss5，通知各投標方中標(Success)或失敗(Failure)，而后宣布此輪拍賣結束（進入Ss6）。當投標方協商代理收到Failure消息時，從狀態Sb3轉到狀態Sb5，此次協商失敗，可終止協商或調整投標策略等待下次投標。相反，當投標方協商代理收到Success消息時，狀態從Sb3轉到Sb6，協商成功結束。

2.2 CPU拍賣背包問題描述

2.3 拍賣背包問題的求解策略及改進策略

2.3.1 拍賣背包問題的求解策略

背包問題是計算機算法中一個經典的NPhard問題。解決0/1背包問題的方法有多種，有蟻群算法［4，5］、遺傳算法［6］等計算智能算法，也有貪婪法［7］和動態規劃法。現在解決拍賣問題常用的算法是遺傳算法、隨機算法等［7～9］智能算法。這些算法中計算智能算法和貪婪法不但無法得到問題的最優解，而且時間開銷太大，不適于規劃CPU時間片內的線程調度問題。而動態規劃法不但可以得到最優解，而且計算開銷小。因此這里使用動態規劃法來解決CPU時間片的拍賣背包問題。下面是對上述CPU拍賣背包問題的求解遞推公式：

V[j，c]=0V[j-1，c]max{V[j-1，c]，V[j-1， j-Sj]+Pj} j=0或c=0c0且c≥Sj

很明顯，計算該公式的每一項需要Θ(1)時間，算法的時間復雜度恰好是ΘnC。因此背包問題的最優解能夠在ΘnC的時間內和ΘC的空間內得到。

2.3.2 基于預處理的改進求解策略及計算開銷分析

3 算例

假設每次拍賣開始時，投標隊列的移動Agent的數目分別為100、200、300、400、500、600、700、800、900、1 000、2 000、3 000、4 000、5 000。執行時間為服從均勻分布的[0，50]的隨機數，出價為[0，1 000]的隨機整數。在配置為Intel Pentium 4 3.0 GHz CPU，512 MB內存的計算機環境下，分別執行10次，所得各結果取平均值，如圖3所示。

由圖3可知，Agent數量越大，該求解策略越具有優越性。由圖4可知，投標Agent的數量不超過1 000時，改進前后的算法均可在0 ms內計算完成。但超過1 000時，改進后的算法明顯優于改進前的算法，同時最大化收入不變。

4 結束語

本文在分析操作系統進/線程調度特點的基礎上，研究移動Agent系統中，移動Agent競爭CPU資源的拍賣背包問題。由上述分析及試驗表明，該調度策略具有高效、實用、開銷小等優點，既具有CPU資源調度要求開銷小的特點，又實現了移動Agent系統收入最大化的目標。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。