動態資源分配演算法常見問題

『壹』 操作系統存儲器動態分區分配的(快速適應演算法)問題

這里的分割指的是：如果空閑分區大小為8k，而程序所佔有的大小隻有6k，對於一般的分配演算法，會將空閑分區劃分成一個6k和一個2k，然後把6k分配給程序，把2k的重新加入到空閑分區鏈。而快速適應演算法會直接把8k都分配給程序。文中說的不會產生內存碎片指的是外碎片，而那空餘的2k屬於內碎片。

『貳』 java應用程序中如何動態的分配CPU資源

方案選擇
在考慮動態分配CPU資源實施方案時，往往有以下兩點要求：

1. 須充分利用現有硬體資源，在系統空閑時，讓低優先順序任務也能夠得到系統所能給予最快響應。

2.當硬體資源超負荷運行時，雖然系統中有大規模、多數量任務不能處理，但它不應受影響，而能夠順利處理那些能夠被處理、最重要高優先順序任務。

多任務系統要用多線程實現最簡單方法就是將線程和任務一一對應，動態調整線程優先順序，利用線程調度來完成CPU資源在不同任務間動態分配。這種思路在以前使用本地化代碼(Native Code)，充分利用特定硬體和操作系統技巧基礎上是基本可行。但在跨平台Java環境中，這個思路對僅有小規模任務數簡單系統才可行，原因有以下兩點：

1. Java線程雖然在編程角度(API)是與平台無關，但它運行效果卻和不同操作系統平台密切相關。為了利用更多CPU資源，Java中一個線程(Thread)就對應著不同操作系統下一個真實線程。因為Java虛擬機沒有實現線程調度，所以這些Java線程在不同操作系統調度下運行差異性也就比較明顯。例如在Windows系統中，不僅線程優先順序少於Java API參數規定十個優先順序，而且微軟明確反對程序員動態調整線程優先順序。即使在操作系統中有足夠優先權，讓線程優先順序參數和真實線程優先順序對應，不同操作系統調度方式也會有許多不同。這最終會造成代碼在不同平台上行為變得不可預測。這就很難滿足復雜、大規模並發任務眾多優先順序需求，從而很難達到用戶業務需要達到效果。

2. 由於在Java系統中，線程被包裝在一個Java語言對象類—Thread中，所以為了完成Java語言對象和操作系統線程對應，Java線程系統開銷還是比較大(在NT 4.0中，平均每個線程大致佔用30KB內存)。因此如果讓Thread對象個數和成千上萬任務數同比例增長，就顯然是不合理。

內容摘要：本文利用協調式多任務模型，提出一個與平台無關、並且能在任務間動態分配CPU資源方案。
綜上所述，根據並發多任務大規模需求和Java平台固有特點，想要利用Java Thread對象優先順序調整CPU資源分配是非常困難，所以應該盡量避免讓線程和任務直接對應，也盡量避免使用操作系統線程優先順序調度機制。

解決方案

根據以上分析，問題症結在於：多任務系統中任務在Java語言中對應以及任務間相互調度。

從本質上看，一個任務就是一系列對象方法調用序列，與JavaThread對象或者別類對象沒有必然聯系。在避免使用不同操作系統線程調度且同時Java虛擬機又沒有線程調度能力情況下，要想構造一個協調式多任務系統，讓各個任務相互配合就成了最直接思路。協調式多任務系統一般有以下特點：

1. 任務由消息驅動，消息響應代碼完成任務邏輯處理;

2. 消息隊列完成消息存儲和管理，從而利用消息處理次序體現任務優先順序不同;

3. 任務中耗時消息響應邏輯能夠主動放棄CPU資源，讓別任務執行(像Windows 3.1中Yield函數、Visual Basic中DoEvents語句)。

可能出於巧合，Java語言具有構造協調式多任務系統天然條件。Java對象方法不僅是一個函數調用，它還是一個java.lang.reflect.Method類對象。而所有對象方法都可以通過Method類invoke方法調用。如果能使每個任務所對應一系列方法全部以對象形式包裝成消息，放到消息隊列中，然後再按照自己優先順序演算法將隊列中消息取出，執行其Method對象invoke調用，那麼一個基本協調式多任務系統就形成了。其中，任務優先順序和線程優先順序沒有綁定關系。該系統主體調度函數可以設置成一個「死循環」，按照需要優先順序演算法處理消息隊列。對於有多重循環、外設等待等耗時操作消息響應函數，可以在響應函數內部遞歸調用主體調度函數,這一次調用把原來「死循環」改成在消息隊列長度減少到一定程度(或者為空)後退出。退出後，函數返回，執行剛才沒有完成消息響應邏輯，這樣就非常自然地實現了協調式系統中任務主動放棄CPU資源要求。

『叄』 什麼是動態規劃演算法，常見的動態規劃問題分析與求解

動態規劃中遞推式的求解方法不是動態規劃的本質，本質，是對問題狀態的定義和狀態轉移方程的定義。

『肆』 java如何實現m個資源動態分配到n個副本上

給定一組函數f1 ... fn(離散時間)和時間限制(int)，應找到最大輸出，即在不同函數之間分配時間以最大化所用函數輸出的總和。

對於任何函數，任何時候的值表示如果用於所述時間的函數的總輸出。 即F(2)=函數的總輸出，如果使用2秒。 不是F(1)+ F(2)。

所有值(時間，函數輸出)都是整數。

