1 资源管理概述
 
1.1 资源管理的目的和任务
 
目的：
 1、保证资源的高利用率；
 2、在“合理”时间内使所有顾客有获得所需资源的机会；
 3、对不可共享的资源实施互斥使用；
 4、防止由资源分配不当而引起的死锁。
 
对资源的管理应包括以下几个方面：
 1、资源管理的描述－－数据结构
 2、确定资源的分配原则和调度原则
 3、执行资源分配（实施）
 4、存取控制和安全保护
 
1.2 资源的几种分类方法
 
（一）物理资源和程序资源
 （二）单一访问入口的资源和多访问入口的资源
 （三）等同资源
 （四）虚拟资源
 
1.3资源管理的机构和策略
 
机构
 进行资源分配所必需的基本部件,它包括描述资源状态的数据结构，还包括保证不可共享资源互斥使用的技术以及对不能满足的资源请求进行排队的手段等。
 
策略
 给出机构所使用的方法，涉及到相应资源满足的情况下，批准请求的决策，包括死锁问题和系统平衡问题。
 
2 资源分配机构
 
描述资源的管理和控制信息的数据结构称为资源分配的机构 。
 在教材上列出了两种：资源描述器、资源信息块
 在实际的系统中，会根据实际需要设计相应的数据结构。例如：进程管理主要管理的机构：PCB、就绪队列和各种等待队列。
 
2.1 资源描述器
 
描述各类资源的最小分配单位的数据结构称为资源描述器rd（resource descriptor）
 存放于一个描述器中的信息取决于资源的特征与对该资源的管理方式。
 最简化的描述器可以用一个二进制位来实现，它表示该资源是可用的，还是已分配的。
 
2.2 资源信息块
 
资源信息块rib (resource information)是一个数据结构，应能说明资源、请求者以及实施分配所需的必要信息。
 资源分配程序是接收分配命令把资源分配给请求者的例程。包括：分配程序和去分配程序。
 
3资源分配策略
 
3.1 概述
 
资源分配有两种方式：
 静态分配：当一个进程（或程序）运行前，将它要求的资源一次分配给该进程，直到该进程终止，释放其占用的所有资源。这种分配方法效率太低；
 动态分配：当一个进程要求使用某个（类）资源时，向系统提出资源的请求，系统响应程序的请求将某种资源分配给请求者，这种方法使得系统资源的利用率提高，但有可能造成死锁。
 几种分配策略：
 1、先请求先服务（FIFO）
 2、优先调度
 3、适应调度
 4、均衡调度
 5、针对设备特性的调度
 
3.2 先请求先服务（FIFO）
 
简单排队站策略或FIFO（First In First Out）策略。
 按照进程就绪的先后次序来调度进程
 优点:实现简单
 缺点:没考虑进程的优先级
 
3.3 优先调度
 
在优先调度策略下，对于每个进程（或作业）要指定一个优先级，这一优先级反映了进程要求处理的紧迫程度。
 进程调度队列是按进程的优先级由高到低的顺序排列的，队首为优先级最高者。
 优先选择就绪队列中优先级最高的进程投入运行
 优先级根据优先数来决定。
 
确定优先数的方法
 静态优先数法：
 在进程创建时指定优先数，在进程运行时优先数不变
 动态优先数法：
 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。
 
两种占用CPU的方式
 可剥夺式（可抢占式Preemptive）：
 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用
 不可剥夺式（不可抢占式Non-preemptive ）：
 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去
 
分时系统中常用时间片轮转法
 
时间片选择问题：
 固定时间片
 可变时间片
 
与时间片大小有关的因素：
 系统响应时间
 就绪进程个数
 CPU能力
 
多队列反馈调度算法：
 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，…当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列 。
 
 
首先系统中设置多个就绪队列
 
 
每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大
 
 
各个队列按照先进先出调度算法
 
 
一个新进程就绪后进入第一级队列
 
 
进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列
 
 
当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾
 
 
当第一级队列空时，就去调度第二级队列，如此类推
 
 
当时间片到后，进程放弃CPU，回到下一级队列
 
 
进程调度的时机
 当一个进程运行完毕，或由于某种错误而终止运行
 当一个进程在运行中处于等待状态（等待I/O）
 分时系统中时间片到
 
 
*进程调度的时机
 当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪。
 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）
 
*CPU调度过程
 
保存现场：顺序保存，最后一步保存PSW
选择要运行的程序
 （如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其他进程时该进程一直运行,在执行过程中可接收中断）
恢复现场：最后一步恢复选中进程的PSW
 
4 死锁
 
4.1 死锁的概念
 
