負載調度演算法

⑴ 幾種進程調度演算法分析

前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。 ，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類： 批處理系統中的調度演算法， 代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。 互動式系統中的調度演算法， 代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。 實時系統中的調度演算法 ，代表調度演算法有：速率單調調度、最早最終時限優先調度。 下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。 保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。 彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。 彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。 速率單調調度 速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。 速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。 速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。 最早最終時限優先調度 最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。 由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。

⑵ 軟體架構中，負載均衡有哪些調度演算法

謝邀！
負載均衡調度演算法也叫負載均衡方法有很多種，下面以使用比較廣的nginx為例說說軟體負載均衡的調度演算法：
nginx默認的調度演算法，按照時間順序逐一分配後台伺服器
在server後加weigth，weight值越高，後台伺服器分配概率越大，下圖是說ip為102的後台服務分配概率是ip為101後台服務的兩倍
按照訪問ip的hash分配，增加ip_hash關鍵字，同一ip訪問相同的後台服務
按照訪問url的hash分配，增加url_hash關鍵字，同一url訪問相同的後台服務
按照最少連接數方式分配，增加least_conn關鍵字，哪個後台服務連接數少就分配哪個
按照最短響應時間分配，增加fair關鍵字，響應時間短的後台服務優先分配

⑶ 簡述負載均衡集群中常見的調度演算法及原理（5種以上）

1.LVS負載均衡集群介紹

2. LVS介紹

3. IPVS發展史

4.LVS體系結構與工作原理簡單描述

5.LVS的基本工作過程

6.LVS的三種工作模式：

6.1NAT模式-網路地址轉換

6.2TUN模式

6.3DR模式（直接路由模式）

⑷ nginx代理負載均衡的調度演算法都有哪些

利用nginx作反向代理apache直接暴露給外界;同nginx主要做負載均衡提升系統並發承載能力nginx處理靜態內容apache處理態內容加快站點訪問速度建議解nginx反向代理

⑸ JAVA中實現多線程負載平衡演算法

將請求放到一個全局的隊列中去。每個子線程不斷地從隊列中取出請求並處理請求，如果隊列中沒有請求則子線程等待。

⑹ 伺服器做負載均衡有什麼優勢怎麼計算的

西部數碼負載均衡EasySLB服務，即在多台雲主機間實現應用程序流量的自動分配。可實現故障自動切換，提高業務可用性，並提高資源利用率。
西部數碼負載均衡只需要在控制台一鍵即可添加後端伺服器，系統將自動設置好相關路由與網關，讓負載均衡集群的搭建變得輕而易舉

⑺ 多台伺服器負載均衡，怎麼選擇

