操作系统--处理机调度与死锁

• 处理机调度的层次和目标
  • 　　处理机调度的层次
    • 　　高级调度：对象是作业，功能：根据某种算法决定将外存上处于队列的哪几个作业调用内存，为他们创建进程、分配资源、放入就绪队列。--》用于多道批处理系统
    • 　　低级调度（进程调度）：功能：根据某种算法决定就绪队列的那个进程获得处理机，并且将处理机分配给进程。--》多道批，分时，实时系统
    • 　　中级调度（内存调度）：作用：提高内存利用率和系统吞吐量。功能：把暂时不能运行的进程调至外存等待，当他们具备运行条件且内存有空闲，再调入内存变为就绪状态。
      
      
  • 　　目标
    
    • 　　批处理系统目标：周转时间短，系统吞吐量大，处理机利用率高。
    • 　　分时系统：响应时间快，均衡性
    • 　　实时系统：截止时间保证，可预测性
      
      
      
• 调度算法：
  • 　　先来先服务FCFS
    • 　　思想：按照作业到达的先后次序进行调度。    优先考虑在队列中等待最长的作业，从后背队列中选择几个，将他们调入内存，为他们分配资源和创建进程，然后放入就绪队列中。
    • 　　实现代码（C++语言）
      
      
  • 　　短作业优先SJF
    • 　　思想：以作业的执行时间的长短来计算优先级。从外存中选取若干个估计运行时间最短的作业，将他们调入内存运行。
    • 　　实现代码（C++语言）
      
      
  • 　　高响应比优先调度算法
    • 　　思想：即安装作业的等待时间又按照作业的要求服务时间来进行调度。综合了fcfs和sjf两个算法的优点。根据优先权进行调度，优先权=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间。响应时间：进程进入到运行结束出来的总时间。当作业的等待时间相同的时候类似SJF，执行时间短的先调度；当作业的执行时间相同时，类似FCFS,等待时间长的先调度。
    • 实现代码（C++语言）
      
      
      
• 进程调度
  • 　　几个术语概念：周转时间：作业到达到作业完成的时间。带权周转时间：周转时间/服务时间。
  • 　　调度任务：保存处理机的现场信息，便于还原；按某种算法选择进程；把处理器分配给内存。
  • 　　进程调度方式：
    • 　　非抢占式：一直运行，不会因为时钟中断或者其他原因被抢占处理机，除非该进程运行完成或者进程阻塞。非抢占式可以被抢占的几种情况：①进程完成或者因某事件无法执行②正在执行的进程提出I/O请求，处理机可以去执行别的操作。
      
      
    • 　　抢占式：根据某种原则进行处理机的调度。抢占原则：①优先权原则②短进程优先③时间片原则。
      
      
  • 　　时间片轮转调度算法
    
    • 　　原理：各个进程的优先级是一样的。给定一个固定的时间片，按照进程进入的时间顺序进行调度，当一个时间片执行完就让下一个进程调度处理机，依次执行，知道所有进程执行完毕。
    • 　　举例：P94.
      
      
  • 　　优先级调度算法
    • 　　非抢占式优先级调度算法：把处理机赋予给进程中优先级最高的进程，直至该进程完成或者因某事件进程停止执行。
    • 　　抢占式优先级调度算法：把处理机赋予给进程中优先级最高的进程，一直执行，直到出现优先级比这个进程还高的进程，处理机赋予给新的进程。
      
      
    • 　　优先级类型：静态优先级：在创建进程时创建，在运行期间保持不变。   动态优先级：在创建进程时创建，动态改变。
      
      
      
• 死锁概述
  • 　　资源
    • 　　可重用性资源：
      • 　　①只能分配给一个进程使用。②使用资源时顺序：请求资源，使用资源，释放资源。③资源时固定的，不能创建也不能删除。
    • 　　消耗性资源：会引起死锁。
    • 　　抢占式资源：可以被抢占的资源，不会引起死锁。
    • 　　非抢占式资源：不能被抢占，只能在进程完成后自行释放。会引起死锁。
      
      
  • 　　死锁
    
    • 　　引起的原因：竞争不可抢占资源引起死锁。竞争消耗性资源引起死锁。进程推进顺序不当。
    • 　　死锁的定义：每个进程锁等待的事件是该组中的其他进程释放所占有的资源。
    • 　　死锁的条件：
      ①互斥条件：一个资源一段时间只能一个进程使用，当有别的进程想调用的时候，必须的鞥该进程释放该资源才能调用。
      ②请求和保持条件：进程已经占有一个资源，又提出一个新的资源请求，新的资源被占有，请求进程被阻塞，自己拥有的资源又不释放。
      ③不可抢占：自己的资源不能被占有。
      ④循环等待：环状条件。
      
      
    • 预防死锁
      • 　　破坏请求和保持条件：当一个已经拥有资源的进程去请求资源时，它持有的资源不能是不可抢占的资源。
      • 　　破坏不可抢占资源：已经有不可抢占资源的进程去请求新的资源而不能得到满足时候，必须释放自己已经拥有的资源，待以后需要的时候再重新申请。
      • 　　破坏循环等待条件：对所有的资源实行线性排序，
        
        
        
    • 　　避免死锁
      
      • 　　银行家算法
        
        银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
        设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
        (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
        (2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
        (3)系统试探分配资源，修改相关数据：
        AVAILABLE[i]-=REQUEST[cusneed][i];
        ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
        NEED[cusneed][i]-=REQUEST[cusneed][i];
        (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

        银行家算法安全性检查算法

        （1)设置两个工作向量Work=AVAILABLE;FINISH
        (2)从进程集合中找到一个满足下述条件的进程，
        FINISH==false;
        NEED<=Work;
        如找到，执行（3)；否则，执行（4)
        (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
        Work=Work+ALLOCATION;
        Finish=true;
        GOTO 2
        (4)如所有的进程Finish= true，则表示安全；否则系统不安全。
        
        
        
  • 　　死锁的检测和解除
    •