在这两个进程并发执行时，当P1进程占有R1、P2进程占用R2时，P1要求R2，由于P2已占R2有而得不到，P1进程只有等待；P2申请R1，由于P1已占有R1，而得不到，P2进程只有等待，就出现了死等的情况。
 
 死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出来的。它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上，死锁问题不仅在计算机系统中存在，在我们日常生活中它也广泛存在。
 在计算机系统中，涉及软件，硬件资源都可能发生死锁。例如：系统中只有一台CD-ROM驱动器和一台打印机，某一个进程占有了CD-ROM驱动器，又申请打印机；另一进程占有了打印机，还申请CD-ROM。结果，两个进程都被阻塞，永远也不能自行解除。
 
死锁简单的定义：
 死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所处的一种系统状态。
 教材上关于死锁的定义：
 两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。
 
4.2 死锁的起因
 
并发进程共享系统资源，在竞争资源时可能会产生称为死锁的附带后果。
 产生死锁的根本原因是系统能够提供的资源个数比要求该资源的进程数要少。所以，当系统中两个或多个进程没有能力进一步时。系统就发生死锁。
 A1: P1 request(r1) A2: P2 request(r2)
 B1: P1 request(r2) B2: P2 request(r1)
 C1: P1 request(r1) C2: P2 request(r2)
 D1: P1 request(r2) D2: P2 request(r1)
 
 第一条折线：p1运行，p2运行。
 p1运行 A1: P1 request(r1)，B1: P1 request(r2)
 C1: P1 request(r2)，D1: P1 request(r1)
 p2运行 A2: P2 request(r2)，B2: P2 request(r1)
 C2: P2 request(r2)，D2: P2 request(r1)
 
第二条折线：p1运行，p2运行， p1运行 。
 p2运行 A2: P2 request(r2)，B2: P2 request(r1)
 C2: P2 request(r2)，D2: P2 request(r1)
 p1运行 A1: P1 request(r1)，B1: P1 request(r2)
 C1: P1 request(r1)，D1: P1 request(r2)
 
第三条折线：p1运行，p2运行。
 p1运行 A1: P1 request(r1)；
 p2运行 A2: P2 request(r2)，进入D区；
 p1运行 B1: P1 request(r2)，p1阻塞；
 p2运行 B2: P2 request(r2)，p2阻塞，到达死锁点N。
 在此种情况下出现死锁。
 
产生死锁的原因是：系统资源不足；进程推进顺序非法。
 
产生死锁的四个必要条件：
 1、互斥条件
 2、不可剥夺条件
 3、部分分配
 4、环路条件
 
 
4.3 解决死锁问题的策略
 
一、解决死锁问题的几个策略
 为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。
 条件1：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；
 条件2：容易否定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。
 条件3：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。
 条件4：实际上系统不采用部分分配，也就破坏了环路条件。
 
二、系统状态分析（略）
 
4.4 死锁的预防
 
预先分配一个进程要用的所有资源是防止死锁的一种安全而简单的方法，但设备的使用效率太低。其缺点也是明显的：
 1、一个用户（进程）在程序运行之前很难提出将要使用的全部设备；
 2、设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分支语句。
 
4.5 死锁的避免
 
为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则拒绝分配。
 预防死锁：
 采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁；
 死锁避免：
 是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能产生死锁的某个资源的请求。
 一、有序资源分配法
 这种算法按某种规则为系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。
 系统要求申请进程：
 1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；
 2、在申请不同类资源时，必须按各类设备的编号依次申请。
 例如：进程PA，使用资源的顺序是R1，R2；
 进程PB，使用资源的顺序是R2，R1；
 若采用动态分配有可能形成环路条件，造成死锁。
 采用有序资源分配法：R1的编号为1，R2的编号为2；
 PA：申请次序应是：R1，R2
 PB：申请次序应是：R1，R2
 这样就破坏了环路条件，避免了死锁的发生。
 
二、银行家算法
 避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法：
 该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。
 这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。
 
4.6 死锁的检测和恢复
 
死锁的检测：
 通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间。在UNIX系统中有命令PS可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁。
 死锁排除的方法：
 1、撤销陷于死锁的全部进程；
 2、逐个撤销陷于死锁的进程，直到死锁不存在；
 3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。

资源分配问题
 
 
 
  大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客
 
 
 
  
本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！
 
 
 
 
博主目前仅在CSDN中写博客，唯一博客更新的地址为：亓官劼的博客
 
 
 
 
题目
 
某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的3个工厂A，B，C， 各工厂在获得这种机器后，可以为国家盈利的情况如表1所示。问：这5台机器如何分配给各工厂，才能使得国家利益最大？
 
利益表：
 

  <
 

 

  

   
S
   
A
   
B
   
C
  
 
 

 
5G资源分配
 
控制区域资源分配
数据区资源分配


 5G的资源分配，从整体上看与4G类似，分为控制区域的资源分配和数据区域的资源分配。

 控制区域即PDCCH占用的资源，数据区域即PDSCH和PUSCH。
 