一般用的就用簡單的輪詢就好了
調度演算法
靜態方法：僅根據演算法本身實現調度；實現起點公平，不管伺服器當前處理多少請求，分配的數量一致
動態方法：根據演算法及後端RS當前的負載狀況實現調度；不管以前分了多少，只看分配的結果是不是公平
靜態調度演算法(static Sche)（4種）:
(1)rr (Round Robin) :輪叫,輪詢
說明：輪詢調度演算法的原理是每一次把來自用戶的請求輪流分配給內部中的伺服器，從1開始，直到N(內部伺服器個數)，然後重新開始循環。演算法的優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。缺點：是不考慮每台伺服器的處理能力。
(2)wrr (Weight Round Robin) :加權輪詢(以權重之間的比例實現在各主機之間進行調度)
說明：由於每台伺服器的配置、安裝的業務應用等不同，其處理能力會不一樣。所以，我們根據伺服器的不同處理能力，給每個伺服器分配不同的權值，使其能夠接受相應權值數的服務請求。
(3)sh (Source Hashing) : 源地址hash實現會話綁定sessionaffinity
說明：簡單的說就是有將同一客戶端的請求發給同一個real server,源地址散列調度演算法正好與目標地址散列調度演算法相反，它根據請求的源IP地址，作為散列鍵（Hash Key）從靜態分配的散列表找出對應的伺服器，若該伺服器是可用的並且沒有超負荷，將請求發送到該伺服器，否則返回空。它採用的散列函數與目標地址散列調度演算法的相同。它的演算法流程與目標地址散列調度演算法的基本相似，除了將請求的目標IP地址換成請求的源IP地址。
(4)dh : (Destination Hashing) : 目標地址hash
說明：將同樣的請求發送給同一個server,一般用於緩存伺服器，簡單的說，LB集群後面又加了一層，在LB與realserver之間加了一層緩存伺服器，當一個客戶端請求一個頁面時,LB發給cache1,當第二個客戶端請求同樣的頁面時，LB還是發給cache1,這就是我們所說的，將同樣的請求發給同一個server,來提高緩存的命中率。目標地址散列調度演算法也是針對目標IP地址的負載均衡，它是一種靜態映射演算法，通過一個散列（Hash）函數將一個目標IP地址映射到一台伺服器。目標地址散列調度演算法先根據請求的目標IP地址，作為散列鍵（Hash Key）從靜態分配的散列表找出對應的伺服器，若該伺服器是可用的且未超載，將請求發送到該伺服器，否則返回空。
動態調度演算法(dynamic Sche)（6種）:
(1)lc (Least-Connection Scheling): 最少連接
說明：最少連接調度演算法是把新的連接請求分配到當前連接數最小的伺服器，最小連接調度是一種動態調度短演算法，它通過伺服器當前所活躍的連接數來估計伺服器的負載均衡，調度器需要記錄各個伺服器已建立連接的數目，當一個請求被調度到某台伺服器，其連接數加1，當連接中止或超時，其連接數減一，在系統實現時，我們也引入當伺服器的權值為0時，表示該伺服器不可用而不被調度。此演算法忽略了伺服器的性能問題，有的伺服器性能好，有的伺服器性能差，通過加權重來區分性能，所以有了下面演算法wlc。
簡單演算法：active*256+inactive (誰的小，挑誰)
(2)wlc (Weighted Least-Connection Scheling):加權最少連接
加權最小連接調度演算法是最小連接調度的超集，各個伺服器用相應的權值表示其處理性能。伺服器的預設權值為1，系統管理員可以動態地設置伺服器的許可權，加權最小連接調度在調度新連接時盡可能使伺服器的已建立連接數和其權值成比例。由於伺服器的性能不同，我們給性能相對好的伺服器，加大權重，即會接收到更多的請求。
簡單演算法：（active*256+inactive）/weight（誰的小，挑誰）
(3)sed (shortest expected delay scheling):最少期望延遲
說明：不考慮非活動連接，誰的權重大，我們優先選擇權重大的伺服器來接收請求，但會出現問題，就是權重比較大的伺服器會很忙，但權重相對較小的伺服器很閑，甚至會接收不到請求，所以便有了下面的演算法nq。
基於wlc演算法，簡單演算法：（active+1)*256/weight （誰的小選誰）
(4).nq (Never Queue Scheling): 永不排隊
說明：在上面我們說明了，由於某台伺服器的權重較小，比較空閑，甚至接收不到請求，而權重大的伺服器會很忙，所此演算法是sed改進，就是說不管你的權重多大都會被分配到請求。簡單說，無需隊列，如果有台real server的連接數為0就直接分配過去，不需要在進行sed運算。
(5).LBLC(Locality-Based Least Connections) :基於局部性的最少連接
說明：基於局部性的最少連接演算法是針對請求報文的目標IP地址的負載均衡調度，主要用於Cache集群系統，因為Cache集群中客戶請求報文的目標IP地址是變化的，這里假設任何後端伺服器都可以處理任何請求，演算法的設計目標在伺服器的負載基本平衡的情況下，將相同的目標IP地址的請求調度到同一個台伺服器，來提高伺服器的訪問局部性和主存Cache命中率，從而調整整個集群系統的處理能力。
(6).LBLCR(Locality-Based Least Connections with Replication) :基於局部性的帶復制功能的最少連接
說明：基於局部性的帶復制功能的最少連接調度演算法也是針對目標IP地址的負載均衡，該演算法根據請求的目標IP地址找出該目標IP地 址對應的伺服器組，按「最小連接」原則從伺服器組中選出一台伺服器，若伺服器沒有超載，將請求發送到該伺服器；若伺服器超載，則按「最小連接」原則從這個集群中選出一台伺服器，將該伺服器加入到伺服器組中，將請求發送到該伺服器。同時，當該伺服器組有一段時間沒有被修改，將最忙的伺服器從伺服器組中刪除， 以降低復制的程度。

⑻ 如何實現負載均衡，哪些演算法可以實現

1、輪詢調度

輪詢調度演算法就是以輪詢的方式依次將請求調度到不同的伺服器，即每次調度執行i = (i + 1) mod n，並選出第i台伺服器。演算法的優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。

2、最小連接調度

最小連接調度演算法是把新的連接請求分配到當前連接數最小的伺服器。最小連接調度是一種動態調度演算法，它通過伺服器當前所活躍的連接數來估計伺服器的負載情況。

在實際實現過程中，一般會為每台伺服器設定一個權重值，這就是加權最小連接

3、 基於局部性的最少鏈接(LBLC)

基於局部性的最少鏈接調度(以下簡稱為LBLC)演算法是針對請求報文的目標IP地址的負載均衡調度，目前主要用於Cache集群系統，因為在Cache集群中客戶請求報文的目標IP地址是變化的。

LBLC調度演算法先根據請求的目標IP地址找出該目標IP地址最近使用的伺服器，若該伺服器是可用的且沒有超載，將請求發送到該伺服器; 若伺服器不存在，或伺服器超載或有伺服器處於其一半的工作負載，則用「最少鏈接」的原則選出一個可用的伺服器，將請求發送到該伺服器。