我的當前演算法通過檢查F(t)找到所有時間被放入一個函數的情況，將最大值與前一個最大M(t-1)+的所有可能輸出的最大值進行比較，找出可能損壞的最大值為每個可能的功能添加1秒(帶有已使用功能和時間的記錄)。
以上內容來源於網路。

『伍』 請教LTE下行資源分配

我的理解你的現在有這么幾個問題？一一列舉

1. 前一個TTI分配的PRB，下一個TTI會被釋放嗎或者重新分配嗎？

2. 釋放要多長時間？

3. 資源耗盡有什麼標志？

4. 如果一個TTI 30個UE，資源會不會無法耗盡？

5. 這是否是輪詢演算法？

我下面一個個回答：

1. 網路側的調度器負責資源的調度。LTE中調度在時域上的基本單位是一個TTI。前一個TTI分配的PRB，在下一個TTI是「重新」分配的，其實也沒有「重新」，因為每個TTI對應一個Harq ID。前後兩個TTI 屬於不同的Harq ID，調度的時候，不同的HarqID的TTI在同時依次調度。不存在釋放，或者重新分配的問題。LTE裡面的資源一直都是動態分配的，SPS的調度資源分配看上去佔用一段時間，但是也不會一直佔用下去。打個比喻，每個PRB就是教學樓裡面的教室。學校規定了，每個教室大家只能使用1個小時，大家依次使用。不存在釋放的說法？因為大家都是按照規定這么做的。

2. 問題2，參見1.

3. 資源耗盡沒有什麼特別的標志。DCI裡面的RB assignment能夠看出來。比如，50個PRB，RA type 0的時候，需要17個比特來表示。那麼著17個比特全部為1，就表示分配完了。但是由於很可能有多個UE同時存在，即使某個UE的RB assignment沒有全部分配完，也不能說明什麼。總之UE是不清楚的，當然eNB是可以根據DCI看出來的。

4. 不可能無法耗盡。首先，只要有需求，資源的分配不會浪費。即使eNB內只有1個UE，只要UE的高層有足夠的數據需求，eNB很可能會把所有資源分配給一個UE。

5. 輪詢演算法是輪詢的是UE之間的優先順序。從你的描述上看，可以算是輪詢演算法。

不知道這么解釋是否有幫助。

總結一下：

• LTE中的資源分配都是動態分配的。UE佔用時頻資源按照高層的需求，按照調度器的演算法依次分配。當然實際調度的時候，按照演算法UE有優先順序，數據按照業務類型也有優先順序。

• LTE中的調度演算法常見的有：輪詢，最大載干比，比例均衡等演算法。

『陸』 在動態分區分配方式中，可利用哪些分區分

連續分配：首次適應演算法（較快，簡單，碎片多），最大適應分配演算法（以期不留下小碎片），最佳適應分配演算法（慢，復雜，碎片少）。都需要碎片整理。離散分配：分段管理（邏輯性好），分頁管理，段頁式管理.動態分區分配演算法：1.首次適應演算法（FF/firstfit）2.循環首次適應演算法（nextfit）3.最佳適應演算法（bestfit）從最小的分區開始分配4.最壞適應演算法（worstfit）從最大的分區開始分配5.快速適應演算法/分類搜索法(quickfit)將空閑分區根據其容量的大小進行分類

『柒』 分配動態數組空間時有時成功有時失敗是什麼原因

cd = (char *) malloc(sizeof(char) * n);
如果要求的空間數值 n 太大，內存不夠，則會失敗。
如果 n 沒有預先給定數值， 或給了 負值 ，則會失敗。
如果 在循環語句中 做動態分配，cd 已分配過 一次，沒有 free(cd) 釋放，又再次分配，則會失敗。
重復分配，無論增加空間或減小空間 可以 用 realloc() , 不用 malloc。
計算機資源共享，多程序都要用內存，當別的程序需要的空間增大時，剩餘空間不夠你的程序用時，也會失敗。 所以分配時，要用返回值 監測 是否成功，並處理。

『捌』 為什麼採用有序資源分配法不會產生死鎖

因為有序方法不會造成資源形成循環等待：即A資源使用者等待B資源，而B資源使用者等待A資源，這樣就造成死鎖。

具體為如果有序方法：取得A資源後方可獲取B資源，那麼就不會出現B資源被使用卻在等待A資源.所以就不會產生死鎖。

系統要求申請進程：

1、對它所必須使用的而且屬於同一類的所有資源，必須一次申請完；

2、在申請不同類資源時，必須按各類設備的編號依次申請。

這種演算法資源按某種規則系統中的所有資源統一編號（例如列印機為1、磁帶機為2、磁碟為3、等等），申請時必須以上升的次序。

(8)動態資源分配演算法常見問題擴展閱讀：

1、資源的靜態分配

系統對作業一級採用資源靜態分配方法。當一個進程（或程序）運行前，將它要求的資源一次分配給該進程，直到該進程終止，釋放其佔用的所有資源。效率太低。

2、資源的動態分配

系統對進程一級採用資源動態分配方法。系統在進程運行中，根據進程提出的資源需求，進行資源的動態分配和回收。資源利用率提高，但有可能造成死鎖。

『玖』 關於C語言動態規劃 資源分配問題演算法的分析

動態規劃演算法一般是n步疊代計算局部最優解，每一步疊代需要計算m個子項，那麼時間復雜度就是O(m*n)。

如果只保存一步疊代的結果，空間復雜度就是O(m)；如果需要保存k步疊代結果，空間復雜度就是O(m*k)。