控制区域资源分配
 
总结：网络通过在系统消息和RRC消息中配置PDCCH-config -> search space -> CORESET 给UE分配控制区资源和DCI解码信息。
 在4G中，PDCCH所占用的频域资源是整个带宽（去除参考信号和PHICH）；而时域占用的符号数由PCFICH确定。
 5G中去掉了PCFICH和PHICH，引入了CORESET的概念。CORESET就是定义5G PDCCH占用资源的一组参数。
 5G中由于BWP和numerology的引入，PDCCH占用的资源与4G相比变得更加灵活，系统可以为UE独立配置CORESET，并且一个UE可以配置多个CORESET。
 
 CORESET由RRC层的IE： ControlResourceSet定义。
 
ControlResourceSet ::=                  SEQUENCE {
    controlResourceSetId                    ControlResourceSetId,    //CORESET ID
    frequencyDomainResources                BIT STRING (SIZE (45)),  //频域资源
    duration                                INTEGER (1..maxCoReSetDuration),   //时域资源
 
CORESET定义了PDCCH占用的资源，而为了解码PDCCH中所承载的DCI信息，5G中同样定义了search space的概念。
 search space根据承载的DCI信息分为common search space和specific search space。
 
 common search space是UE建立RRC连接之前网络在系统消息中为UE配置的UE需要解码的一些DCI信息。
 specific search space是UE建立RRC连接之后在RRC消息中为UE配置的DCI消息。
 在search space配置中可以看到对应CORESET ID。
 
SearchSpace ::=                         SEQUENCE {
    searchSpaceId                           SearchSpaceId,   //ID
    controlResourceSetId                    ControlResourceSetId    OPTIONAL,-- Cond Setup Only    //CORESET ID
    monitoringSlotPeriodicityAndOffset CHOICE {
 
具体到消息中，search space和CORESET又通过PDCCH-config下发到UE。
 
PDCCH-Config ::=                        SEQUENCE {
    controlResourceSetToAddModList          SEQUENCE(SIZE (1..3))
                                                OF ControlResourceSet         OPTIONAL,
    controlResourceSetToReleaseList         SEQUENCE(SIZE (1..3))
                                                OF ControlResourceSetId       OPTIONAL,
    searchSpacesToAddModList                SEQUENCE(SIZE (1..10))
                                                OF SearchSpace                OPTIONAL,
    searchSpacesToReleaseList               SEQUENCE(SIZE (1..10))
                                                OF SearchSpaceId              OPTIONAL,
 
数据区资源分配
 
总结：通过DCI分配时域和频域资源。
 数据区资源分配与4G类似，是通过DCI完成的。不同的地方在于，5G中时域的调度粒度从一个slot变成了一个symbol。
 我们前面说RB的定义的时候也说过，5G中RB在时域上只有一个symbol。
 因此，5G的资源分配在频域上与4G类似，但是却要增加时域上的分配参数。
 
 时域的分配方式如上图。
 其中，n为DCI所在slot，uPDSCH和uPDCCH分别为PDSCH和PDCCH的numerology。
 K0是在RRC层配置的参数，通过DCI指定具体的K0值，从而获得PDSCH所在slot。另外还有K1用于配置PUCCH传输ACK/NAK的slot，K2用于配置PUSCH的slot。
 SLIV也是RRC层配置的参数，指定了PDSCH的其实symbol和持续长度。
 
参考：
 关于5G 物理层设计原则
 https://new.qq.com/omn/20180312/20180312G19BM2.html
 http://www.txrjy.com/thread-1027912-1-1.html
 关于资源分配：
 https://rf.eefocus.com/article/id-333172
 http://sharetechnote.com/

资源分配图是死锁的一种准确而形象地描述，通过资源分配图，可以对当前系统资源分 配和申请情况一目了然，便于对死锁进行分析并采取对策。
 
一、资源分配图
 
资源分配图是一张有向图，一个系统资源分配图SRAG (System Resource Allocation Graph)可定义为一个二元组，即SRAG= (V, E)，其中V是顶点的集合，而E是有向边的集合。顶点集合可分为两种部分：P= (P1,P2,…,Pn)，是由系统内的所有进程组成的集合，每一个P代表一个进程；R = (r1,r2,…,rn)，是系统内所有资源组成的集合， 每一个r代表一类资源。
 
在有向图中，用圆圈表示进程，用方框表示每类资源。每一类资源r,可能有多个实例， 可用方框中的圆点（实心圆点）表示各个资源实例。申请边为从进程到资源的有向边，表示进程申请一个资源，但当前该进程在等待该资源。分配边为从资源到进程的有向边，表示 有一个资源实例分配给进程。注意：一条申请边仅指向代表资源类的方框，表示申请时不 指定哪一个资源实例，而分配边必须由方框中的圆点引出，表明哪一个资源实例已被占有。
 
当进程P,请求资源类r的一个实例时，将一条请求边加人资源分配图，如果这个请求是 可以满足的，则该请求边立即转换成分配边；
 
当进程随后释放了某个资源时，则删除分配边。图5-10是一个资源分配图的示例。
 
图5-10给出的内容如下。
 
集合P，R，E分别为：
 
P = {P1,P2,P3} R = { r1, r2, r3, r4}
 
E = {< P1,r1>,< P2,r2>，< r1,P2>，< r2,P3>，< r3,P1 >，< r3,P2>}
 
资源实例个数为：
 
I r1|= 1,| r2 | =1,| r3 | =2,| r4 | =3
 
进程状态如下
 
(1)进程h已占用一个r3类资源，且正在等待获得一个r1类资源。
 
(2)进程P2已占用r1和r3类资源各一个且正在等待获得一个r2类资源。
 
(3)进程P3已占用一个r2类资源。
 
二、死锁定理
 
基于上述资源分配图的定义，可给出判定死锁的法则，又称为死锁定理。
 
(1)如果资源分配图中没有环路，则系统没有死锁。
 
(2)如果资源分配图中出现了环路，则系统中可能存在死锁。
 
①如果处于环路中的每个资源类中均只包含一个资源实例，则环路的存在即意味着死 锁的存在。此时，环路是死锁的充分必要条件。
 
②如果处于环路中的每个资源类中资源实例的个数不全为1，则环路的存在是产生死锁 的必要条件而不是充分条件。
 
以图5-11中的资源分配图为例，假设此时进程P3申请一个r3类资源，由于此时r2已没有可用资源，于是在图中加人一条新的申请边< P3, r3>，如图5-11所示。
 
此时，资源分配图中有两个环路：
 
P1—>r1—>P2—>r2—>P3—>r3—>P1
 
P2 —>r2 —>P3 —>r3 —>P2
 
显然，进程P1,P2,P3都陷入了死锁，因为进程P3正在等待进程P1或P2释放r3类资源中的—个实例，但P2又在等待P3释放r2, P1又在等待P2释放r1。
 
在图5-12所示的资源分配图中也存在一个环路：
 
P1—>r1一>P3一>r2一>P1
 
但系统没有产生死锁，因为当P4释放了一个r2类资源后，可将它分给P3或者P2释放 一个r1类资源后将它分给P1，这两种情况下环路都消失了，因而不会发生死锁。
 
由此可见，资源分配图中有环路，则可能发生死锁，也可能没有死锁。
 
三、资源分配图化简方法
 
可以利用资源分配图化简方法，来检测系统是否为死锁状态。
 
所谓化简是指若一个进程的所有资源请求均能被满足，可以设想该进程得到其所需的全部资源，最终完成任务，运行完毕，并释放所占有的全部资源。在这种情况下，则称资源分配图可以被该进程化简。假如一个资源分配图可被其所有进程化简，那么称该图是可化简的，否则称该图是不可化简的。
 
化简方法如下：
 
(1)在资源分配图中，找出一个既非等待又非孤立的进程结点Pi，由于Pi可获得它所需要的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去Pi所有的申请边和分配边，使之成为既无申请边又无分配边的孤立结点。
 
(2)将Pi所释放的资源分配给申请它们的进程，即在资源分配图中将这些进程对资源的申请边改为分配边。
 
(3)重复1)、2)两1步骤，直到找不到符合条件的进程结点。
 
经过化简后，若能消去资源分配图中的所有边，使所有进程都成为孤立结点，则该图是可完全化简的；否则为不可化简的。
 
对于较复杂的资源分配图，可能有多个既非等待、又非孤立的进程结点，不同的简化过程是否会得到不同的化简图呢？可以证明，所有的化简顺序将导致相同的不可简化图。同样可以证 明，系统处于死锁状态的充分条件是，当且仅当该系统的资源分配图是不可完全简化的。
 
以图5-11和图5-12为例，说明资源分配图的化简过程以及得出的结论。在图5-11中， 找不到任何一个既非等待、又非孤立的进程结点，所以该资源分配图是不可化简的，根据上述介绍，该系统发生了死锁。在图5-12中，首先找到既非等待、又非孤立的P4结点，消去其分配边，得到一个可用的资源r2，由于P3有一条对r2的申请边，可将该资源分配给P2, 即将P2的申请边改为分配边。在得到的新的资源分配图中，可以找到既非等待、又非孤立的进程结点P3，继续将相应的分配边消去，并将P1对r1的申请边改为分配边；……最终资 源分配图中的所有进程结点都变成孤立结点，资源分配图是可化简的，所以可以得出结论， 该系统没有发生死锁。在图5-11中，可以先挑出进程结点P2，结论是一致的。