动态资源分配算法常见问题

‘壹’ 操作系统存储器动态分区分配的(快速适应算法)问题

这里的分割指的是：如果空闲分区大小为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)。