4、帶復制的基於局部性最少鏈接(LBLCR)

帶復制的基於局部性最少鏈接調度以下簡稱為LBLCR)演算法也是針對目標IP地址的負載均衡，目前主要用於Cache集群系統。它與LBLC演算法的不同之處是它要維護從一個目標IP地址到一組伺服器的映射，而LBLC演算法維護從一個目標IP地址到一台伺服器的映射。

LBLCR調度演算法將「熱門」站點映射到一組Cache伺服器(伺服器集合)，當該「熱門」站點的請求負載增加時，會增加集合里的Cache伺服器，來處理不斷增長的負載; 當該「熱門」站點的請求負載降低時，會減少集合里的Cache伺服器數目。

5、目標地址散列調度

目標地址散列調度演算法是針對目標IP地址的負載均衡，但它是一種靜態映射演算法，通過一個散列(Hash)函數將一個目標IP地址映射到一台伺服器。

目標地址散列調度演算法先根據請求的目標IP地址，作為散列從靜態分配的散列表找出對應的伺服器，若該伺服器是可用的且未超載，將請求發送到該伺服器，否則返回空。

6、 源地址散列調度

和目標地址散列調度類似，唯一的區別是按照源地址為散列函數的散列鍵。

⑼ 接觸過的Nginx的負載均衡演算法有哪些

Nginx 官方默認的幾種負載均衡的演算法
①Round-Robin RR輪詢（默認） 一次一個的來（理論上的，實際實驗可能會有間隔）
②weight 權重 權重高多分發一些 伺服器硬體更好的設置權重更高一些
③ip_hash 同一個IP，所有的訪問都分發到同一個web伺服器
第三方模塊實現的調度演算法 需要編譯安裝第三方模塊
④fair 根據後端伺服器的繁忙程度 將請求發到非繁忙的後端伺服器
⑤url_hash 如果客戶端訪問的url是同一個，將轉發到同一台後端伺服器
看你在學習Nginx的知識，推薦你去看黑馬程序員視頻庫，裡面有它的學習視頻，講解的很詳細哦！

⑽ 怎麼證明負載調度演算法是np-hard問題

什麼是NP問題
概念1:
在計算機學科中，存在多項式時間的演算法的一類問題，稱之為P類問題；而像梵塔問題、推銷員旅行問題、（命題表達式）可滿足問題這類，至今沒有找到多項式時間演算法解的一類問題，稱之為NP類問題。
概念2:
多項式時間（Polynomial time）在計算復雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一復雜度類，此類包括可於此機器以多項式時間求解的問題。

以數學描述的話，則可說m(n) = O(n)，此n為一常數值（依問題而定）

拿推銷員旅行問題為例，假設推銷員亨利有向6個城市推銷公司產品的任務，並規定了一個旅行預算。他手中有一張航班票價表，他要從A城開始走遍圖中的6個城市後返回A城，並且不超出預算，請你幫他找出應走的路線。如果給出的預算寬裕，則任務很簡單；如果預算比較緊張，你就得認真設計路線了。你得考慮每一種可能的次序，以使旅費最少。
而NP問題中最困難的問題稱之為NP完全問題(NP-complete)，已經證明的包括：電話網路的最優幾何設計、格子棋的最佳走法。根據庫克定理，任意一個NP完全問題如果能夠在多項式時間內解決，則所有的NP問題都能在多項式時間內解決，而至今這一問題仍無答案。

什麼是非確定性問題呢？有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出。比如，找大質數的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質數應該是多少呢？這樣的公式是沒有的。再比如，大的合數分解質因數的問題，有沒有一個公式，把合數代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。
這種問題的答案，是無法直接計算得到的，只能通過間接的「猜算」來得到結果。這也就是非確定性問題。而這些問題的通常有個演算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你「猜算」的答案正確與否的演算法，假如可以在多項式時間（多項式時間： 運行時間最多是輸入量的多項式函數）內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。
完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結果。但是這樣演算法的復雜程度，是指數關系，因此計算的時間隨問題的復雜程度成指數的增長，很快便變得不可計算了。人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在一個確定性演算法，可以在指數時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。
解決這個猜想，無非兩種可能，一種是找到一個這樣的演算法，只要針對某個特定NP完全問題找到一個演算法，所有這類問題都可以迎刃而解了，因為他們可以轉化為同一個問題。另外的一種可能，就是這樣的演算法是不存在的。那麼就要從數學理論上證明它為什麼不存在。
前段時間轟動世界的一個數學成果，是幾個印度人提出了一個新演算法，可以在多項式時間內，證明某個數是或者不是質數，而在這之前，人們認為質數的證明，是個非多項式問題。可見，有些看來好象是非多項式的問題，其實是多項式問題，只是人們一時還不知道它的多項式解而已。